Class: RGL::BellmanFordVisitor

Inherits:
DijkstraVisitor show all
Defined in:
lib/rgl/bellman_ford.rb

Overview

Bellman-Ford shortest paths algorithm has the following event points:

* examine_edge
* edge_relaxed
* edge_not_relaxed
* edge_minimized
* edge_not_minimized

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ BellmanFordVisitor

Returns a new instance of BellmanFordVisitor.



19
20
21
22
23
24
25
26
# File 'lib/rgl/bellman_ford.rb', line 19

def initialize(graph)
  super(graph)

  # by default, through an exception if a negative-weight cycle is detected
  @edge_not_minimized_event_handler = lambda do |u, v|
    raise ArgumentError.new("there is a negative-weight cycle including edge (#{u}, #{v})")
  end
end

Instance Attribute Details

#color_mapHash (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

#graphGraph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph)

    the wrapped graph