lemon: lemon/smart_graph.h@4c89e925cfe2 (annotated)

alpar@209	1	/* -- mode: C++; indent-tabs-mode: nil; --
deba@109	2	*
alpar@209	3	* This file is a part of LEMON, a generic C++ optimization library.
deba@109	4	*
alpar@956	5	* Copyright (C) 2003-2010
deba@109	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@109	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@109	8	*
deba@109	9	* Permission to use, modify and distribute this software is granted
deba@109	10	* provided that this copyright notice appears in all copies. For
deba@109	11	* precise terms see the accompanying LICENSE file.
deba@109	12	*
deba@109	13	* This software is provided "AS IS" with no warranty of any kind,
deba@109	14	* express or implied, and with no claim as to its suitability for any
deba@109	15	* purpose.
deba@109	16	*
deba@109	17	*/
deba@109	18
deba@109	19	#ifndef LEMON_SMART_GRAPH_H
deba@109	20	#define LEMON_SMART_GRAPH_H
deba@109	21
deba@109	22	///\ingroup graphs
deba@109	23	///\file
deba@109	24	///\brief SmartDigraph and SmartGraph classes.
deba@109	25
deba@109	26	#include <vector>
deba@109	27
deba@220	28	#include <lemon/core.h>
deba@109	29	#include <lemon/error.h>
deba@109	30	#include <lemon/bits/graph_extender.h>
deba@109	31
deba@109	32	namespace lemon {
deba@109	33
deba@109	34	class SmartDigraph;
deba@109	35
deba@109	36	class SmartDigraphBase {
deba@109	37	protected:
deba@109	38
alpar@209	39	struct NodeT
deba@109	40	{
alpar@209	41	int first_in, first_out;
deba@109	42	NodeT() {}
deba@109	43	};
alpar@209	44	struct ArcT
deba@109	45	{
alpar@209	46	int target, source, next_in, next_out;
alpar@209	47	ArcT() {}
deba@109	48	};
deba@109	49
deba@109	50	std::vector<NodeT> nodes;
deba@109	51	std::vector<ArcT> arcs;
alpar@209	52
deba@109	53	public:
deba@109	54
kpeter@664	55	typedef SmartDigraphBase Digraph;
deba@109	56
deba@109	57	class Node;
deba@109	58	class Arc;
deba@109	59
deba@109	60	public:
deba@109	61
deba@109	62	SmartDigraphBase() : nodes(), arcs() { }
alpar@209	63	SmartDigraphBase(const SmartDigraphBase &_g)
deba@109	64	: nodes(_g.nodes), arcs(_g.arcs) { }
alpar@209	65
deba@109	66	typedef True NodeNumTag;
kpeter@372	67	typedef True ArcNumTag;
deba@109	68
deba@109	69	int nodeNum() const { return nodes.size(); }
deba@109	70	int arcNum() const { return arcs.size(); }
deba@109	71
deba@109	72	int maxNodeId() const { return nodes.size()-1; }
deba@109	73	int maxArcId() const { return arcs.size()-1; }
deba@109	74
deba@109	75	Node addNode() {
alpar@209	76	int n = nodes.size();
deba@109	77	nodes.push_back(NodeT());
deba@109	78	nodes[n].first_in = -1;
deba@109	79	nodes[n].first_out = -1;
deba@109	80	return Node(n);
deba@109	81	}
alpar@209	82
deba@109	83	Arc addArc(Node u, Node v) {
alpar@209	84	int n = arcs.size();
deba@109	85	arcs.push_back(ArcT());
alpar@209	86	arcs[n].source = u._id;
deba@109	87	arcs[n].target = v._id;
deba@109	88	arcs[n].next_out = nodes[u._id].first_out;
deba@109	89	arcs[n].next_in = nodes[v._id].first_in;
deba@109	90	nodes[u._id].first_out = nodes[v._id].first_in = n;
deba@109	91
deba@109	92	return Arc(n);
deba@109	93	}
deba@109	94
deba@109	95	void clear() {
deba@109	96	arcs.clear();
deba@109	97	nodes.clear();
deba@109	98	}
deba@109	99
deba@109	100	Node source(Arc a) const { return Node(arcs[a._id].source); }
deba@109	101	Node target(Arc a) const { return Node(arcs[a._id].target); }
deba@109	102
deba@109	103	static int id(Node v) { return v._id; }
deba@109	104	static int id(Arc a) { return a._id; }
deba@109	105
deba@109	106	static Node nodeFromId(int id) { return Node(id);}
deba@109	107	static Arc arcFromId(int id) { return Arc(id);}
deba@109	108
alpar@209	109	bool valid(Node n) const {
alpar@209	110	return n._id >= 0 && n._id < static_cast<int>(nodes.size());
deba@149	111	}
alpar@209	112	bool valid(Arc a) const {
alpar@209	113	return a._id >= 0 && a._id < static_cast<int>(arcs.size());
deba@149	114	}
deba@149	115
deba@109	116	class Node {
deba@109	117	friend class SmartDigraphBase;
deba@109	118	friend class SmartDigraph;
deba@109	119
deba@109	120	protected:
deba@109	121	int _id;
deba@109	122	explicit Node(int id) : _id(id) {}
deba@109	123	public:
deba@109	124	Node() {}
deba@109	125	Node (Invalid) : _id(-1) {}
deba@109	126	bool operator==(const Node i) const {return _id == i._id;}
deba@109	127	bool operator!=(const Node i) const {return _id != i._id;}
deba@109	128	bool operator<(const Node i) const {return _id < i._id;}
deba@109	129	};
alpar@209	130
deba@109	131
deba@109	132	class Arc {
deba@109	133	friend class SmartDigraphBase;
deba@109	134	friend class SmartDigraph;
deba@109	135
deba@109	136	protected:
deba@109	137	int _id;
deba@109	138	explicit Arc(int id) : _id(id) {}
deba@109	139	public:
deba@109	140	Arc() { }
deba@109	141	Arc (Invalid) : _id(-1) {}
deba@109	142	bool operator==(const Arc i) const {return _id == i._id;}
deba@109	143	bool operator!=(const Arc i) const {return _id != i._id;}
deba@109	144	bool operator<(const Arc i) const {return _id < i._id;}
deba@109	145	};
deba@109	146
deba@109	147	void first(Node& node) const {
deba@109	148	node._id = nodes.size() - 1;
deba@109	149	}
deba@109	150
deba@109	151	static void next(Node& node) {
deba@109	152	--node._id;
deba@109	153	}
deba@109	154
deba@109	155	void first(Arc& arc) const {
deba@109	156	arc._id = arcs.size() - 1;
deba@109	157	}
deba@109	158
deba@109	159	static void next(Arc& arc) {
deba@109	160	--arc._id;
deba@109	161	}
deba@109	162
deba@109	163	void firstOut(Arc& arc, const Node& node) const {
deba@109	164	arc._id = nodes[node._id].first_out;
deba@109	165	}
deba@109	166
deba@109	167	void nextOut(Arc& arc) const {
deba@109	168	arc._id = arcs[arc._id].next_out;
deba@109	169	}
deba@109	170
deba@109	171	void firstIn(Arc& arc, const Node& node) const {
deba@109	172	arc._id = nodes[node._id].first_in;
deba@109	173	}
alpar@209	174
deba@109	175	void nextIn(Arc& arc) const {
deba@109	176	arc._id = arcs[arc._id].next_in;
deba@109	177	}
deba@109	178
deba@109	179	};
deba@109	180
deba@109	181	typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
deba@109	182
deba@109	183	///\ingroup graphs
deba@109	184	///
deba@109	185	///\brief A smart directed graph class.
deba@109	186	///
kpeter@782	187	///\ref SmartDigraph is a simple and fast digraph implementation.
kpeter@782	188	///It is also quite memory efficient but at the price
alpar@956	189	///that it does not support node and arc deletion
kpeter@782	190	///(except for the Snapshot feature).
deba@109	191	///
kpeter@782	192	///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
kpeter@782	193	///and it also provides some additional functionalities.
kpeter@782	194	///Most of its member functions and nested classes are documented
kpeter@782	195	///only in the concept class.
kpeter@782	196	///
kpeter@834	197	///This class provides constant time counting for nodes and arcs.
kpeter@834	198	///
kpeter@782	199	///\sa concepts::Digraph
kpeter@782	200	///\sa SmartGraph
deba@109	201	class SmartDigraph : public ExtendedSmartDigraphBase {
deba@109	202	typedef ExtendedSmartDigraphBase Parent;
deba@109	203
deba@109	204	private:
kpeter@782	205	/// Digraphs are \e not copy constructible. Use DigraphCopy instead.
deba@109	206	SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
kpeter@782	207	/// \brief Assignment of a digraph to another one is \e not allowed.
kpeter@782	208	/// Use DigraphCopy instead.
deba@109	209	void operator=(const SmartDigraph &) {}
deba@109	210
deba@109	211	public:
alpar@209	212
deba@109	213	/// Constructor
alpar@209	214
deba@109	215	/// Constructor.
deba@109	216	///
deba@109	217	SmartDigraph() {};
alpar@209	218
deba@109	219	///Add a new node to the digraph.
alpar@209	220
kpeter@782	221	///This function adds a new node to the digraph.
kpeter@782	222	///\return The new node.
deba@109	223	Node addNode() { return Parent::addNode(); }
alpar@209	224
deba@109	225	///Add a new arc to the digraph.
alpar@209	226
kpeter@782	227	///This function adds a new arc to the digraph with source node \c s
deba@109	228	///and target node \c t.
kpeter@606	229	///\return The new arc.
kpeter@782	230	Arc addArc(Node s, Node t) {
alpar@209	231	return Parent::addArc(s, t);
deba@109	232	}
deba@109	233
deba@149	234	/// \brief Node validity check
deba@149	235	///
kpeter@782	236	/// This function gives back \c true if the given node is valid,
kpeter@782	237	/// i.e. it is a real node of the digraph.
deba@149	238	///
deba@149	239	/// \warning A removed node (using Snapshot) could become valid again
kpeter@782	240	/// if new nodes are added to the digraph.
deba@149	241	bool valid(Node n) const { return Parent::valid(n); }
deba@149	242
deba@149	243	/// \brief Arc validity check
deba@149	244	///
kpeter@782	245	/// This function gives back \c true if the given arc is valid,
kpeter@782	246	/// i.e. it is a real arc of the digraph.
deba@149	247	///
deba@149	248	/// \warning A removed arc (using Snapshot) could become valid again
kpeter@782	249	/// if new arcs are added to the graph.
deba@149	250	bool valid(Arc a) const { return Parent::valid(a); }
deba@149	251
deba@109	252	///Split a node.
alpar@209	253
kpeter@782	254	///This function splits the given node. First, a new node is added
kpeter@782	255	///to the digraph, then the source of each outgoing arc of node \c n
kpeter@782	256	///is moved to this new node.
kpeter@782	257	///If the second parameter \c connect is \c true (this is the default
kpeter@782	258	///value), then a new arc from node \c n to the newly created node
kpeter@782	259	///is also added.
deba@109	260	///\return The newly created node.
deba@109	261	///
kpeter@782	262	///\note All iterators remain valid.
kpeter@782	263	///
deba@109	264	///\warning This functionality cannot be used together with the Snapshot
deba@109	265	///feature.
deba@109	266	Node split(Node n, bool connect = true)
deba@109	267	{
deba@109	268	Node b = addNode();
deba@109	269	nodes[b._id].first_out=nodes[n._id].first_out;
deba@109	270	nodes[n._id].first_out=-1;
kpeter@382	271	for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
kpeter@382	272	arcs[i].source=b._id;
kpeter@382	273	}
deba@109	274	if(connect) addArc(n,b);
deba@109	275	return b;
deba@109	276	}
deba@109	277
kpeter@782	278	///Clear the digraph.
kpeter@782	279
kpeter@782	280	///This function erases all nodes and arcs from the digraph.
kpeter@782	281	///
kpeter@782	282	void clear() {
kpeter@782	283	Parent::clear();
kpeter@782	284	}
kpeter@782	285
kpeter@782	286	/// Reserve memory for nodes.
kpeter@782	287
kpeter@782	288	/// Using this function, it is possible to avoid superfluous memory
kpeter@782	289	/// allocation: if you know that the digraph you want to build will
kpeter@782	290	/// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@782	291	/// then it is worth reserving space for this amount before starting
kpeter@782	292	/// to build the digraph.
kpeter@782	293	/// \sa reserveArc()
kpeter@782	294	void reserveNode(int n) { nodes.reserve(n); };
kpeter@782	295
kpeter@782	296	/// Reserve memory for arcs.
kpeter@782	297
kpeter@782	298	/// Using this function, it is possible to avoid superfluous memory
kpeter@782	299	/// allocation: if you know that the digraph you want to build will
kpeter@782	300	/// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@782	301	/// then it is worth reserving space for this amount before starting
kpeter@782	302	/// to build the digraph.
kpeter@782	303	/// \sa reserveNode()
kpeter@782	304	void reserveArc(int m) { arcs.reserve(m); };
kpeter@782	305
deba@109	306	public:
alpar@209	307
deba@109	308	class Snapshot;
deba@109	309
deba@109	310	protected:
deba@109	311
deba@109	312	void restoreSnapshot(const Snapshot &s)
deba@109	313	{
deba@109	314	while(s.arc_num<arcs.size()) {
deba@109	315	Arc arc = arcFromId(arcs.size()-1);
alpar@209	316	Parent::notifier(Arc()).erase(arc);
alpar@209	317	nodes[arcs.back().source].first_out=arcs.back().next_out;
alpar@209	318	nodes[arcs.back().target].first_in=arcs.back().next_in;
alpar@209	319	arcs.pop_back();
deba@109	320	}
deba@109	321	while(s.node_num<nodes.size()) {
deba@109	322	Node node = nodeFromId(nodes.size()-1);
alpar@209	323	Parent::notifier(Node()).erase(node);
alpar@209	324	nodes.pop_back();
deba@109	325	}
alpar@209	326	}
deba@109	327
deba@109	328	public:
deba@109	329
kpeter@782	330	///Class to make a snapshot of the digraph and to restore it later.
deba@109	331
kpeter@782	332	///Class to make a snapshot of the digraph and to restore it later.
deba@109	333	///
deba@109	334	///The newly added nodes and arcs can be removed using the
kpeter@782	335	///restore() function. This is the only way for deleting nodes and/or
kpeter@782	336	///arcs from a SmartDigraph structure.
deba@109	337	///
alpar@956	338	///\note After a state is restored, you cannot restore a later state,
kpeter@782	339	///i.e. you cannot add the removed nodes and arcs again using
kpeter@782	340	///another Snapshot instance.
kpeter@782	341	///
kpeter@782	342	///\warning Node splitting cannot be restored.
kpeter@782	343	///\warning The validity of the snapshot is not stored due to
kpeter@782	344	///performance reasons. If you do not use the snapshot correctly,
kpeter@782	345	///it can cause broken program, invalid or not restored state of
kpeter@782	346	///the digraph or no change.
alpar@209	347	class Snapshot
deba@109	348	{
deba@109	349	SmartDigraph *_graph;
deba@109	350	protected:
deba@109	351	friend class SmartDigraph;
deba@109	352	unsigned int node_num;
deba@109	353	unsigned int arc_num;
deba@109	354	public:
deba@109	355	///Default constructor.
alpar@209	356
deba@109	357	///Default constructor.
kpeter@782	358	///You have to call save() to actually make a snapshot.
deba@109	359	Snapshot() : _graph(0) {}
deba@109	360	///Constructor that immediately makes a snapshot
alpar@209	361
kpeter@782	362	///This constructor immediately makes a snapshot of the given digraph.
kpeter@782	363	///
kpeter@782	364	Snapshot(SmartDigraph &gr) : _graph(&gr) {
alpar@209	365	node_num=_graph->nodes.size();
alpar@209	366	arc_num=_graph->arcs.size();
deba@109	367	}
deba@109	368
deba@109	369	///Make a snapshot.
deba@109	370
kpeter@782	371	///This function makes a snapshot of the given digraph.
kpeter@782	372	///It can be called more than once. In case of a repeated
deba@109	373	///call, the previous snapshot gets lost.
kpeter@782	374	void save(SmartDigraph &gr) {
kpeter@782	375	_graph=&gr;
alpar@209	376	node_num=_graph->nodes.size();
alpar@209	377	arc_num=_graph->arcs.size();
deba@109	378	}
deba@109	379
deba@109	380	///Undo the changes until a snapshot.
alpar@209	381
kpeter@782	382	///This function undos the changes until the last snapshot
kpeter@782	383	///created by save() or Snapshot(SmartDigraph&).
deba@109	384	void restore()
deba@109	385	{
alpar@209	386	_graph->restoreSnapshot(*this);
deba@109	387	}
deba@109	388	};
deba@109	389	};
deba@109	390
deba@109	391
deba@109	392	class SmartGraphBase {
deba@109	393
deba@109	394	protected:
deba@109	395
deba@109	396	struct NodeT {
deba@109	397	int first_out;
deba@109	398	};
alpar@209	399
deba@109	400	struct ArcT {
deba@109	401	int target;
deba@109	402	int next_out;
deba@109	403	};
deba@109	404
deba@109	405	std::vector<NodeT> nodes;
deba@109	406	std::vector<ArcT> arcs;
deba@109	407
deba@109	408	public:
alpar@209	409
kpeter@664	410	typedef SmartGraphBase Graph;
deba@109	411
deba@109	412	class Node;
deba@109	413	class Arc;
deba@109	414	class Edge;
alpar@209	415
deba@109	416	class Node {
deba@109	417	friend class SmartGraphBase;
deba@109	418	protected:
deba@109	419
deba@109	420	int _id;
deba@109	421	explicit Node(int id) { _id = id;}
deba@109	422
deba@109	423	public:
deba@109	424	Node() {}
deba@109	425	Node (Invalid) { _id = -1; }
deba@109	426	bool operator==(const Node& node) const {return _id == node._id;}
deba@109	427	bool operator!=(const Node& node) const {return _id != node._id;}
deba@109	428	bool operator<(const Node& node) const {return _id < node._id;}
deba@109	429	};
deba@109	430
deba@109	431	class Edge {
deba@109	432	friend class SmartGraphBase;
deba@109	433	protected:
deba@109	434
deba@109	435	int _id;
deba@109	436	explicit Edge(int id) { _id = id;}
deba@109	437
deba@109	438	public:
deba@109	439	Edge() {}
deba@109	440	Edge (Invalid) { _id = -1; }
deba@109	441	bool operator==(const Edge& arc) const {return _id == arc._id;}
deba@109	442	bool operator!=(const Edge& arc) const {return _id != arc._id;}
deba@109	443	bool operator<(const Edge& arc) const {return _id < arc._id;}
deba@109	444	};
deba@109	445
deba@109	446	class Arc {
deba@109	447	friend class SmartGraphBase;
deba@109	448	protected:
deba@109	449
deba@109	450	int _id;
deba@109	451	explicit Arc(int id) { _id = id;}
deba@109	452
deba@109	453	public:
kpeter@341	454	operator Edge() const {
kpeter@341	455	return _id != -1 ? edgeFromId(_id / 2) : INVALID;
deba@238	456	}
deba@109	457
deba@109	458	Arc() {}
deba@109	459	Arc (Invalid) { _id = -1; }
deba@109	460	bool operator==(const Arc& arc) const {return _id == arc._id;}
deba@109	461	bool operator!=(const Arc& arc) const {return _id != arc._id;}
deba@109	462	bool operator<(const Arc& arc) const {return _id < arc._id;}
deba@109	463	};
deba@109	464
deba@109	465
deba@109	466
deba@109	467	SmartGraphBase()
deba@109	468	: nodes(), arcs() {}
deba@109	469
kpeter@380	470	typedef True NodeNumTag;
kpeter@380	471	typedef True EdgeNumTag;
kpeter@380	472	typedef True ArcNumTag;
kpeter@380	473
kpeter@380	474	int nodeNum() const { return nodes.size(); }
kpeter@380	475	int edgeNum() const { return arcs.size() / 2; }
kpeter@380	476	int arcNum() const { return arcs.size(); }
alpar@209	477
alpar@209	478	int maxNodeId() const { return nodes.size()-1; }
deba@109	479	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@109	480	int maxArcId() const { return arcs.size()-1; }
deba@109	481
deba@109	482	Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
deba@109	483	Node target(Arc e) const { return Node(arcs[e._id].target); }
deba@109	484
deba@125	485	Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
deba@125	486	Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
deba@109	487
deba@109	488	static bool direction(Arc e) {
deba@109	489	return (e._id & 1) == 1;
deba@109	490	}
deba@109	491
deba@109	492	static Arc direct(Edge e, bool d) {
deba@109	493	return Arc(e._id * 2 + (d ? 1 : 0));
deba@109	494	}
deba@109	495
alpar@209	496	void first(Node& node) const {
deba@109	497	node._id = nodes.size() - 1;
deba@109	498	}
deba@109	499
kpeter@825	500	static void next(Node& node) {
deba@109	501	--node._id;
deba@109	502	}
deba@109	503
alpar@209	504	void first(Arc& arc) const {
deba@109	505	arc._id = arcs.size() - 1;
deba@109	506	}
deba@109	507
kpeter@825	508	static void next(Arc& arc) {
deba@109	509	--arc._id;
deba@109	510	}
deba@109	511
alpar@209	512	void first(Edge& arc) const {
deba@109	513	arc._id = arcs.size() / 2 - 1;
deba@109	514	}
deba@109	515
kpeter@825	516	static void next(Edge& arc) {
deba@109	517	--arc._id;
deba@109	518	}
deba@109	519
deba@109	520	void firstOut(Arc &arc, const Node& v) const {
deba@109	521	arc._id = nodes[v._id].first_out;
deba@109	522	}
deba@109	523	void nextOut(Arc &arc) const {
deba@109	524	arc._id = arcs[arc._id].next_out;
deba@109	525	}
deba@109	526
deba@109	527	void firstIn(Arc &arc, const Node& v) const {
deba@109	528	arc._id = ((nodes[v._id].first_out) ^ 1);
deba@109	529	if (arc._id == -2) arc._id = -1;
deba@109	530	}
deba@109	531	void nextIn(Arc &arc) const {
deba@109	532	arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
deba@109	533	if (arc._id == -2) arc._id = -1;
deba@109	534	}
deba@109	535
deba@109	536	void firstInc(Edge &arc, bool& d, const Node& v) const {
deba@109	537	int de = nodes[v._id].first_out;
deba@109	538	if (de != -1) {
deba@109	539	arc._id = de / 2;
deba@109	540	d = ((de & 1) == 1);
deba@109	541	} else {
deba@109	542	arc._id = -1;
deba@109	543	d = true;
deba@109	544	}
deba@109	545	}
deba@109	546	void nextInc(Edge &arc, bool& d) const {
deba@109	547	int de = (arcs[(arc._id * 2) \| (d ? 1 : 0)].next_out);
deba@109	548	if (de != -1) {
deba@109	549	arc._id = de / 2;
deba@109	550	d = ((de & 1) == 1);
deba@109	551	} else {
deba@109	552	arc._id = -1;
alpar@209	553	d = true;
deba@109	554	}
deba@109	555	}
alpar@209	556
deba@109	557	static int id(Node v) { return v._id; }
deba@109	558	static int id(Arc e) { return e._id; }
deba@109	559	static int id(Edge e) { return e._id; }
deba@109	560
deba@109	561	static Node nodeFromId(int id) { return Node(id);}
deba@109	562	static Arc arcFromId(int id) { return Arc(id);}
deba@109	563	static Edge edgeFromId(int id) { return Edge(id);}
deba@109	564
alpar@209	565	bool valid(Node n) const {
alpar@209	566	return n._id >= 0 && n._id < static_cast<int>(nodes.size());
deba@149	567	}
alpar@209	568	bool valid(Arc a) const {
deba@149	569	return a._id >= 0 && a._id < static_cast<int>(arcs.size());
deba@149	570	}
alpar@209	571	bool valid(Edge e) const {
alpar@209	572	return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
deba@149	573	}
deba@149	574
alpar@209	575	Node addNode() {
deba@109	576	int n = nodes.size();
deba@109	577	nodes.push_back(NodeT());
deba@109	578	nodes[n].first_out = -1;
alpar@209	579
deba@109	580	return Node(n);
deba@109	581	}
alpar@209	582
deba@138	583	Edge addEdge(Node u, Node v) {
deba@109	584	int n = arcs.size();
deba@109	585	arcs.push_back(ArcT());
deba@109	586	arcs.push_back(ArcT());
alpar@209	587
deba@109	588	arcs[n].target = u._id;
deba@109	589	arcs[n \| 1].target = v._id;
deba@109	590
deba@109	591	arcs[n].next_out = nodes[v._id].first_out;
deba@109	592	nodes[v._id].first_out = n;
deba@109	593
alpar@209	594	arcs[n \| 1].next_out = nodes[u._id].first_out;
deba@109	595	nodes[u._id].first_out = (n \| 1);
deba@109	596
deba@109	597	return Edge(n / 2);
deba@109	598	}
alpar@209	599
deba@109	600	void clear() {
deba@109	601	arcs.clear();
deba@109	602	nodes.clear();
deba@109	603	}
deba@109	604
deba@109	605	};
deba@109	606
deba@109	607	typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
deba@109	608
deba@109	609	/// \ingroup graphs
deba@109	610	///
deba@109	611	/// \brief A smart undirected graph class.
deba@109	612	///
kpeter@782	613	/// \ref SmartGraph is a simple and fast graph implementation.
kpeter@782	614	/// It is also quite memory efficient but at the price
alpar@956	615	/// that it does not support node and edge deletion
kpeter@782	616	/// (except for the Snapshot feature).
deba@109	617	///
kpeter@782	618	/// This type fully conforms to the \ref concepts::Graph "Graph concept"
kpeter@782	619	/// and it also provides some additional functionalities.
kpeter@782	620	/// Most of its member functions and nested classes are documented
kpeter@782	621	/// only in the concept class.
kpeter@782	622	///
kpeter@834	623	/// This class provides constant time counting for nodes, edges and arcs.
kpeter@834	624	///
kpeter@782	625	/// \sa concepts::Graph
kpeter@782	626	/// \sa SmartDigraph
deba@109	627	class SmartGraph : public ExtendedSmartGraphBase {
kpeter@664	628	typedef ExtendedSmartGraphBase Parent;
kpeter@664	629
deba@109	630	private:
kpeter@782	631	/// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@109	632	SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
kpeter@782	633	/// \brief Assignment of a graph to another one is \e not allowed.
kpeter@782	634	/// Use GraphCopy instead.
deba@109	635	void operator=(const SmartGraph &) {}
deba@109	636
deba@109	637	public:
deba@109	638
deba@109	639	/// Constructor
alpar@209	640
deba@109	641	/// Constructor.
deba@109	642	///
deba@109	643	SmartGraph() {}
deba@109	644
kpeter@782	645	/// \brief Add a new node to the graph.
kpeter@782	646	///
kpeter@782	647	/// This function adds a new node to the graph.
kpeter@606	648	/// \return The new node.
deba@109	649	Node addNode() { return Parent::addNode(); }
alpar@209	650
kpeter@782	651	/// \brief Add a new edge to the graph.
kpeter@782	652	///
kpeter@782	653	/// This function adds a new edge to the graph between nodes
kpeter@782	654	/// \c u and \c v with inherent orientation from node \c u to
kpeter@782	655	/// node \c v.
kpeter@782	656	/// \return The new edge.
kpeter@782	657	Edge addEdge(Node u, Node v) {
kpeter@782	658	return Parent::addEdge(u, v);
deba@109	659	}
deba@109	660
deba@149	661	/// \brief Node validity check
deba@149	662	///
kpeter@782	663	/// This function gives back \c true if the given node is valid,
kpeter@782	664	/// i.e. it is a real node of the graph.
deba@149	665	///
deba@149	666	/// \warning A removed node (using Snapshot) could become valid again
kpeter@782	667	/// if new nodes are added to the graph.
deba@149	668	bool valid(Node n) const { return Parent::valid(n); }
deba@149	669
kpeter@782	670	/// \brief Edge validity check
kpeter@782	671	///
kpeter@782	672	/// This function gives back \c true if the given edge is valid,
kpeter@782	673	/// i.e. it is a real edge of the graph.
kpeter@782	674	///
kpeter@782	675	/// \warning A removed edge (using Snapshot) could become valid again
kpeter@782	676	/// if new edges are added to the graph.
kpeter@782	677	bool valid(Edge e) const { return Parent::valid(e); }
kpeter@782	678
deba@149	679	/// \brief Arc validity check
deba@149	680	///
kpeter@782	681	/// This function gives back \c true if the given arc is valid,
kpeter@782	682	/// i.e. it is a real arc of the graph.
deba@149	683	///
deba@149	684	/// \warning A removed arc (using Snapshot) could become valid again
kpeter@782	685	/// if new edges are added to the graph.
deba@149	686	bool valid(Arc a) const { return Parent::valid(a); }
deba@149	687
deba@109	688	///Clear the graph.
alpar@209	689
kpeter@782	690	///This function erases all nodes and arcs from the graph.
deba@109	691	///
deba@109	692	void clear() {
deba@109	693	Parent::clear();
deba@109	694	}
deba@109	695
kpeter@783	696	/// Reserve memory for nodes.
kpeter@783	697
kpeter@783	698	/// Using this function, it is possible to avoid superfluous memory
kpeter@783	699	/// allocation: if you know that the graph you want to build will
kpeter@783	700	/// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@783	701	/// then it is worth reserving space for this amount before starting
kpeter@783	702	/// to build the graph.
kpeter@783	703	/// \sa reserveEdge()
kpeter@783	704	void reserveNode(int n) { nodes.reserve(n); };
kpeter@783	705
kpeter@783	706	/// Reserve memory for edges.
kpeter@783	707
kpeter@783	708	/// Using this function, it is possible to avoid superfluous memory
kpeter@783	709	/// allocation: if you know that the graph you want to build will
kpeter@783	710	/// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@783	711	/// then it is worth reserving space for this amount before starting
kpeter@783	712	/// to build the graph.
kpeter@783	713	/// \sa reserveNode()
kpeter@783	714	void reserveEdge(int m) { arcs.reserve(2 * m); };
kpeter@783	715
deba@109	716	public:
alpar@209	717
deba@109	718	class Snapshot;
deba@109	719
deba@109	720	protected:
deba@109	721
deba@109	722	void saveSnapshot(Snapshot &s)
deba@109	723	{
deba@109	724	s._graph = this;
deba@109	725	s.node_num = nodes.size();
deba@109	726	s.arc_num = arcs.size();
deba@109	727	}
deba@109	728
deba@109	729	void restoreSnapshot(const Snapshot &s)
deba@109	730	{
deba@109	731	while(s.arc_num<arcs.size()) {
deba@109	732	int n=arcs.size()-1;
deba@109	733	Edge arc=edgeFromId(n/2);
alpar@209	734	Parent::notifier(Edge()).erase(arc);
deba@109	735	std::vector<Arc> dir;
deba@109	736	dir.push_back(arcFromId(n));
deba@109	737	dir.push_back(arcFromId(n-1));
alpar@209	738	Parent::notifier(Arc()).erase(dir);
kpeter@386	739	nodes[arcs[n-1].target].first_out=arcs[n].next_out;
kpeter@386	740	nodes[arcs[n].target].first_out=arcs[n-1].next_out;
alpar@209	741	arcs.pop_back();
alpar@209	742	arcs.pop_back();
deba@109	743	}
deba@109	744	while(s.node_num<nodes.size()) {
deba@109	745	int n=nodes.size()-1;
deba@109	746	Node node = nodeFromId(n);
alpar@209	747	Parent::notifier(Node()).erase(node);
alpar@209	748	nodes.pop_back();
deba@109	749	}
alpar@209	750	}
deba@109	751
deba@109	752	public:
deba@109	753
kpeter@782	754	///Class to make a snapshot of the graph and to restore it later.
deba@109	755
kpeter@782	756	///Class to make a snapshot of the graph and to restore it later.
deba@109	757	///
kpeter@782	758	///The newly added nodes and edges can be removed using the
kpeter@782	759	///restore() function. This is the only way for deleting nodes and/or
kpeter@782	760	///edges from a SmartGraph structure.
deba@109	761	///
alpar@956	762	///\note After a state is restored, you cannot restore a later state,
kpeter@782	763	///i.e. you cannot add the removed nodes and edges again using
kpeter@782	764	///another Snapshot instance.
deba@109	765	///
kpeter@782	766	///\warning The validity of the snapshot is not stored due to
kpeter@782	767	///performance reasons. If you do not use the snapshot correctly,
kpeter@782	768	///it can cause broken program, invalid or not restored state of
kpeter@782	769	///the graph or no change.
alpar@209	770	class Snapshot
deba@109	771	{
deba@109	772	SmartGraph *_graph;
deba@109	773	protected:
deba@109	774	friend class SmartGraph;
deba@109	775	unsigned int node_num;
deba@109	776	unsigned int arc_num;
deba@109	777	public:
deba@109	778	///Default constructor.
alpar@209	779
deba@109	780	///Default constructor.
kpeter@782	781	///You have to call save() to actually make a snapshot.
deba@109	782	Snapshot() : _graph(0) {}
deba@109	783	///Constructor that immediately makes a snapshot
alpar@209	784
kpeter@782	785	/// This constructor immediately makes a snapshot of the given graph.
kpeter@782	786	///
kpeter@782	787	Snapshot(SmartGraph &gr) {
kpeter@782	788	gr.saveSnapshot(*this);
deba@109	789	}
deba@109	790
deba@109	791	///Make a snapshot.
deba@109	792
kpeter@782	793	///This function makes a snapshot of the given graph.
kpeter@782	794	///It can be called more than once. In case of a repeated
deba@109	795	///call, the previous snapshot gets lost.
kpeter@782	796	void save(SmartGraph &gr)
deba@109	797	{
kpeter@782	798	gr.saveSnapshot(*this);
deba@109	799	}
deba@109	800
kpeter@782	801	///Undo the changes until the last snapshot.
alpar@209	802
kpeter@782	803	///This function undos the changes until the last snapshot
kpeter@782	804	///created by save() or Snapshot(SmartGraph&).
deba@109	805	void restore()
deba@109	806	{
deba@109	807	_graph->restoreSnapshot(*this);
deba@109	808	}
deba@109	809	};
deba@109	810	};
alpar@209	811
deba@1187	812	class SmartBpGraphBase {
deba@1187	813
deba@1187	814	protected:
deba@1187	815
deba@1187	816	struct NodeT {
deba@1187	817	int first_out;
deba@1187	818	int partition_next;
deba@1187	819	int partition_index;
deba@1187	820	bool red;
deba@1187	821	};
deba@1187	822
deba@1187	823	struct ArcT {
deba@1187	824	int target;
deba@1187	825	int next_out;
deba@1187	826	};
deba@1187	827
deba@1187	828	std::vector<NodeT> nodes;
deba@1187	829	std::vector<ArcT> arcs;
deba@1187	830
deba@1187	831	int first_red, first_blue;
deba@1187	832
deba@1187	833	public:
deba@1187	834
deba@1187	835	typedef SmartBpGraphBase Graph;
deba@1187	836
deba@1187	837	class Node;
deba@1187	838	class Arc;
deba@1187	839	class Edge;
deba@1187	840
deba@1187	841	class Node {
deba@1187	842	friend class SmartBpGraphBase;
deba@1187	843	protected:
deba@1187	844
deba@1187	845	int _id;
deba@1187	846	explicit Node(int id) { _id = id;}
deba@1187	847
deba@1187	848	public:
deba@1187	849	Node() {}
deba@1187	850	Node (Invalid) { _id = -1; }
deba@1187	851	bool operator==(const Node& node) const {return _id == node._id;}
deba@1187	852	bool operator!=(const Node& node) const {return _id != node._id;}
deba@1187	853	bool operator<(const Node& node) const {return _id < node._id;}
deba@1187	854	};
deba@1187	855
deba@1187	856	class Edge {
deba@1187	857	friend class SmartBpGraphBase;
deba@1187	858	protected:
deba@1187	859
deba@1187	860	int _id;
deba@1187	861	explicit Edge(int id) { _id = id;}
deba@1187	862
deba@1187	863	public:
deba@1187	864	Edge() {}
deba@1187	865	Edge (Invalid) { _id = -1; }
deba@1187	866	bool operator==(const Edge& arc) const {return _id == arc._id;}
deba@1187	867	bool operator!=(const Edge& arc) const {return _id != arc._id;}
deba@1187	868	bool operator<(const Edge& arc) const {return _id < arc._id;}
deba@1187	869	};
deba@1187	870
deba@1187	871	class Arc {
deba@1187	872	friend class SmartBpGraphBase;
deba@1187	873	protected:
deba@1187	874
deba@1187	875	int _id;
deba@1187	876	explicit Arc(int id) { _id = id;}
deba@1187	877
deba@1187	878	public:
deba@1187	879	operator Edge() const {
deba@1187	880	return _id != -1 ? edgeFromId(_id / 2) : INVALID;
deba@1187	881	}
deba@1187	882
deba@1187	883	Arc() {}
deba@1187	884	Arc (Invalid) { _id = -1; }
deba@1187	885	bool operator==(const Arc& arc) const {return _id == arc._id;}
deba@1187	886	bool operator!=(const Arc& arc) const {return _id != arc._id;}
deba@1187	887	bool operator<(const Arc& arc) const {return _id < arc._id;}
deba@1187	888	};
deba@1187	889
deba@1187	890
deba@1187	891
deba@1187	892	SmartBpGraphBase()
deba@1187	893	: nodes(), arcs(), first_red(-1), first_blue(-1) {}
deba@1187	894
deba@1187	895	typedef True NodeNumTag;
deba@1187	896	typedef True EdgeNumTag;
deba@1187	897	typedef True ArcNumTag;
deba@1187	898
deba@1187	899	int nodeNum() const { return nodes.size(); }
deba@1187	900	int redNum() const {
deba@1187	901	return first_red == -1 ? 0 : nodes[first_red].partition_index + 1;
deba@1187	902	}
deba@1187	903	int blueNum() const {
deba@1187	904	return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1;
deba@1187	905	}
deba@1187	906	int edgeNum() const { return arcs.size() / 2; }
deba@1187	907	int arcNum() const { return arcs.size(); }
deba@1187	908
deba@1187	909	int maxNodeId() const { return nodes.size()-1; }
deba@1187	910	int maxRedId() const {
deba@1187	911	return first_red == -1 ? -1 : nodes[first_red].partition_index;
deba@1187	912	}
deba@1187	913	int maxBlueId() const {
deba@1187	914	return first_blue == -1 ? -1 : nodes[first_blue].partition_index;
deba@1187	915	}
deba@1187	916	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@1187	917	int maxArcId() const { return arcs.size()-1; }
deba@1187	918
deba@1187	919	bool red(Node n) const { return nodes[n._id].red; }
deba@1187	920	bool blue(Node n) const { return !nodes[n._id].red; }
deba@1187	921
deba@1187	922	Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
deba@1187	923	Node target(Arc a) const { return Node(arcs[a._id].target); }
deba@1187	924
deba@1187	925	Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
deba@1187	926	Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
deba@1187	927
deba@1187	928	Node u(Edge e) const { return redNode(e); }
deba@1187	929	Node v(Edge e) const { return blueNode(e); }
deba@1187	930
deba@1187	931	static bool direction(Arc a) {
deba@1187	932	return (a._id & 1) == 1;
deba@1187	933	}
deba@1187	934
deba@1187	935	static Arc direct(Edge e, bool d) {
deba@1187	936	return Arc(e._id * 2 + (d ? 1 : 0));
deba@1187	937	}
deba@1187	938
deba@1187	939	void first(Node& node) const {
deba@1187	940	node._id = nodes.size() - 1;
deba@1187	941	}
deba@1187	942
deba@1187	943	static void next(Node& node) {
deba@1187	944	--node._id;
deba@1187	945	}
deba@1187	946
deba@1187	947	void firstRed(Node& node) const {
deba@1187	948	node._id = first_red;
deba@1187	949	}
deba@1187	950
deba@1187	951	void nextRed(Node& node) const {
deba@1187	952	node._id = nodes[node._id].partition_next;
deba@1187	953	}
deba@1187	954
deba@1187	955	void firstBlue(Node& node) const {
deba@1187	956	node._id = first_blue;
deba@1187	957	}
deba@1187	958
deba@1187	959	void nextBlue(Node& node) const {
deba@1187	960	node._id = nodes[node._id].partition_next;
deba@1187	961	}
deba@1187	962
deba@1187	963	void first(Arc& arc) const {
deba@1187	964	arc._id = arcs.size() - 1;
deba@1187	965	}
deba@1187	966
deba@1187	967	static void next(Arc& arc) {
deba@1187	968	--arc._id;
deba@1187	969	}
deba@1187	970
deba@1187	971	void first(Edge& arc) const {
deba@1187	972	arc._id = arcs.size() / 2 - 1;
deba@1187	973	}
deba@1187	974
deba@1187	975	static void next(Edge& arc) {
deba@1187	976	--arc._id;
deba@1187	977	}
deba@1187	978
deba@1187	979	void firstOut(Arc &arc, const Node& v) const {
deba@1187	980	arc._id = nodes[v._id].first_out;
deba@1187	981	}
deba@1187	982	void nextOut(Arc &arc) const {
deba@1187	983	arc._id = arcs[arc._id].next_out;
deba@1187	984	}
deba@1187	985
deba@1187	986	void firstIn(Arc &arc, const Node& v) const {
deba@1187	987	arc._id = ((nodes[v._id].first_out) ^ 1);
deba@1187	988	if (arc._id == -2) arc._id = -1;
deba@1187	989	}
deba@1187	990	void nextIn(Arc &arc) const {
deba@1187	991	arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
deba@1187	992	if (arc._id == -2) arc._id = -1;
deba@1187	993	}
deba@1187	994
deba@1187	995	void firstInc(Edge &arc, bool& d, const Node& v) const {
deba@1187	996	int de = nodes[v._id].first_out;
deba@1187	997	if (de != -1) {
deba@1187	998	arc._id = de / 2;
deba@1187	999	d = ((de & 1) == 1);
deba@1187	1000	} else {
deba@1187	1001	arc._id = -1;
deba@1187	1002	d = true;
deba@1187	1003	}
deba@1187	1004	}
deba@1187	1005	void nextInc(Edge &arc, bool& d) const {
deba@1187	1006	int de = (arcs[(arc._id * 2) \| (d ? 1 : 0)].next_out);
deba@1187	1007	if (de != -1) {
deba@1187	1008	arc._id = de / 2;
deba@1187	1009	d = ((de & 1) == 1);
deba@1187	1010	} else {
deba@1187	1011	arc._id = -1;
deba@1187	1012	d = true;
deba@1187	1013	}
deba@1187	1014	}
deba@1187	1015
deba@1187	1016	static int id(Node v) { return v._id; }
deba@1187	1017	int redId(Node v) const {
deba@1187	1018	LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
deba@1187	1019	return nodes[v._id].partition_index;
deba@1187	1020	}
deba@1187	1021	int blueId(Node v) const {
deba@1187	1022	LEMON_DEBUG(nodes[v._id].red, "Node has to be blue");
deba@1187	1023	return nodes[v._id].partition_index;
deba@1187	1024	}
deba@1187	1025	static int id(Arc e) { return e._id; }
deba@1187	1026	static int id(Edge e) { return e._id; }
deba@1187	1027
deba@1187	1028	static Node nodeFromId(int id) { return Node(id);}
deba@1187	1029	static Arc arcFromId(int id) { return Arc(id);}
deba@1187	1030	static Edge edgeFromId(int id) { return Edge(id);}
deba@1187	1031
deba@1187	1032	bool valid(Node n) const {
deba@1187	1033	return n._id >= 0 && n._id < static_cast<int>(nodes.size());
deba@1187	1034	}
deba@1187	1035	bool valid(Arc a) const {
deba@1187	1036	return a._id >= 0 && a._id < static_cast<int>(arcs.size());
deba@1187	1037	}
deba@1187	1038	bool valid(Edge e) const {
deba@1187	1039	return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
deba@1187	1040	}
deba@1187	1041
deba@1187	1042	Node addRedNode() {
deba@1187	1043	int n = nodes.size();
deba@1187	1044	nodes.push_back(NodeT());
deba@1187	1045	nodes[n].first_out = -1;
deba@1187	1046	nodes[n].red = true;
deba@1187	1047	if (first_red == -1) {
deba@1187	1048	nodes[n].partition_index = 0;
deba@1187	1049	} else {
deba@1187	1050	nodes[n].partition_index = nodes[first_red].partition_index + 1;
deba@1187	1051	}
deba@1187	1052	nodes[n].partition_next = first_red;
deba@1187	1053	first_red = n;
deba@1187	1054
deba@1187	1055	return Node(n);
deba@1187	1056	}
deba@1187	1057
deba@1187	1058	Node addBlueNode() {
deba@1187	1059	int n = nodes.size();
deba@1187	1060	nodes.push_back(NodeT());
deba@1187	1061	nodes[n].first_out = -1;
deba@1187	1062	nodes[n].red = false;
deba@1187	1063	if (first_blue == -1) {
deba@1187	1064	nodes[n].partition_index = 0;
deba@1187	1065	} else {
deba@1187	1066	nodes[n].partition_index = nodes[first_blue].partition_index + 1;
deba@1187	1067	}
deba@1187	1068	nodes[n].partition_next = first_blue;
deba@1187	1069	first_blue = n;
deba@1187	1070
deba@1187	1071	return Node(n);
deba@1187	1072	}
deba@1187	1073
deba@1187	1074	Edge addEdge(Node u, Node v) {
deba@1187	1075	int n = arcs.size();
deba@1187	1076	arcs.push_back(ArcT());
deba@1187	1077	arcs.push_back(ArcT());
deba@1187	1078
deba@1187	1079	arcs[n].target = u._id;
deba@1187	1080	arcs[n \| 1].target = v._id;
deba@1187	1081
deba@1187	1082	arcs[n].next_out = nodes[v._id].first_out;
deba@1187	1083	nodes[v._id].first_out = n;
deba@1187	1084
deba@1187	1085	arcs[n \| 1].next_out = nodes[u._id].first_out;
deba@1187	1086	nodes[u._id].first_out = (n \| 1);
deba@1187	1087
deba@1187	1088	return Edge(n / 2);
deba@1187	1089	}
deba@1187	1090
deba@1187	1091	void clear() {
deba@1187	1092	arcs.clear();
deba@1187	1093	nodes.clear();
deba@1187	1094	first_red = -1;
deba@1187	1095	first_blue = -1;
deba@1187	1096	}
deba@1187	1097
deba@1187	1098	};
deba@1187	1099
deba@1187	1100	typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
deba@1187	1101
deba@1187	1102	/// \ingroup graphs
deba@1187	1103	///
deba@1187	1104	/// \brief A smart undirected graph class.
deba@1187	1105	///
deba@1187	1106	/// \ref SmartBpGraph is a simple and fast graph implementation.
deba@1187	1107	/// It is also quite memory efficient but at the price
deba@1187	1108	/// that it does not support node and edge deletion
deba@1187	1109	/// (except for the Snapshot feature).
deba@1187	1110	///
deba@1187	1111	/// This type fully conforms to the \ref concepts::Graph "Graph concept"
deba@1187	1112	/// and it also provides some additional functionalities.
deba@1187	1113	/// Most of its member functions and nested classes are documented
deba@1187	1114	/// only in the concept class.
deba@1187	1115	///
deba@1187	1116	/// This class provides constant time counting for nodes, edges and arcs.
deba@1187	1117	///
deba@1187	1118	/// \sa concepts::Graph
deba@1187	1119	/// \sa SmartDigraph
deba@1187	1120	class SmartBpGraph : public ExtendedSmartBpGraphBase {
deba@1187	1121	typedef ExtendedSmartBpGraphBase Parent;
deba@1187	1122
deba@1187	1123	private:
deba@1187	1124	/// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@1187	1125	SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
deba@1187	1126	/// \brief Assignment of a graph to another one is \e not allowed.
deba@1187	1127	/// Use GraphCopy instead.
deba@1187	1128	void operator=(const SmartBpGraph &) {}
deba@1187	1129
deba@1187	1130	public:
deba@1187	1131
deba@1187	1132	/// Constructor
deba@1187	1133
deba@1187	1134	/// Constructor.
deba@1187	1135	///
deba@1187	1136	SmartBpGraph() {}
deba@1187	1137
deba@1187	1138	/// \brief Add a new red node to the graph.
deba@1187	1139	///
deba@1187	1140	/// This function adds a red new node to the graph.
deba@1187	1141	/// \return The new node.
deba@1187	1142	Node addRedNode() { return Parent::addRedNode(); }
deba@1187	1143
deba@1187	1144	/// \brief Add a new blue node to the graph.
deba@1187	1145	///
deba@1187	1146	/// This function adds a blue new node to the graph.
deba@1187	1147	/// \return The new node.
deba@1187	1148	Node addBlueNode() { return Parent::addBlueNode(); }
deba@1187	1149
deba@1187	1150	/// \brief Add a new edge to the graph.
deba@1187	1151	///
deba@1187	1152	/// This function adds a new edge to the graph between nodes
deba@1187	1153	/// \c u and \c v with inherent orientation from node \c u to
deba@1187	1154	/// node \c v.
deba@1187	1155	/// \return The new edge.
deba@1187	1156	Edge addEdge(Node red, Node blue) {
deba@1187	1157	LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
deba@1187	1158	"Edge has to be formed by a red and a blue nodes");
deba@1187	1159	return Parent::addEdge(red, blue);
deba@1187	1160	}
deba@1187	1161
deba@1187	1162	/// \brief Node validity check
deba@1187	1163	///
deba@1187	1164	/// This function gives back \c true if the given node is valid,
deba@1187	1165	/// i.e. it is a real node of the graph.
deba@1187	1166	///
deba@1187	1167	/// \warning A removed node (using Snapshot) could become valid again
deba@1187	1168	/// if new nodes are added to the graph.
deba@1187	1169	bool valid(Node n) const { return Parent::valid(n); }
deba@1187	1170
deba@1187	1171	/// \brief Edge validity check
deba@1187	1172	///
deba@1187	1173	/// This function gives back \c true if the given edge is valid,
deba@1187	1174	/// i.e. it is a real edge of the graph.
deba@1187	1175	///
deba@1187	1176	/// \warning A removed edge (using Snapshot) could become valid again
deba@1187	1177	/// if new edges are added to the graph.
deba@1187	1178	bool valid(Edge e) const { return Parent::valid(e); }
deba@1187	1179
deba@1187	1180	/// \brief Arc validity check
deba@1187	1181	///
deba@1187	1182	/// This function gives back \c true if the given arc is valid,
deba@1187	1183	/// i.e. it is a real arc of the graph.
deba@1187	1184	///
deba@1187	1185	/// \warning A removed arc (using Snapshot) could become valid again
deba@1187	1186	/// if new edges are added to the graph.
deba@1187	1187	bool valid(Arc a) const { return Parent::valid(a); }
deba@1187	1188
deba@1187	1189	///Clear the graph.
deba@1187	1190
deba@1187	1191	///This function erases all nodes and arcs from the graph.
deba@1187	1192	///
deba@1187	1193	void clear() {
deba@1187	1194	Parent::clear();
deba@1187	1195	}
deba@1187	1196
deba@1187	1197	/// Reserve memory for nodes.
deba@1187	1198
deba@1187	1199	/// Using this function, it is possible to avoid superfluous memory
deba@1187	1200	/// allocation: if you know that the graph you want to build will
deba@1187	1201	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1187	1202	/// then it is worth reserving space for this amount before starting
deba@1187	1203	/// to build the graph.
deba@1187	1204	/// \sa reserveEdge()
deba@1187	1205	void reserveNode(int n) { nodes.reserve(n); };
deba@1187	1206
deba@1187	1207	/// Reserve memory for edges.
deba@1187	1208
deba@1187	1209	/// Using this function, it is possible to avoid superfluous memory
deba@1187	1210	/// allocation: if you know that the graph you want to build will
deba@1187	1211	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1187	1212	/// then it is worth reserving space for this amount before starting
deba@1187	1213	/// to build the graph.
deba@1187	1214	/// \sa reserveNode()
deba@1187	1215	void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@1187	1216
deba@1187	1217	public:
deba@1187	1218
deba@1187	1219	class Snapshot;
deba@1187	1220
deba@1187	1221	protected:
deba@1187	1222
deba@1187	1223	void saveSnapshot(Snapshot &s)
deba@1187	1224	{
deba@1187	1225	s._graph = this;
deba@1187	1226	s.node_num = nodes.size();
deba@1187	1227	s.arc_num = arcs.size();
deba@1187	1228	}
deba@1187	1229
deba@1187	1230	void restoreSnapshot(const Snapshot &s)
deba@1187	1231	{
deba@1187	1232	while(s.arc_num<arcs.size()) {
deba@1187	1233	int n=arcs.size()-1;
deba@1187	1234	Edge arc=edgeFromId(n/2);
deba@1187	1235	Parent::notifier(Edge()).erase(arc);
deba@1187	1236	std::vector<Arc> dir;
deba@1187	1237	dir.push_back(arcFromId(n));
deba@1187	1238	dir.push_back(arcFromId(n-1));
deba@1187	1239	Parent::notifier(Arc()).erase(dir);
deba@1187	1240	nodes[arcs[n-1].target].first_out=arcs[n].next_out;
deba@1187	1241	nodes[arcs[n].target].first_out=arcs[n-1].next_out;
deba@1187	1242	arcs.pop_back();
deba@1187	1243	arcs.pop_back();
deba@1187	1244	}
deba@1187	1245	while(s.node_num<nodes.size()) {
deba@1187	1246	int n=nodes.size()-1;
deba@1187	1247	Node node = nodeFromId(n);
deba@1187	1248	if (Parent::red(node)) {
deba@1187	1249	first_red = nodes[n].partition_next;
deba@1187	1250	Parent::notifier(RedNode()).erase(node);
deba@1187	1251	} else {
deba@1187	1252	first_blue = nodes[n].partition_next;
deba@1187	1253	Parent::notifier(BlueNode()).erase(node);
deba@1187	1254	}
deba@1187	1255	Parent::notifier(Node()).erase(node);
deba@1187	1256	nodes.pop_back();
deba@1187	1257	}
deba@1187	1258	}
deba@1187	1259
deba@1187	1260	public:
deba@1187	1261
deba@1187	1262	///Class to make a snapshot of the graph and to restore it later.
deba@1187	1263
deba@1187	1264	///Class to make a snapshot of the graph and to restore it later.
deba@1187	1265	///
deba@1187	1266	///The newly added nodes and edges can be removed using the
deba@1187	1267	///restore() function. This is the only way for deleting nodes and/or
deba@1187	1268	///edges from a SmartBpGraph structure.
deba@1187	1269	///
deba@1187	1270	///\note After a state is restored, you cannot restore a later state,
deba@1187	1271	///i.e. you cannot add the removed nodes and edges again using
deba@1187	1272	///another Snapshot instance.
deba@1187	1273	///
deba@1187	1274	///\warning The validity of the snapshot is not stored due to
deba@1187	1275	///performance reasons. If you do not use the snapshot correctly,
deba@1187	1276	///it can cause broken program, invalid or not restored state of
deba@1187	1277	///the graph or no change.
deba@1187	1278	class Snapshot
deba@1187	1279	{
deba@1187	1280	SmartBpGraph *_graph;
deba@1187	1281	protected:
deba@1187	1282	friend class SmartBpGraph;
deba@1187	1283	unsigned int node_num;
deba@1187	1284	unsigned int arc_num;
deba@1187	1285	public:
deba@1187	1286	///Default constructor.
deba@1187	1287
deba@1187	1288	///Default constructor.
deba@1187	1289	///You have to call save() to actually make a snapshot.
deba@1187	1290	Snapshot() : _graph(0) {}
deba@1187	1291	///Constructor that immediately makes a snapshot
deba@1187	1292
deba@1187	1293	/// This constructor immediately makes a snapshot of the given graph.
deba@1187	1294	///
deba@1187	1295	Snapshot(SmartBpGraph &gr) {
deba@1187	1296	gr.saveSnapshot(*this);
deba@1187	1297	}
deba@1187	1298
deba@1187	1299	///Make a snapshot.
deba@1187	1300
deba@1187	1301	///This function makes a snapshot of the given graph.
deba@1187	1302	///It can be called more than once. In case of a repeated
deba@1187	1303	///call, the previous snapshot gets lost.
deba@1187	1304	void save(SmartBpGraph &gr)
deba@1187	1305	{
deba@1187	1306	gr.saveSnapshot(*this);
deba@1187	1307	}
deba@1187	1308
deba@1187	1309	///Undo the changes until the last snapshot.
deba@1187	1310
deba@1187	1311	///This function undos the changes until the last snapshot
deba@1187	1312	///created by save() or Snapshot(SmartBpGraph&).
deba@1187	1313	void restore()
deba@1187	1314	{
deba@1187	1315	_graph->restoreSnapshot(*this);
deba@1187	1316	}
deba@1187	1317	};
deba@1187	1318	};
deba@1187	1319
deba@109	1320	} //namespace lemon
deba@109	1321
deba@109	1322
deba@109	1323	#endif //LEMON_SMART_GRAPH_H

author	Balazs Dezso <deba@inf.elte.hu>
	Sun, 14 Nov 2010 20:06:23 +0100
changeset 1187	4c89e925cfe2
parent 956	141f9c0db4a3
child 1188	5ef0ab7b61cd
permissions	-rw-r--r--