Changeset 1695:e6f99fe1723f in lemon0.x for lemon/graph_utils.h
 Timestamp:
 10/03/05 12:14:49 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2221
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r1679 r1695 21 21 #include <vector> 22 22 #include <map> 23 #include <cmath> 23 24 24 25 #include <lemon/invalid.h> … … 1061 1062 } 1062 1063 1063 template <typename _Graph> 1064 class DegMapBase { 1065 public: 1066 1064 /// \brief Potential difference map 1065 /// 1066 /// If there is an potential map on the nodes then we 1067 /// can get an edge map as we get the substraction of the 1068 /// values of the target and source. 1069 template <typename Graph, typename NodeMap> 1070 class PotentialDifferenceMap { 1071 public: 1072 typedef typename Graph::Edge Key; 1073 typedef typename NodeMap::Value Value; 1074 1075 /// \brief Constructor 1076 /// 1077 /// Contructor of the map 1078 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential) 1079 : graph(_graph), potential(_potential) {} 1080 1081 /// \brief Const subscription operator 1082 /// 1083 /// Const subscription operator 1084 Value operator[](const Key& edge) const { 1085 return potential[graph.target(edge)]  potential[graph.source(edge)]; 1086 } 1087 1088 private: 1089 const Graph& graph; 1090 const NodeMap& potential; 1091 }; 1092 1093 /// \brief Just returns a PotentialDifferenceMap 1094 /// 1095 /// Just returns a PotentialDifferenceMap 1096 /// \relates PotentialDifferenceMap 1097 template <typename Graph, typename NodeMap> 1098 PotentialDifferenceMap<Graph, NodeMap> 1099 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) { 1100 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential); 1101 } 1102 1103 /// \brief Container for store values for each ordered pair of nodes 1104 /// 1105 /// Container for store values for each ordered pair of nodes. 1106 template <typename _Graph, typename _Value> 1107 class NodeMatrixMap 1108 : protected AlterationNotifier<typename _Graph::Node>::ObserverBase { 1109 public: 1067 1110 typedef _Graph Graph; 1111 typedef typename Graph::Node Node; 1112 typedef Node Key; 1113 typedef _Value Value; 1114 1115 /// \brief Creates a node matrix for the given graph 1116 /// 1117 /// Creates a node matrix for the given graph. 1118 NodeMatrixMap(const Graph& _graph) 1119 : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {} 1120 1121 /// \brief Creates a node matrix for the given graph 1122 /// 1123 /// Creates a node matrix for the given graph and assigns each 1124 /// initial value to the given parameter. 1125 NodeMatrixMap(const Graph& _graph, const Value& _val) 1126 : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {} 1127 1128 /// \brief Gives back the value assigned to the \c left  \c right 1129 /// ordered pair. 1130 /// 1131 /// Gives back the value assigned to the \c left  \c right ordered pair. 1132 const Value& operator()(const Node& left, const Node& right) const { 1133 return values[index(graph.id(left), graph.id(right))]; 1134 } 1135 1136 /// \brief Gives back the value assigned to the \c left  \c right 1137 /// ordered pair. 1138 /// 1139 /// Gives back the value assigned to the \c left  \c right ordered pair. 1140 Value& operator()(const Node& left, const Node& right) { 1141 return values[index(graph.id(left), graph.id(right))]; 1142 } 1143 1144 /// \brief Setter function for the matrix map. 1145 /// 1146 /// Setter function for the matrix map. 1147 void set(const Node& left, const Node& right, const Value& val) { 1148 values[index(graph.id(left), graph.id(right))] = val; 1149 } 1150 1151 /// \brief Map for the coloumn view of the matrix 1152 /// 1153 /// Map for the coloumn view of the matrix. 1154 class ColMap : public MapBase<Node, Value> { 1155 friend class NodeMatrixMap; 1156 private: 1157 ColMap(NodeMatrixMap& _matrix, Node _col) 1158 : matrix(_matrix), col(_col) {} 1159 1160 public: 1161 /// \brief Subscription operator 1162 /// 1163 /// Subscription operator. 1164 Value& operator[](Node row) { 1165 return matrix(col, row); 1166 } 1167 1168 /// \brief Setter function 1169 /// 1170 /// Setter function. 1171 void set(Node row, const Value& val) { 1172 matrix.set(col, row, val); 1173 } 1174 1175 /// \brief Subscription operator 1176 /// 1177 /// Subscription operator. 1178 const Value& operator[](Node row) const { 1179 return matrix(col, row); 1180 } 1181 1182 private: 1183 NodeMatrixMap& matrix; 1184 Node col; 1185 }; 1186 1187 /// \brief Map for the const coloumn view of the matrix 1188 /// 1189 /// Map for the const coloumn view of the matrix. 1190 class ConstColMap : public MapBase<Node, Value> { 1191 friend class NodeMatrixMap; 1192 private: 1193 ConstColMap(const NodeMatrixMap& _matrix, Node _col) 1194 : matrix(_matrix), col(_col) {} 1195 1196 public: 1197 /// \brief Subscription operator 1198 /// 1199 /// Subscription operator. 1200 const Value& operator[](Node row) const { 1201 return matrix(col, row); 1202 } 1203 1204 private: 1205 const NodeMatrixMap& matrix; 1206 Node col; 1207 }; 1208 1209 /// \brief Map for the row view of the matrix 1210 /// 1211 /// Map for the row view of the matrix. 1212 class RowMap : public MapBase<Node, Value> { 1213 public: 1214 friend class NodeMatrixMap; 1215 private: 1216 RowMap(NodeMatrixMap& _matrix, Node _row) 1217 : matrix(_matrix), row(_row) {} 1218 1219 public: 1220 /// \brief Subscription operator 1221 /// 1222 /// Subscription operator. 1223 Value& operator[](Node col) { 1224 return matrix(col, row); 1225 } 1226 1227 /// \brief Setter function 1228 /// 1229 /// Setter function. 1230 void set(Node col, const Value& val) { 1231 matrix.set(col, row, val); 1232 } 1233 1234 /// \brief Subscription operator 1235 /// 1236 /// Subscription operator. 1237 const Value& operator[](Node col) const { 1238 return matrix(col, row); 1239 } 1240 1241 private: 1242 NodeMatrixMap& matrix; 1243 Node row; 1244 }; 1245 1246 /// \brief Map for the const row view of the matrix 1247 /// 1248 /// Map for the row const view of the matrix. 1249 class ConstRowMap : public MapBase<Node, Value> { 1250 public: 1251 friend class NodeMatrixMap; 1252 private: 1253 ConstRowMap(const NodeMatrixMap& _matrix, Node _row) 1254 : matrix(_matrix), row(_row) {} 1255 1256 public: 1257 /// \brief Subscription operator 1258 /// 1259 /// Subscription operator. 1260 const Value& operator[](Node col) const { 1261 return matrix(col, row); 1262 } 1263 1264 private: 1265 const NodeMatrixMap& matrix; 1266 Node row; 1267 }; 1268 1269 /// \brief Gives back the column view for the given node 1270 /// 1271 /// Gives back the column view for the given node 1272 ConstColMap operator[](Node col) const { return ConstColMap(*this, col); } 1273 /// \brief Gives back the column view for the given node 1274 /// 1275 /// Gives back the column view for the given node 1276 ColMap operator[](Node col) { return ColMap(*this, col); } 1277 1278 /// \brief Gives back the column view for the given node 1279 /// 1280 /// Gives back the column view for the given node 1281 ConstColMap colMap(Node col) const { return ConstColMap(*this, col); } 1282 /// \brief Gives back the column view for the given node 1283 /// 1284 /// Gives back the column view for the given node 1285 ColMap colMap(Node col) { return ColMap(*this, col); } 1286 1287 /// \brief Gives back the row view for the given node 1288 /// 1289 /// Gives back the row view for the given node 1290 ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); } 1291 /// \brief Gives back the row view for the given node 1292 /// 1293 /// Gives back the row view for the given node 1294 RowMap rowMap(Node row) { return RowMap(*this, row); } 1068 1295 1069 1296 protected: 1070 1297 1071 typedef typename Graph::template NodeMap<int> IntNodeMap; 1072 1298 static int index(int i, int j) { 1299 int m = i > j ? i : j; 1300 if (i < j) { 1301 return m * m + i; 1302 } else { 1303 return m * m + m + j; 1304 } 1305 } 1306 1307 static int size(int s) { 1308 return s * s; 1309 } 1310 1311 void add(const Node& node) { 1312 if (size(graph.id(node) + 1) > values.size()) { 1313 values.resize(size(graph.id(node) + 1)); 1314 } 1315 } 1316 1317 void erase(const Node&) {} 1318 1319 void build() { 1320 values.resize(size(graph.maxId(Node()) + 1)); 1321 } 1322 1323 void clear() { 1324 values.clear(); 1325 } 1326 1327 private: 1328 const Graph& graph; 1329 std::vector<Value> values; 1073 1330 }; 1074 1331 … … 1271 1528 }; 1272 1529 1530 // Indicators for the tags 1531 1532 template <typename Graph, typename Enable = void> 1533 struct NodeNumTagIndicator { 1534 static const bool value = false; 1535 }; 1536 1537 template <typename Graph> 1538 struct NodeNumTagIndicator< 1539 Graph, 1540 typename enable_if<typename Graph::NodeNumTag, void>::type 1541 > { 1542 static const bool value = true; 1543 }; 1544 1545 template <typename Graph, typename Enable = void> 1546 struct EdgeNumTagIndicator { 1547 static const bool value = false; 1548 }; 1549 1550 template <typename Graph> 1551 struct EdgeNumTagIndicator< 1552 Graph, 1553 typename enable_if<typename Graph::EdgeNumTag, void>::type 1554 > { 1555 static const bool value = true; 1556 }; 1557 1558 template <typename Graph, typename Enable = void> 1559 struct FindEdgeTagIndicator { 1560 static const bool value = false; 1561 }; 1562 1563 template <typename Graph> 1564 struct FindEdgeTagIndicator< 1565 Graph, 1566 typename enable_if<typename Graph::FindEdgeTag, void>::type 1567 > { 1568 static const bool value = true; 1569 }; 1570 1571 1273 1572 /// @} 1274 1573
Note: See TracChangeset
for help on using the changeset viewer.