RhodeCode

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref PredMap object.

    ///

    /// \ref named-templ-param "Named parameter"

    ///for setting \ref PredMap object.

    template<class T>

    BfsWizard<DefPredMapBase<T> > predMap(const T &t)

    {

      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<DefPredMapBase<T> >(*this);

    }

    template<class T>

    struct DefReachedMapBase : public Base {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &) { return 0; };

      DefReachedMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref ReachedMap object.

    ///

    /// \ref named-templ-param "Named parameter"

    ///for setting \ref ReachedMap object.

    template<class T>

    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)

    {

      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<DefReachedMapBase<T> >(*this);

    }

    template<class T>

    struct DefProcessedMapBase : public Base {

      typedef T ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };

      DefProcessedMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref ProcessedMap object.

    ///

    /// \ref named-templ-param "Named parameter"

    ///for setting \ref ProcessedMap object.

    template<class T>

    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)

    {

      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<DefProcessedMapBase<T> >(*this);

    }

    template<class T>

    struct DefDistMapBase : public Base {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph &) { return 0; };

      DefDistMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref DistMap object.

    ///

    /// \ref named-templ-param "Named parameter"

    ///for setting \ref DistMap object.

    template<class T>

    BfsWizard<DefDistMapBase<T> > distMap(const T &t)

    {

      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<DefDistMapBase<T> >(*this);

    }

  };

  ///Function type interface for Bfs algorithm.

  /// \ingroup search

  ///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<class GR>

  BfsWizard<BfsWizardBase<GR> >

  bfs(const GR &g,typename GR::Node s=INVALID)

  {

    return BfsWizard<BfsWizardBase<GR> >(g,s);

  }

#ifdef DOXYGEN

  /// \brief Visitor class for BFS.

  ///

  /// This class defines the interface of the BfsVisit events, and

  /// it could be the base of a real visitor class.

  template <typename _Digraph>

  struct BfsVisitor {

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    /// \brief Called for the source node(s) of the BFS.

    ///

    /// This function is called for the source node(s) of the BFS.

    void start(const Node& node) {}

    /// \brief Called when a node is reached first time.

    ///

    /// This function is called when a node is reached first time.

    void reach(const Node& node) {}

    /// \brief Called when a node is processed.

    ///

    /// This function is called when a node is processed.

    void process(const Node& node) {}

    /// \brief Called when an arc reaches a new node.

    ///

    /// This function is called when the BFS finds an arc whose target node

    /// is not reached yet.

    void discover(const Arc& arc) {}

    /// \brief Called when an arc is examined but its target node is

    /// already discovered.

    ///

    /// This function is called when an arc is examined but its target node is

    /// already discovered.

    void examine(const Arc& arc) {}

  };

#else

  template <typename _Digraph>

  struct BfsVisitor {

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    void start(const Node&) {}

    void reach(const Node&) {}

    void process(const Node&) {}

    void discover(const Arc&) {}

    void examine(const Arc&) {}

    template <typename _Visitor>

    struct Constraints {

      void constraints() {

        Arc arc;

        Node node;

        visitor.start(node);

        visitor.reach(node);

        visitor.process(node);

        visitor.discover(arc);

        visitor.examine(arc);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  template<class _Digraph>

  struct BfsVisitDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef _Digraph Digraph;

    /// \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 concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a \ref ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %BFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the %BFS algorithm

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// the member functions of the \c Visitor class on every BFS event.

  ///

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// The default value is

  /// \ref ListDigraph. The value of _Digraph is not used directly by

  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam _Visitor The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

  /// \tparam _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a BFS visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = BfsVisitor<_Digraph>,

            typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithm.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw()

      {

        return "lemon::BfsVisit::UninitializedParameter";

      }

    };

    ///The traits class.

    typedef _Traits Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    typedef _Visitor Visitor;

    ///The type of the map that indicates which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *_digraph;

    //Pointer to the visitor object.

    Visitor *_visitor;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    std::vector<typename Digraph::Node> _list;

    int _list_front, _list_back;

    ///Creates the maps if necessary.

    ///\todo Better memory allocation (instead of new).

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    BfsVisit() {}

  public:

    typedef BfsVisit Create;

    /// \name Named template parameters

    ///@{

    template <class T>

    struct DefReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &digraph) {

        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 BfsVisit< Digraph, Visitor,

                                            DefReachedMapTraits<T> > {

      typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;

    };

    ///@}

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param visitor The visitor object of the algorithm.

    BfsVisit(const Digraph& digraph, Visitor& visitor)

      : _digraph(&digraph), _visitor(&visitor),

        _reached(0), local_reached(false) {}

    /// \brief Destructor.

    ~BfsVisit() {

      if(local_reached) delete _reached;

    }

    /// \brief Sets the map that indicates which nodes are reached.

    ///

    /// Sets the map that indicates which nodes are reached.

    /// If you don't use this function before calling \ref run(),

    /// it will allocate one. The destructor deallocates this

    /// automatically allocated map, of course.

    /// \return <tt> (*this) </tt>

    BfsVisit &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 \ref lemon::BfsVisit::run()

    /// "run()".

    /// \n

    /// If you need more control on the execution, first you must call

    /// \ref lemon::BfsVisit::init() "init()", then you can add several

    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".

    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the

    /// actual path computation.

    /// @{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures.

    void init() {

      create_maps();

      _list.resize(countNodes(*_digraph));

      _list_front = _list_back = -1;

      for (NodeIt u(*_digraph) ; 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);

          _list[++_list_back] = s;

        }

    }

    /// \brief Processes the next node.

    ///

    /// Processes the next node.

    ///

    /// \return The processed node.

    ///

    /// \pre The queue must not be empty.

    Node processNextNode() {

      Node n = _list[++_list_front];

      _visitor->process(n);

      Arc e;

      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {

        Node m = _digraph->target(e);

        if (!(*_reached)[m]) {

          _visitor->discover(e);

          _visitor->reach(m);

    template<class T>

    struct DefReachedMapBase : public Base {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &) { return 0; };

      DefReachedMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref ReachedMap object.

    ///

    /// \ref named-templ-param "Named parameter"

    ///for setting \ref ReachedMap object.

    template<class T>

    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)

    {

      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));

      return DfsWizard<DefReachedMapBase<T> >(*this);

    }

    template<class T>

    struct DefProcessedMapBase : public Base {

      typedef T ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };

      DefProcessedMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref ProcessedMap object.

    ///

    /// \ref named-templ-param "Named parameter"

    ///for setting \ref ProcessedMap object.

    template<class T>

    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)

    {

      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));

      return DfsWizard<DefProcessedMapBase<T> >(*this);

    }

    template<class T>

    struct DefDistMapBase : public Base {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph &) { return 0; };

      DefDistMapBase(const TR &b) : TR(b) {}

    };

    ///\brief \ref named-templ-param "Named parameter"

    ///for setting \ref DistMap object.

    ///

    ///\ref named-templ-param "Named parameter"

    ///for setting \ref DistMap object.

    template<class T>

    DfsWizard<DefDistMapBase<T> > distMap(const T &t)

    {

      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));

      return DfsWizard<DefDistMapBase<T> >(*this);

    }

  };

  ///Function type interface for Dfs algorithm.

  ///\ingroup search

  ///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<class GR>

  DfsWizard<DfsWizardBase<GR> >

  dfs(const GR &g,typename GR::Node s=INVALID)

  {

    return DfsWizard<DfsWizardBase<GR> >(g,s);

  }

#ifdef DOXYGEN

  /// \brief Visitor class for DFS.

  ///

  /// This class defines the interface of the DfsVisit events, and

  /// it could be the base of a real visitor class.

  template <typename _Digraph>

  struct DfsVisitor {

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    /// \brief Called for the source node of the DFS.

    ///

    /// This function is called for the source node of the DFS.

    void start(const Node& node) {}

    /// \brief Called when the source node is leaved.

    ///

    /// This function is called when the source node is leaved.

    void stop(const Node& node) {}

    /// \brief Called when a node is reached first time.

    ///

    /// This function is called when a node is reached first time.

    void reach(const Node& node) {}

    /// \brief Called when an arc reaches a new node.

    ///

    /// This function is called when the DFS finds an arc whose target node

    /// is not reached yet.

    void discover(const Arc& arc) {}

    /// \brief Called when an arc is examined but its target node is

    /// already discovered.

    ///

    /// This function is called when an arc is examined but its target node is

    /// already discovered.

    void examine(const Arc& arc) {}

    /// \brief Called when the DFS steps back from a node.

    ///

    /// This function is called when the DFS steps back from a node.

    void leave(const Node& node) {}

    /// \brief Called when the DFS steps back on an arc.

    ///

    /// This function is called when the DFS steps back on an arc.

    void backtrack(const Arc& arc) {}

  };

#else

  template <typename _Digraph>

  struct DfsVisitor {

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    void start(const Node&) {}

    void stop(const Node&) {}

    void reach(const Node&) {}

    void discover(const Arc&) {}

    void examine(const Arc&) {}

    void leave(const Node&) {}

    void backtrack(const Arc&) {}

    template <typename _Visitor>

    struct Constraints {

      void constraints() {

        Arc arc;

        Node node;

        visitor.start(node);

        visitor.stop(arc);

        visitor.reach(node);

        visitor.discover(arc);

        visitor.examine(arc);

        visitor.leave(node);

        visitor.backtrack(arc);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of DfsVisit class.

  ///

  /// Default traits class of DfsVisit class.

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  template<class _Digraph>

  struct DfsVisitDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef _Digraph Digraph;

    /// \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 concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a \ref ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap.

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief %DFS algorithm class with visitor interface.

  ///

  /// 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

  /// the member functions of the \c Visitor class on every DFS event.

  ///

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// The default value is

  /// \ref ListDigraph. The value of _Digraph is not used directly by

  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.

  /// \tparam _Visitor The Visitor type that is used by the algorithm.

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" 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.

  /// \tparam _Traits Traits class to set various data types used by the

  /// algorithm. The default traits class is

  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a DFS visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

            typename _Visitor = DfsVisitor<_Digraph>,

            typename _Traits = DfsDefaultTraits<_Digraph> >

#endif

  class DfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithm.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw()

      {

        return "lemon::DfsVisit::UninitializedParameter";

      }

    };

    ///The traits class.

    typedef _Traits Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    typedef _Visitor Visitor;

    ///The type of the map that indicates which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *_digraph;

    //Pointer to the visitor object.

    Visitor *_visitor;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    std::vector<typename Digraph::Arc> _stack;

    int _stack_head;

    ///Creates the maps if necessary.

    ///\todo Better memory allocation (instead of new).

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    DfsVisit() {}

  public:

    typedef DfsVisit Create;

    /// \name Named template parameters

    ///@{

    template <class T>

    struct DefReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &digraph) {

        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 DfsVisit< Digraph, Visitor,

                                            DefReachedMapTraits<T> > {

      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;

    };

    ///@}

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param visitor The visitor object of the algorithm.

    DfsVisit(const Digraph& digraph, Visitor& visitor)

      : _digraph(&digraph), _visitor(&visitor),

        _reached(0), local_reached(false) {}

    /// \brief Destructor.

    ~DfsVisit() {

      if(local_reached) delete _reached;

    }

    /// \brief Sets the map that indicates which nodes are reached.

    ///

    /// Sets the map that indicates which nodes are reached.

    /// If you don't use this function before calling \ref run(),

    /// it will allocate one. The destructor 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 \ref lemon::DfsVisit::run()

    /// "run()".

    /// \n

    /// If you need more control on the execution, first you must call

    /// \ref lemon::DfsVisit::init() "init()", then you can add several

    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".

    /// Finally \ref lemon::DfsVisit::start() "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(*_digraph));

      _stack_head = -1;

      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {

        _reached->set(u, false);

      }

    }

    ///Adds a new source node.

    ///Adds a new source node to the set of nodes to be processed.

    ///

    ///\pre The stack must be empty. (Otherwise the algorithm gives

    ///false results.)

    ///

    ///\warning Distances will be wrong (or at least strange) in case of

    ///multiple sources.

    void addSource(Node s)

    {

      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");

      if(!(*_reached)[s]) {

          _reached->set(s,true);

          _visitor->start(s);

          _visitor->reach(s);

          Arc e;

          _digraph->firstOut(e, s);

          if (e != INVALID) {

            _stack[++_stack_head] = e;

          } else {

            _visitor->leave(s);

          }

        }

    }

    /// \brief Processes the next arc.

    ///