Class: Ogr::ShortestPaths

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/shortest_pahts.rb

Overview

Finds shortest paths in graph using Dijkstra algorithm

Instance Method Summary collapse

Constructor Details

#initialize(graph, source) ⇒ ShortestPaths

Returns a new instance of ShortestPaths.



7
8
9
10
11
12
13
14
15
 
# File 'lib/ogr/shortest_pahts.rb', line 7

def initialize(graph, source)
  @graph = graph
  @queue = IndexedPriorityQueue.min
  @parent = {}
  @distance = {}
  @graph.vertexes.each { |v| @distance[v] = Float::INFINITY }

  find_paths(source)
end

Instance Method Details

#distance_to(goal) ⇒ Object 



17
18
19
 
# File 'lib/ogr/shortest_pahts.rb', line 17

def distance_to(goal)
  distance[goal]
end

#find_paths(source) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
 
# File 'lib/ogr/shortest_pahts.rb', line 36

def find_paths(source)
  distance[source] = 0
  queue.push(source, 0)

  while v = queue.shift
    graph.neighbors(v).each do |u|
      relax(graph.get_edge(v, u))
    end
  end
end

#found_better(edge, new_distance) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
 
# File 'lib/ogr/shortest_pahts.rb', line 52

def found_better(edge, new_distance)
  v = edge.to
  distance[v] = new_distance
  parent[v] = edge.from
  if queue.include?(v)
    queue.update(v, new_distance)
  else
    queue.push(v, new_distance)
  end
end

#from(goal) ⇒ Object 



21
22
23
 
# File 'lib/ogr/shortest_pahts.rb', line 21

def from(goal)
  parent[goal]
end

#path?(goal) ⇒ Boolean

Returns:

  • (Boolean) 


25
26
27
 
# File 'lib/ogr/shortest_pahts.rb', line 25

def path?(goal)
  distance[goal] < Float::INFINITY
end

#path_to(goal) ⇒ Object 



29
30
31
32
33
34
 
# File 'lib/ogr/shortest_pahts.rb', line 29

def path_to(goal)
  v = goal
  path = [v]
  path.push v while v = parent[v]
  path.reverse
end

#relax(edge) ⇒ Object 



47
48
49
50
 
# File 'lib/ogr/shortest_pahts.rb', line 47

def relax(edge)
  new_distance = distance[edge.from] + edge.weight
  found_better(edge, new_distance) if new_distance < distance[edge.to]
end