jacint@159: #include <iostream> jacint@160: #include <fstream> jacint@159: jacint@159: #include <list_graph.hh> jacint@160: #include <dimacs.hh> jacint@159: #include <dijkstra.h> jacint@160: #include <time_measure.h> jacint@159: jacint@170: #include <bin_heap.hh> jacint@170: #include <fib_heap.h> jacint@170: jacint@159: using namespace hugo; jacint@159: jacint@160: int main(int, char **) { jacint@159: typedef ListGraph::NodeIt NodeIt; jacint@170: typedef ListGraph::EachNodeIt EachNodeIt; jacint@170: typedef ListGraph::InEdgeIt InEdgeIt; jacint@160: jacint@160: ListGraph G; jacint@160: NodeIt s, t; jacint@160: ListGraph::EdgeMap<int> cap(G); jacint@160: readDimacsMaxFlow(std::cin, G, s, t, cap); jacint@160: jacint@160: std::cout << "dijkstra demo ..." << std::endl; jacint@159: jacint@160: double pre_time=currTime(); jacint@170: Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int, jacint@170: ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap); jacint@167: dijkstra_test.run(); jacint@160: double post_time=currTime(); jacint@160: jacint@170: std::cout << "running time with fib_heap: " jacint@170: << post_time-pre_time << " sec"<< std::endl; jacint@159: jacint@170: pre_time=currTime(); jacint@170: Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int, jacint@170: ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap); jacint@170: dijkstra_test2.run(); jacint@170: post_time=currTime(); jacint@170: jacint@170: std::cout << "running time with bin_heap: " jacint@170: << post_time-pre_time << " sec"<< std::endl; jacint@170: jacint@170: jacint@170: int hiba_fib=0; jacint@170: int hiba_bin=0; jacint@170: EachNodeIt u; jacint@170: for ( G.getFirst(u) ; G.valid(u); G.next(u) ) { jacint@170: InEdgeIt e; jacint@170: for ( G.getFirst(e,u); G.valid(e); G.next(e) ) { jacint@170: NodeIt v=G.tail(e); jacint@170: if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) ) jacint@170: { jacint@170: std::cout<<"Hibas el a fibonaccis Dijkstraban: " jacint@170: << dijkstra_test.dist(u) - dijkstra_test.dist(v) - jacint@170: cap.get(e)<<std::endl; jacint@170: ++hiba_fib; jacint@170: } jacint@170: if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) ) jacint@170: { jacint@170: std::cout<<"Hibas el a binarisos Dijkstraban: " jacint@170: << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - jacint@170: cap.get(e)<<std::endl; jacint@170: ++hiba_bin; jacint@170: } jacint@170: if ( e==dijkstra_test.pred(u) && jacint@170: dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) ) jacint@170: { jacint@173: std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< jacint@173: dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl; jacint@170: ++hiba_fib; jacint@170: } jacint@170: if ( e==dijkstra_test2.pred(u) && jacint@170: dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) ) jacint@170: { jacint@173: std::cout<<"Hibas fael a binarisos Dijkstraban: "<< jacint@173: dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl; jacint@170: ++hiba_bin; jacint@170: } jacint@167: } jacint@173: jacint@173: if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) jacint@173: std::cout << "Nem egyezik meg a tavolsag!"<<std::endl; jacint@173: jacint@173: jacint@173: } jacint@159: jacint@170: std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " jacint@170: << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl; jacint@170: jacint@170: std::cout << "Hibas elek szama a binarisos Dijkstraban: " jacint@170: << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl; jacint@167: jacint@173: jacint@173: jacint@173: jacint@159: return 0; jacint@159: }