54 int first_free_node; |
62 int first_free_node; |
55 std::vector<EdgeT> edges; |
63 std::vector<EdgeT> edges; |
56 //The first free edge |
64 //The first free edge |
57 int first_free_edge; |
65 int first_free_edge; |
58 |
66 |
59 protected: |
67 public: |
60 |
68 |
61 template <typename Key> class DynMapBase |
69 typedef ListGraph Graph; |
62 { |
|
63 protected: |
|
64 const ListGraph* G; |
|
65 public: |
|
66 virtual void add(const Key k) = 0; |
|
67 virtual void erase(const Key k) = 0; |
|
68 DynMapBase(const ListGraph &_G) : G(&_G) {} |
|
69 virtual ~DynMapBase() {} |
|
70 friend class ListGraph; |
|
71 }; |
|
72 |
|
73 public: |
|
74 template <typename T> class EdgeMap; |
|
75 template <typename T> class NodeMap; |
|
76 |
70 |
77 class Node; |
71 class Node; |
78 class Edge; |
72 class Edge; |
79 |
73 |
80 // protected: |
|
81 // HELPME: |
|
82 protected: |
|
83 ///\bug It must be public because of SymEdgeMap. |
|
84 /// |
|
85 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; |
|
86 ///\bug It must be public because of SymEdgeMap. |
|
87 /// |
|
88 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; |
|
89 |
74 |
90 public: |
75 public: |
91 |
76 |
92 class NodeIt; |
77 class NodeIt; |
93 class EdgeIt; |
78 class EdgeIt; |
94 class OutEdgeIt; |
79 class OutEdgeIt; |
95 class InEdgeIt; |
80 class InEdgeIt; |
96 |
81 |
97 public: |
82 CREATE_MAP_REGISTRIES; |
98 |
83 CREATE_MAPS(ArrayMapFactory); |
99 ListGraph() : nodes(), first_node(-1), |
84 |
100 first_free_node(-1), edges(), first_free_edge(-1) {} |
85 public: |
101 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node), |
86 |
102 first_free_node(_g.first_free_node), |
87 ListGraph() |
103 edges(_g.edges), |
88 : nodes(), first_node(-1), |
104 first_free_edge(_g.first_free_edge) {} |
89 first_free_node(-1), edges(), first_free_edge(-1) {} |
105 |
90 |
106 ~ListGraph() |
91 ListGraph(const ListGraph &_g) |
107 { |
92 : nodes(_g.nodes), first_node(_g.first_node), |
108 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
93 first_free_node(_g.first_free_node), edges(_g.edges), |
109 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
94 first_free_edge(_g.first_free_edge) {} |
110 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
95 |
111 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; |
|
112 } |
|
113 |
|
114 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
96 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
115 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
97 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
116 |
98 |
117 ///Set the expected number of edges |
99 ///Set the expected number of edges |
118 |
100 |
408 : Edge(_G.nodes[v.n].first_in), G(&_G) { } |
389 : Edge(_G.nodes[v.n].first_in), G(&_G) { } |
409 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
390 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
410 // ///Validity check |
391 // ///Validity check |
411 // operator bool() { return Edge::operator bool(); } |
392 // operator bool() { return Edge::operator bool(); } |
412 }; |
393 }; |
413 |
|
414 template <typename T> class NodeMap : public DynMapBase<Node> |
|
415 { |
|
416 std::vector<T> container; |
|
417 |
|
418 public: |
|
419 typedef T ValueType; |
|
420 typedef Node KeyType; |
|
421 |
|
422 NodeMap(const ListGraph &_G) : |
|
423 DynMapBase<Node>(_G), container(_G.maxNodeId()) |
|
424 { |
|
425 G->dyn_node_maps.push_back(this); |
|
426 } |
|
427 NodeMap(const ListGraph &_G,const T &t) : |
|
428 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) |
|
429 { |
|
430 G->dyn_node_maps.push_back(this); |
|
431 } |
|
432 |
|
433 NodeMap(const NodeMap<T> &m) : |
|
434 DynMapBase<Node>(*m.G), container(m.container) |
|
435 { |
|
436 G->dyn_node_maps.push_back(this); |
|
437 } |
|
438 |
|
439 template<typename TT> friend class NodeMap; |
|
440 |
|
441 ///\todo It can copy between different types. |
|
442 /// |
|
443 template<typename TT> NodeMap(const NodeMap<TT> &m) : |
|
444 DynMapBase<Node>(*m.G), container(m.container.size()) |
|
445 |
|
446 { |
|
447 G->dyn_node_maps.push_back(this); |
|
448 typename std::vector<TT>::const_iterator i; |
|
449 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
450 i!=m.container.end(); |
|
451 i++) |
|
452 container.push_back(*i); |
|
453 } |
|
454 ~NodeMap() |
|
455 { |
|
456 if(G) { |
|
457 std::vector<DynMapBase<Node>* >::iterator i; |
|
458 for(i=G->dyn_node_maps.begin(); |
|
459 i!=G->dyn_node_maps.end() && *i!=this; ++i) ; |
|
460 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... |
|
461 //A better way to do that: (Is this really important?) |
|
462 if(*i==this) { |
|
463 *i=G->dyn_node_maps.back(); |
|
464 G->dyn_node_maps.pop_back(); |
|
465 } |
|
466 } |
|
467 } |
|
468 |
|
469 void add(const Node k) |
|
470 { |
|
471 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
472 } |
|
473 |
|
474 void erase(const Node) { } |
|
475 |
|
476 void set(Node n, T a) { container[n.n]=a; } |
|
477 //'T& operator[](Node n)' would be wrong here |
|
478 typename std::vector<T>::reference |
|
479 operator[](Node n) { return container[n.n]; } |
|
480 //'const T& operator[](Node n)' would be wrong here |
|
481 typename std::vector<T>::const_reference |
|
482 operator[](Node n) const { return container[n.n]; } |
|
483 |
|
484 ///\warning There is no safety check at all! |
|
485 ///Using operator = between maps attached to different graph may |
|
486 ///cause serious problem. |
|
487 ///\todo Is this really so? |
|
488 ///\todo It can copy between different types. |
|
489 const NodeMap<T>& operator=(const NodeMap<T> &m) |
|
490 { |
|
491 container = m.container; |
|
492 return *this; |
|
493 } |
|
494 template<typename TT> |
|
495 const NodeMap<T>& operator=(const NodeMap<TT> &m) |
|
496 { |
|
497 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
498 return *this; |
|
499 } |
|
500 |
|
501 void update() {} //Useless for Dynamic Maps |
|
502 void update(T a) {} //Useless for Dynamic Maps |
|
503 }; |
|
504 |
|
505 template <typename T> class EdgeMap : public DynMapBase<Edge> |
|
506 { |
|
507 protected: |
|
508 std::vector<T> container; |
|
509 |
|
510 public: |
|
511 typedef T ValueType; |
|
512 typedef Edge KeyType; |
|
513 |
|
514 EdgeMap(const ListGraph &_G) : |
|
515 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) |
|
516 { |
|
517 //FIXME: What if there are empty Id's? |
|
518 //FIXME: Can I use 'this' in a constructor? |
|
519 G->dyn_edge_maps.push_back(this); |
|
520 } |
|
521 EdgeMap(const ListGraph &_G,const T &t) : |
|
522 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) |
|
523 { |
|
524 G->dyn_edge_maps.push_back(this); |
|
525 } |
|
526 EdgeMap(const EdgeMap<T> &m) : |
|
527 DynMapBase<Edge>(*m.G), container(m.container) |
|
528 { |
|
529 G->dyn_edge_maps.push_back(this); |
|
530 } |
|
531 |
|
532 template<typename TT> friend class EdgeMap; |
|
533 |
|
534 ///\todo It can copy between different types. |
|
535 /// |
|
536 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : |
|
537 DynMapBase<Edge>(*m.G), container(m.container.size()) |
|
538 { |
|
539 G->dyn_edge_maps.push_back(this); |
|
540 typename std::vector<TT>::const_iterator i; |
|
541 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
542 i!=m.container.end(); |
|
543 i++) |
|
544 container.push_back(*i); |
|
545 } |
|
546 ~EdgeMap() |
|
547 { |
|
548 if(G) { |
|
549 std::vector<DynMapBase<Edge>* >::iterator i; |
|
550 for(i=G->dyn_edge_maps.begin(); |
|
551 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; |
|
552 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
|
553 //A better way to do that: (Is this really important?) |
|
554 if(*i==this) { |
|
555 *i=G->dyn_edge_maps.back(); |
|
556 G->dyn_edge_maps.pop_back(); |
|
557 } |
|
558 } |
|
559 } |
|
560 |
|
561 void add(const Edge k) |
|
562 { |
|
563 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
564 } |
|
565 void erase(const Edge) { } |
|
566 |
|
567 void set(Edge n, T a) { container[n.n]=a; } |
|
568 //T get(Edge n) const { return container[n.n]; } |
|
569 typename std::vector<T>::reference |
|
570 operator[](Edge n) { return container[n.n]; } |
|
571 typename std::vector<T>::const_reference |
|
572 operator[](Edge n) const { return container[n.n]; } |
|
573 |
|
574 ///\warning There is no safety check at all! |
|
575 ///Using operator = between maps attached to different graph may |
|
576 ///cause serious problem. |
|
577 ///\todo Is this really so? |
|
578 ///\todo It can copy between different types. |
|
579 const EdgeMap<T>& operator=(const EdgeMap<T> &m) |
|
580 { |
|
581 container = m.container; |
|
582 return *this; |
|
583 } |
|
584 template<typename TT> |
|
585 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) |
|
586 { |
|
587 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
588 return *this; |
|
589 } |
|
590 |
|
591 void update() {} //Useless for DynMaps |
|
592 void update(T a) {} //Useless for DynMaps |
|
593 }; |
|
594 |
|
595 }; |
394 }; |
596 |
395 |
597 ///Graph for bidirectional edges. |
396 ///Graph for bidirectional edges. |
598 |
397 |
599 ///The purpose of this graph structure is to handle graphs |
398 ///The purpose of this graph structure is to handle graphs |
613 /// |
412 /// |
614 ///Here erase(Edge) deletes a pair of edges. |
413 ///Here erase(Edge) deletes a pair of edges. |
615 /// |
414 /// |
616 ///\todo this date structure need some reconsiderations. Maybe it |
415 ///\todo this date structure need some reconsiderations. Maybe it |
617 ///should be implemented independently from ListGraph. |
416 ///should be implemented independently from ListGraph. |
618 |
417 |
619 class SymListGraph : public ListGraph |
418 class SymListGraph : public ListGraph |
620 { |
419 { |
621 public: |
420 public: |
622 template<typename T> class SymEdgeMap; |
421 |
623 template<typename T> friend class SymEdgeMap; |
422 typedef SymListGraph Graph; |
|
423 |
|
424 KEEP_NODE_MAP(ListGraph); |
|
425 KEEP_EDGE_MAP(ListGraph); |
|
426 |
|
427 CREATE_SYM_EDGE_MAP_REGISTRY; |
|
428 CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory); |
|
429 IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory); |
624 |
430 |
625 SymListGraph() : ListGraph() { } |
431 SymListGraph() : ListGraph() { } |
626 SymListGraph(const ListGraph &_g) : ListGraph(_g) { } |
432 SymListGraph(const ListGraph &_g) : ListGraph(_g) { } |
627 ///Adds a pair of oppositely directed edges to the graph. |
433 ///Adds a pair of oppositely directed edges to the graph. |
628 Edge addEdge(Node u, Node v) |
434 Edge addEdge(Node u, Node v) |
629 { |
435 { |
630 Edge e = ListGraph::addEdge(u,v); |
436 Edge e = ListGraph::addEdge(u,v); |
631 ListGraph::addEdge(v,u); |
437 Edge f = ListGraph::addEdge(v,u); |
|
438 sym_edge_maps.add(e); |
|
439 sym_edge_maps.add(f); |
|
440 |
632 return e; |
441 return e; |
633 } |
442 } |
634 |
443 |
635 void erase(Node n) { ListGraph::erase(n); } |
444 void erase(Node n) { ListGraph::erase(n);} |
636 ///The oppositely directed edge. |
445 ///The oppositely directed edge. |
637 |
446 |
638 ///Returns the oppositely directed |
447 ///Returns the oppositely directed |
639 ///pair of the edge \c e. |
448 ///pair of the edge \c e. |
640 static Edge opposite(Edge e) |
449 static Edge opposite(Edge e) |
644 return f; |
453 return f; |
645 } |
454 } |
646 |
455 |
647 ///Removes a pair of oppositely directed edges to the graph. |
456 ///Removes a pair of oppositely directed edges to the graph. |
648 void erase(Edge e) { |
457 void erase(Edge e) { |
649 ListGraph::erase(opposite(e)); |
458 Edge f = opposite(e); |
|
459 sym_edge_maps.erase(e); |
|
460 sym_edge_maps.erase(f); |
|
461 ListGraph::erase(f); |
650 ListGraph::erase(e); |
462 ListGraph::erase(e); |
651 } |
463 } |
652 |
|
653 ///Common data storage for the edge pairs. |
|
654 |
|
655 ///This map makes it possible to store data shared by the oppositely |
|
656 ///directed pairs of edges. |
|
657 template <typename T> class SymEdgeMap : public DynMapBase<Edge> |
|
658 { |
|
659 std::vector<T> container; |
|
660 |
|
661 public: |
|
662 typedef T ValueType; |
|
663 typedef Edge KeyType; |
|
664 |
|
665 SymEdgeMap(const SymListGraph &_G) : |
|
666 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) |
|
667 { |
|
668 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this); |
|
669 } |
|
670 SymEdgeMap(const SymListGraph &_G,const T &t) : |
|
671 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) |
|
672 { |
|
673 G->dyn_edge_maps.push_back(this); |
|
674 } |
|
675 |
|
676 SymEdgeMap(const SymEdgeMap<T> &m) : |
|
677 DynMapBase<SymEdge>(*m.G), container(m.container) |
|
678 { |
|
679 G->dyn_node_maps.push_back(this); |
|
680 } |
|
681 |
|
682 // template<typename TT> friend class SymEdgeMap; |
|
683 |
|
684 ///\todo It can copy between different types. |
|
685 /// |
|
686 |
|
687 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) : |
|
688 DynMapBase<SymEdge>(*m.G), container(m.container.size()) |
|
689 { |
|
690 G->dyn_node_maps.push_back(this); |
|
691 typename std::vector<TT>::const_iterator i; |
|
692 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
693 i!=m.container.end(); |
|
694 i++) |
|
695 container.push_back(*i); |
|
696 } |
|
697 |
|
698 ~SymEdgeMap() |
|
699 { |
|
700 if(G) { |
|
701 std::vector<DynMapBase<Edge>* >::iterator i; |
|
702 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin(); |
|
703 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end() |
|
704 && *i!=this; ++i) ; |
|
705 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
|
706 //A better way to do that: (Is this really important?) |
|
707 if(*i==this) { |
|
708 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back(); |
|
709 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back(); |
|
710 } |
|
711 } |
|
712 } |
|
713 |
|
714 void add(const Edge k) |
|
715 { |
|
716 if(!k.idref()%2&&k.idref()/2>=int(container.size())) |
|
717 container.resize(k.idref()/2+1); |
|
718 } |
|
719 void erase(const Edge k) { } |
|
720 |
|
721 void set(Edge n, T a) { container[n.idref()/2]=a; } |
|
722 //T get(Edge n) const { return container[n.idref()/2]; } |
|
723 typename std::vector<T>::reference |
|
724 operator[](Edge n) { return container[n.idref()/2]; } |
|
725 typename std::vector<T>::const_reference |
|
726 operator[](Edge n) const { return container[n.idref()/2]; } |
|
727 |
|
728 ///\warning There is no safety check at all! |
|
729 ///Using operator = between maps attached to different graph may |
|
730 ///cause serious problem. |
|
731 ///\todo Is this really so? |
|
732 ///\todo It can copy between different types. |
|
733 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m) |
|
734 { |
|
735 container = m.container; |
|
736 return *this; |
|
737 } |
|
738 template<typename TT> |
|
739 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m) |
|
740 { |
|
741 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
742 return *this; |
|
743 } |
|
744 |
|
745 void update() {} //Useless for DynMaps |
|
746 void update(T a) {} //Useless for DynMaps |
|
747 |
|
748 }; |
|
749 |
|
750 }; |
464 }; |
751 |
465 |
752 |
466 |
753 ///A graph class containing only nodes. |
467 ///A graph class containing only nodes. |
754 |
468 |
755 ///This class implements a graph structure without edges. |
469 ///This class implements a graph structure without edges. |
756 ///The most useful application of this class is to be the node set of an |
470 ///The most useful application of this class is to be the node set of an |
777 //The first node |
491 //The first node |
778 int first_node; |
492 int first_node; |
779 //The first free node |
493 //The first free node |
780 int first_free_node; |
494 int first_free_node; |
781 |
495 |
782 protected: |
496 public: |
783 |
497 |
784 template <typename Key> class DynMapBase |
498 typedef NodeSet Graph; |
785 { |
|
786 protected: |
|
787 const NodeSet* G; |
|
788 public: |
|
789 virtual void add(const Key k) = 0; |
|
790 virtual void erase(const Key k) = 0; |
|
791 DynMapBase(const NodeSet &_G) : G(&_G) {} |
|
792 virtual ~DynMapBase() {} |
|
793 friend class NodeSet; |
|
794 }; |
|
795 |
|
796 public: |
|
797 template <typename T> class EdgeMap; |
|
798 template <typename T> class NodeMap; |
|
799 |
499 |
800 class Node; |
500 class Node; |
801 class Edge; |
501 class Edge; |
802 |
502 |
803 // protected: |
|
804 // HELPME: |
|
805 protected: |
|
806 ///\bug It must be public because of SymEdgeMap. |
|
807 /// |
|
808 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; |
|
809 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; |
|
810 |
|
811 public: |
503 public: |
812 |
504 |
813 class NodeIt; |
505 class NodeIt; |
814 class EdgeIt; |
506 class EdgeIt; |
815 class OutEdgeIt; |
507 class OutEdgeIt; |
816 class InEdgeIt; |
508 class InEdgeIt; |
817 |
509 |
818 template <typename T> class NodeMap; |
510 CREATE_MAP_REGISTRIES; |
819 template <typename T> class EdgeMap; |
511 CREATE_MAPS(ArrayMapFactory); |
820 |
512 |
821 public: |
513 public: |
822 |
514 |
823 ///Default constructor |
515 ///Default constructor |
824 NodeSet() : nodes(), first_node(-1), |
516 NodeSet() |
825 first_free_node(-1) {} |
517 : nodes(), first_node(-1), first_free_node(-1) {} |
826 ///Copy constructor |
518 ///Copy constructor |
827 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node), |
519 NodeSet(const NodeSet &_g) |
828 first_free_node(_g.first_free_node) {} |
520 : nodes(_g.nodes), first_node(_g.first_node), |
829 |
521 first_free_node(_g.first_free_node) {} |
830 ~NodeSet() |
522 |
831 { |
|
832 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
833 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
|
834 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
|
835 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; |
|
836 } |
|
837 |
|
838 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
523 int nodeNum() const { return nodes.size(); } //FIXME: What is this? |
839 int edgeNum() const { return 0; } //FIXME: What is this? |
524 int edgeNum() const { return 0; } //FIXME: What is this? |
840 |
525 |
841 ///\bug This function does something different than |
526 ///\bug This function does something different than |
842 ///its name would suggests... |
527 ///its name would suggests... |
1010 InEdgeIt (Invalid i) : Edge(i) { } |
692 InEdgeIt (Invalid i) : Edge(i) { } |
1011 InEdgeIt(const NodeSet& G,Node v) :Edge() {} |
693 InEdgeIt(const NodeSet& G,Node v) :Edge() {} |
1012 InEdgeIt operator++() { return INVALID; } |
694 InEdgeIt operator++() { return INVALID; } |
1013 }; |
695 }; |
1014 |
696 |
1015 template <typename T> class NodeMap : public DynMapBase<Node> |
|
1016 { |
|
1017 std::vector<T> container; |
|
1018 |
|
1019 public: |
|
1020 typedef T ValueType; |
|
1021 typedef Node KeyType; |
|
1022 |
|
1023 NodeMap(const NodeSet &_G) : |
|
1024 DynMapBase<Node>(_G), container(_G.maxNodeId()) |
|
1025 { |
|
1026 G->dyn_node_maps.push_back(this); |
|
1027 } |
|
1028 NodeMap(const NodeSet &_G,const T &t) : |
|
1029 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) |
|
1030 { |
|
1031 G->dyn_node_maps.push_back(this); |
|
1032 } |
|
1033 |
|
1034 NodeMap(const NodeMap<T> &m) : |
|
1035 DynMapBase<Node>(*m.G), container(m.container) |
|
1036 { |
|
1037 G->dyn_node_maps.push_back(this); |
|
1038 } |
|
1039 |
|
1040 template<typename TT> friend class NodeMap; |
|
1041 |
|
1042 ///\todo It can copy between different types. |
|
1043 /// |
|
1044 template<typename TT> NodeMap(const NodeMap<TT> &m) : |
|
1045 DynMapBase<Node>(*m.G), container(m.container.size()) |
|
1046 { |
|
1047 G->dyn_node_maps.push_back(this); |
|
1048 typename std::vector<TT>::const_iterator i; |
|
1049 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
1050 i!=m.container.end(); |
|
1051 i++) |
|
1052 container.push_back(*i); |
|
1053 } |
|
1054 ~NodeMap() |
|
1055 { |
|
1056 if(G) { |
|
1057 std::vector<DynMapBase<Node>* >::iterator i; |
|
1058 for(i=G->dyn_node_maps.begin(); |
|
1059 i!=G->dyn_node_maps.end() && *i!=this; ++i) ; |
|
1060 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... |
|
1061 //A better way to do that: (Is this really important?) |
|
1062 if(*i==this) { |
|
1063 *i=G->dyn_node_maps.back(); |
|
1064 G->dyn_node_maps.pop_back(); |
|
1065 } |
|
1066 } |
|
1067 } |
|
1068 |
|
1069 void add(const Node k) |
|
1070 { |
|
1071 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
1072 } |
|
1073 |
|
1074 void erase(const Node) { } |
|
1075 |
|
1076 void set(Node n, T a) { container[n.n]=a; } |
|
1077 //'T& operator[](Node n)' would be wrong here |
|
1078 typename std::vector<T>::reference |
|
1079 operator[](Node n) { return container[n.n]; } |
|
1080 //'const T& operator[](Node n)' would be wrong here |
|
1081 typename std::vector<T>::const_reference |
|
1082 operator[](Node n) const { return container[n.n]; } |
|
1083 |
|
1084 ///\warning There is no safety check at all! |
|
1085 ///Using operator = between maps attached to different graph may |
|
1086 ///cause serious problem. |
|
1087 ///\todo Is this really so? |
|
1088 ///\todo It can copy between different types. |
|
1089 const NodeMap<T>& operator=(const NodeMap<T> &m) |
|
1090 { |
|
1091 container = m.container; |
|
1092 return *this; |
|
1093 } |
|
1094 template<typename TT> |
|
1095 const NodeMap<T>& operator=(const NodeMap<TT> &m) |
|
1096 { |
|
1097 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
1098 return *this; |
|
1099 } |
|
1100 |
|
1101 void update() {} //Useless for Dynamic Maps |
|
1102 void update(T a) {} //Useless for Dynamic Maps |
|
1103 }; |
|
1104 |
|
1105 template <typename T> class EdgeMap |
|
1106 { |
|
1107 public: |
|
1108 typedef T ValueType; |
|
1109 typedef Edge KeyType; |
|
1110 |
|
1111 EdgeMap(const NodeSet &) { } |
|
1112 EdgeMap(const NodeSet &,const T &) { } |
|
1113 EdgeMap(const EdgeMap<T> &) { } |
|
1114 // template<typename TT> friend class EdgeMap; |
|
1115 |
|
1116 ///\todo It can copy between different types. |
|
1117 /// |
|
1118 template<typename TT> EdgeMap(const EdgeMap<TT> &) { } |
|
1119 ~EdgeMap() { } |
|
1120 |
|
1121 void add(const Edge ) { } |
|
1122 void erase(const Edge) { } |
|
1123 |
|
1124 void set(Edge, T) { } |
|
1125 //T get(Edge n) const { return container[n.n]; } |
|
1126 ValueType &operator[](Edge) { return *((T*)(NULL)); } |
|
1127 const ValueType &operator[](Edge) const { return *((T*)(NULL)); } |
|
1128 |
|
1129 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; } |
|
1130 |
|
1131 template<typename TT> |
|
1132 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; } |
|
1133 |
|
1134 void update() {} |
|
1135 void update(T a) {} |
|
1136 }; |
|
1137 }; |
697 }; |
1138 |
698 |
1139 |
699 |
1140 |
700 |
1141 ///Graph structure using a node set of another graph. |
701 ///Graph structure using a node set of another graph. |
1227 |
791 |
1228 std::vector<EdgeT> edges; |
792 std::vector<EdgeT> edges; |
1229 //The first free edge |
793 //The first free edge |
1230 int first_free_edge; |
794 int first_free_edge; |
1231 |
795 |
1232 protected: |
796 public: |
1233 |
|
1234 template <typename Key> class DynMapBase |
|
1235 { |
|
1236 protected: |
|
1237 const EdgeSet* G; |
|
1238 public: |
|
1239 virtual void add(const Key k) = 0; |
|
1240 virtual void erase(const Key k) = 0; |
|
1241 DynMapBase(const EdgeSet &_G) : G(&_G) {} |
|
1242 virtual ~DynMapBase() {} |
|
1243 friend class EdgeSet; |
|
1244 }; |
|
1245 |
|
1246 public: |
|
1247 //template <typename T> class NodeMap; |
|
1248 template <typename T> class EdgeMap; |
|
1249 |
797 |
1250 class Node; |
798 class Node; |
1251 class Edge; |
799 class Edge; |
1252 |
|
1253 // protected: |
|
1254 // HELPME: |
|
1255 protected: |
|
1256 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps; |
|
1257 ///\bug It must be public because of SymEdgeMap. |
|
1258 /// |
|
1259 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; |
|
1260 |
|
1261 public: |
|
1262 |
800 |
1263 class NodeIt; |
801 class NodeIt; |
1264 class EdgeIt; |
802 class EdgeIt; |
1265 class OutEdgeIt; |
803 class OutEdgeIt; |
1266 class InEdgeIt; |
804 class InEdgeIt; |
1267 |
805 |
1268 template <typename T> class NodeMap; |
806 |
1269 template <typename T> class EdgeMap; |
807 CREATE_EDGE_MAP_REGISTRY; |
|
808 CREATE_EDGE_MAP_FACTORY(ArrayMapFactory); |
|
809 IMPORT_EDGE_MAP(EdgeMapFactory); |
|
810 |
1270 |
811 |
1271 public: |
812 public: |
1272 |
813 |
1273 ///Constructor |
814 ///Constructor |
1274 |
815 |
1275 ///Construates a new graph based on the nodeset of an existing one. |
816 ///Construates a new graph based on the nodeset of an existing one. |
1276 ///\param _G the base graph. |
817 ///\param _G the base graph. |
1277 ///\todo It looks like a copy constructor, but it isn't. |
818 ///\todo It looks like a copy constructor, but it isn't. |
1278 EdgeSet(NodeGraphType &_G) : G(_G), |
819 EdgeSet(NodeGraphType &_G) |
1279 nodes(_G), edges(), |
820 : G(_G), nodes(_G), edges(), |
1280 first_free_edge(-1) { } |
821 first_free_edge(-1) {} |
1281 ///Copy constructor |
822 ///Copy constructor |
1282 |
823 |
1283 ///Makes a copy of an EdgeSet. |
824 ///Makes a copy of an EdgeSet. |
1284 ///It will be based on the same graph. |
825 ///It will be based on the same graph. |
1285 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), |
826 EdgeSet(const EdgeSet &_g) |
1286 first_free_edge(_g.first_free_edge) { } |
827 : G(_g.G), nodes(_g.G), edges(_g.edges), |
1287 |
828 first_free_edge(_g.first_free_edge) {} |
1288 ~EdgeSet() |
829 |
1289 { |
|
1290 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); |
|
1291 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; |
|
1292 for(typename std::vector<DynMapBase<Edge> * >::iterator |
|
1293 i=dyn_edge_maps.begin(); |
|
1294 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; |
|
1295 } |
|
1296 |
|
1297 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? |
830 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? |
1298 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
831 int edgeNum() const { return edges.size(); } //FIXME: What is this? |
1299 |
832 |
1300 ///\bug This function does something different than |
833 ///\bug This function does something different than |
1301 ///its name would suggests... |
834 ///its name would suggests... |
1503 InEdgeIt(const EdgeSet& _G,Node v) |
1022 InEdgeIt(const EdgeSet& _G,Node v) |
1504 : Edge(_G.nodes[v].first_in), G(&_G) { } |
1023 : Edge(_G.nodes[v].first_in), G(&_G) { } |
1505 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
1024 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
1506 }; |
1025 }; |
1507 |
1026 |
1508 template <typename T> class NodeMap : |
1027 |
1509 public NodeGraphType::template NodeMap<T> |
1028 template <typename V> class NodeMap |
|
1029 : public NodeGraphType::template NodeMap<V> |
1510 { |
1030 { |
1511 //This is a must, the constructors need it. |
1031 //This is a must, the constructors need it. |
1512 typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap; |
1032 typedef typename NodeGraphType::template NodeMap<V> MapImpl; |
1513 public: |
1033 typedef V Value; |
1514 NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { } |
1034 public: |
1515 NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { } |
1035 NodeMap() : MapImpl() {} |
1516 //It is unnecessary |
1036 |
1517 NodeMap(const typename NodeGraphType::template NodeMap<T> &m) : |
1037 NodeMap(const EdgeSet& graph) |
1518 ParentNodeMap(m) { } |
1038 : MapImpl(graph.G) { } |
1519 |
1039 |
1520 ///\todo It can copy between different types. |
1040 NodeMap(const EdgeSet& graph, const Value& value) |
1521 /// |
1041 : MapImpl(graph.G, value) { } |
1522 template<typename TT> |
1042 |
1523 NodeMap(const typename NodeGraphType::template NodeMap<TT> &m) |
1043 NodeMap(const NodeMap& copy) |
1524 : ParentNodeMap(m) { } |
1044 : MapImpl(static_cast<const MapImpl&>(copy)) {} |
1525 }; |
1045 |
1526 |
1046 template<typename CMap> |
1527 /// |
1047 NodeMap(const CMap& copy) |
1528 template <typename T> class EdgeMap : public DynMapBase<Edge> |
1048 : MapImpl(copy) { } |
1529 { |
1049 |
1530 protected: |
1050 NodeMap& operator=(const NodeMap& copy) { |
1531 public: |
1051 MapImpl::operator=(static_cast<const MapImpl&>(copy)); |
1532 ///\bug It should be at least protected |
|
1533 /// |
|
1534 std::vector<T> container; |
|
1535 |
|
1536 public: |
|
1537 typedef T ValueType; |
|
1538 typedef Edge KeyType; |
|
1539 |
|
1540 EdgeMap(const EdgeSet &_G) : |
|
1541 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) |
|
1542 { |
|
1543 //FIXME: What if there are empty Id's? |
|
1544 //FIXME: Can I use 'this' in a constructor? |
|
1545 this->G->dyn_edge_maps.push_back(this); |
|
1546 } |
|
1547 EdgeMap(const EdgeSet &_G,const T &t) : |
|
1548 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) |
|
1549 { |
|
1550 this->G->dyn_edge_maps.push_back(this); |
|
1551 } |
|
1552 EdgeMap(const EdgeMap<T> &m) : |
|
1553 DynMapBase<Edge>(*m.G), container(m.container) |
|
1554 { |
|
1555 this->G->dyn_edge_maps.push_back(this); |
|
1556 } |
|
1557 |
|
1558 ///\todo It can copy between different types. |
|
1559 /// |
|
1560 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : |
|
1561 DynMapBase<Edge>(*m.G), container(m.container.size()) |
|
1562 { |
|
1563 this->G->dyn_edge_maps.push_back(this); |
|
1564 typename std::vector<TT>::const_iterator i; |
|
1565 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
|
1566 i!=m.container.end(); |
|
1567 i++) |
|
1568 container.push_back(*i); |
|
1569 } |
|
1570 ~EdgeMap() |
|
1571 { |
|
1572 if(this->G) { |
|
1573 typename std::vector<DynMapBase<Edge>* >::iterator i; |
|
1574 for(i=this->G->dyn_edge_maps.begin(); |
|
1575 i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ; |
|
1576 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
|
1577 //A better way to do that: (Is this really important?) |
|
1578 if(*i==this) { |
|
1579 *i=this->G->dyn_edge_maps.back(); |
|
1580 this->G->dyn_edge_maps.pop_back(); |
|
1581 } |
|
1582 } |
|
1583 } |
|
1584 |
|
1585 void add(const Edge k) |
|
1586 { |
|
1587 if(k.n>=int(container.size())) container.resize(k.n+1); |
|
1588 } |
|
1589 void erase(const Edge) { } |
|
1590 |
|
1591 ///\bug This doesn't work. Why? |
|
1592 /// void set(Edge n, T a) { container[n.n]=a; } |
|
1593 void set(Edge n, T a) { container[this->G->id(n)]=a; } |
|
1594 //T get(Edge n) const { return container[n.n]; } |
|
1595 typename std::vector<T>::reference |
|
1596 ///\bug This doesn't work. Why? |
|
1597 /// operator[](Edge n) { return container[n.n]; } |
|
1598 operator[](Edge n) { return container[this->G->id(n)]; } |
|
1599 typename std::vector<T>::const_reference |
|
1600 ///\bug This doesn't work. Why? |
|
1601 /// operator[](Edge n) const { return container[n.n]; } |
|
1602 operator[](Edge n) const { return container[this->G->id(n)]; } |
|
1603 |
|
1604 ///\warning There is no safety check at all! |
|
1605 ///Using operator = between maps attached to different graph may |
|
1606 ///cause serious problem. |
|
1607 ///\todo Is this really so? |
|
1608 ///\todo It can copy between different types. |
|
1609 const EdgeMap<T>& operator=(const EdgeMap<T> &m) |
|
1610 { |
|
1611 container = m.container; |
|
1612 return *this; |
1052 return *this; |
1613 } |
1053 } |
1614 |
1054 |
1615 template<typename TT> friend class EdgeMap; |
1055 template <typename CMap> |
1616 |
1056 NodeMap& operator=(const CMap& copy) { |
1617 template<typename TT> |
1057 MapImpl::operator=(copy); |
1618 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) |
|
1619 { |
|
1620 std::copy(m.container.begin(), m.container.end(), container.begin()); |
|
1621 return *this; |
1058 return *this; |
1622 } |
1059 } |
1623 |
1060 |
1624 void update() {} //Useless for DynMaps |
1061 }; |
1625 void update(T a) {} //Useless for DynMaps |
|
1626 }; |
|
1627 |
|
1628 }; |
1062 }; |
1629 |
1063 |
1630 template<typename GG> |
1064 template<typename GG> |
1631 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); } |
1065 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); } |
1632 |
1066 |