RhodeCode

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

  ///

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

    typedef BfsVisit Create;

    /// \name Named template parameters

    ///@{

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &digraph) {

        LEMON_ASSERT(false, "ReachedMap is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \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 SetReachedMap : public BfsVisit< Digraph, Visitor,

                                            SetReachedMapTraits<T> > {

      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<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 Parent::arcFromId(ix);

    }

    int id(const Node &n) const {

      return Parent::id(n);

    }

    int id(const Edge &e) const {

      return Parent::id(e);

    }

    int id(const Arc &e) const {

      return 2 * Parent::id(e) + int(e.forward);

    }

    int maxNodeId() const {

      return Parent::maxNodeId();

    }

    int maxArcId() const {

      return 2 * Parent::maxArcId() + 1;

    }

    int maxEdgeId() const {

      return Parent::maxArcId();

    }

    int arcNum() const {

      return 2 * Parent::arcNum();

    }

    int edgeNum() const {

      return Parent::arcNum();

    }

    Arc findArc(Node s, Node t, Arc p = INVALID) const {

      if (p == INVALID) {

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

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

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

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

      } else if (direction(p)) {

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

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

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

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

      } else {

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

        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;

    protected:

      bool forward;

      Arc(const Edge& arc, bool _forward)

        : Edge(arc), forward(_forward) {}

    public:

      Arc() {}

      Arc (Invalid) : Edge(INVALID), forward(true) {}

      bool operator==(const Arc& i) const {

        return Edge::operator==(i) && forward == i.forward;

      }

      bool operator!=(const Arc& i) const {

        return Edge::operator!=(i) || forward != i.forward;

      }

      bool operator<(const Arc& i) const {

        return Edge::operator<(i) ||

          (!(i.forward<forward) && Edge(*this)<Edge(i));

      }

    };

    void first(Arc& arc) const {

      Parent::first(static_cast<Edge&>(arc));

      arc.forward = true;

    }

    void next(Arc& arc) const {

      if (!arc.forward) {

        Parent::next(static_cast<Edge&>(arc));

      }

      arc.forward = !arc.forward;

    }

    void firstOut(Arc& arc, const Node& node) const {

      if (Parent::red(node)) {

        Parent::firstFromRed(arc, node);

        arc.forward = true;

      } else {

        Parent::firstFromBlue(arc, node);

        arc.forward = static_cast<Edge&>(arc) == INVALID;

      }

    }

    void nextOut(Arc& arc) const {

      if (arc.forward) {

        Parent::nextFromRed(arc);

      } else {

        Parent::nextFromBlue(arc);

        arc.forward = static_cast<Edge&>(arc) == INVALID;

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

  ///

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

    typedef DfsVisit Create;

    /// \name Named template parameters

    ///@{

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &digraph) {

        LEMON_ASSERT(false, "ReachedMap is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \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 SetReachedMap : public DfsVisit< Digraph, Visitor,

                                            SetReachedMapTraits<T> > {

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