Graph Contraction Algorithms

Graph contraction is a technique for implementing recursive graph algorithms, where on each iteration the algorithm is repeated on a smaller graph contracted from the previous step. Probably the most well-known algorithm based on graph contraction is Boruvska's algorithm for computing the Minimum Spanning Forest. Efficient implementation, with a slight modification to the Boruvska's algorithm has now been implemented in GraphChi as well: GraphChi's minimum spanning forest.

Graph Contraction in GraphChi

Graph contraction in GraphChi is implemented by creating a new graph during the computation. That is, instead of defining which vertices and edges to remove, the idea is to output or emit edges for the new graph. When all the edges for the new graph have been output, GraphChi will preprocess the graph and create the corresponding shards. At this point, possible duplicate edges are removed (programmer can specify rule for which edges are retained -- for example the minimum spanning forest (MSF) algorithm retains the edge with the smallest weight).

To output a new graph, one must initialize a graph-output object as follows:

        std::string contractedname = filename + "C";
        sharded_graph_output<VertexDataType, EdgeDataType> shardedout(contractedname, new AcceptMinimum());
        CONTRACTED_GRAPH_OUTPUT = engine.add_output(&shardedout);

(Note, engine can have many output-objects. The minimum spanning forest application uses two outputs: one to output the MSF and one to produce contracted graph for next step).