# Changeset 1190:523e45e37e52 in lemon

Ignore:
Timestamp:
11/16/10 00:59:36 (9 years ago)
Branch:
default
Phase:
public
Message:

Implementation of BpGraphCopy? (#69)

Files:
2 edited

Unmodified
Removed
• ## lemon/core.h

 r1188 template static void copy(const From& from, Graph &to, NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { to.build(from, nodeRefMap, edgeRefMap); } }; template struct BpGraphCopySelector { template static void copy(const From& from, BpGraph &to, NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { to.clear(); for (typename From::RedIt it(from); it != INVALID; ++it) { nodeRefMap[it] = to.addRedNode(); } for (typename From::BlueIt it(from); it != INVALID; ++it) { nodeRefMap[it] = to.addBlueNode(); } for (typename From::EdgeIt it(from); it != INVALID; ++it) { edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)], nodeRefMap[from.blueNode(it)]); } } }; template struct BpGraphCopySelector< BpGraph, typename enable_if::type> { template static void copy(const From& from, BpGraph &to, NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { to.build(from, nodeRefMap, edgeRefMap); graphCopy(const From& from, To& to) { return GraphCopy(from, to); } /// \brief Class to copy a bipartite graph. /// /// Class to copy a bipartite graph to another graph (duplicate a /// graph). The simplest way of using it is through the /// \c bpGraphCopy() function. /// /// This class not only make a copy of a bipartite graph, but it can /// create references and cross references between the nodes, edges /// and arcs of the two graphs, and it can copy maps for using with /// the newly created graph. /// /// To make a copy from a graph, first an instance of BpGraphCopy /// should be created, then the data belongs to the graph should /// assigned to copy. In the end, the \c run() member should be /// called. /// /// The next code copies a graph with several data: ///\code ///  BpGraphCopy cg(orig_graph, new_graph); ///  // Create references for the nodes ///  OrigBpGraph::NodeMap nr(orig_graph); ///  cg.nodeRef(nr); ///  // Create cross references (inverse) for the edges ///  NewBpGraph::EdgeMap ecr(new_graph); ///  cg.edgeCrossRef(ecr); ///  // Copy a red map ///  OrigBpGraph::RedMap ormap(orig_graph); ///  NewBpGraph::RedMap nrmap(new_graph); ///  cg.edgeMap(ormap, nrmap); ///  // Copy a node ///  OrigBpGraph::Node on; ///  NewBpGraph::Node nn; ///  cg.node(on, nn); ///  // Execute copying ///  cg.run(); ///\endcode template class BpGraphCopy { private: typedef typename From::Node Node; typedef typename From::RedNode RedNode; typedef typename From::BlueNode BlueNode; typedef typename From::NodeIt NodeIt; typedef typename From::Arc Arc; typedef typename From::ArcIt ArcIt; typedef typename From::Edge Edge; typedef typename From::EdgeIt EdgeIt; typedef typename To::Node TNode; typedef typename To::Arc TArc; typedef typename To::Edge TEdge; typedef typename From::template NodeMap NodeRefMap; typedef typename From::template EdgeMap EdgeRefMap; struct ArcRefMap { ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref) : _from(from), _to(to), _edge_ref(edge_ref) {} typedef typename From::Arc Key; typedef typename To::Arc Value; Value operator[](const Key& key) const { return _to.direct(_edge_ref[key], _from.direction(key)); } const From& _from; const To& _to; const EdgeRefMap& _edge_ref; }; public: /// \brief Constructor of BpGraphCopy. /// /// Constructor of BpGraphCopy for copying the content of the /// \c from graph into the \c to graph. BpGraphCopy(const From& from, To& to) : _from(from), _to(to) {} /// \brief Destructor of BpGraphCopy /// /// Destructor of BpGraphCopy. ~BpGraphCopy() { for (int i = 0; i < int(_node_maps.size()); ++i) { delete _node_maps[i]; } for (int i = 0; i < int(_red_maps.size()); ++i) { delete _red_maps[i]; } for (int i = 0; i < int(_blue_maps.size()); ++i) { delete _blue_maps[i]; } for (int i = 0; i < int(_arc_maps.size()); ++i) { delete _arc_maps[i]; } for (int i = 0; i < int(_edge_maps.size()); ++i) { delete _edge_maps[i]; } } /// \brief Copy the node references into the given map. /// /// This function copies the node references into the given map. /// The parameter should be a map, whose key type is the Node type of /// the source graph, while the value type is the Node type of the /// destination graph. template BpGraphCopy& nodeRef(NodeRef& map) { _node_maps.push_back(new _core_bits::RefCopy(map)); return *this; } /// \brief Copy the node cross references into the given map. /// /// This function copies the node cross references (reverse references) /// into the given map. The parameter should be a map, whose key type /// is the Node type of the destination graph, while the value type is /// the Node type of the source graph. template BpGraphCopy& nodeCrossRef(NodeCrossRef& map) { _node_maps.push_back(new _core_bits::CrossRefCopy(map)); return *this; } /// \brief Make a copy of the given node map. /// /// This function makes a copy of the given node map for the newly /// created graph. /// The key type of the new map \c tmap should be the Node type of the /// destination graph, and the key type of the original map \c map /// should be the Node type of the source graph. template BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { _node_maps.push_back(new _core_bits::MapCopy(map, tmap)); return *this; } /// \brief Make a copy of the given node. /// /// This function makes a copy of the given node. BpGraphCopy& node(const Node& node, TNode& tnode) { _node_maps.push_back(new _core_bits::ItemCopy(node, tnode)); return *this; } /// \brief Copy the red node references into the given map. /// /// This function copies the red node references into the given /// map.  The parameter should be a map, whose key type is the /// Node type of the source graph with the red item set, while the /// value type is the Node type of the destination graph. template BpGraphCopy& redRef(RedRef& map) { _red_maps.push_back(new _core_bits::RefCopy(map)); return *this; } /// \brief Copy the red node cross references into the given map. /// /// This function copies the red node cross references (reverse /// references) into the given map. The parameter should be a map, /// whose key type is the Node type of the destination graph with /// the red item set, while the value type is the Node type of the /// source graph. template BpGraphCopy& redCrossRef(RedCrossRef& map) { _red_maps.push_back(new _core_bits::CrossRefCopy(map)); return *this; } /// \brief Make a copy of the given red node map. /// /// This function makes a copy of the given red node map for the newly /// created graph. /// The key type of the new map \c tmap should be the Node type of /// the destination graph with the red items, and the key type of /// the original map \c map should be the Node type of the source /// graph. template BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) { _red_maps.push_back(new _core_bits::MapCopy(map, tmap)); return *this; } /// \brief Copy the blue node references into the given map. /// /// This function copies the blue node references into the given /// map.  The parameter should be a map, whose key type is the /// Node type of the source graph with the blue item set, while the /// value type is the Node type of the destination graph. template BpGraphCopy& blueRef(BlueRef& map) { _blue_maps.push_back(new _core_bits::RefCopy(map)); return *this; } /// \brief Copy the blue node cross references into the given map. /// /// This function copies the blue node cross references (reverse /// references) into the given map. The parameter should be a map, /// whose key type is the Node type of the destination graph with /// the blue item set, while the value type is the Node type of the /// source graph. template BpGraphCopy& blueCrossRef(BlueCrossRef& map) { _blue_maps.push_back(new _core_bits::CrossRefCopy(map)); return *this; } /// \brief Make a copy of the given blue node map. /// /// This function makes a copy of the given blue node map for the newly /// created graph. /// The key type of the new map \c tmap should be the Node type of /// the destination graph with the blue items, and the key type of /// the original map \c map should be the Node type of the source /// graph. template BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) { _blue_maps.push_back(new _core_bits::MapCopy(map, tmap)); return *this; } /// \brief Copy the arc references into the given map. /// /// This function copies the arc references into the given map. /// The parameter should be a map, whose key type is the Arc type of /// the source graph, while the value type is the Arc type of the /// destination graph. template BpGraphCopy& arcRef(ArcRef& map) { _arc_maps.push_back(new _core_bits::RefCopy(map)); return *this; } /// \brief Copy the arc cross references into the given map. /// /// This function copies the arc cross references (reverse references) /// into the given map. The parameter should be a map, whose key type /// is the Arc type of the destination graph, while the value type is /// the Arc type of the source graph. template BpGraphCopy& arcCrossRef(ArcCrossRef& map) { _arc_maps.push_back(new _core_bits::CrossRefCopy(map)); return *this; } /// \brief Make a copy of the given arc map. /// /// This function makes a copy of the given arc map for the newly /// created graph. /// The key type of the new map \c tmap should be the Arc type of the /// destination graph, and the key type of the original map \c map /// should be the Arc type of the source graph. template BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) { _arc_maps.push_back(new _core_bits::MapCopy(map, tmap)); return *this; } /// \brief Make a copy of the given arc. /// /// This function makes a copy of the given arc. BpGraphCopy& arc(const Arc& arc, TArc& tarc) { _arc_maps.push_back(new _core_bits::ItemCopy(arc, tarc)); return *this; } /// \brief Copy the edge references into the given map. /// /// This function copies the edge references into the given map. /// The parameter should be a map, whose key type is the Edge type of /// the source graph, while the value type is the Edge type of the /// destination graph. template BpGraphCopy& edgeRef(EdgeRef& map) { _edge_maps.push_back(new _core_bits::RefCopy(map)); return *this; } /// \brief Copy the edge cross references into the given map. /// /// This function copies the edge cross references (reverse references) /// into the given map. The parameter should be a map, whose key type /// is the Edge type of the destination graph, while the value type is /// the Edge type of the source graph. template BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) { _edge_maps.push_back(new _core_bits::CrossRefCopy(map)); return *this; } /// \brief Make a copy of the given edge map. /// /// This function makes a copy of the given edge map for the newly /// created graph. /// The key type of the new map \c tmap should be the Edge type of the /// destination graph, and the key type of the original map \c map /// should be the Edge type of the source graph. template BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { _edge_maps.push_back(new _core_bits::MapCopy(map, tmap)); return *this; } /// \brief Make a copy of the given edge. /// /// This function makes a copy of the given edge. BpGraphCopy& edge(const Edge& edge, TEdge& tedge) { _edge_maps.push_back(new _core_bits::ItemCopy(edge, tedge)); return *this; } /// \brief Execute copying. /// /// This function executes the copying of the graph along with the /// copying of the assigned data. void run() { NodeRefMap nodeRefMap(_from); EdgeRefMap edgeRefMap(_from); ArcRefMap arcRefMap(_from, _to, edgeRefMap); _core_bits::BpGraphCopySelector:: copy(_from, _to, nodeRefMap, edgeRefMap); for (int i = 0; i < int(_node_maps.size()); ++i) { _node_maps[i]->copy(_from, nodeRefMap); } for (int i = 0; i < int(_red_maps.size()); ++i) { _red_maps[i]->copy(_from, nodeRefMap); } for (int i = 0; i < int(_blue_maps.size()); ++i) { _blue_maps[i]->copy(_from, nodeRefMap); } for (int i = 0; i < int(_edge_maps.size()); ++i) { _edge_maps[i]->copy(_from, edgeRefMap); } for (int i = 0; i < int(_arc_maps.size()); ++i) { _arc_maps[i]->copy(_from, arcRefMap); } } private: const From& _from; To& _to; std::vector<_core_bits::MapCopyBase* > _node_maps; std::vector<_core_bits::MapCopyBase* > _red_maps; std::vector<_core_bits::MapCopyBase* > _blue_maps; std::vector<_core_bits::MapCopyBase* > _arc_maps; std::vector<_core_bits::MapCopyBase* > _edge_maps; }; /// \brief Copy a graph to another graph. /// /// This function copies a graph to another graph. /// The complete usage of it is detailed in the BpGraphCopy class, /// but a short example shows a basic work: ///\code /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); ///\endcode /// /// After the copy the \c nr map will contain the mapping from the /// nodes of the \c from graph to the nodes of the \c to graph and /// \c ecr will contain the mapping from the edges of the \c to graph /// to the edges of the \c from graph. /// /// \see BpGraphCopy template BpGraphCopy bpGraphCopy(const From& from, To& to) { return BpGraphCopy(from, to); }
• ## test/graph_copy_test.cc

 r989 } template void bpgraph_copy_test() { const int nn = 10; // Build a graph SmartBpGraph from; SmartBpGraph::NodeMap fnm(from); SmartBpGraph::RedMap frnm(from); SmartBpGraph::BlueMap fbnm(from); SmartBpGraph::ArcMap fam(from); SmartBpGraph::EdgeMap fem(from); SmartBpGraph::Node fn = INVALID; SmartBpGraph::Arc fa = INVALID; SmartBpGraph::Edge fe = INVALID; std::vector frnv; for (int i = 0; i < nn; ++i) { SmartBpGraph::Node node = from.addRedNode(); frnv.push_back(node); fnm[node] = i * i; frnm[node] = i + i; if (i == 0) fn = node; } std::vector fbnv; for (int i = 0; i < nn; ++i) { SmartBpGraph::Node node = from.addBlueNode(); fbnv.push_back(node); fnm[node] = i * i; fbnm[node] = i + i; } for (int i = 0; i < nn; ++i) { for (int j = 0; j < nn; ++j) { SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]); fem[edge] = i * i + j * j; fam[from.direct(edge, true)] = i + j * j; fam[from.direct(edge, false)] = i * i + j; if (i == 0 && j == 0) fa = from.direct(edge, true); if (i == 0 && j == 0) fe = edge; } } // Test graph copy GR to; typename GR::template NodeMap tnm(to); typename GR::template RedMap trnm(to); typename GR::template BlueMap tbnm(to); typename GR::template ArcMap tam(to); typename GR::template EdgeMap tem(to); typename GR::Node tn; typename GR::Arc ta; typename GR::Edge te; SmartBpGraph::NodeMap nr(from); SmartBpGraph::RedMap rnr(from); SmartBpGraph::BlueMap bnr(from); SmartBpGraph::ArcMap ar(from); SmartBpGraph::EdgeMap er(from); typename GR::template NodeMap ncr(to); typename GR::template RedMap rncr(to); typename GR::template BlueMap bncr(to); typename GR::template ArcMap acr(to); typename GR::template EdgeMap ecr(to); bpGraphCopy(from, to). nodeMap(fnm, tnm).redMap(frnm, trnm).blueMap(fbnm, tbnm). arcMap(fam, tam).edgeMap(fem, tem). nodeRef(nr).redRef(rnr).blueRef(bnr). arcRef(ar).edgeRef(er). nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr). arcCrossRef(acr).edgeCrossRef(ecr). node(fn, tn).arc(fa, ta).edge(fe, te).run(); check(countNodes(from) == countNodes(to), "Wrong copy."); check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); check(countEdges(from) == countEdges(to), "Wrong copy."); check(countArcs(from) == countArcs(to), "Wrong copy."); for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) { check(ncr[nr[it]] == it, "Wrong copy."); check(fnm[it] == tnm[nr[it]], "Wrong copy."); if (from.red(it)) { check(rnr[it] == nr[it], "Wrong copy."); check(rncr[rnr[it]] == it, "Wrong copy."); check(frnm[it] == trnm[rnr[it]], "Wrong copy."); check(to.red(rnr[it]), "Wrong copy."); } else { check(bnr[it] == nr[it], "Wrong copy."); check(bncr[bnr[it]] == it, "Wrong copy."); check(fbnm[it] == tbnm[bnr[it]], "Wrong copy."); check(to.blue(bnr[it]), "Wrong copy."); } } for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) { check(acr[ar[it]] == it, "Wrong copy."); check(fam[it] == tam[ar[it]], "Wrong copy."); check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy."); check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy."); } for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) { check(ecr[er[it]] == it, "Wrong copy."); check(fem[it] == tem[er[it]], "Wrong copy."); check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), "Wrong copy."); check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), "Wrong copy."); check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), "Wrong copy."); } for (typename GR::NodeIt it(to); it != INVALID; ++it) { check(nr[ncr[it]] == it, "Wrong copy."); } for (typename GR::RedIt it(to); it != INVALID; ++it) { check(rncr[it] == ncr[it], "Wrong copy."); check(rnr[rncr[it]] == it, "Wrong copy."); } for (typename GR::BlueIt it(to); it != INVALID; ++it) { check(bncr[it] == ncr[it], "Wrong copy."); check(bnr[bncr[it]] == it, "Wrong copy."); } for (typename GR::ArcIt it(to); it != INVALID; ++it) { check(ar[acr[it]] == it, "Wrong copy."); } for (typename GR::EdgeIt it(to); it != INVALID; ++it) { check(er[ecr[it]] == it, "Wrong copy."); } check(tn == nr[fn], "Wrong copy."); check(ta == ar[fa], "Wrong copy."); check(te == er[fe], "Wrong copy."); // Test repeated copy bpGraphCopy(from, to).run(); check(countNodes(from) == countNodes(to), "Wrong copy."); check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); check(countEdges(from) == countEdges(to), "Wrong copy."); check(countArcs(from) == countArcs(to), "Wrong copy."); } int main() { graph_copy_test(); graph_copy_test(); bpgraph_copy_test(); bpgraph_copy_test(); return 0;
Note: See TracChangeset for help on using the changeset viewer.