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

author	marci
	Wed, 04 Feb 2004 12:59:17 +0000
changeset 60	89d2ce014e12
parent 42	3ee2187d6342
child 64	72bd463289a9
permissions	-rw-r--r--