class RGL::BellmanFordAlgorithm

Public Class Methods

new(graph, edge_weights_map, visitor) click to toggle source

Initializes Bellman-Ford algorithm for a graph with provided edges weights map.

   # File lib/rgl/bellman_ford.rb
36 def initialize(graph, edge_weights_map, visitor)
37   @graph            = graph
38   @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?)
39   @visitor          = visitor
40 end

Public Instance Methods

shortest_paths(source) click to toggle source

Finds the shortest path form the source to every other vertex of the graph.

Returns the shortest paths map that contains the shortest path (if it exists) from the source to any vertex of the graph.

   # File lib/rgl/bellman_ford.rb
47 def shortest_paths(source)
48   init(source)
49   relax_edges
50   PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices)
51 end

Private Instance Methods

init(source) click to toggle source
   # File lib/rgl/bellman_ford.rb
55 def init(source)
56   @visitor.set_source(source)
57 end
relax_edge(u, v) click to toggle source
   # File lib/rgl/bellman_ford.rb
76 def relax_edge(u, v)
77   @visitor.handle_examine_edge(u, v)
78 
79   new_v_distance = @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v)
80 
81   if new_v_distance < @visitor.distance_map[v]
82     @visitor.distance_map[v] = new_v_distance
83     @visitor.parents_map[v]  = u
84 
85     @visitor.handle_edge_relaxed(u, v)
86   else
87     @visitor.handle_edge_not_relaxed(u, v)
88   end
89 end
relax_edges() click to toggle source
   # File lib/rgl/bellman_ford.rb
59 def relax_edges
60   (@graph.size - 1).times do
61     @graph.each_edge do |u, v|
62       relax_edge(u, v)
63       relax_edge(v, u) unless @graph.directed?
64     end
65   end
66 
67   @graph.each_edge do |u, v|
68     if @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v) < @visitor.distance_map[v]
69       @visitor.handle_edge_not_minimized(u, v)
70     else
71       @visitor.handle_edge_minimized(u, v)
72     end
73   end
74 end