class Ogr::TopologicalSort

Sorts graph vertexes in topological order

Attributes

graph[R]
marked[R]
sorted[R]

Public Class Methods

new(graph) click to toggle source
# File lib/ogr/topological_sort.rb, line 7
def initialize(graph)
  @graph = graph
  @marked = {}
  @sorted = []
end

Public Instance Methods

sort() click to toggle source
# File lib/ogr/topological_sort.rb, line 13
def sort
  graph.vertexes.each { |v| dfs(v) unless marked[v] }
  sorted.reverse
end

Private Instance Methods

dfs(v) click to toggle source
# File lib/ogr/topological_sort.rb, line 20
def dfs(v)
  marked[v] = true
  graph.neighbors(v).reverse_each do |u|
    dfs(u) unless marked[u]
  end
  sorted.push v
end