lemon-0.x: lemon/graph_adaptor.h@578d8b2b76c6 (annotated)

alpar@906	1	/* -- C++ --
ladanyi@1435	2	* lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
alpar@906	3	*
alpar@1164	4	* Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359	5	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906	6	*
alpar@906	7	* Permission to use, modify and distribute this software is granted
alpar@906	8	* provided that this copyright notice appears in all copies. For
alpar@906	9	* precise terms see the accompanying LICENSE file.
alpar@906	10	*
alpar@906	11	* This software is provided "AS IS" with no warranty of any kind,
alpar@906	12	* express or implied, and with no claim as to its suitability for any
alpar@906	13	* purpose.
alpar@906	14	*
alpar@906	15	*/
alpar@906	16
alpar@1401	17	#ifndef LEMON_GRAPH_ADAPTOR_H
alpar@1401	18	#define LEMON_GRAPH_ADAPTOR_H
marci@556	19
alpar@1401	20	///\ingroup graph_adaptors
marci@556	21	///\file
alpar@1401	22	///\brief Several graph adaptors.
marci@556	23	///
alpar@1401	24	///This file contains several useful graph adaptor functions.
marci@556	25	///
marci@556	26	///\author Marton Makai
marci@556	27
alpar@921	28	#include <lemon/invalid.h>
alpar@921	29	#include <lemon/maps.h>
deba@1472	30	#include <lemon/bits/erasable_graph_extender.h>
deba@1472	31	#include <lemon/bits/clearable_graph_extender.h>
deba@1472	32	#include <lemon/bits/extendable_graph_extender.h>
deba@1307	33	#include <lemon/bits/iterable_graph_extender.h>
deba@1472	34	#include <lemon/bits/alteration_notifier.h>
deba@1472	35	#include <lemon/bits/default_map.h>
marci@1383	36	#include <lemon/bits/undir_graph_extender.h>
alpar@774	37	#include <iostream>
marci@556	38
alpar@921	39	namespace lemon {
marci@556	40
alpar@1401	41	// Graph adaptors
marci@556	42
marci@1172	43	/*!
alpar@1401	44	\addtogroup graph_adaptors
marci@1004	45	@{
marci@1172	46	*/
marci@556	47
marci@1172	48	/*!
alpar@1401	49	Base type for the Graph Adaptors
marci@1242	50
alpar@1401	51	\warning Graph adaptors are in even more experimental state than the other
marci@1004	52	parts of the lib. Use them at you own risk.
marci@1242	53
alpar@1401	54	This is the base type for most of LEMON graph adaptors.
alpar@1401	55	This class implements a trivial graph adaptor i.e. it only wraps the
marci@1004	56	functions and types of the graph. The purpose of this class is to
alpar@1401	57	make easier implementing graph adaptors. E.g. if an adaptor is
marci@1004	58	considered which differs from the wrapped graph only in some of its
alpar@1401	59	functions or types, then it can be derived from GraphAdaptor, and only the
marci@1004	60	differences should be implemented.
marci@1004	61
marci@1004	62	\author Marton Makai
marci@1004	63	*/
marci@970	64	template<typename _Graph>
alpar@1401	65	class GraphAdaptorBase {
marci@970	66	public:
marci@970	67	typedef _Graph Graph;
marci@970	68	typedef Graph ParentGraph;
marci@970	69
marci@556	70	protected:
marci@556	71	Graph* graph;
alpar@1401	72	GraphAdaptorBase() : graph(0) { }
marci@556	73	void setGraph(Graph& _graph) { graph=&_graph; }
marci@556	74
marci@556	75	public:
alpar@1401	76	GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
marci@556	77
alpar@774	78	typedef typename Graph::Node Node;
alpar@774	79	typedef typename Graph::Edge Edge;
marci@556	80
marci@970	81	void first(Node& i) const { graph->first(i); }
marci@970	82	void first(Edge& i) const { graph->first(i); }
marci@970	83	void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970	84	void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556	85
marci@970	86	void next(Node& i) const { graph->next(i); }
marci@970	87	void next(Edge& i) const { graph->next(i); }
marci@970	88	void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970	89	void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970	90
alpar@986	91	Node source(const Edge& e) const { return graph->source(e); }
alpar@986	92	Node target(const Edge& e) const { return graph->target(e); }
marci@556	93
deba@1697	94	typedef NodeNumTagIndicator<Graph> NodeNumTag;
marci@556	95	int nodeNum() const { return graph->nodeNum(); }
deba@1697	96
deba@1697	97	typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
marci@556	98	int edgeNum() const { return graph->edgeNum(); }
deba@1697	99
deba@1697	100	typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1697	101	Edge findEdge(const Node& source, const Node& target,
deba@1697	102	const Edge& prev = INVALID) {
deba@1697	103	return graph->findEdge(source, target, prev);
deba@1697	104	}
marci@556	105
deba@1697	106	Node addNode() const {
deba@1697	107	return Node(graph->addNode());
deba@1697	108	}
deba@1697	109
alpar@986	110	Edge addEdge(const Node& source, const Node& target) const {
deba@1697	111	return Edge(graph->addEdge(source, target));
deba@1697	112	}
marci@556	113
marci@556	114	void erase(const Node& i) const { graph->erase(i); }
marci@556	115	void erase(const Edge& i) const { graph->erase(i); }
marci@556	116
marci@556	117	void clear() const { graph->clear(); }
marci@556	118
marci@739	119	int id(const Node& v) const { return graph->id(v); }
marci@739	120	int id(const Edge& e) const { return graph->id(e); }
marci@650	121
deba@1627	122	Edge oppositeNode(const Edge& e) const {
deba@1627	123	return Edge(graph->opposite(e));
deba@1627	124	}
marci@650	125
marci@970	126	template <typename _Value>
marci@970	127	class NodeMap : public _Graph::template NodeMap<_Value> {
marci@970	128	public:
marci@970	129	typedef typename _Graph::template NodeMap<_Value> Parent;
alpar@1401	130	NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
alpar@1401	131	NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
marci@970	132	: Parent(*gw.graph, value) { }
marci@970	133	};
marci@556	134
marci@970	135	template <typename _Value>
marci@970	136	class EdgeMap : public _Graph::template EdgeMap<_Value> {
marci@970	137	public:
marci@970	138	typedef typename _Graph::template EdgeMap<_Value> Parent;
alpar@1401	139	EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
alpar@1401	140	EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
marci@970	141	: Parent(*gw.graph, value) { }
marci@970	142	};
deba@877	143
marci@556	144	};
marci@556	145
marci@970	146	template <typename _Graph>
alpar@1401	147	class GraphAdaptor :
alpar@1401	148	public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
marci@970	149	public:
marci@970	150	typedef _Graph Graph;
alpar@1401	151	typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
marci@970	152	protected:
alpar@1401	153	GraphAdaptor() : Parent() { }
marci@569	154
marci@970	155	public:
alpar@1401	156	GraphAdaptor(Graph& _graph) { setGraph(_graph); }
marci@970	157	};
marci@569	158
marci@997	159	template <typename _Graph>
alpar@1401	160	class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@997	161	public:
marci@997	162	typedef _Graph Graph;
alpar@1401	163	typedef GraphAdaptorBase<_Graph> Parent;
marci@997	164	protected:
alpar@1401	165	RevGraphAdaptorBase() : Parent() { }
marci@997	166	public:
marci@997	167	typedef typename Parent::Node Node;
marci@997	168	typedef typename Parent::Edge Edge;
marci@997	169
marci@997	170	void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997	171	void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997	172
marci@997	173	void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997	174	void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997	175
marci@997	176	Node source(const Edge& e) const { return Parent::target(e); }
marci@997	177	Node target(const Edge& e) const { return Parent::source(e); }
marci@997	178	};
marci@997	179
marci@997	180
alpar@1401	181	/// A graph adaptor which reverses the orientation of the edges.
marci@556	182
alpar@1401	183	///\warning Graph adaptors are in even more experimental state than the other
alpar@879	184	///parts of the lib. Use them at you own risk.
alpar@879	185	///
marci@923	186	/// Let \f$G=(V, A)\f$ be a directed graph and
marci@923	187	/// suppose that a graph instange \c g of type
marci@923	188	/// \c ListGraph implements \f$G\f$.
marci@923	189	/// \code
marci@923	190	/// ListGraph g;
marci@923	191	/// \endcode
marci@923	192	/// For each directed edge
marci@923	193	/// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
marci@923	194	/// reversing its orientation.
alpar@1401	195	/// Then RevGraphAdaptor implements the graph structure with node-set
marci@923	196	/// \f$V\f$ and edge-set
marci@923	197	/// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
marci@923	198	/// reversing the orientation of its edges. The following code shows how
marci@923	199	/// such an instance can be constructed.
marci@923	200	/// \code
alpar@1401	201	/// RevGraphAdaptor<ListGraph> gw(g);
marci@923	202	/// \endcode
marci@556	203	///\author Marton Makai
marci@997	204	template<typename _Graph>
alpar@1401	205	class RevGraphAdaptor :
alpar@1401	206	public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
marci@650	207	public:
marci@997	208	typedef _Graph Graph;
marci@997	209	typedef IterableGraphExtender<
alpar@1401	210	RevGraphAdaptorBase<_Graph> > Parent;
marci@556	211	protected:
alpar@1401	212	RevGraphAdaptor() { }
marci@556	213	public:
alpar@1401	214	RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
marci@997	215	};
marci@556	216
marci@992	217
deba@1681	218	template <typename _Graph, typename NodeFilterMap,
deba@1681	219	typename EdgeFilterMap, bool checked = true>
alpar@1401	220	class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992	221	public:
marci@992	222	typedef _Graph Graph;
alpar@1401	223	typedef GraphAdaptorBase<_Graph> Parent;
marci@992	224	protected:
marci@992	225	NodeFilterMap* node_filter_map;
marci@992	226	EdgeFilterMap* edge_filter_map;
alpar@1401	227	SubGraphAdaptorBase() : Parent(),
marci@992	228	node_filter_map(0), edge_filter_map(0) { }
marci@775	229
marci@992	230	void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992	231	node_filter_map=&_node_filter_map;
marci@992	232	}
marci@992	233	void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992	234	edge_filter_map=&_edge_filter_map;
marci@992	235	}
marci@992	236
marci@992	237	public:
marci@992	238
marci@992	239	typedef typename Parent::Node Node;
marci@992	240	typedef typename Parent::Edge Edge;
marci@992	241
marci@992	242	void first(Node& i) const {
marci@992	243	Parent::first(i);
marci@992	244	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992	245	}
deba@1681	246
deba@1681	247	void first(Edge& i) const {
deba@1681	248	Parent::first(i);
deba@1681	249	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	250	\|\| !(*node_filter_map)[Parent::source(i)]
deba@1681	251	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681	252	}
deba@1681	253
deba@1681	254	void firstIn(Edge& i, const Node& n) const {
deba@1681	255	Parent::firstIn(i, n);
deba@1681	256	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	257	\|\| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681	258	}
deba@1681	259
deba@1681	260	void firstOut(Edge& i, const Node& n) const {
deba@1681	261	Parent::firstOut(i, n);
deba@1681	262	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	263	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681	264	}
deba@1681	265
deba@1681	266	void next(Node& i) const {
deba@1681	267	Parent::next(i);
deba@1681	268	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681	269	}
deba@1681	270
deba@1681	271	void next(Edge& i) const {
deba@1681	272	Parent::next(i);
deba@1681	273	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	274	\|\| !(*node_filter_map)[Parent::source(i)]
deba@1681	275	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681	276	}
deba@1681	277
deba@1681	278	void nextIn(Edge& i) const {
deba@1681	279	Parent::nextIn(i);
deba@1681	280	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	281	\|\| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681	282	}
deba@1681	283
deba@1681	284	void nextOut(Edge& i) const {
deba@1681	285	Parent::nextOut(i);
deba@1681	286	while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681	287	\|\| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681	288	}
deba@1681	289
deba@1681	290	/// This function hides \c n in the graph, i.e. the iteration
deba@1681	291	/// jumps over it. This is done by simply setting the value of \c n
deba@1681	292	/// to be false in the corresponding node-map.
deba@1681	293	void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1681	294
deba@1681	295	/// This function hides \c e in the graph, i.e. the iteration
deba@1681	296	/// jumps over it. This is done by simply setting the value of \c e
deba@1681	297	/// to be false in the corresponding edge-map.
deba@1681	298	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
deba@1681	299
deba@1681	300	/// The value of \c n is set to be true in the node-map which stores
deba@1681	301	/// hide information. If \c n was hidden previuosly, then it is shown
deba@1681	302	/// again
deba@1681	303	void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1681	304
deba@1681	305	/// The value of \c e is set to be true in the edge-map which stores
deba@1681	306	/// hide information. If \c e was hidden previuosly, then it is shown
deba@1681	307	/// again
deba@1681	308	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
deba@1681	309
deba@1681	310	/// Returns true if \c n is hidden.
deba@1681	311	bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1681	312
deba@1681	313	/// Returns true if \c n is hidden.
deba@1681	314	bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
deba@1681	315
deba@1697	316	typedef False NodeNumTag;
deba@1697	317	typedef False EdgeNumTag;
deba@1681	318	};
deba@1681	319
deba@1681	320	template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1681	321	class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@1681	322	: public GraphAdaptorBase<_Graph> {
deba@1681	323	public:
deba@1681	324	typedef _Graph Graph;
deba@1681	325	typedef GraphAdaptorBase<_Graph> Parent;
deba@1681	326	protected:
deba@1681	327	NodeFilterMap* node_filter_map;
deba@1681	328	EdgeFilterMap* edge_filter_map;
deba@1681	329	SubGraphAdaptorBase() : Parent(),
deba@1681	330	node_filter_map(0), edge_filter_map(0) { }
deba@1681	331
deba@1681	332	void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1681	333	node_filter_map=&_node_filter_map;
deba@1681	334	}
deba@1681	335	void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
deba@1681	336	edge_filter_map=&_edge_filter_map;
deba@1681	337	}
deba@1681	338
deba@1681	339	public:
deba@1681	340
deba@1681	341	typedef typename Parent::Node Node;
deba@1681	342	typedef typename Parent::Edge Edge;
deba@1681	343
deba@1681	344	void first(Node& i) const {
deba@1681	345	Parent::first(i);
deba@1681	346	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681	347	}
deba@1681	348
marci@992	349	void first(Edge& i) const {
marci@992	350	Parent::first(i);
marci@992	351	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992	352	}
deba@1681	353
marci@992	354	void firstIn(Edge& i, const Node& n) const {
marci@992	355	Parent::firstIn(i, n);
marci@992	356	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992	357	}
deba@1681	358
marci@992	359	void firstOut(Edge& i, const Node& n) const {
marci@992	360	Parent::firstOut(i, n);
marci@992	361	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992	362	}
marci@992	363
marci@992	364	void next(Node& i) const {
marci@992	365	Parent::next(i);
marci@992	366	while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992	367	}
marci@992	368	void next(Edge& i) const {
marci@992	369	Parent::next(i);
marci@992	370	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992	371	}
marci@992	372	void nextIn(Edge& i) const {
marci@992	373	Parent::nextIn(i);
marci@992	374	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992	375	}
deba@1681	376
marci@992	377	void nextOut(Edge& i) const {
marci@992	378	Parent::nextOut(i);
marci@992	379	while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992	380	}
marci@992	381
marci@992	382	/// This function hides \c n in the graph, i.e. the iteration
marci@992	383	/// jumps over it. This is done by simply setting the value of \c n
marci@992	384	/// to be false in the corresponding node-map.
marci@992	385	void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992	386
marci@992	387	/// This function hides \c e in the graph, i.e. the iteration
marci@992	388	/// jumps over it. This is done by simply setting the value of \c e
marci@992	389	/// to be false in the corresponding edge-map.
marci@992	390	void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992	391
marci@992	392	/// The value of \c n is set to be true in the node-map which stores
marci@992	393	/// hide information. If \c n was hidden previuosly, then it is shown
marci@992	394	/// again
marci@992	395	void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992	396
marci@992	397	/// The value of \c e is set to be true in the edge-map which stores
marci@992	398	/// hide information. If \c e was hidden previuosly, then it is shown
marci@992	399	/// again
marci@992	400	void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992	401
marci@992	402	/// Returns true if \c n is hidden.
marci@992	403	bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992	404
marci@992	405	/// Returns true if \c n is hidden.
marci@992	406	bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992	407
deba@1697	408	typedef False NodeNumTag;
deba@1697	409	typedef False EdgeNumTag;
marci@992	410	};
marci@775	411
alpar@1401	412	/*! \brief A graph adaptor for hiding nodes and edges from a graph.
marci@1242	413
alpar@1401	414	\warning Graph adaptors are in even more experimental state than the other
marci@930	415	parts of the lib. Use them at you own risk.
marci@930	416
alpar@1401	417	SubGraphAdaptor shows the graph with filtered node-set and
deba@1697	418	edge-set. If the \c checked parameter is true then it filters the edgeset
deba@1697	419	to do not get invalid edges without source or target.
marci@1242	420	Let \f$G=(V, A)\f$ be a directed graph
marci@1242	421	and suppose that the graph instance \c g of type ListGraph implements
marci@1242	422	\f$G\f$.
marci@1242	423	Let moreover \f$b_V\f$ and
marci@1242	424	\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
alpar@1401	425	SubGraphAdaptor<...>::NodeIt iterates
marci@1242	426	on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
alpar@1401	427	SubGraphAdaptor<...>::EdgeIt iterates
marci@1242	428	on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
alpar@1401	429	SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
marci@1242	430	only on edges leaving and entering a specific node which have true value.
marci@1242	431
deba@1697	432	If the \c checked template parameter is false then we have to note that
deba@1697	433	the node-iterator cares only the filter on the node-set, and the
deba@1697	434	edge-iterator cares only the filter on the edge-set. This way the edge-map
deba@1697	435	should filter all edges which's source or target is filtered by the
deba@1697	436	node-filter.
marci@930	437	\code
marci@1242	438	typedef ListGraph Graph;
marci@930	439	Graph g;
marci@930	440	typedef Graph::Node Node;
marci@930	441	typedef Graph::Edge Edge;
marci@930	442	Node u=g.addNode(); //node of id 0
marci@930	443	Node v=g.addNode(); //node of id 1
marci@930	444	Node e=g.addEdge(u, v); //edge of id 0
marci@930	445	Node f=g.addEdge(v, u); //edge of id 1
marci@930	446	Graph::NodeMap<bool> nm(g, true);
marci@930	447	nm.set(u, false);
marci@930	448	Graph::EdgeMap<bool> em(g, true);
marci@930	449	em.set(e, false);
alpar@1401	450	typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
marci@930	451	SubGW gw(g, nm, em);
marci@930	452	for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
marci@930	453	std::cout << ":-)" << std::endl;
marci@930	454	for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
marci@930	455	\endcode
marci@930	456	The output of the above code is the following.
marci@930	457	\code
marci@930	458	1
marci@930	459	:-)
marci@930	460	1
marci@930	461	\endcode
marci@930	462	Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
marci@930	463	\c Graph::Node that is why \c g.id(n) can be applied.
marci@930	464
alpar@1401	465	For other examples see also the documentation of NodeSubGraphAdaptor and
alpar@1401	466	EdgeSubGraphAdaptor.
marci@930	467
marci@930	468	\author Marton Makai
marci@930	469	*/
marci@992	470	template<typename _Graph, typename NodeFilterMap,
deba@1681	471	typename EdgeFilterMap, bool checked = true>
alpar@1401	472	class SubGraphAdaptor :
marci@992	473	public IterableGraphExtender<
deba@1681	474	SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
marci@650	475	public:
marci@992	476	typedef _Graph Graph;
marci@992	477	typedef IterableGraphExtender<
alpar@1401	478	SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
marci@556	479	protected:
alpar@1401	480	SubGraphAdaptor() { }
marci@992	481	public:
alpar@1401	482	SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
marci@992	483	EdgeFilterMap& _edge_filter_map) {
marci@992	484	setGraph(_graph);
marci@992	485	setNodeFilterMap(_node_filter_map);
marci@992	486	setEdgeFilterMap(_edge_filter_map);
marci@992	487	}
marci@992	488	};
marci@556	489
marci@556	490
marci@569	491
alpar@1401	492	/*! \brief An adaptor for hiding nodes from a graph.
marci@933	493
alpar@1401	494	\warning Graph adaptors are in even more experimental state than the other
marci@933	495	parts of the lib. Use them at you own risk.
marci@933	496
alpar@1401	497	An adaptor for hiding nodes from a graph.
alpar@1401	498	This adaptor specializes SubGraphAdaptor in the way that only the node-set
deba@1697	499	can be filtered. In usual case the checked parameter is true, we get the
deba@1697	500	induced subgraph. But if the checked parameter is false then we can only
deba@1697	501	filter only isolated nodes.
marci@933	502	\author Marton Makai
marci@933	503	*/
deba@1681	504	template<typename Graph, typename NodeFilterMap, bool checked = true>
alpar@1401	505	class NodeSubGraphAdaptor :
alpar@1401	506	public SubGraphAdaptor<Graph, NodeFilterMap,
deba@1681	507	ConstMap<typename Graph::Edge,bool>, checked> {
marci@933	508	public:
alpar@1401	509	typedef SubGraphAdaptor<Graph, NodeFilterMap,
marci@933	510	ConstMap<typename Graph::Edge,bool> > Parent;
marci@933	511	protected:
marci@933	512	ConstMap<typename Graph::Edge, bool> const_true_map;
marci@933	513	public:
alpar@1401	514	NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
marci@933	515	Parent(), const_true_map(true) {
marci@933	516	Parent::setGraph(_graph);
marci@933	517	Parent::setNodeFilterMap(_node_filter_map);
marci@933	518	Parent::setEdgeFilterMap(const_true_map);
marci@933	519	}
marci@933	520	};
marci@933	521
marci@933	522
alpar@1401	523	/*! \brief An adaptor for hiding edges from a graph.
marci@932	524
alpar@1401	525	\warning Graph adaptors are in even more experimental state than the other
marci@932	526	parts of the lib. Use them at you own risk.
marci@932	527
alpar@1401	528	An adaptor for hiding edges from a graph.
alpar@1401	529	This adaptor specializes SubGraphAdaptor in the way that only the edge-set
alpar@1401	530	can be filtered. The usefulness of this adaptor is demonstrated in the
marci@933	531	problem of searching a maximum number of edge-disjoint shortest paths
marci@933	532	between
marci@933	533	two nodes \c s and \c t. Shortest here means being shortest w.r.t.
marci@933	534	non-negative edge-lengths. Note that
marci@933	535	the comprehension of the presented solution
marci@1252	536	need's some elementary knowledge from combinatorial optimization.
marci@933	537
marci@933	538	If a single shortest path is to be
marci@1252	539	searched between \c s and \c t, then this can be done easily by
marci@1252	540	applying the Dijkstra algorithm. What happens, if a maximum number of
marci@933	541	edge-disjoint shortest paths is to be computed. It can be proved that an
marci@933	542	edge can be in a shortest path if and only if it is tight with respect to
marci@933	543	the potential function computed by Dijkstra. Moreover, any path containing
marci@933	544	only such edges is a shortest one. Thus we have to compute a maximum number
marci@933	545	of edge-disjoint paths between \c s and \c t in the graph which has edge-set
marci@933	546	all the tight edges. The computation will be demonstrated on the following
alpar@1536	547	graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
marci@1425	548	The full source code is available in \ref sub_graph_adaptor_demo.cc.
marci@1425	549	If you are interested in more demo programs, you can use
marci@1425	550	\ref dim_to_dot.cc to generate .dot files from dimacs files.
athos@1576	551	The .dot file of the following figure was generated by
marci@1425	552	the demo program \ref dim_to_dot.cc.
marci@1425	553
marci@933	554	\dot
marci@933	555	digraph lemon_dot_example {
marci@933	556	node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933	557	n0 [ label="0 (s)" ];
marci@933	558	n1 [ label="1" ];
marci@933	559	n2 [ label="2" ];
marci@933	560	n3 [ label="3" ];
marci@933	561	n4 [ label="4" ];
marci@933	562	n5 [ label="5" ];
marci@933	563	n6 [ label="6 (t)" ];
marci@933	564	edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933	565	n5 -> n6 [ label="9, length:4" ];
marci@933	566	n4 -> n6 [ label="8, length:2" ];
marci@933	567	n3 -> n5 [ label="7, length:1" ];
marci@933	568	n2 -> n5 [ label="6, length:3" ];
marci@933	569	n2 -> n6 [ label="5, length:5" ];
marci@933	570	n2 -> n4 [ label="4, length:2" ];
marci@933	571	n1 -> n4 [ label="3, length:3" ];
marci@933	572	n0 -> n3 [ label="2, length:1" ];
marci@933	573	n0 -> n2 [ label="1, length:2" ];
marci@933	574	n0 -> n1 [ label="0, length:3" ];
marci@933	575	}
marci@933	576	\enddot
marci@933	577
marci@933	578	\code
marci@933	579	Graph g;
marci@933	580	Node s, t;
marci@933	581	LengthMap length(g);
marci@933	582
marci@933	583	readDimacs(std::cin, g, length, s, t);
marci@933	584
alpar@986	585	cout << "edges with lengths (of form id, source--length->target): " << endl;
marci@933	586	for(EdgeIt e(g); e!=INVALID; ++e)
alpar@986	587	cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
alpar@986	588	<< length[e] << "->" << g.id(g.target(e)) << endl;
marci@933	589
marci@933	590	cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
marci@933	591	\endcode
marci@933	592	Next, the potential function is computed with Dijkstra.
marci@933	593	\code
marci@933	594	typedef Dijkstra<Graph, LengthMap> Dijkstra;
marci@933	595	Dijkstra dijkstra(g, length);
marci@933	596	dijkstra.run(s);
marci@933	597	\endcode
marci@933	598	Next, we consrtruct a map which filters the edge-set to the tight edges.
marci@933	599	\code
marci@933	600	typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
marci@933	601	TightEdgeFilter;
marci@933	602	TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
marci@933	603
alpar@1401	604	typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
marci@933	605	SubGW gw(g, tight_edge_filter);
marci@933	606	\endcode
marci@933	607	Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
marci@933	608	with a max flow algorithm Preflow.
marci@933	609	\code
marci@933	610	ConstMap<Edge, int> const_1_map(1);
marci@933	611	Graph::EdgeMap<int> flow(g, 0);
marci@933	612
marci@933	613	Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
marci@933	614	preflow(gw, s, t, const_1_map, flow);
marci@933	615	preflow.run();
marci@933	616	\endcode
marci@933	617	Last, the output is:
marci@933	618	\code
marci@933	619	cout << "maximum number of edge-disjoint shortest path: "
marci@933	620	<< preflow.flowValue() << endl;
marci@933	621	cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
marci@933	622	<< endl;
marci@933	623	for(EdgeIt e(g); e!=INVALID; ++e)
marci@933	624	if (flow[e])
alpar@986	625	cout << " " << g.id(g.source(e)) << "--"
alpar@986	626	<< length[e] << "->" << g.id(g.target(e)) << endl;
marci@933	627	\endcode
marci@933	628	The program has the following (expected :-)) output:
marci@933	629	\code
alpar@986	630	edges with lengths (of form id, source--length->target):
marci@933	631	9, 5--4->6
marci@933	632	8, 4--2->6
marci@933	633	7, 3--1->5
marci@933	634	6, 2--3->5
marci@933	635	5, 2--5->6
marci@933	636	4, 2--2->4
marci@933	637	3, 1--3->4
marci@933	638	2, 0--1->3
marci@933	639	1, 0--2->2
marci@933	640	0, 0--3->1
marci@933	641	s: 0 t: 6
marci@933	642	maximum number of edge-disjoint shortest path: 2
marci@933	643	edges of the maximum number of edge-disjoint shortest s-t paths:
marci@933	644	9, 5--4->6
marci@933	645	8, 4--2->6
marci@933	646	7, 3--1->5
marci@933	647	4, 2--2->4
marci@933	648	2, 0--1->3
marci@933	649	1, 0--2->2
marci@933	650	\endcode
marci@933	651
marci@932	652	\author Marton Makai
marci@932	653	*/
marci@932	654	template<typename Graph, typename EdgeFilterMap>
alpar@1401	655	class EdgeSubGraphAdaptor :
alpar@1401	656	public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1681	657	EdgeFilterMap, false> {
marci@932	658	public:
alpar@1401	659	typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1685	660	EdgeFilterMap, false> Parent;
marci@932	661	protected:
marci@932	662	ConstMap<typename Graph::Node, bool> const_true_map;
marci@932	663	public:
alpar@1401	664	EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
marci@932	665	Parent(), const_true_map(true) {
marci@932	666	Parent::setGraph(_graph);
marci@932	667	Parent::setNodeFilterMap(const_true_map);
marci@932	668	Parent::setEdgeFilterMap(_edge_filter_map);
marci@932	669	}
marci@932	670	};
marci@932	671
marci@1383	672	template <typename _Graph>
alpar@1401	673	class UndirGraphAdaptorBase :
alpar@1401	674	public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
marci@1383	675	public:
marci@1383	676	typedef _Graph Graph;
alpar@1401	677	typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
marci@1383	678	protected:
alpar@1401	679	UndirGraphAdaptorBase() : Parent() { }
marci@1383	680	public:
marci@1383	681	typedef typename Parent::UndirEdge UndirEdge;
marci@1383	682	typedef typename Parent::Edge Edge;
marci@1383	683
marci@1383	684	template <typename T>
marci@1383	685	class EdgeMap {
marci@1383	686	protected:
alpar@1401	687	const UndirGraphAdaptorBase<_Graph>* g;
marci@1383	688	template <typename TT> friend class EdgeMap;
marci@1383	689	typename _Graph::template EdgeMap<T> forward_map, backward_map;
marci@1383	690	public:
marci@1383	691	typedef T Value;
marci@1383	692	typedef Edge Key;
marci@1383	693
alpar@1401	694	EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
marci@1383	695	forward_map((g->graph)), backward_map((g->graph)) { }
marci@569	696
alpar@1401	697	EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
marci@1383	698	forward_map((g->graph), a), backward_map((g->graph), a) { }
marci@1383	699
marci@1383	700	void set(Edge e, T a) {
deba@1627	701	if (g->direction(e))
marci@1383	702	forward_map.set(e, a);
marci@1383	703	else
marci@1383	704	backward_map.set(e, a);
marci@1383	705	}
marci@556	706
marci@1383	707	T operator[](Edge e) const {
deba@1627	708	if (g->direction(e))
marci@1383	709	return forward_map[e];
marci@1383	710	else
marci@1383	711	return backward_map[e];
marci@556	712	}
marci@556	713	};
marci@1383	714
marci@1383	715	template <typename T>
marci@1383	716	class UndirEdgeMap {
marci@1383	717	template <typename TT> friend class UndirEdgeMap;
marci@1383	718	typename _Graph::template EdgeMap<T> map;
marci@1383	719	public:
marci@1383	720	typedef T Value;
marci@1383	721	typedef UndirEdge Key;
marci@1383	722
alpar@1401	723	UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
marci@1383	724	map(*(g.graph)) { }
marci@556	725
alpar@1401	726	UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
marci@1383	727	map(*(g.graph), a) { }
marci@1383	728
marci@1383	729	void set(UndirEdge e, T a) {
marci@1383	730	map.set(e, a);
marci@1383	731	}
marci@556	732
marci@1383	733	T operator[](UndirEdge e) const {
marci@1383	734	return map[e];
marci@1383	735	}
marci@1383	736	};
marci@1383	737
marci@1383	738	};
marci@1383	739
alpar@1401	740	/// \brief An undirected graph is made from a directed graph by an adaptor
marci@1383	741	///
marci@1383	742	/// Undocumented, untested!!!
marci@1383	743	/// If somebody knows nice demo application, let's polulate it.
marci@1383	744	///
marci@1383	745	/// \author Marton Makai
marci@1383	746	template<typename _Graph>
alpar@1401	747	class UndirGraphAdaptor :
marci@1383	748	public IterableUndirGraphExtender<
alpar@1401	749	UndirGraphAdaptorBase<_Graph> > {
marci@1383	750	public:
marci@1383	751	typedef _Graph Graph;
marci@1383	752	typedef IterableUndirGraphExtender<
alpar@1401	753	UndirGraphAdaptorBase<_Graph> > Parent;
marci@1383	754	protected:
alpar@1401	755	UndirGraphAdaptor() { }
marci@1383	756	public:
alpar@1401	757	UndirGraphAdaptor(_Graph& _graph) {
marci@1383	758	setGraph(_graph);
marci@556	759	}
marci@556	760	};
marci@556	761
marci@992	762
marci@992	763	template <typename _Graph,
marci@992	764	typename ForwardFilterMap, typename BackwardFilterMap>
alpar@1401	765	class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992	766	public:
marci@992	767	typedef _Graph Graph;
alpar@1401	768	typedef GraphAdaptorBase<_Graph> Parent;
marci@992	769	protected:
marci@992	770	ForwardFilterMap* forward_filter;
marci@992	771	BackwardFilterMap* backward_filter;
alpar@1401	772	SubBidirGraphAdaptorBase() : Parent(),
marci@992	773	forward_filter(0), backward_filter(0) { }
marci@992	774
marci@992	775	void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
marci@992	776	forward_filter=&_forward_filter;
marci@992	777	}
marci@992	778	void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
marci@992	779	backward_filter=&_backward_filter;
marci@992	780	}
marci@992	781
marci@992	782	public:
alpar@1401	783	// SubGraphAdaptorBase(Graph& _graph,
marci@992	784	// NodeFilterMap& _node_filter_map,
marci@992	785	// EdgeFilterMap& _edge_filter_map) :
marci@992	786	// Parent(&_graph),
marci@992	787	// node_filter_map(&node_filter_map),
marci@992	788	// edge_filter_map(&edge_filter_map) { }
marci@992	789
marci@992	790	typedef typename Parent::Node Node;
marci@992	791	typedef typename _Graph::Edge GraphEdge;
marci@992	792	template <typename T> class EdgeMap;
alpar@1401	793	/// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
marci@992	794	/// _Graph::Edge. It contains an extra bool flag which is true
marci@992	795	/// if and only if the
marci@992	796	/// edge is the backward version of the original edge.
marci@992	797	class Edge : public _Graph::Edge {
alpar@1401	798	friend class SubBidirGraphAdaptorBase<
marci@992	799	Graph, ForwardFilterMap, BackwardFilterMap>;
marci@992	800	template<typename T> friend class EdgeMap;
marci@992	801	protected:
marci@992	802	bool backward; //true, iff backward
marci@992	803	public:
marci@992	804	Edge() { }
marci@992	805	/// \todo =false is needed, or causes problems?
marci@992	806	/// If \c _backward is false, then we get an edge corresponding to the
marci@992	807	/// original one, otherwise its oppositely directed pair is obtained.
marci@992	808	Edge(const typename _Graph::Edge& e, bool _backward/=false/) :
marci@992	809	_Graph::Edge(e), backward(_backward) { }
marci@992	810	Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
marci@992	811	bool operator==(const Edge& v) const {
marci@992	812	return (this->backward==v.backward &&
marci@992	813	static_cast<typename _Graph::Edge>(*this)==
marci@992	814	static_cast<typename _Graph::Edge>(v));
marci@992	815	}
marci@992	816	bool operator!=(const Edge& v) const {
marci@992	817	return (this->backward!=v.backward \|\|
marci@992	818	static_cast<typename _Graph::Edge>(*this)!=
marci@992	819	static_cast<typename _Graph::Edge>(v));
marci@992	820	}
marci@992	821	};
marci@992	822
marci@992	823	void first(Node& i) const {
marci@992	824	Parent::first(i);
marci@992	825	}
marci@992	826
marci@992	827	void first(Edge& i) const {
marci@992	828	Parent::first(i);
marci@992	829	i.backward=false;
marci@992	830	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	831	!(*forward_filter)[i]) Parent::next(i);
marci@992	832	if (static_cast<GraphEdge>(&i)==INVALID) {
marci@992	833	Parent::first(i);
marci@992	834	i.backward=true;
marci@992	835	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	836	!(*backward_filter)[i]) Parent::next(i);
marci@992	837	}
marci@992	838	}
marci@992	839
marci@992	840	void firstIn(Edge& i, const Node& n) const {
marci@992	841	Parent::firstIn(i, n);
marci@992	842	i.backward=false;
marci@992	843	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@1269	844	!(*forward_filter)[i]) Parent::nextIn(i);
marci@992	845	if (static_cast<GraphEdge>(&i)==INVALID) {
marci@992	846	Parent::firstOut(i, n);
marci@992	847	i.backward=true;
marci@992	848	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	849	!(*backward_filter)[i]) Parent::nextOut(i);
marci@992	850	}
marci@992	851	}
marci@992	852
marci@992	853	void firstOut(Edge& i, const Node& n) const {
marci@992	854	Parent::firstOut(i, n);
marci@992	855	i.backward=false;
marci@992	856	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	857	!(*forward_filter)[i]) Parent::nextOut(i);
marci@992	858	if (static_cast<GraphEdge>(&i)==INVALID) {
marci@992	859	Parent::firstIn(i, n);
marci@992	860	i.backward=true;
marci@992	861	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	862	!(*backward_filter)[i]) Parent::nextIn(i);
marci@992	863	}
marci@992	864	}
marci@992	865
marci@992	866	void next(Node& i) const {
marci@992	867	Parent::next(i);
marci@992	868	}
marci@992	869
marci@992	870	void next(Edge& i) const {
marci@992	871	if (!(i.backward)) {
marci@992	872	Parent::next(i);
marci@992	873	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	874	!(*forward_filter)[i]) Parent::next(i);
marci@992	875	if (static_cast<GraphEdge>(&i)==INVALID) {
marci@992	876	Parent::first(i);
marci@992	877	i.backward=true;
marci@992	878	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	879	!(*backward_filter)[i]) Parent::next(i);
marci@992	880	}
marci@992	881	} else {
marci@992	882	Parent::next(i);
marci@992	883	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	884	!(*backward_filter)[i]) Parent::next(i);
marci@992	885	}
marci@992	886	}
marci@992	887
marci@992	888	void nextIn(Edge& i) const {
marci@992	889	if (!(i.backward)) {
marci@992	890	Node n=Parent::target(i);
marci@992	891	Parent::nextIn(i);
marci@992	892	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	893	!(*forward_filter)[i]) Parent::nextIn(i);
marci@992	894	if (static_cast<GraphEdge>(&i)==INVALID) {
marci@992	895	Parent::firstOut(i, n);
marci@992	896	i.backward=true;
marci@992	897	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	898	!(*backward_filter)[i]) Parent::nextOut(i);
marci@992	899	}
marci@992	900	} else {
marci@992	901	Parent::nextOut(i);
marci@992	902	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	903	!(*backward_filter)[i]) Parent::nextOut(i);
marci@992	904	}
marci@992	905	}
marci@992	906
marci@992	907	void nextOut(Edge& i) const {
marci@992	908	if (!(i.backward)) {
marci@992	909	Node n=Parent::source(i);
marci@992	910	Parent::nextOut(i);
marci@992	911	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	912	!(*forward_filter)[i]) Parent::nextOut(i);
marci@992	913	if (static_cast<GraphEdge>(&i)==INVALID) {
marci@992	914	Parent::firstIn(i, n);
marci@992	915	i.backward=true;
marci@992	916	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	917	!(*backward_filter)[i]) Parent::nextIn(i);
marci@992	918	}
marci@992	919	} else {
marci@992	920	Parent::nextIn(i);
marci@992	921	while (static_cast<GraphEdge>(&i)!=INVALID &&
marci@992	922	!(*backward_filter)[i]) Parent::nextIn(i);
marci@992	923	}
marci@992	924	}
marci@992	925
marci@992	926	Node source(Edge e) const {
marci@992	927	return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
marci@992	928	Node target(Edge e) const {
marci@992	929	return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
marci@992	930
marci@992	931	/// Gives back the opposite edge.
marci@992	932	Edge opposite(const Edge& e) const {
marci@992	933	Edge f=e;
marci@992	934	f.backward=!f.backward;
marci@992	935	return f;
marci@992	936	}
marci@992	937
marci@992	938	/// \warning This is a linear time operation and works only if
marci@992	939	/// \c Graph::EdgeIt is defined.
marci@992	940	/// \todo hmm
marci@992	941	int edgeNum() const {
marci@992	942	int i=0;
marci@992	943	Edge e;
marci@992	944	for (first(e); e!=INVALID; next(e)) ++i;
marci@992	945	return i;
marci@992	946	}
marci@992	947
marci@992	948	bool forward(const Edge& e) const { return !e.backward; }
marci@992	949	bool backward(const Edge& e) const { return e.backward; }
marci@992	950
marci@992	951	template <typename T>
alpar@1401	952	/// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
marci@992	953	/// _Graph::EdgeMap one for the forward edges and
marci@992	954	/// one for the backward edges.
marci@992	955	class EdgeMap {
marci@992	956	template <typename TT> friend class EdgeMap;
marci@992	957	typename _Graph::template EdgeMap<T> forward_map, backward_map;
marci@992	958	public:
marci@992	959	typedef T Value;
marci@992	960	typedef Edge Key;
marci@992	961
alpar@1401	962	EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
marci@992	963	ForwardFilterMap, BackwardFilterMap>& g) :
marci@992	964	forward_map((g.graph)), backward_map((g.graph)) { }
marci@992	965
alpar@1401	966	EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
marci@992	967	ForwardFilterMap, BackwardFilterMap>& g, T a) :
marci@992	968	forward_map((g.graph), a), backward_map((g.graph), a) { }
marci@992	969
marci@992	970	void set(Edge e, T a) {
marci@992	971	if (!e.backward)
marci@992	972	forward_map.set(e, a);
marci@992	973	else
marci@992	974	backward_map.set(e, a);
marci@992	975	}
marci@992	976
marci@992	977	// typename _Graph::template EdgeMap<T>::ConstReference
marci@992	978	// operator[](Edge e) const {
marci@992	979	// if (!e.backward)
marci@992	980	// return forward_map[e];
marci@992	981	// else
marci@992	982	// return backward_map[e];
marci@992	983	// }
marci@992	984
marci@992	985	// typename _Graph::template EdgeMap<T>::Reference
marci@1016	986	T operator[](Edge e) const {
marci@992	987	if (!e.backward)
marci@992	988	return forward_map[e];
marci@992	989	else
marci@992	990	return backward_map[e];
marci@992	991	}
marci@992	992
marci@992	993	void update() {
marci@992	994	forward_map.update();
marci@992	995	backward_map.update();
marci@992	996	}
marci@992	997	};
marci@992	998
marci@992	999	};
marci@569	1000
marci@650	1001
alpar@1401	1002	///\brief An adaptor for composing a subgraph of a
marci@792	1003	/// bidirected graph made from a directed one.
marci@612	1004	///
alpar@1401	1005	/// An adaptor for composing a subgraph of a
alpar@911	1006	/// bidirected graph made from a directed one.
alpar@911	1007	///
alpar@1401	1008	///\warning Graph adaptors are in even more experimental state than the other
alpar@879	1009	///parts of the lib. Use them at you own risk.
alpar@879	1010	///
marci@923	1011	/// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
marci@923	1012	/// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
marci@923	1013	/// reversing its orientation. We are given moreover two bool valued
marci@923	1014	/// maps on the edge-set,
marci@923	1015	/// \f$forward\_filter\f$, and \f$backward\_filter\f$.
alpar@1401	1016	/// SubBidirGraphAdaptor implements the graph structure with node-set
marci@923	1017	/// \f$V\f$ and edge-set
marci@923	1018	/// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
marci@792	1019	/// The purpose of writing + instead of union is because parallel
marci@923	1020	/// edges can arise. (Similarly, antiparallel edges also can arise).
marci@792	1021	/// In other words, a subgraph of the bidirected graph obtained, which
marci@792	1022	/// is given by orienting the edges of the original graph in both directions.
marci@923	1023	/// As the oppositely directed edges are logically different,
marci@923	1024	/// the maps are able to attach different values for them.
marci@923	1025	///
alpar@1401	1026	/// An example for such a construction is \c RevGraphAdaptor where the
marci@792	1027	/// forward_filter is everywhere false and the backward_filter is
marci@792	1028	/// everywhere true. We note that for sake of efficiency,
alpar@1401	1029	/// \c RevGraphAdaptor is implemented in a different way.
alpar@1401	1030	/// But BidirGraphAdaptor is obtained from
alpar@1401	1031	/// SubBidirGraphAdaptor by considering everywhere true
marci@910	1032	/// valued maps both for forward_filter and backward_filter.
marci@1252	1033	///
alpar@1401	1034	/// The most important application of SubBidirGraphAdaptor
alpar@1401	1035	/// is ResGraphAdaptor, which stands for the residual graph in directed
marci@792	1036	/// flow and circulation problems.
alpar@1401	1037	/// As adaptors usually, the SubBidirGraphAdaptor implements the
marci@792	1038	/// above mentioned graph structure without its physical storage,
marci@923	1039	/// that is the whole stuff is stored in constant memory.
marci@992	1040	template<typename _Graph,
marci@650	1041	typename ForwardFilterMap, typename BackwardFilterMap>
alpar@1401	1042	class SubBidirGraphAdaptor :
marci@992	1043	public IterableGraphExtender<
alpar@1401	1044	SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
marci@650	1045	public:
marci@992	1046	typedef _Graph Graph;
marci@992	1047	typedef IterableGraphExtender<
alpar@1401	1048	SubBidirGraphAdaptorBase<
marci@992	1049	_Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
marci@569	1050	protected:
alpar@1401	1051	SubBidirGraphAdaptor() { }
marci@992	1052	public:
alpar@1401	1053	SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
marci@992	1054	BackwardFilterMap& _backward_filter) {
marci@992	1055	setGraph(_graph);
marci@992	1056	setForwardFilterMap(_forward_filter);
marci@992	1057	setBackwardFilterMap(_backward_filter);
marci@992	1058	}
marci@992	1059	};
marci@650	1060
marci@569	1061
marci@650	1062
alpar@1401	1063	///\brief An adaptor for composing bidirected graph from a directed one.
marci@650	1064	///
alpar@1401	1065	///\warning Graph adaptors are in even more experimental state than the other
alpar@879	1066	///parts of the lib. Use them at you own risk.
alpar@879	1067	///
alpar@1401	1068	/// An adaptor for composing bidirected graph from a directed one.
marci@650	1069	/// A bidirected graph is composed over the directed one without physical
marci@650	1070	/// storage. As the oppositely directed edges are logically different ones
marci@650	1071	/// the maps are able to attach different values for them.
marci@650	1072	template<typename Graph>
alpar@1401	1073	class BidirGraphAdaptor :
alpar@1401	1074	public SubBidirGraphAdaptor<
marci@650	1075	Graph,
marci@650	1076	ConstMap<typename Graph::Edge, bool>,
marci@650	1077	ConstMap<typename Graph::Edge, bool> > {
marci@650	1078	public:
alpar@1401	1079	typedef SubBidirGraphAdaptor<
marci@650	1080	Graph,
marci@650	1081	ConstMap<typename Graph::Edge, bool>,
marci@650	1082	ConstMap<typename Graph::Edge, bool> > Parent;
marci@650	1083	protected:
marci@650	1084	ConstMap<typename Graph::Edge, bool> cm;
marci@650	1085
alpar@1401	1086	BidirGraphAdaptor() : Parent(), cm(true) {
marci@655	1087	Parent::setForwardFilterMap(cm);
marci@655	1088	Parent::setBackwardFilterMap(cm);
marci@655	1089	}
marci@650	1090	public:
alpar@1401	1091	BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
marci@650	1092	Parent::setGraph(_graph);
marci@650	1093	Parent::setForwardFilterMap(cm);
marci@650	1094	Parent::setBackwardFilterMap(cm);
marci@650	1095	}
marci@738	1096
marci@738	1097	int edgeNum() const {
marci@738	1098	return 2*this->graph->edgeNum();
marci@738	1099	}
marci@650	1100	};
marci@650	1101
marci@650	1102
marci@650	1103	template<typename Graph, typename Number,
marci@650	1104	typename CapacityMap, typename FlowMap>
marci@658	1105	class ResForwardFilter {
marci@658	1106	// const Graph* graph;
marci@650	1107	const CapacityMap* capacity;
marci@650	1108	const FlowMap* flow;
marci@650	1109	public:
marci@658	1110	ResForwardFilter(/const Graph& _graph, /
marci@658	1111	const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658	1112	/graph(&_graph),/ capacity(&_capacity), flow(&_flow) { }
marci@658	1113	ResForwardFilter() : /graph(0),/ capacity(0), flow(0) { }
marci@656	1114	void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656	1115	void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650	1116	bool operator[](const typename Graph::Edge& e) const {
marci@738	1117	return (Number((flow)[e]) < Number((capacity)[e]));
marci@650	1118	}
marci@650	1119	};
marci@650	1120
marci@650	1121	template<typename Graph, typename Number,
marci@650	1122	typename CapacityMap, typename FlowMap>
marci@658	1123	class ResBackwardFilter {
marci@650	1124	const CapacityMap* capacity;
marci@650	1125	const FlowMap* flow;
marci@650	1126	public:
marci@658	1127	ResBackwardFilter(/const Graph& _graph,/
marci@658	1128	const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658	1129	/graph(&_graph),/ capacity(&_capacity), flow(&_flow) { }
marci@658	1130	ResBackwardFilter() : /graph(0),/ capacity(0), flow(0) { }
marci@656	1131	void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656	1132	void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650	1133	bool operator[](const typename Graph::Edge& e) const {
marci@738	1134	return (Number(0) < Number((*flow)[e]));
marci@650	1135	}
marci@650	1136	};
marci@650	1137
marci@653	1138
alpar@1401	1139	/*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
marci@650	1140
alpar@1401	1141	An adaptor for composing the residual graph for directed flow and circulation problems.
marci@1242	1142	Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
marci@1242	1143	number type. Let moreover
marci@1242	1144	\f$f,c:A\to F\f$, be functions on the edge-set.
alpar@1401	1145	In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
marci@1242	1146	and \f$c\f$ for a capacity function.
marci@1242	1147	Suppose that a graph instange \c g of type
marci@1242	1148	\c ListGraph implements \f$G\f$.
marci@1242	1149	\code
marci@1242	1150	ListGraph g;
marci@1242	1151	\endcode
alpar@1401	1152	Then RevGraphAdaptor implements the graph structure with node-set
marci@1242	1153	\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
marci@1242	1154	\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
marci@1242	1155	\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
marci@1242	1156	i.e. the so called residual graph.
marci@1242	1157	When we take the union \f$A_{forward}\cup A_{backward}\f$,
marci@1242	1158	multilicities are counted, i.e. if an edge is in both
alpar@1401	1159	\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
marci@1242	1160	appears twice.
marci@1242	1161	The following code shows how
marci@1242	1162	such an instance can be constructed.
marci@1242	1163	\code
marci@1242	1164	typedef ListGraph Graph;
marci@1242	1165	Graph::EdgeMap<int> f(g);
marci@1242	1166	Graph::EdgeMap<int> c(g);
alpar@1401	1167	ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
marci@1242	1168	\endcode
marci@1242	1169	\author Marton Makai
marci@1242	1170	*/
marci@650	1171	template<typename Graph, typename Number,
marci@650	1172	typename CapacityMap, typename FlowMap>
alpar@1401	1173	class ResGraphAdaptor :
alpar@1401	1174	public SubBidirGraphAdaptor<
marci@650	1175	Graph,
marci@658	1176	ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
marci@658	1177	ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
marci@650	1178	public:
alpar@1401	1179	typedef SubBidirGraphAdaptor<
marci@650	1180	Graph,
marci@658	1181	ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
marci@658	1182	ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
marci@650	1183	protected:
marci@650	1184	const CapacityMap* capacity;
marci@650	1185	FlowMap* flow;
marci@658	1186	ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
marci@658	1187	ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
alpar@1401	1188	ResGraphAdaptor() : Parent(),
marci@658	1189	capacity(0), flow(0) { }
marci@658	1190	void setCapacityMap(const CapacityMap& _capacity) {
marci@658	1191	capacity=&_capacity;
marci@658	1192	forward_filter.setCapacity(_capacity);
marci@658	1193	backward_filter.setCapacity(_capacity);
marci@658	1194	}
marci@658	1195	void setFlowMap(FlowMap& _flow) {
marci@658	1196	flow=&_flow;
marci@658	1197	forward_filter.setFlow(_flow);
marci@658	1198	backward_filter.setFlow(_flow);
marci@658	1199	}
marci@650	1200	public:
alpar@1401	1201	ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
marci@650	1202	FlowMap& _flow) :
marci@650	1203	Parent(), capacity(&_capacity), flow(&_flow),
marci@658	1204	forward_filter(/_graph,/ _capacity, _flow),
marci@658	1205	backward_filter(/_graph,/ _capacity, _flow) {
marci@650	1206	Parent::setGraph(_graph);
marci@650	1207	Parent::setForwardFilterMap(forward_filter);
marci@650	1208	Parent::setBackwardFilterMap(backward_filter);
marci@650	1209	}
marci@650	1210
marci@660	1211	typedef typename Parent::Edge Edge;
marci@660	1212
marci@660	1213	void augment(const Edge& e, Number a) const {
marci@650	1214	if (Parent::forward(e))
marci@650	1215	flow->set(e, (*flow)[e]+a);
marci@650	1216	else
marci@650	1217	flow->set(e, (*flow)[e]-a);
marci@650	1218	}
marci@650	1219
marci@660	1220	/// \brief Residual capacity map.
marci@660	1221	///
marci@910	1222	/// In generic residual graphs the residual capacity can be obtained
marci@910	1223	/// as a map.
marci@660	1224	class ResCap {
marci@660	1225	protected:
alpar@1401	1226	const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
marci@660	1227	public:
alpar@987	1228	typedef Number Value;
alpar@987	1229	typedef Edge Key;
alpar@1401	1230	ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
marci@888	1231	_res_graph) : res_graph(&_res_graph) { }
marci@660	1232	Number operator[](const Edge& e) const {
marci@660	1233	if (res_graph->forward(e))
marci@660	1234	return ((res_graph->capacity))[e]-((res_graph->flow))[e];
marci@660	1235	else
marci@660	1236	return (*(res_graph->flow))[e];
marci@660	1237	}
marci@660	1238	};
marci@660	1239
alpar@1401	1240	// KEEP_MAPS(Parent, ResGraphAdaptor);
marci@650	1241	};
marci@650	1242
marci@650	1243
marci@998	1244
marci@998	1245	template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401	1246	class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@998	1247	public:
marci@998	1248	typedef _Graph Graph;
alpar@1401	1249	typedef GraphAdaptorBase<_Graph> Parent;
marci@998	1250	protected:
marci@998	1251	FirstOutEdgesMap* first_out_edges;
alpar@1401	1252	ErasingFirstGraphAdaptorBase() : Parent(),
marci@998	1253	first_out_edges(0) { }
marci@998	1254
marci@998	1255	void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998	1256	first_out_edges=&_first_out_edges;
marci@998	1257	}
marci@998	1258
marci@998	1259	public:
marci@998	1260
marci@998	1261	typedef typename Parent::Node Node;
marci@998	1262	typedef typename Parent::Edge Edge;
marci@998	1263
marci@998	1264	void firstOut(Edge& i, const Node& n) const {
marci@998	1265	i=(*first_out_edges)[n];
marci@998	1266	}
marci@998	1267
marci@998	1268	void erase(const Edge& e) const {
marci@998	1269	Node n=source(e);
marci@998	1270	Edge f=e;
marci@998	1271	Parent::nextOut(f);
marci@998	1272	first_out_edges->set(n, f);
marci@998	1273	}
marci@998	1274	};
marci@998	1275
marci@998	1276
marci@612	1277	/// For blocking flows.
marci@556	1278
alpar@1401	1279	///\warning Graph adaptors are in even more experimental state than the other
alpar@879	1280	///parts of the lib. Use them at you own risk.
alpar@879	1281	///
alpar@1401	1282	/// This graph adaptor is used for on-the-fly
marci@792	1283	/// Dinits blocking flow computations.
marci@612	1284	/// For each node, an out-edge is stored which is used when the
marci@612	1285	/// \code
marci@612	1286	/// OutEdgeIt& first(OutEdgeIt&, const Node&)
marci@612	1287	/// \endcode
marci@612	1288	/// is called.
marci@556	1289	///
marci@792	1290	/// \author Marton Makai
marci@998	1291	template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401	1292	class ErasingFirstGraphAdaptor :
marci@998	1293	public IterableGraphExtender<
alpar@1401	1294	ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
marci@650	1295	public:
marci@998	1296	typedef _Graph Graph;
marci@998	1297	typedef IterableGraphExtender<
alpar@1401	1298	ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
alpar@1401	1299	ErasingFirstGraphAdaptor(Graph& _graph,
marci@998	1300	FirstOutEdgesMap& _first_out_edges) {
marci@998	1301	setGraph(_graph);
marci@998	1302	setFirstOutEdgesMap(_first_out_edges);
marci@998	1303	}
marci@1019	1304
marci@998	1305	};
marci@556	1306
deba@1472	1307	template <typename _Graph>
deba@1697	1308	class SplitGraphAdaptorBase
deba@1697	1309	: public GraphAdaptorBase<_Graph> {
deba@1697	1310	public:
deba@1697	1311	typedef GraphAdaptorBase<_Graph> Parent;
deba@1697	1312
deba@1697	1313	class Node;
deba@1697	1314	class Edge;
deba@1697	1315	template <typename T> class NodeMap;
deba@1697	1316	template <typename T> class EdgeMap;
deba@1697	1317
deba@1697	1318
deba@1697	1319	class Node : public Parent::Node {
deba@1697	1320	friend class SplitGraphAdaptorBase;
deba@1697	1321	template <typename T> friend class NodeMap;
deba@1697	1322	typedef typename Parent::Node NodeParent;
deba@1697	1323	private:
deba@1697	1324
deba@1697	1325	bool entry;
deba@1697	1326	Node(typename Parent::Node _node, bool _entry)
deba@1697	1327	: Parent::Node(_node), entry(_entry) {}
deba@1697	1328
deba@1697	1329	public:
deba@1697	1330	Node() {}
deba@1697	1331	Node(Invalid) : NodeParent(INVALID), entry(true) {}
deba@1697	1332
deba@1697	1333	bool operator==(const Node& node) const {
deba@1697	1334	return NodeParent::operator==(node) && entry == node.entry;
deba@1697	1335	}
deba@1697	1336
deba@1697	1337	bool operator!=(const Node& node) const {
deba@1697	1338	return !(*this == node);
deba@1697	1339	}
deba@1697	1340
deba@1697	1341	bool operator<(const Node& node) const {
deba@1697	1342	return NodeParent::operator<(node) \|\|
deba@1697	1343	(NodeParent::operator==(node) && entry < node.entry);
deba@1697	1344	}
deba@1697	1345	};
deba@1697	1346
deba@1697	1347	/// \todo May we want VARIANT/union type
deba@1697	1348	class Edge : public Parent::Edge {
deba@1697	1349	friend class SplitGraphAdaptorBase;
deba@1697	1350	template <typename T> friend class EdgeMap;
deba@1697	1351	private:
deba@1697	1352	typedef typename Parent::Edge EdgeParent;
deba@1697	1353	typedef typename Parent::Node NodeParent;
deba@1697	1354	NodeParent bind;
deba@1697	1355
deba@1697	1356	Edge(const EdgeParent& edge, const NodeParent& node)
deba@1697	1357	: EdgeParent(edge), bind(node) {}
deba@1697	1358	public:
deba@1697	1359	Edge() {}
deba@1697	1360	Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
deba@1697	1361
deba@1697	1362	bool operator==(const Edge& edge) const {
deba@1697	1363	return EdgeParent::operator==(edge) && bind == edge.bind;
deba@1697	1364	}
deba@1697	1365
deba@1697	1366	bool operator!=(const Edge& edge) const {
deba@1697	1367	return !(*this == edge);
deba@1697	1368	}
deba@1697	1369
deba@1697	1370	bool operator<(const Edge& edge) const {
deba@1697	1371	return EdgeParent::operator<(edge) \|\|
deba@1697	1372	(EdgeParent::operator==(edge) && bind < edge.bind);
deba@1697	1373	}
deba@1697	1374	};
deba@1697	1375
deba@1697	1376	void first(Node& node) const {
deba@1697	1377	Parent::first(node);
deba@1697	1378	node.entry = true;
deba@1697	1379	}
deba@1697	1380
deba@1697	1381	void next(Node& node) const {
deba@1697	1382	if (node.entry) {
deba@1697	1383	node.entry = false;
deba@1697	1384	} else {
deba@1697	1385	node.entry = true;
deba@1697	1386	Parent::next(node);
deba@1697	1387	}
deba@1697	1388	}
deba@1697	1389
deba@1697	1390	void first(Edge& edge) const {
deba@1697	1391	Parent::first(edge);
deba@1697	1392	if ((typename Parent::Edge&)edge == INVALID) {
deba@1697	1393	Parent::first(edge.bind);
deba@1697	1394	} else {
deba@1697	1395	edge.bind = INVALID;
deba@1697	1396	}
deba@1697	1397	}
deba@1697	1398
deba@1697	1399	void next(Edge& edge) const {
deba@1697	1400	if ((typename Parent::Edge&)edge != INVALID) {
deba@1697	1401	Parent::next(edge);
deba@1697	1402	if ((typename Parent::Edge&)edge == INVALID) {
deba@1697	1403	Parent::first(edge.bind);
deba@1697	1404	}
deba@1697	1405	} else {
deba@1697	1406	Parent::next(edge.bind);
deba@1697	1407	}
deba@1697	1408	}
deba@1697	1409
deba@1697	1410	void firstIn(Edge& edge, const Node& node) const {
deba@1697	1411	if (node.entry) {
deba@1697	1412	Parent::firstIn(edge, node);
deba@1697	1413	edge.bind = INVALID;
deba@1697	1414	} else {
deba@1697	1415	(typename Parent::Edge&)edge = INVALID;
deba@1697	1416	edge.bind = node;
deba@1697	1417	}
deba@1697	1418	}
deba@1697	1419
deba@1697	1420	void nextIn(Edge& edge) const {
deba@1697	1421	if ((typename Parent::Edge&)edge != INVALID) {
deba@1697	1422	Parent::nextIn(edge);
deba@1697	1423	} else {
deba@1697	1424	edge.bind = INVALID;
deba@1697	1425	}
deba@1697	1426	}
deba@1697	1427
deba@1697	1428	void firstOut(Edge& edge, const Node& node) const {
deba@1697	1429	if (!node.entry) {
deba@1697	1430	Parent::firstOut(edge, node);
deba@1697	1431	edge.bind = INVALID;
deba@1697	1432	} else {
deba@1697	1433	(typename Parent::Edge&)edge = INVALID;
deba@1697	1434	edge.bind = node;
deba@1697	1435	}
deba@1697	1436	}
deba@1697	1437
deba@1697	1438	void nextOut(Edge& edge) const {
deba@1697	1439	if ((typename Parent::Edge&)edge != INVALID) {
deba@1697	1440	Parent::nextOut(edge);
deba@1697	1441	} else {
deba@1697	1442	edge.bind = INVALID;
deba@1697	1443	}
deba@1697	1444	}
deba@1697	1445
deba@1697	1446	Node source(const Edge& edge) const {
deba@1697	1447	if ((typename Parent::Edge&)edge != INVALID) {
deba@1697	1448	return Node(Parent::source(edge), false);
deba@1697	1449	} else {
deba@1697	1450	return Node(edge.bind, true);
deba@1697	1451	}
deba@1697	1452	}
deba@1697	1453
deba@1697	1454	Node target(const Edge& edge) const {
deba@1697	1455	if ((typename Parent::Edge&)edge != INVALID) {
deba@1697	1456	return Node(Parent::target(edge), true);
deba@1697	1457	} else {
deba@1697	1458	return Node(edge.bind, false);
deba@1697	1459	}
deba@1697	1460	}
deba@1697	1461
deba@1697	1462	static bool entryNode(const Node& node) {
deba@1697	1463	return node.entry;
deba@1697	1464	}
deba@1697	1465
deba@1697	1466	static bool exitNode(const Node& node) {
deba@1697	1467	return !node.entry;
deba@1697	1468	}
deba@1697	1469
deba@1697	1470	static Node getEntry(const typename Parent::Node& node) {
deba@1697	1471	return Node(node, true);
deba@1697	1472	}
deba@1697	1473
deba@1697	1474	static Node getExit(const typename Parent::Node& node) {
deba@1697	1475	return Node(node, false);
deba@1697	1476	}
deba@1697	1477
deba@1697	1478	static bool originalEdge(const Edge& edge) {
deba@1697	1479	return (typename Parent::Edge&)edge != INVALID;
deba@1697	1480	}
deba@1697	1481
deba@1697	1482	static bool bindingEdge(const Edge& edge) {
deba@1697	1483	return edge.bind != INVALID;
deba@1697	1484	}
deba@1697	1485
deba@1697	1486	static Node getBindedNode(const Edge& edge) {
deba@1697	1487	return edge.bind;
deba@1697	1488	}
deba@1697	1489
deba@1697	1490	int nodeNum() const {
deba@1697	1491	return Parent::nodeNum() * 2;
deba@1697	1492	}
deba@1697	1493
deba@1697	1494	typedef CompileTimeAnd<typename Parent::NodeNumTag,
deba@1697	1495	typename Parent::EdgeNumTag> EdgeNumTag;
deba@1697	1496
deba@1697	1497	int edgeNum() const {
deba@1697	1498	return Parent::edgeNum() + Parent::nodeNum();
deba@1697	1499	}
deba@1697	1500
deba@1697	1501	Edge findEdge(const Node& source, const Node& target,
deba@1697	1502	const Edge& prev = INVALID) const {
deba@1697	1503	if (exitNode(source) && entryNode(target)) {
deba@1697	1504	return Parent::findEdge(source, target, prev);
deba@1697	1505	} else {
deba@1697	1506	if (prev == INVALID && entryNode(source) && exitNode(target) &&
deba@1697	1507	(typename Parent::Node&)source == (typename Parent::Node&)target) {
deba@1697	1508	return Edge(INVALID, source);
deba@1697	1509	} else {
deba@1697	1510	return INVALID;
deba@1697	1511	}
deba@1697	1512	}
deba@1697	1513	}
deba@1697	1514
deba@1697	1515	template <typename T>
deba@1697	1516	class NodeMap : public MapBase<Node, T> {
deba@1697	1517	typedef typename Parent::template NodeMap<T> NodeImpl;
deba@1697	1518	public:
deba@1697	1519	NodeMap(const SplitGraphAdaptorBase& _graph)
deba@1697	1520	: entry(_graph), exit(_graph) {}
deba@1697	1521	NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@1697	1522	: entry(_graph, t), exit(_graph, t) {}
deba@1697	1523
deba@1697	1524	void set(const Node& key, const T& val) {
deba@1697	1525	if (key.entry) { entry.set(key, val); }
deba@1697	1526	else {exit.set(key, val); }
deba@1697	1527	}
deba@1697	1528
deba@1697	1529	typename ReferenceMapTraits<NodeImpl>::Reference
deba@1697	1530	operator[](const Node& key) {
deba@1697	1531	if (key.entry) { return entry[key]; }
deba@1697	1532	else { return exit[key]; }
deba@1697	1533	}
deba@1697	1534
deba@1697	1535	T operator[](const Node& key) const {
deba@1697	1536	if (key.entry) { return entry[key]; }
deba@1697	1537	else { return exit[key]; }
deba@1697	1538	}
deba@1697	1539
deba@1697	1540	private:
deba@1697	1541	NodeImpl entry, exit;
deba@1697	1542	};
deba@1697	1543
deba@1697	1544	template <typename T>
deba@1697	1545	class EdgeMap : public MapBase<Edge, T> {
deba@1697	1546	typedef typename Parent::template NodeMap<T> NodeImpl;
deba@1697	1547	typedef typename Parent::template EdgeMap<T> EdgeImpl;
deba@1697	1548	public:
deba@1697	1549	EdgeMap(const SplitGraphAdaptorBase& _graph)
deba@1697	1550	: bind(_graph), orig(_graph) {}
deba@1697	1551	EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@1697	1552	: bind(_graph, t), orig(_graph, t) {}
deba@1697	1553
deba@1697	1554	void set(const Edge& key, const T& val) {
deba@1697	1555	if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
deba@1697	1556	else {bind.set(key.bind, val); }
deba@1697	1557	}
deba@1697	1558
deba@1697	1559	typename ReferenceMapTraits<EdgeImpl>::Reference
deba@1697	1560	operator[](const Edge& key) {
deba@1697	1561	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
deba@1697	1562	else {return bind[key.bind]; }
deba@1697	1563	}
deba@1697	1564
deba@1697	1565	T operator[](const Edge& key) const {
deba@1697	1566	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
deba@1697	1567	else {return bind[key.bind]; }
deba@1697	1568	}
deba@1697	1569
deba@1697	1570	private:
deba@1697	1571	typename Parent::template NodeMap<T> bind;
deba@1697	1572	typename Parent::template EdgeMap<T> orig;
deba@1697	1573	};
deba@1697	1574
deba@1697	1575	template <typename EntryMap, typename ExitMap>
deba@1697	1576	class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
deba@1697	1577	public:
deba@1697	1578	typedef MapBase<Node, typename EntryMap::Value> Parent;
deba@1697	1579
deba@1697	1580	typedef typename Parent::Key Key;
deba@1697	1581	typedef typename Parent::Value Value;
deba@1697	1582
deba@1697	1583	CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
deba@1697	1584	: entryMap(_entryMap), exitMap(_exitMap) {}
deba@1697	1585
deba@1697	1586	Value& operator[](const Key& key) {
deba@1697	1587	if (key.entry) {
deba@1697	1588	return entryMap[key];
deba@1697	1589	} else {
deba@1697	1590	return exitMap[key];
deba@1697	1591	}
deba@1697	1592	}
deba@1697	1593
deba@1697	1594	Value operator[](const Key& key) const {
deba@1697	1595	if (key.entry) {
deba@1697	1596	return entryMap[key];
deba@1697	1597	} else {
deba@1697	1598	return exitMap[key];
deba@1697	1599	}
deba@1697	1600	}
deba@1697	1601
deba@1697	1602	void set(const Key& key, const Value& value) {
deba@1697	1603	if (key.entry) {
deba@1697	1604	entryMap.set(key, value);
deba@1697	1605	} else {
deba@1697	1606	exitMap.set(key, value);
deba@1697	1607	}
deba@1697	1608	}
deba@1697	1609
deba@1697	1610	private:
deba@1697	1611
deba@1697	1612	EntryMap& entryMap;
deba@1697	1613	ExitMap& exitMap;
deba@1697	1614
deba@1697	1615	};
deba@1697	1616
deba@1697	1617	template <typename EdgeMap, typename NodeMap>
deba@1697	1618	class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
deba@1697	1619	public:
deba@1697	1620	typedef MapBase<Edge, typename EdgeMap::Value> Parent;
deba@1697	1621
deba@1697	1622	typedef typename Parent::Key Key;
deba@1697	1623	typedef typename Parent::Value Value;
deba@1697	1624
deba@1697	1625	CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
deba@1697	1626	: edgeMap(_edgeMap), nodeMap(_nodeMap) {}
deba@1697	1627
deba@1697	1628	void set(const Edge& edge, const Value& val) {
deba@1697	1629	if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1697	1630	edgeMap.set(edge, val);
deba@1697	1631	} else {
deba@1697	1632	nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
deba@1697	1633	}
deba@1697	1634	}
deba@1697	1635
deba@1697	1636	Value operator[](const Key& edge) const {
deba@1697	1637	if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1697	1638	return edgeMap[edge];
deba@1697	1639	} else {
deba@1697	1640	return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
deba@1697	1641	}
deba@1697	1642	}
deba@1697	1643
deba@1697	1644	Value& operator[](const Key& edge) {
deba@1697	1645	if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1697	1646	return edgeMap[edge];
deba@1697	1647	} else {
deba@1697	1648	return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
deba@1697	1649	}
deba@1697	1650	}
deba@1697	1651
deba@1697	1652	private:
deba@1697	1653	EdgeMap& edgeMap;
deba@1697	1654	NodeMap& nodeMap;
deba@1697	1655	};
deba@1697	1656
deba@1697	1657	};
deba@1697	1658
deba@1697	1659	template <typename _Graph>
deba@1697	1660	class SplitGraphAdaptor
deba@1697	1661	: public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
deba@1697	1662	public:
deba@1697	1663	typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@1697	1664
deba@1697	1665	SplitGraphAdaptor(_Graph& graph) {
deba@1697	1666	Parent::setGraph(graph);
deba@1697	1667	}
deba@1697	1668
deba@1697	1669
deba@1697	1670	};
deba@1697	1671
deba@1697	1672	template <typename _Graph>
deba@1472	1673	class NewEdgeSetAdaptorBase {
deba@1472	1674	public:
deba@1472	1675
deba@1472	1676	typedef _Graph Graph;
deba@1472	1677	typedef typename Graph::Node Node;
deba@1472	1678	typedef typename Graph::NodeIt NodeIt;
deba@1472	1679
deba@1472	1680	protected:
deba@1472	1681
deba@1472	1682	struct NodeT {
deba@1472	1683	int first_out, first_in;
deba@1472	1684	NodeT() : first_out(-1), first_in(-1) {}
deba@1472	1685	};
deba@1472	1686
deba@1472	1687	class NodesImpl : protected Graph::template NodeMap<NodeT> {
deba@1472	1688
deba@1472	1689	typedef typename Graph::template NodeMap<NodeT> Parent;
deba@1472	1690	typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
deba@1472	1691
deba@1472	1692	Adaptor& adaptor;
deba@1472	1693
deba@1472	1694	public:
deba@1472	1695
deba@1472	1696	NodesImpl(Adaptor& _adaptor, const Graph& _graph)
deba@1472	1697	: Parent(_graph), adaptor(_adaptor) {}
deba@1472	1698
deba@1472	1699	virtual ~NodesImpl() {}
deba@1472	1700
deba@1472	1701	virtual void build() {
deba@1472	1702	Parent::build();
deba@1472	1703	}
deba@1472	1704
deba@1472	1705	virtual void clear() {
deba@1472	1706	adaptor._clear();
deba@1472	1707	Parent::clear();
deba@1472	1708	}
deba@1472	1709
deba@1472	1710	virtual void add(const Node& node) {
deba@1472	1711	Parent::add(node);
deba@1472	1712	adaptor._add(node);
deba@1472	1713	}
deba@1472	1714
deba@1472	1715	virtual void erase(const Node& node) {
deba@1472	1716	adaptor._erase(node);
deba@1472	1717	Parent::erase(node);
deba@1472	1718	}
deba@1472	1719
deba@1472	1720	NodeT& operator[](const Node& node) {
deba@1472	1721	return Parent::operator[](node);
deba@1472	1722	}
deba@1472	1723
deba@1472	1724	const NodeT& operator[](const Node& node) const {
deba@1472	1725	return Parent::operator[](node);
deba@1472	1726	}
deba@1472	1727
deba@1472	1728	};
deba@1472	1729
deba@1472	1730	NodesImpl* nodes;
deba@1472	1731
deba@1472	1732	struct EdgeT {
deba@1472	1733	Node source, target;
deba@1472	1734	int next_out, next_in;
deba@1472	1735	int prev_out, prev_in;
deba@1472	1736	EdgeT() : prev_out(-1), prev_in(-1) {}
deba@1472	1737	};
deba@1472	1738
deba@1472	1739	std::vector<EdgeT> edges;
deba@1472	1740
deba@1472	1741	int first_edge;
deba@1472	1742	int first_free_edge;
deba@1472	1743
deba@1472	1744	virtual void _clear() = 0;
deba@1472	1745	virtual void _add(const Node& node) = 0;
deba@1472	1746	virtual void _erase(const Node& node) = 0;
deba@1472	1747
deba@1472	1748	const Graph* graph;
deba@1472	1749
deba@1472	1750	void initalize(const Graph& _graph, NodesImpl& _nodes) {
deba@1472	1751	graph = &_graph;
deba@1472	1752	nodes = &_nodes;
deba@1472	1753	}
deba@1472	1754
deba@1472	1755	public:
deba@1472	1756
deba@1472	1757	class Edge {
deba@1472	1758	friend class NewEdgeSetAdaptorBase<Graph>;
deba@1472	1759	protected:
deba@1472	1760	Edge(int _id) : id(_id) {}
deba@1472	1761	int id;
deba@1472	1762	public:
deba@1472	1763	Edge() {}
deba@1472	1764	Edge(Invalid) : id(-1) {}
deba@1472	1765	bool operator==(const Edge& edge) const { return id == edge.id; }
deba@1472	1766	bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@1472	1767	bool operator<(const Edge& edge) const { return id < edge.id; }
deba@1472	1768	};
deba@1472	1769
deba@1472	1770	NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
deba@1472	1771	virtual ~NewEdgeSetAdaptorBase() {}
deba@1472	1772
deba@1472	1773	Edge addEdge(const Node& source, const Node& target) {
deba@1472	1774	int n;
deba@1472	1775	if (first_free_edge == -1) {
deba@1472	1776	n = edges.size();
deba@1472	1777	edges.push_back(EdgeT());
deba@1472	1778	} else {
deba@1472	1779	n = first_free_edge;
deba@1472	1780	first_free_edge = edges[first_free_edge].next_in;
deba@1472	1781	}
deba@1472	1782	edges[n].next_in = (*nodes)[target].first_in;
deba@1472	1783	(*nodes)[target].first_in = n;
deba@1472	1784	edges[n].next_out = (*nodes)[source].first_out;
deba@1472	1785	(*nodes)[source].first_out = n;
deba@1472	1786	edges[n].source = source;
deba@1472	1787	edges[n].target = target;
deba@1472	1788	return Edge(n);
deba@1472	1789	}
deba@1472	1790
deba@1472	1791	void erase(const Edge& edge) {
deba@1472	1792	int n = edge.id;
deba@1472	1793	if (edges[n].prev_in != -1) {
deba@1472	1794	edges[edges[n].prev_in].next_in = edges[n].next_in;
deba@1472	1795	} else {
deba@1472	1796	(*nodes)[edges[n].target].first_in = edges[n].next_in;
deba@1472	1797	}
deba@1472	1798	if (edges[n].next_in != -1) {
deba@1472	1799	edges[edges[n].next_in].prev_in = edges[n].prev_in;
deba@1472	1800	}
deba@1472	1801
deba@1472	1802	if (edges[n].prev_out != -1) {
deba@1472	1803	edges[edges[n].prev_out].next_out = edges[n].next_out;
deba@1472	1804	} else {
deba@1472	1805	(*nodes)[edges[n].source].first_out = edges[n].next_out;
deba@1472	1806	}
deba@1472	1807	if (edges[n].next_out != -1) {
deba@1472	1808	edges[edges[n].next_out].prev_out = edges[n].prev_out;
deba@1472	1809	}
deba@1472	1810
deba@1472	1811	}
deba@1472	1812
deba@1472	1813	void first(Node& node) const {
deba@1472	1814	graph->first(node);
deba@1472	1815	}
deba@1472	1816
deba@1472	1817	void next(Node& node) const {
deba@1472	1818	graph->next(node);
deba@1472	1819	}
deba@1472	1820
deba@1472	1821	void first(Edge& edge) const {
deba@1472	1822	Node node;
deba@1472	1823	for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
deba@1472	1824	next(node));
deba@1472	1825	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1472	1826	}
deba@1472	1827
deba@1472	1828	void next(Edge& edge) const {
deba@1472	1829	if (edges[edge.id].next_in != -1) {
deba@1472	1830	edge.id = edges[edge.id].next_in;
deba@1472	1831	} else {
deba@1472	1832	Node node = edges[edge.id].target;
deba@1472	1833	for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
deba@1472	1834	next(node));
deba@1472	1835	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1472	1836	}
deba@1472	1837	}
deba@1472	1838
deba@1472	1839	void firstOut(Edge& edge, const Node& node) const {
deba@1472	1840	edge.id = (*nodes)[node].first_out;
deba@1472	1841	}
deba@1472	1842
deba@1472	1843	void nextOut(Edge& edge) const {
deba@1472	1844	edge.id = edges[edge.id].next_out;
deba@1472	1845	}
deba@1472	1846
deba@1472	1847	void firstIn(Edge& edge, const Node& node) const {
deba@1472	1848	edge.id = (*nodes)[node].first_in;
deba@1472	1849	}
deba@1472	1850
deba@1472	1851	void nextIn(Edge& edge) const {
deba@1472	1852	edge.id = edges[edge.id].next_in;
deba@1472	1853	}
deba@1472	1854
deba@1472	1855	int id(const Node& node) const { return graph->id(node); }
deba@1472	1856	int id(const Edge& edge) const { return edge.id; }
deba@1472	1857
deba@1472	1858	Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
deba@1472	1859	Edge fromId(int id, Edge) const { return Edge(id); }
deba@1472	1860
deba@1472	1861	int maxId(Node) const { return graph->maxId(Node()); };
deba@1472	1862	int maxId(Edge) const { return edges.size() - 1; }
deba@1472	1863
deba@1472	1864	Node source(const Edge& edge) const { return edges[edge.id].source;}
deba@1472	1865	Node target(const Edge& edge) const { return edges[edge.id].target;}
deba@1472	1866
deba@1472	1867	};
deba@1472	1868
deba@1538	1869
deba@1538	1870	/// \brief Graph adaptor using a node set of another graph and an
deba@1538	1871	/// own edge set.
deba@1538	1872	///
deba@1538	1873	/// This structure can be used to establish another graph over a node set
deba@1538	1874	/// of an existing one. The node iterator will go through the nodes of the
deba@1538	1875	/// original graph.
deba@1538	1876	///
deba@1538	1877	/// \param _Graph The type of the graph which shares its node set with
alpar@1631	1878	/// this class. Its interface must conform to the \ref concept::StaticGraph
deba@1538	1879	/// "StaticGraph" concept.
deba@1538	1880	///
deba@1538	1881	/// In the edge extension and removing it conforms to the
alpar@1631	1882	/// \ref concept::ExtendableGraph "ExtendableGraph" concept.
deba@1472	1883	template <typename _Graph>
deba@1472	1884	class NewEdgeSetAdaptor :
deba@1472	1885	public ErasableGraphExtender<
deba@1472	1886	ClearableGraphExtender<
deba@1472	1887	ExtendableGraphExtender<
deba@1669	1888	MappableGraphExtender<
deba@1472	1889	IterableGraphExtender<
deba@1472	1890	AlterableGraphExtender<
deba@1472	1891	NewEdgeSetAdaptorBase<_Graph> > > > > > > {
deba@1472	1892
deba@1472	1893	public:
deba@1472	1894
deba@1472	1895	typedef ErasableGraphExtender<
deba@1472	1896	ClearableGraphExtender<
deba@1472	1897	ExtendableGraphExtender<
deba@1669	1898	MappableGraphExtender<
deba@1472	1899	IterableGraphExtender<
deba@1472	1900	AlterableGraphExtender<
deba@1472	1901	NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
deba@1472	1902
deba@1472	1903
deba@1472	1904	typedef typename Parent::Node Node;
deba@1472	1905	typedef typename Parent::Edge Edge;
deba@1472	1906
deba@1472	1907	private:
deba@1472	1908
deba@1472	1909	virtual void _clear() {
deba@1472	1910	Parent::edges.clear();
deba@1472	1911	Parent::first_edge = -1;
deba@1472	1912	Parent::first_free_edge = -1;
deba@1472	1913	Parent::getNotifier(Edge()).clear();
deba@1472	1914	Parent::getNotifier(Node()).clear();
deba@1472	1915	}
deba@1472	1916
deba@1472	1917	virtual void _add(const Node& node) {
deba@1472	1918	Parent::getNotifier(Node()).add(node);
deba@1472	1919	}
deba@1472	1920
deba@1472	1921	virtual void _erase(const Node& node) {
deba@1472	1922	Edge edge;
deba@1472	1923	Parent::firstOut(edge, node);
deba@1472	1924	while (edge != INVALID) {
deba@1472	1925	Parent::erase(edge);
deba@1472	1926	Parent::firstOut(edge, node);
deba@1472	1927	}
deba@1472	1928
deba@1472	1929	Parent::firstIn(edge, node);
deba@1472	1930	while (edge != INVALID) {
deba@1472	1931	Parent::erase(edge);
deba@1472	1932	Parent::firstIn(edge, node);
deba@1472	1933	}
deba@1472	1934
deba@1472	1935	Parent::getNotifier(Node()).erase(node);
deba@1472	1936	}
deba@1472	1937
deba@1472	1938
deba@1472	1939	typedef typename Parent::NodesImpl NodesImpl;
deba@1472	1940
deba@1472	1941	NodesImpl nodes;
deba@1472	1942
deba@1472	1943	public:
deba@1472	1944
deba@1538	1945	/// \brief Constructor of the adaptor.
deba@1538	1946	///
deba@1538	1947	/// Constructor of the adaptor.
deba@1472	1948	NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
deba@1472	1949	Parent::initalize(_graph, nodes);
deba@1472	1950	}
deba@1472	1951
deba@1472	1952	void clear() {
deba@1538	1953	Parent::getNotifier(Edge()).clear();
deba@1538	1954
deba@1472	1955	Parent::edges.clear();
deba@1472	1956	Parent::first_edge = -1;
deba@1472	1957	Parent::first_free_edge = -1;
deba@1538	1958	}
deba@1538	1959
deba@1538	1960	};
deba@1472	1961
deba@1538	1962	/// \brief Graph adaptor using a node set of another graph and an
deba@1538	1963	/// own undir edge set.
deba@1538	1964	///
deba@1538	1965	/// This structure can be used to establish another undirected graph over
deba@1538	1966	/// a node set of an existing one. The node iterator will go through the
deba@1538	1967	/// nodes of the original graph.
deba@1538	1968	///
deba@1538	1969	/// \param _Graph The type of the graph which shares its node set with
alpar@1631	1970	/// this class. Its interface must conform to the \ref concept::StaticGraph
deba@1538	1971	/// "StaticGraph" concept.
deba@1538	1972	///
deba@1538	1973	/// In the edge extension and removing it conforms to the
alpar@1631	1974	/// \ref concept::ExtendableGraph "ExtendableGraph" concept.
deba@1538	1975	template <typename _Graph>
deba@1538	1976	class NewUndirEdgeSetAdaptor :
deba@1538	1977	public ErasableUndirGraphExtender<
deba@1538	1978	ClearableUndirGraphExtender<
deba@1538	1979	ExtendableUndirGraphExtender<
deba@1538	1980	MappableUndirGraphExtender<
deba@1538	1981	IterableUndirGraphExtender<
deba@1538	1982	AlterableUndirGraphExtender<
deba@1538	1983	UndirGraphExtender<
deba@1538	1984	NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
deba@1538	1985
deba@1538	1986	public:
deba@1538	1987
deba@1538	1988	typedef ErasableUndirGraphExtender<
deba@1538	1989	ClearableUndirGraphExtender<
deba@1538	1990	ExtendableUndirGraphExtender<
deba@1538	1991	MappableUndirGraphExtender<
deba@1538	1992	IterableUndirGraphExtender<
deba@1538	1993	AlterableUndirGraphExtender<
deba@1538	1994	UndirGraphExtender<
deba@1538	1995	NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
deba@1538	1996
deba@1538	1997
deba@1538	1998	typedef typename Parent::Node Node;
deba@1538	1999	typedef typename Parent::Edge Edge;
deba@1538	2000	typedef typename Parent::UndirEdge UndirEdge;
deba@1538	2001
deba@1538	2002	private:
deba@1538	2003
deba@1538	2004	virtual void _clear() {
deba@1538	2005	Parent::edges.clear();
deba@1538	2006	Parent::first_edge = -1;
deba@1538	2007	Parent::first_free_edge = -1;
deba@1538	2008	Parent::getNotifier(Edge()).clear();
deba@1538	2009	Parent::getNotifier(Node()).clear();
deba@1538	2010	}
deba@1538	2011
deba@1538	2012	virtual void _add(const Node& node) {
deba@1538	2013	Parent::getNotifier(Node()).add(node);
deba@1538	2014	}
deba@1538	2015
deba@1538	2016	virtual void _erase(const Node& node) {
deba@1538	2017	Edge edge;
deba@1538	2018	Parent::firstOut(edge, node);
deba@1538	2019	while (edge != INVALID) {
deba@1538	2020	Parent::erase(edge);
deba@1538	2021	Parent::firstOut(edge, node);
deba@1538	2022	}
deba@1538	2023
deba@1538	2024	Parent::firstIn(edge, node);
deba@1538	2025	while (edge != INVALID) {
deba@1538	2026	Parent::erase(edge);
deba@1538	2027	Parent::firstIn(edge, node);
deba@1538	2028	}
deba@1538	2029
deba@1538	2030	Parent::getNotifier(Node()).erase(node);
deba@1538	2031	}
deba@1538	2032
deba@1538	2033	typedef typename Parent::NodesImpl NodesImpl;
deba@1538	2034
deba@1538	2035	NodesImpl nodes;
deba@1538	2036
deba@1538	2037	public:
deba@1538	2038
deba@1538	2039
deba@1538	2040	/// \brief Constructor of the adaptor.
deba@1538	2041	///
deba@1538	2042	/// Constructor of the adaptor.
deba@1538	2043	NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
deba@1538	2044	Parent::initalize(_graph, nodes);
deba@1538	2045	}
deba@1538	2046
deba@1538	2047	void clear() {
deba@1472	2048	Parent::getNotifier(Edge()).clear();
deba@1538	2049	Parent::getNotifier(UndirEdge()).clear();
deba@1538	2050
deba@1538	2051	Parent::edges.clear();
deba@1538	2052	Parent::first_edge = -1;
deba@1538	2053	Parent::first_free_edge = -1;
deba@1472	2054	}
deba@1472	2055
deba@1472	2056	};
deba@1472	2057
marci@556	2058	///@}
marci@556	2059
alpar@921	2060	} //namespace lemon
marci@556	2061
alpar@1401	2062	#endif //LEMON_GRAPH_ADAPTOR_H
marci@556	2063

author	deba
	Fri, 14 Oct 2005 10:49:51 +0000
changeset 1720	578d8b2b76c6
parent 1685	5b37a10234bc
child 1725	22752dd6c693
permissions	-rw-r--r--