1.1 --- a/src/lemon/bfs.h Wed Mar 16 07:52:16 2005 +0000
1.2 +++ b/src/lemon/bfs.h Wed Mar 16 07:56:25 2005 +0000
1.3 @@ -20,36 +20,149 @@
1.4 ///\ingroup flowalgs
1.5 ///\file
1.6 ///\brief Bfs algorithm.
1.7 -///
1.8 -///\todo Revise Manual.
1.9
1.10 -#include <lemon/bin_heap.h>
1.11 +#include <lemon/list_graph.h>
1.12 +#include <lemon/graph_utils.h>
1.13 #include <lemon/invalid.h>
1.14 -#include <lemon/graph_utils.h>
1.15 +#include <lemon/error.h>
1.16 +#include <lemon/maps.h>
1.17
1.18 namespace lemon {
1.19
1.20 -/// \addtogroup flowalgs
1.21 -/// @{
1.22
1.23 +
1.24 + ///Default traits class of Bfs class.
1.25 +
1.26 + ///Default traits class of Bfs class.
1.27 + ///\param GR Graph type.
1.28 + template<class GR>
1.29 + struct BfsDefaultTraits
1.30 + {
1.31 + ///The graph type the algorithm runs on.
1.32 + typedef GR Graph;
1.33 + ///\brief The type of the map that stores the last
1.34 + ///edges of the shortest paths.
1.35 + ///
1.36 + ///The type of the map that stores the last
1.37 + ///edges of the shortest paths.
1.38 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.39 + ///
1.40 + typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.41 + ///Instantiates a PredMap.
1.42 +
1.43 + ///This function instantiates a \ref PredMap.
1.44 + ///\param G is the graph, to which we would like to define the PredMap.
1.45 + ///\todo The graph alone may be insufficient to initialize
1.46 + static PredMap *createPredMap(const GR &G)
1.47 + {
1.48 + return new PredMap(G);
1.49 + }
1.50 +// ///\brief The type of the map that stores the last but one
1.51 +// ///nodes of the shortest paths.
1.52 +// ///
1.53 +// ///The type of the map that stores the last but one
1.54 +// ///nodes of the shortest paths.
1.55 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.56 +// ///
1.57 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.58 +// ///Instantiates a PredNodeMap.
1.59 +
1.60 +// ///This function instantiates a \ref PredNodeMap.
1.61 +// ///\param G is the graph, to which
1.62 +// ///we would like to define the \ref PredNodeMap
1.63 +// static PredNodeMap *createPredNodeMap(const GR &G)
1.64 +// {
1.65 +// return new PredNodeMap();
1.66 +// }
1.67 +
1.68 + ///The type of the map that indicates which nodes are processed.
1.69 +
1.70 + ///The type of the map that indicates which nodes are processed.
1.71 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.72 + ///\todo named parameter to set this type, function to read and write.
1.73 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.74 + ///Instantiates a ProcessedMap.
1.75 +
1.76 + ///This function instantiates a \ref ProcessedMap.
1.77 + ///\param G is the graph, to which
1.78 + ///we would like to define the \ref ProcessedMap
1.79 + static ProcessedMap *createProcessedMap(const GR &G)
1.80 + {
1.81 + return new ProcessedMap();
1.82 + }
1.83 + ///The type of the map that indicates which nodes are reached.
1.84 +
1.85 + ///The type of the map that indicates which nodes are reached.
1.86 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.87 + ///\todo named parameter to set this type, function to read and write.
1.88 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.89 + ///Instantiates a ReachedMap.
1.90 +
1.91 + ///This function instantiates a \ref ReachedMap.
1.92 + ///\param G is the graph, to which
1.93 + ///we would like to define the \ref ReachedMap.
1.94 + static ReachedMap *createReachedMap(const GR &G)
1.95 + {
1.96 + return new ReachedMap(G);
1.97 + }
1.98 + ///The type of the map that stores the dists of the nodes.
1.99 +
1.100 + ///The type of the map that stores the dists of the nodes.
1.101 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.102 + ///
1.103 + typedef typename Graph::template NodeMap<int> DistMap;
1.104 + ///Instantiates a DistMap.
1.105 +
1.106 + ///This function instantiates a \ref DistMap.
1.107 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.108 + static DistMap *createDistMap(const GR &G)
1.109 + {
1.110 + return new DistMap(G);
1.111 + }
1.112 + };
1.113 +
1.114 ///%BFS algorithm class.
1.115 -
1.116 - ///This class provides an efficient implementation of %BFS algorithm.
1.117 - ///\param GR The graph type the algorithm runs on.
1.118 - ///This class does the same as Dijkstra does with constant 1 edge length,
1.119 - ///but it is faster.
1.120 +
1.121 + ///\ingroup flowalgs
1.122 + ///This class provides an efficient implementation of the %BFS algorithm.
1.123 ///
1.124 - ///\author Alpar Juttner
1.125 + ///\param GR The graph type the algorithm runs on. The default value is
1.126 + ///\ref ListGraph. The value of GR is not used directly by Bfs, it
1.127 + ///is only passed to \ref BfsDefaultTraits.
1.128 + ///\param TR Traits class to set various data types used by the algorithm.
1.129 + ///The default traits class is
1.130 + ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.131 + ///See \ref BfsDefaultTraits for the documentation of
1.132 + ///a Bfs traits class.
1.133 + ///
1.134 + ///\author Jacint Szabo and Alpar Juttner
1.135 + ///\todo A compare object would be nice.
1.136
1.137 #ifdef DOXYGEN
1.138 - template <typename GR>
1.139 + template <typename GR,
1.140 + typename TR>
1.141 #else
1.142 - template <typename GR>
1.143 + template <typename GR=ListGraph,
1.144 + typename TR=BfsDefaultTraits<GR> >
1.145 #endif
1.146 - class Bfs{
1.147 + class Bfs {
1.148 public:
1.149 + /**
1.150 + * \brief \ref Exception for uninitialized parameters.
1.151 + *
1.152 + * This error represents problems in the initialization
1.153 + * of the parameters of the algorithms.
1.154 + */
1.155 + class UninitializedParameter : public lemon::UninitializedParameter {
1.156 + public:
1.157 + virtual const char* exceptionName() const {
1.158 + return "lemon::Bfs::UninitializedParameter";
1.159 + }
1.160 + };
1.161 +
1.162 + typedef TR Traits;
1.163 ///The type of the underlying graph.
1.164 - typedef GR Graph;
1.165 + typedef typename TR::Graph Graph;
1.166 ///\e
1.167 typedef typename Graph::Node Node;
1.168 ///\e
1.169 @@ -61,68 +174,211 @@
1.170
1.171 ///\brief The type of the map that stores the last
1.172 ///edges of the shortest paths.
1.173 - typedef typename Graph::template NodeMap<Edge> PredMap;
1.174 - ///\brief The type of the map that stores the last but one
1.175 - ///nodes of the shortest paths.
1.176 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.177 + typedef typename TR::PredMap PredMap;
1.178 +// ///\brief The type of the map that stores the last but one
1.179 +// ///nodes of the shortest paths.
1.180 +// typedef typename TR::PredNodeMap PredNodeMap;
1.181 + ///The type of the map indicating which nodes are reached.
1.182 + typedef typename TR::ReachedMap ReachedMap;
1.183 + ///The type of the map indicating which nodes are processed.
1.184 + typedef typename TR::ProcessedMap ProcessedMap;
1.185 ///The type of the map that stores the dists of the nodes.
1.186 - typedef typename Graph::template NodeMap<int> DistMap;
1.187 -
1.188 + typedef typename TR::DistMap DistMap;
1.189 private:
1.190 /// Pointer to the underlying graph.
1.191 const Graph *G;
1.192 ///Pointer to the map of predecessors edges.
1.193 - PredMap *predecessor;
1.194 - ///Indicates if \ref predecessor is locally allocated (\c true) or not.
1.195 - bool local_predecessor;
1.196 - ///Pointer to the map of predecessors nodes.
1.197 - PredNodeMap *pred_node;
1.198 - ///Indicates if \ref pred_node is locally allocated (\c true) or not.
1.199 - bool local_pred_node;
1.200 + PredMap *_pred;
1.201 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.202 + bool local_pred;
1.203 +// ///Pointer to the map of predecessors nodes.
1.204 +// PredNodeMap *_predNode;
1.205 +// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.206 +// bool local_predNode;
1.207 ///Pointer to the map of distances.
1.208 - DistMap *distance;
1.209 - ///Indicates if \ref distance is locally allocated (\c true) or not.
1.210 - bool local_distance;
1.211 + DistMap *_dist;
1.212 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.213 + bool local_dist;
1.214 + ///Pointer to the map of reached status of the nodes.
1.215 + ReachedMap *_reached;
1.216 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.217 + bool local_reached;
1.218 + ///Pointer to the map of processed status of the nodes.
1.219 + ProcessedMap *_processed;
1.220 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.221 + bool local_processed;
1.222
1.223 - ///The source node of the last execution.
1.224 - Node source;
1.225 + std::vector<typename Graph::Node> _queue;
1.226 + int _queue_head,_queue_tail,_queue_next_dist;
1.227 + int _curr_dist;
1.228 +// ///The source node of the last execution.
1.229 +// Node source;
1.230
1.231 -
1.232 - ///Initializes the maps.
1.233 - void init_maps()
1.234 + ///Creates the maps if necessary.
1.235 +
1.236 + ///\todo Error if \c G are \c NULL.
1.237 + ///\todo Better memory allocation (instead of new).
1.238 + void create_maps()
1.239 {
1.240 - if(!predecessor) {
1.241 - local_predecessor = true;
1.242 - predecessor = new PredMap(*G);
1.243 + if(!_pred) {
1.244 + local_pred = true;
1.245 + _pred = Traits::createPredMap(*G);
1.246 }
1.247 - if(!pred_node) {
1.248 - local_pred_node = true;
1.249 - pred_node = new PredNodeMap(*G);
1.250 +// if(!_predNode) {
1.251 +// local_predNode = true;
1.252 +// _predNode = Traits::createPredNodeMap(*G);
1.253 +// }
1.254 + if(!_dist) {
1.255 + local_dist = true;
1.256 + _dist = Traits::createDistMap(*G);
1.257 }
1.258 - if(!distance) {
1.259 - local_distance = true;
1.260 - distance = new DistMap(*G);
1.261 + if(!_reached) {
1.262 + local_reached = true;
1.263 + _reached = Traits::createReachedMap(*G);
1.264 + }
1.265 + if(!_processed) {
1.266 + local_processed = true;
1.267 + _processed = Traits::createProcessedMap(*G);
1.268 }
1.269 }
1.270
1.271 - public :
1.272 + public :
1.273 +
1.274 + ///\name Named template parameters
1.275 +
1.276 + ///@{
1.277 +
1.278 + template <class T>
1.279 + struct DefPredMapTraits : public Traits {
1.280 + typedef T PredMap;
1.281 + static PredMap *createPredMap(const Graph &G)
1.282 + {
1.283 + throw UninitializedParameter();
1.284 + }
1.285 + };
1.286 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.287 +
1.288 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.289 + ///
1.290 + template <class T>
1.291 + class DefPredMap : public Bfs< Graph,
1.292 + DefPredMapTraits<T> > { };
1.293 +
1.294 +// template <class T>
1.295 +// struct DefPredNodeMapTraits : public Traits {
1.296 +// typedef T PredNodeMap;
1.297 +// static PredNodeMap *createPredNodeMap(const Graph &G)
1.298 +// {
1.299 +// throw UninitializedParameter();
1.300 +// }
1.301 +// };
1.302 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.303 +
1.304 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.305 +// ///
1.306 +// template <class T>
1.307 +// class DefPredNodeMap : public Bfs< Graph,
1.308 +// LengthMap,
1.309 +// DefPredNodeMapTraits<T> > { };
1.310 +
1.311 + template <class T>
1.312 + struct DefDistMapTraits : public Traits {
1.313 + typedef T DistMap;
1.314 + static DistMap *createDistMap(const Graph &G)
1.315 + {
1.316 + throw UninitializedParameter();
1.317 + }
1.318 + };
1.319 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.320 +
1.321 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.322 + ///
1.323 + template <class T>
1.324 + class DefDistMap : public Bfs< Graph,
1.325 + DefDistMapTraits<T> > { };
1.326 +
1.327 + template <class T>
1.328 + struct DefReachedMapTraits : public Traits {
1.329 + typedef T ReachedMap;
1.330 + static ReachedMap *createReachedMap(const Graph &G)
1.331 + {
1.332 + throw UninitializedParameter();
1.333 + }
1.334 + };
1.335 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.336 +
1.337 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.338 + ///
1.339 + template <class T>
1.340 + class DefReachedMap : public Bfs< Graph,
1.341 + DefReachedMapTraits<T> > { };
1.342 +
1.343 + struct DefGraphReachedMapTraits : public Traits {
1.344 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.345 + static ReachedMap *createReachedMap(const Graph &G)
1.346 + {
1.347 + return new ReachedMap(G);
1.348 + }
1.349 + };
1.350 + template <class T>
1.351 + struct DefProcessedMapTraits : public Traits {
1.352 + typedef T ProcessedMap;
1.353 + static ProcessedMap *createProcessedMap(const Graph &G)
1.354 + {
1.355 + throw UninitializedParameter();
1.356 + }
1.357 + };
1.358 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.359 +
1.360 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.361 + ///
1.362 + template <class T>
1.363 + class DefProcessedMap : public Bfs< Graph,
1.364 + DefProcessedMapTraits<T> > { };
1.365 +
1.366 + struct DefGraphProcessedMapTraits : public Traits {
1.367 + typedef typename Graph::template NodeMap<bool> ProcessedMap;
1.368 + static ProcessedMap *createProcessedMap(const Graph &G)
1.369 + {
1.370 + return new ProcessedMap(G);
1.371 + }
1.372 + };
1.373 + ///\brief \ref named-templ-param "Named parameter"
1.374 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.375 + ///
1.376 + ///\ref named-templ-param "Named parameter"
1.377 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.378 + ///If you don't set it explicitely, it will be automatically allocated.
1.379 + template <class T>
1.380 + class DefProcessedMapToBeDefaultMap :
1.381 + public Bfs< Graph,
1.382 + DefGraphProcessedMapTraits> { };
1.383 +
1.384 + ///@}
1.385 +
1.386 + public:
1.387 +
1.388 ///Constructor.
1.389
1.390 ///\param _G the graph the algorithm will run on.
1.391 ///
1.392 Bfs(const Graph& _G) :
1.393 G(&_G),
1.394 - predecessor(NULL), local_predecessor(false),
1.395 - pred_node(NULL), local_pred_node(false),
1.396 - distance(NULL), local_distance(false)
1.397 + _pred(NULL), local_pred(false),
1.398 +// _predNode(NULL), local_predNode(false),
1.399 + _dist(NULL), local_dist(false),
1.400 + _reached(NULL), local_reached(false),
1.401 + _processed(NULL), local_processed(false)
1.402 { }
1.403
1.404 ///Destructor.
1.405 ~Bfs()
1.406 {
1.407 - if(local_predecessor) delete predecessor;
1.408 - if(local_pred_node) delete pred_node;
1.409 - if(local_distance) delete distance;
1.410 + if(local_pred) delete _pred;
1.411 +// if(local_predNode) delete _predNode;
1.412 + if(local_dist) delete _dist;
1.413 + if(local_reached) delete _reached;
1.414 + if(local_processed) delete _processed;
1.415 }
1.416
1.417 ///Sets the map storing the predecessor edges.
1.418 @@ -132,33 +388,67 @@
1.419 ///it will allocate one. The destuctor deallocates this
1.420 ///automatically allocated map, of course.
1.421 ///\return <tt> (*this) </tt>
1.422 - Bfs &setPredMap(PredMap &m)
1.423 + Bfs &predMap(PredMap &m)
1.424 {
1.425 - if(local_predecessor) {
1.426 - delete predecessor;
1.427 - local_predecessor=false;
1.428 + if(local_pred) {
1.429 + delete _pred;
1.430 + local_pred=false;
1.431 }
1.432 - predecessor = &m;
1.433 + _pred = &m;
1.434 return *this;
1.435 }
1.436
1.437 - ///Sets the map storing the predecessor nodes.
1.438 + ///Sets the map indicating the reached nodes.
1.439
1.440 - ///Sets the map storing the predecessor nodes.
1.441 + ///Sets the map indicating the reached nodes.
1.442 ///If you don't use this function before calling \ref run(),
1.443 ///it will allocate one. The destuctor deallocates this
1.444 ///automatically allocated map, of course.
1.445 ///\return <tt> (*this) </tt>
1.446 - Bfs &setPredNodeMap(PredNodeMap &m)
1.447 + Bfs &reachedMap(ReachedMap &m)
1.448 {
1.449 - if(local_pred_node) {
1.450 - delete pred_node;
1.451 - local_pred_node=false;
1.452 + if(local_reached) {
1.453 + delete _reached;
1.454 + local_reached=false;
1.455 }
1.456 - pred_node = &m;
1.457 + _reached = &m;
1.458 return *this;
1.459 }
1.460
1.461 + ///Sets the map indicating the processed nodes.
1.462 +
1.463 + ///Sets the map indicating the processed nodes.
1.464 + ///If you don't use this function before calling \ref run(),
1.465 + ///it will allocate one. The destuctor deallocates this
1.466 + ///automatically allocated map, of course.
1.467 + ///\return <tt> (*this) </tt>
1.468 + Bfs &processedMap(ProcessedMap &m)
1.469 + {
1.470 + if(local_processed) {
1.471 + delete _processed;
1.472 + local_processed=false;
1.473 + }
1.474 + _processed = &m;
1.475 + return *this;
1.476 + }
1.477 +
1.478 +// ///Sets the map storing the predecessor nodes.
1.479 +
1.480 +// ///Sets the map storing the predecessor nodes.
1.481 +// ///If you don't use this function before calling \ref run(),
1.482 +// ///it will allocate one. The destuctor deallocates this
1.483 +// ///automatically allocated map, of course.
1.484 +// ///\return <tt> (*this) </tt>
1.485 +// Bfs &predNodeMap(PredNodeMap &m)
1.486 +// {
1.487 +// if(local_predNode) {
1.488 +// delete _predNode;
1.489 +// local_predNode=false;
1.490 +// }
1.491 +// _predNode = &m;
1.492 +// return *this;
1.493 +// }
1.494 +
1.495 ///Sets the map storing the distances calculated by the algorithm.
1.496
1.497 ///Sets the map storing the distances calculated by the algorithm.
1.498 @@ -166,122 +456,652 @@
1.499 ///it will allocate one. The destuctor deallocates this
1.500 ///automatically allocated map, of course.
1.501 ///\return <tt> (*this) </tt>
1.502 - Bfs &setDistMap(DistMap &m)
1.503 + Bfs &distMap(DistMap &m)
1.504 {
1.505 - if(local_distance) {
1.506 - delete distance;
1.507 - local_distance=false;
1.508 + if(local_dist) {
1.509 + delete _dist;
1.510 + local_dist=false;
1.511 }
1.512 - distance = &m;
1.513 + _dist = &m;
1.514 return *this;
1.515 }
1.516 -
1.517 - ///Runs %BFS algorithm from node \c s.
1.518
1.519 - ///This method runs the %BFS algorithm from a root node \c s
1.520 - ///in order to
1.521 - ///compute a
1.522 - ///shortest path to each node. The algorithm computes
1.523 - ///- The %BFS tree.
1.524 - ///- The distance of each node from the root.
1.525 -
1.526 - void run(Node s) {
1.527 -
1.528 - init_maps();
1.529 -
1.530 - source = s;
1.531 -
1.532 + public:
1.533 + ///\name Execution control
1.534 + ///The simplest way to execute the algorithm is to use
1.535 + ///one of the member functions called \c run(...).
1.536 + ///\n
1.537 + ///If you need more control on the execution,
1.538 + ///first you must call \ref init(), then you can add several source nodes
1.539 + ///with \ref addSource().
1.540 + ///Finally \ref start() will perform the actual path
1.541 + ///computation.
1.542 +
1.543 + ///@{
1.544 +
1.545 + ///Initializes the internal data structures.
1.546 +
1.547 + ///Initializes the internal data structures.
1.548 + ///
1.549 + void init()
1.550 + {
1.551 + create_maps();
1.552 + _queue.resize(countNodes(*G));
1.553 + _queue_head=_queue_tail=0;
1.554 + _curr_dist=1;
1.555 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.556 - predecessor->set(u,INVALID);
1.557 - pred_node->set(u,INVALID);
1.558 + _pred->set(u,INVALID);
1.559 +// _predNode->set(u,INVALID);
1.560 + _reached->set(u,false);
1.561 + _processed->set(u,false);
1.562 }
1.563 -
1.564 - int N = countNodes(*G);
1.565 - std::vector<typename Graph::Node> Q(N);
1.566 - int Qh=0;
1.567 - int Qt=0;
1.568 -
1.569 - Q[Qh++]=source;
1.570 - distance->set(s, 0);
1.571 - do {
1.572 - Node m;
1.573 - Node n=Q[Qt++];
1.574 - int d= (*distance)[n]+1;
1.575 -
1.576 - for(OutEdgeIt e(*G,n);e!=INVALID;++e)
1.577 - if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
1.578 - Q[Qh++]=m;
1.579 - predecessor->set(m,e);
1.580 - pred_node->set(m,n);
1.581 - distance->set(m,d);
1.582 - }
1.583 - } while(Qt!=Qh);
1.584 }
1.585
1.586 - ///The distance of a node from the root.
1.587 + ///Adds a new source node.
1.588
1.589 - ///Returns the distance of a node from the root.
1.590 + ///Adds a new source node to the set of nodes to be processed.
1.591 + ///
1.592 + void addSource(Node s)
1.593 + {
1.594 + if(!(*_reached)[s])
1.595 + {
1.596 + _reached->set(s,true);
1.597 + _pred->set(s,INVALID);
1.598 + _dist->set(s,0);
1.599 + _queue[_queue_head++]=s;
1.600 + _queue_next_dist=_queue_head;
1.601 + }
1.602 + }
1.603 +
1.604 + ///Processes the next node.
1.605 +
1.606 + ///Processes the next node.
1.607 + ///
1.608 + ///\warning The queue must not be empty!
1.609 + void processNextNode()
1.610 + {
1.611 + if(_queue_tail==_queue_next_dist) {
1.612 + _curr_dist++;
1.613 + _queue_next_dist=_queue_head;
1.614 + }
1.615 + Node n=_queue[_queue_tail++];
1.616 + _processed->set(n,true);
1.617 + Node m;
1.618 + for(OutEdgeIt e(*G,n);e!=INVALID;++e)
1.619 + if(!(*_reached)[m=G->target(e)]) {
1.620 + _queue[_queue_head++]=m;
1.621 + _reached->set(m,true);
1.622 + _pred->set(m,e);
1.623 +// _pred_node->set(m,n);
1.624 + _dist->set(m,_curr_dist);
1.625 + }
1.626 + }
1.627 +
1.628 + ///\brief Returns \c false if there are nodes
1.629 + ///to be processed in the queue
1.630 + ///
1.631 + ///Returns \c false if there are nodes
1.632 + ///to be processed in the queue
1.633 + bool emptyQueue() { return _queue_tail==_queue_head; }
1.634 + ///Returns the number of the nodes to be processed.
1.635 +
1.636 + ///Returns the number of the nodes to be processed in the queue.
1.637 + ///
1.638 + int queueSize() { return _queue_head-_queue_tail; }
1.639 +
1.640 + ///Executes the algorithm.
1.641 +
1.642 + ///Executes the algorithm.
1.643 + ///
1.644 + ///\pre init() must be called and at least one node should be added
1.645 + ///with addSource() before using this function.
1.646 + ///
1.647 + ///This method runs the %BFS algorithm from the root node(s)
1.648 + ///in order to
1.649 + ///compute the
1.650 + ///shortest path to each node. The algorithm computes
1.651 + ///- The shortest path tree.
1.652 + ///- The distance of each node from the root(s).
1.653 + ///
1.654 + void start()
1.655 + {
1.656 + while ( !emptyQueue() ) processNextNode();
1.657 + }
1.658 +
1.659 + ///Executes the algorithm until \c dest is reached.
1.660 +
1.661 + ///Executes the algorithm until \c dest is reached.
1.662 + ///
1.663 + ///\pre init() must be called and at least one node should be added
1.664 + ///with addSource() before using this function.
1.665 + ///
1.666 + ///This method runs the %BFS algorithm from the root node(s)
1.667 + ///in order to
1.668 + ///compute the
1.669 + ///shortest path to \c dest. The algorithm computes
1.670 + ///- The shortest path to \c dest.
1.671 + ///- The distance of \c dest from the root(s).
1.672 + ///
1.673 + void start(Node dest)
1.674 + {
1.675 + while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
1.676 + }
1.677 +
1.678 + ///Executes the algorithm until a condition is met.
1.679 +
1.680 + ///Executes the algorithm until a condition is met.
1.681 + ///
1.682 + ///\pre init() must be called and at least one node should be added
1.683 + ///with addSource() before using this function.
1.684 + ///
1.685 + ///\param nm must be a bool (or convertible) node map. The algorithm
1.686 + ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
1.687 + template<class NM>
1.688 + void start(const NM &nm)
1.689 + {
1.690 + while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
1.691 + }
1.692 +
1.693 + ///Runs %BFS algorithm from node \c s.
1.694 +
1.695 + ///This method runs the %BFS algorithm from a root node \c s
1.696 + ///in order to
1.697 + ///compute the
1.698 + ///shortest path to each node. The algorithm computes
1.699 + ///- The shortest path tree.
1.700 + ///- The distance of each node from the root.
1.701 + ///
1.702 + ///\note d.run(s) is just a shortcut of the following code.
1.703 + ///\code
1.704 + /// d.init();
1.705 + /// d.addSource(s);
1.706 + /// d.start();
1.707 + ///\endcode
1.708 + void run(Node s) {
1.709 + init();
1.710 + addSource(s);
1.711 + start();
1.712 + }
1.713 +
1.714 + ///Finds the shortest path between \c s and \c t.
1.715 +
1.716 + ///Finds the shortest path between \c s and \c t.
1.717 + ///
1.718 + ///\return The length of the shortest s---t path if there exists one,
1.719 + ///0 otherwise.
1.720 + ///\note Apart from the return value, d.run(s) is
1.721 + ///just a shortcut of the following code.
1.722 + ///\code
1.723 + /// d.init();
1.724 + /// d.addSource(s);
1.725 + /// d.start(t);
1.726 + ///\endcode
1.727 + int run(Node s,Node t) {
1.728 + init();
1.729 + addSource(s);
1.730 + start(t);
1.731 + return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
1.732 + }
1.733 +
1.734 + ///@}
1.735 +
1.736 + ///\name Query Functions
1.737 + ///The result of the %BFS algorithm can be obtained using these
1.738 + ///functions.\n
1.739 + ///Before the use of these functions,
1.740 + ///either run() or start() must be called.
1.741 +
1.742 + ///@{
1.743 +
1.744 + ///The distance of a node from the root(s).
1.745 +
1.746 + ///Returns the distance of a node from the root(s).
1.747 ///\pre \ref run() must be called before using this function.
1.748 - ///\warning If node \c v in unreachable from the root the return value
1.749 + ///\warning If node \c v in unreachable from the root(s) the return value
1.750 ///of this funcion is undefined.
1.751 - int dist(Node v) const { return (*distance)[v]; }
1.752 + int dist(Node v) const { return (*_dist)[v]; }
1.753
1.754 - ///Returns the 'previous edge' of the %BFS path tree.
1.755 + ///Returns the 'previous edge' of the shortest path tree.
1.756
1.757 - ///For a node \c v it returns the 'previous edge' of the %BFS tree,
1.758 - ///i.e. it returns the last edge of a shortest path from the root to \c
1.759 + ///For a node \c v it returns the 'previous edge'
1.760 + ///of the shortest path tree,
1.761 + ///i.e. it returns the last edge of a shortest path from the root(s) to \c
1.762 ///v. It is \ref INVALID
1.763 - ///if \c v is unreachable from the root or if \c v=s. The
1.764 - ///%BFS tree used here is equal to the %BFS tree used in
1.765 - ///\ref predNode(Node v). \pre \ref run() must be called before using
1.766 + ///if \c v is unreachable from the root(s) or \c v is a root. The
1.767 + ///shortest path tree used here is equal to the shortest path tree used in
1.768 + ///\ref predNode(Node v).
1.769 + ///\pre Either \ref run() or \ref start() must be called before using
1.770 ///this function.
1.771 - Edge pred(Node v) const { return (*predecessor)[v]; }
1.772 + ///\todo predEdge could be a better name.
1.773 + Edge pred(Node v) const { return (*_pred)[v];}
1.774
1.775 - ///Returns the 'previous node' of the %BFS tree.
1.776 + ///Returns the 'previous node' of the shortest path tree.
1.777
1.778 - ///For a node \c v it returns the 'previous node' on the %BFS tree,
1.779 + ///For a node \c v it returns the 'previous node'
1.780 + ///of the shortest path tree,
1.781 ///i.e. it returns the last but one node from a shortest path from the
1.782 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.783 - ///\c v=s. The shortest path tree used here is equal to the %BFS
1.784 - ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.785 + ///root(a) to \c /v.
1.786 + ///It is INVALID if \c v is unreachable from the root(s) or
1.787 + ///if \c v itself a root.
1.788 + ///The shortest path tree used here is equal to the shortest path
1.789 + ///tree used in \ref pred(Node v).
1.790 + ///\pre Either \ref run() or \ref start() must be called before
1.791 ///using this function.
1.792 - Node predNode(Node v) const { return (*pred_node)[v]; }
1.793 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.794 + G->source((*_pred)[v]); }
1.795
1.796 ///Returns a reference to the NodeMap of distances.
1.797 -
1.798 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.799 +
1.800 + ///Returns a reference to the NodeMap of distances.
1.801 + ///\pre Either \ref run() or \ref init() must
1.802 ///be called before using this function.
1.803 - const DistMap &distMap() const { return *distance;}
1.804 + const DistMap &distMap() const { return *_dist;}
1.805
1.806 - ///Returns a reference to the %BFS tree map.
1.807 + ///Returns a reference to the shortest path tree map.
1.808
1.809 ///Returns a reference to the NodeMap of the edges of the
1.810 - ///%BFS tree.
1.811 - ///\pre \ref run() must be called before using this function.
1.812 - const PredMap &predMap() const { return *predecessor;}
1.813 + ///shortest path tree.
1.814 + ///\pre Either \ref run() or \ref init()
1.815 + ///must be called before using this function.
1.816 + const PredMap &predMap() const { return *_pred;}
1.817
1.818 - ///Returns a reference to the map of last but one nodes of shortest paths.
1.819 +// ///Returns a reference to the map of nodes of shortest paths.
1.820
1.821 - ///Returns a reference to the NodeMap of the last but one nodes on the
1.822 - ///%BFS tree.
1.823 - ///\pre \ref run() must be called before using this function.
1.824 - const PredNodeMap &predNodeMap() const { return *pred_node;}
1.825 +// ///Returns a reference to the NodeMap of the last but one nodes of the
1.826 +// ///shortest path tree.
1.827 +// ///\pre \ref run() must be called before using this function.
1.828 +// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.829
1.830 ///Checks if a node is reachable from the root.
1.831
1.832 ///Returns \c true if \c v is reachable from the root.
1.833 - ///\note The root node is reported to be reached!
1.834 + ///\warning The source nodes are inditated as unreached.
1.835 + ///\pre Either \ref run() or \ref start()
1.836 + ///must be called before using this function.
1.837 ///
1.838 - ///\pre \ref run() must be called before using this function.
1.839 + bool reached(Node v) { return (*_reached)[v]; }
1.840 +
1.841 + ///@}
1.842 + };
1.843 +
1.844 + ///Default traits class of Bfs function.
1.845 +
1.846 + ///Default traits class of Bfs function.
1.847 + ///\param GR Graph type.
1.848 + template<class GR>
1.849 + struct BfsWizardDefaultTraits
1.850 + {
1.851 + ///The graph type the algorithm runs on.
1.852 + typedef GR Graph;
1.853 + ///\brief The type of the map that stores the last
1.854 + ///edges of the shortest paths.
1.855 + ///
1.856 + ///The type of the map that stores the last
1.857 + ///edges of the shortest paths.
1.858 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.859 ///
1.860 - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.861 + typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
1.862 + ///Instantiates a PredMap.
1.863 +
1.864 + ///This function instantiates a \ref PredMap.
1.865 + ///\param G is the graph, to which we would like to define the PredMap.
1.866 + ///\todo The graph alone may be insufficient to initialize
1.867 + static PredMap *createPredMap(const GR &G)
1.868 + {
1.869 + return new PredMap();
1.870 + }
1.871 +// ///\brief The type of the map that stores the last but one
1.872 +// ///nodes of the shortest paths.
1.873 +// ///
1.874 +// ///The type of the map that stores the last but one
1.875 +// ///nodes of the shortest paths.
1.876 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.877 +// ///
1.878 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.879 +// ///Instantiates a PredNodeMap.
1.880 +
1.881 +// ///This function instantiates a \ref PredNodeMap.
1.882 +// ///\param G is the graph, to which
1.883 +// ///we would like to define the \ref PredNodeMap
1.884 +// static PredNodeMap *createPredNodeMap(const GR &G)
1.885 +// {
1.886 +// return new PredNodeMap();
1.887 +// }
1.888 +
1.889 + ///The type of the map that indicates which nodes are processed.
1.890 +
1.891 + ///The type of the map that indicates which nodes are processed.
1.892 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.893 + ///\todo named parameter to set this type, function to read and write.
1.894 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.895 + ///Instantiates a ProcessedMap.
1.896 +
1.897 + ///This function instantiates a \ref ProcessedMap.
1.898 + ///\param G is the graph, to which
1.899 + ///we would like to define the \ref ProcessedMap
1.900 + static ProcessedMap *createProcessedMap(const GR &G)
1.901 + {
1.902 + return new ProcessedMap();
1.903 + }
1.904 + ///The type of the map that indicates which nodes are reached.
1.905 +
1.906 + ///The type of the map that indicates which nodes are reached.
1.907 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.908 + ///\todo named parameter to set this type, function to read and write.
1.909 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.910 + ///Instantiates a ReachedMap.
1.911 +
1.912 + ///This function instantiates a \ref ReachedMap.
1.913 + ///\param G is the graph, to which
1.914 + ///we would like to define the \ref ReachedMap.
1.915 + static ReachedMap *createReachedMap(const GR &G)
1.916 + {
1.917 + return new ReachedMap(G);
1.918 + }
1.919 + ///The type of the map that stores the dists of the nodes.
1.920 +
1.921 + ///The type of the map that stores the dists of the nodes.
1.922 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.923 + ///
1.924 + typedef NullMap<typename Graph::Node,int> DistMap;
1.925 + ///Instantiates a DistMap.
1.926 +
1.927 + ///This function instantiates a \ref DistMap.
1.928 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.929 + static DistMap *createDistMap(const GR &G)
1.930 + {
1.931 + return new DistMap();
1.932 + }
1.933 + };
1.934 +
1.935 + /// Default traits used by \ref BfsWizard
1.936 +
1.937 + /// To make it easier to use Bfs algorithm
1.938 + ///we have created a wizard class.
1.939 + /// This \ref BfsWizard class needs default traits,
1.940 + ///as well as the \ref Bfs class.
1.941 + /// The \ref BfsWizardBase is a class to be the default traits of the
1.942 + /// \ref BfsWizard class.
1.943 + template<class GR>
1.944 + class BfsWizardBase : public BfsWizardDefaultTraits<GR>
1.945 + {
1.946 +
1.947 + typedef BfsWizardDefaultTraits<GR> Base;
1.948 + protected:
1.949 + /// Type of the nodes in the graph.
1.950 + typedef typename Base::Graph::Node Node;
1.951 +
1.952 + /// Pointer to the underlying graph.
1.953 + void *_g;
1.954 + ///Pointer to the map of reached nodes.
1.955 + void *_reached;
1.956 + ///Pointer to the map of processed nodes.
1.957 + void *_processed;
1.958 + ///Pointer to the map of predecessors edges.
1.959 + void *_pred;
1.960 +// ///Pointer to the map of predecessors nodes.
1.961 +// void *_predNode;
1.962 + ///Pointer to the map of distances.
1.963 + void *_dist;
1.964 + ///Pointer to the source node.
1.965 + Node _source;
1.966 +
1.967 + public:
1.968 + /// Constructor.
1.969 +
1.970 + /// This constructor does not require parameters, therefore it initiates
1.971 + /// all of the attributes to default values (0, INVALID).
1.972 + BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.973 +// _predNode(0),
1.974 + _dist(0), _source(INVALID) {}
1.975 +
1.976 + /// Constructor.
1.977 +
1.978 + /// This constructor requires some parameters,
1.979 + /// listed in the parameters list.
1.980 + /// Others are initiated to 0.
1.981 + /// \param g is the initial value of \ref _g
1.982 + /// \param s is the initial value of \ref _source
1.983 + BfsWizardBase(const GR &g, Node s=INVALID) :
1.984 + _g((void *)&g), _reached(0), _processed(0), _pred(0),
1.985 +// _predNode(0),
1.986 + _dist(0), _source(s) {}
1.987 +
1.988 + };
1.989 +
1.990 + /// A class to make the usage of Bfs algorithm easier
1.991 +
1.992 + /// This class is created to make it easier to use Bfs algorithm.
1.993 + /// It uses the functions and features of the plain \ref Bfs,
1.994 + /// but it is much simpler to use it.
1.995 + ///
1.996 + /// Simplicity means that the way to change the types defined
1.997 + /// in the traits class is based on functions that returns the new class
1.998 + /// and not on templatable built-in classes.
1.999 + /// When using the plain \ref Bfs
1.1000 + /// the new class with the modified type comes from
1.1001 + /// the original class by using the ::
1.1002 + /// operator. In the case of \ref BfsWizard only
1.1003 + /// a function have to be called and it will
1.1004 + /// return the needed class.
1.1005 + ///
1.1006 + /// It does not have own \ref run method. When its \ref run method is called
1.1007 + /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
1.1008 + /// method of it.
1.1009 + template<class TR>
1.1010 + class BfsWizard : public TR
1.1011 + {
1.1012 + typedef TR Base;
1.1013 +
1.1014 + ///The type of the underlying graph.
1.1015 + typedef typename TR::Graph Graph;
1.1016 + //\e
1.1017 + typedef typename Graph::Node Node;
1.1018 + //\e
1.1019 + typedef typename Graph::NodeIt NodeIt;
1.1020 + //\e
1.1021 + typedef typename Graph::Edge Edge;
1.1022 + //\e
1.1023 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1024 +
1.1025 + ///\brief The type of the map that stores
1.1026 + ///the reached nodes
1.1027 + typedef typename TR::ReachedMap ReachedMap;
1.1028 + ///\brief The type of the map that stores
1.1029 + ///the processed nodes
1.1030 + typedef typename TR::ProcessedMap ProcessedMap;
1.1031 + ///\brief The type of the map that stores the last
1.1032 + ///edges of the shortest paths.
1.1033 + typedef typename TR::PredMap PredMap;
1.1034 +// ///\brief The type of the map that stores the last but one
1.1035 +// ///nodes of the shortest paths.
1.1036 +// typedef typename TR::PredNodeMap PredNodeMap;
1.1037 + ///The type of the map that stores the dists of the nodes.
1.1038 + typedef typename TR::DistMap DistMap;
1.1039 +
1.1040 +public:
1.1041 + /// Constructor.
1.1042 + BfsWizard() : TR() {}
1.1043 +
1.1044 + /// Constructor that requires parameters.
1.1045 +
1.1046 + /// Constructor that requires parameters.
1.1047 + /// These parameters will be the default values for the traits class.
1.1048 + BfsWizard(const Graph &g, Node s=INVALID) :
1.1049 + TR(g,s) {}
1.1050 +
1.1051 + ///Copy constructor
1.1052 + BfsWizard(const TR &b) : TR(b) {}
1.1053 +
1.1054 + ~BfsWizard() {}
1.1055 +
1.1056 + ///Runs Bfs algorithm from a given node.
1.1057 +
1.1058 + ///Runs Bfs algorithm from a given node.
1.1059 + ///The node can be given by the \ref source function.
1.1060 + void run()
1.1061 + {
1.1062 + if(Base::_source==INVALID) throw UninitializedParameter();
1.1063 + Bfs<Graph,TR> alg(*(Graph*)Base::_g);
1.1064 + if(Base::_reached)
1.1065 + alg.reachedMap(*(ReachedMap*)Base::_reached);
1.1066 + if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1.1067 + if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1.1068 +// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.1069 + if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1.1070 + alg.run(Base::_source);
1.1071 + }
1.1072 +
1.1073 + ///Runs Bfs algorithm from the given node.
1.1074 +
1.1075 + ///Runs Bfs algorithm from the given node.
1.1076 + ///\param s is the given source.
1.1077 + void run(Node s)
1.1078 + {
1.1079 + Base::_source=s;
1.1080 + run();
1.1081 + }
1.1082 +
1.1083 + template<class T>
1.1084 + struct DefPredMapBase : public Base {
1.1085 + typedef T PredMap;
1.1086 + static PredMap *createPredMap(const Graph &G) { return 0; };
1.1087 + DefPredMapBase(const Base &b) : Base(b) {}
1.1088 + };
1.1089 +
1.1090 + ///\brief \ref named-templ-param "Named parameter"
1.1091 + ///function for setting PredMap
1.1092 + ///
1.1093 + /// \ref named-templ-param "Named parameter"
1.1094 + ///function for setting PredMap
1.1095 + ///
1.1096 + template<class T>
1.1097 + BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1098 + {
1.1099 + Base::_pred=(void *)&t;
1.1100 + return BfsWizard<DefPredMapBase<T> >(*this);
1.1101 + }
1.1102 +
1.1103 +
1.1104 + template<class T>
1.1105 + struct DefReachedMapBase : public Base {
1.1106 + typedef T ReachedMap;
1.1107 + static ReachedMap *createReachedMap(const Graph &G) { return 0; };
1.1108 + DefReachedMapBase(const Base &b) : Base(b) {}
1.1109 + };
1.1110 +
1.1111 + ///\brief \ref named-templ-param "Named parameter"
1.1112 + ///function for setting ReachedMap
1.1113 + ///
1.1114 + /// \ref named-templ-param "Named parameter"
1.1115 + ///function for setting ReachedMap
1.1116 + ///
1.1117 + template<class T>
1.1118 + BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1119 + {
1.1120 + Base::_pred=(void *)&t;
1.1121 + return BfsWizard<DefReachedMapBase<T> >(*this);
1.1122 + }
1.1123 +
1.1124 +
1.1125 + template<class T>
1.1126 + struct DefProcessedMapBase : public Base {
1.1127 + typedef T ProcessedMap;
1.1128 + static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
1.1129 + DefProcessedMapBase(const Base &b) : Base(b) {}
1.1130 + };
1.1131 +
1.1132 + ///\brief \ref named-templ-param "Named parameter"
1.1133 + ///function for setting ProcessedMap
1.1134 + ///
1.1135 + /// \ref named-templ-param "Named parameter"
1.1136 + ///function for setting ProcessedMap
1.1137 + ///
1.1138 + template<class T>
1.1139 + BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1140 + {
1.1141 + Base::_pred=(void *)&t;
1.1142 + return BfsWizard<DefProcessedMapBase<T> >(*this);
1.1143 + }
1.1144 +
1.1145 +
1.1146 +// template<class T>
1.1147 +// struct DefPredNodeMapBase : public Base {
1.1148 +// typedef T PredNodeMap;
1.1149 +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.1150 +// DefPredNodeMapBase(const Base &b) : Base(b) {}
1.1151 +// };
1.1152 +
1.1153 +// ///\brief \ref named-templ-param "Named parameter"
1.1154 +// ///function for setting PredNodeMap type
1.1155 +// ///
1.1156 +// /// \ref named-templ-param "Named parameter"
1.1157 +// ///function for setting PredNodeMap type
1.1158 +// ///
1.1159 +// template<class T>
1.1160 +// BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.1161 +// {
1.1162 +// Base::_predNode=(void *)&t;
1.1163 +// return BfsWizard<DefPredNodeMapBase<T> >(*this);
1.1164 +// }
1.1165 +
1.1166 + template<class T>
1.1167 + struct DefDistMapBase : public Base {
1.1168 + typedef T DistMap;
1.1169 + static DistMap *createDistMap(const Graph &G) { return 0; };
1.1170 + DefDistMapBase(const Base &b) : Base(b) {}
1.1171 + };
1.1172 +
1.1173 + ///\brief \ref named-templ-param "Named parameter"
1.1174 + ///function for setting DistMap type
1.1175 + ///
1.1176 + /// \ref named-templ-param "Named parameter"
1.1177 + ///function for setting DistMap type
1.1178 + ///
1.1179 + template<class T>
1.1180 + BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1181 + {
1.1182 + Base::_dist=(void *)&t;
1.1183 + return BfsWizard<DefDistMapBase<T> >(*this);
1.1184 + }
1.1185 +
1.1186 + /// Sets the source node, from which the Bfs algorithm runs.
1.1187 +
1.1188 + /// Sets the source node, from which the Bfs algorithm runs.
1.1189 + /// \param s is the source node.
1.1190 + BfsWizard<TR> &source(Node s)
1.1191 + {
1.1192 + Base::_source=s;
1.1193 + return *this;
1.1194 + }
1.1195
1.1196 };
1.1197
1.1198 -/// @}
1.1199 -
1.1200 + ///Function type interface for Bfs algorithm.
1.1201 +
1.1202 + /// \ingroup flowalgs
1.1203 + ///Function type interface for Bfs algorithm.
1.1204 + ///
1.1205 + ///This function also has several
1.1206 + ///\ref named-templ-func-param "named parameters",
1.1207 + ///they are declared as the members of class \ref BfsWizard.
1.1208 + ///The following
1.1209 + ///example shows how to use these parameters.
1.1210 + ///\code
1.1211 + /// bfs(g,source).predMap(preds).run();
1.1212 + ///\endcode
1.1213 + ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.1214 + ///to the end of the parameter list.
1.1215 + ///\sa BfsWizard
1.1216 + ///\sa Bfs
1.1217 + template<class GR>
1.1218 + BfsWizard<BfsWizardBase<GR> >
1.1219 + bfs(const GR &g,typename GR::Node s=INVALID)
1.1220 + {
1.1221 + return BfsWizard<BfsWizardBase<GR> >(g,s);
1.1222 + }
1.1223 +
1.1224 } //END OF NAMESPACE LEMON
1.1225
1.1226 #endif
1.1227
1.1228 -
2.1 --- a/src/lemon/dfs.h Wed Mar 16 07:52:16 2005 +0000
2.2 +++ b/src/lemon/dfs.h Wed Mar 16 07:56:25 2005 +0000
2.3 @@ -19,35 +19,150 @@
2.4
2.5 ///\ingroup flowalgs
2.6 ///\file
2.7 -///\brief %DFS algorithm.
2.8 -///
2.9 -///\todo Revise Manual.
2.10 +///\brief Dfs algorithm.
2.11
2.12 +#include <lemon/list_graph.h>
2.13 #include <lemon/graph_utils.h>
2.14 #include <lemon/invalid.h>
2.15 +#include <lemon/error.h>
2.16 +#include <lemon/maps.h>
2.17
2.18 namespace lemon {
2.19
2.20 -/// \addtogroup flowalgs
2.21 -/// @{
2.22
2.23 +
2.24 + ///Default traits class of Dfs class.
2.25 +
2.26 + ///Default traits class of Dfs class.
2.27 + ///\param GR Graph type.
2.28 + template<class GR>
2.29 + struct DfsDefaultTraits
2.30 + {
2.31 + ///The graph type the algorithm runs on.
2.32 + typedef GR Graph;
2.33 + ///\brief The type of the map that stores the last
2.34 + ///edges of the %DFS paths.
2.35 + ///
2.36 + ///The type of the map that stores the last
2.37 + ///edges of the %DFS paths.
2.38 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.39 + ///
2.40 + typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
2.41 + ///Instantiates a PredMap.
2.42 +
2.43 + ///This function instantiates a \ref PredMap.
2.44 + ///\param G is the graph, to which we would like to define the PredMap.
2.45 + ///\todo The graph alone may be insufficient to initialize
2.46 + static PredMap *createPredMap(const GR &G)
2.47 + {
2.48 + return new PredMap(G);
2.49 + }
2.50 +// ///\brief The type of the map that stores the last but one
2.51 +// ///nodes of the %DFS paths.
2.52 +// ///
2.53 +// ///The type of the map that stores the last but one
2.54 +// ///nodes of the %DFS paths.
2.55 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.56 +// ///
2.57 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
2.58 +// ///Instantiates a PredNodeMap.
2.59 +
2.60 +// ///This function instantiates a \ref PredNodeMap.
2.61 +// ///\param G is the graph, to which
2.62 +// ///we would like to define the \ref PredNodeMap
2.63 +// static PredNodeMap *createPredNodeMap(const GR &G)
2.64 +// {
2.65 +// return new PredNodeMap();
2.66 +// }
2.67 +
2.68 + ///The type of the map that indicates which nodes are processed.
2.69 +
2.70 + ///The type of the map that indicates which nodes are processed.
2.71 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.72 + ///\todo named parameter to set this type, function to read and write.
2.73 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
2.74 + ///Instantiates a ProcessedMap.
2.75 +
2.76 + ///This function instantiates a \ref ProcessedMap.
2.77 + ///\param G is the graph, to which
2.78 + ///we would like to define the \ref ProcessedMap
2.79 + static ProcessedMap *createProcessedMap(const GR &G)
2.80 + {
2.81 + return new ProcessedMap();
2.82 + }
2.83 + ///The type of the map that indicates which nodes are reached.
2.84 +
2.85 + ///The type of the map that indicates which nodes are reached.
2.86 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.87 + ///\todo named parameter to set this type, function to read and write.
2.88 + typedef typename Graph::template NodeMap<bool> ReachedMap;
2.89 + ///Instantiates a ReachedMap.
2.90 +
2.91 + ///This function instantiates a \ref ReachedMap.
2.92 + ///\param G is the graph, to which
2.93 + ///we would like to define the \ref ReachedMap.
2.94 + static ReachedMap *createReachedMap(const GR &G)
2.95 + {
2.96 + return new ReachedMap(G);
2.97 + }
2.98 + ///The type of the map that stores the dists of the nodes.
2.99 +
2.100 + ///The type of the map that stores the dists of the nodes.
2.101 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.102 + ///
2.103 + typedef typename Graph::template NodeMap<int> DistMap;
2.104 + ///Instantiates a DistMap.
2.105 +
2.106 + ///This function instantiates a \ref DistMap.
2.107 + ///\param G is the graph, to which we would like to define the \ref DistMap
2.108 + static DistMap *createDistMap(const GR &G)
2.109 + {
2.110 + return new DistMap(G);
2.111 + }
2.112 + };
2.113 +
2.114 ///%DFS algorithm class.
2.115 -
2.116 - ///This class provides an efficient implementation of %DFS algorithm.
2.117 +
2.118 + ///\ingroup flowalgs
2.119 + ///This class provides an efficient implementation of the %DFS algorithm.
2.120 ///
2.121 - ///\param GR The graph type the algorithm runs on.
2.122 + ///\param GR The graph type the algorithm runs on. The default value is
2.123 + ///\ref ListGraph. The value of GR is not used directly by Dfs, it
2.124 + ///is only passed to \ref DfsDefaultTraits.
2.125 + ///\param TR Traits class to set various data types used by the algorithm.
2.126 + ///The default traits class is
2.127 + ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
2.128 + ///See \ref DfsDefaultTraits for the documentation of
2.129 + ///a Dfs traits class.
2.130 ///
2.131 - ///\author Alpar Juttner
2.132 + ///\author Jacint Szabo and Alpar Juttner
2.133 + ///\todo A compare object would be nice.
2.134
2.135 #ifdef DOXYGEN
2.136 - template <typename GR>
2.137 + template <typename GR,
2.138 + typename TR>
2.139 #else
2.140 - template <typename GR>
2.141 + template <typename GR=ListGraph,
2.142 + typename TR=DfsDefaultTraits<GR> >
2.143 #endif
2.144 - class Dfs{
2.145 + class Dfs {
2.146 public:
2.147 + /**
2.148 + * \brief \ref Exception for uninitialized parameters.
2.149 + *
2.150 + * This error represents problems in the initialization
2.151 + * of the parameters of the algorithms.
2.152 + */
2.153 + class UninitializedParameter : public lemon::UninitializedParameter {
2.154 + public:
2.155 + virtual const char* exceptionName() const {
2.156 + return "lemon::Dfs::UninitializedParameter";
2.157 + }
2.158 + };
2.159 +
2.160 + typedef TR Traits;
2.161 ///The type of the underlying graph.
2.162 - typedef GR Graph;
2.163 + typedef typename TR::Graph Graph;
2.164 ///\e
2.165 typedef typename Graph::Node Node;
2.166 ///\e
2.167 @@ -58,69 +173,211 @@
2.168 typedef typename Graph::OutEdgeIt OutEdgeIt;
2.169
2.170 ///\brief The type of the map that stores the last
2.171 - ///edges of the paths on the %DFS tree.
2.172 - typedef typename Graph::template NodeMap<Edge> PredMap;
2.173 - ///\brief The type of the map that stores the last but one
2.174 - ///nodes of the paths on the %DFS tree.
2.175 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
2.176 - ///The type of the map that stores the dists of the nodes on the %DFS tree.
2.177 - typedef typename Graph::template NodeMap<int> DistMap;
2.178 -
2.179 + ///edges of the %DFS paths.
2.180 + typedef typename TR::PredMap PredMap;
2.181 +// ///\brief The type of the map that stores the last but one
2.182 +// ///nodes of the %DFS paths.
2.183 +// typedef typename TR::PredNodeMap PredNodeMap;
2.184 + ///The type of the map indicating which nodes are reached.
2.185 + typedef typename TR::ReachedMap ReachedMap;
2.186 + ///The type of the map indicating which nodes are processed.
2.187 + typedef typename TR::ProcessedMap ProcessedMap;
2.188 + ///The type of the map that stores the dists of the nodes.
2.189 + typedef typename TR::DistMap DistMap;
2.190 private:
2.191 /// Pointer to the underlying graph.
2.192 const Graph *G;
2.193 ///Pointer to the map of predecessors edges.
2.194 - PredMap *predecessor;
2.195 - ///Indicates if \ref predecessor is locally allocated (\c true) or not.
2.196 - bool local_predecessor;
2.197 - ///Pointer to the map of predecessors nodes.
2.198 - PredNodeMap *pred_node;
2.199 - ///Indicates if \ref pred_node is locally allocated (\c true) or not.
2.200 - bool local_pred_node;
2.201 + PredMap *_pred;
2.202 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
2.203 + bool local_pred;
2.204 +// ///Pointer to the map of predecessors nodes.
2.205 +// PredNodeMap *_predNode;
2.206 +// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
2.207 +// bool local_predNode;
2.208 ///Pointer to the map of distances.
2.209 - DistMap *distance;
2.210 - ///Indicates if \ref distance is locally allocated (\c true) or not.
2.211 - bool local_distance;
2.212 + DistMap *_dist;
2.213 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
2.214 + bool local_dist;
2.215 + ///Pointer to the map of reached status of the nodes.
2.216 + ReachedMap *_reached;
2.217 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
2.218 + bool local_reached;
2.219 + ///Pointer to the map of processed status of the nodes.
2.220 + ProcessedMap *_processed;
2.221 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
2.222 + bool local_processed;
2.223
2.224 - ///The source node of the last execution.
2.225 - Node source;
2.226 + std::vector<typename Graph::OutEdgeIt> _stack;
2.227 + int _stack_head;
2.228 +// ///The source node of the last execution.
2.229 +// Node source;
2.230
2.231 -
2.232 - ///Initializes the maps.
2.233 - void init_maps()
2.234 + ///Creates the maps if necessary.
2.235 +
2.236 + ///\todo Error if \c G are \c NULL.
2.237 + ///\todo Better memory allocation (instead of new).
2.238 + void create_maps()
2.239 {
2.240 - if(!predecessor) {
2.241 - local_predecessor = true;
2.242 - predecessor = new PredMap(*G);
2.243 + if(!_pred) {
2.244 + local_pred = true;
2.245 + _pred = Traits::createPredMap(*G);
2.246 }
2.247 - if(!pred_node) {
2.248 - local_pred_node = true;
2.249 - pred_node = new PredNodeMap(*G);
2.250 +// if(!_predNode) {
2.251 +// local_predNode = true;
2.252 +// _predNode = Traits::createPredNodeMap(*G);
2.253 +// }
2.254 + if(!_dist) {
2.255 + local_dist = true;
2.256 + _dist = Traits::createDistMap(*G);
2.257 }
2.258 - if(!distance) {
2.259 - local_distance = true;
2.260 - distance = new DistMap(*G);
2.261 + if(!_reached) {
2.262 + local_reached = true;
2.263 + _reached = Traits::createReachedMap(*G);
2.264 + }
2.265 + if(!_processed) {
2.266 + local_processed = true;
2.267 + _processed = Traits::createProcessedMap(*G);
2.268 }
2.269 }
2.270
2.271 - public :
2.272 + public :
2.273 +
2.274 + ///\name Named template parameters
2.275 +
2.276 + ///@{
2.277 +
2.278 + template <class T>
2.279 + struct DefPredMapTraits : public Traits {
2.280 + typedef T PredMap;
2.281 + static PredMap *createPredMap(const Graph &G)
2.282 + {
2.283 + throw UninitializedParameter();
2.284 + }
2.285 + };
2.286 + ///\ref named-templ-param "Named parameter" for setting PredMap type
2.287 +
2.288 + ///\ref named-templ-param "Named parameter" for setting PredMap type
2.289 + ///
2.290 + template <class T>
2.291 + class DefPredMap : public Dfs< Graph,
2.292 + DefPredMapTraits<T> > { };
2.293 +
2.294 +// template <class T>
2.295 +// struct DefPredNodeMapTraits : public Traits {
2.296 +// typedef T PredNodeMap;
2.297 +// static PredNodeMap *createPredNodeMap(const Graph &G)
2.298 +// {
2.299 +// throw UninitializedParameter();
2.300 +// }
2.301 +// };
2.302 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
2.303 +
2.304 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
2.305 +// ///
2.306 +// template <class T>
2.307 +// class DefPredNodeMap : public Dfs< Graph,
2.308 +// LengthMap,
2.309 +// DefPredNodeMapTraits<T> > { };
2.310 +
2.311 + template <class T>
2.312 + struct DefDistMapTraits : public Traits {
2.313 + typedef T DistMap;
2.314 + static DistMap *createDistMap(const Graph &G)
2.315 + {
2.316 + throw UninitializedParameter();
2.317 + }
2.318 + };
2.319 + ///\ref named-templ-param "Named parameter" for setting DistMap type
2.320 +
2.321 + ///\ref named-templ-param "Named parameter" for setting DistMap type
2.322 + ///
2.323 + template <class T>
2.324 + class DefDistMap : public Dfs< Graph,
2.325 + DefDistMapTraits<T> > { };
2.326 +
2.327 + template <class T>
2.328 + struct DefReachedMapTraits : public Traits {
2.329 + typedef T ReachedMap;
2.330 + static ReachedMap *createReachedMap(const Graph &G)
2.331 + {
2.332 + throw UninitializedParameter();
2.333 + }
2.334 + };
2.335 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
2.336 +
2.337 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
2.338 + ///
2.339 + template <class T>
2.340 + class DefReachedMap : public Dfs< Graph,
2.341 + DefReachedMapTraits<T> > { };
2.342 +
2.343 + struct DefGraphReachedMapTraits : public Traits {
2.344 + typedef typename Graph::template NodeMap<bool> ReachedMap;
2.345 + static ReachedMap *createReachedMap(const Graph &G)
2.346 + {
2.347 + return new ReachedMap(G);
2.348 + }
2.349 + };
2.350 + template <class T>
2.351 + struct DefProcessedMapTraits : public Traits {
2.352 + typedef T ProcessedMap;
2.353 + static ProcessedMap *createProcessedMap(const Graph &G)
2.354 + {
2.355 + throw UninitializedParameter();
2.356 + }
2.357 + };
2.358 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
2.359 +
2.360 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
2.361 + ///
2.362 + template <class T>
2.363 + class DefProcessedMap : public Dfs< Graph,
2.364 + DefProcessedMapTraits<T> > { };
2.365 +
2.366 + struct DefGraphProcessedMapTraits : public Traits {
2.367 + typedef typename Graph::template NodeMap<bool> ProcessedMap;
2.368 + static ProcessedMap *createProcessedMap(const Graph &G)
2.369 + {
2.370 + return new ProcessedMap(G);
2.371 + }
2.372 + };
2.373 + ///\brief \ref named-templ-param "Named parameter"
2.374 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
2.375 + ///
2.376 + ///\ref named-templ-param "Named parameter"
2.377 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
2.378 + ///If you don't set it explicitely, it will be automatically allocated.
2.379 + template <class T>
2.380 + class DefProcessedMapToBeDefaultMap :
2.381 + public Dfs< Graph,
2.382 + DefGraphProcessedMapTraits> { };
2.383 +
2.384 + ///@}
2.385 +
2.386 + public:
2.387 +
2.388 ///Constructor.
2.389
2.390 ///\param _G the graph the algorithm will run on.
2.391 ///
2.392 Dfs(const Graph& _G) :
2.393 G(&_G),
2.394 - predecessor(NULL), local_predecessor(false),
2.395 - pred_node(NULL), local_pred_node(false),
2.396 - distance(NULL), local_distance(false)
2.397 + _pred(NULL), local_pred(false),
2.398 +// _predNode(NULL), local_predNode(false),
2.399 + _dist(NULL), local_dist(false),
2.400 + _reached(NULL), local_reached(false),
2.401 + _processed(NULL), local_processed(false)
2.402 { }
2.403
2.404 ///Destructor.
2.405 ~Dfs()
2.406 {
2.407 - if(local_predecessor) delete predecessor;
2.408 - if(local_pred_node) delete pred_node;
2.409 - if(local_distance) delete distance;
2.410 + if(local_pred) delete _pred;
2.411 +// if(local_predNode) delete _predNode;
2.412 + if(local_dist) delete _dist;
2.413 + if(local_reached) delete _reached;
2.414 + if(local_processed) delete _processed;
2.415 }
2.416
2.417 ///Sets the map storing the predecessor edges.
2.418 @@ -130,32 +387,32 @@
2.419 ///it will allocate one. The destuctor deallocates this
2.420 ///automatically allocated map, of course.
2.421 ///\return <tt> (*this) </tt>
2.422 - Dfs &setPredMap(PredMap &m)
2.423 + Dfs &predMap(PredMap &m)
2.424 {
2.425 - if(local_predecessor) {
2.426 - delete predecessor;
2.427 - local_predecessor=false;
2.428 + if(local_pred) {
2.429 + delete _pred;
2.430 + local_pred=false;
2.431 }
2.432 - predecessor = &m;
2.433 + _pred = &m;
2.434 return *this;
2.435 }
2.436
2.437 - ///Sets the map storing the predecessor nodes.
2.438 +// ///Sets the map storing the predecessor nodes.
2.439
2.440 - ///Sets the map storing the predecessor nodes.
2.441 - ///If you don't use this function before calling \ref run(),
2.442 - ///it will allocate one. The destuctor deallocates this
2.443 - ///automatically allocated map, of course.
2.444 - ///\return <tt> (*this) </tt>
2.445 - Dfs &setPredNodeMap(PredNodeMap &m)
2.446 - {
2.447 - if(local_pred_node) {
2.448 - delete pred_node;
2.449 - local_pred_node=false;
2.450 - }
2.451 - pred_node = &m;
2.452 - return *this;
2.453 - }
2.454 +// ///Sets the map storing the predecessor nodes.
2.455 +// ///If you don't use this function before calling \ref run(),
2.456 +// ///it will allocate one. The destuctor deallocates this
2.457 +// ///automatically allocated map, of course.
2.458 +// ///\return <tt> (*this) </tt>
2.459 +// Dfs &predNodeMap(PredNodeMap &m)
2.460 +// {
2.461 +// if(local_predNode) {
2.462 +// delete _predNode;
2.463 +// local_predNode=false;
2.464 +// }
2.465 +// _predNode = &m;
2.466 +// return *this;
2.467 +// }
2.468
2.469 ///Sets the map storing the distances calculated by the algorithm.
2.470
2.471 @@ -164,127 +421,655 @@
2.472 ///it will allocate one. The destuctor deallocates this
2.473 ///automatically allocated map, of course.
2.474 ///\return <tt> (*this) </tt>
2.475 - Dfs &setDistMap(DistMap &m)
2.476 + Dfs &distMap(DistMap &m)
2.477 {
2.478 - if(local_distance) {
2.479 - delete distance;
2.480 - local_distance=false;
2.481 + if(local_dist) {
2.482 + delete _dist;
2.483 + local_dist=false;
2.484 }
2.485 - distance = &m;
2.486 + _dist = &m;
2.487 return *this;
2.488 }
2.489 -
2.490 - ///Runs %DFS algorithm from node \c s.
2.491
2.492 - ///This method runs the %DFS algorithm from a root node \c s
2.493 - ///in order to
2.494 - ///compute
2.495 - ///- a %DFS tree and
2.496 - ///- the distance of each node from the root on this tree.
2.497 -
2.498 - void run(Node s) {
2.499 -
2.500 - init_maps();
2.501 -
2.502 - source = s;
2.503 -
2.504 + public:
2.505 + ///\name Execution control
2.506 + ///The simplest way to execute the algorithm is to use
2.507 + ///one of the member functions called \c run(...).
2.508 + ///\n
2.509 + ///If you need more control on the execution,
2.510 + ///first you must call \ref init(), then you can add several source nodes
2.511 + ///with \ref addSource().
2.512 + ///Finally \ref start() will perform the actual path
2.513 + ///computation.
2.514 +
2.515 + ///@{
2.516 +
2.517 + ///Initializes the internal data structures.
2.518 +
2.519 + ///Initializes the internal data structures.
2.520 + ///
2.521 + void init()
2.522 + {
2.523 + create_maps();
2.524 + _stack.resize(countNodes(*G));
2.525 + _stack_head=-1;
2.526 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
2.527 - predecessor->set(u,INVALID);
2.528 - pred_node->set(u,INVALID);
2.529 + _pred->set(u,INVALID);
2.530 + // _predNode->set(u,INVALID);
2.531 + _reached->set(u,false);
2.532 + _processed->set(u,false);
2.533 }
2.534 -
2.535 - int N = countNodes(*G);
2.536 - std::vector<typename Graph::OutEdgeIt> Q(N);
2.537 -
2.538 - int Qh=0;
2.539 -
2.540 - Q[Qh] = OutEdgeIt(*G, s);
2.541 - distance->set(s, 0);
2.542 -
2.543 - Node n=s;
2.544 - Node m;
2.545 - OutEdgeIt e;
2.546 - do {
2.547 - if((e=Q[Qh])!=INVALID)
2.548 - if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) {
2.549 - predecessor->set(m,e);
2.550 - pred_node->set(m,n);
2.551 - Q[++Qh] = OutEdgeIt(*G, m);
2.552 - distance->set(m,Qh);
2.553 - n=m;
2.554 - }
2.555 - else ++Q[Qh];
2.556 - else if(--Qh>=0) n=G->source(Q[Qh]);
2.557 - } while(Qh>=0);
2.558 }
2.559
2.560 - ///The distance of a node from the root on the %DFS tree.
2.561 + ///Adds a new source node.
2.562
2.563 - ///Returns the distance of a node from the root on the %DFS tree.
2.564 + ///Adds a new source node to the set of nodes to be processed.
2.565 + ///
2.566 + ///\bug dist's are wrong (or at least strange) in case of multiple sources.
2.567 + void addSource(Node s)
2.568 + {
2.569 + if(!(*_reached)[s])
2.570 + {
2.571 + _reached->set(s,true);
2.572 + _pred->set(s,INVALID);
2.573 + // _predNode->set(u,INVALID);
2.574 + _stack[++_stack_head]=OutEdgeIt(*G,s);
2.575 + _dist->set(s,_stack_head);
2.576 + }
2.577 + }
2.578 +
2.579 + ///Processes the next node.
2.580 +
2.581 + ///Processes the next node.
2.582 + ///
2.583 + ///\warning The stack must not be empty!
2.584 + void processNextEdge()
2.585 + {
2.586 + Node m;
2.587 + Edge e=_stack[_stack_head];
2.588 + if(!(*_reached)[m=G->target(e)]) {
2.589 + _pred->set(m,e);
2.590 + _reached->set(m,true);
2.591 + // _pred_node->set(m,G->source(e));
2.592 + _stack[++_stack_head] = OutEdgeIt(*G, m);
2.593 + _dist->set(m,_stack_head);
2.594 + }
2.595 + else {
2.596 + Node n;
2.597 + while(_stack_head>=0 &&
2.598 + (n=G->source(_stack[_stack_head]),
2.599 + ++_stack[_stack_head]==INVALID))
2.600 + {
2.601 + _processed->set(n,true);
2.602 + --_stack_head;
2.603 + }
2.604 + }
2.605 + }
2.606 +
2.607 + ///\brief Returns \c false if there are nodes
2.608 + ///to be processed in the queue
2.609 + ///
2.610 + ///Returns \c false if there are nodes
2.611 + ///to be processed in the queue
2.612 + bool emptyQueue() { return _stack_head<0; }
2.613 + ///Returns the number of the nodes to be processed.
2.614 +
2.615 + ///Returns the number of the nodes to be processed in the queue.
2.616 + ///
2.617 + int queueSize() { return _stack_head+1; }
2.618 +
2.619 + ///Executes the algorithm.
2.620 +
2.621 + ///Executes the algorithm.
2.622 + ///
2.623 + ///\pre init() must be called and at least one node should be added
2.624 + ///with addSource() before using this function.
2.625 + ///
2.626 + ///This method runs the %DFS algorithm from the root node(s)
2.627 + ///in order to
2.628 + ///compute the
2.629 + ///%DFS path to each node. The algorithm computes
2.630 + ///- The %DFS tree.
2.631 + ///- The distance of each node from the root(s).
2.632 + ///
2.633 + void start()
2.634 + {
2.635 + while ( !emptyQueue() ) processNextEdge();
2.636 + }
2.637 +
2.638 + ///Executes the algorithm until \c dest is reached.
2.639 +
2.640 + ///Executes the algorithm until \c dest is reached.
2.641 + ///
2.642 + ///\pre init() must be called and at least one node should be added
2.643 + ///with addSource() before using this function.
2.644 + ///
2.645 + ///This method runs the %DFS algorithm from the root node(s)
2.646 + ///in order to
2.647 + ///compute the
2.648 + ///%DFS path to \c dest. The algorithm computes
2.649 + ///- The %DFS path to \c dest.
2.650 + ///- The distance of \c dest from the root(s).
2.651 + ///
2.652 + void start(Node dest)
2.653 + {
2.654 + while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
2.655 + }
2.656 +
2.657 + ///Executes the algorithm until a condition is met.
2.658 +
2.659 + ///Executes the algorithm until a condition is met.
2.660 + ///
2.661 + ///\pre init() must be called and at least one node should be added
2.662 + ///with addSource() before using this function.
2.663 + ///
2.664 + ///\param nm must be a bool (or convertible) node map. The algorithm
2.665 + ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
2.666 + template<class NM>
2.667 + void start(const NM &nm)
2.668 + {
2.669 + while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
2.670 + }
2.671 +
2.672 + ///Runs %DFS algorithm from node \c s.
2.673 +
2.674 + ///This method runs the %DFS algorithm from a root node \c s
2.675 + ///in order to
2.676 + ///compute the
2.677 + ///%DFS path to each node. The algorithm computes
2.678 + ///- The %DFS tree.
2.679 + ///- The distance of each node from the root.
2.680 + ///
2.681 + ///\note d.run(s) is just a shortcut of the following code.
2.682 + ///\code
2.683 + /// d.init();
2.684 + /// d.addSource(s);
2.685 + /// d.start();
2.686 + ///\endcode
2.687 + void run(Node s) {
2.688 + init();
2.689 + addSource(s);
2.690 + start();
2.691 + }
2.692 +
2.693 + ///Finds the %DFS path between \c s and \c t.
2.694 +
2.695 + ///Finds the %DFS path between \c s and \c t.
2.696 + ///
2.697 + ///\return The length of the %DFS s---t path if there exists one,
2.698 + ///0 otherwise.
2.699 + ///\note Apart from the return value, d.run(s) is
2.700 + ///just a shortcut of the following code.
2.701 + ///\code
2.702 + /// d.init();
2.703 + /// d.addSource(s);
2.704 + /// d.start(t);
2.705 + ///\endcode
2.706 + int run(Node s,Node t) {
2.707 + init();
2.708 + addSource(s);
2.709 + start(t);
2.710 + return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
2.711 + }
2.712 +
2.713 + ///@}
2.714 +
2.715 + ///\name Query Functions
2.716 + ///The result of the %DFS algorithm can be obtained using these
2.717 + ///functions.\n
2.718 + ///Before the use of these functions,
2.719 + ///either run() or start() must be called.
2.720 +
2.721 + ///@{
2.722 +
2.723 + ///The distance of a node from the root(s).
2.724 +
2.725 + ///Returns the distance of a node from the root(s).
2.726 ///\pre \ref run() must be called before using this function.
2.727 - ///\warning If node \c v in unreachable from the root the return value
2.728 + ///\warning If node \c v in unreachable from the root(s) the return value
2.729 ///of this funcion is undefined.
2.730 - int dist(Node v) const { return (*distance)[v]; }
2.731 + int dist(Node v) const { return (*_dist)[v]; }
2.732
2.733 - ///Returns the 'previous edge' of the %DFS path tree.
2.734 + ///Returns the 'previous edge' of the %DFS tree.
2.735
2.736 - ///For a node \c v it returns the last edge of the path on the %DFS tree
2.737 - ///from the root to \c
2.738 + ///For a node \c v it returns the 'previous edge'
2.739 + ///of the %DFS path,
2.740 + ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
2.741 ///v. It is \ref INVALID
2.742 - ///if \c v is unreachable from the root or if \c v=s. The
2.743 + ///if \c v is unreachable from the root(s) or \c v is a root. The
2.744 ///%DFS tree used here is equal to the %DFS tree used in
2.745 - ///\ref predNode(Node v). \pre \ref run() must be called before using
2.746 + ///\ref predNode(Node v).
2.747 + ///\pre Either \ref run() or \ref start() must be called before using
2.748 ///this function.
2.749 - Edge pred(Node v) const { return (*predecessor)[v]; }
2.750 + ///\todo predEdge could be a better name.
2.751 + Edge pred(Node v) const { return (*_pred)[v];}
2.752
2.753 ///Returns the 'previous node' of the %DFS tree.
2.754
2.755 - ///For a node \c v it returns the 'previous node' on the %DFS tree,
2.756 - ///i.e. it returns the last but one node of the path from the
2.757 - ///root to \c /v on the %DFS tree.
2.758 - ///It is INVALID if \c v is unreachable from the root or if
2.759 - ///\c v=s.
2.760 - ///\pre \ref run() must be called before
2.761 + ///For a node \c v it returns the 'previous node'
2.762 + ///of the %DFS tree,
2.763 + ///i.e. it returns the last but one node from a %DFS path from the
2.764 + ///root(a) to \c /v.
2.765 + ///It is INVALID if \c v is unreachable from the root(s) or
2.766 + ///if \c v itself a root.
2.767 + ///The %DFS tree used here is equal to the %DFS
2.768 + ///tree used in \ref pred(Node v).
2.769 + ///\pre Either \ref run() or \ref start() must be called before
2.770 ///using this function.
2.771 - Node predNode(Node v) const { return (*pred_node)[v]; }
2.772 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
2.773 + G->source((*_pred)[v]); }
2.774
2.775 - ///Returns a reference to the NodeMap of distances on the %DFS tree.
2.776 -
2.777 - ///Returns a reference to the NodeMap of distances on the %DFS tree.
2.778 - ///\pre \ref run() must
2.779 + ///Returns a reference to the NodeMap of distances.
2.780 +
2.781 + ///Returns a reference to the NodeMap of distances.
2.782 + ///\pre Either \ref run() or \ref init() must
2.783 ///be called before using this function.
2.784 - const DistMap &distMap() const { return *distance;}
2.785 + const DistMap &distMap() const { return *_dist;}
2.786
2.787 - ///Returns a reference to the %DFS tree map.
2.788 + ///Returns a reference to the %DFS edge-tree map.
2.789
2.790 ///Returns a reference to the NodeMap of the edges of the
2.791 ///%DFS tree.
2.792 - ///\pre \ref run() must be called before using this function.
2.793 - const PredMap &predMap() const { return *predecessor;}
2.794 + ///\pre Either \ref run() or \ref init()
2.795 + ///must be called before using this function.
2.796 + const PredMap &predMap() const { return *_pred;}
2.797
2.798 - ///Returns a reference to the map of last but one nodes of the %DFS tree.
2.799 +// ///Returns a reference to the map of nodes of %DFS paths.
2.800
2.801 - ///Returns a reference to the NodeMap of the last but one nodes of the paths
2.802 - ///on the
2.803 - ///%DFS tree.
2.804 - ///\pre \ref run() must be called before using this function.
2.805 - const PredNodeMap &predNodeMap() const { return *pred_node;}
2.806 +// ///Returns a reference to the NodeMap of the last but one nodes of the
2.807 +// ///%DFS tree.
2.808 +// ///\pre \ref run() must be called before using this function.
2.809 +// const PredNodeMap &predNodeMap() const { return *_predNode;}
2.810
2.811 ///Checks if a node is reachable from the root.
2.812
2.813 ///Returns \c true if \c v is reachable from the root.
2.814 - ///\note The root node is reported to be reached!
2.815 + ///\warning The source nodes are inditated as unreached.
2.816 + ///\pre Either \ref run() or \ref start()
2.817 + ///must be called before using this function.
2.818 ///
2.819 - ///\pre \ref run() must be called before using this function.
2.820 + bool reached(Node v) { return (*_reached)[v]; }
2.821 +
2.822 + ///@}
2.823 + };
2.824 +
2.825 + ///Default traits class of Dfs function.
2.826 +
2.827 + ///Default traits class of Dfs function.
2.828 + ///\param GR Graph type.
2.829 + template<class GR>
2.830 + struct DfsWizardDefaultTraits
2.831 + {
2.832 + ///The graph type the algorithm runs on.
2.833 + typedef GR Graph;
2.834 + ///\brief The type of the map that stores the last
2.835 + ///edges of the %DFS paths.
2.836 + ///
2.837 + ///The type of the map that stores the last
2.838 + ///edges of the %DFS paths.
2.839 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.840 ///
2.841 - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
2.842 + typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
2.843 + ///Instantiates a PredMap.
2.844 +
2.845 + ///This function instantiates a \ref PredMap.
2.846 + ///\param G is the graph, to which we would like to define the PredMap.
2.847 + ///\todo The graph alone may be insufficient to initialize
2.848 + static PredMap *createPredMap(const GR &G)
2.849 + {
2.850 + return new PredMap();
2.851 + }
2.852 +// ///\brief The type of the map that stores the last but one
2.853 +// ///nodes of the %DFS paths.
2.854 +// ///
2.855 +// ///The type of the map that stores the last but one
2.856 +// ///nodes of the %DFS paths.
2.857 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.858 +// ///
2.859 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
2.860 +// ///Instantiates a PredNodeMap.
2.861 +
2.862 +// ///This function instantiates a \ref PredNodeMap.
2.863 +// ///\param G is the graph, to which
2.864 +// ///we would like to define the \ref PredNodeMap
2.865 +// static PredNodeMap *createPredNodeMap(const GR &G)
2.866 +// {
2.867 +// return new PredNodeMap();
2.868 +// }
2.869 +
2.870 + ///The type of the map that indicates which nodes are processed.
2.871 +
2.872 + ///The type of the map that indicates which nodes are processed.
2.873 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.874 + ///\todo named parameter to set this type, function to read and write.
2.875 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
2.876 + ///Instantiates a ProcessedMap.
2.877 +
2.878 + ///This function instantiates a \ref ProcessedMap.
2.879 + ///\param G is the graph, to which
2.880 + ///we would like to define the \ref ProcessedMap
2.881 + static ProcessedMap *createProcessedMap(const GR &G)
2.882 + {
2.883 + return new ProcessedMap();
2.884 + }
2.885 + ///The type of the map that indicates which nodes are reached.
2.886 +
2.887 + ///The type of the map that indicates which nodes are reached.
2.888 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.889 + ///\todo named parameter to set this type, function to read and write.
2.890 + typedef typename Graph::template NodeMap<bool> ReachedMap;
2.891 + ///Instantiates a ReachedMap.
2.892 +
2.893 + ///This function instantiates a \ref ReachedMap.
2.894 + ///\param G is the graph, to which
2.895 + ///we would like to define the \ref ReachedMap.
2.896 + static ReachedMap *createReachedMap(const GR &G)
2.897 + {
2.898 + return new ReachedMap(G);
2.899 + }
2.900 + ///The type of the map that stores the dists of the nodes.
2.901 +
2.902 + ///The type of the map that stores the dists of the nodes.
2.903 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
2.904 + ///
2.905 + typedef NullMap<typename Graph::Node,int> DistMap;
2.906 + ///Instantiates a DistMap.
2.907 +
2.908 + ///This function instantiates a \ref DistMap.
2.909 + ///\param G is the graph, to which we would like to define the \ref DistMap
2.910 + static DistMap *createDistMap(const GR &G)
2.911 + {
2.912 + return new DistMap();
2.913 + }
2.914 + };
2.915 +
2.916 + /// Default traits used by \ref DfsWizard
2.917 +
2.918 + /// To make it easier to use Dfs algorithm
2.919 + ///we have created a wizard class.
2.920 + /// This \ref DfsWizard class needs default traits,
2.921 + ///as well as the \ref Dfs class.
2.922 + /// The \ref DfsWizardBase is a class to be the default traits of the
2.923 + /// \ref DfsWizard class.
2.924 + template<class GR>
2.925 + class DfsWizardBase : public DfsWizardDefaultTraits<GR>
2.926 + {
2.927 +
2.928 + typedef DfsWizardDefaultTraits<GR> Base;
2.929 + protected:
2.930 + /// Type of the nodes in the graph.
2.931 + typedef typename Base::Graph::Node Node;
2.932 +
2.933 + /// Pointer to the underlying graph.
2.934 + void *_g;
2.935 + ///Pointer to the map of reached nodes.
2.936 + void *_reached;
2.937 + ///Pointer to the map of processed nodes.
2.938 + void *_processed;
2.939 + ///Pointer to the map of predecessors edges.
2.940 + void *_pred;
2.941 +// ///Pointer to the map of predecessors nodes.
2.942 +// void *_predNode;
2.943 + ///Pointer to the map of distances.
2.944 + void *_dist;
2.945 + ///Pointer to the source node.
2.946 + Node _source;
2.947 +
2.948 + public:
2.949 + /// Constructor.
2.950 +
2.951 + /// This constructor does not require parameters, therefore it initiates
2.952 + /// all of the attributes to default values (0, INVALID).
2.953 + DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
2.954 +// _predNode(0),
2.955 + _dist(0), _source(INVALID) {}
2.956 +
2.957 + /// Constructor.
2.958 +
2.959 + /// This constructor requires some parameters,
2.960 + /// listed in the parameters list.
2.961 + /// Others are initiated to 0.
2.962 + /// \param g is the initial value of \ref _g
2.963 + /// \param s is the initial value of \ref _source
2.964 + DfsWizardBase(const GR &g, Node s=INVALID) :
2.965 + _g((void *)&g), _reached(0), _processed(0), _pred(0),
2.966 +// _predNode(0),
2.967 + _dist(0), _source(s) {}
2.968 +
2.969 + };
2.970 +
2.971 + /// A class to make the usage of Dfs algorithm easier
2.972 +
2.973 + /// This class is created to make it easier to use Dfs algorithm.
2.974 + /// It uses the functions and features of the plain \ref Dfs,
2.975 + /// but it is much simpler to use it.
2.976 + ///
2.977 + /// Simplicity means that the way to change the types defined
2.978 + /// in the traits class is based on functions that returns the new class
2.979 + /// and not on templatable built-in classes.
2.980 + /// When using the plain \ref Dfs
2.981 + /// the new class with the modified type comes from
2.982 + /// the original class by using the ::
2.983 + /// operator. In the case of \ref DfsWizard only
2.984 + /// a function have to be called and it will
2.985 + /// return the needed class.
2.986 + ///
2.987 + /// It does not have own \ref run method. When its \ref run method is called
2.988 + /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run
2.989 + /// method of it.
2.990 + template<class TR>
2.991 + class DfsWizard : public TR
2.992 + {
2.993 + typedef TR Base;
2.994 +
2.995 + ///The type of the underlying graph.
2.996 + typedef typename TR::Graph Graph;
2.997 + //\e
2.998 + typedef typename Graph::Node Node;
2.999 + //\e
2.1000 + typedef typename Graph::NodeIt NodeIt;
2.1001 + //\e
2.1002 + typedef typename Graph::Edge Edge;
2.1003 + //\e
2.1004 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.1005 +
2.1006 + ///\brief The type of the map that stores
2.1007 + ///the reached nodes
2.1008 + typedef typename TR::ReachedMap ReachedMap;
2.1009 + ///\brief The type of the map that stores
2.1010 + ///the processed nodes
2.1011 + typedef typename TR::ProcessedMap ProcessedMap;
2.1012 + ///\brief The type of the map that stores the last
2.1013 + ///edges of the %DFS paths.
2.1014 + typedef typename TR::PredMap PredMap;
2.1015 +// ///\brief The type of the map that stores the last but one
2.1016 +// ///nodes of the %DFS paths.
2.1017 +// typedef typename TR::PredNodeMap PredNodeMap;
2.1018 + ///The type of the map that stores the dists of the nodes.
2.1019 + typedef typename TR::DistMap DistMap;
2.1020 +
2.1021 +public:
2.1022 + /// Constructor.
2.1023 + DfsWizard() : TR() {}
2.1024 +
2.1025 + /// Constructor that requires parameters.
2.1026 +
2.1027 + /// Constructor that requires parameters.
2.1028 + /// These parameters will be the default values for the traits class.
2.1029 + DfsWizard(const Graph &g, Node s=INVALID) :
2.1030 + TR(g,s) {}
2.1031 +
2.1032 + ///Copy constructor
2.1033 + DfsWizard(const TR &b) : TR(b) {}
2.1034 +
2.1035 + ~DfsWizard() {}
2.1036 +
2.1037 + ///Runs Dfs algorithm from a given node.
2.1038 +
2.1039 + ///Runs Dfs algorithm from a given node.
2.1040 + ///The node can be given by the \ref source function.
2.1041 + void run()
2.1042 + {
2.1043 + if(Base::_source==INVALID) throw UninitializedParameter();
2.1044 + Dfs<Graph,TR> alg(*(Graph*)Base::_g);
2.1045 + if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
2.1046 + if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
2.1047 + if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
2.1048 +// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
2.1049 + if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
2.1050 + alg.run(Base::_source);
2.1051 + }
2.1052 +
2.1053 + ///Runs Dfs algorithm from the given node.
2.1054 +
2.1055 + ///Runs Dfs algorithm from the given node.
2.1056 + ///\param s is the given source.
2.1057 + void run(Node s)
2.1058 + {
2.1059 + Base::_source=s;
2.1060 + run();
2.1061 + }
2.1062 +
2.1063 + template<class T>
2.1064 + struct DefPredMapBase : public Base {
2.1065 + typedef T PredMap;
2.1066 + static PredMap *createPredMap(const Graph &G) { return 0; };
2.1067 + DefPredMapBase(const Base &b) : Base(b) {}
2.1068 + };
2.1069 +
2.1070 + ///\brief \ref named-templ-param "Named parameter"
2.1071 + ///function for setting PredMap type
2.1072 + ///
2.1073 + /// \ref named-templ-param "Named parameter"
2.1074 + ///function for setting PredMap type
2.1075 + ///
2.1076 + template<class T>
2.1077 + DfsWizard<DefPredMapBase<T> > predMap(const T &t)
2.1078 + {
2.1079 + Base::_pred=(void *)&t;
2.1080 + return DfsWizard<DefPredMapBase<T> >(*this);
2.1081 + }
2.1082 +
2.1083 +
2.1084 + template<class T>
2.1085 + struct DefReachedMapBase : public Base {
2.1086 + typedef T ReachedMap;
2.1087 + static ReachedMap *createReachedMap(const Graph &G) { return 0; };
2.1088 + DefReachedMapBase(const Base &b) : Base(b) {}
2.1089 + };
2.1090 +
2.1091 + ///\brief \ref named-templ-param "Named parameter"
2.1092 + ///function for setting ReachedMap
2.1093 + ///
2.1094 + /// \ref named-templ-param "Named parameter"
2.1095 + ///function for setting ReachedMap
2.1096 + ///
2.1097 + template<class T>
2.1098 + DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
2.1099 + {
2.1100 + Base::_pred=(void *)&t;
2.1101 + return DfsWizard<DefReachedMapBase<T> >(*this);
2.1102 + }
2.1103 +
2.1104 +
2.1105 + template<class T>
2.1106 + struct DefProcessedMapBase : public Base {
2.1107 + typedef T ProcessedMap;
2.1108 + static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
2.1109 + DefProcessedMapBase(const Base &b) : Base(b) {}
2.1110 + };
2.1111 +
2.1112 + ///\brief \ref named-templ-param "Named parameter"
2.1113 + ///function for setting ProcessedMap
2.1114 + ///
2.1115 + /// \ref named-templ-param "Named parameter"
2.1116 + ///function for setting ProcessedMap
2.1117 + ///
2.1118 + template<class T>
2.1119 + DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
2.1120 + {
2.1121 + Base::_pred=(void *)&t;
2.1122 + return DfsWizard<DefProcessedMapBase<T> >(*this);
2.1123 + }
2.1124 +
2.1125 +
2.1126 +// template<class T>
2.1127 +// struct DefPredNodeMapBase : public Base {
2.1128 +// typedef T PredNodeMap;
2.1129 +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
2.1130 +// DefPredNodeMapBase(const Base &b) : Base(b) {}
2.1131 +// };
2.1132 +
2.1133 +// ///\brief \ref named-templ-param "Named parameter"
2.1134 +// ///function for setting PredNodeMap type
2.1135 +// ///
2.1136 +// /// \ref named-templ-param "Named parameter"
2.1137 +// ///function for setting PredNodeMap type
2.1138 +// ///
2.1139 +// template<class T>
2.1140 +// DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
2.1141 +// {
2.1142 +// Base::_predNode=(void *)&t;
2.1143 +// return DfsWizard<DefPredNodeMapBase<T> >(*this);
2.1144 +// }
2.1145 +
2.1146 + template<class T>
2.1147 + struct DefDistMapBase : public Base {
2.1148 + typedef T DistMap;
2.1149 + static DistMap *createDistMap(const Graph &G) { return 0; };
2.1150 + DefDistMapBase(const Base &b) : Base(b) {}
2.1151 + };
2.1152 +
2.1153 + ///\brief \ref named-templ-param "Named parameter"
2.1154 + ///function for setting DistMap type
2.1155 + ///
2.1156 + /// \ref named-templ-param "Named parameter"
2.1157 + ///function for setting DistMap type
2.1158 + ///
2.1159 + template<class T>
2.1160 + DfsWizard<DefDistMapBase<T> > distMap(const T &t)
2.1161 + {
2.1162 + Base::_dist=(void *)&t;
2.1163 + return DfsWizard<DefDistMapBase<T> >(*this);
2.1164 + }
2.1165 +
2.1166 + /// Sets the source node, from which the Dfs algorithm runs.
2.1167 +
2.1168 + /// Sets the source node, from which the Dfs algorithm runs.
2.1169 + /// \param s is the source node.
2.1170 + DfsWizard<TR> &source(Node s)
2.1171 + {
2.1172 + Base::_source=s;
2.1173 + return *this;
2.1174 + }
2.1175
2.1176 };
2.1177
2.1178 -/// @}
2.1179 -
2.1180 + ///Function type interface for Dfs algorithm.
2.1181 +
2.1182 + /// \ingroup flowalgs
2.1183 + ///Function type interface for Dfs algorithm.
2.1184 + ///
2.1185 + ///This function also has several
2.1186 + ///\ref named-templ-func-param "named parameters",
2.1187 + ///they are declared as the members of class \ref DfsWizard.
2.1188 + ///The following
2.1189 + ///example shows how to use these parameters.
2.1190 + ///\code
2.1191 + /// dfs(g,source).predMap(preds).run();
2.1192 + ///\endcode
2.1193 + ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
2.1194 + ///to the end of the parameter list.
2.1195 + ///\sa DfsWizard
2.1196 + ///\sa Dfs
2.1197 + template<class GR>
2.1198 + DfsWizard<DfsWizardBase<GR> >
2.1199 + dfs(const GR &g,typename GR::Node s=INVALID)
2.1200 + {
2.1201 + return DfsWizard<DfsWizardBase<GR> >(g,s);
2.1202 + }
2.1203 +
2.1204 } //END OF NAMESPACE LEMON
2.1205
2.1206 #endif
2.1207
2.1208 -
3.1 --- a/src/lemon/dijkstra.h Wed Mar 16 07:52:16 2005 +0000
3.2 +++ b/src/lemon/dijkstra.h Wed Mar 16 07:56:25 2005 +0000
3.3 @@ -76,40 +76,41 @@
3.4 {
3.5 return new PredMap(G);
3.6 }
3.7 - ///\brief The type of the map that stores the last but one
3.8 - ///nodes of the shortest paths.
3.9 - ///
3.10 - ///The type of the map that stores the last but one
3.11 - ///nodes of the shortest paths.
3.12 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.13 - ///
3.14 - typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
3.15 - ///Instantiates a PredNodeMap.
3.16 +// ///\brief The type of the map that stores the last but one
3.17 +// ///nodes of the shortest paths.
3.18 +// ///
3.19 +// ///The type of the map that stores the last but one
3.20 +// ///nodes of the shortest paths.
3.21 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.22 +// ///
3.23 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
3.24 +// ///Instantiates a PredNodeMap.
3.25
3.26 - ///This function instantiates a \ref PredNodeMap.
3.27 - ///\param G is the graph, to which
3.28 - ///we would like to define the \ref PredNodeMap
3.29 - static PredNodeMap *createPredNodeMap(const GR &G)
3.30 - {
3.31 - return new PredNodeMap();
3.32 - }
3.33 +// ///This function instantiates a \ref PredNodeMap.
3.34 +// ///\param G is the graph, to which
3.35 +// ///we would like to define the \ref PredNodeMap
3.36 +// static PredNodeMap *createPredNodeMap(const GR &G)
3.37 +// {
3.38 +// return new PredNodeMap();
3.39 +// }
3.40
3.41 - ///The type of the map that stores whether a nodes is reached.
3.42 + ///The type of the map that stores whether a nodes is processed.
3.43
3.44 - ///The type of the map that stores whether a nodes is reached.
3.45 + ///The type of the map that stores whether a nodes is processed.
3.46 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.47 ///By default it is a NullMap.
3.48 - ///\todo If it is set to a real map, Dijkstra::reached() should read this.
3.49 + ///\todo If it is set to a real map,
3.50 + ///Dijkstra::processed() should read this.
3.51 ///\todo named parameter to set this type, function to read and write.
3.52 - typedef NullMap<typename Graph::Node,bool> ReachedMap;
3.53 - ///Instantiates a ReachedMap.
3.54 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
3.55 + ///Instantiates a ProcessedMap.
3.56
3.57 - ///This function instantiates a \ref ReachedMap.
3.58 + ///This function instantiates a \ref ProcessedMap.
3.59 ///\param G is the graph, to which
3.60 - ///we would like to define the \ref ReachedMap
3.61 - static ReachedMap *createReachedMap(const GR &G)
3.62 + ///we would like to define the \ref ProcessedMap
3.63 + static ProcessedMap *createProcessedMap(const GR &G)
3.64 {
3.65 - return new ReachedMap();
3.66 + return new ProcessedMap();
3.67 }
3.68 ///The type of the map that stores the dists of the nodes.
3.69
3.70 @@ -140,23 +141,21 @@
3.71 ///
3.72 ///It is also possible to change the underlying priority heap.
3.73 ///
3.74 - ///\param GR The graph type the algorithm runs on. The default value is
3.75 - ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
3.76 - ///is only passed to \ref DijkstraDefaultTraits.
3.77 - ///\param LM This read-only
3.78 - ///EdgeMap
3.79 - ///determines the
3.80 - ///lengths of the edges. It is read once for each edge, so the map
3.81 - ///may involve in relatively time consuming process to compute the edge
3.82 - ///length if it is necessary. The default map type is
3.83 - ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
3.84 - ///The value of LM is not used directly by Dijkstra, it
3.85 - ///is only passed to \ref DijkstraDefaultTraits.
3.86 - ///\param TR Traits class to set various data types used by the algorithm.
3.87 - ///The default traits class is
3.88 - ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
3.89 - ///See \ref DijkstraDefaultTraits for the documentation of
3.90 - ///a Dijkstra traits class.
3.91 + ///\param GR The graph type the algorithm runs on. The default value
3.92 + ///is \ref ListGraph. The value of GR is not used directly by
3.93 + ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
3.94 + ///\param LM This read-only EdgeMap determines the lengths of the
3.95 + ///edges. It is read once for each edge, so the map may involve in
3.96 + ///relatively time consuming process to compute the edge length if
3.97 + ///it is necessary. The default map type is \ref
3.98 + ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
3.99 + ///of LM is not used directly by Dijkstra, it is only passed to \ref
3.100 + ///DijkstraDefaultTraits. \param TR Traits class to set
3.101 + ///various data types used by the algorithm. The default traits
3.102 + ///class is \ref DijkstraDefaultTraits
3.103 + ///"DijkstraDefaultTraits<GR,LM>". See \ref
3.104 + ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
3.105 + ///class.
3.106 ///
3.107 ///\author Jacint Szabo and Alpar Juttner
3.108 ///\todo A compare object would be nice.
3.109 @@ -181,7 +180,7 @@
3.110 class UninitializedParameter : public lemon::UninitializedParameter {
3.111 public:
3.112 virtual const char* exceptionName() const {
3.113 - return "lemon::Dijsktra::UninitializedParameter";
3.114 + return "lemon::Dijkstra::UninitializedParameter";
3.115 }
3.116 };
3.117
3.118 @@ -204,11 +203,11 @@
3.119 ///\brief The type of the map that stores the last
3.120 ///edges of the shortest paths.
3.121 typedef typename TR::PredMap PredMap;
3.122 - ///\brief The type of the map that stores the last but one
3.123 - ///nodes of the shortest paths.
3.124 - typedef typename TR::PredNodeMap PredNodeMap;
3.125 - ///The type of the map indicating if a node is reached.
3.126 - typedef typename TR::ReachedMap ReachedMap;
3.127 +// ///\brief The type of the map that stores the last but one
3.128 +// ///nodes of the shortest paths.
3.129 +// typedef typename TR::PredNodeMap PredNodeMap;
3.130 + ///The type of the map indicating if a node is processed.
3.131 + typedef typename TR::ProcessedMap ProcessedMap;
3.132 ///The type of the map that stores the dists of the nodes.
3.133 typedef typename TR::DistMap DistMap;
3.134 ///The heap type used by the dijkstra algorithm.
3.135 @@ -222,21 +221,21 @@
3.136 PredMap *_pred;
3.137 ///Indicates if \ref _pred is locally allocated (\c true) or not.
3.138 bool local_pred;
3.139 - ///Pointer to the map of predecessors nodes.
3.140 - PredNodeMap *_predNode;
3.141 - ///Indicates if \ref _predNode is locally allocated (\c true) or not.
3.142 - bool local_predNode;
3.143 +// ///Pointer to the map of predecessors nodes.
3.144 +// PredNodeMap *_predNode;
3.145 +// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
3.146 +// bool local_predNode;
3.147 ///Pointer to the map of distances.
3.148 DistMap *_dist;
3.149 ///Indicates if \ref _dist is locally allocated (\c true) or not.
3.150 bool local_dist;
3.151 - ///Pointer to the map of reached status of the nodes.
3.152 - ReachedMap *_reached;
3.153 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
3.154 - bool local_reached;
3.155 + ///Pointer to the map of processed status of the nodes.
3.156 + ProcessedMap *_processed;
3.157 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
3.158 + bool local_processed;
3.159
3.160 - ///The source node of the last execution.
3.161 - Node source;
3.162 +// ///The source node of the last execution.
3.163 +// Node source;
3.164
3.165 ///Creates the maps if necessary.
3.166
3.167 @@ -248,17 +247,17 @@
3.168 local_pred = true;
3.169 _pred = Traits::createPredMap(*G);
3.170 }
3.171 - if(!_predNode) {
3.172 - local_predNode = true;
3.173 - _predNode = Traits::createPredNodeMap(*G);
3.174 - }
3.175 +// if(!_predNode) {
3.176 +// local_predNode = true;
3.177 +// _predNode = Traits::createPredNodeMap(*G);
3.178 +// }
3.179 if(!_dist) {
3.180 local_dist = true;
3.181 _dist = Traits::createDistMap(*G);
3.182 }
3.183 - if(!_reached) {
3.184 - local_reached = true;
3.185 - _reached = Traits::createReachedMap(*G);
3.186 + if(!_processed) {
3.187 + local_processed = true;
3.188 + _processed = Traits::createProcessedMap(*G);
3.189 }
3.190 }
3.191
3.192 @@ -285,22 +284,22 @@
3.193 LengthMap,
3.194 DefPredMapTraits<T> > { };
3.195
3.196 - template <class T>
3.197 - struct DefPredNodeMapTraits : public Traits {
3.198 - typedef T PredNodeMap;
3.199 - static PredNodeMap *createPredNodeMap(const Graph &G)
3.200 - {
3.201 - throw UninitializedParameter();
3.202 - }
3.203 - };
3.204 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
3.205 +// template <class T>
3.206 +// struct DefPredNodeMapTraits : public Traits {
3.207 +// typedef T PredNodeMap;
3.208 +// static PredNodeMap *createPredNodeMap(const Graph &G)
3.209 +// {
3.210 +// throw UninitializedParameter();
3.211 +// }
3.212 +// };
3.213 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
3.214
3.215 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
3.216 - ///
3.217 - template <class T>
3.218 - class DefPredNodeMap : public Dijkstra< Graph,
3.219 - LengthMap,
3.220 - DefPredNodeMapTraits<T> > { };
3.221 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
3.222 +// ///
3.223 +// template <class T>
3.224 +// class DefPredNodeMap : public Dijkstra< Graph,
3.225 +// LengthMap,
3.226 +// DefPredNodeMapTraits<T> > { };
3.227
3.228 template <class T>
3.229 struct DefDistMapTraits : public Traits {
3.230 @@ -320,40 +319,40 @@
3.231 DefDistMapTraits<T> > { };
3.232
3.233 template <class T>
3.234 - struct DefReachedMapTraits : public Traits {
3.235 - typedef T ReachedMap;
3.236 - static ReachedMap *createReachedMap(const Graph &G)
3.237 + struct DefProcessedMapTraits : public Traits {
3.238 + typedef T ProcessedMap;
3.239 + static ProcessedMap *createProcessedMap(const Graph &G)
3.240 {
3.241 throw UninitializedParameter();
3.242 }
3.243 };
3.244 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
3.245 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
3.246
3.247 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
3.248 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
3.249 ///
3.250 template <class T>
3.251 - class DefReachedMap : public Dijkstra< Graph,
3.252 + class DefProcessedMap : public Dijkstra< Graph,
3.253 LengthMap,
3.254 - DefReachedMapTraits<T> > { };
3.255 + DefProcessedMapTraits<T> > { };
3.256
3.257 - struct DefGraphReachedMapTraits : public Traits {
3.258 - typedef typename Graph::template NodeMap<bool> ReachedMap;
3.259 - static ReachedMap *createReachedMap(const Graph &G)
3.260 + struct DefGraphProcessedMapTraits : public Traits {
3.261 + typedef typename Graph::template NodeMap<bool> ProcessedMap;
3.262 + static ProcessedMap *createProcessedMap(const Graph &G)
3.263 {
3.264 - return new ReachedMap(G);
3.265 + return new ProcessedMap(G);
3.266 }
3.267 };
3.268 ///\brief \ref named-templ-param "Named parameter"
3.269 - ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
3.270 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
3.271 ///
3.272 ///\ref named-templ-param "Named parameter"
3.273 - ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
3.274 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
3.275 ///If you don't set it explicitely, it will be automatically allocated.
3.276 template <class T>
3.277 - class DefReachedMapToBeDefaultMap :
3.278 + class DefProcessedMapToBeDefaultMap :
3.279 public Dijkstra< Graph,
3.280 LengthMap,
3.281 - DefGraphReachedMapTraits> { };
3.282 + DefGraphProcessedMapTraits> { };
3.283
3.284 ///@}
3.285
3.286 @@ -370,9 +369,9 @@
3.287 Dijkstra(const Graph& _G, const LengthMap& _length) :
3.288 G(&_G), length(&_length),
3.289 _pred(NULL), local_pred(false),
3.290 - _predNode(NULL), local_predNode(false),
3.291 +// _predNode(NULL), local_predNode(false),
3.292 _dist(NULL), local_dist(false),
3.293 - _reached(NULL), local_reached(false),
3.294 + _processed(NULL), local_processed(false),
3.295 _heap_map(*G,-1),_heap(_heap_map)
3.296 { }
3.297
3.298 @@ -380,9 +379,9 @@
3.299 ~Dijkstra()
3.300 {
3.301 if(local_pred) delete _pred;
3.302 - if(local_predNode) delete _predNode;
3.303 +// if(local_predNode) delete _predNode;
3.304 if(local_dist) delete _dist;
3.305 - if(local_reached) delete _reached;
3.306 + if(local_processed) delete _processed;
3.307 }
3.308
3.309 ///Sets the length map.
3.310 @@ -412,22 +411,22 @@
3.311 return *this;
3.312 }
3.313
3.314 - ///Sets the map storing the predecessor nodes.
3.315 +// ///Sets the map storing the predecessor nodes.
3.316
3.317 - ///Sets the map storing the predecessor nodes.
3.318 - ///If you don't use this function before calling \ref run(),
3.319 - ///it will allocate one. The destuctor deallocates this
3.320 - ///automatically allocated map, of course.
3.321 - ///\return <tt> (*this) </tt>
3.322 - Dijkstra &predNodeMap(PredNodeMap &m)
3.323 - {
3.324 - if(local_predNode) {
3.325 - delete _predNode;
3.326 - local_predNode=false;
3.327 - }
3.328 - _predNode = &m;
3.329 - return *this;
3.330 - }
3.331 +// ///Sets the map storing the predecessor nodes.
3.332 +// ///If you don't use this function before calling \ref run(),
3.333 +// ///it will allocate one. The destuctor deallocates this
3.334 +// ///automatically allocated map, of course.
3.335 +// ///\return <tt> (*this) </tt>
3.336 +// Dijkstra &predNodeMap(PredNodeMap &m)
3.337 +// {
3.338 +// if(local_predNode) {
3.339 +// delete _predNode;
3.340 +// local_predNode=false;
3.341 +// }
3.342 +// _predNode = &m;
3.343 +// return *this;
3.344 +// }
3.345
3.346 ///Sets the map storing the distances calculated by the algorithm.
3.347
3.348 @@ -449,19 +448,21 @@
3.349 private:
3.350 void finalizeNodeData(Node v,Value dst)
3.351 {
3.352 - _reached->set(v,true);
3.353 + _processed->set(v,true);
3.354 _dist->set(v, dst);
3.355 - if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
3.356 +// if((*_pred)[v]!=INVALID)
3.357 +// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
3.358 }
3.359
3.360 public:
3.361 - ///\name Excetution control
3.362 + ///\name Execution control
3.363 ///The simplest way to execute the algorithm is to use
3.364 ///one of the member functions called \c run(...).
3.365 ///\n
3.366 - ///It you need more control on the execution,
3.367 + ///If you need more control on the execution,
3.368 ///first you must call \ref init(), then you can add several source nodes
3.369 - ///with \ref addSource(). Finally \ref start() will perform the actual path
3.370 + ///with \ref addSource().
3.371 + ///Finally \ref start() will perform the actual path
3.372 ///computation.
3.373
3.374 ///@{
3.375 @@ -477,8 +478,8 @@
3.376
3.377 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
3.378 _pred->set(u,INVALID);
3.379 - _predNode->set(u,INVALID);
3.380 - ///\todo *_reached is not set to false.
3.381 +// _predNode->set(u,INVALID);
3.382 + _processed->set(u,false);
3.383 _heap_map.set(u,Heap::PRE_HEAP);
3.384 }
3.385 }
3.386 @@ -494,7 +495,7 @@
3.387 ///or the shortest path found till then is longer then \c dst.
3.388 void addSource(Node s,Value dst=0)
3.389 {
3.390 - source = s;
3.391 +// source = s;
3.392 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
3.393 else if(_heap[s]<dst) {
3.394 _heap.push(s,dst);
3.395 @@ -535,16 +536,17 @@
3.396 }
3.397 }
3.398
3.399 - ///Returns \c false if there are nodes to be processed in the priority heap
3.400 -
3.401 - ///Returns \c false if there are nodes to be processed in the priority heap
3.402 + ///\brief Returns \c false if there are nodes
3.403 + ///to be processed in the priority heap
3.404 ///
3.405 - bool emptyHeap() { return _heap.empty(); }
3.406 + ///Returns \c false if there are nodes
3.407 + ///to be processed in the priority heap
3.408 + bool emptyQueue() { return _heap.empty(); }
3.409 ///Returns the number of the nodes to be processed in the priority heap
3.410
3.411 ///Returns the number of the nodes to be processed in the priority heap
3.412 ///
3.413 - int heapSize() { return _heap.size(); }
3.414 + int queueSize() { return _heap.size(); }
3.415
3.416 ///Executes the algorithm.
3.417
3.418 @@ -696,25 +698,107 @@
3.419 ///\pre \ref run() must be called before using this function.
3.420 const PredMap &predMap() const { return *_pred;}
3.421
3.422 - ///Returns a reference to the map of nodes of shortest paths.
3.423 +// ///Returns a reference to the map of nodes of shortest paths.
3.424
3.425 - ///Returns a reference to the NodeMap of the last but one nodes of the
3.426 - ///shortest path tree.
3.427 - ///\pre \ref run() must be called before using this function.
3.428 - const PredNodeMap &predNodeMap() const { return *_predNode;}
3.429 +// ///Returns a reference to the NodeMap of the last but one nodes of the
3.430 +// ///shortest path tree.
3.431 +// ///\pre \ref run() must be called before using this function.
3.432 +// const PredNodeMap &predNodeMap() const { return *_predNode;}
3.433
3.434 ///Checks if a node is reachable from the root.
3.435
3.436 ///Returns \c true if \c v is reachable from the root.
3.437 - ///\warning If the algorithm is started from multiple nodes,
3.438 - ///this function may give false result for the source nodes.
3.439 + ///\warning The source nodes are inditated as unreached.
3.440 ///\pre \ref run() must be called before using this function.
3.441 ///
3.442 - bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
3.443 + bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
3.444
3.445 ///@}
3.446 };
3.447
3.448 +
3.449 +
3.450 +
3.451 +
3.452 + ///Default traits class of Dijkstra function.
3.453 +
3.454 + ///Default traits class of Dijkstra function.
3.455 + ///\param GR Graph type.
3.456 + ///\param LM Type of length map.
3.457 + template<class GR, class LM>
3.458 + struct DijkstraWizardDefaultTraits
3.459 + {
3.460 + ///The graph type the algorithm runs on.
3.461 + typedef GR Graph;
3.462 + ///The type of the map that stores the edge lengths.
3.463 +
3.464 + ///The type of the map that stores the edge lengths.
3.465 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
3.466 + typedef LM LengthMap;
3.467 + //The type of the length of the edges.
3.468 + typedef typename LM::Value Value;
3.469 + ///The heap type used by Dijkstra algorithm.
3.470 +
3.471 + ///The heap type used by Dijkstra algorithm.
3.472 + ///
3.473 + ///\sa BinHeap
3.474 + ///\sa Dijkstra
3.475 + typedef BinHeap<typename Graph::Node,
3.476 + typename LM::Value,
3.477 + typename GR::template NodeMap<int>,
3.478 + std::less<Value> > Heap;
3.479 +
3.480 + ///\brief The type of the map that stores the last
3.481 + ///edges of the shortest paths.
3.482 + ///
3.483 + ///The type of the map that stores the last
3.484 + ///edges of the shortest paths.
3.485 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.486 + ///
3.487 + typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
3.488 + ///Instantiates a PredMap.
3.489 +
3.490 + ///This function instantiates a \ref PredMap.
3.491 + ///\param G is the graph, to which we would like to define the PredMap.
3.492 + ///\todo The graph alone may be insufficient for the initialization
3.493 + static PredMap *createPredMap(const GR &G)
3.494 + {
3.495 + return new PredMap();
3.496 + }
3.497 + ///The type of the map that stores whether a nodes is processed.
3.498 +
3.499 + ///The type of the map that stores whether a nodes is processed.
3.500 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.501 + ///By default it is a NullMap.
3.502 + ///\todo If it is set to a real map,
3.503 + ///Dijkstra::processed() should read this.
3.504 + ///\todo named parameter to set this type, function to read and write.
3.505 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
3.506 + ///Instantiates a ProcessedMap.
3.507 +
3.508 + ///This function instantiates a \ref ProcessedMap.
3.509 + ///\param G is the graph, to which
3.510 + ///we would like to define the \ref ProcessedMap
3.511 + static ProcessedMap *createProcessedMap(const GR &G)
3.512 + {
3.513 + return new ProcessedMap();
3.514 + }
3.515 + ///The type of the map that stores the dists of the nodes.
3.516 +
3.517 + ///The type of the map that stores the dists of the nodes.
3.518 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.519 + ///
3.520 + typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
3.521 + ///Instantiates a DistMap.
3.522 +
3.523 + ///This function instantiates a \ref DistMap.
3.524 + ///\param G is the graph, to which we would like to define the \ref DistMap
3.525 + static DistMap *createDistMap(const GR &G)
3.526 + {
3.527 + return new DistMap();
3.528 + }
3.529 + };
3.530 +
3.531 /// Default traits used by \ref DijkstraWizard
3.532
3.533 /// To make it easier to use Dijkstra algorithm
3.534 @@ -724,10 +808,10 @@
3.535 /// The \ref DijkstraWizardBase is a class to be the default traits of the
3.536 /// \ref DijkstraWizard class.
3.537 template<class GR,class LM>
3.538 - class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
3.539 + class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
3.540 {
3.541
3.542 - typedef DijkstraDefaultTraits<GR,LM> Base;
3.543 + typedef DijkstraWizardDefaultTraits<GR,LM> Base;
3.544 protected:
3.545 /// Type of the nodes in the graph.
3.546 typedef typename Base::Graph::Node Node;
3.547 @@ -738,8 +822,8 @@
3.548 void *_length;
3.549 ///Pointer to the map of predecessors edges.
3.550 void *_pred;
3.551 - ///Pointer to the map of predecessors nodes.
3.552 - void *_predNode;
3.553 +// ///Pointer to the map of predecessors nodes.
3.554 +// void *_predNode;
3.555 ///Pointer to the map of distances.
3.556 void *_dist;
3.557 ///Pointer to the source node.
3.558 @@ -750,8 +834,9 @@
3.559
3.560 /// This constructor does not require parameters, therefore it initiates
3.561 /// all of the attributes to default values (0, INVALID).
3.562 - DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
3.563 - _dist(0), _source(INVALID) {}
3.564 + DijkstraWizardBase() : _g(0), _length(0), _pred(0),
3.565 +// _predNode(0),
3.566 + _dist(0), _source(INVALID) {}
3.567
3.568 /// Constructor.
3.569
3.570 @@ -762,14 +847,14 @@
3.571 /// \param l is the initial value of \ref _length
3.572 /// \param s is the initial value of \ref _source
3.573 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
3.574 - _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
3.575 - _dist(0), _source(s) {}
3.576 + _g((void *)&g), _length((void *)&l), _pred(0),
3.577 +// _predNode(0),
3.578 + _dist(0), _source(s) {}
3.579
3.580 };
3.581
3.582 /// A class to make easier the usage of Dijkstra algorithm
3.583
3.584 - /// \ingroup flowalgs
3.585 /// This class is created to make it easier to use Dijkstra algorithm.
3.586 /// It uses the functions and features of the plain \ref Dijkstra,
3.587 /// but it is much simpler to use it.
3.588 @@ -810,9 +895,9 @@
3.589 ///\brief The type of the map that stores the last
3.590 ///edges of the shortest paths.
3.591 typedef typename TR::PredMap PredMap;
3.592 - ///\brief The type of the map that stores the last but one
3.593 - ///nodes of the shortest paths.
3.594 - typedef typename TR::PredNodeMap PredNodeMap;
3.595 +// ///\brief The type of the map that stores the last but one
3.596 +// ///nodes of the shortest paths.
3.597 +// typedef typename TR::PredNodeMap PredNodeMap;
3.598 ///The type of the map that stores the dists of the nodes.
3.599 typedef typename TR::DistMap DistMap;
3.600
3.601 @@ -844,7 +929,7 @@
3.602 Dijkstra<Graph,LengthMap,TR>
3.603 Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
3.604 if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
3.605 - if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
3.606 +// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
3.607 if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
3.608 Dij.run(Base::_source);
3.609 }
3.610 @@ -880,25 +965,25 @@
3.611 }
3.612
3.613
3.614 - template<class T>
3.615 - struct DefPredNodeMapBase : public Base {
3.616 - typedef T PredNodeMap;
3.617 - static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
3.618 - DefPredNodeMapBase(const Base &b) : Base(b) {}
3.619 - };
3.620 +// template<class T>
3.621 +// struct DefPredNodeMapBase : public Base {
3.622 +// typedef T PredNodeMap;
3.623 +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
3.624 +// DefPredNodeMapBase(const Base &b) : Base(b) {}
3.625 +// };
3.626
3.627 - ///\brief \ref named-templ-param "Named parameter"
3.628 - ///function for setting PredNodeMap type
3.629 - ///
3.630 - /// \ref named-templ-param "Named parameter"
3.631 - ///function for setting PredNodeMap type
3.632 - ///
3.633 - template<class T>
3.634 - DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
3.635 - {
3.636 - Base::_predNode=(void *)&t;
3.637 - return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
3.638 - }
3.639 +// ///\brief \ref named-templ-param "Named parameter"
3.640 +// ///function for setting PredNodeMap type
3.641 +// ///
3.642 +// /// \ref named-templ-param "Named parameter"
3.643 +// ///function for setting PredNodeMap type
3.644 +// ///
3.645 +// template<class T>
3.646 +// DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
3.647 +// {
3.648 +// Base::_predNode=(void *)&t;
3.649 +// return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
3.650 +// }
3.651
3.652 template<class T>
3.653 struct DefDistMapBase : public Base {
3.654 @@ -932,11 +1017,23 @@
3.655
3.656 };
3.657
3.658 - ///\e
3.659 + ///Function type interface for Dijkstra algorithm.
3.660
3.661 /// \ingroup flowalgs
3.662 - ///\todo Please document...
3.663 + ///Function type interface for Dijkstra algorithm.
3.664 ///
3.665 + ///This function also has several
3.666 + ///\ref named-templ-func-param "named parameters",
3.667 + ///they are declared as the members of class \ref DijkstraWizard.
3.668 + ///The following
3.669 + ///example shows how to use these parameters.
3.670 + ///\code
3.671 + /// dijkstra(g,length,source).predMap(preds).run();
3.672 + ///\endcode
3.673 + ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
3.674 + ///to the end of the parameter list.
3.675 + ///\sa DijkstraWizard
3.676 + ///\sa Dijkstra
3.677 template<class GR, class LM>
3.678 DijkstraWizard<DijkstraWizardBase<GR,LM> >
3.679 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
3.680 @@ -944,8 +1041,6 @@
3.681 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
3.682 }
3.683
3.684 -/// @}
3.685 -
3.686 } //END OF NAMESPACE LEMON
3.687
3.688 #endif
4.1 --- a/src/test/bfs_test.cc Wed Mar 16 07:52:16 2005 +0000
4.2 +++ b/src/test/bfs_test.cc Wed Mar 16 07:56:25 2005 +0000
4.3 @@ -42,7 +42,7 @@
4.4 bool b;
4.5 BType::DistMap d(G);
4.6 BType::PredMap p(G);
4.7 - BType::PredNodeMap pn(G);
4.8 + // BType::PredNodeMap pn(G);
4.9
4.10 BType bfs_test(G);
4.11
4.12 @@ -53,7 +53,7 @@
4.13 n = bfs_test.predNode(n);
4.14 d = bfs_test.distMap();
4.15 p = bfs_test.predMap();
4.16 - pn = bfs_test.predNodeMap();
4.17 + // pn = bfs_test.predNodeMap();
4.18 b = bfs_test.reached(n);
4.19
4.20 }
5.1 --- a/src/test/dfs_test.cc Wed Mar 16 07:52:16 2005 +0000
5.2 +++ b/src/test/dfs_test.cc Wed Mar 16 07:56:25 2005 +0000
5.3 @@ -42,7 +42,7 @@
5.4 bool b;
5.5 DType::DistMap d(G);
5.6 DType::PredMap p(G);
5.7 - DType::PredNodeMap pn(G);
5.8 + // DType::PredNodeMap pn(G);
5.9
5.10 DType dfs_test(G);
5.11
5.12 @@ -53,7 +53,7 @@
5.13 n = dfs_test.predNode(n);
5.14 d = dfs_test.distMap();
5.15 p = dfs_test.predMap();
5.16 - pn = dfs_test.predNodeMap();
5.17 + // pn = dfs_test.predNodeMap();
5.18 b = dfs_test.reached(n);
5.19
5.20 }
6.1 --- a/src/test/dijkstra_test.cc Wed Mar 16 07:52:16 2005 +0000
6.2 +++ b/src/test/dijkstra_test.cc Wed Mar 16 07:56:25 2005 +0000
6.3 @@ -119,8 +119,8 @@
6.4
6.5
6.6 {
6.7 - NullMap<Node,Node> myPredNodeMap;
6.8 - dijkstra(G,cap).predNodeMap(myPredNodeMap).run(s);
6.9 + NullMap<Node,Edge> myPredMap;
6.10 + dijkstra(G,cap).predMap(myPredMap).run(s);
6.11 }
6.12 return 0;
6.13 }