alpar@906: /* -*- C++ -*-
alpar@921:  * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@1164:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
marci@944: #include <test/test_tools.h>
alpar@921: #include <lemon/smart_graph.h>
marci@944: #include <bfs_mm.h>
klao@959: #include <lemon/concept/graph.h>
alpar@774: 
alpar@921: using namespace lemon;
alpar@774: 
alpar@774: const int PET_SIZE =5;
alpar@774: 
alpar@774: 
alpar@793: void check_Bfs_Compile() 
alpar@774: {
klao@959:   typedef concept::StaticGraph Graph;
alpar@774: 
alpar@774:   typedef Graph::Edge Edge;
alpar@774:   typedef Graph::Node Node;
alpar@774:   typedef Graph::EdgeIt EdgeIt;
alpar@774:   typedef Graph::NodeIt NodeIt;
alpar@774:  
marci@944:   typedef marci::Bfs<Graph> BType;
alpar@774:   
alpar@774:   Graph G;
alpar@774:   Node n;
alpar@774:   Edge e;
alpar@793:   int l;
alpar@774:   bool b;
alpar@774:   BType::DistMap d(G);
alpar@774:   BType::PredMap p(G);
alpar@774:   BType::PredNodeMap pn(G);
marci@944: 
marci@944:    Graph::NodeMap<bool> reached(G);
marci@944:    Graph::NodeMap<Edge> pred(G);
marci@944:    Graph::NodeMap<Node> pred_node(G);
marci@944:    Graph::NodeMap<int> dist(G);  
marci@944:    BType bfs_test(G, reached, pred, pred_node, dist);
alpar@774:   
alpar@774:   bfs_test.run(n);
alpar@774:   
alpar@774:   l  = bfs_test.dist(n);
alpar@774:   e  = bfs_test.pred(n);
alpar@774:   n  = bfs_test.predNode(n);
alpar@774:   d  = bfs_test.distMap();
alpar@774:   p  = bfs_test.predMap();
alpar@774:   pn = bfs_test.predNodeMap();
alpar@774:   b  = bfs_test.reached(n);
alpar@774: 
alpar@774: }
alpar@774: 
alpar@774: int main()
alpar@774: {
alpar@774:     
alpar@774:   typedef SmartGraph Graph;
alpar@774: 
alpar@774:   typedef Graph::Edge Edge;
alpar@774:   typedef Graph::Node Node;
alpar@774:   typedef Graph::EdgeIt EdgeIt;
alpar@774:   typedef Graph::NodeIt NodeIt;
alpar@774:   typedef Graph::EdgeMap<int> LengthMap;
alpar@774: 
alpar@774:   Graph G;
alpar@774:   Node s, t;
alpar@774:   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@774:    
alpar@774:   s=ps.outer[2];
alpar@774:   t=ps.inner[0];
alpar@774:   
marci@944:    Graph::NodeMap<bool> reached(G);
marci@944:    Graph::NodeMap<Edge> pred(G);
marci@944:    Graph::NodeMap<Node> pred_node(G);
marci@944:    Graph::NodeMap<int> dist(G);
marci@944:    marci::Bfs<Graph> bfs_test(G, reached, pred, pred_node, dist);
alpar@774:   bfs_test.run(s);
alpar@774:   
marci@944: //   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
alpar@774: 
alpar@774: 
marci@944: //   for(EdgeIt e(G); e==INVALID; ++e) {
alpar@986: //     Node u=G.source(e);
alpar@986: //     Node v=G.target(e);
marci@944: //     check( !bfs_test.reached(u) ||
marci@944: // 	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
marci@944: // 	   "Wrong output.");
marci@944: //   }
alpar@774: 
marci@944: //   for(NodeIt v(G); v==INVALID; ++v) {
marci@944: //     check(bfs_test.reached(v),"Each node should be reached.");
marci@944: //     if ( bfs_test.pred(v)!=INVALID ) {
marci@944: //       Edge e=bfs_test.pred(v);
alpar@986: //       Node u=G.source(e);
marci@944: //       check(u==bfs_test.predNode(v),"Wrong tree.");
marci@944: //       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
marci@944: // 	    "Wrong distance. Difference: " 
marci@944: // 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
marci@944: // 			- 1));
marci@944: //     }
marci@944: //   }
alpar@774: }
alpar@780: