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

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 Band-Jensen and Gregory Gutin, [*Digraphs: Theory, Algorithms and Applications*](www.springer.com/mathematics/numbers/book/978-1-84800-997-4), pg. 56-58..

Complexity ‘O(nm)`.

Parameters:

  • s (vertex)
  • weight (Proc, #[]) (defaults to: nil) —

    can be a ‘Proc`, or anything else accessed using the `[]` operator. If not a `Proc`, and if no label accessible through `[]`, it will default to using the value stored in the label for the Arc. If a `Proc`, it will pass the edge to the proc and use the resulting value.

  • zero (Integer) (defaults to: 0) —

    used for math systems with a different definition of zero

Returns:

  • (Hash) —

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



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 non-negative.

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 Band-Jensen and Gregory Gutin, [*Digraphs: Theory, Algorithms and Applications*](www.springer.com/mathematics/numbers/book/978-1-84800-997-4), pg. 53-54.

Complexity ‘O(n*log(n) + m)`.

Parameters:

  • s (vertex)
  • weight (Proc, #[]) (defaults to: nil) —

    can be a ‘Proc`, or anything else accessed using the `[]` operator. If not a `Proc`, and if no label accessible through `[]`, it will default to using the value stored in the label for the Arc. If a `Proc`, it will pass the edge to the proc and use the resulting value.

  • zero (Integer) (defaults to: 0) —

    used for math systems with a different definition of zero

Returns:

  • (Hash) —

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



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 Floyd-Warshall 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.

Parameters:

  • weight (Proc, nil) (defaults to: nil) —

    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 (Integer) (defaults to: 0) —

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

Returns:

  • (Array(matrice, matrice, Hash)) —

    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.



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 Band-Jensen and Gregory Gutin, [*Digraphs: Theory, Algorithms and Applications*](www.springer.com/mathematics/numbers/book/978-1-84800-997-4), pg. 53-54. 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.

Parameters:

  • start (vertex) —

    the starting vertex

  • weight (Proc, #[]) (defaults to: nil) —

    can be a ‘Proc`, or anything else accessed using the `[]` operator. If not a `Proc`, and if no label accessible through `[]`, it will default to using the value stored in the label for the Arc. If a `Proc`, it will pass the edge to the proc and use the resulting value.

  • zero (Integer) (defaults to: 0) —

    used for math systems with a different definition of zero

Returns:

  • (Hash) —

    a hash with the key being a vertex and the value being the



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