lemon/preflow.h
changeset 615 e3d9bff447ed
parent 581 aa1804409f29
parent 610 dacc2cee2b4c
child 641 756a5ec551c8
equal deleted inserted replaced
9:9477044392ce 11:38b67a5a07d4
    44     /// The type of the map that stores the arc capacities.
    44     /// The type of the map that stores the arc capacities.
    45     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    45     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    46     typedef CAP CapacityMap;
    46     typedef CAP CapacityMap;
    47 
    47 
    48     /// \brief The type of the flow values.
    48     /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Value;
    49     typedef typename CapacityMap::Value Flow;
    50 
    50 
    51     /// \brief The type of the map that stores the flow values.
    51     /// \brief The type of the map that stores the flow values.
    52     ///
    52     ///
    53     /// The type of the map that stores the flow values.
    53     /// The type of the map that stores the flow values.
    54     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    54     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55     typedef typename Digraph::template ArcMap<Value> FlowMap;
    55     typedef typename Digraph::template ArcMap<Flow> FlowMap;
    56 
    56 
    57     /// \brief Instantiates a FlowMap.
    57     /// \brief Instantiates a FlowMap.
    58     ///
    58     ///
    59     /// This function instantiates a \ref FlowMap.
    59     /// This function instantiates a \ref FlowMap.
    60     /// \param digraph The digraph, to which we would like to define
    60     /// \param digraph The digraph for which we would like to define
    61     /// the flow map.
    61     /// the flow map.
    62     static FlowMap* createFlowMap(const Digraph& digraph) {
    62     static FlowMap* createFlowMap(const Digraph& digraph) {
    63       return new FlowMap(digraph);
    63       return new FlowMap(digraph);
    64     }
    64     }
    65 
    65 
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    73 
    73 
    74     /// \brief Instantiates an Elevator.
    74     /// \brief Instantiates an Elevator.
    75     ///
    75     ///
    76     /// This function instantiates an \ref Elevator.
    76     /// This function instantiates an \ref Elevator.
    77     /// \param digraph The digraph, to which we would like to define
    77     /// \param digraph The digraph for which we would like to define
    78     /// the elevator.
    78     /// the elevator.
    79     /// \param max_level The maximum level of the elevator.
    79     /// \param max_level The maximum level of the elevator.
    80     static Elevator* createElevator(const Digraph& digraph, int max_level) {
    80     static Elevator* createElevator(const Digraph& digraph, int max_level) {
    81       return new Elevator(digraph, max_level);
    81       return new Elevator(digraph, max_level);
    82     }
    82     }
    83 
    83 
    84     /// \brief The tolerance used by the algorithm
    84     /// \brief The tolerance used by the algorithm
    85     ///
    85     ///
    86     /// The tolerance used by the algorithm to handle inexact computation.
    86     /// The tolerance used by the algorithm to handle inexact computation.
    87     typedef lemon::Tolerance<Value> Tolerance;
    87     typedef lemon::Tolerance<Flow> Tolerance;
    88 
    88 
    89   };
    89   };
    90 
    90 
    91 
    91 
    92   /// \ingroup max_flow
    92   /// \ingroup max_flow
   123     ///The type of the digraph the algorithm runs on.
   123     ///The type of the digraph the algorithm runs on.
   124     typedef typename Traits::Digraph Digraph;
   124     typedef typename Traits::Digraph Digraph;
   125     ///The type of the capacity map.
   125     ///The type of the capacity map.
   126     typedef typename Traits::CapacityMap CapacityMap;
   126     typedef typename Traits::CapacityMap CapacityMap;
   127     ///The type of the flow values.
   127     ///The type of the flow values.
   128     typedef typename Traits::Value Value;
   128     typedef typename Traits::Flow Flow;
   129 
   129 
   130     ///The type of the flow map.
   130     ///The type of the flow map.
   131     typedef typename Traits::FlowMap FlowMap;
   131     typedef typename Traits::FlowMap FlowMap;
   132     ///The type of the elevator.
   132     ///The type of the elevator.
   133     typedef typename Traits::Elevator Elevator;
   133     typedef typename Traits::Elevator Elevator;
   149     bool _local_flow;
   149     bool _local_flow;
   150 
   150 
   151     Elevator* _level;
   151     Elevator* _level;
   152     bool _local_level;
   152     bool _local_level;
   153 
   153 
   154     typedef typename Digraph::template NodeMap<Value> ExcessMap;
   154     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
   155     ExcessMap* _excess;
   155     ExcessMap* _excess;
   156 
   156 
   157     Tolerance _tolerance;
   157     Tolerance _tolerance;
   158 
   158 
   159     bool _phase;
   159     bool _phase;
   468       for (ArcIt e(_graph); e != INVALID; ++e) {
   468       for (ArcIt e(_graph); e != INVALID; ++e) {
   469         _flow->set(e, flowMap[e]);
   469         _flow->set(e, flowMap[e]);
   470       }
   470       }
   471 
   471 
   472       for (NodeIt n(_graph); n != INVALID; ++n) {
   472       for (NodeIt n(_graph); n != INVALID; ++n) {
   473         Value excess = 0;
   473         Flow excess = 0;
   474         for (InArcIt e(_graph, n); e != INVALID; ++e) {
   474         for (InArcIt e(_graph, n); e != INVALID; ++e) {
   475           excess += (*_flow)[e];
   475           excess += (*_flow)[e];
   476         }
   476         }
   477         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   477         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   478           excess -= (*_flow)[e];
   478           excess -= (*_flow)[e];
   517         queue.swap(nqueue);
   517         queue.swap(nqueue);
   518       }
   518       }
   519       _level->initFinish();
   519       _level->initFinish();
   520 
   520 
   521       for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
   521       for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
   522         Value rem = (*_capacity)[e] - (*_flow)[e];
   522         Flow rem = (*_capacity)[e] - (*_flow)[e];
   523         if (_tolerance.positive(rem)) {
   523         if (_tolerance.positive(rem)) {
   524           Node u = _graph.target(e);
   524           Node u = _graph.target(e);
   525           if ((*_level)[u] == _level->maxLevel()) continue;
   525           if ((*_level)[u] == _level->maxLevel()) continue;
   526           _flow->set(e, (*_capacity)[e]);
   526           _flow->set(e, (*_capacity)[e]);
   527           (*_excess)[u] += rem;
   527           (*_excess)[u] += rem;
   529             _level->activate(u);
   529             _level->activate(u);
   530           }
   530           }
   531         }
   531         }
   532       }
   532       }
   533       for (InArcIt e(_graph, _source); e != INVALID; ++e) {
   533       for (InArcIt e(_graph, _source); e != INVALID; ++e) {
   534         Value rem = (*_flow)[e];
   534         Flow rem = (*_flow)[e];
   535         if (_tolerance.positive(rem)) {
   535         if (_tolerance.positive(rem)) {
   536           Node v = _graph.source(e);
   536           Node v = _graph.source(e);
   537           if ((*_level)[v] == _level->maxLevel()) continue;
   537           if ((*_level)[v] == _level->maxLevel()) continue;
   538           _flow->set(e, 0);
   538           _flow->set(e, 0);
   539           (*_excess)[v] += rem;
   539           (*_excess)[v] += rem;
   562       int level = _level->highestActiveLevel();
   562       int level = _level->highestActiveLevel();
   563       while (n != INVALID) {
   563       while (n != INVALID) {
   564         int num = _node_num;
   564         int num = _node_num;
   565 
   565 
   566         while (num > 0 && n != INVALID) {
   566         while (num > 0 && n != INVALID) {
   567           Value excess = (*_excess)[n];
   567           Flow excess = (*_excess)[n];
   568           int new_level = _level->maxLevel();
   568           int new_level = _level->maxLevel();
   569 
   569 
   570           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   570           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   571             Value rem = (*_capacity)[e] - (*_flow)[e];
   571             Flow rem = (*_capacity)[e] - (*_flow)[e];
   572             if (!_tolerance.positive(rem)) continue;
   572             if (!_tolerance.positive(rem)) continue;
   573             Node v = _graph.target(e);
   573             Node v = _graph.target(e);
   574             if ((*_level)[v] < level) {
   574             if ((*_level)[v] < level) {
   575               if (!_level->active(v) && v != _target) {
   575               if (!_level->active(v) && v != _target) {
   576                 _level->activate(v);
   576                 _level->activate(v);
   589               new_level = (*_level)[v];
   589               new_level = (*_level)[v];
   590             }
   590             }
   591           }
   591           }
   592 
   592 
   593           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   593           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   594             Value rem = (*_flow)[e];
   594             Flow rem = (*_flow)[e];
   595             if (!_tolerance.positive(rem)) continue;
   595             if (!_tolerance.positive(rem)) continue;
   596             Node v = _graph.source(e);
   596             Node v = _graph.source(e);
   597             if ((*_level)[v] < level) {
   597             if ((*_level)[v] < level) {
   598               if (!_level->active(v) && v != _target) {
   598               if (!_level->active(v) && v != _target) {
   599                 _level->activate(v);
   599                 _level->activate(v);
   635           --num;
   635           --num;
   636         }
   636         }
   637 
   637 
   638         num = _node_num * 20;
   638         num = _node_num * 20;
   639         while (num > 0 && n != INVALID) {
   639         while (num > 0 && n != INVALID) {
   640           Value excess = (*_excess)[n];
   640           Flow excess = (*_excess)[n];
   641           int new_level = _level->maxLevel();
   641           int new_level = _level->maxLevel();
   642 
   642 
   643           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   643           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   644             Value rem = (*_capacity)[e] - (*_flow)[e];
   644             Flow rem = (*_capacity)[e] - (*_flow)[e];
   645             if (!_tolerance.positive(rem)) continue;
   645             if (!_tolerance.positive(rem)) continue;
   646             Node v = _graph.target(e);
   646             Node v = _graph.target(e);
   647             if ((*_level)[v] < level) {
   647             if ((*_level)[v] < level) {
   648               if (!_level->active(v) && v != _target) {
   648               if (!_level->active(v) && v != _target) {
   649                 _level->activate(v);
   649                 _level->activate(v);
   662               new_level = (*_level)[v];
   662               new_level = (*_level)[v];
   663             }
   663             }
   664           }
   664           }
   665 
   665 
   666           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   666           for (InArcIt e(_graph, n); e != INVALID; ++e) {
   667             Value rem = (*_flow)[e];
   667             Flow rem = (*_flow)[e];
   668             if (!_tolerance.positive(rem)) continue;
   668             if (!_tolerance.positive(rem)) continue;
   669             Node v = _graph.source(e);
   669             Node v = _graph.source(e);
   670             if ((*_level)[v] < level) {
   670             if ((*_level)[v] < level) {
   671               if (!_level->active(v) && v != _target) {
   671               if (!_level->active(v) && v != _target) {
   672                 _level->activate(v);
   672                 _level->activate(v);
   776         }
   776         }
   777       }
   777       }
   778 
   778 
   779       Node n;
   779       Node n;
   780       while ((n = _level->highestActive()) != INVALID) {
   780       while ((n = _level->highestActive()) != INVALID) {
   781         Value excess = (*_excess)[n];
   781         Flow excess = (*_excess)[n];
   782         int level = _level->highestActiveLevel();
   782         int level = _level->highestActiveLevel();
   783         int new_level = _level->maxLevel();
   783         int new_level = _level->maxLevel();
   784 
   784 
   785         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   785         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   786           Value rem = (*_capacity)[e] - (*_flow)[e];
   786           Flow rem = (*_capacity)[e] - (*_flow)[e];
   787           if (!_tolerance.positive(rem)) continue;
   787           if (!_tolerance.positive(rem)) continue;
   788           Node v = _graph.target(e);
   788           Node v = _graph.target(e);
   789           if ((*_level)[v] < level) {
   789           if ((*_level)[v] < level) {
   790             if (!_level->active(v) && v != _source) {
   790             if (!_level->active(v) && v != _source) {
   791               _level->activate(v);
   791               _level->activate(v);
   804             new_level = (*_level)[v];
   804             new_level = (*_level)[v];
   805           }
   805           }
   806         }
   806         }
   807 
   807 
   808         for (InArcIt e(_graph, n); e != INVALID; ++e) {
   808         for (InArcIt e(_graph, n); e != INVALID; ++e) {
   809           Value rem = (*_flow)[e];
   809           Flow rem = (*_flow)[e];
   810           if (!_tolerance.positive(rem)) continue;
   810           if (!_tolerance.positive(rem)) continue;
   811           Node v = _graph.source(e);
   811           Node v = _graph.source(e);
   812           if ((*_level)[v] < level) {
   812           if ((*_level)[v] < level) {
   813             if (!_level->active(v) && v != _source) {
   813             if (!_level->active(v) && v != _source) {
   814               _level->activate(v);
   814               _level->activate(v);
   895     /// of the target node. This value equals to the value of
   895     /// of the target node. This value equals to the value of
   896     /// the maximum flow already after the first phase of the algorithm.
   896     /// the maximum flow already after the first phase of the algorithm.
   897     ///
   897     ///
   898     /// \pre Either \ref run() or \ref init() must be called before
   898     /// \pre Either \ref run() or \ref init() must be called before
   899     /// using this function.
   899     /// using this function.
   900     Value flowValue() const {
   900     Flow flowValue() const {
   901       return (*_excess)[_target];
   901       return (*_excess)[_target];
   902     }
   902     }
   903 
   903 
   904     /// \brief Returns the flow on the given arc.
   904     /// \brief Returns the flow on the given arc.
   905     ///
   905     ///
   906     /// Returns the flow on the given arc. This method can
   906     /// Returns the flow on the given arc. This method can
   907     /// be called after the second phase of the algorithm.
   907     /// be called after the second phase of the algorithm.
   908     ///
   908     ///
   909     /// \pre Either \ref run() or \ref init() must be called before
   909     /// \pre Either \ref run() or \ref init() must be called before
   910     /// using this function.
   910     /// using this function.
   911     Value flow(const Arc& arc) const {
   911     Flow flow(const Arc& arc) const {
   912       return (*_flow)[arc];
   912       return (*_flow)[arc];
   913     }
   913     }
   914 
   914 
   915     /// \brief Returns a const reference to the flow map.
   915     /// \brief Returns a const reference to the flow map.
   916     ///
   916     ///