COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.cc @ 211:9222a9b8b323

Last change on this file since 211:9222a9b8b323 was 211:9222a9b8b323, checked in by jacint, 17 years ago

updating

File size: 2.6 KB
RevLine 
[159]1#include <iostream>
[160]2#include <fstream>
[159]3
[211]4#include <smart_graph.h>
5#include <list_graph.h>
6#include <dimacs.h>
[159]7#include <dijkstra.h>
[160]8#include <time_measure.h>
[159]9
[170]10#include <bin_heap.hh>
11#include <fib_heap.h>
12
[159]13using namespace hugo;
14
[160]15int main(int, char **) {
[211]16  typedef SmartGraph::Node Node;
17  typedef SmartGraph::NodeIt NodeIt;
18  typedef SmartGraph::InEdgeIt InEdgeIt;
[160]19
[211]20  SmartGraph G;
21  Node s, t;
22  SmartGraph::EdgeMap<int> cap(G);
[160]23  readDimacsMaxFlow(std::cin, G, s, t, cap);
24
25  std::cout << "dijkstra demo ..." << std::endl;
[159]26 
[160]27  double pre_time=currTime();
[211]28    Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
29    SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
30    dijkstra_test.run(s);
[160]31  double post_time=currTime();
32   
[170]33  std::cout << "running time with fib_heap: "
34            << post_time-pre_time << " sec"<< std::endl;
[159]35 
[170]36  pre_time=currTime();
[211]37  Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int,
38    SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
39  dijkstra_test2.run(s);
[170]40  post_time=currTime();
41 
42  std::cout << "running time with bin_heap: "
43            << post_time-pre_time << " sec"<< std::endl;
44 
45
46  int hiba_fib=0;
47  int hiba_bin=0;
[211]48  NodeIt u;
49  for ( G.first(u) ; G.valid(u); G.next(u) ) {
[170]50    InEdgeIt e;
[211]51    for ( G.first(e,u); G.valid(e); G.next(e) ) {
52      Node v=G.tail(e);
[170]53      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
54        {
55          std::cout<<"Hibas el a fibonaccis Dijkstraban: "
56                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
57            cap.get(e)<<std::endl;
58          ++hiba_fib;
59        }
60      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )
61        {
62          std::cout<<"Hibas el a binarisos Dijkstraban: "
63                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
64            cap.get(e)<<std::endl;
65          ++hiba_bin;
66        }
67      if ( e==dijkstra_test.pred(u) &&
68           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
69        {
[173]70          std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
71            dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl;
[170]72          ++hiba_fib;
73        }
74      if ( e==dijkstra_test2.pred(u) &&
75           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
76        {
[173]77          std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
78            dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;
[170]79          ++hiba_bin;
80        }
[167]81    }
[173]82 
83    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
84      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
85
86
87 }
[159]88
[170]89  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
90            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
[211]91 
[170]92  std::cout << "Hibas elek szama a binarisos Dijkstraban: "
93            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
[211]94 
[173]95
96
97
[159]98  return 0;
99}
Note: See TracBrowser for help on using the repository browser.