CMakeLists.txt

project(GraphLab)
add_executable(lp labelprop.cpp)

labelprop.cpp

/*
 *  Label Propagation algorithm implementation.
 *  
 *  labelprop.cpp
 *
 *  For description please visit: http://www.akshaybhat.com/LPMR/graphlab 
 */

#include <string>
#include <map>
#include <vector>

#include <graphlab.hpp>
#include <graphlab/macros_def.hpp>
#include <time.h>

// vertex struct
struct vertex_data {
  std::vector<int> label; 	// vector containing all labels 
};

// Empty Edge data
struct edge_data {
};

typedef graphlab::graph<vertex_data, edge_data> lp_graph;
typedef graphlab::types<lp_graph> gl_types;


// update function
void lp_update(gl_types::iscope &scope, gl_types::icallback &scheduler, gl_types::ishared_data* shared_data) 
{
	  vertex_data& vdata = scope.vertex_data();
	  int c = vdata.label.size()-1;
	  if (c > -1)
	  {
	    std::map<int,int> count;
	    std::vector<int> result,labels;
	    int max = 0;
	    int label;
	    foreach(graphlab::edge_id_t eid, scope.out_edge_ids()) 
	    {
		  // Get the neighobr vertex value
		  labels = scope.const_neighbor_vertex_data(scope.target(eid)).label; 
		  if ( labels.size() -1 <  c)
		    label = labels[labels.size() - 1];
		  else    
		    label = labels[c];
		  count[label]++;
		  if (count[label] > max){
		      result.clear();
		      result.push_back(label);
		      max = count[label];
		  }
		  else if(count[label] == max){
		      result.push_back(label);
		  }
	    }
	    // assign the new label to the vertex
	    if (result.size())
		  vdata.label.push_back(result[int(rand()%result.size())]);
	  }
}


// Load the graph
bool load_graph(const std::string& filename, lp_graph& graph) {
	std::ifstream fin(filename.c_str());
	if(!fin.good()) return false;
	// Loop through file reading each line
	while(fin.good()) {
    size_t source = 0;
    size_t target = 0;
    fin >> source;
    fin.ignore(1); // skip comma
    fin >> target;
    if(source >= graph.num_vertices() || target >= graph.num_vertices())
      graph.resize(std::max(source, target) + 1);
    if(source != target) {
          graph.add_edge(source, target);
	  if (!graph.vertex_data(source).label.size())
	    graph.vertex_data(source).label.push_back(source);
	  if (!graph.vertex_data(target).label.size())
	    graph.vertex_data(target).label.push_back(target);
	}
  }
  graph.finalize();
  logger(LOG_INFO, "Graph created\n");
  return true;
}


int main(int argc, char** argv) {
  srand(time(NULL));
  global_logger().set_log_level(LOG_INFO);
  global_logger().set_log_to_console(true);
  logger(LOG_INFO, "Label Propagation\n");
  std::string filename;
  int iter = 10;
 
  // Setup the parser
  graphlab::command_line_options    clopts("Run the Label Propagation algorithm.");
  clopts.attach_option("infile", &filename, "LabelPropagation input file. In src, dest format");
  clopts.attach_option("iterations", &iter, "number of iterations");


  // Create a graphlab core
  gl_types::core core;
  
  // Parse arguments
  if(!clopts.parse(argc, argv) || !load_graph(filename, core.graph()) ) {
     std::cout << "Error in parsing input." << std::endl;
     return EXIT_FAILURE;
  }
  

  // Set the engine options
  core.set_engine_options(clopts);
  
for (; iter > 0; iter--){  
  // Schedule all vertices to run the update function
  core.add_task_to_all(lp_update, 100.0);
  // Run the engine
  double runtime = core.start();
  }

// Write the output to the file
 std::ofstream fout("labels.out");

 for(graphlab::vertex_id_t vid=0; vid<core.graph().num_vertices(); vid++) 
 { 
   if (core.graph().vertex_data(vid).label.size())
   {
     fout<<vid;
     for(unsigned int i=0;i<core.graph().vertex_data(vid).label.size();i++)
       fout<<'\t'<<core.graph().vertex_data(vid).label[i];
     fout<<'\n';
   } 
 } 
fout.close();

  return EXIT_SUCCESS;
} // End of main