COIN-OR::LEMON - Graph Library

source: lemon/test/min_mean_cycle_test.cc @ 812:3b544a9c92db

Last change on this file since 812:3b544a9c92db was 812:3b544a9c92db, checked in by Peter Kovacs <kpeter@…>, 10 years ago

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.

File size: 5.4 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <iostream>
20#include <sstream>
21
22#include <lemon/smart_graph.h>
23#include <lemon/lgf_reader.h>
24#include <lemon/path.h>
25#include <lemon/concepts/digraph.h>
26#include <lemon/concept_check.h>
27
28#include <lemon/karp.h>
29#include <lemon/howard.h>
30
31#include "test_tools.h"
32
33using namespace lemon;
34
35char test_lgf[] =
36  "@nodes\n"
37  "label\n"
38  "1\n"
39  "2\n"
40  "3\n"
41  "4\n"
42  "5\n"
43  "6\n"
44  "7\n"
45  "@arcs\n"
46  "    len1 len2 len3 len4  c1 c2 c3 c4\n"
47  "1 2    1    1    1    1   0  0  0  0\n"
48  "2 4    5    5    5    5   1  0  0  0\n"
49  "2 3    8    8    8    8   0  0  0  0\n"
50  "3 2   -2    0    0    0   1  0  0  0\n"
51  "3 4    4    4    4    4   0  0  0  0\n"
52  "3 7   -4   -4   -4   -4   0  0  0  0\n"
53  "4 1    2    2    2    2   0  0  0  0\n"
54  "4 3    3    3    3    3   1  0  0  0\n"
55  "4 4    3    3    0    0   0  0  1  0\n"
56  "5 2    4    4    4    4   0  0  0  0\n"
57  "5 6    3    3    3    3   0  1  0  0\n"
58  "6 5    2    2    2    2   0  1  0  0\n"
59  "6 4   -1   -1   -1   -1   0  0  0  0\n"
60  "6 7    1    1    1    1   0  0  0  0\n"
61  "7 7    4    4    4   -1   0  0  0  1\n";
62
63                       
64// Check the interface of an MMC algorithm
65template <typename GR, typename Value>
66struct MmcClassConcept
67{
68  template <typename MMC>
69  struct Constraints {
70    void constraints() {
71      const Constraints& me = *this;
72
73      typedef typename MMC
74        ::template SetPath<ListPath<GR> >
75        ::template SetLargeValue<Value>
76        ::Create MmcAlg;
77      MmcAlg mmc(me.g, me.length);
78      const MmcAlg& const_mmc = mmc;
79     
80      b = mmc.cycle(p).run();
81      b = mmc.findMinMean();
82      b = mmc.findCycle();
83
84      v = const_mmc.cycleLength();
85      i = const_mmc.cycleArcNum();
86      d = const_mmc.cycleMean();
87      p = const_mmc.cycle();
88    }
89
90    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
91 
92    GR g;
93    LM length;
94    ListPath<GR> p;
95    Value v;
96    int i;
97    double d;
98    bool b;
99  };
100};
101
102// Perform a test with the given parameters
103template <typename MMC>
104void checkMmcAlg(const SmartDigraph& gr,
105                 const SmartDigraph::ArcMap<int>& lm,
106                 const SmartDigraph::ArcMap<int>& cm,
107                 int length, int size) {
108  MMC alg(gr, lm);
109  alg.findMinMean();
110  check(alg.cycleMean() == static_cast<double>(length) / size,
111        "Wrong cycle mean");
112  alg.findCycle();
113  check(alg.cycleLength() == length && alg.cycleArcNum() == size,
114        "Wrong path");
115  SmartDigraph::ArcMap<int> cycle(gr, 0);
116  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
117    ++cycle[a];
118  }
119  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
120    check(cm[a] == cycle[a], "Wrong path");
121  }
122}
123
124// Class for comparing types
125template <typename T1, typename T2>
126struct IsSameType {
127  static const int result = 0;
128};
129
130template <typename T>
131struct IsSameType<T,T> {
132  static const int result = 1;
133};
134
135
136int main() {
137  #ifdef LEMON_HAVE_LONG_LONG
138    typedef long long long_int;
139  #else
140    typedef long long_int;
141  #endif
142
143  // Check the interface
144  {
145    typedef concepts::Digraph GR;
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> > >();
152   
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");
163  }
164
165  // Run various tests
166  {
167    typedef SmartDigraph GR;
168    DIGRAPH_TYPEDEFS(GR);
169   
170    GR gr;
171    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
172    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
173   
174    std::istringstream input(test_lgf);
175    digraphReader(gr, input).
176      arcMap("len1", l1).
177      arcMap("len2", l2).
178      arcMap("len3", l3).
179      arcMap("len4", l4).
180      arcMap("c1", c1).
181      arcMap("c2", c2).
182      arcMap("c3", c3).
183      arcMap("c4", c4).
184      run();
185
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
193    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
194    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
195    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
196    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
197  }
198
199  return 0;
200}
Note: See TracBrowser for help on using the repository browser.