klao@946
|
1 |
// -*- c++ -*-
|
alpar@395
|
2 |
|
alpar@921
|
3 |
#ifndef LEMON_LIST_GRAPH_H
|
alpar@921
|
4 |
#define LEMON_LIST_GRAPH_H
|
alpar@395
|
5 |
|
klao@946
|
6 |
#include <lemon/erasable_graph_extender.h>
|
klao@946
|
7 |
#include <lemon/clearable_graph_extender.h>
|
klao@946
|
8 |
#include <lemon/extendable_graph_extender.h>
|
alpar@395
|
9 |
|
klao@946
|
10 |
#include <lemon/idmappable_graph_extender.h>
|
alpar@395
|
11 |
|
klao@946
|
12 |
#include <lemon/iterable_graph_extender.h>
|
alpar@395
|
13 |
|
klao@946
|
14 |
#include <lemon/alteration_observer_registry.h>
|
deba@782
|
15 |
|
klao@946
|
16 |
#include <lemon/default_map.h>
|
deba@782
|
17 |
|
deba@782
|
18 |
|
alpar@921
|
19 |
namespace lemon {
|
alpar@395
|
20 |
|
klao@946
|
21 |
class ListGraphBase {
|
alpar@406
|
22 |
|
klao@946
|
23 |
struct NodeT {
|
alpar@397
|
24 |
int first_in,first_out;
|
alpar@397
|
25 |
int prev, next;
|
alpar@395
|
26 |
};
|
klao@946
|
27 |
|
klao@946
|
28 |
struct EdgeT {
|
alpar@397
|
29 |
int head, tail;
|
alpar@397
|
30 |
int prev_in, prev_out;
|
alpar@397
|
31 |
int next_in, next_out;
|
alpar@395
|
32 |
};
|
alpar@395
|
33 |
|
alpar@395
|
34 |
std::vector<NodeT> nodes;
|
klao@946
|
35 |
|
alpar@397
|
36 |
int first_node;
|
klao@946
|
37 |
|
alpar@397
|
38 |
int first_free_node;
|
klao@946
|
39 |
|
alpar@395
|
40 |
std::vector<EdgeT> edges;
|
klao@946
|
41 |
|
alpar@397
|
42 |
int first_free_edge;
|
alpar@395
|
43 |
|
deba@782
|
44 |
public:
|
alpar@395
|
45 |
|
klao@946
|
46 |
typedef ListGraphBase Graph;
|
alpar@397
|
47 |
|
klao@946
|
48 |
class Node {
|
klao@946
|
49 |
friend class Graph;
|
klao@946
|
50 |
protected:
|
alpar@395
|
51 |
|
klao@946
|
52 |
int id;
|
klao@946
|
53 |
Node(int pid) { id = pid;}
|
alpar@395
|
54 |
|
klao@946
|
55 |
public:
|
klao@946
|
56 |
Node() {}
|
klao@946
|
57 |
Node (Invalid) { id = -1; }
|
klao@946
|
58 |
bool operator==(const Node& node) const {return id == node.id;}
|
klao@946
|
59 |
bool operator!=(const Node& node) const {return id != node.id;}
|
klao@946
|
60 |
bool operator<(const Node& node) const {return id < node.id;}
|
klao@946
|
61 |
};
|
deba@782
|
62 |
|
klao@946
|
63 |
class Edge {
|
klao@946
|
64 |
friend class Graph;
|
klao@946
|
65 |
protected:
|
deba@782
|
66 |
|
klao@946
|
67 |
int id;
|
klao@946
|
68 |
Edge(int pid) { id = pid;}
|
alpar@395
|
69 |
|
klao@946
|
70 |
public:
|
klao@946
|
71 |
Edge() {}
|
klao@946
|
72 |
Edge (Invalid) { id = -1; }
|
klao@946
|
73 |
bool operator==(const Edge& edge) const {return id == edge.id;}
|
klao@946
|
74 |
bool operator!=(const Edge& edge) const {return id != edge.id;}
|
klao@946
|
75 |
bool operator<(const Edge& edge) const {return id < edge.id;}
|
klao@946
|
76 |
};
|
klao@946
|
77 |
|
klao@946
|
78 |
|
klao@946
|
79 |
|
klao@946
|
80 |
ListGraphBase()
|
deba@782
|
81 |
: nodes(), first_node(-1),
|
deba@782
|
82 |
first_free_node(-1), edges(), first_free_edge(-1) {}
|
deba@782
|
83 |
|
alpar@395
|
84 |
|
alpar@695
|
85 |
///it possible to avoid the superfluous memory allocation.
|
alpar@695
|
86 |
void reserveEdge(int n) { edges.reserve(n); };
|
alpar@695
|
87 |
|
alpar@813
|
88 |
/// Maximum node ID.
|
alpar@813
|
89 |
|
alpar@813
|
90 |
/// Maximum node ID.
|
alpar@813
|
91 |
///\sa id(Node)
|
alpar@813
|
92 |
int maxNodeId() const { return nodes.size()-1; }
|
klao@946
|
93 |
|
alpar@813
|
94 |
/// Maximum edge ID.
|
alpar@813
|
95 |
|
alpar@813
|
96 |
/// Maximum edge ID.
|
alpar@813
|
97 |
///\sa id(Edge)
|
alpar@813
|
98 |
int maxEdgeId() const { return edges.size()-1; }
|
alpar@395
|
99 |
|
klao@946
|
100 |
Node tail(Edge e) const { return edges[e.id].tail; }
|
klao@946
|
101 |
Node head(Edge e) const { return edges[e.id].head; }
|
alpar@395
|
102 |
|
alpar@395
|
103 |
|
klao@946
|
104 |
void first(Node& node) const {
|
klao@946
|
105 |
node.id = first_node;
|
klao@946
|
106 |
}
|
klao@946
|
107 |
|
klao@946
|
108 |
void next(Node& node) const {
|
klao@946
|
109 |
node.id = nodes[node.id].next;
|
klao@946
|
110 |
}
|
klao@946
|
111 |
|
klao@946
|
112 |
|
klao@946
|
113 |
void first(Edge& e) const {
|
klao@946
|
114 |
int n;
|
klao@946
|
115 |
for(n = first_node;
|
klao@946
|
116 |
n!=-1 && nodes[n].first_in == -1;
|
klao@946
|
117 |
n = nodes[n].next);
|
klao@946
|
118 |
e.id = (n == -1) ? -1 : nodes[n].first_in;
|
klao@946
|
119 |
}
|
klao@946
|
120 |
|
klao@946
|
121 |
void next(Edge& edge) const {
|
klao@946
|
122 |
if (edges[edge.id].next_in != -1) {
|
klao@946
|
123 |
edge.id = edges[edge.id].next_in;
|
klao@946
|
124 |
} else {
|
klao@946
|
125 |
int n;
|
klao@946
|
126 |
for(n = nodes[edges[edge.id].head].next;
|
klao@946
|
127 |
n!=-1 && nodes[n].first_in == -1;
|
klao@946
|
128 |
n = nodes[n].next);
|
klao@946
|
129 |
edge.id = (n == -1) ? -1 : nodes[n].first_in;
|
klao@946
|
130 |
}
|
klao@946
|
131 |
}
|
klao@946
|
132 |
|
klao@946
|
133 |
void firstOut(Edge &e, const Node& v) const {
|
klao@946
|
134 |
e.id = nodes[v.id].first_out;
|
klao@946
|
135 |
}
|
klao@946
|
136 |
void nextOut(Edge &e) const {
|
klao@946
|
137 |
e.id=edges[e.id].next_out;
|
klao@946
|
138 |
}
|
klao@946
|
139 |
|
klao@946
|
140 |
void firstIn(Edge &e, const Node& v) const {
|
klao@946
|
141 |
e.id = nodes[v.id].first_in;
|
klao@946
|
142 |
}
|
klao@946
|
143 |
void nextIn(Edge &e) const {
|
klao@946
|
144 |
e.id=edges[e.id].next_in;
|
klao@946
|
145 |
}
|
klao@946
|
146 |
|
alpar@813
|
147 |
|
klao@946
|
148 |
static int id(Node v) { return v.id; }
|
klao@946
|
149 |
static int id(Edge e) { return e.id; }
|
alpar@395
|
150 |
|
alpar@397
|
151 |
/// Adds a new node to the graph.
|
alpar@397
|
152 |
|
alpar@813
|
153 |
/// \warning It adds the new node to the front of the list.
|
alpar@397
|
154 |
/// (i.e. the lastly added node becomes the first.)
|
klao@946
|
155 |
Node addNode() {
|
alpar@397
|
156 |
int n;
|
alpar@397
|
157 |
|
klao@946
|
158 |
if(first_free_node==-1) {
|
klao@946
|
159 |
n = nodes.size();
|
klao@946
|
160 |
nodes.push_back(NodeT());
|
klao@946
|
161 |
} else {
|
alpar@397
|
162 |
n = first_free_node;
|
alpar@397
|
163 |
first_free_node = nodes[n].next;
|
alpar@397
|
164 |
}
|
alpar@397
|
165 |
|
alpar@397
|
166 |
nodes[n].next = first_node;
|
alpar@397
|
167 |
if(first_node != -1) nodes[first_node].prev = n;
|
alpar@397
|
168 |
first_node = n;
|
alpar@397
|
169 |
nodes[n].prev = -1;
|
alpar@397
|
170 |
|
alpar@397
|
171 |
nodes[n].first_in = nodes[n].first_out = -1;
|
alpar@397
|
172 |
|
klao@946
|
173 |
return Node(n);
|
alpar@395
|
174 |
}
|
alpar@395
|
175 |
|
alpar@395
|
176 |
Edge addEdge(Node u, Node v) {
|
klao@946
|
177 |
int n;
|
klao@946
|
178 |
|
klao@946
|
179 |
if (first_free_edge == -1) {
|
klao@946
|
180 |
n = edges.size();
|
klao@946
|
181 |
edges.push_back(EdgeT());
|
klao@946
|
182 |
} else {
|
alpar@397
|
183 |
n = first_free_edge;
|
alpar@397
|
184 |
first_free_edge = edges[n].next_in;
|
alpar@397
|
185 |
}
|
alpar@397
|
186 |
|
klao@946
|
187 |
edges[n].tail = u.id;
|
klao@946
|
188 |
edges[n].head = v.id;
|
alpar@395
|
189 |
|
klao@946
|
190 |
edges[n].next_out = nodes[u.id].first_out;
|
klao@946
|
191 |
if(nodes[u.id].first_out != -1) {
|
klao@946
|
192 |
edges[nodes[u.id].first_out].prev_out = n;
|
klao@946
|
193 |
}
|
klao@946
|
194 |
|
klao@946
|
195 |
edges[n].next_in = nodes[v.id].first_in;
|
klao@946
|
196 |
if(nodes[v.id].first_in != -1) {
|
klao@946
|
197 |
edges[nodes[v.id].first_in].prev_in = n;
|
klao@946
|
198 |
}
|
klao@946
|
199 |
|
alpar@397
|
200 |
edges[n].prev_in = edges[n].prev_out = -1;
|
alpar@397
|
201 |
|
klao@946
|
202 |
nodes[u.id].first_out = nodes[v.id].first_in = n;
|
alpar@397
|
203 |
|
klao@946
|
204 |
return Edge(n);
|
alpar@395
|
205 |
}
|
alpar@774
|
206 |
|
klao@946
|
207 |
void erase(const Node& node) {
|
klao@946
|
208 |
int n = node.id;
|
klao@946
|
209 |
|
klao@946
|
210 |
if(nodes[n].next != -1) {
|
klao@946
|
211 |
nodes[nodes[n].next].prev = nodes[n].prev;
|
klao@946
|
212 |
}
|
klao@946
|
213 |
|
klao@946
|
214 |
if(nodes[n].prev != -1) {
|
klao@946
|
215 |
nodes[nodes[n].prev].next = nodes[n].next;
|
klao@946
|
216 |
} else {
|
klao@946
|
217 |
first_node = nodes[n].next;
|
klao@946
|
218 |
}
|
klao@946
|
219 |
|
klao@946
|
220 |
nodes[n].next = first_free_node;
|
klao@946
|
221 |
first_free_node = n;
|
alpar@395
|
222 |
|
alpar@774
|
223 |
}
|
alpar@774
|
224 |
|
klao@946
|
225 |
void erase(const Edge& edge) {
|
klao@946
|
226 |
int n = edge.id;
|
alpar@397
|
227 |
|
klao@946
|
228 |
if(edges[n].next_in!=-1) {
|
alpar@397
|
229 |
edges[edges[n].next_in].prev_in = edges[n].prev_in;
|
klao@946
|
230 |
}
|
klao@946
|
231 |
|
klao@946
|
232 |
if(edges[n].prev_in!=-1) {
|
alpar@397
|
233 |
edges[edges[n].prev_in].next_in = edges[n].next_in;
|
klao@946
|
234 |
} else {
|
klao@946
|
235 |
nodes[edges[n].head].first_in = edges[n].next_in;
|
klao@946
|
236 |
}
|
klao@946
|
237 |
|
alpar@397
|
238 |
|
klao@946
|
239 |
if(edges[n].next_out!=-1) {
|
alpar@397
|
240 |
edges[edges[n].next_out].prev_out = edges[n].prev_out;
|
klao@946
|
241 |
}
|
klao@946
|
242 |
|
klao@946
|
243 |
if(edges[n].prev_out!=-1) {
|
alpar@397
|
244 |
edges[edges[n].prev_out].next_out = edges[n].next_out;
|
klao@946
|
245 |
} else {
|
klao@946
|
246 |
nodes[edges[n].tail].first_out = edges[n].next_out;
|
klao@946
|
247 |
}
|
alpar@397
|
248 |
|
alpar@397
|
249 |
edges[n].next_in = first_free_edge;
|
alpar@695
|
250 |
first_free_edge = n;
|
alpar@397
|
251 |
|
alpar@397
|
252 |
}
|
alpar@397
|
253 |
|
alpar@397
|
254 |
void clear() {
|
deba@782
|
255 |
edges.clear();
|
deba@782
|
256 |
nodes.clear();
|
klao@946
|
257 |
first_node = first_free_node = first_free_edge = -1;
|
deba@937
|
258 |
}
|
deba@937
|
259 |
|
alpar@919
|
260 |
};
|
deba@909
|
261 |
|
klao@946
|
262 |
typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
|
klao@946
|
263 |
typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
|
klao@946
|
264 |
typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
|
klao@946
|
265 |
typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
|
klao@946
|
266 |
typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
|
klao@946
|
267 |
typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
|
klao@946
|
268 |
typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
|
alpar@400
|
269 |
|
klao@946
|
270 |
typedef ErasableListGraphBase ListGraph;
|
alpar@400
|
271 |
|
klao@946
|
272 |
}
|
alpar@400
|
273 |
|
deba@782
|
274 |
|
klao@946
|
275 |
|
alpar@400
|
276 |
|
klao@946
|
277 |
#endif
|