1.1 --- a/lemon/bfs.h Wed Oct 05 13:44:29 2005 +0000
1.2 +++ b/lemon/bfs.h Wed Oct 05 16:45:37 2005 +0000
1.3 @@ -57,24 +57,6 @@
1.4 {
1.5 return new PredMap(G);
1.6 }
1.7 -// ///\brief The type of the map that stores the last but one
1.8 -// ///nodes of the shortest paths.
1.9 -// ///
1.10 -// ///The type of the map that stores the last but one
1.11 -// ///nodes of the shortest paths.
1.12 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.13 -// ///
1.14 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.15 -// ///Instantiates a PredNodeMap.
1.16 -
1.17 -// ///This function instantiates a \ref PredNodeMap.
1.18 -// ///\param G is the graph, to which
1.19 -// ///we would like to define the \ref PredNodeMap
1.20 -// static PredNodeMap *createPredNodeMap(const GR &G)
1.21 -// {
1.22 -// return new PredNodeMap();
1.23 -// }
1.24 -
1.25 ///The type of the map that indicates which nodes are processed.
1.26
1.27 ///The type of the map that indicates which nodes are processed.
1.28 @@ -179,9 +161,6 @@
1.29 ///\brief The type of the map that stores the last
1.30 ///edges of the shortest paths.
1.31 typedef typename TR::PredMap PredMap;
1.32 -// ///\brief The type of the map that stores the last but one
1.33 -// ///nodes of the shortest paths.
1.34 -// typedef typename TR::PredNodeMap PredNodeMap;
1.35 ///The type of the map indicating which nodes are reached.
1.36 typedef typename TR::ReachedMap ReachedMap;
1.37 ///The type of the map indicating which nodes are processed.
1.38 @@ -195,10 +174,6 @@
1.39 PredMap *_pred;
1.40 ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.41 bool local_pred;
1.42 -// ///Pointer to the map of predecessors nodes.
1.43 -// PredNodeMap *_predNode;
1.44 -// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.45 -// bool local_predNode;
1.46 ///Pointer to the map of distances.
1.47 DistMap *_dist;
1.48 ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.49 @@ -215,8 +190,6 @@
1.50 std::vector<typename Graph::Node> _queue;
1.51 int _queue_head,_queue_tail,_queue_next_dist;
1.52 int _curr_dist;
1.53 -// ///The source node of the last execution.
1.54 -// Node source;
1.55
1.56 ///Creates the maps if necessary.
1.57
1.58 @@ -228,10 +201,6 @@
1.59 local_pred = true;
1.60 _pred = Traits::createPredMap(*G);
1.61 }
1.62 -// if(!_predNode) {
1.63 -// local_predNode = true;
1.64 -// _predNode = Traits::createPredNodeMap(*G);
1.65 -// }
1.66 if(!_dist) {
1.67 local_dist = true;
1.68 _dist = Traits::createDistMap(*G);
1.69 @@ -265,24 +234,9 @@
1.70 ///\ref named-templ-param "Named parameter" for setting PredMap type
1.71 ///
1.72 template <class T>
1.73 - class DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { };
1.74 -
1.75 -// template <class T>
1.76 -// struct DefPredNodeMapTraits : public Traits {
1.77 -// typedef T PredNodeMap;
1.78 -// static PredNodeMap *createPredNodeMap(const Graph &G)
1.79 -// {
1.80 -// throw UninitializedParameter();
1.81 -// }
1.82 -// };
1.83 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.84 -
1.85 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.86 -// ///
1.87 -// template <class T>
1.88 -// class DefPredNodeMap : public Bfs< Graph,
1.89 -// LengthMap,
1.90 -// DefPredNodeMapTraits<T> > { };
1.91 + struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > {
1.92 + typedef Bfs< Graph, DefPredMapTraits<T> > Create;
1.93 + };
1.94
1.95 template <class T>
1.96 struct DefDistMapTraits : public Traits {
1.97 @@ -297,8 +251,9 @@
1.98 ///\ref named-templ-param "Named parameter" for setting DistMap type
1.99 ///
1.100 template <class T>
1.101 - class DefDistMap : public Bfs< Graph,
1.102 - DefDistMapTraits<T> > { };
1.103 + struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > {
1.104 + typedef Bfs< Graph, DefDistMapTraits<T> > Create;
1.105 + };
1.106
1.107 template <class T>
1.108 struct DefReachedMapTraits : public Traits {
1.109 @@ -313,16 +268,10 @@
1.110 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.111 ///
1.112 template <class T>
1.113 - class DefReachedMap : public Bfs< Graph,
1.114 - DefReachedMapTraits<T> > { };
1.115 + struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > {
1.116 + typedef Bfs< Graph, DefReachedMapTraits<T> > Create;
1.117 + };
1.118
1.119 - struct DefGraphReachedMapTraits : public Traits {
1.120 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.121 - static ReachedMap *createReachedMap(const Graph &G)
1.122 - {
1.123 - return new ReachedMap(G);
1.124 - }
1.125 - };
1.126 template <class T>
1.127 struct DefProcessedMapTraits : public Traits {
1.128 typedef T ProcessedMap;
1.129 @@ -336,8 +285,9 @@
1.130 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.131 ///
1.132 template <class T>
1.133 - class DefProcessedMap : public Bfs< Graph,
1.134 - DefProcessedMapTraits<T> > { };
1.135 + struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > {
1.136 + typedef Bfs< Graph, DefProcessedMapTraits<T> > Create;
1.137 + };
1.138
1.139 struct DefGraphProcessedMapTraits : public Traits {
1.140 typedef typename Graph::template NodeMap<bool> ProcessedMap;
1.141 @@ -353,9 +303,10 @@
1.142 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.143 ///If you don't set it explicitly, it will be automatically allocated.
1.144 template <class T>
1.145 - class DefProcessedMapToBeDefaultMap :
1.146 - public Bfs< Graph,
1.147 - DefGraphProcessedMapTraits> { };
1.148 + struct DefProcessedMapToBeDefaultMap :
1.149 + public Bfs< Graph, DefGraphProcessedMapTraits> {
1.150 + typedef Bfs< Graph, DefGraphProcessedMapTraits> Create;
1.151 + };
1.152
1.153 ///@}
1.154
1.155 @@ -368,7 +319,6 @@
1.156 Bfs(const Graph& _G) :
1.157 G(&_G),
1.158 _pred(NULL), local_pred(false),
1.159 -// _predNode(NULL), local_predNode(false),
1.160 _dist(NULL), local_dist(false),
1.161 _reached(NULL), local_reached(false),
1.162 _processed(NULL), local_processed(false)
1.163 @@ -378,7 +328,6 @@
1.164 ~Bfs()
1.165 {
1.166 if(local_pred) delete _pred;
1.167 -// if(local_predNode) delete _predNode;
1.168 if(local_dist) delete _dist;
1.169 if(local_reached) delete _reached;
1.170 if(local_processed) delete _processed;
1.171 @@ -435,23 +384,6 @@
1.172 return *this;
1.173 }
1.174
1.175 -// ///Sets the map storing the predecessor nodes.
1.176 -
1.177 -// ///Sets the map storing the predecessor nodes.
1.178 -// ///If you don't use this function before calling \ref run(),
1.179 -// ///it will allocate one. The destructor deallocates this
1.180 -// ///automatically allocated map, of course.
1.181 -// ///\return <tt> (*this) </tt>
1.182 -// Bfs &predNodeMap(PredNodeMap &m)
1.183 -// {
1.184 -// if(local_predNode) {
1.185 -// delete _predNode;
1.186 -// local_predNode=false;
1.187 -// }
1.188 -// _predNode = &m;
1.189 -// return *this;
1.190 -// }
1.191 -
1.192 ///Sets the map storing the distances calculated by the algorithm.
1.193
1.194 ///Sets the map storing the distances calculated by the algorithm.
1.195 @@ -494,7 +426,6 @@
1.196 _curr_dist=1;
1.197 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.198 _pred->set(u,INVALID);
1.199 -// _predNode->set(u,INVALID);
1.200 _reached->set(u,false);
1.201 _processed->set(u,false);
1.202 }
1.203 @@ -537,7 +468,6 @@
1.204 _queue[_queue_head++]=m;
1.205 _reached->set(m,true);
1.206 _pred->set(m,e);
1.207 -// _pred_node->set(m,n);
1.208 _dist->set(m,_curr_dist);
1.209 }
1.210 return n;
1.211 @@ -745,13 +675,6 @@
1.212 ///must be called before using this function.
1.213 const PredMap &predMap() const { return *_pred;}
1.214
1.215 -// ///Returns a reference to the map of nodes of shortest paths.
1.216 -
1.217 -// ///Returns a reference to the NodeMap of the last but one nodes of the
1.218 -// ///shortest path tree.
1.219 -// ///\pre \ref run() must be called before using this function.
1.220 -// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.221 -
1.222 ///Checks if a node is reachable from the root.
1.223
1.224 ///Returns \c true if \c v is reachable from the root.
1.225 @@ -794,23 +717,6 @@
1.226 {
1.227 return new PredMap();
1.228 }
1.229 -// ///\brief The type of the map that stores the last but one
1.230 -// ///nodes of the shortest paths.
1.231 -// ///
1.232 -// ///The type of the map that stores the last but one
1.233 -// ///nodes of the shortest paths.
1.234 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.235 -// ///
1.236 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.237 -// ///Instantiates a PredNodeMap.
1.238 -
1.239 -// ///This function instantiates a \ref PredNodeMap.
1.240 -// ///\param G is the graph, to which
1.241 -// ///we would like to define the \ref PredNodeMap
1.242 -// static PredNodeMap *createPredNodeMap(const GR &G)
1.243 -// {
1.244 -// return new PredNodeMap();
1.245 -// }
1.246
1.247 ///The type of the map that indicates which nodes are processed.
1.248
1.249 @@ -891,8 +797,6 @@
1.250 void *_processed;
1.251 ///Pointer to the map of predecessors edges.
1.252 void *_pred;
1.253 -// ///Pointer to the map of predecessors nodes.
1.254 -// void *_predNode;
1.255 ///Pointer to the map of distances.
1.256 void *_dist;
1.257 ///Pointer to the source node.
1.258 @@ -904,7 +808,6 @@
1.259 /// This constructor does not require parameters, therefore it initiates
1.260 /// all of the attributes to default values (0, INVALID).
1.261 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.262 -// _predNode(0),
1.263 _dist(0), _source(INVALID) {}
1.264
1.265 /// Constructor.
1.266 @@ -916,7 +819,6 @@
1.267 /// \param s is the initial value of \ref _source
1.268 BfsWizardBase(const GR &g, Node s=INVALID) :
1.269 _g((void *)&g), _reached(0), _processed(0), _pred(0),
1.270 -// _predNode(0),
1.271 _dist(0), _source(s) {}
1.272
1.273 };
1.274 @@ -965,9 +867,6 @@
1.275 ///\brief The type of the map that stores the last
1.276 ///edges of the shortest paths.
1.277 typedef typename TR::PredMap PredMap;
1.278 -// ///\brief The type of the map that stores the last but one
1.279 -// ///nodes of the shortest paths.
1.280 -// typedef typename TR::PredNodeMap PredNodeMap;
1.281 ///The type of the map that stores the dists of the nodes.
1.282 typedef typename TR::DistMap DistMap;
1.283
1.284 @@ -999,7 +898,6 @@
1.285 alg.reachedMap(*(ReachedMap*)Base::_reached);
1.286 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1.287 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1.288 -// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.289 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1.290 alg.run(Base::_source);
1.291 }
1.292 @@ -1076,26 +974,6 @@
1.293 return BfsWizard<DefProcessedMapBase<T> >(*this);
1.294 }
1.295
1.296 -
1.297 -// template<class T>
1.298 -// struct DefPredNodeMapBase : public Base {
1.299 -// typedef T PredNodeMap;
1.300 -// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.301 -// DefPredNodeMapBase(const TR &b) : TR(b) {}
1.302 -// };
1.303 -
1.304 -// ///\brief \ref named-templ-param "Named parameter"
1.305 -// ///function for setting PredNodeMap type
1.306 -// ///
1.307 -// /// \ref named-templ-param "Named parameter"
1.308 -// ///function for setting PredNodeMap type
1.309 -// ///
1.310 -// template<class T>
1.311 -// BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.312 -// {
1.313 -// Base::_predNode=(void *)&t;
1.314 -// return BfsWizard<DefPredNodeMapBase<T> >(*this);
1.315 -// }
1.316
1.317 template<class T>
1.318 struct DefDistMapBase : public Base {