Class: ActsAsGraph::Dag

Inherits:
Object
  • Object
show all
Defined in:
lib/acts_as_graph/dag.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(vertices) ⇒ Dag

Returns a new instance of Dag.



6
7
8
 
# File 'lib/acts_as_graph/dag.rb', line 6

def initialize vertices
  @vertices = vertices
end

Instance Attribute Details

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



4
5
6
 
# File 'lib/acts_as_graph/dag.rb', line 4

def vertices
  @vertices
end

Instance Method Details

#topological_sort ⇒ Object 



10
11
12
13
14
15
16
17
 
# 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