COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
72 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r712 r1096  
     12011-11-09 Version 1.1.5 released
     2
     3        Bugfix release.
     4
     5        #428: Add missing lemon/lemon.pc.cmake to the release tarball
     6        #429: Fix VS warnings
     7        #430: Fix LpBase::Constr two-side limit bug
     8
     92011-08-08 Version 1.1.4 released
     10
     11        Bugfix release.
     12
     13        #392: Bug fix in Dfs::start(s,t)
     14        #414: Fix wrong initialization in Preflow
     15        #404: Update Doxygen configuration
     16        #416: Support tests with valgrind
     17        #418: Better Win CodeBlock/MinGW support
     18        #419: Backport build environment improvements from the main branch
     19              - Build of mip_test and lp_test precede the running of the tests
     20              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
     21              - Do not look for COIN_VOL libraries
     22        #382: Allow lgf file without Arc maps
     23       
     242010-10-21 Version 1.1.3 released
     25
     26        Bugfix release.
     27
     28        #366: Fix Pred[Matrix]MapPath::empty()
     29        #371: Bug fix in (di)graphCopy()
     30              The target graph is cleared before adding nodes and arcs/edges.
     31
     32        #356: Fix multiple execution bug in weighted matchings
     33        #364: Add missing UndirectedTags
     34        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
     35        #372: Fix a critical bug in preflow
     36
     372010-03-08 Version 1.1.2 released
     38
     39        Bugfix release.
     40
     41        #317: Fix (and improve) error message in mip_test.cc
     42              Remove unnecessary OsiCbc dependency
     43        #250: Fix in pathSource() and pathTarget()
     44        #322: Distribute LEMONConfig.cmake.in
     45        #321: Use pathCopy(from,to) instead of copyPath(to,from)
     46        #330: Bug fix in map_extender.h
     47        #335: Fix clear() function in ExtendFindEnum
     48        #337: Use void* as LPX object pointer
     49        #336: Fix the date field comment of graphToEps() output
     50        #323: Bug fix in Suurballe
     51
     522009-10-03 Version 1.1.1 released
     53
     54        Bugfix release.
     55
     56        #295: Suppress MSVC warnings using pragmas
     57        ----: Various CMAKE related improvements
     58              * Remove duplications from doc/CMakeLists.txt
     59              * Rename documentation install folder from 'docs' to 'html'
     60              * Add tools/CMakeLists.txt to the tarball
     61              * Generate and install LEMONConfig.cmake
     62              * Change the label of the html project in Visual Studio
     63              * Fix the check for the 'long long' type
     64              * Put the version string into config.h
     65              * Minor CMake improvements
     66              * Set the version to 'hg-tip' if everything fails
     67        #311: Add missing 'explicit' keywords
     68        #302: Fix the implementation and doc of CrossRefMap
     69        #308: Remove duplicate list_graph.h entry from source list
     70        #307: Bug fix in Preflow and Circulation
     71
    1722009-05-13 Version 1.1 released
    273
  • doc/groups.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).
     
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    284276This group contains the algorithms for finding shortest paths in digraphs.
    285277
    286  - \ref Dijkstra algorithm for finding shortest paths from a source node
    287    when all arc lengths are non-negative.
    288  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    289    from a source node when arc lenghts can be either positive or negative,
    290    but the digraph should not contain directed cycles with negative total
    291    length.
    292  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    293    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    294    lenghts can be either positive or negative, but the digraph should
    295    not contain directed cycles with negative total length.
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
    296280 - \ref Suurballe A successive shortest path algorithm for finding
    297281   arc-disjoint paths between two nodes having minimum total length.
     
    318302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319303
    320 LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
    327 fastest method for computing a maximum flow. All implementations
    328 also provide functions to query the minimum cut, which is the dual
    329 problem of maximum flow.
    330 
    331 \ref Circulation is a preflow push-relabel algorithm implemented directly
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
     308
     309\ref Circulation is a preflow push-relabel algorithm implemented directly
    332310for finding feasible circulations, which is a somewhat different problem,
    333311but it is strongly related to maximum flow.
     
    345323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    346324
    347 LEMON contains several algorithms for this problem.
    348  - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
    356 
    357 In general NetworkSimplex is the most efficient implementation,
    358 but in special cases other algorithms could be faster.
    359 For example, if the total supply and/or capacities are rather small,
    360 CapacityScaling is usually the fastest algorithm (without effective scaling).
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    361328*/
    362329
     
    382349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383350  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387352  all-pairs minimum cut in undirected graphs.
     
    404369
    405370/**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
    415 */
    416 
    417 /**
    418371@defgroup matching Matching Algorithms
    419372@ingroup algs
    420373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    421374
    422 This group contains the algorithms for calculating
    423 matchings in graphs and bipartite graphs. The general matching problem is
    424 finding a subset of the edges for which each node has at most one incident
    425 edge.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    426378
    427379There are several different algorithms for calculate matchings in
    428 graphs.  The matching problems in bipartite graphs are generally
    429 easier than in general graphs. The goal of the matching optimization
     380graphs. The goal of the matching optimization
    430381can be finding maximum cardinality, maximum weight or minimum cost
    431382matching. The search can be constrained to find perfect or
     
    433384
    434385The matching algorithms implemented in LEMON:
    435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    436   for calculating maximum cardinality matching in bipartite graphs.
    437 - \ref PrBipartiteMatching Push-relabel algorithm
    438   for calculating maximum cardinality matching in bipartite graphs.
    439 - \ref MaxWeightedBipartiteMatching
    440   Successive shortest path algorithm for calculating maximum weighted
    441   matching and maximum weighted bipartite matching in bipartite graphs.
    442 - \ref MinCostMaxBipartiteMatching
    443   Successive shortest path algorithm for calculating minimum cost maximum
    444   matching in bipartite graphs.
    445386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446387  maximum cardinality matching in general graphs.
     
    474415
    475416/**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482 */
    483 
    484 /**
    485417@defgroup gen_opt_group General Optimization Tools
    486418\brief This group contains some general optimization frameworks
     
    499431various LP solvers could be used in the same manner with this
    500432interface.
    501 */
    502 
    503 /**
    504 @defgroup lp_utils Tools for Lp and Mip Solvers
    505 @ingroup lp_group
    506 \brief Helper tools to the Lp and Mip solvers.
    507 
    508 This group adds some helper tools to general optimization framework
    509 implemented in LEMON.
    510 */
    511 
    512 /**
    513 @defgroup metah Metaheuristics
    514 @ingroup gen_opt_group
    515 \brief Metaheuristics for LEMON library.
    516 
    517 This group contains some metaheuristic optimization tools.
    518433*/
    519434
  • 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

    r1157 r1158  
    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

    r730 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

    r1157 r1158  
    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

    r867 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

    r1140 r1141  
    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

    r1157 r1158  
    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

    r1140 r1141  
    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

    r1171 r1172  
    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      ///
     
    126126    /// This class describes the base interface of directed graph types.
    127127    /// All digraph %concepts have to conform to this class.
    128     /// It just provides types for nodes and arcs and functions 
     128    /// It just provides types for nodes and arcs and functions
    129129    /// to get the source and the target nodes of arcs.
    130130    class BaseDigraphComponent {
     
    434434    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    435435    ///
    436     /// This class describes the concept of \c NodeIt, \c ArcIt and 
     436    /// This class describes the concept of \c NodeIt, \c ArcIt and
    437437    /// \c EdgeIt subtypes of digraph and graph types.
    438438    template <typename GR, typename Item>
     
    474474      /// next item.
    475475      GraphItemIt& operator++() { return *this; }
    476  
     476
    477477      /// \brief Equality operator
    478478      ///
     
    512512    };
    513513
    514     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     514    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    515515    /// \c IncEdgeIt types.
    516516    ///
    517     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     517    /// This class describes the concept of \c InArcIt, \c OutArcIt
    518518    /// and \c IncEdgeIt subtypes of digraph and graph types.
    519519    ///
    520520    /// \note Since these iterator classes do not inherit from the same
    521521    /// base class, there is an additional template parameter (selector)
    522     /// \c sel. For \c InArcIt you should instantiate it with character 
     522    /// \c sel. For \c InArcIt you should instantiate it with character
    523523    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    524524    template <typename GR,
     
    541541      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    542542
    543       /// \brief Constructor that sets the iterator to the first 
     543      /// \brief Constructor that sets the iterator to the first
    544544      /// incoming or outgoing arc.
    545545      ///
    546       /// Constructor that sets the iterator to the first arc 
     546      /// Constructor that sets the iterator to the first arc
    547547      /// incoming to or outgoing from the given node.
    548548      explicit GraphIncIt(const GR&, const Base&) {}
     
    819819      /// \brief Return the first edge incident to the given node.
    820820      ///
    821       /// This function gives back the first edge incident to the given 
     821      /// This function gives back the first edge incident to the given
    822822      /// node. The bool parameter gives back the direction for which the
    823       /// source node of the directed arc representing the edge is the 
     823      /// source node of the directed arc representing the edge is the
    824824      /// given node.
    825825      void firstInc(Edge&, bool&, const Node&) const {}
     
    828828      /// given node.
    829829      ///
    830       /// This function gives back the next edge incident to the given 
     830      /// This function gives back the next edge incident to the given
    831831      /// node. The bool parameter should be used as \c firstInc() use it.
    832832      void nextInc(Edge&, bool&) const {}
     
    10081008    ///
    10091009    /// This class describes the concept of standard graph maps, i.e.
    1010     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     1010    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    10111011    /// graph types, which can be used for associating data to graph items.
    10121012    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10631063          _Map m1(g);
    10641064          _Map m2(g,t);
    1065          
     1065
    10661066          // Copy constructor
    10671067          // _Map m3(m);
     
    10871087    ///
    10881088    /// This class describes the interface of mappable directed graphs.
    1089     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1089    /// It extends \ref BaseDigraphComponent with the standard digraph
    10901090    /// map classes, namely \c NodeMap and \c ArcMap.
    10911091    /// This concept is part of the Digraph concept.
     
    12251225    ///
    12261226    /// This class describes the interface of mappable undirected graphs.
    1227     /// It extends \ref MappableDigraphComponent with the standard graph 
     1227    /// It extends \ref MappableDigraphComponent with the standard graph
    12281228    /// map class for edges (\c EdgeMap).
    12291229    /// This concept is part of the Graph concept.
     
    13111311    ///
    13121312    /// This class describes the interface of extendable directed graphs.
    1313     /// It extends \ref BaseDigraphComponent with functions for adding 
     1313    /// It extends \ref BaseDigraphComponent with functions for adding
    13141314    /// nodes and arcs to the digraph.
    13151315    /// This concept requires \ref AlterableDigraphComponent.
     
    13561356    ///
    13571357    /// This class describes the interface of extendable undirected graphs.
    1358     /// It extends \ref BaseGraphComponent with functions for adding 
     1358    /// It extends \ref BaseGraphComponent with functions for adding
    13591359    /// nodes and edges to the graph.
    13601360    /// This concept requires \ref AlterableGraphComponent.
     
    14011401    ///
    14021402    /// This class describes the interface of erasable directed graphs.
    1403     /// It extends \ref BaseDigraphComponent with functions for removing 
     1403    /// It extends \ref BaseDigraphComponent with functions for removing
    14041404    /// nodes and arcs from the digraph.
    14051405    /// This concept requires \ref AlterableDigraphComponent.
     
    14141414      /// \brief Erase a node from the digraph.
    14151415      ///
    1416       /// This function erases the given node from the digraph and all arcs 
     1416      /// This function erases the given node from the digraph and all arcs
    14171417      /// connected to the node.
    14181418      void erase(const Node&) {}
     
    14411441    ///
    14421442    /// This class describes the interface of erasable undirected graphs.
    1443     /// It extends \ref BaseGraphComponent with functions for removing 
     1443    /// It extends \ref BaseGraphComponent with functions for removing
    14441444    /// nodes and edges from the graph.
    14451445    /// This concept requires \ref AlterableGraphComponent.
  • lemon/concepts/maps.h

    r1157 r1158  
    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

    r1236 r1237  
    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).
     
    12471247  protected:
    12481248
    1249     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1249    class AutoNodeMap :
     1250      public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
    12501251      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12511252
     
    12861287    };
    12871288
    1288   protected: 
     1289  protected:
    12891290
    12901291    const Digraph &_g;
  • lemon/cplex.cc

    r1181 r1182  
    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).
     
    456456
    457457  void CplexBase::_applyMessageLevel() {
    458     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     458    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    459459                   _message_enabled ? CPX_ON : CPX_OFF);
    460460  }
  • lemon/dfs.h

    r1125 r1126  
    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

    r1157 r1158  
    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

    r1140 r1141  
    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

    r1144 r1145  
    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).
     
    10191019    };
    10201020
    1021    
     1021
    10221022    template <typename From, typename To,
    10231023              bool revEnable = RevPathTagIndicator<From>::value>
     
    10251025      static void copy(const From& from, To& to) {
    10261026        PathCopySelectorForward<From, To>::copy(from, to);
    1027       }     
     1027      }
    10281028    };
    10291029
     
    10321032      static void copy(const From& from, To& to) {
    10331033        PathCopySelectorBackward<From, To>::copy(from, to);
    1034       }     
     1034      }
    10351035    };
    10361036
  • 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

    r925 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).
     
    4646  /// Note that this problem is a special case of the \ref min_cost_flow
    4747  /// "minimum cost flow problem". This implementation is actually an
    48   /// efficient specialized version of the \ref CapacityScaling
    49   /// "Successive Shortest Path" algorithm directly for this problem.
     48  /// efficient specialized version of the Successive Shortest Path
     49  /// algorithm directly for this problem.
    5050  /// Therefore this class provides query functions for flow values and
    5151  /// node potentials (the dual solution) just like the minimum cost flow
  • lemon/unionfind.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).
  • test/Makefile.am

    r1102 r1109  
    6969test_graph_test_SOURCES = test/graph_test.cc
    7070test_graph_utils_test_SOURCES = test/graph_utils_test.cc
     71test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    7172test_heap_test_SOURCES = test/heap_test.cc
    7273test_kruskal_test_SOURCES = test/kruskal_test.cc
    73 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    7474test_lgf_test_SOURCES = test/lgf_test.cc
    7575test_lp_test_SOURCES = test/lp_test.cc
  • test/adaptors_test.cc

    r1157 r1158  
    13811381
    13821382  // Apply several adaptors on the grid graph
    1383   typedef SplitNodes< ReverseDigraph< const Orienter<
    1384             const GridGraph, GridGraph::EdgeMap<bool> > > >
    1385     RevSplitGridGraph;
     1383  typedef Orienter<const GridGraph, GridGraph::EdgeMap<bool> >
     1384    OrientedGridGraph;
     1385  typedef ReverseDigraph<const OrientedGridGraph> RevOrientedGridGraph;
     1386  typedef SplitNodes<RevOrientedGridGraph> RevSplitGridGraph;
    13861387  typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
    13871388  typedef Undirector<const SplitGridGraph> USplitGridGraph;
     
    13921393  checkConcept<concepts::Graph, UUSplitGridGraph>();
    13931394
     1395  OrientedGridGraph ori_adaptor = orienter(graph, dir_map);
     1396  RevOrientedGridGraph rev_ori_adaptor = reverseDigraph(ori_adaptor);
    13941397  RevSplitGridGraph rev_adaptor =
    1395     splitNodes(reverseDigraph(orienter(graph, dir_map)));
     1398    splitNodes(rev_ori_adaptor);
    13961399  SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
    13971400  USplitGridGraph uadaptor = undirector(adaptor);
  • test/bfs_test.cc

    r1171 r1172  
    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).
     
    8585    b = const_bfs_test.emptyQueue();
    8686    i = const_bfs_test.queueSize();
    87    
     87
    8888    bfs_test.start();
    8989    bfs_test.start(t);
     
    106106      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    107107      ::Create bfs_test(G);
    108      
     108
    109109    concepts::ReadWriteMap<Node,Arc> pred_map;
    110110    concepts::ReadWriteMap<Node,int> dist_map;
    111111    concepts::ReadWriteMap<Node,bool> reached_map;
    112112    concepts::WriteMap<Node,bool> processed_map;
    113    
     113
    114114    bfs_test
    115115      .predMap(pred_map)
     
    121121    bfs_test.run(s,t);
    122122    bfs_test.run();
    123    
     123
    124124    bfs_test.init();
    125125    bfs_test.addSource(s);
     
    130130    b = bfs_test.emptyQueue();
    131131    i = bfs_test.queueSize();
    132    
     132
    133133    bfs_test.start();
    134134    bfs_test.start(t);
  • test/circulation_test.cc

    r1171 r1172  
    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).
     
    8383  CirculationType circ_test(g, lcap, ucap, supply);
    8484  const CirculationType& const_circ_test = circ_test;
    85    
     85
    8686  circ_test
    8787    .lowerMap(lcap)
     
    9999  b = const_circ_test.barrier(n);
    100100  const_circ_test.barrierMap(bar);
    101  
     101
    102102  ignore_unused_variable_warning(fm);
    103103}
  • test/connectivity_test.cc

    r1157 r1158  
    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.");
     
    8484    check(countBiEdgeConnectedComponents(g) == 1,
    8585          "This graph has 1 bi-edge-connected component");
    86          
     86
    8787    check(dag(d), "This digraph is DAG.");
    8888    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
     
    103103    Digraph::NodeMap<int> order(d);
    104104    Graph g(d);
    105    
     105
    106106    Digraph::Node n1 = d.addNode();
    107107    Digraph::Node n2 = d.addNode();
     
    110110    Digraph::Node n5 = d.addNode();
    111111    Digraph::Node n6 = d.addNode();
    112    
     112
    113113    d.addArc(n1, n3);
    114114    d.addArc(n3, n2);
     
    138138    check(!parallelFree(g), "This graph is not parallel-free.");
    139139    check(!simpleGraph(g), "This graph is not simple.");
    140    
     140
    141141    d.addArc(n3, n3);
    142    
     142
    143143    check(!loopFree(d), "This digraph is not loop-free.");
    144144    check(!loopFree(g), "This graph is not loop-free.");
    145145    check(!simpleGraph(d), "This digraph is not simple.");
    146    
     146
    147147    d.addArc(n3, n2);
    148    
     148
    149149    check(!parallelFree(d), "This digraph is not parallel-free.");
    150150  }
    151  
     151
    152152  {
    153153    Digraph d;
    154154    Digraph::ArcMap<bool> cutarcs(d, false);
    155155    Graph g(d);
    156    
     156
    157157    Digraph::Node n1 = d.addNode();
    158158    Digraph::Node n2 = d.addNode();
     
    174174    d.addArc(n6, n7);
    175175    d.addArc(n7, n6);
    176    
     176
    177177    check(!stronglyConnected(d), "This digraph is not strongly connected");
    178178    check(countStronglyConnectedComponents(d) == 3,
     
    237237    Digraph d;
    238238    Digraph::NodeMap<int> order(d);
    239    
     239
    240240    Digraph::Node belt = d.addNode();
    241241    Digraph::Node trousers = d.addNode();
     
    258258    d.addArc(shirt, necktie);
    259259    d.addArc(necktie, coat);
    260    
     260
    261261    check(dag(d), "This digraph is DAG.");
    262262    topologicalSort(d, order);
     
    270270    ListGraph g;
    271271    ListGraph::NodeMap<bool> map(g);
    272    
     272
    273273    ListGraph::Node n1 = g.addNode();
    274274    ListGraph::Node n2 = g.addNode();
     
    286286    g.addEdge(n4, n7);
    287287    g.addEdge(n5, n7);
    288    
     288
    289289    check(bipartite(g), "This graph is bipartite");
    290290    check(bipartitePartitions(g, map), "This graph is bipartite");
    291    
     291
    292292    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
    293293          "Wrong bipartitePartitions()");
  • test/dfs_test.cc

    r1171 r1172  
    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    b = const_dfs_test.emptyQueue();
    9090    i = const_dfs_test.queueSize();
    91    
     91
    9292    dfs_test.start();
    9393    dfs_test.start(t);
     
    115115    concepts::ReadWriteMap<Node,bool> reached_map;
    116116    concepts::WriteMap<Node,bool> processed_map;
    117    
     117
    118118    dfs_test
    119119      .predMap(pred_map)
     
    132132    b = dfs_test.emptyQueue();
    133133    i = dfs_test.queueSize();
    134    
     134
    135135    dfs_test.start();
    136136    dfs_test.start(t);
     
    224224  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
    225225  }
    226  
     226
    227227  {
    228228    NullMap<Node,Arc> myPredMap;
  • test/dijkstra_test.cc

    r1171 r1172  
    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).
     
    8888    b = const_dijkstra_test.emptyQueue();
    8989    i = const_dijkstra_test.queueSize();
    90    
     90
    9191    dijkstra_test.start();
    9292    dijkstra_test.start(t);
     
    112112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    113113      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    114       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 
     114      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
    115115                concepts::ReadWriteMap<Node,int> >
    116116      ::Create dijkstra_test(G,length);
     
    122122    concepts::ReadWriteMap<Node,int> heap_cross_ref;
    123123    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
    124    
     124
    125125    dijkstra_test
    126126      .lengthMap(length_map)
     
    139139    b = dijkstra_test.emptyQueue();
    140140    i = dijkstra_test.queueSize();
    141    
     141
    142142    dijkstra_test.start();
    143143    dijkstra_test.start(t);
  • test/edge_set_test.cc

    r1157 r1158  
    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

    r1157 r1158  
    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);
     
    130130    Digraph::Node n2 = d.addNode();
    131131    Digraph::Node n3 = d.addNode();
    132    
     132
    133133    d.addArc(n1, n2);
    134134    d.addArc(n2, n1);
     
    155155    Digraph::Node n5 = d.addNode();
    156156    Digraph::Node n6 = d.addNode();
    157    
     157
    158158    d.addArc(n1, n2);
    159159    d.addArc(n2, n4);
     
    214214    Digraph::Node n2 = d.addNode();
    215215    Digraph::Node n3 = d.addNode();
    216    
     216
    217217    d.addArc(n1, n2);
    218218    d.addArc(n2, n3);
  • test/gomory_hu_test.cc

    r1171 r1172  
     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{
     
    7189
    7290int cutValue(const Graph& graph, const BoolNodeMap& cut,
    73              const IntEdgeMap& capacity) {
     91             const IntEdgeMap& capacity) {
    7492
    7593  int sum = 0;
     
    109127      int sum=0;
    110128      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    111         sum+=capacity[a]; 
     129        sum+=capacity[a];
    112130      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    113131
     
    120138    }
    121139  }
    122  
     140
    123141  return 0;
    124142}
  • 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

    r1171 r1172  
    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).
     
    8585
    8686template <typename Graph, typename CapMap, typename CutMap>
    87 typename CapMap::Value 
     87typename CapMap::Value
    8888  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    8989{
     
    112112    ho.run();
    113113    ho.minCutMap(cut);
    114    
     114
    115115    check(ho.minCutValue() == 1, "Wrong cut value");
    116116    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
     
    128128    ho.run();
    129129    ho.minCutMap(cut);
    130    
     130
    131131    check(ho.minCutValue() == 1, "Wrong cut value");
    132132    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
    133133  }
    134  
     134
    135135  typedef Undirector<SmartDigraph> UGraph;
    136136  UGraph ugraph(graph);
    137  
     137
    138138  {
    139139    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
    140140    ho.run();
    141141    ho.minCutMap(cut);
    142    
     142
    143143    check(ho.minCutValue() == 2, "Wrong cut value");
    144144    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
     
    148148    ho.run();
    149149    ho.minCutMap(cut);
    150    
     150
    151151    check(ho.minCutValue() == 5, "Wrong cut value");
    152152    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
     
    156156    ho.run();
    157157    ho.minCutMap(cut);
    158    
     158
    159159    check(ho.minCutValue() == 5, "Wrong cut value");
    160160    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
  • test/heap_test.cc

    r728 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

    r1087 r1097  
    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&) 
     120    catch (FormatError&)
    121121      {
    122122        ok = true;
     
    140140
    141141  {
    142     ListDigraph d; 
     142    ListDigraph d;
    143143    std::istringstream input(test_lgf_bad2);
    144144    bool ok=false;
  • test/lp_test.cc

    r1232 r1237  
    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/maps_test.cc

    r1157 r1158  
    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
     
    369371      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    370372  }
    371  
     373
    372374  // CrossRefMap
    373375  {
     
    377379    checkConcept<ReadWriteMap<Node, int>,
    378380                 CrossRefMap<Graph, Node, int> >();
    379    
     381
    380382    Graph gr;
    381383    typedef CrossRefMap<Graph, Node, char> CRMap;
    382384    typedef CRMap::ValueIterator ValueIt;
    383385    CRMap map(gr);
    384    
     386
    385387    Node n0 = gr.addNode();
    386388    Node n1 = gr.addNode();
    387389    Node n2 = gr.addNode();
    388    
     390
    389391    map.set(n0, 'A');
    390392    map.set(n1, 'B');
  • test/matching_test.cc

    r1171 r1172  
    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  ignore_unused_variable_warning(stat);
     
    172172  mat_test.start();
    173173  mat_test.run();
    174  
     174
    175175  const_mat_test.matchingWeight();
    176176  const_mat_test.matchingSize();
     
    181181  e = mmap[n];
    182182  const_mat_test.mate(n);
    183  
     183
    184184  int k = 0;
    185185  const_mat_test.dualValue();
     
    209209  mat_test.start();
    210210  mat_test.run();
    211  
     211
    212212  const_mat_test.matchingWeight();
    213213  const_mat_test.matching(e);
     
    217217  e = mmap[n];
    218218  const_mat_test.mate(n);
    219  
     219
    220220  int k = 0;
    221221  const_mat_test.dualValue();
  • test/min_cost_arborescence_test.cc

    r1171 r1172  
    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).
     
    112112  b = const_mcarb_test.emptyQueue();
    113113  i = const_mcarb_test.queueSize();
    114  
     114
    115115  c = const_mcarb_test.arborescenceCost();
    116116  b = const_mcarb_test.arborescence(e);
     
    122122  b = const_mcarb_test.reached(n);
    123123  b = const_mcarb_test.processed(n);
    124  
     124
    125125  i = const_mcarb_test.dualNum();
    126126  c = const_mcarb_test.dualValue();
    127127  i = const_mcarb_test.dualSize(i);
    128128  c = const_mcarb_test.dualValue(i);
    129  
     129
    130130  ignore_unused_variable_warning(am);
    131131  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

    r1171 r1172  
    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).
     
    115115  b = const_preflow_test.minCut(n);
    116116  const_preflow_test.minCutMap(cut);
    117  
     117
    118118  ignore_unused_variable_warning(fm);
    119119}
     
    156156{
    157157  DIGRAPH_TYPEDEFS(SmartDigraph);
    158  
     158
    159159  SmartDigraph g;
    160160  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     
    268268
    269269  initFlowTest();
    270  
     270
    271271  return 0;
    272272}
  • test/suurballe_test.cc

    r1171 r1172  
    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;
     
    119119  k = const_suurb_test.pathNum();
    120120  Path<Digraph> p = const_suurb_test.path(k);
    121  
     121
    122122  ignore_unused_variable_warning(fm);
    123123  ignore_unused_variable_warning(pm);
  • tools/dimacs-solver.cc

    r1167 r1168  
    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
     
    149149  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';
    150150  if(report) std::cerr << "\nCardinality of max matching: "
    151                        << mat.matchingSize() << '\n'; 
     151                       << mat.matchingSize() << '\n';
    152152}
    153153
     
    167167      exit(1);
    168168    }
    169  
     169
    170170  switch(desc.type)
    171171    {
     
    236236
    237237  DimacsDescriptor desc = dimacsType(is);
    238  
     238
    239239  if(!ap.given("q"))
    240240    {
     
    261261      std::cout << "\n\n";
    262262    }
    263    
     263
    264264  if(ap.given("double"))
    265265    solve<double>(ap,is,os,desc);
Note: See TracChangeset for help on using the changeset viewer.