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