Changeset 1709:a323456bf7c8 in lemon-0.x for lemon/bfs.h

Timestamp:

10/05/05 18:45:37 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Template Named Parameter bugfix

File:

• lemon/bfs.h (modified) (23 diffs)

lemon/bfs.h

@@ -58 +58 @@
       return new PredMap(G);
     }
-//     ///\brief The type of the map that stores the last but one
-//     ///nodes of the shortest paths.
-//     ///
-//     ///The type of the map that stores the last but one
-//     ///nodes of the shortest paths.
-//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
-//     ///
-//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
-//     ///Instantiates a PredNodeMap.
-    
-//     ///This function instantiates a \ref PredNodeMap. 
-//     ///\param G is the graph, to which
-//     ///we would like to define the \ref PredNodeMap
-//     static PredNodeMap *createPredNodeMap(const GR &G)
-//     {
-//       return new PredNodeMap();
-//     }
-
     ///The type of the map that indicates which nodes are processed.
  
@@ -180 +162 @@
     ///edges of the shortest paths.
     typedef typename TR::PredMap PredMap;
-//     ///\brief The type of the map that stores the last but one
-//     ///nodes of the shortest paths.
-//     typedef typename TR::PredNodeMap PredNodeMap;
     ///The type of the map indicating which nodes are reached.
     typedef typename TR::ReachedMap ReachedMap;
@@ -196 +175 @@
     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     bool local_pred;
-//     ///Pointer to the map of predecessors nodes.
-//     PredNodeMap *_predNode;
-//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
-//     bool local_predNode;
     ///Pointer to the map of distances.
     DistMap *_dist;
@@ -216 +191 @@
     int _queue_head,_queue_tail,_queue_next_dist;
     int _curr_dist;
-//     ///The source node of the last execution.
-//     Node source;
 
     ///Creates the maps if necessary.
@@ -229 +202 @@
         _pred = Traits::createPredMap(*G);
       }
-//       if(!_predNode) {
-//      local_predNode = true;
-//      _predNode = Traits::createPredNodeMap(*G);
-//       }
       if(!_dist) {
         local_dist = true;
@@ -266 +235 @@
     ///
     template <class T>
-    class DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { };
-    
-//     template <class T>
-//     struct DefPredNodeMapTraits : public Traits {
-//       typedef T PredNodeMap;
-//       static PredNodeMap *createPredNodeMap(const Graph &G) 
-//       {
-//      throw UninitializedParameter();
-//       }
-//     };
-//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
-
-//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
-//     ///
-//     template <class T>
-//     class DefPredNodeMap : public Bfs< Graph,
-//                                          LengthMap,
-//                                          DefPredNodeMapTraits<T> > { };
+    struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { 
+      typedef Bfs< Graph, DefPredMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -298 +252 @@
     ///
     template <class T>
-    class DefDistMap : public Bfs< Graph,
-                                   DefDistMapTraits<T> > { };
+    struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > { 
+      typedef Bfs< Graph, DefDistMapTraits<T> > Create;
+    };
     
     template <class T>
@@ -314 +269 @@
     ///
     template <class T>
-    class DefReachedMap : public Bfs< Graph,
-                                      DefReachedMapTraits<T> > { };
-    
-    struct DefGraphReachedMapTraits : public Traits {
-      typedef typename Graph::template NodeMap<bool> ReachedMap;
-      static ReachedMap *createReachedMap(const Graph &G) 
-      {
-        return new ReachedMap(G);
-      }
-    };
+    struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > { 
+      typedef Bfs< Graph, DefReachedMapTraits<T> > Create;
+    };
+    
     template <class T>
     struct DefProcessedMapTraits : public Traits {
@@ -337 +286 @@
     ///
     template <class T>
-    class DefProcessedMap : public Bfs< Graph,
-                                        DefProcessedMapTraits<T> > { };
+    struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > {
+      typedef Bfs< Graph, DefProcessedMapTraits<T> > Create;
+    };
     
     struct DefGraphProcessedMapTraits : public Traits {
@@ -354 +304 @@
     ///If you don't set it explicitly, it will be automatically allocated.
     template <class T>
-    class DefProcessedMapToBeDefaultMap :
-      public Bfs< Graph,
-                  DefGraphProcessedMapTraits> { };
+    struct DefProcessedMapToBeDefaultMap :
+      public Bfs< Graph, DefGraphProcessedMapTraits> { 
+      typedef Bfs< Graph, DefGraphProcessedMapTraits> Create;
+    };
     
     ///@}
@@ -369 +320 @@
       G(&_G),
       _pred(NULL), local_pred(false),
-//       _predNode(NULL), local_predNode(false),
       _dist(NULL), local_dist(false),
       _reached(NULL), local_reached(false),
@@ -379 +329 @@
     {
       if(local_pred) delete _pred;
-//       if(local_predNode) delete _predNode;
       if(local_dist) delete _dist;
       if(local_reached) delete _reached;
@@ -435 +384 @@
       return *this;
     }
-
-//     ///Sets the map storing the predecessor nodes.
-
-//     ///Sets the map storing the predecessor nodes.
-//     ///If you don't use this function before calling \ref run(),
-//     ///it will allocate one. The destructor deallocates this
-//     ///automatically allocated map, of course.
-//     ///\return <tt> (*this) </tt>
-//     Bfs &predNodeMap(PredNodeMap &m) 
-//     {
-//       if(local_predNode) {
-//      delete _predNode;
-//      local_predNode=false;
-//       }
-//       _predNode = &m;
-//       return *this;
-//     }
 
     ///Sets the map storing the distances calculated by the algorithm.
@@ -495 +427 @@
       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
         _pred->set(u,INVALID);
-//      _predNode->set(u,INVALID);
         _reached->set(u,false);
         _processed->set(u,false);
@@ -538 +469 @@
           _reached->set(m,true);
           _pred->set(m,e);
-//        _pred_node->set(m,n);
           _dist->set(m,_curr_dist);
         }
@@ -746 +676 @@
     const PredMap &predMap() const { return *_pred;}
  
-//     ///Returns a reference to the map of nodes of shortest paths.
-
-//     ///Returns a reference to the NodeMap of the last but one nodes of the
-//     ///shortest path tree.
-//     ///\pre \ref run() must be called before using this function.
-//     const PredNodeMap &predNodeMap() const { return *_predNode;}
-
     ///Checks if a node is reachable from the root.
 
@@ -795 +718 @@
       return new PredMap();
     }
-//     ///\brief The type of the map that stores the last but one
-//     ///nodes of the shortest paths.
-//     ///
-//     ///The type of the map that stores the last but one
-//     ///nodes of the shortest paths.
-//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
-//     ///
-//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
-//     ///Instantiates a PredNodeMap.
-    
-//     ///This function instantiates a \ref PredNodeMap. 
-//     ///\param G is the graph, to which
-//     ///we would like to define the \ref PredNodeMap
-//     static PredNodeMap *createPredNodeMap(const GR &G)
-//     {
-//       return new PredNodeMap();
-//     }
 
     ///The type of the map that indicates which nodes are processed.
@@ -892 +798 @@
     ///Pointer to the map of predecessors edges.
     void *_pred;
-//     ///Pointer to the map of predecessors nodes.
-//     void *_predNode;
     ///Pointer to the map of distances.
     void *_dist;
@@ -905 +809 @@
     /// all of the attributes to default values (0, INVALID).
     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
-//                         _predNode(0),
                            _dist(0), _source(INVALID) {}
 
@@ -917 +820 @@
     BfsWizardBase(const GR &g, Node s=INVALID) :
       _g((void *)&g), _reached(0), _processed(0), _pred(0),
-//       _predNode(0),
       _dist(0), _source(s) {}
 
@@ -966 +868 @@
     ///edges of the shortest paths.
     typedef typename TR::PredMap PredMap;
-//     ///\brief The type of the map that stores the last but one
-//     ///nodes of the shortest paths.
-//     typedef typename TR::PredNodeMap PredNodeMap;
     ///The type of the map that stores the dists of the nodes.
     typedef typename TR::DistMap DistMap;
@@ -1000 +899 @@
       if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
       if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
-//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
       if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
       alg.run(Base::_source);
@@ -1077 +975 @@
     }
     
-
-//     template<class T>
-//     struct DefPredNodeMapBase : public Base {
-//       typedef T PredNodeMap;
-//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
-//       DefPredNodeMapBase(const TR &b) : TR(b) {}
-//     };
-    
-//     ///\brief \ref named-templ-param "Named parameter"
-//     ///function for setting PredNodeMap type
-//     ///
-//     /// \ref named-templ-param "Named parameter"
-//     ///function for setting PredNodeMap type
-//     ///
-//     template<class T>
-//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
-//     {
-//       Base::_predNode=(void *)&t;
-//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
-//     }
    
     template<class T>