src/test/bfs_test.cc
author athos
Wed, 23 Mar 2005 11:51:40 +0000
changeset 1247 60708e1475ae
parent 1218 5331168bbb18
child 1283 fc20371677b9
permissions -rw-r--r--
Completions.
     1 /* -*- C++ -*-
     2  * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #include "test_tools.h"
    18 #include <lemon/smart_graph.h>
    19 #include <lemon/bfs.h>
    20 #include<lemon/concept/graph.h>
    21 
    22 using namespace lemon;
    23 
    24 const int PET_SIZE =5;
    25 
    26 
    27 void check_Bfs_Compile() 
    28 {
    29   typedef concept::StaticGraph Graph;
    30 
    31   typedef Graph::Edge Edge;
    32   typedef Graph::Node Node;
    33   typedef Graph::EdgeIt EdgeIt;
    34   typedef Graph::NodeIt NodeIt;
    35  
    36   typedef Bfs<Graph> BType;
    37   
    38   Graph G;
    39   Node n;
    40   Edge e;
    41   int l;
    42   bool b;
    43   BType::DistMap d(G);
    44   BType::PredMap p(G);
    45   //  BType::PredNodeMap pn(G);
    46   
    47   BType bfs_test(G);
    48   
    49   bfs_test.run(n);
    50   
    51   l  = bfs_test.dist(n);
    52   e  = bfs_test.pred(n);
    53   n  = bfs_test.predNode(n);
    54   d  = bfs_test.distMap();
    55   p  = bfs_test.predMap();
    56   //  pn = bfs_test.predNodeMap();
    57   b  = bfs_test.reached(n);
    58 
    59 }
    60 
    61 void check_Bfs_Function_Compile() 
    62 {
    63   typedef int VType;
    64   typedef concept::StaticGraph Graph;
    65 
    66   typedef Graph::Edge Edge;
    67   typedef Graph::Node Node;
    68   typedef Graph::EdgeIt EdgeIt;
    69   typedef Graph::NodeIt NodeIt;
    70   typedef concept::ReadMap<Edge,VType> LengthMap;
    71    
    72   bfs(Graph(),Node()).run();
    73   bfs(Graph()).source(Node()).run();
    74   bfs(Graph())
    75     .predMap(concept::WriteMap<Node,Edge>())
    76     .distMap(concept::WriteMap<Node,VType>())
    77     .reachedMap(concept::ReadWriteMap<Node,bool>())
    78     .processedMap(concept::WriteMap<Node,bool>())
    79     .run(Node());
    80   
    81 }
    82 
    83 int main()
    84 {
    85     
    86   typedef SmartGraph Graph;
    87 
    88   typedef Graph::Edge Edge;
    89   typedef Graph::Node Node;
    90   typedef Graph::EdgeIt EdgeIt;
    91   typedef Graph::NodeIt NodeIt;
    92   typedef Graph::EdgeMap<int> LengthMap;
    93 
    94   Graph G;
    95   Node s, t;
    96   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
    97    
    98   s=ps.outer[2];
    99   t=ps.inner[0];
   100   
   101   Bfs<Graph> bfs_test(G);
   102   bfs_test.run(s);
   103   
   104   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
   105 
   106 
   107   for(EdgeIt e(G); e==INVALID; ++e) {
   108     Node u=G.source(e);
   109     Node v=G.target(e);
   110     check( !bfs_test.reached(u) ||
   111 	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
   112 	   "Wrong output.");
   113   }
   114 
   115   for(NodeIt v(G); v==INVALID; ++v) {
   116     check(bfs_test.reached(v),"Each node should be reached.");
   117     if ( bfs_test.pred(v)!=INVALID ) {
   118       Edge e=bfs_test.pred(v);
   119       Node u=G.source(e);
   120       check(u==bfs_test.predNode(v),"Wrong tree.");
   121       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   122 	    "Wrong distance. Difference: " 
   123 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
   124 			- 1));
   125     }
   126   }
   127 }
   128