COIN-OR::LEMON - Graph Library

source: lemon-main/test/circulation_test.cc @ 998:7fdaa05a69a1

Last change on this file since 998:7fdaa05a69a1 was 877:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 15 years ago

Unify the sources (#339)

File size: 4.1 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
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> SupplyMap;
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  SupplyMap supply;
72  FlowMap flow;
73  BarrierMap bar;
74  VType v;
75  bool b;
76
77  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
78            ::SetFlowMap<FlowMap>
79            ::SetElevator<Elev>
80            ::SetStandardElevator<LinkedElev>
81            ::Create CirculationType;
82  CirculationType circ_test(g, lcap, ucap, supply);
83  const CirculationType& const_circ_test = circ_test;
84
85  circ_test
86    .lowerMap(lcap)
87    .upperMap(ucap)
88    .supplyMap(supply)
89    .flowMap(flow);
90
91  const CirculationType::Elevator& elev = const_circ_test.elevator();
92  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
93  CirculationType::Tolerance tol = const_circ_test.tolerance();
94  circ_test.tolerance(tol);
95
96  circ_test.init();
97  circ_test.greedyInit();
98  circ_test.start();
99  circ_test.run();
100
101  v = const_circ_test.flow(a);
102  const FlowMap& fm = const_circ_test.flowMap();
103  b = const_circ_test.barrier(n);
104  const_circ_test.barrierMap(bar);
105
106  ignore_unused_variable_warning(fm);
107}
108
109template <class G, class LM, class UM, class DM>
110void checkCirculation(const G& g, const LM& lm, const UM& um,
111                      const DM& dm, bool find)
112{
113  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
114  bool ret = circ.run();
115  if (find) {
116    check(ret, "A feasible solution should have been found.");
117    check(circ.checkFlow(), "The found flow is corrupt.");
118    check(!circ.checkBarrier(), "A barrier should not have been found.");
119  } else {
120    check(!ret, "A feasible solution should not have been found.");
121    check(circ.checkBarrier(), "The found barrier is corrupt.");
122  }
123}
124
125int main (int, char*[])
126{
127  typedef ListDigraph Digraph;
128  DIGRAPH_TYPEDEFS(Digraph);
129
130  Digraph g;
131  IntArcMap lo(g), up(g);
132  IntNodeMap delta(g, 0);
133  Node s, t;
134
135  std::istringstream input(test_lgf);
136  DigraphReader<Digraph>(g,input).
137    arcMap("lcap", lo).
138    arcMap("ucap", up).
139    node("source",s).
140    node("sink",t).
141    run();
142
143  delta[s] = 7; delta[t] = -7;
144  checkCirculation(g, lo, up, delta, true);
145
146  delta[s] = 13; delta[t] = -13;
147  checkCirculation(g, lo, up, delta, true);
148
149  delta[s] = 6; delta[t] = -6;
150  checkCirculation(g, lo, up, delta, false);
151
152  delta[s] = 14; delta[t] = -14;
153  checkCirculation(g, lo, up, delta, false);
154
155  delta[s] = 7; delta[t] = -13;
156  checkCirculation(g, lo, up, delta, true);
157
158  delta[s] = 5; delta[t] = -15;
159  checkCirculation(g, lo, up, delta, true);
160
161  delta[s] = 10; delta[t] = -11;
162  checkCirculation(g, lo, up, delta, true);
163
164  delta[s] = 11; delta[t] = -10;
165  checkCirculation(g, lo, up, delta, false);
166
167  return 0;
168}
Note: See TracBrowser for help on using the repository browser.