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