RhodeCode

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

    ///Instantiates a PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///PredMap.

    static PredMap *createPredMap(const Digraph &g)

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

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

    ///Instantiates a ReachedMap.

  ///used easier.

  ///

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

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    typedef TR Traits;

  private:

    typedef Bfs Create;

    ///@{

    ///

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

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

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

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

    ///ProcessedMap type.

    template <class T>

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

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

    ///Sets the map that stores the predecessor arcs.

    ///Sets the map that stores the predecessor arcs.

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

    Bfs &predMap(PredMap &m)

    {

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

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

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

    Bfs &reachedMap(ReachedMap &m)

    {

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

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

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

    Bfs &processedMap(ProcessedMap &m)

    {

    ///Sets the map that stores the distances of the nodes calculated by

    ///the algorithm.

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

    Bfs &distMap(DistMap &m)

    {

  public:

    ///@{

    ///Initializes the internal data structures.

    void init()

    {

      create_maps();

      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;

    }

    bool emptyQueue() const { return _queue_tail==_queue_head; }

    ///Returns the number of the nodes to be processed.

    int queueSize() const { return _queue_head-_queue_tail; }

    ///Executes the algorithm.

    ///@}

    ///\name Query Functions

    ///functions.\n

    ///@{

    ///Returns the shortest path to a node.

    ///

    ///

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

    ///The distance of a node from the root(s).

    ///Returns the distance of a node from the root(s).

    ///

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

    ///

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

    ///Returns the 'previous arc' of the shortest path tree for a node.

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

    ///

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

    ///tree used in \ref predNode().

    ///

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

    ///Returns the 'previous node' of the shortest path tree for a node.

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

    ///

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

    ///tree used in \ref predArc().

    ///

    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:

                                  G->source((*_pred)[v]); }

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

    ///of the nodes calculated by the algorithm.

    ///

    ///must be called before using this function.

    const DistMap &distMap() const { return *_dist;}

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

    ///arcs, which form the shortest path tree.

    ///

    ///must be called before using this function.

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

    ///must be called before using this function.

    bool reached(Node v) const { return (*_reached)[v]; }

  /// This auxiliary class is created to implement the

  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.

  ///

  /// This class should only be used through the \ref bfs() function,

  /// which makes it easier to use the algorithm.

  ///  // Compute shortest path from s to t

  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);

  ///\endcode

  ///to the end of the parameter list.

  ///\sa BfsWizard

  ///\sa Bfs

    typedef BfsVisit Create;

    ///@{

    template <class T>

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

    ///

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

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

    BfsVisit &reachedMap(ReachedMap &m) {

      if(local_reached) {

  public:

    /// @{

    ///@}

    /// \name Query Functions

    /// functions.\n

    ///@{

    ///

    /// must be called before using this function.

    bool reached(Node v) { return (*_reached)[v]; }

  ///used easier.

  ///

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

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    typedef TR Traits;

  private:

    ///

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

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

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

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

    ///ProcessedMap type.

    template <class T>

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

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

    ///Sets the map that stores the predecessor arcs.

    ///Sets the map that stores the predecessor arcs.

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

    Dfs &predMap(PredMap &m)

    {

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

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

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

    Dfs &reachedMap(ReachedMap &m)

    {

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

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

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

    Dfs &processedMap(ProcessedMap &m)

    {

    ///Sets the map that stores the distances of the nodes calculated by

    ///the algorithm.

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

    Dfs &distMap(DistMap &m)

    {

  public:

    ///@{

    ///Initializes the internal data structures.

    void init()

    {

      create_maps();

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

    ///

    void addSource(Node s)

    {

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

      return _stack_head>=0?_stack[_stack_head]:INVALID;

    }

    bool emptyQueue() const { return _stack_head<0; }

    ///Returns the number of the nodes to be processed.

    int queueSize() const { return _stack_head+1; }

    ///Executes the algorithm.

    ///%DFS path to each node.

    ///

    ///The algorithm computes

    ///

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

    ///\code

    ///@}

    ///\name Query Functions

    ///functions.\n

    ///@{

    ///Returns the DFS path to a node.

    ///

    ///

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

    ///

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

    ///

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

    ///Returns the 'previous arc' of the %DFS tree for a node.

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

    ///

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

    ///\ref predNode().

    ///

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

    ///Returns the 'previous node' of the %DFS tree.

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

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

    ///

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

    ///\ref predArc().

    ///

    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:

                                  G->source((*_pred)[v]); }

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

    ///distances of the nodes calculated by the algorithm.

    ///

    ///must be called before using this function.

    const DistMap &distMap() const { return *_dist;}

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

    ///arcs, which form the DFS tree.

    ///

    ///must be called before using this function.

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

    ///must be called before using this function.

    bool reached(Node v) const { return (*_reached)[v]; }

  /// This auxiliary class is created to implement the

  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.

  ///

  /// This class should only be used through the \ref dfs() function,

  /// which makes it easier to use the algorithm.

  ///  // Compute the DFS path from s to t

  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);

  ///\endcode

  ///to the end of the parameter list.

  ///\sa DfsWizard

  ///\sa Dfs

    typedef DfsVisit Create;

    ///@{

    template <class T>

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

    ///

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

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

    DfsVisit &reachedMap(ReachedMap &m) {

      if(local_reached) {

  public:

    /// @{

      }

    }

    ///

    ///

    void addSource(Node s)

    {

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

    /// compute the %DFS path to each node.

    ///

    /// The algorithm computes

    ///

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

    ///\code

    ///@}

    /// \name Query Functions

    /// functions.\n

    ///@{

    ///

    /// must be called before using this function.

    bool reached(Node v) { return (*_reached)[v]; }

  ///it can be used easier.

  ///

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

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

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

#ifdef DOXYGEN

  template <typename GR, typename LM, typename TR>

#else

    ///The operation traits class.

    typedef typename TR::OperationTraits OperationTraits;

    typedef TR Traits;

  private:

    ///

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

    ///PredMap type.

    template <class T>

    struct SetPredMap

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

    ///

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

    ///DistMap type.

    template <class T>

    struct SetDistMap

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

    ///

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

    ///ProcessedMap type.

    template <class T>

    struct SetProcessedMap

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

      }

    };

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

    ///

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

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetHeap

      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {

      }

    };

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

    ///

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

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetStandardHeap

      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {

    ///Sets the map that stores the predecessor arcs.

    ///Sets the map that stores the predecessor arcs.

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

    Dijkstra &predMap(PredMap &m)

    {

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

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

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

    Dijkstra &processedMap(ProcessedMap &m)

    {

    ///Sets the map that stores the distances of the nodes calculated by the

    ///algorithm.

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

    Dijkstra &distMap(DistMap &m)

    {

    ///Sets the heap and the cross reference used by algorithm.

    ///Sets the heap and the cross reference used by algorithm.

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

    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)

    {

  public:

    ///@{

    ///Initializes the internal data structures.

    void init()

    {

      create_maps();

      return !_heap->empty()?_heap->top():INVALID;

    }

    bool emptyQueue() const { return _heap->empty(); }

    int queueSize() const { return _heap->size(); }

    ///Executes the algorithm.

    ///@}

    ///\name Query Functions

    ///functions.\n

    ///@{

    ///Returns the shortest path to a node.