COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 deleted
71 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r1096 r712  
    1 2011-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 
    9 2011-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        
    24 2010-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 
    37 2010-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 
    52 2009-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 
    7212009-05-13 Version 1.1 released
    732
  • doc/groups.dox

    r1081 r710  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
     
    276284This group contains the algorithms for finding shortest paths in digraphs.
    277285
    278  - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
    279    source node when all arc lengths are non-negative.
     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.
    280296 - \ref Suurballe A successive shortest path algorithm for finding
    281297   arc-disjoint paths between two nodes having minimum total length.
     
    302318\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    303319
    304 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and
    305 Tarjan for solving this problem. It also provides functions to query the
    306 minimum cut, which is the dual problem of maximum flow.
    307 
    308 
    309 \ref Circulation is a preflow push-relabel algorithm implemented directly
     320LEMON 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
     326In most cases the \ref Preflow "Preflow" algorithm provides the
     327fastest method for computing a maximum flow. All implementations
     328also provide functions to query the minimum cut, which is the dual
     329problem of maximum flow.
     330
     331\ref Circulation is a preflow push-relabel algorithm implemented directly
    310332for finding feasible circulations, which is a somewhat different problem,
    311333but it is strongly related to maximum flow.
     
    323345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    324346
    325 \ref NetworkSimplex is an efficient implementation of the primal Network
    326 Simplex algorithm for finding minimum cost flows. It also provides dual
    327 solution (node potentials), if an optimal flow is found.
     347LEMON 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
     357In general NetworkSimplex is the most efficient implementation,
     358but in special cases other algorithms could be faster.
     359For example, if the total supply and/or capacities are rather small,
     360CapacityScaling is usually the fastest algorithm (without effective scaling).
    328361*/
    329362
     
    349382- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    350383  in directed graphs.
     384- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     385  calculating minimum cut in undirected graphs.
    351386- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    352387  all-pairs minimum cut in undirected graphs.
     
    369404
    370405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
     415*/
     416
     417/**
    371418@defgroup matching Matching Algorithms
    372419@ingroup algs
    373420\brief Algorithms for finding matchings in graphs and bipartite graphs.
    374421
    375 This group contains the algorithms for calculating matchings in graphs.
    376 The general matching problem is finding a subset of the edges for which
    377 each node has at most one incident edge.
     422This group contains the algorithms for calculating
     423matchings in graphs and bipartite graphs. The general matching problem is
     424finding a subset of the edges for which each node has at most one incident
     425edge.
    378426
    379427There are several different algorithms for calculate matchings in
    380 graphs. The goal of the matching optimization
     428graphs.  The matching problems in bipartite graphs are generally
     429easier than in general graphs. The goal of the matching optimization
    381430can be finding maximum cardinality, maximum weight or minimum cost
    382431matching. The search can be constrained to find perfect or
     
    384433
    385434The 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.
    386445- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    387446  maximum cardinality matching in general graphs.
     
    415474
    416475/**
     476@defgroup approx Approximation Algorithms
     477@ingroup algs
     478\brief Approximation algorithms.
     479
     480This group contains the approximation and heuristic algorithms
     481implemented in LEMON.
     482*/
     483
     484/**
    417485@defgroup gen_opt_group General Optimization Tools
    418486\brief This group contains some general optimization frameworks
     
    431499various LP solvers could be used in the same manner with this
    432500interface.
     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
     508This group adds some helper tools to general optimization framework
     509implemented in LEMON.
     510*/
     511
     512/**
     513@defgroup metah Metaheuristics
     514@ingroup gen_opt_group
     515\brief Metaheuristics for LEMON library.
     516
     517This group contains some metaheuristic optimization tools.
    433518*/
    434519
  • doc/lgf.dox

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

    r1081 r710  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r703  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

    r1081 r664  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r674  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r967  
    1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1/* -*- C++ -*-
    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-2011
     5 * Copyright (C) 2003-2008
    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

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

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

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

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

    r1081 r1053  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r735  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

    r1081 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

    r1081 r627  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

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

    r1081 r695  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

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

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

    r1081 r631  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

    r1081 r695  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r900  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

    r1081 r643  
    1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1/* -*- C++ -*-
    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-2011
     5 * Copyright (C) 2003-2008
    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

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

    r1081 r644  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r1069  
    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

    r1081 r646  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r674  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

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

    r1093 r1092  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

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

    r1081 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

    r1081 r731  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r945  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r558  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r672  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

    r1081 r976  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

    r1081 r1027  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

    r1081 r623  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2008
    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

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

    r1081 r925  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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 Successive Shortest Path
    49   /// algorithm directly for this problem.
     48  /// efficient specialized version of the \ref CapacityScaling
     49  /// "Successive Shortest Path" 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

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

    r1109 r1102  
    6969test_graph_test_SOURCES = test/graph_test.cc
    7070test_graph_utils_test_SOURCES = test/graph_utils_test.cc
    71 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    7271test_heap_test_SOURCES = test/heap_test.cc
    7372test_kruskal_test_SOURCES = test/kruskal_test.cc
     73test_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/bfs_test.cc

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

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

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

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

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

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

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

    r1081 r643  
    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 
    191#include <iostream>
    202
     
    5234  "source 0\n"
    5335  "target 3\n";
    54 
     36 
    5537void checkGomoryHuCompile()
    5638{
     
    8870
    8971int cutValue(const Graph& graph, const BoolNodeMap& cut,
    90              const IntEdgeMap& capacity) {
     72             const IntEdgeMap& capacity) {
    9173
    9274  int sum = 0;
     
    126108      int sum=0;
    127109      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
    128         sum+=capacity[a];
     110        sum+=capacity[a]; 
    129111      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
    130112
     
    137119    }
    138120  }
    139 
     121 
    140122  return 0;
    141123}
  • test/graph_copy_test.cc

    r1081 r984  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

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

    r1097 r1087  
    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

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

    r1081 r731  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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&>,
    74                ReferenceMap<A,B,B&,const B&> >();
    75   checkConcept<ReferenceMap<A,C,C&,const C&>,
    76                ReferenceMap<A,C,C&,const 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&> >();
    7775
    7876  // NullMap
     
    203201
    204202    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    205     MapToFunctor<ReadMap<A,B> > map =
    206       MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
     203    MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
    207204
    208205    check(functorToMap(&func)[A()] == 3,
     
    353350      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    354351  }
    355 
     352 
    356353  // CrossRefMap
    357354  {
     
    361358    checkConcept<ReadWriteMap<Node, int>,
    362359                 CrossRefMap<Graph, Node, int> >();
    363 
     360   
    364361    Graph gr;
    365362    typedef CrossRefMap<Graph, Node, char> CRMap;
    366363    typedef CRMap::ValueIterator ValueIt;
    367364    CRMap map(gr);
    368 
     365   
    369366    Node n0 = gr.addNode();
    370367    Node n1 = gr.addNode();
    371368    Node n2 = gr.addNode();
    372 
     369   
    373370    map.set(n0, 'A');
    374371    map.set(n1, 'B');
  • test/matching_test.cc

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

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

    r1081 r716  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2009
    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

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

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

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