COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 658:85cb3aa71cce in lemon for lemon


Ignore:
Timestamp:
04/21/09 16:18:54 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
659:0c8e5c688440, 660:b1811c363299, 666:ec817dfc2cb7
Parents:
647:0ba8dfce7259 (diff), 657:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge and fix

Location:
lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r641 r658  
    9494        lemon/min_cost_arborescence.h \
    9595        lemon/nauty_reader.h \
     96        lemon/network_simplex.h \
    9697        lemon/path.h \
    9798        lemon/preflow.h \

  • lemon/Makefile.am

    r648 r658  
    1313        lemon/lp_base.cc \
    1414        lemon/lp_skeleton.cc \
    15         lemon/random.cc \
     15        lemon/random.cc \
    1616        lemon/bits/windows.cc
    1717
    1818
    1919lemon_libemon_la_CXXFLAGS = \
     20        $(AM_CXXFLAGS) \
    2021        $(GLPK_CFLAGS) \
    2122        $(CPLEX_CFLAGS) \
    2223        $(SOPLEX_CXXFLAGS) \
    23         $(CLP_CXXFLAGS)
     24        $(CLP_CXXFLAGS) \
     25        $(CBC_CXXFLAGS)
    2426
    2527lemon_libemon_la_LDFLAGS = \
    … …  
    2729        $(CPLEX_LIBS) \
    2830        $(SOPLEX_LIBS) \
    29         $(CLP_LIBS)
     31        $(CLP_LIBS) \
     32        $(CBC_LIBS)
    3033
    3134if HAVE_GLPK
    … …  
    4346if HAVE_CLP
    4447lemon_libemon_la_SOURCES += lemon/clp.cc
     48endif
     49
     50if HAVE_CBC
     51lemon_libemon_la_SOURCES += lemon/cbc.cc
    4552endif
    4653
    … …  
    6976        lemon/full_graph.h \
    7077        lemon/glpk.h \
     78        lemon/gomory_hu.h \
    7179        lemon/graph_to_eps.h \
    7280        lemon/grid_graph.h \
    … …  
    8290        lemon/list_graph.h \
    8391        lemon/maps.h \
     92        lemon/matching.h \
    8493        lemon/math.h \
    85         lemon/max_matching.h \
    8694        lemon/min_cost_arborescence.h \
    8795        lemon/nauty_reader.h \

  • lemon/circulation.h

    r628 r658  
    3232  ///
    3333  /// Default traits class of Circulation class.
    34   /// \tparam GR Digraph type.
    35   /// \tparam LM Lower bound capacity map type.
    36   /// \tparam UM Upper bound capacity map type.
    37   /// \tparam DM Delta map type.
     34  ///
     35  /// \tparam GR Type of the digraph the algorithm runs on.
     36  /// \tparam LM The type of the lower bound map.
     37  /// \tparam UM The type of the upper bound (capacity) map.
     38  /// \tparam SM The type of the supply map.
    3839  template <typename GR, typename LM,
    39             typename UM, typename DM>
     40            typename UM, typename SM>
    4041  struct CirculationDefaultTraits {
    4142
    … …  
    4344    typedef GR Digraph;
    4445
    45     /// \brief The type of the map that stores the circulation lower
    46     /// bound.
    47     ///
    48     /// The type of the map that stores the circulation lower bound.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef LM LCapMap;
    51 
    52     /// \brief The type of the map that stores the circulation upper
    53     /// bound.
    54     ///
    55     /// The type of the map that stores the circulation upper bound.
    56     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    57     typedef UM UCapMap;
    58 
    59     /// \brief The type of the map that stores the lower bound for
    60     /// the supply of the nodes.
    61     ///
    62     /// The type of the map that stores the lower bound for the supply
    63     /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
     46    /// \brief The type of the lower bound map.
     47    ///
     48    /// The type of the map that stores the lower bounds on the arcs.
     49    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     50    typedef LM LowerMap;
     51
     52    /// \brief The type of the upper bound (capacity) map.
     53    ///
     54    /// The type of the map that stores the upper bounds (capacities)
     55    /// on the arcs.
     56    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     57    typedef UM UpperMap;
     58
     59    /// \brief The type of supply map.
     60    ///
     61    /// The type of the map that stores the signed supply values of the
     62    /// nodes.
     63    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     64    typedef SM SupplyMap;
     65
     66    /// \brief The type of the flow values.
     67    typedef typename SupplyMap::Value Flow;
     68
     69    /// \brief The type of the map that stores the flow values.
     70    ///
     71    /// The type of the map that stores the flow values.
     72    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    6473    /// concept.
    65     typedef DM DeltaMap;
    66 
    67     /// \brief The type of the flow values.
    68     typedef typename DeltaMap::Value Value;
    69 
    70     /// \brief The type of the map that stores the flow values.
    71     ///
    72     /// The type of the map that stores the flow values.
    73     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    74     typedef typename Digraph::template ArcMap<Value> FlowMap;
     74    typedef typename Digraph::template ArcMap<Flow> FlowMap;
    7575
    7676    /// \brief Instantiates a FlowMap.
    7777    ///
    7878    /// This function instantiates a \ref FlowMap.
    79     /// \param digraph The digraph, to which we would like to define
     79    /// \param digraph The digraph for which we would like to define
    8080    /// the flow map.
    8181    static FlowMap* createFlowMap(const Digraph& digraph) {
    … …  
    9494    ///
    9595    /// This function instantiates an \ref Elevator.
    96     /// \param digraph The digraph, to which we would like to define
     96    /// \param digraph The digraph for which we would like to define
    9797    /// the elevator.
    9898    /// \param max_level The maximum level of the elevator.
    … …  
    104104    ///
    105105    /// The tolerance used by the algorithm to handle inexact computation.
    106     typedef lemon::Tolerance<Value> Tolerance;
     106    typedef lemon::Tolerance<Flow> Tolerance;
    107107
    108108  };
    … …  
    112112
    113113     \ingroup max_flow
    114      This class implements a push-relabel algorithm for the network
    115      circulation problem.
     114     This class implements a push-relabel algorithm for the \e network
     115     \e circulation problem.
    116116     It is to find a feasible circulation when lower and upper bounds
    117      are given for the flow values on the arcs and lower bounds
    118      are given for the supply values of the nodes.
     117     are given for the flow values on the arcs and lower bounds are
     118     given for the difference between the outgoing and incoming flow
     119     at the nodes.
    119120
    120121     The exact formulation of this problem is the following.
    121122     Let \f$G=(V,A)\f$ be a digraph,
    122      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
    123      \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
    124      \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
    125      \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
    126      \geq delta(v) \quad \forall v\in V, \f]
    127      \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
    128      \note \f$delta(v)\f$ specifies a lower bound for the supply of node
    129      \f$v\f$. It can be either positive or negative, however note that
    130      \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
    131      have a feasible solution.
    132 
    133      \note A special case of this problem is when
    134      \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
    135      will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
    136      Thus a feasible solution for the
    137      \ref min_cost_flow "minimum cost flow" problem can be calculated
    138      in this way.
     123     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
     124     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
     125     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
     126     denotes the signed supply values of the nodes.
     127     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
     128     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
     129     \f$-sup(u)\f$ demand.
     130     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
     131     solution of the following problem.
     132
     133     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
     134     \geq sup(u) \quad \forall u\in V, \f]
     135     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
     136     
     137     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
     138     zero or negative in order to have a feasible solution (since the sum
     139     of the expressions on the left-hand side of the inequalities is zero).
     140     It means that the total demand must be greater or equal to the total
     141     supply and all the supplies have to be carried out from the supply nodes,
     142     but there could be demands that are not satisfied.
     143     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
     144     constraints have to be satisfied with equality, i.e. all demands
     145     have to be satisfied and all supplies have to be used.
     146     
     147     If you need the opposite inequalities in the supply/demand constraints
     148     (i.e. the total demand is less than the total supply and all the demands
     149     have to be satisfied while there could be supplies that are not used),
     150     then you could easily transform the problem to the above form by reversing
     151     the direction of the arcs and taking the negative of the supply values
     152     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     153
     154     Note that this algorithm also provides a feasible solution for the
     155     \ref min_cost_flow "minimum cost flow problem".
    139156
    140157     \tparam GR The type of the digraph the algorithm runs on.
    141      \tparam LM The type of the lower bound capacity map. The default
     158     \tparam LM The type of the lower bound map. The default
    142159     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    143      \tparam UM The type of the upper bound capacity map. The default
    144      map type is \c LM.
    145      \tparam DM The type of the map that stores the lower bound
    146      for the supply of the nodes. The default map type is
     160     \tparam UM The type of the upper bound (capacity) map.
     161     The default map type is \c LM.
     162     \tparam SM The type of the supply map. The default map type is
    147163     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    148164  */
    … …  
    151167          typename LM,
    152168          typename UM,
    153           typename DM,
     169          typename SM,
    154170          typename TR >
    155171#else
    … …  
    157173          typename LM = typename GR::template ArcMap<int>,
    158174          typename UM = LM,
    159           typename DM = typename GR::template NodeMap<typename UM::Value>,
    160           typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
     175          typename SM = typename GR::template NodeMap<typename UM::Value>,
     176          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
    161177#endif
    162178  class Circulation {
    … …  
    168184    typedef typename Traits::Digraph Digraph;
    169185    ///The type of the flow values.
    170     typedef typename Traits::Value Value;
    171 
    172     /// The type of the lower bound capacity map.
    173     typedef typename Traits::LCapMap LCapMap;
    174     /// The type of the upper bound capacity map.
    175     typedef typename Traits::UCapMap UCapMap;
    176     /// \brief The type of the map that stores the lower bound for
    177     /// the supply of the nodes.
    178     typedef typename Traits::DeltaMap DeltaMap;
     186    typedef typename Traits::Flow Flow;
     187
     188    ///The type of the lower bound map.
     189    typedef typename Traits::LowerMap LowerMap;
     190    ///The type of the upper bound (capacity) map.
     191    typedef typename Traits::UpperMap UpperMap;
     192    ///The type of the supply map.
     193    typedef typename Traits::SupplyMap SupplyMap;
    179194    ///The type of the flow map.
    180195    typedef typename Traits::FlowMap FlowMap;
    … …  
    192207    int _node_num;
    193208
    194     const LCapMap *_lo;
    195     const UCapMap *_up;
    196     const DeltaMap *_delta;
     209    const LowerMap *_lo;
     210    const UpperMap *_up;
     211    const SupplyMap *_supply;
    197212
    198213    FlowMap *_flow;
    … …  
    202217    bool _local_level;
    203218
    204     typedef typename Digraph::template NodeMap<Value> ExcessMap;
     219    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
    205220    ExcessMap* _excess;
    206221
    … …  
    232247    template <typename T>
    233248    struct SetFlowMap
    234       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     249      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    235250                           SetFlowMapTraits<T> > {
    236       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     251      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    237252                          SetFlowMapTraits<T> > Create;
    238253    };
    … …  
    258273    template <typename T>
    259274    struct SetElevator
    260       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     275      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    261276                           SetElevatorTraits<T> > {
    262       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     277      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    263278                          SetElevatorTraits<T> > Create;
    264279    };
    … …  
    286301    template <typename T>
    287302    struct SetStandardElevator
    288       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     303      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    289304                       SetStandardElevatorTraits<T> > {
    290       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     305      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    291306                      SetStandardElevatorTraits<T> > Create;
    292307    };
    … …  
    300315  public:
    301316
     317    /// Constructor.
     318
    302319    /// The constructor of the class.
    303 
    304     /// The constructor of the class.
    305     /// \param g The digraph the algorithm runs on.
    306     /// \param lo The lower bound capacity of the arcs.
    307     /// \param up The upper bound capacity of the arcs.
    308     /// \param delta The lower bound for the supply of the nodes.
    309     Circulation(const Digraph &g,const LCapMap &lo,
    310                 const UCapMap &up,const DeltaMap &delta)
    311       : _g(g), _node_num(),
    312         _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
    313         _level(0), _local_level(false), _excess(0), _el() {}
     320    ///
     321    /// \param graph The digraph the algorithm runs on.
     322    /// \param lower The lower bounds for the flow values on the arcs.
     323    /// \param upper The upper bounds (capacities) for the flow values
     324    /// on the arcs.
     325    /// \param supply The signed supply values of the nodes.
     326    Circulation(const Digraph &graph, const LowerMap &lower,
     327                const UpperMap &upper, const SupplyMap &supply)
     328      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
     329        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
     330        _excess(NULL) {}
    314331
    315332    /// Destructor.
    … …  
    351368  public:
    352369
    353     /// Sets the lower bound capacity map.
    354 
    355     /// Sets the lower bound capacity map.
     370    /// Sets the lower bound map.
     371
     372    /// Sets the lower bound map.
    356373    /// \return <tt>(*this)</tt>
    357     Circulation& lowerCapMap(const LCapMap& map) {
     374    Circulation& lowerMap(const LowerMap& map) {
    358375      _lo = &map;
    359376      return *this;
    360377    }
    361378
    362     /// Sets the upper bound capacity map.
    363 
    364     /// Sets the upper bound capacity map.
     379    /// Sets the upper bound (capacity) map.
     380
     381    /// Sets the upper bound (capacity) map.
    365382    /// \return <tt>(*this)</tt>
    366     Circulation& upperCapMap(const LCapMap& map) {
     383    Circulation& upperMap(const LowerMap& map) {
    367384      _up = &map;
    368385      return *this;
    369386    }
    370387
    371     /// Sets the lower bound map for the supply of the nodes.
    372 
    373     /// Sets the lower bound map for the supply of the nodes.
     388    /// Sets the supply map.
     389
     390    /// Sets the supply map.
    374391    /// \return <tt>(*this)</tt>
    375     Circulation& deltaMap(const DeltaMap& map) {
    376       _delta = &map;
     392    Circulation& supplyMap(const SupplyMap& map) {
     393      _supply = &map;
    377394      return *this;
    378395    }
    … …  
    454471
    455472      for(NodeIt n(_g);n!=INVALID;++n) {
    456         (*_excess)[n] = (*_delta)[n];
     473        (*_excess)[n] = (*_supply)[n];
    457474      }
    458475
    … …  
    483500
    484501      for(NodeIt n(_g);n!=INVALID;++n) {
    485         (*_excess)[n] = (*_delta)[n];
     502        (*_excess)[n] = (*_supply)[n];
    486503      }
    487504
    … …  
    496513          (*_excess)[_g.source(e)] -= (*_lo)[e];
    497514        } else {
    498           Value fc = -(*_excess)[_g.target(e)];
     515          Flow fc = -(*_excess)[_g.target(e)];
    499516          _flow->set(e, fc);
    500517          (*_excess)[_g.target(e)] = 0;
    … …  
    529546        int actlevel=(*_level)[act];
    530547        int mlevel=_node_num;
    531         Value exc=(*_excess)[act];
     548        Flow exc=(*_excess)[act];
    532549
    533550        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    534551          Node v = _g.target(e);
    535           Value fc=(*_up)[e]-(*_flow)[e];
     552          Flow fc=(*_up)[e]-(*_flow)[e];
    536553          if(!_tol.positive(fc)) continue;
    537554          if((*_level)[v]<actlevel) {
    … …  
    557574        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    558575          Node v = _g.source(e);
    559           Value fc=(*_flow)[e]-(*_lo)[e];
     576          Flow fc=(*_flow)[e]-(*_lo)[e];
    560577          if(!_tol.positive(fc)) continue;
    561578          if((*_level)[v]<actlevel) {
    … …  
    633650    /// \pre Either \ref run() or \ref init() must be called before
    634651    /// using this function.
    635     Value flow(const Arc& arc) const {
     652    Flow flow(const Arc& arc) const {
    636653      return (*_flow)[arc];
    637654    }
    … …  
    652669       Barrier is a set \e B of nodes for which
    653670
    654        \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
    655            \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
     671       \f[ \sum_{uv\in A: u\in B} upper(uv) -
     672           \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
    656673
    657674       holds. The existence of a set with this property prooves that a
    … …  
    716733      for(NodeIt n(_g);n!=INVALID;++n)
    717734        {
    718           Value dif=-(*_delta)[n];
     735          Flow dif=-(*_supply)[n];
    719736          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    720737          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
    … …  
    731748    bool checkBarrier() const
    732749    {
    733       Value delta=0;
     750      Flow delta=0;
    734751      for(NodeIt n(_g);n!=INVALID;++n)
    735752        if(barrier(n))
    736           delta-=(*_delta)[n];
     753          delta-=(*_supply)[n];
    737754      for(ArcIt e(_g);e!=INVALID;++e)
    738755        {

  • lemon/circulation.h

    r657 r658  
    231231    ///@{
    232232
    233     template <typename _FlowMap>
     233    template <typename T>
    234234    struct SetFlowMapTraits : public Traits {
    235       typedef _FlowMap FlowMap;
     235      typedef T FlowMap;
    236236      static FlowMap *createFlowMap(const Digraph&) {
    237237        LEMON_ASSERT(false, "FlowMap is not initialized");
    … …  
    245245    /// \ref named-templ-param "Named parameter" for setting FlowMap
    246246    /// type.
    247     template <typename _FlowMap>
     247    template <typename T>
    248248    struct SetFlowMap
    249249      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    250                            SetFlowMapTraits<_FlowMap> > {
     250                           SetFlowMapTraits<T> > {
    251251      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    252                           SetFlowMapTraits<_FlowMap> > Create;
     252                          SetFlowMapTraits<T> > Create;
    253253    };
    254254
    255     template <typename _Elevator>
     255    template <typename T>
    256256    struct SetElevatorTraits : public Traits {
    257       typedef _Elevator Elevator;
     257      typedef T Elevator;
    258258      static Elevator *createElevator(const Digraph&, int) {
    259259        LEMON_ASSERT(false, "Elevator is not initialized");
    … …  
    271271    /// \ref run() or \ref init().
    272272    /// \sa SetStandardElevator
    273     template <typename _Elevator>
     273    template <typename T>
    274274    struct SetElevator
    275275      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    276                            SetElevatorTraits<_Elevator> > {
     276                           SetElevatorTraits<T> > {
    277277      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    278                           SetElevatorTraits<_Elevator> > Create;
     278                          SetElevatorTraits<T> > Create;
    279279    };
    280280
    281     template <typename _Elevator>
     281    template <typename T>
    282282    struct SetStandardElevatorTraits : public Traits {
    283       typedef _Elevator Elevator;
     283      typedef T Elevator;
    284284      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    285285        return new Elevator(digraph, max_level);
    … …  
    299299    /// before calling \ref run() or \ref init().
    300300    /// \sa SetElevator
    301     template <typename _Elevator>
     301    template <typename T>
    302302    struct SetStandardElevator
    303303      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    304                        SetStandardElevatorTraits<_Elevator> > {
     304                       SetStandardElevatorTraits<T> > {
    305305      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    306                       SetStandardElevatorTraits<_Elevator> > Create;
     306                      SetStandardElevatorTraits<T> > Create;
    307307    };
    308308
    … …  
    471471
    472472      for(NodeIt n(_g);n!=INVALID;++n) {
    473         _excess->set(n, (*_supply)[n]);
     473        (*_excess)[n] = (*_supply)[n];
    474474      }
    475475
    476476      for (ArcIt e(_g);e!=INVALID;++e) {
    477477        _flow->set(e, (*_lo)[e]);
    478         _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
    479         _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
     478        (*_excess)[_g.target(e)] += (*_flow)[e];
     479        (*_excess)[_g.source(e)] -= (*_flow)[e];
    480480      }
    481481
    … …  
    500500
    501501      for(NodeIt n(_g);n!=INVALID;++n) {
    502         _excess->set(n, (*_supply)[n]);
     502        (*_excess)[n] = (*_supply)[n];
    503503      }
    504504
    … …  
    506506        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
    507507          _flow->set(e, (*_up)[e]);
    508           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
    509           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
     508          (*_excess)[_g.target(e)] += (*_up)[e];
     509          (*_excess)[_g.source(e)] -= (*_up)[e];
    510510        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
    511511          _flow->set(e, (*_lo)[e]);
    512           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
    513           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
     512          (*_excess)[_g.target(e)] += (*_lo)[e];
     513          (*_excess)[_g.source(e)] -= (*_lo)[e];
    514514        } else {
    515515          Flow fc = -(*_excess)[_g.target(e)];
    516516          _flow->set(e, fc);
    517           _excess->set(_g.target(e), 0);
    518           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
     517          (*_excess)[_g.target(e)] = 0;
     518          (*_excess)[_g.source(e)] -= fc;
    519519        }
    520520      }
    … …  
    555555            if(!_tol.less(fc, exc)) {
    556556              _flow->set(e, (*_flow)[e] + exc);
    557               _excess->set(v, (*_excess)[v] + exc);
     557              (*_excess)[v] += exc;
    558558              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    559559                _level->activate(v);
    560               _excess->set(act,0);
     560              (*_excess)[act] = 0;
    561561              _level->deactivate(act);
    562562              goto next_l;
    … …  
    564564            else {
    565565              _flow->set(e, (*_up)[e]);
    566               _excess->set(v, (*_excess)[v] + fc);
     566              (*_excess)[v] += fc;
    567567              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    568568                _level->activate(v);
    … …  
    579579            if(!_tol.less(fc, exc)) {
    580580              _flow->set(e, (*_flow)[e] - exc);
    581               _excess->set(v, (*_excess)[v] + exc);
     581              (*_excess)[v] += exc;
    582582              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    583583                _level->activate(v);
    584               _excess->set(act,0);
     584              (*_excess)[act] = 0;
    585585              _level->deactivate(act);
    586586              goto next_l;
    … …  
    588588            else {
    589589              _flow->set(e, (*_lo)[e]);
    590               _excess->set(v, (*_excess)[v] + fc);
     590              (*_excess)[v] += fc;
    591591              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    592592                _level->activate(v);
    … …  
    597597        }
    598598
    599         _excess->set(act, exc);
     599        (*_excess)[act] = exc;
    600600        if(!_tol.positive(exc)) _level->deactivate(act);
    601601        else if(mlevel==_node_num) {
    … …  
    700700    ///
    701701    /// \note This function calls \ref barrier() for each node,
    702     /// so it runs in \f$O(n)\f$ time.
     702    /// so it runs in O(n) time.
    703703    ///
    704704    /// \pre Either \ref run() or \ref init() must be called before

  • lemon/preflow.h

    r628 r658  
    4747
    4848    /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Value;
     49    typedef typename CapacityMap::Value Flow;
    5050
    5151    /// \brief The type of the map that stores the flow values.
    … …  
    5353    /// The type of the map that stores the flow values.
    5454    /// 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;
    5656
    5757    /// \brief Instantiates a FlowMap.
    5858    ///
    5959    /// 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
    6161    /// the flow map.
    6262    static FlowMap* createFlowMap(const Digraph& digraph) {
    … …  
    7575    ///
    7676    /// 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
    7878    /// the elevator.
    7979    /// \param max_level The maximum level of the elevator.
    … …  
    8585    ///
    8686    /// The tolerance used by the algorithm to handle inexact computation.
    87     typedef lemon::Tolerance<Value> Tolerance;
     87    typedef lemon::Tolerance<Flow> Tolerance;
    8888
    8989  };
    … …  
    126126    typedef typename Traits::CapacityMap CapacityMap;
    127127    ///The type of the flow values.
    128     typedef typename Traits::Value Value;
     128    typedef typename Traits::Flow Flow;
    129129
    130130    ///The type of the flow map.
    … …  
    152152    bool _local_level;
    153153
    154     typedef typename Digraph::template NodeMap<Value> ExcessMap;
     154    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
    155155    ExcessMap* _excess;
    156156
    … …  
    471471
    472472      for (NodeIt n(_graph); n != INVALID; ++n) {
    473         Value excess = 0;
     473        Flow excess = 0;
    474474        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    475475          excess += (*_flow)[e];
    … …  
    520520
    521521      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
    522         Value rem = (*_capacity)[e] - (*_flow)[e];
     522        Flow rem = (*_capacity)[e] - (*_flow)[e];
    523523        if (_tolerance.positive(rem)) {
    524524          Node u = _graph.target(e);
    … …  
    532532      }
    533533      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
    534         Value rem = (*_flow)[e];
     534        Flow rem = (*_flow)[e];
    535535        if (_tolerance.positive(rem)) {
    536536          Node v = _graph.source(e);
    … …  
    565565
    566566        while (num > 0 && n != INVALID) {
    567           Value excess = (*_excess)[n];
     567          Flow excess = (*_excess)[n];
    568568          int new_level = _level->maxLevel();
    569569
    570570          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    571             Value rem = (*_capacity)[e] - (*_flow)[e];
     571            Flow rem = (*_capacity)[e] - (*_flow)[e];
    572572            if (!_tolerance.positive(rem)) continue;
    573573            Node v = _graph.target(e);
    … …  
    592592
    593593          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    594             Value rem = (*_flow)[e];
     594            Flow rem = (*_flow)[e];
    595595            if (!_tolerance.positive(rem)) continue;
    596596            Node v = _graph.source(e);
    … …  
    638638        num = _node_num * 20;
    639639        while (num > 0 && n != INVALID) {
    640           Value excess = (*_excess)[n];
     640          Flow excess = (*_excess)[n];
    641641          int new_level = _level->maxLevel();
    642642
    643643          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    644             Value rem = (*_capacity)[e] - (*_flow)[e];
     644            Flow rem = (*_capacity)[e] - (*_flow)[e];
    645645            if (!_tolerance.positive(rem)) continue;
    646646            Node v = _graph.target(e);
    … …  
    665665
    666666          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    667             Value rem = (*_flow)[e];
     667            Flow rem = (*_flow)[e];
    668668            if (!_tolerance.positive(rem)) continue;
    669669            Node v = _graph.source(e);
    … …  
    779779      Node n;
    780780      while ((n = _level->highestActive()) != INVALID) {
    781         Value excess = (*_excess)[n];
     781        Flow excess = (*_excess)[n];
    782782        int level = _level->highestActiveLevel();
    783783        int new_level = _level->maxLevel();
    784784
    785785        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    786           Value rem = (*_capacity)[e] - (*_flow)[e];
     786          Flow rem = (*_capacity)[e] - (*_flow)[e];
    787787          if (!_tolerance.positive(rem)) continue;
    788788          Node v = _graph.target(e);
    … …  
    807807
    808808        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    809           Value rem = (*_flow)[e];
     809          Flow rem = (*_flow)[e];
    810810          if (!_tolerance.positive(rem)) continue;
    811811          Node v = _graph.source(e);
    … …  
    898898    /// \pre Either \ref run() or \ref init() must be called before
    899899    /// using this function.
    900     Value flowValue() const {
     900    Flow flowValue() const {
    901901      return (*_excess)[_target];
    902902    }
    … …  
    909909    /// \pre Either \ref run() or \ref init() must be called before
    910910    /// using this function.
    911     Value flow(const Arc& arc) const {
     911    Flow flow(const Arc& arc) const {
    912912      return (*_flow)[arc];
    913913    }

  • lemon/preflow.h

    r657 r658  
    3333  /// Default traits class of Preflow class.
    3434  /// \tparam GR Digraph type.
    35   /// \tparam CM Capacity map type.
    36   template <typename GR, typename CM>
     35  /// \tparam CAP Capacity map type.
     36  template <typename GR, typename CAP>
    3737  struct PreflowDefaultTraits {
    3838
    … …  
    4444    /// The type of the map that stores the arc capacities.
    4545    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    46     typedef CM CapacityMap;
     46    typedef CAP CapacityMap;
    4747
    4848    /// \brief The type of the flow values.
    … …  
    9595  ///
    9696  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// \e push-relabel algorithm producing a flow of maximum value in a
    98   /// digraph. The preflow algorithms are the fastest known maximum
     97  /// \e push-relabel algorithm producing a \ref max_flow
     98  /// "flow of maximum value" in a digraph.
     99  /// The preflow algorithms are the fastest known maximum
    99100  /// flow algorithms. The current implementation use a mixture of the
    100101  /// \e "highest label" and the \e "bound decrease" heuristics.
    … …  
    106107  ///
    107108  /// \tparam GR The type of the digraph the algorithm runs on.
    108   /// \tparam CM The type of the capacity map. The default map
     109  /// \tparam CAP The type of the capacity map. The default map
    109110  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    110111#ifdef DOXYGEN
    111   template <typename GR, typename CM, typename TR>
     112  template <typename GR, typename CAP, typename TR>
    112113#else
    113114  template <typename GR,
    114             typename CM = typename GR::template ArcMap<int>,
    115             typename TR = PreflowDefaultTraits<GR, CM> >
     115            typename CAP = typename GR::template ArcMap<int>,
     116            typename TR = PreflowDefaultTraits<GR, CAP> >
    116117#endif
    117118  class Preflow {
    … …  
    195196    ///@{
    196197
    197     template <typename _FlowMap>
     198    template <typename T>
    198199    struct SetFlowMapTraits : public Traits {
    199       typedef _FlowMap FlowMap;
     200      typedef T FlowMap;
    200201      static FlowMap *createFlowMap(const Digraph&) {
    201202        LEMON_ASSERT(false, "FlowMap is not initialized");
    … …  
    209210    /// \ref named-templ-param "Named parameter" for setting FlowMap
    210211    /// type.
    211     template <typename _FlowMap>
     212    template <typename T>
    212213    struct SetFlowMap
    213       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
     214      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
    214215      typedef Preflow<Digraph, CapacityMap,
    215                       SetFlowMapTraits<_FlowMap> > Create;
     216                      SetFlowMapTraits<T> > Create;
    216217    };
    217218
    218     template <typename _Elevator>
     219    template <typename T>
    219220    struct SetElevatorTraits : public Traits {
    220       typedef _Elevator Elevator;
     221      typedef T Elevator;
    221222      static Elevator *createElevator(const Digraph&, int) {
    222223        LEMON_ASSERT(false, "Elevator is not initialized");
    … …  
    234235    /// \ref run() or \ref init().
    235236    /// \sa SetStandardElevator
    236     template <typename _Elevator>
     237    template <typename T>
    237238    struct SetElevator
    238       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
     239      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
    239240      typedef Preflow<Digraph, CapacityMap,
    240                       SetElevatorTraits<_Elevator> > Create;
     241                      SetElevatorTraits<T> > Create;
    241242    };
    242243
    243     template <typename _Elevator>
     244    template <typename T>
    244245    struct SetStandardElevatorTraits : public Traits {
    245       typedef _Elevator Elevator;
     246      typedef T Elevator;
    246247      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    247248        return new Elevator(digraph, max_level);
    … …  
    261262    /// before calling \ref run() or \ref init().
    262263    /// \sa SetElevator
    263     template <typename _Elevator>
     264    template <typename T>
    264265    struct SetStandardElevator
    265266      : public Preflow<Digraph, CapacityMap,
    266                        SetStandardElevatorTraits<_Elevator> > {
     267                       SetStandardElevatorTraits<T> > {
    267268      typedef Preflow<Digraph, CapacityMap,
    268                       SetStandardElevatorTraits<_Elevator> > Create;
     269                      SetStandardElevatorTraits<T> > Create;
    269270    };
    270271
    … …  
    404405      _phase = true;
    405406      for (NodeIt n(_graph); n != INVALID; ++n) {
    406         _excess->set(n, 0);
     407        (*_excess)[n] = 0;
    407408      }
    408409
    … …  
    417418
    418419      std::vector<Node> queue;
    419       reached.set(_source, true);
     420      reached[_source] = true;
    420421
    421422      queue.push_back(_target);
    422       reached.set(_target, true);
     423      reached[_target] = true;
    423424      while (!queue.empty()) {
    424425        _level->initNewLevel();
    … …  
    429430            Node u = _graph.source(e);
    430431            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
    431               reached.set(u, true);
     432              reached[u] = true;
    432433              _level->initAddItem(u);
    433434              nqueue.push_back(u);
    … …  
    444445          if ((*_level)[u] == _level->maxLevel()) continue;
    445446          _flow->set(e, (*_capacity)[e]);
    446           _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
     447          (*_excess)[u] += (*_capacity)[e];
    447448          if (u != _target && !_level->active(u)) {
    448449            _level->activate(u);
    … …  
    478479        }
    479480        if (excess < 0 && n != _source) return false;
    480         _excess->set(n, excess);
     481        (*_excess)[n] = excess;
    481482      }
    482483
    … …  
    487488
    488489      std::vector<Node> queue;
    489       reached.set(_source, true);
     490      reached[_source] = true;
    490491
    491492      queue.push_back(_target);
    492       reached.set(_target, true);
     493      reached[_target] = true;
    493494      while (!queue.empty()) {
    494495        _level->initNewLevel();
    … …  
    500501            if (!reached[u] &&
    501502                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    502               reached.set(u, true);
     503              reached[u] = true;
    503504              _level->initAddItem(u);
    504505              nqueue.push_back(u);
    … …  
    508509            Node v = _graph.target(e);
    509510            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    510               reached.set(v, true);
     511              reached[v] = true;
    511512              _level->initAddItem(v);
    512513              nqueue.push_back(v);
    … …  
    524525          if ((*_level)[u] == _level->maxLevel()) continue;
    525526          _flow->set(e, (*_capacity)[e]);
    526           _excess->set(u, (*_excess)[u] + rem);
     527          (*_excess)[u] += rem;
    527528          if (u != _target && !_level->active(u)) {
    528529            _level->activate(u);
    … …  
    536537          if ((*_level)[v] == _level->maxLevel()) continue;
    537538          _flow->set(e, 0);
    538           _excess->set(v, (*_excess)[v] + rem);
     539          (*_excess)[v] += rem;
    539540          if (v != _target && !_level->active(v)) {
    540541            _level->activate(v);
    … …  
    577578              if (!_tolerance.less(rem, excess)) {
    578579                _flow->set(e, (*_flow)[e] + excess);
    579                 _excess->set(v, (*_excess)[v] + excess);
     580                (*_excess)[v] += excess;
    580581                excess = 0;
    581582                goto no_more_push_1;
    582583              } else {
    583584                excess -= rem;
    584                 _excess->set(v, (*_excess)[v] + rem);
     585                (*_excess)[v] += rem;
    585586                _flow->set(e, (*_capacity)[e]);
    586587              }
    … …  
    600601              if (!_tolerance.less(rem, excess)) {
    601602                _flow->set(e, (*_flow)[e] - excess);
    602                 _excess->set(v, (*_excess)[v] + excess);
     603                (*_excess)[v] += excess;
    603604                excess = 0;
    604605                goto no_more_push_1;
    605606              } else {
    606607                excess -= rem;
    607                 _excess->set(v, (*_excess)[v] + rem);
     608                (*_excess)[v] += rem;
    608609                _flow->set(e, 0);
    609610              }
    … …  
    615616        no_more_push_1:
    616617
    617           _excess->set(n, excess);
     618          (*_excess)[n] = excess;
    618619
    619620          if (excess != 0) {
    … …  
    650651              if (!_tolerance.less(rem, excess)) {
    651652                _flow->set(e, (*_flow)[e] + excess);
    652                 _excess->set(v, (*_excess)[v] + excess);
     653                (*_excess)[v] += excess;
    653654                excess = 0;
    654655                goto no_more_push_2;
    655656              } else {
    656657                excess -= rem;
    657                 _excess->set(v, (*_excess)[v] + rem);
     658                (*_excess)[v] += rem;
    658659                _flow->set(e, (*_capacity)[e]);
    659660              }
    … …  
    673674              if (!_tolerance.less(rem, excess)) {
    674675                _flow->set(e, (*_flow)[e] - excess);
    675                 _excess->set(v, (*_excess)[v] + excess);
     676                (*_excess)[v] += excess;
    676677                excess = 0;
    677678                goto no_more_push_2;
    678679              } else {
    679680                excess -= rem;
    680                 _excess->set(v, (*_excess)[v] + rem);
     681                (*_excess)[v] += rem;
    681682                _flow->set(e, 0);
    682683              }
    … …  
    688689        no_more_push_2:
    689690
    690           _excess->set(n, excess);
     691          (*_excess)[n] = excess;
    691692
    692693          if (excess != 0) {
    … …  
    731732      typename Digraph::template NodeMap<bool> reached(_graph);
    732733      for (NodeIt n(_graph); n != INVALID; ++n) {
    733         reached.set(n, (*_level)[n] < _level->maxLevel());
     734        reached[n] = (*_level)[n] < _level->maxLevel();
    734735      }
    735736
    … …  
    739740      std::vector<Node> queue;
    740741      queue.push_back(_source);
    741       reached.set(_source, true);
     742      reached[_source] = true;
    742743
    743744      while (!queue.empty()) {
    … …  
    749750            Node v = _graph.target(e);
    750751            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    751               reached.set(v, true);
     752              reached[v] = true;
    752753              _level->initAddItem(v);
    753754              nqueue.push_back(v);
    … …  
    758759            if (!reached[u] &&
    759760                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    760               reached.set(u, true);
     761              reached[u] = true;
    761762              _level->initAddItem(u);
    762763              nqueue.push_back(u);
    … …  
    792793            if (!_tolerance.less(rem, excess)) {
    793794              _flow->set(e, (*_flow)[e] + excess);
    794               _excess->set(v, (*_excess)[v] + excess);
     795              (*_excess)[v] += excess;
    795796              excess = 0;
    796797              goto no_more_push;
    797798            } else {
    798799              excess -= rem;
    799               _excess->set(v, (*_excess)[v] + rem);
     800              (*_excess)[v] += rem;
    800801              _flow->set(e, (*_capacity)[e]);
    801802            }
    … …  
    815816            if (!_tolerance.less(rem, excess)) {
    816817              _flow->set(e, (*_flow)[e] - excess);
    817               _excess->set(v, (*_excess)[v] + excess);
     818              (*_excess)[v] += excess;
    818819              excess = 0;
    819820              goto no_more_push;
    820821            } else {
    821822              excess -= rem;
    822               _excess->set(v, (*_excess)[v] + rem);
     823              (*_excess)[v] += rem;
    823824              _flow->set(e, 0);
    824825            }
    … …  
    830831      no_more_push:
    831832
    832         _excess->set(n, excess);
     833        (*_excess)[n] = excess;
    833834
    834835        if (excess != 0) {
    … …  
    947948    ///
    948949    /// \note This function calls \ref minCut() for each node, so it runs in
    949     /// \f$O(n)\f$ time.
     950    /// O(n) time.
    950951    ///
    951952    /// \pre Either \ref run() or \ref init() must be called before
Note: See TracChangeset for help on using the changeset viewer.