class method

TSort.each_strongly_connected_component_from

[T] (T node, ::TSort::_EachChild[T] each_child, ?untyped id_map, ?untyped stack) { (::Array[T]) -> void } -> void

[T] (T node, ::TSort::_EachChild[T] each_child, ?untyped id_map, ?untyped stack) -> ::Enumerator[::Array[T], void]

[T] (T node, ^(T) { (T) -> void } -> void each_child, ?untyped id_map, ?untyped stack) { (::Array[T]) -> void } -> void

[T] (T node, ^(T) { (T) -> void } -> void each_child, ?untyped id_map, ?untyped stack) -> ::Enumerator[::Array[T], void]

each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) { |nodes| ... }

lib/tsort.rb View on GitHub ↗

# File tmp/rubies/ruby-4.0.0/lib/tsort.rb, line 413
def self.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
  return to_enum(__method__, node, each_child, id_map, stack) unless block_given?

  minimum_id = node_id = id_map[node] = id_map.size
  stack_length = stack.length
  stack << node

  each_child.call(node) {|child|
    if id_map.include? child
      child_id = id_map[child]
      minimum_id = child_id if child_id && child_id < minimum_id
    else
      sub_minimum_id =
        each_strongly_connected_component_from(child, each_child, id_map, stack) {|c|
          yield c
        }
      minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
    end
  }

  if node_id == minimum_id
    component = stack.slice!(stack_length .. -1)
    component.each {|n| id_map[n] = nil}
    yield component
  end

  minimum_id
end

Iterates over strongly connected components in a graph. The graph is represented by node and each_child.

node is the first node. each_child should have call method which takes a node argument and yields for each child node.

Return value is unspecified.

TSort.each_strongly_connected_component_from is a class method and it doesn’t need a class to represent a graph which includes TSort.

Example

graph = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
each_child = lambda {|n, &b| graph[n].each(&b) }
TSort.each_strongly_connected_component_from(1, each_child) {|scc|
  p scc
}
#=> [4]
#   [2, 3]
#   [1]

See also #each_strongly_connected_component_from .each_strongly_connected_component .strongly_connected_components .tsort also in 3.4 · 3.3 · 3.2 · 3.1 · 3.0

‹ prev.each_strongly_connected_component next ›.strongly_connected_components