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, line 36
def initialize(graph, edge_weights_map, visitor)
  @graph            = graph
  @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?)
  @visitor          = visitor
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, line 47
def shortest_paths(source)
  init(source)
  relax_edges
  PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices)
end

Private Instance Methods

init(source) click to toggle source
# File lib/rgl/bellman_ford.rb, line 55
def init(source)
  @visitor.set_source(source)
end
relax_edge(u, v) click to toggle source
# File lib/rgl/bellman_ford.rb, line 76
def relax_edge(u, v)
  @visitor.handle_examine_edge(u, v)

  new_v_distance = @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v)

  if new_v_distance < @visitor.distance_map[v]
    @visitor.distance_map[v] = new_v_distance
    @visitor.parents_map[v]  = u

    @visitor.handle_edge_relaxed(u, v)
  else
    @visitor.handle_edge_not_relaxed(u, v)
  end
end
relax_edges() click to toggle source
# File lib/rgl/bellman_ford.rb, line 59
def relax_edges
  (@graph.size - 1).times do
    @graph.each_edge do |u, v|
      relax_edge(u, v)
      relax_edge(v, u) unless @graph.directed?
    end
  end

  @graph.each_edge do |u, v|
    if @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v) < @visitor.distance_map[v]
      @visitor.handle_edge_not_minimized(u, v)
    else
      @visitor.handle_edge_minimized(u, v)
    end
  end
end