Changeset 400:cb377609cf1d in lemon0.x for src/work
 Timestamp:
 04/25/04 22:16:16 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@531
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/list_graph.h
r397 r400 69 69 public: 70 70 template <typename T> class EdgeMap; 71 template <typename T> class EdgeMap;71 template <typename T> class NodeMap; 72 72 73 73 class Node; … … 301 301 friend class ListGraph; 302 302 template <typename T> friend class NodeMap; 303 303 304 304 friend class Edge; 305 305 friend class OutEdgeIt; … … 322 322 friend class ListGraph; 323 323 public: 324 NodeIt() : Node() { } 325 NodeIt(Invalid i) : Node(i) { } 324 326 NodeIt(const ListGraph& G) : Node(G.first_node) { } 325 NodeIt() : Node() { }326 327 }; 327 328 … … 722 723 }; 723 724 725 726 ///A smart graph class. 727 728 ///This is a simple and fast erasable graph implementation. 729 /// 730 ///It conforms to the graph interface documented under 731 ///the description of \ref GraphSkeleton. 732 ///\sa \ref GraphSkeleton. 733 class NodeSet { 734 735 //Nodes are double linked. 736 //The free nodes are only single linked using the "next" field. 737 struct NodeT 738 { 739 int first_in,first_out; 740 int prev, next; 741 // NodeT() {} 742 }; 743 744 std::vector<NodeT> nodes; 745 //The first node 746 int first_node; 747 //The first free node 748 int first_free_node; 749 750 protected: 751 752 template <typename Key> class DynMapBase 753 { 754 protected: 755 const NodeSet* G; 756 public: 757 virtual void add(const Key k) = NULL; 758 virtual void erase(const Key k) = NULL; 759 DynMapBase(const NodeSet &_G) : G(&_G) {} 760 virtual ~DynMapBase() {} 761 friend class NodeSet; 762 }; 763 764 public: 765 template <typename T> class EdgeMap; 766 template <typename T> class NodeMap; 767 768 class Node; 769 class Edge; 770 771 // protected: 772 // HELPME: 773 protected: 774 ///\bug It must be public because of SymEdgeMap. 775 /// 776 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 777 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 778 779 public: 780 781 class NodeIt; 782 class EdgeIt; 783 class OutEdgeIt; 784 class InEdgeIt; 785 786 template <typename T> class NodeMap; 787 template <typename T> class EdgeMap; 788 789 public: 790 791 NodeSet() : nodes(), first_node(1), 792 first_free_node(1) {} 793 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node), 794 first_free_node(_g.first_free_node) {} 795 796 ~NodeSet() 797 { 798 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 799 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 800 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 801 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 802 } 803 804 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 805 int edgeNum() const { return 0; } //FIXME: What is this? 806 807 ///\bug This function does something different than 808 ///its name would suggests... 809 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? 810 ///\bug This function does something different than 811 ///its name would suggests... 812 int maxEdgeId() const { return 0; } //FIXME: What is this? 813 814 Node tail(Edge e) const { return INVALID; } 815 Node head(Edge e) const { return INVALID; } 816 817 Node aNode(OutEdgeIt e) const { return INVALID; } 818 Node aNode(InEdgeIt e) const { return INVALID; } 819 820 Node bNode(OutEdgeIt e) const { return INVALID; } 821 Node bNode(InEdgeIt e) const { return INVALID; } 822 823 NodeIt& first(NodeIt& v) const { 824 v=NodeIt(*this); return v; } 825 EdgeIt& first(EdgeIt& e) const { 826 e=EdgeIt(*this); return e; } 827 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 828 e=OutEdgeIt(*this,v); return e; } 829 InEdgeIt& first(InEdgeIt& e, const Node v) const { 830 e=InEdgeIt(*this,v); return e; } 831 832 // template< typename It > 833 // It first() const { It e; first(e); return e; } 834 835 // template< typename It > 836 // It first(Node v) const { It e; first(e,v); return e; } 837 838 bool valid(Edge e) const { return false; } 839 bool valid(Node n) const { return n.n!=1; } 840 841 void setInvalid(Edge &e) { } 842 void setInvalid(Node &n) { n.n=1; } 843 844 template <typename It> It getNext(It it) const 845 { It tmp(it); return next(tmp); } 846 847 NodeIt& next(NodeIt& it) const { 848 it.n=nodes[it.n].next; 849 return it; 850 } 851 OutEdgeIt& next(OutEdgeIt& it) const { return it; } 852 InEdgeIt& next(InEdgeIt& it) const { return it; } 853 EdgeIt& next(EdgeIt& it) const { return it; } 854 855 int id(Node v) const { return v.n; } 856 int id(Edge e) const { return 1; } 857 858 /// Adds a new node to the graph. 859 860 /// \todo It adds the nodes in a reversed order. 861 /// (i.e. the lastly added node becomes the first.) 862 Node addNode() { 863 int n; 864 865 if(first_free_node==1) 866 { 867 n = nodes.size(); 868 nodes.push_back(NodeT()); 869 } 870 else { 871 n = first_free_node; 872 first_free_node = nodes[n].next; 873 } 874 875 nodes[n].next = first_node; 876 if(first_node != 1) nodes[first_node].prev = n; 877 first_node = n; 878 nodes[n].prev = 1; 879 880 nodes[n].first_in = nodes[n].first_out = 1; 881 882 Node nn; nn.n=n; 883 884 //Update dynamic maps 885 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 886 i!=dyn_node_maps.end(); ++i) (**i).add(nn); 887 888 return nn; 889 } 890 891 void erase(Node nn) { 892 int n=nn.n; 893 894 if(nodes[n].next != 1) nodes[nodes[n].next].prev = nodes[n].prev; 895 if(nodes[n].prev != 1) nodes[nodes[n].prev].next = nodes[n].next; 896 else first_node = nodes[n].next; 897 898 nodes[n].next = first_free_node; 899 first_free_node = n; 900 901 //Update dynamic maps 902 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 903 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); 904 } 905 906 ///\bug Dynamic maps must be updated! 907 /// 908 void clear() { 909 nodes.clear(); 910 first_node = first_free_node = 1; 911 } 912 913 class Node { 914 friend class NodeSet; 915 template <typename T> friend class NodeMap; 916 917 friend class Edge; 918 friend class OutEdgeIt; 919 friend class InEdgeIt; 920 921 protected: 922 int n; 923 friend int NodeSet::id(Node v) const; 924 Node(int nn) {n=nn;} 925 public: 926 Node() {} 927 Node (Invalid i) { n=1; } 928 bool operator==(const Node i) const {return n==i.n;} 929 bool operator!=(const Node i) const {return n!=i.n;} 930 bool operator<(const Node i) const {return n<i.n;} 931 }; 932 933 class NodeIt : public Node { 934 friend class NodeSet; 935 public: 936 NodeIt(const NodeSet& G) : Node(G.first_node) { } 937 NodeIt() : Node() { } 938 }; 939 940 class Edge { 941 //friend class NodeSet; 942 //template <typename T> friend class EdgeMap; 943 944 //template <typename T> friend class SymNodeSet::SymEdgeMap; 945 //friend Edge SymNodeSet::opposite(Edge) const; 946 947 // friend class Node; 948 // friend class NodeIt; 949 protected: 950 //friend int NodeSet::id(Edge e) const; 951 // Edge(int nn) {} 952 public: 953 Edge() { } 954 Edge (Invalid) { } 955 bool operator==(const Edge i) const {return true;} 956 bool operator!=(const Edge i) const {return false;} 957 bool operator<(const Edge i) const {return false;} 958 ///\bug This is a workaround until somebody tells me how to 959 ///make class \c SymNodeSet::SymEdgeMap friend of Edge 960 // int idref() {return 1;} 961 // int idref() const {return 1;} 962 }; 963 964 class EdgeIt : public Edge { 965 //friend class NodeSet; 966 public: 967 EdgeIt(const NodeSet& G) : Edge() { } 968 EdgeIt (Invalid i) : Edge(i) { } 969 EdgeIt() : Edge() { } 970 ///\bug This is a workaround until somebody tells me how to 971 ///make class \c SymNodeSet::SymEdgeMap friend of Edge 972 // int idref() {return 1;} 973 }; 974 975 class OutEdgeIt : public Edge { 976 friend class NodeSet; 977 public: 978 OutEdgeIt() : Edge() { } 979 OutEdgeIt (Invalid i) : Edge(i) { } 980 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} 981 }; 982 983 class InEdgeIt : public Edge { 984 friend class NodeSet; 985 public: 986 InEdgeIt() : Edge() { } 987 InEdgeIt (Invalid i) : Edge(i) { } 988 InEdgeIt(const NodeSet& G,Node v) :Edge() {} 989 }; 990 991 template <typename T> class NodeMap : public DynMapBase<Node> 992 { 993 std::vector<T> container; 994 995 public: 996 typedef T ValueType; 997 typedef Node KeyType; 998 999 NodeMap(const NodeSet &_G) : 1000 DynMapBase<Node>(_G), container(_G.maxNodeId()) 1001 { 1002 G>dyn_node_maps.push_back(this); 1003 } 1004 NodeMap(const NodeSet &_G,const T &t) : 1005 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) 1006 { 1007 G>dyn_node_maps.push_back(this); 1008 } 1009 1010 NodeMap(const NodeMap<T> &m) : 1011 DynMapBase<Node>(*m.G), container(m.container) 1012 { 1013 G>dyn_node_maps.push_back(this); 1014 } 1015 1016 template<typename TT> friend class NodeMap; 1017 1018 ///\todo It can copy between different types. 1019 /// 1020 template<typename TT> NodeMap(const NodeMap<TT> &m) : 1021 DynMapBase<Node>(*m.G) 1022 { 1023 G>dyn_node_maps.push_back(this); 1024 typename std::vector<TT>::const_iterator i; 1025 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 1026 i!=m.container.end(); 1027 i++) 1028 container.push_back(*i); 1029 } 1030 ~NodeMap() 1031 { 1032 if(G) { 1033 std::vector<DynMapBase<Node>* >::iterator i; 1034 for(i=G>dyn_node_maps.begin(); 1035 i!=G>dyn_node_maps.end() && *i!=this; ++i) ; 1036 //if(*i==this) G>dyn_node_maps.erase(i); //FIXME: Way too slow... 1037 //A better way to do that: (Is this really important?) 1038 if(*i==this) { 1039 *i=G>dyn_node_maps.back(); 1040 G>dyn_node_maps.pop_back(); 1041 } 1042 } 1043 } 1044 1045 void add(const Node k) 1046 { 1047 if(k.n>=int(container.size())) container.resize(k.n+1); 1048 } 1049 1050 void erase(const Node) { } 1051 1052 void set(Node n, T a) { container[n.n]=a; } 1053 //'T& operator[](Node n)' would be wrong here 1054 typename std::vector<T>::reference 1055 operator[](Node n) { return container[n.n]; } 1056 //'const T& operator[](Node n)' would be wrong here 1057 typename std::vector<T>::const_reference 1058 operator[](Node n) const { return container[n.n]; } 1059 1060 ///\warning There is no safety check at all! 1061 ///Using operator = between maps attached to different graph may 1062 ///cause serious problem. 1063 ///\todo Is this really so? 1064 ///\todo It can copy between different types. 1065 const NodeMap<T>& operator=(const NodeMap<T> &m) 1066 { 1067 container = m.container; 1068 return *this; 1069 } 1070 template<typename TT> 1071 const NodeMap<T>& operator=(const NodeMap<TT> &m) 1072 { 1073 copy(m.container.begin(), m.container.end(), container.begin()); 1074 return *this; 1075 } 1076 1077 void update() {} //Useless for Dynamic Maps 1078 void update(T a) {} //Useless for Dynamic Maps 1079 }; 1080 1081 template <typename T> class EdgeMap 1082 { 1083 public: 1084 typedef T ValueType; 1085 typedef Edge KeyType; 1086 1087 EdgeMap(const NodeSet &) { } 1088 EdgeMap(const NodeSet &,const T &) { } 1089 EdgeMap(const EdgeMap<T> &) { } 1090 // template<typename TT> friend class EdgeMap; 1091 1092 ///\todo It can copy between different types. 1093 /// 1094 template<typename TT> EdgeMap(const EdgeMap<TT> &) { } 1095 ~EdgeMap() { } 1096 1097 void add(const Edge ) { } 1098 void erase(const Edge) { } 1099 1100 void set(Edge, T) { } 1101 //T get(Edge n) const { return container[n.n]; } 1102 ValueType &operator[](Edge) { return *((T*)(NULL)); } 1103 const ValueType &operator[](Edge) const { return *((T*)(NULL)); } 1104 1105 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; } 1106 1107 template<typename TT> 1108 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; } 1109 1110 void update() {} 1111 void update(T a) {} 1112 }; 1113 }; 1114 1115 1116 1117 ///This is a simple and fast erasable graph implementation. 1118 /// 1119 ///It conforms to the graph interface documented under 1120 ///the description of \ref GraphSkeleton. 1121 ///\sa \ref GraphSkeleton. 1122 template<typename GG> 1123 class EdgeSet { 1124 1125 typedef GG NodeGraphType; 1126 1127 NodeGraphType &G; 1128 1129 class Node; 1130 1131 //Edges are double linked. 1132 //The free edges are only single linked using the "next_in" field. 1133 struct NodeT 1134 { 1135 int first_in,first_out; 1136 NodeT() : first_in(1), first_out(1) { } 1137 }; 1138 1139 struct EdgeT 1140 { 1141 Node head, tail; 1142 int prev_in, prev_out; 1143 int next_in, next_out; 1144 }; 1145 1146 1147 typename NodeGraphType::NodeMap<NodeT> nodes; 1148 1149 std::vector<EdgeT> edges; 1150 //The first free edge 1151 int first_free_edge; 1152 1153 protected: 1154 1155 template <typename Key> class DynMapBase 1156 { 1157 protected: 1158 const EdgeSet* G; 1159 public: 1160 virtual void add(const Key k) = NULL; 1161 virtual void erase(const Key k) = NULL; 1162 DynMapBase(const EdgeSet &_G) : G(&_G) {} 1163 virtual ~DynMapBase() {} 1164 friend class EdgeSet; 1165 }; 1166 1167 public: 1168 //template <typename T> class NodeMap; 1169 template <typename T> class EdgeMap; 1170 1171 class Node; 1172 class Edge; 1173 1174 // protected: 1175 // HELPME: 1176 protected: 1177 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 1178 ///\bug It must be public because of SymEdgeMap. 1179 /// 1180 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 1181 1182 public: 1183 1184 class NodeIt; 1185 class EdgeIt; 1186 class OutEdgeIt; 1187 class InEdgeIt; 1188 1189 template <typename T> class NodeMap; 1190 template <typename T> class EdgeMap; 1191 1192 public: 1193 1194 EdgeSet(const NodeGraphType &_G) : G(_G), 1195 nodes(_G), edges(), 1196 first_free_edge(1) {} 1197 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges), 1198 first_free_edge(_g.first_free_edge) {} 1199 1200 ~EdgeSet() 1201 { 1202 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 1203 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 1204 for(typename std::vector<DynMapBase<Edge> * >::iterator 1205 i=dyn_edge_maps.begin(); 1206 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 1207 } 1208 1209 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this? 1210 int edgeNum() const { return edges.size(); } //FIXME: What is this? 1211 1212 ///\bug This function does something different than 1213 ///its name would suggests... 1214 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this? 1215 ///\bug This function does something different than 1216 ///its name would suggests... 1217 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? 1218 1219 Node tail(Edge e) const { return edges[e.n].tail; } 1220 Node head(Edge e) const { return edges[e.n].head; } 1221 1222 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } 1223 Node aNode(InEdgeIt e) const { return edges[e.n].head; } 1224 1225 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } 1226 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } 1227 1228 NodeIt& first(NodeIt& v) const { 1229 v=NodeIt(*this); return v; } 1230 EdgeIt& first(EdgeIt& e) const { 1231 e=EdgeIt(*this); return e; } 1232 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 1233 e=OutEdgeIt(*this,v); return e; } 1234 InEdgeIt& first(InEdgeIt& e, const Node v) const { 1235 e=InEdgeIt(*this,v); return e; } 1236 1237 // template< typename It > 1238 // It first() const { It e; first(e); return e; } 1239 1240 // template< typename It > 1241 // It first(Node v) const { It e; first(e,v); return e; } 1242 1243 bool valid(Edge e) const { return e.n!=1; } 1244 bool valid(Node n) const { return G.valid(n); } 1245 1246 void setInvalid(Edge &e) { e.n=1; } 1247 void setInvalid(Node &n) { G.setInvalid(n); } 1248 1249 template <typename It> It getNext(It it) const 1250 { It tmp(it); return next(tmp); } 1251 1252 NodeIt& next(NodeIt& it) const { G.next(it); return it; } 1253 OutEdgeIt& next(OutEdgeIt& it) const 1254 { it.n=edges[it.n].next_out; return it; } 1255 InEdgeIt& next(InEdgeIt& it) const 1256 { it.n=edges[it.n].next_in; return it; } 1257 EdgeIt& next(EdgeIt& it) const { 1258 if(edges[it.n].next_in!=1) { 1259 it.n=edges[it.n].next_in; 1260 } 1261 else { 1262 typename NodeGraphType::Node n; 1263 for(n=G.next(edges[it.n].head); 1264 G.valid(n) && nodes[n].first_in == 1; 1265 G.next(n)) ; 1266 it.n = (G.valid(n))?1:nodes[n].first_in; 1267 } 1268 return it; 1269 } 1270 1271 int id(Node v) const { return G.id(v); } 1272 int id(Edge e) const { return e.n; } 1273 1274 /// Adds a new node to the graph. 1275 Node addNode() { return G.AddNode(); } 1276 1277 Edge addEdge(Node u, Node v) { 1278 int n; 1279 1280 if(first_free_edge==1) 1281 { 1282 n = edges.size(); 1283 edges.push_back(EdgeT()); 1284 } 1285 else { 1286 n = first_free_edge; 1287 first_free_edge = edges[n].next_in; 1288 } 1289 1290 edges[n].tail = u.n; edges[n].head = v.n; 1291 1292 edges[n].next_out = nodes[u.n].first_out; 1293 if(nodes[u.n].first_out != 1) edges[nodes[u.n].first_out].prev_out = n; 1294 edges[n].next_in = nodes[v.n].first_in; 1295 if(nodes[v.n].first_in != 1) edges[nodes[v.n].first_in].prev_in = n; 1296 edges[n].prev_in = edges[n].prev_out = 1; 1297 1298 nodes[u.n].first_out = nodes[v.n].first_in = n; 1299 1300 Edge e; e.n=n; 1301 1302 //Update dynamic maps 1303 for(typename std::vector<DynMapBase<Edge> * >::iterator 1304 i=dyn_edge_maps.begin(); 1305 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 1306 1307 return e; 1308 } 1309 1310 private: 1311 void eraseEdge(int n) { 1312 1313 if(edges[n].next_in!=1) 1314 edges[edges[n].next_in].prev_in = edges[n].prev_in; 1315 if(edges[n].prev_in!=1) 1316 edges[edges[n].prev_in].next_in = edges[n].next_in; 1317 else nodes[edges[n].head].first_in = edges[n].next_in; 1318 1319 if(edges[n].next_out!=1) 1320 edges[edges[n].next_out].prev_out = edges[n].prev_out; 1321 if(edges[n].prev_out!=1) 1322 edges[edges[n].prev_out].next_out = edges[n].next_out; 1323 else nodes[edges[n].tail].first_out = edges[n].next_out; 1324 1325 edges[n].next_in = first_free_edge; 1326 first_free_edge = 1; 1327 1328 //Update dynamic maps 1329 Edge e; e.n=n; 1330 for(typename std::vector<DynMapBase<Edge> * >::iterator 1331 i=dyn_edge_maps.begin(); 1332 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); 1333 } 1334 1335 public: 1336 1337 // void erase(Node nn) { 1338 // int n=nn.n; 1339 // int m; 1340 // while((m=nodes[n].first_in)!=1) eraseEdge(m); 1341 // while((m=nodes[n].first_out)!=1) eraseEdge(m); 1342 // } 1343 1344 void erase(Edge e) { eraseEdge(e.n); } 1345 1346 // //\bug Dynamic maps must be updated! 1347 // // 1348 // void clear() { 1349 // nodes.clear();edges.clear(); 1350 // first_node=first_free_node=first_free_edge=1; 1351 // } 1352 1353 class Node : public NodeGraphType::Node { 1354 friend class EdgeSet; 1355 // template <typename T> friend class NodeMap; 1356 1357 friend class Edge; 1358 friend class OutEdgeIt; 1359 friend class InEdgeIt; 1360 friend class SymEdge; 1361 1362 protected: 1363 friend int EdgeSet::id(Node v) const; 1364 // Node(int nn) {n=nn;} 1365 public: 1366 Node() : NodeGraphType::Node() {} 1367 Node (Invalid i) : NodeGraphType::Node(i) {} 1368 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {} 1369 }; 1370 1371 class NodeIt : public NodeGraphType::NodeIt { 1372 friend class EdgeSet; 1373 public: 1374 NodeIt() : NodeGraphType::NodeIt() { } 1375 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} 1376 NodeIt(const EdgeSet& _G) : NodeGraphType::Node(_G.G) { } 1377 NodeIt(const typename NodeGraphType::NodeIt &n) 1378 : NodeGraphType::NodeIt(n) {} 1379 operator Node() { return Node(*this);} 1380 }; 1381 1382 class Edge { 1383 friend class EdgeSet; 1384 template <typename T> friend class EdgeMap; 1385 1386 //template <typename T> friend class SymEdgeSet::SymEdgeMap; 1387 //friend Edge SymEdgeSet::opposite(Edge) const; 1388 1389 friend class Node; 1390 friend class NodeIt; 1391 protected: 1392 int n; 1393 friend int EdgeSet::id(Edge e) const; 1394 1395 Edge(int nn) {n=nn;} 1396 public: 1397 Edge() { } 1398 Edge (Invalid) { n=1; } 1399 bool operator==(const Edge i) const {return n==i.n;} 1400 bool operator!=(const Edge i) const {return n!=i.n;} 1401 bool operator<(const Edge i) const {return n<i.n;} 1402 ///\bug This is a workaround until somebody tells me how to 1403 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge 1404 int &idref() {return n;} 1405 const int &idref() const {return n;} 1406 }; 1407 1408 class EdgeIt : public Edge { 1409 friend class EdgeSet; 1410 public: 1411 EdgeIt(const EdgeSet& G) : Edge() { 1412 typename NodeGraphType::Node m; 1413 for(G.first(m); 1414 G.valid(m) && nodes[m].first_in == 1; G.next[m]); 1415 n = G.valid(m)?1:nodes[m].first_in; 1416 } 1417 EdgeIt (Invalid i) : Edge(i) { } 1418 EdgeIt() : Edge() { } 1419 ///\bug This is a workaround until somebody tells me how to 1420 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge 1421 int &idref() {return n;} 1422 }; 1423 1424 class OutEdgeIt : public Edge { 1425 friend class EdgeSet; 1426 public: 1427 OutEdgeIt() : Edge() { } 1428 OutEdgeIt (Invalid i) : Edge(i) { } 1429 1430 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { } 1431 }; 1432 1433 class InEdgeIt : public Edge { 1434 friend class EdgeSet; 1435 public: 1436 InEdgeIt() : Edge() { } 1437 InEdgeIt (Invalid i) : Edge(i) { } 1438 InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { } 1439 }; 1440 1441 template <typename T> class NodeMap : public NodeGraphType::NodeMap<T> 1442 { 1443 public: 1444 NodeMap(const EdgeSet &_G) : 1445 NodeGraphType::NodeMap<T>(_G.G) { } 1446 NodeMap(const EdgeSet &_G,const T &t) : 1447 NodeGraphType::NodeMap<T>(_G.G,t) { } 1448 //It is unnecessary 1449 NodeMap(const typename NodeGraphType::NodeMap<T> &m) 1450 : NodeGraphType::NodeMap<T>(m) { } 1451 1452 ///\todo It can copy between different types. 1453 /// 1454 template<typename TT> friend class NodeMap; 1455 NodeMap(const typename NodeGraphType::NodeMap<TT> &m) 1456 : NodeGraphType::NodeMap<T>(m) { } 1457 }; 1458 1459 template <typename T> class EdgeMap : public DynMapBase<Edge> 1460 { 1461 std::vector<T> container; 1462 1463 public: 1464 typedef T ValueType; 1465 typedef Edge KeyType; 1466 1467 EdgeMap(const EdgeSet &_G) : 1468 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) 1469 { 1470 //FIXME: What if there are empty Id's? 1471 //FIXME: Can I use 'this' in a constructor? 1472 G>dyn_edge_maps.push_back(this); 1473 } 1474 EdgeMap(const EdgeSet &_G,const T &t) : 1475 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) 1476 { 1477 G>dyn_edge_maps.push_back(this); 1478 } 1479 EdgeMap(const EdgeMap<T> &m) : 1480 DynMapBase<Edge>(*m.G), container(m.container) 1481 { 1482 G>dyn_node_maps.push_back(this); 1483 } 1484 1485 template<typename TT> friend class EdgeMap; 1486 1487 ///\todo It can copy between different types. 1488 /// 1489 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : 1490 DynMapBase<Edge>(*m.G) 1491 { 1492 G>dyn_node_maps.push_back(this); 1493 typename std::vector<TT>::const_iterator i; 1494 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 1495 i!=m.container.end(); 1496 i++) 1497 container.push_back(*i); 1498 } 1499 ~EdgeMap() 1500 { 1501 if(G) { 1502 typename std::vector<DynMapBase<Edge>* >::iterator i; 1503 for(i=G>dyn_edge_maps.begin(); 1504 i!=G>dyn_edge_maps.end() && *i!=this; ++i) ; 1505 //if(*i==this) G>dyn_edge_maps.erase(i); //Way too slow... 1506 //A better way to do that: (Is this really important?) 1507 if(*i==this) { 1508 *i=G>dyn_edge_maps.back(); 1509 G>dyn_edge_maps.pop_back(); 1510 } 1511 } 1512 } 1513 1514 void add(const Edge k) 1515 { 1516 if(k.n>=int(container.size())) container.resize(k.n+1); 1517 } 1518 void erase(const Edge) { } 1519 1520 void set(Edge n, T a) { container[n.n]=a; } 1521 //T get(Edge n) const { return container[n.n]; } 1522 typename std::vector<T>::reference 1523 operator[](Edge n) { return container[n.n]; } 1524 typename std::vector<T>::const_reference 1525 operator[](Edge n) const { return container[n.n]; } 1526 1527 ///\warning There is no safety check at all! 1528 ///Using operator = between maps attached to different graph may 1529 ///cause serious problem. 1530 ///\todo Is this really so? 1531 ///\todo It can copy between different types. 1532 const EdgeMap<T>& operator=(const EdgeMap<T> &m) 1533 { 1534 container = m.container; 1535 return *this; 1536 } 1537 template<typename TT> 1538 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) 1539 { 1540 copy(m.container.begin(), m.container.end(), container.begin()); 1541 return *this; 1542 } 1543 1544 void update() {} //Useless for DynMaps 1545 void update(T a) {} //Useless for DynMaps 1546 }; 1547 1548 }; 1549 1550 1551 1552 1553 1554 1555 724 1556 725 1557 } //namespace hugo
Note: See TracChangeset
for help on using the changeset viewer.