COIN-OR::LEMON - Graph Library

Changeset 1081:f1398882a928 in lemon


Ignore:
Timestamp:
08/08/11 12:36:16 (8 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.1
Phase:
public
Tags:
r1.1.4
Message:

Unify sources

Files:
68 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r844 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    276276This group contains the algorithms for finding shortest paths in digraphs.
    277277
    278  - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
    279279   source node when all arc lengths are non-negative.
    280280 - \ref Suurballe A successive shortest path algorithm for finding
     
    307307
    308308
    309 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     309\ref Circulation is a preflow push-relabel algorithm implemented directly
    310310for finding feasible circulations, which is a somewhat different problem,
    311311but it is strongly related to maximum flow.
  • doc/lgf.dox

    r1069 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/min_cost_flow.dox

    r710 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8282   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    8383     then \f$\pi(u)=0\f$.
    84  
     84
    8585Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    8686\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
     
    120120\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    121121
    122 It means that the total demand must be less or equal to the 
     122It means that the total demand must be less or equal to the
    123123total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
    124124positive) and all the demands have to be satisfied, but there
  • lemon/adaptors.h

    r703 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    419419      Parent::initialize(digraph);
    420420      _node_filter = &node_filter;
    421       _arc_filter = &arc_filter;     
     421      _arc_filter = &arc_filter;
    422422    }
    423423
     
    506506
    507507    template <typename V>
    508     class NodeMap 
    509       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
    510               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     508    class NodeMap
     509      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     510              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    511511      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    512         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     512        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    513513
    514514    public:
     
    533533
    534534    template <typename V>
    535     class ArcMap 
     535    class ArcMap
    536536      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    537               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     537              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    538538      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    539539        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     
    580580      Parent::initialize(digraph);
    581581      _node_filter = &node_filter;
    582       _arc_filter = &arc_filter;     
     582      _arc_filter = &arc_filter;
    583583    }
    584584
     
    649649
    650650    template <typename V>
    651     class NodeMap 
     651    class NodeMap
    652652      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    653653          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    654       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
     654      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    655655        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    656656
     
    676676
    677677    template <typename V>
    678     class ArcMap 
     678    class ArcMap
    679679      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    680680          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     
    10171017
    10181018    template <typename V>
    1019     class NodeMap 
     1019    class NodeMap
    10201020      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10211021          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1022       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1022      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10231023        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10241024
     
    10441044
    10451045    template <typename V>
    1046     class ArcMap 
     1046    class ArcMap
    10471047      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10481048          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1049       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1049      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10501050        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10511051
     
    10711071
    10721072    template <typename V>
    1073     class EdgeMap 
     1073    class EdgeMap
    10741074      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10751075        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1076       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1076      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10771077        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10781078
     
    11131113    NF* _node_filter;
    11141114    EF* _edge_filter;
    1115     SubGraphBase() 
    1116           : Parent(), _node_filter(0), _edge_filter(0) { }
     1115    SubGraphBase()
     1116          : Parent(), _node_filter(0), _edge_filter(0) { }
    11171117
    11181118    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     
    12151215
    12161216    template <typename V>
    1217     class NodeMap 
     1217    class NodeMap
    12181218      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12191219          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1220       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1220      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12211221        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12221222
     
    12421242
    12431243    template <typename V>
    1244     class ArcMap 
     1244    class ArcMap
    12451245      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12461246          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1247       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1247      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12481248        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12491249
     
    12691269
    12701270    template <typename V>
    1271     class EdgeMap 
     1271    class EdgeMap
    12721272      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12731273        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    1275         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1274      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1275        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12761276
    12771277    public:
     
    14961496#endif
    14971497    typedef DigraphAdaptorExtender<
    1498       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
     1498      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    14991499                     true> > Parent;
    15001500
     
    15171517    /// Creates a subgraph for the given digraph or graph with the
    15181518    /// given node filter map.
    1519     FilterNodes(GR& graph, NF& node_filter) 
     1519    FilterNodes(GR& graph, NF& node_filter)
    15201520      : Parent(), const_true_map()
    15211521    {
     
    15551555                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15561556    public GraphAdaptorExtender<
    1557       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1557      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15581558                   true> > {
    15591559
    15601560    typedef GraphAdaptorExtender<
    1561       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1561      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15621562                   true> > Parent;
    15631563
     
    16431643#endif
    16441644    typedef DigraphAdaptorExtender<
    1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
     1645      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    16461646                     AF, false> > Parent;
    16471647
     
    17491749  class FilterEdges :
    17501750    public GraphAdaptorExtender<
    1751       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1751      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17521752                   EF, false> > {
    17531753#endif
    17541754    typedef GraphAdaptorExtender<
    1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
     1755      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    17561756                   EF, false> > Parent;
    17571757
     
    17781778    /// Creates a subgraph for the given graph with the given edge
    17791779    /// filter map.
    1780     FilterEdges(GR& graph, EF& edge_filter) 
     1780    FilterEdges(GR& graph, EF& edge_filter)
    17811781      : Parent(), const_true_map() {
    17821782      Parent::initialize(graph, const_true_map, edge_filter);
     
    18461846      bool _forward;
    18471847
    1848       Arc(const Edge& edge, bool forward) 
     1848      Arc(const Edge& edge, bool forward)
    18491849        : _edge(edge), _forward(forward) {}
    18501850
     
    20862086
    20872087      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2088         : _forward(*adaptor._digraph, value), 
     2088        : _forward(*adaptor._digraph, value),
    20892089          _backward(*adaptor._digraph, value) {}
    20902090
     
    22042204    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22052205    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2206    
     2206
    22072207    typedef EdgeNotifier ArcNotifier;
    22082208    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
     
    27082708           typename FM = CM,
    27092709           typename TL = Tolerance<typename CM::Value> >
    2710   class ResidualDigraph 
     2710  class ResidualDigraph
    27112711    : public SubDigraph<
    27122712        Undirector<const DGR>,
     
    27652765    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27662766                    FM& flow, const TL& tolerance = Tolerance())
    2767       : Parent(), _capacity(&capacity), _flow(&flow), 
     2767      : Parent(), _capacity(&capacity), _flow(&flow),
    27682768        _graph(digraph), _node_filter(),
    27692769        _forward_filter(capacity, flow, tolerance),
     
    28472847
    28482848      /// Constructor
    2849       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2849      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28502850        : _adaptor(&adaptor) {}
    28512851
     
    34243424    /// to get a node map of the split digraph.
    34253425    /// Its value type is inherited from the first node map type (\c IN).
    3426     /// \tparam IN The type of the node map for the in-nodes. 
     3426    /// \tparam IN The type of the node map for the in-nodes.
    34273427    /// \tparam OUT The type of the node map for the out-nodes.
    34283428    template <typename IN, typename OUT>
  • lemon/bin_heap.h

    r1064 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/array_map.h

    r664 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7171
    7272  private:
    73  
     73
    7474    // The MapBase of the Map which imlements the core regisitry function.
    7575    typedef typename Notifier::ObserverBase Parent;
  • lemon/bits/default_map.h

    r674 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    158158  public:
    159159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    160    
     160
    161161    typedef typename Parent::GraphType GraphType;
    162162    typedef typename Parent::Value Value;
  • lemon/bits/edge_set_extender.h

    r967 r1081  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464    Node oppositeNode(const Node &n, const Arc &e) const {
    6565      if (n == Parent::source(e))
    66         return Parent::target(e);
     66        return Parent::target(e);
    6767      else if(n==Parent::target(e))
    68         return Parent::source(e);
     68        return Parent::source(e);
    6969      else
    70         return INVALID;
     70        return INVALID;
    7171    }
    7272
     
    9292    // Iterable extensions
    9393
    94     class NodeIt : public Node { 
     94    class NodeIt : public Node {
    9595      const Digraph* digraph;
    9696    public:
     
    101101
    102102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    103         _graph.first(static_cast<Node&>(*this));
    104       }
    105 
    106       NodeIt(const Digraph& _graph, const Node& node) 
    107         : Node(node), digraph(&_graph) {}
    108 
    109       NodeIt& operator++() { 
    110         digraph->next(*this);
    111         return *this;
    112       }
    113 
    114     };
    115 
    116 
    117     class ArcIt : public Arc { 
     103        _graph.first(static_cast<Node&>(*this));
     104      }
     105
     106      NodeIt(const Digraph& _graph, const Node& node)
     107        : Node(node), digraph(&_graph) {}
     108
     109      NodeIt& operator++() {
     110        digraph->next(*this);
     111        return *this;
     112      }
     113
     114    };
     115
     116
     117    class ArcIt : public Arc {
    118118      const Digraph* digraph;
    119119    public:
     
    124124
    125125      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    126         _graph.first(static_cast<Arc&>(*this));
    127       }
    128 
    129       ArcIt(const Digraph& _graph, const Arc& e) : 
    130         Arc(e), digraph(&_graph) { }
    131 
    132       ArcIt& operator++() { 
    133         digraph->next(*this);
    134         return *this;
    135       }
    136 
    137     };
    138 
    139 
    140     class OutArcIt : public Arc { 
     126        _graph.first(static_cast<Arc&>(*this));
     127      }
     128
     129      ArcIt(const Digraph& _graph, const Arc& e) :
     130        Arc(e), digraph(&_graph) { }
     131
     132      ArcIt& operator++() {
     133        digraph->next(*this);
     134        return *this;
     135      }
     136
     137    };
     138
     139
     140    class OutArcIt : public Arc {
    141141      const Digraph* digraph;
    142142    public:
     
    146146      OutArcIt(Invalid i) : Arc(i) { }
    147147
    148       OutArcIt(const Digraph& _graph, const Node& node) 
    149         : digraph(&_graph) {
    150         _graph.firstOut(*this, node);
    151       }
    152 
    153       OutArcIt(const Digraph& _graph, const Arc& arc) 
    154         : Arc(arc), digraph(&_graph) {}
    155 
    156       OutArcIt& operator++() { 
    157         digraph->nextOut(*this);
    158         return *this;
    159       }
    160 
    161     };
    162 
    163 
    164     class InArcIt : public Arc { 
     148      OutArcIt(const Digraph& _graph, const Node& node)
     149        : digraph(&_graph) {
     150        _graph.firstOut(*this, node);
     151      }
     152
     153      OutArcIt(const Digraph& _graph, const Arc& arc)
     154        : Arc(arc), digraph(&_graph) {}
     155
     156      OutArcIt& operator++() {
     157        digraph->nextOut(*this);
     158        return *this;
     159      }
     160
     161    };
     162
     163
     164    class InArcIt : public Arc {
    165165      const Digraph* digraph;
    166166    public:
     
    170170      InArcIt(Invalid i) : Arc(i) { }
    171171
    172       InArcIt(const Digraph& _graph, const Node& node) 
    173         : digraph(&_graph) {
    174         _graph.firstIn(*this, node);
    175       }
    176 
    177       InArcIt(const Digraph& _graph, const Arc& arc) : 
    178         Arc(arc), digraph(&_graph) {}
    179 
    180       InArcIt& operator++() { 
    181         digraph->nextIn(*this);
    182         return *this;
     172      InArcIt(const Digraph& _graph, const Node& node)
     173        : digraph(&_graph) {
     174        _graph.firstIn(*this, node);
     175      }
     176
     177      InArcIt(const Digraph& _graph, const Arc& arc) :
     178        Arc(arc), digraph(&_graph) {}
     179
     180      InArcIt& operator++() {
     181        digraph->nextIn(*this);
     182        return *this;
    183183      }
    184184
     
    216216
    217217    // Mappable extension
    218    
     218
    219219    template <typename _Value>
    220     class ArcMap 
     220    class ArcMap
    221221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    222222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223223
    224224    public:
    225       explicit ArcMap(const Digraph& _g) 
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v) 
    228         : Parent(_g, _v) {}
     225      explicit ArcMap(const Digraph& _g)
     226        : Parent(_g) {}
     227      ArcMap(const Digraph& _g, const _Value& _v)
     228        : Parent(_g, _v) {}
    229229
    230230      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     231        return operator=<ArcMap>(cmap);
    232232      }
    233233
     
    235235      ArcMap& operator=(const CMap& cmap) {
    236236        Parent::operator=(cmap);
    237         return *this;
     237        return *this;
    238238      }
    239239
     
    248248      return arc;
    249249    }
    250    
     250
    251251    void clear() {
    252252      notifier(Arc()).clear();
     
    313313    Node oppositeNode(const Node &n, const Edge &e) const {
    314314      if( n == Parent::u(e))
    315         return Parent::v(e);
     315        return Parent::v(e);
    316316      else if( n == Parent::v(e))
    317         return Parent::u(e);
     317        return Parent::u(e);
    318318      else
    319         return INVALID;
     319        return INVALID;
    320320    }
    321321
     
    341341
    342342    using Parent::notifier;
    343    
     343
    344344    ArcNotifier& notifier(Arc) const {
    345345      return arc_notifier;
     
    351351
    352352
    353     class NodeIt : public Node { 
     353    class NodeIt : public Node {
    354354      const Graph* graph;
    355355    public:
     
    360360
    361361      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    362         _graph.first(static_cast<Node&>(*this));
    363       }
    364 
    365       NodeIt(const Graph& _graph, const Node& node) 
    366         : Node(node), graph(&_graph) {}
    367 
    368       NodeIt& operator++() { 
    369         graph->next(*this);
    370         return *this;
    371       }
    372 
    373     };
    374 
    375 
    376     class ArcIt : public Arc { 
     362        _graph.first(static_cast<Node&>(*this));
     363      }
     364
     365      NodeIt(const Graph& _graph, const Node& node)
     366        : Node(node), graph(&_graph) {}
     367
     368      NodeIt& operator++() {
     369        graph->next(*this);
     370        return *this;
     371      }
     372
     373    };
     374
     375
     376    class ArcIt : public Arc {
    377377      const Graph* graph;
    378378    public:
     
    383383
    384384      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    385         _graph.first(static_cast<Arc&>(*this));
    386       }
    387 
    388       ArcIt(const Graph& _graph, const Arc& e) : 
    389         Arc(e), graph(&_graph) { }
    390 
    391       ArcIt& operator++() { 
    392         graph->next(*this);
    393         return *this;
    394       }
    395 
    396     };
    397 
    398 
    399     class OutArcIt : public Arc { 
     385        _graph.first(static_cast<Arc&>(*this));
     386      }
     387
     388      ArcIt(const Graph& _graph, const Arc& e) :
     389        Arc(e), graph(&_graph) { }
     390
     391      ArcIt& operator++() {
     392        graph->next(*this);
     393        return *this;
     394      }
     395
     396    };
     397
     398
     399    class OutArcIt : public Arc {
    400400      const Graph* graph;
    401401    public:
     
    405405      OutArcIt(Invalid i) : Arc(i) { }
    406406
    407       OutArcIt(const Graph& _graph, const Node& node) 
    408         : graph(&_graph) {
    409         _graph.firstOut(*this, node);
    410       }
    411 
    412       OutArcIt(const Graph& _graph, const Arc& arc) 
    413         : Arc(arc), graph(&_graph) {}
    414 
    415       OutArcIt& operator++() { 
    416         graph->nextOut(*this);
    417         return *this;
    418       }
    419 
    420     };
    421 
    422 
    423     class InArcIt : public Arc { 
     407      OutArcIt(const Graph& _graph, const Node& node)
     408        : graph(&_graph) {
     409        _graph.firstOut(*this, node);
     410      }
     411
     412      OutArcIt(const Graph& _graph, const Arc& arc)
     413        : Arc(arc), graph(&_graph) {}
     414
     415      OutArcIt& operator++() {
     416        graph->nextOut(*this);
     417        return *this;
     418      }
     419
     420    };
     421
     422
     423    class InArcIt : public Arc {
    424424      const Graph* graph;
    425425    public:
     
    429429      InArcIt(Invalid i) : Arc(i) { }
    430430
    431       InArcIt(const Graph& _graph, const Node& node) 
    432         : graph(&_graph) {
    433         _graph.firstIn(*this, node);
    434       }
    435 
    436       InArcIt(const Graph& _graph, const Arc& arc) : 
    437         Arc(arc), graph(&_graph) {}
    438 
    439       InArcIt& operator++() { 
    440         graph->nextIn(*this);
    441         return *this;
    442       }
    443 
    444     };
    445 
    446 
    447     class EdgeIt : public Parent::Edge { 
     431      InArcIt(const Graph& _graph, const Node& node)
     432        : graph(&_graph) {
     433        _graph.firstIn(*this, node);
     434      }
     435
     436      InArcIt(const Graph& _graph, const Arc& arc) :
     437        Arc(arc), graph(&_graph) {}
     438
     439      InArcIt& operator++() {
     440        graph->nextIn(*this);
     441        return *this;
     442      }
     443
     444    };
     445
     446
     447    class EdgeIt : public Parent::Edge {
    448448      const Graph* graph;
    449449    public:
     
    454454
    455455      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    456         _graph.first(static_cast<Edge&>(*this));
    457       }
    458 
    459       EdgeIt(const Graph& _graph, const Edge& e) : 
    460         Edge(e), graph(&_graph) { }
    461 
    462       EdgeIt& operator++() { 
    463         graph->next(*this);
    464         return *this;
     456        _graph.first(static_cast<Edge&>(*this));
     457      }
     458
     459      EdgeIt(const Graph& _graph, const Edge& e) :
     460        Edge(e), graph(&_graph) { }
     461
     462      EdgeIt& operator++() {
     463        graph->next(*this);
     464        return *this;
    465465      }
    466466
     
    478478
    479479      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    480         _graph.firstInc(*this, direction, n);
     480        _graph.firstInc(*this, direction, n);
    481481      }
    482482
    483483      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    484         : graph(&_graph), Edge(ue) {
    485         direction = (_graph.source(ue) == n);
     484        : graph(&_graph), Edge(ue) {
     485        direction = (_graph.source(ue) == n);
    486486      }
    487487
    488488      IncEdgeIt& operator++() {
    489         graph->nextInc(*this, direction);
    490         return *this;
     489        graph->nextInc(*this, direction);
     490        return *this;
    491491      }
    492492    };
     
    535535
    536536    template <typename _Value>
    537     class ArcMap 
     537    class ArcMap
    538538      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    539539      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    540540
    541541    public:
    542       explicit ArcMap(const Graph& _g) 
    543         : Parent(_g) {}
    544       ArcMap(const Graph& _g, const _Value& _v) 
    545         : Parent(_g, _v) {}
     542      explicit ArcMap(const Graph& _g)
     543        : Parent(_g) {}
     544      ArcMap(const Graph& _g, const _Value& _v)
     545        : Parent(_g, _v) {}
    546546
    547547      ArcMap& operator=(const ArcMap& cmap) {
    548         return operator=<ArcMap>(cmap);
     548        return operator=<ArcMap>(cmap);
    549549      }
    550550
     
    552552      ArcMap& operator=(const CMap& cmap) {
    553553        Parent::operator=(cmap);
    554         return *this;
     554        return *this;
    555555      }
    556556
     
    559559
    560560    template <typename _Value>
    561     class EdgeMap 
     561    class EdgeMap
    562562      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    563563      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    564564
    565565    public:
    566       explicit EdgeMap(const Graph& _g) 
    567         : Parent(_g) {}
    568 
    569       EdgeMap(const Graph& _g, const _Value& _v) 
    570         : Parent(_g, _v) {}
     566      explicit EdgeMap(const Graph& _g)
     567        : Parent(_g) {}
     568
     569      EdgeMap(const Graph& _g, const _Value& _v)
     570        : Parent(_g, _v) {}
    571571
    572572      EdgeMap& operator=(const EdgeMap& cmap) {
    573         return operator=<EdgeMap>(cmap);
     573        return operator=<EdgeMap>(cmap);
    574574      }
    575575
     
    577577      EdgeMap& operator=(const CMap& cmap) {
    578578        Parent::operator=(cmap);
    579         return *this;
     579        return *this;
    580580      }
    581581
     
    594594      return edge;
    595595    }
    596    
     596
    597597    void clear() {
    598598      notifier(Arc()).clear();
     
    620620      arc_notifier.clear();
    621621    }
    622    
     622
    623623  };
    624624
  • lemon/bits/graph_adaptor_extender.h

    r965 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/map_extender.h

    r1064 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/path_dump.h

    r973 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/solver_bits.h

    r566 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/windows.cc

    r1053 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999      GetSystemTime(&time);
    100100      char buf1[11], buf2[9], buf3[5];
    101           if (GetDateFormat(MY_LOCALE, 0, &time,
     101          if (GetDateFormat(MY_LOCALE, 0, &time,
    102102                        ("ddd MMM dd"), buf1, 11) &&
    103103          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/cbc.h

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    121121    int _message_level;
    122122
    123    
     123
    124124
    125125  };
  • lemon/circulation.h

    r735 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6060    /// \brief The type of supply map.
    6161    ///
    62     /// The type of the map that stores the signed supply values of the 
    63     /// nodes. 
     62    /// The type of the map that stores the signed supply values of the
     63    /// nodes.
    6464    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    6565    typedef SM SupplyMap;
     
    135135     \geq sup(u) \quad \forall u\in V, \f]
    136136     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    137      
     137
    138138     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    139139     zero or negative in order to have a feasible solution (since the sum
     
    145145     constraints have to be satisfied with equality, i.e. all demands
    146146     have to be satisfied and all supplies have to be used.
    147      
     147
    148148     If you need the opposite inequalities in the supply/demand constraints
    149149     (i.e. the total demand is less than the total supply and all the demands
     
    326326    /// \param graph The digraph the algorithm runs on.
    327327    /// \param lower The lower bounds for the flow values on the arcs.
    328     /// \param upper The upper bounds (capacities) for the flow values 
     328    /// \param upper The upper bounds (capacities) for the flow values
    329329    /// on the arcs.
    330330    /// \param supply The signed supply values of the nodes.
  • lemon/clp.cc

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/clp.h

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    138138
    139139    virtual void _messageLevel(MessageLevel);
    140    
     140
    141141  public:
    142142
  • lemon/concepts/digraph.h

    r627 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    436436      private:
    437437        ///Copy constructor
    438         NodeMap(const NodeMap& nm) : 
     438        NodeMap(const NodeMap& nm) :
    439439          ReferenceMap<Node, T, T&, const T&>(nm) { }
    440440        ///Assignment operator
  • lemon/concepts/graph_components.h

    r713 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3939    /// \note This class is a template class so that we can use it to
    4040    /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same 
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
    4242    /// base class. For \c Node you should instantiate it with character
    4343    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
     
    9090      ///
    9191      /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in 
     92      /// It makes possible to use graph item types as key types in
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
     
    123123    /// This class describes the base interface of directed graph types.
    124124    /// All digraph %concepts have to conform to this class.
    125     /// It just provides types for nodes and arcs and functions 
     125    /// It just provides types for nodes and arcs and functions
    126126    /// to get the source and the target nodes of arcs.
    127127    class BaseDigraphComponent {
     
    427427    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    428428    ///
    429     /// This class describes the concept of \c NodeIt, \c ArcIt and 
     429    /// This class describes the concept of \c NodeIt, \c ArcIt and
    430430    /// \c EdgeIt subtypes of digraph and graph types.
    431431    template <typename GR, typename Item>
     
    467467      /// next item.
    468468      GraphItemIt& operator++() { return *this; }
    469  
     469
    470470      /// \brief Equality operator
    471471      ///
     
    502502    };
    503503
    504     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     504    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    505505    /// \c IncEdgeIt types.
    506506    ///
    507     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     507    /// This class describes the concept of \c InArcIt, \c OutArcIt
    508508    /// and \c IncEdgeIt subtypes of digraph and graph types.
    509509    ///
    510510    /// \note Since these iterator classes do not inherit from the same
    511511    /// base class, there is an additional template parameter (selector)
    512     /// \c sel. For \c InArcIt you should instantiate it with character 
     512    /// \c sel. For \c InArcIt you should instantiate it with character
    513513    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    514514    template <typename GR,
     
    531531      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    532532
    533       /// \brief Constructor that sets the iterator to the first 
     533      /// \brief Constructor that sets the iterator to the first
    534534      /// incoming or outgoing arc.
    535535      ///
    536       /// Constructor that sets the iterator to the first arc 
     536      /// Constructor that sets the iterator to the first arc
    537537      /// incoming to or outgoing from the given node.
    538538      explicit GraphIncIt(const GR&, const Base&) {}
     
    805805      /// \brief Return the first edge incident to the given node.
    806806      ///
    807       /// This function gives back the first edge incident to the given 
     807      /// This function gives back the first edge incident to the given
    808808      /// node. The bool parameter gives back the direction for which the
    809       /// source node of the directed arc representing the edge is the 
     809      /// source node of the directed arc representing the edge is the
    810810      /// given node.
    811811      void firstInc(Edge&, bool&, const Node&) const {}
     
    814814      /// given node.
    815815      ///
    816       /// This function gives back the next edge incident to the given 
     816      /// This function gives back the next edge incident to the given
    817817      /// node. The bool parameter should be used as \c firstInc() use it.
    818818      void nextInc(Edge&, bool&) const {}
     
    991991    ///
    992992    /// This class describes the concept of standard graph maps, i.e.
    993     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     993    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    994994    /// graph types, which can be used for associating data to graph items.
    995995    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10461046          _Map m1(g);
    10471047          _Map m2(g,t);
    1048          
     1048
    10491049          // Copy constructor
    10501050          // _Map m3(m);
     
    10691069    ///
    10701070    /// This class describes the interface of mappable directed graphs.
    1071     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1071    /// It extends \ref BaseDigraphComponent with the standard digraph
    10721072    /// map classes, namely \c NodeMap and \c ArcMap.
    10731073    /// This concept is part of the Digraph concept.
     
    12061206    ///
    12071207    /// This class describes the interface of mappable undirected graphs.
    1208     /// It extends \ref MappableDigraphComponent with the standard graph 
     1208    /// It extends \ref MappableDigraphComponent with the standard graph
    12091209    /// map class for edges (\c EdgeMap).
    12101210    /// This concept is part of the Graph concept.
     
    12911291    ///
    12921292    /// This class describes the interface of extendable directed graphs.
    1293     /// It extends \ref BaseDigraphComponent with functions for adding 
     1293    /// It extends \ref BaseDigraphComponent with functions for adding
    12941294    /// nodes and arcs to the digraph.
    12951295    /// This concept requires \ref AlterableDigraphComponent.
     
    13351335    ///
    13361336    /// This class describes the interface of extendable undirected graphs.
    1337     /// It extends \ref BaseGraphComponent with functions for adding 
     1337    /// It extends \ref BaseGraphComponent with functions for adding
    13381338    /// nodes and edges to the graph.
    13391339    /// This concept requires \ref AlterableGraphComponent.
     
    13791379    ///
    13801380    /// This class describes the interface of erasable directed graphs.
    1381     /// It extends \ref BaseDigraphComponent with functions for removing 
     1381    /// It extends \ref BaseDigraphComponent with functions for removing
    13821382    /// nodes and arcs from the digraph.
    13831383    /// This concept requires \ref AlterableDigraphComponent.
     
    13921392      /// \brief Erase a node from the digraph.
    13931393      ///
    1394       /// This function erases the given node from the digraph and all arcs 
     1394      /// This function erases the given node from the digraph and all arcs
    13951395      /// connected to the node.
    13961396      void erase(const Node&) {}
     
    14181418    ///
    14191419    /// This class describes the interface of erasable undirected graphs.
    1420     /// It extends \ref BaseGraphComponent with functions for removing 
     1420    /// It extends \ref BaseGraphComponent with functions for removing
    14211421    /// nodes and edges from the graph.
    14221422    /// This concept requires \ref AlterableGraphComponent.
  • lemon/concepts/maps.h

    r1064 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/connectivity.h

    r695 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    259259  /// \return \c true if the digraph is strongly connected.
    260260  /// \note By definition, the empty digraph is strongly connected.
    261   /// 
     261  ///
    262262  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
    263263  /// \see connected()
     
    311311  /// \ingroup graph_properties
    312312  ///
    313   /// \brief Count the number of strongly connected components of a 
     313  /// \brief Count the number of strongly connected components of a
    314314  /// directed graph
    315315  ///
     
    745745  /// \brief Check whether an undirected graph is bi-node-connected.
    746746  ///
    747   /// This function checks whether the given undirected graph is 
     747  /// This function checks whether the given undirected graph is
    748748  /// bi-node-connected, i.e. any two edges are on same circle.
    749749  ///
     
    759759  /// \ingroup graph_properties
    760760  ///
    761   /// \brief Count the number of bi-node-connected components of an 
     761  /// \brief Count the number of bi-node-connected components of an
    762762  /// undirected graph.
    763763  ///
     
    813813  /// \retval compMap A writable edge map. The values will be set from 0
    814814  /// to the number of the bi-node-connected components minus one. Each
    815   /// value of the map will be set exactly once, and the values of a 
     815  /// value of the map will be set exactly once, and the values of a
    816816  /// certain component will be set continuously.
    817817  /// \return The number of bi-node-connected components.
     
    859859  ///
    860860  /// \param graph The undirected graph.
    861   /// \retval cutMap A writable node map. The values will be set to 
     861  /// \retval cutMap A writable node map. The values will be set to
    862862  /// \c true for the nodes that separate two or more components
    863863  /// (exactly once for each cut node), and will not be changed for
     
    10861086  /// \brief Check whether an undirected graph is bi-edge-connected.
    10871087  ///
    1088   /// This function checks whether the given undirected graph is 
     1088  /// This function checks whether the given undirected graph is
    10891089  /// bi-edge-connected, i.e. any two nodes are connected with at least
    10901090  /// two edge-disjoint paths.
     
    11931193  ///
    11941194  /// This function finds the bi-edge-connected cut edges in the given
    1195   /// undirected graph. 
     1195  /// undirected graph.
    11961196  ///
    11971197  /// The bi-edge-connected components are the classes of an equivalence
     
    13501350  /// \param digraph The digraph.
    13511351  /// \retval order A readable and writable node map. The values will be
    1352   /// set from 0 to the number of the nodes in the digraph minus one. 
     1352  /// set from 0 to the number of the nodes in the digraph minus one.
    13531353  /// Each value of the map will be set exactly once, and the values will
    13541354  /// be set descending order.
  • lemon/core.h

    r984 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    12421242  protected:
    12431243
    1244     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1244    class AutoNodeMap :
     1245      public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
    12451246      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12461247
     
    12811282    };
    12821283
    1283   protected: 
     1284  protected:
    12841285
    12851286    const Digraph &_g;
  • lemon/cplex.cc

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    457457
    458458  void CplexBase::_applyMessageLevel() {
    459     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     459    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    460460                   _message_enabled ? CPX_ON : CPX_OFF);
    461461  }
  • lemon/dfs.h

    r1009 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/dimacs.h

    r631 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6262
    6363  ///This function starts seeking the beginning of the given file for the
    64   ///problem type and size info. 
     64  ///problem type and size info.
    6565  ///The found data is returned in a special struct that can be evaluated
    6666  ///and passed to the appropriate reader function.
     
    213213        std::numeric_limits<Capacity>::infinity() :
    214214        std::numeric_limits<Capacity>::max();
    215  
     215
    216216    while (is >> c) {
    217217      switch (c) {
     
    238238          e = g.addArc(nodes[i], nodes[j]);
    239239          capacity.set(e, _cap);
    240         } 
     240        }
    241241        else if (desc.type==DimacsDescriptor::MAX) {
    242242          is >> i >> j >> _cap;
     
    363363    g.addArc(s,t);
    364364  }
    365  
     365
    366366  /// \brief DIMACS plain (di)graph reader function.
    367367  ///
    368368  /// This function reads a plain (di)graph without any designated nodes
    369   /// and maps (e.g. a matching instance) from DIMACS format, i.e. from 
     369  /// and maps (e.g. a matching instance) from DIMACS format, i.e. from
    370370  /// DIMACS files having a line starting with
    371371  /// \code
     
    393393      nodes[k] = g.addNode();
    394394    }
    395    
     395
    396396    while (is >> c) {
    397397      switch (c) {
  • lemon/edge_set.h

    r717 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/euler.h

    r695 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727/// \ingroup graph_properties
    2828/// \file
    29 /// \brief Euler tour iterators and a function for checking the \e Eulerian 
     29/// \brief Euler tour iterators and a function for checking the \e Eulerian
    3030/// property.
    3131///
     
    4242  ///
    4343  ///For example, if the given digraph has an Euler tour (i.e it has only one
    44   ///non-trivial component and the in-degree is equal to the out-degree 
     44  ///non-trivial component and the in-degree is equal to the out-degree
    4545  ///for all nodes), then the following code will put the arcs of \c g
    4646  ///to the vector \c et according to an Euler tour of \c g.
     
    139139  ///and \c Edge types of the graph.
    140140  ///
    141   ///For example, if the given graph has an Euler tour (i.e it has only one 
     141  ///For example, if the given graph has an Euler tour (i.e it has only one
    142142  ///non-trivial component and the degree of each node is even),
    143143  ///the following code will print the arc IDs according to an
     
    148148  ///  }
    149149  ///\endcode
    150   ///Although this iterator is for undirected graphs, it still returns 
     150  ///Although this iterator is for undirected graphs, it still returns
    151151  ///arcs in order to indicate the direction of the tour.
    152152  ///(But arcs convert to edges, of course.)
     
    234234    /// Postfix incrementation.
    235235    ///
    236     ///\warning This incrementation returns an \c Arc (which converts to 
     236    ///\warning This incrementation returns an \c Arc (which converts to
    237237    ///an \c Edge), not an \ref EulerIt, as one may expect.
    238238    Arc operator++(int)
  • lemon/glpk.h

    r900 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3131    class VoidPtr {
    3232    private:
    33       void *_ptr;     
     33      void *_ptr;
    3434    public:
    3535      VoidPtr() : _ptr(0) {}
     
    3939
    4040      template <typename T>
    41       VoidPtr& operator=(T* ptr) { 
    42         _ptr = reinterpret_cast<void*>(ptr); 
     41      VoidPtr& operator=(T* ptr) {
     42        _ptr = reinterpret_cast<void*>(ptr);
    4343        return *this;
    4444      }
     
    124124      }
    125125    };
    126    
     126
    127127    static FreeEnvHelper freeEnvHelper;
    128128
    129129  protected:
    130    
     130
    131131    int _message_level;
    132    
     132
    133133  public:
    134134
  • lemon/gomory_hu.h

    r643 r1081  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2828
    2929/// \ingroup min_cut
    30 /// \file 
     30/// \file
    3131/// \brief Gomory-Hu cut tree in graphs.
    3232
     
    3939  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
    4040  /// may contain edges which are not in the original graph. It has the
    41   /// property that the minimum capacity edge of the path between two nodes 
     41  /// property that the minimum capacity edge of the path between two nodes
    4242  /// in this tree has the same weight as the minimum cut in the graph
    4343  /// between these nodes. Moreover the components obtained by removing
     
    4545  /// Therefore once this tree is computed, the minimum cut between any pair
    4646  /// of nodes can easily be obtained.
    47   /// 
     47  ///
    4848  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    4949  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     
    6161#ifdef DOXYGEN
    6262  template <typename GR,
    63             typename CAP>
     63            typename CAP>
    6464#else
    6565  template <typename GR,
    66             typename CAP = typename GR::template EdgeMap<int> >
     66            typename CAP = typename GR::template EdgeMap<int> >
    6767#endif
    6868  class GomoryHu {
     
    7575    /// The value type of capacities
    7676    typedef typename Capacity::Value Value;
    77    
     77
    7878  private:
    7979
     
    9090    void createStructures() {
    9191      if (!_pred) {
    92         _pred = new typename Graph::template NodeMap<Node>(_graph);
     92        _pred = new typename Graph::template NodeMap<Node>(_graph);
    9393      }
    9494      if (!_weight) {
    95         _weight = new typename Graph::template NodeMap<Value>(_graph);
     95        _weight = new typename Graph::template NodeMap<Value>(_graph);
    9696      }
    9797      if (!_order) {
    98         _order = new typename Graph::template NodeMap<int>(_graph);
     98        _order = new typename Graph::template NodeMap<int>(_graph);
    9999      }
    100100    }
     
    102102    void destroyStructures() {
    103103      if (_pred) {
    104         delete _pred;
     104        delete _pred;
    105105      }
    106106      if (_weight) {
    107         delete _weight;
     107        delete _weight;
    108108      }
    109109      if (_order) {
    110         delete _order;
    111       }
    112     }
    113  
     110        delete _order;
     111      }
     112    }
     113
    114114  public:
    115115
     
    119119    /// \param graph The undirected graph the algorithm runs on.
    120120    /// \param capacity The edge capacity map.
    121     GomoryHu(const Graph& graph, const Capacity& capacity) 
     121    GomoryHu(const Graph& graph, const Capacity& capacity)
    122122      : _graph(graph), _capacity(capacity),
    123         _pred(0), _weight(0), _order(0)
     123        _pred(0), _weight(0), _order(0)
    124124    {
    125125      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
     
    135135
    136136  private:
    137  
     137
    138138    // Initialize the internal data structures
    139139    void init() {
     
    146146      }
    147147      (*_pred)[_root] = INVALID;
    148       (*_weight)[_root] = std::numeric_limits<Value>::max(); 
     148      (*_weight)[_root] = std::numeric_limits<Value>::max();
    149149    }
    150150
     
    155155
    156156      for (NodeIt n(_graph); n != INVALID; ++n) {
    157         if (n == _root) continue;
    158 
    159         Node pn = (*_pred)[n];
    160         fa.source(n);
    161         fa.target(pn);
    162 
    163         fa.runMinCut();
    164 
    165         (*_weight)[n] = fa.flowValue();
    166 
    167         for (NodeIt nn(_graph); nn != INVALID; ++nn) {
    168           if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
    169             (*_pred)[nn] = n;
    170           }
    171         }
    172         if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
    173           (*_pred)[n] = (*_pred)[pn];
    174           (*_pred)[pn] = n;
    175           (*_weight)[n] = (*_weight)[pn];
    176           (*_weight)[pn] = fa.flowValue();
    177         }
     157        if (n == _root) continue;
     158
     159        Node pn = (*_pred)[n];
     160        fa.source(n);
     161        fa.target(pn);
     162
     163        fa.runMinCut();
     164
     165        (*_weight)[n] = fa.flowValue();
     166
     167        for (NodeIt nn(_graph); nn != INVALID; ++nn) {
     168          if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
     169            (*_pred)[nn] = n;
     170          }
     171        }
     172        if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
     173          (*_pred)[n] = (*_pred)[pn];
     174          (*_pred)[pn] = n;
     175          (*_weight)[n] = (*_weight)[pn];
     176          (*_weight)[pn] = fa.flowValue();
     177        }
    178178      }
    179179
     
    182182
    183183      for (NodeIt n(_graph); n != INVALID; ++n) {
    184         std::vector<Node> st;
    185         Node nn = n;
    186         while ((*_order)[nn] == -1) {
    187           st.push_back(nn);
    188           nn = (*_pred)[nn];
    189         }
    190         while (!st.empty()) {
    191           (*_order)[st.back()] = index++;
    192           st.pop_back();
    193         }
     184        std::vector<Node> st;
     185        Node nn = n;
     186        while ((*_order)[nn] == -1) {
     187          st.push_back(nn);
     188          nn = (*_pred)[nn];
     189        }
     190        while (!st.empty()) {
     191          (*_order)[st.back()] = index++;
     192          st.pop_back();
     193        }
    194194      }
    195195    }
     
    198198
    199199    ///\name Execution Control
    200  
     200
    201201    ///@{
    202202
     
    208208      start();
    209209    }
    210    
     210
    211211    /// @}
    212212
     
    233233    /// Gomory-Hu tree.
    234234    ///
    235     /// This function returns the weight of the predecessor edge of the 
     235    /// This function returns the weight of the predecessor edge of the
    236236    /// given node in the Gomory-Hu tree.
    237237    /// If \c node is the root of the tree, the result is undefined.
     
    255255    ///
    256256    /// This function returns the minimum cut value between the nodes
    257     /// \c s and \c t. 
     257    /// \c s and \c t.
    258258    /// It finds the nearest common ancestor of the given nodes in the
    259259    /// Gomory-Hu tree and calculates the minimum weight edge on the
     
    264264      Node sn = s, tn = t;
    265265      Value value = std::numeric_limits<Value>::max();
    266      
     266
    267267      while (sn != tn) {
    268         if ((*_order)[sn] < (*_order)[tn]) {
    269           if ((*_weight)[tn] <= value) value = (*_weight)[tn];
    270           tn = (*_pred)[tn];
    271         } else {
    272           if ((*_weight)[sn] <= value) value = (*_weight)[sn];
    273           sn = (*_pred)[sn];
    274         }
     268        if ((*_order)[sn] < (*_order)[tn]) {
     269          if ((*_weight)[tn] <= value) value = (*_weight)[tn];
     270          tn = (*_pred)[tn];
     271        } else {
     272          if ((*_weight)[sn] <= value) value = (*_weight)[sn];
     273          sn = (*_pred)[sn];
     274        }
    275275      }
    276276      return value;
     
    295295    /// \pre \ref run() must be called before using this function.
    296296    template <typename CutMap>
    297     Value minCutMap(const Node& s, ///< 
     297    Value minCutMap(const Node& s, ///<
    298298                    const Node& t,
    299                     ///< 
     299                    ///<
    300300                    CutMap& cutMap
    301                     ///< 
     301                    ///<
    302302                    ) const {
    303303      Node sn = s, tn = t;
     
    305305      Node rn = INVALID;
    306306      Value value = std::numeric_limits<Value>::max();
    307      
     307
    308308      while (sn != tn) {
    309         if ((*_order)[sn] < (*_order)[tn]) {
    310           if ((*_weight)[tn] <= value) {
    311             rn = tn;
     309        if ((*_order)[sn] < (*_order)[tn]) {
     310          if ((*_weight)[tn] <= value) {
     311            rn = tn;
    312312            s_root = false;
    313             value = (*_weight)[tn];
    314           }
    315           tn = (*_pred)[tn];
    316         } else {
    317           if ((*_weight)[sn] <= value) {
    318             rn = sn;
     313            value = (*_weight)[tn];
     314          }
     315          tn = (*_pred)[tn];
     316        } else {
     317          if ((*_weight)[sn] <= value) {
     318            rn = sn;
    319319            s_root = true;
    320             value = (*_weight)[sn];
    321           }
    322           sn = (*_pred)[sn];
    323         }
     320            value = (*_weight)[sn];
     321          }
     322          sn = (*_pred)[sn];
     323        }
    324324      }
    325325
     
    332332      std::vector<Node> st;
    333333      for (NodeIt n(_graph); n != INVALID; ++n) {
    334         st.clear();
     334        st.clear();
    335335        Node nn = n;
    336         while (!reached[nn]) {
    337           st.push_back(nn);
    338           nn = (*_pred)[nn];
    339         }
    340         while (!st.empty()) {
    341           cutMap.set(st.back(), cutMap[nn]);
    342           st.pop_back();
    343         }
    344       }
    345      
     336        while (!reached[nn]) {
     337          st.push_back(nn);
     338          nn = (*_pred)[nn];
     339        }
     340        while (!st.empty()) {
     341          cutMap.set(st.back(), cutMap[nn]);
     342          st.pop_back();
     343        }
     344      }
     345
    346346      return value;
    347347    }
     
    352352
    353353    /// Iterate on the nodes of a minimum cut
    354    
     354
    355355    /// This iterator class lists the nodes of a minimum cut found by
    356356    /// GomoryHu. Before using it, you must allocate a GomoryHu class
     
    445445      }
    446446    };
    447    
     447
    448448    friend class MinCutEdgeIt;
    449    
     449
    450450    /// Iterate on the edges of a minimum cut
    451    
     451
    452452    /// This iterator class lists the edges of a minimum cut found by
    453453    /// GomoryHu. Before using it, you must allocate a GomoryHu class
     
    482482          }
    483483      }
    484      
     484
    485485    public:
    486486      /// Constructor
     
    551551      }
    552552      /// Postfix incrementation
    553      
     553
    554554      /// Postfix incrementation.
    555555      ///
  • lemon/graph_to_eps.h

    r908 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/hao_orlin.h

    r644 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3232/// \brief Implementation of the Hao-Orlin algorithm.
    3333///
    34 /// Implementation of the Hao-Orlin algorithm for finding a minimum cut 
     34/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
    3535/// in a digraph.
    3636
     
    4242  ///
    4343  /// This class implements the Hao-Orlin algorithm for finding a minimum
    44   /// value cut in a directed graph \f$D=(V,A)\f$. 
     44  /// value cut in a directed graph \f$D=(V,A)\f$.
    4545  /// It takes a fixed node \f$ source \in V \f$ and
    4646  /// consists of two phases: in the first phase it determines a
     
    5959  /// For an undirected graph you can run just the first phase of the
    6060  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
    61   /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ 
     61  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
    6262  /// time. It is implemented in the NagamochiIbaraki algorithm class.
    6363  ///
     
    7777  class HaoOrlin {
    7878  public:
    79    
     79
    8080    /// The digraph type of the algorithm
    8181    typedef GR Digraph;
     
    848848    ///
    849849    /// This function initializes the internal data structures. It creates
    850     /// the maps and some bucket structures for the algorithm. 
     850    /// the maps and some bucket structures for the algorithm.
    851851    /// The given node is used as the source node for the push-relabel
    852852    /// algorithm.
     
    928928    /// \brief Run the algorithm.
    929929    ///
    930     /// This function runs the algorithm. It uses the given \c source node, 
     930    /// This function runs the algorithm. It uses the given \c source node,
    931931    /// finds a proper \c target node and then calls the \ref init(),
    932932    /// \ref calculateOut() and \ref calculateIn().
     
    942942    /// The result of the %HaoOrlin algorithm
    943943    /// can be obtained using these functions.\n
    944     /// \ref run(), \ref calculateOut() or \ref calculateIn() 
     944    /// \ref run(), \ref calculateOut() or \ref calculateIn()
    945945    /// should be called before using them.
    946946
     
    951951    /// This function returns the value of the minimum cut.
    952952    ///
    953     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
     953    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    954954    /// must be called before using this function.
    955955    Value minCutValue() const {
     
    970970    /// \return The value of the minimum cut.
    971971    ///
    972     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
     972    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    973973    /// must be called before using this function.
    974974    template <typename CutMap>
  • lemon/lgf_reader.h

    r1069 r1081  
    563563    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
    564564    template <typename TDGR>
    565     friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 
     565    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
    566566                                             const std::string& fn);
    567567    template <typename TDGR>
     
    11951195
    11961196  };
    1197  
     1197
    11981198  /// \ingroup lemon_io
    11991199  ///
     
    12021202  /// This function just returns a \ref DigraphReader class.
    12031203  ///
    1204   /// With this function a digraph can be read from an 
     1204  /// With this function a digraph can be read from an
    12051205  /// \ref lgf-format "LGF" file or input stream with several maps and
    12061206  /// attributes. For example, there is network flow problem on a
     
    12571257  template <typename GR>
    12581258  class GraphReader;
    1259  
     1259
    12601260  template <typename TGR>
    12611261  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
     
    13941394    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
    13951395    template <typename TGR>
    1396     friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 
     1396    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
    13971397    template <typename TGR>
    13981398    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
     
    20782078  /// \brief Return a \ref GraphReader class
    20792079  ///
    2080   /// This function just returns a \ref GraphReader class. 
    2081   ///
    2082   /// With this function a graph can be read from an 
     2080  /// This function just returns a \ref GraphReader class.
     2081  ///
     2082  /// With this function a graph can be read from an
    20832083  /// \ref lgf-format "LGF" file or input stream with several maps and
    20842084  /// attributes. For example, there is weighted matching problem on a
  • lemon/lgf_writer.h

    r646 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    352352
    353353  template <typename TDGR>
    354   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
     354  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
    355355                                   std::ostream& os = std::cout);
    356356  template <typename TDGR>
     
    505505
    506506    template <typename TDGR>
    507     friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
     507    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
    508508                                             std::ostream& os);
    509509    template <typename TDGR>
     
    918918  /// \brief Return a \ref DigraphWriter class
    919919  ///
    920   /// This function just returns a \ref DigraphWriter class. 
     920  /// This function just returns a \ref DigraphWriter class.
    921921  ///
    922922  /// With this function a digraph can be write to a file or output
     
    958958  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
    959959  template <typename TDGR>
    960   DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 
     960  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
    961961                                    const std::string& fn) {
    962962    DigraphWriter<TDGR> tmp(digraph, fn);
     
    11021102    friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
    11031103    template <typename TGR>
    1104     friend GraphWriter<TGR> graphWriter(const TGR& graph, 
     1104    friend GraphWriter<TGR> graphWriter(const TGR& graph,
    11051105                                        const std::string& fn);
    11061106    template <typename TGR>
    11071107    friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn);
    1108    
     1108
    11091109    GraphWriter(GraphWriter& other)
    11101110      : _os(other._os), local_os(other.local_os), _graph(other._graph),
     
    15571557  /// \brief Return a \ref GraphWriter class
    15581558  ///
    1559   /// This function just returns a \ref GraphWriter class. 
     1559  /// This function just returns a \ref GraphWriter class.
    15601560  ///
    15611561  /// With this function a graph can be write to a file or output
  • lemon/lp.h

    r674 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8585#elif LEMON_HAVE_CLP
    8686# define DEFAULT_LP CLP
    87   typedef ClpLp Lp; 
     87  typedef ClpLp Lp;
    8888#endif
    8989#endif
  • lemon/lp_base.cc

    r557 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/lp_base.h

    r631 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383      MESSAGE_VERBOSE
    8484    };
    85    
     85
    8686
    8787    ///The floating point type used by the solver
     
    115115      typedef True LpCol;
    116116      /// Default constructor
    117      
     117
    118118      /// \warning The default constructor sets the Col to an
    119119      /// undefined value.
    120120      Col() {}
    121121      /// Invalid constructor \& conversion.
    122      
     122
    123123      /// This constructor initializes the Col to be invalid.
    124       /// \sa Invalid for more details.     
     124      /// \sa Invalid for more details.
    125125      Col(const Invalid&) : _id(-1) {}
    126126      /// Equality operator
     
    157157    public:
    158158      /// Default constructor
    159      
     159
    160160      /// \warning The default constructor sets the iterator
    161161      /// to an undefined value.
    162162      ColIt() {}
    163163      /// Sets the iterator to the first Col
    164      
     164
    165165      /// Sets the iterator to the first Col.
    166166      ///
     
    170170      }
    171171      /// Invalid constructor \& conversion
    172      
     172
    173173      /// Initialize the iterator to be invalid.
    174174      /// \sa Invalid for more details.
    175175      ColIt(const Invalid&) : Col(INVALID) {}
    176176      /// Next column
    177      
     177
    178178      /// Assign the iterator to the next column.
    179179      ///
     
    210210      typedef True LpRow;
    211211      /// Default constructor
    212      
     212
    213213      /// \warning The default constructor sets the Row to an
    214214      /// undefined value.
    215215      Row() {}
    216216      /// Invalid constructor \& conversion.
    217      
     217
    218218      /// This constructor initializes the Row to be invalid.
    219       /// \sa Invalid for more details.     
     219      /// \sa Invalid for more details.
    220220      Row(const Invalid&) : _id(-1) {}
    221221      /// Equality operator
     
    225225      bool operator==(Row r) const  {return _id == r._id;}
    226226      /// Inequality operator
    227      
     227
    228228      /// \sa operator==(Row r)
    229229      ///
     
    252252    public:
    253253      /// Default constructor
    254      
     254
    255255      /// \warning The default constructor sets the iterator
    256256      /// to an undefined value.
    257257      RowIt() {}
    258258      /// Sets the iterator to the first Row
    259      
     259
    260260      /// Sets the iterator to the first Row.
    261261      ///
     
    265265      }
    266266      /// Invalid constructor \& conversion
    267      
     267
    268268      /// Initialize the iterator to be invalid.
    269269      /// \sa Invalid for more details.
    270270      RowIt(const Invalid&) : Row(INVALID) {}
    271271      /// Next row
    272      
     272
    273273      /// Assign the iterator to the next row.
    274274      ///
     
    348348      typedef True SolverExpr;
    349349      /// Default constructor
    350      
     350
    351351      /// Construct an empty expression, the coefficients and
    352352      /// the constant component are initialized to zero.
     
    449449
    450450      ///Iterator over the expression
    451      
    452       ///The iterator iterates over the terms of the expression. 
    453       /// 
     451
     452      ///The iterator iterates over the terms of the expression.
     453      ///
    454454      ///\code
    455455      ///double s=0;
     
    465465
    466466        /// Sets the iterator to the first term
    467        
     467
    468468        /// Sets the iterator to the first term of the expression.
    469469        ///
     
    482482        const Value& operator*() const { return _it->second; }
    483483        /// Next term
    484        
     484
    485485        /// Assign the iterator to the next term.
    486486        ///
     
    494494
    495495      /// Const iterator over the expression
    496      
    497       ///The iterator iterates over the terms of the expression. 
    498       /// 
     496
     497      ///The iterator iterates over the terms of the expression.
     498      ///
    499499      ///\code
    500500      ///double s=0;
     
    510510
    511511        /// Sets the iterator to the first term
    512        
     512
    513513        /// Sets the iterator to the first term of the expression.
    514514        ///
     
    525525
    526526        /// Next term
    527        
     527
    528528        /// Assign the iterator to the next term.
    529529        ///
     
    674674      typedef True SolverExpr;
    675675      /// Default constructor
    676      
     676
    677677      /// Construct an empty expression, the coefficients are
    678678      /// initialized to zero.
     
    709709      }
    710710      /// \brief Removes the coefficients which's absolute value does
    711       /// not exceed \c epsilon. 
     711      /// not exceed \c epsilon.
    712712      void simplify(Value epsilon = 0.0) {
    713713        std::map<int, Value>::iterator it=comps.begin();
     
    758758
    759759      ///Iterator over the expression
    760      
    761       ///The iterator iterates over the terms of the expression. 
    762       /// 
     760
     761      ///The iterator iterates over the terms of the expression.
     762      ///
    763763      ///\code
    764764      ///double s=0;
     
    774774
    775775        /// Sets the iterator to the first term
    776        
     776
    777777        /// Sets the iterator to the first term of the expression.
    778778        ///
     
    792792
    793793        /// Next term
    794        
     794
    795795        /// Assign the iterator to the next term.
    796796        ///
     
    804804
    805805      ///Iterator over the expression
    806      
    807       ///The iterator iterates over the terms of the expression. 
    808       /// 
     806
     807      ///The iterator iterates over the terms of the expression.
     808      ///
    809809      ///\code
    810810      ///double s=0;
     
    820820
    821821        /// Sets the iterator to the first term
    822        
     822
    823823        /// Sets the iterator to the first term of the expression.
    824824        ///
     
    835835
    836836        /// Next term
    837        
     837
    838838        /// Assign the iterator to the next term.
    839839        ///
     
    18041804    enum VarStatus {
    18051805      /// The variable is in the basis
    1806       BASIC, 
     1806      BASIC,
    18071807      /// The variable is free, but not basic
    18081808      FREE,
    1809       /// The variable has active lower bound 
     1809      /// The variable has active lower bound
    18101810      LOWER,
    18111811      /// The variable has active upper bound
     
    18861886    }
    18871887    /// Returns a component of the primal ray
    1888    
     1888
    18891889    /// The primal ray is solution of the modified primal problem,
    18901890    /// where we change each finite bound to 0, and we looking for a
     
    19201920
    19211921    /// Returns a component of the dual ray
    1922    
     1922
    19231923    /// The dual ray is solution of the modified primal problem, where
    19241924    /// we change each finite bound to 0 (i.e. the objective function
     
    20622062    }
    20632063    ///The value of the objective function
    2064    
     2064
    20652065    ///\return
    20662066    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  • lemon/lp_skeleton.cc

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/lp_skeleton.h

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424///\file
    2525///\brief Skeleton file to implement LP/MIP solver interfaces
    26 /// 
     26///
    2727///The classes in this file do nothing, but they can serve as skeletons when
    2828///implementing an interface to new solvers.
     
    3030
    3131  ///A skeleton class to implement LP/MIP solver base interface
    32  
     32
    3333  ///This class does nothing, but it can serve as a skeleton when
    3434  ///implementing an interface to new solvers.
  • lemon/maps.h

    r731 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    18191819  ///
    18201820  /// IdMap provides a unique and immutable id for each item of the
    1821   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
     1821  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
    18221822  ///  - \b unique: different items get different ids,
    18231823  ///  - \b immutable: the id of an item does not change (even if you
     
    22742274
    22752275    /// \brief Gives back the item belonging to a \e RangeId
    2276     /// 
     2276    ///
    22772277    /// Gives back the item belonging to a \e RangeId.
    22782278    Item operator()(int id) const {
     
    25002500  /// whenever the digraph changes.
    25012501  ///
    2502   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     2502  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    25032503  /// may provide alternative ways to modify the digraph.
    25042504  /// The correct behavior of InDegMap is not guarantied if these additional
     
    25162516
    25172517  public:
    2518    
     2518
    25192519    /// The graph type of InDegMap
    25202520    typedef GR Graph;
     
    26302630  /// whenever the digraph changes.
    26312631  ///
    2632   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     2632  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    26332633  /// may provide alternative ways to modify the digraph.
    26342634  /// The correct behavior of OutDegMap is not guarantied if these additional
  • lemon/matching.h

    r945 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4242  /// This class implements Edmonds' alternating forest matching algorithm
    4343  /// for finding a maximum cardinality matching in a general undirected graph.
    44   /// It can be started from an arbitrary initial matching 
     44  /// It can be started from an arbitrary initial matching
    4545  /// (the default is the empty one).
    4646  ///
     
    7070    ///\brief Status constants for Gallai-Edmonds decomposition.
    7171    ///
    72     ///These constants are used for indicating the Gallai-Edmonds 
     72    ///These constants are used for indicating the Gallai-Edmonds
    7373    ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
    7474    ///induce a subgraph with factor-critical components, the nodes with
    7575    ///status \c ODD (or \c A) form the canonical barrier, and the nodes
    76     ///with status \c MATCHED (or \c C) induce a subgraph having a 
     76    ///with status \c MATCHED (or \c C) induce a subgraph having a
    7777    ///perfect matching.
    7878    enum Status {
     
    513513    }
    514514
    515     /// \brief Start Edmonds' algorithm with a heuristic improvement 
     515    /// \brief Start Edmonds' algorithm with a heuristic improvement
    516516    /// for dense graphs
    517517    ///
     
    535535    /// \brief Run Edmonds' algorithm
    536536    ///
    537     /// This function runs Edmonds' algorithm. An additional heuristic of 
    538     /// postponing shrinks is used for relatively dense graphs 
     537    /// This function runs Edmonds' algorithm. An additional heuristic of
     538    /// postponing shrinks is used for relatively dense graphs
    539539    /// (for which <tt>m>=2*n</tt> holds).
    540540    void run() {
     
    557557    /// \brief Return the size (cardinality) of the matching.
    558558    ///
    559     /// This function returns the size (cardinality) of the current matching. 
     559    /// This function returns the size (cardinality) of the current matching.
    560560    /// After run() it returns the size of the maximum matching in the graph.
    561561    int matchingSize() const {
     
    571571    /// \brief Return \c true if the given edge is in the matching.
    572572    ///
    573     /// This function returns \c true if the given edge is in the current 
     573    /// This function returns \c true if the given edge is in the current
    574574    /// matching.
    575575    bool matching(const Edge& edge) const {
     
    580580    ///
    581581    /// This function returns the matching arc (or edge) incident to the
    582     /// given node in the current matching or \c INVALID if the node is 
     582    /// given node in the current matching or \c INVALID if the node is
    583583    /// not covered by the matching.
    584584    Arc matching(const Node& n) const {
     
    596596    /// \brief Return the mate of the given node.
    597597    ///
    598     /// This function returns the mate of the given node in the current 
     598    /// This function returns the mate of the given node in the current
    599599    /// matching or \c INVALID if the node is not covered by the matching.
    600600    Node mate(const Node& n) const {
     
    606606
    607607    /// \name Dual Solution
    608     /// Functions to get the dual solution, i.e. the Gallai-Edmonds 
     608    /// Functions to get the dual solution, i.e. the Gallai-Edmonds
    609609    /// decomposition.
    610610
     
    649649  /// \f$O(nm\log n)\f$ time complexity.
    650650  ///
    651   /// The maximum weighted matching problem is to find a subset of the 
    652   /// edges in an undirected graph with maximum overall weight for which 
     651  /// The maximum weighted matching problem is to find a subset of the
     652  /// edges in an undirected graph with maximum overall weight for which
    653653  /// each node has at most one incident edge.
    654654  /// It can be formulated with the following linear program.
     
    674674      \frac{\vert B \vert - 1}{2}z_B\f] */
    675675  ///
    676   /// The algorithm can be executed with the run() function. 
     676  /// The algorithm can be executed with the run() function.
    677677  /// After it the matching (the primal solution) and the dual solution
    678   /// can be obtained using the query functions and the 
    679   /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, 
    680   /// which is able to iterate on the nodes of a blossom. 
     678  /// can be obtained using the query functions and the
     679  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
     680  /// which is able to iterate on the nodes of a blossom.
    681681  /// If the value type is integer, then the dual solution is multiplied
    682682  /// by \ref MaxWeightedMatching::dualScale "4".
    683683  ///
    684684  /// \tparam GR The undirected graph type the algorithm runs on.
    685   /// \tparam WM The type edge weight map. The default type is 
     685  /// \tparam WM The type edge weight map. The default type is
    686686  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    687687#ifdef DOXYGEN
     
    17211721        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    17221722      }
    1723      
     1723
    17241724      _delta1->clear();
    17251725      _delta2->clear();
     
    18691869
    18701870    /// \name Primal Solution
    1871     /// Functions to get the primal solution, i.e. the maximum weighted 
     1871    /// Functions to get the primal solution, i.e. the maximum weighted
    18721872    /// matching.\n
    18731873    /// Either \ref run() or \ref start() function should be called before
     
    19081908    /// \brief Return \c true if the given edge is in the matching.
    19091909    ///
    1910     /// This function returns \c true if the given edge is in the found 
     1910    /// This function returns \c true if the given edge is in the found
    19111911    /// matching.
    19121912    ///
     
    19191919    ///
    19201920    /// This function returns the matching arc (or edge) incident to the
    1921     /// given node in the found matching or \c INVALID if the node is 
     1921    /// given node in the found matching or \c INVALID if the node is
    19221922    /// not covered by the matching.
    19231923    ///
     
    19371937    /// \brief Return the mate of the given node.
    19381938    ///
    1939     /// This function returns the mate of the given node in the found 
     1939    /// This function returns the mate of the given node in the found
    19401940    /// matching or \c INVALID if the node is not covered by the matching.
    19411941    ///
     
    19571957    /// \brief Return the value of the dual solution.
    19581958    ///
    1959     /// This function returns the value of the dual solution. 
    1960     /// It should be equal to the primal value scaled by \ref dualScale 
     1959    /// This function returns the value of the dual solution.
     1960    /// It should be equal to the primal value scaled by \ref dualScale
    19611961    /// "dual scale".
    19621962    ///
     
    20132013    /// \brief Iterator for obtaining the nodes of a blossom.
    20142014    ///
    2015     /// This class provides an iterator for obtaining the nodes of the 
     2015    /// This class provides an iterator for obtaining the nodes of the
    20162016    /// given blossom. It lists a subset of the nodes.
    2017     /// Before using this iterator, you must allocate a 
     2017    /// Before using this iterator, you must allocate a
    20182018    /// MaxWeightedMatching class and execute it.
    20192019    class BlossomIt {
     
    20242024      /// Constructor to get the nodes of the given variable.
    20252025      ///
    2026       /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or 
    2027       /// \ref MaxWeightedMatching::start() "algorithm.start()" must be 
     2026      /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
     2027      /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
    20282028      /// called before initializing this iterator.
    20292029      BlossomIt(const MaxWeightedMatching& algorithm, int variable)
     
    20782078  /// \f$O(nm\log n)\f$ time complexity.
    20792079  ///
    2080   /// The maximum weighted perfect matching problem is to find a subset of 
    2081   /// the edges in an undirected graph with maximum overall weight for which 
     2080  /// The maximum weighted perfect matching problem is to find a subset of
     2081  /// the edges in an undirected graph with maximum overall weight for which
    20822082  /// each node has exactly one incident edge.
    20832083  /// It can be formulated with the following linear program.
     
    21022102      \frac{\vert B \vert - 1}{2}z_B\f] */
    21032103  ///
    2104   /// The algorithm can be executed with the run() function. 
     2104  /// The algorithm can be executed with the run() function.
    21052105  /// After it the matching (the primal solution) and the dual solution
    2106   /// can be obtained using the query functions and the 
    2107   /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, 
    2108   /// which is able to iterate on the nodes of a blossom. 
     2106  /// can be obtained using the query functions and the
     2107  /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
     2108  /// which is able to iterate on the nodes of a blossom.
    21092109  /// If the value type is integer, then the dual solution is multiplied
    21102110  /// by \ref MaxWeightedMatching::dualScale "4".
    21112111  ///
    21122112  /// \tparam GR The undirected graph type the algorithm runs on.
    2113   /// \tparam WM The type edge weight map. The default type is 
     2113  /// \tparam WM The type edge weight map. The default type is
    21142114  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    21152115#ifdef DOXYGEN
     
    31163116
    31173117    /// \name Primal Solution
    3118     /// Functions to get the primal solution, i.e. the maximum weighted 
     3118    /// Functions to get the primal solution, i.e. the maximum weighted
    31193119    /// perfect matching.\n
    31203120    /// Either \ref run() or \ref start() function should be called before
     
    31403140    /// \brief Return \c true if the given edge is in the matching.
    31413141    ///
    3142     /// This function returns \c true if the given edge is in the found 
     3142    /// This function returns \c true if the given edge is in the found
    31433143    /// matching.
    31443144    ///
     
    31513151    ///
    31523152    /// This function returns the matching arc (or edge) incident to the
    3153     /// given node in the found matching or \c INVALID if the node is 
     3153    /// given node in the found matching or \c INVALID if the node is
    31543154    /// not covered by the matching.
    31553155    ///
     
    31693169    /// \brief Return the mate of the given node.
    31703170    ///
    3171     /// This function returns the mate of the given node in the found 
     3171    /// This function returns the mate of the given node in the found
    31723172    /// matching or \c INVALID if the node is not covered by the matching.
    31733173    ///
     
    31883188    /// \brief Return the value of the dual solution.
    31893189    ///
    3190     /// This function returns the value of the dual solution. 
    3191     /// It should be equal to the primal value scaled by \ref dualScale 
     3190    /// This function returns the value of the dual solution.
     3191    /// It should be equal to the primal value scaled by \ref dualScale
    31923192    /// "dual scale".
    31933193    ///
     
    32443244    /// \brief Iterator for obtaining the nodes of a blossom.
    32453245    ///
    3246     /// This class provides an iterator for obtaining the nodes of the 
     3246    /// This class provides an iterator for obtaining the nodes of the
    32473247    /// given blossom. It lists a subset of the nodes.
    3248     /// Before using this iterator, you must allocate a 
     3248    /// Before using this iterator, you must allocate a
    32493249    /// MaxWeightedPerfectMatching class and execute it.
    32503250    class BlossomIt {
     
    32553255      /// Constructor to get the nodes of the given variable.
    32563256      ///
    3257       /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" 
    3258       /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" 
     3257      /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
     3258      /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
    32593259      /// must be called before initializing this iterator.
    32603260      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
  • lemon/math.h

    r558 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5757
    5858  ///Check whether the parameter is NaN or not
    59  
     59
    6060  ///This function checks whether the parameter is NaN or not.
    6161  ///Is should be equivalent with std::isnan(), but it is not
  • lemon/min_cost_arborescence.h

    r672 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    128128  public:
    129129
    130     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 
    131     /// of the algorithm. 
     130    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
     131    /// of the algorithm.
    132132    typedef TR Traits;
    133133    /// The type of the underlying digraph.
     
    436436    /// \ref named-templ-param "Named parameter" for setting
    437437    /// \c PredMap type.
    438     /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 
     438    /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
    439439    /// and its value type must be the \c Arc type of the digraph.
    440440    template <class T>
  • lemon/network_simplex.h

    r976 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9696      UNBOUNDED
    9797    };
    98    
     98
    9999    /// \brief Constants for selecting the type of the supply constraints.
    100100    ///
     
    114114      LEQ
    115115    };
    116    
     116
    117117    /// \brief Constants for selecting the pivot rule.
    118118    ///
     
    157157      ALTERING_LIST
    158158    };
    159    
     159
    160160  private:
    161161
     
    224224
    225225  public:
    226  
     226
    227227    /// \brief Constant for infinite upper bounds (capacities).
    228228    ///
     
    645645      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    646646        "The cost type of NetworkSimplex must be signed");
    647        
     647
    648648      // Resize vectors
    649649      _node_num = countNodes(_graph);
     
    685685        if ((i += k) >= _arc_num) i = (i % k) + 1;
    686686      }
    687      
     687
    688688      // Initialize maps
    689689      for (int i = 0; i != _node_num; ++i) {
     
    810810      return *this;
    811811    }
    812    
     812
    813813    /// \brief Set the type of the supply constraints.
    814814    ///
     
    836836    /// This function runs the algorithm.
    837837    /// The paramters can be specified using functions \ref lowerMap(),
    838     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 
     838    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
    839839    /// \ref supplyType().
    840840    /// For example,
     
    10551055        _state[i] = STATE_LOWER;
    10561056      }
    1057      
     1057
    10581058      // Set data for the artificial root node
    10591059      _root = _node_num;
     
    12291229      for (int u = second; u != join; u = _parent[u]) {
    12301230        e = _pred[u];
    1231         d = _forward[u] ? 
     1231        d = _forward[u] ?
    12321232          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
    12331233        if (d <= delta) {
     
    14361436        }
    14371437      }
    1438      
     1438
    14391439      // Check feasibility
    14401440      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
     
    14531453        }
    14541454      }
    1455      
     1455
    14561456      // Shift potentials to meet the requirements of the GEQ/LEQ type
    14571457      // optimality conditions
  • lemon/path.h

    r868 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    967967    };
    968968
    969    
     969
    970970    template <typename From, typename To,
    971971              bool revEnable = RevPathTagIndicator<From>::value>
     
    973973      static void copy(const From& from, To& to) {
    974974        PathCopySelectorForward<From, To>::copy(from, to);
    975       }     
     975      }
    976976    };
    977977
     
    980980      static void copy(const From& from, To& to) {
    981981        PathCopySelectorBackward<From, To>::copy(from, to);
    982       }     
     982      }
    983983    };
    984984
  • lemon/preflow.h

    r1027 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    537537        }
    538538      }
    539       for (NodeIt n(_graph); n != INVALID; ++n) 
     539      for (NodeIt n(_graph); n != INVALID; ++n)
    540540        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
    541541          _level->activate(n);
    542          
     542
    543543      return true;
    544544    }
     
    568568          level = _level->highestActiveLevel();
    569569          --num;
    570          
     570
    571571          Value excess = (*_excess)[n];
    572572          int new_level = _level->maxLevel();
  • lemon/soplex.cc

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    275275
    276276    _clear_temporals();
    277    
     277
    278278    _applyMessageLevel();
    279279
  • lemon/soplex.h

    r623 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/suurballe.h

    r928 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/unionfind.h

    r946 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/bfs_test.cc

    r632 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8484    b = const_bfs_test.emptyQueue();
    8585    i = const_bfs_test.queueSize();
    86    
     86
    8787    bfs_test.start();
    8888    bfs_test.start(t);
     
    105105      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    106106      ::Create bfs_test(G);
    107      
     107
    108108    concepts::ReadWriteMap<Node,Arc> pred_map;
    109109    concepts::ReadWriteMap<Node,int> dist_map;
    110110    concepts::ReadWriteMap<Node,bool> reached_map;
    111111    concepts::WriteMap<Node,bool> processed_map;
    112    
     112
    113113    bfs_test
    114114      .predMap(pred_map)
     
    120120    bfs_test.run(s,t);
    121121    bfs_test.run();
    122    
     122
    123123    bfs_test.init();
    124124    bfs_test.addSource(s);
     
    129129    b = bfs_test.emptyQueue();
    130130    i = bfs_test.queueSize();
    131    
     131
    132132    bfs_test.start();
    133133    bfs_test.start(t);
  • test/circulation_test.cc

    r658 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8282  CirculationType circ_test(g, lcap, ucap, supply);
    8383  const CirculationType& const_circ_test = circ_test;
    84    
     84
    8585  circ_test
    8686    .lowerMap(lcap)
     
    9898  b = const_circ_test.barrier(n);
    9999  const_circ_test.barrierMap(bar);
    100  
     100
    101101  ignore_unused_variable_warning(fm);
    102102}
  • test/connectivity_test.cc

    r696 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  typedef ListDigraph Digraph;
    3131  typedef Undirector<Digraph> Graph;
    32  
    33   {
    34     Digraph d;
    35     Digraph::NodeMap<int> order(d);
    36     Graph g(d);
    37    
     32
     33  {
     34    Digraph d;
     35    Digraph::NodeMap<int> order(d);
     36    Graph g(d);
     37
    3838    check(stronglyConnected(d), "The empty digraph is strongly connected");
    3939    check(countStronglyConnectedComponents(d) == 0,
     
    4949    check(countBiEdgeConnectedComponents(g) == 0,
    5050          "The empty graph has 0 bi-edge-connected component");
    51          
     51
    5252    check(dag(d), "The empty digraph is DAG.");
    5353    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
     
    8383    check(countBiEdgeConnectedComponents(g) == 1,
    8484          "This graph has 1 bi-edge-connected component");
    85          
     85
    8686    check(dag(d), "This digraph is DAG.");
    8787    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
     
    102102    Digraph::NodeMap<int> order(d);
    103103    Graph g(d);
    104    
     104
    105105    Digraph::Node n1 = d.addNode();
    106106    Digraph::Node n2 = d.addNode();
     
    109109    Digraph::Node n5 = d.addNode();
    110110    Digraph::Node n6 = d.addNode();
    111    
     111
    112112    d.addArc(n1, n3);
    113113    d.addArc(n3, n2);
     
    137137    check(!parallelFree(g), "This graph is not parallel-free.");
    138138    check(!simpleGraph(g), "This graph is not simple.");
    139    
     139
    140140    d.addArc(n3, n3);
    141    
     141
    142142    check(!loopFree(d), "This digraph is not loop-free.");
    143143    check(!loopFree(g), "This graph is not loop-free.");
    144144    check(!simpleGraph(d), "This digraph is not simple.");
    145    
     145
    146146    d.addArc(n3, n2);
    147    
     147
    148148    check(!parallelFree(d), "This digraph is not parallel-free.");
    149149  }
    150  
     150
    151151  {
    152152    Digraph d;
    153153    Digraph::ArcMap<bool> cutarcs(d, false);
    154154    Graph g(d);
    155    
     155
    156156    Digraph::Node n1 = d.addNode();
    157157    Digraph::Node n2 = d.addNode();
     
    173173    d.addArc(n6, n7);
    174174    d.addArc(n7, n6);
    175    
     175
    176176    check(!stronglyConnected(d), "This digraph is not strongly connected");
    177177    check(countStronglyConnectedComponents(d) == 3,
     
    236236    Digraph d;
    237237    Digraph::NodeMap<int> order(d);
    238    
     238
    239239    Digraph::Node belt = d.addNode();
    240240    Digraph::Node trousers = d.addNode();
     
    256256    d.addArc(shirt, necktie);
    257257    d.addArc(necktie, coat);
    258    
     258
    259259    check(dag(d), "This digraph is DAG.");
    260260    topologicalSort(d, order);
     
    268268    ListGraph g;
    269269    ListGraph::NodeMap<bool> map(g);
    270    
     270
    271271    ListGraph::Node n1 = g.addNode();
    272272    ListGraph::Node n2 = g.addNode();
     
    284284    g.addEdge(n4, n7);
    285285    g.addEdge(n5, n7);
    286    
     286
    287287    check(bipartite(g), "This graph is bipartite");
    288288    check(bipartitePartitions(g, map), "This graph is bipartite");
    289    
     289
    290290    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
    291291          "Wrong bipartitePartitions()");
  • test/dfs_test.cc

    r1009 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8787    b = const_dfs_test.emptyQueue();
    8888    i = const_dfs_test.queueSize();
    89    
     89
    9090    dfs_test.start();
    9191    dfs_test.start(t);
     
    113113    concepts::ReadWriteMap<Node,bool> reached_map;
    114114    concepts::WriteMap<Node,bool> processed_map;
    115    
     115
    116116    dfs_test
    117117      .predMap(pred_map)
     
    130130    b = dfs_test.emptyQueue();
    131131    i = dfs_test.queueSize();
    132    
     132
    133133    dfs_test.start();
    134134    dfs_test.start(t);
     
    220220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
    221221  }
    222  
     222
    223223  {
    224224    NullMap<Node,Arc> myPredMap;
  • test/dijkstra_test.cc

    r632 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686    b = const_dijkstra_test.emptyQueue();
    8787    i = const_dijkstra_test.queueSize();
    88    
     88
    8989    dijkstra_test.start();
    9090    dijkstra_test.start(t);
     
    110110      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    111111      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    112       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 
     112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
    113113                concepts::ReadWriteMap<Node,int> >
    114114      ::Create dijkstra_test(G,length);
     
    120120    concepts::ReadWriteMap<Node,int> heap_cross_ref;
    121121    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
    122    
     122
    123123    dijkstra_test
    124124      .lengthMap(length_map)
     
    137137    b = dijkstra_test.emptyQueue();
    138138    i = dijkstra_test.queueSize();
    139    
     139
    140140    dijkstra_test.start();
    141141    dijkstra_test.start(t);
  • test/edge_set_test.cc

    r559 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/euler_test.cc

    r639 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686  typedef ListDigraph Digraph;
    8787  typedef Undirector<Digraph> Graph;
    88  
    89   {
    90     Digraph d;
    91     Graph g(d);
    92    
     88
     89  {
     90    Digraph d;
     91    Graph g(d);
     92
    9393    checkDiEulerIt(d);
    9494    checkDiEulerIt(g);
     
    129129    Digraph::Node n2 = d.addNode();
    130130    Digraph::Node n3 = d.addNode();
    131    
     131
    132132    d.addArc(n1, n2);
    133133    d.addArc(n2, n1);
     
    154154    Digraph::Node n5 = d.addNode();
    155155    Digraph::Node n6 = d.addNode();
    156    
     156
    157157    d.addArc(n1, n2);
    158158    d.addArc(n2, n4);
     
    190190    Digraph::Node n4 = d.addNode();
    191191    Digraph::Node n5 = d.addNode();
    192    
     192
    193193    d.addArc(n1, n2);
    194194    d.addArc(n2, n3);
     
    212212    Digraph::Node n2 = d.addNode();
    213213    Digraph::Node n3 = d.addNode();
    214    
     214
    215215    d.addArc(n1, n2);
    216216    d.addArc(n2, n3);
  • test/gomory_hu_test.cc

    r643 r1081  
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
     4 *
     5 * Copyright (C) 2003-2011
     6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8 *
     9 * Permission to use, modify and distribute this software is granted
     10 * provided that this copyright notice appears in all copies. For
     11 * precise terms see the accompanying LICENSE file.
     12 *
     13 * This software is provided "AS IS" with no warranty of any kind,
     14 * express or implied, and with no claim as to its suitability for any
     15 * purpose.
     16 *
     17 */
     18
    119#include <iostream>
    220
     
    3452  "source 0\n"
    3553  "target 3\n";
    36  
     54
    3755void checkGomoryHuCompile()
    3856{
     
    7088
    7189int cutValue(const Graph& graph, const BoolNodeMap& cut,
    72              const IntEdgeMap& capacity) {
     90             const IntEdgeMap& capacity) {
    7391
    7492  int sum = 0;
     
    108126      int sum=0;
    109127      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    110         sum+=capacity[a]; 
     128        sum+=capacity[a];
    111129      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    112130
     
    119137    }
    120138  }
    121  
     139
    122140  return 0;
    123141}
  • test/graph_copy_test.cc

    r984 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7171    nodeCrossRef(ncr).arcCrossRef(ecr).
    7272    node(fn, tn).arc(fa, ta).run();
    73  
     73
    7474  check(countNodes(from) == countNodes(to), "Wrong copy.");
    7575  check(countArcs(from) == countArcs(to), "Wrong copy.");
     
    9999  // Test repeated copy
    100100  digraphCopy(from, to).run();
    101  
     101
    102102  check(countNodes(from) == countNodes(to), "Wrong copy.");
    103103  check(countArcs(from) == countArcs(to), "Wrong copy.");
     
    201201  // Test repeated copy
    202202  graphCopy(from, to).run();
    203  
     203
    204204  check(countNodes(from) == countNodes(to), "Wrong copy.");
    205205  check(countEdges(from) == countEdges(to), "Wrong copy.");
  • test/hao_orlin_test.cc

    r644 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8484
    8585template <typename Graph, typename CapMap, typename CutMap>
    86 typename CapMap::Value 
     86typename CapMap::Value
    8787  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    8888{
     
    111111    ho.run();
    112112    ho.minCutMap(cut);
    113    
     113
    114114    check(ho.minCutValue() == 1, "Wrong cut value");
    115115    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
     
    127127    ho.run();
    128128    ho.minCutMap(cut);
    129    
     129
    130130    check(ho.minCutValue() == 1, "Wrong cut value");
    131131    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
    132132  }
    133  
     133
    134134  typedef Undirector<SmartDigraph> UGraph;
    135135  UGraph ugraph(graph);
    136  
     136
    137137  {
    138138    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
    139139    ho.run();
    140140    ho.minCutMap(cut);
    141    
     141
    142142    check(ho.minCutValue() == 2, "Wrong cut value");
    143143    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
     
    147147    ho.run();
    148148    ho.minCutMap(cut);
    149    
     149
    150150    check(ho.minCutValue() == 5, "Wrong cut value");
    151151    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
     
    155155    ho.run();
    156156    ho.minCutMap(cut);
    157    
     157
    158158    check(ho.minCutValue() == 5, "Wrong cut value");
    159159    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
  • test/heap_test.cc

    r1064 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/lgf_test.cc

    r1067 r1078  
    6464
    6565
    66 int main() 
     66int main()
    6767{
    6868  {
    69     ListDigraph d; 
     69    ListDigraph d;
    7070    ListDigraph::Node s,t;
    7171    ListDigraph::ArcMap<int> label(d);
     
    9494
    9595  {
    96     ListDigraph d; 
     96    ListDigraph d;
    9797    std::istringstream input(test_lgf_nomap);
    9898    digraphReader(d, input).
     
    111111
    112112  {
    113     ListDigraph d; 
     113    ListDigraph d;
    114114    std::istringstream input(test_lgf_bad1);
    115115    bool ok=false;
     
    118118        run();
    119119    }
    120     catch (FormatError& error) 
     120    catch (FormatError& error)
    121121      {
    122122        ok = true;
     
    140140
    141141  {
    142     ListDigraph d; 
     142    ListDigraph d;
    143143    std::istringstream input(test_lgf_bad2);
    144144    bool ok=false;
  • test/maps_test.cc

    r731 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7171  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
    7272  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
    73   checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
    74   checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
     73  checkConcept<ReferenceMap<A,B,B&,const B&>,
     74               ReferenceMap<A,B,B&,const B&> >();
     75  checkConcept<ReferenceMap<A,C,C&,const C&>,
     76               ReferenceMap<A,C,C&,const C&> >();
    7577
    7678  // NullMap
     
    201203
    202204    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    203     MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
     205    MapToFunctor<ReadMap<A,B> > map =
     206      MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
    204207
    205208    check(functorToMap(&func)[A()] == 3,
     
    350353      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    351354  }
    352  
     355
    353356  // CrossRefMap
    354357  {
     
    358361    checkConcept<ReadWriteMap<Node, int>,
    359362                 CrossRefMap<Graph, Node, int> >();
    360    
     363
    361364    Graph gr;
    362365    typedef CrossRefMap<Graph, Node, char> CRMap;
    363366    typedef CRMap::ValueIterator ValueIt;
    364367    CRMap map(gr);
    365    
     368
    366369    Node n0 = gr.addNode();
    367370    Node n1 = gr.addNode();
    368371    Node n2 = gr.addNode();
    369    
     372
    370373    map.set(n0, 'A');
    371374    map.set(n1, 'B');
  • test/matching_test.cc

    r641 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    135135  mat_test.startDense();
    136136  mat_test.run();
    137  
     137
    138138  const_mat_test.matchingSize();
    139139  const_mat_test.matching(e);
     
    144144  const_mat_test.mate(n);
    145145
    146   MaxMatching<Graph>::Status stat = 
     146  MaxMatching<Graph>::Status stat =
    147147    const_mat_test.status(n);
    148148  const MaxMatching<Graph>::StatusMap& smap =
     
    171171  mat_test.start();
    172172  mat_test.run();
    173  
     173
    174174  const_mat_test.matchingWeight();
    175175  const_mat_test.matchingSize();
     
    180180  e = mmap[n];
    181181  const_mat_test.mate(n);
    182  
     182
    183183  int k = 0;
    184184  const_mat_test.dualValue();
     
    208208  mat_test.start();
    209209  mat_test.run();
    210  
     210
    211211  const_mat_test.matchingWeight();
    212212  const_mat_test.matching(e);
     
    216216  e = mmap[n];
    217217  const_mat_test.mate(n);
    218  
     218
    219219  int k = 0;
    220220  const_mat_test.dualValue();
  • test/min_cost_arborescence_test.cc

    r672 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    111111  b = const_mcarb_test.emptyQueue();
    112112  i = const_mcarb_test.queueSize();
    113  
     113
    114114  c = const_mcarb_test.arborescenceCost();
    115115  b = const_mcarb_test.arborescence(e);
     
    121121  b = const_mcarb_test.reached(n);
    122122  b = const_mcarb_test.processed(n);
    123  
     123
    124124  i = const_mcarb_test.dualNum();
    125125  c = const_mcarb_test.dualValue();
    126126  i = const_mcarb_test.dualSize(i);
    127127  c = const_mcarb_test.dualValue(i);
    128  
     128
    129129  ignore_unused_variable_warning(am);
    130130  ignore_unused_variable_warning(pm);
  • test/min_cost_flow_test.cc

    r716 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4848  "   11     0    0    0    0  -10    0\n"
    4949  "   12   -20  -27    0  -30  -30  -20\n"
    50   "\n"               
     50  "\n"
    5151  "@arcs\n"
    5252  "       cost  cap low1 low2 low3\n"
     
    9494    void constraints() {
    9595      checkConcept<concepts::Digraph, GR>();
    96      
     96
    9797      const Constraints& me = *this;
    9898
     
    123123    typedef concepts::WriteMap<Arc, Value> FlowMap;
    124124    typedef concepts::WriteMap<Node, Cost> PotMap;
    125  
     125
    126126    GR g;
    127127    VAM lower;
     
    177177           typename CM, typename SM, typename FM, typename PM >
    178178bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
    179                      const CM& cost, const SM& supply, const FM& flow, 
     179                     const CM& cost, const SM& supply, const FM& flow,
    180180                     const PM& pi, SupplyType type )
    181181{
     
    190190          (red_cost < 0 && flow[e] == upper[e]);
    191191  }
    192  
     192
    193193  for (NodeIt n(gr); opt && n != INVALID; ++n) {
    194194    typename SM::Value sum = 0;
     
    203203    }
    204204  }
    205  
     205
    206206  return opt;
    207207}
     
    228228    }
    229229  }
    230  
     230
    231231  for (NodeIt n(gr); n != INVALID; ++n) {
    232232    dual_cost -= red_supply[n] * pi[n];
     
    237237    dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
    238238  }
    239  
     239
    240240  return dual_cost == total;
    241241}
     
    309309    .node("target", w)
    310310    .run();
    311  
     311
    312312  // Build test digraphs with negative costs
    313313  Digraph neg_gr;
     
    319319  Node n6 = neg_gr.addNode();
    320320  Node n7 = neg_gr.addNode();
    321  
     321
    322322  Arc a1 = neg_gr.addArc(n1, n2);
    323323  Arc a2 = neg_gr.addArc(n1, n3);
     
    329329  Arc a8 = neg_gr.addArc(n6, n7);
    330330  Arc a9 = neg_gr.addArc(n7, n5);
    331  
     331
    332332  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
    333333  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
    334334  Digraph::NodeMap<int> neg_s(neg_gr, 0);
    335  
     335
    336336  neg_l2[a7] =  1000;
    337337  neg_l2[a8] = -1000;
    338  
     338
    339339  neg_s[n1] =  100;
    340340  neg_s[n4] = -100;
    341  
     341
    342342  neg_c[a1] =  100;
    343343  neg_c[a2] =   30;
     
    423423    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
    424424      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
    425      
     425
    426426    NetworkSimplex<Digraph> negs_mcf(negs_gr);
    427427    negs_mcf.costMap(negs_c).supplyMap(negs_s);
  • test/preflow_test.cc

    r1027 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    114114  b = const_preflow_test.minCut(n);
    115115  const_preflow_test.minCutMap(cut);
    116  
     116
    117117  ignore_unused_variable_warning(fm);
    118118}
     
    155155{
    156156  DIGRAPH_TYPEDEFS(SmartDigraph);
    157  
     157
    158158  SmartDigraph g;
    159159  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     
    267267
    268268  initFlowTest();
    269  
     269
    270270  return 0;
    271271}
  • test/suurballe_test.cc

    r670 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8181  typedef Digraph::Arc Arc;
    8282  typedef concepts::ReadMap<Arc, VType> LengthMap;
    83  
     83
    8484  typedef Suurballe<Digraph, LengthMap> SuurballeType;
    8585
     
    105105  k = suurb_test.findFlow(n, k);
    106106  suurb_test.findPaths();
    107  
     107
    108108  int f;
    109109  VType c;
     
    117117  k = const_suurb_test.pathNum();
    118118  Path<Digraph> p = const_suurb_test.path(k);
    119  
     119
    120120  ignore_unused_variable_warning(fm);
    121121  ignore_unused_variable_warning(pm);
  • tools/dimacs-solver.cc

    r691 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8989  pre.run();
    9090  if(report) std::cerr << "Run Preflow: " << ti << '\n';
    91   if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; 
     91  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
    9292}
    9393
     
    148148  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
    149149  if(report) std::cerr << "\nCardinality of max matching: "
    150                        << mat.matchingSize() << '\n'; 
     150                       << mat.matchingSize() << '\n';
    151151}
    152152
     
    166166      exit(1);
    167167    }
    168  
     168
    169169  switch(desc.type)
    170170    {
     
    238238
    239239  DimacsDescriptor desc = dimacsType(is);
    240  
     240
    241241  if(!ap.given("q"))
    242242    {
     
    263263      std::cout << "\n\n";
    264264    }
    265    
     265
    266266  if(ap.given("double"))
    267267    solve<double>(ap,is,os,desc);
Note: See TracChangeset for help on using the changeset viewer.