src/test/dijkstra_heap_test.cc
author alpar
Mon, 21 Feb 2005 09:28:00 +0000
changeset 1160 d9c32f713cad
parent 986 e997802b855c
child 1164 80bb73097736
permissions -rw-r--r--
We have UndirGraph, so BidirGraph has been removed.
alpar@906
     1
/* -*- C++ -*-
alpar@921
     2
 * src/test/dijkstra_heap_test.cc - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@906
     4
 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@906
    16
jacint@384
    17
//Tests dijsktra.h with two heap implementations:
jacint@384
    18
//the default binary heap of bin_heap.h, and the 
jacint@384
    19
//Fibonacci heap of fib_heap.h.
jacint@384
    20
jacint@384
    21
//The input is a graph in standard dimacs format from the standard input (like
alpar@921
    22
//in /lemon_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both
jacint@422
    23
//heaps, checking two postconditions:
jacint@384
    24
jacint@384
    25
//- if the edges e=uv of the shortest path tree reported by dijkstra.h have
jacint@384
    26
//dist(v)-dist(u)=length(e)
jacint@384
    27
jacint@384
    28
// - if all edges e=uv with u reachable from the root have
jacint@384
    29
//dist(v)-dist(u)>=length(e)
jacint@384
    30
#include <iostream>
jacint@384
    31
#include <math.h>
jacint@384
    32
alpar@921
    33
#include <lemon/smart_graph.h>
alpar@921
    34
#include <lemon/dimacs.h>
alpar@921
    35
#include <lemon/dijkstra.h>
alpar@921
    36
#include <lemon/time_measure.h>
alpar@921
    37
#include <lemon/bin_heap.h>
alpar@921
    38
#include <lemon/fib_heap.h>
jacint@384
    39
alpar@921
    40
using namespace lemon;
jacint@384
    41
jacint@384
    42
int main(int, char **) {
jacint@384
    43
  
jacint@384
    44
  typedef SmartGraph Graph;
jacint@384
    45
jacint@384
    46
  typedef Graph::Edge Edge;
jacint@384
    47
  typedef Graph::Node Node;
jacint@384
    48
  typedef Graph::EdgeIt EdgeIt;
jacint@384
    49
  typedef Graph::NodeIt NodeIt;
jacint@833
    50
  typedef Graph::template EdgeMap<int> LengthMap;
jacint@384
    51
jacint@384
    52
  Graph G;
jacint@384
    53
  Node s, t;
jacint@384
    54
  LengthMap cap(G);
jacint@384
    55
  readDimacsMaxFlow(std::cin, G, s, t, cap);
jacint@384
    56
  Timer ts;
jacint@384
    57
    
jacint@384
    58
  std::cout <<
jacint@384
    59
    "\n  Testing dijkstra.h with binary heap implementation bin_heap.h,"
jacint@384
    60
	    <<std::endl;
jacint@384
    61
  std::cout<<"  on a graph with " << 
jacint@384
    62
    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
jacint@384
    63
	   << std::endl<<std::endl;
jacint@384
    64
  
jacint@384
    65
  Dijkstra<Graph, LengthMap> 
jacint@384
    66
    dijkstra_test(G, cap);
jacint@384
    67
  ts.reset();
jacint@384
    68
  dijkstra_test.run(s);
jacint@384
    69
  std::cout << "elapsed time: " << ts << std::endl;
jacint@384
    70
  
jacint@384
    71
  int error1=0;
jacint@384
    72
  int error2=0;
jacint@384
    73
deba@1139
    74
  for(EdgeIt e(G); e!=INVALID; ++e) {
alpar@986
    75
    Node u=G.source(e);
alpar@986
    76
    Node v=G.target(e);
jacint@384
    77
    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
jacint@384
    78
      if ( dijkstra_test.reached(u) ) {
alpar@986
    79
	std::cout<<"Error! dist(target)-dist(source)- edge_length= " 
jacint@384
    80
		 <<dijkstra_test.dist(v) - dijkstra_test.dist(u) 
jacint@384
    81
	  - cap[e]<<std::endl;
jacint@384
    82
	++error1;
jacint@384
    83
      }
jacint@384
    84
  }
jacint@384
    85
jacint@449
    86
  NodeIt v;
deba@1139
    87
  for(NodeIt v(G); v!=INVALID; ++v) {
jacint@384
    88
    if ( dijkstra_test.reached(v) ) {
jacint@384
    89
      Edge e=dijkstra_test.pred(v);
alpar@986
    90
      Node u=G.source(e);
jacint@384
    91
      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
jacint@384
    92
	std::cout<<"Error in a shortest path tree edge! Difference: " 
jacint@384
    93
		 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
jacint@384
    94
			    - cap[e])<<std::endl;
jacint@384
    95
	++error2;
jacint@384
    96
      }
jacint@384
    97
    }
jacint@384
    98
  }
jacint@384
    99
jacint@384
   100
jacint@384
   101
  
jacint@384
   102
  std::cout << error1 << " non-tree and " << error2 
jacint@384
   103
	    << " shortest path tree edge is erroneous."<<std::endl;
jacint@384
   104
jacint@384
   105
jacint@384
   106
jacint@384
   107
  std::cout <<
jacint@449
   108
    "\n\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
jacint@384
   109
	    <<std::endl;
jacint@384
   110
  std::cout<<"  on a graph with " << 
jacint@384
   111
    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
jacint@384
   112
	   << std::endl<<std::endl;
jacint@384
   113
  
jacint@384
   114
  Dijkstra<Graph, LengthMap, FibHeap> 
jacint@384
   115
    dijkstra_test2(G, cap);
jacint@384
   116
  ts.reset();
jacint@384
   117
  dijkstra_test2.run(s);
jacint@384
   118
  std::cout << "elapsed time: " << ts << std::endl;
jacint@384
   119
  
jacint@384
   120
  error1=0;
jacint@384
   121
  error2=0;
jacint@384
   122
deba@1139
   123
  for(EdgeIt e(G); e!=INVALID; ++e) {
alpar@986
   124
    Node u=G.source(e);
alpar@986
   125
    Node v=G.target(e);
jacint@384
   126
    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
jacint@384
   127
      if ( dijkstra_test2.reached(u) ) {
alpar@986
   128
	std::cout<<"Error! dist(target)-dist(source)- edge_length= " 
jacint@384
   129
		 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u) 
jacint@384
   130
	  - cap[e]<<std::endl;
jacint@384
   131
	++error1;
jacint@384
   132
      }
jacint@384
   133
  }
jacint@384
   134
deba@1139
   135
  for(NodeIt n(G); v!=INVALID; ++v) {
jacint@384
   136
    if ( dijkstra_test2.reached(v) ) {
jacint@384
   137
      Edge e=dijkstra_test2.pred(v);
alpar@986
   138
      Node u=G.source(e);
jacint@384
   139
      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
jacint@384
   140
	std::cout<<"Error in a shortest path tree edge! Difference: " 
jacint@384
   141
		 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u) 
jacint@384
   142
			    - cap[e])<<std::endl;
jacint@384
   143
	++error2;
jacint@384
   144
      }
jacint@384
   145
    }
jacint@384
   146
  }
jacint@384
   147
jacint@384
   148
jacint@384
   149
  std::cout << error1 << " non-tree and " << error2 
jacint@384
   150
	    << " shortest path tree edge is erroneous."<<std::endl;
jacint@384
   151
jacint@384
   152
jacint@384
   153
  return 0;
jacint@384
   154
}