1.1 --- a/lemon/core.h Mon Nov 15 09:46:08 2010 +0100
1.2 +++ b/lemon/core.h Tue Nov 16 00:59:36 2010 +0100
1.3 @@ -555,6 +555,37 @@
1.4 }
1.5 };
1.6
1.7 + template <typename BpGraph, typename Enable = void>
1.8 + struct BpGraphCopySelector {
1.9 + template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.10 + static void copy(const From& from, BpGraph &to,
1.11 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.12 + to.clear();
1.13 + for (typename From::RedIt it(from); it != INVALID; ++it) {
1.14 + nodeRefMap[it] = to.addRedNode();
1.15 + }
1.16 + for (typename From::BlueIt it(from); it != INVALID; ++it) {
1.17 + nodeRefMap[it] = to.addBlueNode();
1.18 + }
1.19 + for (typename From::EdgeIt it(from); it != INVALID; ++it) {
1.20 + edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)],
1.21 + nodeRefMap[from.blueNode(it)]);
1.22 + }
1.23 + }
1.24 + };
1.25 +
1.26 + template <typename BpGraph>
1.27 + struct BpGraphCopySelector<
1.28 + BpGraph,
1.29 + typename enable_if<typename BpGraph::BuildTag, void>::type>
1.30 + {
1.31 + template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.32 + static void copy(const From& from, BpGraph &to,
1.33 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.34 + to.build(from, nodeRefMap, edgeRefMap);
1.35 + }
1.36 + };
1.37 +
1.38 }
1.39
1.40 /// \brief Check whether a graph is undirected.
1.41 @@ -1101,6 +1132,409 @@
1.42 return GraphCopy<From, To>(from, to);
1.43 }
1.44
1.45 + /// \brief Class to copy a bipartite graph.
1.46 + ///
1.47 + /// Class to copy a bipartite graph to another graph (duplicate a
1.48 + /// graph). The simplest way of using it is through the
1.49 + /// \c bpGraphCopy() function.
1.50 + ///
1.51 + /// This class not only make a copy of a bipartite graph, but it can
1.52 + /// create references and cross references between the nodes, edges
1.53 + /// and arcs of the two graphs, and it can copy maps for using with
1.54 + /// the newly created graph.
1.55 + ///
1.56 + /// To make a copy from a graph, first an instance of BpGraphCopy
1.57 + /// should be created, then the data belongs to the graph should
1.58 + /// assigned to copy. In the end, the \c run() member should be
1.59 + /// called.
1.60 + ///
1.61 + /// The next code copies a graph with several data:
1.62 + ///\code
1.63 + /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
1.64 + /// // Create references for the nodes
1.65 + /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
1.66 + /// cg.nodeRef(nr);
1.67 + /// // Create cross references (inverse) for the edges
1.68 + /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
1.69 + /// cg.edgeCrossRef(ecr);
1.70 + /// // Copy a red map
1.71 + /// OrigBpGraph::RedMap<double> ormap(orig_graph);
1.72 + /// NewBpGraph::RedMap<double> nrmap(new_graph);
1.73 + /// cg.edgeMap(ormap, nrmap);
1.74 + /// // Copy a node
1.75 + /// OrigBpGraph::Node on;
1.76 + /// NewBpGraph::Node nn;
1.77 + /// cg.node(on, nn);
1.78 + /// // Execute copying
1.79 + /// cg.run();
1.80 + ///\endcode
1.81 + template <typename From, typename To>
1.82 + class BpGraphCopy {
1.83 + private:
1.84 +
1.85 + typedef typename From::Node Node;
1.86 + typedef typename From::RedNode RedNode;
1.87 + typedef typename From::BlueNode BlueNode;
1.88 + typedef typename From::NodeIt NodeIt;
1.89 + typedef typename From::Arc Arc;
1.90 + typedef typename From::ArcIt ArcIt;
1.91 + typedef typename From::Edge Edge;
1.92 + typedef typename From::EdgeIt EdgeIt;
1.93 +
1.94 + typedef typename To::Node TNode;
1.95 + typedef typename To::Arc TArc;
1.96 + typedef typename To::Edge TEdge;
1.97 +
1.98 + typedef typename From::template NodeMap<TNode> NodeRefMap;
1.99 + typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.100 +
1.101 + struct ArcRefMap {
1.102 + ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
1.103 + : _from(from), _to(to), _edge_ref(edge_ref) {}
1.104 +
1.105 + typedef typename From::Arc Key;
1.106 + typedef typename To::Arc Value;
1.107 +
1.108 + Value operator[](const Key& key) const {
1.109 + return _to.direct(_edge_ref[key], _from.direction(key));
1.110 + }
1.111 +
1.112 + const From& _from;
1.113 + const To& _to;
1.114 + const EdgeRefMap& _edge_ref;
1.115 + };
1.116 +
1.117 + public:
1.118 +
1.119 + /// \brief Constructor of BpGraphCopy.
1.120 + ///
1.121 + /// Constructor of BpGraphCopy for copying the content of the
1.122 + /// \c from graph into the \c to graph.
1.123 + BpGraphCopy(const From& from, To& to)
1.124 + : _from(from), _to(to) {}
1.125 +
1.126 + /// \brief Destructor of BpGraphCopy
1.127 + ///
1.128 + /// Destructor of BpGraphCopy.
1.129 + ~BpGraphCopy() {
1.130 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.131 + delete _node_maps[i];
1.132 + }
1.133 + for (int i = 0; i < int(_red_maps.size()); ++i) {
1.134 + delete _red_maps[i];
1.135 + }
1.136 + for (int i = 0; i < int(_blue_maps.size()); ++i) {
1.137 + delete _blue_maps[i];
1.138 + }
1.139 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.140 + delete _arc_maps[i];
1.141 + }
1.142 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.143 + delete _edge_maps[i];
1.144 + }
1.145 + }
1.146 +
1.147 + /// \brief Copy the node references into the given map.
1.148 + ///
1.149 + /// This function copies the node references into the given map.
1.150 + /// The parameter should be a map, whose key type is the Node type of
1.151 + /// the source graph, while the value type is the Node type of the
1.152 + /// destination graph.
1.153 + template <typename NodeRef>
1.154 + BpGraphCopy& nodeRef(NodeRef& map) {
1.155 + _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1.156 + NodeRefMap, NodeRef>(map));
1.157 + return *this;
1.158 + }
1.159 +
1.160 + /// \brief Copy the node cross references into the given map.
1.161 + ///
1.162 + /// This function copies the node cross references (reverse references)
1.163 + /// into the given map. The parameter should be a map, whose key type
1.164 + /// is the Node type of the destination graph, while the value type is
1.165 + /// the Node type of the source graph.
1.166 + template <typename NodeCrossRef>
1.167 + BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.168 + _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1.169 + NodeRefMap, NodeCrossRef>(map));
1.170 + return *this;
1.171 + }
1.172 +
1.173 + /// \brief Make a copy of the given node map.
1.174 + ///
1.175 + /// This function makes a copy of the given node map for the newly
1.176 + /// created graph.
1.177 + /// The key type of the new map \c tmap should be the Node type of the
1.178 + /// destination graph, and the key type of the original map \c map
1.179 + /// should be the Node type of the source graph.
1.180 + template <typename FromMap, typename ToMap>
1.181 + BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
1.182 + _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1.183 + NodeRefMap, FromMap, ToMap>(map, tmap));
1.184 + return *this;
1.185 + }
1.186 +
1.187 + /// \brief Make a copy of the given node.
1.188 + ///
1.189 + /// This function makes a copy of the given node.
1.190 + BpGraphCopy& node(const Node& node, TNode& tnode) {
1.191 + _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1.192 + NodeRefMap, TNode>(node, tnode));
1.193 + return *this;
1.194 + }
1.195 +
1.196 + /// \brief Copy the red node references into the given map.
1.197 + ///
1.198 + /// This function copies the red node references into the given
1.199 + /// map. The parameter should be a map, whose key type is the
1.200 + /// Node type of the source graph with the red item set, while the
1.201 + /// value type is the Node type of the destination graph.
1.202 + template <typename RedRef>
1.203 + BpGraphCopy& redRef(RedRef& map) {
1.204 + _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
1.205 + NodeRefMap, RedRef>(map));
1.206 + return *this;
1.207 + }
1.208 +
1.209 + /// \brief Copy the red node cross references into the given map.
1.210 + ///
1.211 + /// This function copies the red node cross references (reverse
1.212 + /// references) into the given map. The parameter should be a map,
1.213 + /// whose key type is the Node type of the destination graph with
1.214 + /// the red item set, while the value type is the Node type of the
1.215 + /// source graph.
1.216 + template <typename RedCrossRef>
1.217 + BpGraphCopy& redCrossRef(RedCrossRef& map) {
1.218 + _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
1.219 + NodeRefMap, RedCrossRef>(map));
1.220 + return *this;
1.221 + }
1.222 +
1.223 + /// \brief Make a copy of the given red node map.
1.224 + ///
1.225 + /// This function makes a copy of the given red node map for the newly
1.226 + /// created graph.
1.227 + /// The key type of the new map \c tmap should be the Node type of
1.228 + /// the destination graph with the red items, and the key type of
1.229 + /// the original map \c map should be the Node type of the source
1.230 + /// graph.
1.231 + template <typename FromMap, typename ToMap>
1.232 + BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) {
1.233 + _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
1.234 + NodeRefMap, FromMap, ToMap>(map, tmap));
1.235 + return *this;
1.236 + }
1.237 +
1.238 + /// \brief Copy the blue node references into the given map.
1.239 + ///
1.240 + /// This function copies the blue node references into the given
1.241 + /// map. The parameter should be a map, whose key type is the
1.242 + /// Node type of the source graph with the blue item set, while the
1.243 + /// value type is the Node type of the destination graph.
1.244 + template <typename BlueRef>
1.245 + BpGraphCopy& blueRef(BlueRef& map) {
1.246 + _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
1.247 + NodeRefMap, BlueRef>(map));
1.248 + return *this;
1.249 + }
1.250 +
1.251 + /// \brief Copy the blue node cross references into the given map.
1.252 + ///
1.253 + /// This function copies the blue node cross references (reverse
1.254 + /// references) into the given map. The parameter should be a map,
1.255 + /// whose key type is the Node type of the destination graph with
1.256 + /// the blue item set, while the value type is the Node type of the
1.257 + /// source graph.
1.258 + template <typename BlueCrossRef>
1.259 + BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1.260 + _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
1.261 + NodeRefMap, BlueCrossRef>(map));
1.262 + return *this;
1.263 + }
1.264 +
1.265 + /// \brief Make a copy of the given blue node map.
1.266 + ///
1.267 + /// This function makes a copy of the given blue node map for the newly
1.268 + /// created graph.
1.269 + /// The key type of the new map \c tmap should be the Node type of
1.270 + /// the destination graph with the blue items, and the key type of
1.271 + /// the original map \c map should be the Node type of the source
1.272 + /// graph.
1.273 + template <typename FromMap, typename ToMap>
1.274 + BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) {
1.275 + _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
1.276 + NodeRefMap, FromMap, ToMap>(map, tmap));
1.277 + return *this;
1.278 + }
1.279 +
1.280 + /// \brief Copy the arc references into the given map.
1.281 + ///
1.282 + /// This function copies the arc references into the given map.
1.283 + /// The parameter should be a map, whose key type is the Arc type of
1.284 + /// the source graph, while the value type is the Arc type of the
1.285 + /// destination graph.
1.286 + template <typename ArcRef>
1.287 + BpGraphCopy& arcRef(ArcRef& map) {
1.288 + _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1.289 + ArcRefMap, ArcRef>(map));
1.290 + return *this;
1.291 + }
1.292 +
1.293 + /// \brief Copy the arc cross references into the given map.
1.294 + ///
1.295 + /// This function copies the arc cross references (reverse references)
1.296 + /// into the given map. The parameter should be a map, whose key type
1.297 + /// is the Arc type of the destination graph, while the value type is
1.298 + /// the Arc type of the source graph.
1.299 + template <typename ArcCrossRef>
1.300 + BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
1.301 + _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1.302 + ArcRefMap, ArcCrossRef>(map));
1.303 + return *this;
1.304 + }
1.305 +
1.306 + /// \brief Make a copy of the given arc map.
1.307 + ///
1.308 + /// This function makes a copy of the given arc map for the newly
1.309 + /// created graph.
1.310 + /// The key type of the new map \c tmap should be the Arc type of the
1.311 + /// destination graph, and the key type of the original map \c map
1.312 + /// should be the Arc type of the source graph.
1.313 + template <typename FromMap, typename ToMap>
1.314 + BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1.315 + _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1.316 + ArcRefMap, FromMap, ToMap>(map, tmap));
1.317 + return *this;
1.318 + }
1.319 +
1.320 + /// \brief Make a copy of the given arc.
1.321 + ///
1.322 + /// This function makes a copy of the given arc.
1.323 + BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
1.324 + _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1.325 + ArcRefMap, TArc>(arc, tarc));
1.326 + return *this;
1.327 + }
1.328 +
1.329 + /// \brief Copy the edge references into the given map.
1.330 + ///
1.331 + /// This function copies the edge references into the given map.
1.332 + /// The parameter should be a map, whose key type is the Edge type of
1.333 + /// the source graph, while the value type is the Edge type of the
1.334 + /// destination graph.
1.335 + template <typename EdgeRef>
1.336 + BpGraphCopy& edgeRef(EdgeRef& map) {
1.337 + _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1.338 + EdgeRefMap, EdgeRef>(map));
1.339 + return *this;
1.340 + }
1.341 +
1.342 + /// \brief Copy the edge cross references into the given map.
1.343 + ///
1.344 + /// This function copies the edge cross references (reverse references)
1.345 + /// into the given map. The parameter should be a map, whose key type
1.346 + /// is the Edge type of the destination graph, while the value type is
1.347 + /// the Edge type of the source graph.
1.348 + template <typename EdgeCrossRef>
1.349 + BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.350 + _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1.351 + Edge, EdgeRefMap, EdgeCrossRef>(map));
1.352 + return *this;
1.353 + }
1.354 +
1.355 + /// \brief Make a copy of the given edge map.
1.356 + ///
1.357 + /// This function makes a copy of the given edge map for the newly
1.358 + /// created graph.
1.359 + /// The key type of the new map \c tmap should be the Edge type of the
1.360 + /// destination graph, and the key type of the original map \c map
1.361 + /// should be the Edge type of the source graph.
1.362 + template <typename FromMap, typename ToMap>
1.363 + BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1.364 + _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1.365 + EdgeRefMap, FromMap, ToMap>(map, tmap));
1.366 + return *this;
1.367 + }
1.368 +
1.369 + /// \brief Make a copy of the given edge.
1.370 + ///
1.371 + /// This function makes a copy of the given edge.
1.372 + BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
1.373 + _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1.374 + EdgeRefMap, TEdge>(edge, tedge));
1.375 + return *this;
1.376 + }
1.377 +
1.378 + /// \brief Execute copying.
1.379 + ///
1.380 + /// This function executes the copying of the graph along with the
1.381 + /// copying of the assigned data.
1.382 + void run() {
1.383 + NodeRefMap nodeRefMap(_from);
1.384 + EdgeRefMap edgeRefMap(_from);
1.385 + ArcRefMap arcRefMap(_from, _to, edgeRefMap);
1.386 + _core_bits::BpGraphCopySelector<To>::
1.387 + copy(_from, _to, nodeRefMap, edgeRefMap);
1.388 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.389 + _node_maps[i]->copy(_from, nodeRefMap);
1.390 + }
1.391 + for (int i = 0; i < int(_red_maps.size()); ++i) {
1.392 + _red_maps[i]->copy(_from, nodeRefMap);
1.393 + }
1.394 + for (int i = 0; i < int(_blue_maps.size()); ++i) {
1.395 + _blue_maps[i]->copy(_from, nodeRefMap);
1.396 + }
1.397 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.398 + _edge_maps[i]->copy(_from, edgeRefMap);
1.399 + }
1.400 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.401 + _arc_maps[i]->copy(_from, arcRefMap);
1.402 + }
1.403 + }
1.404 +
1.405 + private:
1.406 +
1.407 + const From& _from;
1.408 + To& _to;
1.409 +
1.410 + std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.411 + _node_maps;
1.412 +
1.413 + std::vector<_core_bits::MapCopyBase<From, RedNode, NodeRefMap>* >
1.414 + _red_maps;
1.415 +
1.416 + std::vector<_core_bits::MapCopyBase<From, BlueNode, NodeRefMap>* >
1.417 + _blue_maps;
1.418 +
1.419 + std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.420 + _arc_maps;
1.421 +
1.422 + std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.423 + _edge_maps;
1.424 +
1.425 + };
1.426 +
1.427 + /// \brief Copy a graph to another graph.
1.428 + ///
1.429 + /// This function copies a graph to another graph.
1.430 + /// The complete usage of it is detailed in the BpGraphCopy class,
1.431 + /// but a short example shows a basic work:
1.432 + ///\code
1.433 + /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1.434 + ///\endcode
1.435 + ///
1.436 + /// After the copy the \c nr map will contain the mapping from the
1.437 + /// nodes of the \c from graph to the nodes of the \c to graph and
1.438 + /// \c ecr will contain the mapping from the edges of the \c to graph
1.439 + /// to the edges of the \c from graph.
1.440 + ///
1.441 + /// \see BpGraphCopy
1.442 + template <typename From, typename To>
1.443 + BpGraphCopy<From, To>
1.444 + bpGraphCopy(const From& from, To& to) {
1.445 + return BpGraphCopy<From, To>(from, to);
1.446 + }
1.447 +
1.448 namespace _core_bits {
1.449
1.450 template <typename Graph, typename Enable = void>