lemon-1.3: lemon/edge_set.h@fb5af0411793 (annotated)

deba@468	1	/* -- mode: C++; indent-tabs-mode: nil; --
deba@468	2	*
deba@468	3	* This file is a part of LEMON, a generic C++ optimization library.
deba@468	4	*
deba@468	5	* Copyright (C) 2003-2008
deba@468	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@468	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@468	8	*
deba@468	9	* Permission to use, modify and distribute this software is granted
deba@468	10	* provided that this copyright notice appears in all copies. For
deba@468	11	* precise terms see the accompanying LICENSE file.
deba@468	12	*
deba@468	13	* This software is provided "AS IS" with no warranty of any kind,
deba@468	14	* express or implied, and with no claim as to its suitability for any
deba@468	15	* purpose.
deba@468	16	*
deba@468	17	*/
deba@468	18
deba@468	19	#ifndef LEMON_EDGE_SET_H
deba@468	20	#define LEMON_EDGE_SET_H
deba@468	21
deba@468	22	#include <lemon/core.h>
deba@468	23	#include <lemon/bits/edge_set_extender.h>
deba@468	24
deba@468	25	/// \ingroup semi_adaptors
deba@468	26	/// \file
deba@468	27	/// \brief ArcSet and EdgeSet classes.
deba@468	28	///
deba@468	29	/// Graphs which use another graph's node-set as own.
deba@468	30	namespace lemon {
deba@468	31
deba@468	32	template <typename _Graph>
deba@468	33	class ListArcSetBase {
deba@468	34	public:
deba@468	35
deba@468	36	typedef _Graph Graph;
deba@468	37	typedef typename Graph::Node Node;
deba@468	38	typedef typename Graph::NodeIt NodeIt;
deba@468	39
deba@468	40	protected:
deba@468	41
deba@468	42	struct NodeT {
deba@468	43	int first_out, first_in;
deba@468	44	NodeT() : first_out(-1), first_in(-1) {}
deba@468	45	};
deba@468	46
deba@468	47	typedef typename ItemSetTraits<Graph, Node>::
deba@468	48	template Map<NodeT>::Type NodesImplBase;
deba@468	49
deba@468	50	NodesImplBase* nodes;
deba@468	51
deba@468	52	struct ArcT {
deba@468	53	Node source, target;
deba@468	54	int next_out, next_in;
deba@468	55	int prev_out, prev_in;
deba@468	56	ArcT() : prev_out(-1), prev_in(-1) {}
deba@468	57	};
deba@468	58
deba@468	59	std::vector<ArcT> arcs;
deba@468	60
deba@468	61	int first_arc;
deba@468	62	int first_free_arc;
deba@468	63
deba@468	64	const Graph* graph;
deba@468	65
deba@468	66	void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@468	67	graph = &_graph;
deba@468	68	nodes = &_nodes;
deba@468	69	}
deba@468	70
deba@468	71	public:
deba@468	72
deba@468	73	class Arc {
deba@468	74	friend class ListArcSetBase<Graph>;
deba@468	75	protected:
deba@468	76	Arc(int _id) : id(_id) {}
deba@468	77	int id;
deba@468	78	public:
deba@468	79	Arc() {}
deba@468	80	Arc(Invalid) : id(-1) {}
deba@468	81	bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468	82	bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468	83	bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468	84	};
deba@468	85
deba@468	86	ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
deba@468	87
deba@468	88	Arc addArc(const Node& u, const Node& v) {
deba@468	89	int n;
deba@468	90	if (first_free_arc == -1) {
deba@468	91	n = arcs.size();
deba@468	92	arcs.push_back(ArcT());
deba@468	93	} else {
deba@468	94	n = first_free_arc;
deba@468	95	first_free_arc = arcs[first_free_arc].next_in;
deba@468	96	}
deba@468	97	arcs[n].next_in = (*nodes)[v].first_in;
deba@468	98	if ((*nodes)[v].first_in != -1) {
deba@468	99	arcs[(*nodes)[v].first_in].prev_in = n;
deba@468	100	}
deba@468	101	(*nodes)[v].first_in = n;
deba@468	102	arcs[n].next_out = (*nodes)[u].first_out;
deba@468	103	if ((*nodes)[u].first_out != -1) {
deba@468	104	arcs[(*nodes)[u].first_out].prev_out = n;
deba@468	105	}
deba@468	106	(*nodes)[u].first_out = n;
deba@468	107	arcs[n].source = u;
deba@468	108	arcs[n].target = v;
deba@468	109	return Arc(n);
deba@468	110	}
deba@468	111
deba@468	112	void erase(const Arc& arc) {
deba@468	113	int n = arc.id;
deba@468	114	if (arcs[n].prev_in != -1) {
deba@468	115	arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
deba@468	116	} else {
deba@468	117	(*nodes)[arcs[n].target].first_in = arcs[n].next_in;
deba@468	118	}
deba@468	119	if (arcs[n].next_in != -1) {
deba@468	120	arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
deba@468	121	}
deba@468	122
deba@468	123	if (arcs[n].prev_out != -1) {
deba@468	124	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@468	125	} else {
deba@468	126	(*nodes)[arcs[n].source].first_out = arcs[n].next_out;
deba@468	127	}
deba@468	128	if (arcs[n].next_out != -1) {
deba@468	129	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
deba@468	130	}
deba@468	131
deba@468	132	}
deba@468	133
deba@468	134	void clear() {
deba@468	135	Node node;
deba@468	136	for (first(node); node != INVALID; next(node)) {
deba@468	137	(*nodes)[node].first_in = -1;
deba@468	138	(*nodes)[node].first_out = -1;
deba@468	139	}
deba@468	140	arcs.clear();
deba@468	141	first_arc = -1;
deba@468	142	first_free_arc = -1;
deba@468	143	}
deba@468	144
deba@468	145	void first(Node& node) const {
deba@468	146	graph->first(node);
deba@468	147	}
deba@468	148
deba@468	149	void next(Node& node) const {
deba@468	150	graph->next(node);
deba@468	151	}
deba@468	152
deba@468	153	void first(Arc& arc) const {
deba@468	154	Node node;
deba@468	155	first(node);
deba@468	156	while (node != INVALID && (*nodes)[node].first_in == -1) {
deba@468	157	next(node);
deba@468	158	}
deba@468	159	arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@468	160	}
deba@468	161
deba@468	162	void next(Arc& arc) const {
deba@468	163	if (arcs[arc.id].next_in != -1) {
deba@468	164	arc.id = arcs[arc.id].next_in;
deba@468	165	} else {
deba@468	166	Node node = arcs[arc.id].target;
deba@468	167	next(node);
deba@468	168	while (node != INVALID && (*nodes)[node].first_in == -1) {
deba@468	169	next(node);
deba@468	170	}
deba@468	171	arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@468	172	}
deba@468	173	}
deba@468	174
deba@468	175	void firstOut(Arc& arc, const Node& node) const {
deba@468	176	arc.id = (*nodes)[node].first_out;
deba@468	177	}
deba@468	178
deba@468	179	void nextOut(Arc& arc) const {
deba@468	180	arc.id = arcs[arc.id].next_out;
deba@468	181	}
deba@468	182
deba@468	183	void firstIn(Arc& arc, const Node& node) const {
deba@468	184	arc.id = (*nodes)[node].first_in;
deba@468	185	}
deba@468	186
deba@468	187	void nextIn(Arc& arc) const {
deba@468	188	arc.id = arcs[arc.id].next_in;
deba@468	189	}
deba@468	190
deba@468	191	int id(const Node& node) const { return graph->id(node); }
deba@468	192	int id(const Arc& arc) const { return arc.id; }
deba@468	193
deba@468	194	Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
deba@468	195	Arc arcFromId(int ix) const { return Arc(ix); }
deba@468	196
deba@468	197	int maxNodeId() const { return graph->maxNodeId(); };
deba@468	198	int maxArcId() const { return arcs.size() - 1; }
deba@468	199
deba@468	200	Node source(const Arc& arc) const { return arcs[arc.id].source;}
deba@468	201	Node target(const Arc& arc) const { return arcs[arc.id].target;}
deba@468	202
deba@468	203	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@468	204
deba@468	205	NodeNotifier& notifier(Node) const {
deba@468	206	return graph->notifier(Node());
deba@468	207	}
deba@468	208
deba@468	209	template <typename _Value>
deba@468	210	class NodeMap : public Graph::template NodeMap<_Value> {
deba@468	211	public:
deba@468	212
deba@468	213	typedef typename _Graph::template NodeMap<_Value> Parent;
deba@468	214
deba@468	215	explicit NodeMap(const ListArcSetBase<Graph>& arcset)
deba@468	216	: Parent(*arcset.graph) {}
deba@468	217
deba@468	218	NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
deba@468	219	: Parent(*arcset.graph, value) {}
deba@468	220
deba@468	221	NodeMap& operator=(const NodeMap& cmap) {
deba@468	222	return operator=<NodeMap>(cmap);
deba@468	223	}
deba@468	224
deba@468	225	template <typename CMap>
deba@468	226	NodeMap& operator=(const CMap& cmap) {
deba@468	227	Parent::operator=(cmap);
deba@468	228	return *this;
deba@468	229	}
deba@468	230	};
deba@468	231
deba@468	232	};
deba@468	233
deba@468	234	/// \ingroup semi_adaptors
deba@468	235	///
deba@468	236	/// \brief Digraph using a node set of another digraph or graph and
deba@468	237	/// an own arc set.
deba@468	238	///
deba@468	239	/// This structure can be used to establish another directed graph
deba@468	240	/// over a node set of an existing one. This class uses the same
deba@468	241	/// Node type as the underlying graph, and each valid node of the
deba@468	242	/// original graph is valid in this arc set, therefore the node
deba@468	243	/// objects of the original graph can be used directly with this
deba@468	244	/// class. The node handling functions (id handling, observing, and
deba@468	245	/// iterators) works equivalently as in the original graph.
deba@468	246	///
deba@468	247	/// This implementation is based on doubly-linked lists, from each
deba@468	248	/// node the outgoing and the incoming arcs make up lists, therefore
deba@468	249	/// one arc can be erased in constant time. It also makes possible,
deba@468	250	/// that node can be removed from the underlying graph, in this case
deba@468	251	/// all arcs incident to the given node is erased from the arc set.
deba@468	252	///
deba@468	253	/// \param _Graph The type of the graph which shares its node set with
deba@468	254	/// this class. Its interface must conform to the
deba@468	255	/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468	256	/// concept.
deba@468	257	///
deba@468	258	/// This class is fully conform to the \ref concepts::Digraph
deba@468	259	/// "Digraph" concept.
deba@468	260	template <typename _Graph>
deba@468	261	class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
deba@468	262
deba@468	263	public:
deba@468	264
deba@468	265	typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
deba@468	266
deba@468	267	typedef typename Parent::Node Node;
deba@468	268	typedef typename Parent::Arc Arc;
deba@468	269
deba@468	270	typedef _Graph Graph;
deba@468	271
deba@468	272
deba@468	273	typedef typename Parent::NodesImplBase NodesImplBase;
deba@468	274
deba@468	275	void eraseNode(const Node& node) {
deba@468	276	Arc arc;
deba@468	277	Parent::firstOut(arc, node);
deba@468	278	while (arc != INVALID ) {
deba@468	279	erase(arc);
deba@468	280	Parent::firstOut(arc, node);
deba@468	281	}
deba@468	282
deba@468	283	Parent::firstIn(arc, node);
deba@468	284	while (arc != INVALID ) {
deba@468	285	erase(arc);
deba@468	286	Parent::firstIn(arc, node);
deba@468	287	}
deba@468	288	}
deba@468	289
deba@468	290	void clearNodes() {
deba@468	291	Parent::clear();
deba@468	292	}
deba@468	293
deba@468	294	class NodesImpl : public NodesImplBase {
deba@468	295	public:
deba@468	296	typedef NodesImplBase Parent;
deba@468	297
deba@468	298	NodesImpl(const Graph& graph, ListArcSet& arcset)
deba@468	299	: Parent(graph), _arcset(arcset) {}
deba@468	300
deba@468	301	virtual ~NodesImpl() {}
deba@468	302
deba@468	303	protected:
deba@468	304
deba@468	305	virtual void erase(const Node& node) {
deba@468	306	_arcset.eraseNode(node);
deba@468	307	Parent::erase(node);
deba@468	308	}
deba@468	309	virtual void erase(const std::vector<Node>& nodes) {
deba@468	310	for (int i = 0; i < int(nodes.size()); ++i) {
deba@468	311	_arcset.eraseNode(nodes[i]);
deba@468	312	}
deba@468	313	Parent::erase(nodes);
deba@468	314	}
deba@468	315	virtual void clear() {
deba@468	316	_arcset.clearNodes();
deba@468	317	Parent::clear();
deba@468	318	}
deba@468	319
deba@468	320	private:
deba@468	321	ListArcSet& _arcset;
deba@468	322	};
deba@468	323
deba@468	324	NodesImpl nodes;
deba@468	325
deba@468	326	public:
deba@468	327
deba@468	328	/// \brief Constructor of the ArcSet.
deba@468	329	///
deba@468	330	/// Constructor of the ArcSet.
deba@468	331	ListArcSet(const Graph& graph) : nodes(graph, *this) {
deba@468	332	Parent::initalize(graph, nodes);
deba@468	333	}
deba@468	334
deba@468	335	/// \brief Add a new arc to the digraph.
deba@468	336	///
deba@468	337	/// Add a new arc to the digraph with source node \c s
deba@468	338	/// and target node \c t.
deba@468	339	/// \return the new arc.
deba@468	340	Arc addArc(const Node& s, const Node& t) {
deba@468	341	return Parent::addArc(s, t);
deba@468	342	}
deba@468	343
deba@468	344	/// \brief Erase an arc from the digraph.
deba@468	345	///
deba@468	346	/// Erase an arc \c a from the digraph.
deba@468	347	void erase(const Arc& a) {
deba@468	348	return Parent::erase(a);
deba@468	349	}
deba@468	350
deba@468	351	};
deba@468	352
deba@468	353	template <typename _Graph>
deba@468	354	class ListEdgeSetBase {
deba@468	355	public:
deba@468	356
deba@468	357	typedef _Graph Graph;
deba@468	358	typedef typename Graph::Node Node;
deba@468	359	typedef typename Graph::NodeIt NodeIt;
deba@468	360
deba@468	361	protected:
deba@468	362
deba@468	363	struct NodeT {
deba@468	364	int first_out;
deba@468	365	NodeT() : first_out(-1) {}
deba@468	366	};
deba@468	367
deba@468	368	typedef typename ItemSetTraits<Graph, Node>::
deba@468	369	template Map<NodeT>::Type NodesImplBase;
deba@468	370
deba@468	371	NodesImplBase* nodes;
deba@468	372
deba@468	373	struct ArcT {
deba@468	374	Node target;
deba@468	375	int prev_out, next_out;
deba@468	376	ArcT() : prev_out(-1), next_out(-1) {}
deba@468	377	};
deba@468	378
deba@468	379	std::vector<ArcT> arcs;
deba@468	380
deba@468	381	int first_arc;
deba@468	382	int first_free_arc;
deba@468	383
deba@468	384	const Graph* graph;
deba@468	385
deba@468	386	void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@468	387	graph = &_graph;
deba@468	388	nodes = &_nodes;
deba@468	389	}
deba@468	390
deba@468	391	public:
deba@468	392
deba@468	393	class Edge {
deba@468	394	friend class ListEdgeSetBase;
deba@468	395	protected:
deba@468	396
deba@468	397	int id;
deba@468	398	explicit Edge(int _id) { id = _id;}
deba@468	399
deba@468	400	public:
deba@468	401	Edge() {}
deba@468	402	Edge (Invalid) { id = -1; }
deba@468	403	bool operator==(const Edge& arc) const {return id == arc.id;}
deba@468	404	bool operator!=(const Edge& arc) const {return id != arc.id;}
deba@468	405	bool operator<(const Edge& arc) const {return id < arc.id;}
deba@468	406	};
deba@468	407
deba@468	408	class Arc {
deba@468	409	friend class ListEdgeSetBase;
deba@468	410	protected:
deba@468	411	Arc(int _id) : id(_id) {}
deba@468	412	int id;
deba@468	413	public:
deba@468	414	operator Edge() const { return edgeFromId(id / 2); }
deba@468	415
deba@468	416	Arc() {}
deba@468	417	Arc(Invalid) : id(-1) {}
deba@468	418	bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468	419	bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468	420	bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468	421	};
deba@468	422
deba@468	423	ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
deba@468	424
deba@468	425	Edge addEdge(const Node& u, const Node& v) {
deba@468	426	int n;
deba@468	427
deba@468	428	if (first_free_arc == -1) {
deba@468	429	n = arcs.size();
deba@468	430	arcs.push_back(ArcT());
deba@468	431	arcs.push_back(ArcT());
deba@468	432	} else {
deba@468	433	n = first_free_arc;
deba@468	434	first_free_arc = arcs[n].next_out;
deba@468	435	}
deba@468	436
deba@468	437	arcs[n].target = u;
deba@468	438	arcs[n \| 1].target = v;
deba@468	439
deba@468	440	arcs[n].next_out = (*nodes)[v].first_out;
deba@468	441	if ((*nodes)[v].first_out != -1) {
deba@468	442	arcs[(*nodes)[v].first_out].prev_out = n;
deba@468	443	}
deba@468	444	(*nodes)[v].first_out = n;
deba@468	445	arcs[n].prev_out = -1;
deba@468	446
deba@468	447	if ((*nodes)[u].first_out != -1) {
deba@468	448	arcs[(*nodes)[u].first_out].prev_out = (n \| 1);
deba@468	449	}
deba@468	450	arcs[n \| 1].next_out = (*nodes)[u].first_out;
deba@468	451	(*nodes)[u].first_out = (n \| 1);
deba@468	452	arcs[n \| 1].prev_out = -1;
deba@468	453
deba@468	454	return Edge(n / 2);
deba@468	455	}
deba@468	456
deba@468	457	void erase(const Edge& arc) {
deba@468	458	int n = arc.id * 2;
deba@468	459
deba@468	460	if (arcs[n].next_out != -1) {
deba@468	461	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
deba@468	462	}
deba@468	463
deba@468	464	if (arcs[n].prev_out != -1) {
deba@468	465	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@468	466	} else {
deba@468	467	(*nodes)[arcs[n \| 1].target].first_out = arcs[n].next_out;
deba@468	468	}
deba@468	469
deba@468	470	if (arcs[n \| 1].next_out != -1) {
deba@468	471	arcs[arcs[n \| 1].next_out].prev_out = arcs[n \| 1].prev_out;
deba@468	472	}
deba@468	473
deba@468	474	if (arcs[n \| 1].prev_out != -1) {
deba@468	475	arcs[arcs[n \| 1].prev_out].next_out = arcs[n \| 1].next_out;
deba@468	476	} else {
deba@468	477	(*nodes)[arcs[n].target].first_out = arcs[n \| 1].next_out;
deba@468	478	}
deba@468	479
deba@468	480	arcs[n].next_out = first_free_arc;
deba@468	481	first_free_arc = n;
deba@468	482
deba@468	483	}
deba@468	484
deba@468	485	void clear() {
deba@468	486	Node node;
deba@468	487	for (first(node); node != INVALID; next(node)) {
deba@468	488	(*nodes)[node].first_out = -1;
deba@468	489	}
deba@468	490	arcs.clear();
deba@468	491	first_arc = -1;
deba@468	492	first_free_arc = -1;
deba@468	493	}
deba@468	494
deba@468	495	void first(Node& node) const {
deba@468	496	graph->first(node);
deba@468	497	}
deba@468	498
deba@468	499	void next(Node& node) const {
deba@468	500	graph->next(node);
deba@468	501	}
deba@468	502
deba@468	503	void first(Arc& arc) const {
deba@468	504	Node node;
deba@468	505	first(node);
deba@468	506	while (node != INVALID && (*nodes)[node].first_out == -1) {
deba@468	507	next(node);
deba@468	508	}
deba@468	509	arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
deba@468	510	}
deba@468	511
deba@468	512	void next(Arc& arc) const {
deba@468	513	if (arcs[arc.id].next_out != -1) {
deba@468	514	arc.id = arcs[arc.id].next_out;
deba@468	515	} else {
deba@468	516	Node node = arcs[arc.id ^ 1].target;
deba@468	517	next(node);
deba@468	518	while(node != INVALID && (*nodes)[node].first_out == -1) {
deba@468	519	next(node);
deba@468	520	}
deba@468	521	arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
deba@468	522	}
deba@468	523	}
deba@468	524
deba@468	525	void first(Edge& edge) const {
deba@468	526	Node node;
deba@468	527	first(node);
deba@468	528	while (node != INVALID) {
deba@468	529	edge.id = (*nodes)[node].first_out;
deba@468	530	while ((edge.id & 1) != 1) {
deba@468	531	edge.id = arcs[edge.id].next_out;
deba@468	532	}
deba@468	533	if (edge.id != -1) {
deba@468	534	edge.id /= 2;
deba@468	535	return;
deba@468	536	}
deba@468	537	next(node);
deba@468	538	}
deba@468	539	edge.id = -1;
deba@468	540	}
deba@468	541
deba@468	542	void next(Edge& edge) const {
deba@468	543	Node node = arcs[edge.id * 2].target;
deba@468	544	edge.id = arcs[(edge.id * 2) \| 1].next_out;
deba@468	545	while ((edge.id & 1) != 1) {
deba@468	546	edge.id = arcs[edge.id].next_out;
deba@468	547	}
deba@468	548	if (edge.id != -1) {
deba@468	549	edge.id /= 2;
deba@468	550	return;
deba@468	551	}
deba@468	552	next(node);
deba@468	553	while (node != INVALID) {
deba@468	554	edge.id = (*nodes)[node].first_out;
deba@468	555	while ((edge.id & 1) != 1) {
deba@468	556	edge.id = arcs[edge.id].next_out;
deba@468	557	}
deba@468	558	if (edge.id != -1) {
deba@468	559	edge.id /= 2;
deba@468	560	return;
deba@468	561	}
deba@468	562	next(node);
deba@468	563	}
deba@468	564	edge.id = -1;
deba@468	565	}
deba@468	566
deba@468	567	void firstOut(Arc& arc, const Node& node) const {
deba@468	568	arc.id = (*nodes)[node].first_out;
deba@468	569	}
deba@468	570
deba@468	571	void nextOut(Arc& arc) const {
deba@468	572	arc.id = arcs[arc.id].next_out;
deba@468	573	}
deba@468	574
deba@468	575	void firstIn(Arc& arc, const Node& node) const {
deba@468	576	arc.id = (((*nodes)[node].first_out) ^ 1);
deba@468	577	if (arc.id == -2) arc.id = -1;
deba@468	578	}
deba@468	579
deba@468	580	void nextIn(Arc& arc) const {
deba@468	581	arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
deba@468	582	if (arc.id == -2) arc.id = -1;
deba@468	583	}
deba@468	584
deba@468	585	void firstInc(Edge &arc, bool& dir, const Node& node) const {
deba@468	586	int de = (*nodes)[node].first_out;
deba@468	587	if (de != -1 ) {
deba@468	588	arc.id = de / 2;
deba@468	589	dir = ((de & 1) == 1);
deba@468	590	} else {
deba@468	591	arc.id = -1;
deba@468	592	dir = true;
deba@468	593	}
deba@468	594	}
deba@468	595	void nextInc(Edge &arc, bool& dir) const {
deba@468	596	int de = (arcs[(arc.id * 2) \| (dir ? 1 : 0)].next_out);
deba@468	597	if (de != -1 ) {
deba@468	598	arc.id = de / 2;
deba@468	599	dir = ((de & 1) == 1);
deba@468	600	} else {
deba@468	601	arc.id = -1;
deba@468	602	dir = true;
deba@468	603	}
deba@468	604	}
deba@468	605
deba@468	606	static bool direction(Arc arc) {
deba@468	607	return (arc.id & 1) == 1;
deba@468	608	}
deba@468	609
deba@468	610	static Arc direct(Edge edge, bool dir) {
deba@468	611	return Arc(edge.id * 2 + (dir ? 1 : 0));
deba@468	612	}
deba@468	613
deba@468	614	int id(const Node& node) const { return graph->id(node); }
deba@468	615	static int id(Arc e) { return e.id; }
deba@468	616	static int id(Edge e) { return e.id; }
deba@468	617
deba@468	618	Node nodeFromId(int id) const { return graph->nodeFromId(id); }
deba@468	619	static Arc arcFromId(int id) { return Arc(id);}
deba@468	620	static Edge edgeFromId(int id) { return Edge(id);}
deba@468	621
deba@468	622	int maxNodeId() const { return graph->maxNodeId(); };
deba@468	623	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@468	624	int maxArcId() const { return arcs.size()-1; }
deba@468	625
deba@468	626	Node source(Arc e) const { return arcs[e.id ^ 1].target; }
deba@468	627	Node target(Arc e) const { return arcs[e.id].target; }
deba@468	628
deba@468	629	Node u(Edge e) const { return arcs[2 * e.id].target; }
deba@468	630	Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
deba@468	631
deba@468	632	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@468	633
deba@468	634	NodeNotifier& notifier(Node) const {
deba@468	635	return graph->notifier(Node());
deba@468	636	}
deba@468	637
deba@468	638	template <typename _Value>
deba@468	639	class NodeMap : public Graph::template NodeMap<_Value> {
deba@468	640	public:
deba@468	641
deba@468	642	typedef typename _Graph::template NodeMap<_Value> Parent;
deba@468	643
deba@468	644	explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
deba@468	645	: Parent(*arcset.graph) {}
deba@468	646
deba@468	647	NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
deba@468	648	: Parent(*arcset.graph, value) {}
deba@468	649
deba@468	650	NodeMap& operator=(const NodeMap& cmap) {
deba@468	651	return operator=<NodeMap>(cmap);
deba@468	652	}
deba@468	653
deba@468	654	template <typename CMap>
deba@468	655	NodeMap& operator=(const CMap& cmap) {
deba@468	656	Parent::operator=(cmap);
deba@468	657	return *this;
deba@468	658	}
deba@468	659	};
deba@468	660
deba@468	661	};
deba@468	662
deba@468	663	/// \ingroup semi_adaptors
deba@468	664	///
deba@468	665	/// \brief Graph using a node set of another digraph or graph and an
deba@468	666	/// own edge set.
deba@468	667	///
deba@468	668	/// This structure can be used to establish another graph over a
deba@468	669	/// node set of an existing one. This class uses the same Node type
deba@468	670	/// as the underlying graph, and each valid node of the original
deba@468	671	/// graph is valid in this arc set, therefore the node objects of
deba@468	672	/// the original graph can be used directly with this class. The
deba@468	673	/// node handling functions (id handling, observing, and iterators)
deba@468	674	/// works equivalently as in the original graph.
deba@468	675	///
deba@468	676	/// This implementation is based on doubly-linked lists, from each
deba@468	677	/// node the incident edges make up lists, therefore one edge can be
deba@468	678	/// erased in constant time. It also makes possible, that node can
deba@468	679	/// be removed from the underlying graph, in this case all edges
deba@468	680	/// incident to the given node is erased from the arc set.
deba@468	681	///
deba@468	682	/// \param _Graph The type of the graph which shares its node set
deba@468	683	/// with this class. Its interface must conform to the
deba@468	684	/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468	685	/// concept.
deba@468	686	///
deba@468	687	/// This class is fully conform to the \ref concepts::Graph "Graph"
deba@468	688	/// concept.
deba@468	689	template <typename _Graph>
deba@468	690	class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
deba@468	691
deba@468	692	public:
deba@468	693
deba@468	694	typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
deba@468	695
deba@468	696	typedef typename Parent::Node Node;
deba@468	697	typedef typename Parent::Arc Arc;
deba@468	698	typedef typename Parent::Edge Edge;
deba@468	699
deba@468	700	typedef _Graph Graph;
deba@468	701
deba@468	702
deba@468	703	typedef typename Parent::NodesImplBase NodesImplBase;
deba@468	704
deba@468	705	void eraseNode(const Node& node) {
deba@468	706	Arc arc;
deba@468	707	Parent::firstOut(arc, node);
deba@468	708	while (arc != INVALID ) {
deba@468	709	erase(arc);
deba@468	710	Parent::firstOut(arc, node);
deba@468	711	}
deba@468	712
deba@468	713	}
deba@468	714
deba@468	715	void clearNodes() {
deba@468	716	Parent::clear();
deba@468	717	}
deba@468	718
deba@468	719	class NodesImpl : public NodesImplBase {
deba@468	720	public:
deba@468	721	typedef NodesImplBase Parent;
deba@468	722
deba@468	723	NodesImpl(const Graph& graph, ListEdgeSet& arcset)
deba@468	724	: Parent(graph), _arcset(arcset) {}
deba@468	725
deba@468	726	virtual ~NodesImpl() {}
deba@468	727
deba@468	728	protected:
deba@468	729
deba@468	730	virtual void erase(const Node& node) {
deba@468	731	_arcset.eraseNode(node);
deba@468	732	Parent::erase(node);
deba@468	733	}
deba@468	734	virtual void erase(const std::vector<Node>& nodes) {
deba@468	735	for (int i = 0; i < int(nodes.size()); ++i) {
deba@468	736	_arcset.eraseNode(nodes[i]);
deba@468	737	}
deba@468	738	Parent::erase(nodes);
deba@468	739	}
deba@468	740	virtual void clear() {
deba@468	741	_arcset.clearNodes();
deba@468	742	Parent::clear();
deba@468	743	}
deba@468	744
deba@468	745	private:
deba@468	746	ListEdgeSet& _arcset;
deba@468	747	};
deba@468	748
deba@468	749	NodesImpl nodes;
deba@468	750
deba@468	751	public:
deba@468	752
deba@468	753	/// \brief Constructor of the EdgeSet.
deba@468	754	///
deba@468	755	/// Constructor of the EdgeSet.
deba@468	756	ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@468	757	Parent::initalize(graph, nodes);
deba@468	758	}
deba@468	759
deba@468	760	/// \brief Add a new edge to the graph.
deba@468	761	///
deba@468	762	/// Add a new edge to the graph with node \c u
deba@468	763	/// and node \c v endpoints.
deba@468	764	/// \return the new edge.
deba@468	765	Edge addEdge(const Node& u, const Node& v) {
deba@468	766	return Parent::addEdge(u, v);
deba@468	767	}
deba@468	768
deba@468	769	/// \brief Erase an edge from the graph.
deba@468	770	///
deba@468	771	/// Erase the edge \c e from the graph.
deba@468	772	void erase(const Edge& e) {
deba@468	773	return Parent::erase(e);
deba@468	774	}
deba@468	775
deba@468	776	};
deba@468	777
deba@468	778	template <typename _Graph>
deba@468	779	class SmartArcSetBase {
deba@468	780	public:
deba@468	781
deba@468	782	typedef _Graph Graph;
deba@468	783	typedef typename Graph::Node Node;
deba@468	784	typedef typename Graph::NodeIt NodeIt;
deba@468	785
deba@468	786	protected:
deba@468	787
deba@468	788	struct NodeT {
deba@468	789	int first_out, first_in;
deba@468	790	NodeT() : first_out(-1), first_in(-1) {}
deba@468	791	};
deba@468	792
deba@468	793	typedef typename ItemSetTraits<Graph, Node>::
deba@468	794	template Map<NodeT>::Type NodesImplBase;
deba@468	795
deba@468	796	NodesImplBase* nodes;
deba@468	797
deba@468	798	struct ArcT {
deba@468	799	Node source, target;
deba@468	800	int next_out, next_in;
deba@468	801	ArcT() {}
deba@468	802	};
deba@468	803
deba@468	804	std::vector<ArcT> arcs;
deba@468	805
deba@468	806	const Graph* graph;
deba@468	807
deba@468	808	void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@468	809	graph = &_graph;
deba@468	810	nodes = &_nodes;
deba@468	811	}
deba@468	812
deba@468	813	public:
deba@468	814
deba@468	815	class Arc {
deba@468	816	friend class SmartArcSetBase<Graph>;
deba@468	817	protected:
deba@468	818	Arc(int _id) : id(_id) {}
deba@468	819	int id;
deba@468	820	public:
deba@468	821	Arc() {}
deba@468	822	Arc(Invalid) : id(-1) {}
deba@468	823	bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468	824	bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468	825	bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468	826	};
deba@468	827
deba@468	828	SmartArcSetBase() {}
deba@468	829
deba@468	830	Arc addArc(const Node& u, const Node& v) {
deba@468	831	int n = arcs.size();
deba@468	832	arcs.push_back(ArcT());
deba@468	833	arcs[n].next_in = (*nodes)[v].first_in;
deba@468	834	(*nodes)[v].first_in = n;
deba@468	835	arcs[n].next_out = (*nodes)[u].first_out;
deba@468	836	(*nodes)[u].first_out = n;
deba@468	837	arcs[n].source = u;
deba@468	838	arcs[n].target = v;
deba@468	839	return Arc(n);
deba@468	840	}
deba@468	841
deba@468	842	void clear() {
deba@468	843	Node node;
deba@468	844	for (first(node); node != INVALID; next(node)) {
deba@468	845	(*nodes)[node].first_in = -1;
deba@468	846	(*nodes)[node].first_out = -1;
deba@468	847	}
deba@468	848	arcs.clear();
deba@468	849	}
deba@468	850
deba@468	851	void first(Node& node) const {
deba@468	852	graph->first(node);
deba@468	853	}
deba@468	854
deba@468	855	void next(Node& node) const {
deba@468	856	graph->next(node);
deba@468	857	}
deba@468	858
deba@468	859	void first(Arc& arc) const {
deba@468	860	arc.id = arcs.size() - 1;
deba@468	861	}
deba@468	862
deba@468	863	void next(Arc& arc) const {
deba@468	864	--arc.id;
deba@468	865	}
deba@468	866
deba@468	867	void firstOut(Arc& arc, const Node& node) const {
deba@468	868	arc.id = (*nodes)[node].first_out;
deba@468	869	}
deba@468	870
deba@468	871	void nextOut(Arc& arc) const {
deba@468	872	arc.id = arcs[arc.id].next_out;
deba@468	873	}
deba@468	874
deba@468	875	void firstIn(Arc& arc, const Node& node) const {
deba@468	876	arc.id = (*nodes)[node].first_in;
deba@468	877	}
deba@468	878
deba@468	879	void nextIn(Arc& arc) const {
deba@468	880	arc.id = arcs[arc.id].next_in;
deba@468	881	}
deba@468	882
deba@468	883	int id(const Node& node) const { return graph->id(node); }
deba@468	884	int id(const Arc& arc) const { return arc.id; }
deba@468	885
deba@468	886	Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
deba@468	887	Arc arcFromId(int ix) const { return Arc(ix); }
deba@468	888
deba@468	889	int maxNodeId() const { return graph->maxNodeId(); };
deba@468	890	int maxArcId() const { return arcs.size() - 1; }
deba@468	891
deba@468	892	Node source(const Arc& arc) const { return arcs[arc.id].source;}
deba@468	893	Node target(const Arc& arc) const { return arcs[arc.id].target;}
deba@468	894
deba@468	895	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@468	896
deba@468	897	NodeNotifier& notifier(Node) const {
deba@468	898	return graph->notifier(Node());
deba@468	899	}
deba@468	900
deba@468	901	template <typename _Value>
deba@468	902	class NodeMap : public Graph::template NodeMap<_Value> {
deba@468	903	public:
deba@468	904
deba@468	905	typedef typename _Graph::template NodeMap<_Value> Parent;
deba@468	906
deba@468	907	explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
deba@468	908	: Parent(*arcset.graph) { }
deba@468	909
deba@468	910	NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
deba@468	911	: Parent(*arcset.graph, value) { }
deba@468	912
deba@468	913	NodeMap& operator=(const NodeMap& cmap) {
deba@468	914	return operator=<NodeMap>(cmap);
deba@468	915	}
deba@468	916
deba@468	917	template <typename CMap>
deba@468	918	NodeMap& operator=(const CMap& cmap) {
deba@468	919	Parent::operator=(cmap);
deba@468	920	return *this;
deba@468	921	}
deba@468	922	};
deba@468	923
deba@468	924	};
deba@468	925
deba@468	926
deba@468	927	/// \ingroup semi_adaptors
deba@468	928	///
deba@468	929	/// \brief Digraph using a node set of another digraph or graph and
deba@468	930	/// an own arc set.
deba@468	931	///
deba@468	932	/// This structure can be used to establish another directed graph
deba@468	933	/// over a node set of an existing one. This class uses the same
deba@468	934	/// Node type as the underlying graph, and each valid node of the
deba@468	935	/// original graph is valid in this arc set, therefore the node
deba@468	936	/// objects of the original graph can be used directly with this
deba@468	937	/// class. The node handling functions (id handling, observing, and
deba@468	938	/// iterators) works equivalently as in the original graph.
deba@468	939	///
deba@468	940	/// \param _Graph The type of the graph which shares its node set with
deba@468	941	/// this class. Its interface must conform to the
deba@468	942	/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468	943	/// concept.
deba@468	944	///
deba@468	945	/// This implementation is slightly faster than the \c ListArcSet,
deba@468	946	/// because it uses continuous storage for arcs and it uses just
deba@468	947	/// single-linked lists for enumerate outgoing and incoming
deba@468	948	/// arcs. Therefore the arcs cannot be erased from the arc sets.
deba@468	949	///
deba@468	950	/// \warning If a node is erased from the underlying graph and this
deba@468	951	/// node is the source or target of one arc in the arc set, then
deba@468	952	/// the arc set is invalidated, and it cannot be used anymore. The
deba@468	953	/// validity can be checked with the \c valid() member function.
deba@468	954	///
deba@468	955	/// This class is fully conform to the \ref concepts::Digraph
deba@468	956	/// "Digraph" concept.
deba@468	957	template <typename _Graph>
deba@468	958	class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
deba@468	959
deba@468	960	public:
deba@468	961
deba@468	962	typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
deba@468	963
deba@468	964	typedef typename Parent::Node Node;
deba@468	965	typedef typename Parent::Arc Arc;
deba@468	966
deba@468	967	typedef _Graph Graph;
deba@468	968
deba@468	969	protected:
deba@468	970
deba@468	971	typedef typename Parent::NodesImplBase NodesImplBase;
deba@468	972
deba@468	973	void eraseNode(const Node& node) {
deba@468	974	if (typename Parent::InArcIt(*this, node) == INVALID &&
deba@468	975	typename Parent::OutArcIt(*this, node) == INVALID) {
deba@468	976	return;
deba@468	977	}
deba@468	978	throw typename NodesImplBase::Notifier::ImmediateDetach();
deba@468	979	}
deba@468	980
deba@468	981	void clearNodes() {
deba@468	982	Parent::clear();
deba@468	983	}
deba@468	984
deba@468	985	class NodesImpl : public NodesImplBase {
deba@468	986	public:
deba@468	987	typedef NodesImplBase Parent;
deba@468	988
deba@468	989	NodesImpl(const Graph& graph, SmartArcSet& arcset)
deba@468	990	: Parent(graph), _arcset(arcset) {}
deba@468	991
deba@468	992	virtual ~NodesImpl() {}
deba@468	993
deba@468	994	bool attached() const {
deba@468	995	return Parent::attached();
deba@468	996	}
deba@468	997
deba@468	998	protected:
deba@468	999
deba@468	1000	virtual void erase(const Node& node) {
deba@468	1001	try {
deba@468	1002	_arcset.eraseNode(node);
deba@468	1003	Parent::erase(node);
deba@468	1004	} catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468	1005	Parent::clear();
deba@468	1006	throw;
deba@468	1007	}
deba@468	1008	}
deba@468	1009	virtual void erase(const std::vector<Node>& nodes) {
deba@468	1010	try {
deba@468	1011	for (int i = 0; i < int(nodes.size()); ++i) {
deba@468	1012	_arcset.eraseNode(nodes[i]);
deba@468	1013	}
deba@468	1014	Parent::erase(nodes);
deba@468	1015	} catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468	1016	Parent::clear();
deba@468	1017	throw;
deba@468	1018	}
deba@468	1019	}
deba@468	1020	virtual void clear() {
deba@468	1021	_arcset.clearNodes();
deba@468	1022	Parent::clear();
deba@468	1023	}
deba@468	1024
deba@468	1025	private:
deba@468	1026	SmartArcSet& _arcset;
deba@468	1027	};
deba@468	1028
deba@468	1029	NodesImpl nodes;
deba@468	1030
deba@468	1031	public:
deba@468	1032
deba@468	1033	/// \brief Constructor of the ArcSet.
deba@468	1034	///
deba@468	1035	/// Constructor of the ArcSet.
deba@468	1036	SmartArcSet(const Graph& graph) : nodes(graph, *this) {
deba@468	1037	Parent::initalize(graph, nodes);
deba@468	1038	}
deba@468	1039
deba@468	1040	/// \brief Add a new arc to the digraph.
deba@468	1041	///
deba@468	1042	/// Add a new arc to the digraph with source node \c s
deba@468	1043	/// and target node \c t.
deba@468	1044	/// \return the new arc.
deba@468	1045	Arc addArc(const Node& s, const Node& t) {
deba@468	1046	return Parent::addArc(s, t);
deba@468	1047	}
deba@468	1048
deba@468	1049	/// \brief Validity check
deba@468	1050	///
deba@468	1051	/// This functions gives back false if the ArcSet is
deba@468	1052	/// invalidated. It occurs when a node in the underlying graph is
deba@468	1053	/// erased and it is not isolated in the ArcSet.
deba@468	1054	bool valid() const {
deba@468	1055	return nodes.attached();
deba@468	1056	}
deba@468	1057
deba@468	1058	};
deba@468	1059
deba@468	1060
deba@468	1061	template <typename _Graph>
deba@468	1062	class SmartEdgeSetBase {
deba@468	1063	public:
deba@468	1064
deba@468	1065	typedef _Graph Graph;
deba@468	1066	typedef typename Graph::Node Node;
deba@468	1067	typedef typename Graph::NodeIt NodeIt;
deba@468	1068
deba@468	1069	protected:
deba@468	1070
deba@468	1071	struct NodeT {
deba@468	1072	int first_out;
deba@468	1073	NodeT() : first_out(-1) {}
deba@468	1074	};
deba@468	1075
deba@468	1076	typedef typename ItemSetTraits<Graph, Node>::
deba@468	1077	template Map<NodeT>::Type NodesImplBase;
deba@468	1078
deba@468	1079	NodesImplBase* nodes;
deba@468	1080
deba@468	1081	struct ArcT {
deba@468	1082	Node target;
deba@468	1083	int next_out;
deba@468	1084	ArcT() {}
deba@468	1085	};
deba@468	1086
deba@468	1087	std::vector<ArcT> arcs;
deba@468	1088
deba@468	1089	const Graph* graph;
deba@468	1090
deba@468	1091	void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@468	1092	graph = &_graph;
deba@468	1093	nodes = &_nodes;
deba@468	1094	}
deba@468	1095
deba@468	1096	public:
deba@468	1097
deba@468	1098	class Edge {
deba@468	1099	friend class SmartEdgeSetBase;
deba@468	1100	protected:
deba@468	1101
deba@468	1102	int id;
deba@468	1103	explicit Edge(int _id) { id = _id;}
deba@468	1104
deba@468	1105	public:
deba@468	1106	Edge() {}
deba@468	1107	Edge (Invalid) { id = -1; }
deba@468	1108	bool operator==(const Edge& arc) const {return id == arc.id;}
deba@468	1109	bool operator!=(const Edge& arc) const {return id != arc.id;}
deba@468	1110	bool operator<(const Edge& arc) const {return id < arc.id;}
deba@468	1111	};
deba@468	1112
deba@468	1113	class Arc {
deba@468	1114	friend class SmartEdgeSetBase;
deba@468	1115	protected:
deba@468	1116	Arc(int _id) : id(_id) {}
deba@468	1117	int id;
deba@468	1118	public:
deba@468	1119	operator Edge() const { return edgeFromId(id / 2); }
deba@468	1120
deba@468	1121	Arc() {}
deba@468	1122	Arc(Invalid) : id(-1) {}
deba@468	1123	bool operator==(const Arc& arc) const { return id == arc.id; }
deba@468	1124	bool operator!=(const Arc& arc) const { return id != arc.id; }
deba@468	1125	bool operator<(const Arc& arc) const { return id < arc.id; }
deba@468	1126	};
deba@468	1127
deba@468	1128	SmartEdgeSetBase() {}
deba@468	1129
deba@468	1130	Edge addEdge(const Node& u, const Node& v) {
deba@468	1131	int n = arcs.size();
deba@468	1132	arcs.push_back(ArcT());
deba@468	1133	arcs.push_back(ArcT());
deba@468	1134
deba@468	1135	arcs[n].target = u;
deba@468	1136	arcs[n \| 1].target = v;
deba@468	1137
deba@468	1138	arcs[n].next_out = (*nodes)[v].first_out;
deba@468	1139	(*nodes)[v].first_out = n;
deba@468	1140
deba@468	1141	arcs[n \| 1].next_out = (*nodes)[u].first_out;
deba@468	1142	(*nodes)[u].first_out = (n \| 1);
deba@468	1143
deba@468	1144	return Edge(n / 2);
deba@468	1145	}
deba@468	1146
deba@468	1147	void clear() {
deba@468	1148	Node node;
deba@468	1149	for (first(node); node != INVALID; next(node)) {
deba@468	1150	(*nodes)[node].first_out = -1;
deba@468	1151	}
deba@468	1152	arcs.clear();
deba@468	1153	}
deba@468	1154
deba@468	1155	void first(Node& node) const {
deba@468	1156	graph->first(node);
deba@468	1157	}
deba@468	1158
deba@468	1159	void next(Node& node) const {
deba@468	1160	graph->next(node);
deba@468	1161	}
deba@468	1162
deba@468	1163	void first(Arc& arc) const {
deba@468	1164	arc.id = arcs.size() - 1;
deba@468	1165	}
deba@468	1166
deba@468	1167	void next(Arc& arc) const {
deba@468	1168	--arc.id;
deba@468	1169	}
deba@468	1170
deba@468	1171	void first(Edge& arc) const {
deba@468	1172	arc.id = arcs.size() / 2 - 1;
deba@468	1173	}
deba@468	1174
deba@468	1175	void next(Edge& arc) const {
deba@468	1176	--arc.id;
deba@468	1177	}
deba@468	1178
deba@468	1179	void firstOut(Arc& arc, const Node& node) const {
deba@468	1180	arc.id = (*nodes)[node].first_out;
deba@468	1181	}
deba@468	1182
deba@468	1183	void nextOut(Arc& arc) const {
deba@468	1184	arc.id = arcs[arc.id].next_out;
deba@468	1185	}
deba@468	1186
deba@468	1187	void firstIn(Arc& arc, const Node& node) const {
deba@468	1188	arc.id = (((*nodes)[node].first_out) ^ 1);
deba@468	1189	if (arc.id == -2) arc.id = -1;
deba@468	1190	}
deba@468	1191
deba@468	1192	void nextIn(Arc& arc) const {
deba@468	1193	arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
deba@468	1194	if (arc.id == -2) arc.id = -1;
deba@468	1195	}
deba@468	1196
deba@468	1197	void firstInc(Edge &arc, bool& dir, const Node& node) const {
deba@468	1198	int de = (*nodes)[node].first_out;
deba@468	1199	if (de != -1 ) {
deba@468	1200	arc.id = de / 2;
deba@468	1201	dir = ((de & 1) == 1);
deba@468	1202	} else {
deba@468	1203	arc.id = -1;
deba@468	1204	dir = true;
deba@468	1205	}
deba@468	1206	}
deba@468	1207	void nextInc(Edge &arc, bool& dir) const {
deba@468	1208	int de = (arcs[(arc.id * 2) \| (dir ? 1 : 0)].next_out);
deba@468	1209	if (de != -1 ) {
deba@468	1210	arc.id = de / 2;
deba@468	1211	dir = ((de & 1) == 1);
deba@468	1212	} else {
deba@468	1213	arc.id = -1;
deba@468	1214	dir = true;
deba@468	1215	}
deba@468	1216	}
deba@468	1217
deba@468	1218	static bool direction(Arc arc) {
deba@468	1219	return (arc.id & 1) == 1;
deba@468	1220	}
deba@468	1221
deba@468	1222	static Arc direct(Edge edge, bool dir) {
deba@468	1223	return Arc(edge.id * 2 + (dir ? 1 : 0));
deba@468	1224	}
deba@468	1225
deba@468	1226	int id(Node node) const { return graph->id(node); }
deba@468	1227	static int id(Arc arc) { return arc.id; }
deba@468	1228	static int id(Edge arc) { return arc.id; }
deba@468	1229
deba@468	1230	Node nodeFromId(int id) const { return graph->nodeFromId(id); }
deba@468	1231	static Arc arcFromId(int id) { return Arc(id); }
deba@468	1232	static Edge edgeFromId(int id) { return Edge(id);}
deba@468	1233
deba@468	1234	int maxNodeId() const { return graph->maxNodeId(); };
deba@468	1235	int maxArcId() const { return arcs.size() - 1; }
deba@468	1236	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@468	1237
deba@468	1238	Node source(Arc e) const { return arcs[e.id ^ 1].target; }
deba@468	1239	Node target(Arc e) const { return arcs[e.id].target; }
deba@468	1240
deba@468	1241	Node u(Edge e) const { return arcs[2 * e.id].target; }
deba@468	1242	Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
deba@468	1243
deba@468	1244	typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@468	1245
deba@468	1246	NodeNotifier& notifier(Node) const {
deba@468	1247	return graph->notifier(Node());
deba@468	1248	}
deba@468	1249
deba@468	1250	template <typename _Value>
deba@468	1251	class NodeMap : public Graph::template NodeMap<_Value> {
deba@468	1252	public:
deba@468	1253
deba@468	1254	typedef typename _Graph::template NodeMap<_Value> Parent;
deba@468	1255
deba@468	1256	explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
deba@468	1257	: Parent(*arcset.graph) { }
deba@468	1258
deba@468	1259	NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
deba@468	1260	: Parent(*arcset.graph, value) { }
deba@468	1261
deba@468	1262	NodeMap& operator=(const NodeMap& cmap) {
deba@468	1263	return operator=<NodeMap>(cmap);
deba@468	1264	}
deba@468	1265
deba@468	1266	template <typename CMap>
deba@468	1267	NodeMap& operator=(const CMap& cmap) {
deba@468	1268	Parent::operator=(cmap);
deba@468	1269	return *this;
deba@468	1270	}
deba@468	1271	};
deba@468	1272
deba@468	1273	};
deba@468	1274
deba@468	1275	/// \ingroup semi_adaptors
deba@468	1276	///
deba@468	1277	/// \brief Graph using a node set of another digraph or graph and an
deba@468	1278	/// own edge set.
deba@468	1279	///
deba@468	1280	/// This structure can be used to establish another graph over a
deba@468	1281	/// node set of an existing one. This class uses the same Node type
deba@468	1282	/// as the underlying graph, and each valid node of the original
deba@468	1283	/// graph is valid in this arc set, therefore the node objects of
deba@468	1284	/// the original graph can be used directly with this class. The
deba@468	1285	/// node handling functions (id handling, observing, and iterators)
deba@468	1286	/// works equivalently as in the original graph.
deba@468	1287	///
deba@468	1288	/// \param _Graph The type of the graph which shares its node set
deba@468	1289	/// with this class. Its interface must conform to the
deba@468	1290	/// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
deba@468	1291	/// concept.
deba@468	1292	///
deba@468	1293	/// This implementation is slightly faster than the \c ListEdgeSet,
deba@468	1294	/// because it uses continuous storage for edges and it uses just
deba@468	1295	/// single-linked lists for enumerate incident edges. Therefore the
deba@468	1296	/// edges cannot be erased from the edge sets.
deba@468	1297	///
deba@468	1298	/// \warning If a node is erased from the underlying graph and this
deba@468	1299	/// node is incident to one edge in the edge set, then the edge set
deba@468	1300	/// is invalidated, and it cannot be used anymore. The validity can
deba@468	1301	/// be checked with the \c valid() member function.
deba@468	1302	///
deba@468	1303	/// This class is fully conform to the \ref concepts::Graph
deba@468	1304	/// "Graph" concept.
deba@468	1305	template <typename _Graph>
deba@468	1306	class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
deba@468	1307
deba@468	1308	public:
deba@468	1309
deba@468	1310	typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
deba@468	1311
deba@468	1312	typedef typename Parent::Node Node;
deba@468	1313	typedef typename Parent::Arc Arc;
deba@468	1314	typedef typename Parent::Edge Edge;
deba@468	1315
deba@468	1316	typedef _Graph Graph;
deba@468	1317
deba@468	1318	protected:
deba@468	1319
deba@468	1320	typedef typename Parent::NodesImplBase NodesImplBase;
deba@468	1321
deba@468	1322	void eraseNode(const Node& node) {
deba@468	1323	if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
deba@468	1324	return;
deba@468	1325	}
deba@468	1326	throw typename NodesImplBase::Notifier::ImmediateDetach();
deba@468	1327	}
deba@468	1328
deba@468	1329	void clearNodes() {
deba@468	1330	Parent::clear();
deba@468	1331	}
deba@468	1332
deba@468	1333	class NodesImpl : public NodesImplBase {
deba@468	1334	public:
deba@468	1335	typedef NodesImplBase Parent;
deba@468	1336
deba@468	1337	NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
deba@468	1338	: Parent(graph), _arcset(arcset) {}
deba@468	1339
deba@468	1340	virtual ~NodesImpl() {}
deba@468	1341
deba@468	1342	bool attached() const {
deba@468	1343	return Parent::attached();
deba@468	1344	}
deba@468	1345
deba@468	1346	protected:
deba@468	1347
deba@468	1348	virtual void erase(const Node& node) {
deba@468	1349	try {
deba@468	1350	_arcset.eraseNode(node);
deba@468	1351	Parent::erase(node);
deba@468	1352	} catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468	1353	Parent::clear();
deba@468	1354	throw;
deba@468	1355	}
deba@468	1356	}
deba@468	1357	virtual void erase(const std::vector<Node>& nodes) {
deba@468	1358	try {
deba@468	1359	for (int i = 0; i < int(nodes.size()); ++i) {
deba@468	1360	_arcset.eraseNode(nodes[i]);
deba@468	1361	}
deba@468	1362	Parent::erase(nodes);
deba@468	1363	} catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@468	1364	Parent::clear();
deba@468	1365	throw;
deba@468	1366	}
deba@468	1367	}
deba@468	1368	virtual void clear() {
deba@468	1369	_arcset.clearNodes();
deba@468	1370	Parent::clear();
deba@468	1371	}
deba@468	1372
deba@468	1373	private:
deba@468	1374	SmartEdgeSet& _arcset;
deba@468	1375	};
deba@468	1376
deba@468	1377	NodesImpl nodes;
deba@468	1378
deba@468	1379	public:
deba@468	1380
deba@468	1381	/// \brief Constructor of the EdgeSet.
deba@468	1382	///
deba@468	1383	/// Constructor of the EdgeSet.
deba@468	1384	SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@468	1385	Parent::initalize(graph, nodes);
deba@468	1386	}
deba@468	1387
deba@468	1388	/// \brief Add a new edge to the graph.
deba@468	1389	///
deba@468	1390	/// Add a new edge to the graph with node \c u
deba@468	1391	/// and node \c v endpoints.
deba@468	1392	/// \return the new edge.
deba@468	1393	Edge addEdge(const Node& u, const Node& v) {
deba@468	1394	return Parent::addEdge(u, v);
deba@468	1395	}
deba@468	1396
deba@468	1397	/// \brief Validity check
deba@468	1398	///
deba@468	1399	/// This functions gives back false if the EdgeSet is
deba@468	1400	/// invalidated. It occurs when a node in the underlying graph is
deba@468	1401	/// erased and it is not isolated in the EdgeSet.
deba@468	1402	bool valid() const {
deba@468	1403	return nodes.attached();
deba@468	1404	}
deba@468	1405
deba@468	1406	};
deba@468	1407
deba@468	1408	}
deba@468	1409
deba@468	1410	#endif

author	Balazs Dezso <deba@inf.elte.hu>
	Sun, 18 Jan 2009 17:49:08 +0100
changeset 471	fb5af0411793
child 512	9b9ffe7d9b75
permissions	-rw-r--r--