alpar@906: /* -*- C++ -*-
ladanyi@1435:  * test/dfs_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: 
alpar@780: #include "test_tools.h"
alpar@921: #include <lemon/smart_graph.h>
alpar@921: #include <lemon/dfs.h>
alpar@1283: #include <lemon/path.h>
klao@959: #include <lemon/concept/graph.h>
alpar@780: 
alpar@921: using namespace lemon;
alpar@780: 
alpar@780: const int PET_SIZE =5;
alpar@780: 
alpar@780: 
alpar@780: void check_Dfs_SmartGraph_Compile() 
alpar@780: {
klao@959:   typedef concept::StaticGraph Graph;
alpar@780: 
alpar@780:   typedef Graph::Edge Edge;
alpar@780:   typedef Graph::Node Node;
alpar@780:   typedef Graph::EdgeIt EdgeIt;
alpar@780:   typedef Graph::NodeIt NodeIt;
alpar@780:  
alpar@793:   typedef Dfs<Graph> DType;
alpar@780:   
alpar@780:   Graph G;
alpar@780:   Node n;
alpar@780:   Edge e;
alpar@793:   int l;
alpar@780:   bool b;
alpar@793:   DType::DistMap d(G);
alpar@793:   DType::PredMap p(G);
alpar@1218:   //  DType::PredNodeMap pn(G);
alpar@780:   
alpar@793:   DType dfs_test(G);
alpar@780:   
alpar@780:   dfs_test.run(n);
alpar@780:   
alpar@780:   l  = dfs_test.dist(n);
alpar@780:   e  = dfs_test.pred(n);
alpar@780:   n  = dfs_test.predNode(n);
alpar@780:   d  = dfs_test.distMap();
alpar@780:   p  = dfs_test.predMap();
alpar@1218:   //  pn = dfs_test.predNodeMap();
alpar@780:   b  = dfs_test.reached(n);
alpar@780: 
alpar@1283:   DirPath<Graph> pp(G);
alpar@1283:   dfs_test.getPath(pp,n);
alpar@780: }
alpar@780: 
alpar@1220: 
alpar@1220: void check_Dfs_Function_Compile() 
alpar@1220: {
alpar@1220:   typedef int VType;
alpar@1220:   typedef concept::StaticGraph Graph;
alpar@1220: 
alpar@1220:   typedef Graph::Edge Edge;
alpar@1220:   typedef Graph::Node Node;
alpar@1220:   typedef Graph::EdgeIt EdgeIt;
alpar@1220:   typedef Graph::NodeIt NodeIt;
alpar@1220:   typedef concept::ReadMap<Edge,VType> LengthMap;
alpar@1220:    
alpar@1220:   dfs(Graph(),Node()).run();
alpar@1220:   dfs(Graph()).source(Node()).run();
alpar@1220:   dfs(Graph())
alpar@1220:     .predMap(concept::WriteMap<Node,Edge>())
alpar@1220:     .distMap(concept::WriteMap<Node,VType>())
alpar@1220:     .reachedMap(concept::ReadWriteMap<Node,bool>())
alpar@1220:     .processedMap(concept::WriteMap<Node,bool>())
alpar@1220:     .run(Node());
alpar@1220:   
alpar@1220: }
alpar@1220: 
alpar@780: int main()
alpar@780: {
alpar@780:     
alpar@780:   typedef SmartGraph Graph;
alpar@780: 
alpar@780:   typedef Graph::Edge Edge;
alpar@780:   typedef Graph::Node Node;
alpar@780:   typedef Graph::EdgeIt EdgeIt;
alpar@780:   typedef Graph::NodeIt NodeIt;
alpar@780:   typedef Graph::EdgeMap<int> LengthMap;
alpar@780: 
alpar@780:   Graph G;
alpar@780:   Node s, t;
alpar@780:   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@780:    
alpar@780:   s=ps.outer[2];
alpar@780:   t=ps.inner[0];
alpar@780:   
alpar@780:   Dfs<Graph> dfs_test(G);
alpar@780:   dfs_test.run(s);  
alpar@780:   
alpar@1283:   DirPath<Graph> p(G);
alpar@1283:   check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
alpar@1283:   check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
alpar@1283:   
alpar@780:   for(NodeIt v(G); v!=INVALID; ++v) {
alpar@780:     check(dfs_test.reached(v),"Each node should be reached.");
alpar@780:     if ( dfs_test.pred(v)!=INVALID ) {
alpar@780:       Edge e=dfs_test.pred(v);
alpar@986:       Node u=G.source(e);
alpar@780:       check(u==dfs_test.predNode(v),"Wrong tree.");
alpar@780:       check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
alpar@1233: 	    "Wrong distance. (" << dfs_test.dist(u) << "->" 
alpar@1233: 	    <<dfs_test.dist(v) << ')');
alpar@780:     }
alpar@780:   }
alpar@780: }
alpar@780: