Changeset 812:3b544a9c92db in lemon

Timestamp:

08/11/09 20:55:40 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Add Karp algorithm class (#179)
based on the MinMeanCycle? implementation in SVN -r3436.
The interface is reworked to be the same as Howard's interface.

Files:

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

lemon/Makefile.am

@@ -86 +86 @@
         lemon/howard.h \
         lemon/hypercube_graph.h \
+        lemon/karp.h \
         lemon/kruskal.h \
         lemon/hao_orlin.h \

test/min_mean_cycle_test.cc

@@ -22 +22 @@
 #include <lemon/smart_graph.h>
 #include <lemon/lgf_reader.h>
-#include <lemon/howard.h>
 #include <lemon/path.h>
 #include <lemon/concepts/digraph.h>
 #include <lemon/concept_check.h>
+
+#include <lemon/karp.h>
+#include <lemon/howard.h>
 
 #include "test_tools.h"
@@ -142 +144 @@
   {
     typedef concepts::Digraph GR;
-    typedef Howard<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
-    typedef Howard<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
+
+    // Karp
+    checkConcept< MmcClassConcept<GR, int>,
+                  Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
+    checkConcept< MmcClassConcept<GR, float>,
+                  Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
     
-    checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
-    checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();
-  
-    if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)
-      check(false, "Wrong LargeValue type");
-    if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)
-      check(false, "Wrong LargeValue type");
+    // Howard
+    checkConcept< MmcClassConcept<GR, int>,
+                  Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
+    checkConcept< MmcClassConcept<GR, float>,
+                  Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
+
+    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
+          long_int>::result == 0) check(false, "Wrong LargeValue type");
+    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
+          double>::result == 0) check(false, "Wrong LargeValue type");
   }
 
@@ -175 +184 @@
       run();
 
+    // Karp
+    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
+    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
+    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
+    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+
+    // Howard
     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
     checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);