236 /// the NodeMap. In this case the value for each item |
240 /// the NodeMap. In this case the value for each item |
237 /// is assigned by the value of the given ReadMap. |
241 /// is assigned by the value of the given ReadMap. |
238 template <typename CMap> |
242 template <typename CMap> |
239 NodeMap& operator=(const CMap& cmap) { |
243 NodeMap& operator=(const CMap& cmap) { |
240 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); |
244 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); |
241 const typename Parent::Graph* graph = Parent::getGraph(); |
245 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
242 Node it; |
246 Node it; |
243 for (graph->first(it); it != INVALID; graph->next(it)) { |
247 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
244 Parent::set(it, cmap[it]); |
248 Parent::set(it, cmap[it]); |
245 } |
249 } |
246 return *this; |
250 return *this; |
247 } |
251 } |
248 |
252 |
249 }; |
253 }; |
250 |
254 |
251 template <typename _Value> |
255 template <typename _Value> |
252 class EdgeMap |
256 class EdgeMap |
253 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { |
257 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
254 public: |
258 public: |
255 typedef GraphExtender Graph; |
259 typedef GraphExtender Graph; |
256 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
260 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
257 |
261 |
258 EdgeMap(const Graph& _g) |
262 EdgeMap(const Graph& graph) |
259 : Parent(_g) {} |
263 : Parent(graph) {} |
260 EdgeMap(const Graph& _g, const _Value& _v) |
264 EdgeMap(const Graph& graph, const _Value& value) |
261 : Parent(_g, _v) {} |
265 : Parent(graph, value) {} |
262 |
266 |
263 EdgeMap& operator=(const EdgeMap& cmap) { |
267 EdgeMap& operator=(const EdgeMap& cmap) { |
264 return operator=<EdgeMap>(cmap); |
268 return operator=<EdgeMap>(cmap); |
265 } |
269 } |
266 |
270 |
267 template <typename CMap> |
271 template <typename CMap> |
268 EdgeMap& operator=(const CMap& cmap) { |
272 EdgeMap& operator=(const CMap& cmap) { |
269 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); |
273 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); |
270 const typename Parent::Graph* graph = Parent::getGraph(); |
274 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
271 Edge it; |
275 Edge it; |
272 for (graph->first(it); it != INVALID; graph->next(it)) { |
276 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
273 Parent::set(it, cmap[it]); |
277 Parent::set(it, cmap[it]); |
274 } |
278 } |
275 return *this; |
279 return *this; |
276 } |
280 } |
277 }; |
281 }; |
317 void erase(const Edge& edge) { |
321 void erase(const Edge& edge) { |
318 getNotifier(Edge()).erase(edge); |
322 getNotifier(Edge()).erase(edge); |
319 Parent::erase(edge); |
323 Parent::erase(edge); |
320 } |
324 } |
321 |
325 |
|
326 GraphExtender() { |
|
327 node_notifier.setContainer(*this); |
|
328 edge_notifier.setContainer(*this); |
|
329 } |
|
330 |
322 |
331 |
323 ~GraphExtender() { |
332 ~GraphExtender() { |
324 getNotifier(Edge()).clear(); |
333 edge_notifier.clear(); |
325 getNotifier(Node()).clear(); |
334 node_notifier.clear(); |
326 } |
335 } |
327 }; |
336 }; |
328 |
|
329 /// \ingroup graphbits |
|
330 /// |
|
331 /// \brief BaseExtender for the UGraphs |
|
332 template <typename Base> |
|
333 class UGraphBaseExtender : public Base { |
|
334 |
|
335 public: |
|
336 |
|
337 typedef Base Parent; |
|
338 typedef typename Parent::Edge UEdge; |
|
339 typedef typename Parent::Node Node; |
|
340 |
|
341 typedef True UndirectedTag; |
|
342 |
|
343 class Edge : public UEdge { |
|
344 friend class UGraphBaseExtender; |
|
345 |
|
346 protected: |
|
347 bool forward; |
|
348 |
|
349 Edge(const UEdge &ue, bool _forward) : |
|
350 UEdge(ue), forward(_forward) {} |
|
351 |
|
352 public: |
|
353 Edge() {} |
|
354 |
|
355 /// Invalid edge constructor |
|
356 Edge(Invalid i) : UEdge(i), forward(true) {} |
|
357 |
|
358 bool operator==(const Edge &that) const { |
|
359 return forward==that.forward && UEdge(*this)==UEdge(that); |
|
360 } |
|
361 bool operator!=(const Edge &that) const { |
|
362 return forward!=that.forward || UEdge(*this)!=UEdge(that); |
|
363 } |
|
364 bool operator<(const Edge &that) const { |
|
365 return forward<that.forward || |
|
366 (!(that.forward<forward) && UEdge(*this)<UEdge(that)); |
|
367 } |
|
368 }; |
|
369 |
|
370 |
|
371 |
|
372 using Parent::source; |
|
373 |
|
374 /// Source of the given Edge. |
|
375 Node source(const Edge &e) const { |
|
376 return e.forward ? Parent::source(e) : Parent::target(e); |
|
377 } |
|
378 |
|
379 using Parent::target; |
|
380 |
|
381 /// Target of the given Edge. |
|
382 Node target(const Edge &e) const { |
|
383 return e.forward ? Parent::target(e) : Parent::source(e); |
|
384 } |
|
385 |
|
386 /// \brief Directed edge from an undirected edge. |
|
387 /// |
|
388 /// Returns a directed edge corresponding to the specified UEdge. |
|
389 /// If the given bool is true the given undirected edge and the |
|
390 /// returned edge have the same source node. |
|
391 static Edge direct(const UEdge &ue, bool d) { |
|
392 return Edge(ue, d); |
|
393 } |
|
394 |
|
395 /// Returns whether the given directed edge is same orientation as the |
|
396 /// corresponding undirected edge. |
|
397 /// |
|
398 /// \todo reference to the corresponding point of the undirected graph |
|
399 /// concept. "What does the direction of an undirected edge mean?" |
|
400 static bool direction(const Edge &e) { return e.forward; } |
|
401 |
|
402 |
|
403 using Parent::first; |
|
404 using Parent::next; |
|
405 |
|
406 void first(Edge &e) const { |
|
407 Parent::first(e); |
|
408 e.forward=true; |
|
409 } |
|
410 |
|
411 void next(Edge &e) const { |
|
412 if( e.forward ) { |
|
413 e.forward = false; |
|
414 } |
|
415 else { |
|
416 Parent::next(e); |
|
417 e.forward = true; |
|
418 } |
|
419 } |
|
420 |
|
421 void firstOut(Edge &e, const Node &n) const { |
|
422 Parent::firstIn(e,n); |
|
423 if( UEdge(e) != INVALID ) { |
|
424 e.forward = false; |
|
425 } |
|
426 else { |
|
427 Parent::firstOut(e,n); |
|
428 e.forward = true; |
|
429 } |
|
430 } |
|
431 void nextOut(Edge &e) const { |
|
432 if( ! e.forward ) { |
|
433 Node n = Parent::target(e); |
|
434 Parent::nextIn(e); |
|
435 if( UEdge(e) == INVALID ) { |
|
436 Parent::firstOut(e, n); |
|
437 e.forward = true; |
|
438 } |
|
439 } |
|
440 else { |
|
441 Parent::nextOut(e); |
|
442 } |
|
443 } |
|
444 |
|
445 void firstIn(Edge &e, const Node &n) const { |
|
446 Parent::firstOut(e,n); |
|
447 if( UEdge(e) != INVALID ) { |
|
448 e.forward = false; |
|
449 } |
|
450 else { |
|
451 Parent::firstIn(e,n); |
|
452 e.forward = true; |
|
453 } |
|
454 } |
|
455 void nextIn(Edge &e) const { |
|
456 if( ! e.forward ) { |
|
457 Node n = Parent::source(e); |
|
458 Parent::nextOut(e); |
|
459 if( UEdge(e) == INVALID ) { |
|
460 Parent::firstIn(e, n); |
|
461 e.forward = true; |
|
462 } |
|
463 } |
|
464 else { |
|
465 Parent::nextIn(e); |
|
466 } |
|
467 } |
|
468 |
|
469 void firstInc(UEdge &e, bool &d, const Node &n) const { |
|
470 d = true; |
|
471 Parent::firstOut(e, n); |
|
472 if (e != INVALID) return; |
|
473 d = false; |
|
474 Parent::firstIn(e, n); |
|
475 } |
|
476 |
|
477 void nextInc(UEdge &e, bool &d) const { |
|
478 if (d) { |
|
479 Node s = Parent::source(e); |
|
480 Parent::nextOut(e); |
|
481 if (e != INVALID) return; |
|
482 d = false; |
|
483 Parent::firstIn(e, s); |
|
484 } else { |
|
485 Parent::nextIn(e); |
|
486 } |
|
487 } |
|
488 |
|
489 Node nodeFromId(int id) const { |
|
490 return Parent::nodeFromId(id); |
|
491 } |
|
492 |
|
493 Edge edgeFromId(int id) const { |
|
494 return direct(Parent::edgeFromId(id >> 1), bool(id & 1)); |
|
495 } |
|
496 |
|
497 UEdge uEdgeFromId(int id) const { |
|
498 return Parent::edgeFromId(id >> 1); |
|
499 } |
|
500 |
|
501 int id(const Node &n) const { |
|
502 return Parent::id(n); |
|
503 } |
|
504 |
|
505 int id(const UEdge &e) const { |
|
506 return Parent::id(e); |
|
507 } |
|
508 |
|
509 int id(const Edge &e) const { |
|
510 return 2 * Parent::id(e) + int(e.forward); |
|
511 } |
|
512 |
|
513 int maxNodeId() const { |
|
514 return Parent::maxNodeId(); |
|
515 } |
|
516 |
|
517 int maxEdgeId() const { |
|
518 return 2 * Parent::maxEdgeId() + 1; |
|
519 } |
|
520 |
|
521 int maxUEdgeId() const { |
|
522 return Parent::maxEdgeId(); |
|
523 } |
|
524 |
|
525 |
|
526 int edgeNum() const { |
|
527 return 2 * Parent::edgeNum(); |
|
528 } |
|
529 |
|
530 int uEdgeNum() const { |
|
531 return Parent::edgeNum(); |
|
532 } |
|
533 |
|
534 Edge findEdge(Node source, Node target, Edge prev) const { |
|
535 if (prev == INVALID) { |
|
536 UEdge edge = Parent::findEdge(source, target); |
|
537 if (edge != INVALID) return direct(edge, true); |
|
538 edge = Parent::findEdge(target, source); |
|
539 if (edge != INVALID) return direct(edge, false); |
|
540 } else if (direction(prev)) { |
|
541 UEdge edge = Parent::findEdge(source, target, prev); |
|
542 if (edge != INVALID) return direct(edge, true); |
|
543 edge = Parent::findEdge(target, source); |
|
544 if (edge != INVALID) return direct(edge, false); |
|
545 } else { |
|
546 UEdge edge = Parent::findEdge(target, source, prev); |
|
547 if (edge != INVALID) return direct(edge, false); |
|
548 } |
|
549 return INVALID; |
|
550 } |
|
551 |
|
552 UEdge findUEdge(Node source, Node target, UEdge prev) const { |
|
553 if (prev == INVALID) { |
|
554 UEdge edge = Parent::findEdge(source, target); |
|
555 if (edge != INVALID) return edge; |
|
556 edge = Parent::findEdge(target, source); |
|
557 if (edge != INVALID) return edge; |
|
558 } else if (Parent::source(prev) == source) { |
|
559 UEdge edge = Parent::findEdge(source, target, prev); |
|
560 if (edge != INVALID) return edge; |
|
561 edge = Parent::findEdge(target, source); |
|
562 if (edge != INVALID) return edge; |
|
563 } else { |
|
564 UEdge edge = Parent::findEdge(target, source, prev); |
|
565 if (edge != INVALID) return edge; |
|
566 } |
|
567 return INVALID; |
|
568 } |
|
569 }; |
|
570 |
|
571 |
337 |
572 /// \ingroup graphbits |
338 /// \ingroup graphbits |
573 /// |
339 /// |
574 /// \brief Extender for the UGraphs |
340 /// \brief Extender for the UGraphs |
575 template <typename Base> |
341 template <typename Base> |
864 /// the NodeMap. In this case the value for each item |
630 /// the NodeMap. In this case the value for each item |
865 /// is assigned by the value of the given ReadMap. |
631 /// is assigned by the value of the given ReadMap. |
866 template <typename CMap> |
632 template <typename CMap> |
867 NodeMap& operator=(const CMap& cmap) { |
633 NodeMap& operator=(const CMap& cmap) { |
868 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); |
634 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); |
869 const typename Parent::Graph* graph = Parent::getGraph(); |
635 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
870 Node it; |
636 Node it; |
871 for (graph->first(it); it != INVALID; graph->next(it)) { |
637 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
872 Parent::set(it, cmap[it]); |
638 Parent::set(it, cmap[it]); |
873 } |
639 } |
874 return *this; |
640 return *this; |
875 } |
641 } |
876 |
642 |
877 }; |
643 }; |
878 |
644 |
879 template <typename _Value> |
645 template <typename _Value> |
880 class EdgeMap |
646 class EdgeMap |
881 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { |
647 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
882 public: |
648 public: |
883 typedef UGraphExtender Graph; |
649 typedef UGraphExtender Graph; |
884 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
650 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
885 |
651 |
886 EdgeMap(const Graph& _g) |
652 EdgeMap(const Graph& graph) |
887 : Parent(_g) {} |
653 : Parent(graph) {} |
888 EdgeMap(const Graph& _g, const _Value& _v) |
654 EdgeMap(const Graph& graph, const _Value& value) |
889 : Parent(_g, _v) {} |
655 : Parent(graph, value) {} |
890 |
656 |
891 EdgeMap& operator=(const EdgeMap& cmap) { |
657 EdgeMap& operator=(const EdgeMap& cmap) { |
892 return operator=<EdgeMap>(cmap); |
658 return operator=<EdgeMap>(cmap); |
893 } |
659 } |
894 |
660 |
895 template <typename CMap> |
661 template <typename CMap> |
896 EdgeMap& operator=(const CMap& cmap) { |
662 EdgeMap& operator=(const CMap& cmap) { |
897 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); |
663 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); |
898 const typename Parent::Graph* graph = Parent::getGraph(); |
664 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
899 Edge it; |
665 Edge it; |
900 for (graph->first(it); it != INVALID; graph->next(it)) { |
666 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
901 Parent::set(it, cmap[it]); |
667 Parent::set(it, cmap[it]); |
902 } |
668 } |
903 return *this; |
669 return *this; |
904 } |
670 } |
905 }; |
671 }; |
906 |
672 |
907 |
673 |
908 template <typename _Value> |
674 template <typename _Value> |
909 class UEdgeMap |
675 class UEdgeMap |
910 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { |
676 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { |
911 public: |
677 public: |
912 typedef UGraphExtender Graph; |
678 typedef UGraphExtender Graph; |
913 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
679 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
914 |
680 |
915 UEdgeMap(const Graph& _g) |
681 UEdgeMap(const Graph& graph) |
916 : Parent(_g) {} |
682 : Parent(graph) {} |
917 UEdgeMap(const Graph& _g, const _Value& _v) |
683 UEdgeMap(const Graph& graph, const _Value& value) |
918 : Parent(_g, _v) {} |
684 : Parent(graph, value) {} |
919 |
685 |
920 UEdgeMap& operator=(const UEdgeMap& cmap) { |
686 UEdgeMap& operator=(const UEdgeMap& cmap) { |
921 return operator=<UEdgeMap>(cmap); |
687 return operator=<UEdgeMap>(cmap); |
922 } |
688 } |
923 |
689 |
924 template <typename CMap> |
690 template <typename CMap> |
925 UEdgeMap& operator=(const CMap& cmap) { |
691 UEdgeMap& operator=(const CMap& cmap) { |
926 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); |
692 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); |
927 const typename Parent::Graph* graph = Parent::getGraph(); |
693 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
928 UEdge it; |
694 Edge it; |
929 for (graph->first(it); it != INVALID; graph->next(it)) { |
695 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
930 Parent::set(it, cmap[it]); |
696 Parent::set(it, cmap[it]); |
931 } |
697 } |
932 return *this; |
698 return *this; |
933 } |
699 } |
934 }; |
700 }; |
979 getNotifier(Edge()).erase(Parent::direct(uedge, false)); |
745 getNotifier(Edge()).erase(Parent::direct(uedge, false)); |
980 getNotifier(UEdge()).erase(uedge); |
746 getNotifier(UEdge()).erase(uedge); |
981 Parent::erase(uedge); |
747 Parent::erase(uedge); |
982 } |
748 } |
983 |
749 |
|
750 UGraphExtender() { |
|
751 node_notifier.setContainer(*this); |
|
752 edge_notifier.setContainer(*this); |
|
753 uedge_notifier.setContainer(*this); |
|
754 } |
|
755 |
984 ~UGraphExtender() { |
756 ~UGraphExtender() { |
985 getNotifier(Edge()).clear(); |
757 uedge_notifier.clear(); |
986 getNotifier(UEdge()).clear(); |
758 edge_notifier.clear(); |
987 getNotifier(Node()).clear(); |
759 node_notifier.clear(); |
988 } |
760 } |
989 |
761 |
990 }; |
|
991 |
|
992 |
|
993 /// \ingroup graphbits |
|
994 /// |
|
995 /// \brief BaseExtender for the BpUGraphs |
|
996 template <typename Base> |
|
997 class BpUGraphBaseExtender : public Base { |
|
998 public: |
|
999 typedef Base Parent; |
|
1000 typedef BpUGraphBaseExtender Graph; |
|
1001 |
|
1002 typedef typename Parent::Node Node; |
|
1003 typedef typename Parent::Edge UEdge; |
|
1004 |
|
1005 |
|
1006 using Parent::first; |
|
1007 using Parent::next; |
|
1008 |
|
1009 using Parent::id; |
|
1010 |
|
1011 class ANode : public Node { |
|
1012 friend class BpUGraphBaseExtender; |
|
1013 public: |
|
1014 ANode() {} |
|
1015 ANode(const Node& node) : Node(node) { |
|
1016 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
|
1017 typename Parent::NodeSetError()); |
|
1018 } |
|
1019 ANode(Invalid) : Node(INVALID) {} |
|
1020 }; |
|
1021 |
|
1022 void first(ANode& node) const { |
|
1023 Parent::firstANode(static_cast<Node&>(node)); |
|
1024 } |
|
1025 void next(ANode& node) const { |
|
1026 Parent::nextANode(static_cast<Node&>(node)); |
|
1027 } |
|
1028 |
|
1029 int id(const ANode& node) const { |
|
1030 return Parent::aNodeId(node); |
|
1031 } |
|
1032 |
|
1033 class BNode : public Node { |
|
1034 friend class BpUGraphBaseExtender; |
|
1035 public: |
|
1036 BNode() {} |
|
1037 BNode(const Node& node) : Node(node) { |
|
1038 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
|
1039 typename Parent::NodeSetError()); |
|
1040 } |
|
1041 BNode(Invalid) : Node(INVALID) {} |
|
1042 }; |
|
1043 |
|
1044 void first(BNode& node) const { |
|
1045 Parent::firstBNode(static_cast<Node&>(node)); |
|
1046 } |
|
1047 void next(BNode& node) const { |
|
1048 Parent::nextBNode(static_cast<Node&>(node)); |
|
1049 } |
|
1050 |
|
1051 int id(const BNode& node) const { |
|
1052 return Parent::aNodeId(node); |
|
1053 } |
|
1054 |
|
1055 Node source(const UEdge& edge) const { |
|
1056 return aNode(edge); |
|
1057 } |
|
1058 Node target(const UEdge& edge) const { |
|
1059 return bNode(edge); |
|
1060 } |
|
1061 |
|
1062 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
|
1063 if (Parent::aNode(node)) { |
|
1064 Parent::firstOut(edge, node); |
|
1065 direction = true; |
|
1066 } else { |
|
1067 Parent::firstIn(edge, node); |
|
1068 direction = static_cast<UEdge&>(edge) == INVALID; |
|
1069 } |
|
1070 } |
|
1071 void nextInc(UEdge& edge, bool& direction) const { |
|
1072 if (direction) { |
|
1073 Parent::nextOut(edge); |
|
1074 } else { |
|
1075 Parent::nextIn(edge); |
|
1076 if (edge == INVALID) direction = true; |
|
1077 } |
|
1078 } |
|
1079 |
|
1080 int maxUEdgeId() const { |
|
1081 return Parent::maxEdgeId(); |
|
1082 } |
|
1083 |
|
1084 UEdge uEdgeFromId(int id) const { |
|
1085 return Parent::edgeFromId(id); |
|
1086 } |
|
1087 |
|
1088 class Edge : public UEdge { |
|
1089 friend class BpUGraphBaseExtender; |
|
1090 protected: |
|
1091 bool forward; |
|
1092 |
|
1093 Edge(const UEdge& edge, bool _forward) |
|
1094 : UEdge(edge), forward(_forward) {} |
|
1095 |
|
1096 public: |
|
1097 Edge() {} |
|
1098 Edge (Invalid) : UEdge(INVALID), forward(true) {} |
|
1099 bool operator==(const Edge& i) const { |
|
1100 return UEdge::operator==(i) && forward == i.forward; |
|
1101 } |
|
1102 bool operator!=(const Edge& i) const { |
|
1103 return UEdge::operator!=(i) || forward != i.forward; |
|
1104 } |
|
1105 bool operator<(const Edge& i) const { |
|
1106 return UEdge::operator<(i) || |
|
1107 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); |
|
1108 } |
|
1109 }; |
|
1110 |
|
1111 void first(Edge& edge) const { |
|
1112 Parent::first(static_cast<UEdge&>(edge)); |
|
1113 edge.forward = true; |
|
1114 } |
|
1115 |
|
1116 void next(Edge& edge) const { |
|
1117 if (!edge.forward) { |
|
1118 Parent::next(static_cast<UEdge&>(edge)); |
|
1119 } |
|
1120 edge.forward = !edge.forward; |
|
1121 } |
|
1122 |
|
1123 void firstOut(Edge& edge, const Node& node) const { |
|
1124 if (Parent::aNode(node)) { |
|
1125 Parent::firstOut(edge, node); |
|
1126 edge.forward = true; |
|
1127 } else { |
|
1128 Parent::firstIn(edge, node); |
|
1129 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
1130 } |
|
1131 } |
|
1132 void nextOut(Edge& edge) const { |
|
1133 if (edge.forward) { |
|
1134 Parent::nextOut(edge); |
|
1135 } else { |
|
1136 Parent::nextIn(edge); |
|
1137 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
1138 } |
|
1139 } |
|
1140 |
|
1141 void firstIn(Edge& edge, const Node& node) const { |
|
1142 if (Parent::bNode(node)) { |
|
1143 Parent::firstIn(edge, node); |
|
1144 edge.forward = true; |
|
1145 } else { |
|
1146 Parent::firstOut(edge, node); |
|
1147 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
1148 } |
|
1149 } |
|
1150 void nextIn(Edge& edge) const { |
|
1151 if (edge.forward) { |
|
1152 Parent::nextIn(edge); |
|
1153 } else { |
|
1154 Parent::nextOut(edge); |
|
1155 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
1156 } |
|
1157 } |
|
1158 |
|
1159 Node source(const Edge& edge) const { |
|
1160 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); |
|
1161 } |
|
1162 Node target(const Edge& edge) const { |
|
1163 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); |
|
1164 } |
|
1165 |
|
1166 int id(const Edge& edge) const { |
|
1167 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); |
|
1168 } |
|
1169 Edge edgeFromId(int id) const { |
|
1170 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); |
|
1171 } |
|
1172 int maxEdgeId() const { |
|
1173 return (Parent::maxId(UEdge()) << 1) + 1; |
|
1174 } |
|
1175 |
|
1176 bool direction(const Edge& edge) const { |
|
1177 return edge.forward; |
|
1178 } |
|
1179 |
|
1180 Edge direct(const UEdge& edge, bool direction) const { |
|
1181 return Edge(edge, direction); |
|
1182 } |
|
1183 }; |
762 }; |
1184 |
763 |
1185 /// \ingroup graphbits |
764 /// \ingroup graphbits |
1186 /// |
765 /// |
1187 /// \brief Extender for the BpUGraphs |
766 /// \brief Extender for the BpUGraphs |
1243 } |
822 } |
1244 UEdge fromId(int id, UEdge) const { |
823 UEdge fromId(int id, UEdge) const { |
1245 return Parent::uEdgeFromId(id); |
824 return Parent::uEdgeFromId(id); |
1246 } |
825 } |
1247 |
826 |
1248 typedef AlterationNotifier<Node> NodeNotifier; |
827 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier; |
1249 typedef AlterationNotifier<BNode> BNodeNotifier; |
828 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier; |
1250 typedef AlterationNotifier<ANode> ANodeNotifier; |
829 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier; |
1251 typedef AlterationNotifier<Edge> EdgeNotifier; |
830 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier; |
1252 typedef AlterationNotifier<UEdge> UEdgeNotifier; |
831 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier; |
1253 |
832 |
1254 protected: |
833 protected: |
1255 |
834 |
1256 mutable NodeNotifier nodeNotifier; |
835 mutable ANodeNotifier anode_notifier; |
1257 mutable BNodeNotifier bNodeNotifier; |
836 mutable BNodeNotifier bnode_notifier; |
1258 mutable ANodeNotifier aNodeNotifier; |
837 mutable NodeNotifier node_notifier; |
1259 mutable EdgeNotifier edgeNotifier; |
838 mutable EdgeNotifier edge_notifier; |
1260 mutable UEdgeNotifier uEdgeNotifier; |
839 mutable UEdgeNotifier uedge_notifier; |
1261 |
840 |
1262 public: |
841 public: |
1263 |
842 |
1264 NodeNotifier& getNotifier(Node) const { |
843 NodeNotifier& getNotifier(Node) const { |
1265 return nodeNotifier; |
844 return node_notifier; |
|
845 } |
|
846 |
|
847 ANodeNotifier& getNotifier(ANode) const { |
|
848 return anode_notifier; |
1266 } |
849 } |
1267 |
850 |
1268 BNodeNotifier& getNotifier(BNode) const { |
851 BNodeNotifier& getNotifier(BNode) const { |
1269 return bNodeNotifier; |
852 return bnode_notifier; |
1270 } |
|
1271 |
|
1272 ANodeNotifier& getNotifier(ANode) const { |
|
1273 return aNodeNotifier; |
|
1274 } |
853 } |
1275 |
854 |
1276 EdgeNotifier& getNotifier(Edge) const { |
855 EdgeNotifier& getNotifier(Edge) const { |
1277 return edgeNotifier; |
856 return edge_notifier; |
1278 } |
857 } |
1279 |
858 |
1280 UEdgeNotifier& getNotifier(UEdge) const { |
859 UEdgeNotifier& getNotifier(UEdge) const { |
1281 return uEdgeNotifier; |
860 return uedge_notifier; |
1282 } |
861 } |
1283 |
862 |
1284 class NodeIt : public Node { |
863 class NodeIt : public Node { |
1285 const Graph* graph; |
864 const Graph* graph; |
1286 public: |
865 public: |
1592 |
1169 |
1593 typedef Node Key; |
1170 typedef Node Key; |
1594 typedef _Value Value; |
1171 typedef _Value Value; |
1595 |
1172 |
1596 /// The reference type of the map; |
1173 /// The reference type of the map; |
1597 typedef typename BNodeMap<_Value>::Reference Reference; |
1174 typedef typename ANodeMap<_Value>::Reference Reference; |
1598 /// The pointer type of the map; |
|
1599 typedef typename BNodeMap<_Value>::Pointer Pointer; |
|
1600 |
|
1601 /// The const value type of the map. |
|
1602 typedef const Value ConstValue; |
|
1603 /// The const reference type of the map; |
1175 /// The const reference type of the map; |
1604 typedef typename BNodeMap<_Value>::ConstReference ConstReference; |
1176 typedef typename ANodeMap<_Value>::ConstReference ConstReference; |
1605 /// The pointer type of the map; |
|
1606 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer; |
|
1607 |
1177 |
1608 typedef True ReferenceMapTag; |
1178 typedef True ReferenceMapTag; |
1609 |
1179 |
1610 NodeMapBase(const Graph& _g) |
1180 NodeMapBase(const Graph& graph) |
1611 : aNodeMap(_g), bNodeMap(_g) {} |
1181 : aNodeMap(graph), bNodeMap(graph) {} |
1612 NodeMapBase(const Graph& _g, const _Value& _v) |
1182 NodeMapBase(const Graph& graph, const _Value& value) |
1613 : aNodeMap(_g, _v), bNodeMap(_g, _v) {} |
1183 : aNodeMap(graph, value), bNodeMap(graph, value) {} |
1614 |
1184 |
1615 ConstReference operator[](const Key& node) const { |
1185 ConstReference operator[](const Key& node) const { |
1616 if (Parent::aNode(node)) { |
1186 if (Parent::aNode(node)) { |
1617 return aNodeMap[node]; |
1187 return aNodeMap[node]; |
1618 } else { |
1188 } else { |
1685 |
1255 |
1686 |
1256 |
1687 |
1257 |
1688 template <typename _Value> |
1258 template <typename _Value> |
1689 class EdgeMap |
1259 class EdgeMap |
1690 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { |
1260 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
1691 public: |
1261 public: |
1692 typedef BpUGraphExtender Graph; |
1262 typedef BpUGraphExtender Graph; |
1693 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
1263 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
1694 |
1264 |
1695 EdgeMap(const Graph& _g) |
1265 EdgeMap(const Graph& graph) |
1696 : Parent(_g) {} |
1266 : Parent(graph) {} |
1697 EdgeMap(const Graph& _g, const _Value& _v) |
1267 EdgeMap(const Graph& graph, const _Value& value) |
1698 : Parent(_g, _v) {} |
1268 : Parent(graph, value) {} |
1699 |
1269 |
1700 EdgeMap& operator=(const EdgeMap& cmap) { |
1270 EdgeMap& operator=(const EdgeMap& cmap) { |
1701 return operator=<EdgeMap>(cmap); |
1271 return operator=<EdgeMap>(cmap); |
1702 } |
1272 } |
1703 |
1273 |
1704 template <typename CMap> |
1274 template <typename CMap> |
1705 EdgeMap& operator=(const CMap& cmap) { |
1275 EdgeMap& operator=(const CMap& cmap) { |
1706 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); |
1276 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); |
1707 const typename Parent::Graph* graph = Parent::getGraph(); |
1277 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
1708 Edge it; |
1278 Edge it; |
1709 for (graph->first(it); it != INVALID; graph->next(it)) { |
1279 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
1710 Parent::set(it, cmap[it]); |
1280 Parent::set(it, cmap[it]); |
1711 } |
1281 } |
1712 return *this; |
1282 return *this; |
1713 } |
1283 } |
1714 }; |
1284 }; |
1715 |
1285 |
1716 template <typename _Value> |
1286 template <typename _Value> |
1717 class UEdgeMap |
1287 class UEdgeMap |
1718 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { |
1288 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { |
1719 public: |
1289 public: |
1720 typedef BpUGraphExtender Graph; |
1290 typedef BpUGraphExtender Graph; |
1721 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > |
1291 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
1722 Parent; |
1292 |
1723 |
1293 UEdgeMap(const Graph& graph) |
1724 UEdgeMap(const Graph& _g) |
1294 : Parent(graph) {} |
1725 : Parent(_g) {} |
1295 UEdgeMap(const Graph& graph, const _Value& value) |
1726 UEdgeMap(const Graph& _g, const _Value& _v) |
1296 : Parent(graph, value) {} |
1727 : Parent(_g, _v) {} |
|
1728 |
1297 |
1729 UEdgeMap& operator=(const UEdgeMap& cmap) { |
1298 UEdgeMap& operator=(const UEdgeMap& cmap) { |
1730 return operator=<UEdgeMap>(cmap); |
1299 return operator=<UEdgeMap>(cmap); |
1731 } |
1300 } |
1732 |
1301 |
1733 template <typename CMap> |
1302 template <typename CMap> |
1734 UEdgeMap& operator=(const CMap& cmap) { |
1303 UEdgeMap& operator=(const CMap& cmap) { |
1735 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); |
1304 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); |
1736 const typename Parent::Graph* graph = Parent::getGraph(); |
1305 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
1737 UEdge it; |
1306 Edge it; |
1738 for (graph->first(it); it != INVALID; graph->next(it)) { |
1307 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
1739 Parent::set(it, cmap[it]); |
1308 Parent::set(it, cmap[it]); |
1740 } |
1309 } |
1741 return *this; |
1310 return *this; |
1742 } |
1311 } |
1743 }; |
1312 }; |