COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 deleted
19 edited

Legend:

Unmodified
Added
Removed
  • NEWS

    r1277 r962  
    1 2013-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 
    24 2011-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 
    32 2011-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 
    48 2010-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 
    6012010-03-19 Version 1.2 released
    612
  • configure.ac

    r1276 r1039  
    1919AC_CONFIG_AUX_DIR([build-aux])
    2020AC_CONFIG_MACRO_DIR([m4])
    21 AM_INIT_AUTOMAKE([-Wall foreign subdir-objects nostdinc])
     21AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
    2222AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2323AC_CONFIG_HEADERS([config.h lemon/config.h])
  • doc/groups.dox

    r963 r959  
    287287
    288288/**
     289@defgroup matrices Matrices
     290@ingroup auxdat
     291\brief Two dimensional data storages implemented in LEMON.
     292
     293This group contains two dimensional data storages implemented in LEMON.
     294*/
     295
     296/**
    289297@defgroup algs Algorithms
    290298\brief This group contains the several algorithms
     
    319327   but the digraph should not contain directed cycles with negative total
    320328   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.
    321333 - \ref Suurballe A successive shortest path algorithm for finding
    322334   arc-disjoint paths between two nodes having minimum total length.
     
    352364\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    353365
    354 \ref Preflow is an efficient implementation of Goldberg-Tarjan's
    355 preflow push-relabel algorithm \ref goldberg88newapproach for finding
    356 maximum flows. It also provides functions to query the minimum cut,
    357 which is the dual problem of maximum flow.
     366LEMON 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
     376In most cases the \ref Preflow algorithm provides the
     377fastest method for computing a maximum flow. All implementations
     378also provide functions to query the minimum cut, which is the dual
     379problem of maximum flow.
    358380
    359381\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    412434- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    413435  in directed graphs.
     436- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     437  calculating minimum cut in undirected graphs.
    414438- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    415439  all-pairs minimum cut in undirected graphs.
     
    474498
    475499The 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.
    476510- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    477511  maximum cardinality matching in general graphs.
     
    518552
    519553/**
     554@defgroup approx Approximation Algorithms
     555@ingroup algs
     556\brief Approximation algorithms.
     557
     558This group contains the approximation and heuristic algorithms
     559implemented in LEMON.
     560*/
     561
     562/**
    520563@defgroup auxalg Auxiliary Algorithms
    521564@ingroup algs
     
    546589The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    547590\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
     598This group adds some helper tools to general optimization framework
     599implemented in LEMON.
     600*/
     601
     602/**
     603@defgroup metah Metaheuristics
     604@ingroup gen_opt_group
     605\brief Metaheuristics for LEMON library.
     606
     607This group contains some metaheuristic optimization tools.
    548608*/
    549609
  • doc/lgf.dox

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

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

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

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

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

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

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

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

    r1110 r1107  
    7979test_graph_test_SOURCES = test/graph_test.cc
    8080test_graph_utils_test_SOURCES = test/graph_utils_test.cc
    81 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    8281test_heap_test_SOURCES = test/heap_test.cc
    8382test_kruskal_test_SOURCES = test/kruskal_test.cc
     83test_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

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

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

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

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

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

    r1277 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2011
     5 * Copyright (C) 2003-2010
    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     ConstMap<Edge, bool> true_edge_map(true);
    539     Digraph dgr(gr, true_edge_map);
     538    Digraph dgr(gr, constMap<Edge, bool>(true));
    540539    OutDegMap<Digraph> odm(dgr);
    541540    InDegMap<Digraph> idm(dgr);
  • test/preflow_test.cc

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