Method: Puppet::Graph::SimpleGraph#tarjan

Defined in:
lib/puppet/graph/simple_graph.rb

#tarjan(root, s) ⇒ Object

This is a simple implementation of Tarjan’s algorithm to find strongly connected components in the graph; this is a fairly ugly implementation, because I can’t just decorate the vertices themselves.

This method has an unhealthy relationship with the find_cycles_in_graph method below, which contains the knowledge of how the state object is maintained.



101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/puppet/graph/simple_graph.rb', line 101

def tarjan(root, s)
  # initialize the recursion stack we use to work around the nasty lack of a
  # decent Ruby stack.
  recur = [{ :node => root }]

  while not recur.empty? do
    frame = recur.last
    vertex = frame[:node]

    case frame[:step]
    when nil then
      s[:index][vertex]   = s[:number]
      s[:lowlink][vertex] = s[:number]
      s[:number]          = s[:number] + 1

      s[:stack].push(vertex)
      s[:seen][vertex] = true

      frame[:children] = adjacent(vertex)
      frame[:step]     = :children

    when :children then
      if frame[:children].length > 0 then
        child = frame[:children].shift
        if ! s[:index][child] then
          # Never seen, need to recurse.
          frame[:step] = :after_recursion
          frame[:child] = child
          recur.push({ :node => child })
        elsif s[:seen][child] then
          s[:lowlink][vertex] = [s[:lowlink][vertex], s[:index][child]].min
        end
      else
        if s[:lowlink][vertex] == s[:index][vertex] then
          this_scc = []
          begin
            top = s[:stack].pop
            s[:seen][top] = false
            this_scc << top
          end until top == vertex
          s[:scc] << this_scc
        end
        recur.pop               # done with this node, finally.
      end

    when :after_recursion then
      s[:lowlink][vertex] = [s[:lowlink][vertex], s[:lowlink][frame[:child]]].min
      frame[:step] = :children

    else
      fail "#{frame[:step]} is an unknown step"
    end
  end
end