module PathUtil
Utility functions for path manipulation
Public Class Methods
path_array(predecessors, start, destination)
click to toggle source
Returns array of vertices on shortest path from start to destination
# File lib/util/path_util.rb, line 16 def self.path_array(predecessors, start, destination) path = [] curr_vertex = destination loop do path.push(curr_vertex) return path.reverse if curr_vertex == start curr_vertex = predecessors[curr_vertex] return [] if curr_vertex.nil? end end
path_arrays(predecessors, start)
click to toggle source
Returns hash mapping each vertex to the shortest path from the start to that vertex
# File lib/util/path_util.rb, line 5 def self.path_arrays(predecessors, start) paths = Hash.new { [] } start_has_outgoing_edges = false predecessors.each do |v, pred| start_has_outgoing_edges = true if pred == start paths[v] = path_to_vertex(paths, predecessors, start, v) end start_has_outgoing_edges ? paths : {} end
path_to_vertex(paths, predecessors, start, v)
click to toggle source
Returns path to vertex, re-using existing paths if already have the path to v's predecessor
# File lib/util/path_util.rb, line 29 def self.path_to_vertex(paths, predecessors, start, v) pred = predecessors[v] if paths.include?(pred) paths[pred] + [v] else path_array(predecessors, start, v) end end