1.1 --- a/src/test/bfs_test.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,135 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#include "test_tools.h"
1.21 -#include <lemon/smart_graph.h>
1.22 -#include <lemon/bfs.h>
1.23 -#include <lemon/path.h>
1.24 -#include<lemon/concept/graph.h>
1.25 -
1.26 -using namespace lemon;
1.27 -
1.28 -const int PET_SIZE =5;
1.29 -
1.30 -
1.31 -void check_Bfs_Compile()
1.32 -{
1.33 - typedef concept::StaticGraph Graph;
1.34 -
1.35 - typedef Graph::Edge Edge;
1.36 - typedef Graph::Node Node;
1.37 - typedef Graph::EdgeIt EdgeIt;
1.38 - typedef Graph::NodeIt NodeIt;
1.39 -
1.40 - typedef Bfs<Graph> BType;
1.41 -
1.42 - Graph G;
1.43 - Node n;
1.44 - Edge e;
1.45 - int l;
1.46 - bool b;
1.47 - BType::DistMap d(G);
1.48 - BType::PredMap p(G);
1.49 - // BType::PredNodeMap pn(G);
1.50 -
1.51 - BType bfs_test(G);
1.52 -
1.53 - bfs_test.run(n);
1.54 -
1.55 - l = bfs_test.dist(n);
1.56 - e = bfs_test.pred(n);
1.57 - n = bfs_test.predNode(n);
1.58 - d = bfs_test.distMap();
1.59 - p = bfs_test.predMap();
1.60 - // pn = bfs_test.predNodeMap();
1.61 - b = bfs_test.reached(n);
1.62 -
1.63 - DirPath<Graph> pp(G);
1.64 - bfs_test.getPath(pp,n);
1.65 -}
1.66 -
1.67 -void check_Bfs_Function_Compile()
1.68 -{
1.69 - typedef int VType;
1.70 - typedef concept::StaticGraph Graph;
1.71 -
1.72 - typedef Graph::Edge Edge;
1.73 - typedef Graph::Node Node;
1.74 - typedef Graph::EdgeIt EdgeIt;
1.75 - typedef Graph::NodeIt NodeIt;
1.76 - typedef concept::ReadMap<Edge,VType> LengthMap;
1.77 -
1.78 - bfs(Graph(),Node()).run();
1.79 - bfs(Graph()).source(Node()).run();
1.80 - bfs(Graph())
1.81 - .predMap(concept::WriteMap<Node,Edge>())
1.82 - .distMap(concept::WriteMap<Node,VType>())
1.83 - .reachedMap(concept::ReadWriteMap<Node,bool>())
1.84 - .processedMap(concept::WriteMap<Node,bool>())
1.85 - .run(Node());
1.86 -
1.87 -}
1.88 -
1.89 -int main()
1.90 -{
1.91 -
1.92 - typedef SmartGraph Graph;
1.93 -
1.94 - typedef Graph::Edge Edge;
1.95 - typedef Graph::Node Node;
1.96 - typedef Graph::EdgeIt EdgeIt;
1.97 - typedef Graph::NodeIt NodeIt;
1.98 - typedef Graph::EdgeMap<int> LengthMap;
1.99 -
1.100 - Graph G;
1.101 - Node s, t;
1.102 - PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
1.103 -
1.104 - s=ps.outer[2];
1.105 - t=ps.inner[0];
1.106 -
1.107 - Bfs<Graph> bfs_test(G);
1.108 - bfs_test.run(s);
1.109 -
1.110 - check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
1.111 -
1.112 - DirPath<Graph> p(G);
1.113 - check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
1.114 - check(p.length()==3,"getPath() found a wrong path.");
1.115 -
1.116 -
1.117 - for(EdgeIt e(G); e==INVALID; ++e) {
1.118 - Node u=G.source(e);
1.119 - Node v=G.target(e);
1.120 - check( !bfs_test.reached(u) ||
1.121 - (bfs_test.dist(v) > bfs_test.dist(u)+1),
1.122 - "Wrong output.");
1.123 - }
1.124 -
1.125 - for(NodeIt v(G); v==INVALID; ++v) {
1.126 - check(bfs_test.reached(v),"Each node should be reached.");
1.127 - if ( bfs_test.pred(v)!=INVALID ) {
1.128 - Edge e=bfs_test.pred(v);
1.129 - Node u=G.source(e);
1.130 - check(u==bfs_test.predNode(v),"Wrong tree.");
1.131 - check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
1.132 - "Wrong distance. Difference: "
1.133 - << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
1.134 - - 1));
1.135 - }
1.136 - }
1.137 -}
1.138 -