312 edge_notifier.clear(); |
316 edge_notifier.clear(); |
313 node_notifier.clear(); |
317 node_notifier.clear(); |
314 } |
318 } |
315 }; |
319 }; |
316 |
320 |
|
321 /// \ingroup graphbits |
|
322 /// |
|
323 /// \brief Extender for the UGraphs |
|
324 template <typename Base> |
|
325 class UGraphExtender : public Base { |
|
326 public: |
|
327 |
|
328 typedef Base Parent; |
|
329 typedef UGraphExtender Graph; |
|
330 |
|
331 typedef typename Parent::Node Node; |
|
332 typedef typename Parent::Edge Edge; |
|
333 typedef typename Parent::UEdge UEdge; |
|
334 |
|
335 // UGraph extension |
|
336 |
|
337 int maxId(Node) const { |
|
338 return Parent::maxNodeId(); |
|
339 } |
|
340 |
|
341 int maxId(Edge) const { |
|
342 return Parent::maxEdgeId(); |
|
343 } |
|
344 |
|
345 int maxId(UEdge) const { |
|
346 return Parent::maxUEdgeId(); |
|
347 } |
|
348 |
|
349 Node fromId(int id, Node) const { |
|
350 return Parent::nodeFromId(id); |
|
351 } |
|
352 |
|
353 Edge fromId(int id, Edge) const { |
|
354 return Parent::edgeFromId(id); |
|
355 } |
|
356 |
|
357 UEdge fromId(int id, UEdge) const { |
|
358 return Parent::uEdgeFromId(id); |
|
359 } |
|
360 |
|
361 Node oppositeNode(const Node &n, const UEdge &e) const { |
|
362 if( n == Parent::source(e)) |
|
363 return Parent::target(e); |
|
364 else if( n == Parent::target(e)) |
|
365 return Parent::source(e); |
|
366 else |
|
367 return INVALID; |
|
368 } |
|
369 |
|
370 Edge oppositeEdge(const Edge &e) const { |
|
371 return Parent::direct(e, !Parent::direction(e)); |
|
372 } |
|
373 |
|
374 using Parent::direct; |
|
375 Edge direct(const UEdge &ue, const Node &s) const { |
|
376 return Parent::direct(ue, Parent::source(ue) == s); |
|
377 } |
|
378 |
|
379 // Alterable extension |
|
380 |
|
381 typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier; |
|
382 typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier; |
|
383 typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier; |
|
384 |
|
385 |
|
386 protected: |
|
387 |
|
388 mutable NodeNotifier node_notifier; |
|
389 mutable EdgeNotifier edge_notifier; |
|
390 mutable UEdgeNotifier uedge_notifier; |
|
391 |
|
392 public: |
|
393 |
|
394 NodeNotifier& getNotifier(Node) const { |
|
395 return node_notifier; |
|
396 } |
|
397 |
|
398 EdgeNotifier& getNotifier(Edge) const { |
|
399 return edge_notifier; |
|
400 } |
|
401 |
|
402 UEdgeNotifier& getNotifier(UEdge) const { |
|
403 return uedge_notifier; |
|
404 } |
|
405 |
|
406 |
|
407 |
|
408 class NodeIt : public Node { |
|
409 const Graph* graph; |
|
410 public: |
|
411 |
|
412 NodeIt() {} |
|
413 |
|
414 NodeIt(Invalid i) : Node(i) { } |
|
415 |
|
416 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
417 _graph.first(static_cast<Node&>(*this)); |
|
418 } |
|
419 |
|
420 NodeIt(const Graph& _graph, const Node& node) |
|
421 : Node(node), graph(&_graph) {} |
|
422 |
|
423 NodeIt& operator++() { |
|
424 graph->next(*this); |
|
425 return *this; |
|
426 } |
|
427 |
|
428 }; |
|
429 |
|
430 |
|
431 class EdgeIt : public Edge { |
|
432 const Graph* graph; |
|
433 public: |
|
434 |
|
435 EdgeIt() { } |
|
436 |
|
437 EdgeIt(Invalid i) : Edge(i) { } |
|
438 |
|
439 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
440 _graph.first(static_cast<Edge&>(*this)); |
|
441 } |
|
442 |
|
443 EdgeIt(const Graph& _graph, const Edge& e) : |
|
444 Edge(e), graph(&_graph) { } |
|
445 |
|
446 EdgeIt& operator++() { |
|
447 graph->next(*this); |
|
448 return *this; |
|
449 } |
|
450 |
|
451 }; |
|
452 |
|
453 |
|
454 class OutEdgeIt : public Edge { |
|
455 const Graph* graph; |
|
456 public: |
|
457 |
|
458 OutEdgeIt() { } |
|
459 |
|
460 OutEdgeIt(Invalid i) : Edge(i) { } |
|
461 |
|
462 OutEdgeIt(const Graph& _graph, const Node& node) |
|
463 : graph(&_graph) { |
|
464 _graph.firstOut(*this, node); |
|
465 } |
|
466 |
|
467 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
468 : Edge(edge), graph(&_graph) {} |
|
469 |
|
470 OutEdgeIt& operator++() { |
|
471 graph->nextOut(*this); |
|
472 return *this; |
|
473 } |
|
474 |
|
475 }; |
|
476 |
|
477 |
|
478 class InEdgeIt : public Edge { |
|
479 const Graph* graph; |
|
480 public: |
|
481 |
|
482 InEdgeIt() { } |
|
483 |
|
484 InEdgeIt(Invalid i) : Edge(i) { } |
|
485 |
|
486 InEdgeIt(const Graph& _graph, const Node& node) |
|
487 : graph(&_graph) { |
|
488 _graph.firstIn(*this, node); |
|
489 } |
|
490 |
|
491 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
492 Edge(edge), graph(&_graph) {} |
|
493 |
|
494 InEdgeIt& operator++() { |
|
495 graph->nextIn(*this); |
|
496 return *this; |
|
497 } |
|
498 |
|
499 }; |
|
500 |
|
501 |
|
502 class UEdgeIt : public Parent::UEdge { |
|
503 const Graph* graph; |
|
504 public: |
|
505 |
|
506 UEdgeIt() { } |
|
507 |
|
508 UEdgeIt(Invalid i) : UEdge(i) { } |
|
509 |
|
510 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
511 _graph.first(static_cast<UEdge&>(*this)); |
|
512 } |
|
513 |
|
514 UEdgeIt(const Graph& _graph, const UEdge& e) : |
|
515 UEdge(e), graph(&_graph) { } |
|
516 |
|
517 UEdgeIt& operator++() { |
|
518 graph->next(*this); |
|
519 return *this; |
|
520 } |
|
521 |
|
522 }; |
|
523 |
|
524 class IncEdgeIt : public Parent::UEdge { |
|
525 friend class UGraphExtender; |
|
526 const Graph* graph; |
|
527 bool direction; |
|
528 public: |
|
529 |
|
530 IncEdgeIt() { } |
|
531 |
|
532 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } |
|
533 |
|
534 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { |
|
535 _graph.firstInc(*this, direction, n); |
|
536 } |
|
537 |
|
538 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) |
|
539 : graph(&_graph), UEdge(ue) { |
|
540 direction = (_graph.source(ue) == n); |
|
541 } |
|
542 |
|
543 IncEdgeIt& operator++() { |
|
544 graph->nextInc(*this, direction); |
|
545 return *this; |
|
546 } |
|
547 }; |
|
548 |
|
549 /// \brief Base node of the iterator |
|
550 /// |
|
551 /// Returns the base node (ie. the source in this case) of the iterator |
|
552 Node baseNode(const OutEdgeIt &e) const { |
|
553 return Parent::source((Edge)e); |
|
554 } |
|
555 /// \brief Running node of the iterator |
|
556 /// |
|
557 /// Returns the running node (ie. the target in this case) of the |
|
558 /// iterator |
|
559 Node runningNode(const OutEdgeIt &e) const { |
|
560 return Parent::target((Edge)e); |
|
561 } |
|
562 |
|
563 /// \brief Base node of the iterator |
|
564 /// |
|
565 /// Returns the base node (ie. the target in this case) of the iterator |
|
566 Node baseNode(const InEdgeIt &e) const { |
|
567 return Parent::target((Edge)e); |
|
568 } |
|
569 /// \brief Running node of the iterator |
|
570 /// |
|
571 /// Returns the running node (ie. the source in this case) of the |
|
572 /// iterator |
|
573 Node runningNode(const InEdgeIt &e) const { |
|
574 return Parent::source((Edge)e); |
|
575 } |
|
576 |
|
577 /// Base node of the iterator |
|
578 /// |
|
579 /// Returns the base node of the iterator |
|
580 Node baseNode(const IncEdgeIt &e) const { |
|
581 return e.direction ? source(e) : target(e); |
|
582 } |
|
583 /// Running node of the iterator |
|
584 /// |
|
585 /// Returns the running node of the iterator |
|
586 Node runningNode(const IncEdgeIt &e) const { |
|
587 return e.direction ? target(e) : source(e); |
|
588 } |
|
589 |
|
590 // Mappable extension |
|
591 |
|
592 template <typename _Value> |
|
593 class NodeMap |
|
594 : public MapExtender<DefaultMap<Graph, Node, _Value> > { |
|
595 public: |
|
596 typedef UGraphExtender Graph; |
|
597 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; |
|
598 |
|
599 NodeMap(const Graph& graph) |
|
600 : Parent(graph) {} |
|
601 NodeMap(const Graph& graph, const _Value& value) |
|
602 : Parent(graph, value) {} |
|
603 |
|
604 NodeMap& operator=(const NodeMap& cmap) { |
|
605 return operator=<NodeMap>(cmap); |
|
606 } |
|
607 |
|
608 template <typename CMap> |
|
609 NodeMap& operator=(const CMap& cmap) { |
|
610 Parent::operator=(cmap); |
|
611 return *this; |
|
612 } |
|
613 |
|
614 }; |
|
615 |
|
616 template <typename _Value> |
|
617 class EdgeMap |
|
618 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
|
619 public: |
|
620 typedef UGraphExtender Graph; |
|
621 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
|
622 |
|
623 EdgeMap(const Graph& graph) |
|
624 : Parent(graph) {} |
|
625 EdgeMap(const Graph& graph, const _Value& value) |
|
626 : Parent(graph, value) {} |
|
627 |
|
628 EdgeMap& operator=(const EdgeMap& cmap) { |
|
629 return operator=<EdgeMap>(cmap); |
|
630 } |
|
631 |
|
632 template <typename CMap> |
|
633 EdgeMap& operator=(const CMap& cmap) { |
|
634 Parent::operator=(cmap); |
|
635 return *this; |
|
636 } |
|
637 }; |
|
638 |
|
639 |
|
640 template <typename _Value> |
|
641 class UEdgeMap |
|
642 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { |
|
643 public: |
|
644 typedef UGraphExtender Graph; |
|
645 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
|
646 |
|
647 UEdgeMap(const Graph& graph) |
|
648 : Parent(graph) {} |
|
649 |
|
650 UEdgeMap(const Graph& graph, const _Value& value) |
|
651 : Parent(graph, value) {} |
|
652 |
|
653 UEdgeMap& operator=(const UEdgeMap& cmap) { |
|
654 return operator=<UEdgeMap>(cmap); |
|
655 } |
|
656 |
|
657 template <typename CMap> |
|
658 UEdgeMap& operator=(const CMap& cmap) { |
|
659 Parent::operator=(cmap); |
|
660 return *this; |
|
661 } |
|
662 |
|
663 }; |
|
664 |
|
665 // Alteration extension |
|
666 |
|
667 Node addNode() { |
|
668 Node node = Parent::addNode(); |
|
669 getNotifier(Node()).add(node); |
|
670 return node; |
|
671 } |
|
672 |
|
673 UEdge addEdge(const Node& from, const Node& to) { |
|
674 UEdge uedge = Parent::addEdge(from, to); |
|
675 getNotifier(UEdge()).add(uedge); |
|
676 getNotifier(Edge()).add(Parent::direct(uedge, true)); |
|
677 getNotifier(Edge()).add(Parent::direct(uedge, false)); |
|
678 return uedge; |
|
679 } |
|
680 |
|
681 void clear() { |
|
682 getNotifier(Edge()).clear(); |
|
683 getNotifier(UEdge()).clear(); |
|
684 getNotifier(Node()).clear(); |
|
685 Parent::clear(); |
|
686 } |
|
687 |
|
688 void erase(const Node& node) { |
|
689 Edge edge; |
|
690 Parent::firstOut(edge, node); |
|
691 while (edge != INVALID ) { |
|
692 erase(edge); |
|
693 Parent::firstOut(edge, node); |
|
694 } |
|
695 |
|
696 Parent::firstIn(edge, node); |
|
697 while (edge != INVALID ) { |
|
698 erase(edge); |
|
699 Parent::firstIn(edge, node); |
|
700 } |
|
701 |
|
702 getNotifier(Node()).erase(node); |
|
703 Parent::erase(node); |
|
704 } |
|
705 |
|
706 void erase(const UEdge& uedge) { |
|
707 getNotifier(Edge()).erase(Parent::direct(uedge, true)); |
|
708 getNotifier(Edge()).erase(Parent::direct(uedge, false)); |
|
709 getNotifier(UEdge()).erase(uedge); |
|
710 Parent::erase(uedge); |
|
711 } |
|
712 |
|
713 UGraphExtender() { |
|
714 node_notifier.setContainer(*this); |
|
715 edge_notifier.setContainer(*this); |
|
716 uedge_notifier.setContainer(*this); |
|
717 } |
|
718 |
|
719 ~UGraphExtender() { |
|
720 uedge_notifier.clear(); |
|
721 edge_notifier.clear(); |
|
722 node_notifier.clear(); |
|
723 } |
|
724 |
|
725 }; |
|
726 |
|
727 /// \ingroup graphbits |
|
728 /// |
|
729 /// \brief Extender for the BpUGraphs |
|
730 template <typename Base> |
|
731 class BpUGraphExtender : public Base { |
|
732 public: |
|
733 typedef Base Parent; |
|
734 typedef BpUGraphExtender Graph; |
|
735 |
|
736 typedef typename Parent::Node Node; |
|
737 typedef typename Parent::UEdge UEdge; |
|
738 |
|
739 |
|
740 using Parent::first; |
|
741 using Parent::next; |
|
742 |
|
743 using Parent::id; |
|
744 |
|
745 class ANode : public Node { |
|
746 friend class BpUGraphExtender; |
|
747 public: |
|
748 ANode() {} |
|
749 ANode(const Node& node) : Node(node) { |
|
750 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
|
751 typename Parent::NodeSetError()); |
|
752 } |
|
753 ANode(Invalid) : Node(INVALID) {} |
|
754 }; |
|
755 |
|
756 void first(ANode& node) const { |
|
757 Parent::firstANode(static_cast<Node&>(node)); |
|
758 } |
|
759 void next(ANode& node) const { |
|
760 Parent::nextANode(static_cast<Node&>(node)); |
|
761 } |
|
762 |
|
763 int id(const ANode& node) const { |
|
764 return Parent::aNodeId(node); |
|
765 } |
|
766 |
|
767 class BNode : public Node { |
|
768 friend class BpUGraphExtender; |
|
769 public: |
|
770 BNode() {} |
|
771 BNode(const Node& node) : Node(node) { |
|
772 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
|
773 typename Parent::NodeSetError()); |
|
774 } |
|
775 BNode(Invalid) : Node(INVALID) {} |
|
776 }; |
|
777 |
|
778 void first(BNode& node) const { |
|
779 Parent::firstBNode(static_cast<Node&>(node)); |
|
780 } |
|
781 void next(BNode& node) const { |
|
782 Parent::nextBNode(static_cast<Node&>(node)); |
|
783 } |
|
784 |
|
785 int id(const BNode& node) const { |
|
786 return Parent::aNodeId(node); |
|
787 } |
|
788 |
|
789 Node source(const UEdge& edge) const { |
|
790 return aNode(edge); |
|
791 } |
|
792 Node target(const UEdge& edge) const { |
|
793 return bNode(edge); |
|
794 } |
|
795 |
|
796 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
|
797 if (Parent::aNode(node)) { |
|
798 Parent::firstFromANode(edge, node); |
|
799 direction = true; |
|
800 } else { |
|
801 Parent::firstFromBNode(edge, node); |
|
802 direction = static_cast<UEdge&>(edge) == INVALID; |
|
803 } |
|
804 } |
|
805 void nextInc(UEdge& edge, bool& direction) const { |
|
806 if (direction) { |
|
807 Parent::nextFromANode(edge); |
|
808 } else { |
|
809 Parent::nextFromBNode(edge); |
|
810 if (edge == INVALID) direction = true; |
|
811 } |
|
812 } |
|
813 |
|
814 class Edge : public UEdge { |
|
815 friend class BpUGraphExtender; |
|
816 protected: |
|
817 bool forward; |
|
818 |
|
819 Edge(const UEdge& edge, bool _forward) |
|
820 : UEdge(edge), forward(_forward) {} |
|
821 |
|
822 public: |
|
823 Edge() {} |
|
824 Edge (Invalid) : UEdge(INVALID), forward(true) {} |
|
825 bool operator==(const Edge& i) const { |
|
826 return UEdge::operator==(i) && forward == i.forward; |
|
827 } |
|
828 bool operator!=(const Edge& i) const { |
|
829 return UEdge::operator!=(i) || forward != i.forward; |
|
830 } |
|
831 bool operator<(const Edge& i) const { |
|
832 return UEdge::operator<(i) || |
|
833 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); |
|
834 } |
|
835 }; |
|
836 |
|
837 void first(Edge& edge) const { |
|
838 Parent::first(static_cast<UEdge&>(edge)); |
|
839 edge.forward = true; |
|
840 } |
|
841 |
|
842 void next(Edge& edge) const { |
|
843 if (!edge.forward) { |
|
844 Parent::next(static_cast<UEdge&>(edge)); |
|
845 } |
|
846 edge.forward = !edge.forward; |
|
847 } |
|
848 |
|
849 void firstOut(Edge& edge, const Node& node) const { |
|
850 if (Parent::aNode(node)) { |
|
851 Parent::firstFromANode(edge, node); |
|
852 edge.forward = true; |
|
853 } else { |
|
854 Parent::firstFromBNode(edge, node); |
|
855 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
856 } |
|
857 } |
|
858 void nextOut(Edge& edge) const { |
|
859 if (edge.forward) { |
|
860 Parent::nextFromANode(edge); |
|
861 } else { |
|
862 Parent::nextFromBNode(edge); |
|
863 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
864 } |
|
865 } |
|
866 |
|
867 void firstIn(Edge& edge, const Node& node) const { |
|
868 if (Parent::bNode(node)) { |
|
869 Parent::firstFromBNode(edge, node); |
|
870 edge.forward = true; |
|
871 } else { |
|
872 Parent::firstFromANode(edge, node); |
|
873 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
874 } |
|
875 } |
|
876 void nextIn(Edge& edge) const { |
|
877 if (edge.forward) { |
|
878 Parent::nextFromBNode(edge); |
|
879 } else { |
|
880 Parent::nextFromANode(edge); |
|
881 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
882 } |
|
883 } |
|
884 |
|
885 Node source(const Edge& edge) const { |
|
886 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); |
|
887 } |
|
888 Node target(const Edge& edge) const { |
|
889 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); |
|
890 } |
|
891 |
|
892 int id(const Edge& edge) const { |
|
893 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + |
|
894 (edge.forward ? 0 : 1); |
|
895 } |
|
896 Edge edgeFromId(int id) const { |
|
897 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); |
|
898 } |
|
899 int maxEdgeId() const { |
|
900 return (Parent::maxUEdgeId(UEdge()) << 1) + 1; |
|
901 } |
|
902 |
|
903 bool direction(const Edge& edge) const { |
|
904 return edge.forward; |
|
905 } |
|
906 |
|
907 Edge direct(const UEdge& edge, bool direction) const { |
|
908 return Edge(edge, direction); |
|
909 } |
|
910 |
|
911 int edgeNum() const { |
|
912 return 2 * Parent::uEdgeNum(); |
|
913 } |
|
914 |
|
915 int uEdgeNum() const { |
|
916 return Parent::uEdgeNum(); |
|
917 } |
|
918 |
|
919 Node oppositeNode(const UEdge& edge, const Node& node) const { |
|
920 return source(edge) == node ? |
|
921 target(edge) : source(edge); |
|
922 } |
|
923 |
|
924 Edge direct(const UEdge& edge, const Node& node) const { |
|
925 return Edge(edge, node == Parent::source(edge)); |
|
926 } |
|
927 |
|
928 Edge oppositeEdge(const Edge& edge) const { |
|
929 return Parent::direct(edge, !Parent::direction(edge)); |
|
930 } |
|
931 |
|
932 |
|
933 int maxId(Node) const { |
|
934 return Parent::maxNodeId(); |
|
935 } |
|
936 int maxId(BNode) const { |
|
937 return Parent::maxBNodeId(); |
|
938 } |
|
939 int maxId(ANode) const { |
|
940 return Parent::maxANodeId(); |
|
941 } |
|
942 int maxId(Edge) const { |
|
943 return maxEdgeId(); |
|
944 } |
|
945 int maxId(UEdge) const { |
|
946 return Parent::maxUEdgeId(); |
|
947 } |
|
948 |
|
949 |
|
950 Node fromId(int id, Node) const { |
|
951 return Parent::nodeFromId(id); |
|
952 } |
|
953 ANode fromId(int id, ANode) const { |
|
954 return Parent::fromANodeId(id); |
|
955 } |
|
956 BNode fromId(int id, BNode) const { |
|
957 return Parent::fromBNodeId(id); |
|
958 } |
|
959 Edge fromId(int id, Edge) const { |
|
960 return Parent::edgeFromId(id); |
|
961 } |
|
962 UEdge fromId(int id, UEdge) const { |
|
963 return Parent::uEdgeFromId(id); |
|
964 } |
|
965 |
|
966 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier; |
|
967 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier; |
|
968 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier; |
|
969 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier; |
|
970 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier; |
|
971 |
|
972 protected: |
|
973 |
|
974 mutable ANodeNotifier anode_notifier; |
|
975 mutable BNodeNotifier bnode_notifier; |
|
976 mutable NodeNotifier node_notifier; |
|
977 mutable EdgeNotifier edge_notifier; |
|
978 mutable UEdgeNotifier uedge_notifier; |
|
979 |
|
980 public: |
|
981 |
|
982 NodeNotifier& getNotifier(Node) const { |
|
983 return node_notifier; |
|
984 } |
|
985 |
|
986 ANodeNotifier& getNotifier(ANode) const { |
|
987 return anode_notifier; |
|
988 } |
|
989 |
|
990 BNodeNotifier& getNotifier(BNode) const { |
|
991 return bnode_notifier; |
|
992 } |
|
993 |
|
994 EdgeNotifier& getNotifier(Edge) const { |
|
995 return edge_notifier; |
|
996 } |
|
997 |
|
998 UEdgeNotifier& getNotifier(UEdge) const { |
|
999 return uedge_notifier; |
|
1000 } |
|
1001 |
|
1002 class NodeIt : public Node { |
|
1003 const Graph* graph; |
|
1004 public: |
|
1005 |
|
1006 NodeIt() { } |
|
1007 |
|
1008 NodeIt(Invalid i) : Node(INVALID) { } |
|
1009 |
|
1010 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
1011 graph->first(static_cast<Node&>(*this)); |
|
1012 } |
|
1013 |
|
1014 NodeIt(const Graph& _graph, const Node& node) |
|
1015 : Node(node), graph(&_graph) { } |
|
1016 |
|
1017 NodeIt& operator++() { |
|
1018 graph->next(*this); |
|
1019 return *this; |
|
1020 } |
|
1021 |
|
1022 }; |
|
1023 |
|
1024 class ANodeIt : public Node { |
|
1025 friend class BpUGraphExtender; |
|
1026 const Graph* graph; |
|
1027 public: |
|
1028 |
|
1029 ANodeIt() { } |
|
1030 |
|
1031 ANodeIt(Invalid i) : Node(INVALID) { } |
|
1032 |
|
1033 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { |
|
1034 graph->firstANode(static_cast<Node&>(*this)); |
|
1035 } |
|
1036 |
|
1037 ANodeIt(const Graph& _graph, const Node& node) |
|
1038 : Node(node), graph(&_graph) {} |
|
1039 |
|
1040 ANodeIt& operator++() { |
|
1041 graph->nextANode(*this); |
|
1042 return *this; |
|
1043 } |
|
1044 }; |
|
1045 |
|
1046 class BNodeIt : public Node { |
|
1047 friend class BpUGraphExtender; |
|
1048 const Graph* graph; |
|
1049 public: |
|
1050 |
|
1051 BNodeIt() { } |
|
1052 |
|
1053 BNodeIt(Invalid i) : Node(INVALID) { } |
|
1054 |
|
1055 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { |
|
1056 graph->firstBNode(static_cast<Node&>(*this)); |
|
1057 } |
|
1058 |
|
1059 BNodeIt(const Graph& _graph, const Node& node) |
|
1060 : Node(node), graph(&_graph) {} |
|
1061 |
|
1062 BNodeIt& operator++() { |
|
1063 graph->nextBNode(*this); |
|
1064 return *this; |
|
1065 } |
|
1066 }; |
|
1067 |
|
1068 class EdgeIt : public Edge { |
|
1069 friend class BpUGraphExtender; |
|
1070 const Graph* graph; |
|
1071 public: |
|
1072 |
|
1073 EdgeIt() { } |
|
1074 |
|
1075 EdgeIt(Invalid i) : Edge(INVALID) { } |
|
1076 |
|
1077 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
1078 graph->first(static_cast<Edge&>(*this)); |
|
1079 } |
|
1080 |
|
1081 EdgeIt(const Graph& _graph, const Edge& edge) |
|
1082 : Edge(edge), graph(&_graph) { } |
|
1083 |
|
1084 EdgeIt& operator++() { |
|
1085 graph->next(*this); |
|
1086 return *this; |
|
1087 } |
|
1088 |
|
1089 }; |
|
1090 |
|
1091 class UEdgeIt : public UEdge { |
|
1092 friend class BpUGraphExtender; |
|
1093 const Graph* graph; |
|
1094 public: |
|
1095 |
|
1096 UEdgeIt() { } |
|
1097 |
|
1098 UEdgeIt(Invalid i) : UEdge(INVALID) { } |
|
1099 |
|
1100 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
1101 graph->first(static_cast<UEdge&>(*this)); |
|
1102 } |
|
1103 |
|
1104 UEdgeIt(const Graph& _graph, const UEdge& edge) |
|
1105 : UEdge(edge), graph(&_graph) { } |
|
1106 |
|
1107 UEdgeIt& operator++() { |
|
1108 graph->next(*this); |
|
1109 return *this; |
|
1110 } |
|
1111 }; |
|
1112 |
|
1113 class OutEdgeIt : public Edge { |
|
1114 friend class BpUGraphExtender; |
|
1115 const Graph* graph; |
|
1116 public: |
|
1117 |
|
1118 OutEdgeIt() { } |
|
1119 |
|
1120 OutEdgeIt(Invalid i) : Edge(i) { } |
|
1121 |
|
1122 OutEdgeIt(const Graph& _graph, const Node& node) |
|
1123 : graph(&_graph) { |
|
1124 graph->firstOut(*this, node); |
|
1125 } |
|
1126 |
|
1127 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
1128 : Edge(edge), graph(&_graph) {} |
|
1129 |
|
1130 OutEdgeIt& operator++() { |
|
1131 graph->nextOut(*this); |
|
1132 return *this; |
|
1133 } |
|
1134 |
|
1135 }; |
|
1136 |
|
1137 |
|
1138 class InEdgeIt : public Edge { |
|
1139 friend class BpUGraphExtender; |
|
1140 const Graph* graph; |
|
1141 public: |
|
1142 |
|
1143 InEdgeIt() { } |
|
1144 |
|
1145 InEdgeIt(Invalid i) : Edge(i) { } |
|
1146 |
|
1147 InEdgeIt(const Graph& _graph, const Node& node) |
|
1148 : graph(&_graph) { |
|
1149 graph->firstIn(*this, node); |
|
1150 } |
|
1151 |
|
1152 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
1153 Edge(edge), graph(&_graph) {} |
|
1154 |
|
1155 InEdgeIt& operator++() { |
|
1156 graph->nextIn(*this); |
|
1157 return *this; |
|
1158 } |
|
1159 |
|
1160 }; |
|
1161 |
|
1162 /// \brief Base node of the iterator |
|
1163 /// |
|
1164 /// Returns the base node (ie. the source in this case) of the iterator |
|
1165 Node baseNode(const OutEdgeIt &e) const { |
|
1166 return Parent::source((Edge&)e); |
|
1167 } |
|
1168 /// \brief Running node of the iterator |
|
1169 /// |
|
1170 /// Returns the running node (ie. the target in this case) of the |
|
1171 /// iterator |
|
1172 Node runningNode(const OutEdgeIt &e) const { |
|
1173 return Parent::target((Edge&)e); |
|
1174 } |
|
1175 |
|
1176 /// \brief Base node of the iterator |
|
1177 /// |
|
1178 /// Returns the base node (ie. the target in this case) of the iterator |
|
1179 Node baseNode(const InEdgeIt &e) const { |
|
1180 return Parent::target((Edge&)e); |
|
1181 } |
|
1182 /// \brief Running node of the iterator |
|
1183 /// |
|
1184 /// Returns the running node (ie. the source in this case) of the |
|
1185 /// iterator |
|
1186 Node runningNode(const InEdgeIt &e) const { |
|
1187 return Parent::source((Edge&)e); |
|
1188 } |
|
1189 |
|
1190 class IncEdgeIt : public Parent::UEdge { |
|
1191 friend class BpUGraphExtender; |
|
1192 const Graph* graph; |
|
1193 bool direction; |
|
1194 public: |
|
1195 |
|
1196 IncEdgeIt() { } |
|
1197 |
|
1198 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } |
|
1199 |
|
1200 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { |
|
1201 graph->firstInc(*this, direction, n); |
|
1202 } |
|
1203 |
|
1204 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) |
|
1205 : graph(&_graph), UEdge(ue) { |
|
1206 direction = (graph->source(ue) == n); |
|
1207 } |
|
1208 |
|
1209 IncEdgeIt& operator++() { |
|
1210 graph->nextInc(*this, direction); |
|
1211 return *this; |
|
1212 } |
|
1213 }; |
|
1214 |
|
1215 |
|
1216 /// Base node of the iterator |
|
1217 /// |
|
1218 /// Returns the base node of the iterator |
|
1219 Node baseNode(const IncEdgeIt &e) const { |
|
1220 return e.direction ? source(e) : target(e); |
|
1221 } |
|
1222 |
|
1223 /// Running node of the iterator |
|
1224 /// |
|
1225 /// Returns the running node of the iterator |
|
1226 Node runningNode(const IncEdgeIt &e) const { |
|
1227 return e.direction ? target(e) : source(e); |
|
1228 } |
|
1229 |
|
1230 template <typename _Value> |
|
1231 class ANodeMap |
|
1232 : public MapExtender<DefaultMap<Graph, ANode, _Value> > { |
|
1233 public: |
|
1234 typedef BpUGraphExtender Graph; |
|
1235 typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent; |
|
1236 |
|
1237 ANodeMap(const Graph& graph) |
|
1238 : Parent(graph) {} |
|
1239 ANodeMap(const Graph& graph, const _Value& value) |
|
1240 : Parent(graph, value) {} |
|
1241 |
|
1242 ANodeMap& operator=(const ANodeMap& cmap) { |
|
1243 return operator=<ANodeMap>(cmap); |
|
1244 } |
|
1245 |
|
1246 template <typename CMap> |
|
1247 ANodeMap& operator=(const CMap& cmap) { |
|
1248 Parent::operator=(cmap); |
|
1249 return *this; |
|
1250 } |
|
1251 |
|
1252 }; |
|
1253 |
|
1254 template <typename _Value> |
|
1255 class BNodeMap |
|
1256 : public MapExtender<DefaultMap<Graph, BNode, _Value> > { |
|
1257 public: |
|
1258 typedef BpUGraphExtender Graph; |
|
1259 typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent; |
|
1260 |
|
1261 BNodeMap(const Graph& graph) |
|
1262 : Parent(graph) {} |
|
1263 BNodeMap(const Graph& graph, const _Value& value) |
|
1264 : Parent(graph, value) {} |
|
1265 |
|
1266 BNodeMap& operator=(const BNodeMap& cmap) { |
|
1267 return operator=<BNodeMap>(cmap); |
|
1268 } |
|
1269 |
|
1270 template <typename CMap> |
|
1271 BNodeMap& operator=(const CMap& cmap) { |
|
1272 Parent::operator=(cmap); |
|
1273 return *this; |
|
1274 } |
|
1275 |
|
1276 }; |
|
1277 |
|
1278 public: |
|
1279 |
|
1280 template <typename _Value> |
|
1281 class NodeMap { |
|
1282 public: |
|
1283 typedef BpUGraphExtender Graph; |
|
1284 |
|
1285 typedef Node Key; |
|
1286 typedef _Value Value; |
|
1287 |
|
1288 /// The reference type of the map; |
|
1289 typedef typename ANodeMap<_Value>::Reference Reference; |
|
1290 /// The const reference type of the map; |
|
1291 typedef typename ANodeMap<_Value>::ConstReference ConstReference; |
|
1292 |
|
1293 typedef True ReferenceMapTag; |
|
1294 |
|
1295 NodeMap(const Graph& _graph) |
|
1296 : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} |
|
1297 NodeMap(const Graph& _graph, const _Value& _value) |
|
1298 : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} |
|
1299 |
|
1300 NodeMap& operator=(const NodeMap& cmap) { |
|
1301 return operator=<NodeMap>(cmap); |
|
1302 } |
|
1303 |
|
1304 template <typename CMap> |
|
1305 NodeMap& operator=(const CMap& cmap) { |
|
1306 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); |
|
1307 const typename Parent::Notifier* notifier = Parent::getNotifier(); |
|
1308 Edge it; |
|
1309 for (graph.first(it); it != INVALID; graph.next(it)) { |
|
1310 Parent::set(it, cmap[it]); |
|
1311 } |
|
1312 return *this; |
|
1313 } |
|
1314 |
|
1315 ConstReference operator[](const Key& node) const { |
|
1316 if (Parent::aNode(node)) { |
|
1317 return aNodeMap[node]; |
|
1318 } else { |
|
1319 return bNodeMap[node]; |
|
1320 } |
|
1321 } |
|
1322 |
|
1323 Reference operator[](const Key& node) { |
|
1324 if (Parent::aNode(node)) { |
|
1325 return aNodeMap[node]; |
|
1326 } else { |
|
1327 return bNodeMap[node]; |
|
1328 } |
|
1329 } |
|
1330 |
|
1331 void set(const Key& node, const Value& value) { |
|
1332 if (Parent::aNode(node)) { |
|
1333 aNodeMap.set(node, value); |
|
1334 } else { |
|
1335 bNodeMap.set(node, value); |
|
1336 } |
|
1337 } |
|
1338 |
|
1339 class MapIt : public NodeIt { |
|
1340 public: |
|
1341 |
|
1342 typedef NodeIt Parent; |
|
1343 |
|
1344 explicit MapIt(NodeMap& _map) |
|
1345 : Parent(_map.graph), map(_map) {} |
|
1346 |
|
1347 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { |
|
1348 return map[*this]; |
|
1349 } |
|
1350 |
|
1351 typename MapTraits<NodeMap>::ReturnValue operator*() { |
|
1352 return map[*this]; |
|
1353 } |
|
1354 |
|
1355 void set(const Value& value) { |
|
1356 map.set(*this, value); |
|
1357 } |
|
1358 |
|
1359 private: |
|
1360 NodeMap& map; |
|
1361 }; |
|
1362 |
|
1363 class ConstMapIt : public NodeIt { |
|
1364 public: |
|
1365 |
|
1366 typedef NodeIt Parent; |
|
1367 |
|
1368 explicit ConstMapIt(const NodeMap& _map) |
|
1369 : Parent(_map.graph), map(_map) {} |
|
1370 |
|
1371 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { |
|
1372 return map[*this]; |
|
1373 } |
|
1374 |
|
1375 private: |
|
1376 const NodeMap& map; |
|
1377 }; |
|
1378 |
|
1379 class ItemIt : public NodeIt { |
|
1380 public: |
|
1381 |
|
1382 typedef NodeIt Parent; |
|
1383 |
|
1384 explicit ItemIt(const NodeMap& _map) |
|
1385 : Parent(_map.graph) {} |
|
1386 |
|
1387 }; |
|
1388 |
|
1389 private: |
|
1390 const Graph& graph; |
|
1391 ANodeMap<_Value> aNodeMap; |
|
1392 BNodeMap<_Value> bNodeMap; |
|
1393 }; |
|
1394 |
|
1395 |
|
1396 template <typename _Value> |
|
1397 class EdgeMap |
|
1398 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
|
1399 public: |
|
1400 typedef BpUGraphExtender Graph; |
|
1401 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
|
1402 |
|
1403 EdgeMap(const Graph& graph) |
|
1404 : Parent(graph) {} |
|
1405 EdgeMap(const Graph& graph, const _Value& value) |
|
1406 : Parent(graph, value) {} |
|
1407 |
|
1408 EdgeMap& operator=(const EdgeMap& cmap) { |
|
1409 return operator=<EdgeMap>(cmap); |
|
1410 } |
|
1411 |
|
1412 template <typename CMap> |
|
1413 EdgeMap& operator=(const CMap& cmap) { |
|
1414 Parent::operator=(cmap); |
|
1415 return *this; |
|
1416 } |
|
1417 }; |
|
1418 |
|
1419 template <typename _Value> |
|
1420 class UEdgeMap |
|
1421 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { |
|
1422 public: |
|
1423 typedef BpUGraphExtender Graph; |
|
1424 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
|
1425 |
|
1426 UEdgeMap(const Graph& graph) |
|
1427 : Parent(graph) {} |
|
1428 UEdgeMap(const Graph& graph, const _Value& value) |
|
1429 : Parent(graph, value) {} |
|
1430 |
|
1431 UEdgeMap& operator=(const UEdgeMap& cmap) { |
|
1432 return operator=<UEdgeMap>(cmap); |
|
1433 } |
|
1434 |
|
1435 template <typename CMap> |
|
1436 UEdgeMap& operator=(const CMap& cmap) { |
|
1437 Parent::operator=(cmap); |
|
1438 return *this; |
|
1439 } |
|
1440 }; |
|
1441 |
|
1442 |
|
1443 Node addANode() { |
|
1444 Node node = Parent::addANode(); |
|
1445 getNotifier(ANode()).add(node); |
|
1446 getNotifier(Node()).add(node); |
|
1447 return node; |
|
1448 } |
|
1449 |
|
1450 Node addBNode() { |
|
1451 Node node = Parent::addBNode(); |
|
1452 getNotifier(BNode()).add(node); |
|
1453 getNotifier(Node()).add(node); |
|
1454 return node; |
|
1455 } |
|
1456 |
|
1457 UEdge addEdge(const Node& source, const Node& target) { |
|
1458 UEdge uedge = Parent::addEdge(source, target); |
|
1459 getNotifier(UEdge()).add(uedge); |
|
1460 |
|
1461 std::vector<Edge> edges; |
|
1462 edges.push_back(direct(uedge, true)); |
|
1463 edges.push_back(direct(uedge, false)); |
|
1464 getNotifier(Edge()).add(edges); |
|
1465 |
|
1466 return uedge; |
|
1467 } |
|
1468 |
|
1469 void clear() { |
|
1470 getNotifier(Edge()).clear(); |
|
1471 getNotifier(UEdge()).clear(); |
|
1472 getNotifier(Node()).clear(); |
|
1473 getNotifier(BNode()).clear(); |
|
1474 getNotifier(ANode()).clear(); |
|
1475 Parent::clear(); |
|
1476 } |
|
1477 |
|
1478 void erase(const Node& node) { |
|
1479 UEdge uedge; |
|
1480 if (Parent::aNode(node)) { |
|
1481 Parent::firstFromANode(uedge, node); |
|
1482 while (uedge != INVALID) { |
|
1483 erase(uedge); |
|
1484 Parent::firstFromANode(uedge, node); |
|
1485 } |
|
1486 } else { |
|
1487 Parent::firstFromBNode(uedge, node); |
|
1488 while (uedge != INVALID) { |
|
1489 erase(uedge); |
|
1490 Parent::firstFromBNode(uedge, node); |
|
1491 } |
|
1492 } |
|
1493 |
|
1494 getNotifier(Node()).erase(node); |
|
1495 Parent::erase(node); |
|
1496 } |
|
1497 |
|
1498 void erase(const UEdge& uedge) { |
|
1499 std::vector<Edge> edges; |
|
1500 edges.push_back(direct(uedge, true)); |
|
1501 edges.push_back(direct(uedge, false)); |
|
1502 getNotifier(Edge()).erase(edges); |
|
1503 getNotifier(UEdge()).erase(uedge); |
|
1504 Parent::erase(uedge); |
|
1505 } |
|
1506 |
|
1507 |
|
1508 BpUGraphExtender() { |
|
1509 anode_notifier.setContainer(*this); |
|
1510 bnode_notifier.setContainer(*this); |
|
1511 node_notifier.setContainer(*this); |
|
1512 edge_notifier.setContainer(*this); |
|
1513 uedge_notifier.setContainer(*this); |
|
1514 } |
|
1515 |
|
1516 ~BpUGraphExtender() { |
|
1517 uedge_notifier.clear(); |
|
1518 edge_notifier.clear(); |
|
1519 node_notifier.clear(); |
|
1520 anode_notifier.clear(); |
|
1521 bnode_notifier.clear(); |
|
1522 } |
|
1523 |
|
1524 |
|
1525 }; |
|
1526 |
317 } |
1527 } |
318 |
1528 |
319 #endif |
1529 #endif |