Changes in / [757:9fbbd802020f:770:432c54cec63c] in lemon-1.2

Files:

• doc/groups.dox (modified) (1 diff)
• lemon/Makefile.am (modified) (1 diff)
• lemon/hartmann_orlin.h (added)
• lemon/howard.h (added)
• lemon/karp.h (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/min_mean_cycle_test.cc (added)
• test/test_tools.h (modified) (1 diff)

doc/groups.dox

@@ -454 +454 @@
 
 /**
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref Karp "Karp"'s original algorithm.
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+  version of Karp's algorithm.
+- \ref Howard "Howard"'s policy iteration algorithm.
+
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
+O(n<sup>2</sup>+e), but the latter one is typically faster due to the
+applied early termination scheme.
+*/
+
+/**
 @defgroup matching Matching Algorithms
 @ingroup algs

lemon/Makefile.am

@@ -87 +87 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/hartmann_orlin.h \
+        lemon/howard.h \
         lemon/hypercube_graph.h \
+        lemon/karp.h \
         lemon/kary_heap.h \
         lemon/kruskal.h \

test/CMakeLists.txt

@@ -33 +33 @@
   min_cost_arborescence_test
   min_cost_flow_test
+  min_mean_cycle_test
   path_test
   preflow_test

test/Makefile.am

@@ -31 +31 @@
         test/min_cost_arborescence_test \
         test/min_cost_flow_test \
+        test/min_mean_cycle_test \
         test/path_test \
         test/preflow_test \
@@ -79 +80 @@
 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
+test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_preflow_test_SOURCES = test/preflow_test.cc

test/test_tools.h

@@ -38 +38 @@
 ///print something like this (and then exits).
 ///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
-#define check(rc, msg) \
-  if(!(rc)) { \
-    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
-    abort(); \
-  } else { } \
+#define check(rc, msg)                                                  \
+  {                                                                     \
+    if(!(rc)) {                                                         \
+      std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \
+                << msg << std::endl;                                    \
+      abort();                                                          \
+    } else { }                                                          \
+  }                                                                     \
+    
 
 #endif