lemon: lemon/list_graph.h@1bafdbd2fc46 (annotated)

alpar@209	1	/* -- mode: C++; indent-tabs-mode: nil; --
alpar@39	2	*
alpar@209	3	* This file is a part of LEMON, a generic C++ optimization library.
alpar@39	4	*
alpar@956	5	* Copyright (C) 2003-2010
alpar@39	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@39	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@39	8	*
alpar@39	9	* Permission to use, modify and distribute this software is granted
alpar@39	10	* provided that this copyright notice appears in all copies. For
alpar@39	11	* precise terms see the accompanying LICENSE file.
alpar@39	12	*
alpar@39	13	* This software is provided "AS IS" with no warranty of any kind,
alpar@39	14	* express or implied, and with no claim as to its suitability for any
alpar@39	15	* purpose.
alpar@39	16	*
alpar@39	17	*/
alpar@39	18
deba@57	19	#ifndef LEMON_LIST_GRAPH_H
deba@57	20	#define LEMON_LIST_GRAPH_H
deba@57	21
deba@57	22	///\ingroup graphs
deba@57	23	///\file
kpeter@782	24	///\brief ListDigraph and ListGraph classes.
deba@57	25
deba@220	26	#include <lemon/core.h>
deba@220	27	#include <lemon/error.h>
deba@57	28	#include <lemon/bits/graph_extender.h>
deba@57	29
deba@57	30	#include <vector>
deba@57	31	#include <list>
deba@57	32
deba@57	33	namespace lemon {
deba@57	34
kpeter@785	35	class ListDigraph;
kpeter@785	36
deba@57	37	class ListDigraphBase {
deba@57	38
deba@57	39	protected:
deba@57	40	struct NodeT {
deba@57	41	int first_in, first_out;
deba@57	42	int prev, next;
deba@57	43	};
alpar@209	44
deba@57	45	struct ArcT {
deba@57	46	int target, source;
deba@57	47	int prev_in, prev_out;
deba@57	48	int next_in, next_out;
deba@57	49	};
deba@57	50
deba@57	51	std::vector<NodeT> nodes;
deba@57	52
deba@57	53	int first_node;
deba@57	54
deba@57	55	int first_free_node;
deba@57	56
deba@57	57	std::vector<ArcT> arcs;
deba@57	58
deba@57	59	int first_free_arc;
alpar@209	60
deba@57	61	public:
alpar@209	62
deba@57	63	typedef ListDigraphBase Digraph;
alpar@209	64
deba@57	65	class Node {
deba@57	66	friend class ListDigraphBase;
kpeter@785	67	friend class ListDigraph;
deba@57	68	protected:
deba@57	69
deba@57	70	int id;
deba@57	71	explicit Node(int pid) { id = pid;}
deba@57	72
deba@57	73	public:
deba@57	74	Node() {}
deba@57	75	Node (Invalid) { id = -1; }
deba@57	76	bool operator==(const Node& node) const {return id == node.id;}
deba@57	77	bool operator!=(const Node& node) const {return id != node.id;}
deba@57	78	bool operator<(const Node& node) const {return id < node.id;}
deba@57	79	};
deba@57	80
deba@57	81	class Arc {
deba@57	82	friend class ListDigraphBase;
kpeter@785	83	friend class ListDigraph;
deba@57	84	protected:
deba@57	85
deba@57	86	int id;
deba@57	87	explicit Arc(int pid) { id = pid;}
deba@57	88
deba@57	89	public:
deba@57	90	Arc() {}
deba@57	91	Arc (Invalid) { id = -1; }
deba@57	92	bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57	93	bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57	94	bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57	95	};
deba@57	96
deba@57	97
deba@57	98
deba@57	99	ListDigraphBase()
deba@57	100	: nodes(), first_node(-1),
alpar@209	101	first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57	102
alpar@209	103
alpar@209	104	int maxNodeId() const { return nodes.size()-1; }
deba@57	105	int maxArcId() const { return arcs.size()-1; }
deba@57	106
deba@57	107	Node source(Arc e) const { return Node(arcs[e.id].source); }
deba@57	108	Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57	109
deba@57	110
alpar@209	111	void first(Node& node) const {
deba@57	112	node.id = first_node;
deba@57	113	}
deba@57	114
deba@57	115	void next(Node& node) const {
deba@57	116	node.id = nodes[node.id].next;
deba@57	117	}
deba@57	118
deba@57	119
alpar@209	120	void first(Arc& arc) const {
deba@57	121	int n;
alpar@209	122	for(n = first_node;
kpeter@786	123	n != -1 && nodes[n].first_out == -1;
alpar@209	124	n = nodes[n].next) {}
kpeter@786	125	arc.id = (n == -1) ? -1 : nodes[n].first_out;
deba@57	126	}
deba@57	127
deba@57	128	void next(Arc& arc) const {
kpeter@786	129	if (arcs[arc.id].next_out != -1) {
kpeter@786	130	arc.id = arcs[arc.id].next_out;
deba@57	131	} else {
alpar@209	132	int n;
kpeter@786	133	for(n = nodes[arcs[arc.id].source].next;
kpeter@786	134	n != -1 && nodes[n].first_out == -1;
alpar@209	135	n = nodes[n].next) {}
kpeter@786	136	arc.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@209	137	}
deba@57	138	}
deba@57	139
deba@57	140	void firstOut(Arc &e, const Node& v) const {
deba@57	141	e.id = nodes[v.id].first_out;
deba@57	142	}
deba@57	143	void nextOut(Arc &e) const {
deba@57	144	e.id=arcs[e.id].next_out;
deba@57	145	}
deba@57	146
deba@57	147	void firstIn(Arc &e, const Node& v) const {
deba@57	148	e.id = nodes[v.id].first_in;
deba@57	149	}
deba@57	150	void nextIn(Arc &e) const {
deba@57	151	e.id=arcs[e.id].next_in;
deba@57	152	}
deba@57	153
alpar@209	154
deba@57	155	static int id(Node v) { return v.id; }
deba@57	156	static int id(Arc e) { return e.id; }
deba@57	157
deba@57	158	static Node nodeFromId(int id) { return Node(id);}
deba@57	159	static Arc arcFromId(int id) { return Arc(id);}
deba@57	160
alpar@209	161	bool valid(Node n) const {
alpar@209	162	return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209	163	nodes[n.id].prev != -2;
deba@149	164	}
deba@149	165
alpar@209	166	bool valid(Arc a) const {
alpar@209	167	return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209	168	arcs[a.id].prev_in != -2;
deba@149	169	}
deba@149	170
alpar@209	171	Node addNode() {
deba@57	172	int n;
alpar@209	173
deba@57	174	if(first_free_node==-1) {
alpar@209	175	n = nodes.size();
alpar@209	176	nodes.push_back(NodeT());
deba@57	177	} else {
alpar@209	178	n = first_free_node;
alpar@209	179	first_free_node = nodes[n].next;
deba@57	180	}
alpar@209	181
deba@57	182	nodes[n].next = first_node;
deba@57	183	if(first_node != -1) nodes[first_node].prev = n;
deba@57	184	first_node = n;
deba@57	185	nodes[n].prev = -1;
alpar@209	186
deba@57	187	nodes[n].first_in = nodes[n].first_out = -1;
alpar@209	188
deba@57	189	return Node(n);
deba@57	190	}
alpar@209	191
deba@57	192	Arc addArc(Node u, Node v) {
alpar@209	193	int n;
deba@57	194
deba@57	195	if (first_free_arc == -1) {
alpar@209	196	n = arcs.size();
alpar@209	197	arcs.push_back(ArcT());
deba@57	198	} else {
alpar@209	199	n = first_free_arc;
alpar@209	200	first_free_arc = arcs[n].next_in;
deba@57	201	}
alpar@209	202
alpar@209	203	arcs[n].source = u.id;
deba@57	204	arcs[n].target = v.id;
deba@57	205
deba@57	206	arcs[n].next_out = nodes[u.id].first_out;
deba@57	207	if(nodes[u.id].first_out != -1) {
alpar@209	208	arcs[nodes[u.id].first_out].prev_out = n;
deba@57	209	}
alpar@209	210
deba@57	211	arcs[n].next_in = nodes[v.id].first_in;
deba@57	212	if(nodes[v.id].first_in != -1) {
alpar@209	213	arcs[nodes[v.id].first_in].prev_in = n;
deba@57	214	}
alpar@209	215
deba@57	216	arcs[n].prev_in = arcs[n].prev_out = -1;
alpar@209	217
deba@57	218	nodes[u.id].first_out = nodes[v.id].first_in = n;
deba@57	219
deba@57	220	return Arc(n);
deba@57	221	}
alpar@209	222
deba@57	223	void erase(const Node& node) {
deba@57	224	int n = node.id;
alpar@209	225
deba@57	226	if(nodes[n].next != -1) {
alpar@209	227	nodes[nodes[n].next].prev = nodes[n].prev;
deba@57	228	}
alpar@209	229
deba@57	230	if(nodes[n].prev != -1) {
alpar@209	231	nodes[nodes[n].prev].next = nodes[n].next;
deba@57	232	} else {
alpar@209	233	first_node = nodes[n].next;
deba@57	234	}
alpar@209	235
deba@57	236	nodes[n].next = first_free_node;
deba@57	237	first_free_node = n;
deba@149	238	nodes[n].prev = -2;
deba@57	239
deba@57	240	}
alpar@209	241
deba@57	242	void erase(const Arc& arc) {
deba@57	243	int n = arc.id;
alpar@209	244
deba@57	245	if(arcs[n].next_in!=-1) {
alpar@209	246	arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
deba@57	247	}
deba@57	248
deba@57	249	if(arcs[n].prev_in!=-1) {
alpar@209	250	arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
deba@57	251	} else {
alpar@209	252	nodes[arcs[n].target].first_in = arcs[n].next_in;
deba@57	253	}
deba@57	254
alpar@209	255
deba@57	256	if(arcs[n].next_out!=-1) {
alpar@209	257	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209	258	}
deba@57	259
deba@57	260	if(arcs[n].prev_out!=-1) {
alpar@209	261	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57	262	} else {
alpar@209	263	nodes[arcs[n].source].first_out = arcs[n].next_out;
deba@57	264	}
alpar@209	265
deba@57	266	arcs[n].next_in = first_free_arc;
deba@149	267	first_free_arc = n;
deba@149	268	arcs[n].prev_in = -2;
deba@57	269	}
deba@57	270
deba@57	271	void clear() {
deba@57	272	arcs.clear();
deba@57	273	nodes.clear();
deba@57	274	first_node = first_free_node = first_free_arc = -1;
deba@57	275	}
deba@57	276
deba@57	277	protected:
alpar@209	278	void changeTarget(Arc e, Node n)
deba@57	279	{
deba@57	280	if(arcs[e.id].next_in != -1)
alpar@209	281	arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
deba@57	282	if(arcs[e.id].prev_in != -1)
alpar@209	283	arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
deba@57	284	else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
deba@57	285	if (nodes[n.id].first_in != -1) {
alpar@209	286	arcs[nodes[n.id].first_in].prev_in = e.id;
deba@57	287	}
deba@57	288	arcs[e.id].target = n.id;
deba@57	289	arcs[e.id].prev_in = -1;
deba@57	290	arcs[e.id].next_in = nodes[n.id].first_in;
deba@57	291	nodes[n.id].first_in = e.id;
deba@57	292	}
alpar@209	293	void changeSource(Arc e, Node n)
deba@57	294	{
deba@57	295	if(arcs[e.id].next_out != -1)
alpar@209	296	arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
deba@57	297	if(arcs[e.id].prev_out != -1)
alpar@209	298	arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
deba@57	299	else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
deba@57	300	if (nodes[n.id].first_out != -1) {
alpar@209	301	arcs[nodes[n.id].first_out].prev_out = e.id;
deba@57	302	}
deba@57	303	arcs[e.id].source = n.id;
deba@57	304	arcs[e.id].prev_out = -1;
deba@57	305	arcs[e.id].next_out = nodes[n.id].first_out;
deba@57	306	nodes[n.id].first_out = e.id;
deba@57	307	}
deba@57	308
deba@57	309	};
deba@57	310
deba@57	311	typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
deba@57	312
kpeter@73	313	/// \addtogroup graphs
deba@57	314	/// @{
deba@57	315
alpar@209	316	///A general directed graph structure.
deba@57	317
kpeter@782	318	///\ref ListDigraph is a versatile and fast directed graph
kpeter@782	319	///implementation based on linked lists that are stored in
alpar@209	320	///\c std::vector structures.
deba@57	321	///
kpeter@782	322	///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
kpeter@782	323	///and it also provides several useful additional functionalities.
kpeter@782	324	///Most of its member functions and nested classes are documented
kpeter@73	325	///only in the concept class.
deba@57	326	///
kpeter@834	327	///This class provides only linear time counting for nodes and arcs.
kpeter@834	328	///
kpeter@73	329	///\sa concepts::Digraph
kpeter@782	330	///\sa ListGraph
deba@57	331	class ListDigraph : public ExtendedListDigraphBase {
kpeter@664	332	typedef ExtendedListDigraphBase Parent;
kpeter@664	333
deba@57	334	private:
kpeter@782	335	/// Digraphs are \e not copy constructible. Use DigraphCopy instead.
deba@57	336	ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
kpeter@782	337	/// \brief Assignment of a digraph to another one is \e not allowed.
kpeter@782	338	/// Use DigraphCopy instead.
deba@57	339	void operator=(const ListDigraph &) {}
deba@57	340	public:
deba@57	341
deba@57	342	/// Constructor
alpar@209	343
deba@57	344	/// Constructor.
deba@57	345	///
deba@57	346	ListDigraph() {}
deba@57	347
deba@57	348	///Add a new node to the digraph.
alpar@209	349
kpeter@782	350	///This function adds a new node to the digraph.
kpeter@606	351	///\return The new node.
deba@57	352	Node addNode() { return Parent::addNode(); }
deba@57	353
deba@57	354	///Add a new arc to the digraph.
alpar@209	355
kpeter@782	356	///This function adds a new arc to the digraph with source node \c s
deba@57	357	///and target node \c t.
kpeter@606	358	///\return The new arc.
kpeter@782	359	Arc addArc(Node s, Node t) {
alpar@209	360	return Parent::addArc(s, t);
deba@57	361	}
deba@57	362
deba@234	363	///\brief Erase a node from the digraph.
deba@234	364	///
kpeter@834	365	///This function erases the given node along with its outgoing and
kpeter@834	366	///incoming arcs from the digraph.
kpeter@834	367	///
kpeter@834	368	///\note All iterators referencing the removed node or the connected
kpeter@834	369	///arcs are invalidated, of course.
kpeter@782	370	void erase(Node n) { Parent::erase(n); }
deba@234	371
deba@234	372	///\brief Erase an arc from the digraph.
deba@234	373	///
kpeter@782	374	///This function erases the given arc from the digraph.
kpeter@834	375	///
kpeter@834	376	///\note All iterators referencing the removed arc are invalidated,
kpeter@834	377	///of course.
kpeter@782	378	void erase(Arc a) { Parent::erase(a); }
deba@234	379
deba@149	380	/// Node validity check
deba@149	381
kpeter@782	382	/// This function gives back \c true if the given node is valid,
kpeter@782	383	/// i.e. it is a real node of the digraph.
deba@149	384	///
kpeter@782	385	/// \warning A removed node could become valid again if new nodes are
kpeter@782	386	/// added to the digraph.
deba@149	387	bool valid(Node n) const { return Parent::valid(n); }
deba@149	388
deba@149	389	/// Arc validity check
deba@149	390
kpeter@782	391	/// This function gives back \c true if the given arc is valid,
kpeter@782	392	/// i.e. it is a real arc of the digraph.
deba@149	393	///
kpeter@782	394	/// \warning A removed arc could become valid again if new arcs are
kpeter@782	395	/// added to the digraph.
deba@149	396	bool valid(Arc a) const { return Parent::valid(a); }
deba@149	397
kpeter@782	398	/// Change the target node of an arc
deba@57	399
kpeter@782	400	/// This function changes the target node of the given arc \c a to \c n.
deba@57	401	///
kpeter@782	402	///\note \c ArcIt and \c OutArcIt iterators referencing the changed
kpeter@833	403	///arc remain valid, but \c InArcIt iterators are invalidated.
kpeter@73	404	///
deba@57	405	///\warning This functionality cannot be used together with the Snapshot
deba@57	406	///feature.
deba@235	407	void changeTarget(Arc a, Node n) {
deba@235	408	Parent::changeTarget(a,n);
deba@57	409	}
kpeter@782	410	/// Change the source node of an arc
deba@57	411
kpeter@782	412	/// This function changes the source node of the given arc \c a to \c n.
deba@57	413	///
kpeter@782	414	///\note \c InArcIt iterators referencing the changed arc remain
kpeter@833	415	///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
kpeter@73	416	///
deba@57	417	///\warning This functionality cannot be used together with the Snapshot
deba@57	418	///feature.
deba@235	419	void changeSource(Arc a, Node n) {
deba@235	420	Parent::changeSource(a,n);
deba@57	421	}
deba@57	422
kpeter@782	423	/// Reverse the direction of an arc.
deba@57	424
kpeter@782	425	/// This function reverses the direction of the given arc.
kpeter@782	426	///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
kpeter@782	427	///the changed arc are invalidated.
kpeter@73	428	///
deba@57	429	///\warning This functionality cannot be used together with the Snapshot
deba@57	430	///feature.
kpeter@782	431	void reverseArc(Arc a) {
kpeter@782	432	Node t=target(a);
kpeter@782	433	changeTarget(a,source(a));
kpeter@782	434	changeSource(a,t);
deba@57	435	}
deba@57	436
deba@57	437	///Contract two nodes.
deba@57	438
kpeter@782	439	///This function contracts the given two nodes.
kpeter@782	440	///Node \c v is removed, but instead of deleting its
kpeter@782	441	///incident arcs, they are joined to node \c u.
kpeter@782	442	///If the last parameter \c r is \c true (this is the default value),
kpeter@782	443	///then the newly created loops are removed.
deba@57	444	///
kpeter@782	445	///\note The moved arcs are joined to node \c u using changeSource()
kpeter@782	446	///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
kpeter@782	447	///invalidated for the outgoing arcs of node \c v and \c InArcIt
kpeter@782	448	///iterators are invalidated for the incomming arcs of \c v.
alpar@956	449	///Moreover all iterators referencing node \c v or the removed
kpeter@782	450	///loops are also invalidated. Other iterators remain valid.
kpeter@73	451	///
deba@57	452	///\warning This functionality cannot be used together with the Snapshot
deba@57	453	///feature.
kpeter@782	454	void contract(Node u, Node v, bool r = true)
deba@57	455	{
kpeter@782	456	for(OutArcIt e(*this,v);e!=INVALID;) {
alpar@209	457	OutArcIt f=e;
alpar@209	458	++f;
kpeter@782	459	if(r && target(e)==u) erase(e);
kpeter@782	460	else changeSource(e,u);
alpar@209	461	e=f;
deba@57	462	}
kpeter@782	463	for(InArcIt e(*this,v);e!=INVALID;) {
alpar@209	464	InArcIt f=e;
alpar@209	465	++f;
kpeter@782	466	if(r && source(e)==u) erase(e);
kpeter@782	467	else changeTarget(e,u);
alpar@209	468	e=f;
deba@57	469	}
kpeter@782	470	erase(v);
deba@57	471	}
deba@57	472
deba@57	473	///Split a node.
deba@57	474
kpeter@782	475	///This function splits the given node. First, a new node is added
kpeter@782	476	///to the digraph, then the source of each outgoing arc of node \c n
kpeter@782	477	///is moved to this new node.
kpeter@782	478	///If the second parameter \c connect is \c true (this is the default
kpeter@782	479	///value), then a new arc from node \c n to the newly created node
kpeter@782	480	///is also added.
deba@57	481	///\return The newly created node.
deba@57	482	///
kpeter@785	483	///\note All iterators remain valid.
deba@57	484	///
kpeter@782	485	///\warning This functionality cannot be used together with the
kpeter@73	486	///Snapshot feature.
deba@57	487	Node split(Node n, bool connect = true) {
deba@57	488	Node b = addNode();
kpeter@785	489	nodes[b.id].first_out=nodes[n.id].first_out;
kpeter@785	490	nodes[n.id].first_out=-1;
kpeter@785	491	for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
kpeter@785	492	arcs[i].source=b.id;
deba@57	493	}
deba@57	494	if (connect) addArc(n,b);
deba@57	495	return b;
deba@57	496	}
alpar@209	497
deba@57	498	///Split an arc.
deba@57	499
kpeter@782	500	///This function splits the given arc. First, a new node \c v is
kpeter@782	501	///added to the digraph, then the target node of the original arc
kpeter@782	502	///is set to \c v. Finally, an arc from \c v to the original target
kpeter@782	503	///is added.
kpeter@782	504	///\return The newly created node.
kpeter@73	505	///
kpeter@782	506	///\note \c InArcIt iterators referencing the original arc are
kpeter@782	507	///invalidated. Other iterators remain valid.
kpeter@73	508	///
kpeter@73	509	///\warning This functionality cannot be used together with the
kpeter@73	510	///Snapshot feature.
kpeter@782	511	Node split(Arc a) {
kpeter@782	512	Node v = addNode();
kpeter@782	513	addArc(v,target(a));
kpeter@782	514	changeTarget(a,v);
kpeter@782	515	return v;
deba@57	516	}
alpar@209	517
kpeter@782	518	///Clear the digraph.
kpeter@782	519
kpeter@782	520	///This function erases all nodes and arcs from the digraph.
kpeter@782	521	///
kpeter@834	522	///\note All iterators of the digraph are invalidated, of course.
kpeter@782	523	void clear() {
kpeter@782	524	Parent::clear();
kpeter@782	525	}
kpeter@782	526
kpeter@782	527	/// Reserve memory for nodes.
kpeter@782	528
kpeter@782	529	/// Using this function, it is possible to avoid superfluous memory
kpeter@782	530	/// allocation: if you know that the digraph you want to build will
kpeter@782	531	/// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@782	532	/// then it is worth reserving space for this amount before starting
kpeter@782	533	/// to build the digraph.
kpeter@782	534	/// \sa reserveArc()
kpeter@782	535	void reserveNode(int n) { nodes.reserve(n); };
kpeter@782	536
kpeter@782	537	/// Reserve memory for arcs.
kpeter@782	538
kpeter@782	539	/// Using this function, it is possible to avoid superfluous memory
kpeter@782	540	/// allocation: if you know that the digraph you want to build will
kpeter@782	541	/// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@782	542	/// then it is worth reserving space for this amount before starting
kpeter@782	543	/// to build the digraph.
kpeter@782	544	/// \sa reserveNode()
kpeter@782	545	void reserveArc(int m) { arcs.reserve(m); };
kpeter@782	546
deba@57	547	/// \brief Class to make a snapshot of the digraph and restore
kpeter@73	548	/// it later.
deba@57	549	///
kpeter@73	550	/// Class to make a snapshot of the digraph and restore it later.
deba@57	551	///
deba@57	552	/// The newly added nodes and arcs can be removed using the
deba@57	553	/// restore() function.
deba@57	554	///
alpar@956	555	/// \note After a state is restored, you cannot restore a later state,
kpeter@782	556	/// i.e. you cannot add the removed nodes and arcs again using
kpeter@782	557	/// another Snapshot instance.
kpeter@782	558	///
kpeter@782	559	/// \warning Node and arc deletions and other modifications (e.g.
kpeter@782	560	/// reversing, contracting, splitting arcs or nodes) cannot be
alpar@209	561	/// restored. These events invalidate the snapshot.
kpeter@833	562	/// However, the arcs and nodes that were added to the digraph after
kpeter@782	563	/// making the current snapshot can be removed without invalidating it.
deba@57	564	class Snapshot {
deba@57	565	protected:
deba@57	566
deba@57	567	typedef Parent::NodeNotifier NodeNotifier;
deba@57	568
deba@57	569	class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57	570	public:
deba@57	571
deba@57	572	NodeObserverProxy(Snapshot& _snapshot)
deba@57	573	: snapshot(_snapshot) {}
deba@57	574
deba@57	575	using NodeNotifier::ObserverBase::attach;
deba@57	576	using NodeNotifier::ObserverBase::detach;
deba@57	577	using NodeNotifier::ObserverBase::attached;
alpar@209	578
deba@57	579	protected:
alpar@209	580
deba@57	581	virtual void add(const Node& node) {
deba@57	582	snapshot.addNode(node);
deba@57	583	}
deba@57	584	virtual void add(const std::vector<Node>& nodes) {
deba@57	585	for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@57	586	snapshot.addNode(nodes[i]);
deba@57	587	}
deba@57	588	}
deba@57	589	virtual void erase(const Node& node) {
deba@57	590	snapshot.eraseNode(node);
deba@57	591	}
deba@57	592	virtual void erase(const std::vector<Node>& nodes) {
deba@57	593	for (int i = 0; i < int(nodes.size()); ++i) {
deba@57	594	snapshot.eraseNode(nodes[i]);
deba@57	595	}
deba@57	596	}
deba@57	597	virtual void build() {
deba@57	598	Node node;
deba@57	599	std::vector<Node> nodes;
alpar@209	600	for (notifier()->first(node); node != INVALID;
deba@57	601	notifier()->next(node)) {
deba@57	602	nodes.push_back(node);
deba@57	603	}
deba@57	604	for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57	605	snapshot.addNode(nodes[i]);
deba@57	606	}
deba@57	607	}
deba@57	608	virtual void clear() {
deba@57	609	Node node;
alpar@209	610	for (notifier()->first(node); node != INVALID;
deba@57	611	notifier()->next(node)) {
deba@57	612	snapshot.eraseNode(node);
deba@57	613	}
deba@57	614	}
deba@57	615
deba@57	616	Snapshot& snapshot;
deba@57	617	};
deba@57	618
deba@57	619	class ArcObserverProxy : public ArcNotifier::ObserverBase {
deba@57	620	public:
deba@57	621
deba@57	622	ArcObserverProxy(Snapshot& _snapshot)
deba@57	623	: snapshot(_snapshot) {}
deba@57	624
deba@57	625	using ArcNotifier::ObserverBase::attach;
deba@57	626	using ArcNotifier::ObserverBase::detach;
deba@57	627	using ArcNotifier::ObserverBase::attached;
alpar@209	628
deba@57	629	protected:
deba@57	630
deba@57	631	virtual void add(const Arc& arc) {
deba@57	632	snapshot.addArc(arc);
deba@57	633	}
deba@57	634	virtual void add(const std::vector<Arc>& arcs) {
deba@57	635	for (int i = arcs.size() - 1; i >= 0; ++i) {
deba@57	636	snapshot.addArc(arcs[i]);
deba@57	637	}
deba@57	638	}
deba@57	639	virtual void erase(const Arc& arc) {
deba@57	640	snapshot.eraseArc(arc);
deba@57	641	}
deba@57	642	virtual void erase(const std::vector<Arc>& arcs) {
deba@57	643	for (int i = 0; i < int(arcs.size()); ++i) {
deba@57	644	snapshot.eraseArc(arcs[i]);
deba@57	645	}
deba@57	646	}
deba@57	647	virtual void build() {
deba@57	648	Arc arc;
deba@57	649	std::vector<Arc> arcs;
alpar@209	650	for (notifier()->first(arc); arc != INVALID;
deba@57	651	notifier()->next(arc)) {
deba@57	652	arcs.push_back(arc);
deba@57	653	}
deba@57	654	for (int i = arcs.size() - 1; i >= 0; --i) {
deba@57	655	snapshot.addArc(arcs[i]);
deba@57	656	}
deba@57	657	}
deba@57	658	virtual void clear() {
deba@57	659	Arc arc;
alpar@209	660	for (notifier()->first(arc); arc != INVALID;
deba@57	661	notifier()->next(arc)) {
deba@57	662	snapshot.eraseArc(arc);
deba@57	663	}
deba@57	664	}
deba@57	665
deba@57	666	Snapshot& snapshot;
deba@57	667	};
alpar@209	668
deba@57	669	ListDigraph *digraph;
deba@57	670
deba@57	671	NodeObserverProxy node_observer_proxy;
deba@57	672	ArcObserverProxy arc_observer_proxy;
deba@57	673
deba@57	674	std::list<Node> added_nodes;
deba@57	675	std::list<Arc> added_arcs;
deba@57	676
deba@57	677
deba@57	678	void addNode(const Node& node) {
alpar@209	679	added_nodes.push_front(node);
deba@57	680	}
deba@57	681	void eraseNode(const Node& node) {
alpar@209	682	std::list<Node>::iterator it =
deba@57	683	std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57	684	if (it == added_nodes.end()) {
deba@57	685	clear();
deba@57	686	arc_observer_proxy.detach();
deba@57	687	throw NodeNotifier::ImmediateDetach();
deba@57	688	} else {
deba@57	689	added_nodes.erase(it);
deba@57	690	}
deba@57	691	}
deba@57	692
deba@57	693	void addArc(const Arc& arc) {
alpar@209	694	added_arcs.push_front(arc);
deba@57	695	}
deba@57	696	void eraseArc(const Arc& arc) {
alpar@209	697	std::list<Arc>::iterator it =
deba@57	698	std::find(added_arcs.begin(), added_arcs.end(), arc);
deba@57	699	if (it == added_arcs.end()) {
deba@57	700	clear();
alpar@209	701	node_observer_proxy.detach();
deba@57	702	throw ArcNotifier::ImmediateDetach();
deba@57	703	} else {
deba@57	704	added_arcs.erase(it);
alpar@209	705	}
deba@57	706	}
deba@57	707
deba@57	708	void attach(ListDigraph &_digraph) {
alpar@209	709	digraph = &_digraph;
alpar@209	710	node_observer_proxy.attach(digraph->notifier(Node()));
deba@57	711	arc_observer_proxy.attach(digraph->notifier(Arc()));
deba@57	712	}
alpar@209	713
deba@57	714	void detach() {
alpar@209	715	node_observer_proxy.detach();
alpar@209	716	arc_observer_proxy.detach();
deba@57	717	}
deba@57	718
deba@57	719	bool attached() const {
deba@57	720	return node_observer_proxy.attached();
deba@57	721	}
deba@57	722
deba@57	723	void clear() {
deba@57	724	added_nodes.clear();
alpar@209	725	added_arcs.clear();
deba@57	726	}
deba@57	727
deba@57	728	public:
deba@57	729
deba@57	730	/// \brief Default constructor.
deba@57	731	///
deba@57	732	/// Default constructor.
kpeter@782	733	/// You have to call save() to actually make a snapshot.
alpar@209	734	Snapshot()
alpar@209	735	: digraph(0), node_observer_proxy(*this),
deba@57	736	arc_observer_proxy(*this) {}
alpar@209	737
deba@57	738	/// \brief Constructor that immediately makes a snapshot.
alpar@209	739	///
kpeter@782	740	/// This constructor immediately makes a snapshot of the given digraph.
kpeter@782	741	Snapshot(ListDigraph &gr)
alpar@209	742	: node_observer_proxy(*this),
deba@57	743	arc_observer_proxy(*this) {
kpeter@782	744	attach(gr);
deba@57	745	}
alpar@209	746
deba@57	747	/// \brief Make a snapshot.
deba@57	748	///
kpeter@782	749	/// This function makes a snapshot of the given digraph.
kpeter@782	750	/// It can be called more than once. In case of a repeated
deba@57	751	/// call, the previous snapshot gets lost.
kpeter@782	752	void save(ListDigraph &gr) {
deba@57	753	if (attached()) {
deba@57	754	detach();
deba@57	755	clear();
deba@57	756	}
kpeter@782	757	attach(gr);
deba@57	758	}
alpar@209	759
deba@57	760	/// \brief Undo the changes until the last snapshot.
kpeter@782	761	///
kpeter@782	762	/// This function undos the changes until the last snapshot
kpeter@782	763	/// created by save() or Snapshot(ListDigraph&).
kpeter@787	764	///
kpeter@787	765	/// \warning This method invalidates the snapshot, i.e. repeated
kpeter@787	766	/// restoring is not supported unless you call save() again.
deba@57	767	void restore() {
alpar@209	768	detach();
alpar@209	769	for(std::list<Arc>::iterator it = added_arcs.begin();
deba@57	770	it != added_arcs.end(); ++it) {
alpar@209	771	digraph->erase(*it);
alpar@209	772	}
alpar@209	773	for(std::list<Node>::iterator it = added_nodes.begin();
deba@57	774	it != added_nodes.end(); ++it) {
alpar@209	775	digraph->erase(*it);
alpar@209	776	}
deba@57	777	clear();
deba@57	778	}
deba@57	779
kpeter@782	780	/// \brief Returns \c true if the snapshot is valid.
deba@57	781	///
kpeter@782	782	/// This function returns \c true if the snapshot is valid.
deba@57	783	bool valid() const {
deba@57	784	return attached();
deba@57	785	}
deba@57	786	};
alpar@209	787
deba@57	788	};
deba@57	789
deba@57	790	///@}
deba@57	791
deba@57	792	class ListGraphBase {
deba@57	793
deba@57	794	protected:
deba@57	795
deba@57	796	struct NodeT {
deba@57	797	int first_out;
deba@57	798	int prev, next;
deba@57	799	};
alpar@209	800
deba@57	801	struct ArcT {
deba@57	802	int target;
deba@57	803	int prev_out, next_out;
deba@57	804	};
deba@57	805
deba@57	806	std::vector<NodeT> nodes;
deba@57	807
deba@57	808	int first_node;
deba@57	809
deba@57	810	int first_free_node;
deba@57	811
deba@57	812	std::vector<ArcT> arcs;
deba@57	813
deba@57	814	int first_free_arc;
alpar@209	815
deba@57	816	public:
alpar@209	817
kpeter@664	818	typedef ListGraphBase Graph;
deba@57	819
deba@57	820	class Node {
deba@57	821	friend class ListGraphBase;
deba@57	822	protected:
deba@57	823
deba@57	824	int id;
deba@57	825	explicit Node(int pid) { id = pid;}
deba@57	826
deba@57	827	public:
deba@57	828	Node() {}
deba@57	829	Node (Invalid) { id = -1; }
deba@57	830	bool operator==(const Node& node) const {return id == node.id;}
deba@57	831	bool operator!=(const Node& node) const {return id != node.id;}
deba@57	832	bool operator<(const Node& node) const {return id < node.id;}
deba@57	833	};
deba@57	834
deba@57	835	class Edge {
deba@57	836	friend class ListGraphBase;
deba@57	837	protected:
deba@57	838
deba@57	839	int id;
deba@57	840	explicit Edge(int pid) { id = pid;}
deba@57	841
deba@57	842	public:
deba@57	843	Edge() {}
deba@57	844	Edge (Invalid) { id = -1; }
kpeter@73	845	bool operator==(const Edge& edge) const {return id == edge.id;}
kpeter@73	846	bool operator!=(const Edge& edge) const {return id != edge.id;}
kpeter@73	847	bool operator<(const Edge& edge) const {return id < edge.id;}
deba@57	848	};
deba@57	849
deba@57	850	class Arc {
deba@57	851	friend class ListGraphBase;
deba@57	852	protected:
deba@57	853
deba@57	854	int id;
deba@57	855	explicit Arc(int pid) { id = pid;}
deba@57	856
deba@57	857	public:
kpeter@341	858	operator Edge() const {
kpeter@341	859	return id != -1 ? edgeFromId(id / 2) : INVALID;
deba@238	860	}
deba@57	861
deba@57	862	Arc() {}
deba@57	863	Arc (Invalid) { id = -1; }
deba@57	864	bool operator==(const Arc& arc) const {return id == arc.id;}
deba@57	865	bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@57	866	bool operator<(const Arc& arc) const {return id < arc.id;}
deba@57	867	};
deba@57	868
deba@57	869	ListGraphBase()
deba@57	870	: nodes(), first_node(-1),
alpar@209	871	first_free_node(-1), arcs(), first_free_arc(-1) {}
deba@57	872
alpar@209	873
alpar@209	874	int maxNodeId() const { return nodes.size()-1; }
deba@57	875	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@57	876	int maxArcId() const { return arcs.size()-1; }
deba@57	877
deba@57	878	Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
deba@57	879	Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@57	880
deba@57	881	Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
deba@57	882	Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
deba@57	883
deba@57	884	static bool direction(Arc e) {
deba@57	885	return (e.id & 1) == 1;
deba@57	886	}
deba@57	887
deba@57	888	static Arc direct(Edge e, bool d) {
deba@57	889	return Arc(e.id * 2 + (d ? 1 : 0));
deba@57	890	}
deba@57	891
alpar@209	892	void first(Node& node) const {
deba@57	893	node.id = first_node;
deba@57	894	}
deba@57	895
deba@57	896	void next(Node& node) const {
deba@57	897	node.id = nodes[node.id].next;
deba@57	898	}
deba@57	899
alpar@209	900	void first(Arc& e) const {
deba@57	901	int n = first_node;
deba@57	902	while (n != -1 && nodes[n].first_out == -1) {
deba@57	903	n = nodes[n].next;
deba@57	904	}
deba@57	905	e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@57	906	}
deba@57	907
deba@57	908	void next(Arc& e) const {
deba@57	909	if (arcs[e.id].next_out != -1) {
alpar@209	910	e.id = arcs[e.id].next_out;
deba@57	911	} else {
alpar@209	912	int n = nodes[arcs[e.id ^ 1].target].next;
deba@57	913	while(n != -1 && nodes[n].first_out == -1) {
deba@57	914	n = nodes[n].next;
deba@57	915	}
alpar@209	916	e.id = (n == -1) ? -1 : nodes[n].first_out;
alpar@209	917	}
deba@57	918	}
deba@57	919
alpar@209	920	void first(Edge& e) const {
deba@57	921	int n = first_node;
deba@57	922	while (n != -1) {
deba@57	923	e.id = nodes[n].first_out;
deba@57	924	while ((e.id & 1) != 1) {
deba@57	925	e.id = arcs[e.id].next_out;
deba@57	926	}
deba@57	927	if (e.id != -1) {
deba@57	928	e.id /= 2;
deba@57	929	return;
alpar@209	930	}
deba@57	931	n = nodes[n].next;
deba@57	932	}
deba@57	933	e.id = -1;
deba@57	934	}
deba@57	935
deba@57	936	void next(Edge& e) const {
deba@57	937	int n = arcs[e.id * 2].target;
deba@57	938	e.id = arcs[(e.id * 2) \| 1].next_out;
deba@57	939	while ((e.id & 1) != 1) {
deba@57	940	e.id = arcs[e.id].next_out;
deba@57	941	}
deba@57	942	if (e.id != -1) {
deba@57	943	e.id /= 2;
deba@57	944	return;
alpar@209	945	}
deba@57	946	n = nodes[n].next;
deba@57	947	while (n != -1) {
deba@57	948	e.id = nodes[n].first_out;
deba@57	949	while ((e.id & 1) != 1) {
deba@57	950	e.id = arcs[e.id].next_out;
deba@57	951	}
deba@57	952	if (e.id != -1) {
deba@57	953	e.id /= 2;
deba@57	954	return;
alpar@209	955	}
deba@57	956	n = nodes[n].next;
deba@57	957	}
deba@57	958	e.id = -1;
deba@57	959	}
deba@57	960
deba@57	961	void firstOut(Arc &e, const Node& v) const {
deba@57	962	e.id = nodes[v.id].first_out;
deba@57	963	}
deba@57	964	void nextOut(Arc &e) const {
deba@57	965	e.id = arcs[e.id].next_out;
deba@57	966	}
deba@57	967
deba@57	968	void firstIn(Arc &e, const Node& v) const {
deba@57	969	e.id = ((nodes[v.id].first_out) ^ 1);
deba@57	970	if (e.id == -2) e.id = -1;
deba@57	971	}
deba@57	972	void nextIn(Arc &e) const {
deba@57	973	e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
deba@57	974	if (e.id == -2) e.id = -1;
deba@57	975	}
deba@57	976
deba@57	977	void firstInc(Edge &e, bool& d, const Node& v) const {
kpeter@73	978	int a = nodes[v.id].first_out;
kpeter@73	979	if (a != -1 ) {
kpeter@73	980	e.id = a / 2;
kpeter@73	981	d = ((a & 1) == 1);
deba@57	982	} else {
deba@57	983	e.id = -1;
deba@57	984	d = true;
deba@57	985	}
deba@57	986	}
deba@57	987	void nextInc(Edge &e, bool& d) const {
kpeter@73	988	int a = (arcs[(e.id * 2) \| (d ? 1 : 0)].next_out);
kpeter@73	989	if (a != -1 ) {
kpeter@73	990	e.id = a / 2;
kpeter@73	991	d = ((a & 1) == 1);
deba@57	992	} else {
deba@57	993	e.id = -1;
deba@57	994	d = true;
deba@57	995	}
deba@57	996	}
alpar@209	997
deba@57	998	static int id(Node v) { return v.id; }
deba@57	999	static int id(Arc e) { return e.id; }
deba@57	1000	static int id(Edge e) { return e.id; }
deba@57	1001
deba@57	1002	static Node nodeFromId(int id) { return Node(id);}
deba@57	1003	static Arc arcFromId(int id) { return Arc(id);}
deba@57	1004	static Edge edgeFromId(int id) { return Edge(id);}
deba@57	1005
alpar@209	1006	bool valid(Node n) const {
alpar@209	1007	return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
alpar@209	1008	nodes[n.id].prev != -2;
deba@149	1009	}
deba@149	1010
alpar@209	1011	bool valid(Arc a) const {
alpar@209	1012	return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
alpar@209	1013	arcs[a.id].prev_out != -2;
deba@149	1014	}
deba@149	1015
alpar@209	1016	bool valid(Edge e) const {
alpar@209	1017	return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
alpar@209	1018	arcs[2 * e.id].prev_out != -2;
deba@149	1019	}
deba@149	1020
alpar@209	1021	Node addNode() {
deba@57	1022	int n;
alpar@209	1023
deba@57	1024	if(first_free_node==-1) {
alpar@209	1025	n = nodes.size();
alpar@209	1026	nodes.push_back(NodeT());
deba@57	1027	} else {
alpar@209	1028	n = first_free_node;
alpar@209	1029	first_free_node = nodes[n].next;
deba@57	1030	}
alpar@209	1031
deba@57	1032	nodes[n].next = first_node;
deba@57	1033	if (first_node != -1) nodes[first_node].prev = n;
deba@57	1034	first_node = n;
deba@57	1035	nodes[n].prev = -1;
alpar@209	1036
deba@57	1037	nodes[n].first_out = -1;
alpar@209	1038
deba@57	1039	return Node(n);
deba@57	1040	}
alpar@209	1041
deba@57	1042	Edge addEdge(Node u, Node v) {
alpar@209	1043	int n;
deba@57	1044
deba@57	1045	if (first_free_arc == -1) {
alpar@209	1046	n = arcs.size();
alpar@209	1047	arcs.push_back(ArcT());
alpar@209	1048	arcs.push_back(ArcT());
deba@57	1049	} else {
alpar@209	1050	n = first_free_arc;
alpar@209	1051	first_free_arc = arcs[n].next_out;
deba@57	1052	}
alpar@209	1053
deba@57	1054	arcs[n].target = u.id;
deba@57	1055	arcs[n \| 1].target = v.id;
deba@57	1056
deba@57	1057	arcs[n].next_out = nodes[v.id].first_out;
deba@57	1058	if (nodes[v.id].first_out != -1) {
alpar@209	1059	arcs[nodes[v.id].first_out].prev_out = n;
alpar@209	1060	}
deba@57	1061	arcs[n].prev_out = -1;
deba@57	1062	nodes[v.id].first_out = n;
alpar@209	1063
deba@57	1064	arcs[n \| 1].next_out = nodes[u.id].first_out;
deba@57	1065	if (nodes[u.id].first_out != -1) {
alpar@209	1066	arcs[nodes[u.id].first_out].prev_out = (n \| 1);
deba@57	1067	}
alpar@209	1068	arcs[n \| 1].prev_out = -1;
deba@57	1069	nodes[u.id].first_out = (n \| 1);
deba@57	1070
deba@57	1071	return Edge(n / 2);
deba@57	1072	}
alpar@209	1073
deba@57	1074	void erase(const Node& node) {
deba@57	1075	int n = node.id;
alpar@209	1076
deba@57	1077	if(nodes[n].next != -1) {
alpar@209	1078	nodes[nodes[n].next].prev = nodes[n].prev;
deba@57	1079	}
alpar@209	1080
deba@57	1081	if(nodes[n].prev != -1) {
alpar@209	1082	nodes[nodes[n].prev].next = nodes[n].next;
deba@57	1083	} else {
alpar@209	1084	first_node = nodes[n].next;
deba@57	1085	}
alpar@209	1086
deba@57	1087	nodes[n].next = first_free_node;
deba@57	1088	first_free_node = n;
deba@149	1089	nodes[n].prev = -2;
deba@57	1090	}
alpar@209	1091
kpeter@73	1092	void erase(const Edge& edge) {
kpeter@73	1093	int n = edge.id * 2;
alpar@209	1094
deba@57	1095	if (arcs[n].next_out != -1) {
alpar@209	1096	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
alpar@209	1097	}
deba@57	1098
deba@57	1099	if (arcs[n].prev_out != -1) {
alpar@209	1100	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@57	1101	} else {
alpar@209	1102	nodes[arcs[n \| 1].target].first_out = arcs[n].next_out;
deba@57	1103	}
deba@57	1104
deba@57	1105	if (arcs[n \| 1].next_out != -1) {
alpar@209	1106	arcs[arcs[n \| 1].next_out].prev_out = arcs[n \| 1].prev_out;
alpar@209	1107	}
deba@57	1108
deba@57	1109	if (arcs[n \| 1].prev_out != -1) {
alpar@209	1110	arcs[arcs[n \| 1].prev_out].next_out = arcs[n \| 1].next_out;
deba@57	1111	} else {
alpar@209	1112	nodes[arcs[n].target].first_out = arcs[n \| 1].next_out;
deba@57	1113	}
alpar@209	1114
deba@57	1115	arcs[n].next_out = first_free_arc;
alpar@209	1116	first_free_arc = n;
deba@149	1117	arcs[n].prev_out = -2;
deba@149	1118	arcs[n \| 1].prev_out = -2;
deba@57	1119
deba@57	1120	}
deba@57	1121
deba@57	1122	void clear() {
deba@57	1123	arcs.clear();
deba@57	1124	nodes.clear();
deba@57	1125	first_node = first_free_node = first_free_arc = -1;
deba@57	1126	}
deba@57	1127
deba@57	1128	protected:
deba@57	1129
deba@235	1130	void changeV(Edge e, Node n) {
deba@57	1131	if(arcs[2 * e.id].next_out != -1) {
alpar@209	1132	arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
deba@57	1133	}
deba@57	1134	if(arcs[2 * e.id].prev_out != -1) {
alpar@209	1135	arcs[arcs[2 * e.id].prev_out].next_out =
deba@57	1136	arcs[2 * e.id].next_out;
deba@57	1137	} else {
alpar@209	1138	nodes[arcs[(2 * e.id) \| 1].target].first_out =
deba@57	1139	arcs[2 * e.id].next_out;
deba@57	1140	}
deba@57	1141
deba@57	1142	if (nodes[n.id].first_out != -1) {
alpar@209	1143	arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
deba@57	1144	}
deba@57	1145	arcs[(2 * e.id) \| 1].target = n.id;
deba@57	1146	arcs[2 * e.id].prev_out = -1;
deba@57	1147	arcs[2 * e.id].next_out = nodes[n.id].first_out;
deba@57	1148	nodes[n.id].first_out = 2 * e.id;
deba@57	1149	}
deba@57	1150
deba@235	1151	void changeU(Edge e, Node n) {
deba@57	1152	if(arcs[(2 * e.id) \| 1].next_out != -1) {
alpar@209	1153	arcs[arcs[(2 * e.id) \| 1].next_out].prev_out =
deba@57	1154	arcs[(2 * e.id) \| 1].prev_out;
deba@57	1155	}
deba@57	1156	if(arcs[(2 * e.id) \| 1].prev_out != -1) {
alpar@209	1157	arcs[arcs[(2 * e.id) \| 1].prev_out].next_out =
deba@57	1158	arcs[(2 * e.id) \| 1].next_out;
deba@57	1159	} else {
alpar@209	1160	nodes[arcs[2 * e.id].target].first_out =
deba@57	1161	arcs[(2 * e.id) \| 1].next_out;
deba@57	1162	}
deba@57	1163
deba@57	1164	if (nodes[n.id].first_out != -1) {
alpar@209	1165	arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) \| 1);
deba@57	1166	}
deba@57	1167	arcs[2 * e.id].target = n.id;
deba@57	1168	arcs[(2 * e.id) \| 1].prev_out = -1;
deba@57	1169	arcs[(2 * e.id) \| 1].next_out = nodes[n.id].first_out;
deba@57	1170	nodes[n.id].first_out = ((2 * e.id) \| 1);
deba@57	1171	}
deba@57	1172
deba@57	1173	};
deba@57	1174
deba@57	1175	typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
deba@57	1176
deba@57	1177
kpeter@73	1178	/// \addtogroup graphs
deba@57	1179	/// @{
deba@57	1180
kpeter@73	1181	///A general undirected graph structure.
deba@57	1182
kpeter@782	1183	///\ref ListGraph is a versatile and fast undirected graph
kpeter@782	1184	///implementation based on linked lists that are stored in
alpar@209	1185	///\c std::vector structures.
deba@57	1186	///
kpeter@782	1187	///This type fully conforms to the \ref concepts::Graph "Graph concept"
kpeter@782	1188	///and it also provides several useful additional functionalities.
kpeter@782	1189	///Most of its member functions and nested classes are documented
kpeter@73	1190	///only in the concept class.
kpeter@73	1191	///
kpeter@834	1192	///This class provides only linear time counting for nodes, edges and arcs.
kpeter@834	1193	///
kpeter@73	1194	///\sa concepts::Graph
kpeter@782	1195	///\sa ListDigraph
deba@57	1196	class ListGraph : public ExtendedListGraphBase {
kpeter@664	1197	typedef ExtendedListGraphBase Parent;
kpeter@664	1198
deba@57	1199	private:
kpeter@782	1200	/// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@57	1201	ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
kpeter@782	1202	/// \brief Assignment of a graph to another one is \e not allowed.
kpeter@782	1203	/// Use GraphCopy instead.
deba@57	1204	void operator=(const ListGraph &) {}
deba@57	1205	public:
deba@57	1206	/// Constructor
alpar@209	1207
deba@57	1208	/// Constructor.
deba@57	1209	///
deba@57	1210	ListGraph() {}
deba@57	1211
kpeter@73	1212	typedef Parent::OutArcIt IncEdgeIt;
deba@57	1213
kpeter@73	1214	/// \brief Add a new node to the graph.
deba@57	1215	///
kpeter@782	1216	/// This function adds a new node to the graph.
kpeter@606	1217	/// \return The new node.
deba@57	1218	Node addNode() { return Parent::addNode(); }
deba@57	1219
kpeter@73	1220	/// \brief Add a new edge to the graph.
deba@57	1221	///
kpeter@782	1222	/// This function adds a new edge to the graph between nodes
kpeter@782	1223	/// \c u and \c v with inherent orientation from node \c u to
kpeter@782	1224	/// node \c v.
kpeter@606	1225	/// \return The new edge.
kpeter@782	1226	Edge addEdge(Node u, Node v) {
kpeter@782	1227	return Parent::addEdge(u, v);
deba@57	1228	}
deba@234	1229
kpeter@782	1230	///\brief Erase a node from the graph.
deba@234	1231	///
kpeter@834	1232	/// This function erases the given node along with its incident arcs
kpeter@834	1233	/// from the graph.
kpeter@834	1234	///
kpeter@834	1235	/// \note All iterators referencing the removed node or the incident
kpeter@834	1236	/// edges are invalidated, of course.
kpeter@782	1237	void erase(Node n) { Parent::erase(n); }
kpeter@782	1238
kpeter@782	1239	///\brief Erase an edge from the graph.
deba@234	1240	///
kpeter@782	1241	/// This function erases the given edge from the graph.
kpeter@834	1242	///
kpeter@834	1243	/// \note All iterators referencing the removed edge are invalidated,
kpeter@834	1244	/// of course.
kpeter@782	1245	void erase(Edge e) { Parent::erase(e); }
deba@149	1246	/// Node validity check
deba@149	1247
kpeter@782	1248	/// This function gives back \c true if the given node is valid,
kpeter@782	1249	/// i.e. it is a real node of the graph.
deba@149	1250	///
kpeter@782	1251	/// \warning A removed node could become valid again if new nodes are
deba@149	1252	/// added to the graph.
deba@149	1253	bool valid(Node n) const { return Parent::valid(n); }
kpeter@782	1254	/// Edge validity check
kpeter@782	1255
kpeter@782	1256	/// This function gives back \c true if the given edge is valid,
kpeter@782	1257	/// i.e. it is a real edge of the graph.
kpeter@782	1258	///
kpeter@782	1259	/// \warning A removed edge could become valid again if new edges are
kpeter@782	1260	/// added to the graph.
kpeter@782	1261	bool valid(Edge e) const { return Parent::valid(e); }
deba@149	1262	/// Arc validity check
deba@149	1263
kpeter@782	1264	/// This function gives back \c true if the given arc is valid,
kpeter@782	1265	/// i.e. it is a real arc of the graph.
deba@149	1266	///
kpeter@782	1267	/// \warning A removed arc could become valid again if new edges are
deba@149	1268	/// added to the graph.
deba@149	1269	bool valid(Arc a) const { return Parent::valid(a); }
deba@149	1270
kpeter@782	1271	/// \brief Change the first node of an edge.
deba@149	1272	///
kpeter@782	1273	/// This function changes the first node of the given edge \c e to \c n.
deba@57	1274	///
kpeter@782	1275	///\note \c EdgeIt and \c ArcIt iterators referencing the
kpeter@782	1276	///changed edge are invalidated and all other iterators whose
kpeter@782	1277	///base node is the changed node are also invalidated.
kpeter@73	1278	///
kpeter@73	1279	///\warning This functionality cannot be used together with the
kpeter@73	1280	///Snapshot feature.
deba@235	1281	void changeU(Edge e, Node n) {
deba@235	1282	Parent::changeU(e,n);
alpar@209	1283	}
kpeter@782	1284	/// \brief Change the second node of an edge.
deba@57	1285	///
kpeter@782	1286	/// This function changes the second node of the given edge \c e to \c n.
deba@57	1287	///
kpeter@782	1288	///\note \c EdgeIt iterators referencing the changed edge remain
kpeter@833	1289	///valid, but \c ArcIt iterators referencing the changed edge and
kpeter@782	1290	///all other iterators whose base node is the changed node are also
kpeter@782	1291	///invalidated.
kpeter@73	1292	///
kpeter@73	1293	///\warning This functionality cannot be used together with the
kpeter@73	1294	///Snapshot feature.
deba@235	1295	void changeV(Edge e, Node n) {
deba@235	1296	Parent::changeV(e,n);
deba@57	1297	}
kpeter@782	1298
deba@57	1299	/// \brief Contract two nodes.
deba@57	1300	///
kpeter@782	1301	/// This function contracts the given two nodes.
kpeter@782	1302	/// Node \c b is removed, but instead of deleting
kpeter@782	1303	/// its incident edges, they are joined to node \c a.
kpeter@782	1304	/// If the last parameter \c r is \c true (this is the default value),
kpeter@782	1305	/// then the newly created loops are removed.
deba@57	1306	///
kpeter@782	1307	/// \note The moved edges are joined to node \c a using changeU()
kpeter@782	1308	/// or changeV(), thus all edge and arc iterators whose base node is
kpeter@782	1309	/// \c b are invalidated.
alpar@956	1310	/// Moreover all iterators referencing node \c b or the removed
kpeter@782	1311	/// loops are also invalidated. Other iterators remain valid.
kpeter@73	1312	///
kpeter@73	1313	///\warning This functionality cannot be used together with the
kpeter@73	1314	///Snapshot feature.
deba@57	1315	void contract(Node a, Node b, bool r = true) {
kpeter@73	1316	for(IncEdgeIt e(*this, b); e!=INVALID;) {
alpar@209	1317	IncEdgeIt f = e; ++f;
alpar@209	1318	if (r && runningNode(e) == a) {
alpar@209	1319	erase(e);
deba@235	1320	} else if (u(e) == b) {
deba@235	1321	changeU(e, a);
alpar@209	1322	} else {
deba@235	1323	changeV(e, a);
alpar@209	1324	}
alpar@209	1325	e = f;
deba@57	1326	}
deba@57	1327	erase(b);
deba@57	1328	}
deba@57	1329
kpeter@782	1330	///Clear the graph.
kpeter@782	1331
kpeter@782	1332	///This function erases all nodes and arcs from the graph.
kpeter@782	1333	///
kpeter@834	1334	///\note All iterators of the graph are invalidated, of course.
kpeter@782	1335	void clear() {
kpeter@782	1336	Parent::clear();
kpeter@782	1337	}
kpeter@664	1338
kpeter@783	1339	/// Reserve memory for nodes.
kpeter@783	1340
kpeter@783	1341	/// Using this function, it is possible to avoid superfluous memory
kpeter@783	1342	/// allocation: if you know that the graph you want to build will
kpeter@783	1343	/// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@783	1344	/// then it is worth reserving space for this amount before starting
kpeter@783	1345	/// to build the graph.
kpeter@783	1346	/// \sa reserveEdge()
kpeter@783	1347	void reserveNode(int n) { nodes.reserve(n); };
kpeter@783	1348
kpeter@783	1349	/// Reserve memory for edges.
kpeter@783	1350
kpeter@783	1351	/// Using this function, it is possible to avoid superfluous memory
kpeter@783	1352	/// allocation: if you know that the graph you want to build will
kpeter@783	1353	/// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@783	1354	/// then it is worth reserving space for this amount before starting
kpeter@783	1355	/// to build the graph.
kpeter@783	1356	/// \sa reserveNode()
kpeter@783	1357	void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@57	1358
kpeter@73	1359	/// \brief Class to make a snapshot of the graph and restore
kpeter@73	1360	/// it later.
deba@57	1361	///
kpeter@73	1362	/// Class to make a snapshot of the graph and restore it later.
deba@57	1363	///
deba@57	1364	/// The newly added nodes and edges can be removed
deba@57	1365	/// using the restore() function.
deba@57	1366	///
alpar@956	1367	/// \note After a state is restored, you cannot restore a later state,
kpeter@782	1368	/// i.e. you cannot add the removed nodes and edges again using
kpeter@782	1369	/// another Snapshot instance.
kpeter@782	1370	///
kpeter@782	1371	/// \warning Node and edge deletions and other modifications
kpeter@782	1372	/// (e.g. changing the end-nodes of edges or contracting nodes)
kpeter@782	1373	/// cannot be restored. These events invalidate the snapshot.
kpeter@833	1374	/// However, the edges and nodes that were added to the graph after
kpeter@782	1375	/// making the current snapshot can be removed without invalidating it.
deba@57	1376	class Snapshot {
deba@57	1377	protected:
deba@57	1378
deba@57	1379	typedef Parent::NodeNotifier NodeNotifier;
deba@57	1380
deba@57	1381	class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@57	1382	public:
deba@57	1383
deba@57	1384	NodeObserverProxy(Snapshot& _snapshot)
deba@57	1385	: snapshot(_snapshot) {}
deba@57	1386
deba@57	1387	using NodeNotifier::ObserverBase::attach;
deba@57	1388	using NodeNotifier::ObserverBase::detach;
deba@57	1389	using NodeNotifier::ObserverBase::attached;
alpar@209	1390
deba@57	1391	protected:
alpar@209	1392
deba@57	1393	virtual void add(const Node& node) {
deba@57	1394	snapshot.addNode(node);
deba@57	1395	}
deba@57	1396	virtual void add(const std::vector<Node>& nodes) {
deba@57	1397	for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@57	1398	snapshot.addNode(nodes[i]);
deba@57	1399	}
deba@57	1400	}
deba@57	1401	virtual void erase(const Node& node) {
deba@57	1402	snapshot.eraseNode(node);
deba@57	1403	}
deba@57	1404	virtual void erase(const std::vector<Node>& nodes) {
deba@57	1405	for (int i = 0; i < int(nodes.size()); ++i) {
deba@57	1406	snapshot.eraseNode(nodes[i]);
deba@57	1407	}
deba@57	1408	}
deba@57	1409	virtual void build() {
deba@57	1410	Node node;
deba@57	1411	std::vector<Node> nodes;
alpar@209	1412	for (notifier()->first(node); node != INVALID;
deba@57	1413	notifier()->next(node)) {
deba@57	1414	nodes.push_back(node);
deba@57	1415	}
deba@57	1416	for (int i = nodes.size() - 1; i >= 0; --i) {
deba@57	1417	snapshot.addNode(nodes[i]);
deba@57	1418	}
deba@57	1419	}
deba@57	1420	virtual void clear() {
deba@57	1421	Node node;
alpar@209	1422	for (notifier()->first(node); node != INVALID;
deba@57	1423	notifier()->next(node)) {
deba@57	1424	snapshot.eraseNode(node);
deba@57	1425	}
deba@57	1426	}
deba@57	1427
deba@57	1428	Snapshot& snapshot;
deba@57	1429	};
deba@57	1430
deba@57	1431	class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@57	1432	public:
deba@57	1433
deba@57	1434	EdgeObserverProxy(Snapshot& _snapshot)
deba@57	1435	: snapshot(_snapshot) {}
deba@57	1436
deba@57	1437	using EdgeNotifier::ObserverBase::attach;
deba@57	1438	using EdgeNotifier::ObserverBase::detach;
deba@57	1439	using EdgeNotifier::ObserverBase::attached;
alpar@209	1440
deba@57	1441	protected:
deba@57	1442
kpeter@73	1443	virtual void add(const Edge& edge) {
kpeter@73	1444	snapshot.addEdge(edge);
deba@57	1445	}
kpeter@73	1446	virtual void add(const std::vector<Edge>& edges) {
kpeter@73	1447	for (int i = edges.size() - 1; i >= 0; ++i) {
kpeter@73	1448	snapshot.addEdge(edges[i]);
deba@57	1449	}
deba@57	1450	}
kpeter@73	1451	virtual void erase(const Edge& edge) {
kpeter@73	1452	snapshot.eraseEdge(edge);
deba@57	1453	}
kpeter@73	1454	virtual void erase(const std::vector<Edge>& edges) {
kpeter@73	1455	for (int i = 0; i < int(edges.size()); ++i) {
kpeter@73	1456	snapshot.eraseEdge(edges[i]);
deba@57	1457	}
deba@57	1458	}
deba@57	1459	virtual void build() {
kpeter@73	1460	Edge edge;
kpeter@73	1461	std::vector<Edge> edges;
alpar@209	1462	for (notifier()->first(edge); edge != INVALID;
kpeter@73	1463	notifier()->next(edge)) {
kpeter@73	1464	edges.push_back(edge);
deba@57	1465	}
kpeter@73	1466	for (int i = edges.size() - 1; i >= 0; --i) {
kpeter@73	1467	snapshot.addEdge(edges[i]);
deba@57	1468	}
deba@57	1469	}
deba@57	1470	virtual void clear() {
kpeter@73	1471	Edge edge;
alpar@209	1472	for (notifier()->first(edge); edge != INVALID;
kpeter@73	1473	notifier()->next(edge)) {
kpeter@73	1474	snapshot.eraseEdge(edge);
deba@57	1475	}
deba@57	1476	}
deba@57	1477
deba@57	1478	Snapshot& snapshot;
deba@57	1479	};
kpeter@73	1480
kpeter@73	1481	ListGraph *graph;
deba@57	1482
deba@57	1483	NodeObserverProxy node_observer_proxy;
kpeter@73	1484	EdgeObserverProxy edge_observer_proxy;
deba@57	1485
deba@57	1486	std::list<Node> added_nodes;
kpeter@73	1487	std::list<Edge> added_edges;
deba@57	1488
deba@57	1489
deba@57	1490	void addNode(const Node& node) {
alpar@209	1491	added_nodes.push_front(node);
deba@57	1492	}
deba@57	1493	void eraseNode(const Node& node) {
alpar@209	1494	std::list<Node>::iterator it =
deba@57	1495	std::find(added_nodes.begin(), added_nodes.end(), node);
deba@57	1496	if (it == added_nodes.end()) {
deba@57	1497	clear();
kpeter@73	1498	edge_observer_proxy.detach();
deba@57	1499	throw NodeNotifier::ImmediateDetach();
deba@57	1500	} else {
deba@57	1501	added_nodes.erase(it);
deba@57	1502	}
deba@57	1503	}
deba@57	1504
kpeter@73	1505	void addEdge(const Edge& edge) {
alpar@209	1506	added_edges.push_front(edge);
deba@57	1507	}
kpeter@73	1508	void eraseEdge(const Edge& edge) {
alpar@209	1509	std::list<Edge>::iterator it =
kpeter@73	1510	std::find(added_edges.begin(), added_edges.end(), edge);
kpeter@73	1511	if (it == added_edges.end()) {
deba@57	1512	clear();
deba@57	1513	node_observer_proxy.detach();
deba@57	1514	throw EdgeNotifier::ImmediateDetach();
deba@57	1515	} else {
kpeter@73	1516	added_edges.erase(it);
kpeter@73	1517	}
deba@57	1518	}
deba@57	1519
kpeter@73	1520	void attach(ListGraph &_graph) {
alpar@209	1521	graph = &_graph;
alpar@209	1522	node_observer_proxy.attach(graph->notifier(Node()));
kpeter@73	1523	edge_observer_proxy.attach(graph->notifier(Edge()));
deba@57	1524	}
alpar@209	1525
deba@57	1526	void detach() {
alpar@209	1527	node_observer_proxy.detach();
alpar@209	1528	edge_observer_proxy.detach();
deba@57	1529	}
deba@57	1530
deba@57	1531	bool attached() const {
deba@57	1532	return node_observer_proxy.attached();
deba@57	1533	}
deba@57	1534
deba@57	1535	void clear() {
deba@57	1536	added_nodes.clear();
alpar@209	1537	added_edges.clear();
deba@57	1538	}
deba@57	1539
deba@57	1540	public:
deba@57	1541
deba@57	1542	/// \brief Default constructor.
deba@57	1543	///
deba@57	1544	/// Default constructor.
kpeter@782	1545	/// You have to call save() to actually make a snapshot.
alpar@209	1546	Snapshot()
alpar@209	1547	: graph(0), node_observer_proxy(*this),
kpeter@73	1548	edge_observer_proxy(*this) {}
alpar@209	1549
deba@57	1550	/// \brief Constructor that immediately makes a snapshot.
alpar@209	1551	///
kpeter@782	1552	/// This constructor immediately makes a snapshot of the given graph.
kpeter@782	1553	Snapshot(ListGraph &gr)
alpar@209	1554	: node_observer_proxy(*this),
kpeter@73	1555	edge_observer_proxy(*this) {
kpeter@782	1556	attach(gr);
deba@57	1557	}
alpar@209	1558
deba@57	1559	/// \brief Make a snapshot.
deba@57	1560	///
kpeter@782	1561	/// This function makes a snapshot of the given graph.
kpeter@782	1562	/// It can be called more than once. In case of a repeated
deba@57	1563	/// call, the previous snapshot gets lost.
kpeter@782	1564	void save(ListGraph &gr) {
deba@57	1565	if (attached()) {
deba@57	1566	detach();
deba@57	1567	clear();
deba@57	1568	}
kpeter@782	1569	attach(gr);
deba@57	1570	}
alpar@209	1571
deba@57	1572	/// \brief Undo the changes until the last snapshot.
kpeter@782	1573	///
kpeter@782	1574	/// This function undos the changes until the last snapshot
kpeter@782	1575	/// created by save() or Snapshot(ListGraph&).
kpeter@787	1576	///
kpeter@787	1577	/// \warning This method invalidates the snapshot, i.e. repeated
kpeter@787	1578	/// restoring is not supported unless you call save() again.
deba@57	1579	void restore() {
alpar@209	1580	detach();
alpar@209	1581	for(std::list<Edge>::iterator it = added_edges.begin();
kpeter@73	1582	it != added_edges.end(); ++it) {
alpar@209	1583	graph->erase(*it);
alpar@209	1584	}
alpar@209	1585	for(std::list<Node>::iterator it = added_nodes.begin();
deba@57	1586	it != added_nodes.end(); ++it) {
alpar@209	1587	graph->erase(*it);
alpar@209	1588	}
deba@57	1589	clear();
deba@57	1590	}
deba@57	1591
kpeter@782	1592	/// \brief Returns \c true if the snapshot is valid.
deba@57	1593	///
kpeter@782	1594	/// This function returns \c true if the snapshot is valid.
deba@57	1595	bool valid() const {
deba@57	1596	return attached();
deba@57	1597	}
deba@57	1598	};
deba@57	1599	};
alpar@209	1600
alpar@209	1601	/// @}
deba@1189	1602
deba@1189	1603	class ListBpGraphBase {
deba@1189	1604
deba@1189	1605	protected:
deba@1189	1606
deba@1189	1607	struct NodeT {
deba@1189	1608	int first_out;
deba@1189	1609	int prev, next;
deba@1189	1610	int partition_prev, partition_next;
deba@1189	1611	int partition_index;
deba@1189	1612	bool red;
deba@1189	1613	};
deba@1189	1614
deba@1189	1615	struct ArcT {
deba@1189	1616	int target;
deba@1189	1617	int prev_out, next_out;
deba@1189	1618	};
deba@1189	1619
deba@1189	1620	std::vector<NodeT> nodes;
deba@1189	1621
deba@1189	1622	int first_node, first_red, first_blue;
deba@1189	1623	int max_red, max_blue;
deba@1189	1624
deba@1189	1625	int first_free_red, first_free_blue;
deba@1189	1626
deba@1189	1627	std::vector<ArcT> arcs;
deba@1189	1628
deba@1189	1629	int first_free_arc;
deba@1189	1630
deba@1189	1631	public:
deba@1189	1632
deba@1189	1633	typedef ListBpGraphBase BpGraph;
deba@1189	1634
deba@1189	1635	class Node {
deba@1189	1636	friend class ListBpGraphBase;
deba@1189	1637	protected:
deba@1189	1638
deba@1189	1639	int id;
deba@1189	1640	explicit Node(int pid) { id = pid;}
deba@1189	1641
deba@1189	1642	public:
deba@1189	1643	Node() {}
deba@1189	1644	Node (Invalid) { id = -1; }
deba@1189	1645	bool operator==(const Node& node) const {return id == node.id;}
deba@1189	1646	bool operator!=(const Node& node) const {return id != node.id;}
deba@1189	1647	bool operator<(const Node& node) const {return id < node.id;}
deba@1189	1648	};
deba@1189	1649
deba@1193	1650	class RedNode : public Node {
deba@1193	1651	friend class ListBpGraphBase;
deba@1193	1652	protected:
deba@1193	1653
deba@1193	1654	explicit RedNode(int pid) : Node(pid) {}
deba@1193	1655
deba@1193	1656	public:
deba@1193	1657	RedNode() {}
deba@1193	1658	RedNode(const RedNode& node) : Node(node) {}
deba@1193	1659	RedNode(Invalid) : Node(INVALID){}
deba@1193	1660	};
deba@1193	1661
deba@1193	1662	class BlueNode : public Node {
deba@1193	1663	friend class ListBpGraphBase;
deba@1193	1664	protected:
deba@1193	1665
deba@1193	1666	explicit BlueNode(int pid) : Node(pid) {}
deba@1193	1667
deba@1193	1668	public:
deba@1193	1669	BlueNode() {}
deba@1193	1670	BlueNode(const BlueNode& node) : Node(node) {}
deba@1193	1671	BlueNode(Invalid) : Node(INVALID){}
deba@1193	1672	};
deba@1193	1673
deba@1189	1674	class Edge {
deba@1189	1675	friend class ListBpGraphBase;
deba@1189	1676	protected:
deba@1189	1677
deba@1189	1678	int id;
deba@1189	1679	explicit Edge(int pid) { id = pid;}
deba@1189	1680
deba@1189	1681	public:
deba@1189	1682	Edge() {}
deba@1189	1683	Edge (Invalid) { id = -1; }
deba@1189	1684	bool operator==(const Edge& edge) const {return id == edge.id;}
deba@1189	1685	bool operator!=(const Edge& edge) const {return id != edge.id;}
deba@1189	1686	bool operator<(const Edge& edge) const {return id < edge.id;}
deba@1189	1687	};
deba@1189	1688
deba@1189	1689	class Arc {
deba@1189	1690	friend class ListBpGraphBase;
deba@1189	1691	protected:
deba@1189	1692
deba@1189	1693	int id;
deba@1189	1694	explicit Arc(int pid) { id = pid;}
deba@1189	1695
deba@1189	1696	public:
deba@1189	1697	operator Edge() const {
deba@1189	1698	return id != -1 ? edgeFromId(id / 2) : INVALID;
deba@1189	1699	}
deba@1189	1700
deba@1189	1701	Arc() {}
deba@1189	1702	Arc (Invalid) { id = -1; }
deba@1189	1703	bool operator==(const Arc& arc) const {return id == arc.id;}
deba@1189	1704	bool operator!=(const Arc& arc) const {return id != arc.id;}
deba@1189	1705	bool operator<(const Arc& arc) const {return id < arc.id;}
deba@1189	1706	};
deba@1189	1707
deba@1189	1708	ListBpGraphBase()
deba@1189	1709	: nodes(), first_node(-1),
deba@1189	1710	first_red(-1), first_blue(-1),
deba@1189	1711	max_red(-1), max_blue(-1),
deba@1189	1712	first_free_red(-1), first_free_blue(-1),
deba@1189	1713	arcs(), first_free_arc(-1) {}
deba@1189	1714
deba@1189	1715
deba@1189	1716	bool red(Node n) const { return nodes[n.id].red; }
deba@1189	1717	bool blue(Node n) const { return !nodes[n.id].red; }
deba@1189	1718
deba@1193	1719	static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
deba@1193	1720	static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
deba@1193	1721
deba@1189	1722	int maxNodeId() const { return nodes.size()-1; }
deba@1189	1723	int maxRedId() const { return max_red; }
deba@1189	1724	int maxBlueId() const { return max_blue; }
deba@1189	1725	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@1189	1726	int maxArcId() const { return arcs.size()-1; }
deba@1189	1727
deba@1189	1728	Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
deba@1189	1729	Node target(Arc e) const { return Node(arcs[e.id].target); }
deba@1189	1730
deba@1193	1731	RedNode redNode(Edge e) const {
deba@1193	1732	return RedNode(arcs[2 * e.id].target);
deba@1193	1733	}
deba@1193	1734	BlueNode blueNode(Edge e) const {
deba@1193	1735	return BlueNode(arcs[2 * e.id + 1].target);
deba@1193	1736	}
deba@1189	1737
deba@1189	1738	static bool direction(Arc e) {
deba@1189	1739	return (e.id & 1) == 1;
deba@1189	1740	}
deba@1189	1741
deba@1189	1742	static Arc direct(Edge e, bool d) {
deba@1189	1743	return Arc(e.id * 2 + (d ? 1 : 0));
deba@1189	1744	}
deba@1189	1745
deba@1189	1746	void first(Node& node) const {
deba@1189	1747	node.id = first_node;
deba@1189	1748	}
deba@1189	1749
deba@1189	1750	void next(Node& node) const {
deba@1189	1751	node.id = nodes[node.id].next;
deba@1189	1752	}
deba@1189	1753
deba@1193	1754	void first(RedNode& node) const {
deba@1189	1755	node.id = first_red;
deba@1189	1756	}
deba@1189	1757
deba@1193	1758	void next(RedNode& node) const {
deba@1189	1759	node.id = nodes[node.id].partition_next;
deba@1189	1760	}
deba@1189	1761
deba@1193	1762	void first(BlueNode& node) const {
deba@1189	1763	node.id = first_blue;
deba@1189	1764	}
deba@1189	1765
deba@1193	1766	void next(BlueNode& node) const {
deba@1189	1767	node.id = nodes[node.id].partition_next;
deba@1189	1768	}
deba@1189	1769
deba@1189	1770	void first(Arc& e) const {
deba@1189	1771	int n = first_node;
deba@1189	1772	while (n != -1 && nodes[n].first_out == -1) {
deba@1189	1773	n = nodes[n].next;
deba@1189	1774	}
deba@1189	1775	e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@1189	1776	}
deba@1189	1777
deba@1189	1778	void next(Arc& e) const {
deba@1189	1779	if (arcs[e.id].next_out != -1) {
deba@1189	1780	e.id = arcs[e.id].next_out;
deba@1189	1781	} else {
deba@1189	1782	int n = nodes[arcs[e.id ^ 1].target].next;
deba@1189	1783	while(n != -1 && nodes[n].first_out == -1) {
deba@1189	1784	n = nodes[n].next;
deba@1189	1785	}
deba@1189	1786	e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@1189	1787	}
deba@1189	1788	}
deba@1189	1789
deba@1189	1790	void first(Edge& e) const {
deba@1189	1791	int n = first_node;
deba@1189	1792	while (n != -1) {
deba@1189	1793	e.id = nodes[n].first_out;
deba@1189	1794	while ((e.id & 1) != 1) {
deba@1189	1795	e.id = arcs[e.id].next_out;
deba@1189	1796	}
deba@1189	1797	if (e.id != -1) {
deba@1189	1798	e.id /= 2;
deba@1189	1799	return;
deba@1189	1800	}
deba@1189	1801	n = nodes[n].next;
deba@1189	1802	}
deba@1189	1803	e.id = -1;
deba@1189	1804	}
deba@1189	1805
deba@1189	1806	void next(Edge& e) const {
deba@1189	1807	int n = arcs[e.id * 2].target;
deba@1189	1808	e.id = arcs[(e.id * 2) \| 1].next_out;
deba@1189	1809	while ((e.id & 1) != 1) {
deba@1189	1810	e.id = arcs[e.id].next_out;
deba@1189	1811	}
deba@1189	1812	if (e.id != -1) {
deba@1189	1813	e.id /= 2;
deba@1189	1814	return;
deba@1189	1815	}
deba@1189	1816	n = nodes[n].next;
deba@1189	1817	while (n != -1) {
deba@1189	1818	e.id = nodes[n].first_out;
deba@1189	1819	while ((e.id & 1) != 1) {
deba@1189	1820	e.id = arcs[e.id].next_out;
deba@1189	1821	}
deba@1189	1822	if (e.id != -1) {
deba@1189	1823	e.id /= 2;
deba@1189	1824	return;
deba@1189	1825	}
deba@1189	1826	n = nodes[n].next;
deba@1189	1827	}
deba@1189	1828	e.id = -1;
deba@1189	1829	}
deba@1189	1830
deba@1189	1831	void firstOut(Arc &e, const Node& v) const {
deba@1189	1832	e.id = nodes[v.id].first_out;
deba@1189	1833	}
deba@1189	1834	void nextOut(Arc &e) const {
deba@1189	1835	e.id = arcs[e.id].next_out;
deba@1189	1836	}
deba@1189	1837
deba@1189	1838	void firstIn(Arc &e, const Node& v) const {
deba@1189	1839	e.id = ((nodes[v.id].first_out) ^ 1);
deba@1189	1840	if (e.id == -2) e.id = -1;
deba@1189	1841	}
deba@1189	1842	void nextIn(Arc &e) const {
deba@1189	1843	e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
deba@1189	1844	if (e.id == -2) e.id = -1;
deba@1189	1845	}
deba@1189	1846
deba@1189	1847	void firstInc(Edge &e, bool& d, const Node& v) const {
deba@1189	1848	int a = nodes[v.id].first_out;
deba@1189	1849	if (a != -1 ) {
deba@1189	1850	e.id = a / 2;
deba@1189	1851	d = ((a & 1) == 1);
deba@1189	1852	} else {
deba@1189	1853	e.id = -1;
deba@1189	1854	d = true;
deba@1189	1855	}
deba@1189	1856	}
deba@1189	1857	void nextInc(Edge &e, bool& d) const {
deba@1189	1858	int a = (arcs[(e.id * 2) \| (d ? 1 : 0)].next_out);
deba@1189	1859	if (a != -1 ) {
deba@1189	1860	e.id = a / 2;
deba@1189	1861	d = ((a & 1) == 1);
deba@1189	1862	} else {
deba@1189	1863	e.id = -1;
deba@1189	1864	d = true;
deba@1189	1865	}
deba@1189	1866	}
deba@1189	1867
deba@1189	1868	static int id(Node v) { return v.id; }
deba@1193	1869	int id(RedNode v) const { return nodes[v.id].partition_index; }
deba@1193	1870	int id(BlueNode v) const { return nodes[v.id].partition_index; }
deba@1189	1871	static int id(Arc e) { return e.id; }
deba@1189	1872	static int id(Edge e) { return e.id; }
deba@1189	1873
deba@1189	1874	static Node nodeFromId(int id) { return Node(id);}
deba@1189	1875	static Arc arcFromId(int id) { return Arc(id);}
deba@1189	1876	static Edge edgeFromId(int id) { return Edge(id);}
deba@1189	1877
deba@1189	1878	bool valid(Node n) const {
deba@1189	1879	return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
deba@1189	1880	nodes[n.id].prev != -2;
deba@1189	1881	}
deba@1189	1882
deba@1189	1883	bool valid(Arc a) const {
deba@1189	1884	return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
deba@1189	1885	arcs[a.id].prev_out != -2;
deba@1189	1886	}
deba@1189	1887
deba@1189	1888	bool valid(Edge e) const {
deba@1189	1889	return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
deba@1189	1890	arcs[2 * e.id].prev_out != -2;
deba@1189	1891	}
deba@1189	1892
deba@1193	1893	RedNode addRedNode() {
deba@1189	1894	int n;
deba@1189	1895
deba@1189	1896	if(first_free_red==-1) {
deba@1189	1897	n = nodes.size();
deba@1189	1898	nodes.push_back(NodeT());
deba@1189	1899	nodes[n].partition_index = ++max_red;
deba@1189	1900	nodes[n].red = true;
deba@1189	1901	} else {
deba@1189	1902	n = first_free_red;
deba@1189	1903	first_free_red = nodes[n].next;
deba@1189	1904	}
deba@1189	1905
deba@1189	1906	nodes[n].next = first_node;
deba@1189	1907	if (first_node != -1) nodes[first_node].prev = n;
deba@1189	1908	first_node = n;
deba@1189	1909	nodes[n].prev = -1;
deba@1189	1910
deba@1189	1911	nodes[n].partition_next = first_red;
deba@1189	1912	if (first_red != -1) nodes[first_red].partition_prev = n;
deba@1189	1913	first_red = n;
deba@1189	1914	nodes[n].partition_prev = -1;
deba@1189	1915
deba@1189	1916	nodes[n].first_out = -1;
deba@1189	1917
deba@1193	1918	return RedNode(n);
deba@1189	1919	}
deba@1189	1920
deba@1193	1921	BlueNode addBlueNode() {
deba@1189	1922	int n;
deba@1189	1923
deba@1189	1924	if(first_free_blue==-1) {
deba@1189	1925	n = nodes.size();
deba@1189	1926	nodes.push_back(NodeT());
deba@1189	1927	nodes[n].partition_index = ++max_blue;
deba@1189	1928	nodes[n].red = false;
deba@1189	1929	} else {
deba@1189	1930	n = first_free_blue;
deba@1189	1931	first_free_blue = nodes[n].next;
deba@1189	1932	}
deba@1189	1933
deba@1189	1934	nodes[n].next = first_node;
deba@1189	1935	if (first_node != -1) nodes[first_node].prev = n;
deba@1189	1936	first_node = n;
deba@1189	1937	nodes[n].prev = -1;
deba@1189	1938
deba@1189	1939	nodes[n].partition_next = first_blue;
deba@1189	1940	if (first_blue != -1) nodes[first_blue].partition_prev = n;
deba@1189	1941	first_blue = n;
deba@1189	1942	nodes[n].partition_prev = -1;
deba@1189	1943
deba@1189	1944	nodes[n].first_out = -1;
deba@1189	1945
deba@1193	1946	return BlueNode(n);
deba@1189	1947	}
deba@1189	1948
deba@1189	1949	Edge addEdge(Node u, Node v) {
deba@1189	1950	int n;
deba@1189	1951
deba@1189	1952	if (first_free_arc == -1) {
deba@1189	1953	n = arcs.size();
deba@1189	1954	arcs.push_back(ArcT());
deba@1189	1955	arcs.push_back(ArcT());
deba@1189	1956	} else {
deba@1189	1957	n = first_free_arc;
deba@1189	1958	first_free_arc = arcs[n].next_out;
deba@1189	1959	}
deba@1189	1960
deba@1189	1961	arcs[n].target = u.id;
deba@1189	1962	arcs[n \| 1].target = v.id;
deba@1189	1963
deba@1189	1964	arcs[n].next_out = nodes[v.id].first_out;
deba@1189	1965	if (nodes[v.id].first_out != -1) {
deba@1189	1966	arcs[nodes[v.id].first_out].prev_out = n;
deba@1189	1967	}
deba@1189	1968	arcs[n].prev_out = -1;
deba@1189	1969	nodes[v.id].first_out = n;
deba@1189	1970
deba@1189	1971	arcs[n \| 1].next_out = nodes[u.id].first_out;
deba@1189	1972	if (nodes[u.id].first_out != -1) {
deba@1189	1973	arcs[nodes[u.id].first_out].prev_out = (n \| 1);
deba@1189	1974	}
deba@1189	1975	arcs[n \| 1].prev_out = -1;
deba@1189	1976	nodes[u.id].first_out = (n \| 1);
deba@1189	1977
deba@1189	1978	return Edge(n / 2);
deba@1189	1979	}
deba@1189	1980
deba@1189	1981	void erase(const Node& node) {
deba@1189	1982	int n = node.id;
deba@1189	1983
deba@1189	1984	if(nodes[n].next != -1) {
deba@1189	1985	nodes[nodes[n].next].prev = nodes[n].prev;
deba@1189	1986	}
deba@1189	1987
deba@1189	1988	if(nodes[n].prev != -1) {
deba@1189	1989	nodes[nodes[n].prev].next = nodes[n].next;
deba@1189	1990	} else {
deba@1189	1991	first_node = nodes[n].next;
deba@1189	1992	}
deba@1189	1993
deba@1189	1994	if (nodes[n].partition_next != -1) {
deba@1189	1995	nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
deba@1189	1996	}
deba@1189	1997
deba@1189	1998	if (nodes[n].partition_prev != -1) {
deba@1189	1999	nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
deba@1189	2000	} else {
deba@1189	2001	if (nodes[n].red) {
deba@1189	2002	first_red = nodes[n].partition_next;
deba@1189	2003	} else {
deba@1189	2004	first_blue = nodes[n].partition_next;
deba@1189	2005	}
deba@1189	2006	}
deba@1189	2007
deba@1189	2008	if (nodes[n].red) {
deba@1189	2009	nodes[n].next = first_free_red;
deba@1189	2010	first_free_red = n;
deba@1189	2011	} else {
deba@1189	2012	nodes[n].next = first_free_blue;
deba@1189	2013	first_free_blue = n;
deba@1189	2014	}
deba@1189	2015	nodes[n].prev = -2;
deba@1189	2016	}
deba@1189	2017
deba@1189	2018	void erase(const Edge& edge) {
deba@1189	2019	int n = edge.id * 2;
deba@1189	2020
deba@1189	2021	if (arcs[n].next_out != -1) {
deba@1189	2022	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
deba@1189	2023	}
deba@1189	2024
deba@1189	2025	if (arcs[n].prev_out != -1) {
deba@1189	2026	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
deba@1189	2027	} else {
deba@1189	2028	nodes[arcs[n \| 1].target].first_out = arcs[n].next_out;
deba@1189	2029	}
deba@1189	2030
deba@1189	2031	if (arcs[n \| 1].next_out != -1) {
deba@1189	2032	arcs[arcs[n \| 1].next_out].prev_out = arcs[n \| 1].prev_out;
deba@1189	2033	}
deba@1189	2034
deba@1189	2035	if (arcs[n \| 1].prev_out != -1) {
deba@1189	2036	arcs[arcs[n \| 1].prev_out].next_out = arcs[n \| 1].next_out;
deba@1189	2037	} else {
deba@1189	2038	nodes[arcs[n].target].first_out = arcs[n \| 1].next_out;
deba@1189	2039	}
deba@1189	2040
deba@1189	2041	arcs[n].next_out = first_free_arc;
deba@1189	2042	first_free_arc = n;
deba@1189	2043	arcs[n].prev_out = -2;
deba@1189	2044	arcs[n \| 1].prev_out = -2;
deba@1189	2045
deba@1189	2046	}
deba@1189	2047
deba@1189	2048	void clear() {
deba@1189	2049	arcs.clear();
deba@1189	2050	nodes.clear();
deba@1189	2051	first_node = first_free_arc = first_red = first_blue =
deba@1189	2052	max_red = max_blue = first_free_red = first_free_blue = -1;
deba@1189	2053	}
deba@1189	2054
deba@1189	2055	protected:
deba@1189	2056
deba@1193	2057	void changeRed(Edge e, RedNode n) {
deba@1189	2058	if(arcs[(2 * e.id) \| 1].next_out != -1) {
deba@1189	2059	arcs[arcs[(2 * e.id) \| 1].next_out].prev_out =
deba@1189	2060	arcs[(2 * e.id) \| 1].prev_out;
deba@1189	2061	}
deba@1189	2062	if(arcs[(2 * e.id) \| 1].prev_out != -1) {
deba@1189	2063	arcs[arcs[(2 * e.id) \| 1].prev_out].next_out =
deba@1189	2064	arcs[(2 * e.id) \| 1].next_out;
deba@1189	2065	} else {
deba@1189	2066	nodes[arcs[2 * e.id].target].first_out =
deba@1189	2067	arcs[(2 * e.id) \| 1].next_out;
deba@1189	2068	}
deba@1189	2069
deba@1189	2070	if (nodes[n.id].first_out != -1) {
deba@1189	2071	arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) \| 1);
deba@1189	2072	}
deba@1189	2073	arcs[2 * e.id].target = n.id;
deba@1189	2074	arcs[(2 * e.id) \| 1].prev_out = -1;
deba@1189	2075	arcs[(2 * e.id) \| 1].next_out = nodes[n.id].first_out;
deba@1189	2076	nodes[n.id].first_out = ((2 * e.id) \| 1);
deba@1189	2077	}
deba@1189	2078
deba@1193	2079	void changeBlue(Edge e, BlueNode n) {
deba@1193	2080	if(arcs[2 * e.id].next_out != -1) {
deba@1189	2081	arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
deba@1189	2082	}
deba@1189	2083	if(arcs[2 * e.id].prev_out != -1) {
deba@1189	2084	arcs[arcs[2 * e.id].prev_out].next_out =
deba@1189	2085	arcs[2 * e.id].next_out;
deba@1189	2086	} else {
deba@1189	2087	nodes[arcs[(2 * e.id) \| 1].target].first_out =
deba@1189	2088	arcs[2 * e.id].next_out;
deba@1189	2089	}
deba@1189	2090
deba@1189	2091	if (nodes[n.id].first_out != -1) {
deba@1189	2092	arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
deba@1189	2093	}
deba@1189	2094	arcs[(2 * e.id) \| 1].target = n.id;
deba@1189	2095	arcs[2 * e.id].prev_out = -1;
deba@1189	2096	arcs[2 * e.id].next_out = nodes[n.id].first_out;
deba@1189	2097	nodes[n.id].first_out = 2 * e.id;
deba@1189	2098	}
deba@1189	2099
deba@1189	2100	};
deba@1189	2101
deba@1189	2102	typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
deba@1189	2103
deba@1189	2104
deba@1189	2105	/// \addtogroup graphs
deba@1189	2106	/// @{
deba@1189	2107
deba@1189	2108	///A general undirected graph structure.
deba@1189	2109
deba@1189	2110	///\ref ListBpGraph is a versatile and fast undirected graph
deba@1189	2111	///implementation based on linked lists that are stored in
deba@1189	2112	///\c std::vector structures.
deba@1189	2113	///
deba@1189	2114	///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
deba@1189	2115	///and it also provides several useful additional functionalities.
deba@1189	2116	///Most of its member functions and nested classes are documented
deba@1189	2117	///only in the concept class.
deba@1189	2118	///
deba@1189	2119	///This class provides only linear time counting for nodes, edges and arcs.
deba@1189	2120	///
deba@1189	2121	///\sa concepts::BpGraph
deba@1189	2122	///\sa ListDigraph
deba@1189	2123	class ListBpGraph : public ExtendedListBpGraphBase {
deba@1189	2124	typedef ExtendedListBpGraphBase Parent;
deba@1189	2125
deba@1189	2126	private:
deba@1189	2127	/// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
deba@1189	2128	ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {};
deba@1189	2129	/// \brief Assignment of a graph to another one is \e not allowed.
deba@1189	2130	/// Use BpGraphCopy instead.
deba@1189	2131	void operator=(const ListBpGraph &) {}
deba@1189	2132	public:
deba@1189	2133	/// Constructor
deba@1189	2134
deba@1189	2135	/// Constructor.
deba@1189	2136	///
deba@1189	2137	ListBpGraph() {}
deba@1189	2138
deba@1189	2139	typedef Parent::OutArcIt IncEdgeIt;
deba@1189	2140
deba@1189	2141	/// \brief Add a new red node to the graph.
deba@1189	2142	///
deba@1189	2143	/// This function adds a red new node to the graph.
deba@1189	2144	/// \return The new node.
deba@1193	2145	RedNode addRedNode() { return Parent::addRedNode(); }
deba@1189	2146
deba@1189	2147	/// \brief Add a new blue node to the graph.
deba@1189	2148	///
deba@1189	2149	/// This function adds a blue new node to the graph.
deba@1189	2150	/// \return The new node.
deba@1193	2151	BlueNode addBlueNode() { return Parent::addBlueNode(); }
deba@1189	2152
deba@1189	2153	/// \brief Add a new edge to the graph.
deba@1189	2154	///
deba@1189	2155	/// This function adds a new edge to the graph between nodes
deba@1189	2156	/// \c u and \c v with inherent orientation from node \c u to
deba@1189	2157	/// node \c v.
deba@1189	2158	/// \return The new edge.
deba@1193	2159	Edge addEdge(RedNode u, BlueNode v) {
deba@1193	2160	return Parent::addEdge(u, v);
deba@1193	2161	}
deba@1193	2162	Edge addEdge(BlueNode v, RedNode u) {
deba@1189	2163	return Parent::addEdge(u, v);
deba@1189	2164	}
deba@1189	2165
deba@1189	2166	///\brief Erase a node from the graph.
deba@1189	2167	///
deba@1189	2168	/// This function erases the given node along with its incident arcs
deba@1189	2169	/// from the graph.
deba@1189	2170	///
deba@1189	2171	/// \note All iterators referencing the removed node or the incident
deba@1189	2172	/// edges are invalidated, of course.
deba@1189	2173	void erase(Node n) { Parent::erase(n); }
deba@1189	2174
deba@1189	2175	///\brief Erase an edge from the graph.
deba@1189	2176	///
deba@1189	2177	/// This function erases the given edge from the graph.
deba@1189	2178	///
deba@1189	2179	/// \note All iterators referencing the removed edge are invalidated,
deba@1189	2180	/// of course.
deba@1189	2181	void erase(Edge e) { Parent::erase(e); }
deba@1189	2182	/// Node validity check
deba@1189	2183
deba@1189	2184	/// This function gives back \c true if the given node is valid,
deba@1189	2185	/// i.e. it is a real node of the graph.
deba@1189	2186	///
deba@1189	2187	/// \warning A removed node could become valid again if new nodes are
deba@1189	2188	/// added to the graph.
deba@1189	2189	bool valid(Node n) const { return Parent::valid(n); }
deba@1189	2190	/// Edge validity check
deba@1189	2191
deba@1189	2192	/// This function gives back \c true if the given edge is valid,
deba@1189	2193	/// i.e. it is a real edge of the graph.
deba@1189	2194	///
deba@1189	2195	/// \warning A removed edge could become valid again if new edges are
deba@1189	2196	/// added to the graph.
deba@1189	2197	bool valid(Edge e) const { return Parent::valid(e); }
deba@1189	2198	/// Arc validity check
deba@1189	2199
deba@1189	2200	/// This function gives back \c true if the given arc is valid,
deba@1189	2201	/// i.e. it is a real arc of the graph.
deba@1189	2202	///
deba@1189	2203	/// \warning A removed arc could become valid again if new edges are
deba@1189	2204	/// added to the graph.
deba@1189	2205	bool valid(Arc a) const { return Parent::valid(a); }
deba@1189	2206
deba@1189	2207	/// \brief Change the red node of an edge.
deba@1189	2208	///
deba@1189	2209	/// This function changes the red node of the given edge \c e to \c n.
deba@1189	2210	///
deba@1189	2211	///\note \c EdgeIt and \c ArcIt iterators referencing the
deba@1189	2212	///changed edge are invalidated and all other iterators whose
deba@1189	2213	///base node is the changed node are also invalidated.
deba@1189	2214	///
deba@1189	2215	///\warning This functionality cannot be used together with the
deba@1189	2216	///Snapshot feature.
deba@1193	2217	void changeRed(Edge e, RedNode n) {
deba@1193	2218	Parent::changeRed(e, n);
deba@1189	2219	}
deba@1189	2220	/// \brief Change the blue node of an edge.
deba@1189	2221	///
deba@1189	2222	/// This function changes the blue node of the given edge \c e to \c n.
deba@1189	2223	///
deba@1189	2224	///\note \c EdgeIt iterators referencing the changed edge remain
deba@1189	2225	///valid, but \c ArcIt iterators referencing the changed edge and
deba@1189	2226	///all other iterators whose base node is the changed node are also
deba@1189	2227	///invalidated.
deba@1189	2228	///
deba@1189	2229	///\warning This functionality cannot be used together with the
deba@1189	2230	///Snapshot feature.
deba@1193	2231	void changeBlue(Edge e, BlueNode n) {
deba@1193	2232	Parent::changeBlue(e, n);
deba@1189	2233	}
deba@1189	2234
deba@1189	2235	///Clear the graph.
deba@1189	2236
deba@1189	2237	///This function erases all nodes and arcs from the graph.
deba@1189	2238	///
deba@1189	2239	///\note All iterators of the graph are invalidated, of course.
deba@1189	2240	void clear() {
deba@1189	2241	Parent::clear();
deba@1189	2242	}
deba@1189	2243
deba@1189	2244	/// Reserve memory for nodes.
deba@1189	2245
deba@1189	2246	/// Using this function, it is possible to avoid superfluous memory
deba@1189	2247	/// allocation: if you know that the graph you want to build will
deba@1189	2248	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1189	2249	/// then it is worth reserving space for this amount before starting
deba@1189	2250	/// to build the graph.
deba@1189	2251	/// \sa reserveEdge()
deba@1189	2252	void reserveNode(int n) { nodes.reserve(n); };
deba@1189	2253
deba@1189	2254	/// Reserve memory for edges.
deba@1189	2255
deba@1189	2256	/// Using this function, it is possible to avoid superfluous memory
deba@1189	2257	/// allocation: if you know that the graph you want to build will
deba@1189	2258	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1189	2259	/// then it is worth reserving space for this amount before starting
deba@1189	2260	/// to build the graph.
deba@1189	2261	/// \sa reserveNode()
deba@1189	2262	void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@1189	2263
deba@1189	2264	/// \brief Class to make a snapshot of the graph and restore
deba@1189	2265	/// it later.
deba@1189	2266	///
deba@1189	2267	/// Class to make a snapshot of the graph and restore it later.
deba@1189	2268	///
deba@1189	2269	/// The newly added nodes and edges can be removed
deba@1189	2270	/// using the restore() function.
deba@1189	2271	///
deba@1189	2272	/// \note After a state is restored, you cannot restore a later state,
deba@1189	2273	/// i.e. you cannot add the removed nodes and edges again using
deba@1189	2274	/// another Snapshot instance.
deba@1189	2275	///
deba@1189	2276	/// \warning Node and edge deletions and other modifications
deba@1189	2277	/// (e.g. changing the end-nodes of edges or contracting nodes)
deba@1189	2278	/// cannot be restored. These events invalidate the snapshot.
deba@1189	2279	/// However, the edges and nodes that were added to the graph after
deba@1189	2280	/// making the current snapshot can be removed without invalidating it.
deba@1189	2281	class Snapshot {
deba@1189	2282	protected:
deba@1189	2283
deba@1189	2284	typedef Parent::NodeNotifier NodeNotifier;
deba@1189	2285
deba@1189	2286	class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@1189	2287	public:
deba@1189	2288
deba@1189	2289	NodeObserverProxy(Snapshot& _snapshot)
deba@1189	2290	: snapshot(_snapshot) {}
deba@1189	2291
deba@1189	2292	using NodeNotifier::ObserverBase::attach;
deba@1189	2293	using NodeNotifier::ObserverBase::detach;
deba@1189	2294	using NodeNotifier::ObserverBase::attached;
deba@1189	2295
deba@1189	2296	protected:
deba@1189	2297
deba@1189	2298	virtual void add(const Node& node) {
deba@1189	2299	snapshot.addNode(node);
deba@1189	2300	}
deba@1189	2301	virtual void add(const std::vector<Node>& nodes) {
deba@1189	2302	for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@1189	2303	snapshot.addNode(nodes[i]);
deba@1189	2304	}
deba@1189	2305	}
deba@1189	2306	virtual void erase(const Node& node) {
deba@1189	2307	snapshot.eraseNode(node);
deba@1189	2308	}
deba@1189	2309	virtual void erase(const std::vector<Node>& nodes) {
deba@1189	2310	for (int i = 0; i < int(nodes.size()); ++i) {
deba@1189	2311	snapshot.eraseNode(nodes[i]);
deba@1189	2312	}
deba@1189	2313	}
deba@1189	2314	virtual void build() {
deba@1189	2315	Node node;
deba@1189	2316	std::vector<Node> nodes;
deba@1189	2317	for (notifier()->first(node); node != INVALID;
deba@1189	2318	notifier()->next(node)) {
deba@1189	2319	nodes.push_back(node);
deba@1189	2320	}
deba@1189	2321	for (int i = nodes.size() - 1; i >= 0; --i) {
deba@1189	2322	snapshot.addNode(nodes[i]);
deba@1189	2323	}
deba@1189	2324	}
deba@1189	2325	virtual void clear() {
deba@1189	2326	Node node;
deba@1189	2327	for (notifier()->first(node); node != INVALID;
deba@1189	2328	notifier()->next(node)) {
deba@1189	2329	snapshot.eraseNode(node);
deba@1189	2330	}
deba@1189	2331	}
deba@1189	2332
deba@1189	2333	Snapshot& snapshot;
deba@1189	2334	};
deba@1189	2335
deba@1189	2336	class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@1189	2337	public:
deba@1189	2338
deba@1189	2339	EdgeObserverProxy(Snapshot& _snapshot)
deba@1189	2340	: snapshot(_snapshot) {}
deba@1189	2341
deba@1189	2342	using EdgeNotifier::ObserverBase::attach;
deba@1189	2343	using EdgeNotifier::ObserverBase::detach;
deba@1189	2344	using EdgeNotifier::ObserverBase::attached;
deba@1189	2345
deba@1189	2346	protected:
deba@1189	2347
deba@1189	2348	virtual void add(const Edge& edge) {
deba@1189	2349	snapshot.addEdge(edge);
deba@1189	2350	}
deba@1189	2351	virtual void add(const std::vector<Edge>& edges) {
deba@1189	2352	for (int i = edges.size() - 1; i >= 0; ++i) {
deba@1189	2353	snapshot.addEdge(edges[i]);
deba@1189	2354	}
deba@1189	2355	}
deba@1189	2356	virtual void erase(const Edge& edge) {
deba@1189	2357	snapshot.eraseEdge(edge);
deba@1189	2358	}
deba@1189	2359	virtual void erase(const std::vector<Edge>& edges) {
deba@1189	2360	for (int i = 0; i < int(edges.size()); ++i) {
deba@1189	2361	snapshot.eraseEdge(edges[i]);
deba@1189	2362	}
deba@1189	2363	}
deba@1189	2364	virtual void build() {
deba@1189	2365	Edge edge;
deba@1189	2366	std::vector<Edge> edges;
deba@1189	2367	for (notifier()->first(edge); edge != INVALID;
deba@1189	2368	notifier()->next(edge)) {
deba@1189	2369	edges.push_back(edge);
deba@1189	2370	}
deba@1189	2371	for (int i = edges.size() - 1; i >= 0; --i) {
deba@1189	2372	snapshot.addEdge(edges[i]);
deba@1189	2373	}
deba@1189	2374	}
deba@1189	2375	virtual void clear() {
deba@1189	2376	Edge edge;
deba@1189	2377	for (notifier()->first(edge); edge != INVALID;
deba@1189	2378	notifier()->next(edge)) {
deba@1189	2379	snapshot.eraseEdge(edge);
deba@1189	2380	}
deba@1189	2381	}
deba@1189	2382
deba@1189	2383	Snapshot& snapshot;
deba@1189	2384	};
deba@1189	2385
deba@1189	2386	ListBpGraph *graph;
deba@1189	2387
deba@1189	2388	NodeObserverProxy node_observer_proxy;
deba@1189	2389	EdgeObserverProxy edge_observer_proxy;
deba@1189	2390
deba@1189	2391	std::list<Node> added_nodes;
deba@1189	2392	std::list<Edge> added_edges;
deba@1189	2393
deba@1189	2394
deba@1189	2395	void addNode(const Node& node) {
deba@1189	2396	added_nodes.push_front(node);
deba@1189	2397	}
deba@1189	2398	void eraseNode(const Node& node) {
deba@1189	2399	std::list<Node>::iterator it =
deba@1189	2400	std::find(added_nodes.begin(), added_nodes.end(), node);
deba@1189	2401	if (it == added_nodes.end()) {
deba@1189	2402	clear();
deba@1189	2403	edge_observer_proxy.detach();
deba@1189	2404	throw NodeNotifier::ImmediateDetach();
deba@1189	2405	} else {
deba@1189	2406	added_nodes.erase(it);
deba@1189	2407	}
deba@1189	2408	}
deba@1189	2409
deba@1189	2410	void addEdge(const Edge& edge) {
deba@1189	2411	added_edges.push_front(edge);
deba@1189	2412	}
deba@1189	2413	void eraseEdge(const Edge& edge) {
deba@1189	2414	std::list<Edge>::iterator it =
deba@1189	2415	std::find(added_edges.begin(), added_edges.end(), edge);
deba@1189	2416	if (it == added_edges.end()) {
deba@1189	2417	clear();
deba@1189	2418	node_observer_proxy.detach();
deba@1189	2419	throw EdgeNotifier::ImmediateDetach();
deba@1189	2420	} else {
deba@1189	2421	added_edges.erase(it);
deba@1189	2422	}
deba@1189	2423	}
deba@1189	2424
deba@1189	2425	void attach(ListBpGraph &_graph) {
deba@1189	2426	graph = &_graph;
deba@1189	2427	node_observer_proxy.attach(graph->notifier(Node()));
deba@1189	2428	edge_observer_proxy.attach(graph->notifier(Edge()));
deba@1189	2429	}
deba@1189	2430
deba@1189	2431	void detach() {
deba@1189	2432	node_observer_proxy.detach();
deba@1189	2433	edge_observer_proxy.detach();
deba@1189	2434	}
deba@1189	2435
deba@1189	2436	bool attached() const {
deba@1189	2437	return node_observer_proxy.attached();
deba@1189	2438	}
deba@1189	2439
deba@1189	2440	void clear() {
deba@1189	2441	added_nodes.clear();
deba@1189	2442	added_edges.clear();
deba@1189	2443	}
deba@1189	2444
deba@1189	2445	public:
deba@1189	2446
deba@1189	2447	/// \brief Default constructor.
deba@1189	2448	///
deba@1189	2449	/// Default constructor.
deba@1189	2450	/// You have to call save() to actually make a snapshot.
deba@1189	2451	Snapshot()
deba@1189	2452	: graph(0), node_observer_proxy(*this),
deba@1189	2453	edge_observer_proxy(*this) {}
deba@1189	2454
deba@1189	2455	/// \brief Constructor that immediately makes a snapshot.
deba@1189	2456	///
deba@1189	2457	/// This constructor immediately makes a snapshot of the given graph.
deba@1189	2458	Snapshot(ListBpGraph &gr)
deba@1189	2459	: node_observer_proxy(*this),
deba@1189	2460	edge_observer_proxy(*this) {
deba@1189	2461	attach(gr);
deba@1189	2462	}
deba@1189	2463
deba@1189	2464	/// \brief Make a snapshot.
deba@1189	2465	///
deba@1189	2466	/// This function makes a snapshot of the given graph.
deba@1189	2467	/// It can be called more than once. In case of a repeated
deba@1189	2468	/// call, the previous snapshot gets lost.
deba@1189	2469	void save(ListBpGraph &gr) {
deba@1189	2470	if (attached()) {
deba@1189	2471	detach();
deba@1189	2472	clear();
deba@1189	2473	}
deba@1189	2474	attach(gr);
deba@1189	2475	}
deba@1189	2476
deba@1189	2477	/// \brief Undo the changes until the last snapshot.
deba@1189	2478	///
deba@1189	2479	/// This function undos the changes until the last snapshot
deba@1189	2480	/// created by save() or Snapshot(ListBpGraph&).
deba@1189	2481	///
deba@1189	2482	/// \warning This method invalidates the snapshot, i.e. repeated
deba@1189	2483	/// restoring is not supported unless you call save() again.
deba@1189	2484	void restore() {
deba@1189	2485	detach();
deba@1189	2486	for(std::list<Edge>::iterator it = added_edges.begin();
deba@1189	2487	it != added_edges.end(); ++it) {
deba@1189	2488	graph->erase(*it);
deba@1189	2489	}
deba@1189	2490	for(std::list<Node>::iterator it = added_nodes.begin();
deba@1189	2491	it != added_nodes.end(); ++it) {
deba@1189	2492	graph->erase(*it);
deba@1189	2493	}
deba@1189	2494	clear();
deba@1189	2495	}
deba@1189	2496
deba@1189	2497	/// \brief Returns \c true if the snapshot is valid.
deba@1189	2498	///
deba@1189	2499	/// This function returns \c true if the snapshot is valid.
deba@1189	2500	bool valid() const {
deba@1189	2501	return attached();
deba@1189	2502	}
deba@1189	2503	};
deba@1189	2504	};
deba@1189	2505
deba@1189	2506	/// @}
deba@57	2507	} //namespace lemon
alpar@209	2508
deba@57	2509
deba@57	2510	#endif

author	Alpar Juttner <alpar@cs.elte.hu>
	Sat, 20 Mar 2010 11:03:12 +0100
changeset 1211	1bafdbd2fc46
parent 1189	a12cca3ad15a
child 1217	7bf489cf624e
permissions	-rw-r--r--