1.1 --- a/lemon/graph_utils.h Fri Nov 03 14:14:05 2006 +0000
1.2 +++ b/lemon/graph_utils.h Fri Nov 03 14:20:24 2006 +0000
1.3 @@ -615,6 +615,21 @@
1.4 const SourceMap& _map;
1.5 };
1.6
1.7 + template <typename Graph, typename Item, typename RefMap, typename It>
1.8 + class ItemCopy : public MapCopyBase<Graph, Item, RefMap> {
1.9 + public:
1.10 +
1.11 + ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
1.12 +
1.13 + virtual void copy(const Graph&, const RefMap& refMap) {
1.14 + _it = refMap[_item];
1.15 + }
1.16 +
1.17 + private:
1.18 + It& _it;
1.19 + Item _item;
1.20 + };
1.21 +
1.22 template <typename Graph, typename Item, typename RefMap, typename Ref>
1.23 class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
1.24 public:
1.25 @@ -650,6 +665,95 @@
1.26 CrossRef& _cmap;
1.27 };
1.28
1.29 + template <typename Graph, typename Enable = void>
1.30 + struct GraphCopySelector {
1.31 + template <typename Source, typename NodeRefMap, typename EdgeRefMap>
1.32 + static void copy(Graph &target, const Source& source,
1.33 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.34 + for (typename Source::NodeIt it(source); it != INVALID; ++it) {
1.35 + nodeRefMap[it] = target.addNode();
1.36 + }
1.37 + for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
1.38 + edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.39 + nodeRefMap[source.target(it)]);
1.40 + }
1.41 + }
1.42 + };
1.43 +
1.44 + template <typename Graph>
1.45 + struct GraphCopySelector<
1.46 + Graph,
1.47 + typename enable_if<typename Graph::CloneableTag, void>::type>
1.48 + {
1.49 + template <typename Source, typename NodeRefMap, typename EdgeRefMap>
1.50 + static void copy(Graph &target, const Source& source,
1.51 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.52 + target.clone(source, nodeRefMap, edgeRefMap);
1.53 + }
1.54 + };
1.55 +
1.56 + template <typename UGraph, typename Enable = void>
1.57 + struct UGraphCopySelector {
1.58 + template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
1.59 + static void copy(UGraph &target, const Source& source,
1.60 + NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
1.61 + for (typename Source::NodeIt it(source); it != INVALID; ++it) {
1.62 + nodeRefMap[it] = target.addNode();
1.63 + }
1.64 + for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
1.65 + uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.66 + nodeRefMap[source.target(it)]);
1.67 + }
1.68 + }
1.69 + };
1.70 +
1.71 + template <typename UGraph>
1.72 + struct UGraphCopySelector<
1.73 + UGraph,
1.74 + typename enable_if<typename UGraph::CloneableTag, void>::type>
1.75 + {
1.76 + template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
1.77 + static void copy(UGraph &target, const Source& source,
1.78 + NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
1.79 + target.clone(source, nodeRefMap, uEdgeRefMap);
1.80 + }
1.81 + };
1.82 +
1.83 + template <typename BpUGraph, typename Enable = void>
1.84 + struct BpUGraphCopySelector {
1.85 + template <typename Source, typename ANodeRefMap,
1.86 + typename BNodeRefMap, typename UEdgeRefMap>
1.87 + static void copy(BpUGraph &target, const Source& source,
1.88 + ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
1.89 + UEdgeRefMap& uEdgeRefMap) {
1.90 + for (typename Source::ANodeIt it(source); it != INVALID; ++it) {
1.91 + aNodeRefMap[it] = target.addANode();
1.92 + }
1.93 + for (typename Source::BNodeIt it(source); it != INVALID; ++it) {
1.94 + bNodeRefMap[it] = target.addBNode();
1.95 + }
1.96 + for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
1.97 + uEdgeRefMap[it] = target.addEdge(aNodeRefMap[source.aNode(it)],
1.98 + bNodeRefMap[source.bNode(it)]);
1.99 + }
1.100 + }
1.101 + };
1.102 +
1.103 + template <typename BpUGraph>
1.104 + struct BpUGraphCopySelector<
1.105 + BpUGraph,
1.106 + typename enable_if<typename BpUGraph::CloneableTag, void>::type>
1.107 + {
1.108 + template <typename Source, typename ANodeRefMap,
1.109 + typename BNodeRefMap, typename UEdgeRefMap>
1.110 + static void copy(BpUGraph &target, const Source& source,
1.111 + ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
1.112 + UEdgeRefMap& uEdgeRefMap) {
1.113 + target.clone(source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
1.114 + }
1.115 + };
1.116 +
1.117 +
1.118 }
1.119
1.120 /// \brief Class to copy a graph.
1.121 @@ -705,9 +809,10 @@
1.122 return *this;
1.123 }
1.124
1.125 - /// \brief Reverse and copies the node references into the given map.
1.126 + /// \brief Copies the node cross references into the given map.
1.127 ///
1.128 - /// Reverse and copies the node references into the given map.
1.129 + /// Copies the node cross references (reverse references) into
1.130 + /// the given map.
1.131 template <typename NodeCrossRef>
1.132 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.133 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1.134 @@ -728,6 +833,15 @@
1.135 return *this;
1.136 }
1.137
1.138 + /// \brief Make a copy of the given node.
1.139 + ///
1.140 + /// Make a copy of the given node.
1.141 + GraphCopy& node(TNode& tnode, const Node& node) {
1.142 + nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
1.143 + NodeRefMap, TNode>(tnode, node));
1.144 + return *this;
1.145 + }
1.146 +
1.147 /// \brief Copies the edge references into the given map.
1.148 ///
1.149 /// Copies the edge references into the given map.
1.150 @@ -738,9 +852,10 @@
1.151 return *this;
1.152 }
1.153
1.154 - /// \brief Reverse and copies the edge references into the given map.
1.155 + /// \brief Copies the edge cross references into the given map.
1.156 ///
1.157 - /// Reverse and copies the edge references into the given map.
1.158 + /// Copies the edge cross references (reverse references) into
1.159 + /// the given map.
1.160 template <typename EdgeCrossRef>
1.161 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.162 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1.163 @@ -761,29 +876,34 @@
1.164 return *this;
1.165 }
1.166
1.167 + /// \brief Make a copy of the given edge.
1.168 + ///
1.169 + /// Make a copy of the given edge.
1.170 + GraphCopy& edge(TEdge& tedge, const Edge& edge) {
1.171 + edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
1.172 + EdgeRefMap, TEdge>(tedge, edge));
1.173 + return *this;
1.174 + }
1.175 +
1.176 /// \brief Executes the copies.
1.177 ///
1.178 /// Executes the copies.
1.179 void run() {
1.180 NodeRefMap nodeRefMap(source);
1.181 - for (NodeIt it(source); it != INVALID; ++it) {
1.182 - nodeRefMap[it] = target.addNode();
1.183 - }
1.184 + EdgeRefMap edgeRefMap(source);
1.185 + _graph_utils_bits::GraphCopySelector<Target>::
1.186 + copy(target, source, nodeRefMap, edgeRefMap);
1.187 for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.188 nodeMapCopies[i]->copy(source, nodeRefMap);
1.189 }
1.190 - EdgeRefMap edgeRefMap(source);
1.191 - for (EdgeIt it(source); it != INVALID; ++it) {
1.192 - edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.193 - nodeRefMap[source.target(it)]);
1.194 - }
1.195 for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.196 edgeMapCopies[i]->copy(source, edgeRefMap);
1.197 - }
1.198 + }
1.199 }
1.200
1.201 - private:
1.202 -
1.203 + protected:
1.204 +
1.205 +
1.206 const Source& source;
1.207 Target& target;
1.208
1.209 @@ -808,6 +928,8 @@
1.210 /// source graph's nodes to the target graph's nodes and the \c ecr will
1.211 /// contain the mapping from the target graph's edges to the source's
1.212 /// edges.
1.213 + ///
1.214 + /// \see GraphCopy
1.215 template <typename Target, typename Source>
1.216 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
1.217 return GraphCopy<Target, Source>(target, source);
1.218 @@ -894,9 +1016,10 @@
1.219 return *this;
1.220 }
1.221
1.222 - /// \brief Reverse and copies the node references into the given map.
1.223 + /// \brief Copies the node cross references into the given map.
1.224 ///
1.225 - /// Reverse and copies the node references into the given map.
1.226 + /// Copies the node cross references (reverse references) into
1.227 + /// the given map.
1.228 template <typename NodeCrossRef>
1.229 UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.230 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1.231 @@ -917,6 +1040,15 @@
1.232 return *this;
1.233 }
1.234
1.235 + /// \brief Make a copy of the given node.
1.236 + ///
1.237 + /// Make a copy of the given node.
1.238 + UGraphCopy& node(TNode& tnode, const Node& node) {
1.239 + nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
1.240 + NodeRefMap, TNode>(tnode, node));
1.241 + return *this;
1.242 + }
1.243 +
1.244 /// \brief Copies the edge references into the given map.
1.245 ///
1.246 /// Copies the edge references into the given map.
1.247 @@ -927,9 +1059,10 @@
1.248 return *this;
1.249 }
1.250
1.251 - /// \brief Reverse and copies the edge references into the given map.
1.252 + /// \brief Copies the edge cross references into the given map.
1.253 ///
1.254 - /// Reverse and copies the edge references into the given map.
1.255 + /// Copies the edge cross references (reverse references) into
1.256 + /// the given map.
1.257 template <typename EdgeCrossRef>
1.258 UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.259 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1.260 @@ -950,9 +1083,18 @@
1.261 return *this;
1.262 }
1.263
1.264 - /// \brief Copies the uEdge references into the given map.
1.265 + /// \brief Make a copy of the given edge.
1.266 ///
1.267 - /// Copies the uEdge references into the given map.
1.268 + /// Make a copy of the given edge.
1.269 + UGraphCopy& edge(TEdge& tedge, const Edge& edge) {
1.270 + edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
1.271 + EdgeRefMap, TEdge>(tedge, edge));
1.272 + return *this;
1.273 + }
1.274 +
1.275 + /// \brief Copies the undirected edge references into the given map.
1.276 + ///
1.277 + /// Copies the undirected edge references into the given map.
1.278 template <typename UEdgeRef>
1.279 UGraphCopy& uEdgeRef(UEdgeRef& map) {
1.280 uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
1.281 @@ -960,9 +1102,10 @@
1.282 return *this;
1.283 }
1.284
1.285 - /// \brief Reverse and copies the uEdge references into the given map.
1.286 + /// \brief Copies the undirected edge cross references into the given map.
1.287 ///
1.288 - /// Reverse and copies the uEdge references into the given map.
1.289 + /// Copies the undirected edge cross references (reverse
1.290 + /// references) into the given map.
1.291 template <typename UEdgeCrossRef>
1.292 UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1.293 uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1.294 @@ -973,8 +1116,8 @@
1.295 /// \brief Make copy of the given map.
1.296 ///
1.297 /// Makes copy of the given map for the newly created graph.
1.298 - /// The new map's key type is the target graph's uEdge type,
1.299 - /// and the copied map's key type is the source graph's uEdge
1.300 + /// The new map's key type is the target graph's undirected edge type,
1.301 + /// and the copied map's key type is the source graph's undirected edge
1.302 /// type.
1.303 template <typename TargetMap, typename SourceMap>
1.304 UGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
1.305 @@ -983,23 +1126,27 @@
1.306 return *this;
1.307 }
1.308
1.309 + /// \brief Make a copy of the given undirected edge.
1.310 + ///
1.311 + /// Make a copy of the given undirected edge.
1.312 + UGraphCopy& uEdge(TUEdge& tuedge, const UEdge& uedge) {
1.313 + uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge,
1.314 + UEdgeRefMap, TUEdge>(tuedge, uedge));
1.315 + return *this;
1.316 + }
1.317 +
1.318 /// \brief Executes the copies.
1.319 ///
1.320 /// Executes the copies.
1.321 void run() {
1.322 NodeRefMap nodeRefMap(source);
1.323 - for (NodeIt it(source); it != INVALID; ++it) {
1.324 - nodeRefMap[it] = target.addNode();
1.325 - }
1.326 + UEdgeRefMap uEdgeRefMap(source);
1.327 + EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
1.328 + _graph_utils_bits::UGraphCopySelector<Target>::
1.329 + copy(target, source, nodeRefMap, uEdgeRefMap);
1.330 for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.331 nodeMapCopies[i]->copy(source, nodeRefMap);
1.332 }
1.333 - UEdgeRefMap uEdgeRefMap(source);
1.334 - EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
1.335 - for (UEdgeIt it(source); it != INVALID; ++it) {
1.336 - uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.337 - nodeRefMap[source.target(it)]);
1.338 - }
1.339 for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
1.340 uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
1.341 }
1.342 @@ -1024,9 +1171,9 @@
1.343
1.344 };
1.345
1.346 - /// \brief Copy a graph to another graph.
1.347 + /// \brief Copy an undirected graph to another graph.
1.348 ///
1.349 - /// Copy a graph to another graph.
1.350 + /// Copy an undirected graph to another graph.
1.351 /// The usage of the function:
1.352 ///
1.353 ///\code
1.354 @@ -1037,12 +1184,378 @@
1.355 /// source graph's nodes to the target graph's nodes and the \c ecr will
1.356 /// contain the mapping from the target graph's edges to the source's
1.357 /// edges.
1.358 + ///
1.359 + /// \see UGraphCopy
1.360 template <typename Target, typename Source>
1.361 UGraphCopy<Target, Source>
1.362 copyUGraph(Target& target, const Source& source) {
1.363 return UGraphCopy<Target, Source>(target, source);
1.364 }
1.365
1.366 + /// \brief Class to copy a bipartite undirected graph.
1.367 + ///
1.368 + /// Class to copy a bipartite undirected graph to another graph
1.369 + /// (duplicate a graph). The simplest way of using it is through
1.370 + /// the \c copyBpUGraph() function.
1.371 + template <typename Target, typename Source>
1.372 + class BpUGraphCopy {
1.373 + private:
1.374 +
1.375 + typedef typename Source::Node Node;
1.376 + typedef typename Source::ANode ANode;
1.377 + typedef typename Source::BNode BNode;
1.378 + typedef typename Source::NodeIt NodeIt;
1.379 + typedef typename Source::Edge Edge;
1.380 + typedef typename Source::EdgeIt EdgeIt;
1.381 + typedef typename Source::UEdge UEdge;
1.382 + typedef typename Source::UEdgeIt UEdgeIt;
1.383 +
1.384 + typedef typename Target::Node TNode;
1.385 + typedef typename Target::Edge TEdge;
1.386 + typedef typename Target::UEdge TUEdge;
1.387 +
1.388 + typedef typename Source::template ANodeMap<TNode> ANodeRefMap;
1.389 + typedef typename Source::template BNodeMap<TNode> BNodeRefMap;
1.390 + typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
1.391 +
1.392 + struct NodeRefMap {
1.393 + NodeRefMap(const Source& _source, const ANodeRefMap& _anode_ref,
1.394 + const BNodeRefMap& _bnode_ref)
1.395 + : source(_source), anode_ref(_anode_ref), bnode_ref(_bnode_ref) {}
1.396 +
1.397 + typedef typename Source::Node Key;
1.398 + typedef typename Target::Node Value;
1.399 +
1.400 + Value operator[](const Key& key) const {
1.401 + return source.aNode(key) ? anode_ref[key] : bnode_ref[key];
1.402 + }
1.403 +
1.404 + const Source& source;
1.405 + const ANodeRefMap& anode_ref;
1.406 + const BNodeRefMap& bnode_ref;
1.407 + };
1.408 +
1.409 + struct EdgeRefMap {
1.410 + EdgeRefMap(const Target& _target, const Source& _source,
1.411 + const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
1.412 + : target(_target), source(_source),
1.413 + uedge_ref(_uedge_ref), node_ref(_node_ref) {}
1.414 +
1.415 + typedef typename Source::Edge Key;
1.416 + typedef typename Target::Edge Value;
1.417 +
1.418 + Value operator[](const Key& key) const {
1.419 + bool forward = (source.direction(key) ==
1.420 + (node_ref[source.source((UEdge)key)] ==
1.421 + target.source(uedge_ref[(UEdge)key])));
1.422 + return target.direct(uedge_ref[key], forward);
1.423 + }
1.424 +
1.425 + const Target& target;
1.426 + const Source& source;
1.427 + const UEdgeRefMap& uedge_ref;
1.428 + const NodeRefMap& node_ref;
1.429 + };
1.430 +
1.431 + public:
1.432 +
1.433 +
1.434 + /// \brief Constructor for the GraphCopy.
1.435 + ///
1.436 + /// It copies the content of the \c _source graph into the
1.437 + /// \c _target graph.
1.438 + BpUGraphCopy(Target& _target, const Source& _source)
1.439 + : source(_source), target(_target) {}
1.440 +
1.441 + /// \brief Destructor of the GraphCopy
1.442 + ///
1.443 + /// Destructor of the GraphCopy
1.444 + ~BpUGraphCopy() {
1.445 + for (int i = 0; i < (int)aNodeMapCopies.size(); ++i) {
1.446 + delete aNodeMapCopies[i];
1.447 + }
1.448 + for (int i = 0; i < (int)bNodeMapCopies.size(); ++i) {
1.449 + delete bNodeMapCopies[i];
1.450 + }
1.451 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.452 + delete nodeMapCopies[i];
1.453 + }
1.454 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.455 + delete edgeMapCopies[i];
1.456 + }
1.457 + for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
1.458 + delete uEdgeMapCopies[i];
1.459 + }
1.460 +
1.461 + }
1.462 +
1.463 + /// \brief Copies the A-node references into the given map.
1.464 + ///
1.465 + /// Copies the A-node references into the given map.
1.466 + template <typename ANodeRef>
1.467 + BpUGraphCopy& aNodeRef(ANodeRef& map) {
1.468 + aNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, ANode,
1.469 + ANodeRefMap, ANodeRef>(map));
1.470 + return *this;
1.471 + }
1.472 +
1.473 + /// \brief Copies the A-node cross references into the given map.
1.474 + ///
1.475 + /// Copies the A-node cross references (reverse references) into
1.476 + /// the given map.
1.477 + template <typename ANodeCrossRef>
1.478 + BpUGraphCopy& aNodeCrossRef(ANodeCrossRef& map) {
1.479 + aNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1.480 + ANode, ANodeRefMap, ANodeCrossRef>(map));
1.481 + return *this;
1.482 + }
1.483 +
1.484 + /// \brief Make copy of the given A-node map.
1.485 + ///
1.486 + /// Makes copy of the given map for the newly created graph.
1.487 + /// The new map's key type is the target graph's node type,
1.488 + /// and the copied map's key type is the source graph's node
1.489 + /// type.
1.490 + template <typename TargetMap, typename SourceMap>
1.491 + BpUGraphCopy& aNodeMap(TargetMap& tmap, const SourceMap& map) {
1.492 + aNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, ANode,
1.493 + ANodeRefMap, TargetMap, SourceMap>(tmap, map));
1.494 + return *this;
1.495 + }
1.496 +
1.497 + /// \brief Copies the B-node references into the given map.
1.498 + ///
1.499 + /// Copies the B-node references into the given map.
1.500 + template <typename BNodeRef>
1.501 + BpUGraphCopy& bNodeRef(BNodeRef& map) {
1.502 + bNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, BNode,
1.503 + BNodeRefMap, BNodeRef>(map));
1.504 + return *this;
1.505 + }
1.506 +
1.507 + /// \brief Copies the B-node cross references into the given map.
1.508 + ///
1.509 + /// Copies the B-node cross references (reverse references) into
1.510 + /// the given map.
1.511 + template <typename BNodeCrossRef>
1.512 + BpUGraphCopy& bNodeCrossRef(BNodeCrossRef& map) {
1.513 + bNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1.514 + BNode, BNodeRefMap, BNodeCrossRef>(map));
1.515 + return *this;
1.516 + }
1.517 +
1.518 + /// \brief Make copy of the given B-node map.
1.519 + ///
1.520 + /// Makes copy of the given map for the newly created graph.
1.521 + /// The new map's key type is the target graph's node type,
1.522 + /// and the copied map's key type is the source graph's node
1.523 + /// type.
1.524 + template <typename TargetMap, typename SourceMap>
1.525 + BpUGraphCopy& bNodeMap(TargetMap& tmap, const SourceMap& map) {
1.526 + bNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, BNode,
1.527 + BNodeRefMap, TargetMap, SourceMap>(tmap, map));
1.528 + return *this;
1.529 + }
1.530 + /// \brief Copies the node references into the given map.
1.531 + ///
1.532 + /// Copies the node references into the given map.
1.533 + template <typename NodeRef>
1.534 + BpUGraphCopy& nodeRef(NodeRef& map) {
1.535 + nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
1.536 + NodeRefMap, NodeRef>(map));
1.537 + return *this;
1.538 + }
1.539 +
1.540 + /// \brief Copies the node cross references into the given map.
1.541 + ///
1.542 + /// Copies the node cross references (reverse references) into
1.543 + /// the given map.
1.544 + template <typename NodeCrossRef>
1.545 + BpUGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.546 + nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1.547 + NodeRefMap, NodeCrossRef>(map));
1.548 + return *this;
1.549 + }
1.550 +
1.551 + /// \brief Make copy of the given map.
1.552 + ///
1.553 + /// Makes copy of the given map for the newly created graph.
1.554 + /// The new map's key type is the target graph's node type,
1.555 + /// and the copied map's key type is the source graph's node
1.556 + /// type.
1.557 + template <typename TargetMap, typename SourceMap>
1.558 + BpUGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
1.559 + nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
1.560 + NodeRefMap, TargetMap, SourceMap>(tmap, map));
1.561 + return *this;
1.562 + }
1.563 +
1.564 + /// \brief Make a copy of the given node.
1.565 + ///
1.566 + /// Make a copy of the given node.
1.567 + BpUGraphCopy& node(TNode& tnode, const Node& node) {
1.568 + nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
1.569 + NodeRefMap, TNode>(tnode, node));
1.570 + return *this;
1.571 + }
1.572 +
1.573 + /// \brief Copies the edge references into the given map.
1.574 + ///
1.575 + /// Copies the edge references into the given map.
1.576 + template <typename EdgeRef>
1.577 + BpUGraphCopy& edgeRef(EdgeRef& map) {
1.578 + edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
1.579 + EdgeRefMap, EdgeRef>(map));
1.580 + return *this;
1.581 + }
1.582 +
1.583 + /// \brief Copies the edge cross references into the given map.
1.584 + ///
1.585 + /// Copies the edge cross references (reverse references) into
1.586 + /// the given map.
1.587 + template <typename EdgeCrossRef>
1.588 + BpUGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.589 + edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1.590 + EdgeRefMap, EdgeCrossRef>(map));
1.591 + return *this;
1.592 + }
1.593 +
1.594 + /// \brief Make copy of the given map.
1.595 + ///
1.596 + /// Makes copy of the given map for the newly created graph.
1.597 + /// The new map's key type is the target graph's edge type,
1.598 + /// and the copied map's key type is the source graph's edge
1.599 + /// type.
1.600 + template <typename TargetMap, typename SourceMap>
1.601 + BpUGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
1.602 + edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
1.603 + EdgeRefMap, TargetMap, SourceMap>(tmap, map));
1.604 + return *this;
1.605 + }
1.606 +
1.607 + /// \brief Make a copy of the given edge.
1.608 + ///
1.609 + /// Make a copy of the given edge.
1.610 + BpUGraphCopy& edge(TEdge& tedge, const Edge& edge) {
1.611 + edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
1.612 + EdgeRefMap, TEdge>(tedge, edge));
1.613 + return *this;
1.614 + }
1.615 +
1.616 + /// \brief Copies the undirected edge references into the given map.
1.617 + ///
1.618 + /// Copies the undirected edge references into the given map.
1.619 + template <typename UEdgeRef>
1.620 + BpUGraphCopy& uEdgeRef(UEdgeRef& map) {
1.621 + uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
1.622 + UEdgeRefMap, UEdgeRef>(map));
1.623 + return *this;
1.624 + }
1.625 +
1.626 + /// \brief Copies the undirected edge cross references into the given map.
1.627 + ///
1.628 + /// Copies the undirected edge cross references (reverse
1.629 + /// references) into the given map.
1.630 + template <typename UEdgeCrossRef>
1.631 + BpUGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1.632 + uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1.633 + UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
1.634 + return *this;
1.635 + }
1.636 +
1.637 + /// \brief Make copy of the given map.
1.638 + ///
1.639 + /// Makes copy of the given map for the newly created graph.
1.640 + /// The new map's key type is the target graph's undirected edge type,
1.641 + /// and the copied map's key type is the source graph's undirected edge
1.642 + /// type.
1.643 + template <typename TargetMap, typename SourceMap>
1.644 + BpUGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
1.645 + uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge,
1.646 + UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
1.647 + return *this;
1.648 + }
1.649 +
1.650 + /// \brief Make a copy of the given undirected edge.
1.651 + ///
1.652 + /// Make a copy of the given undirected edge.
1.653 + BpUGraphCopy& uEdge(TUEdge& tuedge, const UEdge& uedge) {
1.654 + uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge,
1.655 + UEdgeRefMap, TUEdge>(tuedge, uedge));
1.656 + return *this;
1.657 + }
1.658 +
1.659 + /// \brief Executes the copies.
1.660 + ///
1.661 + /// Executes the copies.
1.662 + void run() {
1.663 + ANodeRefMap aNodeRefMap(source);
1.664 + BNodeRefMap bNodeRefMap(source);
1.665 + NodeRefMap nodeRefMap(source, aNodeRefMap, bNodeRefMap);
1.666 + UEdgeRefMap uEdgeRefMap(source);
1.667 + EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
1.668 + _graph_utils_bits::BpUGraphCopySelector<Target>::
1.669 + copy(target, source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
1.670 + for (int i = 0; i < (int)aNodeMapCopies.size(); ++i) {
1.671 + aNodeMapCopies[i]->copy(source, aNodeRefMap);
1.672 + }
1.673 + for (int i = 0; i < (int)bNodeMapCopies.size(); ++i) {
1.674 + bNodeMapCopies[i]->copy(source, bNodeRefMap);
1.675 + }
1.676 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.677 + nodeMapCopies[i]->copy(source, nodeRefMap);
1.678 + }
1.679 + for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
1.680 + uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
1.681 + }
1.682 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.683 + edgeMapCopies[i]->copy(source, edgeRefMap);
1.684 + }
1.685 + }
1.686 +
1.687 + private:
1.688 +
1.689 + const Source& source;
1.690 + Target& target;
1.691 +
1.692 + std::vector<_graph_utils_bits::MapCopyBase<Source, ANode, ANodeRefMap>* >
1.693 + aNodeMapCopies;
1.694 +
1.695 + std::vector<_graph_utils_bits::MapCopyBase<Source, BNode, BNodeRefMap>* >
1.696 + bNodeMapCopies;
1.697 +
1.698 + std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
1.699 + nodeMapCopies;
1.700 +
1.701 + std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
1.702 + edgeMapCopies;
1.703 +
1.704 + std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* >
1.705 + uEdgeMapCopies;
1.706 +
1.707 + };
1.708 +
1.709 + /// \brief Copy a bipartite undirected graph to another graph.
1.710 + ///
1.711 + /// Copy a bipartite undirected graph to another graph.
1.712 + /// The usage of the function:
1.713 + ///
1.714 + ///\code
1.715 + /// copyBpUGraph(trg, src).aNodeRef(anr).edgeCrossRef(ecr).run();
1.716 + ///\endcode
1.717 + ///
1.718 + /// After the copy the \c nr map will contain the mapping from the
1.719 + /// source graph's nodes to the target graph's nodes and the \c ecr will
1.720 + /// contain the mapping from the target graph's edges to the source's
1.721 + /// edges.
1.722 + ///
1.723 + /// \see BpUGraphCopy
1.724 + template <typename Target, typename Source>
1.725 + BpUGraphCopy<Target, Source>
1.726 + copyBpUGraph(Target& target, const Source& source) {
1.727 + return BpUGraphCopy<Target, Source>(target, source);
1.728 + }
1.729 +
1.730
1.731 /// @}
1.732