COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
9 added
6 deleted
93 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r610 r944  
    2323lemon/stamp-h2
    2424doc/Doxyfile
     25doc/references.dox
    2526cmake/version.cmake
    2627.dirstamp

  • LICENSE

    r600 r959  
    22copyright/license.
    33
    4 Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).

  • README

    r705 r921  
    1818   Copying, distribution and modification conditions and terms.
    1919
     20NEWS
     21
     22   News and version history.
     23
    2024INSTALL
    2125
    … …  
    3438   Some example programs to make you easier to get familiar with LEMON.
    3539
     40scripts/
     41
     42   Scripts that make it easier to develop LEMON.
     43
    3644test/
    3745

  • demo/arg_parser_demo.cc

    r463 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    6666    .other("...");
    6767
     68  // Throw an exception when problems occurs. The default behavior is to
     69  // exit(1) on these cases, but this makes Valgrind falsely warn
     70  // about memory leaks.
     71  ap.throwOnProblems();
     72
    6873  // Perform the parsing process
    6974  // (in case of any error it terminates the program)
    70   ap.parse();
     75  // The try {} construct is necessary only if the ap.trowOnProblems()
     76  // setting is in use.
     77  try {
     78    ap.parse();
     79  } catch (ArgParserException &) { return 1; }
    7180
    7281  // Check each option if it has been given and print its value

  • doc/CMakeLists.txt

    r895 r943  
    2121    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    2222    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     23    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    2324    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    2425    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps

  • doc/Makefile.am

    r895 r943  
    2828        connected_components.eps \
    2929        edge_biconnected_components.eps \
     30        matching.eps \
    3031        node_biconnected_components.eps \
    3132        planar.eps \

  • doc/groups.dox

    r879 r959  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    264264
    265265/**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
    271 */
    272 
    273 /**
    274266@defgroup auxdat Auxiliary Data Structures
    275267@ingroup datas
    … …  
    387379problem of maximum flow.
    388380
    389 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     381\ref Circulation is a preflow push-relabel algorithm implemented directly
    390382for finding feasible circulations, which is a somewhat different problem,
    391383but it is strongly related to maximum flow.
    … …  
    473465
    474466LEMON contains three algorithms for solving the minimum mean cycle problem:
    475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     467- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    476468  \ref dasdan98minmeancycle.
    477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     469- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    478470  version of Karp's algorithm \ref dasdan98minmeancycle.
    479 - \ref Howard "Howard"'s policy iteration algorithm
     471- \ref HowardMmc Howard's policy iteration algorithm
    480472  \ref dasdan98minmeancycle.
    481473
    482 In practice, the Howard algorithm proved to be by far the most efficient
    483 one, though the best known theoretical bound on its running time is
    484 exponential.
    485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    487 applied early termination scheme.
     474In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     475most efficient one, though the best known theoretical bound on its running
     476time is exponential.
     477Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     478run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     479typically faster due to the applied early termination scheme.
    488480*/
    489481
    … …  
    523515  Edmond's blossom shrinking algorithm for calculating maximum weighted
    524516  perfect matching in general graphs.
    525 
    526 \image html bipartite_matching.png
    527 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
     517- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     518  maximum cardinality fractional matching in general graphs.
     519- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     520  maximum weighted fractional matching in general graphs.
     521- \ref MaxWeightedPerfectFractionalMatching
     522  Augmenting path algorithm for calculating maximum weighted
     523  perfect fractional matching in general graphs.
     524
     525\image html matching.png
     526\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
    528527*/
    529528

  • doc/mainpage.dox

    r802 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2424<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    2525and <b>O</b>ptimization in <b>N</b>etworks</i>.
    26 It is a C++ template library providing efficient implementation of common
     26It is a C++ template library providing efficient implementations of common
    2727data structures and algorithms with focus on combinatorial optimization
    28 problems in graphs and networks.
     28tasks connected mainly with graphs and networks.
    2929
    3030<b>
    … …  
    3636</b>
    3737
    38 The project is maintained by the 
     38The project is maintained by the
    3939<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
    4040Combinatorial Optimization</a> \ref egres
    4141at the Operations Research Department of the
    42 <a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
    43 Budapest</a>, Hungary.
     42<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
     43Budapest, Hungary.
    4444LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
    4545initiative \ref coinor.
    … …  
    5050<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5151
     52If you are interested in starting to use the library, see the <a class="el"
     53href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
     54Guide</a>.
     55
    5256If you know what you are looking for, then try to find it under the
    5357<a class="el" href="modules.html">Modules</a> section.

  • doc/min_cost_flow.dox

    r835 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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/Makefile.am

    r888 r953  
    6161        lemon/bfs.h \
    6262        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
     63        lemon/binomial_heap.h \
    6464        lemon/bucket_heap.h \
    6565        lemon/capacity_scaling.h \
    … …  
    7676        lemon/cycle_canceling.h \
    7777        lemon/dfs.h \
     78        lemon/dheap.h \
    7879        lemon/dijkstra.h \
    7980        lemon/dim2.h \
    … …  
    8485        lemon/euler.h \
    8586        lemon/fib_heap.h \
    86         lemon/fourary_heap.h \
     87        lemon/fractional_matching.h \
    8788        lemon/full_graph.h \
    8889        lemon/glpk.h \
    … …  
    9091        lemon/graph_to_eps.h \
    9192        lemon/grid_graph.h \
    92         lemon/hartmann_orlin.h \
    93         lemon/howard.h \
     93        lemon/hartmann_orlin_mmc.h \
     94        lemon/howard_mmc.h \
    9495        lemon/hypercube_graph.h \
    95         lemon/karp.h \
    96         lemon/kary_heap.h \
     96        lemon/karp_mmc.h \
    9797        lemon/kruskal.h \
    9898        lemon/hao_orlin.h \
    … …  
    113113        lemon/planarity.h \
    114114        lemon/preflow.h \
     115        lemon/quad_heap.h \
    115116        lemon/radix_heap.h \
    116117        lemon/radix_sort.h \

  • lemon/adaptors.h

    r834 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    422422      Parent::initialize(digraph);
    423423      _node_filter = &node_filter;
    424       _arc_filter = &arc_filter;     
     424      _arc_filter = &arc_filter;
    425425    }
    426426
    … …  
    509509
    510510    template <typename V>
    511     class NodeMap 
    512       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
    513               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     511    class NodeMap
     512      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     513              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    514514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     515        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516516
    517517    public:
    … …  
    536536
    537537    template <typename V>
    538     class ArcMap 
     538    class ArcMap
    539539      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    540               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     540              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    541541      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    542542        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    … …  
    583583      Parent::initialize(digraph);
    584584      _node_filter = &node_filter;
    585       _arc_filter = &arc_filter;     
     585      _arc_filter = &arc_filter;
    586586    }
    587587
    … …  
    652652
    653653    template <typename V>
    654     class NodeMap 
     654    class NodeMap
    655655      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656656          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    657       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
     657      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    658658        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    659659
    … …  
    679679
    680680    template <typename V>
    681     class ArcMap 
     681    class ArcMap
    682682      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    683683          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    … …  
    10221022
    10231023    template <typename V>
    1024     class NodeMap 
     1024    class NodeMap
    10251025      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10261026          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1027       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1027      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10281028        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10291029
    … …  
    10491049
    10501050    template <typename V>
    1051     class ArcMap 
     1051    class ArcMap
    10521052      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10531053          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1054       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1054      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10551055        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10561056
    … …  
    10761076
    10771077    template <typename V>
    1078     class EdgeMap 
     1078    class EdgeMap
    10791079      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10801080        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1081       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1081      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10821082        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10831083
    … …  
    11181118    NF* _node_filter;
    11191119    EF* _edge_filter;
    1120     SubGraphBase() 
    1121           : Parent(), _node_filter(0), _edge_filter(0) { }
     1120    SubGraphBase()
     1121          : Parent(), _node_filter(0), _edge_filter(0) { }
    11221122
    11231123    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
    … …  
    12201220
    12211221    template <typename V>
    1222     class NodeMap 
     1222    class NodeMap
    12231223      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12241224          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1225       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1225      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12261226        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12271227
    … …  
    12471247
    12481248    template <typename V>
    1249     class ArcMap 
     1249    class ArcMap
    12501250      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12511251          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1252       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1252      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12531253        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12541254
    … …  
    12741274
    12751275    template <typename V>
    1276     class EdgeMap 
     1276    class EdgeMap
    12771277      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12781278        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1279       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    1280         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1279      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1280        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12811281
    12821282    public:
    … …  
    15051505#endif
    15061506    typedef DigraphAdaptorExtender<
    1507       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
     1507      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    15081508                     true> > Parent;
    15091509
    … …  
    15261526    /// Creates a subgraph for the given digraph or graph with the
    15271527    /// given node filter map.
    1528     FilterNodes(GR& graph, NF& node_filter) 
     1528    FilterNodes(GR& graph, NF& node_filter)
    15291529      : Parent(), const_true_map()
    15301530    {
    … …  
    15641564                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15651565    public GraphAdaptorExtender<
    1566       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1566      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15671567                   true> > {
    15681568
    15691569    typedef GraphAdaptorExtender<
    1570       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1570      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15711571                   true> > Parent;
    15721572
    … …  
    16541654#endif
    16551655    typedef DigraphAdaptorExtender<
    1656       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
     1656      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    16571657                     AF, false> > Parent;
    16581658
    … …  
    17621762  class FilterEdges :
    17631763    public GraphAdaptorExtender<
    1764       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1764      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17651765                   EF, false> > {
    17661766#endif
    17671767    typedef GraphAdaptorExtender<
    1768       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
     1768      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    17691769                   EF, false> > Parent;
    17701770
    … …  
    17911791    /// Creates a subgraph for the given graph with the given edge
    17921792    /// filter map.
    1793     FilterEdges(GR& graph, EF& edge_filter) 
     1793    FilterEdges(GR& graph, EF& edge_filter)
    17941794      : Parent(), const_true_map() {
    17951795      Parent::initialize(graph, const_true_map, edge_filter);
    … …  
    18591859      bool _forward;
    18601860
    1861       Arc(const Edge& edge, bool forward) 
     1861      Arc(const Edge& edge, bool forward)
    18621862        : _edge(edge), _forward(forward) {}
    18631863
    … …  
    20992099
    21002100      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2101         : _forward(*adaptor._digraph, value), 
     2101        : _forward(*adaptor._digraph, value),
    21022102          _backward(*adaptor._digraph, value) {}
    21032103
    … …  
    22172217    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22182218    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2219    
     2219
    22202220    typedef EdgeNotifier ArcNotifier;
    22212221    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
    … …  
    27292729           typename FM = CM,
    27302730           typename TL = Tolerance<typename CM::Value> >
    2731   class ResidualDigraph 
     2731  class ResidualDigraph
    27322732    : public SubDigraph<
    27332733        Undirector<const DGR>,
    … …  
    27862786    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27872787                    FM& flow, const TL& tolerance = Tolerance())
    2788       : Parent(), _capacity(&capacity), _flow(&flow), 
     2788      : Parent(), _capacity(&capacity), _flow(&flow),
    27892789        _graph(digraph), _node_filter(),
    27902790        _forward_filter(capacity, flow, tolerance),
    … …  
    28682868
    28692869      /// Constructor
    2870       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2870      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28712871        : _adaptor(&adaptor) {}
    28722872
    … …  
    34483448    /// to get a node map of the split digraph.
    34493449    /// Its value type is inherited from the first node map type (\c IN).
    3450     /// \tparam IN The type of the node map for the in-nodes. 
     3450    /// \tparam IN The type of the node map for the in-nodes.
    34513451    /// \tparam OUT The type of the node map for the out-nodes.
    34523452    template <typename IN, typename OUT>

  • lemon/arg_parser.cc

    r463 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2121namespace lemon {
    2222
     23  void ArgParser::_terminate(ArgParserException::Reason reason) const
     24  {
     25    if(_exit_on_problems)
     26      exit(1);
     27    else throw(ArgParserException(reason));
     28  }
     29
     30
    2331  void ArgParser::_showHelp(void *p)
    2432  {
    2533    (static_cast<ArgParser*>(p))->showHelp();
    26     exit(1);
     34    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
    2735  }
    2836
    2937  ArgParser::ArgParser(int argc, const char * const *argv)
    30     :_argc(argc), _argv(argv), _command_name(argv[0]) {
     38    :_argc(argc), _argv(argv), _command_name(argv[0]),
     39    _exit_on_problems(true) {
    3140    funcOption("-help","Print a short help message",_showHelp,this);
    3241    synonym("help","-help");
    … …  
    343352        i!=_others_help.end();++i) showHelp(i);
    344353    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    345     exit(1);
     354    _terminate(ArgParserException::HELP);
    346355  }
    347356
    … …  
    352361    std::cerr << "\nType '" << _command_name <<
    353362      " --help' to obtain a short summary on the usage.\n\n";
    354     exit(1);
     363    _terminate(ArgParserException::UNKNOWN_OPT);
    355364  }
    356365
    … …  
    415424      std::cerr << "\nType '" << _command_name <<
    416425        " --help' to obtain a short summary on the usage.\n\n";
    417       exit(1);
     426      _terminate(ArgParserException::INVALID_OPT);
    418427    }
    419428  }

  • lemon/arg_parser.h

    r463 r959  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3535namespace lemon {
    3636
     37  ///Exception used by ArgParser
     38
     39  ///Exception used by ArgParser.
     40  ///
     41  class ArgParserException : public Exception {
     42  public:
     43    /// Reasons for failure
     44
     45    /// Reasons for failure.
     46    ///
     47    enum Reason {
     48      HELP,         ///< <tt>--help</tt> option was given.
     49      UNKNOWN_OPT,  ///< Unknown option was given.
     50      INVALID_OPT   ///< Invalid combination of options.
     51    };
     52
     53  private:
     54    Reason _reason;
     55
     56  public:
     57    ///Constructor
     58    ArgParserException(Reason r) throw() : _reason(r) {}
     59    ///Virtual destructor
     60    virtual ~ArgParserException() throw() {}
     61    ///A short description of the exception
     62    virtual const char* what() const throw() {
     63      switch(_reason)
     64        {
     65        case HELP:
     66          return "lemon::ArgParseException: ask for help";
     67          break;
     68        case UNKNOWN_OPT:
     69          return "lemon::ArgParseException: unknown option";
     70          break;
     71        case INVALID_OPT:
     72          return "lemon::ArgParseException: invalid combination of options";
     73          break;
     74        }
     75      return "";
     76    }
     77    ///Return the reason for the failure
     78    Reason reason() const {return _reason; }
     79  };
     80
     81
    3782  ///Command line arguments parser
    3883
    … …  
    116161                    const std::string &help,
    117162                    void (*func)(void *),void *data);
     163
     164    bool _exit_on_problems;
     165
     166    void _terminate(ArgParserException::Reason reason) const;
    118167
    119168  public:
    … …  
    381430    const std::vector<std::string> &files() const { return _file_args; }
    382431
     432    ///Throw instead of exit in case of problems
     433    void throwOnProblems()
     434    {
     435      _exit_on_problems=false;
     436    }
    383437  };
    384438}

  • lemon/bellman_ford.h

    r958 r960  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3636
    3737  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    38   /// 
     38  ///
    3939  /// This operation traits class defines all computational operations
    4040  /// and constants that are used in the Bellman-Ford algorithm.
    … …  
    4343  /// value is used as extremal infinity value.
    4444  template <
    45     typename V, 
     45    typename V,
    4646    bool has_inf = std::numeric_limits<V>::has_infinity>
    4747  struct BellmanFordDefaultOperationTraits {
    … …  
    8484    }
    8585  };
    86  
     86
    8787  /// \brief Default traits class of BellmanFord class.
    8888  ///
    … …  
    9292  template<typename GR, typename LEN>
    9393  struct BellmanFordDefaultTraits {
    94     /// The type of the digraph the algorithm runs on. 
     94    /// The type of the digraph the algorithm runs on.
    9595    typedef GR Digraph;
    9696
    … …  
    110110    /// \see BellmanFordDefaultOperationTraits
    111111    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    112  
    113     /// \brief The type of the map that stores the last arcs of the 
     112
     113    /// \brief The type of the map that stores the last arcs of the
    114114    /// shortest paths.
    115     /// 
     115    ///
    116116    /// The type of the map that stores the last
    117117    /// arcs of the shortest paths.
    … …  
    120120
    121121    /// \brief Instantiates a \c PredMap.
    122     /// 
    123     /// This function instantiates a \ref PredMap. 
     122    ///
     123    /// This function instantiates a \ref PredMap.
    124124    /// \param g is the digraph to which we would like to define the
    125125    /// \ref PredMap.
    … …  
    136136    /// \brief Instantiates a \c DistMap.
    137137    ///
    138     /// This function instantiates a \ref DistMap. 
    139     /// \param g is the digraph to which we would like to define the 
     138    /// This function instantiates a \ref DistMap.
     139    /// \param g is the digraph to which we would like to define the
    140140    /// \ref DistMap.
    141141    static DistMap *createDistMap(const GR& g) {
    … …  
    144144
    145145  };
    146  
     146
    147147  /// \brief %BellmanFord algorithm class.
    148148  ///
    149149  /// \ingroup shortest_path
    150   /// This class provides an efficient implementation of the Bellman-Ford 
     150  /// This class provides an efficient implementation of the Bellman-Ford
    151151  /// algorithm. The maximum time complexity of the algorithm is
    152152  /// <tt>O(ne)</tt>.
    … …  
    159159  ///
    160160  /// The arc lengths are passed to the algorithm using a
    161   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     161  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    162162  /// kind of length. The type of the length values is determined by the
    163163  /// \ref concepts::ReadMap::Value "Value" type of the length map.
    … …  
    189189    ///The type of the underlying digraph.
    190190    typedef typename TR::Digraph Digraph;
    191    
     191
    192192    /// \brief The type of the arc lengths.
    193193    typedef typename TR::LengthMap::Value Value;
    … …  
    236236    void create_maps() {
    237237      if(!_pred) {
    238         _local_pred = true;
    239         _pred = Traits::createPredMap(*_gr);
     238        _local_pred = true;
     239        _pred = Traits::createPredMap(*_gr);
    240240      }
    241241      if(!_dist) {
    242         _local_dist = true;
    243         _dist = Traits::createDistMap(*_gr);
     242        _local_dist = true;
     243        _dist = Traits::createDistMap(*_gr);
    244244      }
    245245      if(!_mask) {
    … …  
    247247      }
    248248    }
    249    
     249
    250250  public :
    251  
     251
    252252    typedef BellmanFord Create;
    253253
    … …  
    272272    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    273273    template <class T>
    274     struct SetPredMap 
     274    struct SetPredMap
    275275      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
    276276      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
    277277    };
    278    
     278
    279279    template <class T>
    280280    struct SetDistMapTraits : public Traits {
    … …  
    293293    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    294294    template <class T>
    295     struct SetDistMap 
     295    struct SetDistMap
    296296      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
    297297      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
    … …  
    302302      typedef T OperationTraits;
    303303    };
    304    
    305     /// \brief \ref named-templ-param "Named parameter" for setting 
     304
     305    /// \brief \ref named-templ-param "Named parameter" for setting
    306306    /// \c OperationTraits type.
    307307    ///
    … …  
    315315      Create;
    316316    };
    317    
     317
    318318    ///@}
    319319
    320320  protected:
    321    
     321
    322322    BellmanFord() {}
    323323
    324   public:     
    325    
     324  public:
     325
    326326    /// \brief Constructor.
    327327    ///
    … …  
    333333      _pred(0), _local_pred(false),
    334334      _dist(0), _local_dist(false), _mask(0) {}
    335    
     335
    336336    ///Destructor.
    337337    ~BellmanFord() {
    … …  
    360360    BellmanFord &predMap(PredMap &map) {
    361361      if(_local_pred) {
    362         delete _pred;
    363         _local_pred=false;
     362        delete _pred;
     363        _local_pred=false;
    364364      }
    365365      _pred = &map;
    … …  
    378378    BellmanFord &distMap(DistMap &map) {
    379379      if(_local_dist) {
    380         delete _dist;
    381         _local_dist=false;
     380        delete _dist;
     381        _local_dist=false;
    382382      }
    383383      _dist = &map;
    … …  
    397397
    398398    /// \brief Initializes the internal data structures.
    399     /// 
     399    ///
    400400    /// Initializes the internal data structures. The optional parameter
    401401    /// is the initial distance of each node.
    … …  
    403403      create_maps();
    404404      for (NodeIt it(*_gr); it != INVALID; ++it) {
    405         _pred->set(it, INVALID);
    406         _dist->set(it, value);
     405        _pred->set(it, INVALID);
     406        _dist->set(it, value);
    407407      }
    408408      _process.clear();
    409409      if (OperationTraits::less(value, OperationTraits::infinity())) {
    410         for (NodeIt it(*_gr); it != INVALID; ++it) {
    411           _process.push_back(it);
    412           _mask->set(it, true);
    413         }
     410        for (NodeIt it(*_gr); it != INVALID; ++it) {
     411          _process.push_back(it);
     412          _mask->set(it, true);
     413        }
    414414      } else {
    415         for (NodeIt it(*_gr); it != INVALID; ++it) {
    416           _mask->set(it, false);
    417         }
    418       }
    419     }
    420    
     415        for (NodeIt it(*_gr); it != INVALID; ++it) {
     416          _mask->set(it, false);
     417        }
     418      }
     419    }
     420
    421421    /// \brief Adds a new source node.
    422422    ///
    … …  
    426426      _dist->set(source, dst);
    427427      if (!(*_mask)[source]) {
    428         _process.push_back(source);
    429         _mask->set(source, true);
     428        _process.push_back(source);
     429        _mask->set(source, true);
    430430      }
    431431    }
    … …  
    452452    bool processNextRound() {
    453453      for (int i = 0; i < int(_process.size()); ++i) {
    454         _mask->set(_process[i], false);
     454        _mask->set(_process[i], false);
    455455      }
    456456      std::vector<Node> nextProcess;
    457457      std::vector<Value> values(_process.size());
    458458      for (int i = 0; i < int(_process.size()); ++i) {
    459         values[i] = (*_dist)[_process[i]];
     459        values[i] = (*_dist)[_process[i]];
    460460      }
    461461      for (int i = 0; i < int(_process.size()); ++i) {
    462         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    463           Node target = _gr->target(it);
    464           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
    465           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    466             _pred->set(target, it);
    467             _dist->set(target, relaxed);
    468             if (!(*_mask)[target]) {
    469               _mask->set(target, true);
    470               nextProcess.push_back(target);
    471             }
    472           }       
    473         }
     462        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     463          Node target = _gr->target(it);
     464          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
     465          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     466            _pred->set(target, it);
     467            _dist->set(target, relaxed);
     468            if (!(*_mask)[target]) {
     469              _mask->set(target, true);
     470              nextProcess.push_back(target);
     471            }
     472          }
     473        }
    474474      }
    475475      _process.swap(nextProcess);
    … …  
    493493    bool processNextWeakRound() {
    494494      for (int i = 0; i < int(_process.size()); ++i) {
    495         _mask->set(_process[i], false);
     495        _mask->set(_process[i], false);
    496496      }
    497497      std::vector<Node> nextProcess;
    498498      for (int i = 0; i < int(_process.size()); ++i) {
    499         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    500           Node target = _gr->target(it);
    501           Value relaxed =
    502             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
    503           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    504             _pred->set(target, it);
    505             _dist->set(target, relaxed);
    506             if (!(*_mask)[target]) {
    507               _mask->set(target, true);
    508               nextProcess.push_back(target);
    509             }
    510           }       
    511         }
     499        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     500          Node target = _gr->target(it);
     501          Value relaxed =
     502            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
     503          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     504            _pred->set(target, it);
     505            _dist->set(target, relaxed);
     506            if (!(*_mask)[target]) {
     507              _mask->set(target, true);
     508              nextProcess.push_back(target);
     509            }
     510          }
     511        }
    512512      }
    513513      _process.swap(nextProcess);
    … …  
    531531      int num = countNodes(*_gr) - 1;
    532532      for (int i = 0; i < num; ++i) {
    533         if (processNextWeakRound()) break;
     533        if (processNextWeakRound()) break;
    534534      }
    535535    }
    … …  
    543543    /// if the digraph contains cycles with negative total length.
    544544    ///
    545     /// The algorithm computes 
     545    /// The algorithm computes
    546546    /// - the shortest path tree (forest),
    547547    /// - the distance of each node from the root(s).
    548     /// 
     548    ///
    549549    /// \return \c false if there is a negative cycle in the digraph.
    550550    ///
    551551    /// \pre init() must be called and at least one root node should be
    552     /// added with addSource() before using this function. 
     552    /// added with addSource() before using this function.
    553553    bool checkedStart() {
    554554      int num = countNodes(*_gr);
    555555      for (int i = 0; i < num; ++i) {
    556         if (processNextWeakRound()) return true;
     556        if (processNextWeakRound()) return true;
    557557      }
    558558      return _process.empty();
    … …  
    578578    ///
    579579    /// \pre init() must be called and at least one root node should be
    580     /// added with addSource() before using this function. 
     580    /// added with addSource() before using this function.
    581581    void limitedStart(int num) {
    582582      for (int i = 0; i < num; ++i) {
    583         if (processNextRound()) break;
    584       }
    585     }
    586    
     583        if (processNextRound()) break;
     584      }
     585    }
     586
    587587    /// \brief Runs the algorithm from the given root node.
    588     ///   
     588    ///
    589589    /// This method runs the Bellman-Ford algorithm from the given root
    590590    /// node \c s in order to compute the shortest path to each node.
    … …  
    605605      start();
    606606    }
    607    
     607
    608608    /// \brief Runs the algorithm from the given root node with arc
    609609    /// number limit.
    610     ///   
     610    ///
    611611    /// This method runs the Bellman-Ford algorithm from the given root
    612612    /// node \c s in order to compute the shortest path distance for each
    … …  
    634634      limitedStart(num);
    635635    }
    636    
     636
    637637    ///@}
    638638
    … …  
    649649      ///
    650650      /// Constructor for getting the active nodes of the given BellmanFord
    651       /// instance. 
     651      /// instance.
    652652      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    653653      {
    … …  
    663663      ///
    664664      /// Conversion to \c Node.
    665       operator Node() const { 
     665      operator Node() const {
    666666        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
    667667      }
    … …  
    672672      ActiveIt& operator++() {
    673673        --_index;
    674         return *this; 
    675       }
    676 
    677       bool operator==(const ActiveIt& it) const { 
    678         return static_cast<Node>(*this) == static_cast<Node>(it); 
    679       }
    680       bool operator!=(const ActiveIt& it) const { 
    681         return static_cast<Node>(*this) != static_cast<Node>(it); 
    682       }
    683       bool operator<(const ActiveIt& it) const { 
    684         return static_cast<Node>(*this) < static_cast<Node>(it); 
    685       }
    686      
     674        return *this;
     675      }
     676
     677      bool operator==(const ActiveIt& it) const {
     678        return static_cast<Node>(*this) == static_cast<Node>(it);
     679      }
     680      bool operator!=(const ActiveIt& it) const {
     681        return static_cast<Node>(*this) != static_cast<Node>(it);
     682      }
     683      bool operator<(const ActiveIt& it) const {
     684        return static_cast<Node>(*this) < static_cast<Node>(it);
     685      }
     686
    687687    private:
    688688      const BellmanFord* _algorithm;
    689689      int _index;
    690690    };
    691    
     691
    692692    /// \name Query Functions
    693693    /// The result of the Bellman-Ford algorithm can be obtained using these
    694694    /// functions.\n
    695695    /// Either \ref run() or \ref init() should be called before using them.
    696    
     696
    697697    ///@{
    698698
    699699    /// \brief The shortest path to the given node.
    700     ///   
     700    ///
    701701    /// Gives back the shortest path to the given node from the root(s).
    702702    ///
    … …  
    709709      return Path(*_gr, *_pred, t);
    710710    }
    711          
     711
    712712    /// \brief The distance of the given node from the root(s).
    713713    ///
    … …  
    749749    /// \pre Either \ref run() or \ref init() must be called before
    750750    /// using this function.
    751     Node predNode(Node v) const { 
    752       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
    753     }
    754    
     751    Node predNode(Node v) const {
     752      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
     753    }
     754
    755755    /// \brief Returns a const reference to the node map that stores the
    756756    /// distances of the nodes.
    … …  
    762762    /// using this function.
    763763    const DistMap &distMap() const { return *_dist;}
    764  
     764
    765765    /// \brief Returns a const reference to the node map that stores the
    766766    /// predecessor arcs.
    … …  
    772772    /// using this function.
    773773    const PredMap &predMap() const { return *_pred; }
    774  
     774
    775775    /// \brief Checks if a node is reached from the root(s).
    776776    ///
    … …  
    784784
    785785    /// \brief Gives back a negative cycle.
    786     ///   
     786    ///
    787787    /// This function gives back a directed cycle with negative total
    788788    /// length if the algorithm has already found one.
    … …  
    811811      return cycle;
    812812    }
    813    
     813
    814814    ///@}
    815815  };
    816  
     816
    817817  /// \brief Default traits class of bellmanFord() function.
    818818  ///
    … …  
    822822  template <typename GR, typename LEN>
    823823  struct BellmanFordWizardDefaultTraits {
    824     /// The type of the digraph the algorithm runs on. 
     824    /// The type of the digraph the algorithm runs on.
    825825    typedef GR Digraph;
    826826
    … …  
    843843    /// \brief The type of the map that stores the last
    844844    /// arcs of the shortest paths.
    845     /// 
     845    ///
    846846    /// The type of the map that stores the last arcs of the shortest paths.
    847847    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    849849
    850850    /// \brief Instantiates a \c PredMap.
    851     /// 
     851    ///
    852852    /// This function instantiates a \ref PredMap.
    853853    /// \param g is the digraph to which we would like to define the
    … …  
    865865    /// \brief Instantiates a \c DistMap.
    866866    ///
    867     /// This function instantiates a \ref DistMap. 
     867    /// This function instantiates a \ref DistMap.
    868868    /// \param g is the digraph to which we would like to define the
    869869    /// \ref DistMap.
    … …  
    878878    typedef lemon::Path<Digraph> Path;
    879879  };
    880  
     880
    881881  /// \brief Default traits class used by BellmanFordWizard.
    882882  ///
    … …  
    885885  /// \tparam LEN The type of the length map.
    886886  template <typename GR, typename LEN>
    887   class BellmanFordWizardBase 
     887  class BellmanFordWizardBase
    888888    : public BellmanFordWizardDefaultTraits<GR, LEN> {
    889889
    … …  
    908908    public:
    909909    /// Constructor.
    910    
     910
    911911    /// This constructor does not require parameters, it initiates
    912912    /// all of the attributes to default values \c 0.
    … …  
    915915
    916916    /// Constructor.
    917    
     917
    918918    /// This constructor requires two parameters,
    919919    /// others are initiated to \c 0.
    920920    /// \param gr The digraph the algorithm runs on.
    921921    /// \param len The length map.
    922     BellmanFordWizardBase(const GR& gr, 
    923                           const LEN& len) :
    924       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
    925       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
     922    BellmanFordWizardBase(const GR& gr,
     923                          const LEN& len) :
     924      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
     925      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
    926926      _pred(0), _dist(0), _path(0), _di(0) {}
    927927
    928928  };
    929  
     929
    930930  /// \brief Auxiliary class for the function-type interface of the
    931931  /// \ref BellmanFord "Bellman-Ford" algorithm.
    … …  
    952952    typedef typename Digraph::Arc Arc;
    953953    typedef typename Digraph::OutArcIt ArcIt;
    954    
     954
    955955    typedef typename TR::LengthMap LengthMap;
    956956    typedef typename LengthMap::Value Value;
    … …  
    969969    /// \param gr The digraph the algorithm runs on.
    970970    /// \param len The length map.
    971     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
     971    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
    972972      : TR(gr, len) {}
    973973
    … …  
    978978
    979979    /// \brief Runs the Bellman-Ford algorithm from the given source node.
    980     ///   
     980    ///
    981981    /// This method runs the Bellman-Ford algorithm from the given source
    982982    /// node in order to compute the shortest path to each node.
    983983    void run(Node s) {
    984       BellmanFord<Digraph,LengthMap,TR> 
    985         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
     984      BellmanFord<Digraph,LengthMap,TR>
     985        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
    986986           *reinterpret_cast<const LengthMap*>(Base::_length));
    987987      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    … …  
    10181018      SetPredMapBase(const TR &b) : TR(b) {}
    10191019    };
    1020    
     1020
    10211021    /// \brief \ref named-templ-param "Named parameter" for setting
    10221022    /// the predecessor map.
    … …  
    10291029      return BellmanFordWizard<SetPredMapBase<T> >(*this);
    10301030    }
    1031    
     1031
    10321032    template<class T>
    10331033    struct SetDistMapBase : public Base {
    … …  
    10361036      SetDistMapBase(const TR &b) : TR(b) {}
    10371037    };
    1038    
     1038
    10391039    /// \brief \ref named-templ-param "Named parameter" for setting
    10401040    /// the distance map.
    … …  
    10771077      return *this;
    10781078    }
    1079    
     1079
    10801080  };
    1081  
     1081
    10821082  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
    10831083  /// algorithm.
    … …  
    10871087  /// algorithm.
    10881088  ///
    1089   /// This function also has several \ref named-templ-func-param 
    1090   /// "named parameters", they are declared as the members of class 
     1089  /// This function also has several \ref named-templ-func-param
     1090  /// "named parameters", they are declared as the members of class
    10911091  /// \ref BellmanFordWizard.
    10921092  /// The following examples show how to use these parameters.
    … …  
    11051105  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
    11061106  bellmanFord(const GR& digraph,
    1107               const LEN& length)
     1107              const LEN& length)
    11081108  {
    11091109    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);

  • lemon/bfs.h

    r891 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    8383
    8484    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8687    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8788    ///Instantiates a \c ReachedMap.
    … …  
    272273    ///\ref named-templ-param "Named parameter" for setting
    273274    ///\c ReachedMap type.
    274     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    275277    template <class T>
    276278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    873875
    874876    ///The type of the map that indicates which nodes are reached.
    875     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    876879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    877880    ///Instantiates a ReachedMap.
    … …  
    12661269    ///
    12671270    /// The type of the map that indicates which nodes are reached.
    1268     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1271    /// It must conform to
     1272    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12691273    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12701274

  • lemon/bits/array_map.h

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

  • lemon/bits/default_map.h

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

    r732 r956  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    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();
    … …  
    311311    Node oppositeNode(const Node &n, const Edge &e) const {
    312312      if( n == Parent::u(e))
    313         return Parent::v(e);
     313        return Parent::v(e);
    314314      else if( n == Parent::v(e))
    315         return Parent::u(e);
     315        return Parent::u(e);
    316316      else
    317         return INVALID;
     317        return INVALID;
    318318    }
    319319
    … …  
    339339
    340340    using Parent::notifier;
    341    
     341
    342342    ArcNotifier& notifier(Arc) const {
    343343      return arc_notifier;
    … …  
    349349
    350350
    351     class NodeIt : public Node { 
     351    class NodeIt : public Node {
    352352      const Graph* graph;
    353353    public:
    … …  
    358358
    359359      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    360         _graph.first(static_cast<Node&>(*this));
    361       }
    362 
    363       NodeIt(const Graph& _graph, const Node& node) 
    364         : Node(node), graph(&_graph) {}
    365 
    366       NodeIt& operator++() { 
    367         graph->next(*this);
    368         return *this;
    369       }
    370 
    371     };
    372 
    373 
    374     class ArcIt : public Arc { 
     360        _graph.first(static_cast<Node&>(*this));
     361      }
     362
     363      NodeIt(const Graph& _graph, const Node& node)
     364        : Node(node), graph(&_graph) {}
     365
     366      NodeIt& operator++() {
     367        graph->next(*this);
     368        return *this;
     369      }
     370
     371    };
     372
     373
     374    class ArcIt : public Arc {
    375375      const Graph* graph;
    376376    public:
    … …  
    381381
    382382      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    383         _graph.first(static_cast<Arc&>(*this));
    384       }
    385 
    386       ArcIt(const Graph& _graph, const Arc& e) : 
    387         Arc(e), graph(&_graph) { }
    388 
    389       ArcIt& operator++() { 
    390         graph->next(*this);
    391         return *this;
    392       }
    393 
    394     };
    395 
    396 
    397     class OutArcIt : public Arc { 
     383        _graph.first(static_cast<Arc&>(*this));
     384      }
     385
     386      ArcIt(const Graph& _graph, const Arc& e) :
     387        Arc(e), graph(&_graph) { }
     388
     389      ArcIt& operator++() {
     390        graph->next(*this);
     391        return *this;
     392      }
     393
     394    };
     395
     396
     397    class OutArcIt : public Arc {
    398398      const Graph* graph;
    399399    public:
    … …  
    403403      OutArcIt(Invalid i) : Arc(i) { }
    404404
    405       OutArcIt(const Graph& _graph, const Node& node) 
    406         : graph(&_graph) {
    407         _graph.firstOut(*this, node);
    408       }
    409 
    410       OutArcIt(const Graph& _graph, const Arc& arc) 
    411         : Arc(arc), graph(&_graph) {}
    412 
    413       OutArcIt& operator++() { 
    414         graph->nextOut(*this);
    415         return *this;
    416       }
    417 
    418     };
    419 
    420 
    421     class InArcIt : public Arc { 
     405      OutArcIt(const Graph& _graph, const Node& node)
     406        : graph(&_graph) {
     407        _graph.firstOut(*this, node);
     408      }
     409
     410      OutArcIt(const Graph& _graph, const Arc& arc)
     411        : Arc(arc), graph(&_graph) {}
     412
     413      OutArcIt& operator++() {
     414        graph->nextOut(*this);
     415        return *this;
     416      }
     417
     418    };
     419
     420
     421    class InArcIt : public Arc {
    422422      const Graph* graph;
    423423    public:
    … …  
    427427      InArcIt(Invalid i) : Arc(i) { }
    428428
    429       InArcIt(const Graph& _graph, const Node& node) 
    430         : graph(&_graph) {
    431         _graph.firstIn(*this, node);
    432       }
    433 
    434       InArcIt(const Graph& _graph, const Arc& arc) : 
    435         Arc(arc), graph(&_graph) {}
    436 
    437       InArcIt& operator++() { 
    438         graph->nextIn(*this);
    439         return *this;
    440       }
    441 
    442     };
    443 
    444 
    445     class EdgeIt : public Parent::Edge { 
     429      InArcIt(const Graph& _graph, const Node& node)
     430        : graph(&_graph) {
     431        _graph.firstIn(*this, node);
     432      }
     433
     434      InArcIt(const Graph& _graph, const Arc& arc) :
     435        Arc(arc), graph(&_graph) {}
     436
     437      InArcIt& operator++() {
     438        graph->nextIn(*this);
     439        return *this;
     440      }
     441
     442    };
     443
     444
     445    class EdgeIt : public Parent::Edge {
    446446      const Graph* graph;
    447447    public:
    … …  
    452452
    453453      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    454         _graph.first(static_cast<Edge&>(*this));
    455       }
    456 
    457       EdgeIt(const Graph& _graph, const Edge& e) : 
    458         Edge(e), graph(&_graph) { }
    459 
    460       EdgeIt& operator++() { 
    461         graph->next(*this);
    462         return *this;
     454        _graph.first(static_cast<Edge&>(*this));
     455      }
     456
     457      EdgeIt(const Graph& _graph, const Edge& e) :
     458        Edge(e), graph(&_graph) { }
     459
     460      EdgeIt& operator++() {
     461        graph->next(*this);
     462        return *this;
    463463      }
    464464
    … …  
    476476
    477477      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    478         _graph.firstInc(*this, direction, n);
     478        _graph.firstInc(*this, direction, n);
    479479      }
    480480
    481481      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    482         : graph(&_graph), Edge(ue) {
    483         direction = (_graph.source(ue) == n);
     482        : graph(&_graph), Edge(ue) {
     483        direction = (_graph.source(ue) == n);
    484484      }
    485485
    486486      IncEdgeIt& operator++() {
    487         graph->nextInc(*this, direction);
    488         return *this;
     487        graph->nextInc(*this, direction);
     488        return *this;
    489489      }
    490490    };
    … …  
    533533
    534534    template <typename _Value>
    535     class ArcMap 
     535    class ArcMap
    536536      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    537537      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    538538
    539539    public:
    540       explicit ArcMap(const Graph& _g) 
    541         : Parent(_g) {}
    542       ArcMap(const Graph& _g, const _Value& _v) 
    543         : Parent(_g, _v) {}
     540      explicit ArcMap(const Graph& _g)
     541        : Parent(_g) {}
     542      ArcMap(const Graph& _g, const _Value& _v)
     543        : Parent(_g, _v) {}
    544544
    545545      ArcMap& operator=(const ArcMap& cmap) {
    546         return operator=<ArcMap>(cmap);
     546        return operator=<ArcMap>(cmap);
    547547      }
    548548
    … …  
    550550      ArcMap& operator=(const CMap& cmap) {
    551551        Parent::operator=(cmap);
    552         return *this;
     552        return *this;
    553553      }
    554554
    … …  
    557557
    558558    template <typename _Value>
    559     class EdgeMap 
     559    class EdgeMap
    560560      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    561561      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    562562
    563563    public:
    564       explicit EdgeMap(const Graph& _g) 
    565         : Parent(_g) {}
    566 
    567       EdgeMap(const Graph& _g, const _Value& _v) 
    568         : Parent(_g, _v) {}
     564      explicit EdgeMap(const Graph& _g)
     565        : Parent(_g) {}
     566
     567      EdgeMap(const Graph& _g, const _Value& _v)
     568        : Parent(_g, _v) {}
    569569
    570570      EdgeMap& operator=(const EdgeMap& cmap) {
    571         return operator=<EdgeMap>(cmap);
     571        return operator=<EdgeMap>(cmap);
    572572      }
    573573
    … …  
    575575      EdgeMap& operator=(const CMap& cmap) {
    576576        Parent::operator=(cmap);
    577         return *this;
     577        return *this;
    578578      }
    579579
    … …  
    592592      return edge;
    593593    }
    594    
     594
    595595    void clear() {
    596596      notifier(Arc()).clear();
    … …  
    618618      arc_notifier.clear();
    619619    }
    620    
     620
    621621  };
    622622

  • lemon/bits/solver_bits.h

    r566 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/bits/windows.cc

    r513 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    9797      GetSystemTime(&time);
    9898      char buf1[11], buf2[9], buf3[5];
    99           if (GetDateFormat(MY_LOCALE, 0, &time,
     99          if (GetDateFormat(MY_LOCALE, 0, &time,
    100100                        ("ddd MMM dd"), buf1, 11) &&
    101101          GetTimeFormat(MY_LOCALE, 0, &time,

  • lemon/bucket_heap.h

    r758 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    385385  ///
    386386  /// Note that this implementation does not conform to the
    387   /// \ref concepts::Heap "heap concept" due to the lack of some 
     387  /// \ref concepts::Heap "heap concept" due to the lack of some
    388388  /// functionality.
    389389  ///

  • lemon/capacity_scaling.h

    r899 r956  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    134134      UNBOUNDED
    135135    };
    136  
     136
    137137  private:
    138138
    … …  
    140140
    141141    typedef std::vector<int> IntVector;
    142     typedef std::vector<char> BoolVector;
    143142    typedef std::vector<Value> ValueVector;
    144143    typedef std::vector<Cost> CostVector;
     144    typedef std::vector<char> BoolVector;
     145    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    145146
    146147  private:
    … …  
    184185
    185186  public:
    186  
     187
    187188    /// \brief Constant for infinite upper bounds (capacities).
    188189    ///
    … …  
    211212      CostVector &_pi;
    212213      IntVector &_pred;
    213      
     214
    214215      IntVector _proc_nodes;
    215216      CostVector _dist;
    216      
     217
    217218    public:
    218219
    … …  
    301302    /// @}
    302303
     304  protected:
     305
     306    CapacityScaling() {}
     307
    303308  public:
    304309
    … …  
    435440      return *this;
    436441    }
    437    
     442
    438443    /// @}
    439444
    … …  
    571576      _cost.resize(_res_arc_num);
    572577      _supply.resize(_node_num);
    573      
     578
    574579      _res_cap.resize(_res_arc_num);
    575580      _pi.resize(_node_num);
    … …  
    615620        _reverse[bi] = fi;
    616621      }
    617      
     622
    618623      // Reset parameters
    619624      resetParams();
    … …  
    724729      }
    725730      if (_sum_supply > 0) return INFEASIBLE;
    726      
     731
    727732      // Initialize vectors
    728733      for (int i = 0; i != _root; ++i) {
    … …  
    772777        }
    773778      }
    774      
     779
    775780      // Handle GEQ supply type
    776781      if (_sum_supply < 0) {
    … …  
    799804      if (_factor > 1) {
    800805        // With scaling
    801         Value max_sup = 0, max_dem = 0;
    802         for (int i = 0; i != _node_num; ++i) {
     806        Value max_sup = 0, max_dem = 0, max_cap = 0;
     807        for (int i = 0; i != _root; ++i) {
    803808          Value ex = _excess[i];
    804809          if ( ex > max_sup) max_sup =  ex;
    805810          if (-ex > max_dem) max_dem = -ex;
    806         }
    807         Value max_cap = 0;
    808         for (int j = 0; j != _res_arc_num; ++j) {
    809           if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     811          int last_out = _first_out[i+1] - 1;
     812          for (int j = _first_out[i]; j != last_out; ++j) {
     813            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
     814          }
    810815        }
    811816        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
    … …  
    840845        for (int i = 0; i != _node_num; ++i) {
    841846          _pi[i] -= pr;
    842         }       
    843       }
    844      
     847        }
     848      }
     849
    845850      return pt;
    846851    }

  • lemon/cbc.h

    r793 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    122122    int _message_level;
    123123
    124    
     124
    125125
    126126  };

  • lemon/circulation.h

    r891 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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;
    … …  
    142142     \geq sup(u) \quad \forall u\in V, \f]
    143143     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    144      
     144
    145145     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    146146     zero or negative in order to have a feasible solution (since the sum
    … …  
    152152     constraints have to be satisfied with equality, i.e. all demands
    153153     have to be satisfied and all supplies have to be used.
    154      
     154
    155155     If you need the opposite inequalities in the supply/demand constraints
    156156     (i.e. the total demand is less than the total supply and all the demands
    … …  
    338338    /// \param graph The digraph the algorithm runs on.
    339339    /// \param lower The lower bounds for the flow values on the arcs.
    340     /// \param upper The upper bounds (capacities) for the flow values 
     340    /// \param upper The upper bounds (capacities) for the flow values
    341341    /// on the arcs.
    342342    /// \param supply The signed supply values of the nodes.

  • lemon/clp.cc

    r793 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/clp.h

    r793 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    139139
    140140    virtual void _messageLevel(MessageLevel);
    141    
     141
    142142  public:
    143143

  • lemon/concepts/digraph.h

    r833 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    435435      private:
    436436        ///Copy constructor
    437         NodeMap(const NodeMap& nm) : 
     437        NodeMap(const NodeMap& nm) :
    438438          ReferenceMap<Node, T, T&, const T&>(nm) { }
    439439        ///Assignment operator

  • lemon/concepts/graph.h

    r833 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4444    /// run properly, of course.
    4545    /// An actual graph implementation like \ref ListGraph or
    46     /// \ref SmartGraph may have additional functionality.   
     46    /// \ref SmartGraph may have additional functionality.
    4747    ///
    4848    /// The undirected graphs also fulfill the concept of \ref Digraph
    … …  
    8686      ///
    8787      /// Undirected graphs should be tagged with \c UndirectedTag.
    88       /// 
     88      ///
    8989      /// This tag helps the \c enable_if technics to make compile time
    9090      /// specializations for undirected graphs.
    … …  
    361361
    362362        /// Converison to \c Edge
    363        
     363
    364364        /// Converison to \c Edge.
    365365        ///

  • lemon/concepts/graph_components.h

    r833 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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/heap.h

    r883 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    9393#else
    9494      explicit Heap(ItemIntMap&) {}
    95 #endif     
     95#endif
    9696
    9797      /// \brief Constructor.
    … …  
    107107#else
    108108      explicit Heap(ItemIntMap&, const CMP&) {}
    109 #endif     
     109#endif
    110110
    111111      /// \brief The number of items stored in the heap.
    … …  
    139139#else
    140140      void push(const Item&, const Prio&) {}
    141 #endif     
     141#endif
    142142
    143143      /// \brief Return the item having minimum priority.
    … …  
    169169#else
    170170      void erase(const Item&) {}
    171 #endif     
     171#endif
    172172
    173173      /// \brief The priority of the given item.
    … …  
    180180#else
    181181      Prio operator[](const Item&) const { return Prio(); }
    182 #endif     
     182#endif
    183183
    184184      /// \brief Set the priority of an item or insert it, if it is
    … …  
    195195#else
    196196      void set(const Item&, const Prio&) {}
    197 #endif     
     197#endif
    198198
    199199      /// \brief Decrease the priority of an item to the given value.
    … …  
    207207#else
    208208      void decrease(const Item&, const Prio&) {}
    209 #endif     
     209#endif
    210210
    211211      /// \brief Increase the priority of an item to the given value.
    … …  
    219219#else
    220220      void increase(const Item&, const Prio&) {}
    221 #endif     
     221#endif
    222222
    223223      /// \brief Return the state of an item.
    … …  
    233233#else
    234234      State state(const Item&) const { return PRE_HEAP; }
    235 #endif     
     235#endif
    236236
    237237      /// \brief Set the state of an item in the heap.
    … …  
    246246#else
    247247      void state(const Item&, State) {}
    248 #endif     
     248#endif
    249249
    250250

  • lemon/connectivity.h

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

    r718 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    12401240  protected:
    12411241
    1242     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1242    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1243    {
    12431244      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12441245
    … …  
    12791280    };
    12801281
    1281   protected: 
     1282  protected:
    12821283
    12831284    const Digraph &_g;

  • lemon/cost_scaling.h

    r899 r956  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    9494  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient. 
     95  /// \ref goldberg97efficient, \ref bunnagel98efficient.
    9696  /// It is a highly efficient primal-dual solution method, which
    9797  /// can be viewed as the generalization of the \ref Preflow
    … …  
    190190      /// paths from a node with excess to a node with deficit.
    191191      AUGMENT,
    192       /// Partial augment operations are used, i.e. flow is moved on 
     192      /// Partial augment operations are used, i.e. flow is moved on
    193193      /// admissible paths started from a node with excess, but the
    194194      /// lengths of these paths are limited. This method can be viewed
    … …  
    202202
    203203    typedef std::vector<int> IntVector;
    204     typedef std::vector<char> BoolVector;
    205204    typedef std::vector<Value> ValueVector;
    206205    typedef std::vector<Cost> CostVector;
    207206    typedef std::vector<LargeCost> LargeCostVector;
     207    typedef std::vector<char> BoolVector;
     208    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    208209
    209210  private:
    210  
     211
    211212    template <typename KT, typename VT>
    212213    class StaticVectorMap {
    … …  
    214215      typedef KT Key;
    215216      typedef VT Value;
    216      
     217
    217218      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
    218      
     219
    219220      const Value& operator[](const Key& key) const {
    220221        return _v[StaticDigraph::id(key)];
    … …  
    224225        return _v[StaticDigraph::id(key)];
    225226      }
    226      
     227
    227228      void set(const Key& key, const Value& val) {
    228229        _v[StaticDigraph::id(key)] = val;
    … …  
    249250    bool _have_lower;
    250251    Value _sum_supply;
     252    int _sup_node_num;
    251253
    252254    // Data structures for storing the digraph
    … …  
    277279    int _alpha;
    278280
     281    IntVector _buckets;
     282    IntVector _bucket_next;
     283    IntVector _bucket_prev;
     284    IntVector _rank;
     285    int _max_rank;
     286
    279287    // Data for a StaticDigraph structure
    280288    typedef std::pair<int, int> IntPair;
    … …  
    284292    LargeCostArcMap _cost_map;
    285293    LargeCostNodeMap _pi_map;
    286  
     294
    287295  public:
    288  
     296
    289297    /// \brief Constant for infinite upper bounds (capacities).
    290298    ///
    … …  
    317325
    318326    /// @}
     327
     328  protected:
     329
     330    CostScaling() {}
    319331
    320332  public:
    … …  
    337349      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    338350        "The cost type of CostScaling must be signed");
    339      
     351
    340352      // Reset data structures
    341353      reset();
    … …  
    453465      return *this;
    454466    }
    455    
     467
    456468    /// @}
    457469
    … …  
    555567        _scost[j] = 0;
    556568        _scost[_reverse[j]] = 0;
    557       }     
     569      }
    558570      _have_lower = false;
    559571      return *this;
    … …  
    590602      _scost.resize(_res_arc_num);
    591603      _supply.resize(_res_node_num);
    592      
     604
    593605      _res_cap.resize(_res_arc_num);
    594606      _cost.resize(_res_arc_num);
    … …  
    638650        _reverse[bi] = fi;
    639651      }
    640      
     652
    641653      // Reset parameters
    642654      resetParams();
    … …  
    747759      }
    748760      if (_sum_supply > 0) return INFEASIBLE;
    749      
     761
    750762
    751763      // Initialize vectors
    … …  
    754766        _excess[i] = _supply[i];
    755767      }
    756      
     768
    757769      // Remove infinite upper bounds and check negative arcs
    758770      const Value MAX = std::numeric_limits<Value>::max();
    … …  
    829841      }
    830842
     843      _sup_node_num = 0;
     844      for (NodeIt n(_graph); n != INVALID; ++n) {
     845        if (sup[n] > 0) ++_sup_node_num;
     846      }
     847
    831848      // Find a feasible flow using Circulation
    832849      Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>
    … …  
    863880        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
    864881          int ra = _reverse[a];
    865           _res_cap[a] = 1;
     882          _res_cap[a] = 0;
    866883          _res_cap[ra] = 0;
    867884          _cost[a] = 0;
    … …  
    869886        }
    870887      }
    871      
     888
    872889      return OPTIMAL;
    873890    }
    … …  
    877894      // Maximum path length for partial augment
    878895      const int MAX_PATH_LENGTH = 4;
    879      
     896
     897      // Initialize data structures for buckets
     898      _max_rank = _alpha * _res_node_num;
     899      _buckets.resize(_max_rank);
     900      _bucket_next.resize(_res_node_num + 1);
     901      _bucket_prev.resize(_res_node_num + 1);
     902      _rank.resize(_res_node_num + 1);
     903
    880904      // Execute the algorithm
    881905      switch (method) {
    … …  
    917941    }
    918942
     943    // Initialize a cost scaling phase
     944    void initPhase() {
     945      // Saturate arcs not satisfying the optimality condition
     946      for (int u = 0; u != _res_node_num; ++u) {
     947        int last_out = _first_out[u+1];
     948        LargeCost pi_u = _pi[u];
     949        for (int a = _first_out[u]; a != last_out; ++a) {
     950          int v = _target[a];
     951          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
     952            Value delta = _res_cap[a];
     953            _excess[u] -= delta;
     954            _excess[v] += delta;
     955            _res_cap[a] = 0;
     956            _res_cap[_reverse[a]] += delta;
     957          }
     958        }
     959      }
     960
     961      // Find active nodes (i.e. nodes with positive excess)
     962      for (int u = 0; u != _res_node_num; ++u) {
     963        if (_excess[u] > 0) _active_nodes.push_back(u);
     964      }
     965
     966      // Initialize the next arcs
     967      for (int u = 0; u != _res_node_num; ++u) {
     968        _next_out[u] = _first_out[u];
     969      }
     970    }
     971
     972    // Early termination heuristic
     973    bool earlyTermination() {
     974      const double EARLY_TERM_FACTOR = 3.0;
     975
     976      // Build a static residual graph
     977      _arc_vec.clear();
     978      _cost_vec.clear();
     979      for (int j = 0; j != _res_arc_num; ++j) {
     980        if (_res_cap[j] > 0) {
     981          _arc_vec.push_back(IntPair(_source[j], _target[j]));
     982          _cost_vec.push_back(_cost[j] + 1);
     983        }
     984      }
     985      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
     986
     987      // Run Bellman-Ford algorithm to check if the current flow is optimal
     988      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
     989      bf.init(0);
     990      bool done = false;
     991      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
     992      for (int i = 0; i < K && !done; ++i) {
     993        done = bf.processNextWeakRound();
     994      }
     995      return done;
     996    }
     997
     998    // Global potential update heuristic
     999    void globalUpdate() {
     1000      int bucket_end = _root + 1;
     1001
     1002      // Initialize buckets
     1003      for (int r = 0; r != _max_rank; ++r) {
     1004        _buckets[r] = bucket_end;
     1005      }
     1006      Value total_excess = 0;
     1007      for (int i = 0; i != _res_node_num; ++i) {
     1008        if (_excess[i] < 0) {
     1009          _rank[i] = 0;
     1010          _bucket_next[i] = _buckets[0];
     1011          _bucket_prev[_buckets[0]] = i;
     1012          _buckets[0] = i;
     1013        } else {
     1014          total_excess += _excess[i];
     1015          _rank[i] = _max_rank;
     1016        }
     1017      }
     1018      if (total_excess == 0) return;
     1019
     1020      // Search the buckets
     1021      int r = 0;
     1022      for ( ; r != _max_rank; ++r) {
     1023        while (_buckets[r] != bucket_end) {
     1024          // Remove the first node from the current bucket
     1025          int u = _buckets[r];
     1026          _buckets[r] = _bucket_next[u];
     1027
     1028          // Search the incomming arcs of u
     1029          LargeCost pi_u = _pi[u];
     1030          int last_out = _first_out[u+1];
     1031          for (int a = _first_out[u]; a != last_out; ++a) {
     1032            int ra = _reverse[a];
     1033            if (_res_cap[ra] > 0) {
     1034              int v = _source[ra];
     1035              int old_rank_v = _rank[v];
     1036              if (r < old_rank_v) {
     1037                // Compute the new rank of v
     1038                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
     1039                int new_rank_v = old_rank_v;
     1040                if (nrc < LargeCost(_max_rank))
     1041                  new_rank_v = r + 1 + int(nrc);
     1042
     1043                // Change the rank of v
     1044                if (new_rank_v < old_rank_v) {
     1045                  _rank[v] = new_rank_v;
     1046                  _next_out[v] = _first_out[v];
     1047
     1048                  // Remove v from its old bucket
     1049                  if (old_rank_v < _max_rank) {
     1050                    if (_buckets[old_rank_v] == v) {
     1051                      _buckets[old_rank_v] = _bucket_next[v];
     1052                    } else {
     1053                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
     1054                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1055                    }
     1056                  }
     1057
     1058                  // Insert v to its new bucket
     1059                  _bucket_next[v] = _buckets[new_rank_v];
     1060                  _bucket_prev[_buckets[new_rank_v]] = v;
     1061                  _buckets[new_rank_v] = v;
     1062                }
     1063              }
     1064            }
     1065          }
     1066
     1067          // Finish search if there are no more active nodes
     1068          if (_excess[u] > 0) {
     1069            total_excess -= _excess[u];
     1070            if (total_excess <= 0) break;
     1071          }
     1072        }
     1073        if (total_excess <= 0) break;
     1074      }
     1075
     1076      // Relabel nodes
     1077      for (int u = 0; u != _res_node_num; ++u) {
     1078        int k = std::min(_rank[u], r);
     1079        if (k > 0) {
     1080          _pi[u] -= _epsilon * k;
     1081          _next_out[u] = _first_out[u];
     1082        }
     1083      }
     1084    }
     1085
    9191086    /// Execute the algorithm performing augment and relabel operations
    9201087    void startAugment(int max_length = std::numeric_limits<int>::max()) {
    9211088      // Paramters for heuristics
    922       const int BF_HEURISTIC_EPSILON_BOUND = 1000;
    923       const int BF_HEURISTIC_BOUND_FACTOR  = 3;
     1089      const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1090      const double GLOBAL_UPDATE_FACTOR = 3.0;
     1091
     1092      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1093        (_res_node_num + _sup_node_num * _sup_node_num));
     1094      int next_update_limit = global_update_freq;
     1095
     1096      int relabel_cnt = 0;
    9241097
    9251098      // Perform cost scaling phases
    926       IntVector pred_arc(_res_node_num);
    927       std::vector<int> path_nodes;
     1099      std::vector<int> path;
    9281100      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    9291101                                        1 : _epsilon / _alpha )
    9301102      {
    931         // "Early Termination" heuristic: use Bellman-Ford algorithm
    932         // to check if the current flow is optimal
    933         if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
    934           _arc_vec.clear();
    935           _cost_vec.clear();
    936           for (int j = 0; j != _res_arc_num; ++j) {
    937             if (_res_cap[j] > 0) {
    938               _arc_vec.push_back(IntPair(_source[j], _target[j]));
    939               _cost_vec.push_back(_cost[j] + 1);
    940             }
    941           }
    942           _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    943 
    944           BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
    945           bf.init(0);
    946           bool done = false;
    947           int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
    948           for (int i = 0; i < K && !done; ++i)
    949             done = bf.processNextWeakRound();
    950           if (done) break;
    951         }
    952 
    953         // Saturate arcs not satisfying the optimality condition
    954         for (int a = 0; a != _res_arc_num; ++a) {
    955           if (_res_cap[a] > 0 &&
    956               _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
    957             Value delta = _res_cap[a];
    958             _excess[_source[a]] -= delta;
    959             _excess[_target[a]] += delta;
    960             _res_cap[a] = 0;
    961             _res_cap[_reverse[a]] += delta;
    962           }
    963         }
    964        
    965         // Find active nodes (i.e. nodes with positive excess)
    966         for (int u = 0; u != _res_node_num; ++u) {
    967           if (_excess[u] > 0) _active_nodes.push_back(u);
    968         }
    969 
    970         // Initialize the next arcs
    971         for (int u = 0; u != _res_node_num; ++u) {
    972           _next_out[u] = _first_out[u];
    973         }
     1103        // Early termination heuristic
     1104        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
     1105          if (earlyTermination()) break;
     1106        }
     1107
     1108        // Initialize current phase
     1109        initPhase();
    9741110
    9751111        // Perform partial augment and relabel operations
    … …  
    9821118          if (_active_nodes.size() == 0) break;
    9831119          int start = _active_nodes.front();
    984           path_nodes.clear();
    985           path_nodes.push_back(start);
    9861120
    9871121          // Find an augmenting path from the start node
     1122          path.clear();
    9881123          int tip = start;
    989           while (_excess[tip] >= 0 &&
    990                  int(path_nodes.size()) <= max_length) {
     1124          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
    9911125            int u;
    992             LargeCost min_red_cost, rc;
    993             int last_out = _sum_supply < 0 ?
    994               _first_out[tip+1] : _first_out[tip+1] - 1;
     1126            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1127            int last_out = _first_out[tip+1];
    9951128            for (int a = _next_out[tip]; a != last_out; ++a) {
    996               if (_res_cap[a] > 0 &&
    997                   _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
    998                 u = _target[a];
    999                 pred_arc[u] = a;
     1129              u = _target[a];
     1130              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
     1131                path.push_back(a);
    10001132                _next_out[tip] = a;
    10011133                tip = u;
    1002                 path_nodes.push_back(tip);
    10031134                goto next_step;
    10041135              }
    … …  
    10061137
    10071138            // Relabel tip node
    1008             min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
     1139            min_red_cost = std::numeric_limits<LargeCost>::max();
     1140            if (tip != start) {
     1141              int ra = _reverse[path.back()];
     1142              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1143            }
    10091144            for (int a = _first_out[tip]; a != last_out; ++a) {
    1010               rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
     1145              rc = _cost[a] + pi_tip - _pi[_target[a]];
    10111146              if (_res_cap[a] > 0 && rc < min_red_cost) {
    10121147                min_red_cost = rc;
    … …  
    10141149            }
    10151150            _pi[tip] -= min_red_cost + _epsilon;
    1016 
    1017             // Reset the next arc of tip
    10181151            _next_out[tip] = _first_out[tip];
     1152            ++relabel_cnt;
    10191153
    10201154            // Step back
    10211155            if (tip != start) {
    1022               path_nodes.pop_back();
    1023               tip = path_nodes.back();
     1156              tip = _source[path.back()];
     1157              path.pop_back();
    10241158            }
    10251159
    … …  
    10291163          // Augment along the found path (as much flow as possible)
    10301164          Value delta;
    1031           int u, v = path_nodes.front(), pa;
    1032           for (int i = 1; i < int(path_nodes.size()); ++i) {
     1165          int pa, u, v = start;
     1166          for (int i = 0; i != int(path.size()); ++i) {
     1167            pa = path[i];
    10331168            u = v;
    1034             v = path_nodes[i];
    1035             pa = pred_arc[v];
     1169            v = _target[pa];
    10361170            delta = std::min(_res_cap[pa], _excess[u]);
    10371171            _res_cap[pa] -= delta;
    … …  
    10421176              _active_nodes.push_back(v);
    10431177          }
     1178
     1179          // Global update heuristic
     1180          if (relabel_cnt >= next_update_limit) {
     1181            globalUpdate();
     1182            next_update_limit += global_update_freq;
     1183          }
    10441184        }
    10451185      }
    … …  
    10491189    void startPush() {
    10501190      // Paramters for heuristics
    1051       const int BF_HEURISTIC_EPSILON_BOUND = 1000;
    1052       const int BF_HEURISTIC_BOUND_FACTOR  = 3;
     1191      const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1192      const double GLOBAL_UPDATE_FACTOR = 2.0;
     1193
     1194      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1195        (_res_node_num + _sup_node_num * _sup_node_num));
     1196      int next_update_limit = global_update_freq;
     1197
     1198      int relabel_cnt = 0;
    10531199
    10541200      // Perform cost scaling phases
    10551201      BoolVector hyper(_res_node_num, false);
     1202      LargeCostVector hyper_cost(_res_node_num);
    10561203      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    10571204                                        1 : _epsilon / _alpha )
    10581205      {
    1059         // "Early Termination" heuristic: use Bellman-Ford algorithm
    1060         // to check if the current flow is optimal
    1061         if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
    1062           _arc_vec.clear();
    1063           _cost_vec.clear();
    1064           for (int j = 0; j != _res_arc_num; ++j) {
    1065             if (_res_cap[j] > 0) {
    1066               _arc_vec.push_back(IntPair(_source[j], _target[j]));
    1067               _cost_vec.push_back(_cost[j] + 1);
    1068             }
    1069           }
    1070           _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    1071 
    1072           BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
    1073           bf.init(0);
    1074           bool done = false;
    1075           int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
    1076           for (int i = 0; i < K && !done; ++i)
    1077             done = bf.processNextWeakRound();
    1078           if (done) break;
    1079         }
    1080 
    1081         // Saturate arcs not satisfying the optimality condition
    1082         for (int a = 0; a != _res_arc_num; ++a) {
    1083           if (_res_cap[a] > 0 &&
    1084               _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
    1085             Value delta = _res_cap[a];
    1086             _excess[_source[a]] -= delta;
    1087             _excess[_target[a]] += delta;
    1088             _res_cap[a] = 0;
    1089             _res_cap[_reverse[a]] += delta;
    1090           }
    1091         }
    1092 
    1093         // Find active nodes (i.e. nodes with positive excess)
    1094         for (int u = 0; u != _res_node_num; ++u) {
    1095           if (_excess[u] > 0) _active_nodes.push_back(u);
    1096         }
    1097 
    1098         // Initialize the next arcs
    1099         for (int u = 0; u != _res_node_num; ++u) {
    1100           _next_out[u] = _first_out[u];
    1101         }
     1206        // Early termination heuristic
     1207        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
     1208          if (earlyTermination()) break;
     1209        }
     1210
     1211        // Initialize current phase
     1212        initPhase();
    11021213
    11031214        // Perform push and relabel operations
    11041215        while (_active_nodes.size() > 0) {
    1105           LargeCost min_red_cost, rc;
     1216          LargeCost min_red_cost, rc, pi_n;
    11061217          Value delta;
    11071218          int n, t, a, last_out = _res_arc_num;
    11081219
     1220        next_node:
    11091221          // Select an active node (FIFO selection)
    1110         next_node:
    11111222          n = _active_nodes.front();
    1112           last_out = _sum_supply < 0 ?
    1113             _first_out[n+1] : _first_out[n+1] - 1;
     1223          last_out = _first_out[n+1];
     1224          pi_n = _pi[n];
    11141225
    11151226          // Perform push operations if there are admissible arcs
    … …  
    11171228            for (a = _next_out[n]; a != last_out; ++a) {
    11181229              if (_res_cap[a] > 0 &&
    1119                   _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
     1230                  _cost[a] + pi_n - _pi[_target[a]] < 0) {
    11201231                delta = std::min(_res_cap[a], _excess[n]);
    11211232                t = _target[a];
    … …  
    11231234                // Push-look-ahead heuristic
    11241235                Value ahead = -_excess[t];
    1125                 int last_out_t = _sum_supply < 0 ?
    1126                   _first_out[t+1] : _first_out[t+1] - 1;
     1236                int last_out_t = _first_out[t+1];
     1237                LargeCost pi_t = _pi[t];
    11271238                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
    1128                   if (_res_cap[ta] > 0 && 
    1129                       _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0)
     1239                  if (_res_cap[ta] > 0 &&
     1240                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
    11301241                    ahead += _res_cap[ta];
    11311242                  if (ahead >= delta) break;
    … …  
    11341245
    11351246                // Push flow along the arc
    1136                 if (ahead < delta) {
     1247                if (ahead < delta && !hyper[t]) {
    11371248                  _res_cap[a] -= ahead;
    11381249                  _res_cap[_reverse[a]] += ahead;
    … …  
    11411252                  _active_nodes.push_front(t);
    11421253                  hyper[t] = true;
     1254                  hyper_cost[t] = _cost[a] + pi_n - pi_t;
    11431255                  _next_out[n] = a;
    11441256                  goto next_node;
    … …  
    11631275          // Relabel the node if it is still active (or hyper)
    11641276          if (_excess[n] > 0 || hyper[n]) {
    1165             min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
     1277             min_red_cost = hyper[n] ? -hyper_cost[n] :
     1278               std::numeric_limits<LargeCost>::max();
    11661279            for (int a = _first_out[n]; a != last_out; ++a) {
    1167               rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
     1280              rc = _cost[a] + pi_n - _pi[_target[a]];
    11681281              if (_res_cap[a] > 0 && rc < min_red_cost) {
    11691282                min_red_cost = rc;
    … …  
    11711284            }
    11721285            _pi[n] -= min_red_cost + _epsilon;
     1286            _next_out[n] = _first_out[n];
    11731287            hyper[n] = false;
    1174 
    1175             // Reset the next arc
    1176             _next_out[n] = _first_out[n];
     1288            ++relabel_cnt;
    11771289          }
    1178        
     1290
    11791291          // Remove nodes that are not active nor hyper
    11801292        remove_nodes:
    … …  
    11841296            _active_nodes.pop_front();
    11851297          }
     1298
     1299          // Global update heuristic
     1300          if (relabel_cnt >= next_update_limit) {
     1301            globalUpdate();
     1302            for (int u = 0; u != _res_node_num; ++u)
     1303              hyper[u] = false;
     1304            next_update_limit += global_update_freq;
     1305          }
    11861306        }
    11871307      }

  • lemon/cplex.cc

    r793 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    112112  }
    113113
    114   int CplexBase::_addRow(Value lb, ExprIterator b, 
     114  int CplexBase::_addRow(Value lb, ExprIterator b,
    115115                         ExprIterator e, Value ub) {
    116116    int i = CPXgetnumrows(cplexEnv(), _prob);
    … …  
    490490
    491491  void CplexBase::_applyMessageLevel() {
    492     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     492    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    493493                   _message_enabled ? CPX_ON : CPX_OFF);
    494494  }

  • lemon/cycle_canceling.h

    r898 r956  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3535#include <lemon/circulation.h>
    3636#include <lemon/bellman_ford.h>
    37 #include <lemon/howard.h>
     37#include <lemon/howard_mmc.h>
    3838
    3939namespace lemon {
    … …  
    143143
    144144    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    145    
     145
    146146    typedef std::vector<int> IntVector;
    147     typedef std::vector<char> CharVector;
    148147    typedef std::vector<double> DoubleVector;
    149148    typedef std::vector<Value> ValueVector;
    150149    typedef std::vector<Cost> CostVector;
     150    typedef std::vector<char> BoolVector;
     151    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    151152
    152153  private:
    153  
     154
    154155    template <typename KT, typename VT>
    155156    class StaticVectorMap {
    … …  
    157158      typedef KT Key;
    158159      typedef VT Value;
    159      
     160
    160161      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
    161      
     162
    162163      const Value& operator[](const Key& key) const {
    163164        return _v[StaticDigraph::id(key)];
    … …  
    167168        return _v[StaticDigraph::id(key)];
    168169      }
    169      
     170
    170171      void set(const Key& key, const Value& val) {
    171172        _v[StaticDigraph::id(key)] = val;
    … …  
    199200    IntArcMap _arc_idb;
    200201    IntVector _first_out;
    201     CharVector _forward;
     202    BoolVector _forward;
    202203    IntVector _source;
    203204    IntVector _target;
    … …  
    221222    CostArcMap _cost_map;
    222223    CostNodeMap _pi_map;
    223  
     224
    224225  public:
    225  
     226
    226227    /// \brief Constant for infinite upper bounds (capacities).
    227228    ///
    … …  
    366367      return *this;
    367368    }
    368    
     369
    369370    /// @}
    370371
    … …  
    466467        _cost[j] = 0;
    467468        _cost[_reverse[j]] = 0;
    468       }     
     469      }
    469470      _have_lower = false;
    470471      return *this;
    … …  
    508509      _cost.resize(_res_arc_num);
    509510      _supply.resize(_res_node_num);
    510      
     511
    511512      _res_cap.resize(_res_arc_num);
    512513      _pi.resize(_res_node_num);
    … …  
    554555        _reverse[bi] = fi;
    555556      }
    556      
     557
    557558      // Reset parameters
    558559      resetParams();
    … …  
    663664      }
    664665      if (_sum_supply > 0) return INFEASIBLE;
    665      
     666
    666667
    667668      // Initialize vectors
    … …  
    670671      }
    671672      ValueVector excess(_supply);
    672      
     673
    673674      // Remove infinite upper bounds and check negative arcs
    674675      const Value MAX = std::numeric_limits<Value>::max();
    … …  
    770771        }
    771772      }
    772      
     773
    773774      return OPTIMAL;
    774775    }
    775    
     776
    776777    // Build a StaticDigraph structure containing the current
    777778    // residual network
    … …  
    829830      const int BF_FIRST_LIMIT  = 2;
    830831      const double BF_LIMIT_FACTOR = 1.5;
    831      
     832
    832833      typedef StaticVectorMap<StaticDigraph::Arc, Value> FilterMap;
    833834      typedef FilterArcs<StaticDigraph, FilterMap> ResDigraph;
    … …  
    836837        ::template SetDistMap<CostNodeMap>
    837838        ::template SetPredMap<PredMap>::Create BF;
    838      
     839
    839840      // Build the residual network
    840841      _arc_vec.clear();
    … …  
    924925      typedef SimplePath<StaticDigraph> SPath;
    925926      typedef typename SPath::ArcIt SPathArcIt;
    926       typedef typename Howard<StaticDigraph, CostArcMap>
     927      typedef typename HowardMmc<StaticDigraph, CostArcMap>
    927928        ::template SetPath<SPath>::Create MMC;
    928      
     929
    929930      SPath cycle;
    930931      MMC mmc(_sgr, _cost_map);
    931932      mmc.cycle(cycle);
    932933      buildResidualNetwork();
    933       while (mmc.findMinMean() && mmc.cycleLength() < 0) {
     934      while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
    934935        // Find the cycle
    935936        mmc.findCycle();
    … …  
    949950        }
    950951
    951         // Rebuild the residual network       
     952        // Rebuild the residual network
    952953        buildResidualNetwork();
    953954      }
    … …  
    963964      DoubleVector pi(_res_node_num, 0.0);
    964965      IntVector level(_res_node_num);
    965       CharVector reached(_res_node_num);
    966       CharVector processed(_res_node_num);
     966      BoolVector reached(_res_node_num);
     967      BoolVector processed(_res_node_num);
    967968      IntVector pred_node(_res_node_num);
    968969      IntVector pred_arc(_res_node_num);
    … …  
    11321133          }
    11331134        } else {
    1134           typedef Howard<StaticDigraph, CostArcMap> MMC;
     1135          typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
    11351136          typedef typename BellmanFord<StaticDigraph, CostArcMap>
    11361137            ::template SetDistMap<CostNodeMap>::Create BF;
    … …  
    11391140          buildResidualNetwork();
    11401141          MMC mmc(_sgr, _cost_map);
    1141           mmc.findMinMean();
     1142          mmc.findCycleMean();
    11421143          epsilon = -mmc.cycleMean();
    1143           Cost cycle_cost = mmc.cycleLength();
    1144           int cycle_size = mmc.cycleArcNum();
    1145          
     1144          Cost cycle_cost = mmc.cycleCost();
     1145          int cycle_size = mmc.cycleSize();
     1146
    11461147          // Compute feasible potentials for the current epsilon
    11471148          for (int i = 0; i != int(_cost_vec.size()); ++i) {
    … …  
    11551156            pi[u] = static_cast<double>(_pi[u]) / cycle_size;
    11561157          }
    1157        
     1158
    11581159          iter = limit;
    11591160        }

  • lemon/dfs.h

    r891 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    8383
    8484    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8687    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8788    ///Instantiates a \c ReachedMap.
    … …  
    271272    ///\ref named-templ-param "Named parameter" for setting
    272273    ///\c ReachedMap type.
    273     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     274    ///It must conform to
     275    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    274276    template <class T>
    275277    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    803805
    804806    ///The type of the map that indicates which nodes are reached.
    805     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     807    ///It must conform to
     808    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    806809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    807810    ///Instantiates a ReachedMap.
    … …  
    12081211    ///
    12091212    /// The type of the map that indicates which nodes are reached.
    1210     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1213    /// It must conform to the
     1214    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12111215    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12121216

  • lemon/dijkstra.h

    r891 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/dimacs.h

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

    r834 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/euler.h

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

    r834 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    204204    /// \brief Returns the node with the given index.
    205205    ///
    206     /// Returns the node with the given index. Since this structure is 
     206    /// Returns the node with the given index. Since this structure is
    207207    /// completely static, the nodes can be indexed with integers from
    208208    /// the range <tt>[0..nodeNum()-1]</tt>.
    … …  
    213213    /// \brief Returns the index of the given node.
    214214    ///
    215     /// Returns the index of the given node. Since this structure is 
     215    /// Returns the index of the given node. Since this structure is
    216216    /// completely static, the nodes can be indexed with integers from
    217217    /// the range <tt>[0..nodeNum()-1]</tt>.
    … …  
    583583    /// \brief Returns the node with the given index.
    584584    ///
    585     /// Returns the node with the given index. Since this structure is 
     585    /// Returns the node with the given index. Since this structure is
    586586    /// completely static, the nodes can be indexed with integers from
    587587    /// the range <tt>[0..nodeNum()-1]</tt>.
    … …  
    592592    /// \brief Returns the index of the given node.
    593593    ///
    594     /// Returns the index of the given node. Since this structure is 
     594    /// Returns the index of the given node. Since this structure is
    595595    /// completely static, the nodes can be indexed with integers from
    596596    /// the range <tt>[0..nodeNum()-1]</tt>.

  • lemon/glpk.cc

    r793 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    6060  }
    6161
    62   int GlpkBase::_addRow(Value lo, ExprIterator b, 
     62  int GlpkBase::_addRow(Value lo, ExprIterator b,
    6363                        ExprIterator e, Value up) {
    6464    int i = glp_add_rows(lp, 1);
    … …  
    6969      } else {
    7070        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
    71       }   
     71      }
    7272    } else {
    7373      if (up == INF) {
    7474        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
    75       } else if (lo != up) {       
     75      } else if (lo != up) {
    7676        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
    7777      } else {

  • lemon/glpk.h

    r902 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    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      }
    … …  
    125125      }
    126126    };
    127    
     127
    128128    static FreeEnvHelper freeEnvHelper;
    129129
    130130  protected:
    131    
     131
    132132    int _message_level;
    133    
     133
    134134  public:
    135135

  • lemon/gomory_hu.h

    r833 r956  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    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;
    … …  
    303303      Node rn = INVALID;
    304304      Value value = std::numeric_limits<Value>::max();
    305      
     305
    306306      while (sn != tn) {
    307         if ((*_order)[sn] < (*_order)[tn]) {
    308           if ((*_weight)[tn] <= value) {
    309             rn = tn;
     307        if ((*_order)[sn] < (*_order)[tn]) {
     308          if ((*_weight)[tn] <= value) {
     309            rn = tn;
    310310            s_root = false;
    311             value = (*_weight)[tn];
    312           }
    313           tn = (*_pred)[tn];
    314         } else {
    315           if ((*_weight)[sn] <= value) {
    316             rn = sn;
     311            value = (*_weight)[tn];
     312          }
     313          tn = (*_pred)[tn];
     314        } else {
     315          if ((*_weight)[sn] <= value) {
     316            rn = sn;
    317317            s_root = true;
    318             value = (*_weight)[sn];
    319           }
    320           sn = (*_pred)[sn];
    321         }
     318            value = (*_weight)[sn];
     319          }
     320          sn = (*_pred)[sn];
     321        }
    322322      }
    323323
    … …  
    330330      std::vector<Node> st;
    331331      for (NodeIt n(_graph); n != INVALID; ++n) {
    332         st.clear();
     332        st.clear();
    333333        Node nn = n;
    334         while (!reached[nn]) {
    335           st.push_back(nn);
    336           nn = (*_pred)[nn];
    337         }
    338         while (!st.empty()) {
    339           cutMap.set(st.back(), cutMap[nn]);
    340           st.pop_back();
    341         }
    342       }
    343      
     334        while (!reached[nn]) {
     335          st.push_back(nn);
     336          nn = (*_pred)[nn];
     337        }
     338        while (!st.empty()) {
     339          cutMap.set(st.back(), cutMap[nn]);
     340          st.pop_back();
     341        }
     342      }
     343
    344344      return value;
    345345    }
    … …  
    350350
    351351    /// Iterate on the nodes of a minimum cut
    352    
     352
    353353    /// This iterator class lists the nodes of a minimum cut found by
    354354    /// GomoryHu. Before using it, you must allocate a GomoryHu class
    … …  
    443443      }
    444444    };
    445    
     445
    446446    friend class MinCutEdgeIt;
    447    
     447
    448448    /// Iterate on the edges of a minimum cut
    449    
     449
    450450    /// This iterator class lists the edges of a minimum cut found by
    451451    /// GomoryHu. Before using it, you must allocate a GomoryHu class
    … …  
    480480          }
    481481      }
    482      
     482
    483483    public:
    484484      /// Constructor
    … …  
    549549      }
    550550      /// Postfix incrementation
    551      
     551
    552552      /// Postfix incrementation.
    553553      ///

  • lemon/graph_to_eps.h

    r833 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    685685#else
    686686      os << bits::getWinFormattedDate();
     687      os << std::endl;
    687688#endif
    688689    }
    689     os << std::endl;
    690690
    691691    if (_autoArcWidthScale) {

  • lemon/hao_orlin.h

    r644 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    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;
    … …  
    164164        delete _flow;
    165165      }
     166    }
     167
     168    /// \brief Set the tolerance used by the algorithm.
     169    ///
     170    /// This function sets the tolerance object used by the algorithm.
     171    /// \return <tt>(*this)</tt>
     172    HaoOrlin& tolerance(const Tolerance& tolerance) {
     173      _tolerance = tolerance;
     174      return *this;
     175    }
     176
     177    /// \brief Returns a const reference to the tolerance.
     178    ///
     179    /// This function returns a const reference to the tolerance object
     180    /// used by the algorithm.
     181    const Tolerance& tolerance() const {
     182      return _tolerance;
    166183    }
    167184
    … …  
    848865    ///
    849866    /// This function initializes the internal data structures. It creates
    850     /// the maps and some bucket structures for the algorithm. 
     867    /// the maps and some bucket structures for the algorithm.
    851868    /// The given node is used as the source node for the push-relabel
    852869    /// algorithm.
    … …  
    928945    /// \brief Run the algorithm.
    929946    ///
    930     /// This function runs the algorithm. It uses the given \c source node, 
     947    /// This function runs the algorithm. It uses the given \c source node,
    931948    /// finds a proper \c target node and then calls the \ref init(),
    932949    /// \ref calculateOut() and \ref calculateIn().
    … …  
    942959    /// The result of the %HaoOrlin algorithm
    943960    /// can be obtained using these functions.\n
    944     /// \ref run(), \ref calculateOut() or \ref calculateIn() 
     961    /// \ref run(), \ref calculateOut() or \ref calculateIn()
    945962    /// should be called before using them.
    946963
    … …  
    951968    /// This function returns the value of the minimum cut.
    952969    ///
    953     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
     970    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    954971    /// must be called before using this function.
    955972    Value minCutValue() const {
    … …  
    970987    /// \return The value of the minimum cut.
    971988    ///
    972     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 
     989    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    973990    /// must be called before using this function.
    974991    template <typename CutMap>

  • lemon/lgf_reader.h

    r833 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    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>
    … …  
    11881188
    11891189  };
    1190  
     1190
    11911191  /// \ingroup lemon_io
    11921192  ///
    … …  
    11951195  /// This function just returns a \ref DigraphReader class.
    11961196  ///
    1197   /// With this function a digraph can be read from an 
     1197  /// With this function a digraph can be read from an
    11981198  /// \ref lgf-format "LGF" file or input stream with several maps and
    11991199  /// attributes. For example, there is network flow problem on a
    … …  
    12501250  template <typename GR>
    12511251  class GraphReader;
    1252  
     1252
    12531253  template <typename TGR>
    12541254  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
    … …  
    13871387    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
    13881388    template <typename TGR>
    1389     friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 
     1389    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
    13901390    template <typename TGR>
    13911391    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
    … …  
    20642064  /// \brief Return a \ref GraphReader class
    20652065  ///
    2066   /// This function just returns a \ref GraphReader class. 
    2067   ///
    2068   /// With this function a graph can be read from an 
     2066  /// This function just returns a \ref GraphReader class.
     2067  ///
     2068  /// With this function a graph can be read from an
    20692069  /// \ref lgf-format "LGF" file or input stream with several maps and
    20702070  /// attributes. For example, there is weighted matching problem on a

  • lemon/lgf_writer.h

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

    r835 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    447447    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    448448    ///iterators are invalidated for the incomming arcs of \c v.
    449     ///Moreover all iterators referencing node \c v or the removed 
     449    ///Moreover all iterators referencing node \c v or the removed
    450450    ///loops are also invalidated. Other iterators remain valid.
    451451    ///
    … …  
    553553    /// restore() function.
    554554    ///
    555     /// \note After a state is restored, you cannot restore a later state, 
     555    /// \note After a state is restored, you cannot restore a later state,
    556556    /// i.e. you cannot add the removed nodes and arcs again using
    557557    /// another Snapshot instance.
    … …  
    13081308    /// or changeV(), thus all edge and arc iterators whose base node is
    13091309    /// \c b are invalidated.
    1310     /// Moreover all iterators referencing node \c b or the removed 
     1310    /// Moreover all iterators referencing node \c b or the removed
    13111311    /// loops are also invalidated. Other iterators remain valid.
    13121312    ///
    … …  
    13651365    /// using the restore() function.
    13661366    ///
    1367     /// \note After a state is restored, you cannot restore a later state, 
     1367    /// \note After a state is restored, you cannot restore a later state,
    13681368    /// i.e. you cannot add the removed nodes and edges again using
    13691369    /// another Snapshot instance.

  • lemon/lp.h

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

  • lemon/lp_base.cc

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

  • lemon/lp_base.h

    r903 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    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        ///
    … …  
    12301230      Row r;
    12311231      c.expr().simplify();
    1232       r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, 
     1232      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
    12331233                                ExprIterator(c.expr().comps.begin(), cols),
    12341234                                ExprIterator(c.expr().comps.end(), cols),
    … …  
    18181818    enum VarStatus {
    18191819      /// The variable is in the basis
    1820       BASIC, 
     1820      BASIC,
    18211821      /// The variable is free, but not basic
    18221822      FREE,
    1823       /// The variable has active lower bound 
     1823      /// The variable has active lower bound
    18241824      LOWER,
    18251825      /// The variable has active upper bound
    … …  
    19001900    }
    19011901    /// Returns a component of the primal ray
    1902    
     1902
    19031903    /// The primal ray is solution of the modified primal problem,
    19041904    /// where we change each finite bound to 0, and we looking for a
    … …  
    19341934
    19351935    /// Returns a component of the dual ray
    1936    
     1936
    19371937    /// The dual ray is solution of the modified primal problem, where
    19381938    /// we change each finite bound to 0 (i.e. the objective function
    … …  
    20762076    }
    20772077    ///The value of the objective function
    2078    
     2078
    20792079    ///\return
    20802080    ///- \ref INF or -\ref INF means either infeasibility or unboundedness

  • lemon/lp_skeleton.cc

    r793 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/lp_skeleton.h

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

    r839 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    234234  /// heap types and \c UnionFind, when the used items are small
    235235  /// integers. This map conforms to the \ref concepts::ReferenceMap
    236   /// "ReferenceMap" concept. 
     236  /// "ReferenceMap" concept.
    237237  ///
    238238  /// The simplest way of using this map is through the rangeMap()
    … …  
    19171917  /// \c InverseMap or \c operator()(), and the values of the map can be
    19181918  /// accessed with an STL compatible forward iterator (\c ValueIt).
    1919   /// 
     1919  ///
    19201920  /// This map is intended to be used when all associated values are
    19211921  /// different (the map is actually invertable) or there are only a few
    19221922  /// items with the same value.
    1923   /// Otherwise consider to use \c IterableValueMap, which is more 
     1923  /// Otherwise consider to use \c IterableValueMap, which is more
    19241924  /// suitable and more efficient for such cases. It provides iterators
    19251925  /// to traverse the items with the same associated value, but
    … …  
    20032003      typename Container::const_iterator it;
    20042004    };
    2005    
     2005
    20062006    /// Alias for \c ValueIt
    20072007    typedef ValueIt ValueIterator;
    … …  
    20622062      return it != _inv_map.end() ? it->second : INVALID;
    20632063    }
    2064    
     2064
    20652065    /// \brief Returns the number of items with the given value.
    20662066    ///
    … …  
    23792379    return RangeIdMap<GR, K>(graph);
    23802380  }
    2381  
     2381
    23822382  /// \brief Dynamic iterable \c bool map.
    23832383  ///
    … …  
    26392639      /// \param value The value.
    26402640      ItemIt(const IterableBoolMap& map, bool value)
    2641         : Parent(value ? 
     2641        : Parent(value ?
    26422642                 (map._sep > 0 ?
    26432643                  map._array[map._sep - 1] : INVALID) :
    … …  
    37873787    typedef typename To::Key Item;
    37883788    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    3789    
     3789
    37903790    for (ItemIt it(gr); it != INVALID; ++it) {
    37913791      to.set(it, from[it]);
    … …  
    37953795  /// \brief Compare two graph maps.
    37963796  ///
    3797   /// This function compares the values of two graph maps. It returns 
     3797  /// This function compares the values of two graph maps. It returns
    37983798  /// \c true if the maps assign the same value for all items in the graph.
    37993799  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
    … …  
    38073807    typedef typename Map2::Key Item;
    38083808    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
    3809    
     3809
    38103810    for (ItemIt it(gr); it != INVALID; ++it) {
    38113811      if (!(map1[it] == map2[it])) return false;

  • lemon/matching.h

    r698 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_MAX_MATCHING_H
    20 #define LEMON_MAX_MATCHING_H
     19#ifndef LEMON_MATCHING_H
     20#define LEMON_MATCHING_H
    2121
    2222#include <vector>
    … …  
    2929#include <lemon/bin_heap.h>
    3030#include <lemon/maps.h>
     31#include <lemon/fractional_matching.h>
    3132
    3233///\ingroup matching
    … …  
    4243  /// This class implements Edmonds' alternating forest matching algorithm
    4344  /// for finding a maximum cardinality matching in a general undirected graph.
    44   /// It can be started from an arbitrary initial matching 
     45  /// It can be started from an arbitrary initial matching
    4546  /// (the default is the empty one).
    4647  ///
    … …  
    7071    ///\brief Status constants for Gallai-Edmonds decomposition.
    7172    ///
    72     ///These constants are used for indicating the Gallai-Edmonds 
     73    ///These constants are used for indicating the Gallai-Edmonds
    7374    ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
    7475    ///induce a subgraph with factor-critical components, the nodes with
    7576    ///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 
     77    ///with status \c MATCHED (or \c C) induce a subgraph having a
    7778    ///perfect matching.
    7879    enum Status {
    … …  
    513514    }
    514515
    515     /// \brief Start Edmonds' algorithm with a heuristic improvement 
     516    /// \brief Start Edmonds' algorithm with a heuristic improvement
    516517    /// for dense graphs
    517518    ///
    … …  
    535536    /// \brief Run Edmonds' algorithm
    536537    ///
    537     /// This function runs Edmonds' algorithm. An additional heuristic of 
    538     /// postponing shrinks is used for relatively dense graphs 
     538    /// This function runs Edmonds' algorithm. An additional heuristic of
     539    /// postponing shrinks is used for relatively dense graphs
    539540    /// (for which <tt>m>=2*n</tt> holds).
    540541    void run() {
    … …  
    557558    /// \brief Return the size (cardinality) of the matching.
    558559    ///
    559     /// This function returns the size (cardinality) of the current matching. 
     560    /// This function returns the size (cardinality) of the current matching.
    560561    /// After run() it returns the size of the maximum matching in the graph.
    561562    int matchingSize() const {
    … …  
    571572    /// \brief Return \c true if the given edge is in the matching.
    572573    ///
    573     /// This function returns \c true if the given edge is in the current 
     574    /// This function returns \c true if the given edge is in the current
    574575    /// matching.
    575576    bool matching(const Edge& edge) const {
    … …  
    580581    ///
    581582    /// 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 
     583    /// given node in the current matching or \c INVALID if the node is
    583584    /// not covered by the matching.
    584585    Arc matching(const Node& n) const {
    … …  
    596597    /// \brief Return the mate of the given node.
    597598    ///
    598     /// This function returns the mate of the given node in the current 
     599    /// This function returns the mate of the given node in the current
    599600    /// matching or \c INVALID if the node is not covered by the matching.
    600601    Node mate(const Node& n) const {
    … …  
    606607
    607608    /// \name Dual Solution
    608     /// Functions to get the dual solution, i.e. the Gallai-Edmonds 
     609    /// Functions to get the dual solution, i.e. the Gallai-Edmonds
    609610    /// decomposition.
    610611
    … …  
    649650  /// \f$O(nm\log n)\f$ time complexity.
    650651  ///
    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 
     652  /// The maximum weighted matching problem is to find a subset of the
     653  /// edges in an undirected graph with maximum overall weight for which
    653654  /// each node has at most one incident edge.
    654655  /// It can be formulated with the following linear program.
    … …  
    674675      \frac{\vert B \vert - 1}{2}z_B\f] */
    675676  ///
    676   /// The algorithm can be executed with the run() function. 
     677  /// The algorithm can be executed with the run() function.
    677678  /// 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. 
     679  /// can be obtained using the query functions and the
     680  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
     681  /// which is able to iterate on the nodes of a blossom.
    681682  /// If the value type is integer, then the dual solution is multiplied
    682683  /// by \ref MaxWeightedMatching::dualScale "4".
    683684  ///
    684685  /// \tparam GR The undirected graph type the algorithm runs on.
    685   /// \tparam WM The type edge weight map. The default type is 
     686  /// \tparam WM The type edge weight map. The default type is
    686687  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    687688#ifdef DOXYGEN
    … …  
    746747
    747748    enum Status {
    748       EVEN = -1, MATCHED = 0, ODD = 1, UNMATCHED = -2
     749      EVEN = -1, MATCHED = 0, ODD = 1
    749750    };
    750751
    … …  
    798799
    799800    Value _delta_sum;
     801    int _unmatched;
     802
     803    typedef MaxWeightedFractionalMatching<Graph, WeightMap> FractionalMatching;
     804    FractionalMatching *_fractional;
    800805
    801806    void createStructures() {
    … …  
    806811        _matching = new MatchingMap(_graph);
    807812      }
     813
    808814      if (!_node_potential) {
    809815        _node_potential = new NodePotential(_graph);
    810816      }
     817
    811818      if (!_blossom_set) {
    812819        _blossom_index = new IntNodeMap(_graph);
    813820        _blossom_set = new BlossomSet(*_blossom_index);
    814821        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
     822      } else if (_blossom_data->size() != _blossom_num) {
     823        delete _blossom_data;
     824        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
    815825      }
    816826
    … …  
    819829        _node_heap_index = new IntArcMap(_graph);
    820830        _node_data = new RangeMap<NodeData>(_node_num,
    821                                               NodeData(*_node_heap_index));
     831                                            NodeData(*_node_heap_index));
     832      } else {
     833        delete _node_data;
     834        _node_data = new RangeMap<NodeData>(_node_num,
     835                                            NodeData(*_node_heap_index));
    822836      }
    823837
    … …  
    825839        _tree_set_index = new IntIntMap(_blossom_num);
    826840        _tree_set = new TreeSet(*_tree_set_index);
    827       }
     841      } else {
     842        _tree_set_index->resize(_blossom_num);
     843      }
     844
    828845      if (!_delta1) {
    829846        _delta1_index = new IntNodeMap(_graph);
    830847        _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
    831848      }
     849
    832850      if (!_delta2) {
    833851        _delta2_index = new IntIntMap(_blossom_num);
    834852        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
    835       }
     853      } else {
     854        _delta2_index->resize(_blossom_num);
     855      }
     856