RhodeCode

    Node target(const Arc& a) const { return Parent::source(a); }

    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }

    typedef FindArcTagIndicator<DGR> FindArcTag;

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) const {

      return Parent::findArc(v, u, prev);

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for reversing the orientation of the arcs in

  /// a digraph.

  ///

  /// ReverseDigraph can be used for reversing the arcs in a digraph.

  /// It conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  ///

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

  /// digraph are convertible to each other.

  template<typename DGR>

#ifdef DOXYGEN

  class ReverseDigraph {

#else

  class ReverseDigraph :

    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {

#endif

    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;

  public:

    /// The type of the adapted digraph.

    typedef DGR Digraph;

  protected:

    ReverseDigraph() { }

  public:

    /// \brief Constructor

    ///

    /// Creates a reverse digraph adaptor for the given digraph.

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding nodes and arcs in a digraph

  ///

  /// SubDigraph can be used for hiding nodes and arcs in a digraph.

  /// A \c bool node map and a \c bool arc map must be specified, which

  /// define the filters for nodes and arcs.

  /// Only the nodes and arcs with \c true filter value are

  /// shown in the subdigraph. The arcs that are incident to hidden

  /// nodes are also filtered out.

  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

  /// It must be a \c bool (or convertible) node map of the

  /// adapted digraph. The default type is

  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".

  /// \tparam AF The type of the arc filter map.

  /// It must be \c bool (or convertible) arc map of the

  /// adapted digraph. The default type is

  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".

  ///

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

  /// digraph are convertible to each other.

  ///

  /// \see FilterNodes

  /// \see FilterArcs

#ifdef DOXYGEN

  template<typename DGR, typename NF, typename AF>

  class SubDigraph {

#else

  template<typename DGR,

           typename NF = typename DGR::template NodeMap<bool>,

           typename AF = typename DGR::template ArcMap<bool> >

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding nodes and edges in an undirected

  /// graph.

  ///

  /// SubGraph can be used for hiding nodes and edges in a graph.

  /// A \c bool node map and a \c bool edge map must be specified, which

  /// define the filters for nodes and edges.

  /// Only the nodes and edges with \c true filter value are

  /// shown in the subgraph. The edges that are incident to hidden

  /// nodes are also filtered out.

  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

  ///

  /// The adapted graph can also be modified through this adaptor

  /// by adding or removing nodes or edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted graph.

  /// It must conform to the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

  /// It must be a \c bool (or convertible) node map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

  /// \tparam EF The type of the edge filter map.

  /// It must be a \c bool (or convertible) edge map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

  ///

  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

  /// adapted graph are convertible to each other.

  ///

  /// \see FilterNodes

  /// \see FilterEdges

#ifdef DOXYGEN

  template<typename GR, typename NF, typename EF>

  class SubGraph {

#else

  template<typename GR,

           typename NF = typename GR::template NodeMap<bool>,

           typename EF = typename GR::template EdgeMap<bool> >

  template<typename GR, typename NF, typename EF>

  SubGraph<const GR, const NF, const EF>

  subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) {

    return SubGraph<const GR, const NF, const EF>

      (graph, node_filter, edge_filter);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding nodes in a digraph or a graph.

  ///

  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a

  /// graph. A \c bool node map must be specified, which defines the filter

  /// for the nodes. Only the nodes with \c true filter value and the

  /// arcs/edges incident to nodes both with \c true filter value are shown

  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph

  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept

  /// depending on the \c GR template parameter.

  ///

  /// The adapted (di)graph can also be modified through this adaptor

  /// by adding or removing nodes or arcs/edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted digraph or graph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept

  /// or the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

  /// It must be a \c bool (or convertible) node map of the

  /// adapted (di)graph. The default type is

  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

  ///

  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the

  /// adapted (di)graph are convertible to each other.

#ifdef DOXYGEN

  template<typename GR, typename NF>

  class FilterNodes {

#else

  template<typename GR,

           typename NF = typename GR::template NodeMap<bool>,

           typename Enable = void>

  class FilterNodes :

    public DigraphAdaptorExtender<

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,

                     true> > {

#endif

    typedef DigraphAdaptorExtender<

  filterNodes(const GR& graph, NF& node_filter) {

    return FilterNodes<const GR, NF>(graph, node_filter);

  }

  template<typename GR, typename NF>

  FilterNodes<const GR, const NF>

  filterNodes(const GR& graph, const NF& node_filter) {

    return FilterNodes<const GR, const NF>(graph, node_filter);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding arcs in a digraph.

  ///

  /// FilterArcs adaptor can be used for hiding arcs in a digraph.

  /// A \c bool arc map must be specified, which defines the filter for

  /// the arcs. Only the arcs with \c true filter value are shown in the

  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph

  /// "Digraph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  /// \tparam AF The type of the arc filter map.

  /// It must be a \c bool (or convertible) arc map of the

  /// adapted digraph. The default type is

  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".

  ///

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

  /// digraph are convertible to each other.

#ifdef DOXYGEN

  template<typename DGR,

           typename AF>

  class FilterArcs {

#else

  template<typename DGR,

           typename AF = typename DGR::template ArcMap<bool> >

  class FilterArcs :

    public DigraphAdaptorExtender<

      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

                     AF, false> > {

#endif

    typedef DigraphAdaptorExtender<

      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 

  filterArcs(const DGR& digraph, AF& arc_filter) {

    return FilterArcs<const DGR, AF>(digraph, arc_filter);

  }

  template<typename DGR, typename AF>

  FilterArcs<const DGR, const AF>

  filterArcs(const DGR& digraph, const AF& arc_filter) {

    return FilterArcs<const DGR, const AF>(digraph, arc_filter);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding edges in a graph.

  ///

  /// FilterEdges adaptor can be used for hiding edges in a graph.

  /// A \c bool edge map must be specified, which defines the filter for

  /// the edges. Only the edges with \c true filter value are shown in the

  /// subgraph. This adaptor conforms to the \ref concepts::Graph

  /// "Graph" concept.

  ///

  /// The adapted graph can also be modified through this adaptor

  /// by adding or removing nodes or edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted graph.

  /// It must conform to the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam EF The type of the edge filter map.

  /// It must be a \c bool (or convertible) edge map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

  ///

  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

  /// adapted graph are convertible to each other.

#ifdef DOXYGEN

  template<typename GR,

           typename EF>

  class FilterEdges {

#else

  template<typename GR,

           typename EF = typename GR::template EdgeMap<bool> >

  class FilterEdges :

    public GraphAdaptorExtender<

      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 

                   EF, false> > {

#endif

    typedef GraphAdaptorExtender<

      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 

    UndirectorBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(DGR& digraph) {

      _digraph = &digraph;

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for viewing a digraph as an undirected graph.

  ///

  /// Undirector adaptor can be used for viewing a digraph as an undirected

  /// graph. All arcs of the underlying digraph are showed in the

  /// adaptor as an edge (and also as a pair of arcs, of course).

  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  ///

  /// \note The \c Node type of this adaptor and the adapted digraph are

  /// convertible to each other, moreover the \c Edge type of the adaptor

  /// and the \c Arc type of the adapted digraph are also convertible to

  /// each other.

  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type

  /// of the adapted digraph.)

  template<typename DGR>

#ifdef DOXYGEN

  class Undirector {

#else

  class Undirector :

    public GraphAdaptorExtender<UndirectorBase<DGR> > {

#endif

    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;

  public:

    /// The type of the adapted digraph.

    typedef DGR Digraph;

  protected:

    Undirector() { }

  public:

    DM* _direction;

    void initialize(GR& graph, DM& direction) {

      _graph = &graph;

      _direction = &direction;

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for orienting the edges of a graph to get a digraph

  ///

  /// Orienter adaptor can be used for orienting the edges of a graph to

  /// get a digraph. A \c bool edge map of the underlying graph must be

  /// specified, which define the direction of the arcs in the adaptor.

  /// The arcs can be easily reversed by the \c reverseArc() member function

  /// of the adaptor.

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// The adapted graph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted graph.

  /// It must conform to the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam DM The type of the direction map.

  /// It must be a \c bool (or convertible) edge map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

  ///

  /// \note The \c Node type of this adaptor and the adapted graph are

  /// convertible to each other, moreover the \c Arc type of the adaptor

  /// and the \c Edge type of the adapted graph are also convertible to

  /// each other.

#ifdef DOXYGEN

  template<typename GR,

           typename DM>

  class Orienter {

#else

  template<typename GR,

           typename DM = typename GR::template EdgeMap<bool> >

  class Orienter :

    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {

#endif

    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;

  public:

    };

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for composing the residual digraph for directed

  /// flow and circulation problems.

  ///

  /// ResidualDigraph can be used for composing the \e residual digraph

  /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$

  /// be a directed graph and let \f$ F \f$ be a number type.

  /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.

  /// This adaptor implements a digraph structure with node set \f$ V \f$

  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,

  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and

  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so

  /// called residual digraph.

  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,

  /// multiplicities are counted, i.e. the adaptor has exactly

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

  /// arcs).

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It is implicitly \c const.

  /// \tparam CM The type of the capacity map.

  /// It must be an arc map of some numerical type, which defines

  /// the capacities in the flow problem. It is implicitly \c const.

  /// The default type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  /// \tparam FM The type of the flow map.

  /// It must be an arc map of some numerical type, which defines

  /// the flow values in the flow problem. The default type is \c CM.

  /// \tparam TL The tolerance type for handling inexact computation.

  /// The default tolerance type depends on the value type of the

  /// capacity map.

  ///

  /// \note This adaptor is implemented using Undirector and FilterArcs

  /// adaptors.

  ///

  /// \note The \c Node type of this adaptor and the adapted digraph are

  /// convertible to each other, moreover the \c Arc type of the adaptor

  /// is convertible to the \c Arc type of the adapted digraph.

#ifdef DOXYGEN

  template<typename DGR, typename CM, typename FM, typename TL>

  class ResidualDigraph

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for splitting the nodes of a digraph.

  ///

  /// SplitNodes adaptor can be used for splitting each node into an

  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor

  /// replaces each node \f$ u \f$ in the digraph with two nodes,

  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.

  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the

  /// new target of the arc will be \f$ u_{in} \f$ and similarly the

  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.

  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$

  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.

  ///

  /// The aim of this class is running an algorithm with respect to node

  /// costs or capacities if the algorithm considers only arc costs or

  /// capacities directly.

  /// In this case you can use \c SplitNodes adaptor, and set the node

  /// costs/capacities of the original digraph to the \e bind \e arcs

  /// in the adaptor.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It is implicitly \c const.

  ///

  /// \note The \c Node type of this adaptor is converible to the \c Node

  /// type of the adapted digraph.

  template <typename DGR>

#ifdef DOXYGEN

  class SplitNodes {

#else

  class SplitNodes

    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {

#endif

    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;

  public:

    typedef DGR Digraph;

    typedef typename DGR::Node DigraphNode;

    typedef typename DGR::Arc DigraphArc;

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    ///Finds the shortest path between \c s and \c t.

    ///This method runs the %BFS algorithm from node \c s

    ///in order to compute the shortest path to node \c t

    ///(it stops searching when \c t is processed).

    ///

    ///\return \c true if \c t is reachable form \c s.

    ///

    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a

    ///shortcut of the following code.

    ///\code

    ///  b.init();

    ///  b.addSource(s);

    ///  b.start(t);

    ///\endcode

    bool run(Node s,Node t) {

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    ///Runs the algorithm to visit all nodes in the digraph.

    ///

    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.

    ///\code

    ///  b.init();

    ///  for (NodeIt n(gr); n != INVALID; ++n) {

    ///    if (!b.reached(n)) {

    ///      b.addSource(n);

    ///      b.start();

    ///    }

    ///  }

    ///\endcode

    void run() {

      init();

      for (NodeIt n(*G); n != INVALID; ++n) {

        if (!reached(n)) {

          addSource(n);

          start();

        }

      }

    }

    ///@}

    ///\name Query Functions

    ///(it stops searching when \c t is processed).

    ///

    ///\return \c true if \c t is reachable form \c s.

    bool run(Node s, Node t)

    {

      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));

      if (Base::_pred)

        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

      if (Base::_dist)

        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

      if (Base::_reached)

        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));

      if (Base::_processed)

        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));

      alg.run(s,t);

      if (Base::_path)

        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);

      if (Base::_di)

        *Base::_di = alg.dist(t);

      return alg.reached(t);

    }

    ///Runs BFS algorithm to visit all nodes in the digraph.

    void run()

    {

      run(INVALID);

    }

    template<class T>

    struct SetPredMapBase : public Base {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &) { return 0; };

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

    };

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

    ///the predecessor map.

    ///

    ///\ref named-templ-param "Named parameter" function for setting

    ///the map that stores the predecessor arcs of the nodes.

    template<class T>

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

    {

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

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

    }

    /// \brief Finds the shortest path between \c s and \c t.

    ///

    /// This method runs the %BFS algorithm from node \c s

    /// in order to compute the shortest path to node \c t

    /// (it stops searching when \c t is processed).

    ///

    /// \return \c true if \c t is reachable form \c s.

    ///

    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a

    /// shortcut of the following code.

    ///\code

    ///   b.init();

    ///   b.addSource(s);

    ///   b.start(t);

    ///\endcode

    bool run(Node s,Node t) {

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    /// \brief Runs the algorithm to visit all nodes in the digraph.

    ///

    ///

    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.

    ///\code

    ///  b.init();

    ///  for (NodeIt n(gr); n != INVALID; ++n) {

    ///    if (!b.reached(n)) {

    ///      b.addSource(n);

    ///      b.start();

    ///    }

    ///  }

    ///\endcode

    void run() {

      init();

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

        if (!reached(it)) {

          addSource(it);

          start();

        }

      }

    }

    ///@}

    /// \name Query Functions

    ///Finds the %DFS path between \c s and \c t.

    ///This method runs the %DFS algorithm from node \c s

    ///in order to compute the DFS path to node \c t

    ///(it stops searching when \c t is processed)

    ///

    ///\return \c true if \c t is reachable form \c s.

    ///

    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is

    ///just a shortcut of the following code.

    ///\code

    ///  d.init();

    ///  d.addSource(s);

    ///  d.start(t);

    ///\endcode

    bool run(Node s,Node t) {

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    ///Runs the algorithm to visit all nodes in the digraph.

    ///

    ///\note <tt>d.run()</tt> is just a shortcut of the following code.

    ///\code

    ///  d.init();

    ///  for (NodeIt n(digraph); n != INVALID; ++n) {

    ///    if (!d.reached(n)) {

    ///      d.addSource(n);

    ///      d.start();

    ///    }

    ///  }

    ///\endcode

    void run() {

      init();

      for (NodeIt it(*G); it != INVALID; ++it) {

        if (!reached(it)) {

          addSource(it);

          start();

        }

      }

    }

    ///@}

    ///\name Query Functions

    ///(it stops searching when \c t is processed).

    ///

    ///\return \c true if \c t is reachable form \c s.

    bool run(Node s, Node t)

    {

      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));

      if (Base::_pred)

        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

      if (Base::_dist)

        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

      if (Base::_reached)

        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));

      if (Base::_processed)

        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));

      alg.run(s,t);

      if (Base::_path)

        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);

      if (Base::_di)

        *Base::_di = alg.dist(t);

      return alg.reached(t);

      }

    ///Runs DFS algorithm to visit all nodes in the digraph.

    void run()

    {

      run(INVALID);

    }

    template<class T>

    struct SetPredMapBase : public Base {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &) { return 0; };

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

    };

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

    ///the predecessor map.

    ///

    ///\ref named-templ-param "Named parameter" function for setting

    ///the map that stores the predecessor arcs of the nodes.

    template<class T>

    DfsWizard<SetPredMapBase<T> > predMap(const T &t)

    {

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

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

    }

    /// \brief Finds the %DFS path between \c s and \c t.

    /// This method runs the %DFS algorithm from node \c s

    /// in order to compute the DFS path to node \c t

    /// (it stops searching when \c t is processed).

    ///

    /// \return \c true if \c t is reachable form \c s.

    ///

    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is

    /// just a shortcut of the following code.

    ///\code

    ///   d.init();

    ///   d.addSource(s);

    ///   d.start(t);

    ///\endcode

    bool run(Node s,Node t) {

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    /// \brief Runs the algorithm to visit all nodes in the digraph.

    ///

    /// \note <tt>d.run()</tt> is just a shortcut of the following code.

    ///\code

    ///   d.init();

    ///   for (NodeIt n(digraph); n != INVALID; ++n) {

    ///     if (!d.reached(n)) {

    ///       d.addSource(n);

    ///       d.start();

    ///     }

    ///   }

    ///\endcode

    void run() {

      init();

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

        if (!reached(it)) {

          addSource(it);

          start();

        }

      }

    }

    ///@}

    /// \name Query Functions

  ///it can be used easier.

  ///

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

  ///The default type is \ref ListDigraph.

  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  ///the lengths of the arcs.

  ///It is read once for each arc, so the map may involve in

  ///relatively time consuming process to compute the arc lengths if

  ///it is necessary. The default map type is \ref

  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=DijkstraDefaultTraits<GR,LEN> >

#endif

  class Dijkstra {

  public:

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

    typedef typename TR::Digraph Digraph;

    ///The type of the arc lengths.

    ///The type of the map that stores the arc lengths.

    typedef typename TR::LengthMap LengthMap;

    ///\brief The type of the map that stores the predecessor arcs of the

    ///shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

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

    typedef typename TR::ProcessedMap ProcessedMap;

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///The cross reference type used for the current heap.

    typedef typename TR::HeapCrossRef HeapCrossRef;

    ///The heap type used by the algorithm.

    typedef typename TR::Heap Heap;

    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"

    ///of the algorithm.

    typedef typename TR::OperationTraits OperationTraits;

    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

      }

    };

  };

  /// \ingroup graphs

  ///

  /// \brief Digraph using a node set of another digraph or graph and

  /// an own arc set.

  ///

  /// This structure can be used to establish another directed graph

  /// over a node set of an existing one. This class uses the same

  /// Node type as the underlying graph, and each valid node of the

  /// original graph is valid in this arc set, therefore the node

  /// objects of the original graph can be used directly with this

  /// class. The node handling functions (id handling, observing, and

  /// iterators) works equivalently as in the original graph.

  ///

  /// This implementation is based on doubly-linked lists, from each

  /// node the outgoing and the incoming arcs make up lists, therefore

  /// one arc can be erased in constant time. It also makes possible,

  /// that node can be removed from the underlying graph, in this case

  /// all arcs incident to the given node is erased from the arc set.

  ///

  /// \param GR The type of the graph which shares its node set with

  /// this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  template <typename GR>

  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {

    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      Arc arc;

      Parent::firstOut(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstOut(arc, node);

      }

      Parent::firstIn(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstIn(arc, node);

      }

      }

    };

  };

  /// \ingroup graphs

  ///

  /// \brief Graph using a node set of another digraph or graph and an

  /// own edge set.

  ///

  /// This structure can be used to establish another graph over a

  /// node set of an existing one. This class uses the same Node type

  /// as the underlying graph, and each valid node of the original

  /// graph is valid in this arc set, therefore the node objects of

  /// the original graph can be used directly with this class. The

  /// node handling functions (id handling, observing, and iterators)

  /// works equivalently as in the original graph.

  ///

  /// This implementation is based on doubly-linked lists, from each

  /// node the incident edges make up lists, therefore one edge can be

  /// erased in constant time. It also makes possible, that node can

  /// be removed from the underlying graph, in this case all edges

  /// incident to the given node is erased from the arc set.

  ///

  /// \param GR The type of the graph which shares its node set

  /// with this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  template <typename GR>

  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {

    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      Arc arc;

      Parent::firstOut(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstOut(arc, node);

      }

    }

    void clearNodes() {

      Parent::clear();

  /// \ingroup graphs

  ///

  /// \brief Digraph using a node set of another digraph or graph and

  /// an own arc set.

  ///

  /// This structure can be used to establish another directed graph

  /// over a node set of an existing one. This class uses the same

  /// Node type as the underlying graph, and each valid node of the

  /// original graph is valid in this arc set, therefore the node

  /// objects of the original graph can be used directly with this

  /// class. The node handling functions (id handling, observing, and

  /// iterators) works equivalently as in the original graph.

  ///

  /// \param GR The type of the graph which shares its node set with

  /// this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  ///

  /// This implementation is slightly faster than the \c ListArcSet,

  /// because it uses continuous storage for arcs and it uses just

  /// single-linked lists for enumerate outgoing and incoming

  /// arcs. Therefore the arcs cannot be erased from the arc sets.

  ///

  /// \warning If a node is erased from the underlying graph and this

  /// node is the source or target of one arc in the arc set, then

  /// the arc set is invalidated, and it cannot be used anymore. The

  /// validity can be checked with the \c valid() member function.

  template <typename GR>

  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {

    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  protected:

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      if (typename Parent::InArcIt(*this, node) == INVALID &&

          typename Parent::OutArcIt(*this, node) == INVALID) {

        return;

      }

      throw typename NodesImplBase::Notifier::ImmediateDetach();

    }

    void clearNodes() {

      Parent::clear();

    }

  /// \ingroup graphs

  ///

  /// \brief Graph using a node set of another digraph or graph and an

  /// own edge set.

  ///

  /// This structure can be used to establish another graph over a

  /// node set of an existing one. This class uses the same Node type

  /// as the underlying graph, and each valid node of the original

  /// graph is valid in this arc set, therefore the node objects of

  /// the original graph can be used directly with this class. The

  /// node handling functions (id handling, observing, and iterators)

  /// works equivalently as in the original graph.

  ///

  /// \param GR The type of the graph which shares its node set