Changeset 1754:4bf5ceb49023 in lemon-0.x

Timestamp:

11/02/05 16:27:38 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2283

Message:

Documentation modified

Location:

lemon

Files:

• belmann_ford.h (modified) (3 diffs)
• floyd_warshall.h (modified) (3 diffs)
• johnson.h (modified) (8 diffs)

lemon/belmann_ford.h

@@ -142 +142 @@
   };
   
-  /// \brief BelmannFord algorithm class.
+  /// \brief %BelmannFord algorithm class.
   ///
   /// \ingroup flowalgs
@@ -152 +152 @@
   /// The Belmann-Ford algorithm solves the shortest path from one node
   /// problem when the edges can have negative length but the graph should
-  /// not contain circle with negative sum of length. If we can assume
+  /// not contain cycles with negative sum of length. If we can assume
   /// that all edge is non-negative in the graph then the dijkstra algorithm
   /// should be used rather.
@@ -429 +429 @@
     }
 
-    /// \brief Executes the algorithm and checks the negative circles.
+    /// \brief Executes the algorithm and checks the negative cycles.
     ///
     /// \pre init() must be called and at least one node should be added
     /// with addSource() before using this function. If there is
-    /// a negative circle in the graph it gives back false.
+    /// a negative cycles in the graph it gives back false.
     ///
     /// This method runs the %BelmannFord algorithm from the root node(s)

lemon/floyd_warshall.h

@@ -143 +143 @@
   };
   
-  /// \brief FloydWarshall algorithm class.
+  /// \brief %FloydWarshall algorithm class.
   ///
   /// \ingroup flowalgs
-  /// This class provides an efficient implementation of \c FloydWarshall 
+  /// This class provides an efficient implementation of \c Floyd-Warshall 
   /// algorithm. The edge lengths are passed to the algorithm using a
   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
@@ -153 +153 @@
   /// The algorithm solves the shortest path problem for each pairs
   /// of node when the edges can have negative length but the graph should
-  /// not contain circle with negative sum of length. If we can assume
+  /// not contain cycles with negative sum of length. If we can assume
   /// that all edge is non-negative in the graph then the dijkstra algorithm
   /// should be used from each node rather and if the graph is sparse and
-  /// there are negative circles then the johson algorithm.
+  /// there are negative circles then the johnson algorithm.
   ///
   /// The complexity of this algorithm is O(n^3 + e).
@@ -429 +429 @@
     }
 
-    /// \brief Executes the algorithm and checks the negative circles.
+    /// \brief Executes the algorithm and checks the negative cycles.
     ///
     /// This method runs the %FloydWarshall algorithm in order to compute 
-    /// the shortest path to each node pairs. If there is a negative circle 
+    /// the shortest path to each node pairs. If there is a negative cycle 
     /// in the graph it gives back false. 
     /// The algorithm computes 

lemon/johnson.h

@@ -176 +176 @@
   };
 
-  /// \brief Johnson algorithm class.
+  /// \brief %Johnson algorithm class.
   ///
   /// \ingroup flowalgs
-  /// This class provides an efficient implementation of \c Johnson 
+  /// This class provides an efficient implementation of \c %Johnson 
   /// algorithm. The edge lengths are passed to the algorithm using a
   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
@@ -186 +186 @@
   /// The algorithm solves the shortest path problem for each pairs
   /// of node when the edges can have negative length but the graph should
-  /// not contain circle with negative sum of length. If we can assume
+  /// not contain cycles with negative sum of length. If we can assume
   /// that all edge is non-negative in the graph then the dijkstra algorithm
   /// should be used from each node.
@@ -378 +378 @@
       }
     };
-    ///\ref named-templ-param "Named parameter" for setting heap and cross 
-    ///reference type
+    ///\brief \ref named-templ-param "Named parameter" for setting heap and 
+    ///cross reference type
 
     ///\ref named-templ-param "Named parameter" for setting heap and cross 
@@ -488 +488 @@
   protected:
     
-    typedef typename BelmannFord<Graph, LengthMap>::
-    template DefOperationTraits<OperationTraits>::
-    template DefPredMap<NullMap<Node, Edge> >::
-    Create BelmannFordType;
-
-    void shiftedRun(const BelmannFordType& belmannford) {
+    template <typename PotentialMap>
+    void shiftedRun(const PotentialMap& potential) {
       
       typename Graph::template EdgeMap<Value> shiftlen(*graph);
       for (EdgeIt it(*graph);  it != INVALID; ++it) {
         shiftlen[it] = (*length)[it] 
-          + belmannford.dist(graph->source(it)) 
-          - belmannford.dist(graph->target(it));
+          + potential[graph->source(it)] 
+          - potential[graph->target(it)];
       }
       
@@ -513 +509 @@
           if (dijkstra.reached(jt)) {
             _dist->set(it, jt, dijkstra.dist(jt) + 
-                       belmannford.dist(jt) - belmannford.dist(it));
+                       potential[jt] - potential[it]);
             _pred->set(it, jt, dijkstra.pred(jt));
           } else {
@@ -551 +547 @@
     void start() {
 
+      typedef typename BelmannFord<Graph, LengthMap>::
+      template DefOperationTraits<OperationTraits>::
+      template DefPredMap<NullMap<Node, Edge> >::
+      Create BelmannFordType;
+      
       BelmannFordType belmannford(*graph, *length);
 
@@ -560 +561 @@
       belmannford.start();
 
-      shiftedRun(belmannford);
-    }
-
-    /// \brief Executes the algorithm and checks the negatvie circles.
+      shiftedRun(belmannford.distMap());
+    }
+
+    /// \brief Executes the algorithm and checks the negatvie cycles.
     ///
     /// This method runs the %Johnson algorithm in order to compute 
     /// the shortest path to each node pairs. If the graph contains
-    /// negative circle it gives back false. The algorithm 
+    /// negative cycle it gives back false. The algorithm 
     /// computes 
     /// - The shortest path tree for each node.
     /// - The distance between each node pairs.
     bool checkedStart() {
+      
+      typedef typename BelmannFord<Graph, LengthMap>::
+      template DefOperationTraits<OperationTraits>::
+      template DefPredMap<NullMap<Node, Edge> >::
+      Create BelmannFordType;
 
       BelmannFordType belmannford(*graph, *length);
@@ -582 +588 @@
       if (!belmannford.checkedStart()) return false;
 
-      shiftedRun(belmannford);
+      shiftedRun(belmannford.distMap());
       return true;
     }