1.1 --- a/src/work/jacint/dijkstra.cc Thu Apr 22 13:59:37 2004 +0000
1.2 +++ b/src/work/jacint/dijkstra.cc Thu Apr 22 14:11:28 2004 +0000
1.3 @@ -1,99 +1,57 @@
1.4 #include <iostream>
1.5 #include <fstream>
1.6
1.7 -#include <smart_graph.h>
1.8 -#include <list_graph.h>
1.9 -#include <dimacs.h>
1.10 +#include <list_graph.hh>
1.11 +#include <dimacs.hh>
1.12 #include <dijkstra.h>
1.13 #include <time_measure.h>
1.14 -
1.15 -#include <bin_heap.h>
1.16 -#include <fib_heap.h>
1.17 +#include <bin_heap.hh>
1.18
1.19 using namespace hugo;
1.20
1.21 int main(int, char **) {
1.22 - typedef SmartGraph::Node Node;
1.23 - typedef SmartGraph::NodeIt NodeIt;
1.24 - typedef SmartGraph::InEdgeIt InEdgeIt;
1.25 +
1.26 + typedef ListGraph Graph;
1.27
1.28 - SmartGraph G;
1.29 + typedef Graph::Node Node;
1.30 + typedef Graph::EdgeIt EdgeIt;
1.31 +
1.32 + Graph G;
1.33 Node s, t;
1.34 - SmartGraph::EdgeMap<int> cap(G);
1.35 + Graph::EdgeMap<int> cap(G);
1.36 readDimacsMaxFlow(std::cin, G, s, t, cap);
1.37 -
1.38 - std::cout << "dijkstra demo ..." << std::endl;
1.39 + Timer ts;
1.40
1.41 - double pre_time=currTime();
1.42 - Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
1.43 - SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
1.44 - dijkstra_test.run(s);
1.45 + std::cout << "Testing dijkstra.h with Fibonacci-heap
1.46 +implementation fib_heap.h ..." << std::endl;
1.47 +
1.48 + Dijkstra<Graph, int
1.49 + // , BinHeap<ListGraph::NodeIt, int, ListGraph::NodeMap<int> >
1.50 +> dijkstra_test(G, s, cap);
1.51 + ts.reset();
1.52 + dijkstra_test.run();
1.53 + std::cout << "elapsed time: " << ts << std::endl;
1.54 double post_time=currTime();
1.55
1.56 - std::cout << "running time with fib_heap: "
1.57 - << post_time-pre_time << " sec"<< std::endl;
1.58 + std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
1.59
1.60 - pre_time=currTime();
1.61 - Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int,
1.62 - SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
1.63 - dijkstra_test2.run(s);
1.64 - post_time=currTime();
1.65 -
1.66 - std::cout << "running time with bin_heap: "
1.67 - << post_time-pre_time << " sec"<< std::endl;
1.68 -
1.69 + EachEdgeIt e;
1.70
1.71 - int hiba_fib=0;
1.72 - int hiba_bin=0;
1.73 - NodeIt u;
1.74 - for ( G.first(u) ; G.valid(u); G.next(u) ) {
1.75 - InEdgeIt e;
1.76 - for ( G.first(e,u); G.valid(e); G.next(e) ) {
1.77 - Node v=G.tail(e);
1.78 - if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
1.79 - {
1.80 - std::cout<<"Hibas el a fibonaccis Dijkstraban: "
1.81 - << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
1.82 - cap[e]<<std::endl;
1.83 - ++hiba_fib;
1.84 - }
1.85 - if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
1.86 - {
1.87 - std::cout<<"Hibas el a binarisos Dijkstraban: "
1.88 - << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
1.89 - cap[e]<<std::endl;
1.90 - ++hiba_bin;
1.91 - }
1.92 - if ( e==dijkstra_test.pred(u) &&
1.93 - dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
1.94 - {
1.95 - std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
1.96 - dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
1.97 - ++hiba_fib;
1.98 - }
1.99 - if ( e==dijkstra_test2.pred(u) &&
1.100 - dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
1.101 - {
1.102 - std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
1.103 - dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
1.104 - ++hiba_bin;
1.105 - }
1.106 + int hiba=0;
1.107 +
1.108 + int edge=0;
1.109 +
1.110 + for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
1.111 + NodeIt u=G.tail(e);
1.112 + NodeIt v=G.head(e);
1.113 + ++edge;
1.114 + if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
1.115 + std::cout<<"Hiba: "<<edge<<": "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
1.116 + ++hiba;
1.117 }
1.118 -
1.119 - if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
1.120 - std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
1.121 + }
1.122
1.123 -
1.124 - }
1.125 -
1.126 - std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
1.127 - << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.128 -
1.129 - std::cout << "Hibas elek szama a binarisos Dijkstraban: "
1.130 - << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.131 -
1.132 -
1.133 -
1.134 + std::cout << "Osszhibas el: " << hiba << " osszel: " << G.edgeNum() << std::endl;
1.135
1.136 return 0;
1.137 }