RhodeCode

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

  ///

  /// This interface of the BFS algorithm should be used in special cases

  /// when extra actions have to be performed in connection with certain

  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()

  /// instead.

  ///

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

#endif

  class BfsVisit {

  public:

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

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    BfsVisit() {}

  public:

        if (arc != INVALID) return direct(arc, false);

      }

      return INVALID;

    }

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {

      if (s != t) {

        if (p == INVALID) {

          Edge arc = Parent::findArc(s, t);

          if (arc != INVALID) return arc;

          arc = Parent::findArc(t, s);

          if (arc != INVALID) return arc;

        } else if (Parent::s(p) == s) {

          Edge arc = Parent::findArc(s, t, p);

          if (arc != INVALID) return arc;

          arc = Parent::findArc(t, s);

          if (arc != INVALID) return arc;

        } else {

          Edge arc = Parent::findArc(t, s, p);

          if (arc != INVALID) return arc;

        }

      } else {

        return Parent::findArc(s, t, p);

      }

      return INVALID;

    }

  };

  template <typename Base>

  class BidirBpGraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef BidirBpGraphExtender Digraph;

    typedef typename Parent::Node Node;

    typedef typename Parent::Edge Edge;

    using Parent::first;

    using Parent::next;

    using Parent::id;

    class Red : public Node {

      friend class BidirBpGraphExtender;

    public:

      Red() {}

      Red(const Node& node) : Node(node) {

      }

      Red& operator=(const Node& node) {

        Node::operator=(node);

        return *this;

      }

      Red(Invalid) : Node(INVALID) {}

      Red& operator=(Invalid) {

        Node::operator=(INVALID);

        return *this;

      }

    };

    void first(Red& node) const {

      Parent::firstRed(static_cast<Node&>(node));

    }

    void next(Red& node) const {

      Parent::nextRed(static_cast<Node&>(node));

    }

    int id(const Red& node) const {

      return Parent::redId(node);

    }

    class Blue : public Node {

      friend class BidirBpGraphExtender;

    public:

      Blue() {}

      Blue(const Node& node) : Node(node) {

      }

      Blue& operator=(const Node& node) {

        Node::operator=(node);

        return *this;

      }

      Blue(Invalid) : Node(INVALID) {}

      Blue& operator=(Invalid) {

        Node::operator=(INVALID);

        return *this;

      }

    };

    void first(Blue& node) const {

      Parent::firstBlue(static_cast<Node&>(node));

    }

    void next(Blue& node) const {

      Parent::nextBlue(static_cast<Node&>(node));

    }

    int id(const Blue& node) const {

      return Parent::redId(node);

    }

    Node source(const Edge& arc) const {

      return red(arc);

    }

    Node target(const Edge& arc) const {

      return blue(arc);

    }

    void firstInc(Edge& arc, bool& dir, const Node& node) const {

      if (Parent::red(node)) {

        Parent::firstFromRed(arc, node);

        dir = true;

      } else {

        Parent::firstFromBlue(arc, node);

        dir = static_cast<Edge&>(arc) == INVALID;

      }

    }

    void nextInc(Edge& arc, bool& dir) const {

      if (dir) {

        Parent::nextFromRed(arc);

      } else {

        Parent::nextFromBlue(arc);

        if (arc == INVALID) dir = true;

      }

    }

    class Arc : public Edge {

      friend class BidirBpGraphExtender;

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

  ///

  /// This interface of the DFS algorithm should be used in special cases

  /// when extra actions have to be performed in connection with certain

  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()

  /// instead.

  ///

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

#endif

  class DfsVisit {

  public:

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

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    DfsVisit() {}

  public: