RhodeCode

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \c PredMap.

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

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

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

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

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

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

    ///Instantiates a \c ReachedMap.

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

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

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a \c DistMap.

    ///

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

    ///\c PredMap type.

    template <class T>

    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {

      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;

    ///

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

    ///\c DistMap type.

    template <class T>

    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {

      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;

    ///

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

    ///\c ReachedMap type.

    template <class T>

    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {

      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;

    ///

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

    ///\c ProcessedMap type.

    template <class T>

    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {

      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;

    ///@{

    ///

    ///\warning \c t should be reached from the root(s).

    ///

    ///must be called before using this function.

    Path path(Node t) const { return Path(*G, *_pred, t); }

    ///

    ///\warning If node \c v is not reached from the root(s), then

    ///the return value of this function is undefined.

    ///must be called before using this function.

    int dist(Node v) const { return (*_dist)[v]; }

    ///This function returns the 'previous arc' of the shortest path

    ///tree for the node \c v, i.e. it returns the last arc of a

    ///shortest path from a root to \c v. It is \c INVALID if \c v

    ///is not reached from the root(s) or if \c v is a root.

    ///

    ///The shortest path tree used here is equal to the shortest path

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    Arc predArc(Node v) const { return (*_pred)[v];}

    ///This function returns the 'previous node' of the shortest path

    ///tree for the node \c v, i.e. it returns the last but one node

    ///if \c v is not reached from the root(s) or if \c v is a root.

    ///

    ///The shortest path tree used here is equal to the shortest path

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    ///predecessor arcs.

    ///

    ///Returns a const reference to the node map that stores the predecessor

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    const PredMap &predMap() const { return *_pred;}

    ///Returns \c true if \c v is reached from the root(s).

    ///

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a PredMap.

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

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

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

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

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

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

    ///Instantiates a ReachedMap.

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

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

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///The type of the shortest paths.

    ///The type of the shortest paths.

    typedef lemon::Path<Digraph> Path;

  };

  /// Default traits class used by BfsWizard

  template<class GR>

  class BfsWizardBase : public BfsWizardDefaultTraits<GR>

  {

    public:

    /// Constructor.

    /// all of the attributes to \c 0.

    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),

                      _dist(0), _path(0), _di(0) {}

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    typedef typename TR::PredMap PredMap;

    typedef typename TR::DistMap DistMap;

    typedef typename TR::ReachedMap ReachedMap;

    typedef typename TR::ProcessedMap ProcessedMap;

    typedef typename TR::Path Path;

  public:

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

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

    {

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

    ///

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

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

    /// \brief Instantiates a ReachedMap.

    ///@{

    ///

    /// Returns \c true if \c v is reached from the root(s).

    ///

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the %DFS paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \c PredMap.

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

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

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

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

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

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

    ///Instantiates a \c ReachedMap.

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

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

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a \c DistMap.

    ///

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

    ///\c PredMap type.

    template <class T>

    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {

      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;

    ///

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

    ///\c DistMap type.

    template <class T>

    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {

      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;

    ///

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

    ///\c ReachedMap type.

    template <class T>

    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {

      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;

    ///

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

    ///\c ProcessedMap type.

    template <class T>

    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {

      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;

    ///@{

    ///

    ///\warning \c t should be reached from the root(s).

    ///

    ///must be called before using this function.

    Path path(Node t) const { return Path(*G, *_pred, t); }

    ///

    ///\warning If node \c v is not reached from the root(s), then

    ///the return value of this function is undefined.

    ///must be called before using this function.

    int dist(Node v) const { return (*_dist)[v]; }

    ///This function returns the 'previous arc' of the %DFS tree for the

    ///node \c v, i.e. it returns the last arc of a %DFS path from a

    ///root(s) or if \c v is a root.

    ///

    ///The %DFS tree used here is equal to the %DFS tree used in

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    Arc predArc(Node v) const { return (*_pred)[v];}

    ///This function returns the 'previous node' of the %DFS

    ///tree for the node \c v, i.e. it returns the last but one node

    ///if \c v is not reached from the root(s) or if \c v is a root.

    ///

    ///The %DFS tree used here is equal to the %DFS tree used in

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    ///predecessor arcs.

    ///

    ///Returns a const reference to the node map that stores the predecessor

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    const PredMap &predMap() const { return *_pred;}

    ///Returns \c true if \c v is reached from the root(s).

    ///

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the %DFS paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a PredMap.

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

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

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

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

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

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

    ///Instantiates a ReachedMap.

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

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

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///The type of the DFS paths.

    ///The type of the DFS paths.

    typedef lemon::Path<Digraph> Path;

  };

  /// Default traits class used by DfsWizard

  template<class GR>

  class DfsWizardBase : public DfsWizardDefaultTraits<GR>

  {

    public:

    /// Constructor.

    /// all of the attributes to \c 0.

    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),

                      _dist(0), _path(0), _di(0) {}

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    typedef typename TR::PredMap PredMap;

    typedef typename TR::DistMap DistMap;

    typedef typename TR::ReachedMap ReachedMap;

    typedef typename TR::ProcessedMap ProcessedMap;

    typedef typename TR::Path Path;

  public:

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

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

    {

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

    ///

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

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

    /// \brief Instantiates a ReachedMap.

    ///@{

    ///

    /// Returns \c true if \c v is reached from the root(s).

    ///

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

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

    typedef LEN LengthMap;

    typedef typename LEN::Value Value;

    /// Operation traits for %Dijkstra algorithm.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \c PredMap.

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

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

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

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

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

    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;

    ///Instantiates a \c DistMap.

  /// \ingroup shortest_path

  ///This class provides an efficient implementation of the %Dijkstra algorithm.

  ///

  ///The arc lengths are passed to the algorithm using a

  ///\ref concepts::ReadMap "ReadMap",

  ///so it is easy to change it to any kind of length.

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

    typedef typename TR::Digraph Digraph;

    typedef typename TR::LengthMap::Value Value;

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

    typedef typename TR::LengthMap LengthMap;

    ///

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

    ///\c PredMap type.

    template <class T>

    struct SetPredMap

      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {

    ///

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

    ///\c DistMap type.

    template <class T>

    struct SetDistMap

      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {

    ///

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

    ///\c ProcessedMap type.

    template <class T>

    struct SetProcessedMap

      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {

    ///

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

    ///\c OperationTraits type.

    template <class T>

    struct SetOperationTraits

      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {

    ///\name Query Functions

    ///The results of the %Dijkstra algorithm can be obtained using these

    ///functions.\n

    ///before using them.

    ///@{

    ///

    ///\warning \c t should be reached from the root(s).

    ///

    ///must be called before using this function.

    Path path(Node t) const { return Path(*G, *_pred, t); }

    ///

    ///\warning If node \c v is not reached from the root(s), then

    ///the return value of this function is undefined.

    ///must be called before using this function.

    Value dist(Node v) const { return (*_dist)[v]; }

    ///This function returns the 'previous arc' of the shortest path

    ///tree for the node \c v, i.e. it returns the last arc of a

    ///shortest path from a root to \c v. It is \c INVALID if \c v

    ///is not reached from the root(s) or if \c v is a root.

    ///

    ///The shortest path tree used here is equal to the shortest path

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    Arc predArc(Node v) const { return (*_pred)[v]; }

    ///This function returns the 'previous node' of the shortest path

    ///tree for the node \c v, i.e. it returns the last but one node

    ///if \c v is not reached from the root(s) or if \c v is a root.

    ///

    ///The shortest path tree used here is equal to the shortest path

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    ///predecessor arcs.

    ///

    ///Returns a const reference to the node map that stores the predecessor

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    const PredMap &predMap() const { return *_pred;}

    ///Returns \c true if \c v is reached from the root(s).

    ///

    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==

                                          Heap::POST_HEAP; }

    ///It may be decreased in the following processes.

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

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

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

    typedef LEN LengthMap;

    typedef typename LEN::Value Value;

    /// Operation traits for Dijkstra algorithm.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a PredMap.

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

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

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

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

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

    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;

    ///Instantiates a DistMap.

    ///The type of the shortest paths.

    ///The type of the shortest paths.

    typedef lemon::Path<Digraph> Path;

  };

  /// Default traits class used by DijkstraWizard

  template<typename GR, typename LEN>

  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>

  {

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    typedef typename TR::LengthMap LengthMap;

    typedef typename LengthMap::Value Value;

    typedef typename TR::PredMap PredMap;

    typedef typename TR::DistMap DistMap;

    typedef typename TR::ProcessedMap ProcessedMap;

    typedef typename TR::Path Path;

    typedef typename TR::Heap Heap;

  public:

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

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

    };

    ///

    template<class T>

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

    {

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

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

    };

    ///

    template<class T>

    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)

    {

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

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

    };

    ///

    template<class T>

    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)

    {

      typedef T Path;

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

    };

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

    ///for getting the shortest path to the target node.

    ///

  /// order of Dfs algorithm, as the following examples show.

  /// \code

  ///   std::vector<Node> v;

  /// \endcode

  /// \code

  ///   std::vector<Node> v(countNodes(g));

  /// \endcode

  ///

  /// \note The container of the iterator must contain enough space