COIN-OR::LEMON - Graph Library

source: lemon-main/test/min_mean_cycle_test.cc @ 766:97744b6dabf8

Last change on this file since 766:97744b6dabf8 was 766:97744b6dabf8, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Add HartmannOrlin? algorithm class (#179)
This algorithm is an improved version of Karp's original method,
it applies an efficient early termination scheme.
The interface is the same as Karp's and Howard's interface.

File size: 5.9 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/hartmann_orlin.h>
30#include <lemon/howard.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 Value>
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 SetLargeValue<Value>
77        ::Create MmcAlg;
78      MmcAlg mmc(me.g, me.length);
79      const MmcAlg& const_mmc = mmc;
80     
81      b = mmc.cycle(p).run();
82      b = mmc.findMinMean();
83      b = mmc.findCycle();
84
85      v = const_mmc.cycleLength();
86      i = const_mmc.cycleArcNum();
87      d = const_mmc.cycleMean();
88      p = const_mmc.cycle();
89    }
90
91    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
92 
93    GR g;
94    LM length;
95    ListPath<GR> p;
96    Value v;
97    int i;
98    double d;
99    bool b;
100  };
101};
102
103// Perform a test with the given parameters
104template <typename MMC>
105void checkMmcAlg(const SmartDigraph& gr,
106                 const SmartDigraph::ArcMap<int>& lm,
107                 const SmartDigraph::ArcMap<int>& cm,
108                 int length, int size) {
109  MMC alg(gr, lm);
110  alg.findMinMean();
111  check(alg.cycleMean() == static_cast<double>(length) / size,
112        "Wrong cycle mean");
113  alg.findCycle();
114  check(alg.cycleLength() == length && alg.cycleArcNum() == size,
115        "Wrong path");
116  SmartDigraph::ArcMap<int> cycle(gr, 0);
117  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
118    ++cycle[a];
119  }
120  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
121    check(cm[a] == cycle[a], "Wrong path");
122  }
123}
124
125// Class for comparing types
126template <typename T1, typename T2>
127struct IsSameType {
128  static const int result = 0;
129};
130
131template <typename T>
132struct IsSameType<T,T> {
133  static const int result = 1;
134};
135
136
137int main() {
138  #ifdef LEMON_HAVE_LONG_LONG
139    typedef long long long_int;
140  #else
141    typedef long long_int;
142  #endif
143
144  // Check the interface
145  {
146    typedef concepts::Digraph GR;
147
148    // Karp
149    checkConcept< MmcClassConcept<GR, int>,
150                  Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
151    checkConcept< MmcClassConcept<GR, float>,
152                  Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
153   
154    // HartmannOrlin
155    checkConcept< MmcClassConcept<GR, int>,
156                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
157    checkConcept< MmcClassConcept<GR, float>,
158                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
159   
160    // Howard
161    checkConcept< MmcClassConcept<GR, int>,
162                  Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
163    checkConcept< MmcClassConcept<GR, float>,
164                  Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
165
166    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
167          long_int>::result == 0) check(false, "Wrong LargeValue type");
168    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
169          double>::result == 0) check(false, "Wrong LargeValue type");
170  }
171
172  // Run various tests
173  {
174    typedef SmartDigraph GR;
175    DIGRAPH_TYPEDEFS(GR);
176   
177    GR gr;
178    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
179    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
180   
181    std::istringstream input(test_lgf);
182    digraphReader(gr, input).
183      arcMap("len1", l1).
184      arcMap("len2", l2).
185      arcMap("len3", l3).
186      arcMap("len4", l4).
187      arcMap("c1", c1).
188      arcMap("c2", c2).
189      arcMap("c3", c3).
190      arcMap("c4", c4).
191      run();
192
193    // Karp
194    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1,  6, 3);
195    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2,  5, 2);
196    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3,  0, 1);
197    checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
198
199    // HartmannOrlin
200    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1,  6, 3);
201    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2,  5, 2);
202    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3,  0, 1);
203    checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
204
205    // Howard
206    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
207    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
208    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
209    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
210  }
211
212  return 0;
213}
Note: See TracBrowser for help on using the repository browser.