RhodeCode

    ///arcs of the shortest paths.

    ///

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

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

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

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

    ///\param g is the digraph, to which

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

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

    ///\param g is the digraph, to which

    static ReachedMap *createReachedMap(const Digraph &g)

    {

      return new ReachedMap(g);

    }

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

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

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

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

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

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

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

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

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

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    template <class T>

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

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

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

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

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

    };

      {

        return new ProcessedMap(g);

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///If you don't set it explicitly, it will be automatically allocated.

    struct SetStandardProcessedMap :

      public Bfs< Digraph, SetStandardProcessedMapTraits > {

      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;

    };

#ifdef DOXYGEN

  /// \brief Visitor class for BFS.

  ///

  /// This class defines the interface of the BfsVisit events, and

  /// it could be the base of a real visitor class.

  struct BfsVisitor {

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    /// \brief Called for the source node(s) of the BFS.

    ///

    /// This function is called for the source node(s) of the BFS.

    void start(const Node& node) {}

    ///

    /// This function is called when an arc is examined but its target node is

    /// already discovered.

    void examine(const Arc& arc) {}

  };

#else

  struct BfsVisitor {

    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&) {}

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  struct BfsVisitDefaultTraits {

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

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

    }

  };

  /// \ingroup search

  ///

  ///

  /// with visitor interface.

  ///

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

  ///

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

  /// algorithm. The default traits class is

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a BFS visit traits class.

#ifdef DOXYGEN

#else

#endif

  class BfsVisit {

  public:

    ///The traits class.

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

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

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

    typedef typename Traits::ReachedMap ReachedMap;

  private:

      return operator=<ArrayMap>(cmap);

    }

    // \brief Template assign operator.

    //

    // concecpt and could be indiced by the current item set of

    // the NodeMap. In this case the value for each item

    // is assigned by the value of the given ReadMap.

    template <typename CMap>

    ArrayMap& operator=(const CMap& cmap) {

      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();

      return operator=<VectorMap>(cmap);

    }

    // \brief Template assign operator.

    //

    // concecpt and could be indiced by the current item set of

    // the NodeMap. In this case the value for each item

    // is assigned by the value of the given ReadMap.

    template <typename CMap>

    VectorMap& operator=(const CMap& cmap) {

      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();

///

namespace lemon {

  /// \brief Default traits class of Circulation class.

  ///

  /// Default traits class of Circulation class.

  struct CirculationDefaultTraits {

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

    /// \brief The type of the map that stores the circulation lower

    /// bound.

    ///

    /// The type of the map that stores the circulation lower bound.

    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

    /// \brief The type of the map that stores the circulation upper

    /// bound.

    ///

    /// The type of the map that stores the circulation upper bound.

    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.

    /// \brief The type of the map that stores the lower bound for

    /// the supply of the nodes.

    ///

    /// The type of the map that stores the lower bound for the supply

    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"

    /// concept.

    /// \brief The type of the flow values.

    typedef typename DeltaMap::Value Value;

    /// \brief The type of the map that stores the flow values.

    ///

     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$

     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.

     Thus a feasible solution for the

     \ref min_cost_flow "minimum cost flow" problem can be calculated

     in this way.

     for the supply of the nodes. The default map type is

  */

#ifdef DOXYGEN

#else

#endif

  class Circulation {

  public:

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

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

    typedef typename Traits::Digraph Digraph;

    ///The type of the flow values.

    typedef typename Traits::Value Value;

    /// The type of the lower bound capacity map.

      };

    };

    /// \brief An empty base directed graph class.

    ///

    /// This class provides the minimal set of features needed for a

    /// conform to this base directed graph. It just provides types

    /// for nodes and arcs and functions to get the source and the

    /// target of the arcs.

    class BaseDigraphComponent {

    public:

    };

    /// \brief An empty base undirected graph class.

    ///

    /// This class provides the minimal set of features needed for an

    /// undirected graph structure. All undirected graph concepts have

    /// nodes, arcs and edges and functions to get the

    /// source and the target of the arcs and edges,

    /// conversion from arcs to edges and function to get

    /// both direction of the edges.

    class BaseGraphComponent : public BaseDigraphComponent {

    public:

    };

    /// \brief An empty idable base digraph class.

    ///

    /// This class provides beside the core digraph features

    /// core id functions for the digraph structure.

    /// The id's are unique and immutable.

    template <typename _Base = BaseDigraphComponent>

    class IDableDigraphComponent : public _Base {

    public:

      typedef _Base Base;

    };

    /// \brief An empty idable base undirected graph class.

    ///

    /// This class provides beside the core undirected graph features

    /// core id functions for the undirected graph structure.  The

    /// concept.  The id's are unique and immutable.

    template <typename _Base = BaseGraphComponent>

    class IDableGraphComponent : public IDableDigraphComponent<_Base> {

    public:

      typedef _Base Base;

    ///arcs of the %DFS paths.

    ///

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

    ///arcs of the %DFS paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

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

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

    ///\param g is the digraph, to which

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

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

    ///\param g is the digraph, to which

    static ReachedMap *createReachedMap(const Digraph &g)

    {

      return new ReachedMap(g);

    }

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

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

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

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

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

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

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

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

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

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    template <class T>

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

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

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

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

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

    };

      static ProcessedMap *createProcessedMap(const Digraph &g)

      {

        return new ProcessedMap(g);

      }

    };

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

    ///

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

    ///If you don't set it explicitly, it will be automatically allocated.

    struct SetStandardProcessedMap :

      public Dfs< Digraph, SetStandardProcessedMapTraits > {

      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;

    };

#ifdef DOXYGEN

  /// \brief Visitor class for DFS.

  ///

  /// This class defines the interface of the DfsVisit events, and

  /// it could be the base of a real visitor class.

  struct DfsVisitor {

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    /// \brief Called for the source node of the DFS.

    ///

    /// This function is called for the source node of the DFS.

    void start(const Node& node) {}

    /// \brief Called when the DFS steps back on an arc.

    ///

    /// This function is called when the DFS steps back on an arc.

    void backtrack(const Arc& arc) {}

  };

#else

  struct DfsVisitor {

    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&) {}

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

  struct DfsVisitDefaultTraits {

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

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

    }

  };

  /// \ingroup search

  ///

  ///

  /// with visitor interface.

  ///

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

  ///

  /// does not observe the DFS events. If you want to observe the DFS

  /// events, you should implement your own visitor class.

  /// algorithm. The default traits class is

  /// See \ref DfsVisitDefaultTraits for the documentation of

  /// a DFS visit traits class.

#ifdef DOXYGEN

#else

#endif

  class DfsVisit {

  public:

    ///The traits class.

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

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

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

    typedef typename Traits::ReachedMap ReachedMap;

  private:

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

    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.

    typedef LM LengthMap;

    ///The type of the length of the arcs.

    typedef typename LM::Value Value;

    /// This class defines the operations that are used in the algorithm.

    /// \see DijkstraDefaultOperationTraits

    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;

    /// The cross reference type used by the heap.

    /// The cross reference type used by the heap.

    /// Usually it is \c Digraph::NodeMap<int>.

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

    ///This function instantiates a \ref HeapCrossRef.

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

    /// \ref HeapCrossRef.

    static HeapCrossRef *createHeapCrossRef(const Digraph &g)

    {

      return new HeapCrossRef(g);

    }

    ///The heap type used by the Dijkstra algorithm.

    ///

    ///\sa BinHeap

    ///\sa Dijkstra

    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;

    ///This function instantiates a \ref Heap.

    static Heap *createHeap(HeapCrossRef& r)

    {

      return new Heap(r);

    }

    ///arcs of the shortest paths.

    ///

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

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

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

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///By default it is a NullMap.

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

    ///\param g is the digraph, to which

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

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

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

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

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

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

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

    typedef typename TR::OperationTraits OperationTraits;

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

    typedef TR Traits;

  private:

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *G;

    //Pointer to the length map.

    //Pointer to the map of predecessors arcs.

    PredMap *_pred;

    //Indicates if _pred is locally allocated (true) or not.

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetPredMap

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

      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetDistMap

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

      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;

    };

      {

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

        return 0; // ignore warnings

      }

    };

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

    ///

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

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetProcessedMap

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

      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;

    };

      static ProcessedMap *createProcessedMap(const Digraph &g)

      {

        return new ProcessedMap(g);

      }

    };

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

    ///

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

    ///If you don't set it explicitly, it will be automatically allocated.

    struct SetStandardProcessedMap

      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {

      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >

      Create;

    };

    };

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

    ///\c OperationTraits type

    ///

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

    template <class T>

    struct SetOperationTraits

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

      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

  public:

    ///Constructor.

    ///Constructor.

      _pred(NULL), local_pred(false),

      _dist(NULL), local_dist(false),

      _processed(NULL), local_processed(false),

      _heap_cross_ref(NULL), local_heap_cross_ref(false),

      _heap(NULL), local_heap(false)

    { }