/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2007 * 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 #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; } bool checked_path = false; 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)) { if (it != jt && !checked_path) { { Path path = johnson.path(it, jt); check(checkPath(graph, path), "Wrong path."); check(pathSource(graph, path) == it, "Wrong path."); check(pathTarget(graph, path) == jt, "Wrong path."); } { Path path = floyd.path(it, jt); check(checkPath(graph, path), "Wrong path."); check(pathSource(graph, path) == it, "Wrong path."); check(pathTarget(graph, path) == jt, "Wrong path."); } checked_path = true; std::cout << "Path checked" << std::endl; } 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; }