source: lemon-0.x/src/work/alpar/dijkstra/dijkstra.cc @ 505:8589c0658839

#include <iostream>
#include <fstream>

#include <smart_graph.h>
#include <list_graph.h>
#include <dimacs.h>
#include <dijkstra.h>
#include <time_measure.h>

#include <bin_heap.h>
#include <fib_heap.h>

using namespace hugo;

int main(int, char **) {
  typedef SmartGraph::Node Node;
  typedef SmartGraph::NodeIt NodeIt;
  typedef SmartGraph::InEdgeIt InEdgeIt; 

  SmartGraph G;
  Node s, t;
  SmartGraph::EdgeMap<int> cap(G);
  Timer tim;
  std::cout << "DIMACS load ..." << std::endl;
  readDimacsMaxFlow(std::cin, G, s, t, cap);
  std::cout << "               " << tim <<std::endl;

  std::cout << "dijkstra demo ..." << std::endl;
  
  //double pre_time=currTime();
  tim.reset();
//   Dijkstra <SmartGraph,
//     SmartGraph::EdgeMap<int>,
//     FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
//     > dijkstra_test(G, cap); 
  
  Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap >
    dijkstra_test(G, cap); 
  
  dijkstra_test.run(s);
  //double post_time=currTime();
  
  std::cout << "running time with fib_heap: " 
    // << post_time-pre_time << " sec"
            << tim
            << std::endl; 
 
  //pre_time=currTime();
  tim.reset();
//   Dijkstra < SmartGraph,
//     SmartGraph::EdgeMap<int>,
//     BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > > 
//     dijkstra_test2(G, cap);
  
  Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap >
    dijkstra_test2(G, cap); 
  
  dijkstra_test2.run(s);
  //post_time=currTime();
  
  std::cout << "running time with bin_heap: " 
    //    << post_time-pre_time << " sec"
            << tim
            << std::endl; 
  

  int hiba_fib=0;
  int hiba_bin=0;
  NodeIt u;
  for ( G.first(u) ; G.valid(u); G.next(u) ) {
    InEdgeIt e;
    for ( G.first(e,u); G.valid(e); G.next(e) ) {
      Node v=G.tail(e);
      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
        {
          std::cout<<"Hibas el a fibonaccis Dijkstraban: " 
                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) - 
            cap[e]<<std::endl;
          ++hiba_fib;
        }
      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
        {
          std::cout<<"Hibas el a binarisos Dijkstraban: " 
                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) - 
            cap[e]<<std::endl;
          ++hiba_bin;
        }
      if ( e==dijkstra_test.pred(u) && 
           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
        {
          std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
            dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
          ++hiba_fib;
        }
      if ( e==dijkstra_test2.pred(u) && 
           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
        {
          std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
            dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
          ++hiba_bin;
        }
    }
 
    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) 
      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;


 }

  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " 
            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
  
  std::cout << "Hibas elek szama a binarisos Dijkstraban: " 
            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
  
  return 0;
}