Changes in / [972:1fe3b4ad8caa:971:a26b90a17c81] in lemon-1.2
- Files:
-
- 1 deleted
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
NEWS
r934 r883 1 2011-11-09 Version 1.2.3 released2 3 Bugfix release.4 5 #428: Add missing lemon/lemon.pc.cmake to the release tarball6 #429: Fix VS warnings7 #430: Fix LpBase::Constr two-side limit bug8 9 2011-08-08 Version 1.2.2 released10 11 Bugfix release.12 13 #392: Bug fix in Dfs::start(s,t)14 #414: Fix wrong initialization in Preflow15 #404: Update Doxygen configuration16 #416: Support tests with valgrind17 #418: Better Win CodeBlock/MinGW support18 #419: Backport build environment improvements from the main branch19 - Build of mip_test and lp_test precede the running of the tests20 - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin21 - Do not look for COIN_VOL libraries22 #382: Allow lgf file without Arc maps23 #417: Bug fix in CostScaling24 25 2010-10-21 Version 1.2.1 released26 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 UndirectedTags34 #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex35 #372: Fix a critical bug in preflow36 37 1 2010-03-19 Version 1.2 released 38 2 -
doc/groups.dox
r884 r880 287 287 288 288 /** 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 /** 289 297 @defgroup algs Algorithms 290 298 \brief This group contains the several algorithms … … 319 327 but the digraph should not contain directed cycles with negative total 320 328 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. 321 333 - \ref Suurballe A successive shortest path algorithm for finding 322 334 arc-disjoint paths between two nodes having minimum total length. … … 352 364 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 353 365 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. 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. 358 380 359 381 \ref Circulation is a preflow push-relabel algorithm implemented directly … … 412 434 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 413 435 in directed graphs. 436 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 437 calculating minimum cut in undirected graphs. 414 438 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 415 439 all-pairs minimum cut in undirected graphs. … … 474 498 475 499 The 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. 476 510 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 477 511 maximum cardinality matching in general graphs. … … 518 552 519 553 /** 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 /** 520 563 @defgroup auxalg Auxiliary Algorithms 521 564 @ingroup algs … … 546 589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 547 590 \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. 548 608 */ 549 609 -
doc/lgf.dox
r927 r923 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/graph_adaptor_extender.h
r927 r886 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/path_dump.h
r927 r890 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/bits/windows.cc
r927 r914 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/cost_scaling.h
r927 r909 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/lp_base.h
r966 r964 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/maps.h
r927 r915 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/preflow.h
r944 r942 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 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
r944 r942 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.cc82 81 test_heap_test_SOURCES = test/heap_test.cc 83 82 test_kruskal_test_SOURCES = test/kruskal_test.cc 83 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc 84 84 test_lgf_test_SOURCES = test/lgf_test.cc 85 85 test_lp_test_SOURCES = test/lp_test.cc -
test/dfs_test.cc
r972 r970 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 224 224 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); 225 225 } 226 226 227 227 { 228 228 NullMap<Node,Arc> myPredMap; -
test/graph_copy_test.cc
r927 r896 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 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
r927 r921 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/lgf_test.cc
r935 r930 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
r956 r955 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/maps_test.cc
r966 r964 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/preflow_test.cc
r972 r970 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 15 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 161 161 { 162 162 DIGRAPH_TYPEDEFS(SmartDigraph); 163 163 164 164 SmartDigraph g; 165 165 SmartDigraph::ArcMap<int> cap(g),iflow(g); … … 273 273 274 274 initFlowTest(); 275 275 276 276 return 0; 277 277 }
Note: See TracChangeset
for help on using the changeset viewer.