COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.cc @ 372:e6a156fc186d

Last change on this file since 372:e6a156fc186d was 372:e6a156fc186d, checked in by jacint, 17 years ago
File size: 1.3 KB
Line 
1#include <iostream>
2#include <fstream>
3
4#include <list_graph.hh>
5#include <dimacs.hh>
6#include <dijkstra.h>
7#include <time_measure.h>
8#include <bin_heap.hh>
9
10using namespace hugo;
11
12int main(int, char **) {
13 
14  typedef ListGraph Graph;
15
16  typedef Graph::Node Node;
17  typedef Graph::EdgeIt EdgeIt;
18
19  Graph G;
20  Node s, t;
21  Graph::EdgeMap<int> cap(G);
22  readDimacsMaxFlow(std::cin, G, s, t, cap);
23  Timer ts;
24 
25  std::cout << "Testing dijkstra.h with Fibonacci-heap
26implementation fib_heap.h ..." << std::endl;
27 
28  Dijkstra<Graph, int
29      //      , BinHeap<ListGraph::NodeIt, int, ListGraph::NodeMap<int> >
30> dijkstra_test(G, s, cap);
31   ts.reset();
32    dijkstra_test.run();
33    std::cout << "elapsed time: " << ts << std::endl;
34  double post_time=currTime();
35   
36  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
37 
38  EachEdgeIt e;
39
40  int hiba=0;
41
42  int edge=0;
43
44  for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
45    NodeIt u=G.tail(e);
46    NodeIt v=G.head(e);
47    ++edge;
48    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
49      std::cout<<"Hiba: "<<edge<<": "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
50      ++hiba;
51    }
52  }
53
54  std::cout << "Osszhibas el: " << hiba << " osszel: " << G.edgeNum() << std::endl;
55
56  return 0;
57}
Note: See TracBrowser for help on using the repository browser.