*

  *

  *

  *

  * 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

     typedef typename Digraph::template NodeMap<Length> PotentialMap;

     typedef typename Digraph::template NodeMap<Length> PotentialMap;

     /// The type of the path structures.

     /// The type of the path structures.

     typedef SimplePath<Digraph> Path;

     typedef SimplePath<Digraph> Path;

   private:

   private:

     /// \brief Special implementation of the Dijkstra algorithm

     /// \brief Special implementation of the Dijkstra algorithm

     /// for finding shortest paths in the residual network.

     /// for finding shortest paths in the residual network.

     ///

     ///

     /// \ref ResidualDijkstra is a special implementation of the

     /// \ref ResidualDijkstra is a special implementation of the

     /// \ref Dijkstra algorithm for finding shortest paths in the

     /// \ref Dijkstra algorithm for finding shortest paths in the

       PotentialMap _dist;

       PotentialMap _dist;

       // The pred arc map

       // The pred arc map

       PredMap &_pred;

       PredMap &_pred;

       // The processed (i.e. permanently labeled) nodes

       // The processed (i.e. permanently labeled) nodes

       std::vector<Node> _proc_nodes;

       std::vector<Node> _proc_nodes;

       Node _s;

       Node _s;

       Node _t;

       Node _t;

     public:

     public:

     // The digraph the algorithm runs on

     // The digraph the algorithm runs on

     const Digraph &_graph;

     const Digraph &_graph;

     // The length map

     // The length map

     const LengthMap &_length;

     const LengthMap &_length;

     // Arc map of the current flow

     // Arc map of the current flow

     FlowMap *_flow;

     FlowMap *_flow;

     bool _local_flow;

     bool _local_flow;

     // Node map of the current potentials

     // Node map of the current potentials

     PotentialMap *_potential;

     PotentialMap *_potential;

     /// \brief Set the potential map.

     /// \brief Set the potential map.

     ///

     ///

     /// This function sets the potential map.

     /// This function sets the potential map.

     ///

     ///

     /// minimum cost flow problem.

     /// minimum cost flow problem.

     ///

     ///

     /// \return \c (*this)

     /// \return \c (*this)

     Suurballe& potentialMap(PotentialMap &map) {

     Suurballe& potentialMap(PotentialMap &map) {

       if (_local_potential) {

       if (_local_potential) {

         _local_potential = true;

         _local_potential = true;

       }

       }

       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;

       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;

       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;

       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;

                                         *_potential, _pred,

                                         *_potential, _pred,

                                         _source, _target );

                                         _source, _target );

     }

     }

     /// \brief Execute the successive shortest path algorithm to find

     /// \brief Execute the successive shortest path algorithm to find

           }

           }

         }

         }

       }

       }

       return _path_num;

       return _path_num;

     }

     }

     /// \brief Compute the paths from the flow.

     /// \brief Compute the paths from the flow.

     ///

     ///

     /// This function computes the paths from the flow.

     /// This function computes the paths from the flow.

     ///

     ///

     /// \pre \ref init() and \ref findFlow() must be called before using

     /// \pre \ref init() and \ref findFlow() must be called before using