Changeset 1710:f531c16dd923 in lemon-0.x for lemon/johnson.h

Timestamp:

10/06/05 11:37:53 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Bug solved in named parameters
Simplify my Johnson algorithm

File:

• lemon/johnson.h (modified) (6 diffs)

lemon/johnson.h

@@ -25 +25 @@
 #include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
-#include <lemon/dfs.h>
 #include <lemon/dijkstra.h>
 #include <lemon/belmann_ford.h>
@@ -173 +172 @@
   /// \author Balazs Dezso
 
+#ifdef DOXYGEN
+  template <typename _Graph, typename _LengthMap, typename _Traits>
+#else
   template <typename _Graph=ListGraph,
             typename _LengthMap=typename _Graph::template EdgeMap<int>,
             typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
+#endif
   class Johnson {
   public:
@@ -258 +261 @@
     ///
     template <class T>
-    class DefPredMap 
-      : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {};
+    struct DefPredMap 
+      : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
+      typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -274 +279 @@
     ///
     template <class T>
-    class DefDistMap 
-      : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {};
+    struct DefDistMap 
+      : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
+      typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -285 +292 @@
     /// OperationTraits type
     ///
-    /// \ref named-templ-param "Named parameter" for setting PredMap type
+    /// \ref named-templ-param "Named parameter" for setting 
+    /// OperationTraits type
     template <class T>
-    class DefOperationTraits
-      : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {};
+    struct DefOperationTraits
+      : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
+    };
     
     ///@}
+
+  protected:
+
+    Johnson() {}
 
   public:      
@@ -375 +389 @@
     /// - The distance between each node pairs.
     void start() {
-      typename BelmannFord<Graph, LengthMap>::
+      typedef typename BelmannFord<Graph, LengthMap>::
       template DefOperationTraits<OperationTraits>::
-      BelmannFord belmannford(*graph, *length);
+      template DefPredMap<NullMap<Node, Edge> >::
+      Create BelmannFordType;
+
+      BelmannFordType belmannford(*graph, *length);
+
+      NullMap<Node, Edge> predMap;
+
+      belmannford.predMap(predMap);
       
-      belmannford.init();
-
-      typename Graph::template NodeMap<bool> initial(*graph, false);
-
-      {
-        Dfs<Graph> dfs(*graph);
-
-        dfs.init();
-        for (NodeIt it(*graph); it != INVALID; ++it) {
-          if (!dfs.reached(it)) {
-            dfs.addSource(it);
-            while (!dfs.emptyQueue()) {
-              Edge edge = dfs.processNextEdge();
-              initial.set(graph->target(edge), false);
-            }
-            initial.set(it, true);
-          }
-        }
-        for (NodeIt it(*graph); it != INVALID; ++it) {
-          if (initial[it]) {
-            belmannford.addSource(it);
-          }
-        }
-      }
-
+      belmannford.init(OperationTraits::zero());
       belmannford.start();
 
       for (NodeIt it(*graph); it != INVALID; ++it) {
         typedef PotentialDifferenceMap<Graph, 
-          typename BelmannFord<Graph, LengthMap>::DistMap> PotDiffMap;
+          typename BelmannFordType::DistMap> PotDiffMap;
         PotDiffMap potdiff(*graph, belmannford.distMap());
         typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;