Changeset 1710:f531c16dd923 in lemon-0.x

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

Location:

lemon

Files:

• belmann_ford.h (modified) (8 diffs)
• bfs.h (modified) (1 diff)
• dfs.h (modified) (1 diff)
• dijkstra.h (modified) (2 diffs)
• floyd_warshall.h (modified) (4 diffs)
• johnson.h (modified) (6 diffs)

lemon/belmann_ford.h

@@ -168 +168 @@
   /// \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=BelmannFordDefaultTraits<_Graph,_LengthMap> >
+#endif
   class BelmannFord {
   public:
@@ -234 +238 @@
   public :
  
+    typedef BelmannFord Create;
+
     /// \name Named template parameters
 
@@ -241 +247 @@
     struct DefPredMapTraits : public Traits {
       typedef T PredMap;
-      static PredMap *createPredMap(const Graph& graph) {
+      static PredMap *createPredMap(const Graph&) {
         throw UninitializedParameter();
       }
@@ -251 +257 @@
     ///
     template <class T>
-    class DefPredMap 
-      : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {};
+    struct DefPredMap {
+      typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -268 +275 @@
     ///
     template <class T>
-    class DefDistMap 
-      : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {};
+    struct DefDistMap 
+      : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
+      typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -279 +288 @@
     /// 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
+    struct DefOperationTraits
       : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
-    public:
       typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
-      BelmannFord;
+      Create;
     };
     
     ///@}
+
+  protected:
+    
+    BelmannFord() {}
 
   public:      
@@ -363 +376 @@
     /// 
     /// Initializes the internal data structures.
-    void init() {
+    void init(const Value value = OperationTraits::infinity()) {
       create_maps();
       for (NodeIt it(*graph); it != INVALID; ++it) {
         _pred->set(it, INVALID);
-        _dist->set(it, OperationTraits::infinity());
+        _dist->set(it, value);
       }
     }
@@ -741 +754 @@
       return BelmannFordWizard<DefDistMapBase<T> >(*this);
     }
+
+    template<class T>
+    struct DefOperationTraitsBase : public Base {
+      typedef T OperationTraits;
+      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting OperationTraits type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting OperationTraits type
+    ///
+    template<class T>
+    BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
+      return BelmannFordWizard<DefDistMapBase<T> >(*this);
+    }
     
     /// \brief Sets the source node, from which the BelmannFord algorithm runs.

lemon/bfs.h

@@ -215 +215 @@
       }
     }
-    
-  public :
- 
+
+  protected:
+    
+    Bfs() {}
+    
+  public:
+ 
+    typedef Bfs Create;
+
     ///\name Named template parameters
 

lemon/dfs.h

@@ -215 +215 @@
       }
     }
-    
-  public :
+
+  protected:
+
+    Dfs() {}
+    
+  public:
 
     typedef Dfs Create;

lemon/dijkstra.h

@@ -237 +237 @@
     
   public :
+
+    typedef Dijkstra Create;
  
     ///\name Named template parameters
@@ -321 +323 @@
     typename Graph::template NodeMap<int> _heap_map;
     Heap _heap;
+  protected:
+
+    Dijkstra() {}
+
   public:      
     

lemon/floyd_warshall.h

@@ -171 +171 @@
   /// \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=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
+#endif
   class FloydWarshall {
   public:
@@ -257 +260 @@
     ///
     template <class T>
-    class DefPredMap 
-      : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {};
+    struct DefPredMap 
+      : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
+      typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -273 +278 @@
     ///
     template <class T>
-    class DefDistMap 
-      : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {};
+    struct DefDistMap 
+      : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
+      typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -286 +293 @@
     /// \ref named-templ-param "Named parameter" for setting PredMap type
     template <class T>
-    class DefOperationTraits
+    struct DefOperationTraits
       : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
+      Create;
     };
     
     ///@}
 
+  protected:
+
+    FloydWarshall() {}
+
   public:      
+
+    typedef FloydWarshall Create;
     
     /// \brief Constructor.

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;