module Bundler::TSort

def self.each_strongly_connected_component(each_node, each_child) # :yields: nodes

:yields: nodes

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

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

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

The iterator version of the Bundler::TSort.strongly_connected_components method. 
def self.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
      each_strongly_connected_component_from(node, each_child, id_map, stack) {|c|
        yield c
      }
    end
  }
  nil
end

def self.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes

:yields: nodes

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

it doesn't need a class to represent a graph which includes Bundler::TSort.
#Bundler::TSort.each_strongly_connected_component_from is a class method and

Return value is unspecified.

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

The graph is represented by _node_ and _each_child_.
Iterates over strongly connected components in a graph. 
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

def self.strongly_connected_components(each_node, each_child)


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

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

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

Each elements of the array represents a strongly connected component.
The array is sorted from children to parents.
Returns strongly connected components as an array of arrays of nodes. 
def self.strongly_connected_components(each_node, each_child)
  each_strongly_connected_component(each_node, each_child).to_a
end

def self.tsort(each_node, each_child)


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

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

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

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

the first element has no child and the last node has no parent.
The array is sorted from children to parents, i.e.
Returns a topologically sorted array of nodes. 
def self.tsort(each_node, each_child)
  tsort_each(each_node, each_child).to_a
end

def self.tsort_each(each_node, each_child) # :yields: node

:yields: node

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

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

The iterator version of the Bundler::TSort.tsort method. 
def self.tsort_each(each_node, each_child) # :yields: node
  return to_enum(__method__, each_node, each_child) unless block_given?
  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

def each_strongly_connected_component(&block) # :yields: nodes

:yields: nodes

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

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

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

#each_strongly_connected_component returns +nil+.

modification of _obj_ during the iteration may lead to unexpected results.
obj.strongly_connected_components.each, but
obj.each_strongly_connected_component is similar to
The iterator version of the #strongly_connected_components method. 
def each_strongly_connected_component(&block) # :yields: nodes
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Bundler::TSort.each_strongly_connected_component(each_node, each_child, &block)
end

def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes

:yields: nodes

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

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

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

#each_strongly_connected_component_from doesn't call #tsort_each_node.

Return value is unspecified.

_node_.
Iterates over strongly connected component in the subgraph reachable from 
def each_strongly_connected_component_from(node, id_map={}, stack=[], &block) # :yields: nodes
  Bundler::TSort.each_strongly_connected_component_from(node, method(:tsort_each_child), id_map, stack, &block)
end

def strongly_connected_components


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]]
graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})

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

Each elements of the array represents a strongly connected component.
The array is sorted from children to parents.
Returns strongly connected components as an array of arrays of nodes. 
def strongly_connected_components
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Bundler::TSort.strongly_connected_components(each_node, each_child)
end

def tsort


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

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

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

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

the first element has no child and the last node has no parent.
The array is sorted from children to parents, i.e.
Returns a topologically sorted array of nodes. 
def tsort
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Bundler::TSort.tsort(each_node, each_child)
end

def tsort_each(&block) # :yields: node

:yields: node

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

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

If there is a cycle, Bundler::TSort::Cyclic is raised.
#tsort_each returns +nil+.

modification of _obj_ during the iteration may lead to unexpected results.
obj.tsort_each is similar to obj.tsort.each, but
The iterator version of the #tsort method. 
def tsort_each(&block) # :yields: node
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  Bundler::TSort.tsort_each(each_node, each_child, &block)
end

def tsort_each_child(node) # :yields: child

:yields: child

#tsort_each_child is used to iterate for child nodes of _node_.

Should be implemented by a extended class. 
def tsort_each_child(node) # :yields: child
  raise NotImplementedError.new
end

def tsort_each_node # :yields: node

:yields: node

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

Should be implemented by a extended class. 
def tsort_each_node # :yields: node
  raise NotImplementedError.new
end