Changeset 1749:c13f6b4aa40e in lemon-0.x

Timestamp:

11/02/05 16:22:28 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Visitor interface for the dfs algorithm.

File:

• lemon/dfs.h (modified) (19 diffs)

lemon/dfs.h

@@ -28 +28 @@
 #include <lemon/maps.h>
 
+#include <lemon/concept_check.h>
+
 namespace lemon {
-
 
   
@@ -124 +125 @@
   ///
   ///\author Jacint Szabo and Alpar Juttner
-  ///\todo A compare object would be nice.
-
 #ifdef DOXYGEN
   template <typename GR,
@@ -276 +275 @@
     ///
     template <class T>
-    struct DefReachedMap {
+    struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
       typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
     };
@@ -327 +326 @@
       G(&_G),
       _pred(NULL), local_pred(false),
-//       _predNode(NULL), local_predNode(false),
       _dist(NULL), local_dist(false),
       _reached(NULL), local_reached(false),
@@ -337 +335 @@
     {
       if(local_pred) delete _pred;
-//       if(local_predNode) delete _predNode;
       if(local_dist) delete _dist;
       if(local_reached) delete _reached;
@@ -359 +356 @@
       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 <tt> (*this) </tt>
-//     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.
@@ -469 +449 @@
           _reached->set(s,true);
           _pred->set(s,INVALID);
-          // _predNode->set(u,INVALID);
           OutEdgeIt e(*G,s);
           if(e!=INVALID) {
@@ -496 +475 @@
         _pred->set(m,e);
         _reached->set(m,true);
-        //        _pred_node->set(m,G->source(e));
         ++_stack_head;
         _stack[_stack_head] = OutEdgeIt(*G, m);
@@ -505 +483 @@
         ++_stack[_stack_head];
       }
-      //'m' is now the (original) source of the _stack[_stack_head] 
       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
         _processed->set(m,true);
@@ -591 +568 @@
     ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
     ///
-    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
+    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
     ///not a node map.
-    template<class NM>
-      void start(const NM &nm)
-      {
-        while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
-      }
-    
+    template<class EM>
+    void start(const EM &em)
+    {
+      while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
+    }
+
     ///Runs %DFS algorithm from node \c s.
     
@@ -726 +703 @@
     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.
 
@@ -775 +745 @@
       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<typename Graph::Node,typename Graph::Node> PredNodeMap;
-//     ///Instantiates a PredNodeMap.
-    
-//     ///This function instantiates a \ref PredNodeMap. 
-//     ///\param G is the graph, to which
-//     ///we would like to define the \ref PredNodeMap
-//     static PredNodeMap *createPredNodeMap(const GR &G)
-//     {
-//       return new PredNodeMap();
-//     }
 
     ///The type of the map that indicates which nodes are processed.
@@ -872 +825 @@
     ///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;
@@ -885 +836 @@
     /// all of the attributes to default values (0, INVALID).
     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
-//                         _predNode(0),
                            _dist(0), _source(INVALID) {}
 
@@ -897 +847 @@
     DfsWizardBase(const GR &g, Node s=INVALID) :
       _g((void *)&g), _reached(0), _processed(0), _pred(0),
-//       _predNode(0),
       _dist(0), _source(s) {}
 
@@ -946 +895 @@
     ///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 distances of the nodes.
     typedef typename TR::DistMap DistMap;
@@ -979 +925 @@
       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);
@@ -1056 +1001 @@
     }
     
-
-//     template<class T>
-//     struct DefPredNodeMapBase : public Base {
-//       typedef T PredNodeMap;
-//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
-//       DefPredNodeMapBase(const TR &b) : TR(b) {}
-//     };
-    
-//     ///\brief \ref named-templ-param "Named parameter"
-//     ///function for setting PredNodeMap type
-//     ///
-//     /// \ref named-templ-param "Named parameter"
-//     ///function for setting PredNodeMap type
-//     ///
-//     template<class T>
-//     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
-//     {
-//       Base::_predNode=(void *)&t;
-//       return DfsWizard<DefPredNodeMapBase<T> >(*this);
-//     }
-   
     template<class T>
     struct DefDistMapBase : public Base {
@@ -1133 +1057 @@
   }
 
+  /// \brief Visitor class for dfs.
+  ///  
+  /// It gives a simple interface for a functional interface for dfs 
+  /// traversal. The traversal on a linear data structure. 
+  template <typename _Graph>
+  struct DfsVisitor {
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::Node Node;
+    /// \brief Called when the edge reach a node.
+    /// 
+    /// It is called when the dfs find an edge which target is not
+    /// reached yet.
+    void discover(const Edge& edge) {}
+    /// \brief Called when the node reached first time.
+    /// 
+    /// It is Called when the node reached first time.
+    void reach(const Node& node) {}
+    /// \brief Called when we step back on an edge.
+    /// 
+    /// It is called when the dfs should step back on the edge.
+    void backtrack(const Edge& edge) {}
+    /// \brief Called when we step back from the node.
+    /// 
+    /// It is called when we step back from the node.
+    void leave(const Node& node) {}
+    /// \brief Called when the edge examined but target of the edge 
+    /// already discovered.
+    /// 
+    /// It called when the edge examined but the target of the edge 
+    /// already discovered.
+    void examine(const Edge& edge) {}
+    /// \brief Called for the source node of the dfs.
+    /// 
+    /// It is called for the source node of the dfs.
+    void start(const Node&) {}
+    /// \brief Called when we leave the source node of the dfs.
+    /// 
+    /// It is called when we leave the source node of the dfs.
+    void stop(const Node&) {}
+
+    template <typename _Visitor>
+    struct Constraints {
+      void constraints() {
+        Edge edge;
+        Node node;
+        visitor.discover(edge);
+        visitor.reach(node);
+        visitor.backtrack(edge);
+        visitor.leave(node);
+        visitor.examine(edge);
+        visitor.start(node);
+        visitor.stop(edge);
+      }
+      _Visitor& visitor;
+    };
+  };
+
+  /// \brief Default traits class of DfsVisit class.
+  ///
+  /// Default traits class of DfsVisit class.
+  /// \param _Graph Graph type.
+  template<class _Graph>
+  struct DfsVisitDefaultTraits {
+
+    /// \brief The graph type the algorithm runs on. 
+    typedef _Graph Graph;
+
+    /// \brief 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<bool> ReachedMap;
+
+    /// \brief 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 Graph &graph) {
+      return new ReachedMap(graph);
+    }
+
+  };
+  
+  /// %DFS Visit algorithm class.
+  
+  /// \ingroup flowalgs
+  /// This class provides an efficient implementation of the %DFS algorithm
+  /// with visitor interface.
+  ///
+  /// The %DfsVisit class provides an alternative interface to the Dfs
+  /// class. It works with callback mechanism, the DfsVisit object calls
+  /// on every dfs event the \c Visitor class member functions. 
+  ///
+  /// \param _Graph The graph type the algorithm runs on. The default value is
+  /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
+  /// is only passed to \ref DfsDefaultTraits.
+  /// \param _Visitor The Visitor object for the algorithm. The 
+  /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
+  /// does not observe the Dfs events. If you want to observe the dfs
+  /// events you should implement your own Visitor class.
+  /// \param _Traits Traits class to set various data types used by the 
+  /// algorithm. The default traits class is
+  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
+  /// See \ref DfsVisitDefaultTraits for the documentation of
+  /// a Dfs visit traits class.
+  ///
+  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
+#ifdef DOXYGEN
+  template <typename _Graph, typename _Visitor, typename _Traits>
+#else
+  template <typename _Graph = ListGraph,
+            typename _Visitor = DfsVisitor<_Graph>,
+            typename _Traits = DfsDefaultTraits<_Graph> >
+#endif
+  class DfsVisit {
+  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::DfsVisit::UninitializedParameter";
+      }
+    };
+
+    typedef _Traits Traits;
+
+    typedef typename Traits::Graph Graph;
+
+    typedef _Visitor Visitor;
+
+    ///The type of the map indicating which nodes are reached.
+    typedef typename Traits::ReachedMap ReachedMap;
+
+  private:
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+
+    /// Pointer to the underlying graph.
+    const Graph *_graph;
+    /// Pointer to the visitor object.
+    Visitor *_visitor;
+    ///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;
+
+    std::vector<typename Graph::Edge> _stack;
+    int _stack_head;
+
+    /// \brief Creates the maps if necessary.
+    ///
+    /// Creates the maps if necessary.
+    void create_maps() {
+      if(!_reached) {
+        local_reached = true;
+        _reached = Traits::createReachedMap(*_graph);
+      }
+    }
+
+  protected:
+
+    DfsVisit() {}
+    
+  public:
+
+    typedef DfsVisit Create;
+
+    /// \name Named template parameters
+
+    ///@{
+    template <class T>
+    struct DefReachedMapTraits : public Traits {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &graph) {
+        throw UninitializedParameter();
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// ReachedMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
+    template <class T>
+    struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
+      typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
+    };
+    ///@}
+
+  public:      
+    
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    ///
+    /// \param graph the graph the algorithm will run on.
+    /// \param visitor The visitor of the algorithm.
+    ///
+    DfsVisit(const Graph& graph, Visitor& visitor) 
+      : _graph(&graph), _visitor(&visitor),
+        _reached(0), local_reached(false) {}
+    
+    /// \brief Destructor.
+    ///
+    /// Destructor.
+    ~DfsVisit() {
+      if(local_reached) delete _reached;
+    }
+
+    /// \brief 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 <tt> (*this) </tt>
+    DfsVisit &reachedMap(ReachedMap &m) {
+      if(local_reached) {
+        delete _reached;
+        local_reached=false;
+      }
+      _reached = &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.
+
+    /// @{
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures.
+    ///
+    void init() {
+      create_maps();
+      _stack.resize(countNodes(*_graph));
+      _stack_head = -1;
+      for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
+        _reached->set(u, false);
+      }
+    }
+    
+    /// \brief Adds a new source node.
+    ///
+    /// Adds a new source node to the set of nodes to be processed.
+    void addSource(Node s) {
+      if(!(*_reached)[s]) {
+          _reached->set(s,true);
+          _visitor->start(s);
+          _visitor->reach(s);
+          Edge e; 
+          _graph->firstOut(e, s);
+          if (e != INVALID) {
+            _stack[++_stack_head] = e;
+          } else {
+            _visitor->leave(s);
+          }
+        }
+    }
+    
+    /// \brief Processes the next edge.
+    ///
+    /// Processes the next edge.
+    ///
+    /// \return The processed edge.
+    ///
+    /// \pre The stack must not be empty!
+    Edge processNextEdge() { 
+      Edge e = _stack[_stack_head];
+      Node m = _graph->target(e);
+      if(!(*_reached)[m]) {
+        _visitor->discover(e);
+        _visitor->reach(m);
+        _reached->set(m, true);
+        _graph->firstOut(_stack[++_stack_head], m);
+      } else {
+        _visitor->examine(e);
+        m = _graph->source(e);
+        _graph->nextOut(_stack[_stack_head]);
+      }
+      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
+        _visitor->leave(m);
+        --_stack_head;
+        if (_stack_head >= 0) {
+          _visitor->backtrack(_stack[_stack_head]);
+          m = _graph->source(_stack[_stack_head]);
+          _graph->nextOut(_stack[_stack_head]);
+        } else {
+          _visitor->stop(m);      
+        }
+      }
+      return e;
+    }
+
+    /// \brief Next edge to be processed.
+    ///
+    /// Next edge to be processed.
+    ///
+    /// \return The next edge to be processed or INVALID if the stack is
+    /// empty.
+    Edge nextEdge() { 
+      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
+    }
+
+    /// \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
+    ///
+    /// \todo This should be called emptyStack() or some "neutral" name.
+    bool emptyQueue() { return _stack_head < 0; }
+
+    /// \brief Returns the number of the nodes to be processed.
+    ///
+    /// Returns the number of the nodes to be processed in the queue.
+    ///
+    ///\todo This should be called stackSize() or some "neutral" name.
+    int queueSize() { return _stack_head + 1; }
+    
+    /// \brief 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.
+    void start() {
+      while ( !emptyQueue() ) processNextEdge();
+    }
+    
+    /// \brief 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.
+    void start(Node dest) {
+      while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest) 
+        processNextEdge();
+    }
+    
+    /// \brief 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 an edge \c e with <tt>nm[e]==true</tt>.
+    ///
+    /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
+    /// not a node map.
+    template <typename EM>
+    void start(const EM &em) {
+      while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
+    }
+
+    /// \brief Runs %DFS algorithm from node \c s.
+    ///
+    /// This method runs the %DFS algorithm from a root node \c s.
+    /// \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();
+    }
+    ///@}
+
+    /// \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.
+    ///@{
+    /// \brief Checks if a node is reachable from the root.
+    ///
+    /// Returns \c true if \c v is reachable from the root(s).
+    /// \warning The source nodes are inditated as unreachable.
+    /// \pre Either \ref run() or \ref start()
+    /// must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    ///@}
+  };
+
+
 } //END OF NAMESPACE LEMON