]>
Commit | Line | Data |
---|---|---|
1 | package 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. | |
7 | func 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 | ||
22 | func 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 | ||
58 | func 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 | |
67 | type 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 | |
75 | func (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 | |
84 | func (s *sccAcct) push(n Vertex) { | |
85 | s.Stack = append(s.Stack, n) | |
86 | } | |
87 | ||
88 | // pop removes a vertex from the stack | |
89 | func (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 | |
100 | func (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 | } |