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