src/test/dfs_test.cc
author hegyi
Mon, 13 Sep 2004 15:30:01 +0000
changeset 837 2d50d1f045c5
parent 780 e06d0d16595f
child 880 9d0bfd35b97c
permissions -rw-r--r--
Reserve is resolved.
     1 #include "test_tools.h"
     2 #include <hugo/smart_graph.h>
     3 #include <hugo/dfs.h>
     4 #include<hugo/skeletons/graph.h>
     5 
     6 using namespace hugo;
     7 
     8 const int PET_SIZE =5;
     9 
    10 
    11 void check_Dfs_SmartGraph_Compile() 
    12 {
    13   typedef skeleton::StaticGraphSkeleton Graph;
    14 
    15   typedef Graph::Edge Edge;
    16   typedef Graph::Node Node;
    17   typedef Graph::EdgeIt EdgeIt;
    18   typedef Graph::NodeIt NodeIt;
    19  
    20   typedef Dfs<Graph> DType;
    21   
    22   Graph G;
    23   Node n;
    24   Edge e;
    25   int l;
    26   bool b;
    27   DType::DistMap d(G);
    28   DType::PredMap p(G);
    29   DType::PredNodeMap pn(G);
    30   
    31   DType dfs_test(G);
    32   
    33   dfs_test.run(n);
    34   
    35   l  = dfs_test.dist(n);
    36   e  = dfs_test.pred(n);
    37   n  = dfs_test.predNode(n);
    38   d  = dfs_test.distMap();
    39   p  = dfs_test.predMap();
    40   pn = dfs_test.predNodeMap();
    41   b  = dfs_test.reached(n);
    42 
    43 }
    44 
    45 int main()
    46 {
    47     
    48   typedef SmartGraph Graph;
    49 
    50   typedef Graph::Edge Edge;
    51   typedef Graph::Node Node;
    52   typedef Graph::EdgeIt EdgeIt;
    53   typedef Graph::NodeIt NodeIt;
    54   typedef Graph::EdgeMap<int> LengthMap;
    55 
    56   Graph G;
    57   Node s, t;
    58   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
    59    
    60   s=ps.outer[2];
    61   t=ps.inner[0];
    62   
    63   Dfs<Graph> dfs_test(G);
    64   dfs_test.run(s);  
    65   
    66   for(NodeIt v(G); v!=INVALID; ++v) {
    67     check(dfs_test.reached(v),"Each node should be reached.");
    68     if ( dfs_test.pred(v)!=INVALID ) {
    69       Edge e=dfs_test.pred(v);
    70       Node u=G.tail(e);
    71       check(u==dfs_test.predNode(v),"Wrong tree.");
    72       check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
    73 	    "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
    74     }
    75   }
    76 }
    77