alpar@395
|
1 |
// -*- mode:C++ -*-
|
alpar@395
|
2 |
|
alpar@405
|
3 |
#ifndef HUGO_LIST_GRAPH_H
|
alpar@405
|
4 |
#define HUGO_LIST_GRAPH_H
|
alpar@395
|
5 |
|
klao@491
|
6 |
///\ingroup graphs
|
alpar@395
|
7 |
///\file
|
alpar@405
|
8 |
///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
|
alpar@395
|
9 |
|
alpar@395
|
10 |
#include <vector>
|
deba@698
|
11 |
#include <climits>
|
alpar@395
|
12 |
|
deba@698
|
13 |
#include "invalid.h"
|
deba@698
|
14 |
|
deba@698
|
15 |
#include "vector_map_factory.h"
|
deba@698
|
16 |
#include "map_registry.h"
|
deba@698
|
17 |
|
deba@698
|
18 |
#include "map_defines.h"
|
alpar@395
|
19 |
|
alpar@395
|
20 |
namespace hugo {
|
alpar@395
|
21 |
|
alpar@406
|
22 |
/// \addtogroup graphs
|
alpar@406
|
23 |
/// @{
|
alpar@406
|
24 |
|
alpar@401
|
25 |
///A list graph class.
|
alpar@395
|
26 |
|
alpar@397
|
27 |
///This is a simple and fast erasable graph implementation.
|
alpar@397
|
28 |
///
|
alpar@395
|
29 |
///It conforms to the graph interface documented under
|
alpar@395
|
30 |
///the description of \ref GraphSkeleton.
|
alpar@395
|
31 |
///\sa \ref GraphSkeleton.
|
alpar@397
|
32 |
class ListGraph {
|
alpar@395
|
33 |
|
alpar@397
|
34 |
//Nodes are double linked.
|
alpar@397
|
35 |
//The free nodes are only single linked using the "next" field.
|
alpar@395
|
36 |
struct NodeT
|
alpar@395
|
37 |
{
|
alpar@397
|
38 |
int first_in,first_out;
|
alpar@397
|
39 |
int prev, next;
|
alpar@397
|
40 |
// NodeT() {}
|
alpar@395
|
41 |
};
|
alpar@397
|
42 |
//Edges are double linked.
|
alpar@397
|
43 |
//The free edges are only single linked using the "next_in" field.
|
alpar@395
|
44 |
struct EdgeT
|
alpar@395
|
45 |
{
|
alpar@397
|
46 |
int head, tail;
|
alpar@397
|
47 |
int prev_in, prev_out;
|
alpar@397
|
48 |
int next_in, next_out;
|
alpar@395
|
49 |
//FIXME: is this necessary?
|
alpar@397
|
50 |
// EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
|
alpar@395
|
51 |
};
|
alpar@395
|
52 |
|
alpar@395
|
53 |
std::vector<NodeT> nodes;
|
alpar@397
|
54 |
//The first node
|
alpar@397
|
55 |
int first_node;
|
alpar@397
|
56 |
//The first free node
|
alpar@397
|
57 |
int first_free_node;
|
alpar@395
|
58 |
std::vector<EdgeT> edges;
|
alpar@397
|
59 |
//The first free edge
|
alpar@397
|
60 |
int first_free_edge;
|
alpar@395
|
61 |
|
alpar@397
|
62 |
protected:
|
alpar@395
|
63 |
|
alpar@395
|
64 |
public:
|
alpar@397
|
65 |
|
alpar@395
|
66 |
class Node;
|
alpar@395
|
67 |
class Edge;
|
alpar@395
|
68 |
|
deba@698
|
69 |
typedef ListGraph Graph;
|
deba@698
|
70 |
|
alpar@395
|
71 |
public:
|
alpar@395
|
72 |
|
alpar@395
|
73 |
class NodeIt;
|
alpar@395
|
74 |
class EdgeIt;
|
alpar@395
|
75 |
class OutEdgeIt;
|
alpar@395
|
76 |
class InEdgeIt;
|
alpar@395
|
77 |
|
deba@698
|
78 |
CREATE_MAP_REGISTRIES;
|
deba@698
|
79 |
CREATE_MAPS(VectorMapFactory);
|
alpar@395
|
80 |
public:
|
alpar@395
|
81 |
|
alpar@397
|
82 |
ListGraph() : nodes(), first_node(-1),
|
alpar@397
|
83 |
first_free_node(-1), edges(), first_free_edge(-1) {}
|
alpar@397
|
84 |
ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
|
alpar@397
|
85 |
first_free_node(_g.first_free_node),
|
alpar@397
|
86 |
edges(_g.edges),
|
alpar@397
|
87 |
first_free_edge(_g.first_free_edge) {}
|
alpar@395
|
88 |
|
alpar@395
|
89 |
|
alpar@395
|
90 |
int nodeNum() const { return nodes.size(); } //FIXME: What is this?
|
alpar@395
|
91 |
int edgeNum() const { return edges.size(); } //FIXME: What is this?
|
alpar@395
|
92 |
|
alpar@695
|
93 |
///Set the expected number of edges
|
alpar@695
|
94 |
|
alpar@695
|
95 |
///With this function, it is possible to set the expected number of edges.
|
alpar@695
|
96 |
///The use of this fasten the building of the graph and makes
|
alpar@695
|
97 |
///it possible to avoid the superfluous memory allocation.
|
alpar@695
|
98 |
void reserveEdge(int n) { edges.reserve(n); };
|
alpar@695
|
99 |
|
alpar@395
|
100 |
///\bug This function does something different than
|
alpar@395
|
101 |
///its name would suggests...
|
alpar@395
|
102 |
int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
|
alpar@395
|
103 |
///\bug This function does something different than
|
alpar@395
|
104 |
///its name would suggests...
|
alpar@395
|
105 |
int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
|
alpar@395
|
106 |
|
alpar@395
|
107 |
Node tail(Edge e) const { return edges[e.n].tail; }
|
alpar@395
|
108 |
Node head(Edge e) const { return edges[e.n].head; }
|
alpar@395
|
109 |
|
alpar@395
|
110 |
Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
|
alpar@395
|
111 |
Node aNode(InEdgeIt e) const { return edges[e.n].head; }
|
alpar@395
|
112 |
|
alpar@395
|
113 |
Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
|
alpar@395
|
114 |
Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
|
alpar@395
|
115 |
|
alpar@395
|
116 |
NodeIt& first(NodeIt& v) const {
|
alpar@395
|
117 |
v=NodeIt(*this); return v; }
|
alpar@395
|
118 |
EdgeIt& first(EdgeIt& e) const {
|
alpar@395
|
119 |
e=EdgeIt(*this); return e; }
|
alpar@395
|
120 |
OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
|
alpar@395
|
121 |
e=OutEdgeIt(*this,v); return e; }
|
alpar@395
|
122 |
InEdgeIt& first(InEdgeIt& e, const Node v) const {
|
alpar@395
|
123 |
e=InEdgeIt(*this,v); return e; }
|
alpar@395
|
124 |
|
alpar@395
|
125 |
// template< typename It >
|
alpar@395
|
126 |
// It first() const { It e; first(e); return e; }
|
alpar@395
|
127 |
|
alpar@395
|
128 |
// template< typename It >
|
alpar@395
|
129 |
// It first(Node v) const { It e; first(e,v); return e; }
|
alpar@395
|
130 |
|
alpar@395
|
131 |
bool valid(Edge e) const { return e.n!=-1; }
|
alpar@395
|
132 |
bool valid(Node n) const { return n.n!=-1; }
|
alpar@395
|
133 |
|
alpar@395
|
134 |
void setInvalid(Edge &e) { e.n=-1; }
|
alpar@395
|
135 |
void setInvalid(Node &n) { n.n=-1; }
|
alpar@395
|
136 |
|
alpar@395
|
137 |
template <typename It> It getNext(It it) const
|
alpar@395
|
138 |
{ It tmp(it); return next(tmp); }
|
alpar@395
|
139 |
|
alpar@395
|
140 |
NodeIt& next(NodeIt& it) const {
|
alpar@397
|
141 |
it.n=nodes[it.n].next;
|
alpar@395
|
142 |
return it;
|
alpar@395
|
143 |
}
|
alpar@395
|
144 |
OutEdgeIt& next(OutEdgeIt& it) const
|
alpar@395
|
145 |
{ it.n=edges[it.n].next_out; return it; }
|
alpar@395
|
146 |
InEdgeIt& next(InEdgeIt& it) const
|
alpar@395
|
147 |
{ it.n=edges[it.n].next_in; return it; }
|
alpar@397
|
148 |
EdgeIt& next(EdgeIt& it) const {
|
alpar@397
|
149 |
if(edges[it.n].next_in!=-1) {
|
alpar@397
|
150 |
it.n=edges[it.n].next_in;
|
alpar@397
|
151 |
}
|
alpar@397
|
152 |
else {
|
alpar@397
|
153 |
int n;
|
alpar@397
|
154 |
for(n=nodes[edges[it.n].head].next;
|
alpar@397
|
155 |
n!=-1 && nodes[n].first_in == -1;
|
alpar@397
|
156 |
n = nodes[n].next) ;
|
alpar@397
|
157 |
it.n = (n==-1)?-1:nodes[n].first_in;
|
alpar@397
|
158 |
}
|
alpar@397
|
159 |
return it;
|
alpar@397
|
160 |
}
|
alpar@395
|
161 |
|
alpar@395
|
162 |
int id(Node v) const { return v.n; }
|
alpar@395
|
163 |
int id(Edge e) const { return e.n; }
|
alpar@395
|
164 |
|
alpar@397
|
165 |
/// Adds a new node to the graph.
|
alpar@397
|
166 |
|
alpar@397
|
167 |
/// \todo It adds the nodes in a reversed order.
|
alpar@397
|
168 |
/// (i.e. the lastly added node becomes the first.)
|
alpar@395
|
169 |
Node addNode() {
|
alpar@397
|
170 |
int n;
|
alpar@397
|
171 |
|
alpar@397
|
172 |
if(first_free_node==-1)
|
alpar@397
|
173 |
{
|
alpar@397
|
174 |
n = nodes.size();
|
alpar@397
|
175 |
nodes.push_back(NodeT());
|
alpar@397
|
176 |
}
|
alpar@397
|
177 |
else {
|
alpar@397
|
178 |
n = first_free_node;
|
alpar@397
|
179 |
first_free_node = nodes[n].next;
|
alpar@397
|
180 |
}
|
alpar@397
|
181 |
|
alpar@397
|
182 |
nodes[n].next = first_node;
|
alpar@397
|
183 |
if(first_node != -1) nodes[first_node].prev = n;
|
alpar@397
|
184 |
first_node = n;
|
alpar@397
|
185 |
nodes[n].prev = -1;
|
alpar@397
|
186 |
|
alpar@397
|
187 |
nodes[n].first_in = nodes[n].first_out = -1;
|
alpar@397
|
188 |
|
alpar@397
|
189 |
Node nn; nn.n=n;
|
alpar@395
|
190 |
|
alpar@397
|
191 |
//Update dynamic maps
|
deba@698
|
192 |
node_maps.add(nn);
|
alpar@395
|
193 |
|
alpar@397
|
194 |
return nn;
|
alpar@395
|
195 |
}
|
alpar@395
|
196 |
|
alpar@395
|
197 |
Edge addEdge(Node u, Node v) {
|
alpar@397
|
198 |
int n;
|
alpar@397
|
199 |
|
alpar@397
|
200 |
if(first_free_edge==-1)
|
alpar@397
|
201 |
{
|
alpar@397
|
202 |
n = edges.size();
|
alpar@397
|
203 |
edges.push_back(EdgeT());
|
alpar@397
|
204 |
}
|
alpar@397
|
205 |
else {
|
alpar@397
|
206 |
n = first_free_edge;
|
alpar@397
|
207 |
first_free_edge = edges[n].next_in;
|
alpar@397
|
208 |
}
|
alpar@397
|
209 |
|
alpar@397
|
210 |
edges[n].tail = u.n; edges[n].head = v.n;
|
alpar@395
|
211 |
|
alpar@397
|
212 |
edges[n].next_out = nodes[u.n].first_out;
|
alpar@397
|
213 |
if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
|
alpar@397
|
214 |
edges[n].next_in = nodes[v.n].first_in;
|
alpar@397
|
215 |
if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
|
alpar@397
|
216 |
edges[n].prev_in = edges[n].prev_out = -1;
|
alpar@397
|
217 |
|
alpar@397
|
218 |
nodes[u.n].first_out = nodes[v.n].first_in = n;
|
alpar@397
|
219 |
|
alpar@397
|
220 |
Edge e; e.n=n;
|
alpar@397
|
221 |
|
alpar@397
|
222 |
//Update dynamic maps
|
deba@698
|
223 |
edge_maps.add(e);
|
alpar@395
|
224 |
|
alpar@395
|
225 |
return e;
|
alpar@395
|
226 |
}
|
alpar@395
|
227 |
|
alpar@397
|
228 |
private:
|
alpar@397
|
229 |
void eraseEdge(int n) {
|
alpar@397
|
230 |
|
alpar@397
|
231 |
if(edges[n].next_in!=-1)
|
alpar@397
|
232 |
edges[edges[n].next_in].prev_in = edges[n].prev_in;
|
alpar@397
|
233 |
if(edges[n].prev_in!=-1)
|
alpar@397
|
234 |
edges[edges[n].prev_in].next_in = edges[n].next_in;
|
alpar@397
|
235 |
else nodes[edges[n].head].first_in = edges[n].next_in;
|
alpar@397
|
236 |
|
alpar@397
|
237 |
if(edges[n].next_out!=-1)
|
alpar@397
|
238 |
edges[edges[n].next_out].prev_out = edges[n].prev_out;
|
alpar@397
|
239 |
if(edges[n].prev_out!=-1)
|
alpar@397
|
240 |
edges[edges[n].prev_out].next_out = edges[n].next_out;
|
alpar@397
|
241 |
else nodes[edges[n].tail].first_out = edges[n].next_out;
|
alpar@397
|
242 |
|
alpar@397
|
243 |
edges[n].next_in = first_free_edge;
|
alpar@695
|
244 |
first_free_edge = n;
|
alpar@397
|
245 |
|
alpar@397
|
246 |
//Update dynamic maps
|
alpar@397
|
247 |
Edge e; e.n=n;
|
alpar@397
|
248 |
}
|
alpar@397
|
249 |
|
alpar@397
|
250 |
public:
|
alpar@397
|
251 |
|
alpar@397
|
252 |
void erase(Node nn) {
|
alpar@397
|
253 |
int n=nn.n;
|
alpar@397
|
254 |
|
alpar@397
|
255 |
int m;
|
alpar@397
|
256 |
while((m=nodes[n].first_in)!=-1) eraseEdge(m);
|
alpar@397
|
257 |
while((m=nodes[n].first_out)!=-1) eraseEdge(m);
|
alpar@397
|
258 |
|
alpar@397
|
259 |
if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
|
alpar@397
|
260 |
if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
|
alpar@397
|
261 |
else first_node = nodes[n].next;
|
alpar@397
|
262 |
|
alpar@397
|
263 |
nodes[n].next = first_free_node;
|
alpar@397
|
264 |
first_free_node = n;
|
alpar@397
|
265 |
|
alpar@397
|
266 |
//Update dynamic maps
|
deba@698
|
267 |
node_maps.erase(nn);
|
deba@698
|
268 |
}
|
deba@698
|
269 |
|
deba@698
|
270 |
void erase(Edge e) {
|
deba@698
|
271 |
edge_maps.erase(e);
|
deba@698
|
272 |
eraseEdge(e.n);
|
alpar@397
|
273 |
}
|
alpar@397
|
274 |
|
alpar@397
|
275 |
///\bug Dynamic maps must be updated!
|
alpar@397
|
276 |
///
|
alpar@397
|
277 |
void clear() {
|
alpar@397
|
278 |
nodes.clear();edges.clear();
|
alpar@397
|
279 |
first_node=first_free_node=first_free_edge=-1;
|
alpar@397
|
280 |
}
|
alpar@395
|
281 |
|
alpar@395
|
282 |
class Node {
|
alpar@397
|
283 |
friend class ListGraph;
|
alpar@395
|
284 |
template <typename T> friend class NodeMap;
|
alpar@400
|
285 |
|
alpar@395
|
286 |
friend class Edge;
|
alpar@395
|
287 |
friend class OutEdgeIt;
|
alpar@395
|
288 |
friend class InEdgeIt;
|
alpar@395
|
289 |
friend class SymEdge;
|
alpar@395
|
290 |
|
alpar@395
|
291 |
protected:
|
alpar@395
|
292 |
int n;
|
alpar@397
|
293 |
friend int ListGraph::id(Node v) const;
|
alpar@395
|
294 |
Node(int nn) {n=nn;}
|
alpar@395
|
295 |
public:
|
alpar@395
|
296 |
Node() {}
|
alpar@503
|
297 |
Node (Invalid) { n=-1; }
|
alpar@395
|
298 |
bool operator==(const Node i) const {return n==i.n;}
|
alpar@395
|
299 |
bool operator!=(const Node i) const {return n!=i.n;}
|
alpar@395
|
300 |
bool operator<(const Node i) const {return n<i.n;}
|
alpar@395
|
301 |
};
|
alpar@395
|
302 |
|
alpar@395
|
303 |
class NodeIt : public Node {
|
alpar@397
|
304 |
friend class ListGraph;
|
alpar@395
|
305 |
public:
|
alpar@400
|
306 |
NodeIt() : Node() { }
|
alpar@400
|
307 |
NodeIt(Invalid i) : Node(i) { }
|
alpar@397
|
308 |
NodeIt(const ListGraph& G) : Node(G.first_node) { }
|
alpar@579
|
309 |
///\todo Undocumented conversion Node -\> NodeIt.
|
alpar@579
|
310 |
NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
|
alpar@395
|
311 |
};
|
alpar@395
|
312 |
|
alpar@395
|
313 |
class Edge {
|
alpar@397
|
314 |
friend class ListGraph;
|
alpar@395
|
315 |
template <typename T> friend class EdgeMap;
|
alpar@395
|
316 |
|
alpar@397
|
317 |
//template <typename T> friend class SymListGraph::SymEdgeMap;
|
alpar@397
|
318 |
//friend Edge SymListGraph::opposite(Edge) const;
|
alpar@395
|
319 |
|
alpar@395
|
320 |
friend class Node;
|
alpar@395
|
321 |
friend class NodeIt;
|
alpar@395
|
322 |
protected:
|
alpar@395
|
323 |
int n;
|
alpar@397
|
324 |
friend int ListGraph::id(Edge e) const;
|
alpar@395
|
325 |
|
alpar@395
|
326 |
Edge(int nn) {n=nn;}
|
alpar@395
|
327 |
public:
|
alpar@395
|
328 |
Edge() { }
|
alpar@395
|
329 |
Edge (Invalid) { n=-1; }
|
alpar@395
|
330 |
bool operator==(const Edge i) const {return n==i.n;}
|
alpar@395
|
331 |
bool operator!=(const Edge i) const {return n!=i.n;}
|
alpar@395
|
332 |
bool operator<(const Edge i) const {return n<i.n;}
|
alpar@395
|
333 |
///\bug This is a workaround until somebody tells me how to
|
alpar@397
|
334 |
///make class \c SymListGraph::SymEdgeMap friend of Edge
|
alpar@395
|
335 |
int &idref() {return n;}
|
alpar@395
|
336 |
const int &idref() const {return n;}
|
alpar@395
|
337 |
};
|
alpar@395
|
338 |
|
alpar@395
|
339 |
class EdgeIt : public Edge {
|
alpar@397
|
340 |
friend class ListGraph;
|
alpar@395
|
341 |
public:
|
alpar@397
|
342 |
EdgeIt(const ListGraph& G) : Edge() {
|
alpar@397
|
343 |
int m;
|
alpar@397
|
344 |
for(m=G.first_node;
|
alpar@397
|
345 |
m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
|
alpar@397
|
346 |
n = (m==-1)?-1:G.nodes[m].first_in;
|
alpar@397
|
347 |
}
|
alpar@395
|
348 |
EdgeIt (Invalid i) : Edge(i) { }
|
alpar@395
|
349 |
EdgeIt() : Edge() { }
|
alpar@395
|
350 |
///\bug This is a workaround until somebody tells me how to
|
alpar@397
|
351 |
///make class \c SymListGraph::SymEdgeMap friend of Edge
|
alpar@395
|
352 |
int &idref() {return n;}
|
alpar@395
|
353 |
};
|
alpar@395
|
354 |
|
alpar@395
|
355 |
class OutEdgeIt : public Edge {
|
alpar@397
|
356 |
friend class ListGraph;
|
alpar@395
|
357 |
public:
|
alpar@395
|
358 |
OutEdgeIt() : Edge() { }
|
alpar@395
|
359 |
OutEdgeIt (Invalid i) : Edge(i) { }
|
alpar@395
|
360 |
|
alpar@397
|
361 |
OutEdgeIt(const ListGraph& G,const Node v)
|
alpar@395
|
362 |
: Edge(G.nodes[v.n].first_out) {}
|
alpar@395
|
363 |
};
|
alpar@395
|
364 |
|
alpar@395
|
365 |
class InEdgeIt : public Edge {
|
alpar@397
|
366 |
friend class ListGraph;
|
alpar@395
|
367 |
public:
|
alpar@395
|
368 |
InEdgeIt() : Edge() { }
|
alpar@395
|
369 |
InEdgeIt (Invalid i) : Edge(i) { }
|
alpar@681
|
370 |
InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
|
alpar@395
|
371 |
};
|
alpar@395
|
372 |
|
alpar@395
|
373 |
};
|
alpar@395
|
374 |
|
alpar@395
|
375 |
///Graph for bidirectional edges.
|
alpar@395
|
376 |
|
alpar@395
|
377 |
///The purpose of this graph structure is to handle graphs
|
alpar@395
|
378 |
///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
|
alpar@395
|
379 |
///of oppositely directed edges.
|
alpar@395
|
380 |
///There is a new edge map type called
|
alpar@397
|
381 |
///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
|
alpar@395
|
382 |
///that complements this
|
alpar@395
|
383 |
///feature by
|
alpar@395
|
384 |
///storing shared values for the edge pairs. The usual
|
alpar@395
|
385 |
///\ref GraphSkeleton::EdgeMap "EdgeMap"
|
alpar@395
|
386 |
///can be used
|
alpar@395
|
387 |
///as well.
|
alpar@395
|
388 |
///
|
alpar@395
|
389 |
///The oppositely directed edge can also be obtained easily
|
alpar@395
|
390 |
///using \ref opposite.
|
alpar@397
|
391 |
///
|
alpar@397
|
392 |
///Here erase(Edge) deletes a pair of edges.
|
alpar@397
|
393 |
///
|
alpar@397
|
394 |
///\todo this date structure need some reconsiderations. Maybe it
|
alpar@397
|
395 |
///should be implemented independently from ListGraph.
|
alpar@395
|
396 |
|
deba@701
|
397 |
}
|
alpar@395
|
398 |
|
alpar@405
|
399 |
#endif //HUGO_LIST_GRAPH_H
|