Changeset 170:9091b1ebca27 in lemon0.x for src
 Timestamp:
 03/11/04 19:17:20 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@243
 Location:
 src/work/jacint
 Files:

 1 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/dijkstra.cc
r167 r170 7 7 #include <time_measure.h> 8 8 9 #include <bin_heap.hh> 10 #include <fib_heap.h> 11 9 12 using namespace hugo; 10 13 11 14 int main(int, char **) { 12 15 typedef ListGraph::NodeIt NodeIt; 13 typedef ListGraph::EachEdgeIt EachEdgeIt; 16 typedef ListGraph::EachNodeIt EachNodeIt; 17 typedef ListGraph::InEdgeIt InEdgeIt; 14 18 15 19 ListGraph G; … … 21 25 22 26 double pre_time=currTime(); 23 Dijkstra<ListGraph, int> dijkstra_test(G, s, cap); 27 Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int, 28 ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap); 24 29 dijkstra_test.run(); 25 30 double post_time=currTime(); 26 31 27 std::cout << "running time: " << post_timepre_time << " sec"<< std::endl; 32 std::cout << "running time with fib_heap: " 33 << post_timepre_time << " sec"<< std::endl; 28 34 29 int hiba=0; 30 EachEdgeIt e; 31 for ( G.getFirst(e) ; G.valid(e); G.next(e) ) { 32 NodeIt u=G.tail(e); 33 NodeIt v=G.head(e); 34 if ( dijkstra_test.dist(v)  dijkstra_test.dist(u) > cap.get(e) ) { 35 std::cout<<"Hiba: "<<dijkstra_test.dist(v)  dijkstra_test.dist(u)  cap.get(e)<<std::endl; 36 ++hiba; 35 pre_time=currTime(); 36 Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int, 37 ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap); 38 dijkstra_test2.run(); 39 post_time=currTime(); 40 41 std::cout << "running time with bin_heap: " 42 << post_timepre_time << " sec"<< std::endl; 43 44 45 int hiba_fib=0; 46 int hiba_bin=0; 47 EachNodeIt u; 48 for ( G.getFirst(u) ; G.valid(u); G.next(u) ) { 49 InEdgeIt e; 50 for ( G.getFirst(e,u); G.valid(e); G.next(e) ) { 51 NodeIt v=G.tail(e); 52 if ( dijkstra_test.dist(u)  dijkstra_test.dist(v) > cap.get(e) ) 53 { 54 std::cout<<"Hibas el a fibonaccis Dijkstraban: " 55 << dijkstra_test.dist(u)  dijkstra_test.dist(v)  56 cap.get(e)<<std::endl; 57 ++hiba_fib; 58 } 59 if ( dijkstra_test2.dist(u)  dijkstra_test2.dist(v) > cap.get(e) ) 60 { 61 std::cout<<"Hibas el a binarisos Dijkstraban: " 62 << dijkstra_test2.dist(u)  dijkstra_test2.dist(v)  63 cap.get(e)<<std::endl; 64 ++hiba_bin; 65 } 66 if ( e==dijkstra_test.pred(u) && 67 dijkstra_test.dist(u)  dijkstra_test.dist(v) != cap.get(e) ) 68 { 69 std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl; 70 ++hiba_fib; 71 } 72 if ( e==dijkstra_test2.pred(u) && 73 dijkstra_test2.dist(u)  dijkstra_test2.dist(v) != cap.get(e) ) 74 { 75 std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl; 76 ++hiba_bin; 77 } 37 78 } 38 79 } 39 80 40 std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"bol."<< std::endl; 81 std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " 82 << hiba_fib << " a " << G.edgeNum() <<"bol."<< std::endl; 83 84 std::cout << "Hibas elek szama a binarisos Dijkstraban: " 85 << hiba_bin << " a " << G.edgeNum() <<"bol."<< std::endl; 41 86 42 87 return 0; 
src/work/jacint/dijkstra.h
r167 r170 1 1 // * C++ * 2 3 //ha predecessor az elejen nem invalid, akkor hagyd csak ugy 4 //scanned mutatja hogy jo ertek vane benne vagy szemet 5 2 6 /* 3 7 *template <Graph, T, Heap=FibHeap> … … 25 29 */ 26 30 27 #ifndef DIJKSTRA_H H28 #define DIJKSTRA_H H31 #ifndef DIJKSTRA_H 32 #define DIJKSTRA_H 29 33 30 34 #include <fib_heap.h> 
src/work/jacint/makefile
r166 r170 17 17 $(CXX3) $(CXXFLAGS) O3 I. I.. I../marci o dijkstra dijkstra.cc 18 18 19 prim: 20 $(CXX3) $(CXXFLAGS) O3 I. I.. I../marci o prim prim.cc 21 19 22 clean: 20 23 $(RM) *.o $(BINARIES) .depend
Note: See TracChangeset
for help on using the changeset viewer.