# HG changeset patch # User alpar # Date 1110959785 0 # Node ID 5331168bbb1894c5b63f11cd0fc7f74583cf244e # Parent 640ca1bd850fa6e7b21a663e3a3f53d12d0d6b5c - Several updates and clarifications on dijkstra.h - bfs.h and dfs.h is synchronized with dijkstra.h diff -r 640ca1bd850f -r 5331168bbb18 src/lemon/bfs.h --- a/src/lemon/bfs.h Wed Mar 16 07:52:16 2005 +0000 +++ b/src/lemon/bfs.h Wed Mar 16 07:56:25 2005 +0000 @@ -20,36 +20,149 @@ ///\ingroup flowalgs ///\file ///\brief Bfs algorithm. -/// -///\todo Revise Manual. -#include +#include +#include #include -#include +#include +#include namespace lemon { -/// \addtogroup flowalgs -/// @{ + + ///Default traits class of Bfs class. + + ///Default traits class of Bfs class. + ///\param GR Graph type. + template + struct BfsDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + /// + ///The type of the map that stores the last + ///edges of the shortest paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient to initialize + static PredMap *createPredMap(const GR &G) + { + return new PredMap(G); + } +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// /// +// ///The type of the map that stores the last but one +// ///nodes of the shortest paths. +// ///It must meet the \ref concept::WriteMap "WriteMap" concept. +// /// +// typedef NullMap PredNodeMap; +// ///Instantiates a PredNodeMap. + +// ///This function instantiates a \ref PredNodeMap. +// ///\param G is the graph, to which +// ///we would like to define the \ref PredNodeMap +// static PredNodeMap *createPredNodeMap(const GR &G) +// { +// return new PredNodeMap(); +// } + + ///The type of the map that indicates which nodes are processed. + + ///The type of the map that indicates which nodes are processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &G) + { + return new ProcessedMap(); + } + ///The type of the map that indicates which nodes are reached. + + ///The type of the map that indicates which nodes are reached. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef typename Graph::template NodeMap ReachedMap; + ///Instantiates a ReachedMap. + + ///This function instantiates a \ref ReachedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ReachedMap. + static ReachedMap *createReachedMap(const GR &G) + { + return new ReachedMap(G); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &G) + { + return new DistMap(G); + } + }; + ///%BFS algorithm class. - - ///This class provides an efficient implementation of %BFS algorithm. - ///\param GR The graph type the algorithm runs on. - ///This class does the same as Dijkstra does with constant 1 edge length, - ///but it is faster. + + ///\ingroup flowalgs + ///This class provides an efficient implementation of the %BFS algorithm. /// - ///\author Alpar Juttner + ///\param GR The graph type the algorithm runs on. The default value is + ///\ref ListGraph. The value of GR is not used directly by Bfs, it + ///is only passed to \ref BfsDefaultTraits. + ///\param TR Traits class to set various data types used by the algorithm. + ///The default traits class is + ///\ref BfsDefaultTraits "BfsDefaultTraits". + ///See \ref BfsDefaultTraits for the documentation of + ///a Bfs traits class. + /// + ///\author Jacint Szabo and Alpar Juttner + ///\todo A compare object would be nice. #ifdef DOXYGEN - template + template #else - template + template > #endif - class Bfs{ + class Bfs { public: + /** + * \brief \ref Exception for uninitialized parameters. + * + * This error represents problems in the initialization + * of the parameters of the algorithms. + */ + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::Bfs::UninitializedParameter"; + } + }; + + typedef TR Traits; ///The type of the underlying graph. - typedef GR Graph; + typedef typename TR::Graph Graph; ///\e typedef typename Graph::Node Node; ///\e @@ -61,68 +174,211 @@ ///\brief The type of the map that stores the last ///edges of the shortest paths. - typedef typename Graph::template NodeMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - typedef typename Graph::template NodeMap PredNodeMap; + typedef typename TR::PredMap PredMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map indicating which nodes are reached. + typedef typename TR::ReachedMap ReachedMap; + ///The type of the map indicating which nodes are processed. + typedef typename TR::ProcessedMap ProcessedMap; ///The type of the map that stores the dists of the nodes. - typedef typename Graph::template NodeMap DistMap; - + typedef typename TR::DistMap DistMap; private: /// Pointer to the underlying graph. const Graph *G; ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; +// ///Pointer to the map of predecessors nodes. +// PredNodeMap *_predNode; +// ///Indicates if \ref _predNode is locally allocated (\c true) or not. +// bool local_predNode; ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; + ///Pointer to the map of reached status of the nodes. + ReachedMap *_reached; + ///Indicates if \ref _reached is locally allocated (\c true) or not. + bool local_reached; + ///Pointer to the map of processed status of the nodes. + ProcessedMap *_processed; + ///Indicates if \ref _processed is locally allocated (\c true) or not. + bool local_processed; - ///The source node of the last execution. - Node source; + std::vector _queue; + int _queue_head,_queue_tail,_queue_next_dist; + int _curr_dist; +// ///The source node of the last execution. +// Node source; - - ///Initializes the maps. - void init_maps() + ///Creates the maps if necessary. + + ///\todo Error if \c G are \c NULL. + ///\todo Better memory allocation (instead of new). + void create_maps() { - if(!predecessor) { - local_predecessor = true; - predecessor = new PredMap(*G); + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*G); } - if(!pred_node) { - local_pred_node = true; - pred_node = new PredNodeMap(*G); +// if(!_predNode) { +// local_predNode = true; +// _predNode = Traits::createPredNodeMap(*G); +// } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*G); } - if(!distance) { - local_distance = true; - distance = new DistMap(*G); + if(!_reached) { + local_reached = true; + _reached = Traits::createReachedMap(*G); + } + if(!_processed) { + local_processed = true; + _processed = Traits::createProcessedMap(*G); } } - public : + public : + + ///\name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting PredMap type + + ///\ref named-templ-param "Named parameter" for setting PredMap type + /// + template + class DefPredMap : public Bfs< Graph, + DefPredMapTraits > { }; + +// template +// struct DefPredNodeMapTraits : public Traits { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) +// { +// throw UninitializedParameter(); +// } +// }; +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type + +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type +// /// +// template +// class DefPredNodeMap : public Bfs< Graph, +// LengthMap, +// DefPredNodeMapTraits > { }; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting DistMap type + + ///\ref named-templ-param "Named parameter" for setting DistMap type + /// + template + class DefDistMap : public Bfs< Graph, + DefDistMapTraits > { }; + + template + struct DefReachedMapTraits : public Traits { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + /// + template + class DefReachedMap : public Bfs< Graph, + DefReachedMapTraits > { }; + + struct DefGraphReachedMapTraits : public Traits { + typedef typename Graph::template NodeMap ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + return new ReachedMap(G); + } + }; + template + struct DefProcessedMapTraits : public Traits { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + /// + template + class DefProcessedMap : public Bfs< Graph, + DefProcessedMapTraits > { }; + + struct DefGraphProcessedMapTraits : public Traits { + typedef typename Graph::template NodeMap ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) + { + return new ProcessedMap(G); + } + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting the ProcessedMap type to be Graph::NodeMap. + /// + ///\ref named-templ-param "Named parameter" + ///for setting the ProcessedMap type to be Graph::NodeMap. + ///If you don't set it explicitely, it will be automatically allocated. + template + class DefProcessedMapToBeDefaultMap : + public Bfs< Graph, + DefGraphProcessedMapTraits> { }; + + ///@} + + public: + ///Constructor. ///\param _G the graph the algorithm will run on. /// Bfs(const Graph& _G) : G(&_G), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) + _pred(NULL), local_pred(false), +// _predNode(NULL), local_predNode(false), + _dist(NULL), local_dist(false), + _reached(NULL), local_reached(false), + _processed(NULL), local_processed(false) { } ///Destructor. ~Bfs() { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; + if(local_pred) delete _pred; +// if(local_predNode) delete _predNode; + if(local_dist) delete _dist; + if(local_reached) delete _reached; + if(local_processed) delete _processed; } ///Sets the map storing the predecessor edges. @@ -132,33 +388,67 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &setPredMap(PredMap &m) + Bfs &predMap(PredMap &m) { - if(local_predecessor) { - delete predecessor; - local_predecessor=false; + if(local_pred) { + delete _pred; + local_pred=false; } - predecessor = &m; + _pred = &m; return *this; } - ///Sets the map storing the predecessor nodes. + ///Sets the map indicating the reached nodes. - ///Sets the map storing the predecessor nodes. + ///Sets the map indicating the reached nodes. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &setPredNodeMap(PredNodeMap &m) + Bfs &reachedMap(ReachedMap &m) { - if(local_pred_node) { - delete pred_node; - local_pred_node=false; + if(local_reached) { + delete _reached; + local_reached=false; } - pred_node = &m; + _reached = &m; return *this; } + ///Sets the map indicating the processed nodes. + + ///Sets the map indicating the processed nodes. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Bfs &processedMap(ProcessedMap &m) + { + if(local_processed) { + delete _processed; + local_processed=false; + } + _processed = &m; + return *this; + } + +// ///Sets the map storing the predecessor nodes. + +// ///Sets the map storing the predecessor nodes. +// ///If you don't use this function before calling \ref run(), +// ///it will allocate one. The destuctor deallocates this +// ///automatically allocated map, of course. +// ///\return (*this) +// Bfs &predNodeMap(PredNodeMap &m) +// { +// if(local_predNode) { +// delete _predNode; +// local_predNode=false; +// } +// _predNode = &m; +// return *this; +// } + ///Sets the map storing the distances calculated by the algorithm. ///Sets the map storing the distances calculated by the algorithm. @@ -166,122 +456,652 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &setDistMap(DistMap &m) + Bfs &distMap(DistMap &m) { - if(local_distance) { - delete distance; - local_distance=false; + if(local_dist) { + delete _dist; + local_dist=false; } - distance = &m; + _dist = &m; return *this; } - - ///Runs %BFS algorithm from node \c s. - ///This method runs the %BFS algorithm from a root node \c s - ///in order to - ///compute a - ///shortest path to each node. The algorithm computes - ///- The %BFS tree. - ///- The distance of each node from the root. - - void run(Node s) { - - init_maps(); - - source = s; - + public: + ///\name Execution control + ///The simplest way to execute the algorithm is to use + ///one of the member functions called \c run(...). + ///\n + ///If you need more control on the execution, + ///first you must call \ref init(), then you can add several source nodes + ///with \ref addSource(). + ///Finally \ref start() will perform the actual path + ///computation. + + ///@{ + + ///Initializes the internal data structures. + + ///Initializes the internal data structures. + /// + void init() + { + create_maps(); + _queue.resize(countNodes(*G)); + _queue_head=_queue_tail=0; + _curr_dist=1; for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - predecessor->set(u,INVALID); - pred_node->set(u,INVALID); + _pred->set(u,INVALID); +// _predNode->set(u,INVALID); + _reached->set(u,false); + _processed->set(u,false); } - - int N = countNodes(*G); - std::vector Q(N); - int Qh=0; - int Qt=0; - - Q[Qh++]=source; - distance->set(s, 0); - do { - Node m; - Node n=Q[Qt++]; - int d= (*distance)[n]+1; - - for(OutEdgeIt e(*G,n);e!=INVALID;++e) - if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) { - Q[Qh++]=m; - predecessor->set(m,e); - pred_node->set(m,n); - distance->set(m,d); - } - } while(Qt!=Qh); } - ///The distance of a node from the root. + ///Adds a new source node. - ///Returns the distance of a node from the root. + ///Adds a new source node to the set of nodes to be processed. + /// + void addSource(Node s) + { + if(!(*_reached)[s]) + { + _reached->set(s,true); + _pred->set(s,INVALID); + _dist->set(s,0); + _queue[_queue_head++]=s; + _queue_next_dist=_queue_head; + } + } + + ///Processes the next node. + + ///Processes the next node. + /// + ///\warning The queue must not be empty! + void processNextNode() + { + if(_queue_tail==_queue_next_dist) { + _curr_dist++; + _queue_next_dist=_queue_head; + } + Node n=_queue[_queue_tail++]; + _processed->set(n,true); + Node m; + for(OutEdgeIt e(*G,n);e!=INVALID;++e) + if(!(*_reached)[m=G->target(e)]) { + _queue[_queue_head++]=m; + _reached->set(m,true); + _pred->set(m,e); +// _pred_node->set(m,n); + _dist->set(m,_curr_dist); + } + } + + ///\brief Returns \c false if there are nodes + ///to be processed in the queue + /// + ///Returns \c false if there are nodes + ///to be processed in the queue + bool emptyQueue() { return _queue_tail==_queue_head; } + ///Returns the number of the nodes to be processed. + + ///Returns the number of the nodes to be processed in the queue. + /// + int queueSize() { return _queue_head-_queue_tail; } + + ///Executes the algorithm. + + ///Executes the algorithm. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %BFS algorithm from the root node(s) + ///in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node from the root(s). + /// + void start() + { + while ( !emptyQueue() ) processNextNode(); + } + + ///Executes the algorithm until \c dest is reached. + + ///Executes the algorithm until \c dest is reached. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %BFS algorithm from the root node(s) + ///in order to + ///compute the + ///shortest path to \c dest. The algorithm computes + ///- The shortest path to \c dest. + ///- The distance of \c dest from the root(s). + /// + void start(Node dest) + { + while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode(); + } + + ///Executes the algorithm until a condition is met. + + ///Executes the algorithm until a condition is met. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///\param nm must be a bool (or convertible) node map. The algorithm + ///will stop when it reaches a node \c v with nm[v]==true. + template + void start(const NM &nm) + { + while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode(); + } + + ///Runs %BFS algorithm from node \c s. + + ///This method runs the %BFS algorithm from a root node \c s + ///in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node from the root. + /// + ///\note d.run(s) is just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(); + ///\endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + ///Finds the shortest path between \c s and \c t. + + ///Finds the shortest path between \c s and \c t. + /// + ///\return The length of the shortest s---t path if there exists one, + ///0 otherwise. + ///\note Apart from the return value, d.run(s) is + ///just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(t); + ///\endcode + int run(Node s,Node t) { + init(); + addSource(s); + start(t); + return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0; + } + + ///@} + + ///\name Query Functions + ///The result of the %BFS algorithm can be obtained using these + ///functions.\n + ///Before the use of these functions, + ///either run() or start() must be called. + + ///@{ + + ///The distance of a node from the root(s). + + ///Returns the distance of a node from the root(s). ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root the return value + ///\warning If node \c v in unreachable from the root(s) the return value ///of this funcion is undefined. - int dist(Node v) const { return (*distance)[v]; } + int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous edge' of the %BFS path tree. + ///Returns the 'previous edge' of the shortest path tree. - ///For a node \c v it returns the 'previous edge' of the %BFS tree, - ///i.e. it returns the last edge of a shortest path from the root to \c + ///For a node \c v it returns the 'previous edge' + ///of the shortest path tree, + ///i.e. it returns the last edge of a shortest path from the root(s) to \c ///v. It is \ref INVALID - ///if \c v is unreachable from the root or if \c v=s. The - ///%BFS tree used here is equal to the %BFS tree used in - ///\ref predNode(Node v). \pre \ref run() must be called before using + ///if \c v is unreachable from the root(s) or \c v is a root. The + ///shortest path tree used here is equal to the shortest path tree used in + ///\ref predNode(Node v). + ///\pre Either \ref run() or \ref start() must be called before using ///this function. - Edge pred(Node v) const { return (*predecessor)[v]; } + ///\todo predEdge could be a better name. + Edge pred(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the %BFS tree. + ///Returns the 'previous node' of the shortest path tree. - ///For a node \c v it returns the 'previous node' on the %BFS tree, + ///For a node \c v it returns the 'previous node' + ///of the shortest path tree, ///i.e. it returns the last but one node from a shortest path from the - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if - ///\c v=s. The shortest path tree used here is equal to the %BFS - ///tree used in \ref pred(Node v). \pre \ref run() must be called before + ///root(a) to \c /v. + ///It is INVALID if \c v is unreachable from the root(s) or + ///if \c v itself a root. + ///The shortest path tree used here is equal to the shortest path + ///tree used in \ref pred(Node v). + ///\pre Either \ref run() or \ref start() must be called before ///using this function. - Node predNode(Node v) const { return (*pred_node)[v]; } + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: + G->source((*_pred)[v]); } ///Returns a reference to the NodeMap of distances. - - ///Returns a reference to the NodeMap of distances. \pre \ref run() must + + ///Returns a reference to the NodeMap of distances. + ///\pre Either \ref run() or \ref init() must ///be called before using this function. - const DistMap &distMap() const { return *distance;} + const DistMap &distMap() const { return *_dist;} - ///Returns a reference to the %BFS tree map. + ///Returns a reference to the shortest path tree map. ///Returns a reference to the NodeMap of the edges of the - ///%BFS tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *predecessor;} + ///shortest path tree. + ///\pre Either \ref run() or \ref init() + ///must be called before using this function. + const PredMap &predMap() const { return *_pred;} - ///Returns a reference to the map of last but one nodes of shortest paths. +// ///Returns a reference to the map of nodes of shortest paths. - ///Returns a reference to the NodeMap of the last but one nodes on the - ///%BFS tree. - ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return *pred_node;} +// ///Returns a reference to the NodeMap of the last but one nodes of the +// ///shortest path tree. +// ///\pre \ref run() must be called before using this function. +// const PredNodeMap &predNodeMap() const { return *_predNode;} ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root. - ///\note The root node is reported to be reached! + ///\warning The source nodes are inditated as unreached. + ///\pre Either \ref run() or \ref start() + ///must be called before using this function. /// - ///\pre \ref run() must be called before using this function. + bool reached(Node v) { return (*_reached)[v]; } + + ///@} + }; + + ///Default traits class of Bfs function. + + ///Default traits class of Bfs function. + ///\param GR Graph type. + template + struct BfsWizardDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + /// + ///The type of the map that stores the last + ///edges of the shortest paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. /// - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } + typedef NullMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient to initialize + static PredMap *createPredMap(const GR &G) + { + return new PredMap(); + } +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// /// +// ///The type of the map that stores the last but one +// ///nodes of the shortest paths. +// ///It must meet the \ref concept::WriteMap "WriteMap" concept. +// /// +// typedef NullMap PredNodeMap; +// ///Instantiates a PredNodeMap. + +// ///This function instantiates a \ref PredNodeMap. +// ///\param G is the graph, to which +// ///we would like to define the \ref PredNodeMap +// static PredNodeMap *createPredNodeMap(const GR &G) +// { +// return new PredNodeMap(); +// } + + ///The type of the map that indicates which nodes are processed. + + ///The type of the map that indicates which nodes are processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &G) + { + return new ProcessedMap(); + } + ///The type of the map that indicates which nodes are reached. + + ///The type of the map that indicates which nodes are reached. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef typename Graph::template NodeMap ReachedMap; + ///Instantiates a ReachedMap. + + ///This function instantiates a \ref ReachedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ReachedMap. + static ReachedMap *createReachedMap(const GR &G) + { + return new ReachedMap(G); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NullMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &G) + { + return new DistMap(); + } + }; + + /// Default traits used by \ref BfsWizard + + /// To make it easier to use Bfs algorithm + ///we have created a wizard class. + /// This \ref BfsWizard class needs default traits, + ///as well as the \ref Bfs class. + /// The \ref BfsWizardBase is a class to be the default traits of the + /// \ref BfsWizard class. + template + class BfsWizardBase : public BfsWizardDefaultTraits + { + + typedef BfsWizardDefaultTraits Base; + protected: + /// Type of the nodes in the graph. + typedef typename Base::Graph::Node Node; + + /// Pointer to the underlying graph. + void *_g; + ///Pointer to the map of reached nodes. + void *_reached; + ///Pointer to the map of processed nodes. + void *_processed; + ///Pointer to the map of predecessors edges. + void *_pred; +// ///Pointer to the map of predecessors nodes. +// void *_predNode; + ///Pointer to the map of distances. + void *_dist; + ///Pointer to the source node. + Node _source; + + public: + /// Constructor. + + /// This constructor does not require parameters, therefore it initiates + /// all of the attributes to default values (0, INVALID). + BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), +// _predNode(0), + _dist(0), _source(INVALID) {} + + /// Constructor. + + /// This constructor requires some parameters, + /// listed in the parameters list. + /// Others are initiated to 0. + /// \param g is the initial value of \ref _g + /// \param s is the initial value of \ref _source + BfsWizardBase(const GR &g, Node s=INVALID) : + _g((void *)&g), _reached(0), _processed(0), _pred(0), +// _predNode(0), + _dist(0), _source(s) {} + + }; + + /// A class to make the usage of Bfs algorithm easier + + /// This class is created to make it easier to use Bfs algorithm. + /// It uses the functions and features of the plain \ref Bfs, + /// but it is much simpler to use it. + /// + /// Simplicity means that the way to change the types defined + /// in the traits class is based on functions that returns the new class + /// and not on templatable built-in classes. + /// When using the plain \ref Bfs + /// the new class with the modified type comes from + /// the original class by using the :: + /// operator. In the case of \ref BfsWizard only + /// a function have to be called and it will + /// return the needed class. + /// + /// It does not have own \ref run method. When its \ref run method is called + /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run + /// method of it. + template + class BfsWizard : public TR + { + typedef TR Base; + + ///The type of the underlying graph. + typedef typename TR::Graph Graph; + //\e + typedef typename Graph::Node Node; + //\e + typedef typename Graph::NodeIt NodeIt; + //\e + typedef typename Graph::Edge Edge; + //\e + typedef typename Graph::OutEdgeIt OutEdgeIt; + + ///\brief The type of the map that stores + ///the reached nodes + typedef typename TR::ReachedMap ReachedMap; + ///\brief The type of the map that stores + ///the processed nodes + typedef typename TR::ProcessedMap ProcessedMap; + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename TR::PredMap PredMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map that stores the dists of the nodes. + typedef typename TR::DistMap DistMap; + +public: + /// Constructor. + BfsWizard() : TR() {} + + /// Constructor that requires parameters. + + /// Constructor that requires parameters. + /// These parameters will be the default values for the traits class. + BfsWizard(const Graph &g, Node s=INVALID) : + TR(g,s) {} + + ///Copy constructor + BfsWizard(const TR &b) : TR(b) {} + + ~BfsWizard() {} + + ///Runs Bfs algorithm from a given node. + + ///Runs Bfs algorithm from a given node. + ///The node can be given by the \ref source function. + void run() + { + if(Base::_source==INVALID) throw UninitializedParameter(); + Bfs alg(*(Graph*)Base::_g); + if(Base::_reached) + alg.reachedMap(*(ReachedMap*)Base::_reached); + if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); + if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); +// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode); + if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); + alg.run(Base::_source); + } + + ///Runs Bfs algorithm from the given node. + + ///Runs Bfs algorithm from the given node. + ///\param s is the given source. + void run(Node s) + { + Base::_source=s; + run(); + } + + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Graph &G) { return 0; }; + DefPredMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting PredMap + /// + /// \ref named-templ-param "Named parameter" + ///function for setting PredMap + /// + template + BfsWizard > predMap(const T &t) + { + Base::_pred=(void *)&t; + return BfsWizard >(*this); + } + + + template + struct DefReachedMapBase : public Base { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) { return 0; }; + DefReachedMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting ReachedMap + /// + /// \ref named-templ-param "Named parameter" + ///function for setting ReachedMap + /// + template + BfsWizard > reachedMap(const T &t) + { + Base::_pred=(void *)&t; + return BfsWizard >(*this); + } + + + template + struct DefProcessedMapBase : public Base { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) { return 0; }; + DefProcessedMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting ProcessedMap + /// + /// \ref named-templ-param "Named parameter" + ///function for setting ProcessedMap + /// + template + BfsWizard > processedMap(const T &t) + { + Base::_pred=(void *)&t; + return BfsWizard >(*this); + } + + +// template +// struct DefPredNodeMapBase : public Base { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; +// DefPredNodeMapBase(const Base &b) : Base(b) {} +// }; + +// ///\brief \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// /// \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// template +// BfsWizard > predNodeMap(const T &t) +// { +// Base::_predNode=(void *)&t; +// return BfsWizard >(*this); +// } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Graph &G) { return 0; }; + DefDistMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + template + BfsWizard > distMap(const T &t) + { + Base::_dist=(void *)&t; + return BfsWizard >(*this); + } + + /// Sets the source node, from which the Bfs algorithm runs. + + /// Sets the source node, from which the Bfs algorithm runs. + /// \param s is the source node. + BfsWizard &source(Node s) + { + Base::_source=s; + return *this; + } }; -/// @} - + ///Function type interface for Bfs algorithm. + + /// \ingroup flowalgs + ///Function type interface for Bfs algorithm. + /// + ///This function also has several + ///\ref named-templ-func-param "named parameters", + ///they are declared as the members of class \ref BfsWizard. + ///The following + ///example shows how to use these parameters. + ///\code + /// bfs(g,source).predMap(preds).run(); + ///\endcode + ///\warning Don't forget to put the \ref BfsWizard::run() "run()" + ///to the end of the parameter list. + ///\sa BfsWizard + ///\sa Bfs + template + BfsWizard > + bfs(const GR &g,typename GR::Node s=INVALID) + { + return BfsWizard >(g,s); + } + } //END OF NAMESPACE LEMON #endif - diff -r 640ca1bd850f -r 5331168bbb18 src/lemon/dfs.h --- a/src/lemon/dfs.h Wed Mar 16 07:52:16 2005 +0000 +++ b/src/lemon/dfs.h Wed Mar 16 07:56:25 2005 +0000 @@ -19,35 +19,150 @@ ///\ingroup flowalgs ///\file -///\brief %DFS algorithm. -/// -///\todo Revise Manual. +///\brief Dfs algorithm. +#include #include #include +#include +#include namespace lemon { -/// \addtogroup flowalgs -/// @{ + + ///Default traits class of Dfs class. + + ///Default traits class of Dfs class. + ///\param GR Graph type. + template + struct DfsDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///\brief The type of the map that stores the last + ///edges of the %DFS paths. + /// + ///The type of the map that stores the last + ///edges of the %DFS paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient to initialize + static PredMap *createPredMap(const GR &G) + { + return new PredMap(G); + } +// ///\brief The type of the map that stores the last but one +// ///nodes of the %DFS paths. +// /// +// ///The type of the map that stores the last but one +// ///nodes of the %DFS paths. +// ///It must meet the \ref concept::WriteMap "WriteMap" concept. +// /// +// typedef NullMap PredNodeMap; +// ///Instantiates a PredNodeMap. + +// ///This function instantiates a \ref PredNodeMap. +// ///\param G is the graph, to which +// ///we would like to define the \ref PredNodeMap +// static PredNodeMap *createPredNodeMap(const GR &G) +// { +// return new PredNodeMap(); +// } + + ///The type of the map that indicates which nodes are processed. + + ///The type of the map that indicates which nodes are processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &G) + { + return new ProcessedMap(); + } + ///The type of the map that indicates which nodes are reached. + + ///The type of the map that indicates which nodes are reached. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef typename Graph::template NodeMap ReachedMap; + ///Instantiates a ReachedMap. + + ///This function instantiates a \ref ReachedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ReachedMap. + static ReachedMap *createReachedMap(const GR &G) + { + return new ReachedMap(G); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef typename Graph::template NodeMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &G) + { + return new DistMap(G); + } + }; + ///%DFS algorithm class. - - ///This class provides an efficient implementation of %DFS algorithm. + + ///\ingroup flowalgs + ///This class provides an efficient implementation of the %DFS algorithm. /// - ///\param GR The graph type the algorithm runs on. + ///\param GR The graph type the algorithm runs on. The default value is + ///\ref ListGraph. The value of GR is not used directly by Dfs, it + ///is only passed to \ref DfsDefaultTraits. + ///\param TR Traits class to set various data types used by the algorithm. + ///The default traits class is + ///\ref DfsDefaultTraits "DfsDefaultTraits". + ///See \ref DfsDefaultTraits for the documentation of + ///a Dfs traits class. /// - ///\author Alpar Juttner + ///\author Jacint Szabo and Alpar Juttner + ///\todo A compare object would be nice. #ifdef DOXYGEN - template + template #else - template + template > #endif - class Dfs{ + class Dfs { public: + /** + * \brief \ref Exception for uninitialized parameters. + * + * This error represents problems in the initialization + * of the parameters of the algorithms. + */ + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::Dfs::UninitializedParameter"; + } + }; + + typedef TR Traits; ///The type of the underlying graph. - typedef GR Graph; + typedef typename TR::Graph Graph; ///\e typedef typename Graph::Node Node; ///\e @@ -58,69 +173,211 @@ typedef typename Graph::OutEdgeIt OutEdgeIt; ///\brief The type of the map that stores the last - ///edges of the paths on the %DFS tree. - typedef typename Graph::template NodeMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the paths on the %DFS tree. - typedef typename Graph::template NodeMap PredNodeMap; - ///The type of the map that stores the dists of the nodes on the %DFS tree. - typedef typename Graph::template NodeMap DistMap; - + ///edges of the %DFS paths. + typedef typename TR::PredMap PredMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the %DFS paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map indicating which nodes are reached. + typedef typename TR::ReachedMap ReachedMap; + ///The type of the map indicating which nodes are processed. + typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the map that stores the dists of the nodes. + typedef typename TR::DistMap DistMap; private: /// Pointer to the underlying graph. const Graph *G; ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; + PredMap *_pred; + ///Indicates if \ref _pred is locally allocated (\c true) or not. + bool local_pred; +// ///Pointer to the map of predecessors nodes. +// PredNodeMap *_predNode; +// ///Indicates if \ref _predNode is locally allocated (\c true) or not. +// bool local_predNode; ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; + DistMap *_dist; + ///Indicates if \ref _dist is locally allocated (\c true) or not. + bool local_dist; + ///Pointer to the map of reached status of the nodes. + ReachedMap *_reached; + ///Indicates if \ref _reached is locally allocated (\c true) or not. + bool local_reached; + ///Pointer to the map of processed status of the nodes. + ProcessedMap *_processed; + ///Indicates if \ref _processed is locally allocated (\c true) or not. + bool local_processed; - ///The source node of the last execution. - Node source; + std::vector _stack; + int _stack_head; +// ///The source node of the last execution. +// Node source; - - ///Initializes the maps. - void init_maps() + ///Creates the maps if necessary. + + ///\todo Error if \c G are \c NULL. + ///\todo Better memory allocation (instead of new). + void create_maps() { - if(!predecessor) { - local_predecessor = true; - predecessor = new PredMap(*G); + if(!_pred) { + local_pred = true; + _pred = Traits::createPredMap(*G); } - if(!pred_node) { - local_pred_node = true; - pred_node = new PredNodeMap(*G); +// if(!_predNode) { +// local_predNode = true; +// _predNode = Traits::createPredNodeMap(*G); +// } + if(!_dist) { + local_dist = true; + _dist = Traits::createDistMap(*G); } - if(!distance) { - local_distance = true; - distance = new DistMap(*G); + if(!_reached) { + local_reached = true; + _reached = Traits::createReachedMap(*G); + } + if(!_processed) { + local_processed = true; + _processed = Traits::createProcessedMap(*G); } } - public : + public : + + ///\name Named template parameters + + ///@{ + + template + struct DefPredMapTraits : public Traits { + typedef T PredMap; + static PredMap *createPredMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting PredMap type + + ///\ref named-templ-param "Named parameter" for setting PredMap type + /// + template + class DefPredMap : public Dfs< Graph, + DefPredMapTraits > { }; + +// template +// struct DefPredNodeMapTraits : public Traits { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) +// { +// throw UninitializedParameter(); +// } +// }; +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type + +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type +// /// +// template +// class DefPredNodeMap : public Dfs< Graph, +// LengthMap, +// DefPredNodeMapTraits > { }; + + template + struct DefDistMapTraits : public Traits { + typedef T DistMap; + static DistMap *createDistMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting DistMap type + + ///\ref named-templ-param "Named parameter" for setting DistMap type + /// + template + class DefDistMap : public Dfs< Graph, + DefDistMapTraits > { }; + + template + struct DefReachedMapTraits : public Traits { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + + ///\ref named-templ-param "Named parameter" for setting ReachedMap type + /// + template + class DefReachedMap : public Dfs< Graph, + DefReachedMapTraits > { }; + + struct DefGraphReachedMapTraits : public Traits { + typedef typename Graph::template NodeMap ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) + { + return new ReachedMap(G); + } + }; + template + struct DefProcessedMapTraits : public Traits { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) + { + throw UninitializedParameter(); + } + }; + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type + /// + template + class DefProcessedMap : public Dfs< Graph, + DefProcessedMapTraits > { }; + + struct DefGraphProcessedMapTraits : public Traits { + typedef typename Graph::template NodeMap ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) + { + return new ProcessedMap(G); + } + }; + ///\brief \ref named-templ-param "Named parameter" + ///for setting the ProcessedMap type to be Graph::NodeMap. + /// + ///\ref named-templ-param "Named parameter" + ///for setting the ProcessedMap type to be Graph::NodeMap. + ///If you don't set it explicitely, it will be automatically allocated. + template + class DefProcessedMapToBeDefaultMap : + public Dfs< Graph, + DefGraphProcessedMapTraits> { }; + + ///@} + + public: + ///Constructor. ///\param _G the graph the algorithm will run on. /// Dfs(const Graph& _G) : G(&_G), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) + _pred(NULL), local_pred(false), +// _predNode(NULL), local_predNode(false), + _dist(NULL), local_dist(false), + _reached(NULL), local_reached(false), + _processed(NULL), local_processed(false) { } ///Destructor. ~Dfs() { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; + if(local_pred) delete _pred; +// if(local_predNode) delete _predNode; + if(local_dist) delete _dist; + if(local_reached) delete _reached; + if(local_processed) delete _processed; } ///Sets the map storing the predecessor edges. @@ -130,32 +387,32 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Dfs &setPredMap(PredMap &m) + Dfs &predMap(PredMap &m) { - if(local_predecessor) { - delete predecessor; - local_predecessor=false; + if(local_pred) { + delete _pred; + local_pred=false; } - predecessor = &m; + _pred = &m; return *this; } - ///Sets the map storing the predecessor nodes. +// ///Sets the map storing the predecessor nodes. - ///Sets the map storing the predecessor nodes. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dfs &setPredNodeMap(PredNodeMap &m) - { - if(local_pred_node) { - delete pred_node; - local_pred_node=false; - } - pred_node = &m; - return *this; - } +// ///Sets the map storing the predecessor nodes. +// ///If you don't use this function before calling \ref run(), +// ///it will allocate one. The destuctor deallocates this +// ///automatically allocated map, of course. +// ///\return (*this) +// Dfs &predNodeMap(PredNodeMap &m) +// { +// if(local_predNode) { +// delete _predNode; +// local_predNode=false; +// } +// _predNode = &m; +// return *this; +// } ///Sets the map storing the distances calculated by the algorithm. @@ -164,127 +421,655 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Dfs &setDistMap(DistMap &m) + Dfs &distMap(DistMap &m) { - if(local_distance) { - delete distance; - local_distance=false; + if(local_dist) { + delete _dist; + local_dist=false; } - distance = &m; + _dist = &m; return *this; } - - ///Runs %DFS algorithm from node \c s. - ///This method runs the %DFS algorithm from a root node \c s - ///in order to - ///compute - ///- a %DFS tree and - ///- the distance of each node from the root on this tree. - - void run(Node s) { - - init_maps(); - - source = s; - + public: + ///\name Execution control + ///The simplest way to execute the algorithm is to use + ///one of the member functions called \c run(...). + ///\n + ///If you need more control on the execution, + ///first you must call \ref init(), then you can add several source nodes + ///with \ref addSource(). + ///Finally \ref start() will perform the actual path + ///computation. + + ///@{ + + ///Initializes the internal data structures. + + ///Initializes the internal data structures. + /// + void init() + { + create_maps(); + _stack.resize(countNodes(*G)); + _stack_head=-1; for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - predecessor->set(u,INVALID); - pred_node->set(u,INVALID); + _pred->set(u,INVALID); + // _predNode->set(u,INVALID); + _reached->set(u,false); + _processed->set(u,false); } - - int N = countNodes(*G); - std::vector Q(N); - - int Qh=0; - - Q[Qh] = OutEdgeIt(*G, s); - distance->set(s, 0); - - Node n=s; - Node m; - OutEdgeIt e; - do { - if((e=Q[Qh])!=INVALID) - if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) { - predecessor->set(m,e); - pred_node->set(m,n); - Q[++Qh] = OutEdgeIt(*G, m); - distance->set(m,Qh); - n=m; - } - else ++Q[Qh]; - else if(--Qh>=0) n=G->source(Q[Qh]); - } while(Qh>=0); } - ///The distance of a node from the root on the %DFS tree. + ///Adds a new source node. - ///Returns the distance of a node from the root on the %DFS tree. + ///Adds a new source node to the set of nodes to be processed. + /// + ///\bug dist's are wrong (or at least strange) in case of multiple sources. + void addSource(Node s) + { + if(!(*_reached)[s]) + { + _reached->set(s,true); + _pred->set(s,INVALID); + // _predNode->set(u,INVALID); + _stack[++_stack_head]=OutEdgeIt(*G,s); + _dist->set(s,_stack_head); + } + } + + ///Processes the next node. + + ///Processes the next node. + /// + ///\warning The stack must not be empty! + void processNextEdge() + { + Node m; + Edge e=_stack[_stack_head]; + if(!(*_reached)[m=G->target(e)]) { + _pred->set(m,e); + _reached->set(m,true); + // _pred_node->set(m,G->source(e)); + _stack[++_stack_head] = OutEdgeIt(*G, m); + _dist->set(m,_stack_head); + } + else { + Node n; + while(_stack_head>=0 && + (n=G->source(_stack[_stack_head]), + ++_stack[_stack_head]==INVALID)) + { + _processed->set(n,true); + --_stack_head; + } + } + } + + ///\brief Returns \c false if there are nodes + ///to be processed in the queue + /// + ///Returns \c false if there are nodes + ///to be processed in the queue + bool emptyQueue() { return _stack_head<0; } + ///Returns the number of the nodes to be processed. + + ///Returns the number of the nodes to be processed in the queue. + /// + int queueSize() { return _stack_head+1; } + + ///Executes the algorithm. + + ///Executes the algorithm. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %DFS algorithm from the root node(s) + ///in order to + ///compute the + ///%DFS path to each node. The algorithm computes + ///- The %DFS tree. + ///- The distance of each node from the root(s). + /// + void start() + { + while ( !emptyQueue() ) processNextEdge(); + } + + ///Executes the algorithm until \c dest is reached. + + ///Executes the algorithm until \c dest is reached. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///This method runs the %DFS algorithm from the root node(s) + ///in order to + ///compute the + ///%DFS path to \c dest. The algorithm computes + ///- The %DFS path to \c dest. + ///- The distance of \c dest from the root(s). + /// + void start(Node dest) + { + while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge(); + } + + ///Executes the algorithm until a condition is met. + + ///Executes the algorithm until a condition is met. + /// + ///\pre init() must be called and at least one node should be added + ///with addSource() before using this function. + /// + ///\param nm must be a bool (or convertible) node map. The algorithm + ///will stop when it reaches a node \c v with nm[v]==true. + template + void start(const NM &nm) + { + while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge(); + } + + ///Runs %DFS algorithm from node \c s. + + ///This method runs the %DFS algorithm from a root node \c s + ///in order to + ///compute the + ///%DFS path to each node. The algorithm computes + ///- The %DFS tree. + ///- The distance of each node from the root. + /// + ///\note d.run(s) is just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(); + ///\endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + + ///Finds the %DFS path between \c s and \c t. + + ///Finds the %DFS path between \c s and \c t. + /// + ///\return The length of the %DFS s---t path if there exists one, + ///0 otherwise. + ///\note Apart from the return value, d.run(s) is + ///just a shortcut of the following code. + ///\code + /// d.init(); + /// d.addSource(s); + /// d.start(t); + ///\endcode + int run(Node s,Node t) { + init(); + addSource(s); + start(t); + return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0; + } + + ///@} + + ///\name Query Functions + ///The result of the %DFS algorithm can be obtained using these + ///functions.\n + ///Before the use of these functions, + ///either run() or start() must be called. + + ///@{ + + ///The distance of a node from the root(s). + + ///Returns the distance of a node from the root(s). ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the root the return value + ///\warning If node \c v in unreachable from the root(s) the return value ///of this funcion is undefined. - int dist(Node v) const { return (*distance)[v]; } + int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous edge' of the %DFS path tree. + ///Returns the 'previous edge' of the %DFS tree. - ///For a node \c v it returns the last edge of the path on the %DFS tree - ///from the root to \c + ///For a node \c v it returns the 'previous edge' + ///of the %DFS path, + ///i.e. it returns the last edge of a %DFS path from the root(s) to \c ///v. It is \ref INVALID - ///if \c v is unreachable from the root or if \c v=s. The + ///if \c v is unreachable from the root(s) or \c v is a root. The ///%DFS tree used here is equal to the %DFS tree used in - ///\ref predNode(Node v). \pre \ref run() must be called before using + ///\ref predNode(Node v). + ///\pre Either \ref run() or \ref start() must be called before using ///this function. - Edge pred(Node v) const { return (*predecessor)[v]; } + ///\todo predEdge could be a better name. + Edge pred(Node v) const { return (*_pred)[v];} ///Returns the 'previous node' of the %DFS tree. - ///For a node \c v it returns the 'previous node' on the %DFS tree, - ///i.e. it returns the last but one node of the path from the - ///root to \c /v on the %DFS tree. - ///It is INVALID if \c v is unreachable from the root or if - ///\c v=s. - ///\pre \ref run() must be called before + ///For a node \c v it returns the 'previous node' + ///of the %DFS tree, + ///i.e. it returns the last but one node from a %DFS path from the + ///root(a) to \c /v. + ///It is INVALID if \c v is unreachable from the root(s) or + ///if \c v itself a root. + ///The %DFS tree used here is equal to the %DFS + ///tree used in \ref pred(Node v). + ///\pre Either \ref run() or \ref start() must be called before ///using this function. - Node predNode(Node v) const { return (*pred_node)[v]; } + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: + G->source((*_pred)[v]); } - ///Returns a reference to the NodeMap of distances on the %DFS tree. - - ///Returns a reference to the NodeMap of distances on the %DFS tree. - ///\pre \ref run() must + ///Returns a reference to the NodeMap of distances. + + ///Returns a reference to the NodeMap of distances. + ///\pre Either \ref run() or \ref init() must ///be called before using this function. - const DistMap &distMap() const { return *distance;} + const DistMap &distMap() const { return *_dist;} - ///Returns a reference to the %DFS tree map. + ///Returns a reference to the %DFS edge-tree map. ///Returns a reference to the NodeMap of the edges of the ///%DFS tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *predecessor;} + ///\pre Either \ref run() or \ref init() + ///must be called before using this function. + const PredMap &predMap() const { return *_pred;} - ///Returns a reference to the map of last but one nodes of the %DFS tree. +// ///Returns a reference to the map of nodes of %DFS paths. - ///Returns a reference to the NodeMap of the last but one nodes of the paths - ///on the - ///%DFS tree. - ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return *pred_node;} +// ///Returns a reference to the NodeMap of the last but one nodes of the +// ///%DFS tree. +// ///\pre \ref run() must be called before using this function. +// const PredNodeMap &predNodeMap() const { return *_predNode;} ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root. - ///\note The root node is reported to be reached! + ///\warning The source nodes are inditated as unreached. + ///\pre Either \ref run() or \ref start() + ///must be called before using this function. /// - ///\pre \ref run() must be called before using this function. + bool reached(Node v) { return (*_reached)[v]; } + + ///@} + }; + + ///Default traits class of Dfs function. + + ///Default traits class of Dfs function. + ///\param GR Graph type. + template + struct DfsWizardDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///\brief The type of the map that stores the last + ///edges of the %DFS paths. + /// + ///The type of the map that stores the last + ///edges of the %DFS paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. /// - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } + typedef NullMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient to initialize + static PredMap *createPredMap(const GR &G) + { + return new PredMap(); + } +// ///\brief The type of the map that stores the last but one +// ///nodes of the %DFS paths. +// /// +// ///The type of the map that stores the last but one +// ///nodes of the %DFS paths. +// ///It must meet the \ref concept::WriteMap "WriteMap" concept. +// /// +// typedef NullMap PredNodeMap; +// ///Instantiates a PredNodeMap. + +// ///This function instantiates a \ref PredNodeMap. +// ///\param G is the graph, to which +// ///we would like to define the \ref PredNodeMap +// static PredNodeMap *createPredNodeMap(const GR &G) +// { +// return new PredNodeMap(); +// } + + ///The type of the map that indicates which nodes are processed. + + ///The type of the map that indicates which nodes are processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &G) + { + return new ProcessedMap(); + } + ///The type of the map that indicates which nodes are reached. + + ///The type of the map that indicates which nodes are reached. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///\todo named parameter to set this type, function to read and write. + typedef typename Graph::template NodeMap ReachedMap; + ///Instantiates a ReachedMap. + + ///This function instantiates a \ref ReachedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ReachedMap. + static ReachedMap *createReachedMap(const GR &G) + { + return new ReachedMap(G); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NullMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &G) + { + return new DistMap(); + } + }; + + /// Default traits used by \ref DfsWizard + + /// To make it easier to use Dfs algorithm + ///we have created a wizard class. + /// This \ref DfsWizard class needs default traits, + ///as well as the \ref Dfs class. + /// The \ref DfsWizardBase is a class to be the default traits of the + /// \ref DfsWizard class. + template + class DfsWizardBase : public DfsWizardDefaultTraits + { + + typedef DfsWizardDefaultTraits Base; + protected: + /// Type of the nodes in the graph. + typedef typename Base::Graph::Node Node; + + /// Pointer to the underlying graph. + void *_g; + ///Pointer to the map of reached nodes. + void *_reached; + ///Pointer to the map of processed nodes. + void *_processed; + ///Pointer to the map of predecessors edges. + void *_pred; +// ///Pointer to the map of predecessors nodes. +// void *_predNode; + ///Pointer to the map of distances. + void *_dist; + ///Pointer to the source node. + Node _source; + + public: + /// Constructor. + + /// This constructor does not require parameters, therefore it initiates + /// all of the attributes to default values (0, INVALID). + DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), +// _predNode(0), + _dist(0), _source(INVALID) {} + + /// Constructor. + + /// This constructor requires some parameters, + /// listed in the parameters list. + /// Others are initiated to 0. + /// \param g is the initial value of \ref _g + /// \param s is the initial value of \ref _source + DfsWizardBase(const GR &g, Node s=INVALID) : + _g((void *)&g), _reached(0), _processed(0), _pred(0), +// _predNode(0), + _dist(0), _source(s) {} + + }; + + /// A class to make the usage of Dfs algorithm easier + + /// This class is created to make it easier to use Dfs algorithm. + /// It uses the functions and features of the plain \ref Dfs, + /// but it is much simpler to use it. + /// + /// Simplicity means that the way to change the types defined + /// in the traits class is based on functions that returns the new class + /// and not on templatable built-in classes. + /// When using the plain \ref Dfs + /// the new class with the modified type comes from + /// the original class by using the :: + /// operator. In the case of \ref DfsWizard only + /// a function have to be called and it will + /// return the needed class. + /// + /// It does not have own \ref run method. When its \ref run method is called + /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run + /// method of it. + template + class DfsWizard : public TR + { + typedef TR Base; + + ///The type of the underlying graph. + typedef typename TR::Graph Graph; + //\e + typedef typename Graph::Node Node; + //\e + typedef typename Graph::NodeIt NodeIt; + //\e + typedef typename Graph::Edge Edge; + //\e + typedef typename Graph::OutEdgeIt OutEdgeIt; + + ///\brief The type of the map that stores + ///the reached nodes + typedef typename TR::ReachedMap ReachedMap; + ///\brief The type of the map that stores + ///the processed nodes + typedef typename TR::ProcessedMap ProcessedMap; + ///\brief The type of the map that stores the last + ///edges of the %DFS paths. + typedef typename TR::PredMap PredMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the %DFS paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map that stores the dists of the nodes. + typedef typename TR::DistMap DistMap; + +public: + /// Constructor. + DfsWizard() : TR() {} + + /// Constructor that requires parameters. + + /// Constructor that requires parameters. + /// These parameters will be the default values for the traits class. + DfsWizard(const Graph &g, Node s=INVALID) : + TR(g,s) {} + + ///Copy constructor + DfsWizard(const TR &b) : TR(b) {} + + ~DfsWizard() {} + + ///Runs Dfs algorithm from a given node. + + ///Runs Dfs algorithm from a given node. + ///The node can be given by the \ref source function. + void run() + { + if(Base::_source==INVALID) throw UninitializedParameter(); + Dfs alg(*(Graph*)Base::_g); + if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached); + if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); + if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); +// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode); + if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); + alg.run(Base::_source); + } + + ///Runs Dfs algorithm from the given node. + + ///Runs Dfs algorithm from the given node. + ///\param s is the given source. + void run(Node s) + { + Base::_source=s; + run(); + } + + template + struct DefPredMapBase : public Base { + typedef T PredMap; + static PredMap *createPredMap(const Graph &G) { return 0; }; + DefPredMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting PredMap type + /// + template + DfsWizard > predMap(const T &t) + { + Base::_pred=(void *)&t; + return DfsWizard >(*this); + } + + + template + struct DefReachedMapBase : public Base { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &G) { return 0; }; + DefReachedMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting ReachedMap + /// + /// \ref named-templ-param "Named parameter" + ///function for setting ReachedMap + /// + template + DfsWizard > reachedMap(const T &t) + { + Base::_pred=(void *)&t; + return DfsWizard >(*this); + } + + + template + struct DefProcessedMapBase : public Base { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) { return 0; }; + DefProcessedMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting ProcessedMap + /// + /// \ref named-templ-param "Named parameter" + ///function for setting ProcessedMap + /// + template + DfsWizard > processedMap(const T &t) + { + Base::_pred=(void *)&t; + return DfsWizard >(*this); + } + + +// template +// struct DefPredNodeMapBase : public Base { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; +// DefPredNodeMapBase(const Base &b) : Base(b) {} +// }; + +// ///\brief \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// /// \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// template +// DfsWizard > predNodeMap(const T &t) +// { +// Base::_predNode=(void *)&t; +// return DfsWizard >(*this); +// } + + template + struct DefDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Graph &G) { return 0; }; + DefDistMapBase(const Base &b) : Base(b) {} + }; + + ///\brief \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + /// \ref named-templ-param "Named parameter" + ///function for setting DistMap type + /// + template + DfsWizard > distMap(const T &t) + { + Base::_dist=(void *)&t; + return DfsWizard >(*this); + } + + /// Sets the source node, from which the Dfs algorithm runs. + + /// Sets the source node, from which the Dfs algorithm runs. + /// \param s is the source node. + DfsWizard &source(Node s) + { + Base::_source=s; + return *this; + } }; -/// @} - + ///Function type interface for Dfs algorithm. + + /// \ingroup flowalgs + ///Function type interface for Dfs algorithm. + /// + ///This function also has several + ///\ref named-templ-func-param "named parameters", + ///they are declared as the members of class \ref DfsWizard. + ///The following + ///example shows how to use these parameters. + ///\code + /// dfs(g,source).predMap(preds).run(); + ///\endcode + ///\warning Don't forget to put the \ref DfsWizard::run() "run()" + ///to the end of the parameter list. + ///\sa DfsWizard + ///\sa Dfs + template + DfsWizard > + dfs(const GR &g,typename GR::Node s=INVALID) + { + return DfsWizard >(g,s); + } + } //END OF NAMESPACE LEMON #endif - diff -r 640ca1bd850f -r 5331168bbb18 src/lemon/dijkstra.h --- a/src/lemon/dijkstra.h Wed Mar 16 07:52:16 2005 +0000 +++ b/src/lemon/dijkstra.h Wed Mar 16 07:56:25 2005 +0000 @@ -76,40 +76,41 @@ { return new PredMap(G); } - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - /// - ///The type of the map that stores the last but one - ///nodes of the shortest paths. - ///It must meet the \ref concept::WriteMap "WriteMap" concept. - /// - typedef NullMap PredNodeMap; - ///Instantiates a PredNodeMap. +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// /// +// ///The type of the map that stores the last but one +// ///nodes of the shortest paths. +// ///It must meet the \ref concept::WriteMap "WriteMap" concept. +// /// +// typedef NullMap PredNodeMap; +// ///Instantiates a PredNodeMap. - ///This function instantiates a \ref PredNodeMap. - ///\param G is the graph, to which - ///we would like to define the \ref PredNodeMap - static PredNodeMap *createPredNodeMap(const GR &G) - { - return new PredNodeMap(); - } +// ///This function instantiates a \ref PredNodeMap. +// ///\param G is the graph, to which +// ///we would like to define the \ref PredNodeMap +// static PredNodeMap *createPredNodeMap(const GR &G) +// { +// return new PredNodeMap(); +// } - ///The type of the map that stores whether a nodes is reached. + ///The type of the map that stores whether a nodes is processed. - ///The type of the map that stores whether a nodes is reached. + ///The type of the map that stores whether a nodes is processed. ///It must meet the \ref concept::WriteMap "WriteMap" concept. ///By default it is a NullMap. - ///\todo If it is set to a real map, Dijkstra::reached() should read this. + ///\todo If it is set to a real map, + ///Dijkstra::processed() should read this. ///\todo named parameter to set this type, function to read and write. - typedef NullMap ReachedMap; - ///Instantiates a ReachedMap. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. - ///This function instantiates a \ref ReachedMap. + ///This function instantiates a \ref ProcessedMap. ///\param G is the graph, to which - ///we would like to define the \ref ReachedMap - static ReachedMap *createReachedMap(const GR &G) + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &G) { - return new ReachedMap(); + return new ProcessedMap(); } ///The type of the map that stores the dists of the nodes. @@ -140,23 +141,21 @@ /// ///It is also possible to change the underlying priority heap. /// - ///\param GR The graph type the algorithm runs on. The default value is - ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it - ///is only passed to \ref DijkstraDefaultTraits. - ///\param LM This read-only - ///EdgeMap - ///determines the - ///lengths of the edges. It is read once for each edge, so the map - ///may involve in relatively time consuming process to compute the edge - ///length if it is necessary. The default map type is - ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap". - ///The value of LM is not used directly by Dijkstra, it - ///is only passed to \ref DijkstraDefaultTraits. - ///\param TR Traits class to set various data types used by the algorithm. - ///The default traits class is - ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits". - ///See \ref DijkstraDefaultTraits for the documentation of - ///a Dijkstra traits class. + ///\param GR The graph type the algorithm runs on. The default value + ///is \ref ListGraph. The value of GR is not used directly by + ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. + ///\param LM This read-only EdgeMap determines the lengths of the + ///edges. It is read once for each edge, so the map may involve in + ///relatively time consuming process to compute the edge length if + ///it is necessary. The default map type is \ref + ///concept::StaticGraph::EdgeMap "Graph::EdgeMap". The value + ///of LM is not used directly by Dijkstra, it is only passed to \ref + ///DijkstraDefaultTraits. \param TR Traits class to set + ///various data types used by the algorithm. The default traits + ///class is \ref DijkstraDefaultTraits + ///"DijkstraDefaultTraits". See \ref + ///DijkstraDefaultTraits for the documentation of a Dijkstra traits + ///class. /// ///\author Jacint Szabo and Alpar Juttner ///\todo A compare object would be nice. @@ -181,7 +180,7 @@ class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* exceptionName() const { - return "lemon::Dijsktra::UninitializedParameter"; + return "lemon::Dijkstra::UninitializedParameter"; } }; @@ -204,11 +203,11 @@ ///\brief The type of the map that stores the last ///edges of the shortest paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - typedef typename TR::PredNodeMap PredNodeMap; - ///The type of the map indicating if a node is reached. - typedef typename TR::ReachedMap ReachedMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// typedef typename TR::PredNodeMap PredNodeMap; + ///The type of the map indicating if a node is processed. + typedef typename TR::ProcessedMap ProcessedMap; ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; ///The heap type used by the dijkstra algorithm. @@ -222,21 +221,21 @@ PredMap *_pred; ///Indicates if \ref _pred is locally allocated (\c true) or not. bool local_pred; - ///Pointer to the map of predecessors nodes. - PredNodeMap *_predNode; - ///Indicates if \ref _predNode is locally allocated (\c true) or not. - bool local_predNode; +// ///Pointer to the map of predecessors nodes. +// PredNodeMap *_predNode; +// ///Indicates if \ref _predNode is locally allocated (\c true) or not. +// bool local_predNode; ///Pointer to the map of distances. DistMap *_dist; ///Indicates if \ref _dist is locally allocated (\c true) or not. bool local_dist; - ///Pointer to the map of reached status of the nodes. - ReachedMap *_reached; - ///Indicates if \ref _reached is locally allocated (\c true) or not. - bool local_reached; + ///Pointer to the map of processed status of the nodes. + ProcessedMap *_processed; + ///Indicates if \ref _processed is locally allocated (\c true) or not. + bool local_processed; - ///The source node of the last execution. - Node source; +// ///The source node of the last execution. +// Node source; ///Creates the maps if necessary. @@ -248,17 +247,17 @@ local_pred = true; _pred = Traits::createPredMap(*G); } - if(!_predNode) { - local_predNode = true; - _predNode = Traits::createPredNodeMap(*G); - } +// if(!_predNode) { +// local_predNode = true; +// _predNode = Traits::createPredNodeMap(*G); +// } if(!_dist) { local_dist = true; _dist = Traits::createDistMap(*G); } - if(!_reached) { - local_reached = true; - _reached = Traits::createReachedMap(*G); + if(!_processed) { + local_processed = true; + _processed = Traits::createProcessedMap(*G); } } @@ -285,22 +284,22 @@ LengthMap, DefPredMapTraits > { }; - template - struct DefPredNodeMapTraits : public Traits { - typedef T PredNodeMap; - static PredNodeMap *createPredNodeMap(const Graph &G) - { - throw UninitializedParameter(); - } - }; - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type +// template +// struct DefPredNodeMapTraits : public Traits { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) +// { +// throw UninitializedParameter(); +// } +// }; +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type - /// - template - class DefPredNodeMap : public Dijkstra< Graph, - LengthMap, - DefPredNodeMapTraits > { }; +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type +// /// +// template +// class DefPredNodeMap : public Dijkstra< Graph, +// LengthMap, +// DefPredNodeMapTraits > { }; template struct DefDistMapTraits : public Traits { @@ -320,40 +319,40 @@ DefDistMapTraits > { }; template - struct DefReachedMapTraits : public Traits { - typedef T ReachedMap; - static ReachedMap *createReachedMap(const Graph &G) + struct DefProcessedMapTraits : public Traits { + typedef T ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) { throw UninitializedParameter(); } }; - ///\ref named-templ-param "Named parameter" for setting ReachedMap type + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type - ///\ref named-templ-param "Named parameter" for setting ReachedMap type + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type /// template - class DefReachedMap : public Dijkstra< Graph, + class DefProcessedMap : public Dijkstra< Graph, LengthMap, - DefReachedMapTraits > { }; + DefProcessedMapTraits > { }; - struct DefGraphReachedMapTraits : public Traits { - typedef typename Graph::template NodeMap ReachedMap; - static ReachedMap *createReachedMap(const Graph &G) + struct DefGraphProcessedMapTraits : public Traits { + typedef typename Graph::template NodeMap ProcessedMap; + static ProcessedMap *createProcessedMap(const Graph &G) { - return new ReachedMap(G); + return new ProcessedMap(G); } }; ///\brief \ref named-templ-param "Named parameter" - ///for setting the ReachedMap type to be Graph::NodeMap. + ///for setting the ProcessedMap type to be Graph::NodeMap. /// ///\ref named-templ-param "Named parameter" - ///for setting the ReachedMap type to be Graph::NodeMap. + ///for setting the ProcessedMap type to be Graph::NodeMap. ///If you don't set it explicitely, it will be automatically allocated. template - class DefReachedMapToBeDefaultMap : + class DefProcessedMapToBeDefaultMap : public Dijkstra< Graph, LengthMap, - DefGraphReachedMapTraits> { }; + DefGraphProcessedMapTraits> { }; ///@} @@ -370,9 +369,9 @@ Dijkstra(const Graph& _G, const LengthMap& _length) : G(&_G), length(&_length), _pred(NULL), local_pred(false), - _predNode(NULL), local_predNode(false), +// _predNode(NULL), local_predNode(false), _dist(NULL), local_dist(false), - _reached(NULL), local_reached(false), + _processed(NULL), local_processed(false), _heap_map(*G,-1),_heap(_heap_map) { } @@ -380,9 +379,9 @@ ~Dijkstra() { if(local_pred) delete _pred; - if(local_predNode) delete _predNode; +// if(local_predNode) delete _predNode; if(local_dist) delete _dist; - if(local_reached) delete _reached; + if(local_processed) delete _processed; } ///Sets the length map. @@ -412,22 +411,22 @@ return *this; } - ///Sets the map storing the predecessor nodes. +// ///Sets the map storing the predecessor nodes. - ///Sets the map storing the predecessor nodes. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destuctor deallocates this - ///automatically allocated map, of course. - ///\return (*this) - Dijkstra &predNodeMap(PredNodeMap &m) - { - if(local_predNode) { - delete _predNode; - local_predNode=false; - } - _predNode = &m; - return *this; - } +// ///Sets the map storing the predecessor nodes. +// ///If you don't use this function before calling \ref run(), +// ///it will allocate one. The destuctor deallocates this +// ///automatically allocated map, of course. +// ///\return (*this) +// Dijkstra &predNodeMap(PredNodeMap &m) +// { +// if(local_predNode) { +// delete _predNode; +// local_predNode=false; +// } +// _predNode = &m; +// return *this; +// } ///Sets the map storing the distances calculated by the algorithm. @@ -449,19 +448,21 @@ private: void finalizeNodeData(Node v,Value dst) { - _reached->set(v,true); + _processed->set(v,true); _dist->set(v, dst); - if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do? +// if((*_pred)[v]!=INVALID) +// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do? } public: - ///\name Excetution control + ///\name Execution control ///The simplest way to execute the algorithm is to use ///one of the member functions called \c run(...). ///\n - ///It you need more control on the execution, + ///If you need more control on the execution, ///first you must call \ref init(), then you can add several source nodes - ///with \ref addSource(). Finally \ref start() will perform the actual path + ///with \ref addSource(). + ///Finally \ref start() will perform the actual path ///computation. ///@{ @@ -477,8 +478,8 @@ for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); - _predNode->set(u,INVALID); - ///\todo *_reached is not set to false. +// _predNode->set(u,INVALID); + _processed->set(u,false); _heap_map.set(u,Heap::PRE_HEAP); } } @@ -494,7 +495,7 @@ ///or the shortest path found till then is longer then \c dst. void addSource(Node s,Value dst=0) { - source = s; +// source = s; if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); else if(_heap[s] + struct DijkstraWizardDefaultTraits + { + ///The graph type the algorithm runs on. + typedef GR Graph; + ///The type of the map that stores the edge lengths. + + ///The type of the map that stores the edge lengths. + ///It must meet the \ref concept::ReadMap "ReadMap" concept. + typedef LM LengthMap; + //The type of the length of the edges. + typedef typename LM::Value Value; + ///The heap type used by Dijkstra algorithm. + + ///The heap type used by Dijkstra algorithm. + /// + ///\sa BinHeap + ///\sa Dijkstra + typedef BinHeap, + std::less > Heap; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + /// + ///The type of the map that stores the last + ///edges of the shortest paths. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NullMap PredMap; + ///Instantiates a PredMap. + + ///This function instantiates a \ref PredMap. + ///\param G is the graph, to which we would like to define the PredMap. + ///\todo The graph alone may be insufficient for the initialization + static PredMap *createPredMap(const GR &G) + { + return new PredMap(); + } + ///The type of the map that stores whether a nodes is processed. + + ///The type of the map that stores whether a nodes is processed. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + ///By default it is a NullMap. + ///\todo If it is set to a real map, + ///Dijkstra::processed() should read this. + ///\todo named parameter to set this type, function to read and write. + typedef NullMap ProcessedMap; + ///Instantiates a ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. + ///\param G is the graph, to which + ///we would like to define the \ref ProcessedMap + static ProcessedMap *createProcessedMap(const GR &G) + { + return new ProcessedMap(); + } + ///The type of the map that stores the dists of the nodes. + + ///The type of the map that stores the dists of the nodes. + ///It must meet the \ref concept::WriteMap "WriteMap" concept. + /// + typedef NullMap DistMap; + ///Instantiates a DistMap. + + ///This function instantiates a \ref DistMap. + ///\param G is the graph, to which we would like to define the \ref DistMap + static DistMap *createDistMap(const GR &G) + { + return new DistMap(); + } + }; + /// Default traits used by \ref DijkstraWizard /// To make it easier to use Dijkstra algorithm @@ -724,10 +808,10 @@ /// The \ref DijkstraWizardBase is a class to be the default traits of the /// \ref DijkstraWizard class. template - class DijkstraWizardBase : public DijkstraDefaultTraits + class DijkstraWizardBase : public DijkstraWizardDefaultTraits { - typedef DijkstraDefaultTraits Base; + typedef DijkstraWizardDefaultTraits Base; protected: /// Type of the nodes in the graph. typedef typename Base::Graph::Node Node; @@ -738,8 +822,8 @@ void *_length; ///Pointer to the map of predecessors edges. void *_pred; - ///Pointer to the map of predecessors nodes. - void *_predNode; +// ///Pointer to the map of predecessors nodes. +// void *_predNode; ///Pointer to the map of distances. void *_dist; ///Pointer to the source node. @@ -750,8 +834,9 @@ /// This constructor does not require parameters, therefore it initiates /// all of the attributes to default values (0, INVALID). - DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0), - _dist(0), _source(INVALID) {} + DijkstraWizardBase() : _g(0), _length(0), _pred(0), +// _predNode(0), + _dist(0), _source(INVALID) {} /// Constructor. @@ -762,14 +847,14 @@ /// \param l is the initial value of \ref _length /// \param s is the initial value of \ref _source DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : - _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0), - _dist(0), _source(s) {} + _g((void *)&g), _length((void *)&l), _pred(0), +// _predNode(0), + _dist(0), _source(s) {} }; /// A class to make easier the usage of Dijkstra algorithm - /// \ingroup flowalgs /// This class is created to make it easier to use Dijkstra algorithm. /// It uses the functions and features of the plain \ref Dijkstra, /// but it is much simpler to use it. @@ -810,9 +895,9 @@ ///\brief The type of the map that stores the last ///edges of the shortest paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - typedef typename TR::PredNodeMap PredNodeMap; +// ///\brief The type of the map that stores the last but one +// ///nodes of the shortest paths. +// typedef typename TR::PredNodeMap PredNodeMap; ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; @@ -844,7 +929,7 @@ Dijkstra Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length); if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred); - if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode); +// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode); if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist); Dij.run(Base::_source); } @@ -880,25 +965,25 @@ } - template - struct DefPredNodeMapBase : public Base { - typedef T PredNodeMap; - static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; - DefPredNodeMapBase(const Base &b) : Base(b) {} - }; +// template +// struct DefPredNodeMapBase : public Base { +// typedef T PredNodeMap; +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; +// DefPredNodeMapBase(const Base &b) : Base(b) {} +// }; - ///\brief \ref named-templ-param "Named parameter" - ///function for setting PredNodeMap type - /// - /// \ref named-templ-param "Named parameter" - ///function for setting PredNodeMap type - /// - template - DijkstraWizard > predNodeMap(const T &t) - { - Base::_predNode=(void *)&t; - return DijkstraWizard >(*this); - } +// ///\brief \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// /// \ref named-templ-param "Named parameter" +// ///function for setting PredNodeMap type +// /// +// template +// DijkstraWizard > predNodeMap(const T &t) +// { +// Base::_predNode=(void *)&t; +// return DijkstraWizard >(*this); +// } template struct DefDistMapBase : public Base { @@ -932,11 +1017,23 @@ }; - ///\e + ///Function type interface for Dijkstra algorithm. /// \ingroup flowalgs - ///\todo Please document... + ///Function type interface for Dijkstra algorithm. /// + ///This function also has several + ///\ref named-templ-func-param "named parameters", + ///they are declared as the members of class \ref DijkstraWizard. + ///The following + ///example shows how to use these parameters. + ///\code + /// dijkstra(g,length,source).predMap(preds).run(); + ///\endcode + ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" + ///to the end of the parameter list. + ///\sa DijkstraWizard + ///\sa Dijkstra template DijkstraWizard > dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) @@ -944,8 +1041,6 @@ return DijkstraWizard >(g,l,s); } -/// @} - } //END OF NAMESPACE LEMON #endif diff -r 640ca1bd850f -r 5331168bbb18 src/test/bfs_test.cc --- a/src/test/bfs_test.cc Wed Mar 16 07:52:16 2005 +0000 +++ b/src/test/bfs_test.cc Wed Mar 16 07:56:25 2005 +0000 @@ -42,7 +42,7 @@ bool b; BType::DistMap d(G); BType::PredMap p(G); - BType::PredNodeMap pn(G); + // BType::PredNodeMap pn(G); BType bfs_test(G); @@ -53,7 +53,7 @@ n = bfs_test.predNode(n); d = bfs_test.distMap(); p = bfs_test.predMap(); - pn = bfs_test.predNodeMap(); + // pn = bfs_test.predNodeMap(); b = bfs_test.reached(n); } diff -r 640ca1bd850f -r 5331168bbb18 src/test/dfs_test.cc --- a/src/test/dfs_test.cc Wed Mar 16 07:52:16 2005 +0000 +++ b/src/test/dfs_test.cc Wed Mar 16 07:56:25 2005 +0000 @@ -42,7 +42,7 @@ bool b; DType::DistMap d(G); DType::PredMap p(G); - DType::PredNodeMap pn(G); + // DType::PredNodeMap pn(G); DType dfs_test(G); @@ -53,7 +53,7 @@ n = dfs_test.predNode(n); d = dfs_test.distMap(); p = dfs_test.predMap(); - pn = dfs_test.predNodeMap(); + // pn = dfs_test.predNodeMap(); b = dfs_test.reached(n); } diff -r 640ca1bd850f -r 5331168bbb18 src/test/dijkstra_test.cc --- a/src/test/dijkstra_test.cc Wed Mar 16 07:52:16 2005 +0000 +++ b/src/test/dijkstra_test.cc Wed Mar 16 07:56:25 2005 +0000 @@ -119,8 +119,8 @@ { - NullMap myPredNodeMap; - dijkstra(G,cap).predNodeMap(myPredNodeMap).run(s); + NullMap myPredMap; + dijkstra(G,cap).predMap(myPredMap).run(s); } return 0; }