Class: RGL::DirectedAdjacencyGraph
- Inherits:
-
Object
- Object
- RGL::DirectedAdjacencyGraph
- Defined in:
- lib/extensions/rgl.rb
Instance Method Summary collapse
-
#topsorted_vertices ⇒ Array
Returns array of topologically sorted vertices.
Instance Method Details
#topsorted_vertices ⇒ Array
Note:
Default implementation of topsort iterator is a bit faster, but it doesn't
Returns array of topologically sorted vertices. Also checks if there are cycles.
check for that condition.
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
# File 'lib/extensions/rgl.rb', line 12 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 |