class RGL::DijkstraAlgorithm

This class implements {Graph#dijkstra_shortest_path} and {Graph#dijkstra_shortest_paths}

Constants

DEFAULT_DISTANCE_COMBINATOR

Distance combinator is a lambda that accepts the distance (usually from the source) to vertex u and the weight of the edge connecting vertex u to another vertex v and returns the distance to vertex v if it’s reached through the vertex u. By default, the distance to vertex u and the edge’s weight are summed.

Public Class Methods

new(graph, edge_weights_map, visitor, distance_combinator = nil) click to toggle source

Initializes Dijkstra’s algorithm for a graph with provided edges weights map.

   # File lib/rgl/dijkstra.rb
19 def initialize(graph, edge_weights_map, visitor, distance_combinator = nil)
20   @graph               = graph
21   @edge_weights_map    = build_edge_weights_map(edge_weights_map)
22   @visitor             = visitor
23   @distance_combinator = distance_combinator || DEFAULT_DISTANCE_COMBINATOR
24 end

Public Instance Methods

find_shortest_paths(source) click to toggle source

Finds the shortest path from the source to every other vertex.

   # File lib/rgl/dijkstra.rb
48 def find_shortest_paths(source)
49   init(source)
50   relax_edges
51 end
shortest_path(source, target) click to toggle source

Finds the shortest path from the source to the target in the graph.

Returns the shortest path, if it exists, as an Array of vertices. Otherwise, returns nil.

   # File lib/rgl/dijkstra.rb
30 def shortest_path(source, target)
31   init(source)
32   relax_edges(target, true)
33   PathBuilder.new(source, @visitor.parents_map).path(target)
34 end
shortest_paths(source) click to toggle source

Finds the shortest path form the source to every other vertex of the graph and builds shortest paths map.

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/dijkstra.rb
41 def shortest_paths(source)
42   find_shortest_paths(source)
43   PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices)
44 end

Private Instance Methods

build_edge_weights_map(edge_weights_map) click to toggle source
    # File lib/rgl/dijkstra.rb
101 def build_edge_weights_map(edge_weights_map)
102   edge_weights_map.is_a?(EdgePropertiesMap) ? edge_weights_map : NonNegativeEdgePropertiesMap.new(edge_weights_map, @graph.directed?)
103 end
init(source) click to toggle source
   # File lib/rgl/dijkstra.rb
55 def init(source)
56   @visitor.set_source(source)
57 
58   @queue = PairingHeap::MinPriorityQueue.new
59   @queue.push(source, 0)
60 end
relax_edge(u, v) click to toggle source
   # File lib/rgl/dijkstra.rb
79 def relax_edge(u, v)
80   @visitor.handle_examine_edge(u, v)
81 
82   new_v_distance = @distance_combinator.call(@visitor.distance_map[u], @edge_weights_map.edge_property(u, v))
83 
84   if new_v_distance < @visitor.distance_map[v]
85     @visitor.distance_map[v] = new_v_distance
86     @visitor.parents_map[v]  = u
87 
88     if @visitor.color_map[v] == :WHITE
89       @visitor.color_map[v] = :GRAY
90       @queue.push(v, new_v_distance)
91     elsif @visitor.color_map[v] == :GRAY
92       @queue.decrease_key(v, new_v_distance)
93     end
94 
95     @visitor.handle_edge_relaxed(u, v)
96   else
97     @visitor.handle_edge_not_relaxed(u, v)
98   end
99 end
relax_edges(target = nil, break_on_target = false) click to toggle source
   # File lib/rgl/dijkstra.rb
62 def relax_edges(target = nil, break_on_target = false)
63   until @queue.empty?
64     u = @queue.pop
65 
66     break if break_on_target && u == target
67 
68     @visitor.handle_examine_vertex(u)
69 
70     @graph.each_adjacent(u) do |v|
71       relax_edge(u, v) unless @visitor.finished_vertex?(v)
72     end
73 
74     @visitor.color_map[u] = :BLACK
75     @visitor.handle_finish_vertex(u)
76   end
77 end