Bug fixes in min cost flow files.
Use enum type instead of static constants in NetworkSimplex to avoid
linker errors.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
22 #include <lemon/math.h>
25 #include <lemon/smart_graph.h>
26 #include <lemon/dijkstra.h>
27 #include <lemon/floyd_warshall.h>
28 #include <lemon/johnson.h>
30 #include <lemon/fib_heap.h>
32 #include <lemon/path.h>
34 #include <lemon/time_measure.h>
35 #include "test_tools.h"
37 using namespace lemon;
40 int main(int argc, const char *argv[]) {
41 typedef SmartGraph Graph;
42 typedef Graph::Node Node;
43 typedef Graph::Edge Edge;
44 typedef Graph::NodeIt NodeIt;
45 typedef Graph::EdgeIt EdgeIt;
47 typedef Graph::EdgeMap<int> LengthMap;
48 typedef Graph::NodeMap<int> DistMap;
50 const int n = argc > 1 ? atoi(argv[1]) : 20;
51 const int e = argc > 2 ? atoi(argv[2]) : int(n * log(double(n)));
52 const int m = argc > 3 ? atoi(argv[3]) : 100;
55 LengthMap length(graph);
59 for (int i = 0; i < n; ++i) {
60 Node node = graph.addNode();
61 nodes.push_back(node);
65 for (int i = 0; i < e; ++i) {
68 Edge edge = graph.addEdge(nodes[s], nodes[t]);
69 length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]];
72 Johnson<Graph, LengthMap> johnson(graph, length);
76 cout << "Johnson: " << timer << endl;
79 typedef FibHeap<int, Graph::NodeMap<int> > IntFibHeap;
80 Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap>
81 ::Create fibJohnson(graph, length);
85 cout << "Johnson with fibonacci heap: " << timer << endl;
88 FloydWarshall<Graph, LengthMap> floyd(graph, length);
92 cout << "FloydWarshall: " << timer << endl;
95 bool checked_path = false;
97 for (NodeIt it(graph); it != INVALID; ++it) {
98 for (NodeIt jt(graph); jt != INVALID; ++jt) {
99 check(johnson.connected(it, jt) == floyd.connected(it, jt),
100 "Wrong connection in all pairs shortest path");
101 check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
102 "Wrong connection in all pairs shortest path");
103 if (johnson.connected(it, jt)) {
104 if (it != jt && !checked_path) {
106 Path<Graph> path = johnson.path(it, jt);
107 check(checkPath(graph, path), "Wrong path.");
108 check(pathSource(graph, path) == it, "Wrong path.");
109 check(pathTarget(graph, path) == jt, "Wrong path.");
112 Path<Graph> path = floyd.path(it, jt);
113 check(checkPath(graph, path), "Wrong path.");
114 check(pathSource(graph, path) == it, "Wrong path.");
115 check(pathTarget(graph, path) == jt, "Wrong path.");
118 std::cout << "Path checked" << std::endl;
120 check(johnson.dist(it, jt) == floyd.dist(it, jt),
121 "Wrong distance in all pairs shortest path");
122 check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
123 "Wrong distance in all pairs shortest path");
125 check(johnson.dist(it, jt) ==
126 johnson.dist(it, johnson.predNode(it, jt)) +
127 length[johnson.predEdge(it, jt)],
128 "Wrong edge in all pairs shortest path");
129 check(fibJohnson.dist(it, jt) ==
130 fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
131 length[fibJohnson.predEdge(it, jt)],
132 "Wrong edge in all pairs shortest path");
133 check(floyd.dist(it, jt) ==
134 floyd.dist(it, floyd.predNode(it, jt)) +
135 length[floyd.predEdge(it, jt)],
136 "Wrong edge in all pairs shortest path");