1 // -*- mode:C++ -*- |
|
2 |
|
3 #ifndef HUGO_LIST_GRAPH_H |
|
4 #define HUGO_LIST_GRAPH_H |
|
5 |
|
6 ///\ingroup graphs |
|
7 ///\file |
|
8 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes. |
|
9 |
|
10 #include <vector> |
|
11 #include <limits.h> |
|
12 |
|
13 #include <hugo/invalid.h> |
|
14 |
|
15 namespace hugo { |
|
16 |
|
17 /// \addtogroup graphs |
|
18 /// @{ |
|
19 |
|
20 class SymListGraph; |
|
21 |
|
22 ///A list graph class. |
|
23 |
|
24 ///This is a simple and fast erasable graph implementation. |
|
25 /// |
|
26 ///It conforms to the graph interface documented under |
|
27 ///the description of \ref GraphSkeleton. |
|
28 ///\sa \ref GraphSkeleton. |
|
29 class ListGraph { |
|
30 |
|
31 //Nodes are double linked. |
|
32 //The free nodes are only single linked using the "next" field. |
|
33 struct NodeT |
|
34 { |
|
35 int first_in,first_out; |
|
36 int prev, next; |
|
37 // NodeT() {} |
|
38 }; |
|
39 //Edges are double linked. |
|
40 //The free edges are only single linked using the "next_in" field. |
|
41 struct EdgeT |
|
42 { |
|
43 int head, tail; |
|
44 int prev_in, prev_out; |
|
45 int next_in, next_out; |
|
46 //FIXME: is this necessary? |
|
47 // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {} |
|
48 }; |
|
49 |
|
50 std::vector<NodeT> nodes; |
|
51 //The first node |
|
52 int first_node; |
|
53 //The first free node |
|
54 int first_free_node; |
|
55 std::vector<EdgeT> edges; |
|
56 //The first free edge |
|
57 int first_free_edge; |
|
58 |
|
59 protected: |
|
60 |
|
61 template <typename Key> class DynMapBase |
|
62 { |
|
63 protected: |
|
64 const ListGraph* G; |
|
65 public: |
|
66 virtual void add(const Key k) = 0; |
|
67 virtual void erase(const Key k) = 0; |
|
68 DynMapBase(const ListGraph &_G) : G(&_G) {} |
|
69 virtual ~DynMapBase() {} |
|
70 friend class ListGraph; |
|
71 }; |
|
72 |
|
73 public: |
|
74 template <typename T> class EdgeMap; |
|
75 template <typename T> class NodeMap; |
|
76 |
|
77 class Node; |
|
78 class Edge; |
|
79 |
|
80 // protected: |
|
81 // HELPME: |
|
82 protected: |
|
83 ///\bug It must be public because of SymEdgeMap. |
|
84 /// |
|
85 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; |
|
86 ///\bug It must be public because of SymEdgeMap. |
|
87 /// |
|
88 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; |
|
89 |
|
90 public: |
|
91 |
|
92 class NodeIt; |
|
93 class EdgeIt; |
|
94 class OutEdgeIt; |
|
95 class InEdgeIt; |
|
96 |
|
97 template <typename T> class NodeMap; |
|
98 template <typename T> class EdgeMap; |
|
99 |
|
100 public: |
|
101 |
|
102 ListGraph() : nodes(), first_node(-1), |
|
103 first_free_node(-1), edges(), first_free_edge(-1) {} |
|
104 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node), |
|
105 first_free_node(_g.first_free_node), |
|
106 edges(_g.edges), |
|
107 first_free_edge(_g.first_free_edge) {} |
|
108 |
|
109 ~ListGraph() |
|
110 { |
|
111 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
112 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
|
113 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
|
114 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; |
|
115 } |
|
116 |
|
117 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
|
118 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
|
119 |
|
120 ///\bug This function does something different than |
|
121 ///its name would suggests... |
|
122 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? |
|
123 ///\bug This function does something different than |
|
124 ///its name would suggests... |
|
125 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
|
126 |
|
127 Node tail(Edge e) const { return edges[e.n].tail; } |
|
128 Node head(Edge e) const { return edges[e.n].head; } |
|
129 |
|
130 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } |
|
131 Node aNode(InEdgeIt e) const { return edges[e.n].head; } |
|
132 |
|
133 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } |
|
134 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } |
|
135 |
|
136 NodeIt& first(NodeIt& v) const { |
|
137 v=NodeIt(*this); return v; } |
|
138 EdgeIt& first(EdgeIt& e) const { |
|
139 e=EdgeIt(*this); return e; } |
|
140 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
|
141 e=OutEdgeIt(*this,v); return e; } |
|
142 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
|
143 e=InEdgeIt(*this,v); return e; } |
|
144 |
|
145 // template< typename It > |
|
146 // It first() const { It e; first(e); return e; } |
|
147 |
|
148 // template< typename It > |
|
149 // It first(Node v) const { It e; first(e,v); return e; } |
|
150 |
|
151 bool valid(Edge e) const { return e.n!=-1; } |
|
152 bool valid(Node n) const { return n.n!=-1; } |
|
153 |
|
154 void setInvalid(Edge &e) { e.n=-1; } |
|
155 void setInvalid(Node &n) { n.n=-1; } |
|
156 |
|
157 template <typename It> It getNext(It it) const |
|
158 { It tmp(it); return next(tmp); } |
|
159 |
|
160 NodeIt& next(NodeIt& it) const { |
|
161 it.n=nodes[it.n].next; |
|
162 return it; |
|
163 } |
|
164 OutEdgeIt& next(OutEdgeIt& it) const |
|
165 { it.n=edges[it.n].next_out; return it; } |
|
166 InEdgeIt& next(InEdgeIt& it) const |
|
167 { it.n=edges[it.n].next_in; return it; } |
|
168 EdgeIt& next(EdgeIt& it) const { |
|
169 if(edges[it.n].next_in!=-1) { |
|
170 it.n=edges[it.n].next_in; |
|
171 } |
|
172 else { |
|
173 int n; |
|
174 for(n=nodes[edges[it.n].head].next; |
|
175 n!=-1 && nodes[n].first_in == -1; |
|
176 n = nodes[n].next) ; |
|
177 it.n = (n==-1)?-1:nodes[n].first_in; |
|
178 } |
|
179 return it; |
|
180 } |
|
181 |
|
182 int id(Node v) const { return v.n; } |
|
183 int id(Edge e) const { return e.n; } |
|
184 |
|
185 /// Adds a new node to the graph. |
|
186 |
|
187 /// \todo It adds the nodes in a reversed order. |
|
188 /// (i.e. the lastly added node becomes the first.) |
|
189 Node addNode() { |
|
190 int n; |
|
191 |
|
192 if(first_free_node==-1) |
|
193 { |
|
194 n = nodes.size(); |
|
195 nodes.push_back(NodeT()); |
|
196 } |
|
197 else { |
|
198 n = first_free_node; |
|
199 first_free_node = nodes[n].next; |
|
200 } |
|
201 |
|
202 nodes[n].next = first_node; |
|
203 if(first_node != -1) nodes[first_node].prev = n; |
|
204 first_node = n; |
|
205 nodes[n].prev = -1; |
|
206 |
|
207 nodes[n].first_in = nodes[n].first_out = -1; |
|
208 |
|
209 Node nn; nn.n=n; |
|
210 |
|
211 //Update dynamic maps |
|
212 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
213 i!=dyn_node_maps.end(); ++i) (**i).add(nn); |
|
214 |
|
215 return nn; |
|
216 } |
|
217 |
|
218 Edge addEdge(Node u, Node v) { |
|
219 int n; |
|
220 |
|
221 if(first_free_edge==-1) |
|
222 { |
|
223 n = edges.size(); |
|
224 edges.push_back(EdgeT()); |
|
225 } |
|
226 else { |
|
227 n = first_free_edge; |
|
228 first_free_edge = edges[n].next_in; |
|
229 } |
|
230 |
|
231 edges[n].tail = u.n; edges[n].head = v.n; |
|
232 |
|
233 edges[n].next_out = nodes[u.n].first_out; |
|
234 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; |
|
235 edges[n].next_in = nodes[v.n].first_in; |
|
236 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; |
|
237 edges[n].prev_in = edges[n].prev_out = -1; |
|
238 |
|
239 nodes[u.n].first_out = nodes[v.n].first_in = n; |
|
240 |
|
241 Edge e; e.n=n; |
|
242 |
|
243 //Update dynamic maps |
|
244 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
|
245 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
|
246 |
|
247 return e; |
|
248 } |
|
249 |
|
250 private: |
|
251 void eraseEdge(int n) { |
|
252 |
|
253 if(edges[n].next_in!=-1) |
|
254 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
|
255 if(edges[n].prev_in!=-1) |
|
256 edges[edges[n].prev_in].next_in = edges[n].next_in; |
|
257 else nodes[edges[n].head].first_in = edges[n].next_in; |
|
258 |
|
259 if(edges[n].next_out!=-1) |
|
260 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
|
261 if(edges[n].prev_out!=-1) |
|
262 edges[edges[n].prev_out].next_out = edges[n].next_out; |
|
263 else nodes[edges[n].tail].first_out = edges[n].next_out; |
|
264 |
|
265 edges[n].next_in = first_free_edge; |
|
266 first_free_edge = -1; |
|
267 |
|
268 //Update dynamic maps |
|
269 Edge e; e.n=n; |
|
270 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
|
271 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); |
|
272 } |
|
273 |
|
274 public: |
|
275 |
|
276 void erase(Node nn) { |
|
277 int n=nn.n; |
|
278 |
|
279 int m; |
|
280 while((m=nodes[n].first_in)!=-1) eraseEdge(m); |
|
281 while((m=nodes[n].first_out)!=-1) eraseEdge(m); |
|
282 |
|
283 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; |
|
284 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; |
|
285 else first_node = nodes[n].next; |
|
286 |
|
287 nodes[n].next = first_free_node; |
|
288 first_free_node = n; |
|
289 |
|
290 //Update dynamic maps |
|
291 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
292 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); |
|
293 } |
|
294 |
|
295 void erase(Edge e) { eraseEdge(e.n); } |
|
296 |
|
297 ///\bug Dynamic maps must be updated! |
|
298 /// |
|
299 void clear() { |
|
300 nodes.clear();edges.clear(); |
|
301 first_node=first_free_node=first_free_edge=-1; |
|
302 } |
|
303 |
|
304 class Node { |
|
305 friend class ListGraph; |
|
306 template <typename T> friend class NodeMap; |
|
307 |
|
308 friend class Edge; |
|
309 friend class OutEdgeIt; |
|
310 friend class InEdgeIt; |
|
311 friend class SymEdge; |
|
312 |
|
313 protected: |
|
314 int n; |
|
315 friend int ListGraph::id(Node v) const; |
|
316 Node(int nn) {n=nn;} |
|
317 public: |
|
318 Node() {} |
|
319 Node (Invalid) { n=-1; } |
|
320 bool operator==(const Node i) const {return n==i.n;} |
|
321 bool operator!=(const Node i) const {return n!=i.n;} |
|
322 bool operator<(const Node i) const {return n<i.n;} |
|
323 }; |
|
324 |
|
325 class NodeIt : public Node { |
|
326 friend class ListGraph; |
|
327 public: |
|
328 NodeIt() : Node() { } |
|
329 NodeIt(Invalid i) : Node(i) { } |
|
330 NodeIt(const ListGraph& G) : Node(G.first_node) { } |
|
331 }; |
|
332 |
|
333 class Edge { |
|
334 friend class ListGraph; |
|
335 template <typename T> friend class EdgeMap; |
|
336 |
|
337 //template <typename T> friend class SymListGraph::SymEdgeMap; |
|
338 //friend Edge SymListGraph::opposite(Edge) const; |
|
339 |
|
340 friend class Node; |
|
341 friend class NodeIt; |
|
342 protected: |
|
343 int n; |
|
344 friend int ListGraph::id(Edge e) const; |
|
345 |
|
346 Edge(int nn) {n=nn;} |
|
347 public: |
|
348 Edge() { } |
|
349 Edge (Invalid) { n=-1; } |
|
350 bool operator==(const Edge i) const {return n==i.n;} |
|
351 bool operator!=(const Edge i) const {return n!=i.n;} |
|
352 bool operator<(const Edge i) const {return n<i.n;} |
|
353 ///\bug This is a workaround until somebody tells me how to |
|
354 ///make class \c SymListGraph::SymEdgeMap friend of Edge |
|
355 int &idref() {return n;} |
|
356 const int &idref() const {return n;} |
|
357 }; |
|
358 |
|
359 class EdgeIt : public Edge { |
|
360 friend class ListGraph; |
|
361 public: |
|
362 EdgeIt(const ListGraph& G) : Edge() { |
|
363 int m; |
|
364 for(m=G.first_node; |
|
365 m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next); |
|
366 n = (m==-1)?-1:G.nodes[m].first_in; |
|
367 } |
|
368 EdgeIt (Invalid i) : Edge(i) { } |
|
369 EdgeIt() : Edge() { } |
|
370 ///\bug This is a workaround until somebody tells me how to |
|
371 ///make class \c SymListGraph::SymEdgeMap friend of Edge |
|
372 int &idref() {return n;} |
|
373 }; |
|
374 |
|
375 class OutEdgeIt : public Edge { |
|
376 friend class ListGraph; |
|
377 public: |
|
378 OutEdgeIt() : Edge() { } |
|
379 OutEdgeIt (Invalid i) : Edge(i) { } |
|
380 |
|
381 OutEdgeIt(const ListGraph& G,const Node v) |
|
382 : Edge(G.nodes[v.n].first_out) {} |
|
383 }; |
|
384 |
|
385 class InEdgeIt : public Edge { |
|
386 friend class ListGraph; |
|
387 public: |
|
388 InEdgeIt() : Edge() { } |
|
389 InEdgeIt (Invalid i) : Edge(i) { } |
|
390 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){} |
|
391 }; |
|
392 |
|
393 template <typename T> class NodeMap : public DynMapBase<Node> |
|
394 { |
|
395 std::vector<T> container; |
|
396 |
|
397 public: |
|
398 typedef T ValueType; |
|
399 typedef Node KeyType; |
|
400 |
|
401 NodeMap(const ListGraph &_G) : |
|
402 DynMapBase<Node>(_G), container(_G.maxNodeId()) |
|
403 { |
|
404 G->dyn_node_maps.push_back(this); |
|
405 } |
|
406 NodeMap(const ListGraph &_G,const T &t) : |
|
407 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) |
|
408 { |
|
409 G->dyn_node_maps.push_back(this); |
|
410 } |
|
411 |
|
412 NodeMap(const NodeMap<T> &m) : |
|
413 DynMapBase<Node>(*m.G), container(m.container) |
|
414 { |
|
415 G->dyn_node_maps.push_back(this); |
|
416 } |
|
417 |
|
418 template<typename TT> friend class NodeMap; |
|
419 |
|
420 ///\todo It can copy between different types. |
|
421 /// |
|
422 template<typename TT> NodeMap(const NodeMap<TT> &m) : |
|
423 DynMapBase<Node>(*m.G) |
|
424 { |
|
425 G->dyn_node_maps.push_back(this); |
|
426 typename std::vector<TT>::const_iterator i; |
|
427 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
428 i!=m.container.end(); |
|
429 i++) |
|
430 container.push_back(*i); |
|
431 } |
|
432 ~NodeMap() |
|
433 { |
|
434 if(G) { |
|
435 std::vector<DynMapBase<Node>* >::iterator i; |
|
436 for(i=G->dyn_node_maps.begin(); |
|
437 i!=G->dyn_node_maps.end() && *i!=this; ++i) ; |
|
438 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... |
|
439 //A better way to do that: (Is this really important?) |
|
440 if(*i==this) { |
|
441 *i=G->dyn_node_maps.back(); |
|
442 G->dyn_node_maps.pop_back(); |
|
443 } |
|
444 } |
|
445 } |
|
446 |
|
447 void add(const Node k) |
|
448 { |
|
449 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
450 } |
|
451 |
|
452 void erase(const Node) { } |
|
453 |
|
454 void set(Node n, T a) { container[n.n]=a; } |
|
455 //'T& operator[](Node n)' would be wrong here |
|
456 typename std::vector<T>::reference |
|
457 operator[](Node n) { return container[n.n]; } |
|
458 //'const T& operator[](Node n)' would be wrong here |
|
459 typename std::vector<T>::const_reference |
|
460 operator[](Node n) const { return container[n.n]; } |
|
461 |
|
462 ///\warning There is no safety check at all! |
|
463 ///Using operator = between maps attached to different graph may |
|
464 ///cause serious problem. |
|
465 ///\todo Is this really so? |
|
466 ///\todo It can copy between different types. |
|
467 const NodeMap<T>& operator=(const NodeMap<T> &m) |
|
468 { |
|
469 container = m.container; |
|
470 return *this; |
|
471 } |
|
472 template<typename TT> |
|
473 const NodeMap<T>& operator=(const NodeMap<TT> &m) |
|
474 { |
|
475 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
476 return *this; |
|
477 } |
|
478 |
|
479 void update() {} //Useless for Dynamic Maps |
|
480 void update(T a) {} //Useless for Dynamic Maps |
|
481 }; |
|
482 |
|
483 template <typename T> class EdgeMap : public DynMapBase<Edge> |
|
484 { |
|
485 std::vector<T> container; |
|
486 |
|
487 public: |
|
488 typedef T ValueType; |
|
489 typedef Edge KeyType; |
|
490 |
|
491 EdgeMap(const ListGraph &_G) : |
|
492 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) |
|
493 { |
|
494 //FIXME: What if there are empty Id's? |
|
495 //FIXME: Can I use 'this' in a constructor? |
|
496 G->dyn_edge_maps.push_back(this); |
|
497 } |
|
498 EdgeMap(const ListGraph &_G,const T &t) : |
|
499 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) |
|
500 { |
|
501 G->dyn_edge_maps.push_back(this); |
|
502 } |
|
503 EdgeMap(const EdgeMap<T> &m) : |
|
504 DynMapBase<Edge>(*m.G), container(m.container) |
|
505 { |
|
506 G->dyn_edge_maps.push_back(this); |
|
507 } |
|
508 |
|
509 template<typename TT> friend class EdgeMap; |
|
510 |
|
511 ///\todo It can copy between different types. |
|
512 /// |
|
513 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : |
|
514 DynMapBase<Edge>(*m.G) |
|
515 { |
|
516 G->dyn_edge_maps.push_back(this); |
|
517 typename std::vector<TT>::const_iterator i; |
|
518 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
519 i!=m.container.end(); |
|
520 i++) |
|
521 container.push_back(*i); |
|
522 } |
|
523 ~EdgeMap() |
|
524 { |
|
525 if(G) { |
|
526 std::vector<DynMapBase<Edge>* >::iterator i; |
|
527 for(i=G->dyn_edge_maps.begin(); |
|
528 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; |
|
529 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
|
530 //A better way to do that: (Is this really important?) |
|
531 if(*i==this) { |
|
532 *i=G->dyn_edge_maps.back(); |
|
533 G->dyn_edge_maps.pop_back(); |
|
534 } |
|
535 } |
|
536 } |
|
537 |
|
538 void add(const Edge k) |
|
539 { |
|
540 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
541 } |
|
542 void erase(const Edge) { } |
|
543 |
|
544 void set(Edge n, T a) { container[n.n]=a; } |
|
545 //T get(Edge n) const { return container[n.n]; } |
|
546 typename std::vector<T>::reference |
|
547 operator[](Edge n) { return container[n.n]; } |
|
548 typename std::vector<T>::const_reference |
|
549 operator[](Edge n) const { return container[n.n]; } |
|
550 |
|
551 ///\warning There is no safety check at all! |
|
552 ///Using operator = between maps attached to different graph may |
|
553 ///cause serious problem. |
|
554 ///\todo Is this really so? |
|
555 ///\todo It can copy between different types. |
|
556 const EdgeMap<T>& operator=(const EdgeMap<T> &m) |
|
557 { |
|
558 container = m.container; |
|
559 return *this; |
|
560 } |
|
561 template<typename TT> |
|
562 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) |
|
563 { |
|
564 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
565 return *this; |
|
566 } |
|
567 |
|
568 void update() {} //Useless for DynMaps |
|
569 void update(T a) {} //Useless for DynMaps |
|
570 }; |
|
571 |
|
572 }; |
|
573 |
|
574 ///Graph for bidirectional edges. |
|
575 |
|
576 ///The purpose of this graph structure is to handle graphs |
|
577 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair |
|
578 ///of oppositely directed edges. |
|
579 ///There is a new edge map type called |
|
580 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap" |
|
581 ///that complements this |
|
582 ///feature by |
|
583 ///storing shared values for the edge pairs. The usual |
|
584 ///\ref GraphSkeleton::EdgeMap "EdgeMap" |
|
585 ///can be used |
|
586 ///as well. |
|
587 /// |
|
588 ///The oppositely directed edge can also be obtained easily |
|
589 ///using \ref opposite. |
|
590 /// |
|
591 ///Here erase(Edge) deletes a pair of edges. |
|
592 /// |
|
593 ///\todo this date structure need some reconsiderations. Maybe it |
|
594 ///should be implemented independently from ListGraph. |
|
595 |
|
596 class SymListGraph : public ListGraph |
|
597 { |
|
598 public: |
|
599 template<typename T> class SymEdgeMap; |
|
600 template<typename T> friend class SymEdgeMap; |
|
601 |
|
602 SymListGraph() : ListGraph() { } |
|
603 SymListGraph(const ListGraph &_g) : ListGraph(_g) { } |
|
604 ///Adds a pair of oppositely directed edges to the graph. |
|
605 Edge addEdge(Node u, Node v) |
|
606 { |
|
607 Edge e = ListGraph::addEdge(u,v); |
|
608 ListGraph::addEdge(v,u); |
|
609 return e; |
|
610 } |
|
611 |
|
612 void erase(Node n) { ListGraph::erase(n); } |
|
613 ///The oppositely directed edge. |
|
614 |
|
615 ///Returns the oppositely directed |
|
616 ///pair of the edge \c e. |
|
617 Edge opposite(Edge e) const |
|
618 { |
|
619 Edge f; |
|
620 f.idref() = e.idref() - 2*(e.idref()%2) + 1; |
|
621 return f; |
|
622 } |
|
623 |
|
624 ///Removes a pair of oppositely directed edges to the graph. |
|
625 void erase(Edge e) { |
|
626 ListGraph::erase(opposite(e)); |
|
627 ListGraph::erase(e); |
|
628 } |
|
629 |
|
630 ///Common data storage for the edge pairs. |
|
631 |
|
632 ///This map makes it possible to store data shared by the oppositely |
|
633 ///directed pairs of edges. |
|
634 template <typename T> class SymEdgeMap : public DynMapBase<Edge> |
|
635 { |
|
636 std::vector<T> container; |
|
637 |
|
638 public: |
|
639 typedef T ValueType; |
|
640 typedef Edge KeyType; |
|
641 |
|
642 SymEdgeMap(const SymListGraph &_G) : |
|
643 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) |
|
644 { |
|
645 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this); |
|
646 } |
|
647 SymEdgeMap(const SymListGraph &_G,const T &t) : |
|
648 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) |
|
649 { |
|
650 G->dyn_edge_maps.push_back(this); |
|
651 } |
|
652 |
|
653 SymEdgeMap(const SymEdgeMap<T> &m) : |
|
654 DynMapBase<SymEdge>(*m.G), container(m.container) |
|
655 { |
|
656 G->dyn_node_maps.push_back(this); |
|
657 } |
|
658 |
|
659 // template<typename TT> friend class SymEdgeMap; |
|
660 |
|
661 ///\todo It can copy between different types. |
|
662 /// |
|
663 |
|
664 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) : |
|
665 DynMapBase<SymEdge>(*m.G) |
|
666 { |
|
667 G->dyn_node_maps.push_back(this); |
|
668 typename std::vector<TT>::const_iterator i; |
|
669 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
670 i!=m.container.end(); |
|
671 i++) |
|
672 container.push_back(*i); |
|
673 } |
|
674 |
|
675 ~SymEdgeMap() |
|
676 { |
|
677 if(G) { |
|
678 std::vector<DynMapBase<Edge>* >::iterator i; |
|
679 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin(); |
|
680 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end() |
|
681 && *i!=this; ++i) ; |
|
682 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
|
683 //A better way to do that: (Is this really important?) |
|
684 if(*i==this) { |
|
685 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back(); |
|
686 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back(); |
|
687 } |
|
688 } |
|
689 } |
|
690 |
|
691 void add(const Edge k) |
|
692 { |
|
693 if(!k.idref()%2&&k.idref()/2>=int(container.size())) |
|
694 container.resize(k.idref()/2+1); |
|
695 } |
|
696 void erase(const Edge k) { } |
|
697 |
|
698 void set(Edge n, T a) { container[n.idref()/2]=a; } |
|
699 //T get(Edge n) const { return container[n.idref()/2]; } |
|
700 typename std::vector<T>::reference |
|
701 operator[](Edge n) { return container[n.idref()/2]; } |
|
702 typename std::vector<T>::const_reference |
|
703 operator[](Edge n) const { return container[n.idref()/2]; } |
|
704 |
|
705 ///\warning There is no safety check at all! |
|
706 ///Using operator = between maps attached to different graph may |
|
707 ///cause serious problem. |
|
708 ///\todo Is this really so? |
|
709 ///\todo It can copy between different types. |
|
710 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m) |
|
711 { |
|
712 container = m.container; |
|
713 return *this; |
|
714 } |
|
715 template<typename TT> |
|
716 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m) |
|
717 { |
|
718 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
719 return *this; |
|
720 } |
|
721 |
|
722 void update() {} //Useless for DynMaps |
|
723 void update(T a) {} //Useless for DynMaps |
|
724 |
|
725 }; |
|
726 |
|
727 }; |
|
728 |
|
729 |
|
730 ///A graph class containing only nodes. |
|
731 |
|
732 ///This class implements a graph structure without edges. |
|
733 ///The most useful application of this class is to be the node set of an |
|
734 ///\ref EdgeSet class. |
|
735 /// |
|
736 ///It conforms to the graph interface documented under |
|
737 ///the description of \ref GraphSkeleton with the exception that you cannot |
|
738 ///add (or delete) edges. The usual edge iterators are exists, but they are |
|
739 ///always \ref INVALID. |
|
740 ///\sa \ref GraphSkeleton |
|
741 ///\sa \ref EdgeSet |
|
742 class NodeSet { |
|
743 |
|
744 //Nodes are double linked. |
|
745 //The free nodes are only single linked using the "next" field. |
|
746 struct NodeT |
|
747 { |
|
748 int first_in,first_out; |
|
749 int prev, next; |
|
750 // NodeT() {} |
|
751 }; |
|
752 |
|
753 std::vector<NodeT> nodes; |
|
754 //The first node |
|
755 int first_node; |
|
756 //The first free node |
|
757 int first_free_node; |
|
758 |
|
759 protected: |
|
760 |
|
761 template <typename Key> class DynMapBase |
|
762 { |
|
763 protected: |
|
764 const NodeSet* G; |
|
765 public: |
|
766 virtual void add(const Key k) = 0; |
|
767 virtual void erase(const Key k) = 0; |
|
768 DynMapBase(const NodeSet &_G) : G(&_G) {} |
|
769 virtual ~DynMapBase() {} |
|
770 friend class NodeSet; |
|
771 }; |
|
772 |
|
773 public: |
|
774 template <typename T> class EdgeMap; |
|
775 template <typename T> class NodeMap; |
|
776 |
|
777 class Node; |
|
778 class Edge; |
|
779 |
|
780 // protected: |
|
781 // HELPME: |
|
782 protected: |
|
783 ///\bug It must be public because of SymEdgeMap. |
|
784 /// |
|
785 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; |
|
786 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; |
|
787 |
|
788 public: |
|
789 |
|
790 class NodeIt; |
|
791 class EdgeIt; |
|
792 class OutEdgeIt; |
|
793 class InEdgeIt; |
|
794 |
|
795 template <typename T> class NodeMap; |
|
796 template <typename T> class EdgeMap; |
|
797 |
|
798 public: |
|
799 |
|
800 ///Default constructor |
|
801 NodeSet() : nodes(), first_node(-1), |
|
802 first_free_node(-1) {} |
|
803 ///Copy constructor |
|
804 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node), |
|
805 first_free_node(_g.first_free_node) {} |
|
806 |
|
807 ~NodeSet() |
|
808 { |
|
809 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
810 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
|
811 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
|
812 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; |
|
813 } |
|
814 |
|
815 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
|
816 int edgeNum() const { return 0; } //FIXME: What is this? |
|
817 |
|
818 ///\bug This function does something different than |
|
819 ///its name would suggests... |
|
820 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? |
|
821 ///\bug This function does something different than |
|
822 ///its name would suggests... |
|
823 int maxEdgeId() const { return 0; } //FIXME: What is this? |
|
824 |
|
825 Node tail(Edge e) const { return INVALID; } |
|
826 Node head(Edge e) const { return INVALID; } |
|
827 |
|
828 Node aNode(OutEdgeIt e) const { return INVALID; } |
|
829 Node aNode(InEdgeIt e) const { return INVALID; } |
|
830 |
|
831 Node bNode(OutEdgeIt e) const { return INVALID; } |
|
832 Node bNode(InEdgeIt e) const { return INVALID; } |
|
833 |
|
834 NodeIt& first(NodeIt& v) const { |
|
835 v=NodeIt(*this); return v; } |
|
836 EdgeIt& first(EdgeIt& e) const { |
|
837 e=EdgeIt(*this); return e; } |
|
838 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
|
839 e=OutEdgeIt(*this,v); return e; } |
|
840 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
|
841 e=InEdgeIt(*this,v); return e; } |
|
842 |
|
843 // template< typename It > |
|
844 // It first() const { It e; first(e); return e; } |
|
845 |
|
846 // template< typename It > |
|
847 // It first(Node v) const { It e; first(e,v); return e; } |
|
848 |
|
849 bool valid(Edge e) const { return false; } |
|
850 bool valid(Node n) const { return n.n!=-1; } |
|
851 |
|
852 void setInvalid(Edge &e) { } |
|
853 void setInvalid(Node &n) { n.n=-1; } |
|
854 |
|
855 template <typename It> It getNext(It it) const |
|
856 { It tmp(it); return next(tmp); } |
|
857 |
|
858 NodeIt& next(NodeIt& it) const { |
|
859 it.n=nodes[it.n].next; |
|
860 return it; |
|
861 } |
|
862 OutEdgeIt& next(OutEdgeIt& it) const { return it; } |
|
863 InEdgeIt& next(InEdgeIt& it) const { return it; } |
|
864 EdgeIt& next(EdgeIt& it) const { return it; } |
|
865 |
|
866 int id(Node v) const { return v.n; } |
|
867 int id(Edge e) const { return -1; } |
|
868 |
|
869 /// Adds a new node to the graph. |
|
870 |
|
871 /// \todo It adds the nodes in a reversed order. |
|
872 /// (i.e. the lastly added node becomes the first.) |
|
873 Node addNode() { |
|
874 int n; |
|
875 |
|
876 if(first_free_node==-1) |
|
877 { |
|
878 n = nodes.size(); |
|
879 nodes.push_back(NodeT()); |
|
880 } |
|
881 else { |
|
882 n = first_free_node; |
|
883 first_free_node = nodes[n].next; |
|
884 } |
|
885 |
|
886 nodes[n].next = first_node; |
|
887 if(first_node != -1) nodes[first_node].prev = n; |
|
888 first_node = n; |
|
889 nodes[n].prev = -1; |
|
890 |
|
891 nodes[n].first_in = nodes[n].first_out = -1; |
|
892 |
|
893 Node nn; nn.n=n; |
|
894 |
|
895 //Update dynamic maps |
|
896 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
897 i!=dyn_node_maps.end(); ++i) (**i).add(nn); |
|
898 |
|
899 return nn; |
|
900 } |
|
901 |
|
902 void erase(Node nn) { |
|
903 int n=nn.n; |
|
904 |
|
905 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; |
|
906 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; |
|
907 else first_node = nodes[n].next; |
|
908 |
|
909 nodes[n].next = first_free_node; |
|
910 first_free_node = n; |
|
911 |
|
912 //Update dynamic maps |
|
913 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
914 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); |
|
915 } |
|
916 |
|
917 ///\bug Dynamic maps must be updated! |
|
918 /// |
|
919 void clear() { |
|
920 nodes.clear(); |
|
921 first_node = first_free_node = -1; |
|
922 } |
|
923 |
|
924 class Node { |
|
925 friend class NodeSet; |
|
926 template <typename T> friend class NodeMap; |
|
927 |
|
928 friend class Edge; |
|
929 friend class OutEdgeIt; |
|
930 friend class InEdgeIt; |
|
931 |
|
932 protected: |
|
933 int n; |
|
934 friend int NodeSet::id(Node v) const; |
|
935 Node(int nn) {n=nn;} |
|
936 public: |
|
937 Node() {} |
|
938 Node (Invalid i) { n=-1; } |
|
939 bool operator==(const Node i) const {return n==i.n;} |
|
940 bool operator!=(const Node i) const {return n!=i.n;} |
|
941 bool operator<(const Node i) const {return n<i.n;} |
|
942 }; |
|
943 |
|
944 class NodeIt : public Node { |
|
945 friend class NodeSet; |
|
946 public: |
|
947 NodeIt(const NodeSet& G) : Node(G.first_node) { } |
|
948 NodeIt() : Node() { } |
|
949 }; |
|
950 |
|
951 class Edge { |
|
952 //friend class NodeSet; |
|
953 //template <typename T> friend class EdgeMap; |
|
954 |
|
955 //template <typename T> friend class SymNodeSet::SymEdgeMap; |
|
956 //friend Edge SymNodeSet::opposite(Edge) const; |
|
957 |
|
958 // friend class Node; |
|
959 // friend class NodeIt; |
|
960 protected: |
|
961 //friend int NodeSet::id(Edge e) const; |
|
962 // Edge(int nn) {} |
|
963 public: |
|
964 Edge() { } |
|
965 Edge (Invalid) { } |
|
966 bool operator==(const Edge i) const {return true;} |
|
967 bool operator!=(const Edge i) const {return false;} |
|
968 bool operator<(const Edge i) const {return false;} |
|
969 ///\bug This is a workaround until somebody tells me how to |
|
970 ///make class \c SymNodeSet::SymEdgeMap friend of Edge |
|
971 // int idref() {return -1;} |
|
972 // int idref() const {return -1;} |
|
973 }; |
|
974 |
|
975 class EdgeIt : public Edge { |
|
976 //friend class NodeSet; |
|
977 public: |
|
978 EdgeIt(const NodeSet& G) : Edge() { } |
|
979 EdgeIt (Invalid i) : Edge(i) { } |
|
980 EdgeIt() : Edge() { } |
|
981 ///\bug This is a workaround until somebody tells me how to |
|
982 ///make class \c SymNodeSet::SymEdgeMap friend of Edge |
|
983 // int idref() {return -1;} |
|
984 }; |
|
985 |
|
986 class OutEdgeIt : public Edge { |
|
987 friend class NodeSet; |
|
988 public: |
|
989 OutEdgeIt() : Edge() { } |
|
990 OutEdgeIt (Invalid i) : Edge(i) { } |
|
991 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} |
|
992 }; |
|
993 |
|
994 class InEdgeIt : public Edge { |
|
995 friend class NodeSet; |
|
996 public: |
|
997 InEdgeIt() : Edge() { } |
|
998 InEdgeIt (Invalid i) : Edge(i) { } |
|
999 InEdgeIt(const NodeSet& G,Node v) :Edge() {} |
|
1000 }; |
|
1001 |
|
1002 template <typename T> class NodeMap : public DynMapBase<Node> |
|
1003 { |
|
1004 std::vector<T> container; |
|
1005 |
|
1006 public: |
|
1007 typedef T ValueType; |
|
1008 typedef Node KeyType; |
|
1009 |
|
1010 NodeMap(const NodeSet &_G) : |
|
1011 DynMapBase<Node>(_G), container(_G.maxNodeId()) |
|
1012 { |
|
1013 G->dyn_node_maps.push_back(this); |
|
1014 } |
|
1015 NodeMap(const NodeSet &_G,const T &t) : |
|
1016 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) |
|
1017 { |
|
1018 G->dyn_node_maps.push_back(this); |
|
1019 } |
|
1020 |
|
1021 NodeMap(const NodeMap<T> &m) : |
|
1022 DynMapBase<Node>(*m.G), container(m.container) |
|
1023 { |
|
1024 G->dyn_node_maps.push_back(this); |
|
1025 } |
|
1026 |
|
1027 template<typename TT> friend class NodeMap; |
|
1028 |
|
1029 ///\todo It can copy between different types. |
|
1030 /// |
|
1031 template<typename TT> NodeMap(const NodeMap<TT> &m) : |
|
1032 DynMapBase<Node>(*m.G) |
|
1033 { |
|
1034 G->dyn_node_maps.push_back(this); |
|
1035 typename std::vector<TT>::const_iterator i; |
|
1036 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
1037 i!=m.container.end(); |
|
1038 i++) |
|
1039 container.push_back(*i); |
|
1040 } |
|
1041 ~NodeMap() |
|
1042 { |
|
1043 if(G) { |
|
1044 std::vector<DynMapBase<Node>* >::iterator i; |
|
1045 for(i=G->dyn_node_maps.begin(); |
|
1046 i!=G->dyn_node_maps.end() && *i!=this; ++i) ; |
|
1047 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... |
|
1048 //A better way to do that: (Is this really important?) |
|
1049 if(*i==this) { |
|
1050 *i=G->dyn_node_maps.back(); |
|
1051 G->dyn_node_maps.pop_back(); |
|
1052 } |
|
1053 } |
|
1054 } |
|
1055 |
|
1056 void add(const Node k) |
|
1057 { |
|
1058 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
1059 } |
|
1060 |
|
1061 void erase(const Node) { } |
|
1062 |
|
1063 void set(Node n, T a) { container[n.n]=a; } |
|
1064 //'T& operator[](Node n)' would be wrong here |
|
1065 typename std::vector<T>::reference |
|
1066 operator[](Node n) { return container[n.n]; } |
|
1067 //'const T& operator[](Node n)' would be wrong here |
|
1068 typename std::vector<T>::const_reference |
|
1069 operator[](Node n) const { return container[n.n]; } |
|
1070 |
|
1071 ///\warning There is no safety check at all! |
|
1072 ///Using operator = between maps attached to different graph may |
|
1073 ///cause serious problem. |
|
1074 ///\todo Is this really so? |
|
1075 ///\todo It can copy between different types. |
|
1076 const NodeMap<T>& operator=(const NodeMap<T> &m) |
|
1077 { |
|
1078 container = m.container; |
|
1079 return *this; |
|
1080 } |
|
1081 template<typename TT> |
|
1082 const NodeMap<T>& operator=(const NodeMap<TT> &m) |
|
1083 { |
|
1084 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
1085 return *this; |
|
1086 } |
|
1087 |
|
1088 void update() {} //Useless for Dynamic Maps |
|
1089 void update(T a) {} //Useless for Dynamic Maps |
|
1090 }; |
|
1091 |
|
1092 template <typename T> class EdgeMap |
|
1093 { |
|
1094 public: |
|
1095 typedef T ValueType; |
|
1096 typedef Edge KeyType; |
|
1097 |
|
1098 EdgeMap(const NodeSet &) { } |
|
1099 EdgeMap(const NodeSet &,const T &) { } |
|
1100 EdgeMap(const EdgeMap<T> &) { } |
|
1101 // template<typename TT> friend class EdgeMap; |
|
1102 |
|
1103 ///\todo It can copy between different types. |
|
1104 /// |
|
1105 template<typename TT> EdgeMap(const EdgeMap<TT> &) { } |
|
1106 ~EdgeMap() { } |
|
1107 |
|
1108 void add(const Edge ) { } |
|
1109 void erase(const Edge) { } |
|
1110 |
|
1111 void set(Edge, T) { } |
|
1112 //T get(Edge n) const { return container[n.n]; } |
|
1113 ValueType &operator[](Edge) { return *((T*)(NULL)); } |
|
1114 const ValueType &operator[](Edge) const { return *((T*)(NULL)); } |
|
1115 |
|
1116 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; } |
|
1117 |
|
1118 template<typename TT> |
|
1119 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; } |
|
1120 |
|
1121 void update() {} |
|
1122 void update(T a) {} |
|
1123 }; |
|
1124 }; |
|
1125 |
|
1126 |
|
1127 |
|
1128 ///Graph structure using a node set of another graph. |
|
1129 |
|
1130 ///This structure can be used to establish another graph over a node set |
|
1131 /// of an existing one. The node iterator will go through the nodes of the |
|
1132 /// original graph, and the NodeMap's of both graphs will convert to |
|
1133 /// each other. |
|
1134 /// |
|
1135 ///\warning Adding or deleting nodes from the graph is not safe if an |
|
1136 ///\ref EdgeSet is currently attached to it! |
|
1137 /// |
|
1138 ///\todo Make it possible to add/delete edges from the base graph |
|
1139 ///(and from \ref EdgeSet, as well) |
|
1140 /// |
|
1141 ///\param GG The type of the graph which shares its node set with this class. |
|
1142 ///Its interface must conform with \ref GraphSkeleton. |
|
1143 /// |
|
1144 ///It conforms to the graph interface documented under |
|
1145 ///the description of \ref GraphSkeleton. |
|
1146 ///\sa \ref GraphSkeleton. |
|
1147 ///\sa \ref NodeSet. |
|
1148 template<typename GG> |
|
1149 class EdgeSet { |
|
1150 |
|
1151 typedef GG NodeGraphType; |
|
1152 |
|
1153 NodeGraphType &G; |
|
1154 |
|
1155 public: |
|
1156 class Node; |
|
1157 int id(Node v) const; |
|
1158 |
|
1159 class Node : public NodeGraphType::Node { |
|
1160 friend class EdgeSet; |
|
1161 // template <typename T> friend class NodeMap; |
|
1162 |
|
1163 friend class Edge; |
|
1164 friend class OutEdgeIt; |
|
1165 friend class InEdgeIt; |
|
1166 friend class SymEdge; |
|
1167 |
|
1168 public: |
|
1169 friend int EdgeSet::id(Node v) const; |
|
1170 // Node(int nn) {n=nn;} |
|
1171 public: |
|
1172 Node() : NodeGraphType::Node() {} |
|
1173 Node (Invalid i) : NodeGraphType::Node(i) {} |
|
1174 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {} |
|
1175 }; |
|
1176 |
|
1177 class NodeIt : public NodeGraphType::NodeIt { |
|
1178 friend class EdgeSet; |
|
1179 public: |
|
1180 NodeIt() : NodeGraphType::NodeIt() { } |
|
1181 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} |
|
1182 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } |
|
1183 NodeIt(const typename NodeGraphType::NodeIt &n) |
|
1184 : NodeGraphType::NodeIt(n) {} |
|
1185 operator Node() { return Node(*this);} |
|
1186 }; |
|
1187 |
|
1188 private: |
|
1189 //Edges are double linked. |
|
1190 //The free edges are only single linked using the "next_in" field. |
|
1191 struct NodeT |
|
1192 { |
|
1193 int first_in,first_out; |
|
1194 NodeT() : first_in(-1), first_out(-1) { } |
|
1195 }; |
|
1196 |
|
1197 struct EdgeT |
|
1198 { |
|
1199 Node head, tail; |
|
1200 int prev_in, prev_out; |
|
1201 int next_in, next_out; |
|
1202 }; |
|
1203 |
|
1204 |
|
1205 typename NodeGraphType::template NodeMap<NodeT> nodes; |
|
1206 |
|
1207 std::vector<EdgeT> edges; |
|
1208 //The first free edge |
|
1209 int first_free_edge; |
|
1210 |
|
1211 protected: |
|
1212 |
|
1213 template <typename Key> class DynMapBase |
|
1214 { |
|
1215 protected: |
|
1216 const EdgeSet* G; |
|
1217 public: |
|
1218 virtual void add(const Key k) = 0; |
|
1219 virtual void erase(const Key k) = 0; |
|
1220 DynMapBase(const EdgeSet &_G) : G(&_G) {} |
|
1221 virtual ~DynMapBase() {} |
|
1222 friend class EdgeSet; |
|
1223 }; |
|
1224 |
|
1225 public: |
|
1226 //template <typename T> class NodeMap; |
|
1227 template <typename T> class EdgeMap; |
|
1228 |
|
1229 class Node; |
|
1230 class Edge; |
|
1231 |
|
1232 // protected: |
|
1233 // HELPME: |
|
1234 protected: |
|
1235 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps; |
|
1236 ///\bug It must be public because of SymEdgeMap. |
|
1237 /// |
|
1238 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; |
|
1239 |
|
1240 public: |
|
1241 |
|
1242 class NodeIt; |
|
1243 class EdgeIt; |
|
1244 class OutEdgeIt; |
|
1245 class InEdgeIt; |
|
1246 |
|
1247 template <typename T> class NodeMap; |
|
1248 template <typename T> class EdgeMap; |
|
1249 |
|
1250 public: |
|
1251 |
|
1252 ///Constructor |
|
1253 |
|
1254 ///Construates a new graph based on the nodeset of an existing one. |
|
1255 ///\param _G the base graph. |
|
1256 ///\todo It looks like a copy constructor, but it isn't. |
|
1257 EdgeSet(NodeGraphType &_G) : G(_G), |
|
1258 nodes(_G), edges(), |
|
1259 first_free_edge(-1) { } |
|
1260 ///Copy constructor |
|
1261 |
|
1262 ///Makes a copy of an EdgeSet. |
|
1263 ///It will be based on the same graph. |
|
1264 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), |
|
1265 first_free_edge(_g.first_free_edge) { } |
|
1266 |
|
1267 ~EdgeSet() |
|
1268 { |
|
1269 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
1270 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
|
1271 for(typename std::vector<DynMapBase<Edge> * >::iterator |
|
1272 i=dyn_edge_maps.begin(); |
|
1273 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; |
|
1274 } |
|
1275 |
|
1276 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? |
|
1277 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
|
1278 |
|
1279 ///\bug This function does something different than |
|
1280 ///its name would suggests... |
|
1281 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this? |
|
1282 ///\bug This function does something different than |
|
1283 ///its name would suggests... |
|
1284 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
|
1285 |
|
1286 Node tail(Edge e) const { return edges[e.n].tail; } |
|
1287 Node head(Edge e) const { return edges[e.n].head; } |
|
1288 |
|
1289 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } |
|
1290 Node aNode(InEdgeIt e) const { return edges[e.n].head; } |
|
1291 |
|
1292 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } |
|
1293 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } |
|
1294 |
|
1295 NodeIt& first(NodeIt& v) const { |
|
1296 v=NodeIt(*this); return v; } |
|
1297 EdgeIt& first(EdgeIt& e) const { |
|
1298 e=EdgeIt(*this); return e; } |
|
1299 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
|
1300 e=OutEdgeIt(*this,v); return e; } |
|
1301 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
|
1302 e=InEdgeIt(*this,v); return e; } |
|
1303 |
|
1304 // template< typename It > |
|
1305 // It first() const { It e; first(e); return e; } |
|
1306 |
|
1307 // template< typename It > |
|
1308 // It first(Node v) const { It e; first(e,v); return e; } |
|
1309 |
|
1310 bool valid(Edge e) const { return e.n!=-1; } |
|
1311 bool valid(Node n) const { return G.valid(n); } |
|
1312 |
|
1313 void setInvalid(Edge &e) { e.n=-1; } |
|
1314 void setInvalid(Node &n) { G.setInvalid(n); } |
|
1315 |
|
1316 template <typename It> It getNext(It it) const |
|
1317 { It tmp(it); return next(tmp); } |
|
1318 |
|
1319 NodeIt& next(NodeIt& it) const { G.next(it); return it; } |
|
1320 OutEdgeIt& next(OutEdgeIt& it) const |
|
1321 { it.n=edges[it.n].next_out; return it; } |
|
1322 InEdgeIt& next(InEdgeIt& it) const |
|
1323 { it.n=edges[it.n].next_in; return it; } |
|
1324 EdgeIt& next(EdgeIt& it) const { |
|
1325 if(edges[it.n].next_in!=-1) { |
|
1326 it.n=edges[it.n].next_in; |
|
1327 } |
|
1328 else { |
|
1329 NodeIt n; |
|
1330 for(n=next(edges[it.n].head); |
|
1331 valid(n) && nodes[n].first_in == -1; |
|
1332 next(n)) ; |
|
1333 it.n = (valid(n))?-1:nodes[n].first_in; |
|
1334 } |
|
1335 return it; |
|
1336 } |
|
1337 |
|
1338 int id(Edge e) const { return e.n; } |
|
1339 |
|
1340 /// Adds a new node to the graph. |
|
1341 Node addNode() { return G.AddNode(); } |
|
1342 |
|
1343 Edge addEdge(Node u, Node v) { |
|
1344 int n; |
|
1345 |
|
1346 if(first_free_edge==-1) |
|
1347 { |
|
1348 n = edges.size(); |
|
1349 edges.push_back(EdgeT()); |
|
1350 } |
|
1351 else { |
|
1352 n = first_free_edge; |
|
1353 first_free_edge = edges[n].next_in; |
|
1354 } |
|
1355 |
|
1356 edges[n].tail = u; edges[n].head = v; |
|
1357 |
|
1358 edges[n].next_out = nodes[u].first_out; |
|
1359 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n; |
|
1360 edges[n].next_in = nodes[v].first_in; |
|
1361 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n; |
|
1362 edges[n].prev_in = edges[n].prev_out = -1; |
|
1363 |
|
1364 nodes[u].first_out = nodes[v].first_in = n; |
|
1365 |
|
1366 Edge e; e.n=n; |
|
1367 |
|
1368 //Update dynamic maps |
|
1369 for(typename std::vector<DynMapBase<Edge> * >::iterator |
|
1370 i=dyn_edge_maps.begin(); |
|
1371 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
|
1372 |
|
1373 return e; |
|
1374 } |
|
1375 |
|
1376 private: |
|
1377 void eraseEdge(int n) { |
|
1378 |
|
1379 if(edges[n].next_in!=-1) |
|
1380 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
|
1381 if(edges[n].prev_in!=-1) |
|
1382 edges[edges[n].prev_in].next_in = edges[n].next_in; |
|
1383 else nodes[edges[n].head].first_in = edges[n].next_in; |
|
1384 |
|
1385 if(edges[n].next_out!=-1) |
|
1386 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
|
1387 if(edges[n].prev_out!=-1) |
|
1388 edges[edges[n].prev_out].next_out = edges[n].next_out; |
|
1389 else nodes[edges[n].tail].first_out = edges[n].next_out; |
|
1390 |
|
1391 edges[n].next_in = first_free_edge; |
|
1392 first_free_edge = -1; |
|
1393 |
|
1394 //Update dynamic maps |
|
1395 Edge e; e.n=n; |
|
1396 for(typename std::vector<DynMapBase<Edge> * >::iterator |
|
1397 i=dyn_edge_maps.begin(); |
|
1398 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); |
|
1399 } |
|
1400 |
|
1401 public: |
|
1402 |
|
1403 // void erase(Node nn) { |
|
1404 // int n=nn.n; |
|
1405 // int m; |
|
1406 // while((m=nodes[n].first_in)!=-1) eraseEdge(m); |
|
1407 // while((m=nodes[n].first_out)!=-1) eraseEdge(m); |
|
1408 // } |
|
1409 |
|
1410 void erase(Edge e) { eraseEdge(e.n); } |
|
1411 |
|
1412 // //\bug Dynamic maps must be updated! |
|
1413 // // |
|
1414 // void clear() { |
|
1415 // nodes.clear();edges.clear(); |
|
1416 // first_node=first_free_node=first_free_edge=-1; |
|
1417 // } |
|
1418 |
|
1419 class Edge { |
|
1420 friend class EdgeSet; |
|
1421 template <typename T> friend class EdgeMap; |
|
1422 |
|
1423 //template <typename T> friend class SymEdgeSet::SymEdgeMap; |
|
1424 //friend Edge SymEdgeSet::opposite(Edge) const; |
|
1425 |
|
1426 friend class Node; |
|
1427 friend class NodeIt; |
|
1428 protected: |
|
1429 int n; |
|
1430 friend int EdgeSet::id(Edge e) const; |
|
1431 |
|
1432 Edge(int nn) {n=nn;} |
|
1433 public: |
|
1434 Edge() { } |
|
1435 Edge (Invalid) { n=-1; } |
|
1436 bool operator==(const Edge i) const {return n==i.n;} |
|
1437 bool operator!=(const Edge i) const {return n!=i.n;} |
|
1438 bool operator<(const Edge i) const {return n<i.n;} |
|
1439 ///\bug This is a workaround until somebody tells me how to |
|
1440 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge |
|
1441 int &idref() {return n;} |
|
1442 const int &idref() const {return n;} |
|
1443 }; |
|
1444 |
|
1445 class EdgeIt : public Edge { |
|
1446 friend class EdgeSet; |
|
1447 public: |
|
1448 EdgeIt(const EdgeSet& G) : Edge() { |
|
1449 // typename NodeGraphType::Node m; |
|
1450 NodeIt m; |
|
1451 for(G.first(m); |
|
1452 G.valid(m) && G.nodes[m].first_in == -1; G.next(m)); |
|
1453 //AJJAJ! This is a non sense!!!!!!! |
|
1454 this->n = G.valid(m)?-1:G.nodes[m].first_in; |
|
1455 } |
|
1456 EdgeIt (Invalid i) : Edge(i) { } |
|
1457 EdgeIt() : Edge() { } |
|
1458 ///\bug This is a workaround until somebody tells me how to |
|
1459 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge |
|
1460 int &idref() {return this->n;} |
|
1461 }; |
|
1462 |
|
1463 class OutEdgeIt : public Edge { |
|
1464 friend class EdgeSet; |
|
1465 public: |
|
1466 OutEdgeIt() : Edge() { } |
|
1467 OutEdgeIt (Invalid i) : Edge(i) { } |
|
1468 |
|
1469 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { } |
|
1470 }; |
|
1471 |
|
1472 class InEdgeIt : public Edge { |
|
1473 friend class EdgeSet; |
|
1474 public: |
|
1475 InEdgeIt() : Edge() { } |
|
1476 InEdgeIt (Invalid i) : Edge(i) { } |
|
1477 InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { } |
|
1478 }; |
|
1479 |
|
1480 template <typename T> class NodeMap : |
|
1481 public NodeGraphType::template NodeMap<T> |
|
1482 { |
|
1483 public: |
|
1484 NodeMap(const EdgeSet &_G) : |
|
1485 NodeGraphType::NodeMap(_G.G) { } //AJAJJ <T> would be wrong!!! |
|
1486 NodeMap(const EdgeSet &_G,const T &t) : |
|
1487 NodeGraphType::NodeMap(_G.G,t) { } |
|
1488 //It is unnecessary |
|
1489 NodeMap(const typename NodeGraphType::template NodeMap<T> &m) : |
|
1490 NodeGraphType::NodeMap(m) { } |
|
1491 |
|
1492 ///\todo It can copy between different types. |
|
1493 /// |
|
1494 template<typename TT> |
|
1495 NodeMap(const typename NodeGraphType::template NodeMap<TT> &m) |
|
1496 : NodeGraphType::NodeMap(m) { } |
|
1497 }; |
|
1498 |
|
1499 template <typename T> class EdgeMap : public DynMapBase<Edge> |
|
1500 { |
|
1501 std::vector<T> container; |
|
1502 |
|
1503 public: |
|
1504 typedef T ValueType; |
|
1505 typedef Edge KeyType; |
|
1506 |
|
1507 EdgeMap(const EdgeSet &_G) : |
|
1508 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) |
|
1509 { |
|
1510 //FIXME: What if there are empty Id's? |
|
1511 //FIXME: Can I use 'this' in a constructor? |
|
1512 G->dyn_edge_maps.push_back(this); |
|
1513 } |
|
1514 EdgeMap(const EdgeSet &_G,const T &t) : |
|
1515 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) |
|
1516 { |
|
1517 G->dyn_edge_maps.push_back(this); |
|
1518 } |
|
1519 EdgeMap(const EdgeMap<T> &m) : |
|
1520 DynMapBase<Edge>(*m.G), container(m.container) |
|
1521 { |
|
1522 G->dyn_edge_maps.push_back(this); |
|
1523 } |
|
1524 |
|
1525 template<typename TT> friend class EdgeMap; |
|
1526 |
|
1527 ///\todo It can copy between different types. |
|
1528 /// |
|
1529 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : |
|
1530 DynMapBase<Edge>(*m.G) |
|
1531 { |
|
1532 G->dyn_edge_maps.push_back(this); |
|
1533 typename std::vector<TT>::const_iterator i; |
|
1534 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
1535 i!=m.container.end(); |
|
1536 i++) |
|
1537 container.push_back(*i); |
|
1538 } |
|
1539 ~EdgeMap() |
|
1540 { |
|
1541 if(G) { |
|
1542 typename std::vector<DynMapBase<Edge>* >::iterator i; |
|
1543 for(i=G->dyn_edge_maps.begin(); |
|
1544 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; |
|
1545 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
|
1546 //A better way to do that: (Is this really important?) |
|
1547 if(*i==this) { |
|
1548 *i=G->dyn_edge_maps.back(); |
|
1549 G->dyn_edge_maps.pop_back(); |
|
1550 } |
|
1551 } |
|
1552 } |
|
1553 |
|
1554 void add(const Edge k) |
|
1555 { |
|
1556 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
1557 } |
|
1558 void erase(const Edge) { } |
|
1559 |
|
1560 void set(Edge n, T a) { container[n.n]=a; } |
|
1561 //T get(Edge n) const { return container[n.n]; } |
|
1562 typename std::vector<T>::reference |
|
1563 operator[](Edge n) { return container[n.n]; } |
|
1564 typename std::vector<T>::const_reference |
|
1565 operator[](Edge n) const { return container[n.n]; } |
|
1566 |
|
1567 ///\warning There is no safety check at all! |
|
1568 ///Using operator = between maps attached to different graph may |
|
1569 ///cause serious problem. |
|
1570 ///\todo Is this really so? |
|
1571 ///\todo It can copy between different types. |
|
1572 const EdgeMap<T>& operator=(const EdgeMap<T> &m) |
|
1573 { |
|
1574 container = m.container; |
|
1575 return *this; |
|
1576 } |
|
1577 template<typename TT> |
|
1578 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) |
|
1579 { |
|
1580 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
1581 return *this; |
|
1582 } |
|
1583 |
|
1584 void update() {} //Useless for DynMaps |
|
1585 void update(T a) {} //Useless for DynMaps |
|
1586 }; |
|
1587 |
|
1588 }; |
|
1589 |
|
1590 template< typename GG> |
|
1591 int EdgeSet<GG>::id(Node v) const { return G.id(v); } |
|
1592 |
|
1593 /// @} |
|
1594 |
|
1595 } //namespace hugo |
|
1596 |
|
1597 #endif //HUGO_LIST_GRAPH_H |
|