COIN-OR::LEMON - Graph Library

Changeset 170:9091b1ebca27 in lemon-0.x


Ignore:
Timestamp:
03/11/04 19:17:20 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@243
Message:

* empty log message *

Location:
src/work/jacint
Files:
1 added
3 edited

Legend:

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

    r167 r170  
    77#include <time_measure.h>
    88
     9#include <bin_heap.hh>
     10#include <fib_heap.h>
     11
    912using namespace hugo;
    1013
    1114int main(int, char **) {
    1215  typedef ListGraph::NodeIt NodeIt;
    13   typedef ListGraph::EachEdgeIt EachEdgeIt;
     16  typedef ListGraph::EachNodeIt EachNodeIt;
     17  typedef ListGraph::InEdgeIt InEdgeIt;
    1418
    1519  ListGraph G;
     
    2125 
    2226  double pre_time=currTime();
    23     Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
     27    Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
     28    ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
    2429    dijkstra_test.run();
    2530  double post_time=currTime();
    2631   
    27   std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
     32  std::cout << "running time with fib_heap: "
     33            << post_time-pre_time << " sec"<< std::endl;
    2834 
    29   int hiba=0;
    30   EachEdgeIt e;
    31   for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
    32     NodeIt u=G.tail(e);
    33     NodeIt v=G.head(e);
    34     if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
    35       std::cout<<"Hiba: "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
    36       ++hiba;
     35  pre_time=currTime();
     36  Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
     37    ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap);
     38  dijkstra_test2.run();
     39  post_time=currTime();
     40 
     41  std::cout << "running time with bin_heap: "
     42            << post_time-pre_time << " sec"<< std::endl;
     43 
     44
     45  int hiba_fib=0;
     46  int hiba_bin=0;
     47  EachNodeIt u;
     48  for ( G.getFirst(u) ; G.valid(u); G.next(u) ) {
     49    InEdgeIt e;
     50    for ( G.getFirst(e,u); G.valid(e); G.next(e) ) {
     51      NodeIt v=G.tail(e);
     52      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
     53        {
     54          std::cout<<"Hibas el a fibonaccis Dijkstraban: "
     55                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
     56            cap.get(e)<<std::endl;
     57          ++hiba_fib;
     58        }
     59      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )
     60        {
     61          std::cout<<"Hibas el a binarisos Dijkstraban: "
     62                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
     63            cap.get(e)<<std::endl;
     64          ++hiba_bin;
     65        }
     66      if ( e==dijkstra_test.pred(u) &&
     67           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
     68        {
     69          std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl;
     70          ++hiba_fib;
     71        }
     72      if ( e==dijkstra_test2.pred(u) &&
     73           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
     74        {
     75          std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl;
     76          ++hiba_bin;
     77        }
    3778    }
    3879  }
    3980
    40   std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"-bol."<< std::endl;
     81  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
     82            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
     83
     84  std::cout << "Hibas elek szama a binarisos Dijkstraban: "
     85            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
    4186
    4287  return 0;
  • src/work/jacint/dijkstra.h

    r167 r170  
    11// -*- C++ -*-
     2
     3//ha predecessor az elejen nem invalid, akkor hagyd csak ugy
     4//scanned mutatja hogy jo ertek van-e benne vagy szemet
     5
    26/*
    37 *template <Graph, T, Heap=FibHeap>
     
    2529 */
    2630
    27 #ifndef DIJKSTRA_HH
    28 #define DIJKSTRA_HH
     31#ifndef DIJKSTRA_H
     32#define DIJKSTRA_H
    2933
    3034#include <fib_heap.h>
  • src/work/jacint/makefile

    r166 r170  
    1717        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
    1818
     19prim:
     20        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o prim prim.cc
     21
    1922clean:
    2023        $(RM) *.o $(BINARIES) .depend
Note: See TracChangeset for help on using the changeset viewer.