Class: Ogr::TopologicalSort

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/topological_sort.rb

Overview

Sorts graph vertexes in topological order

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ TopologicalSort

Returns a new instance of TopologicalSort.



7
8
9
10
11
 
# File 'lib/ogr/topological_sort.rb', line 7

def initialize(graph)
  @graph = graph
  @marked = {}
  @sorted = []
end

Instance Method Details

#sort ⇒ Object 



13
14
15
16
 
# File 'lib/ogr/topological_sort.rb', line 13

def sort
  graph.vertexes.each { |v| dfs(v) unless marked[v] }
  sorted.reverse
end