COIN-OR::LEMON - Graph Library

source: lemon-main/test/min_mean_cycle_test.cc @ 764:1fac515a59c1

Last change on this file since 764:1fac515a59c1 was 764:1fac515a59c1, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Rename MinMeanCycle? to Howard (#179)

File size: 4.8 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/howard.h>
25#include <lemon/path.h>
26#include <lemon/concepts/digraph.h>
27#include <lemon/concept_check.h>
28
29#include "test_tools.h"
30
31using namespace lemon;
32
33char test_lgf[] =
34  "@nodes\n"
35  "label\n"
36  "1\n"
37  "2\n"
38  "3\n"
39  "4\n"
40  "5\n"
41  "6\n"
42  "7\n"
43  "@arcs\n"
44  "    len1 len2 len3 len4  c1 c2 c3 c4\n"
45  "1 2    1    1    1    1   0  0  0  0\n"
46  "2 4    5    5    5    5   1  0  0  0\n"
47  "2 3    8    8    8    8   0  0  0  0\n"
48  "3 2   -2    0    0    0   1  0  0  0\n"
49  "3 4    4    4    4    4   0  0  0  0\n"
50  "3 7   -4   -4   -4   -4   0  0  0  0\n"
51  "4 1    2    2    2    2   0  0  0  0\n"
52  "4 3    3    3    3    3   1  0  0  0\n"
53  "4 4    3    3    0    0   0  0  1  0\n"
54  "5 2    4    4    4    4   0  0  0  0\n"
55  "5 6    3    3    3    3   0  1  0  0\n"
56  "6 5    2    2    2    2   0  1  0  0\n"
57  "6 4   -1   -1   -1   -1   0  0  0  0\n"
58  "6 7    1    1    1    1   0  0  0  0\n"
59  "7 7    4    4    4   -1   0  0  0  1\n";
60
61                       
62// Check the interface of an MMC algorithm
63template <typename GR, typename Value>
64struct MmcClassConcept
65{
66  template <typename MMC>
67  struct Constraints {
68    void constraints() {
69      const Constraints& me = *this;
70
71      typedef typename MMC
72        ::template SetPath<ListPath<GR> >
73        ::template SetLargeValue<Value>
74        ::Create MmcAlg;
75      MmcAlg mmc(me.g, me.length);
76      const MmcAlg& const_mmc = mmc;
77     
78      b = mmc.cycle(p).run();
79      b = mmc.findMinMean();
80      b = mmc.findCycle();
81
82      v = const_mmc.cycleLength();
83      i = const_mmc.cycleArcNum();
84      d = const_mmc.cycleMean();
85      p = const_mmc.cycle();
86    }
87
88    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
89 
90    GR g;
91    LM length;
92    ListPath<GR> p;
93    Value v;
94    int i;
95    double d;
96    bool b;
97  };
98};
99
100// Perform a test with the given parameters
101template <typename MMC>
102void checkMmcAlg(const SmartDigraph& gr,
103                 const SmartDigraph::ArcMap<int>& lm,
104                 const SmartDigraph::ArcMap<int>& cm,
105                 int length, int size) {
106  MMC alg(gr, lm);
107  alg.findMinMean();
108  check(alg.cycleMean() == static_cast<double>(length) / size,
109        "Wrong cycle mean");
110  alg.findCycle();
111  check(alg.cycleLength() == length && alg.cycleArcNum() == size,
112        "Wrong path");
113  SmartDigraph::ArcMap<int> cycle(gr, 0);
114  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
115    ++cycle[a];
116  }
117  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
118    check(cm[a] == cycle[a], "Wrong path");
119  }
120}
121
122// Class for comparing types
123template <typename T1, typename T2>
124struct IsSameType {
125  static const int result = 0;
126};
127
128template <typename T>
129struct IsSameType<T,T> {
130  static const int result = 1;
131};
132
133
134int main() {
135  #ifdef LEMON_HAVE_LONG_LONG
136    typedef long long long_int;
137  #else
138    typedef long long_int;
139  #endif
140
141  // Check the interface
142  {
143    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    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");
154  }
155
156  // Run various tests
157  {
158    typedef SmartDigraph GR;
159    DIGRAPH_TYPEDEFS(GR);
160   
161    GR gr;
162    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
163    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
164   
165    std::istringstream input(test_lgf);
166    digraphReader(gr, input).
167      arcMap("len1", l1).
168      arcMap("len2", l2).
169      arcMap("len3", l3).
170      arcMap("len4", l4).
171      arcMap("c1", c1).
172      arcMap("c2", c2).
173      arcMap("c3", c3).
174      arcMap("c4", c4).
175      run();
176
177    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
178    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
179    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
180    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
181  }
182
183  return 0;
184}
Note: See TracBrowser for help on using the repository browser.