COIN-OR::LEMON - Graph Library

source: lemon/test/circulation_test.cc @ 463:88ed40ad0d4f

Last change on this file since 463:88ed40ad0d4f was 463:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 15 years ago

Happy New Year again

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