# HG changeset patch
# User deba
# Date 1128591473 0
# Node ID f531c16dd923027008ea198b8456ccc11677f174
# Parent  a323456bf7c845b9e19cc3d845499585b40dd315
Bug solved in named parameters
Simplify my Johnson algorithm

diff -r a323456bf7c8 -r f531c16dd923 lemon/belmann_ford.h
--- a/lemon/belmann_ford.h	Wed Oct 05 16:45:37 2005 +0000
+++ b/lemon/belmann_ford.h	Thu Oct 06 09:37:53 2005 +0000
@@ -167,9 +167,13 @@
   ///
   /// \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:
     
@@ -233,6 +237,8 @@
     
   public :
  
+    typedef BelmannFord Create;
+
     /// \name Named template parameters
 
     ///@{
@@ -240,7 +246,7 @@
     template <class T>
     struct DefPredMapTraits : public Traits {
       typedef T PredMap;
-      static PredMap *createPredMap(const Graph& graph) {
+      static PredMap *createPredMap(const Graph&) {
 	throw UninitializedParameter();
       }
     };
@@ -250,8 +256,9 @@
     /// \ref named-templ-param "Named parameter" for setting PredMap type
     ///
     template <class T>
-    class DefPredMap 
-      : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {};
+    struct DefPredMap {
+      typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
+    };
     
     template <class T>
     struct DefDistMapTraits : public Traits {
@@ -267,8 +274,10 @@
     /// \ref named-templ-param "Named parameter" for setting DistMap type
     ///
     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>
     struct DefOperationTraitsTraits : public Traits {
@@ -278,17 +287,21 @@
     /// \brief \ref named-templ-param "Named parameter" for setting 
     /// 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:      
     
     /// \brief Constructor.
@@ -362,11 +375,11 @@
     /// \brief Initializes the internal data structures.
     /// 
     /// 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);
       }
     }
     
@@ -740,6 +753,23 @@
       Base::_dist=(void *)&t;
       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.
     ///
diff -r a323456bf7c8 -r f531c16dd923 lemon/bfs.h
--- a/lemon/bfs.h	Wed Oct 05 16:45:37 2005 +0000
+++ b/lemon/bfs.h	Thu Oct 06 09:37:53 2005 +0000
@@ -214,9 +214,15 @@
 	_processed = Traits::createProcessedMap(*G);
       }
     }
+
+  protected:
     
-  public :
+    Bfs() {}
+    
+  public:
  
+    typedef Bfs Create;
+
     ///\name Named template parameters
 
     ///@{
diff -r a323456bf7c8 -r f531c16dd923 lemon/dfs.h
--- a/lemon/dfs.h	Wed Oct 05 16:45:37 2005 +0000
+++ b/lemon/dfs.h	Thu Oct 06 09:37:53 2005 +0000
@@ -214,8 +214,12 @@
 	_processed = Traits::createProcessedMap(*G);
       }
     }
+
+  protected:
+
+    Dfs() {}
     
-  public :
+  public:
 
     typedef Dfs Create;
 
diff -r a323456bf7c8 -r f531c16dd923 lemon/dijkstra.h
--- a/lemon/dijkstra.h	Wed Oct 05 16:45:37 2005 +0000
+++ b/lemon/dijkstra.h	Thu Oct 06 09:37:53 2005 +0000
@@ -236,6 +236,8 @@
     }
     
   public :
+
+    typedef Dijkstra Create;
  
     ///\name Named template parameters
 
@@ -320,6 +322,10 @@
   private:
     typename Graph::template NodeMap<int> _heap_map;
     Heap _heap;
+  protected:
+
+    Dijkstra() {}
+
   public:      
     
     ///Constructor.
diff -r a323456bf7c8 -r f531c16dd923 lemon/floyd_warshall.h
--- a/lemon/floyd_warshall.h	Wed Oct 05 16:45:37 2005 +0000
+++ b/lemon/floyd_warshall.h	Thu Oct 06 09:37:53 2005 +0000
@@ -170,10 +170,13 @@
   ///
   /// \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:
     
@@ -256,8 +259,10 @@
     /// \ref named-templ-param "Named parameter" for setting PredMap type
     ///
     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>
     struct DefDistMapTraits : public Traits {
@@ -272,8 +277,10 @@
     /// \ref named-templ-param "Named parameter" for setting DistMap type
     ///
     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>
     struct DefOperationTraitsTraits : public Traits {
@@ -285,13 +292,21 @@
     ///
     /// \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.
     ///
diff -r a323456bf7c8 -r f531c16dd923 lemon/johnson.h
--- a/lemon/johnson.h	Wed Oct 05 16:45:37 2005 +0000
+++ b/lemon/johnson.h	Thu Oct 06 09:37:53 2005 +0000
@@ -24,7 +24,6 @@
 
 #include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
-#include <lemon/dfs.h>
 #include <lemon/dijkstra.h>
 #include <lemon/belmann_ford.h>
 #include <lemon/invalid.h>
@@ -172,9 +171,13 @@
   ///
   /// \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:
     
@@ -257,8 +260,10 @@
     /// \ref named-templ-param "Named parameter" for setting PredMap type
     ///
     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>
     struct DefDistMapTraits : public Traits {
@@ -273,8 +278,10 @@
     /// \ref named-templ-param "Named parameter" for setting DistMap type
     ///
     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>
     struct DefOperationTraitsTraits : public Traits {
@@ -284,13 +291,20 @@
     /// \brief \ref named-templ-param "Named parameter" for setting 
     /// 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:      
     
     /// \brief Constructor.
@@ -374,40 +388,23 @@
     /// - The shortest path tree for each node.
     /// - 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;
 	ShiftLengthMap shiftlen(*length, potdiff);