/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

     ///

     ///

     /// The type used for storing the found arc-disjoint paths.

     /// The type used for storing the found arc-disjoint paths.

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

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

     /// and it must have an \c addBack() function.

     /// and it must have an \c addBack() function.

     typedef lemon::Path<Digraph> Path;

     typedef lemon::Path<Digraph> Path;

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

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

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

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

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

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

     ///

     ///

       const FlowMap &_flow;

       const FlowMap &_flow;

       PotentialMap &_pi;

       PotentialMap &_pi;

       PredMap &_pred;

       PredMap &_pred;

       Node _s;

       Node _s;

       Node _t;

       Node _t;

       PotentialMap _dist;

       PotentialMap _dist;

       std::vector<Node> _proc_nodes;

       std::vector<Node> _proc_nodes;

     public:

     public:

       // Constructor

       // Constructor

       ResidualDijkstra(Suurballe &srb) :

       ResidualDijkstra(Suurballe &srb) :

         _graph(srb._graph), _length(srb._length),

         _graph(srb._graph), _length(srb._length),

         _s(srb._s), _t(srb._t), _dist(_graph) {}

         _s(srb._s), _t(srb._t), _dist(_graph) {}

       // Run the algorithm and return true if a path is found

       // Run the algorithm and return true if a path is found

       // from the source node to the target node.

       // from the source node to the target node.

       bool run(int cnt) {

       bool run(int cnt) {

         return cnt == 0 ? startFirst() : start();

         return cnt == 0 ? startFirst() : start();

       }

       }

     private:

     private:

       // Execute the algorithm for the first time (the flow and potential

       // Execute the algorithm for the first time (the flow and potential

       // functions have to be identically zero).

       // functions have to be identically zero).

       bool startFirst() {

       bool startFirst() {

         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);

         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);

         Heap heap(heap_cross_ref);

         Heap heap(heap_cross_ref);

     template <typename T>

     template <typename T>

     struct SetPath

     struct SetPath

       : public Suurballe<GR, LEN, SetPathTraits<T> > {

       : public Suurballe<GR, LEN, SetPathTraits<T> > {

       typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;

       typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;

     };

     };

     template <typename H, typename CR>

     template <typename H, typename CR>

     struct SetHeapTraits : public Traits {

     struct SetHeapTraits : public Traits {

       typedef H Heap;

       typedef H Heap;

       typedef CR HeapCrossRef;

       typedef CR HeapCrossRef;

     };

     };

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

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

     /// \c Heap and \c HeapCrossRef types.

     /// \c Heap and \c HeapCrossRef types.

     ///

     ///

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

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

     /// They will be used for internal Dijkstra computations.

     /// They will be used for internal Dijkstra computations.

     /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"

     /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"

     /// concept and its priority type must be \c Length.

     /// concept and its priority type must be \c Length.

     template <typename H,

     template <typename H,

               typename CR = typename Digraph::template NodeMap<int> >

               typename CR = typename Digraph::template NodeMap<int> >

     std::vector<Path> _paths;

     std::vector<Path> _paths;

     int _path_num;

     int _path_num;

     // The pred arc map

     // The pred arc map

     PredMap _pred;

     PredMap _pred;

     // Data for full init

     // Data for full init

     PotentialMap *_init_dist;

     PotentialMap *_init_dist;

     PredMap *_init_pred;

     PredMap *_init_pred;

     bool _full_init;

     bool _full_init;

         ::template SetDistMap<PotentialMap>

         ::template SetDistMap<PotentialMap>

         ::template SetPredMap<PredMap>

         ::template SetPredMap<PredMap>

         ::Create dijk(_graph, _length);

         ::Create dijk(_graph, _length);

       dijk.distMap(*_init_dist).predMap(*_init_pred);

       dijk.distMap(*_init_dist).predMap(*_init_pred);

       dijk.run(s);

       dijk.run(s);

       _full_init = true;

       _full_init = true;

     }

     }

     /// \brief Execute the algorithm.

     /// \brief Execute the algorithm.

     ///

     ///

     ///

     ///

     /// \pre \ref init() must be called before using this function.

     /// \pre \ref init() must be called before using this function.

     int findFlow(const Node& t, int k = 2) {

     int findFlow(const Node& t, int k = 2) {

       _t = t;

       _t = t;

       ResidualDijkstra dijkstra(*this);

       ResidualDijkstra dijkstra(*this);

       // Initialization

       // Initialization

       for (ArcIt e(_graph); e != INVALID; ++e) {

       for (ArcIt e(_graph); e != INVALID; ++e) {

         (*_flow)[e] = 0;

         (*_flow)[e] = 0;

       }

       }

       if (_full_init) {

       if (_full_init) {

         Node u = _t;

         Node u = _t;

         Arc e;

         Arc e;

         while ((e = (*_init_pred)[u]) != INVALID) {

         while ((e = (*_init_pred)[u]) != INVALID) {

           (*_flow)[e] = 1;

           (*_flow)[e] = 1;

           u = _graph.source(e);

           u = _graph.source(e);

         _path_num = 1;

         _path_num = 1;

       } else {

       } else {

         for (NodeIt n(_graph); n != INVALID; ++n) {

         for (NodeIt n(_graph); n != INVALID; ++n) {

           (*_potential)[n] = 0;

           (*_potential)[n] = 0;

         }

         }