1.1 --- a/lemon/core.h Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/lemon/core.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -19,6 +19,29 @@
1.13 #ifndef LEMON_CORE_H
1.14 #define LEMON_CORE_H
1.15
1.16 +///\file
1.17 +///\brief LEMON core utilities.
1.18 +///
1.19 +///This header file contains core utilities for LEMON.
1.20 +///It is automatically included by all graph types, therefore it usually
1.21 +///do not have to be included directly.
1.22 +
1.23 +// Disable the following warnings when compiling with MSVC:
1.24 +// C4250: 'class1' : inherits 'class2::member' via dominance
1.25 +// C4267: conversion from 'size_t' to 'type', possible loss of data
1.26 +// C4355: 'this' : used in base member initializer list
1.27 +// C4503: 'function' : decorated name length exceeded, name was truncated
1.28 +// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
1.29 +// C4996: 'function': was declared deprecated
1.30 +#ifdef _MSC_VER
1.31 +#pragma warning( disable : 4250 4267 4355 4503 4800 4996 )
1.32 +#endif
1.33 +
1.34 +#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
1.35 +// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
1.36 +#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
1.37 +#endif
1.38 +
1.39 #include <vector>
1.40 #include <algorithm>
1.41
1.42 @@ -27,22 +50,7 @@
1.43 #include <lemon/bits/traits.h>
1.44 #include <lemon/assert.h>
1.45
1.46 -// Disable the following warnings when compiling with MSVC:
1.47 -// C4250: 'class1' : inherits 'class2::member' via dominance
1.48 -// C4355: 'this' : used in base member initializer list
1.49 -// C4503: 'function' : decorated name length exceeded, name was truncated
1.50 -// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
1.51 -// C4996: 'function': was declared deprecated
1.52 -#ifdef _MSC_VER
1.53 -#pragma warning( disable : 4250 4355 4503 4800 4996 )
1.54 -#endif
1.55
1.56 -///\file
1.57 -///\brief LEMON core utilities.
1.58 -///
1.59 -///This header file contains core utilities for LEMON.
1.60 -///It is automatically included by all graph types, therefore it usually
1.61 -///do not have to be included directly.
1.62
1.63 namespace lemon {
1.64
1.65 @@ -148,6 +156,49 @@
1.66 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
1.67 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
1.68
1.69 + ///Create convenience typedefs for the bipartite graph types and iterators
1.70 +
1.71 + ///This \c \#define creates the same convenient type definitions as
1.72 + ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
1.73 + ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
1.74 + ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
1.75 + ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
1.76 + ///
1.77 + ///\note If the graph type is a dependent type, ie. the graph type depend
1.78 + ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
1.79 + ///macro.
1.80 +#define BPGRAPH_TYPEDEFS(BpGraph) \
1.81 + GRAPH_TYPEDEFS(BpGraph); \
1.82 + typedef BpGraph::RedNode RedNode; \
1.83 + typedef BpGraph::RedNodeIt RedNodeIt; \
1.84 + typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap; \
1.85 + typedef BpGraph::RedNodeMap<int> IntRedNodeMap; \
1.86 + typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap; \
1.87 + typedef BpGraph::BlueNode BlueNode; \
1.88 + typedef BpGraph::BlueNodeIt BlueNodeIt; \
1.89 + typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap; \
1.90 + typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap; \
1.91 + typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
1.92 +
1.93 + ///Create convenience typedefs for the bipartite graph types and iterators
1.94 +
1.95 + ///\see BPGRAPH_TYPEDEFS
1.96 + ///
1.97 + ///\note Use this macro, if the graph type is a dependent type,
1.98 + ///ie. the graph type depend on a template parameter.
1.99 +#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \
1.100 + TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \
1.101 + typedef typename BpGraph::RedNode RedNode; \
1.102 + typedef typename BpGraph::RedNodeIt RedNodeIt; \
1.103 + typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap; \
1.104 + typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap; \
1.105 + typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap; \
1.106 + typedef typename BpGraph::BlueNode BlueNode; \
1.107 + typedef typename BpGraph::BlueNodeIt BlueNodeIt; \
1.108 + typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap; \
1.109 + typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap; \
1.110 + typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
1.111 +
1.112 /// \brief Function to count the items in a graph.
1.113 ///
1.114 /// This function counts the items (nodes, arcs etc.) in a graph.
1.115 @@ -199,6 +250,74 @@
1.116 return _core_bits::CountNodesSelector<Graph>::count(g);
1.117 }
1.118
1.119 + namespace _graph_utils_bits {
1.120 +
1.121 + template <typename Graph, typename Enable = void>
1.122 + struct CountRedNodesSelector {
1.123 + static int count(const Graph &g) {
1.124 + return countItems<Graph, typename Graph::RedNode>(g);
1.125 + }
1.126 + };
1.127 +
1.128 + template <typename Graph>
1.129 + struct CountRedNodesSelector<
1.130 + Graph, typename
1.131 + enable_if<typename Graph::NodeNumTag, void>::type>
1.132 + {
1.133 + static int count(const Graph &g) {
1.134 + return g.redNum();
1.135 + }
1.136 + };
1.137 + }
1.138 +
1.139 + /// \brief Function to count the red nodes in the graph.
1.140 + ///
1.141 + /// This function counts the red nodes in the graph.
1.142 + /// The complexity of the function is O(n) but for some
1.143 + /// graph structures it is specialized to run in O(1).
1.144 + ///
1.145 + /// If the graph contains a \e redNum() member function and a
1.146 + /// \e NodeNumTag tag then this function calls directly the member
1.147 + /// function to query the cardinality of the node set.
1.148 + template <typename Graph>
1.149 + inline int countRedNodes(const Graph& g) {
1.150 + return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
1.151 + }
1.152 +
1.153 + namespace _graph_utils_bits {
1.154 +
1.155 + template <typename Graph, typename Enable = void>
1.156 + struct CountBlueNodesSelector {
1.157 + static int count(const Graph &g) {
1.158 + return countItems<Graph, typename Graph::BlueNode>(g);
1.159 + }
1.160 + };
1.161 +
1.162 + template <typename Graph>
1.163 + struct CountBlueNodesSelector<
1.164 + Graph, typename
1.165 + enable_if<typename Graph::NodeNumTag, void>::type>
1.166 + {
1.167 + static int count(const Graph &g) {
1.168 + return g.blueNum();
1.169 + }
1.170 + };
1.171 + }
1.172 +
1.173 + /// \brief Function to count the blue nodes in the graph.
1.174 + ///
1.175 + /// This function counts the blue nodes in the graph.
1.176 + /// The complexity of the function is O(n) but for some
1.177 + /// graph structures it is specialized to run in O(1).
1.178 + ///
1.179 + /// If the graph contains a \e blueNum() member function and a
1.180 + /// \e NodeNumTag tag then this function calls directly the member
1.181 + /// function to query the cardinality of the node set.
1.182 + template <typename Graph>
1.183 + inline int countBlueNodes(const Graph& g) {
1.184 + return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
1.185 + }
1.186 +
1.187 // Arc counting:
1.188
1.189 namespace _core_bits {
1.190 @@ -440,13 +559,70 @@
1.191 {
1.192 template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.193 static void copy(const From& from, Graph &to,
1.194 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.195 + NodeRefMap& nodeRefMap,
1.196 + EdgeRefMap& edgeRefMap) {
1.197 to.build(from, nodeRefMap, edgeRefMap);
1.198 }
1.199 };
1.200
1.201 + template <typename BpGraph, typename Enable = void>
1.202 + struct BpGraphCopySelector {
1.203 + template <typename From, typename RedNodeRefMap,
1.204 + typename BlueNodeRefMap, typename EdgeRefMap>
1.205 + static void copy(const From& from, BpGraph &to,
1.206 + RedNodeRefMap& redNodeRefMap,
1.207 + BlueNodeRefMap& blueNodeRefMap,
1.208 + EdgeRefMap& edgeRefMap) {
1.209 + to.clear();
1.210 + for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
1.211 + redNodeRefMap[it] = to.addRedNode();
1.212 + }
1.213 + for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
1.214 + blueNodeRefMap[it] = to.addBlueNode();
1.215 + }
1.216 + for (typename From::EdgeIt it(from); it != INVALID; ++it) {
1.217 + edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
1.218 + blueNodeRefMap[from.blueNode(it)]);
1.219 + }
1.220 + }
1.221 + };
1.222 +
1.223 + template <typename BpGraph>
1.224 + struct BpGraphCopySelector<
1.225 + BpGraph,
1.226 + typename enable_if<typename BpGraph::BuildTag, void>::type>
1.227 + {
1.228 + template <typename From, typename RedNodeRefMap,
1.229 + typename BlueNodeRefMap, typename EdgeRefMap>
1.230 + static void copy(const From& from, BpGraph &to,
1.231 + RedNodeRefMap& redNodeRefMap,
1.232 + BlueNodeRefMap& blueNodeRefMap,
1.233 + EdgeRefMap& edgeRefMap) {
1.234 + to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
1.235 + }
1.236 + };
1.237 +
1.238 }
1.239
1.240 + /// \brief Check whether a graph is undirected.
1.241 + ///
1.242 + /// This function returns \c true if the given graph is undirected.
1.243 +#ifdef DOXYGEN
1.244 + template <typename GR>
1.245 + bool undirected(const GR& g) { return false; }
1.246 +#else
1.247 + template <typename GR>
1.248 + typename enable_if<UndirectedTagIndicator<GR>, bool>::type
1.249 + undirected(const GR&) {
1.250 + return true;
1.251 + }
1.252 + template <typename GR>
1.253 + typename disable_if<UndirectedTagIndicator<GR>, bool>::type
1.254 + undirected(const GR&) {
1.255 + return false;
1.256 + }
1.257 +#endif
1.258 +
1.259 /// \brief Class to copy a digraph.
1.260 ///
1.261 /// Class to copy a digraph to another digraph (duplicate a digraph). The
1.262 @@ -972,6 +1148,454 @@
1.263 return GraphCopy<From, To>(from, to);
1.264 }
1.265
1.266 + /// \brief Class to copy a bipartite graph.
1.267 + ///
1.268 + /// Class to copy a bipartite graph to another graph (duplicate a
1.269 + /// graph). The simplest way of using it is through the
1.270 + /// \c bpGraphCopy() function.
1.271 + ///
1.272 + /// This class not only make a copy of a bipartite graph, but it can
1.273 + /// create references and cross references between the nodes, edges
1.274 + /// and arcs of the two graphs, and it can copy maps for using with
1.275 + /// the newly created graph.
1.276 + ///
1.277 + /// To make a copy from a graph, first an instance of BpGraphCopy
1.278 + /// should be created, then the data belongs to the graph should
1.279 + /// assigned to copy. In the end, the \c run() member should be
1.280 + /// called.
1.281 + ///
1.282 + /// The next code copies a graph with several data:
1.283 + ///\code
1.284 + /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
1.285 + /// // Create references for the nodes
1.286 + /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
1.287 + /// cg.nodeRef(nr);
1.288 + /// // Create cross references (inverse) for the edges
1.289 + /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
1.290 + /// cg.edgeCrossRef(ecr);
1.291 + /// // Copy a red node map
1.292 + /// OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
1.293 + /// NewBpGraph::RedNodeMap<double> nrmap(new_graph);
1.294 + /// cg.redNodeMap(ormap, nrmap);
1.295 + /// // Copy a node
1.296 + /// OrigBpGraph::Node on;
1.297 + /// NewBpGraph::Node nn;
1.298 + /// cg.node(on, nn);
1.299 + /// // Execute copying
1.300 + /// cg.run();
1.301 + ///\endcode
1.302 + template <typename From, typename To>
1.303 + class BpGraphCopy {
1.304 + private:
1.305 +
1.306 + typedef typename From::Node Node;
1.307 + typedef typename From::RedNode RedNode;
1.308 + typedef typename From::BlueNode BlueNode;
1.309 + typedef typename From::NodeIt NodeIt;
1.310 + typedef typename From::Arc Arc;
1.311 + typedef typename From::ArcIt ArcIt;
1.312 + typedef typename From::Edge Edge;
1.313 + typedef typename From::EdgeIt EdgeIt;
1.314 +
1.315 + typedef typename To::Node TNode;
1.316 + typedef typename To::RedNode TRedNode;
1.317 + typedef typename To::BlueNode TBlueNode;
1.318 + typedef typename To::Arc TArc;
1.319 + typedef typename To::Edge TEdge;
1.320 +
1.321 + typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
1.322 + typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
1.323 + typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.324 +
1.325 + struct NodeRefMap {
1.326 + NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
1.327 + const BlueNodeRefMap& blue_node_ref)
1.328 + : _from(from), _red_node_ref(red_node_ref),
1.329 + _blue_node_ref(blue_node_ref) {}
1.330 +
1.331 + typedef typename From::Node Key;
1.332 + typedef typename To::Node Value;
1.333 +
1.334 + Value operator[](const Key& key) const {
1.335 + if (_from.red(key)) {
1.336 + return _red_node_ref[_from.asRedNodeUnsafe(key)];
1.337 + } else {
1.338 + return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
1.339 + }
1.340 + }
1.341 +
1.342 + const From& _from;
1.343 + const RedNodeRefMap& _red_node_ref;
1.344 + const BlueNodeRefMap& _blue_node_ref;
1.345 + };
1.346 +
1.347 + struct ArcRefMap {
1.348 + ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
1.349 + : _from(from), _to(to), _edge_ref(edge_ref) {}
1.350 +
1.351 + typedef typename From::Arc Key;
1.352 + typedef typename To::Arc Value;
1.353 +
1.354 + Value operator[](const Key& key) const {
1.355 + return _to.direct(_edge_ref[key], _from.direction(key));
1.356 + }
1.357 +
1.358 + const From& _from;
1.359 + const To& _to;
1.360 + const EdgeRefMap& _edge_ref;
1.361 + };
1.362 +
1.363 + public:
1.364 +
1.365 + /// \brief Constructor of BpGraphCopy.
1.366 + ///
1.367 + /// Constructor of BpGraphCopy for copying the content of the
1.368 + /// \c from graph into the \c to graph.
1.369 + BpGraphCopy(const From& from, To& to)
1.370 + : _from(from), _to(to) {}
1.371 +
1.372 + /// \brief Destructor of BpGraphCopy
1.373 + ///
1.374 + /// Destructor of BpGraphCopy.
1.375 + ~BpGraphCopy() {
1.376 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.377 + delete _node_maps[i];
1.378 + }
1.379 + for (int i = 0; i < int(_red_maps.size()); ++i) {
1.380 + delete _red_maps[i];
1.381 + }
1.382 + for (int i = 0; i < int(_blue_maps.size()); ++i) {
1.383 + delete _blue_maps[i];
1.384 + }
1.385 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.386 + delete _arc_maps[i];
1.387 + }
1.388 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.389 + delete _edge_maps[i];
1.390 + }
1.391 + }
1.392 +
1.393 + /// \brief Copy the node references into the given map.
1.394 + ///
1.395 + /// This function copies the node references into the given map.
1.396 + /// The parameter should be a map, whose key type is the Node type of
1.397 + /// the source graph, while the value type is the Node type of the
1.398 + /// destination graph.
1.399 + template <typename NodeRef>
1.400 + BpGraphCopy& nodeRef(NodeRef& map) {
1.401 + _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1.402 + NodeRefMap, NodeRef>(map));
1.403 + return *this;
1.404 + }
1.405 +
1.406 + /// \brief Copy the node cross references into the given map.
1.407 + ///
1.408 + /// This function copies the node cross references (reverse references)
1.409 + /// into the given map. The parameter should be a map, whose key type
1.410 + /// is the Node type of the destination graph, while the value type is
1.411 + /// the Node type of the source graph.
1.412 + template <typename NodeCrossRef>
1.413 + BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.414 + _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1.415 + NodeRefMap, NodeCrossRef>(map));
1.416 + return *this;
1.417 + }
1.418 +
1.419 + /// \brief Make a copy of the given node map.
1.420 + ///
1.421 + /// This function makes a copy of the given node map for the newly
1.422 + /// created graph.
1.423 + /// The key type of the new map \c tmap should be the Node type of the
1.424 + /// destination graph, and the key type of the original map \c map
1.425 + /// should be the Node type of the source graph.
1.426 + template <typename FromMap, typename ToMap>
1.427 + BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
1.428 + _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1.429 + NodeRefMap, FromMap, ToMap>(map, tmap));
1.430 + return *this;
1.431 + }
1.432 +
1.433 + /// \brief Make a copy of the given node.
1.434 + ///
1.435 + /// This function makes a copy of the given node.
1.436 + BpGraphCopy& node(const Node& node, TNode& tnode) {
1.437 + _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1.438 + NodeRefMap, TNode>(node, tnode));
1.439 + return *this;
1.440 + }
1.441 +
1.442 + /// \brief Copy the red node references into the given map.
1.443 + ///
1.444 + /// This function copies the red node references into the given
1.445 + /// map. The parameter should be a map, whose key type is the
1.446 + /// Node type of the source graph with the red item set, while the
1.447 + /// value type is the Node type of the destination graph.
1.448 + template <typename RedRef>
1.449 + BpGraphCopy& redRef(RedRef& map) {
1.450 + _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
1.451 + RedNodeRefMap, RedRef>(map));
1.452 + return *this;
1.453 + }
1.454 +
1.455 + /// \brief Copy the red node cross references into the given map.
1.456 + ///
1.457 + /// This function copies the red node cross references (reverse
1.458 + /// references) into the given map. The parameter should be a map,
1.459 + /// whose key type is the Node type of the destination graph with
1.460 + /// the red item set, while the value type is the Node type of the
1.461 + /// source graph.
1.462 + template <typename RedCrossRef>
1.463 + BpGraphCopy& redCrossRef(RedCrossRef& map) {
1.464 + _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
1.465 + RedNodeRefMap, RedCrossRef>(map));
1.466 + return *this;
1.467 + }
1.468 +
1.469 + /// \brief Make a copy of the given red node map.
1.470 + ///
1.471 + /// This function makes a copy of the given red node map for the newly
1.472 + /// created graph.
1.473 + /// The key type of the new map \c tmap should be the Node type of
1.474 + /// the destination graph with the red items, and the key type of
1.475 + /// the original map \c map should be the Node type of the source
1.476 + /// graph.
1.477 + template <typename FromMap, typename ToMap>
1.478 + BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
1.479 + _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
1.480 + RedNodeRefMap, FromMap, ToMap>(map, tmap));
1.481 + return *this;
1.482 + }
1.483 +
1.484 + /// \brief Make a copy of the given red node.
1.485 + ///
1.486 + /// This function makes a copy of the given red node.
1.487 + BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
1.488 + _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
1.489 + RedNodeRefMap, TRedNode>(node, tnode));
1.490 + return *this;
1.491 + }
1.492 +
1.493 + /// \brief Copy the blue node references into the given map.
1.494 + ///
1.495 + /// This function copies the blue node references into the given
1.496 + /// map. The parameter should be a map, whose key type is the
1.497 + /// Node type of the source graph with the blue item set, while the
1.498 + /// value type is the Node type of the destination graph.
1.499 + template <typename BlueRef>
1.500 + BpGraphCopy& blueRef(BlueRef& map) {
1.501 + _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
1.502 + BlueNodeRefMap, BlueRef>(map));
1.503 + return *this;
1.504 + }
1.505 +
1.506 + /// \brief Copy the blue node cross references into the given map.
1.507 + ///
1.508 + /// This function copies the blue node cross references (reverse
1.509 + /// references) into the given map. The parameter should be a map,
1.510 + /// whose key type is the Node type of the destination graph with
1.511 + /// the blue item set, while the value type is the Node type of the
1.512 + /// source graph.
1.513 + template <typename BlueCrossRef>
1.514 + BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1.515 + _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
1.516 + BlueNodeRefMap, BlueCrossRef>(map));
1.517 + return *this;
1.518 + }
1.519 +
1.520 + /// \brief Make a copy of the given blue node map.
1.521 + ///
1.522 + /// This function makes a copy of the given blue node map for the newly
1.523 + /// created graph.
1.524 + /// The key type of the new map \c tmap should be the Node type of
1.525 + /// the destination graph with the blue items, and the key type of
1.526 + /// the original map \c map should be the Node type of the source
1.527 + /// graph.
1.528 + template <typename FromMap, typename ToMap>
1.529 + BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
1.530 + _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
1.531 + BlueNodeRefMap, FromMap, ToMap>(map, tmap));
1.532 + return *this;
1.533 + }
1.534 +
1.535 + /// \brief Make a copy of the given blue node.
1.536 + ///
1.537 + /// This function makes a copy of the given blue node.
1.538 + BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
1.539 + _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
1.540 + BlueNodeRefMap, TBlueNode>(node, tnode));
1.541 + return *this;
1.542 + }
1.543 +
1.544 + /// \brief Copy the arc references into the given map.
1.545 + ///
1.546 + /// This function copies the arc references into the given map.
1.547 + /// The parameter should be a map, whose key type is the Arc type of
1.548 + /// the source graph, while the value type is the Arc type of the
1.549 + /// destination graph.
1.550 + template <typename ArcRef>
1.551 + BpGraphCopy& arcRef(ArcRef& map) {
1.552 + _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1.553 + ArcRefMap, ArcRef>(map));
1.554 + return *this;
1.555 + }
1.556 +
1.557 + /// \brief Copy the arc cross references into the given map.
1.558 + ///
1.559 + /// This function copies the arc cross references (reverse references)
1.560 + /// into the given map. The parameter should be a map, whose key type
1.561 + /// is the Arc type of the destination graph, while the value type is
1.562 + /// the Arc type of the source graph.
1.563 + template <typename ArcCrossRef>
1.564 + BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
1.565 + _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1.566 + ArcRefMap, ArcCrossRef>(map));
1.567 + return *this;
1.568 + }
1.569 +
1.570 + /// \brief Make a copy of the given arc map.
1.571 + ///
1.572 + /// This function makes a copy of the given arc map for the newly
1.573 + /// created graph.
1.574 + /// The key type of the new map \c tmap should be the Arc type of the
1.575 + /// destination graph, and the key type of the original map \c map
1.576 + /// should be the Arc type of the source graph.
1.577 + template <typename FromMap, typename ToMap>
1.578 + BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1.579 + _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1.580 + ArcRefMap, FromMap, ToMap>(map, tmap));
1.581 + return *this;
1.582 + }
1.583 +
1.584 + /// \brief Make a copy of the given arc.
1.585 + ///
1.586 + /// This function makes a copy of the given arc.
1.587 + BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
1.588 + _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1.589 + ArcRefMap, TArc>(arc, tarc));
1.590 + return *this;
1.591 + }
1.592 +
1.593 + /// \brief Copy the edge references into the given map.
1.594 + ///
1.595 + /// This function copies the edge references into the given map.
1.596 + /// The parameter should be a map, whose key type is the Edge type of
1.597 + /// the source graph, while the value type is the Edge type of the
1.598 + /// destination graph.
1.599 + template <typename EdgeRef>
1.600 + BpGraphCopy& edgeRef(EdgeRef& map) {
1.601 + _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1.602 + EdgeRefMap, EdgeRef>(map));
1.603 + return *this;
1.604 + }
1.605 +
1.606 + /// \brief Copy the edge cross references into the given map.
1.607 + ///
1.608 + /// This function copies the edge cross references (reverse references)
1.609 + /// into the given map. The parameter should be a map, whose key type
1.610 + /// is the Edge type of the destination graph, while the value type is
1.611 + /// the Edge type of the source graph.
1.612 + template <typename EdgeCrossRef>
1.613 + BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.614 + _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1.615 + Edge, EdgeRefMap, EdgeCrossRef>(map));
1.616 + return *this;
1.617 + }
1.618 +
1.619 + /// \brief Make a copy of the given edge map.
1.620 + ///
1.621 + /// This function makes a copy of the given edge map for the newly
1.622 + /// created graph.
1.623 + /// The key type of the new map \c tmap should be the Edge type of the
1.624 + /// destination graph, and the key type of the original map \c map
1.625 + /// should be the Edge type of the source graph.
1.626 + template <typename FromMap, typename ToMap>
1.627 + BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1.628 + _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1.629 + EdgeRefMap, FromMap, ToMap>(map, tmap));
1.630 + return *this;
1.631 + }
1.632 +
1.633 + /// \brief Make a copy of the given edge.
1.634 + ///
1.635 + /// This function makes a copy of the given edge.
1.636 + BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
1.637 + _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1.638 + EdgeRefMap, TEdge>(edge, tedge));
1.639 + return *this;
1.640 + }
1.641 +
1.642 + /// \brief Execute copying.
1.643 + ///
1.644 + /// This function executes the copying of the graph along with the
1.645 + /// copying of the assigned data.
1.646 + void run() {
1.647 + RedNodeRefMap redNodeRefMap(_from);
1.648 + BlueNodeRefMap blueNodeRefMap(_from);
1.649 + NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
1.650 + EdgeRefMap edgeRefMap(_from);
1.651 + ArcRefMap arcRefMap(_from, _to, edgeRefMap);
1.652 + _core_bits::BpGraphCopySelector<To>::
1.653 + copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
1.654 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.655 + _node_maps[i]->copy(_from, nodeRefMap);
1.656 + }
1.657 + for (int i = 0; i < int(_red_maps.size()); ++i) {
1.658 + _red_maps[i]->copy(_from, redNodeRefMap);
1.659 + }
1.660 + for (int i = 0; i < int(_blue_maps.size()); ++i) {
1.661 + _blue_maps[i]->copy(_from, blueNodeRefMap);
1.662 + }
1.663 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.664 + _edge_maps[i]->copy(_from, edgeRefMap);
1.665 + }
1.666 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.667 + _arc_maps[i]->copy(_from, arcRefMap);
1.668 + }
1.669 + }
1.670 +
1.671 + private:
1.672 +
1.673 + const From& _from;
1.674 + To& _to;
1.675 +
1.676 + std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.677 + _node_maps;
1.678 +
1.679 + std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
1.680 + _red_maps;
1.681 +
1.682 + std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
1.683 + _blue_maps;
1.684 +
1.685 + std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.686 + _arc_maps;
1.687 +
1.688 + std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.689 + _edge_maps;
1.690 +
1.691 + };
1.692 +
1.693 + /// \brief Copy a graph to another graph.
1.694 + ///
1.695 + /// This function copies a graph to another graph.
1.696 + /// The complete usage of it is detailed in the BpGraphCopy class,
1.697 + /// but a short example shows a basic work:
1.698 + ///\code
1.699 + /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1.700 + ///\endcode
1.701 + ///
1.702 + /// After the copy the \c nr map will contain the mapping from the
1.703 + /// nodes of the \c from graph to the nodes of the \c to graph and
1.704 + /// \c ecr will contain the mapping from the edges of the \c to graph
1.705 + /// to the edges of the \c from graph.
1.706 + ///
1.707 + /// \see BpGraphCopy
1.708 + template <typename From, typename To>
1.709 + BpGraphCopy<From, To>
1.710 + bpGraphCopy(const From& from, To& to) {
1.711 + return BpGraphCopy<From, To>(from, to);
1.712 + }
1.713 +
1.714 namespace _core_bits {
1.715
1.716 template <typename Graph, typename Enable = void>