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