RhodeCode

    static PredMap *createPredMap(const GR& g) {

      return new PredMap(g);

    }

    /// \brief 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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    /// \brief Instantiates a \c DistMap.

    ///

    /// This function instantiates a \ref DistMap. 

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

    /// \ref DistMap.

    static DistMap *createDistMap(const GR& g) {

      return new DistMap(g);

    }

  };

  /// \brief %BellmanFord algorithm class.

  ///

  /// \ingroup shortest_path

  /// This class provides an efficient implementation of the Bellman-Ford 

  /// algorithm. The maximum time complexity of the algorithm is

  /// <tt>O(ne)</tt>.

  ///

  /// The Bellman-Ford algorithm solves the single-source shortest path

  /// problem when the arcs can have negative lengths, but the digraph

  /// should not contain directed cycles with negative total length.

  /// If all arc costs are non-negative, consider to use the Dijkstra

  /// algorithm instead, since it is more efficient.

  ///

  /// 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 length values is determined by the

  /// \ref concepts::ReadMap::Value "Value" type of the length map.

  ///

  /// There is also a \ref bellmanFord() "function-type interface" for the

  /// Bellman-Ford algorithm, which is convenient in the simplier cases and

  /// 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. 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=BellmanFordDefaultTraits<GR,LEN> >

#endif

  class BellmanFord {

  public:

    ///The type of the underlying digraph.

    typedef typename TR::Digraph Digraph;

    /// \brief The type of the arc lengths.

    typedef typename TR::LengthMap::Value Value;

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

    typedef typename TR::LengthMap LengthMap;

    /// \brief The type of the map that stores the last

    /// arcs of the shortest paths.

    typedef typename TR::PredMap PredMap;

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

    typedef typename TR::DistMap DistMap;

    /// The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///\brief The \ref BellmanFordDefaultOperationTraits

    /// "operation traits class" of the algorithm.

    typedef typename TR::OperationTraits OperationTraits;

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

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    // Pointer to the underlying digraph.

    const Digraph *_gr;

    // Pointer to the length map

    const LengthMap *_length;

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

    typedef typename Base::Digraph::Node Node;

    // Pointer to the underlying digraph.

    void *_graph;

    // Pointer to the length map

    void *_length;

    // Pointer to the map of predecessors arcs.

    void *_pred;

    // Pointer to the map of distances.

    void *_dist;

    //Pointer to the shortest path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    void *_di;

    public:

    /// Constructor.

    /// This constructor does not require parameters, it initiates

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

    BellmanFordWizardBase() :

      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}

    /// Constructor.

    /// This constructor requires two parameters,

    /// others are initiated to \c 0.

    /// \param gr The digraph the algorithm runs on.

    /// \param len The length map.

    BellmanFordWizardBase(const GR& gr, 

			  const LEN& len) :

      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 

      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 

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

  };

  /// \brief Auxiliary class for the function-type interface of the

  /// \ref BellmanFord "Bellman-Ford" algorithm.

  ///

  /// This auxiliary class is created to implement the

  /// \ref bellmanFord() "function-type interface" of the

  /// \ref BellmanFord "Bellman-Ford" algorithm.

  /// It does not have own \ref run() method, it uses the

  /// functions and features of the plain \ref BellmanFord.

  ///

  /// This class should only be used through the \ref bellmanFord()

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

  template<class TR>

  class BellmanFordWizard : public TR {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt ArcIt;

    typedef typename TR::LengthMap LengthMap;

    typedef typename LengthMap::Value Value;

    typedef typename TR::PredMap PredMap;

    typedef typename TR::DistMap DistMap;

    typedef typename TR::Path Path;

  public:

    /// Constructor.

    BellmanFordWizard() : TR() {}

    /// \brief Constructor that requires parameters.

    ///

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    /// \param gr The digraph the algorithm runs on.

    /// \param len The length map.

    BellmanFordWizard(const Digraph& gr, const LengthMap& len) 

      : TR(gr, len) {}

    /// \brief Copy constructor

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

    ~BellmanFordWizard() {}

    /// \brief Runs the Bellman-Ford algorithm from the given source node.

    ///    

    /// This method runs the Bellman-Ford algorithm from the given source

    /// node in order to compute the shortest path to each node.

    void run(Node s) {

      BellmanFord<Digraph,LengthMap,TR> 

	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 

           *reinterpret_cast<const LengthMap*>(Base::_length));

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

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

      bf.run(s);

    }

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

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

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

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

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

    ///Instantiates a \c ReachedMap.

    ///This function instantiates a \ref ReachedMap.

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

    ///we would like to define the \ref ReachedMap.

    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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a \c DistMap.

    ///This function instantiates a \ref DistMap.

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

    ///\ref DistMap.

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

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

  ///

  ///There is also a \ref bfs() "function-type interface" for the BFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

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

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

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

    typedef typename TR::Digraph Digraph;

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

    typedef typename TR::ReachedMap ReachedMap;

    ///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 \ref BfsDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *G;

    //Pointer to the map of predecessor arcs.

    PredMap *_pred;

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

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

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

    bool local_dist;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

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

    typedef BfsWizardDefaultTraits<GR> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

    //Pointer to the map of reached nodes.

    void *_reached;

    //Pointer to the map of processed nodes.

    void *_processed;

    //Pointer to the map of predecessors arcs.

    void *_pred;

    //Pointer to the map of distances.

    void *_dist;

    //Pointer to the shortest path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    int *_di;

    public:

    /// Constructor.

    /// This constructor does not require parameters, it initiates

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

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

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

    /// Constructor.

    /// This constructor requires one parameter,

    /// others are initiated to \c 0.

    /// \param g The digraph the algorithm runs on.

    BfsWizardBase(const GR &g) :

      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),

      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}

  };

  /// Auxiliary class for the function-type interface of BFS algorithm.

  /// This auxiliary class is created to implement the

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

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Bfs.

  ///

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

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

  template<class TR>

  class BfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    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:

    /// Constructor.

    BfsWizard() : TR() {}

    /// Constructor that requires parameters.

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    /// \param g The digraph the algorithm runs on.

    BfsWizard(const Digraph &g) :

      TR(g) {}

    ///Copy constructor

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

    ~BfsWizard() {}

    ///Runs BFS algorithm from the given source node.

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

    ///in order to compute the shortest path to each node.

    void run(Node s)

    {

      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)

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

  template<class GR>

  struct BfsVisitDefaultTraits {

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

    typedef GR Digraph;

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

    ///

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

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

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

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a ReachedMap.

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

    /// we would like to define the ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief BFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the BFS algorithm

  /// with visitor interface.

  ///

  /// The BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// the member functions of the \c Visitor class on every BFS event.

  ///

  /// This interface of the BFS algorithm should be used in special cases

  /// when extra actions have to be performed in connection with certain

  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()

  /// instead.

  ///

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

  /// The default type is \ref ListDigraph.

  /// The value of GR is not used directly by \ref BfsVisit,

  /// it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which

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

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

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = BfsVisitor<GR>,

            typename TR = BfsVisitDefaultTraits<GR> >

#endif

  class BfsVisit {

  public:

    ///The traits class.

    typedef TR Traits;

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

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    typedef VS Visitor;

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

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *_digraph;

    //Pointer to the visitor object.

    Visitor *_visitor;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

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

    bool local_reached;

    std::vector<typename Digraph::Node> _list;

    int _list_front, _list_back;

    //Creates the maps if necessary.

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

namespace lemon {

  /// \brief Default traits class of CapacityScaling algorithm.

  ///

  /// Default traits class of CapacityScaling algorithm.

  /// \tparam GR Digraph type.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values. By default it is \c int.

  /// \tparam C The number type used for costs and potentials.

  /// By default it is the same as \c V.

  template <typename GR, typename V = int, typename C = V>

  struct CapacityScalingDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

    /// \brief The type of the heap used for internal Dijkstra computations.

    ///

    /// The type of the heap used for internal Dijkstra computations.

    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,

    /// its priority type must be \c Cost and its cross reference type

    /// must be \ref RangeMap "RangeMap<int>".

    typedef BinHeap<Cost, RangeMap<int> > Heap;

  };

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the Capacity Scaling algorithm for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CapacityScaling implements the capacity scaling version

  /// of the successive shortest path algorithm for finding a

  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,

  /// \ref edmondskarp72theoretical. It is an efficient dual

  /// solution method.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CapacityScalingDefaultTraits<GR, V, C> >

#endif

  class CapacityScaling

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// The type of the heap used for internal Dijkstra computations

    typedef typename TR::Heap Heap;

    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

      /// upper bound. It means that the objective function is unbounded

      /// on that arc, however, note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

     The exact formulation of this problem is the following.

     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$

     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and

     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$

     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$

     denotes the signed supply values of the nodes.

     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

     \f$-sup(u)\f$ demand.

     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$

     solution of the following problem.

     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)

     \geq sup(u) \quad \forall u\in V, \f]

     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]

     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

     zero or negative in order to have a feasible solution (since the sum

     of the expressions on the left-hand side of the inequalities is zero).

     It means that the total demand must be greater or equal to the total

     supply and all the supplies have to be carried out from the supply nodes,

     but there could be demands that are not satisfied.

     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

     constraints have to be satisfied with equality, i.e. all demands

     have to be satisfied and all supplies have to be used.

     If you need the opposite inequalities in the supply/demand constraints

     (i.e. the total demand is less than the total supply and all the demands

     have to be satisfied while there could be supplies that are not used),

     then you could easily transform the problem to the above form by reversing

     the direction of the arcs and taking the negative of the supply values

     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).

     This algorithm either calculates a feasible circulation, or provides

     a \ref barrier() "barrier", which prooves that a feasible soultion

     cannot exist.

     Note that this algorithm also provides a feasible solution for the

     \ref min_cost_flow "minimum cost flow problem".

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

     \tparam LM The type of the lower bound map. The default

     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

     \tparam UM The type of the upper bound (capacity) map.

     The default map type is \c LM.

     \tparam SM The type of the supply map. The default map type is

     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".

  */

#ifdef DOXYGEN

template< typename GR,

          typename LM,

          typename UM,

          typename SM,

          typename TR >

#else

template< typename GR,

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

          typename UM = LM,

          typename SM = typename GR::template NodeMap<typename UM::Value>,

          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >

#endif

  class Circulation {

  public:

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

    typedef TR Traits;

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

    typedef typename Traits::Digraph Digraph;

    ///The type of the flow and supply values.

    typedef typename Traits::Value Value;

    ///The type of the lower bound map.

    typedef typename Traits::LowerMap LowerMap;

    ///The type of the upper bound (capacity) map.

    typedef typename Traits::UpperMap UpperMap;

    ///The type of the supply map.

    typedef typename Traits::SupplyMap SupplyMap;

    ///The type of the flow map.

    typedef typename Traits::FlowMap FlowMap;

    ///The type of the elevator.

    typedef typename Traits::Elevator Elevator;

    ///The type of the tolerance.

    typedef typename Traits::Tolerance Tolerance;

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    const Digraph &_g;

    int _node_num;

    const LowerMap *_lo;

    const UpperMap *_up;

    const SupplyMap *_supply;

    /// The type of the arc costs

    typedef C Cost;

    /// \brief The large cost type used for internal computations

    ///

    /// The large cost type used for internal computations.

    /// It is \c long \c long if the \c Cost type is integer,

    /// otherwise it is \c double.

    /// \c Cost must be convertible to \c LargeCost.

    typedef double LargeCost;

  };

  // Default traits class for integer cost types

  template <typename GR, typename V, typename C>

  struct CostScalingDefaultTraits<GR, V, C, true>

  {

    typedef GR Digraph;

    typedef V Value;

    typedef C Cost;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeCost;

#else

    typedef long LargeCost;

#endif

  };

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the Cost Scaling algorithm for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CostScaling implements a cost scaling algorithm that performs

  /// push/augment and relabel operations for finding a \ref min_cost_flow

  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,

  /// \ref goldberg97efficient, \ref bunnagel98efficient. 

  /// It is a highly efficient primal-dual solution method, which

  /// can be viewed as the generalization of the \ref Preflow

  /// "preflow push-relabel" algorithm for the maximum flow problem.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

  ///

  /// \note %CostScaling provides three different internal methods,

  /// from which the most efficient one is used by default.

  /// For more information, see \ref Method.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CostScalingDefaultTraits<GR, V, C> >

#endif

  class CostScaling

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// \brief The large cost type

    ///

    /// The large cost type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeCost LargeCost;

    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

      /// upper bound. It means that the objective function is unbounded

      /// on that arc, however, note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

    /// \brief Constants for selecting the internal method.

    ///

    /// Enum type containing constants for selecting the internal method

    /// for the \ref run() function.

    ///

    /// \ref CostScaling provides three internal methods that differ mainly

    /// in their base operations, which are used in conjunction with the

    /// relabel operation.

    /// By default, the so called \ref PARTIAL_AUGMENT

    /// "Partial Augment-Relabel" method is used, which proved to be

    /// the most efficient and the most robust on various test inputs.

    /// However, the other methods can be selected using the \ref run()

    /// function with the proper parameter.

    enum Method {

      /// Local push operations are used, i.e. flow is moved only on one

      /// admissible arc at once.

      PUSH,

      /// Augment operations are used, i.e. flow is moved on admissible

      /// paths from a node with excess to a node with deficit.

      AUGMENT,

      /// Partial augment operations are used, i.e. flow is moved on 

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

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

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

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

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

    ///Instantiates a \c ReachedMap.

    ///This function instantiates a \ref ReachedMap.

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

    ///we would like to define the \ref ReachedMap.

    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 conform to the \ref concepts::WriteMap "WriteMap" concept.

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

    ///Instantiates a \c DistMap.

    ///This function instantiates a \ref DistMap.

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

    ///\ref DistMap.

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

  ///%DFS algorithm class.

  ///\ingroup search

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

  ///

  ///There is also a \ref dfs() "function-type interface" for the DFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

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

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=DfsDefaultTraits<GR> >

#endif

  class Dfs {

  public:

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

    typedef typename TR::Digraph Digraph;

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

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

    typedef typename TR::ReachedMap ReachedMap;

    ///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 \ref DfsDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *G;

    //Pointer to the map of predecessor arcs.

    PredMap *_pred;

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

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

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

    bool local_dist;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

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

    typedef DfsWizardDefaultTraits<GR> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

    //Pointer to the map of reached nodes.

    void *_reached;

    //Pointer to the map of processed nodes.

    void *_processed;

    //Pointer to the map of predecessors arcs.

    void *_pred;

    //Pointer to the map of distances.

    void *_dist;

    //Pointer to the DFS path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    int *_di;

    public:

    /// Constructor.

    /// This constructor does not require parameters, it initiates

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

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

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

    /// Constructor.

    /// This constructor requires one parameter,

    /// others are initiated to \c 0.

    /// \param g The digraph the algorithm runs on.

    DfsWizardBase(const GR &g) :

      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),

      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}

  };

  /// Auxiliary class for the function-type interface of DFS algorithm.

  /// This auxiliary class is created to implement the

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

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Dfs.

  ///

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

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

  template<class TR>

  class DfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    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:

    /// Constructor.

    DfsWizard() : TR() {}

    /// Constructor that requires parameters.

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    /// \param g The digraph the algorithm runs on.

    DfsWizard(const Digraph &g) :

      TR(g) {}

    ///Copy constructor

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

    ~DfsWizard() {}

    ///Runs DFS algorithm from the given source node.

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

    ///in order to compute the DFS path to each node.

    void run(Node s)

    {

      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)

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

  template<class GR>

  struct DfsVisitDefaultTraits {

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

    typedef GR Digraph;

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

    ///

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

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

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

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a ReachedMap.

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

    /// we would like to define the ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief DFS algorithm class with visitor interface.