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