1.1 --- a/lemon/bits/graph_extender.h Fri Nov 03 14:14:05 2006 +0000
1.2 +++ b/lemon/bits/graph_extender.h Fri Nov 03 14:20:24 2006 +0000
1.3 @@ -282,6 +282,12 @@
1.4 Parent::clear();
1.5 }
1.6
1.7 + template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
1.8 + void clone(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
1.9 + Parent::clone(graph, nodeRef, edgeRef);
1.10 + getNotifier(Node()).build();
1.11 + getNotifier(Edge()).build();
1.12 + }
1.13
1.14 void erase(const Node& node) {
1.15 Edge edge;
1.16 @@ -687,6 +693,15 @@
1.17 Parent::clear();
1.18 }
1.19
1.20 + template <typename Graph, typename NodeRefMap, typename UEdgeRefMap>
1.21 + void clone(const Graph& graph, NodeRefMap& nodeRef,
1.22 + UEdgeRefMap& uEdgeRef) {
1.23 + Parent::clone(graph, nodeRef, uEdgeRef);
1.24 + getNotifier(Node()).build();
1.25 + getNotifier(UEdge()).build();
1.26 + getNotifier(Edge()).build();
1.27 + }
1.28 +
1.29 void erase(const Node& node) {
1.30 Edge edge;
1.31 Parent::firstOut(edge, node);
1.32 @@ -1301,6 +1316,18 @@
1.33 Parent::clear();
1.34 }
1.35
1.36 + template <typename Graph, typename ANodeRefMap,
1.37 + typename BNodeRefMap, typename UEdgeRefMap>
1.38 + void clone(const Graph& graph, ANodeRefMap& aNodeRef,
1.39 + BNodeRefMap& bNodeRef, UEdgeRefMap& uEdgeRef) {
1.40 + Parent::clone(graph, aNodeRef, bNodeRef, uEdgeRef);
1.41 + getNotifier(ANode()).build();
1.42 + getNotifier(BNode()).build();
1.43 + getNotifier(Node()).build();
1.44 + getNotifier(UEdge()).build();
1.45 + getNotifier(Edge()).build();
1.46 + }
1.47 +
1.48 void erase(const Node& node) {
1.49 UEdge uedge;
1.50 if (Parent::aNode(node)) {
2.1 --- a/lemon/bits/traits.h Fri Nov 03 14:14:05 2006 +0000
2.2 +++ b/lemon/bits/traits.h Fri Nov 03 14:20:24 2006 +0000
2.3 @@ -323,7 +323,18 @@
2.4 static const bool value = true;
2.5 };
2.6
2.7 + template <typename Graph, typename Enable = void>
2.8 + struct CloneableTagIndicator {
2.9 + static const bool value = false;
2.10 + };
2.11
2.12 + template <typename Graph>
2.13 + struct CloneableTagIndicator<
2.14 + Graph,
2.15 + typename enable_if<typename Graph::CloneableTag, void>::type
2.16 + > {
2.17 + static const bool value = true;
2.18 + };
2.19
2.20 }
2.21
3.1 --- a/lemon/graph_utils.h Fri Nov 03 14:14:05 2006 +0000
3.2 +++ b/lemon/graph_utils.h Fri Nov 03 14:20:24 2006 +0000
3.3 @@ -615,6 +615,21 @@
3.4 const SourceMap& _map;
3.5 };
3.6
3.7 + template <typename Graph, typename Item, typename RefMap, typename It>
3.8 + class ItemCopy : public MapCopyBase<Graph, Item, RefMap> {
3.9 + public:
3.10 +
3.11 + ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
3.12 +
3.13 + virtual void copy(const Graph&, const RefMap& refMap) {
3.14 + _it = refMap[_item];
3.15 + }
3.16 +
3.17 + private:
3.18 + It& _it;
3.19 + Item _item;
3.20 + };
3.21 +
3.22 template <typename Graph, typename Item, typename RefMap, typename Ref>
3.23 class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
3.24 public:
3.25 @@ -650,6 +665,95 @@
3.26 CrossRef& _cmap;
3.27 };
3.28
3.29 + template <typename Graph, typename Enable = void>
3.30 + struct GraphCopySelector {
3.31 + template <typename Source, typename NodeRefMap, typename EdgeRefMap>
3.32 + static void copy(Graph &target, const Source& source,
3.33 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
3.34 + for (typename Source::NodeIt it(source); it != INVALID; ++it) {
3.35 + nodeRefMap[it] = target.addNode();
3.36 + }
3.37 + for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
3.38 + edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
3.39 + nodeRefMap[source.target(it)]);
3.40 + }
3.41 + }
3.42 + };
3.43 +
3.44 + template <typename Graph>
3.45 + struct GraphCopySelector<
3.46 + Graph,
3.47 + typename enable_if<typename Graph::CloneableTag, void>::type>
3.48 + {
3.49 + template <typename Source, typename NodeRefMap, typename EdgeRefMap>
3.50 + static void copy(Graph &target, const Source& source,
3.51 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
3.52 + target.clone(source, nodeRefMap, edgeRefMap);
3.53 + }
3.54 + };
3.55 +
3.56 + template <typename UGraph, typename Enable = void>
3.57 + struct UGraphCopySelector {
3.58 + template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
3.59 + static void copy(UGraph &target, const Source& source,
3.60 + NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
3.61 + for (typename Source::NodeIt it(source); it != INVALID; ++it) {
3.62 + nodeRefMap[it] = target.addNode();
3.63 + }
3.64 + for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
3.65 + uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
3.66 + nodeRefMap[source.target(it)]);
3.67 + }
3.68 + }
3.69 + };
3.70 +
3.71 + template <typename UGraph>
3.72 + struct UGraphCopySelector<
3.73 + UGraph,
3.74 + typename enable_if<typename UGraph::CloneableTag, void>::type>
3.75 + {
3.76 + template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
3.77 + static void copy(UGraph &target, const Source& source,
3.78 + NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
3.79 + target.clone(source, nodeRefMap, uEdgeRefMap);
3.80 + }
3.81 + };
3.82 +
3.83 + template <typename BpUGraph, typename Enable = void>
3.84 + struct BpUGraphCopySelector {
3.85 + template <typename Source, typename ANodeRefMap,
3.86 + typename BNodeRefMap, typename UEdgeRefMap>
3.87 + static void copy(BpUGraph &target, const Source& source,
3.88 + ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
3.89 + UEdgeRefMap& uEdgeRefMap) {
3.90 + for (typename Source::ANodeIt it(source); it != INVALID; ++it) {
3.91 + aNodeRefMap[it] = target.addANode();
3.92 + }
3.93 + for (typename Source::BNodeIt it(source); it != INVALID; ++it) {
3.94 + bNodeRefMap[it] = target.addBNode();
3.95 + }
3.96 + for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
3.97 + uEdgeRefMap[it] = target.addEdge(aNodeRefMap[source.aNode(it)],
3.98 + bNodeRefMap[source.bNode(it)]);
3.99 + }
3.100 + }
3.101 + };
3.102 +
3.103 + template <typename BpUGraph>
3.104 + struct BpUGraphCopySelector<
3.105 + BpUGraph,
3.106 + typename enable_if<typename BpUGraph::CloneableTag, void>::type>
3.107 + {
3.108 + template <typename Source, typename ANodeRefMap,
3.109 + typename BNodeRefMap, typename UEdgeRefMap>
3.110 + static void copy(BpUGraph &target, const Source& source,
3.111 + ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
3.112 + UEdgeRefMap& uEdgeRefMap) {
3.113 + target.clone(source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
3.114 + }
3.115 + };
3.116 +
3.117 +
3.118 }
3.119
3.120 /// \brief Class to copy a graph.
3.121 @@ -705,9 +809,10 @@
3.122 return *this;
3.123 }
3.124
3.125 - /// \brief Reverse and copies the node references into the given map.
3.126 + /// \brief Copies the node cross references into the given map.
3.127 ///
3.128 - /// Reverse and copies the node references into the given map.
3.129 + /// Copies the node cross references (reverse references) into
3.130 + /// the given map.
3.131 template <typename NodeCrossRef>
3.132 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
3.133 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
3.134 @@ -728,6 +833,15 @@
3.135 return *this;
3.136 }
3.137
3.138 + /// \brief Make a copy of the given node.
3.139 + ///
3.140 + /// Make a copy of the given node.
3.141 + GraphCopy& node(TNode& tnode, const Node& node) {
3.142 + nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
3.143 + NodeRefMap, TNode>(tnode, node));
3.144 + return *this;
3.145 + }
3.146 +
3.147 /// \brief Copies the edge references into the given map.
3.148 ///
3.149 /// Copies the edge references into the given map.
3.150 @@ -738,9 +852,10 @@
3.151 return *this;
3.152 }
3.153
3.154 - /// \brief Reverse and copies the edge references into the given map.
3.155 + /// \brief Copies the edge cross references into the given map.
3.156 ///
3.157 - /// Reverse and copies the edge references into the given map.
3.158 + /// Copies the edge cross references (reverse references) into
3.159 + /// the given map.
3.160 template <typename EdgeCrossRef>
3.161 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
3.162 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
3.163 @@ -761,29 +876,34 @@
3.164 return *this;
3.165 }
3.166
3.167 + /// \brief Make a copy of the given edge.
3.168 + ///
3.169 + /// Make a copy of the given edge.
3.170 + GraphCopy& edge(TEdge& tedge, const Edge& edge) {
3.171 + edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
3.172 + EdgeRefMap, TEdge>(tedge, edge));
3.173 + return *this;
3.174 + }
3.175 +
3.176 /// \brief Executes the copies.
3.177 ///
3.178 /// Executes the copies.
3.179 void run() {
3.180 NodeRefMap nodeRefMap(source);
3.181 - for (NodeIt it(source); it != INVALID; ++it) {
3.182 - nodeRefMap[it] = target.addNode();
3.183 - }
3.184 + EdgeRefMap edgeRefMap(source);
3.185 + _graph_utils_bits::GraphCopySelector<Target>::
3.186 + copy(target, source, nodeRefMap, edgeRefMap);
3.187 for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
3.188 nodeMapCopies[i]->copy(source, nodeRefMap);
3.189 }
3.190 - EdgeRefMap edgeRefMap(source);
3.191 - for (EdgeIt it(source); it != INVALID; ++it) {
3.192 - edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
3.193 - nodeRefMap[source.target(it)]);
3.194 - }
3.195 for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
3.196 edgeMapCopies[i]->copy(source, edgeRefMap);
3.197 - }
3.198 + }
3.199 }
3.200
3.201 - private:
3.202 -
3.203 + protected:
3.204 +
3.205 +
3.206 const Source& source;
3.207 Target& target;
3.208
3.209 @@ -808,6 +928,8 @@
3.210 /// source graph's nodes to the target graph's nodes and the \c ecr will
3.211 /// contain the mapping from the target graph's edges to the source's
3.212 /// edges.
3.213 + ///
3.214 + /// \see GraphCopy
3.215 template <typename Target, typename Source>
3.216 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
3.217 return GraphCopy<Target, Source>(target, source);
3.218 @@ -894,9 +1016,10 @@
3.219 return *this;
3.220 }
3.221
3.222 - /// \brief Reverse and copies the node references into the given map.
3.223 + /// \brief Copies the node cross references into the given map.
3.224 ///
3.225 - /// Reverse and copies the node references into the given map.
3.226 + /// Copies the node cross references (reverse references) into
3.227 + /// the given map.
3.228 template <typename NodeCrossRef>
3.229 UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
3.230 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
3.231 @@ -917,6 +1040,15 @@
3.232 return *this;
3.233 }
3.234
3.235 + /// \brief Make a copy of the given node.
3.236 + ///
3.237 + /// Make a copy of the given node.
3.238 + UGraphCopy& node(TNode& tnode, const Node& node) {
3.239 + nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
3.240 + NodeRefMap, TNode>(tnode, node));
3.241 + return *this;
3.242 + }
3.243 +
3.244 /// \brief Copies the edge references into the given map.
3.245 ///
3.246 /// Copies the edge references into the given map.
3.247 @@ -927,9 +1059,10 @@
3.248 return *this;
3.249 }
3.250
3.251 - /// \brief Reverse and copies the edge references into the given map.
3.252 + /// \brief Copies the edge cross references into the given map.
3.253 ///
3.254 - /// Reverse and copies the edge references into the given map.
3.255 + /// Copies the edge cross references (reverse references) into
3.256 + /// the given map.
3.257 template <typename EdgeCrossRef>
3.258 UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
3.259 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
3.260 @@ -950,9 +1083,18 @@
3.261 return *this;
3.262 }
3.263
3.264 - /// \brief Copies the uEdge references into the given map.
3.265 + /// \brief Make a copy of the given edge.
3.266 ///
3.267 - /// Copies the uEdge references into the given map.
3.268 + /// Make a copy of the given edge.
3.269 + UGraphCopy& edge(TEdge& tedge, const Edge& edge) {
3.270 + edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
3.271 + EdgeRefMap, TEdge>(tedge, edge));
3.272 + return *this;
3.273 + }
3.274 +
3.275 + /// \brief Copies the undirected edge references into the given map.
3.276 + ///
3.277 + /// Copies the undirected edge references into the given map.
3.278 template <typename UEdgeRef>
3.279 UGraphCopy& uEdgeRef(UEdgeRef& map) {
3.280 uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
3.281 @@ -960,9 +1102,10 @@
3.282 return *this;
3.283 }
3.284
3.285 - /// \brief Reverse and copies the uEdge references into the given map.
3.286 + /// \brief Copies the undirected edge cross references into the given map.
3.287 ///
3.288 - /// Reverse and copies the uEdge references into the given map.
3.289 + /// Copies the undirected edge cross references (reverse
3.290 + /// references) into the given map.
3.291 template <typename UEdgeCrossRef>
3.292 UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
3.293 uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
3.294 @@ -973,8 +1116,8 @@
3.295 /// \brief Make copy of the given map.
3.296 ///
3.297 /// Makes copy of the given map for the newly created graph.
3.298 - /// The new map's key type is the target graph's uEdge type,
3.299 - /// and the copied map's key type is the source graph's uEdge
3.300 + /// The new map's key type is the target graph's undirected edge type,
3.301 + /// and the copied map's key type is the source graph's undirected edge
3.302 /// type.
3.303 template <typename TargetMap, typename SourceMap>
3.304 UGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
3.305 @@ -983,23 +1126,27 @@
3.306 return *this;
3.307 }
3.308
3.309 + /// \brief Make a copy of the given undirected edge.
3.310 + ///
3.311 + /// Make a copy of the given undirected edge.
3.312 + UGraphCopy& uEdge(TUEdge& tuedge, const UEdge& uedge) {
3.313 + uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge,
3.314 + UEdgeRefMap, TUEdge>(tuedge, uedge));
3.315 + return *this;
3.316 + }
3.317 +
3.318 /// \brief Executes the copies.
3.319 ///
3.320 /// Executes the copies.
3.321 void run() {
3.322 NodeRefMap nodeRefMap(source);
3.323 - for (NodeIt it(source); it != INVALID; ++it) {
3.324 - nodeRefMap[it] = target.addNode();
3.325 - }
3.326 + UEdgeRefMap uEdgeRefMap(source);
3.327 + EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
3.328 + _graph_utils_bits::UGraphCopySelector<Target>::
3.329 + copy(target, source, nodeRefMap, uEdgeRefMap);
3.330 for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
3.331 nodeMapCopies[i]->copy(source, nodeRefMap);
3.332 }
3.333 - UEdgeRefMap uEdgeRefMap(source);
3.334 - EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
3.335 - for (UEdgeIt it(source); it != INVALID; ++it) {
3.336 - uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
3.337 - nodeRefMap[source.target(it)]);
3.338 - }
3.339 for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
3.340 uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
3.341 }
3.342 @@ -1024,9 +1171,9 @@
3.343
3.344 };
3.345
3.346 - /// \brief Copy a graph to another graph.
3.347 + /// \brief Copy an undirected graph to another graph.
3.348 ///
3.349 - /// Copy a graph to another graph.
3.350 + /// Copy an undirected graph to another graph.
3.351 /// The usage of the function:
3.352 ///
3.353 ///\code
3.354 @@ -1037,12 +1184,378 @@
3.355 /// source graph's nodes to the target graph's nodes and the \c ecr will
3.356 /// contain the mapping from the target graph's edges to the source's
3.357 /// edges.
3.358 + ///
3.359 + /// \see UGraphCopy
3.360 template <typename Target, typename Source>
3.361 UGraphCopy<Target, Source>
3.362 copyUGraph(Target& target, const Source& source) {
3.363 return UGraphCopy<Target, Source>(target, source);
3.364 }
3.365
3.366 + /// \brief Class to copy a bipartite undirected graph.
3.367 + ///
3.368 + /// Class to copy a bipartite undirected graph to another graph
3.369 + /// (duplicate a graph). The simplest way of using it is through
3.370 + /// the \c copyBpUGraph() function.
3.371 + template <typename Target, typename Source>
3.372 + class BpUGraphCopy {
3.373 + private:
3.374 +
3.375 + typedef typename Source::Node Node;
3.376 + typedef typename Source::ANode ANode;
3.377 + typedef typename Source::BNode BNode;
3.378 + typedef typename Source::NodeIt NodeIt;
3.379 + typedef typename Source::Edge Edge;
3.380 + typedef typename Source::EdgeIt EdgeIt;
3.381 + typedef typename Source::UEdge UEdge;
3.382 + typedef typename Source::UEdgeIt UEdgeIt;
3.383 +
3.384 + typedef typename Target::Node TNode;
3.385 + typedef typename Target::Edge TEdge;
3.386 + typedef typename Target::UEdge TUEdge;
3.387 +
3.388 + typedef typename Source::template ANodeMap<TNode> ANodeRefMap;
3.389 + typedef typename Source::template BNodeMap<TNode> BNodeRefMap;
3.390 + typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
3.391 +
3.392 + struct NodeRefMap {
3.393 + NodeRefMap(const Source& _source, const ANodeRefMap& _anode_ref,
3.394 + const BNodeRefMap& _bnode_ref)
3.395 + : source(_source), anode_ref(_anode_ref), bnode_ref(_bnode_ref) {}
3.396 +
3.397 + typedef typename Source::Node Key;
3.398 + typedef typename Target::Node Value;
3.399 +
3.400 + Value operator[](const Key& key) const {
3.401 + return source.aNode(key) ? anode_ref[key] : bnode_ref[key];
3.402 + }
3.403 +
3.404 + const Source& source;
3.405 + const ANodeRefMap& anode_ref;
3.406 + const BNodeRefMap& bnode_ref;
3.407 + };
3.408 +
3.409 + struct EdgeRefMap {
3.410 + EdgeRefMap(const Target& _target, const Source& _source,
3.411 + const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
3.412 + : target(_target), source(_source),
3.413 + uedge_ref(_uedge_ref), node_ref(_node_ref) {}
3.414 +
3.415 + typedef typename Source::Edge Key;
3.416 + typedef typename Target::Edge Value;
3.417 +
3.418 + Value operator[](const Key& key) const {
3.419 + bool forward = (source.direction(key) ==
3.420 + (node_ref[source.source((UEdge)key)] ==
3.421 + target.source(uedge_ref[(UEdge)key])));
3.422 + return target.direct(uedge_ref[key], forward);
3.423 + }
3.424 +
3.425 + const Target& target;
3.426 + const Source& source;
3.427 + const UEdgeRefMap& uedge_ref;
3.428 + const NodeRefMap& node_ref;
3.429 + };
3.430 +
3.431 + public:
3.432 +
3.433 +
3.434 + /// \brief Constructor for the GraphCopy.
3.435 + ///
3.436 + /// It copies the content of the \c _source graph into the
3.437 + /// \c _target graph.
3.438 + BpUGraphCopy(Target& _target, const Source& _source)
3.439 + : source(_source), target(_target) {}
3.440 +
3.441 + /// \brief Destructor of the GraphCopy
3.442 + ///
3.443 + /// Destructor of the GraphCopy
3.444 + ~BpUGraphCopy() {
3.445 + for (int i = 0; i < (int)aNodeMapCopies.size(); ++i) {
3.446 + delete aNodeMapCopies[i];
3.447 + }
3.448 + for (int i = 0; i < (int)bNodeMapCopies.size(); ++i) {
3.449 + delete bNodeMapCopies[i];
3.450 + }
3.451 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
3.452 + delete nodeMapCopies[i];
3.453 + }
3.454 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
3.455 + delete edgeMapCopies[i];
3.456 + }
3.457 + for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
3.458 + delete uEdgeMapCopies[i];
3.459 + }
3.460 +
3.461 + }
3.462 +
3.463 + /// \brief Copies the A-node references into the given map.
3.464 + ///
3.465 + /// Copies the A-node references into the given map.
3.466 + template <typename ANodeRef>
3.467 + BpUGraphCopy& aNodeRef(ANodeRef& map) {
3.468 + aNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, ANode,
3.469 + ANodeRefMap, ANodeRef>(map));
3.470 + return *this;
3.471 + }
3.472 +
3.473 + /// \brief Copies the A-node cross references into the given map.
3.474 + ///
3.475 + /// Copies the A-node cross references (reverse references) into
3.476 + /// the given map.
3.477 + template <typename ANodeCrossRef>
3.478 + BpUGraphCopy& aNodeCrossRef(ANodeCrossRef& map) {
3.479 + aNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
3.480 + ANode, ANodeRefMap, ANodeCrossRef>(map));
3.481 + return *this;
3.482 + }
3.483 +
3.484 + /// \brief Make copy of the given A-node map.
3.485 + ///
3.486 + /// Makes copy of the given map for the newly created graph.
3.487 + /// The new map's key type is the target graph's node type,
3.488 + /// and the copied map's key type is the source graph's node
3.489 + /// type.
3.490 + template <typename TargetMap, typename SourceMap>
3.491 + BpUGraphCopy& aNodeMap(TargetMap& tmap, const SourceMap& map) {
3.492 + aNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, ANode,
3.493 + ANodeRefMap, TargetMap, SourceMap>(tmap, map));
3.494 + return *this;
3.495 + }
3.496 +
3.497 + /// \brief Copies the B-node references into the given map.
3.498 + ///
3.499 + /// Copies the B-node references into the given map.
3.500 + template <typename BNodeRef>
3.501 + BpUGraphCopy& bNodeRef(BNodeRef& map) {
3.502 + bNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, BNode,
3.503 + BNodeRefMap, BNodeRef>(map));
3.504 + return *this;
3.505 + }
3.506 +
3.507 + /// \brief Copies the B-node cross references into the given map.
3.508 + ///
3.509 + /// Copies the B-node cross references (reverse references) into
3.510 + /// the given map.
3.511 + template <typename BNodeCrossRef>
3.512 + BpUGraphCopy& bNodeCrossRef(BNodeCrossRef& map) {
3.513 + bNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
3.514 + BNode, BNodeRefMap, BNodeCrossRef>(map));
3.515 + return *this;
3.516 + }
3.517 +
3.518 + /// \brief Make copy of the given B-node map.
3.519 + ///
3.520 + /// Makes copy of the given map for the newly created graph.
3.521 + /// The new map's key type is the target graph's node type,
3.522 + /// and the copied map's key type is the source graph's node
3.523 + /// type.
3.524 + template <typename TargetMap, typename SourceMap>
3.525 + BpUGraphCopy& bNodeMap(TargetMap& tmap, const SourceMap& map) {
3.526 + bNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, BNode,
3.527 + BNodeRefMap, TargetMap, SourceMap>(tmap, map));
3.528 + return *this;
3.529 + }
3.530 + /// \brief Copies the node references into the given map.
3.531 + ///
3.532 + /// Copies the node references into the given map.
3.533 + template <typename NodeRef>
3.534 + BpUGraphCopy& nodeRef(NodeRef& map) {
3.535 + nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
3.536 + NodeRefMap, NodeRef>(map));
3.537 + return *this;
3.538 + }
3.539 +
3.540 + /// \brief Copies the node cross references into the given map.
3.541 + ///
3.542 + /// Copies the node cross references (reverse references) into
3.543 + /// the given map.
3.544 + template <typename NodeCrossRef>
3.545 + BpUGraphCopy& nodeCrossRef(NodeCrossRef& map) {
3.546 + nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
3.547 + NodeRefMap, NodeCrossRef>(map));
3.548 + return *this;
3.549 + }
3.550 +
3.551 + /// \brief Make copy of the given map.
3.552 + ///
3.553 + /// Makes copy of the given map for the newly created graph.
3.554 + /// The new map's key type is the target graph's node type,
3.555 + /// and the copied map's key type is the source graph's node
3.556 + /// type.
3.557 + template <typename TargetMap, typename SourceMap>
3.558 + BpUGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
3.559 + nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
3.560 + NodeRefMap, TargetMap, SourceMap>(tmap, map));
3.561 + return *this;
3.562 + }
3.563 +
3.564 + /// \brief Make a copy of the given node.
3.565 + ///
3.566 + /// Make a copy of the given node.
3.567 + BpUGraphCopy& node(TNode& tnode, const Node& node) {
3.568 + nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
3.569 + NodeRefMap, TNode>(tnode, node));
3.570 + return *this;
3.571 + }
3.572 +
3.573 + /// \brief Copies the edge references into the given map.
3.574 + ///
3.575 + /// Copies the edge references into the given map.
3.576 + template <typename EdgeRef>
3.577 + BpUGraphCopy& edgeRef(EdgeRef& map) {
3.578 + edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
3.579 + EdgeRefMap, EdgeRef>(map));
3.580 + return *this;
3.581 + }
3.582 +
3.583 + /// \brief Copies the edge cross references into the given map.
3.584 + ///
3.585 + /// Copies the edge cross references (reverse references) into
3.586 + /// the given map.
3.587 + template <typename EdgeCrossRef>
3.588 + BpUGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
3.589 + edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
3.590 + EdgeRefMap, EdgeCrossRef>(map));
3.591 + return *this;
3.592 + }
3.593 +
3.594 + /// \brief Make copy of the given map.
3.595 + ///
3.596 + /// Makes copy of the given map for the newly created graph.
3.597 + /// The new map's key type is the target graph's edge type,
3.598 + /// and the copied map's key type is the source graph's edge
3.599 + /// type.
3.600 + template <typename TargetMap, typename SourceMap>
3.601 + BpUGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
3.602 + edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
3.603 + EdgeRefMap, TargetMap, SourceMap>(tmap, map));
3.604 + return *this;
3.605 + }
3.606 +
3.607 + /// \brief Make a copy of the given edge.
3.608 + ///
3.609 + /// Make a copy of the given edge.
3.610 + BpUGraphCopy& edge(TEdge& tedge, const Edge& edge) {
3.611 + edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
3.612 + EdgeRefMap, TEdge>(tedge, edge));
3.613 + return *this;
3.614 + }
3.615 +
3.616 + /// \brief Copies the undirected edge references into the given map.
3.617 + ///
3.618 + /// Copies the undirected edge references into the given map.
3.619 + template <typename UEdgeRef>
3.620 + BpUGraphCopy& uEdgeRef(UEdgeRef& map) {
3.621 + uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
3.622 + UEdgeRefMap, UEdgeRef>(map));
3.623 + return *this;
3.624 + }
3.625 +
3.626 + /// \brief Copies the undirected edge cross references into the given map.
3.627 + ///
3.628 + /// Copies the undirected edge cross references (reverse
3.629 + /// references) into the given map.
3.630 + template <typename UEdgeCrossRef>
3.631 + BpUGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
3.632 + uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
3.633 + UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
3.634 + return *this;
3.635 + }
3.636 +
3.637 + /// \brief Make copy of the given map.
3.638 + ///
3.639 + /// Makes copy of the given map for the newly created graph.
3.640 + /// The new map's key type is the target graph's undirected edge type,
3.641 + /// and the copied map's key type is the source graph's undirected edge
3.642 + /// type.
3.643 + template <typename TargetMap, typename SourceMap>
3.644 + BpUGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
3.645 + uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge,
3.646 + UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
3.647 + return *this;
3.648 + }
3.649 +
3.650 + /// \brief Make a copy of the given undirected edge.
3.651 + ///
3.652 + /// Make a copy of the given undirected edge.
3.653 + BpUGraphCopy& uEdge(TUEdge& tuedge, const UEdge& uedge) {
3.654 + uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge,
3.655 + UEdgeRefMap, TUEdge>(tuedge, uedge));
3.656 + return *this;
3.657 + }
3.658 +
3.659 + /// \brief Executes the copies.
3.660 + ///
3.661 + /// Executes the copies.
3.662 + void run() {
3.663 + ANodeRefMap aNodeRefMap(source);
3.664 + BNodeRefMap bNodeRefMap(source);
3.665 + NodeRefMap nodeRefMap(source, aNodeRefMap, bNodeRefMap);
3.666 + UEdgeRefMap uEdgeRefMap(source);
3.667 + EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
3.668 + _graph_utils_bits::BpUGraphCopySelector<Target>::
3.669 + copy(target, source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
3.670 + for (int i = 0; i < (int)aNodeMapCopies.size(); ++i) {
3.671 + aNodeMapCopies[i]->copy(source, aNodeRefMap);
3.672 + }
3.673 + for (int i = 0; i < (int)bNodeMapCopies.size(); ++i) {
3.674 + bNodeMapCopies[i]->copy(source, bNodeRefMap);
3.675 + }
3.676 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
3.677 + nodeMapCopies[i]->copy(source, nodeRefMap);
3.678 + }
3.679 + for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
3.680 + uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
3.681 + }
3.682 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
3.683 + edgeMapCopies[i]->copy(source, edgeRefMap);
3.684 + }
3.685 + }
3.686 +
3.687 + private:
3.688 +
3.689 + const Source& source;
3.690 + Target& target;
3.691 +
3.692 + std::vector<_graph_utils_bits::MapCopyBase<Source, ANode, ANodeRefMap>* >
3.693 + aNodeMapCopies;
3.694 +
3.695 + std::vector<_graph_utils_bits::MapCopyBase<Source, BNode, BNodeRefMap>* >
3.696 + bNodeMapCopies;
3.697 +
3.698 + std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
3.699 + nodeMapCopies;
3.700 +
3.701 + std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
3.702 + edgeMapCopies;
3.703 +
3.704 + std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* >
3.705 + uEdgeMapCopies;
3.706 +
3.707 + };
3.708 +
3.709 + /// \brief Copy a bipartite undirected graph to another graph.
3.710 + ///
3.711 + /// Copy a bipartite undirected graph to another graph.
3.712 + /// The usage of the function:
3.713 + ///
3.714 + ///\code
3.715 + /// copyBpUGraph(trg, src).aNodeRef(anr).edgeCrossRef(ecr).run();
3.716 + ///\endcode
3.717 + ///
3.718 + /// After the copy the \c nr map will contain the mapping from the
3.719 + /// source graph's nodes to the target graph's nodes and the \c ecr will
3.720 + /// contain the mapping from the target graph's edges to the source's
3.721 + /// edges.
3.722 + ///
3.723 + /// \see BpUGraphCopy
3.724 + template <typename Target, typename Source>
3.725 + BpUGraphCopy<Target, Source>
3.726 + copyBpUGraph(Target& target, const Source& source) {
3.727 + return BpUGraphCopy<Target, Source>(target, source);
3.728 + }
3.729 +
3.730
3.731 /// @}
3.732
4.1 --- a/test/Makefile.am Fri Nov 03 14:14:05 2006 +0000
4.2 +++ b/test/Makefile.am Fri Nov 03 14:20:24 2006 +0000
4.3 @@ -22,6 +22,7 @@
4.4 test/dim_test \
4.5 test/edge_set_test \
4.6 test/graph_adaptor_test \
4.7 + test/graph_copy_test \
4.8 test/graph_test \
4.9 test/graph_utils_test \
4.10 test/heap_test \
4.11 @@ -65,6 +66,7 @@
4.12 test_dim_test_SOURCES = test/dim_test.cc
4.13 test_edge_set_test_SOURCES = test/edge_set_test.cc
4.14 test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
4.15 +test_graph_copy_test_SOURCES = test/graph_copy_test.cc
4.16 test_graph_test_SOURCES = test/graph_test.cc
4.17 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
4.18 test_heap_test_SOURCES = test/heap_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/graph_copy_test.cc Fri Nov 03 14:20:24 2006 +0000
5.3 @@ -0,0 +1,312 @@
5.4 +#include <lemon/smart_graph.h>
5.5 +#include <lemon/list_graph.h>
5.6 +#include <lemon/graph_reader.h>
5.7 +#include <lemon/graph_utils.h>
5.8 +#include <lemon/error.h>
5.9 +
5.10 +#include "test_tools.h"
5.11 +
5.12 +using namespace std;
5.13 +using namespace lemon;
5.14 +
5.15 +void graph_copy_test() {
5.16 + const int nn = 10;
5.17 +
5.18 + SmartGraph source;
5.19 + SmartGraph::NodeMap<int> snm(source);
5.20 + SmartGraph::EdgeMap<int> sem(source);
5.21 + SmartGraph::Node sn = INVALID;
5.22 + SmartGraph::Edge se = INVALID;
5.23 +
5.24 + std::vector<SmartGraph::Node> snv;
5.25 + for (int i = 0; i < nn; ++i) {
5.26 + SmartGraph::Node node = source.addNode();
5.27 + snv.push_back(node);
5.28 + snm[node] = i * i;
5.29 + if (i == 0) sn = node;
5.30 + }
5.31 +
5.32 + for (int i = 0; i < nn; ++i) {
5.33 + for (int j = 0; j < nn; ++j) {
5.34 + SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);
5.35 + sem[edge] = i + j * j;
5.36 + if (i == 0 && j == 0) se = edge;
5.37 + }
5.38 + }
5.39 +
5.40 + ListGraph target;
5.41 + ListGraph::NodeMap<int> tnm(target);
5.42 + ListGraph::EdgeMap<int> tem(target);
5.43 + ListGraph::Node tn;
5.44 + ListGraph::Edge te;
5.45 +
5.46 + SmartGraph::NodeMap<ListGraph::Node> nr(source);
5.47 + SmartGraph::EdgeMap<ListGraph::Edge> er(source);
5.48 +
5.49 + ListGraph::NodeMap<SmartGraph::Node> ncr(target);
5.50 + ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
5.51 +
5.52 + GraphCopy<ListGraph, SmartGraph>(target, source).
5.53 + nodeMap(tnm, snm).edgeMap(tem, sem).
5.54 + nodeRef(nr).edgeRef(er).
5.55 + nodeCrossRef(ncr).edgeCrossRef(ecr).
5.56 + node(tn, sn).edge(te, se).run();
5.57 +
5.58 + for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {
5.59 + check(ncr[nr[it]] == it, "Wrong copy.");
5.60 + check(snm[it] == tnm[nr[it]], "Wrong copy.");
5.61 + }
5.62 +
5.63 + for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {
5.64 + check(ecr[er[it]] == it, "Wrong copy.");
5.65 + check(sem[it] == tem[er[it]], "Wrong copy.");
5.66 + check(nr[source.source(it)] ==
5.67 + target.source(er[it]), "Wrong copy.");
5.68 + check(nr[source.target(it)] ==
5.69 + target.target(er[it]), "Wrong copy.");
5.70 + }
5.71 +
5.72 + for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
5.73 + check(nr[ncr[it]] == it, "Wrong copy.");
5.74 + }
5.75 +
5.76 + for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {
5.77 + check(er[ecr[it]] == it, "Wrong copy.");
5.78 + }
5.79 + check(tn == nr[sn], "Wrong copy.");
5.80 + check(te == er[se], "Wrong copy.");
5.81 +}
5.82 +
5.83 +void ugraph_copy_test() {
5.84 + const int nn = 10;
5.85 +
5.86 + SmartUGraph source;
5.87 + SmartUGraph::NodeMap<int> snm(source);
5.88 + SmartUGraph::EdgeMap<int> sem(source);
5.89 + SmartUGraph::UEdgeMap<int> suem(source);
5.90 + SmartUGraph::Node sn = INVALID;
5.91 + SmartUGraph::Edge se = INVALID;
5.92 + SmartUGraph::UEdge sue = INVALID;
5.93 +
5.94 + std::vector<SmartGraph::Node> snv;
5.95 + for (int i = 0; i < nn; ++i) {
5.96 + SmartUGraph::Node node = source.addNode();
5.97 + snv.push_back(node);
5.98 + snm[node] = i * i;
5.99 + if (i == 0) sn = node;
5.100 + }
5.101 +
5.102 + for (int i = 0; i < nn; ++i) {
5.103 + for (int j = 0; j < nn; ++j) {
5.104 + SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);
5.105 + suem[edge] = i * i + j * j;
5.106 + sem[source.direct(edge, true)] = i + j * j;
5.107 + sem[source.direct(edge, false)] = i * i + j;
5.108 + if (i == 0 && j == 0) se = source.direct(edge, true);
5.109 + if (i == 0 && j == 0) sue = edge;
5.110 + }
5.111 + }
5.112 +
5.113 + ListUGraph target;
5.114 + ListUGraph::NodeMap<int> tnm(target);
5.115 + ListUGraph::EdgeMap<int> tem(target);
5.116 + ListUGraph::UEdgeMap<int> tuem(target);
5.117 + ListUGraph::Node tn;
5.118 + ListUGraph::Edge te;
5.119 + ListUGraph::UEdge tue;
5.120 +
5.121 + SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
5.122 + SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
5.123 + SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
5.124 +
5.125 + ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
5.126 + ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
5.127 + ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
5.128 +
5.129 + UGraphCopy<ListUGraph, SmartUGraph>(target, source).
5.130 + nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).
5.131 + nodeRef(nr).edgeRef(er).uEdgeRef(uer).
5.132 + nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).
5.133 + node(tn, sn).edge(te, se).uEdge(tue, sue).run();
5.134 +
5.135 + for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {
5.136 + check(ncr[nr[it]] == it, "Wrong copy.");
5.137 + check(snm[it] == tnm[nr[it]], "Wrong copy.");
5.138 + }
5.139 +
5.140 + for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {
5.141 + check(ecr[er[it]] == it, "Wrong copy.");
5.142 + check(sem[it] == tem[er[it]], "Wrong copy.");
5.143 + check(nr[source.source(it)] ==
5.144 + target.source(er[it]), "Wrong copy.");
5.145 + check(nr[source.target(it)] ==
5.146 + target.target(er[it]), "Wrong copy.");
5.147 + }
5.148 +
5.149 + for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {
5.150 + check(uecr[uer[it]] == it, "Wrong copy.");
5.151 + check(suem[it] == tuem[uer[it]], "Wrong copy.");
5.152 + check(nr[source.source(it)] == target.source(uer[it]) ||
5.153 + nr[source.source(it)] == target.target(uer[it]),
5.154 + "Wrong copy.");
5.155 + check(nr[source.target(it)] == target.source(uer[it]) ||
5.156 + nr[source.target(it)] == target.target(uer[it]),
5.157 + "Wrong copy.");
5.158 + check((source.source(it) != source.target(it)) ==
5.159 + (target.source(uer[it]) != target.target(uer[it])),
5.160 + "Wrong copy.");
5.161 + }
5.162 +
5.163 + for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
5.164 + check(nr[ncr[it]] == it, "Wrong copy.");
5.165 + }
5.166 +
5.167 + for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {
5.168 + check(er[ecr[it]] == it, "Wrong copy.");
5.169 + }
5.170 + for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {
5.171 + check(uer[uecr[it]] == it, "Wrong copy.");
5.172 + }
5.173 + check(tn == nr[sn], "Wrong copy.");
5.174 + check(te == er[se], "Wrong copy.");
5.175 + check(tue == uer[sue], "Wrong copy.");
5.176 +}
5.177 +
5.178 +void bpugraph_copy_test() {
5.179 + const int nn = 10;
5.180 +
5.181 + SmartBpUGraph source;
5.182 + SmartBpUGraph::ANodeMap<int> sanm(source);
5.183 + SmartBpUGraph::BNodeMap<int> sbnm(source);
5.184 + SmartBpUGraph::NodeMap<int> snm(source);
5.185 + SmartBpUGraph::EdgeMap<int> sem(source);
5.186 + SmartBpUGraph::UEdgeMap<int> suem(source);
5.187 + SmartBpUGraph::Node sn = INVALID;
5.188 + SmartBpUGraph::Edge se = INVALID;
5.189 + SmartBpUGraph::UEdge sue = INVALID;
5.190 +
5.191 + std::vector<SmartBpUGraph::Node> sanv;
5.192 + for (int i = 0; i < nn; ++i) {
5.193 + SmartBpUGraph::Node node = source.addANode();
5.194 + sanv.push_back(node);
5.195 + sanm[node] = i * i;
5.196 + snm[node] = i * i + i;
5.197 + if (i == 0) sn = node;
5.198 + }
5.199 +
5.200 + std::vector<SmartBpUGraph::Node> sbnv;
5.201 + for (int i = 0; i < nn; ++i) {
5.202 + SmartBpUGraph::Node node = source.addBNode();
5.203 + sbnv.push_back(node);
5.204 + sbnm[node] = i * i - i;
5.205 + snm[node] = i * i + i + 1;
5.206 + }
5.207 +
5.208 + for (int i = 0; i < nn; ++i) {
5.209 + for (int j = 0; j < nn; ++j) {
5.210 + SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);
5.211 + suem[edge] = i * i + j * j;
5.212 + sem[source.direct(edge, true)] = i + j * j;
5.213 + sem[source.direct(edge, false)] = i * i + j;
5.214 + if (i == 0 && j == 0) se = source.direct(edge, true);
5.215 + if (i == 0 && j == 0) sue = edge;
5.216 + }
5.217 + }
5.218 +
5.219 + ListBpUGraph target;
5.220 + ListBpUGraph::ANodeMap<int> tanm(target);
5.221 + ListBpUGraph::BNodeMap<int> tbnm(target);
5.222 + ListBpUGraph::NodeMap<int> tnm(target);
5.223 + ListBpUGraph::EdgeMap<int> tem(target);
5.224 + ListBpUGraph::UEdgeMap<int> tuem(target);
5.225 + ListBpUGraph::Node tn;
5.226 + ListBpUGraph::Edge te;
5.227 + ListBpUGraph::UEdge tue;
5.228 +
5.229 + SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
5.230 + SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
5.231 + SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
5.232 + SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
5.233 + SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);
5.234 +
5.235 + ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
5.236 + ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
5.237 + ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
5.238 + ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
5.239 + ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);
5.240 +
5.241 + BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).
5.242 + aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).
5.243 + edgeMap(tem, sem).uEdgeMap(tuem, suem).
5.244 + aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).
5.245 + aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).
5.246 + edgeCrossRef(ecr).uEdgeCrossRef(uecr).
5.247 + node(tn, sn).edge(te, se).uEdge(tue, sue).run();
5.248 +
5.249 + for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {
5.250 + check(nr[it] == anr[it], "Wrong copy.");
5.251 + check(ancr[anr[it]] == it, "Wrong copy.");
5.252 + check(sanm[it] == tanm[anr[it]], "Wrong copy.");
5.253 + }
5.254 +
5.255 + for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {
5.256 + check(nr[it] == bnr[it], "Wrong copy.");
5.257 + check(bncr[bnr[it]] == it, "Wrong copy.");
5.258 + check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");
5.259 + }
5.260 +
5.261 + for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {
5.262 + check(ncr[nr[it]] == it, "Wrong copy.");
5.263 + check(snm[it] == tnm[nr[it]], "Wrong copy.");
5.264 + }
5.265 +
5.266 + for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {
5.267 + check(ecr[er[it]] == it, "Wrong copy.");
5.268 + check(sem[it] == tem[er[it]], "Wrong copy.");
5.269 + check(nr[source.source(it)] ==
5.270 + target.source(er[it]), "Wrong copy.");
5.271 + check(nr[source.target(it)] ==
5.272 + target.target(er[it]), "Wrong copy.");
5.273 + }
5.274 +
5.275 + for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {
5.276 + check(uecr[uer[it]] == it, "Wrong copy.");
5.277 + check(suem[it] == tuem[uer[it]], "Wrong copy.");
5.278 + check(nr[source.aNode(it)] ==
5.279 + target.aNode(uer[it]), "Wrong copy.");
5.280 + check(nr[source.bNode(it)] ==
5.281 + target.bNode(uer[it]), "Wrong copy.");
5.282 + }
5.283 +
5.284 + for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {
5.285 + check(ancr[it] == ncr[it], "Wrong copy.");
5.286 + check(anr[ancr[it]] == it, "Wrong copy.");
5.287 + }
5.288 +
5.289 + for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {
5.290 + check(bncr[it] == ncr[it], "Wrong copy.");
5.291 + check(bnr[bncr[it]] == it, "Wrong copy.");
5.292 + }
5.293 +
5.294 + for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
5.295 + check(nr[ncr[it]] == it, "Wrong copy.");
5.296 + }
5.297 +
5.298 + for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {
5.299 + check(er[ecr[it]] == it, "Wrong copy.");
5.300 + }
5.301 + for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {
5.302 + check(uer[uecr[it]] == it, "Wrong copy.");
5.303 + }
5.304 + check(tn == nr[sn], "Wrong copy.");
5.305 + check(te == er[se], "Wrong copy.");
5.306 + check(tue == uer[sue], "Wrong copy.");
5.307 +}
5.308 +
5.309 +int main() {
5.310 + graph_copy_test();
5.311 + ugraph_copy_test();
5.312 + bpugraph_copy_test();
5.313 +
5.314 + return 0;
5.315 +}