Changeset 1190:523e45e37e52 in lemon for lemon
 Timestamp:
 11/16/10 00:59:36 (9 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/core.h
r1188 r1190 551 551 template <typename From, typename NodeRefMap, typename EdgeRefMap> 552 552 static void copy(const From& from, Graph &to, 553 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 554 to.build(from, nodeRefMap, edgeRefMap); 555 } 556 }; 557 558 template <typename BpGraph, typename Enable = void> 559 struct BpGraphCopySelector { 560 template <typename From, typename NodeRefMap, typename EdgeRefMap> 561 static void copy(const From& from, BpGraph &to, 562 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 563 to.clear(); 564 for (typename From::RedIt it(from); it != INVALID; ++it) { 565 nodeRefMap[it] = to.addRedNode(); 566 } 567 for (typename From::BlueIt it(from); it != INVALID; ++it) { 568 nodeRefMap[it] = to.addBlueNode(); 569 } 570 for (typename From::EdgeIt it(from); it != INVALID; ++it) { 571 edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)], 572 nodeRefMap[from.blueNode(it)]); 573 } 574 } 575 }; 576 577 template <typename BpGraph> 578 struct BpGraphCopySelector< 579 BpGraph, 580 typename enable_if<typename BpGraph::BuildTag, void>::type> 581 { 582 template <typename From, typename NodeRefMap, typename EdgeRefMap> 583 static void copy(const From& from, BpGraph &to, 553 584 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 554 585 to.build(from, nodeRefMap, edgeRefMap); … … 1100 1131 graphCopy(const From& from, To& to) { 1101 1132 return GraphCopy<From, To>(from, to); 1133 } 1134 1135 /// \brief Class to copy a bipartite graph. 1136 /// 1137 /// Class to copy a bipartite graph to another graph (duplicate a 1138 /// graph). The simplest way of using it is through the 1139 /// \c bpGraphCopy() function. 1140 /// 1141 /// This class not only make a copy of a bipartite graph, but it can 1142 /// create references and cross references between the nodes, edges 1143 /// and arcs of the two graphs, and it can copy maps for using with 1144 /// the newly created graph. 1145 /// 1146 /// To make a copy from a graph, first an instance of BpGraphCopy 1147 /// should be created, then the data belongs to the graph should 1148 /// assigned to copy. In the end, the \c run() member should be 1149 /// called. 1150 /// 1151 /// The next code copies a graph with several data: 1152 ///\code 1153 /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph); 1154 /// // Create references for the nodes 1155 /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph); 1156 /// cg.nodeRef(nr); 1157 /// // Create cross references (inverse) for the edges 1158 /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph); 1159 /// cg.edgeCrossRef(ecr); 1160 /// // Copy a red map 1161 /// OrigBpGraph::RedMap<double> ormap(orig_graph); 1162 /// NewBpGraph::RedMap<double> nrmap(new_graph); 1163 /// cg.edgeMap(ormap, nrmap); 1164 /// // Copy a node 1165 /// OrigBpGraph::Node on; 1166 /// NewBpGraph::Node nn; 1167 /// cg.node(on, nn); 1168 /// // Execute copying 1169 /// cg.run(); 1170 ///\endcode 1171 template <typename From, typename To> 1172 class BpGraphCopy { 1173 private: 1174 1175 typedef typename From::Node Node; 1176 typedef typename From::RedNode RedNode; 1177 typedef typename From::BlueNode BlueNode; 1178 typedef typename From::NodeIt NodeIt; 1179 typedef typename From::Arc Arc; 1180 typedef typename From::ArcIt ArcIt; 1181 typedef typename From::Edge Edge; 1182 typedef typename From::EdgeIt EdgeIt; 1183 1184 typedef typename To::Node TNode; 1185 typedef typename To::Arc TArc; 1186 typedef typename To::Edge TEdge; 1187 1188 typedef typename From::template NodeMap<TNode> NodeRefMap; 1189 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; 1190 1191 struct ArcRefMap { 1192 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref) 1193 : _from(from), _to(to), _edge_ref(edge_ref) {} 1194 1195 typedef typename From::Arc Key; 1196 typedef typename To::Arc Value; 1197 1198 Value operator[](const Key& key) const { 1199 return _to.direct(_edge_ref[key], _from.direction(key)); 1200 } 1201 1202 const From& _from; 1203 const To& _to; 1204 const EdgeRefMap& _edge_ref; 1205 }; 1206 1207 public: 1208 1209 /// \brief Constructor of BpGraphCopy. 1210 /// 1211 /// Constructor of BpGraphCopy for copying the content of the 1212 /// \c from graph into the \c to graph. 1213 BpGraphCopy(const From& from, To& to) 1214 : _from(from), _to(to) {} 1215 1216 /// \brief Destructor of BpGraphCopy 1217 /// 1218 /// Destructor of BpGraphCopy. 1219 ~BpGraphCopy() { 1220 for (int i = 0; i < int(_node_maps.size()); ++i) { 1221 delete _node_maps[i]; 1222 } 1223 for (int i = 0; i < int(_red_maps.size()); ++i) { 1224 delete _red_maps[i]; 1225 } 1226 for (int i = 0; i < int(_blue_maps.size()); ++i) { 1227 delete _blue_maps[i]; 1228 } 1229 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1230 delete _arc_maps[i]; 1231 } 1232 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1233 delete _edge_maps[i]; 1234 } 1235 } 1236 1237 /// \brief Copy the node references into the given map. 1238 /// 1239 /// This function copies the node references into the given map. 1240 /// The parameter should be a map, whose key type is the Node type of 1241 /// the source graph, while the value type is the Node type of the 1242 /// destination graph. 1243 template <typename NodeRef> 1244 BpGraphCopy& nodeRef(NodeRef& map) { 1245 _node_maps.push_back(new _core_bits::RefCopy<From, Node, 1246 NodeRefMap, NodeRef>(map)); 1247 return *this; 1248 } 1249 1250 /// \brief Copy the node cross references into the given map. 1251 /// 1252 /// This function copies the node cross references (reverse references) 1253 /// into the given map. The parameter should be a map, whose key type 1254 /// is the Node type of the destination graph, while the value type is 1255 /// the Node type of the source graph. 1256 template <typename NodeCrossRef> 1257 BpGraphCopy& nodeCrossRef(NodeCrossRef& map) { 1258 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, 1259 NodeRefMap, NodeCrossRef>(map)); 1260 return *this; 1261 } 1262 1263 /// \brief Make a copy of the given node map. 1264 /// 1265 /// This function makes a copy of the given node map for the newly 1266 /// created graph. 1267 /// The key type of the new map \c tmap should be the Node type of the 1268 /// destination graph, and the key type of the original map \c map 1269 /// should be the Node type of the source graph. 1270 template <typename FromMap, typename ToMap> 1271 BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 1272 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 1273 NodeRefMap, FromMap, ToMap>(map, tmap)); 1274 return *this; 1275 } 1276 1277 /// \brief Make a copy of the given node. 1278 /// 1279 /// This function makes a copy of the given node. 1280 BpGraphCopy& node(const Node& node, TNode& tnode) { 1281 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 1282 NodeRefMap, TNode>(node, tnode)); 1283 return *this; 1284 } 1285 1286 /// \brief Copy the red node references into the given map. 1287 /// 1288 /// This function copies the red node references into the given 1289 /// map. The parameter should be a map, whose key type is the 1290 /// Node type of the source graph with the red item set, while the 1291 /// value type is the Node type of the destination graph. 1292 template <typename RedRef> 1293 BpGraphCopy& redRef(RedRef& map) { 1294 _red_maps.push_back(new _core_bits::RefCopy<From, RedNode, 1295 NodeRefMap, RedRef>(map)); 1296 return *this; 1297 } 1298 1299 /// \brief Copy the red node cross references into the given map. 1300 /// 1301 /// This function copies the red node cross references (reverse 1302 /// references) into the given map. The parameter should be a map, 1303 /// whose key type is the Node type of the destination graph with 1304 /// the red item set, while the value type is the Node type of the 1305 /// source graph. 1306 template <typename RedCrossRef> 1307 BpGraphCopy& redCrossRef(RedCrossRef& map) { 1308 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode, 1309 NodeRefMap, RedCrossRef>(map)); 1310 return *this; 1311 } 1312 1313 /// \brief Make a copy of the given red node map. 1314 /// 1315 /// This function makes a copy of the given red node map for the newly 1316 /// created graph. 1317 /// The key type of the new map \c tmap should be the Node type of 1318 /// the destination graph with the red items, and the key type of 1319 /// the original map \c map should be the Node type of the source 1320 /// graph. 1321 template <typename FromMap, typename ToMap> 1322 BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) { 1323 _red_maps.push_back(new _core_bits::MapCopy<From, RedNode, 1324 NodeRefMap, FromMap, ToMap>(map, tmap)); 1325 return *this; 1326 } 1327 1328 /// \brief Copy the blue node references into the given map. 1329 /// 1330 /// This function copies the blue node references into the given 1331 /// map. The parameter should be a map, whose key type is the 1332 /// Node type of the source graph with the blue item set, while the 1333 /// value type is the Node type of the destination graph. 1334 template <typename BlueRef> 1335 BpGraphCopy& blueRef(BlueRef& map) { 1336 _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode, 1337 NodeRefMap, BlueRef>(map)); 1338 return *this; 1339 } 1340 1341 /// \brief Copy the blue node cross references into the given map. 1342 /// 1343 /// This function copies the blue node cross references (reverse 1344 /// references) into the given map. The parameter should be a map, 1345 /// whose key type is the Node type of the destination graph with 1346 /// the blue item set, while the value type is the Node type of the 1347 /// source graph. 1348 template <typename BlueCrossRef> 1349 BpGraphCopy& blueCrossRef(BlueCrossRef& map) { 1350 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode, 1351 NodeRefMap, BlueCrossRef>(map)); 1352 return *this; 1353 } 1354 1355 /// \brief Make a copy of the given blue node map. 1356 /// 1357 /// This function makes a copy of the given blue node map for the newly 1358 /// created graph. 1359 /// The key type of the new map \c tmap should be the Node type of 1360 /// the destination graph with the blue items, and the key type of 1361 /// the original map \c map should be the Node type of the source 1362 /// graph. 1363 template <typename FromMap, typename ToMap> 1364 BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) { 1365 _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode, 1366 NodeRefMap, FromMap, ToMap>(map, tmap)); 1367 return *this; 1368 } 1369 1370 /// \brief Copy the arc references into the given map. 1371 /// 1372 /// This function copies the arc references into the given map. 1373 /// The parameter should be a map, whose key type is the Arc type of 1374 /// the source graph, while the value type is the Arc type of the 1375 /// destination graph. 1376 template <typename ArcRef> 1377 BpGraphCopy& arcRef(ArcRef& map) { 1378 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, 1379 ArcRefMap, ArcRef>(map)); 1380 return *this; 1381 } 1382 1383 /// \brief Copy the arc cross references into the given map. 1384 /// 1385 /// This function copies the arc cross references (reverse references) 1386 /// into the given map. The parameter should be a map, whose key type 1387 /// is the Arc type of the destination graph, while the value type is 1388 /// the Arc type of the source graph. 1389 template <typename ArcCrossRef> 1390 BpGraphCopy& arcCrossRef(ArcCrossRef& map) { 1391 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, 1392 ArcRefMap, ArcCrossRef>(map)); 1393 return *this; 1394 } 1395 1396 /// \brief Make a copy of the given arc map. 1397 /// 1398 /// This function makes a copy of the given arc map for the newly 1399 /// created graph. 1400 /// The key type of the new map \c tmap should be the Arc type of the 1401 /// destination graph, and the key type of the original map \c map 1402 /// should be the Arc type of the source graph. 1403 template <typename FromMap, typename ToMap> 1404 BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 1405 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 1406 ArcRefMap, FromMap, ToMap>(map, tmap)); 1407 return *this; 1408 } 1409 1410 /// \brief Make a copy of the given arc. 1411 /// 1412 /// This function makes a copy of the given arc. 1413 BpGraphCopy& arc(const Arc& arc, TArc& tarc) { 1414 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 1415 ArcRefMap, TArc>(arc, tarc)); 1416 return *this; 1417 } 1418 1419 /// \brief Copy the edge references into the given map. 1420 /// 1421 /// This function copies the edge references into the given map. 1422 /// The parameter should be a map, whose key type is the Edge type of 1423 /// the source graph, while the value type is the Edge type of the 1424 /// destination graph. 1425 template <typename EdgeRef> 1426 BpGraphCopy& edgeRef(EdgeRef& map) { 1427 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, 1428 EdgeRefMap, EdgeRef>(map)); 1429 return *this; 1430 } 1431 1432 /// \brief Copy the edge cross references into the given map. 1433 /// 1434 /// This function copies the edge cross references (reverse references) 1435 /// into the given map. The parameter should be a map, whose key type 1436 /// is the Edge type of the destination graph, while the value type is 1437 /// the Edge type of the source graph. 1438 template <typename EdgeCrossRef> 1439 BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1440 _edge_maps.push_back(new _core_bits::CrossRefCopy<From, 1441 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1442 return *this; 1443 } 1444 1445 /// \brief Make a copy of the given edge map. 1446 /// 1447 /// This function makes a copy of the given edge map for the newly 1448 /// created graph. 1449 /// The key type of the new map \c tmap should be the Edge type of the 1450 /// destination graph, and the key type of the original map \c map 1451 /// should be the Edge type of the source graph. 1452 template <typename FromMap, typename ToMap> 1453 BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { 1454 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 1455 EdgeRefMap, FromMap, ToMap>(map, tmap)); 1456 return *this; 1457 } 1458 1459 /// \brief Make a copy of the given edge. 1460 /// 1461 /// This function makes a copy of the given edge. 1462 BpGraphCopy& edge(const Edge& edge, TEdge& tedge) { 1463 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 1464 EdgeRefMap, TEdge>(edge, tedge)); 1465 return *this; 1466 } 1467 1468 /// \brief Execute copying. 1469 /// 1470 /// This function executes the copying of the graph along with the 1471 /// copying of the assigned data. 1472 void run() { 1473 NodeRefMap nodeRefMap(_from); 1474 EdgeRefMap edgeRefMap(_from); 1475 ArcRefMap arcRefMap(_from, _to, edgeRefMap); 1476 _core_bits::BpGraphCopySelector<To>:: 1477 copy(_from, _to, nodeRefMap, edgeRefMap); 1478 for (int i = 0; i < int(_node_maps.size()); ++i) { 1479 _node_maps[i]>copy(_from, nodeRefMap); 1480 } 1481 for (int i = 0; i < int(_red_maps.size()); ++i) { 1482 _red_maps[i]>copy(_from, nodeRefMap); 1483 } 1484 for (int i = 0; i < int(_blue_maps.size()); ++i) { 1485 _blue_maps[i]>copy(_from, nodeRefMap); 1486 } 1487 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1488 _edge_maps[i]>copy(_from, edgeRefMap); 1489 } 1490 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1491 _arc_maps[i]>copy(_from, arcRefMap); 1492 } 1493 } 1494 1495 private: 1496 1497 const From& _from; 1498 To& _to; 1499 1500 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 1501 _node_maps; 1502 1503 std::vector<_core_bits::MapCopyBase<From, RedNode, NodeRefMap>* > 1504 _red_maps; 1505 1506 std::vector<_core_bits::MapCopyBase<From, BlueNode, NodeRefMap>* > 1507 _blue_maps; 1508 1509 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1510 _arc_maps; 1511 1512 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1513 _edge_maps; 1514 1515 }; 1516 1517 /// \brief Copy a graph to another graph. 1518 /// 1519 /// This function copies a graph to another graph. 1520 /// The complete usage of it is detailed in the BpGraphCopy class, 1521 /// but a short example shows a basic work: 1522 ///\code 1523 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); 1524 ///\endcode 1525 /// 1526 /// After the copy the \c nr map will contain the mapping from the 1527 /// nodes of the \c from graph to the nodes of the \c to graph and 1528 /// \c ecr will contain the mapping from the edges of the \c to graph 1529 /// to the edges of the \c from graph. 1530 /// 1531 /// \see BpGraphCopy 1532 template <typename From, typename To> 1533 BpGraphCopy<From, To> 1534 bpGraphCopy(const From& from, To& to) { 1535 return BpGraphCopy<From, To>(from, to); 1102 1536 } 1103 1537
Note: See TracChangeset
for help on using the changeset viewer.