COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/suurballe_test.cc

Last change on this file was 983:8b2d4e5d96e4, checked in by Alpar Juttner <alpar@…>, 6 years ago

Merge #294 to branches >=1.2

File size: 7.2 KB
RevLine 
[440]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[345]2 *
[440]3 * This file is a part of LEMON, a generic C++ optimization library.
[345]4 *
[877]5 * Copyright (C) 2003-2010
[345]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>
[623]25#include <lemon/concepts/digraph.h>
[857]26#include <lemon/concepts/heap.h>
[345]27
28#include "test_tools.h"
29
30using namespace lemon;
31
[423]32char test_lgf[] =
33  "@nodes\n"
[623]34  "label\n"
35  "1\n"
36  "2\n"
37  "3\n"
38  "4\n"
39  "5\n"
40  "6\n"
41  "7\n"
42  "8\n"
43  "9\n"
44  "10\n"
45  "11\n"
46  "12\n"
[423]47  "@arcs\n"
[623]48  "      length\n"
49  " 1  2  70\n"
50  " 1  3 150\n"
51  " 1  4  80\n"
52  " 2  8  80\n"
53  " 3  5 140\n"
54  " 4  6  60\n"
55  " 4  7  80\n"
56  " 4  8 110\n"
57  " 5  7  60\n"
58  " 5 11 120\n"
59  " 6  3   0\n"
60  " 6  9 140\n"
61  " 6 10  90\n"
62  " 7  1  30\n"
63  " 8 12  60\n"
64  " 9 12  50\n"
65  "10 12  70\n"
66  "10  2 100\n"
67  "10  7  60\n"
68  "11 10  20\n"
69  "12 11  30\n"
[423]70  "@attributes\n"
71  "source  1\n"
72  "target 12\n"
73  "@end\n";
74
[623]75// Check the interface of Suurballe
76void checkSuurballeCompile()
77{
78  typedef int VType;
79  typedef concepts::Digraph Digraph;
80
81  typedef Digraph::Node Node;
82  typedef Digraph::Arc Arc;
83  typedef concepts::ReadMap<Arc, VType> LengthMap;
[877]84
[857]85  typedef Suurballe<Digraph, LengthMap> ST;
86  typedef Suurballe<Digraph, LengthMap>
87    ::SetFlowMap<ST::FlowMap>
88    ::SetPotentialMap<ST::PotentialMap>
89    ::SetPath<SimplePath<Digraph> >
90    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
91    ::Create SuurballeType;
[623]92
93  Digraph g;
94  Node n;
95  Arc e;
96  LengthMap len;
97  SuurballeType::FlowMap flow(g);
98  SuurballeType::PotentialMap pi(g);
99
100  SuurballeType suurb_test(g, len);
101  const SuurballeType& const_suurb_test = suurb_test;
102
103  suurb_test
104    .flowMap(flow)
105    .potentialMap(pi);
106
107  int k;
108  k = suurb_test.run(n, n);
109  k = suurb_test.run(n, n, k);
110  suurb_test.init(n);
[854]111  suurb_test.fullInit(n);
112  suurb_test.start(n);
113  suurb_test.start(n, k);
[623]114  k = suurb_test.findFlow(n);
115  k = suurb_test.findFlow(n, k);
116  suurb_test.findPaths();
[877]117
[623]118  int f;
119  VType c;
[982]120  ::lemon::ignore_unused_variable_warning(f,c);
[969]121
[623]122  c = const_suurb_test.totalLength();
123  f = const_suurb_test.flow(e);
124  const SuurballeType::FlowMap& fm =
125    const_suurb_test.flowMap();
126  c = const_suurb_test.potential(n);
127  const SuurballeType::PotentialMap& pm =
128    const_suurb_test.potentialMap();
129  k = const_suurb_test.pathNum();
130  Path<Digraph> p = const_suurb_test.path(k);
[877]131
[982]132  ::lemon::ignore_unused_variable_warning(fm);
133  ::lemon::ignore_unused_variable_warning(pm);
[623]134}
135
[346]136// Check the feasibility of the flow
[345]137template <typename Digraph, typename FlowMap>
[440]138bool checkFlow( const Digraph& gr, const FlowMap& flow,
[345]139                typename Digraph::Node s, typename Digraph::Node t,
140                int value )
141{
142  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
143  for (ArcIt e(gr); e != INVALID; ++e)
144    if (!(flow[e] == 0 || flow[e] == 1)) return false;
145
146  for (NodeIt n(gr); n != INVALID; ++n) {
147    int sum = 0;
148    for (OutArcIt e(gr, n); e != INVALID; ++e)
149      sum += flow[e];
150    for (InArcIt e(gr, n); e != INVALID; ++e)
151      sum -= flow[e];
152    if (n == s && sum != value) return false;
153    if (n == t && sum != -value) return false;
154    if (n != s && n != t && sum != 0) return false;
155  }
156
157  return true;
158}
159
[346]160// Check the optimalitiy of the flow
[440]161template < typename Digraph, typename CostMap,
[345]162           typename FlowMap, typename PotentialMap >
163bool checkOptimality( const Digraph& gr, const CostMap& cost,
164                      const FlowMap& flow, const PotentialMap& pi )
165{
[346]166  // Check the "Complementary Slackness" optimality condition
[345]167  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
168  bool opt = true;
169  for (ArcIt e(gr); e != INVALID; ++e) {
170    typename CostMap::Value red_cost =
171      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
172    opt = (flow[e] == 0 && red_cost >= 0) ||
173          (flow[e] == 1 && red_cost <= 0);
174    if (!opt) break;
175  }
176  return opt;
177}
178
[346]179// Check a path
180template <typename Digraph, typename Path>
[345]181bool checkPath( const Digraph& gr, const Path& path,
182                typename Digraph::Node s, typename Digraph::Node t)
183{
184  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
185  Node n = s;
186  for (int i = 0; i < path.length(); ++i) {
187    if (gr.source(path.nth(i)) != n) return false;
188    n = gr.target(path.nth(i));
189  }
190  return n == t;
191}
192
193
194int main()
195{
196  DIGRAPH_TYPEDEFS(ListDigraph);
197
[346]198  // Read the test digraph
[345]199  ListDigraph digraph;
200  ListDigraph::ArcMap<int> length(digraph);
[623]201  Node s, t;
[345]202
[423]203  std::istringstream input(test_lgf);
[345]204  DigraphReader<ListDigraph>(digraph, input).
[623]205    arcMap("length", length).
206    node("source", s).
207    node("target", t).
[345]208    run();
[440]209
[858]210  // Check run()
[345]211  {
[623]212    Suurballe<ListDigraph> suurballe(digraph, length);
[877]213
[858]214    // Find 2 paths
[623]215    check(suurballe.run(s, t) == 2, "Wrong number of paths");
216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
[345]217          "The flow is not feasible");
218    check(suurballe.totalLength() == 510, "The flow is not optimal");
[440]219    check(checkOptimality(digraph, length, suurballe.flowMap(),
[345]220                          suurballe.potentialMap()),
221          "Wrong potentials");
222    for (int i = 0; i < suurballe.pathNum(); ++i)
[623]223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
[345]224
[858]225    // Find 3 paths
[623]226    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
227    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
[345]228          "The flow is not feasible");
229    check(suurballe.totalLength() == 1040, "The flow is not optimal");
[440]230    check(checkOptimality(digraph, length, suurballe.flowMap(),
[345]231                          suurballe.potentialMap()),
232          "Wrong potentials");
233    for (int i = 0; i < suurballe.pathNum(); ++i)
[623]234      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
[345]235
[858]236    // Find 5 paths (only 3 can be found)
[623]237    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
238    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
[345]239          "The flow is not feasible");
240    check(suurballe.totalLength() == 1040, "The flow is not optimal");
[440]241    check(checkOptimality(digraph, length, suurballe.flowMap(),
[345]242                          suurballe.potentialMap()),
243          "Wrong potentials");
244    for (int i = 0; i < suurballe.pathNum(); ++i)
[623]245      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
[345]246  }
247
[858]248  // Check fullInit() + start()
249  {
250    Suurballe<ListDigraph> suurballe(digraph, length);
251    suurballe.fullInit(s);
[877]252
[858]253    // Find 2 paths
254    check(suurballe.start(t) == 2, "Wrong number of paths");
255    check(suurballe.totalLength() == 510, "The flow is not optimal");
256
257    // Find 3 paths
258    check(suurballe.start(t, 3) == 3, "Wrong number of paths");
259    check(suurballe.totalLength() == 1040, "The flow is not optimal");
260
261    // Find 5 paths (only 3 can be found)
262    check(suurballe.start(t, 5) == 3, "Wrong number of paths");
263    check(suurballe.totalLength() == 1040, "The flow is not optimal");
264  }
[623]265
[345]266  return 0;
267}
Note: See TracBrowser for help on using the repository browser.