COIN-OR::LEMON - Graph Library

Changeset 372:e6a156fc186d in lemon-0.x for src/work/jacint/dijkstra.cc


Ignore:
Timestamp:
04/22/04 16:11:28 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@502
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/dijkstra.cc

    r258 r372  
    22#include <fstream>
    33
    4 #include <smart_graph.h>
    5 #include <list_graph.h>
    6 #include <dimacs.h>
     4#include <list_graph.hh>
     5#include <dimacs.hh>
    76#include <dijkstra.h>
    87#include <time_measure.h>
    9 
    10 #include <bin_heap.h>
    11 #include <fib_heap.h>
     8#include <bin_heap.hh>
    129
    1310using namespace hugo;
    1411
    1512int main(int, char **) {
    16   typedef SmartGraph::Node Node;
    17   typedef SmartGraph::NodeIt NodeIt;
    18   typedef SmartGraph::InEdgeIt InEdgeIt;
     13 
     14  typedef ListGraph Graph;
    1915
    20   SmartGraph G;
     16  typedef Graph::Node Node;
     17  typedef Graph::EdgeIt EdgeIt;
     18
     19  Graph G;
    2120  Node s, t;
    22   SmartGraph::EdgeMap<int> cap(G);
     21  Graph::EdgeMap<int> cap(G);
    2322  readDimacsMaxFlow(std::cin, G, s, t, cap);
    24 
    25   std::cout << "dijkstra demo ..." << std::endl;
     23  Timer ts;
    2624 
    27   double pre_time=currTime();
    28   Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
    29     SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
    30   dijkstra_test.run(s);
     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;
    3134  double post_time=currTime();
    3235   
    33     std::cout << "running time with fib_heap: "
    34             << post_time-pre_time << " sec"<< std::endl;
     36  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
    3537 
    36   pre_time=currTime();
    37   Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int,
    38     SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
    39   dijkstra_test2.run(s);
    40   post_time=currTime();
    41  
    42   std::cout << "running time with bin_heap: "
    43             << post_time-pre_time << " sec"<< std::endl;
    44  
     38  EachEdgeIt e;
    4539
    46   int hiba_fib=0;
    47   int hiba_bin=0;
    48   NodeIt u;
    49   for ( G.first(u) ; G.valid(u); G.next(u) ) {
    50     InEdgeIt e;
    51     for ( G.first(e,u); G.valid(e); G.next(e) ) {
    52       Node v=G.tail(e);
    53       if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
    54         {
    55           std::cout<<"Hibas el a fibonaccis Dijkstraban: "
    56                    << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
    57             cap[e]<<std::endl;
    58           ++hiba_fib;
    59         }
    60       if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
    61         {
    62           std::cout<<"Hibas el a binarisos Dijkstraban: "
    63                    << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
    64             cap[e]<<std::endl;
    65           ++hiba_bin;
    66         }
    67       if ( e==dijkstra_test.pred(u) &&
    68            dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
    69         {
    70           std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
    71             dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
    72           ++hiba_fib;
    73         }
    74       if ( e==dijkstra_test2.pred(u) &&
    75            dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
    76         {
    77           std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
    78             dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
    79           ++hiba_bin;
    80         }
     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;
    8151    }
    82  
    83     if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
    84       std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
     52  }
    8553
    86 
    87  }
    88 
    89   std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
    90             << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
    91  
    92   std::cout << "Hibas elek szama a binarisos Dijkstraban: "
    93             << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
    94  
    95 
    96 
     54  std::cout << "Osszhibas el: " << hiba << " osszel: " << G.edgeNum() << std::endl;
    9755
    9856  return 0;
Note: See TracChangeset for help on using the changeset viewer.