Context Navigation

bfs_iterator.hh @ 214:44f01e580f16

Last change on this file since 214:44f01e580f16 was 168:27fbd1559fb7, checked in by marci, 21 years ago
graph wrapper improvements, blocking flow on fly
File size: 25.3 KB

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

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

Context Navigation

source: lemon-0.x/src/work/bfs_iterator.hh @ 214:44f01e580f16

Download in other formats: