Module: Plexus::DirectedGraphBuilder::Distance
 Included in:
 Algorithms
 Defined in:
 lib/plexus/directed_graph/distance.rb
Overview
This module provides algorithms computing distance between vertices.
Instance Method Summary collapse

#bellman_ford_moore(start, weight = nil, zero = 0) ⇒ Hash
Finds the distances from a given vertex in a weighted digraph to the rest of the vertices, provided the graph has no negative cycle.

#dijkstras_algorithm(s, weight = nil, zero = 0) ⇒ Hash
Finds the distance from a given vertex in a weighted digraph to the rest of the vertices, provided all the weights of arcs are nonnegative.

#floyd_warshall(weight = nil, zero = 0) ⇒ Array(matrice, matrice, Hash)
Uses the FloydWarshall algorithm to efficiently find and record shortest paths while establishing at the same time the costs for all vertices in a graph.

#shortest_path(start, weight = nil, zero = 0) ⇒ Hash
Shortest path computation.
Instance Method Details
#bellman_ford_moore(start, weight = nil, zero = 0) ⇒ Hash
Finds the distances from a given vertex in a weighted digraph to the rest of the vertices, provided the graph has no negative cycle.
If no negative weights exist, then #dijkstras_algorithm is more efficient in time and space. Also, if the graph is acyclic, use the #shortest_path algorithm.
From: Jorgen BandJensen and Gregory Gutin, [*Digraphs: Theory, Algorithms and Applications*](www.springer.com/mathematics/numbers/book/9781848009974), pg. 5658..
Complexity `O(nm)`.
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 
# File 'lib/plexus/directed_graph/distance.rb', line 100 def bellman_ford_moore(start, weight = nil, zero = 0) distance = { start => zero } path = {} 2.upto(vertices.size) do edges.each do e u, v = e[0], e[1] unless distance[u].nil? c = cost(u, v, weight) + distance[u] if distance[v].nil? or c < distance[v] distance[v] = c path[v] = u end end end end [distance, path] end 
#dijkstras_algorithm(s, weight = nil, zero = 0) ⇒ Hash
Finds the distance from a given vertex in a weighted digraph to the rest of the vertices, provided all the weights of arcs are nonnegative.
If negative arcs exist in the graph, two basic options exist:

modify all weights to be positive using an offset (temporary at least)

use the #bellman_ford_moore algorithm.
Also, if the graph is acyclic, use the algorithm.
From: Jorgen BandJensen and Gregory Gutin, [*Digraphs: Theory, Algorithms and Applications*](www.springer.com/mathematics/numbers/book/9781848009974), pg. 5354.
Complexity `O(n*log(n) + m)`.
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 
# File 'lib/plexus/directed_graph/distance.rb', line 63 def dijkstras_algorithm(s, weight = nil, zero = 0) q = vertices; distance = { s => zero } path = {} while not q.empty? v = (q & distance.keys).inject(nil) { a,k (!a.nil?) && (distance[a] < distance[k]) ? a : k} q.delete(v) (q & adjacent(v)).each do u c = cost(v, u, weight) if distance[u].nil? or distance[u] > (c + distance[v]) distance[u] = c + distance[v] path[u] = v end end end [distance, path] end 
#floyd_warshall(weight = nil, zero = 0) ⇒ Array(matrice, matrice, Hash)
Uses the FloydWarshall algorithm to efficiently find and record shortest paths while establishing at the same time the costs for all vertices in a graph.
See S.Skiena, *The Algorithm Design Manual*, Springer Verlag, 1998 for more details.
O(n^3) complexity in time.
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 
# File 'lib/plexus/directed_graph/distance.rb', line 138 def floyd_warshall(weight = nil, zero = 0) c = Hash.new { h,k h[k] = Hash.new } path = Hash.new { h,k h[k] = Hash.new } delta = Hash.new { h,k h[k] = 0 } edges.each do e delta[e.source] += 1 delta[e.target] = 1 path[e.source][e.target] = e.target c[e.source][e.target] = cost(e, weight) end vertices.each do k vertices.each do i if c[i][k] vertices.each do j if c[k][j] && (c[i][j].nil? or c[i][j] > (c[i][k] + c[k][j])) path[i][j] = path[i][k] c[i][j] = c[i][k] + c[k][j] return nil if i == j and c[i][j] < zero end end end end end [c, path, delta] end 
#shortest_path(start, weight = nil, zero = 0) ⇒ Hash
Shortest path computation.
From: Jorgen BandJensen and Gregory Gutin, [*Digraphs: Theory, Algorithms and Applications*](www.springer.com/mathematics/numbers/book/9781848009974), pg. 5354. Complexity `O(n+m)`.
Requires the graph to be acyclic. If the graph is not acyclic, then see #dijkstras_algorithm or #bellman_ford_moore for possible solutions.
distance. A missing vertex from the hash is equivalent to an infinite distance.
27 28 29 30 31 32 33 34 35 36 37 
# File 'lib/plexus/directed_graph/distance.rb', line 27 def shortest_path(start, weight = nil, zero = 0) dist = { start => zero } path = {} topsort(start) do vi next if vi == start dist[vi], path[vi] = adjacent(vi, :direction => :in).map do vj [dist[vj] + cost(vj,vi,weight), vj] end.min { a,b a[0] <=> b[0]} end; dist.keys.size == vertices.size ? [dist, path] : nil end 