|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_BITS_BPUGRAPH_EXTENDER_H |
|
20 #define LEMON_BITS_BPUGRAPH_EXTENDER_H |
|
21 |
|
22 #include <lemon/bits/invalid.h> |
|
23 #include <lemon/error.h> |
|
24 |
|
25 #include <lemon/bits/map_extender.h> |
|
26 #include <lemon/bits/default_map.h> |
|
27 |
|
28 #include <lemon/concept_check.h> |
|
29 #include <lemon/concept/maps.h> |
|
30 |
|
31 ///\ingroup graphbits |
|
32 ///\file |
|
33 ///\brief Extenders for the graph types |
|
34 namespace lemon { |
|
35 |
|
36 /// \ingroup graphbits |
|
37 /// |
|
38 /// \brief Extender for the BpUGraphs |
|
39 template <typename Base> |
|
40 class BpUGraphExtender : public Base { |
|
41 public: |
|
42 typedef Base Parent; |
|
43 typedef BpUGraphExtender Graph; |
|
44 |
|
45 typedef typename Parent::Node Node; |
|
46 typedef typename Parent::UEdge UEdge; |
|
47 |
|
48 |
|
49 using Parent::first; |
|
50 using Parent::next; |
|
51 |
|
52 using Parent::id; |
|
53 |
|
54 class ANode : public Node { |
|
55 friend class BpUGraphExtender; |
|
56 public: |
|
57 ANode() {} |
|
58 ANode(const Node& node) : Node(node) { |
|
59 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
|
60 typename Parent::NodeSetError()); |
|
61 } |
|
62 ANode(Invalid) : Node(INVALID) {} |
|
63 }; |
|
64 |
|
65 void first(ANode& node) const { |
|
66 Parent::firstANode(static_cast<Node&>(node)); |
|
67 } |
|
68 void next(ANode& node) const { |
|
69 Parent::nextANode(static_cast<Node&>(node)); |
|
70 } |
|
71 |
|
72 int id(const ANode& node) const { |
|
73 return Parent::aNodeId(node); |
|
74 } |
|
75 |
|
76 class BNode : public Node { |
|
77 friend class BpUGraphExtender; |
|
78 public: |
|
79 BNode() {} |
|
80 BNode(const Node& node) : Node(node) { |
|
81 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
|
82 typename Parent::NodeSetError()); |
|
83 } |
|
84 BNode(Invalid) : Node(INVALID) {} |
|
85 }; |
|
86 |
|
87 void first(BNode& node) const { |
|
88 Parent::firstBNode(static_cast<Node&>(node)); |
|
89 } |
|
90 void next(BNode& node) const { |
|
91 Parent::nextBNode(static_cast<Node&>(node)); |
|
92 } |
|
93 |
|
94 int id(const BNode& node) const { |
|
95 return Parent::aNodeId(node); |
|
96 } |
|
97 |
|
98 Node source(const UEdge& edge) const { |
|
99 return aNode(edge); |
|
100 } |
|
101 Node target(const UEdge& edge) const { |
|
102 return bNode(edge); |
|
103 } |
|
104 |
|
105 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
|
106 if (Parent::aNode(node)) { |
|
107 Parent::firstFromANode(edge, node); |
|
108 direction = true; |
|
109 } else { |
|
110 Parent::firstFromBNode(edge, node); |
|
111 direction = static_cast<UEdge&>(edge) == INVALID; |
|
112 } |
|
113 } |
|
114 void nextInc(UEdge& edge, bool& direction) const { |
|
115 if (direction) { |
|
116 Parent::nextFromANode(edge); |
|
117 } else { |
|
118 Parent::nextFromBNode(edge); |
|
119 if (edge == INVALID) direction = true; |
|
120 } |
|
121 } |
|
122 |
|
123 class Edge : public UEdge { |
|
124 friend class BpUGraphExtender; |
|
125 protected: |
|
126 bool forward; |
|
127 |
|
128 Edge(const UEdge& edge, bool _forward) |
|
129 : UEdge(edge), forward(_forward) {} |
|
130 |
|
131 public: |
|
132 Edge() {} |
|
133 Edge (Invalid) : UEdge(INVALID), forward(true) {} |
|
134 bool operator==(const Edge& i) const { |
|
135 return UEdge::operator==(i) && forward == i.forward; |
|
136 } |
|
137 bool operator!=(const Edge& i) const { |
|
138 return UEdge::operator!=(i) || forward != i.forward; |
|
139 } |
|
140 bool operator<(const Edge& i) const { |
|
141 return UEdge::operator<(i) || |
|
142 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); |
|
143 } |
|
144 }; |
|
145 |
|
146 void first(Edge& edge) const { |
|
147 Parent::first(static_cast<UEdge&>(edge)); |
|
148 edge.forward = true; |
|
149 } |
|
150 |
|
151 void next(Edge& edge) const { |
|
152 if (!edge.forward) { |
|
153 Parent::next(static_cast<UEdge&>(edge)); |
|
154 } |
|
155 edge.forward = !edge.forward; |
|
156 } |
|
157 |
|
158 void firstOut(Edge& edge, const Node& node) const { |
|
159 if (Parent::aNode(node)) { |
|
160 Parent::firstFromANode(edge, node); |
|
161 edge.forward = true; |
|
162 } else { |
|
163 Parent::firstFromBNode(edge, node); |
|
164 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
165 } |
|
166 } |
|
167 void nextOut(Edge& edge) const { |
|
168 if (edge.forward) { |
|
169 Parent::nextFromANode(edge); |
|
170 } else { |
|
171 Parent::nextFromBNode(edge); |
|
172 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
173 } |
|
174 } |
|
175 |
|
176 void firstIn(Edge& edge, const Node& node) const { |
|
177 if (Parent::bNode(node)) { |
|
178 Parent::firstFromBNode(edge, node); |
|
179 edge.forward = true; |
|
180 } else { |
|
181 Parent::firstFromANode(edge, node); |
|
182 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
183 } |
|
184 } |
|
185 void nextIn(Edge& edge) const { |
|
186 if (edge.forward) { |
|
187 Parent::nextFromBNode(edge); |
|
188 } else { |
|
189 Parent::nextFromANode(edge); |
|
190 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
191 } |
|
192 } |
|
193 |
|
194 Node source(const Edge& edge) const { |
|
195 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); |
|
196 } |
|
197 Node target(const Edge& edge) const { |
|
198 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); |
|
199 } |
|
200 |
|
201 int id(const Edge& edge) const { |
|
202 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + |
|
203 (edge.forward ? 0 : 1); |
|
204 } |
|
205 Edge edgeFromId(int id) const { |
|
206 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); |
|
207 } |
|
208 int maxEdgeId() const { |
|
209 return (Parent::maxUEdgeId(UEdge()) << 1) + 1; |
|
210 } |
|
211 |
|
212 bool direction(const Edge& edge) const { |
|
213 return edge.forward; |
|
214 } |
|
215 |
|
216 Edge direct(const UEdge& edge, bool direction) const { |
|
217 return Edge(edge, direction); |
|
218 } |
|
219 |
|
220 int edgeNum() const { |
|
221 return 2 * Parent::uEdgeNum(); |
|
222 } |
|
223 |
|
224 int uEdgeNum() const { |
|
225 return Parent::uEdgeNum(); |
|
226 } |
|
227 |
|
228 Node oppositeNode(const UEdge& edge, const Node& node) const { |
|
229 return source(edge) == node ? |
|
230 target(edge) : source(edge); |
|
231 } |
|
232 |
|
233 Edge direct(const UEdge& edge, const Node& node) const { |
|
234 return Edge(edge, node == Parent::source(edge)); |
|
235 } |
|
236 |
|
237 Edge oppositeEdge(const Edge& edge) const { |
|
238 return Parent::direct(edge, !Parent::direction(edge)); |
|
239 } |
|
240 |
|
241 |
|
242 int maxId(Node) const { |
|
243 return Parent::maxNodeId(); |
|
244 } |
|
245 int maxId(BNode) const { |
|
246 return Parent::maxBNodeId(); |
|
247 } |
|
248 int maxId(ANode) const { |
|
249 return Parent::maxANodeId(); |
|
250 } |
|
251 int maxId(Edge) const { |
|
252 return maxEdgeId(); |
|
253 } |
|
254 int maxId(UEdge) const { |
|
255 return Parent::maxUEdgeId(); |
|
256 } |
|
257 |
|
258 |
|
259 Node fromId(int id, Node) const { |
|
260 return Parent::nodeFromId(id); |
|
261 } |
|
262 ANode fromId(int id, ANode) const { |
|
263 return Parent::fromANodeId(id); |
|
264 } |
|
265 BNode fromId(int id, BNode) const { |
|
266 return Parent::fromBNodeId(id); |
|
267 } |
|
268 Edge fromId(int id, Edge) const { |
|
269 return Parent::edgeFromId(id); |
|
270 } |
|
271 UEdge fromId(int id, UEdge) const { |
|
272 return Parent::uEdgeFromId(id); |
|
273 } |
|
274 |
|
275 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier; |
|
276 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier; |
|
277 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier; |
|
278 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier; |
|
279 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier; |
|
280 |
|
281 protected: |
|
282 |
|
283 mutable ANodeNotifier anode_notifier; |
|
284 mutable BNodeNotifier bnode_notifier; |
|
285 mutable NodeNotifier node_notifier; |
|
286 mutable EdgeNotifier edge_notifier; |
|
287 mutable UEdgeNotifier uedge_notifier; |
|
288 |
|
289 public: |
|
290 |
|
291 NodeNotifier& getNotifier(Node) const { |
|
292 return node_notifier; |
|
293 } |
|
294 |
|
295 ANodeNotifier& getNotifier(ANode) const { |
|
296 return anode_notifier; |
|
297 } |
|
298 |
|
299 BNodeNotifier& getNotifier(BNode) const { |
|
300 return bnode_notifier; |
|
301 } |
|
302 |
|
303 EdgeNotifier& getNotifier(Edge) const { |
|
304 return edge_notifier; |
|
305 } |
|
306 |
|
307 UEdgeNotifier& getNotifier(UEdge) const { |
|
308 return uedge_notifier; |
|
309 } |
|
310 |
|
311 class NodeIt : public Node { |
|
312 const Graph* graph; |
|
313 public: |
|
314 |
|
315 NodeIt() { } |
|
316 |
|
317 NodeIt(Invalid i) : Node(INVALID) { } |
|
318 |
|
319 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
320 graph->first(static_cast<Node&>(*this)); |
|
321 } |
|
322 |
|
323 NodeIt(const Graph& _graph, const Node& node) |
|
324 : Node(node), graph(&_graph) { } |
|
325 |
|
326 NodeIt& operator++() { |
|
327 graph->next(*this); |
|
328 return *this; |
|
329 } |
|
330 |
|
331 }; |
|
332 |
|
333 class ANodeIt : public Node { |
|
334 friend class BpUGraphExtender; |
|
335 const Graph* graph; |
|
336 public: |
|
337 |
|
338 ANodeIt() { } |
|
339 |
|
340 ANodeIt(Invalid i) : Node(INVALID) { } |
|
341 |
|
342 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { |
|
343 graph->firstANode(static_cast<Node&>(*this)); |
|
344 } |
|
345 |
|
346 ANodeIt(const Graph& _graph, const Node& node) |
|
347 : Node(node), graph(&_graph) {} |
|
348 |
|
349 ANodeIt& operator++() { |
|
350 graph->nextANode(*this); |
|
351 return *this; |
|
352 } |
|
353 }; |
|
354 |
|
355 class BNodeIt : public Node { |
|
356 friend class BpUGraphExtender; |
|
357 const Graph* graph; |
|
358 public: |
|
359 |
|
360 BNodeIt() { } |
|
361 |
|
362 BNodeIt(Invalid i) : Node(INVALID) { } |
|
363 |
|
364 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { |
|
365 graph->firstBNode(static_cast<Node&>(*this)); |
|
366 } |
|
367 |
|
368 BNodeIt(const Graph& _graph, const Node& node) |
|
369 : Node(node), graph(&_graph) {} |
|
370 |
|
371 BNodeIt& operator++() { |
|
372 graph->nextBNode(*this); |
|
373 return *this; |
|
374 } |
|
375 }; |
|
376 |
|
377 class EdgeIt : public Edge { |
|
378 friend class BpUGraphExtender; |
|
379 const Graph* graph; |
|
380 public: |
|
381 |
|
382 EdgeIt() { } |
|
383 |
|
384 EdgeIt(Invalid i) : Edge(INVALID) { } |
|
385 |
|
386 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
387 graph->first(static_cast<Edge&>(*this)); |
|
388 } |
|
389 |
|
390 EdgeIt(const Graph& _graph, const Edge& edge) |
|
391 : Edge(edge), graph(&_graph) { } |
|
392 |
|
393 EdgeIt& operator++() { |
|
394 graph->next(*this); |
|
395 return *this; |
|
396 } |
|
397 |
|
398 }; |
|
399 |
|
400 class UEdgeIt : public UEdge { |
|
401 friend class BpUGraphExtender; |
|
402 const Graph* graph; |
|
403 public: |
|
404 |
|
405 UEdgeIt() { } |
|
406 |
|
407 UEdgeIt(Invalid i) : UEdge(INVALID) { } |
|
408 |
|
409 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
410 graph->first(static_cast<UEdge&>(*this)); |
|
411 } |
|
412 |
|
413 UEdgeIt(const Graph& _graph, const UEdge& edge) |
|
414 : UEdge(edge), graph(&_graph) { } |
|
415 |
|
416 UEdgeIt& operator++() { |
|
417 graph->next(*this); |
|
418 return *this; |
|
419 } |
|
420 }; |
|
421 |
|
422 class OutEdgeIt : public Edge { |
|
423 friend class BpUGraphExtender; |
|
424 const Graph* graph; |
|
425 public: |
|
426 |
|
427 OutEdgeIt() { } |
|
428 |
|
429 OutEdgeIt(Invalid i) : Edge(i) { } |
|
430 |
|
431 OutEdgeIt(const Graph& _graph, const Node& node) |
|
432 : graph(&_graph) { |
|
433 graph->firstOut(*this, node); |
|
434 } |
|
435 |
|
436 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
437 : Edge(edge), graph(&_graph) {} |
|
438 |
|
439 OutEdgeIt& operator++() { |
|
440 graph->nextOut(*this); |
|
441 return *this; |
|
442 } |
|
443 |
|
444 }; |
|
445 |
|
446 |
|
447 class InEdgeIt : public Edge { |
|
448 friend class BpUGraphExtender; |
|
449 const Graph* graph; |
|
450 public: |
|
451 |
|
452 InEdgeIt() { } |
|
453 |
|
454 InEdgeIt(Invalid i) : Edge(i) { } |
|
455 |
|
456 InEdgeIt(const Graph& _graph, const Node& node) |
|
457 : graph(&_graph) { |
|
458 graph->firstIn(*this, node); |
|
459 } |
|
460 |
|
461 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
462 Edge(edge), graph(&_graph) {} |
|
463 |
|
464 InEdgeIt& operator++() { |
|
465 graph->nextIn(*this); |
|
466 return *this; |
|
467 } |
|
468 |
|
469 }; |
|
470 |
|
471 /// \brief Base node of the iterator |
|
472 /// |
|
473 /// Returns the base node (ie. the source in this case) of the iterator |
|
474 Node baseNode(const OutEdgeIt &e) const { |
|
475 return Parent::source((Edge&)e); |
|
476 } |
|
477 /// \brief Running node of the iterator |
|
478 /// |
|
479 /// Returns the running node (ie. the target in this case) of the |
|
480 /// iterator |
|
481 Node runningNode(const OutEdgeIt &e) const { |
|
482 return Parent::target((Edge&)e); |
|
483 } |
|
484 |
|
485 /// \brief Base node of the iterator |
|
486 /// |
|
487 /// Returns the base node (ie. the target in this case) of the iterator |
|
488 Node baseNode(const InEdgeIt &e) const { |
|
489 return Parent::target((Edge&)e); |
|
490 } |
|
491 /// \brief Running node of the iterator |
|
492 /// |
|
493 /// Returns the running node (ie. the source in this case) of the |
|
494 /// iterator |
|
495 Node runningNode(const InEdgeIt &e) const { |
|
496 return Parent::source((Edge&)e); |
|
497 } |
|
498 |
|
499 class IncEdgeIt : public Parent::UEdge { |
|
500 friend class BpUGraphExtender; |
|
501 const Graph* graph; |
|
502 bool direction; |
|
503 public: |
|
504 |
|
505 IncEdgeIt() { } |
|
506 |
|
507 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } |
|
508 |
|
509 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { |
|
510 graph->firstInc(*this, direction, n); |
|
511 } |
|
512 |
|
513 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) |
|
514 : graph(&_graph), UEdge(ue) { |
|
515 direction = (graph->source(ue) == n); |
|
516 } |
|
517 |
|
518 IncEdgeIt& operator++() { |
|
519 graph->nextInc(*this, direction); |
|
520 return *this; |
|
521 } |
|
522 }; |
|
523 |
|
524 |
|
525 /// Base node of the iterator |
|
526 /// |
|
527 /// Returns the base node of the iterator |
|
528 Node baseNode(const IncEdgeIt &e) const { |
|
529 return e.direction ? source(e) : target(e); |
|
530 } |
|
531 |
|
532 /// Running node of the iterator |
|
533 /// |
|
534 /// Returns the running node of the iterator |
|
535 Node runningNode(const IncEdgeIt &e) const { |
|
536 return e.direction ? target(e) : source(e); |
|
537 } |
|
538 |
|
539 template <typename _Value> |
|
540 class ANodeMap |
|
541 : public MapExtender<DefaultMap<Graph, ANode, _Value> > { |
|
542 public: |
|
543 typedef BpUGraphExtender Graph; |
|
544 typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent; |
|
545 |
|
546 ANodeMap(const Graph& graph) |
|
547 : Parent(graph) {} |
|
548 ANodeMap(const Graph& graph, const _Value& value) |
|
549 : Parent(graph, value) {} |
|
550 |
|
551 ANodeMap& operator=(const ANodeMap& cmap) { |
|
552 return operator=<ANodeMap>(cmap); |
|
553 } |
|
554 |
|
555 template <typename CMap> |
|
556 ANodeMap& operator=(const CMap& cmap) { |
|
557 Parent::operator=(cmap); |
|
558 return *this; |
|
559 } |
|
560 |
|
561 }; |
|
562 |
|
563 template <typename _Value> |
|
564 class BNodeMap |
|
565 : public MapExtender<DefaultMap<Graph, BNode, _Value> > { |
|
566 public: |
|
567 typedef BpUGraphExtender Graph; |
|
568 typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent; |
|
569 |
|
570 BNodeMap(const Graph& graph) |
|
571 : Parent(graph) {} |
|
572 BNodeMap(const Graph& graph, const _Value& value) |
|
573 : Parent(graph, value) {} |
|
574 |
|
575 BNodeMap& operator=(const BNodeMap& cmap) { |
|
576 return operator=<BNodeMap>(cmap); |
|
577 } |
|
578 |
|
579 template <typename CMap> |
|
580 BNodeMap& operator=(const CMap& cmap) { |
|
581 Parent::operator=(cmap); |
|
582 return *this; |
|
583 } |
|
584 |
|
585 }; |
|
586 |
|
587 public: |
|
588 |
|
589 template <typename _Value> |
|
590 class NodeMap { |
|
591 public: |
|
592 typedef BpUGraphExtender Graph; |
|
593 |
|
594 typedef Node Key; |
|
595 typedef _Value Value; |
|
596 |
|
597 /// The reference type of the map; |
|
598 typedef typename ANodeMap<_Value>::Reference Reference; |
|
599 /// The const reference type of the map; |
|
600 typedef typename ANodeMap<_Value>::ConstReference ConstReference; |
|
601 |
|
602 typedef True ReferenceMapTag; |
|
603 |
|
604 NodeMap(const Graph& _graph) |
|
605 : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} |
|
606 NodeMap(const Graph& _graph, const _Value& _value) |
|
607 : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} |
|
608 |
|
609 NodeMap& operator=(const NodeMap& cmap) { |
|
610 return operator=<NodeMap>(cmap); |
|
611 } |
|
612 |
|
613 template <typename CMap> |
|
614 NodeMap& operator=(const CMap& cmap) { |
|
615 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); |
|
616 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
|
617 Edge it; |
|
618 for (graph.first(it); it != INVALID; graph.next(it)) { |
|
619 Parent::set(it, cmap[it]); |
|
620 } |
|
621 return *this; |
|
622 } |
|
623 |
|
624 ConstReference operator[](const Key& node) const { |
|
625 if (Parent::aNode(node)) { |
|
626 return aNodeMap[node]; |
|
627 } else { |
|
628 return bNodeMap[node]; |
|
629 } |
|
630 } |
|
631 |
|
632 Reference operator[](const Key& node) { |
|
633 if (Parent::aNode(node)) { |
|
634 return aNodeMap[node]; |
|
635 } else { |
|
636 return bNodeMap[node]; |
|
637 } |
|
638 } |
|
639 |
|
640 void set(const Key& node, const Value& value) { |
|
641 if (Parent::aNode(node)) { |
|
642 aNodeMap.set(node, value); |
|
643 } else { |
|
644 bNodeMap.set(node, value); |
|
645 } |
|
646 } |
|
647 |
|
648 class MapIt : public NodeIt { |
|
649 public: |
|
650 |
|
651 typedef NodeIt Parent; |
|
652 |
|
653 explicit MapIt(NodeMap& _map) |
|
654 : Parent(_map.graph), map(_map) {} |
|
655 |
|
656 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { |
|
657 return map[*this]; |
|
658 } |
|
659 |
|
660 typename MapTraits<NodeMap>::ReturnValue operator*() { |
|
661 return map[*this]; |
|
662 } |
|
663 |
|
664 void set(const Value& value) { |
|
665 map.set(*this, value); |
|
666 } |
|
667 |
|
668 private: |
|
669 NodeMap& map; |
|
670 }; |
|
671 |
|
672 class ConstMapIt : public NodeIt { |
|
673 public: |
|
674 |
|
675 typedef NodeIt Parent; |
|
676 |
|
677 explicit ConstMapIt(const NodeMap& _map) |
|
678 : Parent(_map.graph), map(_map) {} |
|
679 |
|
680 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { |
|
681 return map[*this]; |
|
682 } |
|
683 |
|
684 private: |
|
685 const NodeMap& map; |
|
686 }; |
|
687 |
|
688 class ItemIt : public NodeIt { |
|
689 public: |
|
690 |
|
691 typedef NodeIt Parent; |
|
692 |
|
693 explicit ItemIt(const NodeMap& _map) |
|
694 : Parent(_map.graph) {} |
|
695 |
|
696 }; |
|
697 |
|
698 private: |
|
699 const Graph& graph; |
|
700 ANodeMap<_Value> aNodeMap; |
|
701 BNodeMap<_Value> bNodeMap; |
|
702 }; |
|
703 |
|
704 |
|
705 template <typename _Value> |
|
706 class EdgeMap |
|
707 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
|
708 public: |
|
709 typedef BpUGraphExtender Graph; |
|
710 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
|
711 |
|
712 EdgeMap(const Graph& graph) |
|
713 : Parent(graph) {} |
|
714 EdgeMap(const Graph& graph, const _Value& value) |
|
715 : Parent(graph, value) {} |
|
716 |
|
717 EdgeMap& operator=(const EdgeMap& cmap) { |
|
718 return operator=<EdgeMap>(cmap); |
|
719 } |
|
720 |
|
721 template <typename CMap> |
|
722 EdgeMap& operator=(const CMap& cmap) { |
|
723 Parent::operator=(cmap); |
|
724 return *this; |
|
725 } |
|
726 }; |
|
727 |
|
728 template <typename _Value> |
|
729 class UEdgeMap |
|
730 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { |
|
731 public: |
|
732 typedef BpUGraphExtender Graph; |
|
733 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
|
734 |
|
735 UEdgeMap(const Graph& graph) |
|
736 : Parent(graph) {} |
|
737 UEdgeMap(const Graph& graph, const _Value& value) |
|
738 : Parent(graph, value) {} |
|
739 |
|
740 UEdgeMap& operator=(const UEdgeMap& cmap) { |
|
741 return operator=<UEdgeMap>(cmap); |
|
742 } |
|
743 |
|
744 template <typename CMap> |
|
745 UEdgeMap& operator=(const CMap& cmap) { |
|
746 Parent::operator=(cmap); |
|
747 return *this; |
|
748 } |
|
749 }; |
|
750 |
|
751 |
|
752 Node addANode() { |
|
753 Node node = Parent::addANode(); |
|
754 getNotifier(ANode()).add(node); |
|
755 getNotifier(Node()).add(node); |
|
756 return node; |
|
757 } |
|
758 |
|
759 Node addBNode() { |
|
760 Node node = Parent::addBNode(); |
|
761 getNotifier(BNode()).add(node); |
|
762 getNotifier(Node()).add(node); |
|
763 return node; |
|
764 } |
|
765 |
|
766 UEdge addEdge(const Node& source, const Node& target) { |
|
767 UEdge uedge = Parent::addEdge(source, target); |
|
768 getNotifier(UEdge()).add(uedge); |
|
769 |
|
770 std::vector<Edge> edges; |
|
771 edges.push_back(direct(uedge, true)); |
|
772 edges.push_back(direct(uedge, false)); |
|
773 getNotifier(Edge()).add(edges); |
|
774 |
|
775 return uedge; |
|
776 } |
|
777 |
|
778 void clear() { |
|
779 getNotifier(Edge()).clear(); |
|
780 getNotifier(UEdge()).clear(); |
|
781 getNotifier(Node()).clear(); |
|
782 getNotifier(BNode()).clear(); |
|
783 getNotifier(ANode()).clear(); |
|
784 Parent::clear(); |
|
785 } |
|
786 |
|
787 void erase(const Node& node) { |
|
788 UEdge uedge; |
|
789 if (Parent::aNode(node)) { |
|
790 Parent::firstFromANode(uedge, node); |
|
791 while (uedge != INVALID) { |
|
792 erase(uedge); |
|
793 Parent::firstFromANode(uedge, node); |
|
794 } |
|
795 } else { |
|
796 Parent::firstFromBNode(uedge, node); |
|
797 while (uedge != INVALID) { |
|
798 erase(uedge); |
|
799 Parent::firstFromBNode(uedge, node); |
|
800 } |
|
801 } |
|
802 |
|
803 getNotifier(Node()).erase(node); |
|
804 Parent::erase(node); |
|
805 } |
|
806 |
|
807 void erase(const UEdge& uedge) { |
|
808 std::vector<Edge> edges; |
|
809 edges.push_back(direct(uedge, true)); |
|
810 edges.push_back(direct(uedge, false)); |
|
811 getNotifier(Edge()).erase(edges); |
|
812 getNotifier(UEdge()).erase(uedge); |
|
813 Parent::erase(uedge); |
|
814 } |
|
815 |
|
816 |
|
817 BpUGraphExtender() { |
|
818 anode_notifier.setContainer(*this); |
|
819 bnode_notifier.setContainer(*this); |
|
820 node_notifier.setContainer(*this); |
|
821 edge_notifier.setContainer(*this); |
|
822 uedge_notifier.setContainer(*this); |
|
823 } |
|
824 |
|
825 ~BpUGraphExtender() { |
|
826 uedge_notifier.clear(); |
|
827 edge_notifier.clear(); |
|
828 node_notifier.clear(); |
|
829 anode_notifier.clear(); |
|
830 bnode_notifier.clear(); |
|
831 } |
|
832 |
|
833 |
|
834 }; |
|
835 |
|
836 } |
|
837 |
|
838 #endif |