lemon: lemon/smart_graph.h@2126945deb6a (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@1270	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@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@1191	832	int max_red, max_blue;
deba@1187	833
deba@1187	834	public:
deba@1187	835
deba@1187	836	typedef SmartBpGraphBase Graph;
deba@1187	837
deba@1187	838	class Node;
deba@1187	839	class Arc;
deba@1187	840	class Edge;
deba@1187	841
deba@1187	842	class Node {
deba@1187	843	friend class SmartBpGraphBase;
deba@1187	844	protected:
deba@1187	845
deba@1187	846	int _id;
deba@1187	847	explicit Node(int id) { _id = id;}
deba@1187	848
deba@1187	849	public:
deba@1187	850	Node() {}
deba@1187	851	Node (Invalid) { _id = -1; }
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	bool operator<(const Node& node) const {return _id < node._id;}
deba@1187	855	};
deba@1187	856
deba@1193	857	class RedNode : public Node {
deba@1193	858	friend class SmartBpGraphBase;
deba@1193	859	protected:
deba@1193	860
deba@1193	861	explicit RedNode(int pid) : Node(pid) {}
deba@1193	862
deba@1193	863	public:
deba@1193	864	RedNode() {}
deba@1193	865	RedNode(const RedNode& node) : Node(node) {}
deba@1193	866	RedNode(Invalid) : Node(INVALID){}
deba@1193	867	};
deba@1193	868
deba@1193	869	class BlueNode : public Node {
deba@1193	870	friend class SmartBpGraphBase;
deba@1193	871	protected:
deba@1193	872
deba@1193	873	explicit BlueNode(int pid) : Node(pid) {}
deba@1193	874
deba@1193	875	public:
deba@1193	876	BlueNode() {}
deba@1193	877	BlueNode(const BlueNode& node) : Node(node) {}
deba@1193	878	BlueNode(Invalid) : Node(INVALID){}
deba@1193	879	};
deba@1193	880
deba@1187	881	class Edge {
deba@1187	882	friend class SmartBpGraphBase;
deba@1187	883	protected:
deba@1187	884
deba@1187	885	int _id;
deba@1187	886	explicit Edge(int id) { _id = id;}
deba@1187	887
deba@1187	888	public:
deba@1187	889	Edge() {}
deba@1187	890	Edge (Invalid) { _id = -1; }
deba@1187	891	bool operator==(const Edge& arc) const {return _id == arc._id;}
deba@1187	892	bool operator!=(const Edge& arc) const {return _id != arc._id;}
deba@1187	893	bool operator<(const Edge& arc) const {return _id < arc._id;}
deba@1187	894	};
deba@1187	895
deba@1187	896	class Arc {
deba@1187	897	friend class SmartBpGraphBase;
deba@1187	898	protected:
deba@1187	899
deba@1187	900	int _id;
deba@1187	901	explicit Arc(int id) { _id = id;}
deba@1187	902
deba@1187	903	public:
deba@1187	904	operator Edge() const {
deba@1187	905	return _id != -1 ? edgeFromId(_id / 2) : INVALID;
deba@1187	906	}
deba@1187	907
deba@1187	908	Arc() {}
deba@1187	909	Arc (Invalid) { _id = -1; }
deba@1187	910	bool operator==(const Arc& arc) const {return _id == arc._id;}
deba@1187	911	bool operator!=(const Arc& arc) const {return _id != arc._id;}
deba@1187	912	bool operator<(const Arc& arc) const {return _id < arc._id;}
deba@1187	913	};
deba@1187	914
deba@1187	915
deba@1187	916
deba@1187	917	SmartBpGraphBase()
deba@1191	918	: nodes(), arcs(), first_red(-1), first_blue(-1),
deba@1191	919	max_red(-1), max_blue(-1) {}
deba@1187	920
deba@1187	921	typedef True NodeNumTag;
deba@1187	922	typedef True EdgeNumTag;
deba@1187	923	typedef True ArcNumTag;
deba@1187	924
deba@1187	925	int nodeNum() const { return nodes.size(); }
deba@1191	926	int redNum() const { return max_red + 1; }
deba@1191	927	int blueNum() const { return max_blue + 1; }
deba@1187	928	int edgeNum() const { return arcs.size() / 2; }
deba@1187	929	int arcNum() const { return arcs.size(); }
deba@1187	930
deba@1187	931	int maxNodeId() const { return nodes.size()-1; }
deba@1191	932	int maxRedId() const { return max_red; }
deba@1191	933	int maxBlueId() const { return max_blue; }
deba@1187	934	int maxEdgeId() const { return arcs.size() / 2 - 1; }
deba@1187	935	int maxArcId() const { return arcs.size()-1; }
deba@1187	936
deba@1187	937	bool red(Node n) const { return nodes[n._id].red; }
deba@1187	938	bool blue(Node n) const { return !nodes[n._id].red; }
deba@1187	939
deba@1193	940	static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
deba@1193	941	static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
deba@1193	942
deba@1187	943	Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
deba@1187	944	Node target(Arc a) const { return Node(arcs[a._id].target); }
deba@1187	945
deba@1193	946	RedNode redNode(Edge e) const {
deba@1193	947	return RedNode(arcs[2 * e._id].target);
deba@1193	948	}
deba@1193	949	BlueNode blueNode(Edge e) const {
deba@1193	950	return BlueNode(arcs[2 * e._id + 1].target);
deba@1193	951	}
deba@1187	952
deba@1187	953	static bool direction(Arc a) {
deba@1187	954	return (a._id & 1) == 1;
deba@1187	955	}
deba@1187	956
deba@1187	957	static Arc direct(Edge e, bool d) {
deba@1187	958	return Arc(e._id * 2 + (d ? 1 : 0));
deba@1187	959	}
deba@1187	960
deba@1187	961	void first(Node& node) const {
deba@1187	962	node._id = nodes.size() - 1;
deba@1187	963	}
deba@1187	964
deba@1187	965	static void next(Node& node) {
deba@1187	966	--node._id;
deba@1187	967	}
deba@1187	968
deba@1193	969	void first(RedNode& node) const {
deba@1187	970	node._id = first_red;
deba@1187	971	}
deba@1187	972
deba@1193	973	void next(RedNode& node) const {
deba@1187	974	node._id = nodes[node._id].partition_next;
deba@1187	975	}
deba@1187	976
deba@1193	977	void first(BlueNode& node) const {
deba@1187	978	node._id = first_blue;
deba@1187	979	}
deba@1187	980
deba@1193	981	void next(BlueNode& node) const {
deba@1187	982	node._id = nodes[node._id].partition_next;
deba@1187	983	}
deba@1187	984
deba@1187	985	void first(Arc& arc) const {
deba@1187	986	arc._id = arcs.size() - 1;
deba@1187	987	}
deba@1187	988
deba@1187	989	static void next(Arc& arc) {
deba@1187	990	--arc._id;
deba@1187	991	}
deba@1187	992
deba@1187	993	void first(Edge& arc) const {
deba@1187	994	arc._id = arcs.size() / 2 - 1;
deba@1187	995	}
deba@1187	996
deba@1187	997	static void next(Edge& arc) {
deba@1187	998	--arc._id;
deba@1187	999	}
deba@1187	1000
deba@1187	1001	void firstOut(Arc &arc, const Node& v) const {
deba@1187	1002	arc._id = nodes[v._id].first_out;
deba@1187	1003	}
deba@1187	1004	void nextOut(Arc &arc) const {
deba@1187	1005	arc._id = arcs[arc._id].next_out;
deba@1187	1006	}
deba@1187	1007
deba@1187	1008	void firstIn(Arc &arc, const Node& v) const {
deba@1187	1009	arc._id = ((nodes[v._id].first_out) ^ 1);
deba@1187	1010	if (arc._id == -2) arc._id = -1;
deba@1187	1011	}
deba@1187	1012	void nextIn(Arc &arc) const {
deba@1187	1013	arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
deba@1187	1014	if (arc._id == -2) arc._id = -1;
deba@1187	1015	}
deba@1187	1016
deba@1187	1017	void firstInc(Edge &arc, bool& d, const Node& v) const {
deba@1187	1018	int de = nodes[v._id].first_out;
deba@1187	1019	if (de != -1) {
deba@1187	1020	arc._id = de / 2;
deba@1187	1021	d = ((de & 1) == 1);
deba@1187	1022	} else {
deba@1187	1023	arc._id = -1;
deba@1187	1024	d = true;
deba@1187	1025	}
deba@1187	1026	}
deba@1187	1027	void nextInc(Edge &arc, bool& d) const {
deba@1187	1028	int de = (arcs[(arc._id * 2) \| (d ? 1 : 0)].next_out);
deba@1187	1029	if (de != -1) {
deba@1187	1030	arc._id = de / 2;
deba@1187	1031	d = ((de & 1) == 1);
deba@1187	1032	} else {
deba@1187	1033	arc._id = -1;
deba@1187	1034	d = true;
deba@1187	1035	}
deba@1187	1036	}
deba@1187	1037
deba@1187	1038	static int id(Node v) { return v._id; }
deba@1193	1039	int id(RedNode v) const { return nodes[v._id].partition_index; }
deba@1193	1040	int id(BlueNode v) const { return nodes[v._id].partition_index; }
deba@1187	1041	static int id(Arc e) { return e._id; }
deba@1187	1042	static int id(Edge e) { return e._id; }
deba@1187	1043
deba@1187	1044	static Node nodeFromId(int id) { return Node(id);}
deba@1187	1045	static Arc arcFromId(int id) { return Arc(id);}
deba@1187	1046	static Edge edgeFromId(int id) { return Edge(id);}
deba@1187	1047
deba@1187	1048	bool valid(Node n) const {
deba@1187	1049	return n._id >= 0 && n._id < static_cast<int>(nodes.size());
deba@1187	1050	}
deba@1187	1051	bool valid(Arc a) const {
deba@1187	1052	return a._id >= 0 && a._id < static_cast<int>(arcs.size());
deba@1187	1053	}
deba@1187	1054	bool valid(Edge e) const {
deba@1187	1055	return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
deba@1187	1056	}
deba@1187	1057
deba@1193	1058	RedNode addRedNode() {
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 = true;
deba@1191	1063	nodes[n].partition_index = ++max_red;
deba@1187	1064	nodes[n].partition_next = first_red;
deba@1187	1065	first_red = n;
deba@1187	1066
deba@1193	1067	return RedNode(n);
deba@1187	1068	}
deba@1187	1069
deba@1193	1070	BlueNode addBlueNode() {
deba@1187	1071	int n = nodes.size();
deba@1187	1072	nodes.push_back(NodeT());
deba@1187	1073	nodes[n].first_out = -1;
deba@1187	1074	nodes[n].red = false;
deba@1191	1075	nodes[n].partition_index = ++max_blue;
deba@1187	1076	nodes[n].partition_next = first_blue;
deba@1187	1077	first_blue = n;
deba@1187	1078
deba@1193	1079	return BlueNode(n);
deba@1187	1080	}
deba@1187	1081
deba@1193	1082	Edge addEdge(RedNode u, BlueNode v) {
deba@1187	1083	int n = arcs.size();
deba@1187	1084	arcs.push_back(ArcT());
deba@1187	1085	arcs.push_back(ArcT());
deba@1187	1086
deba@1187	1087	arcs[n].target = u._id;
deba@1187	1088	arcs[n \| 1].target = v._id;
deba@1187	1089
deba@1187	1090	arcs[n].next_out = nodes[v._id].first_out;
deba@1187	1091	nodes[v._id].first_out = n;
deba@1187	1092
deba@1187	1093	arcs[n \| 1].next_out = nodes[u._id].first_out;
deba@1187	1094	nodes[u._id].first_out = (n \| 1);
deba@1187	1095
deba@1187	1096	return Edge(n / 2);
deba@1187	1097	}
deba@1187	1098
deba@1187	1099	void clear() {
deba@1187	1100	arcs.clear();
deba@1187	1101	nodes.clear();
deba@1187	1102	first_red = -1;
deba@1187	1103	first_blue = -1;
deba@1191	1104	max_blue = -1;
deba@1191	1105	max_red = -1;
deba@1187	1106	}
deba@1187	1107
deba@1187	1108	};
deba@1187	1109
deba@1187	1110	typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
deba@1187	1111
deba@1187	1112	/// \ingroup graphs
deba@1187	1113	///
deba@1188	1114	/// \brief A smart undirected bipartite graph class.
deba@1187	1115	///
deba@1188	1116	/// \ref SmartBpGraph is a simple and fast bipartite graph implementation.
deba@1187	1117	/// It is also quite memory efficient but at the price
deba@1187	1118	/// that it does not support node and edge deletion
deba@1187	1119	/// (except for the Snapshot feature).
deba@1187	1120	///
deba@1188	1121	/// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
deba@1187	1122	/// and it also provides some additional functionalities.
deba@1187	1123	/// Most of its member functions and nested classes are documented
deba@1187	1124	/// only in the concept class.
deba@1187	1125	///
deba@1187	1126	/// This class provides constant time counting for nodes, edges and arcs.
deba@1187	1127	///
deba@1188	1128	/// \sa concepts::BpGraph
deba@1188	1129	/// \sa SmartGraph
deba@1187	1130	class SmartBpGraph : public ExtendedSmartBpGraphBase {
deba@1187	1131	typedef ExtendedSmartBpGraphBase Parent;
deba@1187	1132
deba@1187	1133	private:
deba@1187	1134	/// Graphs are \e not copy constructible. Use GraphCopy instead.
deba@1187	1135	SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
deba@1187	1136	/// \brief Assignment of a graph to another one is \e not allowed.
deba@1187	1137	/// Use GraphCopy instead.
deba@1187	1138	void operator=(const SmartBpGraph &) {}
deba@1187	1139
deba@1187	1140	public:
deba@1187	1141
deba@1187	1142	/// Constructor
deba@1187	1143
deba@1187	1144	/// Constructor.
deba@1187	1145	///
deba@1187	1146	SmartBpGraph() {}
deba@1187	1147
deba@1187	1148	/// \brief Add a new red node to the graph.
deba@1187	1149	///
deba@1187	1150	/// This function adds a red new node to the graph.
deba@1187	1151	/// \return The new node.
deba@1193	1152	RedNode addRedNode() { return Parent::addRedNode(); }
deba@1187	1153
deba@1187	1154	/// \brief Add a new blue node to the graph.
deba@1187	1155	///
deba@1187	1156	/// This function adds a blue new node to the graph.
deba@1187	1157	/// \return The new node.
deba@1193	1158	BlueNode addBlueNode() { return Parent::addBlueNode(); }
deba@1187	1159
deba@1187	1160	/// \brief Add a new edge to the graph.
deba@1187	1161	///
deba@1187	1162	/// This function adds a new edge to the graph between nodes
deba@1187	1163	/// \c u and \c v with inherent orientation from node \c u to
deba@1187	1164	/// node \c v.
deba@1187	1165	/// \return The new edge.
deba@1193	1166	Edge addEdge(RedNode u, BlueNode v) {
deba@1193	1167	return Parent::addEdge(u, v);
deba@1193	1168	}
deba@1193	1169	Edge addEdge(BlueNode v, RedNode u) {
deba@1193	1170	return Parent::addEdge(u, v);
deba@1187	1171	}
deba@1187	1172
deba@1187	1173	/// \brief Node validity check
deba@1187	1174	///
deba@1187	1175	/// This function gives back \c true if the given node is valid,
deba@1187	1176	/// i.e. it is a real node of the graph.
deba@1187	1177	///
deba@1187	1178	/// \warning A removed node (using Snapshot) could become valid again
deba@1187	1179	/// if new nodes are added to the graph.
deba@1187	1180	bool valid(Node n) const { return Parent::valid(n); }
deba@1187	1181
deba@1187	1182	/// \brief Edge validity check
deba@1187	1183	///
deba@1187	1184	/// This function gives back \c true if the given edge is valid,
deba@1187	1185	/// i.e. it is a real edge of the graph.
deba@1187	1186	///
deba@1187	1187	/// \warning A removed edge (using Snapshot) could become valid again
deba@1187	1188	/// if new edges are added to the graph.
deba@1187	1189	bool valid(Edge e) const { return Parent::valid(e); }
deba@1187	1190
deba@1187	1191	/// \brief Arc validity check
deba@1187	1192	///
deba@1187	1193	/// This function gives back \c true if the given arc is valid,
deba@1187	1194	/// i.e. it is a real arc of the graph.
deba@1187	1195	///
deba@1187	1196	/// \warning A removed arc (using Snapshot) could become valid again
deba@1187	1197	/// if new edges are added to the graph.
deba@1187	1198	bool valid(Arc a) const { return Parent::valid(a); }
deba@1187	1199
deba@1187	1200	///Clear the graph.
deba@1187	1201
deba@1187	1202	///This function erases all nodes and arcs from the graph.
deba@1187	1203	///
deba@1187	1204	void clear() {
deba@1187	1205	Parent::clear();
deba@1187	1206	}
deba@1187	1207
deba@1187	1208	/// Reserve memory for nodes.
deba@1187	1209
deba@1187	1210	/// Using this function, it is possible to avoid superfluous memory
deba@1187	1211	/// allocation: if you know that the graph you want to build will
deba@1187	1212	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1187	1213	/// then it is worth reserving space for this amount before starting
deba@1187	1214	/// to build the graph.
deba@1187	1215	/// \sa reserveEdge()
deba@1187	1216	void reserveNode(int n) { nodes.reserve(n); };
deba@1187	1217
deba@1187	1218	/// Reserve memory for edges.
deba@1187	1219
deba@1187	1220	/// Using this function, it is possible to avoid superfluous memory
deba@1187	1221	/// allocation: if you know that the graph you want to build will
deba@1187	1222	/// be large (e.g. it will contain millions of nodes and/or edges),
deba@1187	1223	/// then it is worth reserving space for this amount before starting
deba@1187	1224	/// to build the graph.
deba@1187	1225	/// \sa reserveNode()
deba@1187	1226	void reserveEdge(int m) { arcs.reserve(2 * m); };
deba@1187	1227
deba@1187	1228	public:
deba@1187	1229
deba@1187	1230	class Snapshot;
deba@1187	1231
deba@1187	1232	protected:
deba@1187	1233
deba@1187	1234	void saveSnapshot(Snapshot &s)
deba@1187	1235	{
deba@1187	1236	s._graph = this;
deba@1187	1237	s.node_num = nodes.size();
deba@1187	1238	s.arc_num = arcs.size();
deba@1187	1239	}
deba@1187	1240
deba@1187	1241	void restoreSnapshot(const Snapshot &s)
deba@1187	1242	{
deba@1187	1243	while(s.arc_num<arcs.size()) {
deba@1187	1244	int n=arcs.size()-1;
deba@1187	1245	Edge arc=edgeFromId(n/2);
deba@1187	1246	Parent::notifier(Edge()).erase(arc);
deba@1187	1247	std::vector<Arc> dir;
deba@1187	1248	dir.push_back(arcFromId(n));
deba@1187	1249	dir.push_back(arcFromId(n-1));
deba@1187	1250	Parent::notifier(Arc()).erase(dir);
deba@1187	1251	nodes[arcs[n-1].target].first_out=arcs[n].next_out;
deba@1187	1252	nodes[arcs[n].target].first_out=arcs[n-1].next_out;
deba@1187	1253	arcs.pop_back();
deba@1187	1254	arcs.pop_back();
deba@1187	1255	}
deba@1187	1256	while(s.node_num<nodes.size()) {
deba@1187	1257	int n=nodes.size()-1;
deba@1187	1258	Node node = nodeFromId(n);
deba@1187	1259	if (Parent::red(node)) {
deba@1187	1260	first_red = nodes[n].partition_next;
deba@1191	1261	if (first_red != -1) {
deba@1191	1262	max_red = nodes[first_red].partition_index;
deba@1191	1263	} else {
deba@1191	1264	max_red = -1;
deba@1191	1265	}
alpar@1270	1266	Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));
deba@1187	1267	} else {
deba@1187	1268	first_blue = nodes[n].partition_next;
deba@1191	1269	if (first_blue != -1) {
deba@1191	1270	max_blue = nodes[first_blue].partition_index;
deba@1191	1271	} else {
deba@1191	1272	max_blue = -1;
deba@1191	1273	}
deba@1193	1274	Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
deba@1187	1275	}
deba@1187	1276	Parent::notifier(Node()).erase(node);
deba@1187	1277	nodes.pop_back();
deba@1187	1278	}
deba@1187	1279	}
deba@1187	1280
deba@1187	1281	public:
deba@1187	1282
deba@1187	1283	///Class to make a snapshot of the graph and to restore it later.
deba@1187	1284
deba@1187	1285	///Class to make a snapshot of the graph and to restore it later.
deba@1187	1286	///
deba@1187	1287	///The newly added nodes and edges can be removed using the
deba@1187	1288	///restore() function. This is the only way for deleting nodes and/or
deba@1187	1289	///edges from a SmartBpGraph structure.
deba@1187	1290	///
deba@1187	1291	///\note After a state is restored, you cannot restore a later state,
deba@1187	1292	///i.e. you cannot add the removed nodes and edges again using
deba@1187	1293	///another Snapshot instance.
deba@1187	1294	///
deba@1187	1295	///\warning The validity of the snapshot is not stored due to
deba@1187	1296	///performance reasons. If you do not use the snapshot correctly,
deba@1187	1297	///it can cause broken program, invalid or not restored state of
deba@1187	1298	///the graph or no change.
deba@1187	1299	class Snapshot
deba@1187	1300	{
deba@1187	1301	SmartBpGraph *_graph;
deba@1187	1302	protected:
deba@1187	1303	friend class SmartBpGraph;
deba@1187	1304	unsigned int node_num;
deba@1187	1305	unsigned int arc_num;
deba@1187	1306	public:
deba@1187	1307	///Default constructor.
deba@1187	1308
deba@1187	1309	///Default constructor.
deba@1187	1310	///You have to call save() to actually make a snapshot.
deba@1187	1311	Snapshot() : _graph(0) {}
deba@1187	1312	///Constructor that immediately makes a snapshot
deba@1187	1313
deba@1187	1314	/// This constructor immediately makes a snapshot of the given graph.
deba@1187	1315	///
deba@1187	1316	Snapshot(SmartBpGraph &gr) {
deba@1187	1317	gr.saveSnapshot(*this);
deba@1187	1318	}
deba@1187	1319
deba@1187	1320	///Make a snapshot.
deba@1187	1321
deba@1187	1322	///This function makes a snapshot of the given graph.
deba@1187	1323	///It can be called more than once. In case of a repeated
deba@1187	1324	///call, the previous snapshot gets lost.
deba@1187	1325	void save(SmartBpGraph &gr)
deba@1187	1326	{
deba@1187	1327	gr.saveSnapshot(*this);
deba@1187	1328	}
deba@1187	1329
deba@1187	1330	///Undo the changes until the last snapshot.
deba@1187	1331
deba@1187	1332	///This function undos the changes until the last snapshot
deba@1187	1333	///created by save() or Snapshot(SmartBpGraph&).
deba@1187	1334	void restore()
deba@1187	1335	{
deba@1187	1336	_graph->restoreSnapshot(*this);
deba@1187	1337	}
deba@1187	1338	};
deba@1187	1339	};
deba@1187	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>
	Fri, 22 May 2015 17:47:18 +0200
changeset 1357	2126945deb6a
parent 1193	c8fa41fcc4a7
child 1336	0759d974de81
permissions	-rw-r--r--