test/bfs_test.cc
author alpar
Wed, 02 Nov 2005 16:32:29 +0000
changeset 1756 b1f441f24d08
parent 1359 1581f961cfaa
child 1763 49045f2d28d4
permissions -rw-r--r--
GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.
     1 /* -*- C++ -*-
     2  * test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, 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/path.h>
    21 #include<lemon/concept/graph.h>
    22 
    23 using namespace lemon;
    24 
    25 const int PET_SIZE =5;
    26 
    27 
    28 void check_Bfs_Compile() 
    29 {
    30   typedef concept::StaticGraph Graph;
    31 
    32   typedef Graph::Edge Edge;
    33   typedef Graph::Node Node;
    34   typedef Graph::EdgeIt EdgeIt;
    35   typedef Graph::NodeIt NodeIt;
    36  
    37   typedef Bfs<Graph> BType;
    38   
    39   Graph G;
    40   Node n;
    41   Edge e;
    42   int l;
    43   bool b;
    44   BType::DistMap d(G);
    45   BType::PredMap p(G);
    46   //  BType::PredNodeMap pn(G);
    47   
    48   BType bfs_test(G);
    49   
    50   bfs_test.run(n);
    51   
    52   l  = bfs_test.dist(n);
    53   e  = bfs_test.pred(n);
    54   n  = bfs_test.predNode(n);
    55   d  = bfs_test.distMap();
    56   p  = bfs_test.predMap();
    57   //  pn = bfs_test.predNodeMap();
    58   b  = bfs_test.reached(n);
    59 
    60   DirPath<Graph> pp(G);
    61   bfs_test.getPath(pp,n);
    62 }
    63 
    64 void check_Bfs_Function_Compile() 
    65 {
    66   typedef int VType;
    67   typedef concept::StaticGraph Graph;
    68 
    69   typedef Graph::Edge Edge;
    70   typedef Graph::Node Node;
    71   typedef Graph::EdgeIt EdgeIt;
    72   typedef Graph::NodeIt NodeIt;
    73   typedef concept::ReadMap<Edge,VType> LengthMap;
    74    
    75   bfs(Graph(),Node()).run();
    76   bfs(Graph()).source(Node()).run();
    77   bfs(Graph())
    78     .predMap(concept::WriteMap<Node,Edge>())
    79     .distMap(concept::WriteMap<Node,VType>())
    80     .reachedMap(concept::ReadWriteMap<Node,bool>())
    81     .processedMap(concept::WriteMap<Node,bool>())
    82     .run(Node());
    83   
    84 }
    85 
    86 int main()
    87 {
    88     
    89   typedef SmartGraph Graph;
    90 
    91   typedef Graph::Edge Edge;
    92   typedef Graph::Node Node;
    93   typedef Graph::EdgeIt EdgeIt;
    94   typedef Graph::NodeIt NodeIt;
    95   typedef Graph::EdgeMap<int> LengthMap;
    96 
    97   Graph G;
    98   Node s, t;
    99   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
   100    
   101   s=ps.outer[2];
   102   t=ps.inner[0];
   103   
   104   Bfs<Graph> bfs_test(G);
   105   bfs_test.run(s);
   106   
   107   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
   108 
   109   DirPath<Graph> p(G);
   110   check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
   111   check(p.length()==3,"getPath() found a wrong path.");
   112   
   113 
   114   for(EdgeIt e(G); e==INVALID; ++e) {
   115     Node u=G.source(e);
   116     Node v=G.target(e);
   117     check( !bfs_test.reached(u) ||
   118 	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
   119 	   "Wrong output.");
   120   }
   121 
   122   for(NodeIt v(G); v==INVALID; ++v) {
   123     check(bfs_test.reached(v),"Each node should be reached.");
   124     if ( bfs_test.pred(v)!=INVALID ) {
   125       Edge e=bfs_test.pred(v);
   126       Node u=G.source(e);
   127       check(u==bfs_test.predNode(v),"Wrong tree.");
   128       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   129 	    "Wrong distance. Difference: " 
   130 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
   131 			- 1));
   132     }
   133   }
   134 }
   135