alpar@906: /* -*- C++ -*- alpar@921: * src/test/dijkstra_heap_test.cc - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@906: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: jacint@384: //Tests dijsktra.h with two heap implementations: jacint@384: //the default binary heap of bin_heap.h, and the jacint@384: //Fibonacci heap of fib_heap.h. jacint@384: jacint@384: //The input is a graph in standard dimacs format from the standard input (like alpar@921: //in /lemon_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both jacint@422: //heaps, checking two postconditions: jacint@384: jacint@384: //- if the edges e=uv of the shortest path tree reported by dijkstra.h have jacint@384: //dist(v)-dist(u)=length(e) jacint@384: jacint@384: // - if all edges e=uv with u reachable from the root have jacint@384: //dist(v)-dist(u)>=length(e) jacint@384: #include jacint@384: #include jacint@384: alpar@921: #include alpar@921: #include alpar@921: #include alpar@921: #include alpar@921: #include alpar@921: #include jacint@384: alpar@921: using namespace lemon; jacint@384: jacint@384: int main(int, char **) { jacint@384: jacint@384: typedef SmartGraph Graph; jacint@384: jacint@384: typedef Graph::Edge Edge; jacint@384: typedef Graph::Node Node; jacint@384: typedef Graph::EdgeIt EdgeIt; jacint@384: typedef Graph::NodeIt NodeIt; jacint@833: typedef Graph::template EdgeMap LengthMap; jacint@384: jacint@384: Graph G; jacint@384: Node s, t; jacint@384: LengthMap cap(G); jacint@384: readDimacsMaxFlow(std::cin, G, s, t, cap); jacint@384: Timer ts; jacint@384: jacint@384: std::cout << jacint@384: "\n Testing dijkstra.h with binary heap implementation bin_heap.h," jacint@384: < jacint@384: dijkstra_test(G, cap); jacint@384: ts.reset(); jacint@384: dijkstra_test.run(s); jacint@384: std::cout << "elapsed time: " << ts << std::endl; jacint@384: jacint@384: int error1=0; jacint@384: int error2=0; jacint@384: deba@1139: for(EdgeIt e(G); e!=INVALID; ++e) { alpar@986: Node u=G.source(e); alpar@986: Node v=G.target(e); jacint@384: if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) jacint@384: if ( dijkstra_test.reached(u) ) { alpar@986: std::cout<<"Error! dist(target)-dist(source)- edge_length= " jacint@384: < jacint@384: dijkstra_test2(G, cap); jacint@384: ts.reset(); jacint@384: dijkstra_test2.run(s); jacint@384: std::cout << "elapsed time: " << ts << std::endl; jacint@384: jacint@384: error1=0; jacint@384: error2=0; jacint@384: deba@1139: for(EdgeIt e(G); e!=INVALID; ++e) { alpar@986: Node u=G.source(e); alpar@986: Node v=G.target(e); jacint@384: if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) jacint@384: if ( dijkstra_test2.reached(u) ) { alpar@986: std::cout<<"Error! dist(target)-dist(source)- edge_length= " jacint@384: <