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