COIN-OR::LEMON - Graph Library

Changeset 765:3b544a9c92db in lemon-main


Ignore:
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:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r764 r765  
    8686        lemon/howard.h \
    8787        lemon/hypercube_graph.h \
     88        lemon/karp.h \
    8889        lemon/kruskal.h \
    8990        lemon/hao_orlin.h \
  • test/min_mean_cycle_test.cc

    r764 r765  
    2222#include <lemon/smart_graph.h>
    2323#include <lemon/lgf_reader.h>
    24 #include <lemon/howard.h>
    2524#include <lemon/path.h>
    2625#include <lemon/concepts/digraph.h>
    2726#include <lemon/concept_check.h>
     27
     28#include <lemon/karp.h>
     29#include <lemon/howard.h>
    2830
    2931#include "test_tools.h"
     
    142144  {
    143145    typedef concepts::Digraph GR;
    144     typedef Howard<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
    145     typedef Howard<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
     146
     147    // Karp
     148    checkConcept< MmcClassConcept<GR, int>,
     149                  Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
     150    checkConcept< MmcClassConcept<GR, float>,
     151                  Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
    146152   
    147     checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
    148     checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();
    149  
    150     if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)
    151       check(false, "Wrong LargeValue type");
    152     if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)
    153       check(false, "Wrong LargeValue type");
     153    // Howard
     154    checkConcept< MmcClassConcept<GR, int>,
     155                  Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
     156    checkConcept< MmcClassConcept<GR, float>,
     157                  Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
     158
     159    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
     160          long_int>::result == 0) check(false, "Wrong LargeValue type");
     161    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
     162          double>::result == 0) check(false, "Wrong LargeValue type");
    154163  }
    155164
     
    175184      run();
    176185
     186    // Karp
     187    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
     188    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
     189    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
     190    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
     191
     192    // Howard
    177193    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
    178194    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
Note: See TracChangeset for help on using the changeset viewer.