Method: Plexus::Search#topsort

Defined in:
lib/plexus/search.rb

#topsort(start = nil, &block) ⇒ Array

Topological Sort Iterator.

The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then u comes before v in the ordering. The graph must be a directed acyclic graph (DAG).

The iterator can also be applied to undirected graph or to a DG graph which contains a cycle. In this case, the Iterator does not reach all vertices. The implementation of acyclic? and cyclic? uses this fact.

Can be called with a block as a standard ruby iterator, or can be used directly as it will return the result as an Array.

Parameters:

  • start (vertex) (defaults to: nil) —

    (nil) the start vertex (nil will fallback on the first vertex inserted within the graph)

Returns:

  • (Array) —

    a linear representation of the sorted graph



471
472
473
474
475
476
477
478
479
480
 
# File 'lib/plexus/search.rb', line 471

def topsort(start = nil, &block)
  result  = []
  go      = true
  back    = Proc.new { |e| go = false }
  push    = Proc.new { |v| result.unshift(v) if go }
  start ||= vertices[0]
  dfs({ :exit_vertex => push, :back_edge => back, :start => start })
  result.each { |v| block.call(v) } if block
  result
end