COIN-OR::LEMON - Graph Library

source: lemon/test/suurballe_test.cc @ 926:ec0b1b423b8b

Last change on this file since 926:ec0b1b423b8b was 670:7c1324b35d89, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Modify the interface of Suurballe (#266, #181)

  • Move the parameters s and t from the constructor to the run() function. It makes the interface capable for multiple run(s,t,k) calls (possible improvement in the future) and it is more similar to Dijkstra.
  • Simliarly init() and findFlow(k) were replaced by init(s) and findFlow(t,k). The separation of parameters s and t is for the future plans of supporting multiple targets with one source node. For more information see #181.
  • LEMON_ASSERT for the Length type (check if it is integer).
  • Doc improvements.
  • Rearrange query functions.
  • Extend test file.
File size: 6.3 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#include <lemon/concepts/digraph.h>
26
27#include "test_tools.h"
28
29using namespace lemon;
30
31char test_lgf[] =
32  "@nodes\n"
33  "label\n"
34  "1\n"
35  "2\n"
36  "3\n"
37  "4\n"
38  "5\n"
39  "6\n"
40  "7\n"
41  "8\n"
42  "9\n"
43  "10\n"
44  "11\n"
45  "12\n"
46  "@arcs\n"
47  "      length\n"
48  " 1  2  70\n"
49  " 1  3 150\n"
50  " 1  4  80\n"
51  " 2  8  80\n"
52  " 3  5 140\n"
53  " 4  6  60\n"
54  " 4  7  80\n"
55  " 4  8 110\n"
56  " 5  7  60\n"
57  " 5 11 120\n"
58  " 6  3   0\n"
59  " 6  9 140\n"
60  " 6 10  90\n"
61  " 7  1  30\n"
62  " 8 12  60\n"
63  " 9 12  50\n"
64  "10 12  70\n"
65  "10  2 100\n"
66  "10  7  60\n"
67  "11 10  20\n"
68  "12 11  30\n"
69  "@attributes\n"
70  "source  1\n"
71  "target 12\n"
72  "@end\n";
73
74// Check the interface of Suurballe
75void checkSuurballeCompile()
76{
77  typedef int VType;
78  typedef concepts::Digraph Digraph;
79
80  typedef Digraph::Node Node;
81  typedef Digraph::Arc Arc;
82  typedef concepts::ReadMap<Arc, VType> LengthMap;
83 
84  typedef Suurballe<Digraph, LengthMap> SuurballeType;
85
86  Digraph g;
87  Node n;
88  Arc e;
89  LengthMap len;
90  SuurballeType::FlowMap flow(g);
91  SuurballeType::PotentialMap pi(g);
92
93  SuurballeType suurb_test(g, len);
94  const SuurballeType& const_suurb_test = suurb_test;
95
96  suurb_test
97    .flowMap(flow)
98    .potentialMap(pi);
99
100  int k;
101  k = suurb_test.run(n, n);
102  k = suurb_test.run(n, n, k);
103  suurb_test.init(n);
104  k = suurb_test.findFlow(n);
105  k = suurb_test.findFlow(n, k);
106  suurb_test.findPaths();
107 
108  int f;
109  VType c;
110  c = const_suurb_test.totalLength();
111  f = const_suurb_test.flow(e);
112  const SuurballeType::FlowMap& fm =
113    const_suurb_test.flowMap();
114  c = const_suurb_test.potential(n);
115  const SuurballeType::PotentialMap& pm =
116    const_suurb_test.potentialMap();
117  k = const_suurb_test.pathNum();
118  Path<Digraph> p = const_suurb_test.path(k);
119 
120  ignore_unused_variable_warning(fm);
121  ignore_unused_variable_warning(pm);
122}
123
124// Check the feasibility of the flow
125template <typename Digraph, typename FlowMap>
126bool checkFlow( const Digraph& gr, const FlowMap& flow,
127                typename Digraph::Node s, typename Digraph::Node t,
128                int value )
129{
130  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
131  for (ArcIt e(gr); e != INVALID; ++e)
132    if (!(flow[e] == 0 || flow[e] == 1)) return false;
133
134  for (NodeIt n(gr); n != INVALID; ++n) {
135    int sum = 0;
136    for (OutArcIt e(gr, n); e != INVALID; ++e)
137      sum += flow[e];
138    for (InArcIt e(gr, n); e != INVALID; ++e)
139      sum -= flow[e];
140    if (n == s && sum != value) return false;
141    if (n == t && sum != -value) return false;
142    if (n != s && n != t && sum != 0) return false;
143  }
144
145  return true;
146}
147
148// Check the optimalitiy of the flow
149template < typename Digraph, typename CostMap,
150           typename FlowMap, typename PotentialMap >
151bool checkOptimality( const Digraph& gr, const CostMap& cost,
152                      const FlowMap& flow, const PotentialMap& pi )
153{
154  // Check the "Complementary Slackness" optimality condition
155  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
156  bool opt = true;
157  for (ArcIt e(gr); e != INVALID; ++e) {
158    typename CostMap::Value red_cost =
159      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
160    opt = (flow[e] == 0 && red_cost >= 0) ||
161          (flow[e] == 1 && red_cost <= 0);
162    if (!opt) break;
163  }
164  return opt;
165}
166
167// Check a path
168template <typename Digraph, typename Path>
169bool checkPath( const Digraph& gr, const Path& path,
170                typename Digraph::Node s, typename Digraph::Node t)
171{
172  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
173  Node n = s;
174  for (int i = 0; i < path.length(); ++i) {
175    if (gr.source(path.nth(i)) != n) return false;
176    n = gr.target(path.nth(i));
177  }
178  return n == t;
179}
180
181
182int main()
183{
184  DIGRAPH_TYPEDEFS(ListDigraph);
185
186  // Read the test digraph
187  ListDigraph digraph;
188  ListDigraph::ArcMap<int> length(digraph);
189  Node s, t;
190
191  std::istringstream input(test_lgf);
192  DigraphReader<ListDigraph>(digraph, input).
193    arcMap("length", length).
194    node("source", s).
195    node("target", t).
196    run();
197
198  // Find 2 paths
199  {
200    Suurballe<ListDigraph> suurballe(digraph, length);
201    check(suurballe.run(s, t) == 2, "Wrong number of paths");
202    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
203          "The flow is not feasible");
204    check(suurballe.totalLength() == 510, "The flow is not optimal");
205    check(checkOptimality(digraph, length, suurballe.flowMap(),
206                          suurballe.potentialMap()),
207          "Wrong potentials");
208    for (int i = 0; i < suurballe.pathNum(); ++i)
209      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
210  }
211
212  // Find 3 paths
213  {
214    Suurballe<ListDigraph> suurballe(digraph, length);
215    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
217          "The flow is not feasible");
218    check(suurballe.totalLength() == 1040, "The flow is not optimal");
219    check(checkOptimality(digraph, length, suurballe.flowMap(),
220                          suurballe.potentialMap()),
221          "Wrong potentials");
222    for (int i = 0; i < suurballe.pathNum(); ++i)
223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
224  }
225
226  // Find 5 paths (only 3 can be found)
227  {
228    Suurballe<ListDigraph> suurballe(digraph, length);
229    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
230    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
231          "The flow is not feasible");
232    check(suurballe.totalLength() == 1040, "The flow is not optimal");
233    check(checkOptimality(digraph, length, suurballe.flowMap(),
234                          suurballe.potentialMap()),
235          "Wrong potentials");
236    for (int i = 0; i < suurballe.pathNum(); ++i)
237      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
238  }
239
240  return 0;
241}
Note: See TracBrowser for help on using the repository browser.