COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.cc @ 172:c645f4a2a6ae

Last change on this file since 172:c645f4a2a6ae was 170:9091b1ebca27, checked in by jacint, 17 years ago

* empty log message *

File size: 2.4 KB
RevLine 
[159]1#include <iostream>
[160]2#include <fstream>
[159]3
4#include <list_graph.hh>
[160]5#include <dimacs.hh>
[159]6#include <dijkstra.h>
[160]7#include <time_measure.h>
[159]8
[170]9#include <bin_heap.hh>
10#include <fib_heap.h>
11
[159]12using namespace hugo;
13
[160]14int main(int, char **) {
[159]15  typedef ListGraph::NodeIt NodeIt;
[170]16  typedef ListGraph::EachNodeIt EachNodeIt;
17  typedef ListGraph::InEdgeIt InEdgeIt;
[160]18
19  ListGraph G;
20  NodeIt s, t;
21  ListGraph::EdgeMap<int> cap(G);
22  readDimacsMaxFlow(std::cin, G, s, t, cap);
23
24  std::cout << "dijkstra demo ..." << std::endl;
[159]25 
[160]26  double pre_time=currTime();
[170]27    Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
28    ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
[167]29    dijkstra_test.run();
[160]30  double post_time=currTime();
31   
[170]32  std::cout << "running time with fib_heap: "
33            << post_time-pre_time << " sec"<< std::endl;
[159]34 
[170]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_time-pre_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        }
[167]78    }
[159]79  }
80
[170]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;
[167]86
[159]87  return 0;
88}
Note: See TracBrowser for help on using the repository browser.