COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bfs_test.cc @ 2247:269a0dcee70b

Last change on this file since 2247:269a0dcee70b was 2247:269a0dcee70b, checked in by Balazs Dezso, 13 years ago

Update the Path concept
Concept check for paths

DirPath? renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed

I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

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