amplab/graphx — pull request #112 by amatsukawa (2013-12-19 02:30:24+00:00)
Title: Strongly connected component algorithm

A SCC implementation in GraphX based on graph coloring. SCC of a vertex is the intersection of a vertex's successor and predecessors in the graph.

1. Each vertex starts with its vertex id as its "color".
2. Propagate the color forward from each vertex, accept a neighbor's color if it's smaller than yours. At convergence, vertices with the same color represents all nodes that are visitable from the root of that color.
3. Reverse the graph.
4. Start at all roots, walk the graph. Visit a neighbor if it has the same color as you. All nodes visited belongs to the SCC identified by the root color.