Module: PathUtil

Defined in:
lib/util/path_util.rb

Overview

Utility functions for path manipulation

Class Method Summary collapse

Class Method Details

.path_array(predecessors, start, destination) ⇒ Object

Returns array of vertices on shortest path from start to destination



16
17
18
19
20
21
22
23
24
25
 
# 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) ⇒ Object

Returns hash mapping each vertex to the shortest path from the start to that vertex



5
6
7
8
9
10
11
12
13
 
# 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) ⇒ Object

Returns path to vertex, re-using existing paths if already have the path to v’s predecessor



29
30
31
32
33
34
35
36
 
# 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