diff options
author | Jake Champlin <jake.champlin.27@gmail.com> | 2017-06-06 12:40:07 -0400 |
---|---|---|
committer | Jake Champlin <jake.champlin.27@gmail.com> | 2017-06-06 12:40:07 -0400 |
commit | bae9f6d2fd5eb5bc80929bd393932b23f14d7c93 (patch) | |
tree | ca9ab12a7d78b1fc27a8f734729081357ce6d252 /vendor/github.com/hashicorp/terraform/dag/tarjan.go | |
parent | 254c495b6bebab3fb72a243c4bce858d79e6ee99 (diff) | |
download | terraform-provider-statuscake-bae9f6d2fd5eb5bc80929bd393932b23f14d7c93.tar.gz terraform-provider-statuscake-bae9f6d2fd5eb5bc80929bd393932b23f14d7c93.tar.zst terraform-provider-statuscake-bae9f6d2fd5eb5bc80929bd393932b23f14d7c93.zip |
Initial transfer of provider code
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag/tarjan.go')
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/tarjan.go | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/vendor/github.com/hashicorp/terraform/dag/tarjan.go b/vendor/github.com/hashicorp/terraform/dag/tarjan.go new file mode 100644 index 0000000..9d8b25c --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/tarjan.go | |||
@@ -0,0 +1,107 @@ | |||
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 | } | ||