COIN-OR::LEMON - Graph Library

source: lemon/test/circulation_test.cc @ 1173:d216e1c8b3fa

Last change on this file since 1173:d216e1c8b3fa was 1173:d216e1c8b3fa, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge #453 to branches >=1.2

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