COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/arborescence_test.cc @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 3.5 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 <set>
21#include <vector>
22#include <iterator>
23
24#include <cmath>
25#include <cstdlib>
26
27#include <lemon/smart_graph.h>
28#include <lemon/min_cost_arborescence.h>
29
30#include <lemon/graph_utils.h>
31#include <lemon/time_measure.h>
32
33#include <lemon/tolerance.h>
34
35#include "test_tools.h"
36
37using namespace lemon;
38using namespace std;
39
40const int NODES = 10;
41const int EDGES = 22;
42
43int sourceNode = 0;
44
45int sources[EDGES] = {
46  1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
47  4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
48  1, 0
49};
50
51int targets[EDGES] = {
52  8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
53  3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
54  1, 3
55};
56
57double costs[EDGES] = {
58  107.444, 70.3069, 46.0496, 28.3962, 91.4325,
59  76.9443, 61.986, 39.3754, 74.9575, 39.3153,
60  45.7094, 34.6184, 100.156, 95.726, 22.3429,
61  31.587, 51.6972, 29.6773, 115.038, 32.4137,
62  60.0038, 40.1237
63};
64
65
66
67int main() {
68  typedef SmartGraph Graph;
69  GRAPH_TYPEDEFS(Graph);
70
71  typedef Graph::EdgeMap<double> CostMap;
72
73  Graph graph;
74  CostMap cost(graph);
75  vector<Node> nodes;
76 
77  for (int i = 0; i < NODES; ++i) {
78    nodes.push_back(graph.addNode());
79  }
80
81  for (int i = 0; i < EDGES; ++i) {
82    Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
83    cost[edge] = costs[i];
84  }
85
86  Node source = nodes[sourceNode];
87
88  MinCostArborescence<Graph, CostMap> mca(graph, cost);
89  mca.run(source);
90
91  vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
92
93  for (int i = 0; i < mca.dualSize(); ++i) {
94    dualSolution[i].first = mca.dualValue(i);
95    for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i);
96         it != INVALID; ++it) {
97      dualSolution[i].second.insert(it);
98    }
99  }
100
101  Tolerance<double> tolerance;
102
103  for (EdgeIt it(graph); it != INVALID; ++it) {
104    if (mca.reached(graph.source(it))) {
105      double sum = 0.0;
106      for (int i = 0; i < int(dualSolution.size()); ++i) {
107        if (dualSolution[i].second.find(graph.target(it))
108            != dualSolution[i].second.end() &&
109            dualSolution[i].second.find(graph.source(it))
110            == dualSolution[i].second.end()) {
111          sum += dualSolution[i].first;
112        }
113      }
114      if (mca.arborescence(it)) {
115        check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
116      }
117      check(!tolerance.less(cost[it], sum), "INVALID DUAL");
118    }
119  }
120
121
122  check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
123               "INVALID DUAL");
124
125
126  check(mca.reached(source), "INVALID ARBORESCENCE");
127  for (EdgeIt it(graph); it != INVALID; ++it) {
128    check(!mca.reached(graph.source(it)) ||
129                 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
130  }
131
132  for (NodeIt it(graph); it != INVALID; ++it) {
133    if (!mca.reached(it)) continue;
134    int cnt = 0;
135    for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
136      if (mca.arborescence(jt)) {
137        ++cnt;
138      }
139    }
140    check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
141  }
142 
143  return 0;
144}
Note: See TracBrowser for help on using the repository browser.