COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
19 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r962 r1277  
     12013-08-10 Version 1.2.4 released
     2
     3        Bugfix release.
     4
     5        #432: Add missing doc/template.h and doc/references.bib to release
     6              tarball
     7        #433: Support shared library build
     8        ----: Update CPLEX lookup
     9        ----: Make CBC interface compatible with latest CBC releases
     10        ----: Intel C++ compatibility fixes
     11        #441: Fix buggy reinitialization in _solver_bits::VarIndex::clear()
     12        #444: Bugfix in path copy constructors and assignment operators
     13        #447: Bugfix in AllArcLookUp<>
     14        #448: Bugfix in adaptor_test.cc
     15        #449: Fix clang compilation warnings and errors
     16        #440: Fix a bug + remove redundant typedefs in dimacs-solver
     17        #453: Avoid GCC 4.7 compiler warnings
     18        #445: Fix missing initialization in CplexEnv::CplexEnv()
     19        #461: Bugfix in assert.h
     20        #470: Fix compilation issues related to various gcc versions
     21        #439: Bugfix in biNodeConnected()
     22        #469: Bugfix in test/maps_test.cc
     23
     242011-11-09 Version 1.2.3 released
     25
     26        Bugfix release.
     27
     28        #428: Add missing lemon/lemon.pc.cmake to the release tarball
     29        #429: Fix VS warnings
     30        #430: Fix LpBase::Constr two-side limit bug
     31
     322011-08-08 Version 1.2.2 released
     33
     34        Bugfix release.
     35
     36        #392: Bug fix in Dfs::start(s,t)
     37        #414: Fix wrong initialization in Preflow
     38        #404: Update Doxygen configuration
     39        #416: Support tests with valgrind
     40        #418: Better Win CodeBlock/MinGW support
     41        #419: Backport build environment improvements from the main branch
     42              - Build of mip_test and lp_test precede the running of the tests
     43              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
     44              - Do not look for COIN_VOL libraries
     45        #382: Allow lgf file without Arc maps
     46        #417: Bug fix in CostScaling
     47
     482010-10-21 Version 1.2.1 released
     49
     50        Bugfix release.
     51
     52        #366: Fix Pred[Matrix]MapPath::empty()
     53        #371: Bug fix in (di)graphCopy()
     54              The target graph is cleared before adding nodes and arcs/edges.
     55
     56        #364: Add missing UndirectedTags
     57        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
     58        #372: Fix a critical bug in preflow
     59
    1602010-03-19 Version 1.2 released
    261
  • configure.ac

    r1039 r1276  
    1919AC_CONFIG_AUX_DIR([build-aux])
    2020AC_CONFIG_MACRO_DIR([m4])
    21 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
     21AM_INIT_AUTOMAKE([-Wall foreign subdir-objects nostdinc])
    2222AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2323AC_CONFIG_HEADERS([config.h lemon/config.h])
  • 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

    r1143 r1161  
    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 r1324  
    1212check_PROGRAMS += \
    1313        test/adaptors_test \
     14        test/arc_lookup_test \
    1415        test/bellman_ford_test \
    1516        test/bfs_test \
     
    6263
    6364test_adaptors_test_SOURCES = test/adaptors_test.cc
     65test_adaptors_test_SOURCES = test/arc_lookup_test.cc
    6466test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    6567test_bfs_test_SOURCES = test/bfs_test.cc
     
    7981test_graph_test_SOURCES = test/graph_test.cc
    8082test_graph_utils_test_SOURCES = test/graph_utils_test.cc
     83test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    8184test_heap_test_SOURCES = test/heap_test.cc
    8285test_kruskal_test_SOURCES = test/kruskal_test.cc
    83 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    8486test_lgf_test_SOURCES = test/lgf_test.cc
    8587test_lp_test_SOURCES = test/lp_test.cc
  • test/dfs_test.cc

    r1259 r1263  
    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).
     
    224224  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
    225225  }
    226  
     226
    227227  {
    228228    NullMap<Node,Arc> myPredMap;
  • test/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

    r1247 r1248  
    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

    r1259 r1277  
    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).
     
    536536
    537537    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
    538     Digraph dgr(gr, constMap<Edge, bool>(true));
     538    ConstMap<Edge, bool> true_edge_map(true);
     539    Digraph dgr(gr, true_edge_map);
    539540    OutDegMap<Digraph> odm(dgr);
    540541    InDegMap<Digraph> idm(dgr);
  • test/preflow_test.cc

    r1259 r1263  
    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).
     
    161161{
    162162  DIGRAPH_TYPEDEFS(SmartDigraph);
    163  
     163
    164164  SmartDigraph g;
    165165  SmartDigraph::ArcMap<int> cap(g),iflow(g);
     
    273273
    274274  initFlowTest();
    275  
     275
    276276  return 0;
    277277}
Note: See TracChangeset for help on using the changeset viewer.