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@427
|
5 |
* Copyright (C) 2003-2011
|
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 |
///Base of SmartDigraph
|
deba@109
|
36 |
|
deba@109
|
37 |
///Base of SmartDigraph
|
deba@109
|
38 |
///
|
deba@109
|
39 |
class SmartDigraphBase {
|
deba@109
|
40 |
protected:
|
deba@109
|
41 |
|
alpar@209
|
42 |
struct NodeT
|
deba@109
|
43 |
{
|
alpar@209
|
44 |
int first_in, first_out;
|
deba@109
|
45 |
NodeT() {}
|
deba@109
|
46 |
};
|
alpar@209
|
47 |
struct ArcT
|
deba@109
|
48 |
{
|
alpar@209
|
49 |
int target, source, next_in, next_out;
|
alpar@209
|
50 |
ArcT() {}
|
deba@109
|
51 |
};
|
deba@109
|
52 |
|
deba@109
|
53 |
std::vector<NodeT> nodes;
|
deba@109
|
54 |
std::vector<ArcT> arcs;
|
alpar@209
|
55 |
|
deba@109
|
56 |
public:
|
deba@109
|
57 |
|
deba@109
|
58 |
typedef SmartDigraphBase Graph;
|
deba@109
|
59 |
|
deba@109
|
60 |
class Node;
|
deba@109
|
61 |
class Arc;
|
deba@109
|
62 |
|
deba@109
|
63 |
public:
|
deba@109
|
64 |
|
deba@109
|
65 |
SmartDigraphBase() : nodes(), arcs() { }
|
alpar@209
|
66 |
SmartDigraphBase(const SmartDigraphBase &_g)
|
deba@109
|
67 |
: nodes(_g.nodes), arcs(_g.arcs) { }
|
alpar@209
|
68 |
|
deba@109
|
69 |
typedef True NodeNumTag;
|
deba@139
|
70 |
typedef True EdgeNumTag;
|
deba@109
|
71 |
|
deba@109
|
72 |
int nodeNum() const { return nodes.size(); }
|
deba@109
|
73 |
int arcNum() const { return arcs.size(); }
|
deba@109
|
74 |
|
deba@109
|
75 |
int maxNodeId() const { return nodes.size()-1; }
|
deba@109
|
76 |
int maxArcId() const { return arcs.size()-1; }
|
deba@109
|
77 |
|
deba@109
|
78 |
Node addNode() {
|
alpar@209
|
79 |
int n = nodes.size();
|
deba@109
|
80 |
nodes.push_back(NodeT());
|
deba@109
|
81 |
nodes[n].first_in = -1;
|
deba@109
|
82 |
nodes[n].first_out = -1;
|
deba@109
|
83 |
return Node(n);
|
deba@109
|
84 |
}
|
alpar@209
|
85 |
|
deba@109
|
86 |
Arc addArc(Node u, Node v) {
|
alpar@209
|
87 |
int n = arcs.size();
|
deba@109
|
88 |
arcs.push_back(ArcT());
|
alpar@209
|
89 |
arcs[n].source = u._id;
|
deba@109
|
90 |
arcs[n].target = v._id;
|
deba@109
|
91 |
arcs[n].next_out = nodes[u._id].first_out;
|
deba@109
|
92 |
arcs[n].next_in = nodes[v._id].first_in;
|
deba@109
|
93 |
nodes[u._id].first_out = nodes[v._id].first_in = n;
|
deba@109
|
94 |
|
deba@109
|
95 |
return Arc(n);
|
deba@109
|
96 |
}
|
deba@109
|
97 |
|
deba@109
|
98 |
void clear() {
|
deba@109
|
99 |
arcs.clear();
|
deba@109
|
100 |
nodes.clear();
|
deba@109
|
101 |
}
|
deba@109
|
102 |
|
deba@109
|
103 |
Node source(Arc a) const { return Node(arcs[a._id].source); }
|
deba@109
|
104 |
Node target(Arc a) const { return Node(arcs[a._id].target); }
|
deba@109
|
105 |
|
deba@109
|
106 |
static int id(Node v) { return v._id; }
|
deba@109
|
107 |
static int id(Arc a) { return a._id; }
|
deba@109
|
108 |
|
deba@109
|
109 |
static Node nodeFromId(int id) { return Node(id);}
|
deba@109
|
110 |
static Arc arcFromId(int id) { return Arc(id);}
|
deba@109
|
111 |
|
alpar@209
|
112 |
bool valid(Node n) const {
|
alpar@209
|
113 |
return n._id >= 0 && n._id < static_cast<int>(nodes.size());
|
deba@149
|
114 |
}
|
alpar@209
|
115 |
bool valid(Arc a) const {
|
alpar@209
|
116 |
return a._id >= 0 && a._id < static_cast<int>(arcs.size());
|
deba@149
|
117 |
}
|
deba@149
|
118 |
|
deba@109
|
119 |
class Node {
|
deba@109
|
120 |
friend class SmartDigraphBase;
|
deba@109
|
121 |
friend class SmartDigraph;
|
deba@109
|
122 |
|
deba@109
|
123 |
protected:
|
deba@109
|
124 |
int _id;
|
deba@109
|
125 |
explicit Node(int id) : _id(id) {}
|
deba@109
|
126 |
public:
|
deba@109
|
127 |
Node() {}
|
deba@109
|
128 |
Node (Invalid) : _id(-1) {}
|
deba@109
|
129 |
bool operator==(const Node i) const {return _id == i._id;}
|
deba@109
|
130 |
bool operator!=(const Node i) const {return _id != i._id;}
|
deba@109
|
131 |
bool operator<(const Node i) const {return _id < i._id;}
|
deba@109
|
132 |
};
|
alpar@209
|
133 |
|
deba@109
|
134 |
|
deba@109
|
135 |
class Arc {
|
deba@109
|
136 |
friend class SmartDigraphBase;
|
deba@109
|
137 |
friend class SmartDigraph;
|
deba@109
|
138 |
|
deba@109
|
139 |
protected:
|
deba@109
|
140 |
int _id;
|
deba@109
|
141 |
explicit Arc(int id) : _id(id) {}
|
deba@109
|
142 |
public:
|
deba@109
|
143 |
Arc() { }
|
deba@109
|
144 |
Arc (Invalid) : _id(-1) {}
|
deba@109
|
145 |
bool operator==(const Arc i) const {return _id == i._id;}
|
deba@109
|
146 |
bool operator!=(const Arc i) const {return _id != i._id;}
|
deba@109
|
147 |
bool operator<(const Arc i) const {return _id < i._id;}
|
deba@109
|
148 |
};
|
deba@109
|
149 |
|
deba@109
|
150 |
void first(Node& node) const {
|
deba@109
|
151 |
node._id = nodes.size() - 1;
|
deba@109
|
152 |
}
|
deba@109
|
153 |
|
deba@109
|
154 |
static void next(Node& node) {
|
deba@109
|
155 |
--node._id;
|
deba@109
|
156 |
}
|
deba@109
|
157 |
|
deba@109
|
158 |
void first(Arc& arc) const {
|
deba@109
|
159 |
arc._id = arcs.size() - 1;
|
deba@109
|
160 |
}
|
deba@109
|
161 |
|
deba@109
|
162 |
static void next(Arc& arc) {
|
deba@109
|
163 |
--arc._id;
|
deba@109
|
164 |
}
|
deba@109
|
165 |
|
deba@109
|
166 |
void firstOut(Arc& arc, const Node& node) const {
|
deba@109
|
167 |
arc._id = nodes[node._id].first_out;
|
deba@109
|
168 |
}
|
deba@109
|
169 |
|
deba@109
|
170 |
void nextOut(Arc& arc) const {
|
deba@109
|
171 |
arc._id = arcs[arc._id].next_out;
|
deba@109
|
172 |
}
|
deba@109
|
173 |
|
deba@109
|
174 |
void firstIn(Arc& arc, const Node& node) const {
|
deba@109
|
175 |
arc._id = nodes[node._id].first_in;
|
deba@109
|
176 |
}
|
alpar@209
|
177 |
|
deba@109
|
178 |
void nextIn(Arc& arc) const {
|
deba@109
|
179 |
arc._id = arcs[arc._id].next_in;
|
deba@109
|
180 |
}
|
deba@109
|
181 |
|
deba@109
|
182 |
};
|
deba@109
|
183 |
|
deba@109
|
184 |
typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
|
deba@109
|
185 |
|
deba@109
|
186 |
///\ingroup graphs
|
deba@109
|
187 |
///
|
deba@109
|
188 |
///\brief A smart directed graph class.
|
deba@109
|
189 |
///
|
deba@109
|
190 |
///This is a simple and fast digraph implementation.
|
deba@109
|
191 |
///It is also quite memory efficient, but at the price
|
deba@109
|
192 |
///that <b> it does support only limited (only stack-like)
|
deba@109
|
193 |
///node and arc deletions</b>.
|
deba@109
|
194 |
///It conforms to the \ref concepts::Digraph "Digraph concept" with
|
deba@109
|
195 |
///an important extra feature that its maps are real \ref
|
deba@109
|
196 |
///concepts::ReferenceMap "reference map"s.
|
deba@109
|
197 |
///
|
deba@109
|
198 |
///\sa concepts::Digraph.
|
deba@109
|
199 |
class SmartDigraph : public ExtendedSmartDigraphBase {
|
deba@109
|
200 |
public:
|
deba@109
|
201 |
|
deba@109
|
202 |
typedef ExtendedSmartDigraphBase Parent;
|
deba@109
|
203 |
|
deba@109
|
204 |
private:
|
deba@109
|
205 |
|
deba@109
|
206 |
///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
|
deba@109
|
207 |
|
deba@109
|
208 |
///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
|
deba@109
|
209 |
///
|
deba@109
|
210 |
SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
|
deba@109
|
211 |
///\brief Assignment of SmartDigraph to another one is \e not allowed.
|
deba@109
|
212 |
///Use DigraphCopy() instead.
|
deba@109
|
213 |
|
deba@109
|
214 |
///Assignment of SmartDigraph to another one is \e not allowed.
|
deba@109
|
215 |
///Use DigraphCopy() instead.
|
deba@109
|
216 |
void operator=(const SmartDigraph &) {}
|
deba@109
|
217 |
|
deba@109
|
218 |
public:
|
alpar@209
|
219 |
|
deba@109
|
220 |
/// Constructor
|
alpar@209
|
221 |
|
deba@109
|
222 |
/// Constructor.
|
deba@109
|
223 |
///
|
deba@109
|
224 |
SmartDigraph() {};
|
alpar@209
|
225 |
|
deba@109
|
226 |
///Add a new node to the digraph.
|
alpar@209
|
227 |
|
deba@109
|
228 |
/// \return the new node.
|
deba@109
|
229 |
///
|
deba@109
|
230 |
Node addNode() { return Parent::addNode(); }
|
alpar@209
|
231 |
|
deba@109
|
232 |
///Add a new arc to the digraph.
|
alpar@209
|
233 |
|
deba@109
|
234 |
///Add a new arc to the digraph with source node \c s
|
deba@109
|
235 |
///and target node \c t.
|
deba@109
|
236 |
///\return the new arc.
|
alpar@209
|
237 |
Arc addArc(const Node& s, const Node& t) {
|
alpar@209
|
238 |
return Parent::addArc(s, t);
|
deba@109
|
239 |
}
|
deba@109
|
240 |
|
deba@109
|
241 |
/// \brief Using this it is possible to avoid the superfluous memory
|
deba@109
|
242 |
/// allocation.
|
deba@109
|
243 |
|
deba@109
|
244 |
/// Using this it is possible to avoid the superfluous memory
|
deba@109
|
245 |
/// allocation: if you know that the digraph you want to build will
|
deba@109
|
246 |
/// be very large (e.g. it will contain millions of nodes and/or arcs)
|
deba@109
|
247 |
/// then it is worth reserving space for this amount before starting
|
deba@109
|
248 |
/// to build the digraph.
|
deba@109
|
249 |
/// \sa reserveArc
|
deba@109
|
250 |
void reserveNode(int n) { nodes.reserve(n); };
|
deba@109
|
251 |
|
deba@109
|
252 |
/// \brief Using this it is possible to avoid the superfluous memory
|
deba@109
|
253 |
/// allocation.
|
deba@109
|
254 |
|
deba@109
|
255 |
/// Using this it is possible to avoid the superfluous memory
|
deba@109
|
256 |
/// allocation: if you know that the digraph you want to build will
|
deba@109
|
257 |
/// be very large (e.g. it will contain millions of nodes and/or arcs)
|
deba@109
|
258 |
/// then it is worth reserving space for this amount before starting
|
deba@109
|
259 |
/// to build the digraph.
|
deba@109
|
260 |
/// \sa reserveNode
|
deba@109
|
261 |
void reserveArc(int m) { arcs.reserve(m); };
|
deba@109
|
262 |
|
deba@149
|
263 |
/// \brief Node validity check
|
deba@149
|
264 |
///
|
deba@149
|
265 |
/// This function gives back true if the given node is valid,
|
alpar@209
|
266 |
/// ie. it is a real node of the graph.
|
deba@149
|
267 |
///
|
deba@149
|
268 |
/// \warning A removed node (using Snapshot) could become valid again
|
deba@149
|
269 |
/// when new nodes are added to the graph.
|
deba@149
|
270 |
bool valid(Node n) const { return Parent::valid(n); }
|
deba@149
|
271 |
|
deba@149
|
272 |
/// \brief Arc validity check
|
deba@149
|
273 |
///
|
deba@149
|
274 |
/// This function gives back true if the given arc is valid,
|
alpar@209
|
275 |
/// ie. it is a real arc of the graph.
|
deba@149
|
276 |
///
|
deba@149
|
277 |
/// \warning A removed arc (using Snapshot) could become valid again
|
deba@149
|
278 |
/// when new arcs are added to the graph.
|
deba@149
|
279 |
bool valid(Arc a) const { return Parent::valid(a); }
|
deba@149
|
280 |
|
deba@109
|
281 |
///Clear the digraph.
|
alpar@209
|
282 |
|
deba@109
|
283 |
///Erase all the nodes and arcs from the digraph.
|
deba@109
|
284 |
///
|
deba@109
|
285 |
void clear() {
|
deba@109
|
286 |
Parent::clear();
|
deba@109
|
287 |
}
|
deba@109
|
288 |
|
deba@109
|
289 |
///Split a node.
|
alpar@209
|
290 |
|
deba@109
|
291 |
///This function splits a node. First a new node is added to the digraph,
|
deba@109
|
292 |
///then the source of each outgoing arc of \c n is moved to this new node.
|
deba@109
|
293 |
///If \c connect is \c true (this is the default value), then a new arc
|
deba@109
|
294 |
///from \c n to the newly created node is also added.
|
deba@109
|
295 |
///\return The newly created node.
|
deba@109
|
296 |
///
|
deba@109
|
297 |
///\note The <tt>Arc</tt>s
|
deba@109
|
298 |
///referencing a moved arc remain
|
deba@109
|
299 |
///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
|
deba@109
|
300 |
///may be invalidated.
|
deba@109
|
301 |
///\warning This functionality cannot be used together with the Snapshot
|
deba@109
|
302 |
///feature.
|
deba@109
|
303 |
Node split(Node n, bool connect = true)
|
deba@109
|
304 |
{
|
deba@109
|
305 |
Node b = addNode();
|
deba@109
|
306 |
nodes[b._id].first_out=nodes[n._id].first_out;
|
deba@109
|
307 |
nodes[n._id].first_out=-1;
|
kpeter@335
|
308 |
for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
|
kpeter@335
|
309 |
arcs[i].source=b._id;
|
kpeter@335
|
310 |
}
|
deba@109
|
311 |
if(connect) addArc(n,b);
|
deba@109
|
312 |
return b;
|
deba@109
|
313 |
}
|
deba@109
|
314 |
|
deba@109
|
315 |
public:
|
alpar@209
|
316 |
|
deba@109
|
317 |
class Snapshot;
|
deba@109
|
318 |
|
deba@109
|
319 |
protected:
|
deba@109
|
320 |
|
deba@109
|
321 |
void restoreSnapshot(const Snapshot &s)
|
deba@109
|
322 |
{
|
deba@109
|
323 |
while(s.arc_num<arcs.size()) {
|
deba@109
|
324 |
Arc arc = arcFromId(arcs.size()-1);
|
alpar@209
|
325 |
Parent::notifier(Arc()).erase(arc);
|
alpar@209
|
326 |
nodes[arcs.back().source].first_out=arcs.back().next_out;
|
alpar@209
|
327 |
nodes[arcs.back().target].first_in=arcs.back().next_in;
|
alpar@209
|
328 |
arcs.pop_back();
|
deba@109
|
329 |
}
|
deba@109
|
330 |
while(s.node_num<nodes.size()) {
|
deba@109
|
331 |
Node node = nodeFromId(nodes.size()-1);
|
alpar@209
|
332 |
Parent::notifier(Node()).erase(node);
|
alpar@209
|
333 |
nodes.pop_back();
|
deba@109
|
334 |
}
|
alpar@209
|
335 |
}
|
deba@109
|
336 |
|
deba@109
|
337 |
public:
|
deba@109
|
338 |
|
deba@109
|
339 |
///Class to make a snapshot of the digraph and to restrore to it later.
|
deba@109
|
340 |
|
deba@109
|
341 |
///Class to make a snapshot of the digraph and to restrore to it later.
|
deba@109
|
342 |
///
|
deba@109
|
343 |
///The newly added nodes and arcs can be removed using the
|
deba@109
|
344 |
///restore() function.
|
deba@109
|
345 |
///\note After you restore a state, you cannot restore
|
deba@109
|
346 |
///a later state, in other word you cannot add again the arcs deleted
|
deba@109
|
347 |
///by restore() using another one Snapshot instance.
|
deba@109
|
348 |
///
|
deba@109
|
349 |
///\warning If you do not use correctly the snapshot that can cause
|
deba@109
|
350 |
///either broken program, invalid state of the digraph, valid but
|
deba@109
|
351 |
///not the restored digraph or no change. Because the runtime performance
|
deba@109
|
352 |
///the validity of the snapshot is not stored.
|
alpar@209
|
353 |
class Snapshot
|
deba@109
|
354 |
{
|
deba@109
|
355 |
SmartDigraph *_graph;
|
deba@109
|
356 |
protected:
|
deba@109
|
357 |
friend class SmartDigraph;
|
deba@109
|
358 |
unsigned int node_num;
|
deba@109
|
359 |
unsigned int arc_num;
|
deba@109
|
360 |
public:
|
deba@109
|
361 |
///Default constructor.
|
alpar@209
|
362 |
|
deba@109
|
363 |
///Default constructor.
|
deba@109
|
364 |
///To actually make a snapshot you must call save().
|
deba@109
|
365 |
///
|
deba@109
|
366 |
Snapshot() : _graph(0) {}
|
deba@109
|
367 |
///Constructor that immediately makes a snapshot
|
alpar@209
|
368 |
|
deba@109
|
369 |
///This constructor immediately makes a snapshot of the digraph.
|
kpeter@317
|
370 |
///\param graph The digraph we make a snapshot of.
|
deba@109
|
371 |
Snapshot(SmartDigraph &graph) : _graph(&graph) {
|
alpar@209
|
372 |
node_num=_graph->nodes.size();
|
alpar@209
|
373 |
arc_num=_graph->arcs.size();
|
deba@109
|
374 |
}
|
deba@109
|
375 |
|
deba@109
|
376 |
///Make a snapshot.
|
deba@109
|
377 |
|
deba@109
|
378 |
///Make a snapshot of the digraph.
|
deba@109
|
379 |
///
|
deba@109
|
380 |
///This function can be called more than once. In case of a repeated
|
deba@109
|
381 |
///call, the previous snapshot gets lost.
|
kpeter@317
|
382 |
///\param graph The digraph we make the snapshot of.
|
alpar@209
|
383 |
void save(SmartDigraph &graph)
|
deba@109
|
384 |
{
|
alpar@209
|
385 |
_graph=&graph;
|
alpar@209
|
386 |
node_num=_graph->nodes.size();
|
alpar@209
|
387 |
arc_num=_graph->arcs.size();
|
deba@109
|
388 |
}
|
deba@109
|
389 |
|
deba@109
|
390 |
///Undo the changes until a snapshot.
|
alpar@209
|
391 |
|
deba@109
|
392 |
///Undo the changes until a snapshot created by save().
|
deba@109
|
393 |
///
|
deba@109
|
394 |
///\note After you restored a state, you cannot restore
|
deba@109
|
395 |
///a later state, in other word you cannot add again the arcs deleted
|
deba@109
|
396 |
///by restore().
|
deba@109
|
397 |
void restore()
|
deba@109
|
398 |
{
|
alpar@209
|
399 |
_graph->restoreSnapshot(*this);
|
deba@109
|
400 |
}
|
deba@109
|
401 |
};
|
deba@109
|
402 |
};
|
deba@109
|
403 |
|
deba@109
|
404 |
|
deba@109
|
405 |
class SmartGraphBase {
|
deba@109
|
406 |
|
deba@109
|
407 |
protected:
|
deba@109
|
408 |
|
deba@109
|
409 |
struct NodeT {
|
deba@109
|
410 |
int first_out;
|
deba@109
|
411 |
};
|
alpar@209
|
412 |
|
deba@109
|
413 |
struct ArcT {
|
deba@109
|
414 |
int target;
|
deba@109
|
415 |
int next_out;
|
deba@109
|
416 |
};
|
deba@109
|
417 |
|
deba@109
|
418 |
std::vector<NodeT> nodes;
|
deba@109
|
419 |
std::vector<ArcT> arcs;
|
deba@109
|
420 |
|
deba@109
|
421 |
int first_free_arc;
|
alpar@209
|
422 |
|
deba@109
|
423 |
public:
|
alpar@209
|
424 |
|
deba@109
|
425 |
typedef SmartGraphBase Digraph;
|
deba@109
|
426 |
|
deba@109
|
427 |
class Node;
|
deba@109
|
428 |
class Arc;
|
deba@109
|
429 |
class Edge;
|
alpar@209
|
430 |
|
deba@109
|
431 |
class Node {
|
deba@109
|
432 |
friend class SmartGraphBase;
|
deba@109
|
433 |
protected:
|
deba@109
|
434 |
|
deba@109
|
435 |
int _id;
|
deba@109
|
436 |
explicit Node(int id) { _id = id;}
|
deba@109
|
437 |
|
deba@109
|
438 |
public:
|
deba@109
|
439 |
Node() {}
|
deba@109
|
440 |
Node (Invalid) { _id = -1; }
|
deba@109
|
441 |
bool operator==(const Node& node) const {return _id == node._id;}
|
deba@109
|
442 |
bool operator!=(const Node& node) const {return _id != node._id;}
|
deba@109
|
443 |
bool operator<(const Node& node) const {return _id < node._id;}
|
deba@109
|
444 |
};
|
deba@109
|
445 |
|
deba@109
|
446 |
class Edge {
|
deba@109
|
447 |
friend class SmartGraphBase;
|
deba@109
|
448 |
protected:
|
deba@109
|
449 |
|
deba@109
|
450 |
int _id;
|
deba@109
|
451 |
explicit Edge(int id) { _id = id;}
|
deba@109
|
452 |
|
deba@109
|
453 |
public:
|
deba@109
|
454 |
Edge() {}
|
deba@109
|
455 |
Edge (Invalid) { _id = -1; }
|
deba@109
|
456 |
bool operator==(const Edge& arc) const {return _id == arc._id;}
|
deba@109
|
457 |
bool operator!=(const Edge& arc) const {return _id != arc._id;}
|
deba@109
|
458 |
bool operator<(const Edge& arc) const {return _id < arc._id;}
|
deba@109
|
459 |
};
|
deba@109
|
460 |
|
deba@109
|
461 |
class Arc {
|
deba@109
|
462 |
friend class SmartGraphBase;
|
deba@109
|
463 |
protected:
|
deba@109
|
464 |
|
deba@109
|
465 |
int _id;
|
deba@109
|
466 |
explicit Arc(int id) { _id = id;}
|
deba@109
|
467 |
|
deba@109
|
468 |
public:
|
alpar@427
|
469 |
operator Edge() const {
|
alpar@427
|
470 |
return _id != -1 ? edgeFromId(_id / 2) : INVALID;
|
deba@238
|
471 |
}
|
deba@109
|
472 |
|
deba@109
|
473 |
Arc() {}
|
deba@109
|
474 |
Arc (Invalid) { _id = -1; }
|
deba@109
|
475 |
bool operator==(const Arc& arc) const {return _id == arc._id;}
|
deba@109
|
476 |
bool operator!=(const Arc& arc) const {return _id != arc._id;}
|
deba@109
|
477 |
bool operator<(const Arc& arc) const {return _id < arc._id;}
|
deba@109
|
478 |
};
|
deba@109
|
479 |
|
deba@109
|
480 |
|
deba@109
|
481 |
|
deba@109
|
482 |
SmartGraphBase()
|
deba@109
|
483 |
: nodes(), arcs() {}
|
deba@109
|
484 |
|
alpar@209
|
485 |
|
alpar@209
|
486 |
int maxNodeId() const { return nodes.size()-1; }
|
deba@109
|
487 |
int maxEdgeId() const { return arcs.size() / 2 - 1; }
|
deba@109
|
488 |
int maxArcId() const { return arcs.size()-1; }
|
deba@109
|
489 |
|
deba@109
|
490 |
Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }
|
deba@109
|
491 |
Node target(Arc e) const { return Node(arcs[e._id].target); }
|
deba@109
|
492 |
|
deba@125
|
493 |
Node u(Edge e) const { return Node(arcs[2 * e._id].target); }
|
deba@125
|
494 |
Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
|
deba@109
|
495 |
|
deba@109
|
496 |
static bool direction(Arc e) {
|
deba@109
|
497 |
return (e._id & 1) == 1;
|
deba@109
|
498 |
}
|
deba@109
|
499 |
|
deba@109
|
500 |
static Arc direct(Edge e, bool d) {
|
deba@109
|
501 |
return Arc(e._id * 2 + (d ? 1 : 0));
|
deba@109
|
502 |
}
|
deba@109
|
503 |
|
alpar@209
|
504 |
void first(Node& node) const {
|
deba@109
|
505 |
node._id = nodes.size() - 1;
|
deba@109
|
506 |
}
|
deba@109
|
507 |
|
deba@109
|
508 |
void next(Node& node) const {
|
deba@109
|
509 |
--node._id;
|
deba@109
|
510 |
}
|
deba@109
|
511 |
|
alpar@209
|
512 |
void first(Arc& arc) const {
|
deba@109
|
513 |
arc._id = arcs.size() - 1;
|
deba@109
|
514 |
}
|
deba@109
|
515 |
|
deba@109
|
516 |
void next(Arc& arc) const {
|
deba@109
|
517 |
--arc._id;
|
deba@109
|
518 |
}
|
deba@109
|
519 |
|
alpar@209
|
520 |
void first(Edge& arc) const {
|
deba@109
|
521 |
arc._id = arcs.size() / 2 - 1;
|
deba@109
|
522 |
}
|
deba@109
|
523 |
|
deba@109
|
524 |
void next(Edge& arc) const {
|
deba@109
|
525 |
--arc._id;
|
deba@109
|
526 |
}
|
deba@109
|
527 |
|
deba@109
|
528 |
void firstOut(Arc &arc, const Node& v) const {
|
deba@109
|
529 |
arc._id = nodes[v._id].first_out;
|
deba@109
|
530 |
}
|
deba@109
|
531 |
void nextOut(Arc &arc) const {
|
deba@109
|
532 |
arc._id = arcs[arc._id].next_out;
|
deba@109
|
533 |
}
|
deba@109
|
534 |
|
deba@109
|
535 |
void firstIn(Arc &arc, const Node& v) const {
|
deba@109
|
536 |
arc._id = ((nodes[v._id].first_out) ^ 1);
|
deba@109
|
537 |
if (arc._id == -2) arc._id = -1;
|
deba@109
|
538 |
}
|
deba@109
|
539 |
void nextIn(Arc &arc) const {
|
deba@109
|
540 |
arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
|
deba@109
|
541 |
if (arc._id == -2) arc._id = -1;
|
deba@109
|
542 |
}
|
deba@109
|
543 |
|
deba@109
|
544 |
void firstInc(Edge &arc, bool& d, const Node& v) const {
|
deba@109
|
545 |
int de = nodes[v._id].first_out;
|
deba@109
|
546 |
if (de != -1) {
|
deba@109
|
547 |
arc._id = de / 2;
|
deba@109
|
548 |
d = ((de & 1) == 1);
|
deba@109
|
549 |
} else {
|
deba@109
|
550 |
arc._id = -1;
|
deba@109
|
551 |
d = true;
|
deba@109
|
552 |
}
|
deba@109
|
553 |
}
|
deba@109
|
554 |
void nextInc(Edge &arc, bool& d) const {
|
deba@109
|
555 |
int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
|
deba@109
|
556 |
if (de != -1) {
|
deba@109
|
557 |
arc._id = de / 2;
|
deba@109
|
558 |
d = ((de & 1) == 1);
|
deba@109
|
559 |
} else {
|
deba@109
|
560 |
arc._id = -1;
|
alpar@209
|
561 |
d = true;
|
deba@109
|
562 |
}
|
deba@109
|
563 |
}
|
alpar@209
|
564 |
|
deba@109
|
565 |
static int id(Node v) { return v._id; }
|
deba@109
|
566 |
static int id(Arc e) { return e._id; }
|
deba@109
|
567 |
static int id(Edge e) { return e._id; }
|
deba@109
|
568 |
|
deba@109
|
569 |
static Node nodeFromId(int id) { return Node(id);}
|
deba@109
|
570 |
static Arc arcFromId(int id) { return Arc(id);}
|
deba@109
|
571 |
static Edge edgeFromId(int id) { return Edge(id);}
|
deba@109
|
572 |
|
alpar@209
|
573 |
bool valid(Node n) const {
|
alpar@209
|
574 |
return n._id >= 0 && n._id < static_cast<int>(nodes.size());
|
deba@149
|
575 |
}
|
alpar@209
|
576 |
bool valid(Arc a) const {
|
deba@149
|
577 |
return a._id >= 0 && a._id < static_cast<int>(arcs.size());
|
deba@149
|
578 |
}
|
alpar@209
|
579 |
bool valid(Edge e) const {
|
alpar@209
|
580 |
return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
|
deba@149
|
581 |
}
|
deba@149
|
582 |
|
alpar@209
|
583 |
Node addNode() {
|
deba@109
|
584 |
int n = nodes.size();
|
deba@109
|
585 |
nodes.push_back(NodeT());
|
deba@109
|
586 |
nodes[n].first_out = -1;
|
alpar@209
|
587 |
|
deba@109
|
588 |
return Node(n);
|
deba@109
|
589 |
}
|
alpar@209
|
590 |
|
deba@138
|
591 |
Edge addEdge(Node u, Node v) {
|
deba@109
|
592 |
int n = arcs.size();
|
deba@109
|
593 |
arcs.push_back(ArcT());
|
deba@109
|
594 |
arcs.push_back(ArcT());
|
alpar@209
|
595 |
|
deba@109
|
596 |
arcs[n].target = u._id;
|
deba@109
|
597 |
arcs[n | 1].target = v._id;
|
deba@109
|
598 |
|
deba@109
|
599 |
arcs[n].next_out = nodes[v._id].first_out;
|
deba@109
|
600 |
nodes[v._id].first_out = n;
|
deba@109
|
601 |
|
alpar@209
|
602 |
arcs[n | 1].next_out = nodes[u._id].first_out;
|
deba@109
|
603 |
nodes[u._id].first_out = (n | 1);
|
deba@109
|
604 |
|
deba@109
|
605 |
return Edge(n / 2);
|
deba@109
|
606 |
}
|
alpar@209
|
607 |
|
deba@109
|
608 |
void clear() {
|
deba@109
|
609 |
arcs.clear();
|
deba@109
|
610 |
nodes.clear();
|
deba@109
|
611 |
}
|
deba@109
|
612 |
|
deba@109
|
613 |
};
|
deba@109
|
614 |
|
deba@109
|
615 |
typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
|
deba@109
|
616 |
|
deba@109
|
617 |
/// \ingroup graphs
|
deba@109
|
618 |
///
|
deba@109
|
619 |
/// \brief A smart undirected graph class.
|
deba@109
|
620 |
///
|
deba@109
|
621 |
/// This is a simple and fast graph implementation.
|
deba@109
|
622 |
/// It is also quite memory efficient, but at the price
|
deba@109
|
623 |
/// that <b> it does support only limited (only stack-like)
|
deba@109
|
624 |
/// node and arc deletions</b>.
|
alpar@209
|
625 |
/// Except from this it conforms to
|
deba@109
|
626 |
/// the \ref concepts::Graph "Graph concept".
|
deba@109
|
627 |
///
|
deba@109
|
628 |
/// It also has an
|
deba@109
|
629 |
/// important extra feature that
|
deba@109
|
630 |
/// its maps are real \ref concepts::ReferenceMap "reference map"s.
|
deba@109
|
631 |
///
|
deba@109
|
632 |
/// \sa concepts::Graph.
|
deba@109
|
633 |
///
|
deba@109
|
634 |
class SmartGraph : public ExtendedSmartGraphBase {
|
deba@109
|
635 |
private:
|
deba@109
|
636 |
|
deba@109
|
637 |
///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
|
deba@109
|
638 |
|
deba@109
|
639 |
///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
|
deba@109
|
640 |
///
|
deba@109
|
641 |
SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
|
deba@109
|
642 |
|
deba@109
|
643 |
///\brief Assignment of SmartGraph to another one is \e not allowed.
|
deba@109
|
644 |
///Use GraphCopy() instead.
|
deba@109
|
645 |
|
deba@109
|
646 |
///Assignment of SmartGraph to another one is \e not allowed.
|
deba@109
|
647 |
///Use GraphCopy() instead.
|
deba@109
|
648 |
void operator=(const SmartGraph &) {}
|
deba@109
|
649 |
|
deba@109
|
650 |
public:
|
deba@109
|
651 |
|
deba@109
|
652 |
typedef ExtendedSmartGraphBase Parent;
|
deba@109
|
653 |
|
deba@109
|
654 |
/// Constructor
|
alpar@209
|
655 |
|
deba@109
|
656 |
/// Constructor.
|
deba@109
|
657 |
///
|
deba@109
|
658 |
SmartGraph() {}
|
deba@109
|
659 |
|
deba@109
|
660 |
///Add a new node to the graph.
|
alpar@209
|
661 |
|
deba@109
|
662 |
/// \return the new node.
|
deba@109
|
663 |
///
|
deba@109
|
664 |
Node addNode() { return Parent::addNode(); }
|
alpar@209
|
665 |
|
deba@109
|
666 |
///Add a new edge to the graph.
|
alpar@209
|
667 |
|
deba@109
|
668 |
///Add a new edge to the graph with node \c s
|
deba@109
|
669 |
///and \c t.
|
deba@109
|
670 |
///\return the new edge.
|
alpar@209
|
671 |
Edge addEdge(const Node& s, const Node& t) {
|
alpar@209
|
672 |
return Parent::addEdge(s, t);
|
deba@109
|
673 |
}
|
deba@109
|
674 |
|
deba@149
|
675 |
/// \brief Node validity check
|
deba@149
|
676 |
///
|
deba@149
|
677 |
/// This function gives back true if the given node is valid,
|
alpar@209
|
678 |
/// ie. it is a real node of the graph.
|
deba@149
|
679 |
///
|
deba@149
|
680 |
/// \warning A removed node (using Snapshot) could become valid again
|
deba@149
|
681 |
/// when new nodes are added to the graph.
|
deba@149
|
682 |
bool valid(Node n) const { return Parent::valid(n); }
|
deba@149
|
683 |
|
deba@149
|
684 |
/// \brief Arc validity check
|
deba@149
|
685 |
///
|
deba@149
|
686 |
/// This function gives back true if the given arc is valid,
|
alpar@209
|
687 |
/// ie. it is a real arc of the graph.
|
deba@149
|
688 |
///
|
deba@149
|
689 |
/// \warning A removed arc (using Snapshot) could become valid again
|
deba@149
|
690 |
/// when new edges are added to the graph.
|
deba@149
|
691 |
bool valid(Arc a) const { return Parent::valid(a); }
|
deba@149
|
692 |
|
deba@149
|
693 |
/// \brief Edge validity check
|
deba@149
|
694 |
///
|
deba@149
|
695 |
/// This function gives back true if the given edge is valid,
|
alpar@209
|
696 |
/// ie. it is a real edge of the graph.
|
deba@149
|
697 |
///
|
deba@149
|
698 |
/// \warning A removed edge (using Snapshot) could become valid again
|
deba@149
|
699 |
/// when new edges are added to the graph.
|
deba@149
|
700 |
bool valid(Edge e) const { return Parent::valid(e); }
|
deba@149
|
701 |
|
deba@109
|
702 |
///Clear the graph.
|
alpar@209
|
703 |
|
deba@109
|
704 |
///Erase all the nodes and edges from the graph.
|
deba@109
|
705 |
///
|
deba@109
|
706 |
void clear() {
|
deba@109
|
707 |
Parent::clear();
|
deba@109
|
708 |
}
|
deba@109
|
709 |
|
deba@109
|
710 |
public:
|
alpar@209
|
711 |
|
deba@109
|
712 |
class Snapshot;
|
deba@109
|
713 |
|
deba@109
|
714 |
protected:
|
deba@109
|
715 |
|
deba@109
|
716 |
void saveSnapshot(Snapshot &s)
|
deba@109
|
717 |
{
|
deba@109
|
718 |
s._graph = this;
|
deba@109
|
719 |
s.node_num = nodes.size();
|
deba@109
|
720 |
s.arc_num = arcs.size();
|
deba@109
|
721 |
}
|
deba@109
|
722 |
|
deba@109
|
723 |
void restoreSnapshot(const Snapshot &s)
|
deba@109
|
724 |
{
|
deba@109
|
725 |
while(s.arc_num<arcs.size()) {
|
deba@109
|
726 |
int n=arcs.size()-1;
|
deba@109
|
727 |
Edge arc=edgeFromId(n/2);
|
alpar@209
|
728 |
Parent::notifier(Edge()).erase(arc);
|
deba@109
|
729 |
std::vector<Arc> dir;
|
deba@109
|
730 |
dir.push_back(arcFromId(n));
|
deba@109
|
731 |
dir.push_back(arcFromId(n-1));
|
alpar@209
|
732 |
Parent::notifier(Arc()).erase(dir);
|
kpeter@337
|
733 |
nodes[arcs[n-1].target].first_out=arcs[n].next_out;
|
kpeter@337
|
734 |
nodes[arcs[n].target].first_out=arcs[n-1].next_out;
|
alpar@209
|
735 |
arcs.pop_back();
|
alpar@209
|
736 |
arcs.pop_back();
|
deba@109
|
737 |
}
|
deba@109
|
738 |
while(s.node_num<nodes.size()) {
|
deba@109
|
739 |
int n=nodes.size()-1;
|
deba@109
|
740 |
Node node = nodeFromId(n);
|
alpar@209
|
741 |
Parent::notifier(Node()).erase(node);
|
alpar@209
|
742 |
nodes.pop_back();
|
deba@109
|
743 |
}
|
alpar@209
|
744 |
}
|
deba@109
|
745 |
|
deba@109
|
746 |
public:
|
deba@109
|
747 |
|
deba@109
|
748 |
///Class to make a snapshot of the digraph and to restrore to it later.
|
deba@109
|
749 |
|
deba@109
|
750 |
///Class to make a snapshot of the digraph and to restrore to it later.
|
deba@109
|
751 |
///
|
deba@109
|
752 |
///The newly added nodes and arcs can be removed using the
|
deba@109
|
753 |
///restore() function.
|
deba@109
|
754 |
///
|
deba@109
|
755 |
///\note After you restore a state, you cannot restore
|
deba@109
|
756 |
///a later state, in other word you cannot add again the arcs deleted
|
deba@109
|
757 |
///by restore() using another one Snapshot instance.
|
deba@109
|
758 |
///
|
deba@109
|
759 |
///\warning If you do not use correctly the snapshot that can cause
|
deba@109
|
760 |
///either broken program, invalid state of the digraph, valid but
|
deba@109
|
761 |
///not the restored digraph or no change. Because the runtime performance
|
deba@109
|
762 |
///the validity of the snapshot is not stored.
|
alpar@209
|
763 |
class Snapshot
|
deba@109
|
764 |
{
|
deba@109
|
765 |
SmartGraph *_graph;
|
deba@109
|
766 |
protected:
|
deba@109
|
767 |
friend class SmartGraph;
|
deba@109
|
768 |
unsigned int node_num;
|
deba@109
|
769 |
unsigned int arc_num;
|
deba@109
|
770 |
public:
|
deba@109
|
771 |
///Default constructor.
|
alpar@209
|
772 |
|
deba@109
|
773 |
///Default constructor.
|
deba@109
|
774 |
///To actually make a snapshot you must call save().
|
deba@109
|
775 |
///
|
deba@109
|
776 |
Snapshot() : _graph(0) {}
|
deba@109
|
777 |
///Constructor that immediately makes a snapshot
|
alpar@209
|
778 |
|
deba@109
|
779 |
///This constructor immediately makes a snapshot of the digraph.
|
kpeter@317
|
780 |
///\param graph The digraph we make a snapshot of.
|
deba@109
|
781 |
Snapshot(SmartGraph &graph) {
|
deba@109
|
782 |
graph.saveSnapshot(*this);
|
deba@109
|
783 |
}
|
deba@109
|
784 |
|
deba@109
|
785 |
///Make a snapshot.
|
deba@109
|
786 |
|
deba@109
|
787 |
///Make a snapshot of the graph.
|
deba@109
|
788 |
///
|
deba@109
|
789 |
///This function can be called more than once. In case of a repeated
|
deba@109
|
790 |
///call, the previous snapshot gets lost.
|
kpeter@317
|
791 |
///\param graph The digraph we make the snapshot of.
|
alpar@209
|
792 |
void save(SmartGraph &graph)
|
deba@109
|
793 |
{
|
deba@109
|
794 |
graph.saveSnapshot(*this);
|
deba@109
|
795 |
}
|
deba@109
|
796 |
|
deba@109
|
797 |
///Undo the changes until a snapshot.
|
alpar@209
|
798 |
|
deba@109
|
799 |
///Undo the changes until a snapshot created by save().
|
deba@109
|
800 |
///
|
deba@109
|
801 |
///\note After you restored a state, you cannot restore
|
deba@109
|
802 |
///a later state, in other word you cannot add again the arcs deleted
|
deba@109
|
803 |
///by restore().
|
deba@109
|
804 |
void restore()
|
deba@109
|
805 |
{
|
deba@109
|
806 |
_graph->restoreSnapshot(*this);
|
deba@109
|
807 |
}
|
deba@109
|
808 |
};
|
deba@109
|
809 |
};
|
alpar@209
|
810 |
|
deba@109
|
811 |
} //namespace lemon
|
deba@109
|
812 |
|
deba@109
|
813 |
|
deba@109
|
814 |
#endif //LEMON_SMART_GRAPH_H
|