lemon/suurballe.h
changeset 465 2b5496c62ccd
parent 425 cace3206223b
child 519 c786cd201266
equal deleted inserted replaced
2:f8d782c2d81b 3:6dcf6d36bdcf
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    74     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    74     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    75     /// The type of the path structures.
    75     /// The type of the path structures.
    76     typedef SimplePath<Digraph> Path;
    76     typedef SimplePath<Digraph> Path;
    77 
    77 
    78   private:
    78   private:
    79   
    79 
    80     /// \brief Special implementation of the Dijkstra algorithm
    80     /// \brief Special implementation of the Dijkstra algorithm
    81     /// for finding shortest paths in the residual network.
    81     /// for finding shortest paths in the residual network.
    82     ///
    82     ///
    83     /// \ref ResidualDijkstra is a special implementation of the
    83     /// \ref ResidualDijkstra is a special implementation of the
    84     /// \ref Dijkstra algorithm for finding shortest paths in the
    84     /// \ref Dijkstra algorithm for finding shortest paths in the
   104       PotentialMap _dist;
   104       PotentialMap _dist;
   105       // The pred arc map
   105       // The pred arc map
   106       PredMap &_pred;
   106       PredMap &_pred;
   107       // The processed (i.e. permanently labeled) nodes
   107       // The processed (i.e. permanently labeled) nodes
   108       std::vector<Node> _proc_nodes;
   108       std::vector<Node> _proc_nodes;
   109       
   109 
   110       Node _s;
   110       Node _s;
   111       Node _t;
   111       Node _t;
   112 
   112 
   113     public:
   113     public:
   114 
   114 
   198 
   198 
   199     // The digraph the algorithm runs on
   199     // The digraph the algorithm runs on
   200     const Digraph &_graph;
   200     const Digraph &_graph;
   201     // The length map
   201     // The length map
   202     const LengthMap &_length;
   202     const LengthMap &_length;
   203     
   203 
   204     // Arc map of the current flow
   204     // Arc map of the current flow
   205     FlowMap *_flow;
   205     FlowMap *_flow;
   206     bool _local_flow;
   206     bool _local_flow;
   207     // Node map of the current potentials
   207     // Node map of the current potentials
   208     PotentialMap *_potential;
   208     PotentialMap *_potential;
   266 
   266 
   267     /// \brief Set the potential map.
   267     /// \brief Set the potential map.
   268     ///
   268     ///
   269     /// This function sets the potential map.
   269     /// This function sets the potential map.
   270     ///
   270     ///
   271     /// The potentials provide the dual solution of the underlying 
   271     /// The potentials provide the dual solution of the underlying
   272     /// minimum cost flow problem.
   272     /// minimum cost flow problem.
   273     ///
   273     ///
   274     /// \return \c (*this)
   274     /// \return \c (*this)
   275     Suurballe& potentialMap(PotentialMap &map) {
   275     Suurballe& potentialMap(PotentialMap &map) {
   276       if (_local_potential) {
   276       if (_local_potential) {
   328         _local_potential = true;
   328         _local_potential = true;
   329       }
   329       }
   330       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   330       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   331       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   331       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   332 
   332 
   333       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, 
   333       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
   334                                         *_potential, _pred,
   334                                         *_potential, _pred,
   335                                         _source, _target );
   335                                         _source, _target );
   336     }
   336     }
   337 
   337 
   338     /// \brief Execute the successive shortest path algorithm to find
   338     /// \brief Execute the successive shortest path algorithm to find
   368           }
   368           }
   369         }
   369         }
   370       }
   370       }
   371       return _path_num;
   371       return _path_num;
   372     }
   372     }
   373     
   373 
   374     /// \brief Compute the paths from the flow.
   374     /// \brief Compute the paths from the flow.
   375     ///
   375     ///
   376     /// This function computes the paths from the flow.
   376     /// This function computes the paths from the flow.
   377     ///
   377     ///
   378     /// \pre \ref init() and \ref findFlow() must be called before using
   378     /// \pre \ref init() and \ref findFlow() must be called before using