COIN-OR::LEMON - Graph Library

Context Navigation

source: lemon-0.x/src/work/bfs_iterator.hh @ 66:cd56b9c11492

Last change on this file since 66:cd56b9c11492 was 64:72bd463289a9, checked in by marci, 22 years ago
.
File size: 13.6 KB

Line
1	#ifndef BFS_ITERATOR_HH
2	#define BFS_ITERATOR_HH
3
4	#include <queue>
5	#include <stack>
6
7	namespace marci {
8
9	template <typename Graph>
10	struct bfs {
11	typedef typename Graph::NodeIt NodeIt;
12	typedef typename Graph::EdgeIt EdgeIt;
13	typedef typename Graph::EachNodeIt EachNodeIt;
14	typedef typename Graph::OutEdgeIt OutEdgeIt;
15	Graph& G;
16	NodeIt s;
17	typename Graph::NodeMap<bool> reached;
18	typename Graph::NodeMap<EdgeIt> pred;
19	typename Graph::NodeMap<int> dist;
20	std::queue<NodeIt> bfs_queue;
21	bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
22	bfs_queue.push(s);
23	for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
24	reached.set(i, false);
25	reached.set(s, true);
26	dist.set(s, 0);
27	}
28
29	void run() {
30	while (!bfs_queue.empty()) {
31	NodeIt v=bfs_queue.front();
32	OutEdgeIt e=G.template first<OutEdgeIt>(v);
33	bfs_queue.pop();
34	for( ; e.valid(); ++e) {
35	NodeIt w=G.bNode(e);
36	std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
37	if (!reached.get(w)) {
38	std::cout << G.id(w) << " is newly reached :-)" << std::endl;
39	bfs_queue.push(w);
40	dist.set(w, dist.get(v)+1);
41	pred.set(w, e);
42	reached.set(w, true);
43	} else {
44	std::cout << G.id(w) << " is already reached" << std::endl;
45	}
46	}
47	}
48	}
49	};
50
51	template <typename Graph>
52	struct bfs_visitor {
53	typedef typename Graph::NodeIt NodeIt;
54	typedef typename Graph::EdgeIt EdgeIt;
55	typedef typename Graph::OutEdgeIt OutEdgeIt;
56	Graph& G;
57	bfs_visitor(Graph& _G) : G(_G) { }
58	void at_previously_reached(OutEdgeIt& e) {
59	//NodeIt v=G.aNode(e);
60	NodeIt w=G.bNode(e);
61	std::cout << G.id(w) << " is already reached" << std::endl;
62	}
63	void at_newly_reached(OutEdgeIt& e) {
64	//NodeIt v=G.aNode(e);
65	NodeIt w=G.bNode(e);
66	std::cout << G.id(w) << " is newly reached :-)" << std::endl;
67	}
68	};
69
70	template <typename Graph, typename ReachedMap, typename visitor_type>
71	struct bfs_iterator {
72	typedef typename Graph::NodeIt NodeIt;
73	typedef typename Graph::EdgeIt EdgeIt;
74	typedef typename Graph::OutEdgeIt OutEdgeIt;
75	Graph& G;
76	std::queue<OutEdgeIt>& bfs_queue;
77	ReachedMap& reached;
78	visitor_type& visitor;
79	void process() {
80	while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
81	if (bfs_queue.empty()) return;
82	OutEdgeIt e=bfs_queue.front();
83	//NodeIt v=G.aNode(e);
84	NodeIt w=G.bNode(e);
85	if (!reached.get(w)) {
86	visitor.at_newly_reached(e);
87	bfs_queue.push(G.template first<OutEdgeIt>(w));
88	reached.set(w, true);
89	} else {
90	visitor.at_previously_reached(e);
91	}
92	}
93	bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
94	//while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
95	valid();
96	}
97	bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
98	//while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
99	//if (bfs_queue.empty()) return *this;
100	if (!valid()) return *this;
101	++(bfs_queue.front());
102	//while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
103	valid();
104	return *this;
105	}
106	//void next() {
107	// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
108	// if (bfs_queue.empty()) return;
109	// ++(bfs_queue.front());
110	// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
111	//}
112	bool valid() {
113	while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
114	if (bfs_queue.empty()) return false; else return true;
115	}
116	//bool finished() {
117	// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
118	// if (bfs_queue.empty()) return true; else return false;
119	//}
120	operator EdgeIt () { return bfs_queue.front(); }
121
122	};
123
124	template <typename Graph, typename ReachedMap>
125	struct bfs_iterator1 {
126	typedef typename Graph::NodeIt NodeIt;
127	typedef typename Graph::EdgeIt EdgeIt;
128	typedef typename Graph::OutEdgeIt OutEdgeIt;
129	Graph& G;
130	std::queue<OutEdgeIt>& bfs_queue;
131	ReachedMap& reached;
132	bool _newly_reached;
133	bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
134	valid();
135	if (!bfs_queue.empty() && bfs_queue.front().valid()) {
136	OutEdgeIt e=bfs_queue.front();
137	NodeIt w=G.bNode(e);
138	if (!reached.get(w)) {
139	bfs_queue.push(G.template first<OutEdgeIt>(w));
140	reached.set(w, true);
141	_newly_reached=true;
142	} else {
143	_newly_reached=false;
144	}
145	}
146	}
147	bfs_iterator1<Graph, ReachedMap>& operator++() {
148	if (!valid()) return *this;
149	++(bfs_queue.front());
150	valid();
151	if (!bfs_queue.empty() && bfs_queue.front().valid()) {
152	OutEdgeIt e=bfs_queue.front();
153	NodeIt w=G.bNode(e);
154	if (!reached.get(w)) {
155	bfs_queue.push(G.template first<OutEdgeIt>(w));
156	reached.set(w, true);
157	_newly_reached=true;
158	} else {
159	_newly_reached=false;
160	}
161	}
162	return *this;
163	}
164	bool valid() {
165	while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
166	if (bfs_queue.empty()) return false; else return true;
167	}
168	operator OutEdgeIt() { return bfs_queue.front(); }
169	//ize
170	bool newly_reached() { return _newly_reached; }
171
172	};
173
174	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
175	struct BfsIterator {
176	typedef typename Graph::NodeIt NodeIt;
177	Graph& G;
178	std::queue<OutEdgeIt>& bfs_queue;
179	ReachedMap& reached;
180	bool b_node_newly_reached;
181	OutEdgeIt actual_edge;
182	BfsIterator(Graph& _G,
183	std::queue<OutEdgeIt>& _bfs_queue,
184	ReachedMap& _reached) :
185	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
186	actual_edge=bfs_queue.front();
187	if (actual_edge.valid()) {
188	NodeIt w=G.bNode(actual_edge);
189	if (!reached.get(w)) {
190	bfs_queue.push(G.firstOutEdge(w));
191	reached.set(w, true);
192	b_node_newly_reached=true;
193	} else {
194	b_node_newly_reached=false;
195	}
196	}
197	}
198	BfsIterator<Graph, OutEdgeIt, ReachedMap>&
199	operator++() {
200	if (bfs_queue.front().valid()) {
201	++(bfs_queue.front());
202	actual_edge=bfs_queue.front();
203	if (actual_edge.valid()) {
204	NodeIt w=G.bNode(actual_edge);
205	if (!reached.get(w)) {
206	bfs_queue.push(G.firstOutEdge(w));
207	reached.set(w, true);
208	b_node_newly_reached=true;
209	} else {
210	b_node_newly_reached=false;
211	}
212	}
213	} else {
214	bfs_queue.pop();
215	actual_edge=bfs_queue.front();
216	if (actual_edge.valid()) {
217	NodeIt w=G.bNode(actual_edge);
218	if (!reached.get(w)) {
219	bfs_queue.push(G.firstOutEdge(w));
220	reached.set(w, true);
221	b_node_newly_reached=true;
222	} else {
223	b_node_newly_reached=false;
224	}
225	}
226	}
227	return *this;
228	}
229	bool finished() { return bfs_queue.empty(); }
230	operator OutEdgeIt () { return actual_edge; }
231	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
232	bool aNodeIsExamined() { return !(actual_edge.valid()); }
233	};
234
235
236	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
237	struct DfsIterator {
238	typedef typename Graph::NodeIt NodeIt;
239	Graph& G;
240	std::stack<OutEdgeIt>& bfs_queue;
241	ReachedMap& reached;
242	bool b_node_newly_reached;
243	OutEdgeIt actual_edge;
244	DfsIterator(Graph& _G,
245	std::stack<OutEdgeIt>& _bfs_queue,
246	ReachedMap& _reached) :
247	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
248	actual_edge=bfs_queue.top();
249	if (actual_edge.valid()) {
250	NodeIt w=G.bNode(actual_edge);
251	if (!reached.get(w)) {
252	bfs_queue.push(G.firstOutEdge(w));
253	reached.set(w, true);
254	b_node_newly_reached=true;
255	} else {
256	++(bfs_queue.top());
257	b_node_newly_reached=false;
258	}
259	} else {
260	bfs_queue.pop();
261	}
262	}
263	DfsIterator<Graph, OutEdgeIt, ReachedMap>&
264	operator++() {
265	actual_edge=bfs_queue.top();
266	if (actual_edge.valid()) {
267	NodeIt w=G.bNode(actual_edge);
268	if (!reached.get(w)) {
269	bfs_queue.push(G.firstOutEdge(w));
270	reached.set(w, true);
271	b_node_newly_reached=true;
272	} else {
273	++(bfs_queue.top());
274	b_node_newly_reached=false;
275	}
276	} else {
277	bfs_queue.pop();
278	}
279	return *this;
280	}
281	bool finished() { return bfs_queue.empty(); }
282	operator OutEdgeIt () { return actual_edge; }
283	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
284	bool aNodeIsLeaved() { return !(actual_edge.valid()); }
285	};
286
287	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
288	struct BfsIterator1 {
289	typedef typename Graph::NodeIt NodeIt;
290	Graph& G;
291	std::queue<OutEdgeIt>& bfs_queue;
292	ReachedMap& reached;
293	bool b_node_newly_reached;
294	OutEdgeIt actual_edge;
295	BfsIterator1(Graph& _G,
296	std::queue<OutEdgeIt>& _bfs_queue,
297	ReachedMap& _reached) :
298	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
299	actual_edge=bfs_queue.front();
300	if (actual_edge.valid()) {
301	NodeIt w=G.bNode(actual_edge);
302	if (!reached.get(w)) {
303	bfs_queue.push(OutEdgeIt(G, w));
304	reached.set(w, true);
305	b_node_newly_reached=true;
306	} else {
307	b_node_newly_reached=false;
308	}
309	}
310	}
311	void next() {
312	if (bfs_queue.front().valid()) {
313	++(bfs_queue.front());
314	actual_edge=bfs_queue.front();
315	if (actual_edge.valid()) {
316	NodeIt w=G.bNode(actual_edge);
317	if (!reached.get(w)) {
318	bfs_queue.push(OutEdgeIt(G, w));
319	reached.set(w, true);
320	b_node_newly_reached=true;
321	} else {
322	b_node_newly_reached=false;
323	}
324	}
325	} else {
326	bfs_queue.pop();
327	actual_edge=bfs_queue.front();
328	if (actual_edge.valid()) {
329	NodeIt w=G.bNode(actual_edge);
330	if (!reached.get(w)) {
331	bfs_queue.push(OutEdgeIt(G, w));
332	reached.set(w, true);
333	b_node_newly_reached=true;
334	} else {
335	b_node_newly_reached=false;
336	}
337	}
338	}
339	//return *this;
340	}
341	bool finished() { return bfs_queue.empty(); }
342	operator OutEdgeIt () { return actual_edge; }
343	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
344	bool aNodeIsExamined() { return !(actual_edge.valid()); }
345	};
346
347
348	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
349	struct DfsIterator1 {
350	typedef typename Graph::NodeIt NodeIt;
351	Graph& G;
352	std::stack<OutEdgeIt>& bfs_queue;
353	ReachedMap& reached;
354	bool b_node_newly_reached;
355	OutEdgeIt actual_edge;
356	DfsIterator1(Graph& _G,
357	std::stack<OutEdgeIt>& _bfs_queue,
358	ReachedMap& _reached) :
359	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
360	//actual_edge=bfs_queue.top();
361	//if (actual_edge.valid()) {
362	// NodeIt w=G.bNode(actual_edge);
363	//if (!reached.get(w)) {
364	// bfs_queue.push(OutEdgeIt(G, w));
365	// reached.set(w, true);
366	// b_node_newly_reached=true;
367	//} else {
368	// ++(bfs_queue.top());
369	// b_node_newly_reached=false;
370	//}
371	//} else {
372	// bfs_queue.pop();
373	//}
374	}
375	void next() {
376	actual_edge=bfs_queue.top();
377	if (actual_edge.valid()) {
378	NodeIt w=G.bNode(actual_edge);
379	if (!reached.get(w)) {
380	bfs_queue.push(OutEdgeIt(G, w));
381	reached.set(w, true);
382	b_node_newly_reached=true;
383	} else {
384	++(bfs_queue.top());
385	b_node_newly_reached=false;
386	}
387	} else {
388	bfs_queue.pop();
389	}
390	//return *this;
391	}
392	bool finished() { return bfs_queue.empty(); }
393	operator OutEdgeIt () { return actual_edge; }
394	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
395	bool aNodeIsLeaved() { return !(actual_edge.valid()); }
396	};
397
398	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
399	class BfsIterator2 {
400	typedef typename Graph::NodeIt NodeIt;
401	const Graph& G;
402	std::queue<OutEdgeIt> bfs_queue;
403	ReachedMap reached;
404	bool b_node_newly_reached;
405	OutEdgeIt actual_edge;
406	public:
407	BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
408	void pushAndSetReached(NodeIt s) {
409	reached.set(s, true);
410	if (bfs_queue.empty()) {
411	bfs_queue.push(G.template first<OutEdgeIt>(s));
412	actual_edge=bfs_queue.front();
413	if (actual_edge.valid()) {
414	NodeIt w=G.bNode(actual_edge);
415	if (!reached.get(w)) {
416	bfs_queue.push(G.template first<OutEdgeIt>(w));
417	reached.set(w, true);
418	b_node_newly_reached=true;
419	} else {
420	b_node_newly_reached=false;
421	}
422	} //else {
423	//}
424	} else {
425	bfs_queue.push(G.template first<OutEdgeIt>(s));
426	}
427	}
428	BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
429	operator++() {
430	if (bfs_queue.front().valid()) {
431	++(bfs_queue.front());
432	actual_edge=bfs_queue.front();
433	if (actual_edge.valid()) {
434	NodeIt w=G.bNode(actual_edge);
435	if (!reached.get(w)) {
436	bfs_queue.push(G.template first<OutEdgeIt>(w));
437	reached.set(w, true);
438	b_node_newly_reached=true;
439	} else {
440	b_node_newly_reached=false;
441	}
442	}
443	} else {
444	bfs_queue.pop();
445	if (!bfs_queue.empty()) {
446	actual_edge=bfs_queue.front();
447	if (actual_edge.valid()) {
448	NodeIt w=G.bNode(actual_edge);
449	if (!reached.get(w)) {
450	bfs_queue.push(G.template first<OutEdgeIt>(w));
451	reached.set(w, true);
452	b_node_newly_reached=true;
453	} else {
454	b_node_newly_reached=false;
455	}
456	}
457	}
458	}
459	return *this;
460	}
461	bool finished() const { return bfs_queue.empty(); }
462	operator OutEdgeIt () const { return actual_edge; }
463	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
464	bool isANodeExamined() const { return !(actual_edge.valid()); }
465	const ReachedMap& getReachedMap() const { return reached; }
466	const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
467	};
468
469	} // namespace marci
470
471	#endif //BFS_ITERATOR_HH

Note: See TracBrowser for help on using the repository browser.

Download in other formats: