COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_mm_test.cc @ 1139:f59038affc7e

Last change on this file since 1139:f59038affc7e was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 2.8 KB
Line 
1/* -*- C++ -*-
2 * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#include <test/test_tools.h>
18#include <lemon/smart_graph.h>
19#include <bfs_mm.h>
20#include <lemon/concept/graph.h>
21
22using namespace lemon;
23
24const int PET_SIZE =5;
25
26
27void check_Bfs_Compile()
28{
29  typedef concept::StaticGraph Graph;
30
31  typedef Graph::Edge Edge;
32  typedef Graph::Node Node;
33  typedef Graph::EdgeIt EdgeIt;
34  typedef Graph::NodeIt NodeIt;
35 
36  typedef marci::Bfs<Graph> BType;
37 
38  Graph G;
39  Node n;
40  Edge e;
41  int l;
42  bool b;
43  BType::DistMap d(G);
44  BType::PredMap p(G);
45  BType::PredNodeMap pn(G);
46
47   Graph::NodeMap<bool> reached(G);
48   Graph::NodeMap<Edge> pred(G);
49   Graph::NodeMap<Node> pred_node(G);
50   Graph::NodeMap<int> dist(G); 
51   BType bfs_test(G, reached, pred, pred_node, dist);
52 
53  bfs_test.run(n);
54 
55  l  = bfs_test.dist(n);
56  e  = bfs_test.pred(n);
57  n  = bfs_test.predNode(n);
58  d  = bfs_test.distMap();
59  p  = bfs_test.predMap();
60  pn = bfs_test.predNodeMap();
61  b  = bfs_test.reached(n);
62
63}
64
65int main()
66{
67   
68  typedef SmartGraph Graph;
69
70  typedef Graph::Edge Edge;
71  typedef Graph::Node Node;
72  typedef Graph::EdgeIt EdgeIt;
73  typedef Graph::NodeIt NodeIt;
74  typedef Graph::EdgeMap<int> LengthMap;
75
76  Graph G;
77  Node s, t;
78  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
79   
80  s=ps.outer[2];
81  t=ps.inner[0];
82 
83   Graph::NodeMap<bool> reached(G);
84   Graph::NodeMap<Edge> pred(G);
85   Graph::NodeMap<Node> pred_node(G);
86   Graph::NodeMap<int> dist(G);
87   marci::Bfs<Graph> bfs_test(G, reached, pred, pred_node, dist);
88  bfs_test.run(s);
89 
90//   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
91
92
93//   for(EdgeIt e(G); e==INVALID; ++e) {
94//     Node u=G.source(e);
95//     Node v=G.target(e);
96//     check( !bfs_test.reached(u) ||
97//         (bfs_test.dist(v) > bfs_test.dist(u)+1),
98//         "Wrong output.");
99//   }
100
101//   for(NodeIt v(G); v==INVALID; ++v) {
102//     check(bfs_test.reached(v),"Each node should be reached.");
103//     if ( bfs_test.pred(v)!=INVALID ) {
104//       Edge e=bfs_test.pred(v);
105//       Node u=G.source(e);
106//       check(u==bfs_test.predNode(v),"Wrong tree.");
107//       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
108//          "Wrong distance. Difference: "
109//          << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
110//                      - 1));
111//     }
112//   }
113}
114
Note: See TracBrowser for help on using the repository browser.