Changeset 701:c03e073b8394 in lemon-0.x for src/work/deba
- Timestamp:
- 07/14/04 12:06:27 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@952
- Location:
- src/work/deba
- Files:
-
- 1 added
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/deba/list_graph.h
r698 r701 396 396 ///should be implemented independently from ListGraph. 397 397 398 }; 399 400 401 ///A graph class containing only nodes. 402 403 ///This class implements a graph structure without edges. 404 ///The most useful application of this class is to be the node set of an 405 ///\ref EdgeSet class. 406 /// 407 ///It conforms to the graph interface documented under 408 ///the description of \ref GraphSkeleton with the exception that you cannot 409 ///add (or delete) edges. The usual edge iterators are exists, but they are 410 ///always \ref INVALID. 411 ///\sa \ref GraphSkeleton 412 ///\sa \ref EdgeSet 413 class NodeSet { 414 415 //Nodes are double linked. 416 //The free nodes are only single linked using the "next" field. 417 struct NodeT 418 { 419 int first_in,first_out; 420 int prev, next; 421 // NodeT() {} 422 }; 423 424 std::vector<NodeT> nodes; 425 //The first node 426 int first_node; 427 //The first free node 428 int first_free_node; 429 430 protected: 431 432 template <typename Key> class DynMapBase 433 { 434 protected: 435 const NodeSet* G; 436 public: 437 virtual void add(const Key k) = 0; 438 virtual void erase(const Key k) = 0; 439 DynMapBase(const NodeSet &_G) : G(&_G) {} 440 virtual ~DynMapBase() {} 441 friend class NodeSet; 442 }; 443 444 public: 445 template <typename T> class EdgeMap; 446 template <typename T> class NodeMap; 447 448 class Node; 449 class Edge; 450 451 // protected: 452 // HELPME: 453 protected: 454 ///\bug It must be public because of SymEdgeMap. 455 /// 456 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 457 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 458 459 public: 460 461 class NodeIt; 462 class EdgeIt; 463 class OutEdgeIt; 464 class InEdgeIt; 465 466 template <typename T> class NodeMap; 467 template <typename T> class EdgeMap; 468 469 public: 470 471 ///Default constructor 472 NodeSet() : nodes(), first_node(-1), 473 first_free_node(-1) {} 474 ///Copy constructor 475 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node), 476 first_free_node(_g.first_free_node) {} 477 478 ~NodeSet() 479 { 480 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 481 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 482 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 483 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 484 } 485 486 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 487 int edgeNum() const { return 0; } //FIXME: What is this? 488 489 ///\bug This function does something different than 490 ///its name would suggests... 491 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? 492 ///\bug This function does something different than 493 ///its name would suggests... 494 int maxEdgeId() const { return 0; } //FIXME: What is this? 495 496 Node tail(Edge e) const { return INVALID; } 497 Node head(Edge e) const { return INVALID; } 498 499 Node aNode(OutEdgeIt e) const { return INVALID; } 500 Node aNode(InEdgeIt e) const { return INVALID; } 501 502 Node bNode(OutEdgeIt e) const { return INVALID; } 503 Node bNode(InEdgeIt e) const { return INVALID; } 504 505 NodeIt& first(NodeIt& v) const { 506 v=NodeIt(*this); return v; } 507 EdgeIt& first(EdgeIt& e) const { 508 e=EdgeIt(*this); return e; } 509 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 510 e=OutEdgeIt(*this,v); return e; } 511 InEdgeIt& first(InEdgeIt& e, const Node v) const { 512 e=InEdgeIt(*this,v); return e; } 513 514 // template< typename It > 515 // It first() const { It e; first(e); return e; } 516 517 // template< typename It > 518 // It first(Node v) const { It e; first(e,v); return e; } 519 520 bool valid(Edge e) const { return false; } 521 bool valid(Node n) const { return n.n!=-1; } 522 523 void setInvalid(Edge &e) { } 524 void setInvalid(Node &n) { n.n=-1; } 525 526 template <typename It> It getNext(It it) const 527 { It tmp(it); return next(tmp); } 528 529 NodeIt& next(NodeIt& it) const { 530 it.n=nodes[it.n].next; 531 return it; 532 } 533 OutEdgeIt& next(OutEdgeIt& it) const { return it; } 534 InEdgeIt& next(InEdgeIt& it) const { return it; } 535 EdgeIt& next(EdgeIt& it) const { return it; } 536 537 int id(Node v) const { return v.n; } 538 int id(Edge e) const { return -1; } 539 540 /// Adds a new node to the graph. 541 542 /// \todo It adds the nodes in a reversed order. 543 /// (i.e. the lastly added node becomes the first.) 544 Node addNode() { 545 int n; 546 547 if(first_free_node==-1) 548 { 549 n = nodes.size(); 550 nodes.push_back(NodeT()); 551 } 552 else { 553 n = first_free_node; 554 first_free_node = nodes[n].next; 555 } 556 557 nodes[n].next = first_node; 558 if(first_node != -1) nodes[first_node].prev = n; 559 first_node = n; 560 nodes[n].prev = -1; 561 562 nodes[n].first_in = nodes[n].first_out = -1; 563 564 Node nn; nn.n=n; 565 566 //Update dynamic maps 567 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 568 i!=dyn_node_maps.end(); ++i) (**i).add(nn); 569 570 return nn; 571 } 572 573 void erase(Node nn) { 574 int n=nn.n; 575 576 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; 577 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; 578 else first_node = nodes[n].next; 579 580 nodes[n].next = first_free_node; 581 first_free_node = n; 582 583 //Update dynamic maps 584 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 585 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); 586 } 587 588 ///\bug Dynamic maps must be updated! 589 /// 590 void clear() { 591 nodes.clear(); 592 first_node = first_free_node = -1; 593 } 594 595 class Node { 596 friend class NodeSet; 597 template <typename T> friend class NodeMap; 598 599 friend class Edge; 600 friend class OutEdgeIt; 601 friend class InEdgeIt; 602 603 protected: 604 int n; 605 friend int NodeSet::id(Node v) const; 606 Node(int nn) {n=nn;} 607 public: 608 Node() {} 609 Node (Invalid i) { n=-1; } 610 bool operator==(const Node i) const {return n==i.n;} 611 bool operator!=(const Node i) const {return n!=i.n;} 612 bool operator<(const Node i) const {return n<i.n;} 613 }; 614 615 class NodeIt : public Node { 616 friend class NodeSet; 617 public: 618 NodeIt() : Node() { } 619 NodeIt(Invalid i) : Node(i) { } 620 NodeIt(const NodeSet& G) : Node(G.first_node) { } 621 ///\todo Undocumented conversion Node -\> NodeIt. 622 NodeIt(const NodeSet& G, const Node &n) : Node(n) { } 623 624 }; 625 626 class Edge { 627 //friend class NodeSet; 628 //template <typename T> friend class EdgeMap; 629 630 //template <typename T> friend class SymNodeSet::SymEdgeMap; 631 //friend Edge SymNodeSet::opposite(Edge) const; 632 633 // friend class Node; 634 // friend class NodeIt; 635 protected: 636 //friend int NodeSet::id(Edge e) const; 637 // Edge(int nn) {} 638 public: 639 Edge() { } 640 Edge (Invalid) { } 641 bool operator==(const Edge i) const {return true;} 642 bool operator!=(const Edge i) const {return false;} 643 bool operator<(const Edge i) const {return false;} 644 ///\bug This is a workaround until somebody tells me how to 645 ///make class \c SymNodeSet::SymEdgeMap friend of Edge 646 // int idref() {return -1;} 647 // int idref() const {return -1;} 648 }; 649 650 class EdgeIt : public Edge { 651 //friend class NodeSet; 652 public: 653 EdgeIt(const NodeSet& G) : Edge() { } 654 EdgeIt (Invalid i) : Edge(i) { } 655 EdgeIt() : Edge() { } 656 ///\bug This is a workaround until somebody tells me how to 657 ///make class \c SymNodeSet::SymEdgeMap friend of Edge 658 // int idref() {return -1;} 659 }; 660 661 class OutEdgeIt : public Edge { 662 friend class NodeSet; 663 public: 664 OutEdgeIt() : Edge() { } 665 OutEdgeIt (Invalid i) : Edge(i) { } 666 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} 667 }; 668 669 class InEdgeIt : public Edge { 670 friend class NodeSet; 671 public: 672 InEdgeIt() : Edge() { } 673 InEdgeIt (Invalid i) : Edge(i) { } 674 InEdgeIt(const NodeSet& G,Node v) :Edge() {} 675 }; 676 677 template <typename T> class NodeMap : public DynMapBase<Node> 678 { 679 std::vector<T> container; 680 681 public: 682 typedef T ValueType; 683 typedef Node KeyType; 684 685 NodeMap(const NodeSet &_G) : 686 DynMapBase<Node>(_G), container(_G.maxNodeId()) 687 { 688 G->dyn_node_maps.push_back(this); 689 } 690 NodeMap(const NodeSet &_G,const T &t) : 691 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) 692 { 693 G->dyn_node_maps.push_back(this); 694 } 695 696 NodeMap(const NodeMap<T> &m) : 697 DynMapBase<Node>(*m.G), container(m.container) 698 { 699 G->dyn_node_maps.push_back(this); 700 } 701 702 template<typename TT> friend class NodeMap; 703 704 ///\todo It can copy between different types. 705 /// 706 template<typename TT> NodeMap(const NodeMap<TT> &m) : 707 DynMapBase<Node>(*m.G), container(m.container.size()) 708 { 709 G->dyn_node_maps.push_back(this); 710 typename std::vector<TT>::const_iterator i; 711 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 712 i!=m.container.end(); 713 i++) 714 container.push_back(*i); 715 } 716 ~NodeMap() 717 { 718 if(G) { 719 std::vector<DynMapBase<Node>* >::iterator i; 720 for(i=G->dyn_node_maps.begin(); 721 i!=G->dyn_node_maps.end() && *i!=this; ++i) ; 722 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... 723 //A better way to do that: (Is this really important?) 724 if(*i==this) { 725 *i=G->dyn_node_maps.back(); 726 G->dyn_node_maps.pop_back(); 727 } 728 } 729 } 730 731 void add(const Node k) 732 { 733 if(k.n>=int(container.size())) container.resize(k.n+1); 734 } 735 736 void erase(const Node) { } 737 738 void set(Node n, T a) { container[n.n]=a; } 739 //'T& operator[](Node n)' would be wrong here 740 typename std::vector<T>::reference 741 operator[](Node n) { return container[n.n]; } 742 //'const T& operator[](Node n)' would be wrong here 743 typename std::vector<T>::const_reference 744 operator[](Node n) const { return container[n.n]; } 745 746 ///\warning There is no safety check at all! 747 ///Using operator = between maps attached to different graph may 748 ///cause serious problem. 749 ///\todo Is this really so? 750 ///\todo It can copy between different types. 751 const NodeMap<T>& operator=(const NodeMap<T> &m) 752 { 753 container = m.container; 754 return *this; 755 } 756 template<typename TT> 757 const NodeMap<T>& operator=(const NodeMap<TT> &m) 758 { 759 std::copy(m.container.begin(), m.container.end(), container.begin()); 760 return *this; 761 } 762 763 void update() {} //Useless for Dynamic Maps 764 void update(T a) {} //Useless for Dynamic Maps 765 }; 766 767 template <typename T> class EdgeMap 768 { 769 public: 770 typedef T ValueType; 771 typedef Edge KeyType; 772 773 EdgeMap(const NodeSet &) { } 774 EdgeMap(const NodeSet &,const T &) { } 775 EdgeMap(const EdgeMap<T> &) { } 776 // template<typename TT> friend class EdgeMap; 777 778 ///\todo It can copy between different types. 779 /// 780 template<typename TT> EdgeMap(const EdgeMap<TT> &) { } 781 ~EdgeMap() { } 782 783 void add(const Edge ) { } 784 void erase(const Edge) { } 785 786 void set(Edge, T) { } 787 //T get(Edge n) const { return container[n.n]; } 788 ValueType &operator[](Edge) { return *((T*)(NULL)); } 789 const ValueType &operator[](Edge) const { return *((T*)(NULL)); } 790 791 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; } 792 793 template<typename TT> 794 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; } 795 796 void update() {} 797 void update(T a) {} 798 }; 799 }; 800 801 802 803 ///Graph structure using a node set of another graph. 804 805 ///This structure can be used to establish another graph over a node set 806 /// of an existing one. The node iterator will go through the nodes of the 807 /// original graph, and the NodeMap's of both graphs will convert to 808 /// each other. 809 /// 810 ///\warning Adding or deleting nodes from the graph is not safe if an 811 ///\ref EdgeSet is currently attached to it! 812 /// 813 ///\todo Make it possible to add/delete edges from the base graph 814 ///(and from \ref EdgeSet, as well) 815 /// 816 ///\param GG The type of the graph which shares its node set with this class. 817 ///Its interface must conform with \ref GraphSkeleton. 818 /// 819 ///It conforms to the graph interface documented under 820 ///the description of \ref GraphSkeleton. 821 ///\sa \ref GraphSkeleton. 822 ///\sa \ref NodeSet. 823 template<typename GG> 824 class EdgeSet { 825 826 typedef GG NodeGraphType; 827 828 NodeGraphType &G; 829 830 public: 831 class Node; 832 int id(Node v) const; 833 834 class Node : public NodeGraphType::Node { 835 friend class EdgeSet; 836 // template <typename T> friend class NodeMap; 837 838 friend class Edge; 839 friend class OutEdgeIt; 840 friend class InEdgeIt; 841 friend class SymEdge; 842 843 public: 844 friend int EdgeSet::id(Node v) const; 845 // Node(int nn) {n=nn;} 846 public: 847 Node() : NodeGraphType::Node() {} 848 Node (Invalid i) : NodeGraphType::Node(i) {} 849 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {} 850 }; 851 852 class NodeIt : public NodeGraphType::NodeIt { 853 friend class EdgeSet; 854 public: 855 NodeIt() : NodeGraphType::NodeIt() { } 856 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} 857 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } 858 NodeIt(const typename NodeGraphType::NodeIt &n) 859 : NodeGraphType::NodeIt(n) {} 860 ///\todo Undocumented conversion Node -\> NodeIt. 861 NodeIt(const EdgeSet& _G, const Node &n) 862 : NodeGraphType::NodeIt(_G.G,n) { } 863 864 operator Node() { return Node(*this);} 865 }; 866 867 private: 868 //Edges are double linked. 869 //The free edges are only single linked using the "next_in" field. 870 struct NodeT 871 { 872 int first_in,first_out; 873 NodeT() : first_in(-1), first_out(-1) { } 874 }; 875 876 struct EdgeT 877 { 878 Node head, tail; 879 int prev_in, prev_out; 880 int next_in, next_out; 881 }; 882 883 884 typename NodeGraphType::template NodeMap<NodeT> nodes; 885 886 std::vector<EdgeT> edges; 887 //The first free edge 888 int first_free_edge; 889 890 protected: 891 892 template <typename Key> class DynMapBase 893 { 894 protected: 895 const EdgeSet* G; 896 public: 897 virtual void add(const Key k) = 0; 898 virtual void erase(const Key k) = 0; 899 DynMapBase(const EdgeSet &_G) : G(&_G) {} 900 virtual ~DynMapBase() {} 901 friend class EdgeSet; 902 }; 903 904 public: 905 //template <typename T> class NodeMap; 906 template <typename T> class EdgeMap; 907 908 class Node; 909 class Edge; 910 911 // protected: 912 // HELPME: 913 protected: 914 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 915 ///\bug It must be public because of SymEdgeMap. 916 /// 917 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 918 919 public: 920 921 class NodeIt; 922 class EdgeIt; 923 class OutEdgeIt; 924 class InEdgeIt; 925 926 template <typename T> class NodeMap; 927 template <typename T> class EdgeMap; 928 929 public: 930 931 ///Constructor 932 933 ///Construates a new graph based on the nodeset of an existing one. 934 ///\param _G the base graph. 935 ///\todo It looks like a copy constructor, but it isn't. 936 EdgeSet(NodeGraphType &_G) : G(_G), 937 nodes(_G), edges(), 938 first_free_edge(-1) { } 939 ///Copy constructor 940 941 ///Makes a copy of an EdgeSet. 942 ///It will be based on the same graph. 943 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), 944 first_free_edge(_g.first_free_edge) { } 945 946 ~EdgeSet() 947 { 948 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 949 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 950 for(typename std::vector<DynMapBase<Edge> * >::iterator 951 i=dyn_edge_maps.begin(); 952 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 953 } 954 955 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? 956 int edgeNum() const { return edges.size(); } //FIXME: What is this? 957 958 ///\bug This function does something different than 959 ///its name would suggests... 960 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this? 961 ///\bug This function does something different than 962 ///its name would suggests... 963 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? 964 965 Node tail(Edge e) const { return edges[e.n].tail; } 966 Node head(Edge e) const { return edges[e.n].head; } 967 968 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } 969 Node aNode(InEdgeIt e) const { return edges[e.n].head; } 970 971 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } 972 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } 973 974 NodeIt& first(NodeIt& v) const { 975 v=NodeIt(*this); return v; } 976 EdgeIt& first(EdgeIt& e) const { 977 e=EdgeIt(*this); return e; } 978 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 979 e=OutEdgeIt(*this,v); return e; } 980 InEdgeIt& first(InEdgeIt& e, const Node v) const { 981 e=InEdgeIt(*this,v); return e; } 982 983 // template< typename It > 984 // It first() const { It e; first(e); return e; } 985 986 // template< typename It > 987 // It first(Node v) const { It e; first(e,v); return e; } 988 989 bool valid(Edge e) const { return e.n!=-1; } 990 bool valid(Node n) const { return G.valid(n); } 991 992 void setInvalid(Edge &e) { e.n=-1; } 993 void setInvalid(Node &n) { G.setInvalid(n); } 994 995 template <typename It> It getNext(It it) const 996 { It tmp(it); return next(tmp); } 997 998 NodeIt& next(NodeIt& it) const { G.next(it); return it; } 999 OutEdgeIt& next(OutEdgeIt& it) const 1000 { it.n=edges[it.n].next_out; return it; } 1001 InEdgeIt& next(InEdgeIt& it) const 1002 { it.n=edges[it.n].next_in; return it; } 1003 EdgeIt& next(EdgeIt& it) const { 1004 if(edges[it.n].next_in!=-1) { 1005 it.n=edges[it.n].next_in; 1006 } 1007 else { 1008 NodeIt n(*this,edges[it.n].head); 1009 for(n=next(n); 1010 valid(n) && nodes[n].first_in == -1; 1011 next(n)) ; 1012 it.n = (valid(n))?-1:nodes[n].first_in; 1013 } 1014 return it; 1015 } 1016 1017 int id(Edge e) const { return e.n; } 1018 1019 /// Adds a new node to the graph. 1020 Node addNode() { return G.addNode(); } 1021 1022 Edge addEdge(Node u, Node v) { 1023 int n; 1024 1025 if(first_free_edge==-1) 1026 { 1027 n = edges.size(); 1028 edges.push_back(EdgeT()); 1029 } 1030 else { 1031 n = first_free_edge; 1032 first_free_edge = edges[n].next_in; 1033 } 1034 1035 edges[n].tail = u; edges[n].head = v; 1036 1037 edges[n].next_out = nodes[u].first_out; 1038 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n; 1039 edges[n].next_in = nodes[v].first_in; 1040 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n; 1041 edges[n].prev_in = edges[n].prev_out = -1; 1042 1043 nodes[u].first_out = nodes[v].first_in = n; 1044 1045 Edge e; e.n=n; 1046 1047 //Update dynamic maps 1048 for(typename std::vector<DynMapBase<Edge> * >::iterator 1049 i=dyn_edge_maps.begin(); 1050 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 1051 1052 return e; 1053 } 1054 1055 private: 1056 void eraseEdge(int n) { 1057 1058 if(edges[n].next_in!=-1) 1059 edges[edges[n].next_in].prev_in = edges[n].prev_in; 1060 if(edges[n].prev_in!=-1) 1061 edges[edges[n].prev_in].next_in = edges[n].next_in; 1062 else nodes[edges[n].head].first_in = edges[n].next_in; 1063 1064 if(edges[n].next_out!=-1) 1065 edges[edges[n].next_out].prev_out = edges[n].prev_out; 1066 if(edges[n].prev_out!=-1) 1067 edges[edges[n].prev_out].next_out = edges[n].next_out; 1068 else nodes[edges[n].tail].first_out = edges[n].next_out; 1069 1070 edges[n].next_in = first_free_edge; 1071 first_free_edge = -1; 1072 1073 //Update dynamic maps 1074 Edge e; e.n=n; 1075 for(typename std::vector<DynMapBase<Edge> * >::iterator 1076 i=dyn_edge_maps.begin(); 1077 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); 1078 } 1079 1080 public: 1081 1082 // void erase(Node nn) { 1083 // int n=nn.n; 1084 // int m; 1085 // while((m=nodes[n].first_in)!=-1) eraseEdge(m); 1086 // while((m=nodes[n].first_out)!=-1) eraseEdge(m); 1087 // } 1088 1089 void erase(Edge e) { eraseEdge(e.n); } 1090 1091 ///Clear all edges. (Doesn't clear the nodes!) 1092 void clear() { 1093 edges.clear(); 1094 first_free_edge=-1; 1095 } 1096 1097 1098 // //\bug Dynamic maps must be updated! 1099 // // 1100 // void clear() { 1101 // nodes.clear();edges.clear(); 1102 // first_node=first_free_node=first_free_edge=-1; 1103 // } 1104 1105 public: 1106 template <typename T> class EdgeMap; 1107 1108 /// 1109 class Edge { 1110 public: 1111 friend class EdgeSet; 1112 template <typename T> friend class EdgeMap; 1113 1114 friend class Node; 1115 friend class NodeIt; 1116 public: 1117 ///\bug It shoud be at least protected 1118 /// 1119 int n; 1120 protected: 1121 friend int EdgeSet::id(Edge e) const; 1122 1123 Edge(int nn) {n=nn;} 1124 public: 1125 Edge() { } 1126 Edge (Invalid) { n=-1; } 1127 bool operator==(const Edge i) const {return n==i.n;} 1128 bool operator!=(const Edge i) const {return n!=i.n;} 1129 bool operator<(const Edge i) const {return n<i.n;} 1130 ///\bug This is a workaround until somebody tells me how to 1131 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge 1132 int &idref() {return n;} 1133 const int &idref() const {return n;} 1134 }; 1135 1136 class EdgeIt : public Edge { 1137 friend class EdgeSet; 1138 template <typename T> friend class EdgeMap; 1139 1140 1141 public: 1142 EdgeIt(const EdgeSet& G) : Edge() { 1143 // typename NodeGraphType::Node m; 1144 NodeIt m; 1145 for(G.first(m); 1146 G.valid(m) && G.nodes[m].first_in == -1; G.next(m)); 1147 //AJJAJ! This is a non sense!!!!!!! 1148 this->n = G.valid(m)?-1:G.nodes[m].first_in; 1149 } 1150 EdgeIt (Invalid i) : Edge(i) { } 1151 EdgeIt() : Edge() { } 1152 ///\bug This is a workaround until somebody tells me how to 1153 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge 1154 int &idref() {return this->n;} 1155 }; 1156 1157 class OutEdgeIt : public Edge { 1158 friend class EdgeSet; 1159 public: 1160 OutEdgeIt() : Edge() { } 1161 OutEdgeIt (Invalid i) : Edge(i) { } 1162 1163 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { } 1164 }; 1165 1166 class InEdgeIt : public Edge { 1167 friend class EdgeSet; 1168 public: 1169 InEdgeIt() : Edge() { } 1170 InEdgeIt (Invalid i) : Edge(i) { } 1171 InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { } 1172 }; 1173 1174 template <typename T> class NodeMap : 1175 public NodeGraphType::template NodeMap<T> 1176 { 1177 //This is a must, the constructors need it. 1178 typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap; 1179 public: 1180 NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { } 1181 NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { } 1182 //It is unnecessary 1183 NodeMap(const typename NodeGraphType::template NodeMap<T> &m) : 1184 ParentNodeMap(m) { } 1185 1186 ///\todo It can copy between different types. 1187 /// 1188 template<typename TT> 1189 NodeMap(const typename NodeGraphType::template NodeMap<TT> &m) 1190 : ParentNodeMap(m) { } 1191 }; 1192 1193 /// 1194 template <typename T> class EdgeMap : public DynMapBase<Edge> 1195 { 1196 protected: 1197 public: 1198 ///\bug It should be at least protected 1199 /// 1200 std::vector<T> container; 1201 1202 public: 1203 typedef T ValueType; 1204 typedef Edge KeyType; 1205 1206 EdgeMap(const EdgeSet &_G) : 1207 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) 1208 { 1209 //FIXME: What if there are empty Id's? 1210 //FIXME: Can I use 'this' in a constructor? 1211 G->dyn_edge_maps.push_back(this); 1212 } 1213 EdgeMap(const EdgeSet &_G,const T &t) : 1214 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) 1215 { 1216 G->dyn_edge_maps.push_back(this); 1217 } 1218 EdgeMap(const EdgeMap<T> &m) : 1219 DynMapBase<Edge>(*m.G), container(m.container) 1220 { 1221 G->dyn_edge_maps.push_back(this); 1222 } 1223 1224 template<typename TT> friend class EdgeMap; 1225 1226 ///\todo It can copy between different types. 1227 /// 1228 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : 1229 DynMapBase<Edge>(*m.G), container(m.container.size()) 1230 { 1231 G->dyn_edge_maps.push_back(this); 1232 typename std::vector<TT>::const_iterator i; 1233 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 1234 i!=m.container.end(); 1235 i++) 1236 container.push_back(*i); 1237 } 1238 ~EdgeMap() 1239 { 1240 if(G) { 1241 typename std::vector<DynMapBase<Edge>* >::iterator i; 1242 for(i=G->dyn_edge_maps.begin(); 1243 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; 1244 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... 1245 //A better way to do that: (Is this really important?) 1246 if(*i==this) { 1247 *i=G->dyn_edge_maps.back(); 1248 G->dyn_edge_maps.pop_back(); 1249 } 1250 } 1251 } 1252 1253 void add(const Edge k) 1254 { 1255 if(k.n>=int(container.size())) container.resize(k.n+1); 1256 } 1257 void erase(const Edge) { } 1258 1259 ///\bug This doesn't work. Why? 1260 /// void set(Edge n, T a) { container[n.n]=a; } 1261 void set(Edge n, T a) { container[G->id(n)]=a; } 1262 //T get(Edge n) const { return container[n.n]; } 1263 typename std::vector<T>::reference 1264 ///\bug This doesn't work. Why? 1265 /// operator[](Edge n) { return container[n.n]; } 1266 operator[](Edge n) { return container[G->id(n)]; } 1267 typename std::vector<T>::const_reference 1268 ///\bug This doesn't work. Why? 1269 /// operator[](Edge n) const { return container[n.n]; } 1270 operator[](Edge n) const { return container[G->id(n)]; } 1271 1272 ///\warning There is no safety check at all! 1273 ///Using operator = between maps attached to different graph may 1274 ///cause serious problem. 1275 ///\todo Is this really so? 1276 ///\todo It can copy between different types. 1277 const EdgeMap<T>& operator=(const EdgeMap<T> &m) 1278 { 1279 container = m.container; 1280 return *this; 1281 } 1282 1283 template<typename TT> friend class EdgeMap; 1284 1285 template<typename TT> 1286 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) 1287 { 1288 std::copy(m.container.begin(), m.container.end(), container.begin()); 1289 return *this; 1290 } 1291 1292 void update() {} //Useless for DynMaps 1293 void update(T a) {} //Useless for DynMaps 1294 }; 1295 1296 }; 1297 1298 template<typename GG> 1299 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); } 1300 1301 /// @} 1302 1303 } //namespace hugo 398 } 1304 399 1305 400 #endif //HUGO_LIST_GRAPH_H -
src/work/deba/main.cpp
r698 r701 12 12 ListGraph::Node node = g.addNode(); 13 13 } 14 ListGraph::NodeMap<int> map(g );14 ListGraph::NodeMap<int> map(g, 10); 15 15 for (int i = 0; i < 10; ++i) { 16 16 ListGraph::Node node = g.addNode(); … … 20 20 cout << map[it] << endl; 21 21 } 22 ListGraph::NodeMap<int>::iterator pit; 23 for (pit = map.begin(); pit != map.end(); ++pit) { 24 cout << g.id(pit->first) << ' ' << pit->second << endl; 25 } 26 ListGraph::NodeMap<double> ot_map = map; 27 for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) { 28 ot_map[it] *= 2.1; 29 cout << ot_map[it] << endl; 30 } 31 ot_map = map; 32 for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) { 33 ot_map[it] *= 3.1; 34 cout << ot_map[it] << endl; 35 } 22 36 return 0; 23 37 } -
src/work/deba/map_defines.h
r676 r701 3 3 #define MAP_DEFINES_H 4 4 5 /** Creates the EdgeMapRegistry type an declare a mutable instance 6 * named edge_maps. 7 */ 5 8 #define CREATE_EDGE_MAP_REGISTRY \ 6 9 typedef MapRegistry<Graph, Edge, EdgeIt> EdgeMapRegistry; \ 7 EdgeMapRegistry edge_maps;10 mutable EdgeMapRegistry edge_maps; 8 11 12 /** Creates the NodeMapRegistry type an declare a mutable instance 13 * named node_maps. 14 */ 9 15 #define CREATE_NODE_MAP_REGISTRY \ 10 16 typedef MapRegistry<Graph, Node, NodeIt> NodeMapRegistry; \ 11 NodeMapRegistry node_maps;17 mutable NodeMapRegistry node_maps; 12 18 19 /** Creates both map registries. 20 */ 13 21 #define CREATE_MAP_REGISTRIES \ 14 22 CREATE_NODE_MAP_REGISTRY \ 15 23 CREATE_EDGE_MAP_REGISTRY 16 24 25 /** Creates a map a concrete factory type from a template map 26 * factory to use as node map factory. 27 */ 17 28 #define CREATE_NODE_MAP_FACTORY(TemplateFactory) \ 18 29 typedef TemplateFactory<NodeMapRegistry> NodeMapFactory; 19 30 31 /** Creates a map a concrete factory type from a template map 32 * factory to use as edge map factory. 33 */ 20 34 #define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \ 21 35 typedef TemplateFactory<EdgeMapRegistry> EdgeMapFactory; 22 36 37 /** Creates both map factories. 38 */ 23 39 #define CREATE_MAP_FACTORIES(TemplateFactory) \ 24 40 CREATE_NODE_MAP_FACTORY(TemplateFactory) \ 25 41 CREATE_EDGE_MAP_FACTORY(TemplateFactory) 26 42 43 /** Import a map from a concrete map factory. The import method is 44 * an overloading of the map type. 45 * The reason to use these macro is that the c++ does not support 46 * the template typedefs. If a future release of the c++ 47 * supports this feature it should be fixed. 48 */ 27 49 #define IMPORT_NODE_MAP(Factory) \ 28 50 template <typename V> \ … … 30 52 public: \ 31 53 NodeMap() {} \ 32 NodeMap(Graph& g) : Factory::Map<V>(g, g.node_maps) {} \ 54 NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \ 55 NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \ 56 NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \ 57 template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \ 58 NodeMap& operator=(const NodeMap& copy) { \ 59 this->Factory::Map<V>::operator=(copy); \ 60 return *this; \ 61 } \ 62 template <typename CMap>NodeMap& operator=(const CMap& copy) { \ 63 this->Factory::Map<V>::operator=<CMap>(copy); \ 64 return *this; \ 65 } \ 33 66 }; 34 67 68 /** Import a map from a concrete map factory. The import method is 69 * an overloading of the map type. 70 * The reason to use these macro is that the c++ does not support 71 * the template typedefs. If a future release of the c++ 72 * supports this feature it should be fixed. 73 */ 35 74 #define IMPORT_EDGE_MAP(Factory) \ 36 75 template <typename V> \ … … 38 77 public: \ 39 78 EdgeMap() {} \ 40 EdgeMap(Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \ 79 EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \ 80 EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \ 81 EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \ 82 template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \ 83 EdgeMap& operator=(const EdgeMap& copy) { \ 84 this->Factory::Map<V>::operator=(copy); \ 85 return *this; \ 86 } \ 87 template <typename CMap>EdgeMap& operator=(const CMap& copy) { \ 88 this->Factory::Map<V>::operator=<CMap>(copy); \ 89 return *this; \ 90 } \ 41 91 }; 42 92 93 /** This macro creates both map factories and imports both maps. 94 */ 43 95 #define CREATE_MAPS(TemplateFactory) \ 44 96 CREATE_MAP_FACTORIES(TemplateFactory) \ -
src/work/deba/map_registry.h
r676 r701 9 9 10 10 /** 11 Registry class to register edge or node maps inthe graph. The12 13 14 11 * Registry class to register edge or node maps into the graph. The 12 * registry helps you to implement an observer pattern. If you add 13 * or erase an edge or node you must notify all the maps about the 14 * event. 15 15 */ 16 16 template <typename G, typename K, typename KIt> … … 23 23 24 24 25 ///. 26 27 ///. 28 /// 25 /** 26 * MapBase is the base class of the registered maps. 27 * It defines the core modification operations on the maps and 28 * implements some helper functions. 29 */ 29 30 class MapBase { 30 31 public: … … 35 36 36 37 friend class Registry; 37 38 /** 39 Default constructor.40 */41 38 39 /** 40 * Default constructor for MapBase. 41 */ 42 42 43 MapBase() : graph(0), registry(0) {} 43 44 /** 45 46 */ 47 48 MapBase( Graph& g, Registry& r) : graph(&g), registry(0) {44 45 /** 46 * Simple constructor to register into a graph registry. 47 */ 48 49 MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) { 49 50 r.attach(*this); 50 51 } 51 52 52 53 /** 53 Copy constructor with registering into the map.54 * Copy constructor to register into the registry. 54 55 */ 55 56 … … 61 62 62 63 /** 63 64 * Assign operator. 64 65 */ 65 66 … … 76 77 77 78 /** 78 Destructor. 79 * Destructor. 79 80 */ 80 81 … … 84 85 } 85 86 } 86 87 88 /* 89 * Returns the graph that the map belongs to. 90 */ 91 92 const Graph* getGraph() const { return graph; } 93 94 private: 95 96 const Graph* graph; 97 Registry* registry; 98 99 int registry_index; 100 87 101 protected: 88 89 Graph* graph;90 Registry* registry;91 92 int registry_index;93 102 94 103 /** … … 107 116 108 117 virtual void destroy() { 109 for (KeyIt it(*g raph); graph->valid(it); graph->next(it)) {118 for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) { 110 119 erase(it); 111 120 } … … 135 144 protected: 136 145 146 /** 147 * The container type of the maps. 148 */ 137 149 typedef std::vector<MapBase*> Container; 150 151 /** 152 * The container of the registered maps. 153 */ 138 154 Container container; 139 155 140 156 141 public: 142 143 ///. 157 public: 158 159 /** 160 * Default Constructor of the MapRegistry. It creates an empty registry. 161 */ 144 162 MapRegistry() {} 145 163 146 ///. 164 /** 165 * Copy Constructor of the MapRegistry. The new registry does not steal 166 * the maps from the right value. The new registry will be an empty. 167 */ 147 168 MapRegistry(const MapRegistry&) {} 148 169 149 ///. 170 /** 171 * Assign operator. The left value does not steal the maps 172 * from the right value. The left value will be an empty registry. 173 */ 150 174 MapRegistry& operator=(const MapRegistry&) { 151 175 for (it = container.begin(); it != container.end(); ++it) { … … 156 180 } 157 181 158 ///. 182 /** 183 * Destructor of the MapRegistry. 184 */ 159 185 ~MapRegistry() { 160 186 typename Container::iterator it; … … 169 195 public: 170 196 171 ///. 197 /** 198 * Attach a map into thr registry. If the map has been attached 199 * into an other registry it is detached from that automaticly. 200 */ 172 201 void attach(MapBase& map) { 173 202 if (map.registry) { … … 179 208 } 180 209 181 ///. 210 /** 211 * Detach the map from the registry. 212 */ 182 213 void detach(MapBase& map) { 183 214 container.back()->registry_index = map.registry_index; … … 189 220 190 221 191 ///. 222 /** 223 * Notify all the registered maps about a Key added. 224 */ 192 225 virtual void add(Key& key) { 193 226 typename Container::iterator it; … … 197 230 } 198 231 199 ///. 232 /** 233 * Notify all the registered maps about a Key erased. 234 */ 200 235 virtual void erase(Key& key) { 201 236 typename Container::iterator it;
Note: See TracChangeset
for help on using the changeset viewer.