Class: RGL::DirectedAdjacencyGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/extensions/rgl.rb

Instance Method Summary collapse

Instance Method Details

#topsorted_vertices ⇒ Array

Note:

Default implementation of topsort iterator is a bit faster, but it doesn't check for cycles.

Returns array of topologically sorted vertices. Also checks if there are cycles.

Returns:

  • (Array) —

    sorted vertices list

Raises:



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/extensions/rgl.rb', line 13

def topsorted_vertices
  result = []
  available_vertices = []
  reversed_graph = reverse
  out_degrees = {}

  vertices.each do |v|
    out_degrees[v] = reversed_graph.out_degree(v)
    available_vertices.push(v) if out_degrees[v] == 0
  end

  while available_vertices.size > 0
    vertice = available_vertices.pop
    result.push(vertice)
    each_adjacent(vertice) do |dependent|
      reversed_graph.remove_edge(dependent, vertice)
      out_degrees[dependent] -= 1
      available_vertices.push(dependent) if out_degrees[dependent] == 0
    end
  end

  raise TopsortedGraphHasCycles unless result.size == vertices.size
  result
end