COIN-OR::LEMON - Graph Library

source: lemon-main/test/circulation_test.cc @ 585:65fbcf2f978a

Last change on this file since 585:65fbcf2f978a was 585:65fbcf2f978a, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Improve test files for some algorithms (#263)

File size: 3.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
21#include "test_tools.h"
22#include <lemon/list_graph.h>
23#include <lemon/circulation.h>
24#include <lemon/lgf_reader.h>
25#include <lemon/concepts/digraph.h>
26#include <lemon/concepts/maps.h>
27
28using namespace lemon;
29
30char test_lgf[] =
31  "@nodes\n"
32  "label\n"
33  "0\n"
34  "1\n"
35  "2\n"
36  "3\n"
37  "4\n"
38  "5\n"
39  "@arcs\n"
40  "     lcap  ucap\n"
41  "0 1  2  10\n"
42  "0 2  2  6\n"
43  "1 3  4  7\n"
44  "1 4  0  5\n"
45  "2 4  1  3\n"
46  "3 5  3  8\n"
47  "4 5  3  7\n"
48  "@attributes\n"
49  "source 0\n"
50  "sink   5\n";
51
52void checkCirculationCompile()
53{
54  typedef int VType;
55  typedef concepts::Digraph Digraph;
56
57  typedef Digraph::Node Node;
58  typedef Digraph::Arc Arc;
59  typedef concepts::ReadMap<Arc,VType> CapMap;
60  typedef concepts::ReadMap<Node,VType> DeltaMap;
61  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
62  typedef concepts::WriteMap<Node,bool> BarrierMap;
63
64  typedef Elevator<Digraph, Digraph::Node> Elev;
65  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
66
67  Digraph g;
68  Node n;
69  Arc a;
70  CapMap lcap, ucap;
71  DeltaMap delta;
72  FlowMap flow;
73  BarrierMap bar;
74  VType v;
75  bool b;
76
77  typedef Circulation<Digraph, CapMap, CapMap, DeltaMap>
78            ::SetFlowMap<FlowMap>
79            ::SetElevator<Elev>
80            ::SetStandardElevator<LinkedElev>
81            ::Create CirculationType;
82  CirculationType circ_test(g, lcap, ucap, delta);
83  const CirculationType& const_circ_test = circ_test;
84   
85  circ_test
86    .lowerCapMap(lcap)
87    .upperCapMap(ucap)
88    .deltaMap(delta)
89    .flowMap(flow);
90
91  circ_test.init();
92  circ_test.greedyInit();
93  circ_test.start();
94  circ_test.run();
95
96  v = const_circ_test.flow(a);
97  const FlowMap& fm = const_circ_test.flowMap();
98  b = const_circ_test.barrier(n);
99  const_circ_test.barrierMap(bar);
100 
101  ignore_unused_variable_warning(fm);
102}
103
104template <class G, class LM, class UM, class DM>
105void checkCirculation(const G& g, const LM& lm, const UM& um,
106                      const DM& dm, bool find)
107{
108  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
109  bool ret = circ.run();
110  if (find) {
111    check(ret, "A feasible solution should have been found.");
112    check(circ.checkFlow(), "The found flow is corrupt.");
113    check(!circ.checkBarrier(), "A barrier should not have been found.");
114  } else {
115    check(!ret, "A feasible solution should not have been found.");
116    check(circ.checkBarrier(), "The found barrier is corrupt.");
117  }
118}
119
120int main (int, char*[])
121{
122  typedef ListDigraph Digraph;
123  DIGRAPH_TYPEDEFS(Digraph);
124
125  Digraph g;
126  IntArcMap lo(g), up(g);
127  IntNodeMap delta(g, 0);
128  Node s, t;
129
130  std::istringstream input(test_lgf);
131  DigraphReader<Digraph>(g,input).
132    arcMap("lcap", lo).
133    arcMap("ucap", up).
134    node("source",s).
135    node("sink",t).
136    run();
137
138  delta[s] = 7; delta[t] = -7;
139  checkCirculation(g, lo, up, delta, true);
140
141  delta[s] = 13; delta[t] = -13;
142  checkCirculation(g, lo, up, delta, true);
143
144  delta[s] = 6; delta[t] = -6;
145  checkCirculation(g, lo, up, delta, false);
146
147  delta[s] = 14; delta[t] = -14;
148  checkCirculation(g, lo, up, delta, false);
149
150  delta[s] = 7; delta[t] = -13;
151  checkCirculation(g, lo, up, delta, true);
152
153  delta[s] = 5; delta[t] = -15;
154  checkCirculation(g, lo, up, delta, true);
155
156  delta[s] = 10; delta[t] = -11;
157  checkCirculation(g, lo, up, delta, true);
158
159  delta[s] = 11; delta[t] = -10;
160  checkCirculation(g, lo, up, delta, false);
161
162  return 0;
163}
Note: See TracBrowser for help on using the repository browser.