COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
18 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r962 r1099  
     12011-11-09 Version 1.2.3 released
     2
     3        Bugfix release.
     4
     5        #428: Add missing lemon/lemon.pc.cmake to the release tarball
     6        #429: Fix VS warnings
     7        #430: Fix LpBase::Constr two-side limit bug
     8
     92011-08-08 Version 1.2.2 released
     10
     11        Bugfix release.
     12
     13        #392: Bug fix in Dfs::start(s,t)
     14        #414: Fix wrong initialization in Preflow
     15        #404: Update Doxygen configuration
     16        #416: Support tests with valgrind
     17        #418: Better Win CodeBlock/MinGW support
     18        #419: Backport build environment improvements from the main branch
     19              - Build of mip_test and lp_test precede the running of the tests
     20              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
     21              - Do not look for COIN_VOL libraries
     22        #382: Allow lgf file without Arc maps
     23        #417: Bug fix in CostScaling
     24
     252010-10-21 Version 1.2.1 released
     26
     27        Bugfix release.
     28
     29        #366: Fix Pred[Matrix]MapPath::empty()
     30        #371: Bug fix in (di)graphCopy()
     31              The target graph is cleared before adding nodes and arcs/edges.
     32
     33        #364: Add missing UndirectedTags
     34        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
     35        #372: Fix a critical bug in preflow
     36
    1372010-03-19 Version 1.2 released
    238
  • doc/groups.dox

    r959 r963  
    287287
    288288/**
    289 @defgroup matrices Matrices
    290 @ingroup auxdat
    291 \brief Two dimensional data storages implemented in LEMON.
    292 
    293 This group contains two dimensional data storages implemented in LEMON.
    294 */
    295 
    296 /**
    297289@defgroup algs Algorithms
    298290\brief This group contains the several algorithms
     
    327319   but the digraph should not contain directed cycles with negative total
    328320   length.
    329  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    330    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    331    lenghts can be either positive or negative, but the digraph should
    332    not contain directed cycles with negative total length.
    333321 - \ref Suurballe A successive shortest path algorithm for finding
    334322   arc-disjoint paths between two nodes having minimum total length.
     
    364352\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    365353
    366 LEMON contains several algorithms for solving maximum flow problems:
    367 - \ref EdmondsKarp Edmonds-Karp algorithm
    368   \ref edmondskarp72theoretical.
    369 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    370   \ref goldberg88newapproach.
    371 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    372   \ref dinic70algorithm, \ref sleator83dynamic.
    373 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    374   \ref goldberg88newapproach, \ref sleator83dynamic.
    375 
    376 In most cases the \ref Preflow algorithm provides the
    377 fastest method for computing a maximum flow. All implementations
    378 also provide functions to query the minimum cut, which is the dual
    379 problem of maximum flow.
     354\ref Preflow is an efficient implementation of Goldberg-Tarjan's
     355preflow push-relabel algorithm \ref goldberg88newapproach for finding
     356maximum flows. It also provides functions to query the minimum cut,
     357which is the dual problem of maximum flow.
    380358
    381359\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    434412- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    435413  in directed graphs.
    436 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    437   calculating minimum cut in undirected graphs.
    438414- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    439415  all-pairs minimum cut in undirected graphs.
     
    498474
    499475The matching algorithms implemented in LEMON:
    500 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    501   for calculating maximum cardinality matching in bipartite graphs.
    502 - \ref PrBipartiteMatching Push-relabel algorithm
    503   for calculating maximum cardinality matching in bipartite graphs.
    504 - \ref MaxWeightedBipartiteMatching
    505   Successive shortest path algorithm for calculating maximum weighted
    506   matching and maximum weighted bipartite matching in bipartite graphs.
    507 - \ref MinCostMaxBipartiteMatching
    508   Successive shortest path algorithm for calculating minimum cost maximum
    509   matching in bipartite graphs.
    510476- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    511477  maximum cardinality matching in general graphs.
     
    552518
    553519/**
    554 @defgroup approx Approximation Algorithms
    555 @ingroup algs
    556 \brief Approximation algorithms.
    557 
    558 This group contains the approximation and heuristic algorithms
    559 implemented in LEMON.
    560 */
    561 
    562 /**
    563520@defgroup auxalg Auxiliary Algorithms
    564521@ingroup algs
     
    589546The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    590547\ref cplex, \ref soplex.
    591 */
    592 
    593 /**
    594 @defgroup lp_utils Tools for Lp and Mip Solvers
    595 @ingroup lp_group
    596 \brief Helper tools to the Lp and Mip solvers.
    597 
    598 This group adds some helper tools to general optimization framework
    599 implemented in LEMON.
    600 */
    601 
    602 /**
    603 @defgroup metah Metaheuristics
    604 @ingroup gen_opt_group
    605 \brief Metaheuristics for LEMON library.
    606 
    607 This group contains some metaheuristic optimization tools.
    608548*/
    609549
  • doc/lgf.dox

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

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

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

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

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

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

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

    r1107 r1110  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    555555        }
    556556      }
    557       for (NodeIt n(_graph); n != INVALID; ++n) 
     557      for (NodeIt n(_graph); n != INVALID; ++n)
    558558        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
    559559          _level->activate(n);
    560          
     560
    561561      return true;
    562562    }
     
    586586          level = _level->highestActiveLevel();
    587587          --num;
    588          
     588
    589589          Value excess = (*_excess)[n];
    590590          int new_level = _level->maxLevel();
  • test/Makefile.am

    r1107 r1110  
    7979test_graph_test_SOURCES = test/graph_test.cc
    8080test_graph_utils_test_SOURCES = test/graph_utils_test.cc
     81test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    8182test_heap_test_SOURCES = test/heap_test.cc
    8283test_kruskal_test_SOURCES = test/kruskal_test.cc
    83 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    8484test_lgf_test_SOURCES = test/lgf_test.cc
    8585test_lp_test_SOURCES = test/lp_test.cc
  • test/dfs_test.cc

    r1107 r1110  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    220220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
    221221  }
    222  
     222
    223223  {
    224224    NullMap<Node,Arc> myPredMap;
  • test/graph_copy_test.cc

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

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

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

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

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

    r1029 r1084  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    160160{
    161161  DIGRAPH_TYPEDEFS(SmartDigraph);
    162  
     162
    163163  SmartDigraph g;
    164164  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     
    272272
    273273  initFlowTest();
    274  
     274
    275275  return 0;
    276276}
Note: See TracChangeset for help on using the changeset viewer.