diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/dfs.h --- a/src/lemon/dfs.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1136 +0,0 @@ -/* -*- C++ -*- - * src/lemon/dfs.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_DFS_H -#define LEMON_DFS_H - -///\ingroup flowalgs -///\file -///\brief Dfs algorithm. - -#include -#include -#include -#include -#include - -namespace lemon { - - - - ///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 &) - { - 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. - - ///\ingroup flowalgs - ///This class provides an efficient implementation of the %DFS algorithm. - /// - ///\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 Jacint Szabo and Alpar Juttner - ///\todo A compare object would be nice. - -#ifdef DOXYGEN - template -#else - template > -#endif - 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 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 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 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 *_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 *_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; - - std::vector _stack; - int _stack_head; -// ///The source node of the last execution. -// Node source; - - ///Creates the maps if necessary. - - ///\todo Error if \c G are \c NULL. - ///\todo Better memory allocation (instead of new). - void create_maps() - { - if(!_pred) { - local_pred = true; - _pred = Traits::createPredMap(*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); - } - } - - 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), - _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_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. - - ///Sets the map storing the predecessor edges. - ///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 &predMap(PredMap &m) - { - if(local_pred) { - delete _pred; - local_pred=false; - } - _pred = &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) -// 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. - - ///Sets the map storing the distances calculated by the algorithm. - ///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 &distMap(DistMap &m) - { - if(local_dist) { - delete _dist; - local_dist=false; - } - _dist = &m; - return *this; - } - - ///Sets the map indicating if a node is reached. - - ///Sets the map indicating if a node is reached. - ///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 &reachedMap(ReachedMap &m) - { - if(local_reached) { - delete _reached; - local_reached=false; - } - _reached = &m; - return *this; - } - - ///Sets the map indicating if a node is processed. - - ///Sets the map indicating if a node is processed. - ///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 &processedMap(ProcessedMap &m) - { - if(local_processed) { - delete _processed; - local_processed=false; - } - _processed = &m; - return *this; - } - - 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 ) { - _pred->set(u,INVALID); - // _predNode->set(u,INVALID); - _reached->set(u,false); - _processed->set(u,false); - } - } - - ///Adds a new source node. - - ///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_head; - _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() && G->target(_stack[_stack_head])!=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) edge map. The algorithm - ///will stop when it reaches a edge \c v with nm[v]==true. - ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map, - ///not a node map. - template - void start(const NM &nm) - { - while ( !emptyQueue() && !nm[_stack[_stack_head]] ) 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)?_stack_head+1: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. - - ///@{ - - ///Copies the path to \c t on the DFS tree into \c p - - ///This function copies the path on the DFS tree to \c t into \c p. - ///If it \c \t is a source itself or unreachable, then it does not - ///alter \c p. - ///\todo Is it the right way to handle unreachable nodes? - ///\return Returns \c true if a path to \c t was actually copied to \c p, - ///\c false otherwise. - ///\sa DirPath - template - bool getPath(P &p,Node t) - { - if(reached(t)) { - p.clear(); - typename P::Builder b(p); - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) - b.pushFront(pred(t)); - b.commit(); - return true; - } - return false; - } - - ///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(s) the return value - ///of this funcion is undefined. - int dist(Node v) const { return (*_dist)[v]; } - - ///Returns the 'previous edge' of the %DFS tree. - - ///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(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 Either \ref run() or \ref start() must be called before using - ///this function. - ///\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' - ///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)[v]==INVALID ? INVALID: - G->source((*_pred)[v]); } - - ///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 *_dist;} - - ///Returns a reference to the %DFS edge-tree map. - - ///Returns a reference to the NodeMap of the edges of the - ///%DFS 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 nodes of %DFS paths. - -// ///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. - ///\warning The source nodes are inditated as unreached. - ///\pre Either \ref run() or \ref start() - ///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. - /// - 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 &) - { - 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 &) - { - 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 &) - { - 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 &) { return 0; }; - DefPredMapBase(const TR &b) : TR(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 &) { return 0; }; - DefReachedMapBase(const TR &b) : TR(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 &) { return 0; }; - DefProcessedMapBase(const TR &b) : TR(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 TR &b) : TR(b) {} -// }; - -// ///\brief \ref named-templ-param "Named parameter" -// ///function for setting PredNodeMap type -// /// -// /// \ref named-templ-param "Named parameter" -// ///function for setting PredNodeMap type -// /// -// template -// 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 &) { return 0; }; - DefDistMapBase(const TR &b) : TR(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 -