|
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/dfs.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 checkDfsCompile()
|
|
alpar@100
|
31 |
{
|
|
alpar@100
|
32 |
typedef concepts::Digraph Digraph;
|
|
alpar@100
|
33 |
typedef Dfs<Digraph> DType;
|
|
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 |
DType::DistMap d(G);
|
|
alpar@100
|
41 |
DType::PredMap p(G);
|
|
alpar@100
|
42 |
// DType::PredNodeMap pn(G);
|
|
alpar@100
|
43 |
|
|
alpar@100
|
44 |
DType dfs_test(G);
|
|
alpar@100
|
45 |
|
|
alpar@100
|
46 |
dfs_test.run(n);
|
|
alpar@100
|
47 |
|
|
alpar@100
|
48 |
l = dfs_test.dist(n);
|
|
alpar@100
|
49 |
e = dfs_test.predArc(n);
|
|
alpar@100
|
50 |
n = dfs_test.predNode(n);
|
|
alpar@100
|
51 |
d = dfs_test.distMap();
|
|
alpar@100
|
52 |
p = dfs_test.predMap();
|
|
alpar@100
|
53 |
// pn = dfs_test.predNodeMap();
|
|
alpar@100
|
54 |
b = dfs_test.reached(n);
|
|
alpar@100
|
55 |
|
|
alpar@100
|
56 |
Path<Digraph> pp = dfs_test.path(n);
|
|
alpar@100
|
57 |
}
|
|
alpar@100
|
58 |
|
|
kpeter@171
|
59 |
void checkDfsFunctionCompile()
|
|
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 |
dfs(g,Node()).run();
|
|
alpar@100
|
68 |
dfs(g).source(Node()).run();
|
|
alpar@100
|
69 |
dfs(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>())
|
|
kpeter@171
|
74 |
.run(Node());
|
|
alpar@100
|
75 |
}
|
|
alpar@100
|
76 |
|
|
kpeter@171
|
77 |
template <class Digraph>
|
|
kpeter@171
|
78 |
void checkDfs() {
|
|
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 |
Dfs<Digraph> dfs_test(G);
|
|
alpar@100
|
89 |
dfs_test.run(s);
|
|
alpar@100
|
90 |
|
|
alpar@100
|
91 |
Path<Digraph> p = dfs_test.path(t);
|
|
kpeter@171
|
92 |
check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
|
|
alpar@100
|
93 |
check(checkPath(G, p),"path() found a wrong path.");
|
|
alpar@100
|
94 |
check(pathSource(G, p) == s,"path() found a wrong path.");
|
|
alpar@100
|
95 |
check(pathTarget(G, p) == t,"path() found a wrong path.");
|
|
alpar@100
|
96 |
|
|
alpar@100
|
97 |
for(NodeIt v(G); v!=INVALID; ++v) {
|
|
alpar@100
|
98 |
check(dfs_test.reached(v),"Each node should be reached.");
|
|
alpar@100
|
99 |
if ( dfs_test.predArc(v)!=INVALID ) {
|
|
alpar@100
|
100 |
Arc e=dfs_test.predArc(v);
|
|
alpar@100
|
101 |
Node u=G.source(e);
|
|
alpar@100
|
102 |
check(u==dfs_test.predNode(v),"Wrong tree.");
|
|
alpar@100
|
103 |
check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
|
|
alpar@100
|
104 |
"Wrong distance. (" << dfs_test.dist(u) << "->"
|
|
alpar@100
|
105 |
<<dfs_test.dist(v) << ')');
|
|
alpar@100
|
106 |
}
|
|
alpar@100
|
107 |
}
|
|
alpar@100
|
108 |
}
|
|
alpar@100
|
109 |
|
|
kpeter@171
|
110 |
int main()
|
|
kpeter@171
|
111 |
{
|
|
kpeter@171
|
112 |
checkDfs<ListDigraph>();
|
|
kpeter@171
|
113 |
checkDfs<SmartDigraph>();
|
|
kpeter@171
|
114 |
return 0;
|
|
kpeter@171
|
115 |
}
|