alpar@395
|
1 |
// -*- mode:C++ -*-
|
alpar@395
|
2 |
|
alpar@395
|
3 |
#ifndef HUGO_SMART_GRAPH_H
|
alpar@395
|
4 |
#define HUGO_SMART_GRAPH_H
|
alpar@395
|
5 |
|
alpar@395
|
6 |
///\file
|
alpar@397
|
7 |
///\brief ListGraph and SymListGraph classes.
|
alpar@395
|
8 |
|
alpar@395
|
9 |
#include <vector>
|
alpar@395
|
10 |
#include <limits.h>
|
alpar@395
|
11 |
|
alpar@395
|
12 |
#include "invalid.h"
|
alpar@395
|
13 |
|
alpar@395
|
14 |
namespace hugo {
|
alpar@395
|
15 |
|
alpar@397
|
16 |
class SymListGraph;
|
alpar@395
|
17 |
|
alpar@395
|
18 |
///A smart graph class.
|
alpar@395
|
19 |
|
alpar@397
|
20 |
///This is a simple and fast erasable graph implementation.
|
alpar@397
|
21 |
///
|
alpar@395
|
22 |
///It conforms to the graph interface documented under
|
alpar@395
|
23 |
///the description of \ref GraphSkeleton.
|
alpar@395
|
24 |
///\sa \ref GraphSkeleton.
|
alpar@397
|
25 |
class ListGraph {
|
alpar@395
|
26 |
|
alpar@397
|
27 |
//Nodes are double linked.
|
alpar@397
|
28 |
//The free nodes are only single linked using the "next" field.
|
alpar@395
|
29 |
struct NodeT
|
alpar@395
|
30 |
{
|
alpar@397
|
31 |
int first_in,first_out;
|
alpar@397
|
32 |
int prev, next;
|
alpar@397
|
33 |
// NodeT() {}
|
alpar@395
|
34 |
};
|
alpar@397
|
35 |
//Edges are double linked.
|
alpar@397
|
36 |
//The free edges are only single linked using the "next_in" field.
|
alpar@395
|
37 |
struct EdgeT
|
alpar@395
|
38 |
{
|
alpar@397
|
39 |
int head, tail;
|
alpar@397
|
40 |
int prev_in, prev_out;
|
alpar@397
|
41 |
int next_in, next_out;
|
alpar@395
|
42 |
//FIXME: is this necessary?
|
alpar@397
|
43 |
// EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
|
alpar@395
|
44 |
};
|
alpar@395
|
45 |
|
alpar@395
|
46 |
std::vector<NodeT> nodes;
|
alpar@397
|
47 |
//The first node
|
alpar@397
|
48 |
int first_node;
|
alpar@397
|
49 |
//The first free node
|
alpar@397
|
50 |
int first_free_node;
|
alpar@395
|
51 |
std::vector<EdgeT> edges;
|
alpar@397
|
52 |
//The first free edge
|
alpar@397
|
53 |
int first_free_edge;
|
alpar@395
|
54 |
|
alpar@397
|
55 |
protected:
|
alpar@395
|
56 |
|
alpar@395
|
57 |
template <typename Key> class DynMapBase
|
alpar@395
|
58 |
{
|
alpar@395
|
59 |
protected:
|
alpar@397
|
60 |
const ListGraph* G;
|
alpar@395
|
61 |
public:
|
alpar@395
|
62 |
virtual void add(const Key k) = NULL;
|
alpar@395
|
63 |
virtual void erase(const Key k) = NULL;
|
alpar@397
|
64 |
DynMapBase(const ListGraph &_G) : G(&_G) {}
|
alpar@395
|
65 |
virtual ~DynMapBase() {}
|
alpar@397
|
66 |
friend class ListGraph;
|
alpar@395
|
67 |
};
|
alpar@395
|
68 |
|
alpar@395
|
69 |
public:
|
alpar@395
|
70 |
template <typename T> class EdgeMap;
|
alpar@395
|
71 |
template <typename T> class EdgeMap;
|
alpar@397
|
72 |
|
alpar@395
|
73 |
class Node;
|
alpar@395
|
74 |
class Edge;
|
alpar@395
|
75 |
|
alpar@395
|
76 |
// protected:
|
alpar@395
|
77 |
// HELPME:
|
alpar@395
|
78 |
protected:
|
alpar@395
|
79 |
///\bug It must be public because of SymEdgeMap.
|
alpar@395
|
80 |
///
|
alpar@395
|
81 |
mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
|
alpar@395
|
82 |
///\bug It must be public because of SymEdgeMap.
|
alpar@395
|
83 |
///
|
alpar@395
|
84 |
mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
|
alpar@395
|
85 |
|
alpar@395
|
86 |
public:
|
alpar@395
|
87 |
|
alpar@395
|
88 |
class NodeIt;
|
alpar@395
|
89 |
class EdgeIt;
|
alpar@395
|
90 |
class OutEdgeIt;
|
alpar@395
|
91 |
class InEdgeIt;
|
alpar@395
|
92 |
|
alpar@395
|
93 |
template <typename T> class NodeMap;
|
alpar@395
|
94 |
template <typename T> class EdgeMap;
|
alpar@395
|
95 |
|
alpar@395
|
96 |
public:
|
alpar@395
|
97 |
|
alpar@397
|
98 |
ListGraph() : nodes(), first_node(-1),
|
alpar@397
|
99 |
first_free_node(-1), edges(), first_free_edge(-1) {}
|
alpar@397
|
100 |
ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
|
alpar@397
|
101 |
first_free_node(_g.first_free_node),
|
alpar@397
|
102 |
edges(_g.edges),
|
alpar@397
|
103 |
first_free_edge(_g.first_free_edge) {}
|
alpar@395
|
104 |
|
alpar@397
|
105 |
~ListGraph()
|
alpar@395
|
106 |
{
|
alpar@395
|
107 |
for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
|
alpar@395
|
108 |
i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
|
alpar@395
|
109 |
for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
|
alpar@395
|
110 |
i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
|
alpar@395
|
111 |
}
|
alpar@395
|
112 |
|
alpar@395
|
113 |
int nodeNum() const { return nodes.size(); } //FIXME: What is this?
|
alpar@395
|
114 |
int edgeNum() const { return edges.size(); } //FIXME: What is this?
|
alpar@395
|
115 |
|
alpar@395
|
116 |
///\bug This function does something different than
|
alpar@395
|
117 |
///its name would suggests...
|
alpar@395
|
118 |
int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
|
alpar@395
|
119 |
///\bug This function does something different than
|
alpar@395
|
120 |
///its name would suggests...
|
alpar@395
|
121 |
int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
|
alpar@395
|
122 |
|
alpar@395
|
123 |
Node tail(Edge e) const { return edges[e.n].tail; }
|
alpar@395
|
124 |
Node head(Edge e) const { return edges[e.n].head; }
|
alpar@395
|
125 |
|
alpar@395
|
126 |
Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
|
alpar@395
|
127 |
Node aNode(InEdgeIt e) const { return edges[e.n].head; }
|
alpar@395
|
128 |
|
alpar@395
|
129 |
Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
|
alpar@395
|
130 |
Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
|
alpar@395
|
131 |
|
alpar@395
|
132 |
NodeIt& first(NodeIt& v) const {
|
alpar@395
|
133 |
v=NodeIt(*this); return v; }
|
alpar@395
|
134 |
EdgeIt& first(EdgeIt& e) const {
|
alpar@395
|
135 |
e=EdgeIt(*this); return e; }
|
alpar@395
|
136 |
OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
|
alpar@395
|
137 |
e=OutEdgeIt(*this,v); return e; }
|
alpar@395
|
138 |
InEdgeIt& first(InEdgeIt& e, const Node v) const {
|
alpar@395
|
139 |
e=InEdgeIt(*this,v); return e; }
|
alpar@395
|
140 |
|
alpar@395
|
141 |
// template< typename It >
|
alpar@395
|
142 |
// It first() const { It e; first(e); return e; }
|
alpar@395
|
143 |
|
alpar@395
|
144 |
// template< typename It >
|
alpar@395
|
145 |
// It first(Node v) const { It e; first(e,v); return e; }
|
alpar@395
|
146 |
|
alpar@395
|
147 |
bool valid(Edge e) const { return e.n!=-1; }
|
alpar@395
|
148 |
bool valid(Node n) const { return n.n!=-1; }
|
alpar@395
|
149 |
|
alpar@395
|
150 |
void setInvalid(Edge &e) { e.n=-1; }
|
alpar@395
|
151 |
void setInvalid(Node &n) { n.n=-1; }
|
alpar@395
|
152 |
|
alpar@395
|
153 |
template <typename It> It getNext(It it) const
|
alpar@395
|
154 |
{ It tmp(it); return next(tmp); }
|
alpar@395
|
155 |
|
alpar@395
|
156 |
NodeIt& next(NodeIt& it) const {
|
alpar@397
|
157 |
it.n=nodes[it.n].next;
|
alpar@395
|
158 |
return it;
|
alpar@395
|
159 |
}
|
alpar@395
|
160 |
OutEdgeIt& next(OutEdgeIt& it) const
|
alpar@395
|
161 |
{ it.n=edges[it.n].next_out; return it; }
|
alpar@395
|
162 |
InEdgeIt& next(InEdgeIt& it) const
|
alpar@395
|
163 |
{ it.n=edges[it.n].next_in; return it; }
|
alpar@397
|
164 |
EdgeIt& next(EdgeIt& it) const {
|
alpar@397
|
165 |
if(edges[it.n].next_in!=-1) {
|
alpar@397
|
166 |
it.n=edges[it.n].next_in;
|
alpar@397
|
167 |
}
|
alpar@397
|
168 |
else {
|
alpar@397
|
169 |
int n;
|
alpar@397
|
170 |
for(n=nodes[edges[it.n].head].next;
|
alpar@397
|
171 |
n!=-1 && nodes[n].first_in == -1;
|
alpar@397
|
172 |
n = nodes[n].next) ;
|
alpar@397
|
173 |
it.n = (n==-1)?-1:nodes[n].first_in;
|
alpar@397
|
174 |
}
|
alpar@397
|
175 |
return it;
|
alpar@397
|
176 |
}
|
alpar@395
|
177 |
|
alpar@395
|
178 |
int id(Node v) const { return v.n; }
|
alpar@395
|
179 |
int id(Edge e) const { return e.n; }
|
alpar@395
|
180 |
|
alpar@397
|
181 |
/// Adds a new node to the graph.
|
alpar@397
|
182 |
|
alpar@397
|
183 |
/// \todo It adds the nodes in a reversed order.
|
alpar@397
|
184 |
/// (i.e. the lastly added node becomes the first.)
|
alpar@395
|
185 |
Node addNode() {
|
alpar@397
|
186 |
int n;
|
alpar@397
|
187 |
|
alpar@397
|
188 |
if(first_free_node==-1)
|
alpar@397
|
189 |
{
|
alpar@397
|
190 |
n = nodes.size();
|
alpar@397
|
191 |
nodes.push_back(NodeT());
|
alpar@397
|
192 |
}
|
alpar@397
|
193 |
else {
|
alpar@397
|
194 |
n = first_free_node;
|
alpar@397
|
195 |
first_free_node = nodes[n].next;
|
alpar@397
|
196 |
}
|
alpar@397
|
197 |
|
alpar@397
|
198 |
nodes[n].next = first_node;
|
alpar@397
|
199 |
if(first_node != -1) nodes[first_node].prev = n;
|
alpar@397
|
200 |
first_node = n;
|
alpar@397
|
201 |
nodes[n].prev = -1;
|
alpar@397
|
202 |
|
alpar@397
|
203 |
nodes[n].first_in = nodes[n].first_out = -1;
|
alpar@397
|
204 |
|
alpar@397
|
205 |
Node nn; nn.n=n;
|
alpar@395
|
206 |
|
alpar@397
|
207 |
//Update dynamic maps
|
alpar@395
|
208 |
for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
|
alpar@397
|
209 |
i!=dyn_node_maps.end(); ++i) (**i).add(nn);
|
alpar@395
|
210 |
|
alpar@397
|
211 |
return nn;
|
alpar@395
|
212 |
}
|
alpar@395
|
213 |
|
alpar@395
|
214 |
Edge addEdge(Node u, Node v) {
|
alpar@397
|
215 |
int n;
|
alpar@397
|
216 |
|
alpar@397
|
217 |
if(first_free_edge==-1)
|
alpar@397
|
218 |
{
|
alpar@397
|
219 |
n = edges.size();
|
alpar@397
|
220 |
edges.push_back(EdgeT());
|
alpar@397
|
221 |
}
|
alpar@397
|
222 |
else {
|
alpar@397
|
223 |
n = first_free_edge;
|
alpar@397
|
224 |
first_free_edge = edges[n].next_in;
|
alpar@397
|
225 |
}
|
alpar@397
|
226 |
|
alpar@397
|
227 |
edges[n].tail = u.n; edges[n].head = v.n;
|
alpar@395
|
228 |
|
alpar@397
|
229 |
edges[n].next_out = nodes[u.n].first_out;
|
alpar@397
|
230 |
if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
|
alpar@397
|
231 |
edges[n].next_in = nodes[v.n].first_in;
|
alpar@397
|
232 |
if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
|
alpar@397
|
233 |
edges[n].prev_in = edges[n].prev_out = -1;
|
alpar@397
|
234 |
|
alpar@397
|
235 |
nodes[u.n].first_out = nodes[v.n].first_in = n;
|
alpar@397
|
236 |
|
alpar@397
|
237 |
Edge e; e.n=n;
|
alpar@397
|
238 |
|
alpar@397
|
239 |
//Update dynamic maps
|
alpar@395
|
240 |
for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
|
alpar@395
|
241 |
i!=dyn_edge_maps.end(); ++i) (**i).add(e);
|
alpar@395
|
242 |
|
alpar@395
|
243 |
return e;
|
alpar@395
|
244 |
}
|
alpar@395
|
245 |
|
alpar@397
|
246 |
private:
|
alpar@397
|
247 |
void eraseEdge(int n) {
|
alpar@397
|
248 |
|
alpar@397
|
249 |
if(edges[n].next_in!=-1)
|
alpar@397
|
250 |
edges[edges[n].next_in].prev_in = edges[n].prev_in;
|
alpar@397
|
251 |
if(edges[n].prev_in!=-1)
|
alpar@397
|
252 |
edges[edges[n].prev_in].next_in = edges[n].next_in;
|
alpar@397
|
253 |
else nodes[edges[n].head].first_in = edges[n].next_in;
|
alpar@397
|
254 |
|
alpar@397
|
255 |
if(edges[n].next_out!=-1)
|
alpar@397
|
256 |
edges[edges[n].next_out].prev_out = edges[n].prev_out;
|
alpar@397
|
257 |
if(edges[n].prev_out!=-1)
|
alpar@397
|
258 |
edges[edges[n].prev_out].next_out = edges[n].next_out;
|
alpar@397
|
259 |
else nodes[edges[n].tail].first_out = edges[n].next_out;
|
alpar@397
|
260 |
|
alpar@397
|
261 |
edges[n].next_in = first_free_edge;
|
alpar@397
|
262 |
first_free_edge = -1;
|
alpar@397
|
263 |
|
alpar@397
|
264 |
//Update dynamic maps
|
alpar@397
|
265 |
Edge e; e.n=n;
|
alpar@397
|
266 |
for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
|
alpar@397
|
267 |
i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
|
alpar@397
|
268 |
}
|
alpar@397
|
269 |
|
alpar@397
|
270 |
public:
|
alpar@397
|
271 |
|
alpar@397
|
272 |
void erase(Node nn) {
|
alpar@397
|
273 |
int n=nn.n;
|
alpar@397
|
274 |
|
alpar@397
|
275 |
int m;
|
alpar@397
|
276 |
while((m=nodes[n].first_in)!=-1) eraseEdge(m);
|
alpar@397
|
277 |
while((m=nodes[n].first_out)!=-1) eraseEdge(m);
|
alpar@397
|
278 |
|
alpar@397
|
279 |
if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
|
alpar@397
|
280 |
if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
|
alpar@397
|
281 |
else first_node = nodes[n].next;
|
alpar@397
|
282 |
|
alpar@397
|
283 |
nodes[n].next = first_free_node;
|
alpar@397
|
284 |
first_free_node = n;
|
alpar@397
|
285 |
|
alpar@397
|
286 |
//Update dynamic maps
|
alpar@397
|
287 |
for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
|
alpar@397
|
288 |
i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
|
alpar@397
|
289 |
}
|
alpar@397
|
290 |
|
alpar@397
|
291 |
void erase(Edge e) { eraseEdge(e.n); }
|
alpar@397
|
292 |
|
alpar@397
|
293 |
///\bug Dynamic maps must be updated!
|
alpar@397
|
294 |
///
|
alpar@397
|
295 |
void clear() {
|
alpar@397
|
296 |
nodes.clear();edges.clear();
|
alpar@397
|
297 |
first_node=first_free_node=first_free_edge=-1;
|
alpar@397
|
298 |
}
|
alpar@395
|
299 |
|
alpar@395
|
300 |
class Node {
|
alpar@397
|
301 |
friend class ListGraph;
|
alpar@395
|
302 |
template <typename T> friend class NodeMap;
|
alpar@395
|
303 |
|
alpar@395
|
304 |
friend class Edge;
|
alpar@395
|
305 |
friend class OutEdgeIt;
|
alpar@395
|
306 |
friend class InEdgeIt;
|
alpar@395
|
307 |
friend class SymEdge;
|
alpar@395
|
308 |
|
alpar@395
|
309 |
protected:
|
alpar@395
|
310 |
int n;
|
alpar@397
|
311 |
friend int ListGraph::id(Node v) const;
|
alpar@395
|
312 |
Node(int nn) {n=nn;}
|
alpar@395
|
313 |
public:
|
alpar@395
|
314 |
Node() {}
|
alpar@395
|
315 |
Node (Invalid i) { n=-1; }
|
alpar@395
|
316 |
bool operator==(const Node i) const {return n==i.n;}
|
alpar@395
|
317 |
bool operator!=(const Node i) const {return n!=i.n;}
|
alpar@395
|
318 |
bool operator<(const Node i) const {return n<i.n;}
|
alpar@395
|
319 |
};
|
alpar@395
|
320 |
|
alpar@395
|
321 |
class NodeIt : public Node {
|
alpar@397
|
322 |
friend class ListGraph;
|
alpar@395
|
323 |
public:
|
alpar@397
|
324 |
NodeIt(const ListGraph& G) : Node(G.first_node) { }
|
alpar@395
|
325 |
NodeIt() : Node() { }
|
alpar@395
|
326 |
};
|
alpar@395
|
327 |
|
alpar@395
|
328 |
class Edge {
|
alpar@397
|
329 |
friend class ListGraph;
|
alpar@395
|
330 |
template <typename T> friend class EdgeMap;
|
alpar@395
|
331 |
|
alpar@397
|
332 |
//template <typename T> friend class SymListGraph::SymEdgeMap;
|
alpar@397
|
333 |
//friend Edge SymListGraph::opposite(Edge) const;
|
alpar@395
|
334 |
|
alpar@395
|
335 |
friend class Node;
|
alpar@395
|
336 |
friend class NodeIt;
|
alpar@395
|
337 |
protected:
|
alpar@395
|
338 |
int n;
|
alpar@397
|
339 |
friend int ListGraph::id(Edge e) const;
|
alpar@395
|
340 |
|
alpar@395
|
341 |
Edge(int nn) {n=nn;}
|
alpar@395
|
342 |
public:
|
alpar@395
|
343 |
Edge() { }
|
alpar@395
|
344 |
Edge (Invalid) { n=-1; }
|
alpar@395
|
345 |
bool operator==(const Edge i) const {return n==i.n;}
|
alpar@395
|
346 |
bool operator!=(const Edge i) const {return n!=i.n;}
|
alpar@395
|
347 |
bool operator<(const Edge i) const {return n<i.n;}
|
alpar@395
|
348 |
///\bug This is a workaround until somebody tells me how to
|
alpar@397
|
349 |
///make class \c SymListGraph::SymEdgeMap friend of Edge
|
alpar@395
|
350 |
int &idref() {return n;}
|
alpar@395
|
351 |
const int &idref() const {return n;}
|
alpar@395
|
352 |
};
|
alpar@395
|
353 |
|
alpar@395
|
354 |
class EdgeIt : public Edge {
|
alpar@397
|
355 |
friend class ListGraph;
|
alpar@395
|
356 |
public:
|
alpar@397
|
357 |
EdgeIt(const ListGraph& G) : Edge() {
|
alpar@397
|
358 |
int m;
|
alpar@397
|
359 |
for(m=G.first_node;
|
alpar@397
|
360 |
m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
|
alpar@397
|
361 |
n = (m==-1)?-1:G.nodes[m].first_in;
|
alpar@397
|
362 |
}
|
alpar@395
|
363 |
EdgeIt (Invalid i) : Edge(i) { }
|
alpar@395
|
364 |
EdgeIt() : Edge() { }
|
alpar@395
|
365 |
///\bug This is a workaround until somebody tells me how to
|
alpar@397
|
366 |
///make class \c SymListGraph::SymEdgeMap friend of Edge
|
alpar@395
|
367 |
int &idref() {return n;}
|
alpar@395
|
368 |
};
|
alpar@395
|
369 |
|
alpar@395
|
370 |
class OutEdgeIt : public Edge {
|
alpar@397
|
371 |
friend class ListGraph;
|
alpar@395
|
372 |
public:
|
alpar@395
|
373 |
OutEdgeIt() : Edge() { }
|
alpar@395
|
374 |
OutEdgeIt (Invalid i) : Edge(i) { }
|
alpar@395
|
375 |
|
alpar@397
|
376 |
OutEdgeIt(const ListGraph& G,const Node v)
|
alpar@395
|
377 |
: Edge(G.nodes[v.n].first_out) {}
|
alpar@395
|
378 |
};
|
alpar@395
|
379 |
|
alpar@395
|
380 |
class InEdgeIt : public Edge {
|
alpar@397
|
381 |
friend class ListGraph;
|
alpar@395
|
382 |
public:
|
alpar@395
|
383 |
InEdgeIt() : Edge() { }
|
alpar@395
|
384 |
InEdgeIt (Invalid i) : Edge(i) { }
|
alpar@397
|
385 |
InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
|
alpar@395
|
386 |
};
|
alpar@395
|
387 |
|
alpar@395
|
388 |
template <typename T> class NodeMap : public DynMapBase<Node>
|
alpar@395
|
389 |
{
|
alpar@395
|
390 |
std::vector<T> container;
|
alpar@395
|
391 |
|
alpar@395
|
392 |
public:
|
alpar@395
|
393 |
typedef T ValueType;
|
alpar@395
|
394 |
typedef Node KeyType;
|
alpar@395
|
395 |
|
alpar@397
|
396 |
NodeMap(const ListGraph &_G) :
|
alpar@395
|
397 |
DynMapBase<Node>(_G), container(_G.maxNodeId())
|
alpar@395
|
398 |
{
|
alpar@395
|
399 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
400 |
}
|
alpar@397
|
401 |
NodeMap(const ListGraph &_G,const T &t) :
|
alpar@395
|
402 |
DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
|
alpar@395
|
403 |
{
|
alpar@395
|
404 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
405 |
}
|
alpar@395
|
406 |
|
alpar@395
|
407 |
NodeMap(const NodeMap<T> &m) :
|
alpar@395
|
408 |
DynMapBase<Node>(*m.G), container(m.container)
|
alpar@395
|
409 |
{
|
alpar@395
|
410 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
411 |
}
|
alpar@395
|
412 |
|
alpar@395
|
413 |
template<typename TT> friend class NodeMap;
|
alpar@395
|
414 |
|
alpar@395
|
415 |
///\todo It can copy between different types.
|
alpar@395
|
416 |
///
|
alpar@395
|
417 |
template<typename TT> NodeMap(const NodeMap<TT> &m) :
|
alpar@395
|
418 |
DynMapBase<Node>(*m.G)
|
alpar@395
|
419 |
{
|
alpar@395
|
420 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
421 |
typename std::vector<TT>::const_iterator i;
|
alpar@395
|
422 |
for(typename std::vector<TT>::const_iterator i=m.container.begin();
|
alpar@395
|
423 |
i!=m.container.end();
|
alpar@395
|
424 |
i++)
|
alpar@395
|
425 |
container.push_back(*i);
|
alpar@395
|
426 |
}
|
alpar@395
|
427 |
~NodeMap()
|
alpar@395
|
428 |
{
|
alpar@395
|
429 |
if(G) {
|
alpar@395
|
430 |
std::vector<DynMapBase<Node>* >::iterator i;
|
alpar@395
|
431 |
for(i=G->dyn_node_maps.begin();
|
alpar@395
|
432 |
i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
|
alpar@395
|
433 |
//if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
|
alpar@395
|
434 |
//A better way to do that: (Is this really important?)
|
alpar@395
|
435 |
if(*i==this) {
|
alpar@395
|
436 |
*i=G->dyn_node_maps.back();
|
alpar@395
|
437 |
G->dyn_node_maps.pop_back();
|
alpar@395
|
438 |
}
|
alpar@395
|
439 |
}
|
alpar@395
|
440 |
}
|
alpar@395
|
441 |
|
alpar@395
|
442 |
void add(const Node k)
|
alpar@395
|
443 |
{
|
alpar@395
|
444 |
if(k.n>=int(container.size())) container.resize(k.n+1);
|
alpar@395
|
445 |
}
|
alpar@395
|
446 |
|
alpar@395
|
447 |
void erase(const Node) { }
|
alpar@395
|
448 |
|
alpar@395
|
449 |
void set(Node n, T a) { container[n.n]=a; }
|
alpar@395
|
450 |
//'T& operator[](Node n)' would be wrong here
|
alpar@395
|
451 |
typename std::vector<T>::reference
|
alpar@395
|
452 |
operator[](Node n) { return container[n.n]; }
|
alpar@395
|
453 |
//'const T& operator[](Node n)' would be wrong here
|
alpar@395
|
454 |
typename std::vector<T>::const_reference
|
alpar@395
|
455 |
operator[](Node n) const { return container[n.n]; }
|
alpar@395
|
456 |
|
alpar@395
|
457 |
///\warning There is no safety check at all!
|
alpar@395
|
458 |
///Using operator = between maps attached to different graph may
|
alpar@395
|
459 |
///cause serious problem.
|
alpar@395
|
460 |
///\todo Is this really so?
|
alpar@395
|
461 |
///\todo It can copy between different types.
|
alpar@395
|
462 |
const NodeMap<T>& operator=(const NodeMap<T> &m)
|
alpar@395
|
463 |
{
|
alpar@395
|
464 |
container = m.container;
|
alpar@395
|
465 |
return *this;
|
alpar@395
|
466 |
}
|
alpar@395
|
467 |
template<typename TT>
|
alpar@395
|
468 |
const NodeMap<T>& operator=(const NodeMap<TT> &m)
|
alpar@395
|
469 |
{
|
alpar@395
|
470 |
copy(m.container.begin(), m.container.end(), container.begin());
|
alpar@395
|
471 |
return *this;
|
alpar@395
|
472 |
}
|
alpar@395
|
473 |
|
alpar@395
|
474 |
void update() {} //Useless for Dynamic Maps
|
alpar@395
|
475 |
void update(T a) {} //Useless for Dynamic Maps
|
alpar@395
|
476 |
};
|
alpar@395
|
477 |
|
alpar@395
|
478 |
template <typename T> class EdgeMap : public DynMapBase<Edge>
|
alpar@395
|
479 |
{
|
alpar@395
|
480 |
std::vector<T> container;
|
alpar@395
|
481 |
|
alpar@395
|
482 |
public:
|
alpar@395
|
483 |
typedef T ValueType;
|
alpar@395
|
484 |
typedef Edge KeyType;
|
alpar@395
|
485 |
|
alpar@397
|
486 |
EdgeMap(const ListGraph &_G) :
|
alpar@395
|
487 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId())
|
alpar@395
|
488 |
{
|
alpar@395
|
489 |
//FIXME: What if there are empty Id's?
|
alpar@395
|
490 |
//FIXME: Can I use 'this' in a constructor?
|
alpar@395
|
491 |
G->dyn_edge_maps.push_back(this);
|
alpar@395
|
492 |
}
|
alpar@397
|
493 |
EdgeMap(const ListGraph &_G,const T &t) :
|
alpar@395
|
494 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
|
alpar@395
|
495 |
{
|
alpar@395
|
496 |
G->dyn_edge_maps.push_back(this);
|
alpar@395
|
497 |
}
|
alpar@395
|
498 |
EdgeMap(const EdgeMap<T> &m) :
|
alpar@395
|
499 |
DynMapBase<Edge>(*m.G), container(m.container)
|
alpar@395
|
500 |
{
|
alpar@395
|
501 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
502 |
}
|
alpar@395
|
503 |
|
alpar@395
|
504 |
template<typename TT> friend class EdgeMap;
|
alpar@395
|
505 |
|
alpar@395
|
506 |
///\todo It can copy between different types.
|
alpar@395
|
507 |
///
|
alpar@395
|
508 |
template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
|
alpar@395
|
509 |
DynMapBase<Edge>(*m.G)
|
alpar@395
|
510 |
{
|
alpar@395
|
511 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
512 |
typename std::vector<TT>::const_iterator i;
|
alpar@395
|
513 |
for(typename std::vector<TT>::const_iterator i=m.container.begin();
|
alpar@395
|
514 |
i!=m.container.end();
|
alpar@395
|
515 |
i++)
|
alpar@395
|
516 |
container.push_back(*i);
|
alpar@395
|
517 |
}
|
alpar@395
|
518 |
~EdgeMap()
|
alpar@395
|
519 |
{
|
alpar@395
|
520 |
if(G) {
|
alpar@395
|
521 |
std::vector<DynMapBase<Edge>* >::iterator i;
|
alpar@395
|
522 |
for(i=G->dyn_edge_maps.begin();
|
alpar@395
|
523 |
i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
|
alpar@395
|
524 |
//if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
|
alpar@395
|
525 |
//A better way to do that: (Is this really important?)
|
alpar@395
|
526 |
if(*i==this) {
|
alpar@395
|
527 |
*i=G->dyn_edge_maps.back();
|
alpar@395
|
528 |
G->dyn_edge_maps.pop_back();
|
alpar@395
|
529 |
}
|
alpar@395
|
530 |
}
|
alpar@395
|
531 |
}
|
alpar@395
|
532 |
|
alpar@395
|
533 |
void add(const Edge k)
|
alpar@395
|
534 |
{
|
alpar@395
|
535 |
if(k.n>=int(container.size())) container.resize(k.n+1);
|
alpar@395
|
536 |
}
|
alpar@395
|
537 |
void erase(const Edge) { }
|
alpar@395
|
538 |
|
alpar@395
|
539 |
void set(Edge n, T a) { container[n.n]=a; }
|
alpar@395
|
540 |
//T get(Edge n) const { return container[n.n]; }
|
alpar@395
|
541 |
typename std::vector<T>::reference
|
alpar@395
|
542 |
operator[](Edge n) { return container[n.n]; }
|
alpar@395
|
543 |
typename std::vector<T>::const_reference
|
alpar@395
|
544 |
operator[](Edge n) const { return container[n.n]; }
|
alpar@395
|
545 |
|
alpar@395
|
546 |
///\warning There is no safety check at all!
|
alpar@395
|
547 |
///Using operator = between maps attached to different graph may
|
alpar@395
|
548 |
///cause serious problem.
|
alpar@395
|
549 |
///\todo Is this really so?
|
alpar@395
|
550 |
///\todo It can copy between different types.
|
alpar@395
|
551 |
const EdgeMap<T>& operator=(const EdgeMap<T> &m)
|
alpar@395
|
552 |
{
|
alpar@395
|
553 |
container = m.container;
|
alpar@395
|
554 |
return *this;
|
alpar@395
|
555 |
}
|
alpar@395
|
556 |
template<typename TT>
|
alpar@395
|
557 |
const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
|
alpar@395
|
558 |
{
|
alpar@395
|
559 |
copy(m.container.begin(), m.container.end(), container.begin());
|
alpar@395
|
560 |
return *this;
|
alpar@395
|
561 |
}
|
alpar@395
|
562 |
|
alpar@395
|
563 |
void update() {} //Useless for DynMaps
|
alpar@395
|
564 |
void update(T a) {} //Useless for DynMaps
|
alpar@395
|
565 |
};
|
alpar@395
|
566 |
|
alpar@395
|
567 |
};
|
alpar@395
|
568 |
|
alpar@395
|
569 |
///Graph for bidirectional edges.
|
alpar@395
|
570 |
|
alpar@395
|
571 |
///The purpose of this graph structure is to handle graphs
|
alpar@395
|
572 |
///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
|
alpar@395
|
573 |
///of oppositely directed edges.
|
alpar@395
|
574 |
///There is a new edge map type called
|
alpar@397
|
575 |
///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
|
alpar@395
|
576 |
///that complements this
|
alpar@395
|
577 |
///feature by
|
alpar@395
|
578 |
///storing shared values for the edge pairs. The usual
|
alpar@395
|
579 |
///\ref GraphSkeleton::EdgeMap "EdgeMap"
|
alpar@395
|
580 |
///can be used
|
alpar@395
|
581 |
///as well.
|
alpar@395
|
582 |
///
|
alpar@395
|
583 |
///The oppositely directed edge can also be obtained easily
|
alpar@395
|
584 |
///using \ref opposite.
|
alpar@397
|
585 |
///
|
alpar@397
|
586 |
///Here erase(Edge) deletes a pair of edges.
|
alpar@397
|
587 |
///
|
alpar@397
|
588 |
///\todo this date structure need some reconsiderations. Maybe it
|
alpar@397
|
589 |
///should be implemented independently from ListGraph.
|
alpar@395
|
590 |
|
alpar@397
|
591 |
class SymListGraph : public ListGraph
|
alpar@395
|
592 |
{
|
alpar@395
|
593 |
public:
|
alpar@395
|
594 |
template<typename T> class SymEdgeMap;
|
alpar@395
|
595 |
template<typename T> friend class SymEdgeMap;
|
alpar@395
|
596 |
|
alpar@397
|
597 |
SymListGraph() : ListGraph() { }
|
alpar@397
|
598 |
SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
|
alpar@397
|
599 |
///Adds a pair of oppositely directed edges to the graph.
|
alpar@395
|
600 |
Edge addEdge(Node u, Node v)
|
alpar@395
|
601 |
{
|
alpar@397
|
602 |
Edge e = ListGraph::addEdge(u,v);
|
alpar@397
|
603 |
ListGraph::addEdge(v,u);
|
alpar@395
|
604 |
return e;
|
alpar@395
|
605 |
}
|
alpar@395
|
606 |
|
alpar@397
|
607 |
void erase(Node n) { ListGraph::erase(n); }
|
alpar@395
|
608 |
///The oppositely directed edge.
|
alpar@395
|
609 |
|
alpar@395
|
610 |
///Returns the oppositely directed
|
alpar@395
|
611 |
///pair of the edge \c e.
|
alpar@395
|
612 |
Edge opposite(Edge e) const
|
alpar@395
|
613 |
{
|
alpar@395
|
614 |
Edge f;
|
alpar@395
|
615 |
f.idref() = e.idref() - 2*(e.idref()%2) + 1;
|
alpar@395
|
616 |
return f;
|
alpar@395
|
617 |
}
|
alpar@395
|
618 |
|
alpar@397
|
619 |
///Removes a pair of oppositely directed edges to the graph.
|
alpar@397
|
620 |
void erase(Edge e) {
|
alpar@397
|
621 |
ListGraph::erase(opposite(e));
|
alpar@397
|
622 |
ListGraph::erase(e);
|
alpar@397
|
623 |
}
|
alpar@397
|
624 |
|
alpar@395
|
625 |
///Common data storage for the edge pairs.
|
alpar@395
|
626 |
|
alpar@395
|
627 |
///This map makes it possible to store data shared by the oppositely
|
alpar@395
|
628 |
///directed pairs of edges.
|
alpar@395
|
629 |
template <typename T> class SymEdgeMap : public DynMapBase<Edge>
|
alpar@395
|
630 |
{
|
alpar@395
|
631 |
std::vector<T> container;
|
alpar@395
|
632 |
|
alpar@395
|
633 |
public:
|
alpar@395
|
634 |
typedef T ValueType;
|
alpar@395
|
635 |
typedef Edge KeyType;
|
alpar@395
|
636 |
|
alpar@397
|
637 |
SymEdgeMap(const SymListGraph &_G) :
|
alpar@395
|
638 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
|
alpar@395
|
639 |
{
|
alpar@397
|
640 |
static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
|
alpar@395
|
641 |
}
|
alpar@397
|
642 |
SymEdgeMap(const SymListGraph &_G,const T &t) :
|
alpar@395
|
643 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
|
alpar@395
|
644 |
{
|
alpar@395
|
645 |
G->dyn_edge_maps.push_back(this);
|
alpar@395
|
646 |
}
|
alpar@395
|
647 |
|
alpar@395
|
648 |
SymEdgeMap(const SymEdgeMap<T> &m) :
|
alpar@395
|
649 |
DynMapBase<SymEdge>(*m.G), container(m.container)
|
alpar@395
|
650 |
{
|
alpar@395
|
651 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
652 |
}
|
alpar@395
|
653 |
|
alpar@395
|
654 |
// template<typename TT> friend class SymEdgeMap;
|
alpar@395
|
655 |
|
alpar@395
|
656 |
///\todo It can copy between different types.
|
alpar@395
|
657 |
///
|
alpar@395
|
658 |
|
alpar@395
|
659 |
template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
|
alpar@395
|
660 |
DynMapBase<SymEdge>(*m.G)
|
alpar@395
|
661 |
{
|
alpar@395
|
662 |
G->dyn_node_maps.push_back(this);
|
alpar@395
|
663 |
typename std::vector<TT>::const_iterator i;
|
alpar@395
|
664 |
for(typename std::vector<TT>::const_iterator i=m.container.begin();
|
alpar@395
|
665 |
i!=m.container.end();
|
alpar@395
|
666 |
i++)
|
alpar@395
|
667 |
container.push_back(*i);
|
alpar@395
|
668 |
}
|
alpar@395
|
669 |
|
alpar@395
|
670 |
~SymEdgeMap()
|
alpar@395
|
671 |
{
|
alpar@395
|
672 |
if(G) {
|
alpar@395
|
673 |
std::vector<DynMapBase<Edge>* >::iterator i;
|
alpar@397
|
674 |
for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
|
alpar@397
|
675 |
i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
|
alpar@395
|
676 |
&& *i!=this; ++i) ;
|
alpar@395
|
677 |
//if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
|
alpar@395
|
678 |
//A better way to do that: (Is this really important?)
|
alpar@395
|
679 |
if(*i==this) {
|
alpar@397
|
680 |
*i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
|
alpar@397
|
681 |
static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
|
alpar@395
|
682 |
}
|
alpar@395
|
683 |
}
|
alpar@395
|
684 |
}
|
alpar@395
|
685 |
|
alpar@395
|
686 |
void add(const Edge k)
|
alpar@395
|
687 |
{
|
alpar@395
|
688 |
if(!k.idref()%2&&k.idref()/2>=int(container.size()))
|
alpar@395
|
689 |
container.resize(k.idref()/2+1);
|
alpar@395
|
690 |
}
|
alpar@395
|
691 |
void erase(const Edge k) { }
|
alpar@395
|
692 |
|
alpar@395
|
693 |
void set(Edge n, T a) { container[n.idref()/2]=a; }
|
alpar@395
|
694 |
//T get(Edge n) const { return container[n.idref()/2]; }
|
alpar@395
|
695 |
typename std::vector<T>::reference
|
alpar@395
|
696 |
operator[](Edge n) { return container[n.idref()/2]; }
|
alpar@395
|
697 |
typename std::vector<T>::const_reference
|
alpar@395
|
698 |
operator[](Edge n) const { return container[n.idref()/2]; }
|
alpar@395
|
699 |
|
alpar@395
|
700 |
///\warning There is no safety check at all!
|
alpar@395
|
701 |
///Using operator = between maps attached to different graph may
|
alpar@395
|
702 |
///cause serious problem.
|
alpar@395
|
703 |
///\todo Is this really so?
|
alpar@395
|
704 |
///\todo It can copy between different types.
|
alpar@395
|
705 |
const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
|
alpar@395
|
706 |
{
|
alpar@395
|
707 |
container = m.container;
|
alpar@395
|
708 |
return *this;
|
alpar@395
|
709 |
}
|
alpar@395
|
710 |
template<typename TT>
|
alpar@395
|
711 |
const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
|
alpar@395
|
712 |
{
|
alpar@395
|
713 |
copy(m.container.begin(), m.container.end(), container.begin());
|
alpar@395
|
714 |
return *this;
|
alpar@395
|
715 |
}
|
alpar@395
|
716 |
|
alpar@395
|
717 |
void update() {} //Useless for DynMaps
|
alpar@395
|
718 |
void update(T a) {} //Useless for DynMaps
|
alpar@395
|
719 |
|
alpar@395
|
720 |
};
|
alpar@395
|
721 |
|
alpar@395
|
722 |
};
|
alpar@395
|
723 |
|
alpar@395
|
724 |
|
alpar@395
|
725 |
} //namespace hugo
|
alpar@395
|
726 |
|
alpar@395
|
727 |
|
alpar@395
|
728 |
|
alpar@395
|
729 |
|
alpar@395
|
730 |
#endif //SMART_GRAPH_H
|