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