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

author	jacint
	Thu, 11 Mar 2004 12:55:50 +0000
changeset 167	7949a29a334e
parent 148	004fdf703abb
child 168	27fbd1559fb7
permissions	-rw-r--r--