lemon-0.x: src/work/bfs_iterator.hh@c4adf922624f (annotated)

marci@58	1	#ifndef BFS_ITERATOR_HH
marci@58	2	#define BFS_ITERATOR_HH
marci@42	3
marci@42	4	#include <queue>
marci@42	5	#include <stack>
marci@75	6	#include <utility>
marci@75	7	#include <graph_wrapper.h>
marci@42	8
alpar@105	9	namespace hugo {
marci@42	10
marci@42	11	template <typename Graph>
marci@42	12	struct bfs {
marci@42	13	typedef typename Graph::NodeIt NodeIt;
marci@42	14	typedef typename Graph::EdgeIt EdgeIt;
marci@42	15	typedef typename Graph::EachNodeIt EachNodeIt;
marci@42	16	typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42	17	Graph& G;
marci@42	18	NodeIt s;
marci@42	19	typename Graph::NodeMap<bool> reached;
marci@42	20	typename Graph::NodeMap<EdgeIt> pred;
marci@42	21	typename Graph::NodeMap<int> dist;
marci@42	22	std::queue<NodeIt> bfs_queue;
marci@42	23	bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
marci@42	24	bfs_queue.push(s);
marci@42	25	for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
marci@42	26	reached.set(i, false);
marci@42	27	reached.set(s, true);
marci@42	28	dist.set(s, 0);
marci@42	29	}
marci@42	30
marci@42	31	void run() {
marci@42	32	while (!bfs_queue.empty()) {
marci@42	33	NodeIt v=bfs_queue.front();
marci@42	34	OutEdgeIt e=G.template first<OutEdgeIt>(v);
marci@42	35	bfs_queue.pop();
marci@42	36	for( ; e.valid(); ++e) {
marci@42	37	NodeIt w=G.bNode(e);
marci@42	38	std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
marci@42	39	if (!reached.get(w)) {
marci@42	40	std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@42	41	bfs_queue.push(w);
marci@42	42	dist.set(w, dist.get(v)+1);
marci@42	43	pred.set(w, e);
marci@42	44	reached.set(w, true);
marci@42	45	} else {
marci@42	46	std::cout << G.id(w) << " is already reached" << std::endl;
marci@42	47	}
marci@42	48	}
marci@42	49	}
marci@42	50	}
marci@42	51	};
marci@42	52
marci@42	53	template <typename Graph>
marci@42	54	struct bfs_visitor {
marci@42	55	typedef typename Graph::NodeIt NodeIt;
marci@42	56	typedef typename Graph::EdgeIt EdgeIt;
marci@42	57	typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42	58	Graph& G;
marci@42	59	bfs_visitor(Graph& _G) : G(_G) { }
marci@42	60	void at_previously_reached(OutEdgeIt& e) {
marci@42	61	//NodeIt v=G.aNode(e);
marci@42	62	NodeIt w=G.bNode(e);
marci@42	63	std::cout << G.id(w) << " is already reached" << std::endl;
marci@42	64	}
marci@42	65	void at_newly_reached(OutEdgeIt& e) {
marci@42	66	//NodeIt v=G.aNode(e);
marci@42	67	NodeIt w=G.bNode(e);
marci@42	68	std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@42	69	}
marci@42	70	};
marci@42	71
marci@42	72	template <typename Graph, typename ReachedMap, typename visitor_type>
marci@42	73	struct bfs_iterator {
marci@42	74	typedef typename Graph::NodeIt NodeIt;
marci@42	75	typedef typename Graph::EdgeIt EdgeIt;
marci@42	76	typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42	77	Graph& G;
marci@42	78	std::queue<OutEdgeIt>& bfs_queue;
marci@42	79	ReachedMap& reached;
marci@42	80	visitor_type& visitor;
marci@42	81	void process() {
marci@42	82	while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	83	if (bfs_queue.empty()) return;
marci@42	84	OutEdgeIt e=bfs_queue.front();
marci@42	85	//NodeIt v=G.aNode(e);
marci@42	86	NodeIt w=G.bNode(e);
marci@42	87	if (!reached.get(w)) {
marci@42	88	visitor.at_newly_reached(e);
marci@42	89	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@42	90	reached.set(w, true);
marci@42	91	} else {
marci@42	92	visitor.at_previously_reached(e);
marci@42	93	}
marci@42	94	}
marci@42	95	bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
marci@42	96	//while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	97	valid();
marci@42	98	}
marci@42	99	bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
marci@42	100	//while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	101	//if (bfs_queue.empty()) return *this;
marci@42	102	if (!valid()) return *this;
marci@42	103	++(bfs_queue.front());
marci@42	104	//while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	105	valid();
marci@42	106	return *this;
marci@42	107	}
marci@42	108	//void next() {
marci@42	109	// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	110	// if (bfs_queue.empty()) return;
marci@42	111	// ++(bfs_queue.front());
marci@42	112	// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	113	//}
marci@42	114	bool valid() {
marci@42	115	while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	116	if (bfs_queue.empty()) return false; else return true;
marci@42	117	}
marci@42	118	//bool finished() {
marci@42	119	// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	120	// if (bfs_queue.empty()) return true; else return false;
marci@42	121	//}
marci@42	122	operator EdgeIt () { return bfs_queue.front(); }
marci@42	123
marci@42	124	};
marci@42	125
marci@42	126	template <typename Graph, typename ReachedMap>
marci@42	127	struct bfs_iterator1 {
marci@42	128	typedef typename Graph::NodeIt NodeIt;
marci@42	129	typedef typename Graph::EdgeIt EdgeIt;
marci@42	130	typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42	131	Graph& G;
marci@42	132	std::queue<OutEdgeIt>& bfs_queue;
marci@42	133	ReachedMap& reached;
marci@42	134	bool _newly_reached;
marci@42	135	bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
marci@42	136	valid();
marci@42	137	if (!bfs_queue.empty() && bfs_queue.front().valid()) {
marci@42	138	OutEdgeIt e=bfs_queue.front();
marci@42	139	NodeIt w=G.bNode(e);
marci@42	140	if (!reached.get(w)) {
marci@42	141	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@42	142	reached.set(w, true);
marci@42	143	_newly_reached=true;
marci@42	144	} else {
marci@42	145	_newly_reached=false;
marci@42	146	}
marci@42	147	}
marci@42	148	}
marci@42	149	bfs_iterator1<Graph, ReachedMap>& operator++() {
marci@42	150	if (!valid()) return *this;
marci@42	151	++(bfs_queue.front());
marci@42	152	valid();
marci@42	153	if (!bfs_queue.empty() && bfs_queue.front().valid()) {
marci@42	154	OutEdgeIt e=bfs_queue.front();
marci@42	155	NodeIt w=G.bNode(e);
marci@42	156	if (!reached.get(w)) {
marci@42	157	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@42	158	reached.set(w, true);
marci@42	159	_newly_reached=true;
marci@42	160	} else {
marci@42	161	_newly_reached=false;
marci@42	162	}
marci@42	163	}
marci@42	164	return *this;
marci@42	165	}
marci@42	166	bool valid() {
marci@42	167	while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
marci@42	168	if (bfs_queue.empty()) return false; else return true;
marci@42	169	}
marci@42	170	operator OutEdgeIt() { return bfs_queue.front(); }
marci@42	171	//ize
marci@42	172	bool newly_reached() { return _newly_reached; }
marci@42	173
marci@42	174	};
marci@42	175
marci@42	176	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42	177	struct BfsIterator {
marci@42	178	typedef typename Graph::NodeIt NodeIt;
marci@42	179	Graph& G;
marci@42	180	std::queue<OutEdgeIt>& bfs_queue;
marci@42	181	ReachedMap& reached;
marci@42	182	bool b_node_newly_reached;
marci@42	183	OutEdgeIt actual_edge;
marci@42	184	BfsIterator(Graph& _G,
marci@42	185	std::queue<OutEdgeIt>& _bfs_queue,
marci@42	186	ReachedMap& _reached) :
marci@42	187	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
marci@42	188	actual_edge=bfs_queue.front();
marci@42	189	if (actual_edge.valid()) {
marci@42	190	NodeIt w=G.bNode(actual_edge);
marci@42	191	if (!reached.get(w)) {
marci@42	192	bfs_queue.push(G.firstOutEdge(w));
marci@42	193	reached.set(w, true);
marci@42	194	b_node_newly_reached=true;
marci@42	195	} else {
marci@42	196	b_node_newly_reached=false;
marci@42	197	}
marci@42	198	}
marci@42	199	}
marci@42	200	BfsIterator<Graph, OutEdgeIt, ReachedMap>&
marci@42	201	operator++() {
marci@42	202	if (bfs_queue.front().valid()) {
marci@42	203	++(bfs_queue.front());
marci@42	204	actual_edge=bfs_queue.front();
marci@42	205	if (actual_edge.valid()) {
marci@42	206	NodeIt w=G.bNode(actual_edge);
marci@42	207	if (!reached.get(w)) {
marci@42	208	bfs_queue.push(G.firstOutEdge(w));
marci@42	209	reached.set(w, true);
marci@42	210	b_node_newly_reached=true;
marci@42	211	} else {
marci@42	212	b_node_newly_reached=false;
marci@42	213	}
marci@42	214	}
marci@42	215	} else {
marci@42	216	bfs_queue.pop();
marci@42	217	actual_edge=bfs_queue.front();
marci@42	218	if (actual_edge.valid()) {
marci@42	219	NodeIt w=G.bNode(actual_edge);
marci@42	220	if (!reached.get(w)) {
marci@42	221	bfs_queue.push(G.firstOutEdge(w));
marci@42	222	reached.set(w, true);
marci@42	223	b_node_newly_reached=true;
marci@42	224	} else {
marci@42	225	b_node_newly_reached=false;
marci@42	226	}
marci@42	227	}
marci@42	228	}
marci@42	229	return *this;
marci@42	230	}
marci@42	231	bool finished() { return bfs_queue.empty(); }
marci@42	232	operator OutEdgeIt () { return actual_edge; }
marci@42	233	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42	234	bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@42	235	};
marci@42	236
marci@42	237
marci@42	238	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42	239	struct DfsIterator {
marci@42	240	typedef typename Graph::NodeIt NodeIt;
marci@42	241	Graph& G;
marci@42	242	std::stack<OutEdgeIt>& bfs_queue;
marci@42	243	ReachedMap& reached;
marci@42	244	bool b_node_newly_reached;
marci@42	245	OutEdgeIt actual_edge;
marci@42	246	DfsIterator(Graph& _G,
marci@42	247	std::stack<OutEdgeIt>& _bfs_queue,
marci@42	248	ReachedMap& _reached) :
marci@42	249	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
marci@42	250	actual_edge=bfs_queue.top();
marci@42	251	if (actual_edge.valid()) {
marci@42	252	NodeIt w=G.bNode(actual_edge);
marci@42	253	if (!reached.get(w)) {
marci@42	254	bfs_queue.push(G.firstOutEdge(w));
marci@42	255	reached.set(w, true);
marci@42	256	b_node_newly_reached=true;
marci@42	257	} else {
marci@42	258	++(bfs_queue.top());
marci@42	259	b_node_newly_reached=false;
marci@42	260	}
marci@42	261	} else {
marci@42	262	bfs_queue.pop();
marci@42	263	}
marci@42	264	}
marci@42	265	DfsIterator<Graph, OutEdgeIt, ReachedMap>&
marci@42	266	operator++() {
marci@42	267	actual_edge=bfs_queue.top();
marci@42	268	if (actual_edge.valid()) {
marci@42	269	NodeIt w=G.bNode(actual_edge);
marci@42	270	if (!reached.get(w)) {
marci@42	271	bfs_queue.push(G.firstOutEdge(w));
marci@42	272	reached.set(w, true);
marci@42	273	b_node_newly_reached=true;
marci@42	274	} else {
marci@42	275	++(bfs_queue.top());
marci@42	276	b_node_newly_reached=false;
marci@42	277	}
marci@42	278	} else {
marci@42	279	bfs_queue.pop();
marci@42	280	}
marci@42	281	return *this;
marci@42	282	}
marci@42	283	bool finished() { return bfs_queue.empty(); }
marci@42	284	operator OutEdgeIt () { return actual_edge; }
marci@42	285	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@99	286	bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@42	287	};
marci@42	288
marci@42	289	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42	290	struct BfsIterator1 {
marci@42	291	typedef typename Graph::NodeIt NodeIt;
marci@42	292	Graph& G;
marci@42	293	std::queue<OutEdgeIt>& bfs_queue;
marci@42	294	ReachedMap& reached;
marci@42	295	bool b_node_newly_reached;
marci@42	296	OutEdgeIt actual_edge;
marci@42	297	BfsIterator1(Graph& _G,
marci@42	298	std::queue<OutEdgeIt>& _bfs_queue,
marci@42	299	ReachedMap& _reached) :
marci@42	300	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
marci@42	301	actual_edge=bfs_queue.front();
marci@42	302	if (actual_edge.valid()) {
marci@42	303	NodeIt w=G.bNode(actual_edge);
marci@42	304	if (!reached.get(w)) {
marci@42	305	bfs_queue.push(OutEdgeIt(G, w));
marci@42	306	reached.set(w, true);
marci@42	307	b_node_newly_reached=true;
marci@42	308	} else {
marci@42	309	b_node_newly_reached=false;
marci@42	310	}
marci@42	311	}
marci@42	312	}
marci@42	313	void next() {
marci@42	314	if (bfs_queue.front().valid()) {
marci@42	315	++(bfs_queue.front());
marci@42	316	actual_edge=bfs_queue.front();
marci@42	317	if (actual_edge.valid()) {
marci@42	318	NodeIt w=G.bNode(actual_edge);
marci@42	319	if (!reached.get(w)) {
marci@42	320	bfs_queue.push(OutEdgeIt(G, w));
marci@42	321	reached.set(w, true);
marci@42	322	b_node_newly_reached=true;
marci@42	323	} else {
marci@42	324	b_node_newly_reached=false;
marci@42	325	}
marci@42	326	}
marci@42	327	} else {
marci@42	328	bfs_queue.pop();
marci@42	329	actual_edge=bfs_queue.front();
marci@42	330	if (actual_edge.valid()) {
marci@42	331	NodeIt w=G.bNode(actual_edge);
marci@42	332	if (!reached.get(w)) {
marci@42	333	bfs_queue.push(OutEdgeIt(G, w));
marci@42	334	reached.set(w, true);
marci@42	335	b_node_newly_reached=true;
marci@42	336	} else {
marci@42	337	b_node_newly_reached=false;
marci@42	338	}
marci@42	339	}
marci@42	340	}
marci@42	341	//return *this;
marci@42	342	}
marci@42	343	bool finished() { return bfs_queue.empty(); }
marci@42	344	operator OutEdgeIt () { return actual_edge; }
marci@42	345	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42	346	bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@42	347	};
marci@42	348
marci@42	349
marci@42	350	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42	351	struct DfsIterator1 {
marci@42	352	typedef typename Graph::NodeIt NodeIt;
marci@42	353	Graph& G;
marci@42	354	std::stack<OutEdgeIt>& bfs_queue;
marci@42	355	ReachedMap& reached;
marci@42	356	bool b_node_newly_reached;
marci@42	357	OutEdgeIt actual_edge;
marci@42	358	DfsIterator1(Graph& _G,
marci@42	359	std::stack<OutEdgeIt>& _bfs_queue,
marci@42	360	ReachedMap& _reached) :
marci@42	361	G(_G), bfs_queue(_bfs_queue), reached(_reached) {
marci@42	362	//actual_edge=bfs_queue.top();
marci@42	363	//if (actual_edge.valid()) {
marci@42	364	// NodeIt w=G.bNode(actual_edge);
marci@42	365	//if (!reached.get(w)) {
marci@42	366	// bfs_queue.push(OutEdgeIt(G, w));
marci@42	367	// reached.set(w, true);
marci@42	368	// b_node_newly_reached=true;
marci@42	369	//} else {
marci@42	370	// ++(bfs_queue.top());
marci@42	371	// b_node_newly_reached=false;
marci@42	372	//}
marci@42	373	//} else {
marci@42	374	// bfs_queue.pop();
marci@42	375	//}
marci@42	376	}
marci@42	377	void next() {
marci@42	378	actual_edge=bfs_queue.top();
marci@42	379	if (actual_edge.valid()) {
marci@42	380	NodeIt w=G.bNode(actual_edge);
marci@42	381	if (!reached.get(w)) {
marci@42	382	bfs_queue.push(OutEdgeIt(G, w));
marci@42	383	reached.set(w, true);
marci@42	384	b_node_newly_reached=true;
marci@42	385	} else {
marci@42	386	++(bfs_queue.top());
marci@42	387	b_node_newly_reached=false;
marci@42	388	}
marci@42	389	} else {
marci@42	390	bfs_queue.pop();
marci@42	391	}
marci@42	392	//return *this;
marci@42	393	}
marci@42	394	bool finished() { return bfs_queue.empty(); }
marci@42	395	operator OutEdgeIt () { return actual_edge; }
marci@42	396	bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42	397	bool aNodeIsLeaved() { return !(actual_edge.valid()); }
marci@42	398	};
marci@42	399
marci@58	400	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@58	401	class BfsIterator2 {
marci@58	402	typedef typename Graph::NodeIt NodeIt;
marci@58	403	const Graph& G;
marci@58	404	std::queue<OutEdgeIt> bfs_queue;
marci@58	405	ReachedMap reached;
marci@58	406	bool b_node_newly_reached;
marci@58	407	OutEdgeIt actual_edge;
marci@58	408	public:
marci@58	409	BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
marci@64	410	void pushAndSetReached(NodeIt s) {
marci@58	411	reached.set(s, true);
marci@58	412	if (bfs_queue.empty()) {
marci@58	413	bfs_queue.push(G.template first<OutEdgeIt>(s));
marci@58	414	actual_edge=bfs_queue.front();
marci@58	415	if (actual_edge.valid()) {
marci@58	416	NodeIt w=G.bNode(actual_edge);
marci@58	417	if (!reached.get(w)) {
marci@58	418	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@58	419	reached.set(w, true);
marci@58	420	b_node_newly_reached=true;
marci@58	421	} else {
marci@58	422	b_node_newly_reached=false;
marci@58	423	}
marci@58	424	} //else {
marci@58	425	//}
marci@58	426	} else {
marci@58	427	bfs_queue.push(G.template first<OutEdgeIt>(s));
marci@58	428	}
marci@58	429	}
marci@58	430	BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
marci@58	431	operator++() {
marci@58	432	if (bfs_queue.front().valid()) {
marci@58	433	++(bfs_queue.front());
marci@58	434	actual_edge=bfs_queue.front();
marci@58	435	if (actual_edge.valid()) {
marci@58	436	NodeIt w=G.bNode(actual_edge);
marci@58	437	if (!reached.get(w)) {
marci@58	438	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@58	439	reached.set(w, true);
marci@58	440	b_node_newly_reached=true;
marci@58	441	} else {
marci@58	442	b_node_newly_reached=false;
marci@58	443	}
marci@58	444	}
marci@58	445	} else {
marci@58	446	bfs_queue.pop();
marci@58	447	if (!bfs_queue.empty()) {
marci@58	448	actual_edge=bfs_queue.front();
marci@64	449	if (actual_edge.valid()) {
marci@64	450	NodeIt w=G.bNode(actual_edge);
marci@64	451	if (!reached.get(w)) {
marci@64	452	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@64	453	reached.set(w, true);
marci@64	454	b_node_newly_reached=true;
marci@64	455	} else {
marci@64	456	b_node_newly_reached=false;
marci@64	457	}
marci@58	458	}
marci@58	459	}
marci@58	460	}
marci@58	461	return *this;
marci@58	462	}
marci@58	463	bool finished() const { return bfs_queue.empty(); }
marci@58	464	operator OutEdgeIt () const { return actual_edge; }
marci@58	465	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@58	466	bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@58	467	const ReachedMap& getReachedMap() const { return reached; }
marci@58	468	const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
marci@58	469	};
marci@58	470
marci@75	471
marci@75	472	template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@75	473	class BfsIterator3 {
marci@75	474	typedef typename Graph::NodeIt NodeIt;
marci@75	475	const Graph& G;
marci@75	476	std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
marci@75	477	ReachedMap reached;
marci@75	478	bool b_node_newly_reached;
marci@75	479	OutEdgeIt actual_edge;
marci@75	480	public:
marci@75	481	BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
marci@75	482	void pushAndSetReached(NodeIt s) {
marci@75	483	reached.set(s, true);
marci@75	484	if (bfs_queue.empty()) {
marci@75	485	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
marci@75	486	actual_edge=bfs_queue.front().second;
marci@75	487	if (actual_edge.valid()) {
marci@75	488	NodeIt w=G.bNode(actual_edge);
marci@75	489	if (!reached.get(w)) {
marci@75	490	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@75	491	reached.set(w, true);
marci@75	492	b_node_newly_reached=true;
marci@75	493	} else {
marci@75	494	b_node_newly_reached=false;
marci@75	495	}
marci@75	496	} //else {
marci@75	497	//}
marci@75	498	} else {
marci@75	499	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
marci@75	500	}
marci@75	501	}
marci@75	502	BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
marci@75	503	operator++() {
marci@75	504	if (bfs_queue.front().second.valid()) {
marci@75	505	++(bfs_queue.front().second);
marci@75	506	actual_edge=bfs_queue.front().second;
marci@75	507	if (actual_edge.valid()) {
marci@75	508	NodeIt w=G.bNode(actual_edge);
marci@75	509	if (!reached.get(w)) {
marci@75	510	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@75	511	reached.set(w, true);
marci@75	512	b_node_newly_reached=true;
marci@75	513	} else {
marci@75	514	b_node_newly_reached=false;
marci@75	515	}
marci@75	516	}
marci@75	517	} else {
marci@75	518	bfs_queue.pop();
marci@75	519	if (!bfs_queue.empty()) {
marci@75	520	actual_edge=bfs_queue.front().second;
marci@75	521	if (actual_edge.valid()) {
marci@75	522	NodeIt w=G.bNode(actual_edge);
marci@75	523	if (!reached.get(w)) {
marci@75	524	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@75	525	reached.set(w, true);
marci@75	526	b_node_newly_reached=true;
marci@75	527	} else {
marci@75	528	b_node_newly_reached=false;
marci@75	529	}
marci@75	530	}
marci@75	531	}
marci@75	532	}
marci@75	533	return *this;
marci@75	534	}
marci@75	535	bool finished() const { return bfs_queue.empty(); }
marci@75	536	operator OutEdgeIt () const { return actual_edge; }
marci@75	537	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@75	538	bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@75	539	NodeIt aNode() const { return bfs_queue.front().first; }
marci@75	540	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@75	541	const ReachedMap& getReachedMap() const { return reached; }
marci@75	542	//const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
marci@75	543	};
marci@75	544
marci@144	545
marci@144	546	template <typename Graph, typename OutEdgeIt,
marci@144	547	typename ReachedMap=typename Graph::NodeMap<bool> >
marci@75	548	class BfsIterator4 {
marci@75	549	typedef typename Graph::NodeIt NodeIt;
marci@75	550	const Graph& G;
marci@75	551	std::queue<NodeIt> bfs_queue;
marci@144	552	ReachedMap& reached;
marci@75	553	bool b_node_newly_reached;
marci@75	554	OutEdgeIt actual_edge;
marci@144	555	bool own_reached_map;
marci@75	556	public:
marci@144	557	BfsIterator4(const Graph& _G, ReachedMap& _reached) :
marci@144	558	G(_G), reached(_reached),
marci@144	559	own_reached_map(false) { }
marci@144	560	BfsIterator4(const Graph& _G) :
marci@144	561	G(_G), reached((new ReachedMap(G /, false*/))),
marci@144	562	own_reached_map(true) { }
marci@144	563	~BfsIterator4() { if (own_reached_map) delete &reached; }
marci@75	564	void pushAndSetReached(NodeIt s) {
marci@75	565	reached.set(s, true);
marci@75	566	if (bfs_queue.empty()) {
marci@75	567	bfs_queue.push(s);
marci@75	568	G.getFirst(actual_edge, s);
marci@75	569	if (actual_edge.valid()) {
marci@75	570	NodeIt w=G.bNode(actual_edge);
marci@75	571	if (!reached.get(w)) {
marci@75	572	bfs_queue.push(w);
marci@75	573	reached.set(w, true);
marci@75	574	b_node_newly_reached=true;
marci@75	575	} else {
marci@75	576	b_node_newly_reached=false;
marci@75	577	}
marci@75	578	}
marci@75	579	} else {
marci@75	580	bfs_queue.push(s);
marci@75	581	}
marci@75	582	}
marci@75	583	BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
marci@75	584	operator++() {
marci@75	585	if (actual_edge.valid()) {
marci@75	586	++actual_edge;
marci@75	587	if (actual_edge.valid()) {
marci@75	588	NodeIt w=G.bNode(actual_edge);
marci@75	589	if (!reached.get(w)) {
marci@75	590	bfs_queue.push(w);
marci@75	591	reached.set(w, true);
marci@75	592	b_node_newly_reached=true;
marci@75	593	} else {
marci@75	594	b_node_newly_reached=false;
marci@75	595	}
marci@75	596	}
marci@75	597	} else {
marci@75	598	bfs_queue.pop();
marci@75	599	if (!bfs_queue.empty()) {
marci@75	600	G.getFirst(actual_edge, bfs_queue.front());
marci@75	601	if (actual_edge.valid()) {
marci@75	602	NodeIt w=G.bNode(actual_edge);
marci@75	603	if (!reached.get(w)) {
marci@75	604	bfs_queue.push(w);
marci@75	605	reached.set(w, true);
marci@75	606	b_node_newly_reached=true;
marci@75	607	} else {
marci@75	608	b_node_newly_reached=false;
marci@75	609	}
marci@75	610	}
marci@75	611	}
marci@75	612	}
marci@75	613	return *this;
marci@75	614	}
marci@75	615	bool finished() const { return bfs_queue.empty(); }
marci@75	616	operator OutEdgeIt () const { return actual_edge; }
marci@75	617	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@75	618	bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@75	619	NodeIt aNode() const { return bfs_queue.front(); }
marci@75	620	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@75	621	const ReachedMap& getReachedMap() const { return reached; }
marci@75	622	const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
marci@144	623	};
marci@75	624
marci@144	625	template <typename Graph, typename OutEdgeIt,
marci@144	626	typename ReachedMap=typename Graph::NodeMap<bool> >
marci@144	627	class DfsIterator4 {
marci@99	628	typedef typename Graph::NodeIt NodeIt;
marci@99	629	const Graph& G;
marci@99	630	std::stack<OutEdgeIt> dfs_stack;
marci@99	631	bool b_node_newly_reached;
marci@99	632	OutEdgeIt actual_edge;
marci@99	633	NodeIt actual_node;
marci@144	634	ReachedMap& reached;
marci@144	635	bool own_reached_map;
marci@144	636	public:
marci@144	637	DfsIterator4(const Graph& _G, ReachedMap& _reached) :
marci@144	638	G(_G), reached(_reached),
marci@144	639	own_reached_map(false) { }
marci@144	640	DfsIterator4(const Graph& _G) :
marci@144	641	G(_G), reached((new ReachedMap(G /, false*/))),
marci@144	642	own_reached_map(true) { }
marci@144	643	~DfsIterator4() { if (own_reached_map) delete &reached; }
marci@99	644	void pushAndSetReached(NodeIt s) {
marci@133	645	actual_node=s;
marci@99	646	reached.set(s, true);
marci@99	647	dfs_stack.push(G.template first<OutEdgeIt>(s));
marci@99	648	}
marci@99	649	DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
marci@99	650	operator++() {
marci@99	651	actual_edge=dfs_stack.top();
marci@99	652	//actual_node=G.aNode(actual_edge);
marci@99	653	if (actual_edge.valid()) {
marci@99	654	NodeIt w=G.bNode(actual_edge);
marci@99	655	actual_node=w;
marci@99	656	if (!reached.get(w)) {
marci@99	657	dfs_stack.push(G.template first<OutEdgeIt>(w));
marci@99	658	reached.set(w, true);
marci@99	659	b_node_newly_reached=true;
marci@99	660	} else {
marci@133	661	actual_node=G.aNode(actual_edge);
marci@99	662	++(dfs_stack.top());
marci@99	663	b_node_newly_reached=false;
marci@99	664	}
marci@99	665	} else {
marci@99	666	//actual_node=G.aNode(dfs_stack.top());
marci@99	667	dfs_stack.pop();
marci@99	668	}
marci@99	669	return *this;
marci@99	670	}
marci@99	671	bool finished() const { return dfs_stack.empty(); }
marci@99	672	operator OutEdgeIt () const { return actual_edge; }
marci@99	673	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@99	674	bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@133	675	NodeIt aNode() const { return actual_node; /FIXME/}
marci@99	676	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@99	677	const ReachedMap& getReachedMap() const { return reached; }
marci@99	678	const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
marci@99	679	};
marci@99	680
marci@99	681
marci@99	682
marci@75	683	template <typename GraphWrapper, typename ReachedMap>
marci@75	684	class BfsIterator5 {
marci@75	685	typedef typename GraphWrapper::NodeIt NodeIt;
marci@75	686	typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
marci@75	687	GraphWrapper gw;
marci@75	688	std::queue<NodeIt> bfs_queue;
marci@75	689	ReachedMap reached;
marci@75	690	bool b_node_newly_reached;
marci@75	691	OutEdgeIt actual_edge;
marci@75	692	public:
marci@75	693	BfsIterator5(GraphWrapper _gw) :
marci@75	694	gw(_gw), reached(_gw.getGraph()) { }
marci@75	695	void pushAndSetReached(NodeIt s) {
marci@75	696	reached.set(s, true);
marci@75	697	if (bfs_queue.empty()) {
marci@75	698	bfs_queue.push(s);
marci@75	699	gw.getFirst(actual_edge, s);
marci@75	700	if (actual_edge.valid()) {
marci@75	701	NodeIt w=gw.bNode(actual_edge);
marci@75	702	if (!reached.get(w)) {
marci@75	703	bfs_queue.push(w);
marci@75	704	reached.set(w, true);
marci@75	705	b_node_newly_reached=true;
marci@75	706	} else {
marci@75	707	b_node_newly_reached=false;
marci@75	708	}
marci@75	709	}
marci@75	710	} else {
marci@75	711	bfs_queue.push(s);
marci@75	712	}
marci@75	713	}
marci@75	714	BfsIterator5<GraphWrapper, ReachedMap>&
marci@75	715	operator++() {
marci@75	716	if (actual_edge.valid()) {
marci@75	717	++actual_edge;
marci@75	718	if (actual_edge.valid()) {
marci@75	719	NodeIt w=gw.bNode(actual_edge);
marci@75	720	if (!reached.get(w)) {
marci@75	721	bfs_queue.push(w);
marci@75	722	reached.set(w, true);
marci@75	723	b_node_newly_reached=true;
marci@75	724	} else {
marci@75	725	b_node_newly_reached=false;
marci@75	726	}
marci@75	727	}
marci@75	728	} else {
marci@75	729	bfs_queue.pop();
marci@75	730	if (!bfs_queue.empty()) {
marci@75	731	gw.getFirst(actual_edge, bfs_queue.front());
marci@75	732	if (actual_edge.valid()) {
marci@75	733	NodeIt w=gw.bNode(actual_edge);
marci@75	734	if (!reached.get(w)) {
marci@75	735	bfs_queue.push(w);
marci@75	736	reached.set(w, true);
marci@75	737	b_node_newly_reached=true;
marci@75	738	} else {
marci@75	739	b_node_newly_reached=false;
marci@75	740	}
marci@75	741	}
marci@75	742	}
marci@75	743	}
marci@75	744	return *this;
marci@75	745	}
marci@75	746	bool finished() const { return bfs_queue.empty(); }
marci@75	747	operator OutEdgeIt () const { return actual_edge; }
marci@75	748	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@75	749	bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@75	750	NodeIt aNode() const { return bfs_queue.front(); }
marci@75	751	NodeIt bNode() const { return gw.bNode(actual_edge); }
marci@75	752	const ReachedMap& getReachedMap() const { return reached; }
marci@75	753	const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
marci@75	754	};
marci@75	755
marci@75	756
marci@75	757
alpar@105	758	} // namespace hugo
marci@42	759
marci@58	760	#endif //BFS_ITERATOR_HH

author	marci
	Tue, 02 Mar 2004 18:24:00 +0000
changeset 146	c4adf922624f
parent 133	0631992fe7a1
child 148	004fdf703abb
permissions	-rw-r--r--