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