class ActsAsGraph::Dag
Attributes
vertices[R]
Public Class Methods
new(vertices)
click to toggle source
# File lib/acts_as_graph/dag.rb, line 6 def initialize vertices @vertices = vertices end
Public Instance Methods
topological_sort()
click to toggle source
# File lib/acts_as_graph/dag.rb, line 10 def topological_sort visited = [] post_order = [] vertices.each do |vertice| dfs(vertice, visited, post_order) unless visited.include?(vertice) end post_order end
Private Instance Methods
dfs(vertice, visited, post_order)
click to toggle source
# File lib/acts_as_graph/dag.rb, line 21 def dfs vertice, visited, post_order visited << vertice vertice.child_vertices.each do |child_vertice| dfs(child_vertice, visited, post_order) unless visited.include?(child_vertice) end if vertice.respond_to?(:child_vertices) post_order << vertice end