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

Instance Method Summary collapse

Instance Attribute Details

#color_map ⇒ Hash (readonly) Originally defined in module GraphVisitor

Returns a map which store the colors for each vertex.

Returns:

  • (Hash) —

    a map which store the colors for each vertex

#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

#graph ⇒ Graph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

#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

#attach_distance_map(map = Hash.new(0)) ⇒ Object Originally defined in module GraphVisitor

Attach a map to the visitor which records the distance of a visited vertex to the start vertex.

This is similar to BGLs distance_recorder.

After the distance_map is attached, the visitor has a new method distance_to_root, which answers the distance to the start vertex.

#finished_vertex?(v) ⇒ Boolean Originally defined in module GraphVisitor

Returns true if vertex v is colored :BLACK (i.e. finished).

Returns:

  • (Boolean)

#follow_edge?(u, v) ⇒ Boolean Originally defined in module GraphVisitor

Shall we follow the edge (u,v); i.e. v has color :WHITE

Returns:

  • (Boolean)

#initialize(graph) ⇒ Object Originally defined in module GraphVisitor

Create a new GraphVisitor on graph.

Parameters:

#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