vendor/github.com/hashicorp/terraform/dag/tarjan.go

   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 }