lemon-0.x: lemon/list_graph.h@096d83158d41 (annotated)

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

author	deba
	Fri, 02 Mar 2007 17:56:22 +0000
changeset 2385	096d83158d41
parent 2343	21587bc5922b
child 2386	81b47fc5c444
permissions	-rw-r--r--