Changes in / [1161:08712a8c3afe:1160:00f8d9f9920d] in lemon

Files:

• .hgtags (deleted)
• NEWS (modified) (1 diff)
• doc/groups.dox (modified) (7 diffs)
• doc/lgf.dox (modified) (1 diff)
• lemon/bits/graph_adaptor_extender.h (modified) (1 diff)
• lemon/bits/path_dump.h (modified) (1 diff)
• lemon/bits/windows.cc (modified) (1 diff)
• lemon/cost_scaling.h (modified) (1 diff)
• lemon/lp_base.h (modified) (1 diff)
• lemon/maps.h (modified) (1 diff)
• lemon/preflow.h (modified) (3 diffs)
• test/Makefile.am (modified) (1 diff)
• test/dfs_test.cc (modified) (2 diffs)
• test/graph_copy_test.cc (modified) (4 diffs)
• test/heap_test.cc (modified) (1 diff)
• test/lgf_test.cc (modified) (5 diffs)
• test/lp_test.cc (modified) (1 diff)
• test/maps_test.cc (modified) (1 diff)
• test/preflow_test.cc (modified) (3 diffs)

NEWS

@@ -1 @@
-2011-11-09 Version 1.2.3 released
-
-        Bugfix release.
-
-        #428: Add missing lemon/lemon.pc.cmake to the release tarball
-        #429: Fix VS warnings
-        #430: Fix LpBase::Constr two-side limit bug
-
-2011-08-08 Version 1.2.2 released
-
-        Bugfix release.
-
-        #392: Bug fix in Dfs::start(s,t)
-        #414: Fix wrong initialization in Preflow
-        #404: Update Doxygen configuration
-        #416: Support tests with valgrind
-        #418: Better Win CodeBlock/MinGW support
-        #419: Backport build environment improvements from the main branch
-              - Build of mip_test and lp_test precede the running of the tests
-              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
-              - Do not look for COIN_VOL libraries
-        #382: Allow lgf file without Arc maps
-        #417: Bug fix in CostScaling
-
-2010-10-21 Version 1.2.1 released
-
-        Bugfix release.
-
-        #366: Fix Pred[Matrix]MapPath::empty()
-        #371: Bug fix in (di)graphCopy()
-              The target graph is cleared before adding nodes and arcs/edges.
-
-        #364: Add missing UndirectedTags
-        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
-        #372: Fix a critical bug in preflow
-
 2010-03-19 Version 1.2 released
 

doc/groups.dox

@@ -287 +287 @@
 
 /**
+@defgroup matrices Matrices
+@ingroup auxdat
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
 @defgroup algs Algorithms
 \brief This group contains the several algorithms
@@ -319 +327 @@
    but the digraph should not contain directed cycles with negative total
    length.
+ - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
+   for solving the \e all-pairs \e shortest \e paths \e problem when arc
+   lenghts can be either positive or negative, but the digraph should
+   not contain directed cycles with negative total length.
  - \ref Suurballe A successive shortest path algorithm for finding
    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]
 
-\ref Preflow is an efficient implementation of Goldberg-Tarjan's
-preflow push-relabel algorithm \ref goldberg88newapproach for finding
-maximum flows. It also provides functions to query the minimum cut,
-which is the dual problem of maximum flow.
+LEMON contains several algorithms for solving maximum flow problems:
+- \ref EdmondsKarp Edmonds-Karp algorithm
+  \ref edmondskarp72theoretical.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
+  \ref goldberg88newapproach.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
+  \ref dinic70algorithm, \ref sleator83dynamic.
+- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
+  \ref goldberg88newapproach, \ref sleator83dynamic.
+
+In most cases the \ref Preflow algorithm provides the
+fastest method for computing a maximum flow. All implementations
+also provide functions to query the minimum cut, which is the dual
+problem of maximum flow.
 
 \ref Circulation is a preflow push-relabel algorithm implemented directly
@@ -412 +434 @@
 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   in directed graphs.
+- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
+  calculating minimum cut in undirected graphs.
 - \ref GomoryHu "Gomory-Hu tree computation" for calculating
   all-pairs minimum cut in undirected graphs.
@@ -474 +498 @@
 
 The matching algorithms implemented in LEMON:
+- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
+  for calculating maximum cardinality matching in bipartite graphs.
+- \ref PrBipartiteMatching Push-relabel algorithm
+  for calculating maximum cardinality matching in bipartite graphs.
+- \ref MaxWeightedBipartiteMatching
+  Successive shortest path algorithm for calculating maximum weighted
+  matching and maximum weighted bipartite matching in bipartite graphs.
+- \ref MinCostMaxBipartiteMatching
+  Successive shortest path algorithm for calculating minimum cost maximum
+  matching in bipartite graphs.
 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
   maximum cardinality matching in general graphs.
@@ -518 +552 @@
 
 /**
+@defgroup approx Approximation Algorithms
+@ingroup algs
+\brief Approximation algorithms.
+
+This group contains the approximation and heuristic algorithms
+implemented in LEMON.
+*/
+
+/**
 @defgroup auxalg Auxiliary Algorithms
 @ingroup algs
@@ -546 +589 @@
 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
 \ref cplex, \ref soplex.
+*/
+
+/**
+@defgroup lp_utils Tools for Lp and Mip Solvers
+@ingroup lp_group
+\brief Helper tools to the Lp and Mip solvers.
+
+This group adds some helper tools to general optimization framework
+implemented in LEMON.
+*/
+
+/**
+@defgroup metah Metaheuristics
+@ingroup gen_opt_group
+\brief Metaheuristics for LEMON library.
+
+This group contains some metaheuristic optimization tools.
 */
 

doc/lgf.dox

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/graph_adaptor_extender.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/path_dump.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/windows.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/cost_scaling.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/lp_base.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/maps.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/preflow.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -555 +555 @@
         }
       }
-      for (NodeIt n(_graph); n != INVALID; ++n)
+      for (NodeIt n(_graph); n != INVALID; ++n) 
         if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
           _level->activate(n);
-
+          
       return true;
     }
@@ -586 +586 @@
           level = _level->highestActiveLevel();
           --num;
-
+          
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();

test/Makefile.am

@@ -79 +79 @@
 test_graph_test_SOURCES = test/graph_test.cc
 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
-test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 test_heap_test_SOURCES = test/heap_test.cc
 test_kruskal_test_SOURCES = test/kruskal_test.cc
+test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 test_lgf_test_SOURCES = test/lgf_test.cc
 test_lp_test_SOURCES = test/lp_test.cc

test/dfs_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -220 +220 @@
   check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
   }
-
+  
   {
     NullMap<Node,Arc> myPredMap;

test/graph_copy_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -71 +71 @@
     nodeCrossRef(ncr).arcCrossRef(ecr).
     node(fn, tn).arc(fa, ta).run();
-
+  
   check(countNodes(from) == countNodes(to), "Wrong copy.");
   check(countArcs(from) == countArcs(to), "Wrong copy.");
@@ -99 +99 @@
   // Test repeated copy
   digraphCopy(from, to).run();
-
+  
   check(countNodes(from) == countNodes(to), "Wrong copy.");
   check(countArcs(from) == countArcs(to), "Wrong copy.");
@@ -201 +201 @@
   // Test repeated copy
   graphCopy(from, to).run();
-
+  
   check(countNodes(from) == countNodes(to), "Wrong copy.");
   check(countEdges(from) == countEdges(to), "Wrong copy.");

test/heap_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

test/lgf_test.cc

@@ -64 +64 @@
 
 
-int main()
+int main() 
 {
   {
-    ListDigraph d;
+    ListDigraph d; 
     ListDigraph::Node s,t;
     ListDigraph::ArcMap<int> label(d);
@@ -94 +94 @@
 
   {
-    ListDigraph d;
+    ListDigraph d; 
     std::istringstream input(test_lgf_nomap);
     digraphReader(d, input).
@@ -111 +111 @@
 
   {
-    ListDigraph d;
+    ListDigraph d; 
     std::istringstream input(test_lgf_bad1);
     bool ok=false;
@@ -118 +118 @@
         run();
     }
-    catch (FormatError&)
+    catch (FormatError&) 
       {
         ok = true;
@@ -140 +140 @@
 
   {
-    ListDigraph d;
+    ListDigraph d; 
     std::istringstream input(test_lgf_bad2);
     bool ok=false;

test/lp_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

test/maps_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

test/preflow_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2011
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -160 +160 @@
 {
   DIGRAPH_TYPEDEFS(SmartDigraph);
-
+  
   SmartDigraph g;
   SmartDigraph::ArcMap<int> cap(g),iflow(g);
@@ -272 +272 @@
 
   initFlowTest();
-
+  
   return 0;
 }