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