# 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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/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 lib/rubygems/tsort/lib/tsort.rb, line 442
    def tsort_each_node # :yields: node
      raise NotImplementedError.new
    end