Changes in / [1108:a1fd7008a052:1110:02c93d1f00d7] in lemon
- Files:
-
- 1 added
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
NEWS
r962 r1099 1 2011-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 9 2011-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 25 2010-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 1 37 2010-03-19 Version 1.2 released 2 38 -
doc/groups.dox
r959 r963 287 287 288 288 /** 289 @defgroup matrices Matrices290 @ingroup auxdat291 \brief Two dimensional data storages implemented in LEMON.292 293 This group contains two dimensional data storages implemented in LEMON.294 */295 296 /**297 289 @defgroup algs Algorithms 298 290 \brief This group contains the several algorithms … … 327 319 but the digraph should not contain directed cycles with negative total 328 320 length. 329 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms330 for solving the \e all-pairs \e shortest \e paths \e problem when arc331 lenghts can be either positive or negative, but the digraph should332 not contain directed cycles with negative total length.333 321 - \ref Suurballe A successive shortest path algorithm for finding 334 322 arc-disjoint paths between two nodes having minimum total length. … … 364 352 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 365 353 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 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. 380 358 381 359 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 434 412 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 435 413 in directed graphs. 436 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for437 calculating minimum cut in undirected graphs.438 414 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 439 415 all-pairs minimum cut in undirected graphs. … … 498 474 499 475 The matching algorithms implemented in LEMON: 500 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm501 for calculating maximum cardinality matching in bipartite graphs.502 - \ref PrBipartiteMatching Push-relabel algorithm503 for calculating maximum cardinality matching in bipartite graphs.504 - \ref MaxWeightedBipartiteMatching505 Successive shortest path algorithm for calculating maximum weighted506 matching and maximum weighted bipartite matching in bipartite graphs.507 - \ref MinCostMaxBipartiteMatching508 Successive shortest path algorithm for calculating minimum cost maximum509 matching in bipartite graphs.510 476 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 511 477 maximum cardinality matching in general graphs. … … 552 518 553 519 /** 554 @defgroup approx Approximation Algorithms555 @ingroup algs556 \brief Approximation algorithms.557 558 This group contains the approximation and heuristic algorithms559 implemented in LEMON.560 */561 562 /**563 520 @defgroup auxalg Auxiliary Algorithms 564 521 @ingroup algs … … 589 546 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 590 547 \ref cplex, \ref soplex. 591 */592 593 /**594 @defgroup lp_utils Tools for Lp and Mip Solvers595 @ingroup lp_group596 \brief Helper tools to the Lp and Mip solvers.597 598 This group adds some helper tools to general optimization framework599 implemented in LEMON.600 */601 602 /**603 @defgroup metah Metaheuristics604 @ingroup gen_opt_group605 \brief Metaheuristics for LEMON library.606 607 This group contains some metaheuristic optimization tools.608 548 */ 609 549 -
doc/lgf.dox
r1069 r1081 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/graph_adaptor_extender.h
r965 r1081 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/path_dump.h
r973 r1081 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/windows.cc
r1055 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/cost_scaling.h
r1041 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/lp_base.h
r1094 r1100 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/maps.h
r1057 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/preflow.h
r1107 r1110 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 555 555 } 556 556 } 557 for (NodeIt n(_graph); n != INVALID; ++n) 557 for (NodeIt n(_graph); n != INVALID; ++n) 558 558 if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) 559 559 _level->activate(n); 560 560 561 561 return true; 562 562 } … … 586 586 level = _level->highestActiveLevel(); 587 587 --num; 588 588 589 589 Value excess = (*_excess)[n]; 590 590 int new_level = _level->maxLevel(); -
test/Makefile.am
r1107 r1110 79 79 test_graph_test_SOURCES = test/graph_test.cc 80 80 test_graph_utils_test_SOURCES = test/graph_utils_test.cc 81 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc 81 82 test_heap_test_SOURCES = test/heap_test.cc 82 83 test_kruskal_test_SOURCES = test/kruskal_test.cc 83 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc84 84 test_lgf_test_SOURCES = test/lgf_test.cc 85 85 test_lp_test_SOURCES = test/lp_test.cc -
test/dfs_test.cc
r1107 r1110 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 220 220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); 221 221 } 222 222 223 223 { 224 224 NullMap<Node,Arc> myPredMap; -
test/graph_copy_test.cc
r984 r1081 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 71 71 nodeCrossRef(ncr).arcCrossRef(ecr). 72 72 node(fn, tn).arc(fa, ta).run(); 73 73 74 74 check(countNodes(from) == countNodes(to), "Wrong copy."); 75 75 check(countArcs(from) == countArcs(to), "Wrong copy."); … … 99 99 // Test repeated copy 100 100 digraphCopy(from, to).run(); 101 101 102 102 check(countNodes(from) == countNodes(to), "Wrong copy."); 103 103 check(countArcs(from) == countArcs(to), "Wrong copy."); … … 201 201 // Test repeated copy 202 202 graphCopy(from, to).run(); 203 203 204 204 check(countNodes(from) == countNodes(to), "Wrong copy."); 205 205 check(countEdges(from) == countEdges(to), "Wrong copy."); -
test/heap_test.cc
r1065 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/lgf_test.cc
r1087 r1097 64 64 65 65 66 int main() 66 int main() 67 67 { 68 68 { 69 ListDigraph d; 69 ListDigraph d; 70 70 ListDigraph::Node s,t; 71 71 ListDigraph::ArcMap<int> label(d); … … 94 94 95 95 { 96 ListDigraph d; 96 ListDigraph d; 97 97 std::istringstream input(test_lgf_nomap); 98 98 digraphReader(d, input). … … 111 111 112 112 { 113 ListDigraph d; 113 ListDigraph d; 114 114 std::istringstream input(test_lgf_bad1); 115 115 bool ok=false; … … 118 118 run(); 119 119 } 120 catch (FormatError&) 120 catch (FormatError&) 121 121 { 122 122 ok = true; … … 140 140 141 141 { 142 ListDigraph d; 142 ListDigraph d; 143 143 std::istringstream input(test_lgf_bad2); 144 144 bool ok=false; -
test/lp_test.cc
r1092 r1097 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/maps_test.cc
r1057 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/preflow_test.cc
r1029 r1084 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 160 160 { 161 161 DIGRAPH_TYPEDEFS(SmartDigraph); 162 162 163 163 SmartDigraph g; 164 164 SmartDigraph::ArcMap<int> cap(g),iflow(g); … … 272 272 273 273 initFlowTest(); 274 274 275 275 return 0; 276 276 }
Note: See TracChangeset
for help on using the changeset viewer.