module Gem::TSort

Public Class Methods

each_strongly_connected_component(each_node, each_child) { |nodes| ... } click to toggle source

The iterator version of the Gem::TSort.strongly_connected_components method.

The graph is represented by each_node and each_child. each_node should have call method which yields for each node in the graph. each_child should have call method which takes a node argument and yields for each child node.

g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
Gem::TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc }
#=> [4]
#   [2]
#   [3]
#   [1]

g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
Gem::TSort.each_strongly_connected_component(each_node, each_child) {|scc| p scc }
#=> [4]
#   [2, 3]
#   [1]

# File rubygems/tsort/lib/tsort.rb, line 343
def TSort.each_strongly_connected_component(each_node, each_child) # :yields: nodes
  return to_enum(__method__, each_node, each_child) unless block_given?

  id_map = {}
  stack = []
  each_node.call {|node|
    unless id_map.include? node
      Gem::TSort.each_strongly_connected_component_from(node, each_child, id_map, stack) {|c|
        yield c
      }
    end
  }
  nil
end
each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) { |nodes| ... } click to toggle source

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.

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

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

# File rubygems/tsort/lib/tsort.rb, line 409
def TSort.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 =
        Gem::TSort.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
strongly_connected_components(each_node, each_child) click to toggle source

Returns strongly connected components as an array of arrays of nodes. The array is sorted from children to parents. Each elements of the array represents a strongly connected component.

The graph is represented by each_node and each_child. each_node should have call method which yields for each node in the graph. each_child should have call method which takes a node argument and yields for each child node.

g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
p Gem::TSort.strongly_connected_components(each_node, each_child)
#=> [[4], [2], [3], [1]]

g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
p Gem::TSort.strongly_connected_components(each_node, each_child)
#=> [[4], [2, 3], [1]]

# File rubygems/tsort/lib/tsort.rb, line 281
def TSort.strongly_connected_components(each_node, each_child)
  Gem::TSort.each_strongly_connected_component(each_node, each_child).to_a
end
tsort(each_node, each_child) click to toggle source

Returns a topologically sorted array of nodes. The array is sorted from children to parents, i.e. the first element has no child and the last node has no parent.

The graph is represented by each_node and each_child. each_node should have call method which yields for each node in the graph. each_child should have call method which takes a node argument and yields for each child node.

If there is a cycle, Gem::TSort::Cyclic is raised.

g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
p Gem::TSort.tsort(each_node, each_child) #=> [4, 2, 3, 1]

g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
p Gem::TSort.tsort(each_node, each_child) # raises Gem::TSort::Cyclic

# File rubygems/tsort/lib/tsort.rb, line 176
def TSort.tsort(each_node, each_child)
  Gem::TSort.tsort_each(each_node, each_child).to_a
end
tsort_each(each_node, each_child) { |node| ... } click to toggle source

The iterator version of the Gem::TSort.tsort method.

The graph is represented by each_node and each_child. each_node should have call method which yields for each node in the graph. each_child should have call method which takes a node argument and yields for each child node.

g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
each_node = lambda {|&b| g.each_key(&b) }
each_child = lambda {|n, &b| g[n].each(&b) }
Gem::TSort.tsort_each(each_node, each_child) {|n| p n }
#=> 4
#   2
#   3
#   1

# File rubygems/tsort/lib/tsort.rb, line 224
def TSort.tsort_each(each_node, each_child) # :yields: node
  return to_enum(__method__, each_node, each_child) unless block_given?

  Gem::TSort.each_strongly_connected_component(each_node, each_child) {|component|
    if component.size == 1
      yield component.first
    else
      raise Cyclic.new("topological sort failed: #{component.inspect}")
    end
  }
end

Public Instance Methods

each_strongly_connected_component() { |nodes| ... } click to toggle source

The iterator version of the strongly_connected_components method. obj.each_strongly_connected_component is similar to obj.strongly_connected_components.each, but modification of obj during the iteration may lead to unexpected results.

each_strongly_connected_component returns nil.

class G
  include Gem::TSort
  def initialize(g)
    @g = g
  end
  def tsort_each_child(n, &b) @g[n].each(&b) end
  def tsort_each_node(&b) @g.each_key(&b) end
end

graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
graph.each_strongly_connected_component {|scc| p scc }
#=> [4]
#   [2]
#   [3]
#   [1]

graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
graph.each_strongly_connected_component {|scc| p scc }
#=> [4]
#   [2, 3]
#   [1]

# File rubygems/tsort/lib/tsort.rb, line 314
def each_strongly_connected_component(&block) # :yields: nodes
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Gem::TSort.each_strongly_connected_component(each_node, each_child, &block)
end
each_strongly_connected_component_from(node, id_map={}, stack=[]) { |nodes| ... } click to toggle source

Iterates over strongly connected component in the subgraph reachable from node.

Return value is unspecified.

each_strongly_connected_component_from doesn’t call tsort_each_node.

class G
  include Gem::TSort
  def initialize(g)
    @g = g
  end
  def tsort_each_child(n, &b) @g[n].each(&b) end
  def tsort_each_node(&b) @g.each_key(&b) end
end

graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
graph.each_strongly_connected_component_from(2) {|scc| p scc }
#=> [4]
#   [2]

graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
graph.each_strongly_connected_component_from(2) {|scc| p scc }
#=> [4]
#   [2, 3]

# File rubygems/tsort/lib/tsort.rb, line 384
def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes
  Gem::TSort.each_strongly_connected_component_from(node, method(:tsort_each_child), id_map, stack, &block)
end
strongly_connected_components() click to toggle source

Returns strongly connected components as an array of arrays of nodes. The array is sorted from children to parents. Each elements of the array represents a strongly connected component.

class G
  include Gem::TSort
  def initialize(g)
    @g = g
  end
  def tsort_each_child(n, &b) @g[n].each(&b) end
  def tsort_each_node(&b) @g.each_key(&b) end
end

graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
p graph.strongly_connected_components #=> [[4], [2], [3], [1]]

graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
p graph.strongly_connected_components #=> [[4], [2, 3], [1]]

# File rubygems/tsort/lib/tsort.rb, line 255
def strongly_connected_components
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Gem::TSort.strongly_connected_components(each_node, each_child)
end
tsort() click to toggle source

Returns a topologically sorted array of nodes. The array is sorted from children to parents, i.e. the first element has no child and the last node has no parent.

If there is a cycle, Gem::TSort::Cyclic is raised.

class G
  include Gem::TSort
  def initialize(g)
    @g = g
  end
  def tsort_each_child(n, &b) @g[n].each(&b) end
  def tsort_each_node(&b) @g.each_key(&b) end
end

graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
p graph.tsort #=> [4, 2, 3, 1]

graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
p graph.tsort # raises Gem::TSort::Cyclic

# File rubygems/tsort/lib/tsort.rb, line 150
def tsort
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Gem::TSort.tsort(each_node, each_child)
end
tsort_each() { |node| ... } click to toggle source

The iterator version of the tsort method. obj.tsort_each is similar to obj.tsort.each, but modification of obj during the iteration may lead to unexpected results.

tsort_each returns nil. If there is a cycle, Gem::TSort::Cyclic is raised.

class G
  include Gem::TSort
  def initialize(g)
    @g = g
  end
  def tsort_each_child(n, &b) @g[n].each(&b) end
  def tsort_each_node(&b) @g.each_key(&b) end
end

graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
graph.tsort_each {|n| p n }
#=> 4
#   2
#   3
#   1

# File rubygems/tsort/lib/tsort.rb, line 203
def tsort_each(&block) # :yields: node
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Gem::TSort.tsort_each(each_node, each_child, &block)
end
tsort_each_child(node) { |child| ... } click to toggle source

Should be implemented by a extended class.

tsort_each_child is used to iterate for child nodes of node.

# File rubygems/tsort/lib/tsort.rb, line 450
def tsort_each_child(node) # :yields: child
  raise NotImplementedError.new
end
tsort_each_node() { |node| ... } click to toggle source

Should be implemented by a extended class.

tsort_each_node is used to iterate for all nodes over a graph.

# File rubygems/tsort/lib/tsort.rb, line 442
def tsort_each_node # :yields: node
  raise NotImplementedError.new
end