COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/suurballe_test.cc @ 346:7f26c4b32651

Last change on this file since 346:7f26c4b32651 was 346:7f26c4b32651, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Minor doc improvements related to Suurballe (#47)

File size: 5.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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#include <fstream>
21
22#include <lemon/list_graph.h>
23#include <lemon/lgf_reader.h>
24#include <lemon/path.h>
25#include <lemon/suurballe.h>
26
27#include "test_tools.h"
28
29using namespace lemon;
30
31// Check the feasibility of the flow
32template <typename Digraph, typename FlowMap>
33bool checkFlow( const Digraph& gr, const FlowMap& flow,
34                typename Digraph::Node s, typename Digraph::Node t,
35                int value )
36{
37  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
38  for (ArcIt e(gr); e != INVALID; ++e)
39    if (!(flow[e] == 0 || flow[e] == 1)) return false;
40
41  for (NodeIt n(gr); n != INVALID; ++n) {
42    int sum = 0;
43    for (OutArcIt e(gr, n); e != INVALID; ++e)
44      sum += flow[e];
45    for (InArcIt e(gr, n); e != INVALID; ++e)
46      sum -= flow[e];
47    if (n == s && sum != value) return false;
48    if (n == t && sum != -value) return false;
49    if (n != s && n != t && sum != 0) return false;
50  }
51
52  return true;
53}
54
55// Check the optimalitiy of the flow
56template < typename Digraph, typename CostMap,
57           typename FlowMap, typename PotentialMap >
58bool checkOptimality( const Digraph& gr, const CostMap& cost,
59                      const FlowMap& flow, const PotentialMap& pi )
60{
61  // Check the "Complementary Slackness" optimality condition
62  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
63  bool opt = true;
64  for (ArcIt e(gr); e != INVALID; ++e) {
65    typename CostMap::Value red_cost =
66      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
67    opt = (flow[e] == 0 && red_cost >= 0) ||
68          (flow[e] == 1 && red_cost <= 0);
69    if (!opt) break;
70  }
71  return opt;
72}
73
74// Check a path
75template <typename Digraph, typename Path>
76bool checkPath( const Digraph& gr, const Path& path,
77                typename Digraph::Node s, typename Digraph::Node t)
78{
79  // Check the "Complementary Slackness" optimality condition
80  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
81  Node n = s;
82  for (int i = 0; i < path.length(); ++i) {
83    if (gr.source(path.nth(i)) != n) return false;
84    n = gr.target(path.nth(i));
85  }
86  return n == t;
87}
88
89
90int main()
91{
92  DIGRAPH_TYPEDEFS(ListDigraph);
93
94  // Read the test digraph
95  ListDigraph digraph;
96  ListDigraph::ArcMap<int> length(digraph);
97  Node source, target;
98
99  std::string fname;
100  if(getenv("srcdir"))
101    fname = std::string(getenv("srcdir"));
102  else fname = ".";
103  fname += "/test/min_cost_flow_test.lgf";
104
105  std::ifstream input(fname.c_str());
106  check(input, "Input file '" << fname << "' not found");
107  DigraphReader<ListDigraph>(digraph, input).
108    arcMap("cost", length).
109    node("source", source).
110    node("target", target).
111    run();
112  input.close();
113 
114  // Find 2 paths
115  {
116    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
117    check(suurballe.run(2) == 2, "Wrong number of paths");
118    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
119          "The flow is not feasible");
120    check(suurballe.totalLength() == 510, "The flow is not optimal");
121    check(checkOptimality(digraph, length, suurballe.flowMap(),
122                          suurballe.potentialMap()),
123          "Wrong potentials");
124    for (int i = 0; i < suurballe.pathNum(); ++i)
125      check(checkPath(digraph, suurballe.path(i), source, target),
126            "Wrong path");
127  }
128
129  // Find 3 paths
130  {
131    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
132    check(suurballe.run(3) == 3, "Wrong number of paths");
133    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
134          "The flow is not feasible");
135    check(suurballe.totalLength() == 1040, "The flow is not optimal");
136    check(checkOptimality(digraph, length, suurballe.flowMap(),
137                          suurballe.potentialMap()),
138          "Wrong potentials");
139    for (int i = 0; i < suurballe.pathNum(); ++i)
140      check(checkPath(digraph, suurballe.path(i), source, target),
141            "Wrong path");
142  }
143
144  // Find 5 paths (only 3 can be found)
145  {
146    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
147    check(suurballe.run(5) == 3, "Wrong number of paths");
148    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
149          "The flow is not feasible");
150    check(suurballe.totalLength() == 1040, "The flow is not optimal");
151    check(checkOptimality(digraph, length, suurballe.flowMap(),
152                          suurballe.potentialMap()),
153          "Wrong potentials");
154    for (int i = 0; i < suurballe.pathNum(); ++i)
155      check(checkPath(digraph, suurballe.path(i), source, target),
156            "Wrong path");
157  }
158
159  return 0;
160}
Note: See TracBrowser for help on using the repository browser.