# Module: GRATR::Graph::Distance

Included in:
Digraph
Defined in:
lib/gratr/digraph_distance.rb

## Instance Method Summary collapse

• Algorithm from Jorgen Band-Jensen and Gregory Gutin, _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 56-58 Finds the distances from a given vertex s in a weighted digraph to the rest of the vertices, provided the graph has no negative cycle.

• Algorithm from Jorgen Band-Jensen and Gregory Gutin, _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 Finds the distances from a given vertex s in a weighted digraph to the rest of the vertices, provided all the weights of arcs are non-negative.

• This uses the Floyd-Warshall algorithm to efficiently find and record shortest paths at the same time as establishing the costs for all vertices in a graph.

• Shortest path from Jorgen Band-Jensen and Gregory Gutin, _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54.

## Instance Method Details

### #bellman_ford_moore(start, weight = nil, zero = 0) ⇒ Object

Algorithm from Jorgen Band-Jensen and Gregory Gutin, _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 56-58

Finds the distances from a given vertex s 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.

weight can be a Proc, or anything else is accessed using the [] for the

``````the label or it defaults to using
the value stored in the label for the Arc. If it is a Proc it will
pass the edge to the proc and use the resulting value.
``````

zero is used for math system with a different definition of zero

Returns a hash with the key being a vertex and the value being the distance. A missing vertex from the hash is an infinite distance

O(nm) complexity

 ``` 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131``` ```# File 'lib/gratr/digraph_distance.rb', line 117 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) ⇒ Object

Algorithm from Jorgen Band-Jensen and Gregory Gutin, _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54

Finds the distances from a given vertex s in a weighted digraph to the rest of the vertices, provided all the weights of arcs are non-negative. If negative arcs exist in the graph, two basic options exist, 1) modify all weights to be positive by using an offset, or 2) use the bellman_ford_moore algorithm. Also if the graph is acyclic, use the shortest_path algorithm.

weight can be a Proc, or anything else is accessed using the [] for the

``````the label or it defaults to using
the value stored in the label for the Arc. If it is a Proc it will
pass the edge to the proc and use the resulting value.
``````

zero is used for math system with a different definition of zero

Returns a hash with the key being a vertex and the value being the distance. A missing vertex from the hash is an infinite distance

O(n*log(n) + m) complexity

 ``` 82 83 84 85 86 87 88 89 90 91 92 93 94 95``` ```# File 'lib/gratr/digraph_distance.rb', line 82 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) ⇒ Object

This uses the Floyd-Warshall algorithm to efficiently find and record shortest paths at the same time as establishing the costs for all vertices in a graph. See, S.Skiena, “The Algorithm Design Manual”, Springer Verlag, 1998 for more details.

Returns a pair of matrices and a hash of delta values. The matrices will be indexed by two vertices and are implemented as a Hash of Hashes. The first matrix is the cost, the second matrix is the shortest path spanning tree. The delta (difference of number of in edges and out edges) is indexed by vertex.

weight specifies how an edge weight is determined, if it’s a Proc the Arc is passed to it, if it’s nil it will just use the value in the label for the Arc, otherwise the weight is determined by applying the [] operator to the value in the label for the Arc

zero defines the zero value in the math system used. Defaults of course, to 0. This allows for no assumptions to be made about the math system and fully functional duck typing.

O(n^3) complexity in time.

 ``` 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181``` ```# File 'lib/gratr/digraph_distance.rb', line 156 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) ⇒ Object

Shortest path from Jorgen Band-Jensen and Gregory Gutin, _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54

Requires that the graph be acyclic. If the graph is not acyclic, then see dijkstras_algorithm or bellman_ford_moore for possible solutions.

start is the starting vertex weight can be a Proc, or anything else is accessed using the [] for the

``````the label or it defaults to using
the value stored in the label for the Arc. If it is a Proc it will
pass the edge to the proc and use the resulting value.
``````

zero is used for math system with a different definition of zero

Returns a hash with the key being a vertex and the value being the distance. A missing vertex from the hash is an infinite distance

Complexity O(n+m)

 ``` 50 51 52 53 54 55 56 57 58 59``` ```# File 'lib/gratr/digraph_distance.rb', line 50 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```