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

Attributes inherited from DijkstraVisitor

#distance_map, #parents_map

Attributes included from GraphVisitor

#color_map

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Methods inherited from DijkstraVisitor

#reset, #set_source

Methods included from GraphVisitor

#attach_distance_map, #finished_vertex?, #follow_edge?, included, #reset

Methods included from GraphVisitor::ClassMethods

#def_event_handlers

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