1.1 --- a/src/work/marci/bfs_mm_test.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,114 +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/test_tools.h>
1.21 -#include <lemon/smart_graph.h>
1.22 -#include <bfs_mm.h>
1.23 -#include <lemon/concept/graph.h>
1.24 -
1.25 -using namespace lemon;
1.26 -
1.27 -const int PET_SIZE =5;
1.28 -
1.29 -
1.30 -void check_Bfs_Compile()
1.31 -{
1.32 - typedef concept::StaticGraph Graph;
1.33 -
1.34 - typedef Graph::Edge Edge;
1.35 - typedef Graph::Node Node;
1.36 - typedef Graph::EdgeIt EdgeIt;
1.37 - typedef Graph::NodeIt NodeIt;
1.38 -
1.39 - typedef marci::Bfs<Graph> BType;
1.40 -
1.41 - Graph G;
1.42 - Node n;
1.43 - Edge e;
1.44 - int l;
1.45 - bool b;
1.46 - BType::DistMap d(G);
1.47 - BType::PredMap p(G);
1.48 - BType::PredNodeMap pn(G);
1.49 -
1.50 - Graph::NodeMap<bool> reached(G);
1.51 - Graph::NodeMap<Edge> pred(G);
1.52 - Graph::NodeMap<Node> pred_node(G);
1.53 - Graph::NodeMap<int> dist(G);
1.54 - BType bfs_test(G, reached, pred, pred_node, dist);
1.55 -
1.56 - bfs_test.run(n);
1.57 -
1.58 - l = bfs_test.dist(n);
1.59 - e = bfs_test.pred(n);
1.60 - n = bfs_test.predNode(n);
1.61 - d = bfs_test.distMap();
1.62 - p = bfs_test.predMap();
1.63 - pn = bfs_test.predNodeMap();
1.64 - b = bfs_test.reached(n);
1.65 -
1.66 -}
1.67 -
1.68 -int main()
1.69 -{
1.70 -
1.71 - typedef SmartGraph Graph;
1.72 -
1.73 - typedef Graph::Edge Edge;
1.74 - typedef Graph::Node Node;
1.75 - typedef Graph::EdgeIt EdgeIt;
1.76 - typedef Graph::NodeIt NodeIt;
1.77 - typedef Graph::EdgeMap<int> LengthMap;
1.78 -
1.79 - Graph G;
1.80 - Node s, t;
1.81 - PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
1.82 -
1.83 - s=ps.outer[2];
1.84 - t=ps.inner[0];
1.85 -
1.86 - Graph::NodeMap<bool> reached(G);
1.87 - Graph::NodeMap<Edge> pred(G);
1.88 - Graph::NodeMap<Node> pred_node(G);
1.89 - Graph::NodeMap<int> dist(G);
1.90 - marci::Bfs<Graph> bfs_test(G, reached, pred, pred_node, dist);
1.91 - bfs_test.run(s);
1.92 -
1.93 -// check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
1.94 -
1.95 -
1.96 -// for(EdgeIt e(G); e==INVALID; ++e) {
1.97 -// Node u=G.source(e);
1.98 -// Node v=G.target(e);
1.99 -// check( !bfs_test.reached(u) ||
1.100 -// (bfs_test.dist(v) > bfs_test.dist(u)+1),
1.101 -// "Wrong output.");
1.102 -// }
1.103 -
1.104 -// for(NodeIt v(G); v==INVALID; ++v) {
1.105 -// check(bfs_test.reached(v),"Each node should be reached.");
1.106 -// if ( bfs_test.pred(v)!=INVALID ) {
1.107 -// Edge e=bfs_test.pred(v);
1.108 -// Node u=G.source(e);
1.109 -// check(u==bfs_test.predNode(v),"Wrong tree.");
1.110 -// check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
1.111 -// "Wrong distance. Difference: "
1.112 -// << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
1.113 -// - 1));
1.114 -// }
1.115 -// }
1.116 -}
1.117 -