# HG changeset patch
# User deba
# Date 1162563624 0
# Node ID f30867b359a82aa08c9030d4ea56188ad1705b25
# Parent  03e4d2128efe2d126ed96595bb34e7d112082525
GraphCopy and UGraphCopy modifications
Preliminary support for static graphs
 => cloning graphs

Added BpUGraphCopy

Tests for graph copies

diff -r 03e4d2128efe -r f30867b359a8 lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h	Fri Nov 03 14:14:05 2006 +0000
+++ b/lemon/bits/graph_extender.h	Fri Nov 03 14:20:24 2006 +0000
@@ -282,6 +282,12 @@
       Parent::clear();
     }
 
+    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
+    void clone(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
+      Parent::clone(graph, nodeRef, edgeRef);
+      getNotifier(Node()).build();
+      getNotifier(Edge()).build();
+    }
 
     void erase(const Node& node) {
       Edge edge;
@@ -687,6 +693,15 @@
       Parent::clear();
     }
 
+    template <typename Graph, typename NodeRefMap, typename UEdgeRefMap>
+    void clone(const Graph& graph, NodeRefMap& nodeRef, 
+               UEdgeRefMap& uEdgeRef) {
+      Parent::clone(graph, nodeRef, uEdgeRef);
+      getNotifier(Node()).build();
+      getNotifier(UEdge()).build();
+      getNotifier(Edge()).build();
+    }
+
     void erase(const Node& node) {
       Edge edge;
       Parent::firstOut(edge, node);
@@ -1301,6 +1316,18 @@
       Parent::clear();
     }
 
+    template <typename Graph, typename ANodeRefMap, 
+              typename BNodeRefMap, typename UEdgeRefMap>
+    void clone(const Graph& graph, ANodeRefMap& aNodeRef, 
+               BNodeRefMap& bNodeRef, UEdgeRefMap& uEdgeRef) {
+      Parent::clone(graph, aNodeRef, bNodeRef, uEdgeRef);
+      getNotifier(ANode()).build();
+      getNotifier(BNode()).build();
+      getNotifier(Node()).build();
+      getNotifier(UEdge()).build();
+      getNotifier(Edge()).build();
+    }
+
     void erase(const Node& node) {
       UEdge uedge;
       if (Parent::aNode(node)) {
diff -r 03e4d2128efe -r f30867b359a8 lemon/bits/traits.h
--- a/lemon/bits/traits.h	Fri Nov 03 14:14:05 2006 +0000
+++ b/lemon/bits/traits.h	Fri Nov 03 14:20:24 2006 +0000
@@ -323,7 +323,18 @@
     static const bool value = true;
   };
 
+  template <typename Graph, typename Enable = void>
+  struct CloneableTagIndicator {
+    static const bool value = false;
+  };
 
+  template <typename Graph>
+  struct CloneableTagIndicator<
+    Graph, 
+    typename enable_if<typename Graph::CloneableTag, void>::type
+  > {
+    static const bool value = true;
+  };
 
 }
 
diff -r 03e4d2128efe -r f30867b359a8 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Fri Nov 03 14:14:05 2006 +0000
+++ b/lemon/graph_utils.h	Fri Nov 03 14:20:24 2006 +0000
@@ -615,6 +615,21 @@
       const SourceMap& _map;
     };
 
+    template <typename Graph, typename Item, typename RefMap, typename It>
+    class ItemCopy : public MapCopyBase<Graph, Item, RefMap> {
+    public:
+
+      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
+      
+      virtual void copy(const Graph&, const RefMap& refMap) {
+        _it = refMap[_item];
+      }
+
+    private:
+      It& _it;
+      Item _item;
+    };
+
     template <typename Graph, typename Item, typename RefMap, typename Ref>
     class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
     public:
@@ -650,6 +665,95 @@
       CrossRef& _cmap;
     };
 
+    template <typename Graph, typename Enable = void>
+    struct GraphCopySelector {
+      template <typename Source, typename NodeRefMap, typename EdgeRefMap>
+      static void copy(Graph &target, const Source& source,
+                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+        for (typename Source::NodeIt it(source); it != INVALID; ++it) {
+          nodeRefMap[it] = target.addNode();
+        }
+        for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
+          edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
+                                          nodeRefMap[source.target(it)]);
+        }
+      }
+    };
+
+    template <typename Graph>
+    struct GraphCopySelector<
+      Graph, 
+      typename enable_if<typename Graph::CloneableTag, void>::type> 
+    {
+      template <typename Source, typename NodeRefMap, typename EdgeRefMap>
+      static void copy(Graph &target, const Source& source,
+                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+        target.clone(source, nodeRefMap, edgeRefMap);
+      }
+    };
+
+    template <typename UGraph, typename Enable = void>
+    struct UGraphCopySelector {
+      template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
+      static void copy(UGraph &target, const Source& source,
+                       NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
+        for (typename Source::NodeIt it(source); it != INVALID; ++it) {
+          nodeRefMap[it] = target.addNode();
+        }
+        for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
+          uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
+                                          nodeRefMap[source.target(it)]);
+        }
+      }
+    };
+
+    template <typename UGraph>
+    struct UGraphCopySelector<
+      UGraph, 
+      typename enable_if<typename UGraph::CloneableTag, void>::type> 
+    {
+      template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
+      static void copy(UGraph &target, const Source& source,
+                       NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
+        target.clone(source, nodeRefMap, uEdgeRefMap);
+      }
+    };
+
+    template <typename BpUGraph, typename Enable = void>
+    struct BpUGraphCopySelector {
+      template <typename Source, typename ANodeRefMap, 
+                typename BNodeRefMap, typename UEdgeRefMap>
+      static void copy(BpUGraph &target, const Source& source,
+                       ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
+                       UEdgeRefMap& uEdgeRefMap) {
+        for (typename Source::ANodeIt it(source); it != INVALID; ++it) {
+          aNodeRefMap[it] = target.addANode();
+        }
+        for (typename Source::BNodeIt it(source); it != INVALID; ++it) {
+          bNodeRefMap[it] = target.addBNode();
+        }
+        for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
+          uEdgeRefMap[it] = target.addEdge(aNodeRefMap[source.aNode(it)], 
+                                           bNodeRefMap[source.bNode(it)]);
+        }
+      }
+    };
+
+    template <typename BpUGraph>
+    struct BpUGraphCopySelector<
+      BpUGraph, 
+      typename enable_if<typename BpUGraph::CloneableTag, void>::type> 
+    {
+      template <typename Source, typename ANodeRefMap, 
+                typename BNodeRefMap, typename UEdgeRefMap>
+      static void copy(BpUGraph &target, const Source& source,
+                       ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
+                       UEdgeRefMap& uEdgeRefMap) {
+        target.clone(source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
+      }
+    };
+    
+
   }
 
   /// \brief Class to copy a graph.
@@ -705,9 +809,10 @@
       return *this;
     }
 
-    /// \brief Reverse and copies the node references into the given map.
+    /// \brief Copies the node cross references into the given map.
     ///
-    /// Reverse and copies the node references into the given map.
+    ///  Copies the node cross references (reverse references) into
+    ///  the given map.
     template <typename NodeCrossRef>
     GraphCopy& nodeCrossRef(NodeCrossRef& map) {
       nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
@@ -728,6 +833,15 @@
       return *this;
     }
 
+    /// \brief Make a copy of the given node.
+    ///
+    /// Make a copy of the given node.
+    GraphCopy& node(TNode& tnode, const Node& node) {
+      nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node, 
+                              NodeRefMap, TNode>(tnode, node));
+      return *this;
+    }
+
     /// \brief Copies the edge references into the given map.
     ///
     /// Copies the edge references into the given map.
@@ -738,9 +852,10 @@
       return *this;
     }
 
-    /// \brief Reverse and copies the edge references into the given map.
+    /// \brief Copies the edge cross references into the given map.
     ///
-    /// Reverse and copies the edge references into the given map.
+    ///  Copies the edge cross references (reverse references) into
+    ///  the given map.
     template <typename EdgeCrossRef>
     GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
       edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
@@ -761,29 +876,34 @@
       return *this;
     }
 
+    /// \brief Make a copy of the given edge.
+    ///
+    /// Make a copy of the given edge.
+    GraphCopy& edge(TEdge& tedge, const Edge& edge) {
+      edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge, 
+                              EdgeRefMap, TEdge>(tedge, edge));
+      return *this;
+    }
+
     /// \brief Executes the copies.
     ///
     /// Executes the copies.
     void run() {
       NodeRefMap nodeRefMap(source);
-      for (NodeIt it(source); it != INVALID; ++it) {
-	nodeRefMap[it] = target.addNode();
-      }
+      EdgeRefMap edgeRefMap(source);
+      _graph_utils_bits::GraphCopySelector<Target>::
+        copy(target, source, nodeRefMap, edgeRefMap);
       for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
         nodeMapCopies[i]->copy(source, nodeRefMap);
       }
-      EdgeRefMap edgeRefMap(source);
-      for (EdgeIt it(source); it != INVALID; ++it) {
-	edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
-					nodeRefMap[source.target(it)]);
-      }
       for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
         edgeMapCopies[i]->copy(source, edgeRefMap);
-      }
+      }      
     }
 
-  private:
-    
+  protected:
+
+
     const Source& source;
     Target& target;
 
@@ -808,6 +928,8 @@
   /// source graph's nodes to the target graph's nodes and the \c ecr will
   /// contain the mapping from the target graph's edges to the source's
   /// edges.
+  ///
+  /// \see GraphCopy 
   template <typename Target, typename Source>
   GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
     return GraphCopy<Target, Source>(target, source);
@@ -894,9 +1016,10 @@
       return *this;
     }
 
-    /// \brief Reverse and copies the node references into the given map.
+    /// \brief Copies the node cross references into the given map.
     ///
-    /// Reverse and copies the node references into the given map.
+    ///  Copies the node cross references (reverse references) into
+    ///  the given map.
     template <typename NodeCrossRef>
     UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
       nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
@@ -917,6 +1040,15 @@
       return *this;
     }
 
+    /// \brief Make a copy of the given node.
+    ///
+    /// Make a copy of the given node.
+    UGraphCopy& node(TNode& tnode, const Node& node) {
+      nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node, 
+                              NodeRefMap, TNode>(tnode, node));
+      return *this;
+    }
+
     /// \brief Copies the edge references into the given map.
     ///
     /// Copies the edge references into the given map.
@@ -927,9 +1059,10 @@
       return *this;
     }
 
-    /// \brief Reverse and copies the edge references into the given map.
+    /// \brief Copies the edge cross references into the given map.
     ///
-    /// Reverse and copies the edge references into the given map.
+    ///  Copies the edge cross references (reverse references) into
+    ///  the given map.
     template <typename EdgeCrossRef>
     UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
       edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
@@ -950,9 +1083,18 @@
       return *this;
     }
 
-    /// \brief Copies the uEdge references into the given map.
+    /// \brief Make a copy of the given edge.
     ///
-    /// Copies the uEdge references into the given map.
+    /// Make a copy of the given edge.
+    UGraphCopy& edge(TEdge& tedge, const Edge& edge) {
+      edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge, 
+                              EdgeRefMap, TEdge>(tedge, edge));
+      return *this;
+    }
+
+    /// \brief Copies the undirected edge references into the given map.
+    ///
+    /// Copies the undirected edge references into the given map.
     template <typename UEdgeRef>
     UGraphCopy& uEdgeRef(UEdgeRef& map) {
       uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge, 
@@ -960,9 +1102,10 @@
       return *this;
     }
 
-    /// \brief Reverse and copies the uEdge references into the given map.
+    /// \brief Copies the undirected edge cross references into the given map.
     ///
-    /// Reverse and copies the uEdge references into the given map.
+    /// Copies the undirected edge cross references (reverse
+    /// references) into the given map.
     template <typename UEdgeCrossRef>
     UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
       uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, 
@@ -973,8 +1116,8 @@
     /// \brief Make copy of the given map.
     ///
     /// Makes copy of the given map for the newly created graph. 
-    /// The new map's key type is the target graph's uEdge type,
-    /// and the copied map's key type is the source graph's uEdge
+    /// The new map's key type is the target graph's undirected edge type,
+    /// and the copied map's key type is the source graph's undirected edge
     /// type.  
     template <typename TargetMap, typename SourceMap>
     UGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
@@ -983,23 +1126,27 @@
       return *this;
     }
 
+    /// \brief Make a copy of the given undirected edge.
+    ///
+    /// Make a copy of the given undirected edge.
+    UGraphCopy& uEdge(TUEdge& tuedge, const UEdge& uedge) {
+      uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge, 
+                               UEdgeRefMap, TUEdge>(tuedge, uedge));
+      return *this;
+    }
+
     /// \brief Executes the copies.
     ///
     /// Executes the copies.
     void run() {
       NodeRefMap nodeRefMap(source);
-      for (NodeIt it(source); it != INVALID; ++it) {
-	nodeRefMap[it] = target.addNode();
-      }
+      UEdgeRefMap uEdgeRefMap(source);
+      EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
+      _graph_utils_bits::UGraphCopySelector<Target>::
+        copy(target, source, nodeRefMap, uEdgeRefMap);
       for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
         nodeMapCopies[i]->copy(source, nodeRefMap);
       }
-      UEdgeRefMap uEdgeRefMap(source);
-      EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
-      for (UEdgeIt it(source); it != INVALID; ++it) {
-	uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
-                                         nodeRefMap[source.target(it)]);
-      }
       for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
         uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
       }
@@ -1024,9 +1171,9 @@
 
   };
 
-  /// \brief Copy a graph to another graph.
+  /// \brief Copy an undirected graph to another graph.
   ///
-  /// Copy a graph to another graph.
+  /// Copy an undirected graph to another graph.
   /// The usage of the function:
   /// 
   ///\code
@@ -1037,12 +1184,378 @@
   /// source graph's nodes to the target graph's nodes and the \c ecr will
   /// contain the mapping from the target graph's edges to the source's
   /// edges.
+  ///
+  /// \see UGraphCopy 
   template <typename Target, typename Source>
   UGraphCopy<Target, Source> 
   copyUGraph(Target& target, const Source& source) {
     return UGraphCopy<Target, Source>(target, source);
   }
 
+  /// \brief Class to copy a bipartite undirected graph.
+  ///
+  /// Class to copy a bipartite undirected graph to another graph
+  /// (duplicate a graph).  The simplest way of using it is through
+  /// the \c copyBpUGraph() function.
+  template <typename Target, typename Source>
+  class BpUGraphCopy {
+  private:
+
+    typedef typename Source::Node Node;
+    typedef typename Source::ANode ANode;
+    typedef typename Source::BNode BNode;
+    typedef typename Source::NodeIt NodeIt;
+    typedef typename Source::Edge Edge;
+    typedef typename Source::EdgeIt EdgeIt;
+    typedef typename Source::UEdge UEdge;
+    typedef typename Source::UEdgeIt UEdgeIt;
+
+    typedef typename Target::Node TNode;
+    typedef typename Target::Edge TEdge;
+    typedef typename Target::UEdge TUEdge;
+
+    typedef typename Source::template ANodeMap<TNode> ANodeRefMap;
+    typedef typename Source::template BNodeMap<TNode> BNodeRefMap;
+    typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
+
+    struct NodeRefMap {
+      NodeRefMap(const Source& _source, const ANodeRefMap& _anode_ref,
+                 const BNodeRefMap& _bnode_ref)
+        : source(_source), anode_ref(_anode_ref), bnode_ref(_bnode_ref) {}
+
+      typedef typename Source::Node Key;
+      typedef typename Target::Node Value;
+
+      Value operator[](const Key& key) const {
+	return source.aNode(key) ? anode_ref[key] : bnode_ref[key]; 
+      }
+      
+      const Source& source;
+      const ANodeRefMap& anode_ref;
+      const BNodeRefMap& bnode_ref;
+    };
+
+    struct EdgeRefMap {
+      EdgeRefMap(const Target& _target, const Source& _source,
+                 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref) 
+        : target(_target), source(_source), 
+          uedge_ref(_uedge_ref), node_ref(_node_ref) {}
+
+      typedef typename Source::Edge Key;
+      typedef typename Target::Edge Value;
+
+      Value operator[](const Key& key) const {
+        bool forward = (source.direction(key) == 
+                        (node_ref[source.source((UEdge)key)] == 
+                         target.source(uedge_ref[(UEdge)key])));
+	return target.direct(uedge_ref[key], forward); 
+      }
+      
+      const Target& target;
+      const Source& source;
+      const UEdgeRefMap& uedge_ref;
+      const NodeRefMap& node_ref;
+    };
+    
+  public: 
+
+
+    /// \brief Constructor for the GraphCopy.
+    ///
+    /// It copies the content of the \c _source graph into the
+    /// \c _target graph.
+    BpUGraphCopy(Target& _target, const Source& _source) 
+      : source(_source), target(_target) {}
+
+    /// \brief Destructor of the GraphCopy
+    ///
+    /// Destructor of the GraphCopy
+    ~BpUGraphCopy() {
+      for (int i = 0; i < (int)aNodeMapCopies.size(); ++i) {
+        delete aNodeMapCopies[i];
+      }
+      for (int i = 0; i < (int)bNodeMapCopies.size(); ++i) {
+        delete bNodeMapCopies[i];
+      }
+      for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
+        delete nodeMapCopies[i];
+      }
+      for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
+        delete edgeMapCopies[i];
+      }
+      for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
+        delete uEdgeMapCopies[i];
+      }
+
+    }
+
+    /// \brief Copies the A-node references into the given map.
+    ///
+    /// Copies the A-node references into the given map.
+    template <typename ANodeRef>
+    BpUGraphCopy& aNodeRef(ANodeRef& map) {
+      aNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, ANode, 
+                               ANodeRefMap, ANodeRef>(map));
+      return *this;
+    }
+
+    /// \brief Copies the A-node cross references into the given map.
+    ///
+    /// Copies the A-node cross references (reverse references) into
+    /// the given map.
+    template <typename ANodeCrossRef>
+    BpUGraphCopy& aNodeCrossRef(ANodeCrossRef& map) {
+      aNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, 
+                               ANode, ANodeRefMap, ANodeCrossRef>(map));
+      return *this;
+    }
+
+    /// \brief Make copy of the given A-node map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's node type,
+    /// and the copied map's key type is the source graph's node
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    BpUGraphCopy& aNodeMap(TargetMap& tmap, const SourceMap& map) {
+      aNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, ANode, 
+                               ANodeRefMap, TargetMap, SourceMap>(tmap, map));
+      return *this;
+    }
+
+    /// \brief Copies the B-node references into the given map.
+    ///
+    /// Copies the B-node references into the given map.
+    template <typename BNodeRef>
+    BpUGraphCopy& bNodeRef(BNodeRef& map) {
+      bNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, BNode, 
+                               BNodeRefMap, BNodeRef>(map));
+      return *this;
+    }
+
+    /// \brief Copies the B-node cross references into the given map.
+    ///
+    ///  Copies the B-node cross references (reverse references) into
+    ///  the given map.
+    template <typename BNodeCrossRef>
+    BpUGraphCopy& bNodeCrossRef(BNodeCrossRef& map) {
+      bNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, 
+                              BNode, BNodeRefMap, BNodeCrossRef>(map));
+      return *this;
+    }
+
+    /// \brief Make copy of the given B-node map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's node type,
+    /// and the copied map's key type is the source graph's node
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    BpUGraphCopy& bNodeMap(TargetMap& tmap, const SourceMap& map) {
+      bNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, BNode, 
+                               BNodeRefMap, TargetMap, SourceMap>(tmap, map));
+      return *this;
+    }
+    /// \brief Copies the node references into the given map.
+    ///
+    /// Copies the node references into the given map.
+    template <typename NodeRef>
+    BpUGraphCopy& nodeRef(NodeRef& map) {
+      nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node, 
+                              NodeRefMap, NodeRef>(map));
+      return *this;
+    }
+
+    /// \brief Copies the node cross references into the given map.
+    ///
+    ///  Copies the node cross references (reverse references) into
+    ///  the given map.
+    template <typename NodeCrossRef>
+    BpUGraphCopy& nodeCrossRef(NodeCrossRef& map) {
+      nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
+                              NodeRefMap, NodeCrossRef>(map));
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's node type,
+    /// and the copied map's key type is the source graph's node
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    BpUGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
+      nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node, 
+                              NodeRefMap, TargetMap, SourceMap>(tmap, map));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given node.
+    ///
+    /// Make a copy of the given node.
+    BpUGraphCopy& node(TNode& tnode, const Node& node) {
+      nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node, 
+                              NodeRefMap, TNode>(tnode, node));
+      return *this;
+    }
+
+    /// \brief Copies the edge references into the given map.
+    ///
+    /// Copies the edge references into the given map.
+    template <typename EdgeRef>
+    BpUGraphCopy& edgeRef(EdgeRef& map) {
+      edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge, 
+                              EdgeRefMap, EdgeRef>(map));
+      return *this;
+    }
+
+    /// \brief Copies the edge cross references into the given map.
+    ///
+    ///  Copies the edge cross references (reverse references) into
+    ///  the given map.
+    template <typename EdgeCrossRef>
+    BpUGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
+      edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
+                              EdgeRefMap, EdgeCrossRef>(map));
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's edge type,
+    /// and the copied map's key type is the source graph's edge
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    BpUGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
+      edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge, 
+                              EdgeRefMap, TargetMap, SourceMap>(tmap, map));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given edge.
+    ///
+    /// Make a copy of the given edge.
+    BpUGraphCopy& edge(TEdge& tedge, const Edge& edge) {
+      edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge, 
+                              EdgeRefMap, TEdge>(tedge, edge));
+      return *this;
+    }
+
+    /// \brief Copies the undirected edge references into the given map.
+    ///
+    /// Copies the undirected edge references into the given map.
+    template <typename UEdgeRef>
+    BpUGraphCopy& uEdgeRef(UEdgeRef& map) {
+      uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge, 
+                               UEdgeRefMap, UEdgeRef>(map));
+      return *this;
+    }
+
+    /// \brief Copies the undirected edge cross references into the given map.
+    ///
+    /// Copies the undirected edge cross references (reverse
+    /// references) into the given map.
+    template <typename UEdgeCrossRef>
+    BpUGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
+      uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, 
+                               UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's undirected edge type,
+    /// and the copied map's key type is the source graph's undirected edge
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    BpUGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
+      uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge, 
+                               UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given undirected edge.
+    ///
+    /// Make a copy of the given undirected edge.
+    BpUGraphCopy& uEdge(TUEdge& tuedge, const UEdge& uedge) {
+      uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge, 
+                               UEdgeRefMap, TUEdge>(tuedge, uedge));
+      return *this;
+    }
+
+    /// \brief Executes the copies.
+    ///
+    /// Executes the copies.
+    void run() {
+      ANodeRefMap aNodeRefMap(source);
+      BNodeRefMap bNodeRefMap(source);
+      NodeRefMap nodeRefMap(source, aNodeRefMap, bNodeRefMap);
+      UEdgeRefMap uEdgeRefMap(source);
+      EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
+      _graph_utils_bits::BpUGraphCopySelector<Target>::
+        copy(target, source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
+      for (int i = 0; i < (int)aNodeMapCopies.size(); ++i) {
+        aNodeMapCopies[i]->copy(source, aNodeRefMap);
+      }
+      for (int i = 0; i < (int)bNodeMapCopies.size(); ++i) {
+        bNodeMapCopies[i]->copy(source, bNodeRefMap);
+      }
+      for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
+        nodeMapCopies[i]->copy(source, nodeRefMap);
+      }
+      for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
+        uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
+      }
+      for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
+        edgeMapCopies[i]->copy(source, edgeRefMap);
+      }
+    }
+
+  private:
+    
+    const Source& source;
+    Target& target;
+
+    std::vector<_graph_utils_bits::MapCopyBase<Source, ANode, ANodeRefMap>* > 
+    aNodeMapCopies;
+
+    std::vector<_graph_utils_bits::MapCopyBase<Source, BNode, BNodeRefMap>* > 
+    bNodeMapCopies;
+
+    std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* > 
+    nodeMapCopies;
+
+    std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* > 
+    edgeMapCopies;
+
+    std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* > 
+    uEdgeMapCopies;
+
+  };
+
+  /// \brief Copy a bipartite undirected graph to another graph.
+  ///
+  /// Copy a bipartite undirected graph to another graph.
+  /// The usage of the function:
+  /// 
+  ///\code
+  /// copyBpUGraph(trg, src).aNodeRef(anr).edgeCrossRef(ecr).run();
+  ///\endcode
+  /// 
+  /// After the copy the \c nr map will contain the mapping from the
+  /// source graph's nodes to the target graph's nodes and the \c ecr will
+  /// contain the mapping from the target graph's edges to the source's
+  /// edges.
+  ///
+  /// \see BpUGraphCopy
+  template <typename Target, typename Source>
+  BpUGraphCopy<Target, Source> 
+  copyBpUGraph(Target& target, const Source& source) {
+    return BpUGraphCopy<Target, Source>(target, source);
+  }
+
 
   /// @}
 
diff -r 03e4d2128efe -r f30867b359a8 test/Makefile.am
--- a/test/Makefile.am	Fri Nov 03 14:14:05 2006 +0000
+++ b/test/Makefile.am	Fri Nov 03 14:20:24 2006 +0000
@@ -22,6 +22,7 @@
 	test/dim_test \
 	test/edge_set_test \
 	test/graph_adaptor_test \
+	test/graph_copy_test \
 	test/graph_test \
 	test/graph_utils_test \
 	test/heap_test \
@@ -65,6 +66,7 @@
 test_dim_test_SOURCES = test/dim_test.cc
 test_edge_set_test_SOURCES = test/edge_set_test.cc
 test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
+test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 test_heap_test_SOURCES = test/heap_test.cc
diff -r 03e4d2128efe -r f30867b359a8 test/graph_copy_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/graph_copy_test.cc	Fri Nov 03 14:20:24 2006 +0000
@@ -0,0 +1,312 @@
+#include <lemon/smart_graph.h>
+#include <lemon/list_graph.h>
+#include <lemon/graph_reader.h>
+#include <lemon/graph_utils.h>
+#include <lemon/error.h>
+
+#include "test_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+void graph_copy_test() {
+  const int nn = 10;
+
+  SmartGraph source;
+  SmartGraph::NodeMap<int> snm(source);
+  SmartGraph::EdgeMap<int> sem(source);
+  SmartGraph::Node sn = INVALID;
+  SmartGraph::Edge se = INVALID;
+
+  std::vector<SmartGraph::Node> snv;
+  for (int i = 0; i < nn; ++i) {
+    SmartGraph::Node node = source.addNode();
+    snv.push_back(node);
+    snm[node] = i * i;
+    if (i == 0) sn = node;
+  }
+
+  for (int i = 0; i < nn; ++i) {
+    for (int j = 0; j < nn; ++j) {
+      SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);
+      sem[edge] = i + j * j;
+      if (i == 0 && j == 0) se = edge;
+    }
+  }
+
+  ListGraph target;
+  ListGraph::NodeMap<int> tnm(target);
+  ListGraph::EdgeMap<int> tem(target);
+  ListGraph::Node tn;
+  ListGraph::Edge te;
+
+  SmartGraph::NodeMap<ListGraph::Node> nr(source);
+  SmartGraph::EdgeMap<ListGraph::Edge> er(source);
+
+  ListGraph::NodeMap<SmartGraph::Node> ncr(target);
+  ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
+
+  GraphCopy<ListGraph, SmartGraph>(target, source).
+    nodeMap(tnm, snm).edgeMap(tem, sem).
+    nodeRef(nr).edgeRef(er).
+    nodeCrossRef(ncr).edgeCrossRef(ecr).
+    node(tn, sn).edge(te, se).run();
+
+  for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {
+    check(ncr[nr[it]] == it, "Wrong copy.");
+    check(snm[it] == tnm[nr[it]], "Wrong copy.");
+  }
+
+  for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {
+    check(ecr[er[it]] == it, "Wrong copy.");
+    check(sem[it] == tem[er[it]], "Wrong copy.");
+    check(nr[source.source(it)] == 
+                 target.source(er[it]), "Wrong copy.");
+    check(nr[source.target(it)] == 
+                 target.target(er[it]), "Wrong copy.");
+  }
+
+  for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
+    check(nr[ncr[it]] == it, "Wrong copy.");
+  }
+
+  for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {
+    check(er[ecr[it]] == it, "Wrong copy.");
+  }
+  check(tn == nr[sn], "Wrong copy.");
+  check(te == er[se], "Wrong copy.");
+}
+
+void ugraph_copy_test() {
+  const int nn = 10;
+
+  SmartUGraph source;
+  SmartUGraph::NodeMap<int> snm(source);
+  SmartUGraph::EdgeMap<int> sem(source);
+  SmartUGraph::UEdgeMap<int> suem(source);
+  SmartUGraph::Node sn = INVALID;
+  SmartUGraph::Edge se = INVALID;
+  SmartUGraph::UEdge sue = INVALID;
+
+  std::vector<SmartGraph::Node> snv;
+  for (int i = 0; i < nn; ++i) {
+    SmartUGraph::Node node = source.addNode();
+    snv.push_back(node);
+    snm[node] = i * i;
+    if (i == 0) sn = node;
+  }
+
+  for (int i = 0; i < nn; ++i) {
+    for (int j = 0; j < nn; ++j) {
+      SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);
+      suem[edge] = i * i + j * j;
+      sem[source.direct(edge, true)] = i + j * j;
+      sem[source.direct(edge, false)] = i * i + j;
+      if (i == 0 && j == 0) se = source.direct(edge, true);
+      if (i == 0 && j == 0) sue = edge;
+    }
+  }
+  
+  ListUGraph target;
+  ListUGraph::NodeMap<int> tnm(target);
+  ListUGraph::EdgeMap<int> tem(target);
+  ListUGraph::UEdgeMap<int> tuem(target);
+  ListUGraph::Node tn;
+  ListUGraph::Edge te;
+  ListUGraph::UEdge tue;
+
+  SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
+  SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
+  SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
+
+  ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
+  ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
+  ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
+
+  UGraphCopy<ListUGraph, SmartUGraph>(target, source).
+    nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).
+    nodeRef(nr).edgeRef(er).uEdgeRef(uer).
+    nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).
+    node(tn, sn).edge(te, se).uEdge(tue, sue).run();
+
+  for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {
+    check(ncr[nr[it]] == it, "Wrong copy.");
+    check(snm[it] == tnm[nr[it]], "Wrong copy.");
+  }
+
+  for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {
+    check(ecr[er[it]] == it, "Wrong copy.");
+    check(sem[it] == tem[er[it]], "Wrong copy.");
+    check(nr[source.source(it)] == 
+                 target.source(er[it]), "Wrong copy.");
+    check(nr[source.target(it)] == 
+                 target.target(er[it]), "Wrong copy.");
+  }
+
+  for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {
+    check(uecr[uer[it]] == it, "Wrong copy.");
+    check(suem[it] == tuem[uer[it]], "Wrong copy.");
+    check(nr[source.source(it)] == target.source(uer[it]) ||
+                 nr[source.source(it)] == target.target(uer[it]), 
+                 "Wrong copy.");
+    check(nr[source.target(it)] == target.source(uer[it]) ||
+                 nr[source.target(it)] == target.target(uer[it]), 
+                 "Wrong copy.");
+    check((source.source(it) != source.target(it)) ==
+                 (target.source(uer[it]) != target.target(uer[it])), 
+                 "Wrong copy.");
+  }
+
+  for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
+    check(nr[ncr[it]] == it, "Wrong copy.");
+  }
+
+  for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {
+    check(er[ecr[it]] == it, "Wrong copy.");
+  }
+  for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {
+    check(uer[uecr[it]] == it, "Wrong copy.");
+  }
+  check(tn == nr[sn], "Wrong copy.");
+  check(te == er[se], "Wrong copy.");
+  check(tue == uer[sue], "Wrong copy.");
+}
+
+void bpugraph_copy_test() {
+  const int nn = 10;
+
+  SmartBpUGraph source;
+  SmartBpUGraph::ANodeMap<int> sanm(source);
+  SmartBpUGraph::BNodeMap<int> sbnm(source);
+  SmartBpUGraph::NodeMap<int> snm(source);
+  SmartBpUGraph::EdgeMap<int> sem(source);
+  SmartBpUGraph::UEdgeMap<int> suem(source);
+  SmartBpUGraph::Node sn = INVALID;
+  SmartBpUGraph::Edge se = INVALID;
+  SmartBpUGraph::UEdge sue = INVALID;
+
+  std::vector<SmartBpUGraph::Node> sanv;
+  for (int i = 0; i < nn; ++i) {
+    SmartBpUGraph::Node node = source.addANode();
+    sanv.push_back(node);
+    sanm[node] = i * i;
+    snm[node] = i * i + i;
+    if (i == 0) sn = node;
+  }
+
+  std::vector<SmartBpUGraph::Node> sbnv;
+  for (int i = 0; i < nn; ++i) {
+    SmartBpUGraph::Node node = source.addBNode();
+    sbnv.push_back(node);
+    sbnm[node] = i * i - i;
+    snm[node] = i * i + i + 1;
+  }
+
+  for (int i = 0; i < nn; ++i) {
+    for (int j = 0; j < nn; ++j) {
+      SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);
+      suem[edge] = i * i + j * j;
+      sem[source.direct(edge, true)] = i + j * j;
+      sem[source.direct(edge, false)] = i * i + j;
+      if (i == 0 && j == 0) se = source.direct(edge, true);
+      if (i == 0 && j == 0) sue = edge;
+    }
+  }
+  
+  ListBpUGraph target;
+  ListBpUGraph::ANodeMap<int> tanm(target);
+  ListBpUGraph::BNodeMap<int> tbnm(target);
+  ListBpUGraph::NodeMap<int> tnm(target);
+  ListBpUGraph::EdgeMap<int> tem(target);
+  ListBpUGraph::UEdgeMap<int> tuem(target);
+  ListBpUGraph::Node tn;
+  ListBpUGraph::Edge te;
+  ListBpUGraph::UEdge tue;
+
+  SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
+  SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
+  SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
+  SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
+  SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);
+
+  ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
+  ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
+  ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
+  ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
+  ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);
+
+  BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).
+    aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).
+    edgeMap(tem, sem).uEdgeMap(tuem, suem).
+    aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).
+    aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).
+    edgeCrossRef(ecr).uEdgeCrossRef(uecr).
+    node(tn, sn).edge(te, se).uEdge(tue, sue).run();
+
+  for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {
+    check(nr[it] == anr[it], "Wrong copy.");
+    check(ancr[anr[it]] == it, "Wrong copy.");
+    check(sanm[it] == tanm[anr[it]], "Wrong copy.");
+  }
+
+  for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {
+    check(nr[it] == bnr[it], "Wrong copy.");
+    check(bncr[bnr[it]] == it, "Wrong copy.");
+    check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");
+  }
+
+  for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {
+    check(ncr[nr[it]] == it, "Wrong copy.");
+    check(snm[it] == tnm[nr[it]], "Wrong copy.");
+  }
+
+  for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {
+    check(ecr[er[it]] == it, "Wrong copy.");
+    check(sem[it] == tem[er[it]], "Wrong copy.");
+    check(nr[source.source(it)] == 
+                 target.source(er[it]), "Wrong copy.");
+    check(nr[source.target(it)] == 
+                 target.target(er[it]), "Wrong copy.");
+  }
+
+  for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {
+    check(uecr[uer[it]] == it, "Wrong copy.");
+    check(suem[it] == tuem[uer[it]], "Wrong copy.");
+    check(nr[source.aNode(it)] == 
+                 target.aNode(uer[it]), "Wrong copy.");
+    check(nr[source.bNode(it)] == 
+                 target.bNode(uer[it]), "Wrong copy.");
+  }
+
+  for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {
+    check(ancr[it] == ncr[it], "Wrong copy.");
+    check(anr[ancr[it]] == it, "Wrong copy.");
+  }
+
+  for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {
+    check(bncr[it] == ncr[it], "Wrong copy.");
+    check(bnr[bncr[it]] == it, "Wrong copy.");
+  }
+
+  for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
+    check(nr[ncr[it]] == it, "Wrong copy.");
+  }
+
+  for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {
+    check(er[ecr[it]] == it, "Wrong copy.");
+  }
+  for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {
+    check(uer[uecr[it]] == it, "Wrong copy.");
+  }
+  check(tn == nr[sn], "Wrong copy.");
+  check(te == er[se], "Wrong copy.");
+  check(tue == uer[sue], "Wrong copy.");
+}
+
+int main() {
+  graph_copy_test();
+  ugraph_copy_test();
+  bpugraph_copy_test();
+
+  return 0; 
+}