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

author	hegyi
	Mon, 21 Nov 2005 18:03:20 +0000
changeset 1823	cb082cdf3667
parent 1755	bf267b301a5e
child 1839	b2dfd32b4895
permissions	-rw-r--r--