COIN-OR::LEMON - Graph Library

Changeset 1022:523e45e37e52 in lemon-main


Ignore:
Timestamp:
11/16/10 00:59:36 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Implementation of BpGraphCopy? (#69)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r1020 r1022  
    551551      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    552552      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,
    553584                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    554585        to.build(from, nodeRefMap, edgeRefMap);
     
    11001131  graphCopy(const From& from, To& to) {
    11011132    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);
    11021536  }
    11031537
  • test/graph_copy_test.cc

    r894 r1022  
    210210}
    211211
     212template <typename GR>
     213void bpgraph_copy_test() {
     214  const int nn = 10;
     215
     216  // Build a graph
     217  SmartBpGraph from;
     218  SmartBpGraph::NodeMap<int> fnm(from);
     219  SmartBpGraph::RedMap<int> frnm(from);
     220  SmartBpGraph::BlueMap<int> fbnm(from);
     221  SmartBpGraph::ArcMap<int> fam(from);
     222  SmartBpGraph::EdgeMap<int> fem(from);
     223  SmartBpGraph::Node fn = INVALID;
     224  SmartBpGraph::Arc fa = INVALID;
     225  SmartBpGraph::Edge fe = INVALID;
     226
     227  std::vector<SmartBpGraph::Node> frnv;
     228  for (int i = 0; i < nn; ++i) {
     229    SmartBpGraph::Node node = from.addRedNode();
     230    frnv.push_back(node);
     231    fnm[node] = i * i;
     232    frnm[node] = i + i;
     233    if (i == 0) fn = node;
     234  }
     235
     236  std::vector<SmartBpGraph::Node> fbnv;
     237  for (int i = 0; i < nn; ++i) {
     238    SmartBpGraph::Node node = from.addBlueNode();
     239    fbnv.push_back(node);
     240    fnm[node] = i * i;
     241    fbnm[node] = i + i;
     242  }
     243
     244  for (int i = 0; i < nn; ++i) {
     245    for (int j = 0; j < nn; ++j) {
     246      SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]);
     247      fem[edge] = i * i + j * j;
     248      fam[from.direct(edge, true)] = i + j * j;
     249      fam[from.direct(edge, false)] = i * i + j;
     250      if (i == 0 && j == 0) fa = from.direct(edge, true);
     251      if (i == 0 && j == 0) fe = edge;
     252    }
     253  }
     254
     255  // Test graph copy
     256  GR to;
     257  typename GR::template NodeMap<int> tnm(to);
     258  typename GR::template RedMap<int> trnm(to);
     259  typename GR::template BlueMap<int> tbnm(to);
     260  typename GR::template ArcMap<int> tam(to);
     261  typename GR::template EdgeMap<int> tem(to);
     262  typename GR::Node tn;
     263  typename GR::Arc ta;
     264  typename GR::Edge te;
     265
     266  SmartBpGraph::NodeMap<typename GR::Node> nr(from);
     267  SmartBpGraph::RedMap<typename GR::Node> rnr(from);
     268  SmartBpGraph::BlueMap<typename GR::Node> bnr(from);
     269  SmartBpGraph::ArcMap<typename GR::Arc> ar(from);
     270  SmartBpGraph::EdgeMap<typename GR::Edge> er(from);
     271
     272  typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);
     273  typename GR::template RedMap<SmartBpGraph::Node> rncr(to);
     274  typename GR::template BlueMap<SmartBpGraph::Node> bncr(to);
     275  typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);
     276  typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);
     277
     278  bpGraphCopy(from, to).
     279    nodeMap(fnm, tnm).redMap(frnm, trnm).blueMap(fbnm, tbnm).
     280    arcMap(fam, tam).edgeMap(fem, tem).
     281    nodeRef(nr).redRef(rnr).blueRef(bnr).
     282    arcRef(ar).edgeRef(er).
     283    nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).
     284    arcCrossRef(acr).edgeCrossRef(ecr).
     285    node(fn, tn).arc(fa, ta).edge(fe, te).run();
     286
     287  check(countNodes(from) == countNodes(to), "Wrong copy.");
     288  check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
     289  check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");
     290  check(countEdges(from) == countEdges(to), "Wrong copy.");
     291  check(countArcs(from) == countArcs(to), "Wrong copy.");
     292
     293  for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) {
     294    check(ncr[nr[it]] == it, "Wrong copy.");
     295    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
     296    if (from.red(it)) {
     297      check(rnr[it] == nr[it], "Wrong copy.");
     298      check(rncr[rnr[it]] == it, "Wrong copy.");
     299      check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
     300      check(to.red(rnr[it]), "Wrong copy.");
     301    } else {
     302      check(bnr[it] == nr[it], "Wrong copy.");
     303      check(bncr[bnr[it]] == it, "Wrong copy.");
     304      check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
     305      check(to.blue(bnr[it]), "Wrong copy.");
     306    }
     307  }
     308
     309  for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) {
     310    check(acr[ar[it]] == it, "Wrong copy.");
     311    check(fam[it] == tam[ar[it]], "Wrong copy.");
     312    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
     313    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
     314  }
     315
     316  for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) {
     317    check(ecr[er[it]] == it, "Wrong copy.");
     318    check(fem[it] == tem[er[it]], "Wrong copy.");
     319    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
     320          "Wrong copy.");
     321    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
     322          "Wrong copy.");
     323    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
     324          "Wrong copy.");
     325  }
     326
     327  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
     328    check(nr[ncr[it]] == it, "Wrong copy.");
     329  }
     330  for (typename GR::RedIt it(to); it != INVALID; ++it) {
     331    check(rncr[it] == ncr[it], "Wrong copy.");
     332    check(rnr[rncr[it]] == it, "Wrong copy.");
     333  }
     334  for (typename GR::BlueIt it(to); it != INVALID; ++it) {
     335    check(bncr[it] == ncr[it], "Wrong copy.");
     336    check(bnr[bncr[it]] == it, "Wrong copy.");
     337  }
     338  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
     339    check(ar[acr[it]] == it, "Wrong copy.");
     340  }
     341  for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
     342    check(er[ecr[it]] == it, "Wrong copy.");
     343  }
     344  check(tn == nr[fn], "Wrong copy.");
     345  check(ta == ar[fa], "Wrong copy.");
     346  check(te == er[fe], "Wrong copy.");
     347
     348  // Test repeated copy
     349  bpGraphCopy(from, to).run();
     350 
     351  check(countNodes(from) == countNodes(to), "Wrong copy.");
     352  check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
     353  check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");
     354  check(countEdges(from) == countEdges(to), "Wrong copy.");
     355  check(countArcs(from) == countArcs(to), "Wrong copy.");
     356}
     357
    212358
    213359int main() {
     
    217363  graph_copy_test<SmartGraph>();
    218364  graph_copy_test<ListGraph>();
     365  bpgraph_copy_test<SmartBpGraph>();
     366  bpgraph_copy_test<ListBpGraph>();
    219367
    220368  return 0;
Note: See TracChangeset for help on using the changeset viewer.