|
marci@45
|
1 |
#include <iostream>
|
|
marci@45
|
2 |
#include <vector>
|
|
marci@45
|
3 |
#include <string>
|
|
marci@45
|
4 |
|
|
marci@45
|
5 |
#include <list_graph.hh>
|
|
marci@45
|
6 |
#include <bfs_iterator.hh>
|
|
marci@45
|
7 |
|
|
marci@45
|
8 |
using namespace marci;
|
|
marci@45
|
9 |
|
|
marci@45
|
10 |
int main (int, char*[])
|
|
marci@45
|
11 |
{
|
|
marci@45
|
12 |
typedef ListGraph::NodeIt NodeIt;
|
|
marci@45
|
13 |
typedef ListGraph::EdgeIt EdgeIt;
|
|
marci@45
|
14 |
typedef ListGraph::EachNodeIt EachNodeIt;
|
|
marci@45
|
15 |
typedef ListGraph::EachEdgeIt EachEdgeIt;
|
|
marci@45
|
16 |
typedef ListGraph::OutEdgeIt OutEdgeIt;
|
|
marci@45
|
17 |
typedef ListGraph::InEdgeIt InEdgeIt;
|
|
marci@45
|
18 |
typedef ListGraph::SymEdgeIt SymEdgeIt;
|
|
marci@45
|
19 |
|
|
marci@45
|
20 |
ListGraph G;
|
|
marci@45
|
21 |
|
|
marci@45
|
22 |
NodeIt s=G.addNode();
|
|
marci@45
|
23 |
NodeIt v1=G.addNode();
|
|
marci@45
|
24 |
NodeIt v2=G.addNode();
|
|
marci@45
|
25 |
NodeIt v3=G.addNode();
|
|
marci@45
|
26 |
NodeIt v4=G.addNode();
|
|
marci@45
|
27 |
NodeIt t=G.addNode();
|
|
marci@45
|
28 |
|
|
marci@45
|
29 |
G.addEdge(s, v1);
|
|
marci@45
|
30 |
G.addEdge(s, v2);
|
|
marci@45
|
31 |
G.addEdge(v1, v2);
|
|
marci@45
|
32 |
G.addEdge(v2, v1);
|
|
marci@45
|
33 |
G.addEdge(v1, v3);
|
|
marci@45
|
34 |
G.addEdge(v3, v2);
|
|
marci@45
|
35 |
G.addEdge(v2, v4);
|
|
marci@45
|
36 |
G.addEdge(v4, v3);
|
|
marci@45
|
37 |
G.addEdge(v3, t);
|
|
marci@45
|
38 |
G.addEdge(v4, t);
|
|
marci@45
|
39 |
|
|
marci@45
|
40 |
std::cout << "bfs and dfs demo on the directed graph" << std::endl;
|
|
marci@45
|
41 |
for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
|
|
marci@45
|
42 |
std::cout << i << ": ";
|
|
marci@45
|
43 |
std::cout << "out edges: ";
|
|
marci@45
|
44 |
for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
|
|
marci@45
|
45 |
std::cout << j << " ";
|
|
marci@45
|
46 |
std::cout << "in edges: ";
|
|
marci@45
|
47 |
for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
|
|
marci@45
|
48 |
std::cout << j << " ";
|
|
marci@45
|
49 |
std::cout << std::endl;
|
|
marci@45
|
50 |
}
|
|
marci@45
|
51 |
|
|
marci@45
|
52 |
//std::cout << std::endl;
|
|
marci@45
|
53 |
//EachNodeIt u1=G.first<EachNodeIt>();
|
|
marci@45
|
54 |
//EachEdgeIt u=G.first<EachEdgeIt>();
|
|
marci@45
|
55 |
//OutEdgeIt u=G.first<OutEdgeIt>(s);
|
|
marci@45
|
56 |
//InEdgeIt u=G.first<InEdgeIt>(s);
|
|
marci@45
|
57 |
//SymEdgeIt u=G.first<SymEdgeIt>(s);
|
|
marci@45
|
58 |
//OutEdgeIt u=G.first<OutEdgeIt>(s);
|
|
marci@45
|
59 |
//EachNodeIt u=G.first<EachNodeIt>();
|
|
marci@45
|
60 |
//EachEdgeIt u=G.first<EachEdgeIt>();
|
|
marci@45
|
61 |
//OutEdgeIt u=G.first<OutEdgeIt>(s);
|
|
marci@45
|
62 |
//InEdgeIt u=G.first<InEdgeIt>(s);
|
|
marci@45
|
63 |
//SymEdgeIt u=G.first<SymEdgeIt>(s);
|
|
marci@45
|
64 |
//u=G.first(s);
|
|
marci@45
|
65 |
//u=G.first_ize(s, OutEdgeIt());
|
|
marci@45
|
66 |
//std::cout << "ize " << u << std::endl;
|
|
marci@45
|
67 |
|
|
marci@45
|
68 |
/*
|
|
marci@45
|
69 |
{
|
|
marci@45
|
70 |
std::cout << "iterator bfs demo..." << std::endl;
|
|
marci@45
|
71 |
NodePropertyVector<ListGraph, bool> reached(G, false);
|
|
marci@45
|
72 |
reached.set(s, true);
|
|
marci@45
|
73 |
std::queue<ListGraph::OutEdgeIt> bfs_queue;
|
|
marci@45
|
74 |
bfs_queue.push(G.firstOutEdge(G.firstNode()));
|
|
marci@45
|
75 |
BfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > bfs(G, bfs_queue, reached);
|
|
marci@45
|
76 |
for ( ; !bfs.finished(); ++bfs) {
|
|
marci@45
|
77 |
if (OutEdgeIt(bfs).valid()) {
|
|
marci@45
|
78 |
std::cout << "OutEdgeIt: " << bfs;
|
|
marci@45
|
79 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
80 |
std::cout << " bNode: " << G.bNode(bfs) << " ";
|
|
marci@45
|
81 |
} else {
|
|
marci@45
|
82 |
std::cout << "OutEdgeIt: " << "invalid";
|
|
marci@45
|
83 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
84 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
85 |
}
|
|
marci@45
|
86 |
if (bfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
87 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
88 |
} else {
|
|
marci@45
|
89 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
90 |
}
|
|
marci@45
|
91 |
if (bfs.aNodeIsExamined()) {
|
|
marci@45
|
92 |
std::cout << "aNodeIsExamined ";
|
|
marci@45
|
93 |
} else {
|
|
marci@45
|
94 |
std::cout << "aNodeIsNotExamined ";
|
|
marci@45
|
95 |
}
|
|
marci@45
|
96 |
std::cout<<std::endl;
|
|
marci@45
|
97 |
}
|
|
marci@45
|
98 |
}
|
|
marci@45
|
99 |
|
|
marci@45
|
100 |
{
|
|
marci@45
|
101 |
std::cout << "iterator dfs demo..." << std::endl;
|
|
marci@45
|
102 |
NodePropertyVector<ListGraph, bool> reached(G, false);
|
|
marci@45
|
103 |
reached.set(s, true);
|
|
marci@45
|
104 |
std::stack<ListGraph::OutEdgeIt> dfs_stack;
|
|
marci@45
|
105 |
dfs_stack.push(G.firstOutEdge(G.firstNode()));
|
|
marci@45
|
106 |
DfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > dfs(G, dfs_stack, reached);
|
|
marci@45
|
107 |
for(; !dfs.finished(); ++dfs) {
|
|
marci@45
|
108 |
if (OutEdgeIt(dfs).valid()) {
|
|
marci@45
|
109 |
std::cout << "OutEdgeIt: " << dfs;
|
|
marci@45
|
110 |
std::cout << " aNode: " << G.aNode(dfs);
|
|
marci@45
|
111 |
std::cout << " bNode: " << G.bNode(dfs) << " ";
|
|
marci@45
|
112 |
} else {
|
|
marci@45
|
113 |
std::cout << "OutEdgeIt: " << "invalid";
|
|
marci@45
|
114 |
std::cout << " aNode: " << G.aNode(dfs);
|
|
marci@45
|
115 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
116 |
}
|
|
marci@45
|
117 |
if (dfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
118 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
119 |
} else {
|
|
marci@45
|
120 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
121 |
}
|
|
marci@45
|
122 |
if (dfs.aNodeIsLeaved()) {
|
|
marci@45
|
123 |
std::cout << "aNodeIsLeaved ";
|
|
marci@45
|
124 |
} else {
|
|
marci@45
|
125 |
std::cout << "aNodeIsNotLeaved ";
|
|
marci@45
|
126 |
}
|
|
marci@45
|
127 |
std::cout<<std::endl;
|
|
marci@45
|
128 |
}
|
|
marci@45
|
129 |
if (OutEdgeIt(dfs).valid()) {
|
|
marci@45
|
130 |
std::cout << "OutEdgeIt: " << dfs;
|
|
marci@45
|
131 |
std::cout << " aNode: " << G.aNode(dfs);
|
|
marci@45
|
132 |
std::cout << " bNode: " << G.bNode(dfs) << " ";
|
|
marci@45
|
133 |
} else {
|
|
marci@45
|
134 |
std::cout << "OutEdgeIt: " << "invalid";
|
|
marci@45
|
135 |
std::cout << " aNode: " << G.aNode(dfs);
|
|
marci@45
|
136 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
137 |
}
|
|
marci@45
|
138 |
if (dfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
139 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
140 |
} else {
|
|
marci@45
|
141 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
142 |
}
|
|
marci@45
|
143 |
if (dfs.aNodeIsLeaved()) {
|
|
marci@45
|
144 |
std::cout << "aNodeIsLeaved ";
|
|
marci@45
|
145 |
} else {
|
|
marci@45
|
146 |
std::cout << "aNodeIsNotLeaved ";
|
|
marci@45
|
147 |
}
|
|
marci@45
|
148 |
std::cout<<std::endl;
|
|
marci@45
|
149 |
}
|
|
marci@45
|
150 |
*/
|
|
marci@45
|
151 |
|
|
marci@45
|
152 |
{
|
|
marci@45
|
153 |
std::cout << "iterator bfs demo 1 ..." << std::endl;
|
|
marci@45
|
154 |
ListGraph::NodeMap<bool> reached(G, false);
|
|
marci@45
|
155 |
reached.set(s, true);
|
|
marci@45
|
156 |
std::queue<ListGraph::OutEdgeIt> bfs_queue;
|
|
marci@45
|
157 |
bfs_queue.push(G.first<OutEdgeIt>(s));
|
|
marci@45
|
158 |
BfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
|
|
marci@45
|
159 |
while (!bfs.finished()) {
|
|
marci@45
|
160 |
if (OutEdgeIt(bfs).valid()) {
|
|
marci@45
|
161 |
std::cout << "OutEdgeIt: " << bfs;
|
|
marci@45
|
162 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
163 |
std::cout << " bNode: " << G.bNode(bfs) << " ";
|
|
marci@45
|
164 |
} else {
|
|
marci@45
|
165 |
std::cout << "OutEdgeIt: " << "invalid";
|
|
marci@45
|
166 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
167 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
168 |
}
|
|
marci@45
|
169 |
if (bfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
170 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
171 |
} else {
|
|
marci@45
|
172 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
173 |
}
|
|
marci@45
|
174 |
if (bfs.aNodeIsExamined()) {
|
|
marci@45
|
175 |
std::cout << "aNodeIsExamined ";
|
|
marci@45
|
176 |
} else {
|
|
marci@45
|
177 |
std::cout << "aNodeIsNotExamined ";
|
|
marci@45
|
178 |
}
|
|
marci@45
|
179 |
std::cout<<std::endl;
|
|
marci@45
|
180 |
bfs.next();
|
|
marci@45
|
181 |
}
|
|
marci@45
|
182 |
}
|
|
marci@45
|
183 |
|
|
marci@59
|
184 |
{
|
|
marci@59
|
185 |
std::cout << "iterator bfs demo 2 ..." << std::endl;
|
|
marci@59
|
186 |
//ListGraph::NodeMap<bool> reached(G, false);
|
|
marci@59
|
187 |
//reached.set(s, true);
|
|
marci@59
|
188 |
//std::queue<ListGraph::OutEdgeIt> bfs_queue;
|
|
marci@59
|
189 |
//bfs_queue.push(G.first<OutEdgeIt>(s));
|
|
marci@59
|
190 |
BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
|
|
marci@59
|
191 |
bfs.pushAndSetReached(s);
|
|
marci@59
|
192 |
while (!bfs.finished()) {
|
|
marci@59
|
193 |
if (OutEdgeIt(bfs).valid()) {
|
|
marci@59
|
194 |
std::cout << "OutEdgeIt: " << bfs;
|
|
marci@59
|
195 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@59
|
196 |
std::cout << " bNode: " << G.bNode(bfs) << " ";
|
|
marci@59
|
197 |
} else {
|
|
marci@59
|
198 |
std::cout << "OutEdgeIt: " << "invalid";
|
|
marci@59
|
199 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@59
|
200 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@59
|
201 |
}
|
|
marci@59
|
202 |
if (bfs.isBNodeNewlyReached()) {
|
|
marci@59
|
203 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@59
|
204 |
} else {
|
|
marci@59
|
205 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@59
|
206 |
}
|
|
marci@59
|
207 |
if (bfs.isANodeExamined()) {
|
|
marci@59
|
208 |
std::cout << "aNodeIsExamined ";
|
|
marci@59
|
209 |
} else {
|
|
marci@59
|
210 |
std::cout << "aNodeIsNotExamined ";
|
|
marci@59
|
211 |
}
|
|
marci@59
|
212 |
std::cout<<std::endl;
|
|
marci@59
|
213 |
++bfs;
|
|
marci@59
|
214 |
}
|
|
marci@59
|
215 |
}
|
|
marci@59
|
216 |
|
|
marci@59
|
217 |
|
|
marci@59
|
218 |
|
|
marci@45
|
219 |
|
|
marci@45
|
220 |
{
|
|
marci@45
|
221 |
std::cout << "iterator dfs demo 1..." << std::endl;
|
|
marci@45
|
222 |
ListGraph::NodeMap<bool> reached(G, false);
|
|
marci@45
|
223 |
reached.set(s, true);
|
|
marci@45
|
224 |
std::stack<ListGraph::OutEdgeIt> dfs_stack;
|
|
marci@45
|
225 |
dfs_stack.push(G.first<OutEdgeIt>(s));
|
|
marci@45
|
226 |
DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);
|
|
marci@45
|
227 |
do {
|
|
marci@45
|
228 |
dfs.next();
|
|
marci@45
|
229 |
if (OutEdgeIt(dfs).valid()) {
|
|
marci@45
|
230 |
std::cout << "OutEdgeIt: " << dfs;
|
|
marci@45
|
231 |
std::cout << " aNode: " << G.aNode(dfs);
|
|
marci@45
|
232 |
std::cout << " bNode: " << G.bNode(dfs) << " ";
|
|
marci@45
|
233 |
} else {
|
|
marci@45
|
234 |
std::cout << "OutEdgeIt: " << "invalid";
|
|
marci@45
|
235 |
std::cout << " aNode: " << G.aNode(dfs);
|
|
marci@45
|
236 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
237 |
}
|
|
marci@45
|
238 |
if (dfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
239 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
240 |
} else {
|
|
marci@45
|
241 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
242 |
}
|
|
marci@45
|
243 |
if (dfs.aNodeIsLeaved()) {
|
|
marci@45
|
244 |
std::cout << "aNodeIsLeaved ";
|
|
marci@45
|
245 |
} else {
|
|
marci@45
|
246 |
std::cout << "aNodeIsNotLeaved ";
|
|
marci@45
|
247 |
}
|
|
marci@45
|
248 |
std::cout<<std::endl;
|
|
marci@45
|
249 |
} while (!dfs.finished());
|
|
marci@45
|
250 |
}
|
|
marci@45
|
251 |
|
|
marci@45
|
252 |
|
|
marci@45
|
253 |
{
|
|
marci@45
|
254 |
std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;
|
|
marci@45
|
255 |
ListGraph::NodeMap<bool> reached(G, false);
|
|
marci@45
|
256 |
reached.set(t, true);
|
|
marci@45
|
257 |
std::queue<ListGraph::InEdgeIt> bfs_queue;
|
|
marci@45
|
258 |
bfs_queue.push(G.first<InEdgeIt>(t));
|
|
marci@45
|
259 |
BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
|
|
marci@45
|
260 |
while (!bfs.finished()) {
|
|
marci@45
|
261 |
if (InEdgeIt(bfs).valid()) {
|
|
marci@45
|
262 |
std::cout << "InEdgeIt: " << bfs;
|
|
marci@45
|
263 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
264 |
std::cout << " bNode: " << G.bNode(bfs) << " ";
|
|
marci@45
|
265 |
} else {
|
|
marci@45
|
266 |
std::cout << "InEdgeIt: " << "invalid";
|
|
marci@45
|
267 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
268 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
269 |
}
|
|
marci@45
|
270 |
if (bfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
271 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
272 |
} else {
|
|
marci@45
|
273 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
274 |
}
|
|
marci@45
|
275 |
if (bfs.aNodeIsExamined()) {
|
|
marci@45
|
276 |
std::cout << "aNodeIsExamined ";
|
|
marci@45
|
277 |
} else {
|
|
marci@45
|
278 |
std::cout << "aNodeIsNotExamined ";
|
|
marci@45
|
279 |
}
|
|
marci@45
|
280 |
std::cout<<std::endl;
|
|
marci@45
|
281 |
bfs.next();
|
|
marci@45
|
282 |
}
|
|
marci@45
|
283 |
}
|
|
marci@45
|
284 |
|
|
marci@45
|
285 |
|
|
marci@45
|
286 |
{
|
|
marci@45
|
287 |
std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;
|
|
marci@45
|
288 |
ListGraph::NodeMap<bool> reached(G, false);
|
|
marci@45
|
289 |
reached.set(t, true);
|
|
marci@45
|
290 |
std::queue<ListGraph::SymEdgeIt> bfs_queue;
|
|
marci@45
|
291 |
bfs_queue.push(G.first<SymEdgeIt>(t));
|
|
marci@45
|
292 |
BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
|
|
marci@45
|
293 |
while (!bfs.finished()) {
|
|
marci@45
|
294 |
if (SymEdgeIt(bfs).valid()) {
|
|
marci@45
|
295 |
std::cout << "SymEdgeIt: " << bfs;
|
|
marci@45
|
296 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
297 |
std::cout << " bNode: " << G.bNode(bfs) << " ";
|
|
marci@45
|
298 |
} else {
|
|
marci@45
|
299 |
std::cout << "SymEdgeIt: " << "invalid";
|
|
marci@45
|
300 |
std::cout << " aNode: " << G.aNode(bfs);
|
|
marci@45
|
301 |
std::cout << " bNode: " << "invalid" << " ";
|
|
marci@45
|
302 |
}
|
|
marci@45
|
303 |
if (bfs.bNodeIsNewlyReached()) {
|
|
marci@45
|
304 |
std::cout << "bNodeIsNewlyReached ";
|
|
marci@45
|
305 |
} else {
|
|
marci@45
|
306 |
std::cout << "bNodeIsNotNewlyReached ";
|
|
marci@45
|
307 |
}
|
|
marci@45
|
308 |
if (bfs.aNodeIsExamined()) {
|
|
marci@45
|
309 |
std::cout << "aNodeIsExamined ";
|
|
marci@45
|
310 |
} else {
|
|
marci@45
|
311 |
std::cout << "aNodeIsNotExamined ";
|
|
marci@45
|
312 |
}
|
|
marci@45
|
313 |
std::cout<<std::endl;
|
|
marci@45
|
314 |
bfs.next();
|
|
marci@45
|
315 |
}
|
|
marci@45
|
316 |
}
|
|
marci@45
|
317 |
|
|
marci@45
|
318 |
return 0;
|
|
marci@45
|
319 |
}
|