COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.cc @ 374:0fc9cd9b854a

Last change on this file since 374:0fc9cd9b854a was 372:e6a156fc186d, checked in by jacint, 20 years ago
File size: 1.3 KB
RevLine 
[159]1#include <iostream>
[160]2#include <fstream>
[159]3
[372]4#include <list_graph.hh>
5#include <dimacs.hh>
[159]6#include <dijkstra.h>
[160]7#include <time_measure.h>
[372]8#include <bin_heap.hh>
[170]9
[159]10using namespace hugo;
11
[160]12int main(int, char **) {
[372]13 
14  typedef ListGraph Graph;
[160]15
[372]16  typedef Graph::Node Node;
17  typedef Graph::EdgeIt EdgeIt;
18
19  Graph G;
[211]20  Node s, t;
[372]21  Graph::EdgeMap<int> cap(G);
[160]22  readDimacsMaxFlow(std::cin, G, s, t, cap);
[372]23  Timer ts;
[159]24 
[372]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;
[160]34  double post_time=currTime();
35   
[372]36  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
[159]37 
[372]38  EachEdgeIt e;
[170]39
[372]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;
[167]51    }
[372]52  }
[173]53
[372]54  std::cout << "Osszhibas el: " << hiba << " osszel: " << G.edgeNum() << std::endl;
[173]55
[159]56  return 0;
57}
Note: See TracBrowser for help on using the repository browser.