lemon-0.x: src/work/bfs_iterator.hh@259540358bbf (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@148	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@168	565	//std::cout << "mimi" << &reached << std::endl;
marci@75	566	reached.set(s, true);
marci@168	567	//std::cout << "mumus" << std::endl;
marci@75	568	if (bfs_queue.empty()) {
marci@168	569	//std::cout << "bibi1" << std::endl;
marci@75	570	bfs_queue.push(s);
marci@168	571	//std::cout << "zizi" << std::endl;
marci@75	572	G.getFirst(actual_edge, s);
marci@168	573	//std::cout << "kiki" << std::endl;
marci@148	574	if (G.valid(actual_edge)/.valid()/) {
marci@75	575	NodeIt w=G.bNode(actual_edge);
marci@75	576	if (!reached.get(w)) {
marci@75	577	bfs_queue.push(w);
marci@75	578	reached.set(w, true);
marci@75	579	b_node_newly_reached=true;
marci@75	580	} else {
marci@75	581	b_node_newly_reached=false;
marci@75	582	}
marci@75	583	}
marci@75	584	} else {
marci@168	585	//std::cout << "bibi2" << std::endl;
marci@75	586	bfs_queue.push(s);
marci@75	587	}
marci@75	588	}
marci@75	589	BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
marci@75	590	operator++() {
marci@148	591	if (G.valid(actual_edge)/.valid()/) {
marci@148	592	/++/G.next(actual_edge);
marci@148	593	if (G.valid(actual_edge)/.valid()/) {
marci@75	594	NodeIt w=G.bNode(actual_edge);
marci@75	595	if (!reached.get(w)) {
marci@75	596	bfs_queue.push(w);
marci@75	597	reached.set(w, true);
marci@75	598	b_node_newly_reached=true;
marci@75	599	} else {
marci@75	600	b_node_newly_reached=false;
marci@75	601	}
marci@75	602	}
marci@75	603	} else {
marci@75	604	bfs_queue.pop();
marci@75	605	if (!bfs_queue.empty()) {
marci@75	606	G.getFirst(actual_edge, bfs_queue.front());
marci@148	607	if (G.valid(actual_edge)/.valid()/) {
marci@75	608	NodeIt w=G.bNode(actual_edge);
marci@75	609	if (!reached.get(w)) {
marci@75	610	bfs_queue.push(w);
marci@75	611	reached.set(w, true);
marci@75	612	b_node_newly_reached=true;
marci@75	613	} else {
marci@75	614	b_node_newly_reached=false;
marci@75	615	}
marci@75	616	}
marci@75	617	}
marci@75	618	}
marci@75	619	return *this;
marci@75	620	}
marci@75	621	bool finished() const { return bfs_queue.empty(); }
marci@75	622	operator OutEdgeIt () const { return actual_edge; }
marci@75	623	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@148	624	bool isANodeExamined() const { return !(G.valid(actual_edge)/.valid()/); }
marci@75	625	NodeIt aNode() const { return bfs_queue.front(); }
marci@75	626	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@75	627	const ReachedMap& getReachedMap() const { return reached; }
marci@75	628	const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
marci@144	629	};
marci@75	630
marci@148	631
marci@158	632	template <typename GraphWrapper, /typename OutEdgeIt,/
marci@148	633	typename ReachedMap/=typename GraphWrapper::NodeMap<bool>/ >
marci@148	634	class BfsIterator5 {
marci@148	635	typedef typename GraphWrapper::NodeIt NodeIt;
marci@158	636	typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
marci@148	637	GraphWrapper G;
marci@148	638	std::queue<NodeIt> bfs_queue;
marci@148	639	ReachedMap& reached;
marci@148	640	bool b_node_newly_reached;
marci@148	641	OutEdgeIt actual_edge;
marci@148	642	bool own_reached_map;
marci@148	643	public:
marci@148	644	BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
marci@148	645	G(_G), reached(_reached),
marci@148	646	own_reached_map(false) { }
marci@148	647	BfsIterator5(const GraphWrapper& _G) :
marci@148	648	G(_G), reached((new ReachedMap(G /, false*/))),
marci@148	649	own_reached_map(true) { }
marci@158	650	// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
marci@158	651	// ReachedMap& _reached) :
marci@158	652	// G(_G), reached(_reached),
marci@158	653	// own_reached_map(false) { }
marci@158	654	// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
marci@158	655	// G(_G), reached((new ReachedMap(G /, false*/))),
marci@158	656	// own_reached_map(true) { }
marci@148	657	~BfsIterator5() { if (own_reached_map) delete &reached; }
marci@148	658	void pushAndSetReached(NodeIt s) {
marci@148	659	reached.set(s, true);
marci@148	660	if (bfs_queue.empty()) {
marci@148	661	bfs_queue.push(s);
marci@148	662	G.getFirst(actual_edge, s);
marci@148	663	if (G.valid(actual_edge)/.valid()/) {
marci@148	664	NodeIt w=G.bNode(actual_edge);
marci@148	665	if (!reached.get(w)) {
marci@148	666	bfs_queue.push(w);
marci@148	667	reached.set(w, true);
marci@148	668	b_node_newly_reached=true;
marci@148	669	} else {
marci@148	670	b_node_newly_reached=false;
marci@148	671	}
marci@148	672	}
marci@148	673	} else {
marci@148	674	bfs_queue.push(s);
marci@148	675	}
marci@148	676	}
marci@158	677	BfsIterator5<GraphWrapper, /OutEdgeIt,/ ReachedMap>&
marci@148	678	operator++() {
marci@148	679	if (G.valid(actual_edge)/.valid()/) {
marci@148	680	/++/G.next(actual_edge);
marci@148	681	if (G.valid(actual_edge)/.valid()/) {
marci@148	682	NodeIt w=G.bNode(actual_edge);
marci@148	683	if (!reached.get(w)) {
marci@148	684	bfs_queue.push(w);
marci@148	685	reached.set(w, true);
marci@148	686	b_node_newly_reached=true;
marci@148	687	} else {
marci@148	688	b_node_newly_reached=false;
marci@148	689	}
marci@148	690	}
marci@148	691	} else {
marci@148	692	bfs_queue.pop();
marci@148	693	if (!bfs_queue.empty()) {
marci@148	694	G.getFirst(actual_edge, bfs_queue.front());
marci@148	695	if (G.valid(actual_edge)/.valid()/) {
marci@148	696	NodeIt w=G.bNode(actual_edge);
marci@148	697	if (!reached.get(w)) {
marci@148	698	bfs_queue.push(w);
marci@148	699	reached.set(w, true);
marci@148	700	b_node_newly_reached=true;
marci@148	701	} else {
marci@148	702	b_node_newly_reached=false;
marci@148	703	}
marci@148	704	}
marci@148	705	}
marci@148	706	}
marci@148	707	return *this;
marci@148	708	}
marci@148	709	bool finished() const { return bfs_queue.empty(); }
marci@148	710	operator OutEdgeIt () const { return actual_edge; }
marci@148	711	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@148	712	bool isANodeExamined() const { return !(G.valid(actual_edge)/.valid()/); }
marci@148	713	NodeIt aNode() const { return bfs_queue.front(); }
marci@148	714	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@148	715	const ReachedMap& getReachedMap() const { return reached; }
marci@148	716	const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
marci@148	717	};
marci@148	718
marci@144	719	template <typename Graph, typename OutEdgeIt,
marci@148	720	typename ReachedMap/=typename Graph::NodeMap<bool>/ >
marci@144	721	class DfsIterator4 {
marci@99	722	typedef typename Graph::NodeIt NodeIt;
marci@99	723	const Graph& G;
marci@99	724	std::stack<OutEdgeIt> dfs_stack;
marci@99	725	bool b_node_newly_reached;
marci@99	726	OutEdgeIt actual_edge;
marci@99	727	NodeIt actual_node;
marci@144	728	ReachedMap& reached;
marci@144	729	bool own_reached_map;
marci@144	730	public:
marci@144	731	DfsIterator4(const Graph& _G, ReachedMap& _reached) :
marci@144	732	G(_G), reached(_reached),
marci@144	733	own_reached_map(false) { }
marci@144	734	DfsIterator4(const Graph& _G) :
marci@144	735	G(_G), reached((new ReachedMap(G /, false*/))),
marci@144	736	own_reached_map(true) { }
marci@144	737	~DfsIterator4() { if (own_reached_map) delete &reached; }
marci@99	738	void pushAndSetReached(NodeIt s) {
marci@133	739	actual_node=s;
marci@99	740	reached.set(s, true);
marci@99	741	dfs_stack.push(G.template first<OutEdgeIt>(s));
marci@99	742	}
marci@99	743	DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
marci@99	744	operator++() {
marci@99	745	actual_edge=dfs_stack.top();
marci@99	746	//actual_node=G.aNode(actual_edge);
marci@148	747	if (G.valid(actual_edge)/.valid()/) {
marci@99	748	NodeIt w=G.bNode(actual_edge);
marci@99	749	actual_node=w;
marci@99	750	if (!reached.get(w)) {
marci@99	751	dfs_stack.push(G.template first<OutEdgeIt>(w));
marci@99	752	reached.set(w, true);
marci@99	753	b_node_newly_reached=true;
marci@99	754	} else {
marci@133	755	actual_node=G.aNode(actual_edge);
marci@148	756	/++/G.next(dfs_stack.top());
marci@99	757	b_node_newly_reached=false;
marci@99	758	}
marci@99	759	} else {
marci@99	760	//actual_node=G.aNode(dfs_stack.top());
marci@99	761	dfs_stack.pop();
marci@99	762	}
marci@99	763	return *this;
marci@99	764	}
marci@99	765	bool finished() const { return dfs_stack.empty(); }
marci@99	766	operator OutEdgeIt () const { return actual_edge; }
marci@99	767	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@148	768	bool isANodeExamined() const { return !(G.valid(actual_edge)/.valid()/); }
marci@133	769	NodeIt aNode() const { return actual_node; /FIXME/}
marci@99	770	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@99	771	const ReachedMap& getReachedMap() const { return reached; }
marci@99	772	const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
marci@99	773	};
marci@99	774
marci@158	775	template <typename GraphWrapper, /typename OutEdgeIt,/
marci@148	776	typename ReachedMap/=typename GraphWrapper::NodeMap<bool>/ >
marci@148	777	class DfsIterator5 {
marci@75	778	typedef typename GraphWrapper::NodeIt NodeIt;
marci@158	779	typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
marci@148	780	GraphWrapper G;
marci@148	781	std::stack<OutEdgeIt> dfs_stack;
marci@75	782	bool b_node_newly_reached;
marci@75	783	OutEdgeIt actual_edge;
marci@148	784	NodeIt actual_node;
marci@148	785	ReachedMap& reached;
marci@148	786	bool own_reached_map;
marci@75	787	public:
marci@148	788	DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
marci@148	789	G(_G), reached(_reached),
marci@148	790	own_reached_map(false) { }
marci@148	791	DfsIterator5(const GraphWrapper& _G) :
marci@148	792	G(_G), reached((new ReachedMap(G /, false*/))),
marci@148	793	own_reached_map(true) { }
marci@148	794	~DfsIterator5() { if (own_reached_map) delete &reached; }
marci@75	795	void pushAndSetReached(NodeIt s) {
marci@148	796	actual_node=s;
marci@75	797	reached.set(s, true);
marci@148	798	dfs_stack.push(G.template first<OutEdgeIt>(s));
marci@75	799	}
marci@158	800	DfsIterator5<GraphWrapper, /OutEdgeIt,/ ReachedMap>&
marci@75	801	operator++() {
marci@148	802	actual_edge=dfs_stack.top();
marci@148	803	//actual_node=G.aNode(actual_edge);
marci@148	804	if (G.valid(actual_edge)/.valid()/) {
marci@148	805	NodeIt w=G.bNode(actual_edge);
marci@148	806	actual_node=w;
marci@148	807	if (!reached.get(w)) {
marci@148	808	dfs_stack.push(G.template first<OutEdgeIt>(w));
marci@148	809	reached.set(w, true);
marci@148	810	b_node_newly_reached=true;
marci@148	811	} else {
marci@148	812	actual_node=G.aNode(actual_edge);
marci@148	813	/++/G.next(dfs_stack.top());
marci@148	814	b_node_newly_reached=false;
marci@75	815	}
marci@75	816	} else {
marci@148	817	//actual_node=G.aNode(dfs_stack.top());
marci@148	818	dfs_stack.pop();
marci@75	819	}
marci@75	820	return *this;
marci@75	821	}
marci@148	822	bool finished() const { return dfs_stack.empty(); }
marci@75	823	operator OutEdgeIt () const { return actual_edge; }
marci@75	824	bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@148	825	bool isANodeExamined() const { return !(G.valid(actual_edge)/.valid()/); }
marci@148	826	NodeIt aNode() const { return actual_node; /FIXME/}
marci@148	827	NodeIt bNode() const { return G.bNode(actual_edge); }
marci@75	828	const ReachedMap& getReachedMap() const { return reached; }
marci@148	829	const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
marci@148	830	};
marci@75	831
marci@75	832
marci@75	833
alpar@105	834	} // namespace hugo
marci@42	835
marci@58	836	#endif //BFS_ITERATOR_HH

author	alpar
	Sat, 13 Mar 2004 22:53:07 +0000
changeset 185	259540358bbf
parent 158	4f54d89fa9d2
permissions	-rw-r--r--