cluster.h

Go to the documentation of this file.

#ifndef CLUSTER_H_
#define CLUSTER_H_

#include <queue>
#include <vector>

#include <map>
#include <set>
#include <vector>
#include <fstream>
#include <iostream>

#include <stdarg.h>
#include "graph.h"
#include "density.h"
#include "seed.h"

#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"
#include "boost/tuple/tuple_io.hpp"

#include "ComponentsLoop.h"

namespace std {
template<class T >
class complex;}

using namespace std;

template <typename R>
class ClusterAlg
{
  public:
    virtual void calculate() = 0;
 
    static density<bidirected_t>* dens; 
  float get_Density(bidirected_t::graph* graph, const set < bidirected_t::vertex >* cluster)
  {      
      set < bidirected_t::vertex >::iterator it;
      it = cluster->begin();
      
      //Create a seed with the first vertex
      seed calc(dens, *graph, *it);
      
      //Add the remaining vertices to the seed. 
      for (++it; it != cluster->end(); ++it)
      {
        calc.add_vertex(*it);
      }
        
      //Calculate density
      return calc.dens();
  }
  
  float get_Density(set <lui>* cluster){
    double win = 0, wout = 0;
    
    set <lui>::iterator it_sl;
    typename map <lui, map <lui, R> >::iterator it_gr;
    typename map <lui, R>::iterator it_nei;
    
    //Calculate internal and external link weights
    sui k, t;
    for (it_sl = cluster->begin(), k = 0; it_sl != cluster->end() && k < cluster->size(); it_sl++, k++){
        if ((it_gr = network.find(*it_sl)) != network.end()){
          for (it_nei = it_gr->second.begin(), t = 0; it_nei != it_gr->second.end() && t < it_gr->second.size(); it_nei++, t++){
            if (cluster->find(it_nei->first) != cluster->end()){
              win += it_nei->second;
            } else {
              wout += it_nei->second;
            }
          }
        }
    }
   
    //Density calculation
    return (*(this->dens))(win, wout, cluster->size());
  }
  
  static ClusterAlg* Create (string type, string args, double alpha, double beta, double weightThresh, bool translate);
  
  bool ReadGraph(ifstream* fin, string delimiters = " ,\t", double alpha = 1, double beta = 1) {
      vector <string> fields;
      map < string, lui >::iterator it_id;
      lui nxtID = 1;
      typename map < lui, map < lui, R > >::iterator it_gr, it_gr2;
      lui source, target;
     
      while (fline_tr(fin, &fields, delimiters.c_str())){
      if (fields.size() != 3) continue;
     
      //Check to see if vertex already has ID. If not, give the next ID to vertex.
      if ((it_id = idmap.find(fields[0]))!=idmap.end()){
        source = it_id->second;
      } else {
        idmap.insert(make_pair<string, lui>(fields[0], nxtID));
        source = nxtID++;
      } 
      
      //Same for second edge endpoint
      if ((it_id = idmap.find(fields[1]))!=idmap.end()){
        target = it_id->second;
      } else {
        idmap.insert(make_pair<string, lui>(fields[1], nxtID));
        target = nxtID++;
      }
      
      R weight = boost::lexical_cast<R>(fields[2]);
      if (weight > 0)
        weight = alpha * weight;
      else
        weight = beta * weight;
      
      //Add the edge to the network      
      if ((it_gr = network.find(source)) != network.end()){
        if ((it_gr2 = network.find(target)) != network.end()){
          if (it_gr2->second.find(source) != it_gr2->second.end()){
            //The edge is already in the network
            cerr << "Duplicate edge : " << source << " - " << target << " :: " << fields[2] << endl;
          } else {
            it_gr->second.insert(make_pair<lui,R>(target, weight));
          }
        } else {
          it_gr->second.insert(make_pair<lui,R>(target, weight));
        }
      } else if ((it_gr2 = network.find(target)) != network.end()){
        it_gr2->second.insert(make_pair<lui,R>(source, weight));
      } else {
        map < lui, R > tmp;
        tmp.insert(make_pair<lui,R>(target, weight));
        network.insert(make_pair<lui, map <lui, R> >(source, tmp));
      }
    }
      
    for (it_id = this->idmap.begin(); it_id != this->idmap.end(); it_id++){
      idLookup.insert(make_pair<lui, string>(it_id->second, it_id->first));
    }
    return true;
  };
  
  bool PrintGraph(ofstream* fout){
    typename map < lui, map < lui, R > >::iterator source;
    typename map < lui, R >::iterator target;
    
    for (source = network.begin(); source != network.end(); source++){
      for (target = source->second.begin(); target != source->second.end(); target++){
        (*fout) << source->first << " " << target->first << " " << target->second << endl;
      }
    }
    return true;
  }
  
  bool PrintCommunities(string filename){
    ofstream fout(filename.c_str());
    set < lui >::iterator it_cl;
    
    for (int i = 0; i < communities.size(); i++){
      fout << this->get_Density(&communities[i]) << " " << communities[i].size();
      for (it_cl = communities[i].begin(); it_cl != communities[i].end(); it_cl++){
        fout << " " << *it_cl;
      }
      fout << endl;
    }
    
    return true;
  }
  
  void PrintCommunity(set <lui> * comm){
    set < lui >::iterator it_cl;
    
    *fileout << this->get_Density(&(*comm)) << " " << (*comm).size();
    for (it_cl = (*comm).begin(); it_cl != (*comm).end(); it_cl++){
      *fileout << " " << *it_cl;
    }
    *fileout << endl;
  }
  
  bool PrintTranslatedCommunities(string filename){
    set <lui>::iterator it_sl; 
    
    ofstream fout(filename.c_str());
    set < lui >::iterator it_cl;
    
    for (int i = 0; i < communities.size(); i++){
      fout << this->get_Density(&communities[i]) << " " << communities[i].size();
      for (it_cl = communities[i].begin(); it_cl != communities[i].end(); it_cl++){
        fout << " " << (idLookup.find(*it_cl))->second;
      }
    }
    
    fout << endl;
    
    return true;
  }
  
  void PrintTranslatedCommunity(set <lui> * comm){
    set < lui >::iterator it_cl;
    
    *fileout << this->get_Density(&(*comm)) << " " << (*comm).size();
    for (it_cl = (*comm).begin(); it_cl != (*comm).end(); it_cl++){
      *fileout << " " << (idLookup.find(*it_cl))->second;
    }
    *fileout << endl;
  }
  
  void TranslateCommunities(){
    
    set < lui >::iterator it_cl;
    
    vector < set <lui> > copy = communities;
    communities.clear();
    
    for (int i = 0; i < copy.size(); i++){
      set <lui> clust;
      for (it_cl = copy[i].begin(); it_cl != copy[i].end(); it_cl++){
        clust.insert(boost::lexical_cast<lui>((idLookup.find(*it_cl))->second));
      }
      communities.push_back(clust);
    }    
  }
  
  void setOutput(string filename){
      fileout = new ofstream(filename.c_str());
  }
  
  map <lui, map <lui, R> > network; 
  vector < set < lui > > communities; 
  map <string, lui> idmap; 
  map <lui, string> idLookup; 
  string args; 
  bool translate;
  ostream* fileout; 
};

#endif