Class: RGL::DijkstraVisitor

Inherits:
Object
  • Object
show all
Includes:
GraphVisitor
Defined in:
lib/rgl/dijkstra_visitor.rb

Overview

Dijkstra shortest path algorithm has the following event points:

* examine_vertex
* examine_edge
* edge_relaxed
* edge_not_relaxed
* finish_vertex

Direct Known Subclasses

BellmanFordVisitor

Instance Attribute Summary collapse

Attributes included from GraphVisitor

#color_map

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Methods included from GraphVisitor

#attach_distance_map, #finished_vertex?, #follow_edge?, included, #initialize

Methods included from GraphVisitor::ClassMethods

#def_event_handlers

Methods included from GraphWrapper

#initialize

Instance Attribute Details

#distance_map ⇒ Object

Returns the value of attribute distance_map.



18
19
20
 
# File 'lib/rgl/dijkstra_visitor.rb', line 18

def distance_map
  @distance_map
end

#parents_map ⇒ Object

Returns the value of attribute parents_map.



18
19
20
 
# File 'lib/rgl/dijkstra_visitor.rb', line 18

def parents_map
  @parents_map
end

Instance Method Details

#reset ⇒ Object

Returns visitor into initial state.



24
25
26
27
28
29
 
# File 'lib/rgl/dijkstra_visitor.rb', line 24

def reset
  super

  @distance_map = Hash.new(INFINITY)
  @parents_map  = {}
end

#set_source(source) ⇒ Object

Initializes visitor with a new source.



33
34
35
36
37
38
 
# File 'lib/rgl/dijkstra_visitor.rb', line 33

def set_source(source)
  reset

  color_map[source]    = :GRAY
  distance_map[source] = 0
end