jacint@159: #include <iostream> jacint@160: #include <fstream> jacint@159: jacint@211: #include <smart_graph.h> jacint@211: #include <list_graph.h> jacint@211: #include <dimacs.h> jacint@159: #include <dijkstra.h> jacint@160: #include <time_measure.h> jacint@159: klao@258: #include <bin_heap.h> jacint@170: #include <fib_heap.h> jacint@170: jacint@159: using namespace hugo; jacint@159: jacint@160: int main(int, char **) { jacint@211: typedef SmartGraph::Node Node; jacint@211: typedef SmartGraph::NodeIt NodeIt; jacint@211: typedef SmartGraph::InEdgeIt InEdgeIt; jacint@160: jacint@211: SmartGraph G; jacint@211: Node s, t; jacint@211: SmartGraph::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(); alpar@217: Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, jacint@211: SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); alpar@217: dijkstra_test.run(s); jacint@160: double post_time=currTime(); jacint@160: alpar@217: std::cout << "running time with fib_heap: " jacint@170: << post_time-pre_time << " sec"<< std::endl; jacint@159: jacint@170: pre_time=currTime(); jacint@211: Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int, jacint@211: SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap); jacint@211: dijkstra_test2.run(s); 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@211: NodeIt u; jacint@211: for ( G.first(u) ; G.valid(u); G.next(u) ) { jacint@170: InEdgeIt e; jacint@211: for ( G.first(e,u); G.valid(e); G.next(e) ) { jacint@211: Node v=G.tail(e); alpar@217: if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] ) jacint@170: { jacint@170: std::cout<<"Hibas el a fibonaccis Dijkstraban: " jacint@170: << dijkstra_test.dist(u) - dijkstra_test.dist(v) - alpar@217: cap[e]<<std::endl; jacint@170: ++hiba_fib; jacint@170: } alpar@217: if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] ) jacint@170: { jacint@170: std::cout<<"Hibas el a binarisos Dijkstraban: " jacint@170: << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - alpar@217: cap[e]<<std::endl; jacint@170: ++hiba_bin; jacint@170: } jacint@170: if ( e==dijkstra_test.pred(u) && alpar@217: dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] ) jacint@170: { jacint@173: std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< alpar@217: dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl; jacint@170: ++hiba_fib; jacint@170: } jacint@170: if ( e==dijkstra_test2.pred(u) && alpar@217: dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] ) jacint@170: { jacint@173: std::cout<<"Hibas fael a binarisos Dijkstraban: "<< alpar@217: dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[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@211: jacint@170: std::cout << "Hibas elek szama a binarisos Dijkstraban: " jacint@170: << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl; jacint@211: jacint@173: jacint@173: jacint@173: jacint@159: return 0; jacint@159: }