src/work/jacint/prim.cc
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 220 7deda4d6a07a
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
jacint@173
     1
#include <iostream>
jacint@173
     2
#include <fstream>
jacint@173
     3
jacint@220
     4
#include <smart_graph.h>
jacint@211
     5
#include <list_graph.h>
jacint@211
     6
#include <dimacs.h>
jacint@173
     7
#include <prim.h>
jacint@173
     8
#include <time_measure.h>
jacint@173
     9
klao@258
    10
#include <bin_heap.h>
jacint@173
    11
#include <fib_heap.h>
jacint@173
    12
jacint@173
    13
using namespace hugo;
jacint@173
    14
jacint@173
    15
int main(int, char **) {
jacint@220
    16
  typedef SmartGraph::Node Node;
jacint@173
    17
jacint@220
    18
  SmartGraph G;
jacint@211
    19
  Node s, t;
jacint@220
    20
  SmartGraph::EdgeMap<int> cap(G);
jacint@173
    21
  readDimacsMaxFlow(std::cin, G, s, t, cap);
jacint@173
    22
jacint@173
    23
  std::cout << "prim demo ..." << std::endl;
jacint@173
    24
  
jacint@173
    25
  double pre_time=currTime();
jacint@220
    26
    Prim<SmartGraph, int, FibHeap<SmartGraph::Node, int, 
jacint@220
    27
    SmartGraph::NodeMap<int> > > prim_test(G, cap);
jacint@173
    28
    prim_test.run();
jacint@173
    29
  double post_time=currTime();
jacint@173
    30
    
jacint@173
    31
  std::cout << "running time with fib_heap: " 
jacint@173
    32
	    << post_time-pre_time << " sec"<< std::endl; 
jacint@173
    33
 
jacint@173
    34
  pre_time=currTime();
jacint@220
    35
  Prim<SmartGraph, int, BinHeap<SmartGraph::Node, int, 
jacint@220
    36
    SmartGraph::NodeMap<int> > > prim_test2(G, cap);
jacint@173
    37
  prim_test2.run();
jacint@173
    38
  post_time=currTime();
jacint@173
    39
  
jacint@173
    40
  std::cout << "running time with bin_heap: " 
jacint@173
    41
	    << post_time-pre_time << " sec"<< std::endl; 
jacint@173
    42
  
jacint@173
    43
  std::cout<<"A minimalis feszitofa sulya fib kupaccal: "<< prim_test.weight() <<std::endl;
jacint@173
    44
  std::cout<<"A minimalis feszitofa sulya bin kupaccal: "<< prim_test2.weight() <<std::endl;
jacint@173
    45
  if ( prim_test.weight() != prim_test2.weight() ) 
jacint@173
    46
    std::cout<<"Nem egyezik meg!"<<std::endl; 
jacint@173
    47
  else std::cout<<"Megegyezik."<<std::endl; 
jacint@173
    48
jacint@173
    49
  return 0;
jacint@173
    50
}