Lemon Graph Format uses label instead of id named map.
7 #include <lemon/smart_graph.h>
8 #include <lemon/dijkstra.h>
9 #include <lemon/floyd_warshall.h>
10 #include <lemon/johnson.h>
12 #include <lemon/fib_heap.h>
14 #include <lemon/time_measure.h>
15 #include "test_tools.h"
17 using namespace lemon;
20 int main(int argc, const char *argv[]) {
22 typedef SmartGraph Graph;
23 typedef Graph::Node Node;
24 typedef Graph::Edge Edge;
25 typedef Graph::NodeIt NodeIt;
26 typedef Graph::EdgeIt EdgeIt;
28 typedef Graph::EdgeMap<double> LengthMap;
29 typedef Graph::NodeMap<double> DistMap;
31 const int n = argc > 1 ? atoi(argv[1]) : 20;
32 const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n));
33 const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0;
36 LengthMap length(graph);
40 for (int i = 0; i < n; ++i) {
41 Node node = graph.addNode();
42 nodes.push_back(node);
43 shift[node] = m * (double)rand() / (RAND_MAX + 1.0);
46 for (int i = 0; i < e; ++i) {
47 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
48 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
49 double c = m * (double)rand() / (RAND_MAX + 1.0);
50 Edge edge = graph.addEdge(nodes[s], nodes[t]);
51 length[edge] = c - shift[nodes[s]] + shift[nodes[t]];
54 Johnson<Graph, LengthMap> johnson(graph, length);
58 cout << "Johnson: " << timer << endl;
61 typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap;
62 Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap>
63 ::Create fibJohnson(graph, length);
67 cout << "Johnson with fibonacci heap: " << timer << endl;
70 FloydWarshall<Graph, LengthMap> floyd(graph, length);
74 cout << "FloydWarshall: " << timer << endl;
77 for (NodeIt it(graph); it != INVALID; ++it) {
78 for (NodeIt jt(graph); jt != INVALID; ++jt) {
79 check(johnson.connected(it, jt) == floyd.connected(it, jt),
80 "Wrong connection in all pairs shortest path");
81 check(johnson.connected(it, jt) == fibJohnson.connected(it, jt),
82 "Wrong connection in all pairs shortest path");
83 if (johnson.connected(it, jt)) {
84 check(johnson.dist(it, jt) == floyd.dist(it, jt),
85 "Wrong distance in all pairs shortest path");
86 check(johnson.dist(it, jt) == fibJohnson.dist(it, jt),
87 "Wrong distance in all pairs shortest path");
89 check(johnson.dist(it, jt) ==
90 johnson.dist(it, johnson.predNode(it, jt)) +
91 length[johnson.predEdge(it, jt)],
92 "Wrong edge in all pairs shortest path");
93 check(fibJohnson.dist(it, jt) ==
94 fibJohnson.dist(it, fibJohnson.predNode(it, jt)) +
95 length[fibJohnson.predEdge(it, jt)],
96 "Wrong edge in all pairs shortest path");
97 check(floyd.dist(it, jt) ==
98 floyd.dist(it, floyd.predNode(it, jt)) +
99 length[floyd.predEdge(it, jt)],
100 "Wrong edge in all pairs shortest path");