src/test/dijkstra_test.cc
author alpar
Mon, 13 Sep 2004 11:24:35 +0000
changeset 835 eb9587f09b42
parent 780 e06d0d16595f
child 880 9d0bfd35b97c
permissions -rw-r--r--
Remove one remaining range checking.
alpar@578
     1
#include "test_tools.h"
alpar@568
     2
#include <hugo/smart_graph.h>
alpar@568
     3
#include <hugo/dijkstra.h>
alpar@793
     4
#include<hugo/skeletons/graph.h>
alpar@793
     5
#include<hugo/skeletons/maps.h>
alpar@568
     6
using namespace hugo;
alpar@568
     7
alpar@568
     8
const int PET_SIZE =5;
alpar@568
     9
alpar@570
    10
alpar@793
    11
void check_Dijkstra_BinHeap_Compile() 
alpar@570
    12
{
alpar@570
    13
  typedef int VType;
alpar@793
    14
  typedef skeleton::StaticGraphSkeleton Graph;
alpar@570
    15
alpar@570
    16
  typedef Graph::Edge Edge;
alpar@570
    17
  typedef Graph::Node Node;
alpar@570
    18
  typedef Graph::EdgeIt EdgeIt;
alpar@570
    19
  typedef Graph::NodeIt NodeIt;
alpar@793
    20
  typedef skeleton::ReadMap<Edge,VType> LengthMap;
alpar@570
    21
 
alpar@570
    22
  typedef Dijkstra<Graph, LengthMap> DType;
alpar@570
    23
  
alpar@570
    24
  Graph G;
alpar@570
    25
  Node n;
alpar@570
    26
  Edge e;
alpar@570
    27
  VType l;
alpar@570
    28
  bool b;
alpar@570
    29
  DType::DistMap d(G);
alpar@570
    30
  DType::PredMap p(G);
alpar@570
    31
  DType::PredNodeMap pn(G);
alpar@793
    32
  LengthMap cap;
alpar@570
    33
alpar@570
    34
  DType dijkstra_test(G,cap);
alpar@570
    35
alpar@570
    36
  dijkstra_test.run(n);
alpar@570
    37
alpar@570
    38
  l  = dijkstra_test.dist(n);
alpar@570
    39
  e  = dijkstra_test.pred(n);
alpar@570
    40
  n  = dijkstra_test.predNode(n);
alpar@570
    41
  d  = dijkstra_test.distMap();
alpar@570
    42
  p  = dijkstra_test.predMap();
alpar@570
    43
  pn = dijkstra_test.predNodeMap();
alpar@570
    44
  b  = dijkstra_test.reached(n);
alpar@570
    45
alpar@570
    46
}
alpar@570
    47
alpar@568
    48
int main()
alpar@568
    49
{
alpar@568
    50
    
alpar@568
    51
  typedef SmartGraph Graph;
alpar@568
    52
alpar@568
    53
  typedef Graph::Edge Edge;
alpar@568
    54
  typedef Graph::Node Node;
alpar@568
    55
  typedef Graph::EdgeIt EdgeIt;
alpar@568
    56
  typedef Graph::NodeIt NodeIt;
alpar@568
    57
  typedef Graph::EdgeMap<int> LengthMap;
alpar@568
    58
alpar@568
    59
  Graph G;
alpar@568
    60
  Node s, t;
alpar@568
    61
  LengthMap cap(G);
alpar@568
    62
  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@578
    63
   
alpar@568
    64
  for(int i=0;i<PET_SIZE;i++) {
alpar@568
    65
    cap[ps.outcir[i]]=4;
alpar@568
    66
    cap[ps.incir[i]]=1;
alpar@568
    67
    cap[ps.chords[i]]=10;
alpar@568
    68
  }
alpar@568
    69
  s=ps.outer[0];
alpar@568
    70
  t=ps.inner[1];
alpar@568
    71
  
alpar@568
    72
  Dijkstra<Graph, LengthMap> 
alpar@568
    73
	dijkstra_test(G, cap);
alpar@568
    74
  dijkstra_test.run(s);
alpar@568
    75
  
alpar@568
    76
  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
alpar@585
    77
alpar@585
    78
hegyi@776
    79
  for(EdgeIt e(G); e!=INVALID; ++e) {
alpar@585
    80
    Node u=G.tail(e);
alpar@585
    81
    Node v=G.head(e);
alpar@585
    82
    check( !dijkstra_test.reached(u) ||
alpar@585
    83
	   (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
alpar@585
    84
	   "dist(head)-dist(tail)- edge_length= " 
alpar@585
    85
	   << dijkstra_test.dist(v) - dijkstra_test.dist(u) 
alpar@585
    86
	   - cap[e]);
alpar@585
    87
  }
alpar@585
    88
alpar@585
    89
  ///\bug This works only for integer lengths
alpar@780
    90
  for(NodeIt v(G); v!=INVALID; ++v){
alpar@780
    91
    check(dijkstra_test.reached(v),"Each node should be reached.");
alpar@780
    92
    if ( dijkstra_test.pred(v)!=INVALID ) {
alpar@585
    93
      Edge e=dijkstra_test.pred(v);
alpar@585
    94
      Node u=G.tail(e);
alpar@780
    95
      check(u==dijkstra_test.predNode(v),"Wrong tree.");
alpar@585
    96
      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
alpar@780
    97
	    "Wrong distance! Difference: " 
alpar@585
    98
	    << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
alpar@585
    99
			    - cap[e]));
alpar@585
   100
    }
alpar@780
   101
  }
alpar@568
   102
}
alpar@780
   103