/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2006 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include #include #include #include #include #include #include #include #include #include "test_tools.h" using namespace lemon; using namespace std; int main(int argc, const char *argv[]) { typedef SmartGraph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; typedef Graph::NodeIt NodeIt; typedef Graph::EdgeIt EdgeIt; typedef Graph::EdgeMap LengthMap; typedef Graph::NodeMap DistMap; const int n = argc > 1 ? atoi(argv[1]) : 20; const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n)); const int m = argc > 3 ? atoi(argv[3]) : 100; Graph graph; LengthMap length(graph); vector nodes; DistMap shift(graph); for (int i = 0; i < n; ++i) { Node node = graph.addNode(); nodes.push_back(node); shift[node] = rnd[m]; } for (int i = 0; i < e; ++i) { int s = rnd[n]; int t = rnd[n]; Edge edge = graph.addEdge(nodes[s], nodes[t]); length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]]; } Johnson johnson(graph, length); { Timer timer; johnson.run(); cout << "Johnson: " << timer << endl; } typedef FibHeap > IntFibHeap; Johnson::DefStandardHeap ::Create fibJohnson(graph, length); { Timer timer; fibJohnson.run(); cout << "Johnson with fibonacci heap: " << timer << endl; } FloydWarshall floyd(graph, length); { Timer timer; floyd.run(); cout << "FloydWarshall: " << timer << endl; } for (NodeIt it(graph); it != INVALID; ++it) { for (NodeIt jt(graph); jt != INVALID; ++jt) { check(johnson.connected(it, jt) == floyd.connected(it, jt), "Wrong connection in all pairs shortest path"); check(johnson.connected(it, jt) == fibJohnson.connected(it, jt), "Wrong connection in all pairs shortest path"); if (johnson.connected(it, jt)) { check(johnson.dist(it, jt) == floyd.dist(it, jt), "Wrong distance in all pairs shortest path"); check(johnson.dist(it, jt) == fibJohnson.dist(it, jt), "Wrong distance in all pairs shortest path"); if (it != jt) { check(johnson.dist(it, jt) == johnson.dist(it, johnson.predNode(it, jt)) + length[johnson.predEdge(it, jt)], "Wrong edge in all pairs shortest path"); check(fibJohnson.dist(it, jt) == fibJohnson.dist(it, fibJohnson.predNode(it, jt)) + length[fibJohnson.predEdge(it, jt)], "Wrong edge in all pairs shortest path"); check(floyd.dist(it, jt) == floyd.dist(it, floyd.predNode(it, jt)) + length[floyd.predEdge(it, jt)], "Wrong edge in all pairs shortest path"); } } } } return 0; }