alpar@948
|
1 |
/* -*- C++ -*-
|
alpar@948
|
2 |
*
|
alpar@1956
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
alpar@1956
|
4 |
*
|
alpar@1956
|
5 |
* Copyright (C) 2003-2006
|
alpar@1956
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@1359
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@948
|
8 |
*
|
alpar@948
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@948
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@948
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@948
|
12 |
*
|
alpar@948
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@948
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@948
|
15 |
* purpose.
|
alpar@948
|
16 |
*
|
alpar@948
|
17 |
*/
|
alpar@395
|
18 |
|
alpar@921
|
19 |
#ifndef LEMON_LIST_GRAPH_H
|
alpar@921
|
20 |
#define LEMON_LIST_GRAPH_H
|
alpar@395
|
21 |
|
alpar@948
|
22 |
///\ingroup graphs
|
alpar@948
|
23 |
///\file
|
deba@2115
|
24 |
///\brief ListGraph class.
|
alpar@948
|
25 |
|
deba@1791
|
26 |
#include <lemon/bits/graph_extender.h>
|
deba@782
|
27 |
|
deba@1979
|
28 |
#include <vector>
|
alpar@1011
|
29 |
#include <list>
|
deba@782
|
30 |
|
alpar@921
|
31 |
namespace lemon {
|
alpar@395
|
32 |
|
klao@946
|
33 |
class ListGraphBase {
|
alpar@406
|
34 |
|
alpar@949
|
35 |
protected:
|
klao@946
|
36 |
struct NodeT {
|
deba@1470
|
37 |
int first_in, first_out;
|
alpar@397
|
38 |
int prev, next;
|
alpar@395
|
39 |
};
|
klao@946
|
40 |
|
klao@946
|
41 |
struct EdgeT {
|
alpar@986
|
42 |
int target, source;
|
alpar@397
|
43 |
int prev_in, prev_out;
|
alpar@397
|
44 |
int next_in, next_out;
|
alpar@395
|
45 |
};
|
alpar@395
|
46 |
|
alpar@395
|
47 |
std::vector<NodeT> nodes;
|
klao@946
|
48 |
|
alpar@397
|
49 |
int first_node;
|
klao@946
|
50 |
|
alpar@397
|
51 |
int first_free_node;
|
klao@946
|
52 |
|
alpar@395
|
53 |
std::vector<EdgeT> edges;
|
klao@946
|
54 |
|
alpar@397
|
55 |
int first_free_edge;
|
alpar@395
|
56 |
|
deba@782
|
57 |
public:
|
alpar@395
|
58 |
|
klao@946
|
59 |
typedef ListGraphBase Graph;
|
alpar@397
|
60 |
|
klao@946
|
61 |
class Node {
|
marci@975
|
62 |
friend class ListGraphBase;
|
klao@946
|
63 |
protected:
|
alpar@395
|
64 |
|
klao@946
|
65 |
int id;
|
deba@2031
|
66 |
explicit Node(int pid) { id = pid;}
|
alpar@395
|
67 |
|
klao@946
|
68 |
public:
|
klao@946
|
69 |
Node() {}
|
klao@946
|
70 |
Node (Invalid) { id = -1; }
|
klao@946
|
71 |
bool operator==(const Node& node) const {return id == node.id;}
|
klao@946
|
72 |
bool operator!=(const Node& node) const {return id != node.id;}
|
klao@946
|
73 |
bool operator<(const Node& node) const {return id < node.id;}
|
klao@946
|
74 |
};
|
deba@782
|
75 |
|
klao@946
|
76 |
class Edge {
|
marci@975
|
77 |
friend class ListGraphBase;
|
klao@946
|
78 |
protected:
|
deba@782
|
79 |
|
klao@946
|
80 |
int id;
|
deba@2031
|
81 |
explicit Edge(int pid) { id = pid;}
|
alpar@395
|
82 |
|
klao@946
|
83 |
public:
|
klao@946
|
84 |
Edge() {}
|
klao@946
|
85 |
Edge (Invalid) { id = -1; }
|
klao@946
|
86 |
bool operator==(const Edge& edge) const {return id == edge.id;}
|
klao@946
|
87 |
bool operator!=(const Edge& edge) const {return id != edge.id;}
|
klao@946
|
88 |
bool operator<(const Edge& edge) const {return id < edge.id;}
|
klao@946
|
89 |
};
|
klao@946
|
90 |
|
klao@946
|
91 |
|
klao@946
|
92 |
|
klao@946
|
93 |
ListGraphBase()
|
deba@782
|
94 |
: nodes(), first_node(-1),
|
deba@782
|
95 |
first_free_node(-1), edges(), first_free_edge(-1) {}
|
deba@782
|
96 |
|
alpar@395
|
97 |
|
alpar@813
|
98 |
/// Maximum node ID.
|
alpar@813
|
99 |
|
alpar@813
|
100 |
/// Maximum node ID.
|
alpar@813
|
101 |
///\sa id(Node)
|
deba@1791
|
102 |
int maxNodeId() const { return nodes.size()-1; }
|
klao@946
|
103 |
|
alpar@813
|
104 |
/// Maximum edge ID.
|
alpar@813
|
105 |
|
alpar@813
|
106 |
/// Maximum edge ID.
|
alpar@813
|
107 |
///\sa id(Edge)
|
deba@1791
|
108 |
int maxEdgeId() const { return edges.size()-1; }
|
alpar@395
|
109 |
|
deba@2031
|
110 |
Node source(Edge e) const { return Node(edges[e.id].source); }
|
deba@2031
|
111 |
Node target(Edge e) const { return Node(edges[e.id].target); }
|
alpar@395
|
112 |
|
alpar@395
|
113 |
|
klao@946
|
114 |
void first(Node& node) const {
|
klao@946
|
115 |
node.id = first_node;
|
klao@946
|
116 |
}
|
klao@946
|
117 |
|
klao@946
|
118 |
void next(Node& node) const {
|
klao@946
|
119 |
node.id = nodes[node.id].next;
|
klao@946
|
120 |
}
|
klao@946
|
121 |
|
klao@946
|
122 |
|
klao@946
|
123 |
void first(Edge& e) const {
|
klao@946
|
124 |
int n;
|
klao@946
|
125 |
for(n = first_node;
|
klao@946
|
126 |
n!=-1 && nodes[n].first_in == -1;
|
klao@946
|
127 |
n = nodes[n].next);
|
klao@946
|
128 |
e.id = (n == -1) ? -1 : nodes[n].first_in;
|
klao@946
|
129 |
}
|
klao@946
|
130 |
|
klao@946
|
131 |
void next(Edge& edge) const {
|
klao@946
|
132 |
if (edges[edge.id].next_in != -1) {
|
klao@946
|
133 |
edge.id = edges[edge.id].next_in;
|
klao@946
|
134 |
} else {
|
klao@946
|
135 |
int n;
|
alpar@986
|
136 |
for(n = nodes[edges[edge.id].target].next;
|
klao@946
|
137 |
n!=-1 && nodes[n].first_in == -1;
|
klao@946
|
138 |
n = nodes[n].next);
|
klao@946
|
139 |
edge.id = (n == -1) ? -1 : nodes[n].first_in;
|
klao@946
|
140 |
}
|
klao@946
|
141 |
}
|
klao@946
|
142 |
|
klao@946
|
143 |
void firstOut(Edge &e, const Node& v) const {
|
klao@946
|
144 |
e.id = nodes[v.id].first_out;
|
klao@946
|
145 |
}
|
klao@946
|
146 |
void nextOut(Edge &e) const {
|
klao@946
|
147 |
e.id=edges[e.id].next_out;
|
klao@946
|
148 |
}
|
klao@946
|
149 |
|
klao@946
|
150 |
void firstIn(Edge &e, const Node& v) const {
|
klao@946
|
151 |
e.id = nodes[v.id].first_in;
|
klao@946
|
152 |
}
|
klao@946
|
153 |
void nextIn(Edge &e) const {
|
klao@946
|
154 |
e.id=edges[e.id].next_in;
|
klao@946
|
155 |
}
|
klao@946
|
156 |
|
alpar@813
|
157 |
|
klao@946
|
158 |
static int id(Node v) { return v.id; }
|
klao@946
|
159 |
static int id(Edge e) { return e.id; }
|
alpar@395
|
160 |
|
deba@1791
|
161 |
static Node nodeFromId(int id) { return Node(id);}
|
deba@1791
|
162 |
static Edge edgeFromId(int id) { return Edge(id);}
|
deba@1106
|
163 |
|
alpar@397
|
164 |
/// Adds a new node to the graph.
|
alpar@397
|
165 |
|
alpar@813
|
166 |
/// \warning It adds the new node to the front of the list.
|
alpar@397
|
167 |
/// (i.e. the lastly added node becomes the first.)
|
klao@946
|
168 |
Node addNode() {
|
alpar@397
|
169 |
int n;
|
alpar@397
|
170 |
|
klao@946
|
171 |
if(first_free_node==-1) {
|
klao@946
|
172 |
n = nodes.size();
|
klao@946
|
173 |
nodes.push_back(NodeT());
|
klao@946
|
174 |
} else {
|
alpar@397
|
175 |
n = first_free_node;
|
alpar@397
|
176 |
first_free_node = nodes[n].next;
|
alpar@397
|
177 |
}
|
alpar@397
|
178 |
|
alpar@397
|
179 |
nodes[n].next = first_node;
|
alpar@397
|
180 |
if(first_node != -1) nodes[first_node].prev = n;
|
alpar@397
|
181 |
first_node = n;
|
alpar@397
|
182 |
nodes[n].prev = -1;
|
alpar@397
|
183 |
|
alpar@397
|
184 |
nodes[n].first_in = nodes[n].first_out = -1;
|
alpar@397
|
185 |
|
klao@946
|
186 |
return Node(n);
|
alpar@395
|
187 |
}
|
alpar@395
|
188 |
|
alpar@395
|
189 |
Edge addEdge(Node u, Node v) {
|
klao@946
|
190 |
int n;
|
klao@946
|
191 |
|
klao@946
|
192 |
if (first_free_edge == -1) {
|
klao@946
|
193 |
n = edges.size();
|
klao@946
|
194 |
edges.push_back(EdgeT());
|
klao@946
|
195 |
} else {
|
alpar@397
|
196 |
n = first_free_edge;
|
alpar@397
|
197 |
first_free_edge = edges[n].next_in;
|
alpar@397
|
198 |
}
|
alpar@397
|
199 |
|
alpar@986
|
200 |
edges[n].source = u.id;
|
alpar@986
|
201 |
edges[n].target = v.id;
|
alpar@395
|
202 |
|
klao@946
|
203 |
edges[n].next_out = nodes[u.id].first_out;
|
klao@946
|
204 |
if(nodes[u.id].first_out != -1) {
|
klao@946
|
205 |
edges[nodes[u.id].first_out].prev_out = n;
|
klao@946
|
206 |
}
|
klao@946
|
207 |
|
klao@946
|
208 |
edges[n].next_in = nodes[v.id].first_in;
|
klao@946
|
209 |
if(nodes[v.id].first_in != -1) {
|
klao@946
|
210 |
edges[nodes[v.id].first_in].prev_in = n;
|
klao@946
|
211 |
}
|
klao@946
|
212 |
|
alpar@397
|
213 |
edges[n].prev_in = edges[n].prev_out = -1;
|
alpar@397
|
214 |
|
klao@946
|
215 |
nodes[u.id].first_out = nodes[v.id].first_in = n;
|
alpar@397
|
216 |
|
klao@946
|
217 |
return Edge(n);
|
alpar@395
|
218 |
}
|
alpar@774
|
219 |
|
klao@946
|
220 |
void erase(const Node& node) {
|
klao@946
|
221 |
int n = node.id;
|
klao@946
|
222 |
|
klao@946
|
223 |
if(nodes[n].next != -1) {
|
klao@946
|
224 |
nodes[nodes[n].next].prev = nodes[n].prev;
|
klao@946
|
225 |
}
|
klao@946
|
226 |
|
klao@946
|
227 |
if(nodes[n].prev != -1) {
|
klao@946
|
228 |
nodes[nodes[n].prev].next = nodes[n].next;
|
klao@946
|
229 |
} else {
|
klao@946
|
230 |
first_node = nodes[n].next;
|
klao@946
|
231 |
}
|
klao@946
|
232 |
|
klao@946
|
233 |
nodes[n].next = first_free_node;
|
klao@946
|
234 |
first_free_node = n;
|
alpar@395
|
235 |
|
alpar@774
|
236 |
}
|
alpar@774
|
237 |
|
klao@946
|
238 |
void erase(const Edge& edge) {
|
klao@946
|
239 |
int n = edge.id;
|
alpar@397
|
240 |
|
klao@946
|
241 |
if(edges[n].next_in!=-1) {
|
alpar@397
|
242 |
edges[edges[n].next_in].prev_in = edges[n].prev_in;
|
klao@946
|
243 |
}
|
klao@946
|
244 |
|
klao@946
|
245 |
if(edges[n].prev_in!=-1) {
|
alpar@397
|
246 |
edges[edges[n].prev_in].next_in = edges[n].next_in;
|
klao@946
|
247 |
} else {
|
alpar@986
|
248 |
nodes[edges[n].target].first_in = edges[n].next_in;
|
klao@946
|
249 |
}
|
klao@946
|
250 |
|
alpar@397
|
251 |
|
klao@946
|
252 |
if(edges[n].next_out!=-1) {
|
alpar@397
|
253 |
edges[edges[n].next_out].prev_out = edges[n].prev_out;
|
klao@946
|
254 |
}
|
klao@946
|
255 |
|
klao@946
|
256 |
if(edges[n].prev_out!=-1) {
|
alpar@397
|
257 |
edges[edges[n].prev_out].next_out = edges[n].next_out;
|
klao@946
|
258 |
} else {
|
alpar@986
|
259 |
nodes[edges[n].source].first_out = edges[n].next_out;
|
klao@946
|
260 |
}
|
alpar@397
|
261 |
|
alpar@397
|
262 |
edges[n].next_in = first_free_edge;
|
alpar@695
|
263 |
first_free_edge = n;
|
alpar@397
|
264 |
|
alpar@397
|
265 |
}
|
alpar@397
|
266 |
|
alpar@397
|
267 |
void clear() {
|
deba@782
|
268 |
edges.clear();
|
deba@782
|
269 |
nodes.clear();
|
klao@946
|
270 |
first_node = first_free_node = first_free_edge = -1;
|
deba@937
|
271 |
}
|
deba@937
|
272 |
|
alpar@949
|
273 |
protected:
|
deba@2111
|
274 |
void changeTarget(Edge e, Node n)
|
alpar@949
|
275 |
{
|
alpar@949
|
276 |
if(edges[e.id].next_in != -1)
|
alpar@949
|
277 |
edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
|
alpar@949
|
278 |
if(edges[e.id].prev_in != -1)
|
alpar@949
|
279 |
edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
|
alpar@986
|
280 |
else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
|
deba@1702
|
281 |
if (nodes[n.id].first_in != -1) {
|
deba@1702
|
282 |
edges[nodes[n.id].first_in].prev_in = e.id;
|
deba@1702
|
283 |
}
|
alpar@986
|
284 |
edges[e.id].target = n.id;
|
alpar@949
|
285 |
edges[e.id].prev_in = -1;
|
alpar@949
|
286 |
edges[e.id].next_in = nodes[n.id].first_in;
|
alpar@949
|
287 |
nodes[n.id].first_in = e.id;
|
alpar@949
|
288 |
}
|
deba@2111
|
289 |
void changeSource(Edge e, Node n)
|
alpar@949
|
290 |
{
|
alpar@949
|
291 |
if(edges[e.id].next_out != -1)
|
alpar@949
|
292 |
edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
|
alpar@949
|
293 |
if(edges[e.id].prev_out != -1)
|
alpar@949
|
294 |
edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
|
alpar@986
|
295 |
else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
|
deba@1702
|
296 |
if (nodes[n.id].first_out != -1) {
|
deba@1702
|
297 |
edges[nodes[n.id].first_out].prev_out = e.id;
|
deba@1702
|
298 |
}
|
alpar@986
|
299 |
edges[e.id].source = n.id;
|
alpar@949
|
300 |
edges[e.id].prev_out = -1;
|
alpar@949
|
301 |
edges[e.id].next_out = nodes[n.id].first_out;
|
alpar@949
|
302 |
nodes[n.id].first_out = e.id;
|
alpar@949
|
303 |
}
|
alpar@949
|
304 |
|
alpar@919
|
305 |
};
|
deba@909
|
306 |
|
deba@1979
|
307 |
typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
|
alpar@400
|
308 |
|
deba@2115
|
309 |
/// \ingroup graphs
|
alpar@400
|
310 |
|
alpar@948
|
311 |
///A list graph class.
|
alpar@400
|
312 |
|
alpar@948
|
313 |
///This is a simple and fast erasable graph implementation.
|
alpar@948
|
314 |
///
|
deba@2111
|
315 |
///It conforms to the \ref concept::Graph "Graph" concept and it
|
deba@2111
|
316 |
///also provides several additional useful extra functionalities.
|
deba@2111
|
317 |
///The most of the member functions and nested classes are
|
deba@2111
|
318 |
///documented only in the concept class.
|
deba@2111
|
319 |
///\sa concept::Graph.
|
deba@782
|
320 |
|
deba@1999
|
321 |
class ListGraph : public ExtendedListGraphBase {
|
alpar@948
|
322 |
public:
|
deba@1999
|
323 |
|
deba@1999
|
324 |
typedef ExtendedListGraphBase Parent;
|
deba@1999
|
325 |
|
deba@2111
|
326 |
///Add a new node to the graph.
|
deba@2111
|
327 |
|
deba@2111
|
328 |
/// \return the new node.
|
deba@2111
|
329 |
///
|
deba@2111
|
330 |
Node addNode() { return Parent::addNode(); }
|
deba@2111
|
331 |
|
deba@2111
|
332 |
///Add a new edge to the graph.
|
deba@2111
|
333 |
|
deba@2111
|
334 |
///Add a new edge to the graph with source node \c s
|
deba@2111
|
335 |
///and target node \c t.
|
deba@2111
|
336 |
///\return the new edge.
|
deba@2111
|
337 |
Edge addEdge(const Node& s, const Node& t) {
|
deba@2111
|
338 |
return Parent::addEdge(s, t);
|
deba@2111
|
339 |
}
|
deba@2111
|
340 |
|
alpar@1546
|
341 |
/// Changes the target of \c e to \c n
|
alpar@948
|
342 |
|
alpar@1546
|
343 |
/// Changes the target of \c e to \c n
|
alpar@948
|
344 |
///
|
deba@2114
|
345 |
///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
|
deba@2114
|
346 |
///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
|
deba@2114
|
347 |
///invalidated.
|
deba@1718
|
348 |
void changeTarget(Edge e, Node n) {
|
deba@2111
|
349 |
Parent::changeTarget(e,n);
|
deba@1718
|
350 |
}
|
alpar@1546
|
351 |
/// Changes the source of \c e to \c n
|
alpar@948
|
352 |
|
alpar@1546
|
353 |
/// Changes the source of \c e to \c n
|
alpar@948
|
354 |
///
|
deba@2114
|
355 |
///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
|
deba@2114
|
356 |
///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
|
deba@2114
|
357 |
///invalidated.
|
deba@1718
|
358 |
void changeSource(Edge e, Node n) {
|
deba@2111
|
359 |
Parent::changeSource(e,n);
|
deba@1718
|
360 |
}
|
alpar@949
|
361 |
|
alpar@1010
|
362 |
/// Invert the direction of an edge.
|
alpar@1010
|
363 |
|
deba@2114
|
364 |
///\note The <tt>Edge</tt>s referencing the changed edge remain
|
deba@2114
|
365 |
///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
|
deba@2114
|
366 |
///invalidated.
|
alpar@1010
|
367 |
void reverseEdge(Edge e) {
|
alpar@1010
|
368 |
Node t=target(e);
|
deba@2111
|
369 |
changeTarget(e,source(e));
|
deba@2111
|
370 |
changeSource(e,t);
|
alpar@1010
|
371 |
}
|
alpar@1010
|
372 |
|
deba@2111
|
373 |
/// \brief Using this it is possible to avoid the superfluous memory
|
deba@2111
|
374 |
/// allocation.
|
alpar@1010
|
375 |
|
deba@2107
|
376 |
///Using this it is possible to avoid the superfluous memory
|
deba@2107
|
377 |
///allocation: if you know that the graph you want to build will
|
deba@2107
|
378 |
///contain at least 10 million nodes then it is worth to reserve
|
deba@2107
|
379 |
///space for this amount before starting to build the graph.
|
deba@2107
|
380 |
void reserveNode(int n) { nodes.reserve(n); };
|
deba@2107
|
381 |
|
deba@2111
|
382 |
/// \brief Using this it is possible to avoid the superfluous memory
|
deba@2111
|
383 |
/// allocation.
|
deba@2107
|
384 |
|
deba@2107
|
385 |
///Using this it is possible to avoid the superfluous memory
|
deba@2107
|
386 |
///allocation: see the \ref reserveNode function.
|
alpar@949
|
387 |
void reserveEdge(int n) { edges.reserve(n); };
|
alpar@1010
|
388 |
|
deba@2107
|
389 |
|
alpar@1010
|
390 |
///Contract two nodes.
|
alpar@1010
|
391 |
|
alpar@1010
|
392 |
///This function contracts two nodes.
|
alpar@1010
|
393 |
///
|
alpar@1010
|
394 |
///Node \p b will be removed but instead of deleting
|
athos@2102
|
395 |
///incident edges, they will be joined to \p a.
|
alpar@1010
|
396 |
///The last parameter \p r controls whether to remove loops. \c true
|
alpar@1010
|
397 |
///means that loops will be removed.
|
alpar@1010
|
398 |
///
|
alpar@1010
|
399 |
///\note The <tt>Edge</tt>s
|
alpar@1281
|
400 |
///referencing a moved edge remain
|
athos@2102
|
401 |
///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
|
alpar@1010
|
402 |
///may be invalidated.
|
deba@1718
|
403 |
void contract(Node a, Node b, bool r = true)
|
alpar@1010
|
404 |
{
|
alpar@1010
|
405 |
for(OutEdgeIt e(*this,b);e!=INVALID;) {
|
alpar@1010
|
406 |
OutEdgeIt f=e;
|
alpar@1010
|
407 |
++f;
|
alpar@1010
|
408 |
if(r && target(e)==a) erase(e);
|
alpar@1546
|
409 |
else changeSource(e,a);
|
alpar@1010
|
410 |
e=f;
|
alpar@1010
|
411 |
}
|
alpar@1010
|
412 |
for(InEdgeIt e(*this,b);e!=INVALID;) {
|
alpar@1010
|
413 |
InEdgeIt f=e;
|
alpar@1010
|
414 |
++f;
|
alpar@1010
|
415 |
if(r && source(e)==a) erase(e);
|
alpar@1546
|
416 |
else changeTarget(e,a);
|
alpar@1010
|
417 |
e=f;
|
alpar@1010
|
418 |
}
|
alpar@1010
|
419 |
erase(b);
|
alpar@1010
|
420 |
}
|
alpar@1011
|
421 |
|
alpar@1281
|
422 |
///Split a node.
|
alpar@1011
|
423 |
|
alpar@1284
|
424 |
///This function splits a node. First a new node is added to the graph,
|
alpar@1284
|
425 |
///then the source of each outgoing edge of \c n is moved to this new node.
|
alpar@1281
|
426 |
///If \c connect is \c true (this is the default value), then a new edge
|
alpar@1281
|
427 |
///from \c n to the newly created node is also added.
|
alpar@1281
|
428 |
///\return The newly created node.
|
alpar@1281
|
429 |
///
|
alpar@1281
|
430 |
///\note The <tt>Edge</tt>s
|
alpar@1281
|
431 |
///referencing a moved edge remain
|
athos@2102
|
432 |
///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
|
alpar@1281
|
433 |
///may be invalidated.
|
alpar@1770
|
434 |
///\warning This functionality cannot be used together with the Snapshot
|
alpar@1284
|
435 |
///feature.
|
alpar@1281
|
436 |
///\todo It could be implemented in a bit faster way.
|
deba@2114
|
437 |
Node split(Node n, bool connect = true) {
|
alpar@1281
|
438 |
Node b = addNode();
|
alpar@1281
|
439 |
for(OutEdgeIt e(*this,n);e!=INVALID;) {
|
alpar@1281
|
440 |
OutEdgeIt f=e;
|
alpar@1281
|
441 |
++f;
|
alpar@1546
|
442 |
changeSource(e,b);
|
alpar@1281
|
443 |
e=f;
|
alpar@1281
|
444 |
}
|
deba@2114
|
445 |
if (connect) addEdge(n,b);
|
alpar@1281
|
446 |
return b;
|
alpar@1281
|
447 |
}
|
alpar@1281
|
448 |
|
alpar@1812
|
449 |
///Split an edge.
|
alpar@1812
|
450 |
|
athos@2102
|
451 |
///This function splits an edge. First a new node \c b is added to
|
athos@2102
|
452 |
///the graph, then the original edge is re-targeted to \c
|
athos@2102
|
453 |
///b. Finally an edge from \c b to the original target is added.
|
athos@2102
|
454 |
///\return The newly created node.
|
athos@2102
|
455 |
///\warning This functionality
|
athos@2102
|
456 |
///cannot be used together with the Snapshot feature.
|
deba@2114
|
457 |
Node split(Edge e) {
|
alpar@1812
|
458 |
Node b = addNode();
|
alpar@1812
|
459 |
addEdge(b,target(e));
|
alpar@1812
|
460 |
changeTarget(e,b);
|
alpar@1812
|
461 |
return b;
|
alpar@1812
|
462 |
}
|
alpar@1812
|
463 |
|
deba@2114
|
464 |
/// \brief Class to make a snapshot of the graph and restore
|
deba@2114
|
465 |
/// to it later.
|
alpar@1011
|
466 |
///
|
deba@2114
|
467 |
/// Class to make a snapshot of the graph and to restore it
|
deba@2114
|
468 |
/// later.
|
alpar@1011
|
469 |
///
|
deba@2114
|
470 |
/// The newly added nodes and edges can be removed using the
|
deba@2114
|
471 |
/// restore() function.
|
deba@2114
|
472 |
///
|
deba@2114
|
473 |
/// \warning Edge and node deletions cannot be restored.
|
deba@2114
|
474 |
class Snapshot {
|
deba@1774
|
475 |
public:
|
deba@1774
|
476 |
|
deba@1774
|
477 |
class UnsupportedOperation : public LogicError {
|
deba@1774
|
478 |
public:
|
deba@1774
|
479 |
virtual const char* exceptionName() const {
|
deba@1774
|
480 |
return "lemon::ListGraph::Snapshot::UnsupportedOperation";
|
deba@1774
|
481 |
}
|
deba@1774
|
482 |
};
|
deba@1774
|
483 |
|
deba@1774
|
484 |
|
deba@1999
|
485 |
protected:
|
deba@2114
|
486 |
|
deba@2114
|
487 |
typedef Parent::NodeNotifier NodeNotifier;
|
deba@2114
|
488 |
|
deba@2114
|
489 |
class NodeObserverProxy : public NodeNotifier::ObserverBase {
|
deba@2114
|
490 |
public:
|
deba@2114
|
491 |
|
deba@2114
|
492 |
NodeObserverProxy(Snapshot& _snapshot)
|
deba@2114
|
493 |
: snapshot(_snapshot) {}
|
deba@2114
|
494 |
|
deba@2114
|
495 |
using NodeNotifier::ObserverBase::attach;
|
deba@2114
|
496 |
using NodeNotifier::ObserverBase::detach;
|
deba@2114
|
497 |
using NodeNotifier::ObserverBase::attached;
|
deba@2114
|
498 |
|
deba@2114
|
499 |
protected:
|
deba@2114
|
500 |
|
deba@2114
|
501 |
virtual void add(const Node& node) {
|
deba@2114
|
502 |
snapshot.addNode(node);
|
deba@2114
|
503 |
}
|
deba@2114
|
504 |
virtual void add(const std::vector<Node>& nodes) {
|
deba@2114
|
505 |
for (int i = nodes.size() - 1; i >= 0; ++i) {
|
deba@2114
|
506 |
snapshot.addNode(nodes[i]);
|
deba@2114
|
507 |
}
|
deba@2114
|
508 |
}
|
deba@2114
|
509 |
virtual void erase(const Node& node) {
|
deba@2114
|
510 |
snapshot.eraseNode(node);
|
deba@2114
|
511 |
}
|
deba@2114
|
512 |
virtual void erase(const std::vector<Node>& nodes) {
|
deba@2114
|
513 |
for (int i = 0; i < (int)nodes.size(); ++i) {
|
deba@2114
|
514 |
if (!snapshot.eraseNode(nodes[i])) break;
|
deba@2114
|
515 |
}
|
deba@2114
|
516 |
}
|
deba@2114
|
517 |
virtual void build() {
|
deba@2114
|
518 |
NodeNotifier* notifier = getNotifier();
|
deba@2114
|
519 |
Node node;
|
deba@2114
|
520 |
std::vector<Node> nodes;
|
deba@2114
|
521 |
for (notifier->first(node); node != INVALID; notifier->next(node)) {
|
deba@2114
|
522 |
nodes.push_back(node);
|
deba@2114
|
523 |
}
|
deba@2114
|
524 |
for (int i = nodes.size() - 1; i >= 0; --i) {
|
deba@2114
|
525 |
snapshot.addNode(nodes[i]);
|
deba@2114
|
526 |
}
|
deba@2114
|
527 |
}
|
deba@2114
|
528 |
virtual void clear() {
|
deba@2114
|
529 |
NodeNotifier* notifier = getNotifier();
|
deba@2114
|
530 |
Node node;
|
deba@2114
|
531 |
for (notifier->first(node); node != INVALID; notifier->next(node)) {
|
deba@2114
|
532 |
if (!snapshot.eraseNode(node)) break;
|
deba@2114
|
533 |
}
|
deba@2114
|
534 |
}
|
deba@2114
|
535 |
|
deba@2114
|
536 |
Snapshot& snapshot;
|
deba@2114
|
537 |
};
|
deba@2114
|
538 |
|
deba@2114
|
539 |
class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
|
deba@2114
|
540 |
public:
|
deba@2114
|
541 |
|
deba@2114
|
542 |
EdgeObserverProxy(Snapshot& _snapshot)
|
deba@2114
|
543 |
: snapshot(_snapshot) {}
|
deba@2114
|
544 |
|
deba@2114
|
545 |
using EdgeNotifier::ObserverBase::attach;
|
deba@2114
|
546 |
using EdgeNotifier::ObserverBase::detach;
|
deba@2114
|
547 |
using EdgeNotifier::ObserverBase::attached;
|
deba@2114
|
548 |
|
deba@2114
|
549 |
protected:
|
deba@2114
|
550 |
|
deba@2114
|
551 |
virtual void add(const Edge& edge) {
|
deba@2114
|
552 |
snapshot.addEdge(edge);
|
deba@2114
|
553 |
}
|
deba@2114
|
554 |
virtual void add(const std::vector<Edge>& edges) {
|
deba@2114
|
555 |
for (int i = edges.size() - 1; i >= 0; ++i) {
|
deba@2114
|
556 |
snapshot.addEdge(edges[i]);
|
deba@2114
|
557 |
}
|
deba@2114
|
558 |
}
|
deba@2114
|
559 |
virtual void erase(const Edge& edge) {
|
deba@2114
|
560 |
snapshot.eraseEdge(edge);
|
deba@2114
|
561 |
}
|
deba@2114
|
562 |
virtual void erase(const std::vector<Edge>& edges) {
|
deba@2114
|
563 |
for (int i = 0; i < (int)edges.size(); ++i) {
|
deba@2114
|
564 |
if (!snapshot.eraseEdge(edges[i])) break;
|
deba@2114
|
565 |
}
|
deba@2114
|
566 |
}
|
deba@2114
|
567 |
virtual void build() {
|
deba@2114
|
568 |
EdgeNotifier* notifier = getNotifier();
|
deba@2114
|
569 |
Edge edge;
|
deba@2114
|
570 |
std::vector<Edge> edges;
|
deba@2114
|
571 |
for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
|
deba@2114
|
572 |
edges.push_back(edge);
|
deba@2114
|
573 |
}
|
deba@2114
|
574 |
for (int i = edges.size() - 1; i >= 0; --i) {
|
deba@2114
|
575 |
snapshot.addEdge(edges[i]);
|
deba@2114
|
576 |
}
|
deba@2114
|
577 |
}
|
deba@2114
|
578 |
virtual void clear() {
|
deba@2114
|
579 |
EdgeNotifier* notifier = getNotifier();
|
deba@2114
|
580 |
Edge edge;
|
deba@2114
|
581 |
for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
|
deba@2114
|
582 |
if (!snapshot.eraseEdge(edge)) break;
|
deba@2114
|
583 |
}
|
deba@2114
|
584 |
}
|
deba@2114
|
585 |
|
deba@2114
|
586 |
Snapshot& snapshot;
|
deba@2114
|
587 |
};
|
alpar@1011
|
588 |
|
deba@2114
|
589 |
ListGraph *graph;
|
deba@2114
|
590 |
|
deba@2114
|
591 |
NodeObserverProxy node_observer_proxy;
|
deba@2114
|
592 |
EdgeObserverProxy edge_observer_proxy;
|
deba@2114
|
593 |
|
alpar@1011
|
594 |
std::list<Node> added_nodes;
|
alpar@1011
|
595 |
std::list<Edge> added_edges;
|
deba@2114
|
596 |
|
deba@2114
|
597 |
|
deba@2114
|
598 |
void addNode(const Node& node) {
|
deba@2114
|
599 |
added_nodes.push_front(node);
|
alpar@1011
|
600 |
}
|
deba@2114
|
601 |
bool eraseNode(const Node& node) {
|
deba@2114
|
602 |
std::list<Node>::iterator it =
|
deba@2114
|
603 |
std::find(added_nodes.begin(), added_nodes.end(), node);
|
deba@2114
|
604 |
if (it == added_nodes.end()) {
|
deba@2114
|
605 |
clear();
|
deba@2114
|
606 |
return false;
|
deba@2114
|
607 |
} else {
|
deba@2114
|
608 |
added_nodes.erase(it);
|
deba@2114
|
609 |
return true;
|
deba@2114
|
610 |
}
|
alpar@1011
|
611 |
}
|
alpar@1011
|
612 |
|
deba@2114
|
613 |
void addEdge(const Edge& edge) {
|
deba@2114
|
614 |
added_edges.push_front(edge);
|
deba@2114
|
615 |
}
|
deba@2114
|
616 |
bool eraseEdge(const Edge& edge) {
|
deba@2114
|
617 |
std::list<Edge>::iterator it =
|
deba@2114
|
618 |
std::find(added_edges.begin(), added_edges.end(), edge);
|
deba@2114
|
619 |
if (it == added_edges.end()) {
|
deba@2114
|
620 |
clear();
|
deba@2114
|
621 |
return false;
|
deba@2114
|
622 |
} else {
|
deba@2114
|
623 |
added_edges.erase(it);
|
deba@2114
|
624 |
return true;
|
deba@2114
|
625 |
}
|
deba@2114
|
626 |
}
|
alpar@1457
|
627 |
|
deba@2114
|
628 |
void attach(ListGraph &_graph) {
|
deba@2114
|
629 |
graph = &_graph;
|
deba@2114
|
630 |
node_observer_proxy.attach(graph->getNotifier(Node()));
|
deba@2114
|
631 |
edge_observer_proxy.attach(graph->getNotifier(Edge()));
|
alpar@1011
|
632 |
}
|
alpar@1011
|
633 |
|
deba@2114
|
634 |
void detach() {
|
deba@2114
|
635 |
node_observer_proxy.detach();
|
deba@2114
|
636 |
edge_observer_proxy.detach();
|
deba@2114
|
637 |
}
|
deba@2114
|
638 |
|
deba@2114
|
639 |
void clear() {
|
deba@2114
|
640 |
detach();
|
deba@2114
|
641 |
added_nodes.clear();
|
deba@2114
|
642 |
added_edges.clear();
|
alpar@1011
|
643 |
}
|
deba@1774
|
644 |
|
alpar@1011
|
645 |
public:
|
deba@2114
|
646 |
|
deba@2114
|
647 |
/// \brief Default constructur.
|
deba@2114
|
648 |
///
|
deba@2114
|
649 |
/// Default constructor.
|
deba@2114
|
650 |
/// To actually make a snapshot you must call save().
|
deba@2114
|
651 |
Snapshot()
|
deba@2114
|
652 |
: graph(0), node_observer_proxy(*this),
|
deba@2114
|
653 |
edge_observer_proxy(*this) {}
|
alpar@1011
|
654 |
|
deba@2114
|
655 |
/// \brief Constructor that immediately makes a snapshot.
|
deba@2114
|
656 |
///
|
deba@2114
|
657 |
/// This constructor immediately makes a snapshot of the graph.
|
deba@2114
|
658 |
/// \param _graph The graph we make a snapshot of.
|
deba@2114
|
659 |
Snapshot(ListGraph &_graph)
|
deba@2114
|
660 |
: node_observer_proxy(*this),
|
deba@2114
|
661 |
edge_observer_proxy(*this) {
|
deba@2114
|
662 |
attach(_graph);
|
alpar@1011
|
663 |
}
|
alpar@1011
|
664 |
|
deba@2114
|
665 |
/// \brief Make a snapshot.
|
alpar@1011
|
666 |
///
|
deba@2114
|
667 |
/// Make a snapshot of the graph.
|
deba@2114
|
668 |
///
|
deba@2114
|
669 |
/// This function can be called more than once. In case of a repeated
|
deba@2114
|
670 |
/// call, the previous snapshot gets lost.
|
deba@2114
|
671 |
/// \param _graph The graph we make the snapshot of.
|
deba@2114
|
672 |
void save(ListGraph &_graph) {
|
deba@2114
|
673 |
clear();
|
deba@2114
|
674 |
attach(_graph);
|
alpar@1011
|
675 |
}
|
alpar@1011
|
676 |
|
deba@2114
|
677 |
/// \brief Undo the changes until the last snapshot.
|
deba@2114
|
678 |
//
|
deba@2114
|
679 |
/// Undo the changes until last snapshot created by save().
|
deba@2114
|
680 |
///
|
deba@2114
|
681 |
/// \todo This function might be called undo().
|
alpar@1011
|
682 |
void restore() {
|
deba@2114
|
683 |
detach();
|
alpar@1011
|
684 |
while(!added_edges.empty()) {
|
deba@2114
|
685 |
graph->erase(added_edges.front());
|
alpar@1011
|
686 |
added_edges.pop_front();
|
alpar@1011
|
687 |
}
|
alpar@1011
|
688 |
while(!added_nodes.empty()) {
|
deba@2114
|
689 |
graph->erase(added_nodes.front());
|
alpar@1011
|
690 |
added_nodes.pop_front();
|
alpar@1011
|
691 |
}
|
alpar@1011
|
692 |
}
|
deba@2114
|
693 |
|
deba@2114
|
694 |
/// \brief Gives back true when the snapshot is valid.
|
deba@2114
|
695 |
///
|
deba@2114
|
696 |
/// Gives back true when the snapshot is valid.
|
deba@2114
|
697 |
bool valid() const {
|
deba@2114
|
698 |
return node_observer_proxy.attached();
|
deba@2114
|
699 |
}
|
alpar@1011
|
700 |
};
|
alpar@1011
|
701 |
|
alpar@949
|
702 |
};
|
klao@1034
|
703 |
|
alpar@948
|
704 |
} //namespace lemon
|
klao@946
|
705 |
|
alpar@400
|
706 |
|
klao@946
|
707 |
#endif
|