COIN-OR::LEMON - Graph Library

source: lemon-main/test/suurballe_test.cc @ 558:f53d641aa967

Last change on this file since 558:f53d641aa967 was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 6.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-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 <lemon/list_graph.h>
22#include <lemon/lgf_reader.h>
23#include <lemon/path.h>
24#include <lemon/suurballe.h>
25
26#include "test_tools.h"
27
28using namespace lemon;
29
30char test_lgf[] =
31  "@nodes\n"
32  "label supply1 supply2 supply3\n"
33  "1     0        20      27\n"
34  "2     0       -4        0\n"
35  "3     0        0        0\n"
36  "4     0        0        0\n"
37  "5     0        9        0\n"
38  "6     0       -6        0\n"
39  "7     0        0        0\n"
40  "8     0        0        0\n"
41  "9     0        3        0\n"
42  "10    0       -2        0\n"
43  "11    0        0        0\n"
44  "12    0       -20     -27\n"
45  "@arcs\n"
46  "      cost capacity lower1 lower2\n"
47  " 1  2  70  11       0      8\n"
48  " 1  3 150   3       0      1\n"
49  " 1  4  80  15       0      2\n"
50  " 2  8  80  12       0      0\n"
51  " 3  5 140   5       0      3\n"
52  " 4  6  60  10       0      1\n"
53  " 4  7  80   2       0      0\n"
54  " 4  8 110   3       0      0\n"
55  " 5  7  60  14       0      0\n"
56  " 5 11 120  12       0      0\n"
57  " 6  3   0   3       0      0\n"
58  " 6  9 140   4       0      0\n"
59  " 6 10  90   8       0      0\n"
60  " 7  1  30   5       0      0\n"
61  " 8 12  60  16       0      4\n"
62  " 9 12  50   6       0      0\n"
63  "10 12  70  13       0      5\n"
64  "10  2 100   7       0      0\n"
65  "10  7  60  10       0      0\n"
66  "11 10  20  14       0      6\n"
67  "12 11  30  10       0      0\n"
68  "@attributes\n"
69  "source  1\n"
70  "target 12\n"
71  "@end\n";
72
73// Check the feasibility of the flow
74template <typename Digraph, typename FlowMap>
75bool checkFlow( const Digraph& gr, const FlowMap& flow,
76                typename Digraph::Node s, typename Digraph::Node t,
77                int value )
78{
79  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
80  for (ArcIt e(gr); e != INVALID; ++e)
81    if (!(flow[e] == 0 || flow[e] == 1)) return false;
82
83  for (NodeIt n(gr); n != INVALID; ++n) {
84    int sum = 0;
85    for (OutArcIt e(gr, n); e != INVALID; ++e)
86      sum += flow[e];
87    for (InArcIt e(gr, n); e != INVALID; ++e)
88      sum -= flow[e];
89    if (n == s && sum != value) return false;
90    if (n == t && sum != -value) return false;
91    if (n != s && n != t && sum != 0) return false;
92  }
93
94  return true;
95}
96
97// Check the optimalitiy of the flow
98template < typename Digraph, typename CostMap,
99           typename FlowMap, typename PotentialMap >
100bool checkOptimality( const Digraph& gr, const CostMap& cost,
101                      const FlowMap& flow, const PotentialMap& pi )
102{
103  // Check the "Complementary Slackness" optimality condition
104  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
105  bool opt = true;
106  for (ArcIt e(gr); e != INVALID; ++e) {
107    typename CostMap::Value red_cost =
108      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
109    opt = (flow[e] == 0 && red_cost >= 0) ||
110          (flow[e] == 1 && red_cost <= 0);
111    if (!opt) break;
112  }
113  return opt;
114}
115
116// Check a path
117template <typename Digraph, typename Path>
118bool checkPath( const Digraph& gr, const Path& path,
119                typename Digraph::Node s, typename Digraph::Node t)
120{
121  // Check the "Complementary Slackness" optimality condition
122  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
123  Node n = s;
124  for (int i = 0; i < path.length(); ++i) {
125    if (gr.source(path.nth(i)) != n) return false;
126    n = gr.target(path.nth(i));
127  }
128  return n == t;
129}
130
131
132int main()
133{
134  DIGRAPH_TYPEDEFS(ListDigraph);
135
136  // Read the test digraph
137  ListDigraph digraph;
138  ListDigraph::ArcMap<int> length(digraph);
139  Node source, target;
140
141  std::istringstream input(test_lgf);
142  DigraphReader<ListDigraph>(digraph, input).
143    arcMap("cost", length).
144    node("source", source).
145    node("target", target).
146    run();
147
148  // Find 2 paths
149  {
150    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
151    check(suurballe.run(2) == 2, "Wrong number of paths");
152    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
153          "The flow is not feasible");
154    check(suurballe.totalLength() == 510, "The flow is not optimal");
155    check(checkOptimality(digraph, length, suurballe.flowMap(),
156                          suurballe.potentialMap()),
157          "Wrong potentials");
158    for (int i = 0; i < suurballe.pathNum(); ++i)
159      check(checkPath(digraph, suurballe.path(i), source, target),
160            "Wrong path");
161  }
162
163  // Find 3 paths
164  {
165    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
166    check(suurballe.run(3) == 3, "Wrong number of paths");
167    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
168          "The flow is not feasible");
169    check(suurballe.totalLength() == 1040, "The flow is not optimal");
170    check(checkOptimality(digraph, length, suurballe.flowMap(),
171                          suurballe.potentialMap()),
172          "Wrong potentials");
173    for (int i = 0; i < suurballe.pathNum(); ++i)
174      check(checkPath(digraph, suurballe.path(i), source, target),
175            "Wrong path");
176  }
177
178  // Find 5 paths (only 3 can be found)
179  {
180    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
181    check(suurballe.run(5) == 3, "Wrong number of paths");
182    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
183          "The flow is not feasible");
184    check(suurballe.totalLength() == 1040, "The flow is not optimal");
185    check(checkOptimality(digraph, length, suurballe.flowMap(),
186                          suurballe.potentialMap()),
187          "Wrong potentials");
188    for (int i = 0; i < suurballe.pathNum(); ++i)
189      check(checkPath(digraph, suurballe.path(i), source, target),
190            "Wrong path");
191  }
192
193  return 0;
194}
Note: See TracBrowser for help on using the repository browser.