lemon-1.3: lemon/smart_graph.h@d7e25df22e88 (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@1092	5	* Copyright (C) 2003-2013
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@617	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@360	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@735	187	///\ref SmartDigraph is a simple and fast digraph implementation.
kpeter@735	188	///It is also quite memory efficient but at the price
alpar@877	189	///that it does not support node and arc deletion
kpeter@735	190	///(except for the Snapshot feature).
deba@109	191	///
kpeter@735	192	///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
kpeter@735	193	///and it also provides some additional functionalities.
kpeter@735	194	///Most of its member functions and nested classes are documented
kpeter@735	195	///only in the concept class.
kpeter@735	196	///
kpeter@787	197	///This class provides constant time counting for nodes and arcs.
kpeter@787	198	///
kpeter@735	199	///\sa concepts::Digraph
kpeter@735	200	///\sa SmartGraph
deba@109	201	class SmartDigraph : public ExtendedSmartDigraphBase {
deba@109	202	typedef ExtendedSmartDigraphBase Parent;
deba@109	203
deba@109	204	private:
kpeter@735	205	/// Digraphs are \e not copy constructible. Use DigraphCopy instead.
deba@109	206	SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
kpeter@735	207	/// \brief Assignment of a digraph to another one is \e not allowed.
kpeter@735	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@735	221	///This function adds a new node to the digraph.
kpeter@735	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@735	227	///This function adds a new arc to the digraph with source node \c s
deba@109	228	///and target node \c t.
kpeter@559	229	///\return The new arc.
kpeter@735	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@735	236	/// This function gives back \c true if the given node is valid,
kpeter@735	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@735	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@735	245	/// This function gives back \c true if the given arc is valid,
kpeter@735	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@735	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@735	254	///This function splits the given node. First, a new node is added
kpeter@735	255	///to the digraph, then the source of each outgoing arc of node \c n
kpeter@735	256	///is moved to this new node.
kpeter@735	257	///If the second parameter \c connect is \c true (this is the default
kpeter@735	258	///value), then a new arc from node \c n to the newly created node
kpeter@735	259	///is also added.
deba@109	260	///\return The newly created node.
deba@109	261	///
kpeter@735	262	///\note All iterators remain valid.
kpeter@735	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@370	271	for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
kpeter@370	272	arcs[i].source=b._id;
kpeter@370	273	}
deba@109	274	if(connect) addArc(n,b);
deba@109	275	return b;
deba@109	276	}
deba@109	277
kpeter@735	278	///Clear the digraph.
kpeter@735	279
kpeter@735	280	///This function erases all nodes and arcs from the digraph.
kpeter@735	281	///
kpeter@735	282	void clear() {
kpeter@735	283	Parent::clear();
kpeter@735	284	}
kpeter@735	285
kpeter@735	286	/// Reserve memory for nodes.
kpeter@735	287
kpeter@735	288	/// Using this function, it is possible to avoid superfluous memory
kpeter@735	289	/// allocation: if you know that the digraph you want to build will
kpeter@735	290	/// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@735	291	/// then it is worth reserving space for this amount before starting
kpeter@735	292	/// to build the digraph.
kpeter@735	293	/// \sa reserveArc()
kpeter@735	294	void reserveNode(int n) { nodes.reserve(n); };
kpeter@735	295
kpeter@735	296	/// Reserve memory for arcs.
kpeter@735	297
kpeter@735	298	/// Using this function, it is possible to avoid superfluous memory
kpeter@735	299	/// allocation: if you know that the digraph you want to build will
kpeter@735	300	/// be large (e.g. it will contain millions of nodes and/or arcs),
kpeter@735	301	/// then it is worth reserving space for this amount before starting
kpeter@735	302	/// to build the digraph.
kpeter@735	303	/// \sa reserveNode()
kpeter@735	304	void reserveArc(int m) { arcs.reserve(m); };
kpeter@735	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@735	330	///Class to make a snapshot of the digraph and to restore it later.
deba@109	331
kpeter@735	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@735	335	///restore() function. This is the only way for deleting nodes and/or
kpeter@735	336	///arcs from a SmartDigraph structure.
deba@109	337	///
alpar@877	338	///\note After a state is restored, you cannot restore a later state,
kpeter@735	339	///i.e. you cannot add the removed nodes and arcs again using
kpeter@735	340	///another Snapshot instance.
kpeter@735	341	///
kpeter@735	342	///\warning Node splitting cannot be restored.
kpeter@735	343	///\warning The validity of the snapshot is not stored due to
kpeter@735	344	///performance reasons. If you do not use the snapshot correctly,
kpeter@735	345	///it can cause broken program, invalid or not restored state of
kpeter@735	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@735	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@735	362	///This constructor immediately makes a snapshot of the given digraph.
kpeter@735	363	///
kpeter@735	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@735	371	///This function makes a snapshot of the given digraph.
kpeter@735	372	///It can be called more than once. In case of a repeated
deba@109	373	///call, the previous snapshot gets lost.
kpeter@735	374	void save(SmartDigraph &gr) {
kpeter@735	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@735	382	///This function undos the changes until the last snapshot
kpeter@735	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@617	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@329	454	operator Edge() const {
kpeter@329	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@368	470	typedef True NodeNumTag;
kpeter@368	471	typedef True EdgeNumTag;
kpeter@368	472	typedef True ArcNumTag;
kpeter@368	473
kpeter@368	474	int nodeNum() const { return nodes.size(); }
kpeter@368	475	int edgeNum() const { return arcs.size() / 2; }
kpeter@368	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@778	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@778	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@778	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@735	613	/// \ref SmartGraph is a simple and fast graph implementation.
kpeter@735	614	/// It is also quite memory efficient but at the price
alpar@877	615	/// that it does not support node and edge deletion
kpeter@735	616	/// (except for the Snapshot feature).
deba@109	617	///
kpeter@735	618	/// This type fully conforms to the \ref concepts::Graph "Graph concept"
kpeter@735	619	/// and it also provides some additional functionalities.
kpeter@735	620	/// Most of its member functions and nested classes are documented
kpeter@735	621	/// only in the concept class.
kpeter@735	622	///
kpeter@787	623	/// This class provides constant time counting for nodes, edges and arcs.
kpeter@787	624	///
kpeter@735	625	/// \sa concepts::Graph
kpeter@735	626	/// \sa SmartDigraph
deba@109	627	class SmartGraph : public ExtendedSmartGraphBase {
kpeter@617	628	typedef ExtendedSmartGraphBase Parent;
kpeter@617	629
deba@109	630	private:
kpeter@735	631	/// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@109	632	SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
kpeter@735	633	/// \brief Assignment of a graph to another one is \e not allowed.
kpeter@735	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@735	645	/// \brief Add a new node to the graph.
kpeter@735	646	///
kpeter@735	647	/// This function adds a new node to the graph.
kpeter@559	648	/// \return The new node.
deba@109	649	Node addNode() { return Parent::addNode(); }
alpar@209	650
kpeter@735	651	/// \brief Add a new edge to the graph.
kpeter@735	652	///
kpeter@735	653	/// This function adds a new edge to the graph between nodes
kpeter@735	654	/// \c u and \c v with inherent orientation from node \c u to
kpeter@735	655	/// node \c v.
kpeter@735	656	/// \return The new edge.
kpeter@735	657	Edge addEdge(Node u, Node v) {
kpeter@735	658	return Parent::addEdge(u, v);
deba@109	659	}
deba@109	660
deba@149	661	/// \brief Node validity check
deba@149	662	///
kpeter@735	663	/// This function gives back \c true if the given node is valid,
kpeter@735	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@735	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@735	670	/// \brief Edge validity check
kpeter@735	671	///
kpeter@735	672	/// This function gives back \c true if the given edge is valid,
kpeter@735	673	/// i.e. it is a real edge of the graph.
kpeter@735	674	///
kpeter@735	675	/// \warning A removed edge (using Snapshot) could become valid again
kpeter@735	676	/// if new edges are added to the graph.
kpeter@735	677	bool valid(Edge e) const { return Parent::valid(e); }
kpeter@735	678
deba@149	679	/// \brief Arc validity check
deba@149	680	///
kpeter@735	681	/// This function gives back \c true if the given arc is valid,
kpeter@735	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@735	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@735	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@736	696	/// Reserve memory for nodes.
kpeter@736	697
kpeter@736	698	/// Using this function, it is possible to avoid superfluous memory
kpeter@736	699	/// allocation: if you know that the graph you want to build will
kpeter@736	700	/// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@736	701	/// then it is worth reserving space for this amount before starting
kpeter@736	702	/// to build the graph.
kpeter@736	703	/// \sa reserveEdge()
kpeter@736	704	void reserveNode(int n) { nodes.reserve(n); };
kpeter@736	705
kpeter@736	706	/// Reserve memory for edges.
kpeter@736	707
kpeter@736	708	/// Using this function, it is possible to avoid superfluous memory
kpeter@736	709	/// allocation: if you know that the graph you want to build will
kpeter@736	710	/// be large (e.g. it will contain millions of nodes and/or edges),
kpeter@736	711	/// then it is worth reserving space for this amount before starting
kpeter@736	712	/// to build the graph.
kpeter@736	713	/// \sa reserveNode()
kpeter@736	714	void reserveEdge(int m) { arcs.reserve(2 * m); };
kpeter@736	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@373	739	nodes[arcs[n-1].target].first_out=arcs[n].next_out;
kpeter@373	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@735	754	///Class to make a snapshot of the graph and to restore it later.
deba@109	755
kpeter@735	756	///Class to make a snapshot of the graph and to restore it later.
deba@109	757	///
kpeter@735	758	///The newly added nodes and edges can be removed using the
kpeter@735	759	///restore() function. This is the only way for deleting nodes and/or
kpeter@735	760	///edges from a SmartGraph structure.
deba@109	761	///
alpar@877	762	///\note After a state is restored, you cannot restore a later state,
kpeter@735	763	///i.e. you cannot add the removed nodes and edges again using
kpeter@735	764	///another Snapshot instance.
deba@109	765	///
kpeter@735	766	///\warning The validity of the snapshot is not stored due to
kpeter@735	767	///performance reasons. If you do not use the snapshot correctly,
kpeter@735	768	///it can cause broken program, invalid or not restored state of
kpeter@735	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@735	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@735	785	/// This constructor immediately makes a snapshot of the given graph.
kpeter@735	786	///
kpeter@735	787	Snapshot(SmartGraph &gr) {
kpeter@735	788	gr.saveSnapshot(*this);
deba@109	789	}
deba@109	790
deba@109	791	///Make a snapshot.
deba@109	792
kpeter@735	793	///This function makes a snapshot of the given graph.
kpeter@735	794	///It can be called more than once. In case of a repeated
deba@109	795	///call, the previous snapshot gets lost.
kpeter@735	796	void save(SmartGraph &gr)
deba@109	797	{
kpeter@735	798	gr.saveSnapshot(*this);
deba@109	799	}
deba@109	800
kpeter@735	801	///Undo the changes until the last snapshot.
alpar@209	802
kpeter@735	803	///This function undos the changes until the last snapshot
kpeter@735	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@1019	812	class SmartBpGraphBase {
deba@1019	813
deba@1019	814	protected:
deba@1019	815
deba@1019	816	struct NodeT {
deba@1019	817	int first_out;
deba@1019	818	int partition_next;
deba@1019	819	int partition_index;
deba@1019	820	bool red;
deba@1019	821	};
deba@1019	822
deba@1019	823	struct ArcT {
deba@1019	824	int target;
deba@1019	825	int next_out;
deba@1019	826	};
deba@1019	827
deba@1019	828	std::vector<NodeT> nodes;
deba@1019	829	std::vector<ArcT> arcs;
deba@1019	830
deba@1019	831	int first_red, first_blue;
deba@1023	832	int max_red, max_blue;
deba@1019	833
deba@1019	834	public:
deba@1019	835
deba@1019	836	typedef SmartBpGraphBase Graph;
deba@1019	837
deba@1019	838	class Node;
deba@1019	839	class Arc;
deba@1019	840	class Edge;
deba@1019	841
deba@1019	842	class Node {
deba@1019	843	friend class SmartBpGraphBase;
deba@1019	844	protected:
deba@1019	845
deba@1019	846	int _id;
deba@1019	847	explicit Node(int id) { _id = id;}
deba@1019	848
deba@1019	849	public:
deba@1019	850	Node() {}
deba@1019	851	Node (Invalid) { _id = -1; }
deba@1019	852	bool operator==(const Node& node) const {return _id == node._id;}
deba@1019	853	bool operator!=(const Node& node) const {return _id != node._id;}
deba@1019	854	bool operator<(const Node& node) const {return _id < node._id;}
deba@1019	855	};
deba@1019	856
deba@1025	857	class RedNode : public Node {
deba@1025	858	friend class SmartBpGraphBase;
deba@1025	859	protected:
deba@1025	860
deba@1025	861	explicit RedNode(int pid) : Node(pid) {}
deba@1025	862
deba@1025	863	public:
deba@1025	864	RedNode() {}
deba@1025	865	RedNode(const RedNode& node) : Node(node) {}
deba@1025	866	RedNode(Invalid) : Node(INVALID){}
deba@1025	867	};
deba@1025	868
deba@1025	869	class BlueNode : public Node {
deba@1025	870	friend class SmartBpGraphBase;
deba@1025	871	protected:
deba@1025	872
deba@1025	873	explicit BlueNode(int pid) : Node(pid) {}
deba@1025	874
deba@1025	875	public:
deba@1025	876	BlueNode() {}
deba@1025	877	BlueNode(const BlueNode& node) : Node(node) {}
deba@1025	878	BlueNode(Invalid) : Node(INVALID){}
deba@1025	879	};
deba@1025	880
deba@1019	881	class Edge {
deba@1019	882	friend class SmartBpGraphBase;
deba@1019	883	protected:
deba@1019	884
deba@1019	885	int _id;
deba@1019	886	explicit Edge(int id) { _id = id;}
deba@1019	887
deba@1019	888	public:
deba@1019	889	Edge() {}
deba@1019	890	Edge (Invalid) { _id = -1; }
deba@1019	891	bool operator==(const Edge& arc) const {return _id == arc._id;}
deba@1019	892	bool operator!=(const Edge& arc) const {return _id != arc._id;}
deba@1019	893	bool operator<(const Edge& arc) const {return _id < arc._id;}
deba@1019	894	};
deba@1019	895
deba@1019	896	class Arc {
deba@1019	897	friend class SmartBpGraphBase;
deba@1019	898	protected:
deba@1019	899
deba@1019	900	int _id;
deba@1019	901	explicit Arc(int id) { _id = id;}
deba@1019	902
deba@1019	903	public:
deba@1019	904	operator Edge() const {
deba@1019	905	return _id != -1 ? edgeFromId(_id / 2) : INVALID;
deba@1019	906	}
deba@1019	907
deba@1019	908	Arc() {}
deba@1019	909	Arc (Invalid) { _id = -1; }
deba@1019	910	bool operator==(const Arc& arc) const {return _id == arc._id;}
deba@1019	911	bool operator!=(const Arc& arc) const {return _id != arc._id;}
deba@1019	912	bool operator<(const Arc& arc) const {return _id < arc._id;}
deba@1019	913	};
deba@1019	914
deba@1019	915
deba@1019	916
deba@1019	917	SmartBpGraphBase()
deba@1023	918	: nodes(), arcs(), first_red(-1), first_blue(-1),
deba@1023	919	max_red(-1), max_blue(-1) {}
deba@1019	920
deba@1019	921	typedef True NodeNumTag;
deba@1019	922	typedef True EdgeNumTag;
deba@1019	923	typedef True ArcNumTag;
deba@1019	924
deba@1019	925	int nodeNum() const { return nodes.size(); }
deba@1023	926	int redNum() const { return max_red + 1; }
deba@1023	927	int blueNum() const { return max_blue + 1; }
deba@1019	928	int edgeNum() const { return arcs.size() / 2; }
deba@1019	929	int arcNum() const { return arcs.size(); }
deba@1019	930
deba@1019	931	int maxNodeId() const { return nodes.size()-1; }
deba@1023	932	int maxRedId() const { return max_red; }
deba@1023	933	int maxBlueId() const { return max_blue; }
deba@1019	934	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@1019	935	int maxArcId() const { return arcs.size()-1; }
deba@1019	936
deba@1019	937	bool red(Node n) const { return nodes[n._id].red; }
deba@1019	938	bool blue(Node n) const { return !nodes[n._id].red; }
deba@1019	939
deba@1025	940	static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
deba@1025	941	static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
deba@1025	942
deba@1019	943	Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
deba@1019	944	Node target(Arc a) const { return Node(arcs[a._id].target); }
deba@1019	945
deba@1025	946	RedNode redNode(Edge e) const {
deba@1025	947	return RedNode(arcs[2 * e._id].target);
deba@1025	948	}
deba@1025	949	BlueNode blueNode(Edge e) const {
deba@1025	950	return BlueNode(arcs[2 * e._id + 1].target);
deba@1025	951	}
deba@1019	952
deba@1019	953	static bool direction(Arc a) {
deba@1019	954	return (a._id & 1) == 1;
deba@1019	955	}
deba@1019	956
deba@1019	957	static Arc direct(Edge e, bool d) {
deba@1019	958	return Arc(e._id * 2 + (d ? 1 : 0));
deba@1019	959	}
deba@1019	960
deba@1019	961	void first(Node& node) const {
deba@1019	962	node._id = nodes.size() - 1;
deba@1019	963	}
deba@1019	964
deba@1019	965	static void next(Node& node) {
deba@1019	966	--node._id;
deba@1019	967	}
deba@1019	968
deba@1025	969	void first(RedNode& node) const {
deba@1019	970	node._id = first_red;
deba@1019	971	}
deba@1019	972
deba@1025	973	void next(RedNode& node) const {
deba@1019	974	node._id = nodes[node._id].partition_next;
deba@1019	975	}
deba@1019	976
deba@1025	977	void first(BlueNode& node) const {
deba@1019	978	node._id = first_blue;
deba@1019	979	}
deba@1019	980
deba@1025	981	void next(BlueNode& node) const {
deba@1019	982	node._id = nodes[node._id].partition_next;
deba@1019	983	}
deba@1019	984
deba@1019	985	void first(Arc& arc) const {
deba@1019	986	arc._id = arcs.size() - 1;
deba@1019	987	}
deba@1019	988
deba@1019	989	static void next(Arc& arc) {
deba@1019	990	--arc._id;
deba@1019	991	}
deba@1019	992
deba@1019	993	void first(Edge& arc) const {
deba@1019	994	arc._id = arcs.size() / 2 - 1;
deba@1019	995	}
deba@1019	996
deba@1019	997	static void next(Edge& arc) {
deba@1019	998	--arc._id;
deba@1019	999	}
deba@1019	1000
deba@1019	1001	void firstOut(Arc &arc, const Node& v) const {
deba@1019	1002	arc._id = nodes[v._id].first_out;
deba@1019	1003	}
deba@1019	1004	void nextOut(Arc &arc) const {
deba@1019	1005	arc._id = arcs[arc._id].next_out;
deba@1019	1006	}
deba@1019	1007
deba@1019	1008	void firstIn(Arc &arc, const Node& v) const {
deba@1019	1009	arc._id = ((nodes[v._id].first_out) ^ 1);
deba@1019	1010	if (arc._id == -2) arc._id = -1;
deba@1019	1011	}
deba@1019	1012	void nextIn(Arc &arc) const {
deba@1019	1013	arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
deba@1019	1014	if (arc._id == -2) arc._id = -1;
deba@1019	1015	}
deba@1019	1016
deba@1019	1017	void firstInc(Edge &arc, bool& d, const Node& v) const {
deba@1019	1018	int de = nodes[v._id].first_out;
deba@1019	1019	if (de != -1) {
deba@1019	1020	arc._id = de / 2;
deba@1019	1021	d = ((de & 1) == 1);
deba@1019	1022	} else {
deba@1019	1023	arc._id = -1;
deba@1019	1024	d = true;
deba@1019	1025	}
deba@1019	1026	}
deba@1019	1027	void nextInc(Edge &arc, bool& d) const {
deba@1019	1028	int de = (arcs[(arc._id * 2) \| (d ? 1 : 0)].next_out);
deba@1019	1029	if (de != -1) {
deba@1019	1030	arc._id = de / 2;
deba@1019	1031	d = ((de & 1) == 1);
deba@1019	1032	} else {
deba@1019	1033	arc._id = -1;
deba@1019	1034	d = true;
deba@1019	1035	}
deba@1019	1036	}
deba@1019	1037
deba@1019	1038	static int id(Node v) { return v._id; }
deba@1025	1039	int id(RedNode v) const { return nodes[v._id].partition_index; }
deba@1025	1040	int id(BlueNode v) const { return nodes[v._id].partition_index; }
deba@1019	1041	static int id(Arc e) { return e._id; }
deba@1019	1042	static int id(Edge e) { return e._id; }
deba@1019	1043
deba@1019	1044	static Node nodeFromId(int id) { return Node(id);}
deba@1019	1045	static Arc arcFromId(int id) { return Arc(id);}
deba@1019	1046	static Edge edgeFromId(int id) { return Edge(id);}
deba@1019	1047
deba@1019	1048	bool valid(Node n) const {
deba@1019	1049	return n._id >= 0 && n._id < static_cast<int>(nodes.size());
deba@1019	1050	}
deba@1019	1051	bool valid(Arc a) const {
deba@1019	1052	return a._id >= 0 && a._id < static_cast<int>(arcs.size());
deba@1019	1053	}
deba@1019	1054	bool valid(Edge e) const {
deba@1019	1055	return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
deba@1019	1056	}
deba@1019	1057
deba@1025	1058	RedNode addRedNode() {
deba@1019	1059	int n = nodes.size();
deba@1019	1060	nodes.push_back(NodeT());
deba@1019	1061	nodes[n].first_out = -1;
deba@1019	1062	nodes[n].red = true;
deba@1023	1063	nodes[n].partition_index = ++max_red;
deba@1019	1064	nodes[n].partition_next = first_red;
deba@1019	1065	first_red = n;
deba@1019	1066
deba@1025	1067	return RedNode(n);
deba@1019	1068	}
deba@1019	1069
deba@1025	1070	BlueNode addBlueNode() {
deba@1019	1071	int n = nodes.size();
deba@1019	1072	nodes.push_back(NodeT());
deba@1019	1073	nodes[n].first_out = -1;
deba@1019	1074	nodes[n].red = false;
deba@1023	1075	nodes[n].partition_index = ++max_blue;
deba@1019	1076	nodes[n].partition_next = first_blue;
deba@1019	1077	first_blue = n;
deba@1019	1078
deba@1025	1079	return BlueNode(n);
deba@1019	1080	}
deba@1019	1081
deba@1025	1082	Edge addEdge(RedNode u, BlueNode v) {
deba@1019	1083	int n = arcs.size();
deba@1019	1084	arcs.push_back(ArcT());
deba@1019	1085	arcs.push_back(ArcT());
deba@1019	1086
deba@1019	1087	arcs[n].target = u._id;
deba@1019	1088	arcs[n \| 1].target = v._id;
deba@1019	1089
deba@1019	1090	arcs[n].next_out = nodes[v._id].first_out;
deba@1019	1091	nodes[v._id].first_out = n;
deba@1019	1092
deba@1019	1093	arcs[n \| 1].next_out = nodes[u._id].first_out;
deba@1019	1094	nodes[u._id].first_out = (n \| 1);
deba@1019	1095
deba@1019	1096	return Edge(n / 2);
deba@1019	1097	}
deba@1019	1098
deba@1019	1099	void clear() {
deba@1019	1100	arcs.clear();
deba@1019	1101	nodes.clear();
deba@1019	1102	first_red = -1;
deba@1019	1103	first_blue = -1;
deba@1023	1104	max_blue = -1;
deba@1023	1105	max_red = -1;
deba@1019	1106	}
deba@1019	1107
deba@1019	1108	};
deba@1019	1109
deba@1019	1110	typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
deba@1019	1111
deba@1019	1112	/// \ingroup graphs
deba@1019	1113	///
deba@1020	1114	/// \brief A smart undirected bipartite graph class.
deba@1019	1115	///
deba@1020	1116	/// \ref SmartBpGraph is a simple and fast bipartite graph implementation.
deba@1019	1117	/// It is also quite memory efficient but at the price
deba@1019	1118	/// that it does not support node and edge deletion
deba@1019	1119	/// (except for the Snapshot feature).
deba@1019	1120	///
deba@1020	1121	/// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
deba@1019	1122	/// and it also provides some additional functionalities.
deba@1019	1123	/// Most of its member functions and nested classes are documented
deba@1019	1124	/// only in the concept class.
deba@1019	1125	///
deba@1019	1126	/// This class provides constant time counting for nodes, edges and arcs.
deba@1019	1127	///
deba@1020	1128	/// \sa concepts::BpGraph
deba@1020	1129	/// \sa SmartGraph
deba@1019	1130	class SmartBpGraph : public ExtendedSmartBpGraphBase {
deba@1019	1131	typedef ExtendedSmartBpGraphBase Parent;
deba@1019	1132
deba@1019	1133	private:
deba@1019	1134	/// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@1019	1135	SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
deba@1019	1136	/// \brief Assignment of a graph to another one is \e not allowed.
deba@1019	1137	/// Use GraphCopy instead.
deba@1019	1138	void operator=(const SmartBpGraph &) {}
deba@1019	1139
deba@1019	1140	public:
deba@1019	1141
deba@1019	1142	/// Constructor
deba@1019	1143
deba@1019	1144	/// Constructor.
deba@1019	1145	///
deba@1019	1146	SmartBpGraph() {}
deba@1019	1147
deba@1019	1148	/// \brief Add a new red node to the graph.
deba@1019	1149	///
deba@1019	1150	/// This function adds a red new node to the graph.
deba@1019	1151	/// \return The new node.
deba@1025	1152	RedNode addRedNode() { return Parent::addRedNode(); }
deba@1019	1153
deba@1019	1154	/// \brief Add a new blue node to the graph.
deba@1019	1155	///
deba@1019	1156	/// This function adds a blue new node to the graph.
deba@1019	1157	/// \return The new node.
deba@1025	1158	BlueNode addBlueNode() { return Parent::addBlueNode(); }
deba@1019	1159
deba@1019	1160	/// \brief Add a new edge to the graph.
deba@1019	1161	///
deba@1019	1162	/// This function adds a new edge to the graph between nodes
deba@1019	1163	/// \c u and \c v with inherent orientation from node \c u to
deba@1019	1164	/// node \c v.
deba@1019	1165	/// \return The new edge.
deba@1025	1166	Edge addEdge(RedNode u, BlueNode v) {
deba@1025	1167	return Parent::addEdge(u, v);
deba@1025	1168	}
deba@1025	1169	Edge addEdge(BlueNode v, RedNode u) {
deba@1025	1170	return Parent::addEdge(u, v);
deba@1019	1171	}
deba@1019	1172
deba@1019	1173	/// \brief Node validity check
deba@1019	1174	///
deba@1019	1175	/// This function gives back \c true if the given node is valid,
deba@1019	1176	/// i.e. it is a real node of the graph.
deba@1019	1177	///
deba@1019	1178	/// \warning A removed node (using Snapshot) could become valid again
deba@1019	1179	/// if new nodes are added to the graph.
deba@1019	1180	bool valid(Node n) const { return Parent::valid(n); }
deba@1019	1181
deba@1019	1182	/// \brief Edge validity check
deba@1019	1183	///
deba@1019	1184	/// This function gives back \c true if the given edge is valid,
deba@1019	1185	/// i.e. it is a real edge of the graph.
deba@1019	1186	///
deba@1019	1187	/// \warning A removed edge (using Snapshot) could become valid again
deba@1019	1188	/// if new edges are added to the graph.
deba@1019	1189	bool valid(Edge e) const { return Parent::valid(e); }
deba@1019	1190
deba@1019	1191	/// \brief Arc validity check
deba@1019	1192	///
deba@1019	1193	/// This function gives back \c true if the given arc is valid,
deba@1019	1194	/// i.e. it is a real arc of the graph.
deba@1019	1195	///
deba@1019	1196	/// \warning A removed arc (using Snapshot) could become valid again
deba@1019	1197	/// if new edges are added to the graph.
deba@1019	1198	bool valid(Arc a) const { return Parent::valid(a); }
deba@1019	1199
deba@1019	1200	///Clear the graph.
deba@1019	1201
deba@1019	1202	///This function erases all nodes and arcs from the graph.
deba@1019	1203	///
deba@1019	1204	void clear() {
deba@1019	1205	Parent::clear();
deba@1019	1206	}
deba@1019	1207
deba@1019	1208	/// Reserve memory for nodes.
deba@1019	1209
deba@1019	1210	/// Using this function, it is possible to avoid superfluous memory
deba@1019	1211	/// allocation: if you know that the graph you want to build will
deba@1019	1212	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1019	1213	/// then it is worth reserving space for this amount before starting
deba@1019	1214	/// to build the graph.
deba@1019	1215	/// \sa reserveEdge()
deba@1019	1216	void reserveNode(int n) { nodes.reserve(n); };
deba@1019	1217
deba@1019	1218	/// Reserve memory for edges.
deba@1019	1219
deba@1019	1220	/// Using this function, it is possible to avoid superfluous memory
deba@1019	1221	/// allocation: if you know that the graph you want to build will
deba@1019	1222	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1019	1223	/// then it is worth reserving space for this amount before starting
deba@1019	1224	/// to build the graph.
deba@1019	1225	/// \sa reserveNode()
deba@1019	1226	void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@1019	1227
deba@1019	1228	public:
deba@1019	1229
deba@1019	1230	class Snapshot;
deba@1019	1231
deba@1019	1232	protected:
deba@1019	1233
deba@1019	1234	void saveSnapshot(Snapshot &s)
deba@1019	1235	{
deba@1019	1236	s._graph = this;
deba@1019	1237	s.node_num = nodes.size();
deba@1019	1238	s.arc_num = arcs.size();
deba@1019	1239	}
deba@1019	1240
deba@1019	1241	void restoreSnapshot(const Snapshot &s)
deba@1019	1242	{
deba@1019	1243	while(s.arc_num<arcs.size()) {
deba@1019	1244	int n=arcs.size()-1;
deba@1019	1245	Edge arc=edgeFromId(n/2);
deba@1019	1246	Parent::notifier(Edge()).erase(arc);
deba@1019	1247	std::vector<Arc> dir;
deba@1019	1248	dir.push_back(arcFromId(n));
deba@1019	1249	dir.push_back(arcFromId(n-1));
deba@1019	1250	Parent::notifier(Arc()).erase(dir);
deba@1019	1251	nodes[arcs[n-1].target].first_out=arcs[n].next_out;
deba@1019	1252	nodes[arcs[n].target].first_out=arcs[n-1].next_out;
deba@1019	1253	arcs.pop_back();
deba@1019	1254	arcs.pop_back();
deba@1019	1255	}
deba@1019	1256	while(s.node_num<nodes.size()) {
deba@1019	1257	int n=nodes.size()-1;
deba@1019	1258	Node node = nodeFromId(n);
deba@1019	1259	if (Parent::red(node)) {
deba@1019	1260	first_red = nodes[n].partition_next;
deba@1023	1261	if (first_red != -1) {
deba@1023	1262	max_red = nodes[first_red].partition_index;
deba@1023	1263	} else {
deba@1023	1264	max_red = -1;
deba@1023	1265	}
alpar@1092	1266	Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
deba@1019	1267	} else {
deba@1019	1268	first_blue = nodes[n].partition_next;
deba@1023	1269	if (first_blue != -1) {
deba@1023	1270	max_blue = nodes[first_blue].partition_index;
deba@1023	1271	} else {
deba@1023	1272	max_blue = -1;
deba@1023	1273	}
deba@1025	1274	Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
deba@1019	1275	}
deba@1019	1276	Parent::notifier(Node()).erase(node);
deba@1019	1277	nodes.pop_back();
deba@1019	1278	}
deba@1019	1279	}
deba@1019	1280
deba@1019	1281	public:
deba@1019	1282
deba@1019	1283	///Class to make a snapshot of the graph and to restore it later.
deba@1019	1284
deba@1019	1285	///Class to make a snapshot of the graph and to restore it later.
deba@1019	1286	///
deba@1019	1287	///The newly added nodes and edges can be removed using the
deba@1019	1288	///restore() function. This is the only way for deleting nodes and/or
deba@1019	1289	///edges from a SmartBpGraph structure.
deba@1019	1290	///
deba@1019	1291	///\note After a state is restored, you cannot restore a later state,
deba@1019	1292	///i.e. you cannot add the removed nodes and edges again using
deba@1019	1293	///another Snapshot instance.
deba@1019	1294	///
deba@1019	1295	///\warning The validity of the snapshot is not stored due to
deba@1019	1296	///performance reasons. If you do not use the snapshot correctly,
deba@1019	1297	///it can cause broken program, invalid or not restored state of
deba@1019	1298	///the graph or no change.
deba@1019	1299	class Snapshot
deba@1019	1300	{
deba@1019	1301	SmartBpGraph *_graph;
deba@1019	1302	protected:
deba@1019	1303	friend class SmartBpGraph;
deba@1019	1304	unsigned int node_num;
deba@1019	1305	unsigned int arc_num;
deba@1019	1306	public:
deba@1019	1307	///Default constructor.
deba@1019	1308
deba@1019	1309	///Default constructor.
deba@1019	1310	///You have to call save() to actually make a snapshot.
deba@1019	1311	Snapshot() : _graph(0) {}
deba@1019	1312	///Constructor that immediately makes a snapshot
deba@1019	1313
deba@1019	1314	/// This constructor immediately makes a snapshot of the given graph.
deba@1019	1315	///
deba@1019	1316	Snapshot(SmartBpGraph &gr) {
deba@1019	1317	gr.saveSnapshot(*this);
deba@1019	1318	}
deba@1019	1319
deba@1019	1320	///Make a snapshot.
deba@1019	1321
deba@1019	1322	///This function makes a snapshot of the given graph.
deba@1019	1323	///It can be called more than once. In case of a repeated
deba@1019	1324	///call, the previous snapshot gets lost.
deba@1019	1325	void save(SmartBpGraph &gr)
deba@1019	1326	{
deba@1019	1327	gr.saveSnapshot(*this);
deba@1019	1328	}
deba@1019	1329
deba@1019	1330	///Undo the changes until the last snapshot.
deba@1019	1331
deba@1019	1332	///This function undos the changes until the last snapshot
deba@1019	1333	///created by save() or Snapshot(SmartBpGraph&).
deba@1019	1334	void restore()
deba@1019	1335	{
deba@1019	1336	_graph->restoreSnapshot(*this);
deba@1019	1337	}
deba@1019	1338	};
deba@1019	1339	};
deba@1019	1340
deba@109	1341	} //namespace lemon
deba@109	1342
deba@109	1343
deba@109	1344	#endif //LEMON_SMART_GRAPH_H

author	Alpar Juttner <alpar@cs.elte.hu>
	Mon, 15 Oct 2018 23:39:22 +0200
changeset 1172	d7e25df22e88
parent 1025	c8fa41fcc4a7
permissions	-rw-r--r--