1package dag
2
3// StronglyConnected returns the list of strongly connected components
4// within the Graph g. This information is primarily used by this package
5// for cycle detection, but strongly connected components have widespread
6// use.
7func StronglyConnected(g *Graph) [][]Vertex {
8	vs := g.Vertices()
9	acct := sccAcct{
10		NextIndex:   1,
11		VertexIndex: make(map[Vertex]int, len(vs)),
12	}
13	for _, v := range vs {
14		// Recurse on any non-visited nodes
15		if acct.VertexIndex[v] == 0 {
16			stronglyConnected(&acct, g, v)
17		}
18	}
19	return acct.SCC
20}
21
22func stronglyConnected(acct *sccAcct, g *Graph, v Vertex) int {
23	// Initial vertex visit
24	index := acct.visit(v)
25	minIdx := index
26
27	for _, raw := range g.DownEdges(v).List() {
28		target := raw.(Vertex)
29		targetIdx := acct.VertexIndex[target]
30
31		// Recurse on successor if not yet visited
32		if targetIdx == 0 {
33			minIdx = min(minIdx, stronglyConnected(acct, g, target))
34		} else if acct.inStack(target) {
35			// Check if the vertex is in the stack
36			minIdx = min(minIdx, targetIdx)
37		}
38	}
39
40	// Pop the strongly connected components off the stack if
41	// this is a root vertex
42	if index == minIdx {
43		var scc []Vertex
44		for {
45			v2 := acct.pop()
46			scc = append(scc, v2)
47			if v2 == v {
48				break
49			}
50		}
51
52		acct.SCC = append(acct.SCC, scc)
53	}
54
55	return minIdx
56}
57
58func min(a, b int) int {
59	if a <= b {
60		return a
61	}
62	return b
63}
64
65// sccAcct is used ot pass around accounting information for
66// the StronglyConnectedComponents algorithm
67type sccAcct struct {
68	NextIndex   int
69	VertexIndex map[Vertex]int
70	Stack       []Vertex
71	SCC         [][]Vertex
72}
73
74// visit assigns an index and pushes a vertex onto the stack
75func (s *sccAcct) visit(v Vertex) int {
76	idx := s.NextIndex
77	s.VertexIndex[v] = idx
78	s.NextIndex++
79	s.push(v)
80	return idx
81}
82
83// push adds a vertex to the stack
84func (s *sccAcct) push(n Vertex) {
85	s.Stack = append(s.Stack, n)
86}
87
88// pop removes a vertex from the stack
89func (s *sccAcct) pop() Vertex {
90	n := len(s.Stack)
91	if n == 0 {
92		return nil
93	}
94	vertex := s.Stack[n-1]
95	s.Stack = s.Stack[:n-1]
96	return vertex
97}
98
99// inStack checks if a vertex is in the stack
100func (s *sccAcct) inStack(needle Vertex) bool {
101	for _, n := range s.Stack {
102		if n == needle {
103			return true
104		}
105	}
106	return false
107}
108