COIN-OR::LEMON - Graph Library

source: lemon-main/test/min_mean_cycle_test.cc @ 1018:2e959a5a0c2d

Last change on this file since 1018:2e959a5a0c2d was 1012:21a9f829ab68, checked in by Peter Kovacs <kpeter@…>, 12 years ago

Optional iteration limit in HowardMmc? (#438)

File size: 6.3 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-2010
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_mmc.h>
29#include <lemon/hartmann_orlin_mmc.h>
30#include <lemon/howard_mmc.h>
31
32#include "test_tools.h"
33
34using namespace lemon;
35
36char test_lgf[] =
37  "@nodes\n"
38  "label\n"
39  "1\n"
40  "2\n"
41  "3\n"
42  "4\n"
43  "5\n"
44  "6\n"
45  "7\n"
46  "@arcs\n"
47  "    len1 len2 len3 len4  c1 c2 c3 c4\n"
48  "1 2    1    1    1    1   0  0  0  0\n"
49  "2 4    5    5    5    5   1  0  0  0\n"
50  "2 3    8    8    8    8   0  0  0  0\n"
51  "3 2   -2    0    0    0   1  0  0  0\n"
52  "3 4    4    4    4    4   0  0  0  0\n"
53  "3 7   -4   -4   -4   -4   0  0  0  0\n"
54  "4 1    2    2    2    2   0  0  0  0\n"
55  "4 3    3    3    3    3   1  0  0  0\n"
56  "4 4    3    3    0    0   0  0  1  0\n"
57  "5 2    4    4    4    4   0  0  0  0\n"
58  "5 6    3    3    3    3   0  1  0  0\n"
59  "6 5    2    2    2    2   0  1  0  0\n"
60  "6 4   -1   -1   -1   -1   0  0  0  0\n"
61  "6 7    1    1    1    1   0  0  0  0\n"
62  "7 7    4    4    4   -1   0  0  0  1\n";
63
64
65// Check the interface of an MMC algorithm
66template <typename GR, typename Cost>
67struct MmcClassConcept
68{
69  template <typename MMC>
70  struct Constraints {
71    void constraints() {
72      const Constraints& me = *this;
73
74      typedef typename MMC
75        ::template SetPath<ListPath<GR> >
76        ::template SetLargeCost<Cost>
77        ::Create MmcAlg;
78      MmcAlg mmc(me.g, me.cost);
79      const MmcAlg& const_mmc = mmc;
80
81      typename MmcAlg::Tolerance tol = const_mmc.tolerance();
82      mmc.tolerance(tol);
83
84      b = mmc.cycle(p).run();
85      b = mmc.findCycleMean();
86      b = mmc.findCycle();
87
88      v = const_mmc.cycleCost();
89      i = const_mmc.cycleSize();
90      d = const_mmc.cycleMean();
91      p = const_mmc.cycle();
92    }
93
94    typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
95
96    GR g;
97    CM cost;
98    ListPath<GR> p;
99    Cost v;
100    int i;
101    double d;
102    bool b;
103  };
104};
105
106// Perform a test with the given parameters
107template <typename MMC>
108void checkMmcAlg(const SmartDigraph& gr,
109                 const SmartDigraph::ArcMap<int>& lm,
110                 const SmartDigraph::ArcMap<int>& cm,
111                 int cost, int size) {
112  MMC alg(gr, lm);
113  check(alg.findCycleMean(), "Wrong result");
114  check(alg.cycleMean() == static_cast<double>(cost) / size,
115        "Wrong cycle mean");
116  alg.findCycle();
117  check(alg.cycleCost() == cost && alg.cycleSize() == size,
118        "Wrong path");
119  SmartDigraph::ArcMap<int> cycle(gr, 0);
120  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
121    ++cycle[a];
122  }
123  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
124    check(cm[a] == cycle[a], "Wrong path");
125  }
126}
127
128// Class for comparing types
129template <typename T1, typename T2>
130struct IsSameType {
131  static const int result = 0;
132};
133
134template <typename T>
135struct IsSameType<T,T> {
136  static const int result = 1;
137};
138
139
140int main() {
141  #ifdef LEMON_HAVE_LONG_LONG
142    typedef long long long_int;
143  #else
144    typedef long long_int;
145  #endif
146
147  // Check the interface
148  {
149    typedef concepts::Digraph GR;
150
151    // KarpMmc
152    checkConcept< MmcClassConcept<GR, int>,
153                  KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
154    checkConcept< MmcClassConcept<GR, float>,
155                  KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
156
157    // HartmannOrlinMmc
158    checkConcept< MmcClassConcept<GR, int>,
159                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
160    checkConcept< MmcClassConcept<GR, float>,
161                  HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
162
163    // HowardMmc
164    checkConcept< MmcClassConcept<GR, int>,
165                  HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
166    checkConcept< MmcClassConcept<GR, float>,
167                  HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
168
169    check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
170           ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
171    check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
172           ::LargeCost, double>::result == 1), "Wrong LargeCost type");
173  }
174
175  // Run various tests
176  {
177    typedef SmartDigraph GR;
178    DIGRAPH_TYPEDEFS(GR);
179
180    GR gr;
181    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
182    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
183
184    std::istringstream input(test_lgf);
185    digraphReader(gr, input).
186      arcMap("len1", l1).
187      arcMap("len2", l2).
188      arcMap("len3", l3).
189      arcMap("len4", l4).
190      arcMap("c1", c1).
191      arcMap("c2", c2).
192      arcMap("c3", c3).
193      arcMap("c4", c4).
194      run();
195
196    // Karp
197    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
198    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
199    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
200    checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
201
202    // HartmannOrlin
203    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
204    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
205    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
206    checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
207
208    // Howard
209    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1,  6, 3);
210    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
211    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
212    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
213   
214    // Howard with iteration limit
215    HowardMmc<GR, IntArcMap> mmc(gr, l1);
216    check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT),
217      "Wrong termination cause");
218    check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL),
219      "Wrong termination cause");
220  }
221
222  return 0;
223}
Note: See TracBrowser for help on using the repository browser.