23 /// |
23 /// |
24 |
24 |
25 #include <lemon/list_graph.h> |
25 #include <lemon/list_graph.h> |
26 #include <lemon/graph_utils.h> |
26 #include <lemon/graph_utils.h> |
27 #include <lemon/dijkstra.h> |
27 #include <lemon/dijkstra.h> |
28 #include <lemon/belmann_ford.h> |
28 #include <lemon/bellman_ford.h> |
29 #include <lemon/invalid.h> |
29 #include <lemon/invalid.h> |
30 #include <lemon/error.h> |
30 #include <lemon/error.h> |
31 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
32 #include <lemon/matrix_maps.h> |
32 #include <lemon/matrix_maps.h> |
33 |
33 |
98 typedef _LengthMap LengthMap; |
98 typedef _LengthMap LengthMap; |
99 |
99 |
100 // The type of the length of the edges. |
100 // The type of the length of the edges. |
101 typedef typename _LengthMap::Value Value; |
101 typedef typename _LengthMap::Value Value; |
102 |
102 |
103 /// \brief Operation traits for belmann-ford algorithm. |
103 /// \brief Operation traits for bellman-ford algorithm. |
104 /// |
104 /// |
105 /// It defines the infinity type on the given Value type |
105 /// It defines the infinity type on the given Value type |
106 /// and the used operation. |
106 /// and the used operation. |
107 /// \see JohnsonDefaultOperationTraits |
107 /// \see JohnsonDefaultOperationTraits |
108 typedef JohnsonDefaultOperationTraits<Value> OperationTraits; |
108 typedef JohnsonDefaultOperationTraits<Value> OperationTraits; |
542 /// computes |
542 /// computes |
543 /// - The shortest path tree for each node. |
543 /// - The shortest path tree for each node. |
544 /// - The distance between each node pairs. |
544 /// - The distance between each node pairs. |
545 void start() { |
545 void start() { |
546 |
546 |
547 typedef typename BelmannFord<Graph, LengthMap>:: |
547 typedef typename BellmanFord<Graph, LengthMap>:: |
548 template DefOperationTraits<OperationTraits>:: |
548 template DefOperationTraits<OperationTraits>:: |
549 template DefPredMap<NullMap<Node, Edge> >:: |
549 template DefPredMap<NullMap<Node, Edge> >:: |
550 Create BelmannFordType; |
550 Create BellmanFordType; |
551 |
551 |
552 BelmannFordType belmannford(*graph, *length); |
552 BellmanFordType bellmanford(*graph, *length); |
553 |
553 |
554 NullMap<Node, Edge> predMap; |
554 NullMap<Node, Edge> predMap; |
555 |
555 |
556 belmannford.predMap(predMap); |
556 bellmanford.predMap(predMap); |
557 |
557 |
558 belmannford.init(OperationTraits::zero()); |
558 bellmanford.init(OperationTraits::zero()); |
559 belmannford.start(); |
559 bellmanford.start(); |
560 |
560 |
561 shiftedRun(belmannford.distMap()); |
561 shiftedRun(bellmanford.distMap()); |
562 } |
562 } |
563 |
563 |
564 /// \brief Executes the algorithm and checks the negatvie cycles. |
564 /// \brief Executes the algorithm and checks the negatvie cycles. |
565 /// |
565 /// |
566 /// This method runs the %Johnson algorithm in order to compute |
566 /// This method runs the %Johnson algorithm in order to compute |
569 /// computes |
569 /// computes |
570 /// - The shortest path tree for each node. |
570 /// - The shortest path tree for each node. |
571 /// - The distance between each node pairs. |
571 /// - The distance between each node pairs. |
572 bool checkedStart() { |
572 bool checkedStart() { |
573 |
573 |
574 typedef typename BelmannFord<Graph, LengthMap>:: |
574 typedef typename BellmanFord<Graph, LengthMap>:: |
575 template DefOperationTraits<OperationTraits>:: |
575 template DefOperationTraits<OperationTraits>:: |
576 template DefPredMap<NullMap<Node, Edge> >:: |
576 template DefPredMap<NullMap<Node, Edge> >:: |
577 Create BelmannFordType; |
577 Create BellmanFordType; |
578 |
578 |
579 BelmannFordType belmannford(*graph, *length); |
579 BellmanFordType bellmanford(*graph, *length); |
580 |
580 |
581 NullMap<Node, Edge> predMap; |
581 NullMap<Node, Edge> predMap; |
582 |
582 |
583 belmannford.predMap(predMap); |
583 bellmanford.predMap(predMap); |
584 |
584 |
585 belmannford.init(OperationTraits::zero()); |
585 bellmanford.init(OperationTraits::zero()); |
586 if (!belmannford.checkedStart()) return false; |
586 if (!bellmanford.checkedStart()) return false; |
587 |
587 |
588 shiftedRun(belmannford.distMap()); |
588 shiftedRun(bellmanford.distMap()); |
589 return true; |
589 return true; |
590 } |
590 } |
591 |
591 |
592 |
592 |
593 /// \brief Runs %Johnson algorithm. |
593 /// \brief Runs %Johnson algorithm. |