communities.cpp

#include <algorithm>
#include <fstream>
#include <sstream>
#include <iostream>

#include <boost/foreach.hpp>
#include <boost/format.hpp>

#include "communities.h"

using namespace std;

Community::~Community() {
    if (set == NULL) delete set;
}

Communities::Communities(igraph_t *graph) {
    // salviamo il puntatore al grafo
    this->graph = graph;

    // Vogliamo copiare i gradi in un array
    unsigned int vc = igraph_vcount(graph);

    igraph_vector_t degree;
    igraph_vector_init(&degree, vc);

    // per quanto riguarda igraph_vss_1, la guida di igraph
    // dice che è immediato, e può essere usato senza preoccuparsi di distruggerlo
    igraph_degree(graph, &degree, igraph_vss_all(), IGRAPH_ALL, false);

    // creiamo l'array e lo popoliamo
    degrees = new unsigned int[vc];
    for (unsigned int i = 0; i < vc; i++) degrees[i] = VECTOR(degree)[i];
    igraph_vector_destroy(&degree);

    // questa è una costante ricorrente
    factor = 0.5 / ((double) igraph_ecount(graph));
}


Communities::~Communities() {
    delete[] degrees;
    delete[] membership;

    // non possiamo fare il delete di altre cose, perché parte sono condivise.
    // si usa sync quando si vuole fare pulizia tra una copia e l'altra,
    // si usa free quando si vuole fare pulizia prima di cancellare TUTTE le
    // istanze
}

Communities::Communities(const Communities &c) {
    this->graph = c.graph;
    this->communities = c.communities;
    this->counter = c.counter;
    this->keys = c.keys;
    this->factor = c.factor;

#ifdef EQ_HARD
    this->mmap = c.mmap;
#endif

    unsigned int vs = igraph_vcount(graph);
    this->degrees = new unsigned int[vs];
    this->membership = new unsigned int[vs];
    for (unsigned int i = 0; i < vs; i++) {
        degrees[i] = c.degrees[i];
        membership[i] = c.membership[i];
    }
}

void Communities::free() {
    BOOST_FOREACH(CID c, keys) {
                    delete communities[c];
                }
}

void Communities::sync(Communities &b) {
    set<CID> toDelete;

    std::set_difference(keys.begin(), keys.end(), b.keys.begin(), b.keys.end(),
                        std::inserter(toDelete, toDelete.begin()));

    BOOST_FOREACH(CID c, toDelete) {
                    delete communities[c];
                }
}


bool Communities::has(CID i) {
    return keys.find(i) != keys.end();
}

////////////////////////////////////////////////////////////////////////////////
// utilità
////////////////////////////////////////////////////////////////////////////////
// FIXME: inserire il controllo degli errori
unsigned int Communities::getCommunityInternalEdges(unsigned int s) {
    int err;

    igraph_vector_t *v = communities[s]->toVector();
    igraph_vs_t *vs = communities[s]->toVertexSelector(v);

    //creazione sottografo dal vertex_selector;
    igraph_t subgraph;
    err = igraph_subgraph(graph, &subgraph, *vs);

    // quello che ci interessa realmente
    unsigned int e = igraph_ecount(&subgraph);

    // queste funzioni non restituiscono niente
    igraph_vs_destroy(vs);
    igraph_vector_destroy(v);
    delete vs;
    delete v;
    igraph_destroy(&subgraph);

    return e;
}

// FIXME: inserire il controllo degli errori
unsigned int Communities::getCommunityBoundaryEdges(unsigned int s) {
    int err;
    unsigned int o = 0;

    igraph_vector_t *v = communities[s]->toVector();
    igraph_vs_t *vs = communities[s]->toVertexSelector(v);

    igraph_vit_t vit;
    igraph_vit_create(graph, *vs, &vit);

    unsigned int cSize = communities[s]->set->size();

    igraph_vector_ptr_t p;
    err = igraph_vector_ptr_init(&p, cSize);
    err = igraph_neighborhood(graph, &p, *vs, 1, IGRAPH_ALL, 1);
    // la componente i-esima di p contiene l'elenco di vicini di ordine 1
    // dell'i-esimo nodo della community (quindi anche sé stesso)

    //conteggio edge che escono dalla community
    for (unsigned int i = 0; i < cSize; i++)  //per ogni vertice della community
    {
        igraph_vector_t *vv = (igraph_vector_t *) igraph_vector_ptr_e(&p, i);

        // per ogni vertice vicino di i
        for (int l = 0; l < igraph_vector_size(vv); l++) {
            //se non appartiene alla community, incrementa o
            if (!ownership(VECTOR(*vv)[l], s))
                o++;
        }
    }

    igraph_vit_destroy(&vit);
    igraph_vs_destroy(vs);
    igraph_vector_destroy(v);
    delete vs;
    delete v;

    igraph_vector_ptr_destroy(&p);

    return o;
}

void Communities::load(std::istream &s) {
    // TODO: pulire la struttura dati prima di fare il load
    unsigned int cSize;
    s >> cSize;

    for (unsigned int i = 0; i < cSize; i++) {
        unsigned int iSize;
        s >> iSize;

        NodeSet *nsp = new NodeSet;
        Node aux;

        for (unsigned int j = 0; j < iSize; j++) {
            s >> aux;

            // calcola membership automaticamente
            nsp->insert(aux);
        }

        addCommunity(nsp);
    }
}

void Communities::dump(std::ostream &s) {
    s << size() << endl;

    BOOST_FOREACH(unsigned int i, keys) {
                    // K n1 n2 .. nK\n
                    unsigned int size = getCommunitySize(i);

                    // commentato perché voglio che usi gli id anziché label..
                    /*
                    igraph_vector_t* v = communities[i]->toVector();
                    igraph_vs_t*    vs = communities[i]->toVertexSelector(v);
                    igraph_strvector_t result;
                    igraph_strvector_init(&result, size);

                    igraph_cattribute_VASV(graph, "label", *vs, &result);
                    */
                    s << size;
                    BOOST_FOREACH(Node n, *communities[i]->set) s << " " << n;
                    s << endl;

                    /*
                    igraph_strvector_destroy(&result);
                    igraph_vs_destroy(vs);
                    igraph_vector_destroy(v);
                    delete vs;
                    delete v;*/
                }
}

////////////////////////////////////////////////////////////////////////////////    
// Metodi di supporto a GCE e EAGLE
////////////////////////////////////////////////////////////////////////////////
// ho rimosso il parametro graph, tanto gli viene passato al costruttore
int Communities::setCommunities(string fileName) {
    counter = 0;
    ifstream f1(fileName.c_str());

    if (!f1) {
        return -1;
    }

    communities.clear();

    string s;
    string sub;

    while (f1.good()) {
        //legge tutta la riga dal file e la mette nella variabile s
        getline(f1, s);

        if (s.length() == 0)
            continue;

        NodeSet *ns = new NodeSet;
        //unsigned int vs = igraph_vcount(graph);

        //Estrapolazione interi dalla stringa s
        istringstream iss(s);

        while (iss.good()) {
            unsigned int node;

            iss >> node;
            //node--;
            //cout << node << " < " << vs << " == " << (node < vs) << endl;
            //assert(node < vs);
            ns->insert(node);
        }
        //cout << "Inserisco tutto e speriamo" << endl;
        addCommunity(ns);
    }

    // ricordarsi di chiamare
    return 0;
}


////////////////////////////////////////////////////////////////////////////////
// Metodi di supporto ad EAGLE
////////////////////////////////////////////////////////////////////////////////
CID Communities::registerCommunity(CommunityPtr c) {
    CID r = counter++;
    communities[r] = c;
    keys.insert(r);

    return r;
}

CID Communities::addCommunity(NodeSet *s) {
    CommunityPtr c = Community::spawn();
    c->set = s;

    CID r = registerCommunity(c);

    BOOST_FOREACH(Node n, *c->set) {
                    membership[n]++;
#ifdef EQ_HARD
                    mmap[n].insert(r);
#endif
                }

    c->communitySize = getCommunitySize(r);
    c->communityInternalEdges = getCommunityInternalEdges(r);
    c->communityBoundaryEdges = getCommunityBoundaryEdges(r);

    return r;
}

CID Communities::addCommunity(igraph_vector_t *vector) {
    // Creiamo una nuova community
    CommunityPtr c = Community::spawn();
    c->set = new NodeSet;
    CID r = registerCommunity(c);

    // popoliamola
    int s = igraph_vector_size(vector);
    for (int j = 0; j < s; j++) {
        int node = VECTOR(*vector)[j];
        membership[node]++;
        c->set->insert(node);
#ifdef EQ_HARD
        mmap[node].insert(r);
#endif
    }

    return r;
}

CID Communities::addCommunity(unsigned int i) {
    // Creiamo una nuova community
    CommunityPtr c = Community::spawn();
    c->set = new NodeSet;

    // inseriamo la community nella lista
    CID r = registerCommunity(c);

    // Popoliamola
    membership[i]++;
    c->set->insert(i);
#ifdef EQ_HARD
    mmap[i].insert(r);
#endif

    return r;
}

void Communities::prepareForEAGLE() {
    unsigned int s = igraph_vcount(graph);

    communities.clear();
    keys.clear();

#ifdef EQ_HARD
    mmap.clear();
#endif

    membership = new unsigned int[s];
    for (unsigned int i = 0; i < s; i++) membership[i] = 0;

    counter = 0;
}

void Communities::precalculateData() {
    BOOST_FOREACH(CommunitiesMap::value_type
                          cp, communities)cp.second->update(graph, degrees, membership);
}

unsigned int Communities::merge(unsigned int a, unsigned int b, bool hasComms) {
    // m è la community unione
    CommunityPtr m = get(a)->unite(get(b));
    CID r = registerCommunity(m);

    // abbiamo bisogno della community intersezione per poter aggiustare il
    // vettore membership
    CommunityPtr is = get(a)->intersect(get(b));

    // questo fa cambiare membership, ed è necessario fare l'update di tutte le
    // communities che hanno questi nodi
    BOOST_FOREACH(Node n, *is->set)membership[n]--;
    delete is;

#ifdef EQ_HARD
    BOOST_FOREACH(Node n, *m->set) {
                    mmap[n].erase(a);
                    mmap[n].erase(b);
                    mmap[n].insert(r);
                }
#endif
    /*
    if (!hasComms)
    {
      delete get(a);
      delete get(b);
    }
    */
    communities.erase(a);
    keys.erase(a);
    communities.erase(b);
    keys.erase(b);


#ifdef EQ_HARD
    // qui mettiamo i CID delle communities da aggiornare
    set<CID> toUpdate;

    // popliamo update, prendendo tutte le communities che hanno nodi la cui
    // membership è cambiata (e questi per forza sono quelli dell'intersezione)
    BOOST_FOREACH(Node n, *m->set)
                    BOOST_FOREACH(CID cid, mmap[n])toUpdate.insert(cid);

    int upSize = toUpdate.size();
    CommunityPtr *temp = new CommunityPtr[upSize];
    int upc = 0;

    // a questo punto chiamiamo l'update solo su queste communities
    BOOST_FOREACH(CID cid, toUpdate)temp[upc++] = get(cid);

#pragma omp parallel for if (upSize > 10) default(shared)
    for (int iterator = 0; iterator < upSize; iterator++)
        temp[iterator]->update(graph, degrees, membership);

#else
    m->update(graph, degrees, membership);
#endif

    return r;
}

////////////////////////////////////////////////////////////////////////////////
// grim, forgotten and frostbitten
////////////////////////////////////////////////////////////////////////////////    
std::string Communities::summary(bool verbose, bool debug) {
    ostringstream s;
    s << "Dimensione: " << size() << endl;

    if (verbose) {
        s << "Elenco communities:" << endl;
        BOOST_FOREACH(CID c, keys) s << summary(c, debug) << endl;
    }

    return s.str();
}

std::string Communities::summary(CID i, bool debug) {

    ostringstream s;
    if (debug) s << i << " (" << communities[i] << "):";
    else s << i << ":";

    // procuriamoci il vertex selector
    igraph_vector_t *v = communities[i]->toVector();
    igraph_vs_t *vs = communities[i]->toVertexSelector(v);
    igraph_strvector_t result;
    unsigned int size = getCommunitySize(i);
    igraph_strvector_init(&result, size);

    igraph_cattribute_VASV(graph, "label", *vs, &result);

    for (unsigned int j = 0; j < size; j++)
        s << " " << STR(result, j);

    if (debug) {
        s << " - " << communities[i]->comdegree;
#ifdef EQ_HARD
        s << ", " << communities[i]->cf << ", " << communities[i]->dm;
#endif
    }

    igraph_strvector_destroy(&result);
    igraph_vs_destroy(vs);
    igraph_vector_destroy(v);
    delete vs;
    delete v;

    return s.str();
}