src/test/bfs_test.cc
author alpar
Thu, 02 Sep 2004 15:13:21 +0000
changeset 785 a9b0863c2265
parent 774 4297098d9677
child 793 9cd0aeea47b0
permissions -rw-r--r--
Changes in doc. (New module name for array/vector maps added.)
     1 #include "test_tools.h"
     2 #include <hugo/smart_graph.h>
     3 #include <hugo/bfs.h>
     4 
     5 using namespace hugo;
     6 
     7 const int PET_SIZE =5;
     8 
     9 
    10 void check_Bfs_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 Bfs<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 bfs_test(G);
    34   
    35   bfs_test.run(n);
    36   
    37   l  = bfs_test.dist(n);
    38   e  = bfs_test.pred(n);
    39   n  = bfs_test.predNode(n);
    40   d  = bfs_test.distMap();
    41   p  = bfs_test.predMap();
    42   pn = bfs_test.predNodeMap();
    43   b  = bfs_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   Bfs<Graph> bfs_test(G);
    66   bfs_test.run(s);
    67   
    68   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
    69 
    70 
    71   for(EdgeIt e(G); e==INVALID; ++e) {
    72     Node u=G.tail(e);
    73     Node v=G.head(e);
    74     check( !bfs_test.reached(u) ||
    75 	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
    76 	   "Wrong output.");
    77   }
    78 
    79   for(NodeIt v(G); v==INVALID; ++v) {
    80     check(bfs_test.reached(v),"Each node should be reached.");
    81     if ( bfs_test.pred(v)!=INVALID ) {
    82       Edge e=bfs_test.pred(v);
    83       Node u=G.tail(e);
    84       check(u==bfs_test.predNode(v),"Wrong tree.");
    85       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
    86 	    "Wrong distance. Difference: " 
    87 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
    88 			- 1));
    89     }
    90   }
    91 }
    92