alpar@222: #include <iostream> alpar@222: #include <fstream> alpar@222: alpar@222: #include <smart_graph.h> alpar@222: #include <list_graph.h> alpar@222: #include <dimacs.h> alpar@222: #include <dijkstra.h> alpar@222: #include <time_measure.h> alpar@222: klao@258: #include <bin_heap.h> alpar@222: #include <fib_heap.h> alpar@222: alpar@222: using namespace hugo; alpar@222: alpar@222: int main(int, char **) { alpar@222: typedef SmartGraph::Node Node; alpar@222: typedef SmartGraph::NodeIt NodeIt; alpar@222: typedef SmartGraph::InEdgeIt InEdgeIt; alpar@222: alpar@222: SmartGraph G; alpar@222: Node s, t; alpar@222: SmartGraph::EdgeMap<int> cap(G); alpar@222: Timer tim; alpar@222: std::cout << "DIMACS load ..." << std::endl; alpar@222: readDimacsMaxFlow(std::cin, G, s, t, cap); alpar@222: std::cout << " " << tim <<std::endl; alpar@222: alpar@222: std::cout << "dijkstra demo ..." << std::endl; alpar@222: alpar@222: //double pre_time=currTime(); alpar@222: tim.reset(); alpar@247: // Dijkstra <SmartGraph, alpar@247: // SmartGraph::EdgeMap<int>, alpar@247: // FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > alpar@247: // > dijkstra_test(G, cap); alpar@247: alpar@247: Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap > alpar@247: dijkstra_test(G, cap); alpar@222: alpar@222: dijkstra_test.run(s); alpar@222: //double post_time=currTime(); alpar@222: alpar@222: std::cout << "running time with fib_heap: " alpar@222: // << post_time-pre_time << " sec" alpar@222: << tim alpar@222: << std::endl; alpar@222: alpar@222: //pre_time=currTime(); alpar@222: tim.reset(); alpar@247: // Dijkstra < SmartGraph, alpar@247: // SmartGraph::EdgeMap<int>, alpar@247: // BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > alpar@247: // dijkstra_test2(G, cap); alpar@247: alpar@247: Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap > alpar@247: dijkstra_test2(G, cap); alpar@222: alpar@222: dijkstra_test2.run(s); alpar@222: //post_time=currTime(); alpar@222: alpar@222: std::cout << "running time with bin_heap: " alpar@222: // << post_time-pre_time << " sec" alpar@222: << tim alpar@222: << std::endl; alpar@222: alpar@222: alpar@222: int hiba_fib=0; alpar@222: int hiba_bin=0; alpar@222: NodeIt u; alpar@222: for ( G.first(u) ; G.valid(u); G.next(u) ) { alpar@222: InEdgeIt e; alpar@222: for ( G.first(e,u); G.valid(e); G.next(e) ) { alpar@222: Node v=G.tail(e); alpar@222: if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] ) alpar@222: { alpar@222: std::cout<<"Hibas el a fibonaccis Dijkstraban: " alpar@222: << dijkstra_test.dist(u) - dijkstra_test.dist(v) - alpar@222: cap[e]<<std::endl; alpar@222: ++hiba_fib; alpar@222: } alpar@222: if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] ) alpar@222: { alpar@222: std::cout<<"Hibas el a binarisos Dijkstraban: " alpar@222: << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - alpar@222: cap[e]<<std::endl; alpar@222: ++hiba_bin; alpar@222: } alpar@222: if ( e==dijkstra_test.pred(u) && alpar@222: dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] ) alpar@222: { alpar@222: std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< alpar@222: dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl; alpar@222: ++hiba_fib; alpar@222: } alpar@222: if ( e==dijkstra_test2.pred(u) && alpar@222: dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] ) alpar@222: { alpar@222: std::cout<<"Hibas fael a binarisos Dijkstraban: "<< alpar@222: dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl; alpar@222: ++hiba_bin; alpar@222: } alpar@222: } alpar@222: alpar@222: if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) alpar@222: std::cout << "Nem egyezik meg a tavolsag!"<<std::endl; alpar@222: alpar@222: alpar@222: } alpar@222: alpar@222: std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " alpar@222: << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl; alpar@222: alpar@222: std::cout << "Hibas elek szama a binarisos Dijkstraban: " alpar@222: << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl; alpar@222: alpar@222: return 0; alpar@222: }