Changeset 766:97744b6dabf8 in lemon-main

Timestamp:

08/11/09 21:53:39 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Add HartmannOrlin? algorithm class (#179)
This algorithm is an improved version of Karp's original method,
it applies an efficient early termination scheme.
The interface is the same as Karp's and Howard's interface.

Files:

• lemon/Makefile.am (modified) (1 diff)
• lemon/hartmann_orlin.h (added)
• test/min_mean_cycle_test.cc (modified) (3 diffs)

lemon/Makefile.am

@@ -84 +84 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/hartmann_orlin.h \
         lemon/howard.h \
         lemon/hypercube_graph.h \

test/min_mean_cycle_test.cc

@@ -27 +27 @@
 
 #include <lemon/karp.h>
+#include <lemon/hartmann_orlin.h>
 #include <lemon/howard.h>
 
@@ -151 +152 @@
                   Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
     
+    // HartmannOrlin
+    checkConcept< MmcClassConcept<GR, int>,
+                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
+    checkConcept< MmcClassConcept<GR, float>,
+                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
+    
     // Howard
     checkConcept< MmcClassConcept<GR, int>,
@@ -190 +197 @@
     checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
 
+    // HartmannOrlin
+    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1,  6, 3);
+    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2,  5, 2);
+    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3,  0, 1);
+    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+
     // Howard
     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);