graph.rb in dijkstra_graph-0.1.1

- old
+ new
@@ -11,97 +11,136 @@
   # to the neighbours list of a given vertex.
   #
   # Vertices 'to-visit' are stored in a priority queue that
   # uses a Fibonacci heap to give O(1) insert, amortized O(1)
   # decrease_priority, and amortized O(log n) delete_min.
-  # Priority represents path distance from the start vertex.
+  # Priority represents path distance from the source vertex.
   #
   # The shortest distances found so far to each vertex are
   # stored in a simple hash which gives O(1) read/write.
   class Graph < WeightedGraph::PositiveWeightedGraph
     # Initialize graph edges
     def initialize
       super
     end
 
     # Use Dijkstra's algorithm to find the shortest distances
-    # from the start vertex to each of the other vertices
+    # from the source vertex to each of the other vertices
     #
-    # Returns a hash of form { 'start' => 0, 'a' => 3, 'b' => 4 },
-    # where result[v] indicates the shortest distance from start to v
-    def shortest_distances(start)
+    # Returns a hash of form { 'source' => 0, 'a' => 3, 'b' => 4 },
+    # where result[v] indicates the shortest distance from source to v
+    def shortest_distances(source)
       distances = Hash.new { Float::INFINITY } # Initial distances = Inf
-      queue = initialize_queue(start)          # Begin at start node
+      queue = initialize_queue(source)         # Begin at source node
       until queue.empty?
         v, distances[v] = queue.delete_min     # Visit next closest vertex
         update_distances_to_neighbours(v, distances, queue) # Update neighbours
       end
       distances
     end
 
     # Use Dijkstra's algorithm to find the shortest paths
-    # from the start vertex to each of the other vertices
+    # from the source vertex to each of the other vertices
     #
     # Returns a hash of form { 'c' => ['a', 'b', 'c'] }, where
-    # result[v] indicates the shortest path from start to v
-    def shortest_paths(start)
+    # result[v] indicates the shortest path from source to v
+    def shortest_paths(source)
       predecessors = {}                        # Initialize vertex predecessors
       distances = Hash.new { Float::INFINITY } # Initialize distances to Inf
-      queue = initialize_queue(start)          # Initialize queue with start
+      queue = initialize_queue(source)         # Initialize queue with source
       until queue.empty?
         # Visit next closest vertex and update neighbours
         v, distances[v] = queue.delete_min
-        update_paths_to_neighbours(v, predecessors, distances, queue)
+        update_paths_to_neighbours(v, distances, queue, predecessors)
       end
-      PathUtil.path_arrays(predecessors, start)
+      PathUtil.path_arrays(predecessors, source)
     end
 
+    # Use Dijkstra's algorithm to find the shortest paths
+    # from the source vertex to vertices within a given radius
+    #
+    # Returns a hash of form { 'c' => ['a', 'b', 'c'] }, where
+    # result[v] indicates the shortest path from source to v
+    def shortest_paths_in_radius(source, radius)
+      predecessors = {}                        # Initialize vertex predecessors
+      distances = Hash.new { Float::INFINITY } # Initialize distances to Inf
+      queue = initialize_queue(source)         # Initialize queue with source
+      until queue.empty?
+        # Visit next closest vertex and update neighbours
+        v, distance = queue.delete_min
+        return PathUtil.path_arrays(predecessors, source) if distance > radius
+        distances[v] = distance
+        update_neighbours_in_radius(v, distances, queue, predecessors, radius)
+      end
+      PathUtil.path_arrays(predecessors, source)
+    end
+
     # Use Dijkstra's algorithm to find the shortest path
-    # from the start vertex to the destination vertex
+    # from the source vertex to the destination vertex
     #
     # Returns an array of vertices along the shortest path
     # of form ['a', 'b', 'c'], or [] if no such path exists
-    def shortest_path(start, dest)
+    def shortest_path(source, dest)
       predecessors = {}                        # Initialize vertex predecessors
       distances = Hash.new { Float::INFINITY } # Initialize distances to Inf
-      queue = initialize_queue(start)          # Initialize queue with start
+      queue = initialize_queue(source)         # Initialize queue with source
       until queue.empty?
         v, distances[v] = queue.delete_min     # Visit next closest node
-        return PathUtil.path_array(predecessors, start, dest) if v == dest
-        update_paths_to_neighbours(v, predecessors, distances, queue)
+        return PathUtil.path_array(predecessors, source, dest) if v == dest
+        update_paths_to_neighbours(v, distances, queue, predecessors)
       end
-      [] # No path found from start to dest
+      [] # No path found from source to dest
     end
 
     private
 
-    # Initialize priority queue with start vertex at distance = 0
-    def initialize_queue(start_vertex)
+    # Initialize priority queue with source vertex at distance = 0
+    def initialize_queue(source_vertex)
       queue = PriorityQueue.new
-      queue[start_vertex] = 0
+      queue[source_vertex] = 0
       queue
     end
 
     # Update distances to neighbours of v and queue changed neighbours
     def update_distances_to_neighbours(v, distances, queue)
-      distance_v = distances[v]
-      get_adjacent_vertices(v).each do |w|
-        distance_through_v = distance_v + get_edge_weight(v, w)
-        if distance_through_v < distances[w]
-          queue[w] = distances[w] = distance_through_v
-        end
-      end
+      update_neighbours(v, distances, method(:update_distance),
+                        distances: distances, queue: queue)
     end
 
     # Update paths to neighbours of v and queue changed neighbours
-    def update_paths_to_neighbours(v, predecessors, distances, queue)
+    def update_paths_to_neighbours(v, distances, queue, predecessors)
+      update_neighbours(v, distances, method(:update_path),
+                        distances: distances, queue: queue,
+                        predecessors: predecessors, predecessor: v)
+    end
+
+    # Update paths to neighbours of v in radius and queue changed neighbours
+    def update_neighbours_in_radius(v, distances, queue, predecessors, radius)
+      update_neighbours(v, distances, method(:update_path),
+                        distances: distances, queue: queue, radius: radius,
+                        predecessors: predecessors, predecessor: v)
+    end
+
+    # Apply given method to each neighbour we find a shorter path to
+    def update_neighbours(v, distances, update_method, update_params)
       distance_v = distances[v]
       get_adjacent_vertices(v).each do |w|
         distance_through_v = distance_v + get_edge_weight(v, w)
         if distance_through_v < distances[w]
-          queue[w] = distances[w] = distance_through_v
-          predecessors[w] = v
+          update_method.call(w, distance_through_v, update_params)
         end
       end
+    end
+
+    # Update shortest distance to vertex
+    def update_distance(vertex, distance, params)
+      params[:queue][vertex] = params[:distances][vertex] = distance
+    end
+
+    # Update shortest path to vertex
+    def update_path(vertex, distance, params)
+      return if params[:radius] && distance > params[:radius]
+      update_distance(vertex, distance, params)
+      params[:predecessors][vertex] = params[:predecessor]
     end
   end
 end