Implementation of BpGraphCopy (#69)
authorBalazs Dezso <deba@inf.elte.hu>
Tue, 16 Nov 2010 00:59:36 +0100
changeset 1022523e45e37e52
parent 1021 a12cca3ad15a
child 1023 939ee6d1e525
Implementation of BpGraphCopy (#69)
lemon/core.h
test/graph_copy_test.cc
     1.1 --- a/lemon/core.h	Mon Nov 15 09:46:08 2010 +0100
     1.2 +++ b/lemon/core.h	Tue Nov 16 00:59:36 2010 +0100
     1.3 @@ -555,6 +555,37 @@
     1.4        }
     1.5      };
     1.6  
     1.7 +    template <typename BpGraph, typename Enable = void>
     1.8 +    struct BpGraphCopySelector {
     1.9 +      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    1.10 +      static void copy(const From& from, BpGraph &to,
    1.11 +                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    1.12 +        to.clear();
    1.13 +        for (typename From::RedIt it(from); it != INVALID; ++it) {
    1.14 +          nodeRefMap[it] = to.addRedNode();
    1.15 +        }
    1.16 +        for (typename From::BlueIt it(from); it != INVALID; ++it) {
    1.17 +          nodeRefMap[it] = to.addBlueNode();
    1.18 +        }
    1.19 +        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
    1.20 +          edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)],
    1.21 +                                      nodeRefMap[from.blueNode(it)]);
    1.22 +        }
    1.23 +      }
    1.24 +    };
    1.25 +
    1.26 +    template <typename BpGraph>
    1.27 +    struct BpGraphCopySelector<
    1.28 +      BpGraph,
    1.29 +      typename enable_if<typename BpGraph::BuildTag, void>::type>
    1.30 +    {
    1.31 +      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    1.32 +      static void copy(const From& from, BpGraph &to,
    1.33 +                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    1.34 +        to.build(from, nodeRefMap, edgeRefMap);
    1.35 +      }
    1.36 +    };
    1.37 +
    1.38    }
    1.39  
    1.40    /// \brief Check whether a graph is undirected.
    1.41 @@ -1101,6 +1132,409 @@
    1.42      return GraphCopy<From, To>(from, to);
    1.43    }
    1.44  
    1.45 +  /// \brief Class to copy a bipartite graph.
    1.46 +  ///
    1.47 +  /// Class to copy a bipartite graph to another graph (duplicate a
    1.48 +  /// graph). The simplest way of using it is through the
    1.49 +  /// \c bpGraphCopy() function.
    1.50 +  ///
    1.51 +  /// This class not only make a copy of a bipartite graph, but it can
    1.52 +  /// create references and cross references between the nodes, edges
    1.53 +  /// and arcs of the two graphs, and it can copy maps for using with
    1.54 +  /// the newly created graph.
    1.55 +  ///
    1.56 +  /// To make a copy from a graph, first an instance of BpGraphCopy
    1.57 +  /// should be created, then the data belongs to the graph should
    1.58 +  /// assigned to copy. In the end, the \c run() member should be
    1.59 +  /// called.
    1.60 +  ///
    1.61 +  /// The next code copies a graph with several data:
    1.62 +  ///\code
    1.63 +  ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
    1.64 +  ///  // Create references for the nodes
    1.65 +  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
    1.66 +  ///  cg.nodeRef(nr);
    1.67 +  ///  // Create cross references (inverse) for the edges
    1.68 +  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
    1.69 +  ///  cg.edgeCrossRef(ecr);
    1.70 +  ///  // Copy a red map
    1.71 +  ///  OrigBpGraph::RedMap<double> ormap(orig_graph);
    1.72 +  ///  NewBpGraph::RedMap<double> nrmap(new_graph);
    1.73 +  ///  cg.edgeMap(ormap, nrmap);
    1.74 +  ///  // Copy a node
    1.75 +  ///  OrigBpGraph::Node on;
    1.76 +  ///  NewBpGraph::Node nn;
    1.77 +  ///  cg.node(on, nn);
    1.78 +  ///  // Execute copying
    1.79 +  ///  cg.run();
    1.80 +  ///\endcode
    1.81 +  template <typename From, typename To>
    1.82 +  class BpGraphCopy {
    1.83 +  private:
    1.84 +
    1.85 +    typedef typename From::Node Node;
    1.86 +    typedef typename From::RedNode RedNode;
    1.87 +    typedef typename From::BlueNode BlueNode;
    1.88 +    typedef typename From::NodeIt NodeIt;
    1.89 +    typedef typename From::Arc Arc;
    1.90 +    typedef typename From::ArcIt ArcIt;
    1.91 +    typedef typename From::Edge Edge;
    1.92 +    typedef typename From::EdgeIt EdgeIt;
    1.93 +
    1.94 +    typedef typename To::Node TNode;
    1.95 +    typedef typename To::Arc TArc;
    1.96 +    typedef typename To::Edge TEdge;
    1.97 +
    1.98 +    typedef typename From::template NodeMap<TNode> NodeRefMap;
    1.99 +    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
   1.100 +
   1.101 +    struct ArcRefMap {
   1.102 +      ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
   1.103 +        : _from(from), _to(to), _edge_ref(edge_ref) {}
   1.104 +
   1.105 +      typedef typename From::Arc Key;
   1.106 +      typedef typename To::Arc Value;
   1.107 +
   1.108 +      Value operator[](const Key& key) const {
   1.109 +        return _to.direct(_edge_ref[key], _from.direction(key));
   1.110 +      }
   1.111 +
   1.112 +      const From& _from;
   1.113 +      const To& _to;
   1.114 +      const EdgeRefMap& _edge_ref;
   1.115 +    };
   1.116 +
   1.117 +  public:
   1.118 +
   1.119 +    /// \brief Constructor of BpGraphCopy.
   1.120 +    ///
   1.121 +    /// Constructor of BpGraphCopy for copying the content of the
   1.122 +    /// \c from graph into the \c to graph.
   1.123 +    BpGraphCopy(const From& from, To& to)
   1.124 +      : _from(from), _to(to) {}
   1.125 +
   1.126 +    /// \brief Destructor of BpGraphCopy
   1.127 +    ///
   1.128 +    /// Destructor of BpGraphCopy.
   1.129 +    ~BpGraphCopy() {
   1.130 +      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.131 +        delete _node_maps[i];
   1.132 +      }
   1.133 +      for (int i = 0; i < int(_red_maps.size()); ++i) {
   1.134 +        delete _red_maps[i];
   1.135 +      }
   1.136 +      for (int i = 0; i < int(_blue_maps.size()); ++i) {
   1.137 +        delete _blue_maps[i];
   1.138 +      }
   1.139 +      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.140 +        delete _arc_maps[i];
   1.141 +      }
   1.142 +      for (int i = 0; i < int(_edge_maps.size()); ++i) {
   1.143 +        delete _edge_maps[i];
   1.144 +      }
   1.145 +    }
   1.146 +
   1.147 +    /// \brief Copy the node references into the given map.
   1.148 +    ///
   1.149 +    /// This function copies the node references into the given map.
   1.150 +    /// The parameter should be a map, whose key type is the Node type of
   1.151 +    /// the source graph, while the value type is the Node type of the
   1.152 +    /// destination graph.
   1.153 +    template <typename NodeRef>
   1.154 +    BpGraphCopy& nodeRef(NodeRef& map) {
   1.155 +      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
   1.156 +                           NodeRefMap, NodeRef>(map));
   1.157 +      return *this;
   1.158 +    }
   1.159 +
   1.160 +    /// \brief Copy the node cross references into the given map.
   1.161 +    ///
   1.162 +    /// This function copies the node cross references (reverse references)
   1.163 +    /// into the given map. The parameter should be a map, whose key type
   1.164 +    /// is the Node type of the destination graph, while the value type is
   1.165 +    /// the Node type of the source graph.
   1.166 +    template <typename NodeCrossRef>
   1.167 +    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
   1.168 +      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
   1.169 +                           NodeRefMap, NodeCrossRef>(map));
   1.170 +      return *this;
   1.171 +    }
   1.172 +
   1.173 +    /// \brief Make a copy of the given node map.
   1.174 +    ///
   1.175 +    /// This function makes a copy of the given node map for the newly
   1.176 +    /// created graph.
   1.177 +    /// The key type of the new map \c tmap should be the Node type of the
   1.178 +    /// destination graph, and the key type of the original map \c map
   1.179 +    /// should be the Node type of the source graph.
   1.180 +    template <typename FromMap, typename ToMap>
   1.181 +    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
   1.182 +      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
   1.183 +                           NodeRefMap, FromMap, ToMap>(map, tmap));
   1.184 +      return *this;
   1.185 +    }
   1.186 +
   1.187 +    /// \brief Make a copy of the given node.
   1.188 +    ///
   1.189 +    /// This function makes a copy of the given node.
   1.190 +    BpGraphCopy& node(const Node& node, TNode& tnode) {
   1.191 +      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
   1.192 +                           NodeRefMap, TNode>(node, tnode));
   1.193 +      return *this;
   1.194 +    }
   1.195 +
   1.196 +    /// \brief Copy the red node references into the given map.
   1.197 +    ///
   1.198 +    /// This function copies the red node references into the given
   1.199 +    /// map.  The parameter should be a map, whose key type is the
   1.200 +    /// Node type of the source graph with the red item set, while the
   1.201 +    /// value type is the Node type of the destination graph.
   1.202 +    template <typename RedRef>
   1.203 +    BpGraphCopy& redRef(RedRef& map) {
   1.204 +      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
   1.205 +                          NodeRefMap, RedRef>(map));
   1.206 +      return *this;
   1.207 +    }
   1.208 +
   1.209 +    /// \brief Copy the red node cross references into the given map.
   1.210 +    ///
   1.211 +    /// This function copies the red node cross references (reverse
   1.212 +    /// references) into the given map. The parameter should be a map,
   1.213 +    /// whose key type is the Node type of the destination graph with
   1.214 +    /// the red item set, while the value type is the Node type of the
   1.215 +    /// source graph.
   1.216 +    template <typename RedCrossRef>
   1.217 +    BpGraphCopy& redCrossRef(RedCrossRef& map) {
   1.218 +      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
   1.219 +                          NodeRefMap, RedCrossRef>(map));
   1.220 +      return *this;
   1.221 +    }
   1.222 +
   1.223 +    /// \brief Make a copy of the given red node map.
   1.224 +    ///
   1.225 +    /// This function makes a copy of the given red node map for the newly
   1.226 +    /// created graph.
   1.227 +    /// The key type of the new map \c tmap should be the Node type of
   1.228 +    /// the destination graph with the red items, and the key type of
   1.229 +    /// the original map \c map should be the Node type of the source
   1.230 +    /// graph.
   1.231 +    template <typename FromMap, typename ToMap>
   1.232 +    BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) {
   1.233 +      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
   1.234 +                           NodeRefMap, FromMap, ToMap>(map, tmap));
   1.235 +      return *this;
   1.236 +    }
   1.237 +
   1.238 +    /// \brief Copy the blue node references into the given map.
   1.239 +    ///
   1.240 +    /// This function copies the blue node references into the given
   1.241 +    /// map.  The parameter should be a map, whose key type is the
   1.242 +    /// Node type of the source graph with the blue item set, while the
   1.243 +    /// value type is the Node type of the destination graph.
   1.244 +    template <typename BlueRef>
   1.245 +    BpGraphCopy& blueRef(BlueRef& map) {
   1.246 +      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
   1.247 +                           NodeRefMap, BlueRef>(map));
   1.248 +      return *this;
   1.249 +    }
   1.250 +
   1.251 +    /// \brief Copy the blue node cross references into the given map.
   1.252 +    ///
   1.253 +    /// This function copies the blue node cross references (reverse
   1.254 +    /// references) into the given map. The parameter should be a map,
   1.255 +    /// whose key type is the Node type of the destination graph with
   1.256 +    /// the blue item set, while the value type is the Node type of the
   1.257 +    /// source graph.
   1.258 +    template <typename BlueCrossRef>
   1.259 +    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
   1.260 +      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
   1.261 +                           NodeRefMap, BlueCrossRef>(map));
   1.262 +      return *this;
   1.263 +    }
   1.264 +
   1.265 +    /// \brief Make a copy of the given blue node map.
   1.266 +    ///
   1.267 +    /// This function makes a copy of the given blue node map for the newly
   1.268 +    /// created graph.
   1.269 +    /// The key type of the new map \c tmap should be the Node type of
   1.270 +    /// the destination graph with the blue items, and the key type of
   1.271 +    /// the original map \c map should be the Node type of the source
   1.272 +    /// graph.
   1.273 +    template <typename FromMap, typename ToMap>
   1.274 +    BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) {
   1.275 +      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
   1.276 +                           NodeRefMap, FromMap, ToMap>(map, tmap));
   1.277 +      return *this;
   1.278 +    }
   1.279 +
   1.280 +    /// \brief Copy the arc references into the given map.
   1.281 +    ///
   1.282 +    /// This function copies the arc references into the given map.
   1.283 +    /// The parameter should be a map, whose key type is the Arc type of
   1.284 +    /// the source graph, while the value type is the Arc type of the
   1.285 +    /// destination graph.
   1.286 +    template <typename ArcRef>
   1.287 +    BpGraphCopy& arcRef(ArcRef& map) {
   1.288 +      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
   1.289 +                          ArcRefMap, ArcRef>(map));
   1.290 +      return *this;
   1.291 +    }
   1.292 +
   1.293 +    /// \brief Copy the arc cross references into the given map.
   1.294 +    ///
   1.295 +    /// This function copies the arc cross references (reverse references)
   1.296 +    /// into the given map. The parameter should be a map, whose key type
   1.297 +    /// is the Arc type of the destination graph, while the value type is
   1.298 +    /// the Arc type of the source graph.
   1.299 +    template <typename ArcCrossRef>
   1.300 +    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
   1.301 +      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
   1.302 +                          ArcRefMap, ArcCrossRef>(map));
   1.303 +      return *this;
   1.304 +    }
   1.305 +
   1.306 +    /// \brief Make a copy of the given arc map.
   1.307 +    ///
   1.308 +    /// This function makes a copy of the given arc map for the newly
   1.309 +    /// created graph.
   1.310 +    /// The key type of the new map \c tmap should be the Arc type of the
   1.311 +    /// destination graph, and the key type of the original map \c map
   1.312 +    /// should be the Arc type of the source graph.
   1.313 +    template <typename FromMap, typename ToMap>
   1.314 +    BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
   1.315 +      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
   1.316 +                          ArcRefMap, FromMap, ToMap>(map, tmap));
   1.317 +      return *this;
   1.318 +    }
   1.319 +
   1.320 +    /// \brief Make a copy of the given arc.
   1.321 +    ///
   1.322 +    /// This function makes a copy of the given arc.
   1.323 +    BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
   1.324 +      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
   1.325 +                          ArcRefMap, TArc>(arc, tarc));
   1.326 +      return *this;
   1.327 +    }
   1.328 +
   1.329 +    /// \brief Copy the edge references into the given map.
   1.330 +    ///
   1.331 +    /// This function copies the edge references into the given map.
   1.332 +    /// The parameter should be a map, whose key type is the Edge type of
   1.333 +    /// the source graph, while the value type is the Edge type of the
   1.334 +    /// destination graph.
   1.335 +    template <typename EdgeRef>
   1.336 +    BpGraphCopy& edgeRef(EdgeRef& map) {
   1.337 +      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
   1.338 +                           EdgeRefMap, EdgeRef>(map));
   1.339 +      return *this;
   1.340 +    }
   1.341 +
   1.342 +    /// \brief Copy the edge cross references into the given map.
   1.343 +    ///
   1.344 +    /// This function copies the edge cross references (reverse references)
   1.345 +    /// into the given map. The parameter should be a map, whose key type
   1.346 +    /// is the Edge type of the destination graph, while the value type is
   1.347 +    /// the Edge type of the source graph.
   1.348 +    template <typename EdgeCrossRef>
   1.349 +    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
   1.350 +      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
   1.351 +                           Edge, EdgeRefMap, EdgeCrossRef>(map));
   1.352 +      return *this;
   1.353 +    }
   1.354 +
   1.355 +    /// \brief Make a copy of the given edge map.
   1.356 +    ///
   1.357 +    /// This function makes a copy of the given edge map for the newly
   1.358 +    /// created graph.
   1.359 +    /// The key type of the new map \c tmap should be the Edge type of the
   1.360 +    /// destination graph, and the key type of the original map \c map
   1.361 +    /// should be the Edge type of the source graph.
   1.362 +    template <typename FromMap, typename ToMap>
   1.363 +    BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
   1.364 +      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
   1.365 +                           EdgeRefMap, FromMap, ToMap>(map, tmap));
   1.366 +      return *this;
   1.367 +    }
   1.368 +
   1.369 +    /// \brief Make a copy of the given edge.
   1.370 +    ///
   1.371 +    /// This function makes a copy of the given edge.
   1.372 +    BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
   1.373 +      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
   1.374 +                           EdgeRefMap, TEdge>(edge, tedge));
   1.375 +      return *this;
   1.376 +    }
   1.377 +
   1.378 +    /// \brief Execute copying.
   1.379 +    ///
   1.380 +    /// This function executes the copying of the graph along with the
   1.381 +    /// copying of the assigned data.
   1.382 +    void run() {
   1.383 +      NodeRefMap nodeRefMap(_from);
   1.384 +      EdgeRefMap edgeRefMap(_from);
   1.385 +      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
   1.386 +      _core_bits::BpGraphCopySelector<To>::
   1.387 +        copy(_from, _to, nodeRefMap, edgeRefMap);
   1.388 +      for (int i = 0; i < int(_node_maps.size()); ++i) {
   1.389 +        _node_maps[i]->copy(_from, nodeRefMap);
   1.390 +      }
   1.391 +      for (int i = 0; i < int(_red_maps.size()); ++i) {
   1.392 +        _red_maps[i]->copy(_from, nodeRefMap);
   1.393 +      }
   1.394 +      for (int i = 0; i < int(_blue_maps.size()); ++i) {
   1.395 +        _blue_maps[i]->copy(_from, nodeRefMap);
   1.396 +      }
   1.397 +      for (int i = 0; i < int(_edge_maps.size()); ++i) {
   1.398 +        _edge_maps[i]->copy(_from, edgeRefMap);
   1.399 +      }
   1.400 +      for (int i = 0; i < int(_arc_maps.size()); ++i) {
   1.401 +        _arc_maps[i]->copy(_from, arcRefMap);
   1.402 +      }
   1.403 +    }
   1.404 +
   1.405 +  private:
   1.406 +
   1.407 +    const From& _from;
   1.408 +    To& _to;
   1.409 +
   1.410 +    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
   1.411 +      _node_maps;
   1.412 +
   1.413 +    std::vector<_core_bits::MapCopyBase<From, RedNode, NodeRefMap>* >
   1.414 +      _red_maps;
   1.415 +
   1.416 +    std::vector<_core_bits::MapCopyBase<From, BlueNode, NodeRefMap>* >
   1.417 +      _blue_maps;
   1.418 +
   1.419 +    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
   1.420 +      _arc_maps;
   1.421 +
   1.422 +    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
   1.423 +      _edge_maps;
   1.424 +
   1.425 +  };
   1.426 +
   1.427 +  /// \brief Copy a graph to another graph.
   1.428 +  ///
   1.429 +  /// This function copies a graph to another graph.
   1.430 +  /// The complete usage of it is detailed in the BpGraphCopy class,
   1.431 +  /// but a short example shows a basic work:
   1.432 +  ///\code
   1.433 +  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
   1.434 +  ///\endcode
   1.435 +  ///
   1.436 +  /// After the copy the \c nr map will contain the mapping from the
   1.437 +  /// nodes of the \c from graph to the nodes of the \c to graph and
   1.438 +  /// \c ecr will contain the mapping from the edges of the \c to graph
   1.439 +  /// to the edges of the \c from graph.
   1.440 +  ///
   1.441 +  /// \see BpGraphCopy
   1.442 +  template <typename From, typename To>
   1.443 +  BpGraphCopy<From, To>
   1.444 +  bpGraphCopy(const From& from, To& to) {
   1.445 +    return BpGraphCopy<From, To>(from, to);
   1.446 +  }
   1.447 +
   1.448    namespace _core_bits {
   1.449  
   1.450      template <typename Graph, typename Enable = void>
     2.1 --- a/test/graph_copy_test.cc	Mon Nov 15 09:46:08 2010 +0100
     2.2 +++ b/test/graph_copy_test.cc	Tue Nov 16 00:59:36 2010 +0100
     2.3 @@ -209,6 +209,152 @@
     2.4    check(countArcs(from) == countArcs(to), "Wrong copy.");
     2.5  }
     2.6  
     2.7 +template <typename GR>
     2.8 +void bpgraph_copy_test() {
     2.9 +  const int nn = 10;
    2.10 +
    2.11 +  // Build a graph
    2.12 +  SmartBpGraph from;
    2.13 +  SmartBpGraph::NodeMap<int> fnm(from);
    2.14 +  SmartBpGraph::RedMap<int> frnm(from);
    2.15 +  SmartBpGraph::BlueMap<int> fbnm(from);
    2.16 +  SmartBpGraph::ArcMap<int> fam(from);
    2.17 +  SmartBpGraph::EdgeMap<int> fem(from);
    2.18 +  SmartBpGraph::Node fn = INVALID;
    2.19 +  SmartBpGraph::Arc fa = INVALID;
    2.20 +  SmartBpGraph::Edge fe = INVALID;
    2.21 +
    2.22 +  std::vector<SmartBpGraph::Node> frnv;
    2.23 +  for (int i = 0; i < nn; ++i) {
    2.24 +    SmartBpGraph::Node node = from.addRedNode();
    2.25 +    frnv.push_back(node);
    2.26 +    fnm[node] = i * i;
    2.27 +    frnm[node] = i + i;
    2.28 +    if (i == 0) fn = node;
    2.29 +  }
    2.30 +
    2.31 +  std::vector<SmartBpGraph::Node> fbnv;
    2.32 +  for (int i = 0; i < nn; ++i) {
    2.33 +    SmartBpGraph::Node node = from.addBlueNode();
    2.34 +    fbnv.push_back(node);
    2.35 +    fnm[node] = i * i;
    2.36 +    fbnm[node] = i + i;
    2.37 +  }
    2.38 +
    2.39 +  for (int i = 0; i < nn; ++i) {
    2.40 +    for (int j = 0; j < nn; ++j) {
    2.41 +      SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]);
    2.42 +      fem[edge] = i * i + j * j;
    2.43 +      fam[from.direct(edge, true)] = i + j * j;
    2.44 +      fam[from.direct(edge, false)] = i * i + j;
    2.45 +      if (i == 0 && j == 0) fa = from.direct(edge, true);
    2.46 +      if (i == 0 && j == 0) fe = edge;
    2.47 +    }
    2.48 +  }
    2.49 +
    2.50 +  // Test graph copy
    2.51 +  GR to;
    2.52 +  typename GR::template NodeMap<int> tnm(to);
    2.53 +  typename GR::template RedMap<int> trnm(to);
    2.54 +  typename GR::template BlueMap<int> tbnm(to);
    2.55 +  typename GR::template ArcMap<int> tam(to);
    2.56 +  typename GR::template EdgeMap<int> tem(to);
    2.57 +  typename GR::Node tn;
    2.58 +  typename GR::Arc ta;
    2.59 +  typename GR::Edge te;
    2.60 +
    2.61 +  SmartBpGraph::NodeMap<typename GR::Node> nr(from);
    2.62 +  SmartBpGraph::RedMap<typename GR::Node> rnr(from);
    2.63 +  SmartBpGraph::BlueMap<typename GR::Node> bnr(from);
    2.64 +  SmartBpGraph::ArcMap<typename GR::Arc> ar(from);
    2.65 +  SmartBpGraph::EdgeMap<typename GR::Edge> er(from);
    2.66 +
    2.67 +  typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);
    2.68 +  typename GR::template RedMap<SmartBpGraph::Node> rncr(to);
    2.69 +  typename GR::template BlueMap<SmartBpGraph::Node> bncr(to);
    2.70 +  typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);
    2.71 +  typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);
    2.72 +
    2.73 +  bpGraphCopy(from, to).
    2.74 +    nodeMap(fnm, tnm).redMap(frnm, trnm).blueMap(fbnm, tbnm).
    2.75 +    arcMap(fam, tam).edgeMap(fem, tem).
    2.76 +    nodeRef(nr).redRef(rnr).blueRef(bnr).
    2.77 +    arcRef(ar).edgeRef(er).
    2.78 +    nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).
    2.79 +    arcCrossRef(acr).edgeCrossRef(ecr).
    2.80 +    node(fn, tn).arc(fa, ta).edge(fe, te).run();
    2.81 +
    2.82 +  check(countNodes(from) == countNodes(to), "Wrong copy.");
    2.83 +  check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
    2.84 +  check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");
    2.85 +  check(countEdges(from) == countEdges(to), "Wrong copy.");
    2.86 +  check(countArcs(from) == countArcs(to), "Wrong copy.");
    2.87 +
    2.88 +  for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) {
    2.89 +    check(ncr[nr[it]] == it, "Wrong copy.");
    2.90 +    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
    2.91 +    if (from.red(it)) {
    2.92 +      check(rnr[it] == nr[it], "Wrong copy.");
    2.93 +      check(rncr[rnr[it]] == it, "Wrong copy.");
    2.94 +      check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
    2.95 +      check(to.red(rnr[it]), "Wrong copy.");
    2.96 +    } else {
    2.97 +      check(bnr[it] == nr[it], "Wrong copy.");
    2.98 +      check(bncr[bnr[it]] == it, "Wrong copy.");
    2.99 +      check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
   2.100 +      check(to.blue(bnr[it]), "Wrong copy.");
   2.101 +    }
   2.102 +  }
   2.103 +
   2.104 +  for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) {
   2.105 +    check(acr[ar[it]] == it, "Wrong copy.");
   2.106 +    check(fam[it] == tam[ar[it]], "Wrong copy.");
   2.107 +    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
   2.108 +    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
   2.109 +  }
   2.110 +
   2.111 +  for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) {
   2.112 +    check(ecr[er[it]] == it, "Wrong copy.");
   2.113 +    check(fem[it] == tem[er[it]], "Wrong copy.");
   2.114 +    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
   2.115 +          "Wrong copy.");
   2.116 +    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
   2.117 +          "Wrong copy.");
   2.118 +    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
   2.119 +          "Wrong copy.");
   2.120 +  }
   2.121 +
   2.122 +  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
   2.123 +    check(nr[ncr[it]] == it, "Wrong copy.");
   2.124 +  }
   2.125 +  for (typename GR::RedIt it(to); it != INVALID; ++it) {
   2.126 +    check(rncr[it] == ncr[it], "Wrong copy.");
   2.127 +    check(rnr[rncr[it]] == it, "Wrong copy.");
   2.128 +  }
   2.129 +  for (typename GR::BlueIt it(to); it != INVALID; ++it) {
   2.130 +    check(bncr[it] == ncr[it], "Wrong copy.");
   2.131 +    check(bnr[bncr[it]] == it, "Wrong copy.");
   2.132 +  }
   2.133 +  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
   2.134 +    check(ar[acr[it]] == it, "Wrong copy.");
   2.135 +  }
   2.136 +  for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
   2.137 +    check(er[ecr[it]] == it, "Wrong copy.");
   2.138 +  }
   2.139 +  check(tn == nr[fn], "Wrong copy.");
   2.140 +  check(ta == ar[fa], "Wrong copy.");
   2.141 +  check(te == er[fe], "Wrong copy.");
   2.142 +
   2.143 +  // Test repeated copy
   2.144 +  bpGraphCopy(from, to).run();
   2.145 +  
   2.146 +  check(countNodes(from) == countNodes(to), "Wrong copy.");
   2.147 +  check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
   2.148 +  check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");
   2.149 +  check(countEdges(from) == countEdges(to), "Wrong copy.");
   2.150 +  check(countArcs(from) == countArcs(to), "Wrong copy.");
   2.151 +}
   2.152 +
   2.153  
   2.154  int main() {
   2.155    digraph_copy_test<SmartDigraph>();
   2.156 @@ -216,6 +362,8 @@
   2.157    digraph_copy_test<StaticDigraph>();
   2.158    graph_copy_test<SmartGraph>();
   2.159    graph_copy_test<ListGraph>();
   2.160 +  bpgraph_copy_test<SmartBpGraph>();
   2.161 +  bpgraph_copy_test<ListBpGraph>();
   2.162  
   2.163    return 0;
   2.164  }