Changeset 1086:97f1760dcd13 in lemon-main

Timestamp:

08/07/13 07:04:58 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1082:cae19e9eeca4 (diff), 1085:a337a0dd3f75 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge #294

Files:

• lemon/concepts/digraph.h (modified) (1 diff)
• lemon/concepts/digraph.h (modified) (2 diffs)
• lemon/concepts/graph.h (modified) (3 diffs)
• lemon/concepts/graph.h (modified) (3 diffs)
• lemon/concepts/graph_components.h (modified) (10 diffs)
• lemon/concepts/graph_components.h (modified) (13 diffs)
• lemon/core.h (modified) (5 diffs)
• test/dfs_test.cc (modified) (2 diffs)
• test/maps_test.cc (modified) (8 diffs)
• test/maps_test.cc (modified) (1 diff)

lemon/concepts/digraph.h

@@ -313 +313 @@
         /// Sets the iterator to the first arc of the given digraph.
         ///
-        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+        explicit ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); }
         /// Sets the iterator to the given arc.
 

lemon/concepts/digraph.h

@@ -410 +410 @@
       /// \brief The base node of the iterator.
       ///
-      /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
@@ -416 +416 @@
       /// \brief The running node of the iterator.
       ///
-      /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/graph.h

@@ -397 +397 @@
         /// Sets the iterator to the first arc of the given graph.
         ///
-        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+        explicit ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); }
         /// Sets the iterator to the given arc.
 
@@ -443 +443 @@
         ///
         OutArcIt(const Graph& n, const Node& g) {
-          ignore_unused_variable_warning(n);
-          ignore_unused_variable_warning(g);
+          ::lemon::ignore_unused_variable_warning(n);
+          ::lemon::ignore_unused_variable_warning(g);
         }
         /// Sets the iterator to the given arc.
@@ -491 +491 @@
         ///
         InArcIt(const Graph& g, const Node& n) {
-          ignore_unused_variable_warning(n);
-          ignore_unused_variable_warning(g);
+          ::lemon::ignore_unused_variable_warning(n);
+          ::lemon::ignore_unused_variable_warning(g);
         }
         /// Sets the iterator to the given arc.

lemon/concepts/graph.h

@@ -73 +73 @@
     class Graph {
     private:
-      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+      /// Graphs are \e not copy constructible. Use GraphCopy instead.
       Graph(const Graph&) {}
       /// \brief Assignment of a graph to another one is \e not allowed.
-      /// Use DigraphCopy instead.
+      /// Use GraphCopy instead.
       void operator=(const Graph&) {}
 
@@ -758 +758 @@
       /// \brief The base node of the iterator.
       ///
-      /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
@@ -764 +764 @@
       /// \brief The running node of the iterator.
       ///
-      /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/graph_components.h

@@ -109 +109 @@
 
           bool b;
-          ignore_unused_variable_warning(b);
+          ::lemon::ignore_unused_variable_warning(b);
 
           b = (ia == ib) && (ia != ib);
@@ -290 +290 @@
             ue = e;
             bool d = graph.direction(e);
-            ignore_unused_variable_warning(d);
+            ::lemon::ignore_unused_variable_warning(d);
           }
         }
@@ -535 +535 @@
 
           nid = digraph.maxNodeId();
-          ignore_unused_variable_warning(nid);
+          ::lemon::ignore_unused_variable_warning(nid);
           eid = digraph.maxArcId();
-          ignore_unused_variable_warning(eid);
+          ::lemon::ignore_unused_variable_warning(eid);
         }
 
@@ -590 +590 @@
           edge = graph.edgeFromId(ueid);
           ueid = graph.maxEdgeId();
-          ignore_unused_variable_warning(ueid);
+          ::lemon::ignore_unused_variable_warning(ueid);
         }
 
@@ -727 +727 @@
           _GraphItemIt it3 = it1;
           _GraphItemIt it4 = INVALID;
-          ignore_unused_variable_warning(it3);
-          ignore_unused_variable_warning(it4);
+          ::lemon::ignore_unused_variable_warning(it3);
+          ::lemon::ignore_unused_variable_warning(it4);
 
           it2 = ++it1;
@@ -818 +818 @@
           _GraphIncIt it3 = it1;
           _GraphIncIt it4 = INVALID;
-          ignore_unused_variable_warning(it3);
-          ignore_unused_variable_warning(it4);
+          ::lemon::ignore_unused_variable_warning(it3);
+          ::lemon::ignore_unused_variable_warning(it4);
 
           it2 = ++it1;
@@ -1001 +1001 @@
             n = digraph.baseNode(oait);
             n = digraph.runningNode(oait);
-            ignore_unused_variable_warning(n);
+            ::lemon::ignore_unused_variable_warning(n);
           }
         }
@@ -1278 +1278 @@
             = digraph.notifier(typename _Digraph::Arc());
 
-          ignore_unused_variable_warning(nn);
-          ignore_unused_variable_warning(en);
+          ::lemon::ignore_unused_variable_warning(nn);
+          ::lemon::ignore_unused_variable_warning(en);
         }
 
@@ -1326 +1326 @@
           typename _Graph::EdgeNotifier& uen
             = graph.notifier(typename _Graph::Edge());
-          ignore_unused_variable_warning(uen);
+          ::lemon::ignore_unused_variable_warning(uen);
         }
 
@@ -1462 +1462 @@
           // m3 = cmap;
 
-          ignore_unused_variable_warning(m1);
-          ignore_unused_variable_warning(m2);
-          // ignore_unused_variable_warning(m3);
+          ::lemon::ignore_unused_variable_warning(m1);
+          ::lemon::ignore_unused_variable_warning(m2);
+          // ::lemon::ignore_unused_variable_warning(m3);
         }
 

lemon/concepts/graph_components.h

@@ -300 +300 @@
     };
 
+    /// \brief Base skeleton class for undirected bipartite graphs.
+    ///
+    /// This class describes the base interface of undirected
+    /// bipartite graph types.  All bipartite graph %concepts have to
+    /// conform to this class.  It extends the interface of \ref
+    /// BaseGraphComponent with an \c Edge type and functions to get
+    /// the end nodes of edges, to convert from arcs to edges and to
+    /// get both direction of edges.
+    class BaseBpGraphComponent : public BaseGraphComponent {
+    public:
+
+      typedef BaseBpGraphComponent BpGraph;
+
+      typedef BaseDigraphComponent::Node Node;
+      typedef BaseDigraphComponent::Arc Arc;
+
+      /// \brief Class to represent red nodes.
+      ///
+      /// This class represents the red nodes of the graph. The red
+      /// nodes can also be used as normal nodes.
+      class RedNode : public Node {
+        typedef Node Parent;
+
+      public:
+        /// \brief Default constructor.
+        ///
+        /// Default constructor.
+        /// \warning The default constructor is not required to set
+        /// the item to some well-defined value. So you should consider it
+        /// as uninitialized.
+        RedNode() {}
+
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        RedNode(const RedNode &) : Parent() {}
+
+        /// \brief Constructor for conversion from \c INVALID.
+        ///
+        /// Constructor for conversion from \c INVALID.
+        /// It initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        RedNode(Invalid) {}
+      };
+
+      /// \brief Class to represent blue nodes.
+      ///
+      /// This class represents the blue nodes of the graph. The blue
+      /// nodes can also be used as normal nodes.
+      class BlueNode : public Node {
+        typedef Node Parent;
+
+      public:
+        /// \brief Default constructor.
+        ///
+        /// Default constructor.
+        /// \warning The default constructor is not required to set
+        /// the item to some well-defined value. So you should consider it
+        /// as uninitialized.
+        BlueNode() {}
+
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        BlueNode(const BlueNode &) : Parent() {}
+
+        /// \brief Constructor for conversion from \c INVALID.
+        ///
+        /// Constructor for conversion from \c INVALID.
+        /// It initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        BlueNode(Invalid) {}
+
+        /// \brief Constructor for conversion from a node.
+        ///
+        /// Constructor for conversion from a node. The conversion can
+        /// be invalid, since the Node can be member of the red
+        /// set.
+        BlueNode(const Node&) {}
+      };
+
+      /// \brief Gives back %true for red nodes.
+      ///
+      /// Gives back %true for red nodes.
+      bool red(const Node&) const { return true; }
+
+      /// \brief Gives back %true for blue nodes.
+      ///
+      /// Gives back %true for blue nodes.
+      bool blue(const Node&) const { return true; }
+
+      /// \brief Gives back the red end node of the edge.
+      /// 
+      /// Gives back the red end node of the edge.
+      RedNode redNode(const Edge&) const { return RedNode(); }
+
+      /// \brief Gives back the blue end node of the edge.
+      /// 
+      /// Gives back the blue end node of the edge.
+      BlueNode blueNode(const Edge&) const { return BlueNode(); }
+
+      /// \brief Converts the node to red node object.
+      ///
+      /// This function converts unsafely the node to red node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
+
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This function converts unsafely the node to blue node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
+
+      /// \brief Converts the node to red node object.
+      ///
+      /// This function converts safely the node to red node
+      /// object. If the node is not from the red partition, then it
+      /// returns INVALID.
+      RedNode asRedNode(const Node&) const { return RedNode(); }
+
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This function converts unsafely the node to blue node
+      /// object. If the node is not from the blue partition, then it
+      /// returns INVALID.
+      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
+
+      template <typename _BpGraph>
+      struct Constraints {
+        typedef typename _BpGraph::Node Node;
+        typedef typename _BpGraph::RedNode RedNode;
+        typedef typename _BpGraph::BlueNode BlueNode;
+        typedef typename _BpGraph::Arc Arc;
+        typedef typename _BpGraph::Edge Edge;
+
+        void constraints() {
+          checkConcept<BaseGraphComponent, _BpGraph>();
+          checkConcept<GraphItem<'n'>, RedNode>();
+          checkConcept<GraphItem<'n'>, BlueNode>();
+          {
+            Node n;
+            RedNode rn;
+            BlueNode bn;
+            Node rnan = rn;
+            Node bnan = bn;
+            Edge e;
+            bool b;
+            b = bpgraph.red(rnan);
+            b = bpgraph.blue(bnan);
+            rn = bpgraph.redNode(e);
+            bn = bpgraph.blueNode(e);
+            rn = bpgraph.asRedNodeUnsafe(rnan);
+            bn = bpgraph.asBlueNodeUnsafe(bnan);
+            rn = bpgraph.asRedNode(rnan);
+            bn = bpgraph.asBlueNode(bnan);
+            ignore_unused_variable_warning(b);
+          }
+        }
+
+        const _BpGraph& bpgraph;
+      };
+
+    };
+
     /// \brief Skeleton class for \e idable directed graphs.
     ///
@@ -432 +598 @@
     };
 
+    /// \brief Skeleton class for \e idable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of \e idable undirected
+    /// bipartite graphs. It extends \ref IDableGraphComponent with
+    /// the core ID functions of undirected bipartite graphs. Beside
+    /// the regular node ids, this class also provides ids within the
+    /// the red and blue sets of the nodes. This concept is part of
+    /// the BpGraph concept.
+    template <typename BAS = BaseBpGraphComponent>
+    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
+      typedef IDableGraphComponent<BAS> Parent;
+      typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+
+      using Parent::id;
+
+      /// \brief Return a unique integer id for the given node in the red set.
+      ///
+      /// Return a unique integer id for the given node in the red set.
+      int id(const RedNode&) const { return -1; }
+
+      /// \brief Return a unique integer id for the given node in the blue set.
+      ///
+      /// Return a unique integer id for the given node in the blue set.
+      int id(const BlueNode&) const { return -1; }
+
+      /// \brief Return an integer greater or equal to the maximum
+      /// node id in the red set.
+      ///
+      /// Return an integer greater or equal to the maximum
+      /// node id in the red set.
+      int maxRedId() const { return -1; }
+
+      /// \brief Return an integer greater or equal to the maximum
+      /// node id in the blue set.
+      ///
+      /// Return an integer greater or equal to the maximum
+      /// node id in the blue set.
+      int maxBlueId() const { return -1; }
+
+      template <typename _BpGraph>
+      struct Constraints {
+
+        void constraints() {
+          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
+          typename _BpGraph::Node node;
+          typename _BpGraph::RedNode red;
+          typename _BpGraph::BlueNode blue;
+          int rid = bpgraph.id(red);
+          int bid = bpgraph.id(blue);
+          rid = bpgraph.maxRedId();
+          bid = bpgraph.maxBlueId();
+          ignore_unused_variable_warning(rid);
+          ignore_unused_variable_warning(bid);
+        }
+
+        const _BpGraph& bpgraph;
+      };
+    };
+
     /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
     ///
@@ -646 +876 @@
       void next(Arc&) const {}
 
-      /// \brief Return the first arc incomming to the given node.
-      ///
-      /// This function gives back the first arc incomming to the
+      /// \brief Return the first arc incoming to the given node.
+      ///
+      /// This function gives back the first arc incoming to the
       /// given node.
       void firstIn(Arc&, const Node&) const {}
 
-      /// \brief Return the next arc incomming to the given node.
-      ///
-      /// This function gives back the next arc incomming to the
+      /// \brief Return the next arc incoming to the given node.
+      ///
+      /// This function gives back the next arc incoming to the
       /// given node.
       void nextIn(Arc&) const {}
@@ -905 +1135 @@
     };
 
+    /// \brief Skeleton class for iterable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of iterable undirected
+    /// bipartite graphs. It extends \ref IterableGraphComponent with
+    /// the core iterable interface of undirected bipartite graphs.
+    /// This concept is part of the BpGraph concept.
+    template <typename BAS = BaseBpGraphComponent>
+    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+      typedef typename Base::Arc Arc;
+      typedef typename Base::Edge Edge;
+      
+      typedef IterableBpGraphComponent BpGraph;
+
+      using IterableGraphComponent<BAS>::first;
+      using IterableGraphComponent<BAS>::next;
+
+      /// \name Base Iteration
+      ///
+      /// This interface provides functions for iteration on red and blue nodes.
+      ///
+      /// @{
+
+      /// \brief Return the first red node.
+      ///
+      /// This function gives back the first red node in the iteration order.
+      void first(RedNode&) const {}
+
+      /// \brief Return the next red node.
+      ///
+      /// This function gives back the next red node in the iteration order.
+      void next(RedNode&) const {}
+
+      /// \brief Return the first blue node.
+      ///
+      /// This function gives back the first blue node in the iteration order.
+      void first(BlueNode&) const {}
+
+      /// \brief Return the next blue node.
+      ///
+      /// This function gives back the next blue node in the iteration order.
+      void next(BlueNode&) const {}
+
+
+      /// @}
+
+      /// \name Class Based Iteration
+      ///
+      /// This interface provides iterator classes for red and blue nodes.
+      ///
+      /// @{
+
+      /// \brief This iterator goes through each red node.
+      ///
+      /// This iterator goes through each red node.
+      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
+
+      /// \brief This iterator goes through each blue node.
+      ///
+      /// This iterator goes through each blue node.
+      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
+
+      /// @}
+
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
+
+          typename _BpGraph::RedNode rn(INVALID);
+          bpgraph.first(rn);
+          bpgraph.next(rn); 
+          typename _BpGraph::BlueNode bn(INVALID);
+          bpgraph.first(bn);
+          bpgraph.next(bn);
+
+          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
+            typename _BpGraph::RedNodeIt>();
+          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
+            typename _BpGraph::BlueNodeIt>();
+        }
+
+        const _BpGraph& bpgraph;
+      };
+    };
+
     /// \brief Skeleton class for alterable directed graphs.
     ///
@@ -930 +1251 @@
       ArcNotifier;
 
+      mutable NodeNotifier node_notifier;
+      mutable ArcNotifier arc_notifier;
+
       /// \brief Return the node alteration notifier.
       ///
       /// This function gives back the node alteration notifier.
       NodeNotifier& notifier(Node) const {
-         return NodeNotifier();
+        return node_notifier;
       }
 
@@ -941 +1265 @@
       /// This function gives back the arc alteration notifier.
       ArcNotifier& notifier(Arc) const {
-        return ArcNotifier();
+        return arc_notifier;
       }
 
@@ -977 +1301 @@
 
       typedef BAS Base;
+      typedef AlterableDigraphComponent<Base> Parent;
       typedef typename Base::Edge Edge;
 
@@ -984 +1309 @@
       EdgeNotifier;
 
+      mutable EdgeNotifier edge_notifier;
+
+      using Parent::notifier;
+
       /// \brief Return the edge alteration notifier.
       ///
       /// This function gives back the edge alteration notifier.
       EdgeNotifier& notifier(Edge) const {
-        return EdgeNotifier();
+        return edge_notifier;
       }
 
@@ -1002 +1331 @@
         const _Graph& graph;
         Constraints() {}
+      };
+    };
+
+    /// \brief Skeleton class for alterable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of alterable undirected
+    /// bipartite graphs. It extends \ref AlterableGraphComponent with
+    /// the alteration notifier interface of bipartite graphs. It
+    /// implements an observer-notifier pattern for the red and blue
+    /// nodes. More obsevers can be registered into the notifier and
+    /// whenever an alteration occured in the graph all the observers
+    /// will be notified about it.
+    template <typename BAS = BaseBpGraphComponent>
+    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
+      typedef AlterableGraphComponent<Base> Parent;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+
+
+      /// Red node alteration notifier class.
+      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
+      RedNodeNotifier;
+
+      /// Blue node alteration notifier class.
+      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
+      BlueNodeNotifier;
+
+      mutable RedNodeNotifier red_node_notifier;
+      mutable BlueNodeNotifier blue_node_notifier;
+
+      using Parent::notifier;
+
+      /// \brief Return the red node alteration notifier.
+      ///
+      /// This function gives back the red node alteration notifier.
+      RedNodeNotifier& notifier(RedNode) const {
+        return red_node_notifier;
+      }
+
+      /// \brief Return the blue node alteration notifier.
+      ///
+      /// This function gives back the blue node alteration notifier.
+      BlueNodeNotifier& notifier(BlueNode) const {
+        return blue_node_notifier;
+      }
+
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
+          typename _BpGraph::RedNodeNotifier& rnn
+            = bpgraph.notifier(typename _BpGraph::RedNode());
+          typename _BpGraph::BlueNodeNotifier& bnn
+            = bpgraph.notifier(typename _BpGraph::BlueNode());
+          ignore_unused_variable_warning(rnn);
+          ignore_unused_variable_warning(bnn);
+        }
+
+        const _BpGraph& bpgraph;
       };
     };
@@ -1308 +1699 @@
     };
 
+    /// \brief Skeleton class for mappable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of mappable undirected
+    /// bipartite graphs.  It extends \ref MappableGraphComponent with
+    /// the standard graph map class for red and blue nodes (\c
+    /// RedNodeMap and BlueNodeMap). This concept is part of the
+    /// BpGraph concept.
+    template <typename BAS = BaseBpGraphComponent>
+    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
+    public:
+
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+
+      typedef MappableBpGraphComponent BpGraph;
+
+      /// \brief Standard graph map for the red nodes.
+      ///
+      /// Standard graph map for the red nodes.
+      /// It conforms to the ReferenceMap concept.
+      template <typename V>
+      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
+        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
+
+      public:
+        /// \brief Construct a new map.
+        ///
+        /// Construct a new map for the graph.
+        explicit RedNodeMap(const MappableBpGraphComponent& graph)
+          : Parent(graph) {}
+
+        /// \brief Construct a new map with default value.
+        ///
+        /// Construct a new map for the graph and initalize the values.
+        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
+          : Parent(graph, value) {}
+
+      private:
+        /// \brief Copy constructor.
+        ///
+        /// Copy Constructor.
+        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
+
+        /// \brief Assignment operator.
+        ///
+        /// Assignment operator.
+        template <typename CMap>
+        RedNodeMap& operator=(const CMap&) {
+          checkConcept<ReadMap<Node, V>, CMap>();
+          return *this;
+        }
+
+      };
+
+      /// \brief Standard graph map for the blue nodes.
+      ///
+      /// Standard graph map for the blue nodes.
+      /// It conforms to the ReferenceMap concept.
+      template <typename V>
+      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
+        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
+
+      public:
+        /// \brief Construct a new map.
+        ///
+        /// Construct a new map for the graph.
+        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
+          : Parent(graph) {}
+
+        /// \brief Construct a new map with default value.
+        ///
+        /// Construct a new map for the graph and initalize the values.
+        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
+          : Parent(graph, value) {}
+
+      private:
+        /// \brief Copy constructor.
+        ///
+        /// Copy Constructor.
+        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
+
+        /// \brief Assignment operator.
+        ///
+        /// Assignment operator.
+        template <typename CMap>
+        BlueNodeMap& operator=(const CMap&) {
+          checkConcept<ReadMap<Node, V>, CMap>();
+          return *this;
+        }
+
+      };
+
+
+      template <typename _BpGraph>
+      struct Constraints {
+
+        struct Dummy {
+          int value;
+          Dummy() : value(0) {}
+          Dummy(int _v) : value(_v) {}
+        };
+
+        void constraints() {
+          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
+
+          { // int map test
+            typedef typename _BpGraph::template RedNodeMap<int>
+              IntRedNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
+              IntRedNodeMap >();
+          } { // bool map test
+            typedef typename _BpGraph::template RedNodeMap<bool>
+              BoolRedNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
+              BoolRedNodeMap >();
+          } { // Dummy map test
+            typedef typename _BpGraph::template RedNodeMap<Dummy>
+              DummyRedNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
+              DummyRedNodeMap >();
+          }
+
+          { // int map test
+            typedef typename _BpGraph::template BlueNodeMap<int>
+              IntBlueNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
+              IntBlueNodeMap >();
+          } { // bool map test
+            typedef typename _BpGraph::template BlueNodeMap<bool>
+              BoolBlueNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
+              BoolBlueNodeMap >();
+          } { // Dummy map test
+            typedef typename _BpGraph::template BlueNodeMap<Dummy>
+              DummyBlueNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
+              DummyBlueNodeMap >();
+          }
+        }
+
+        const _BpGraph& bpgraph;
+      };
+    };
+
     /// \brief Skeleton class for extendable directed graphs.
     ///
@@ -1398 +1933 @@
     };
 
+    /// \brief Skeleton class for extendable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of extendable undirected
+    /// bipartite graphs. It extends \ref BaseGraphComponent with
+    /// functions for adding nodes and edges to the graph. This
+    /// concept requires \ref AlterableBpGraphComponent.
+    template <typename BAS = BaseBpGraphComponent>
+    class ExtendableBpGraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+      typedef typename Base::Edge Edge;
+
+      /// \brief Add a new red node to the digraph.
+      ///
+      /// This function adds a red new node to the digraph.
+      RedNode addRedNode() {
+        return INVALID;
+      }
+
+      /// \brief Add a new blue node to the digraph.
+      ///
+      /// This function adds a blue new node to the digraph.
+      BlueNode addBlueNode() {
+        return INVALID;
+      }
+
+      /// \brief Add a new edge connecting the given two nodes.
+      ///
+      /// This function adds a new edge connecting the given two nodes
+      /// of the graph. The first node has to be a red node, and the
+      /// second one a blue node.
+      Edge addEdge(const RedNode&, const BlueNode&) {
+        return INVALID;
+      }
+      Edge addEdge(const BlueNode&, const RedNode&) {
+        return INVALID;
+      }
+
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<Base, _BpGraph>();
+          typename _BpGraph::RedNode red_node;
+          typename _BpGraph::BlueNode blue_node;
+          red_node = bpgraph.addRedNode();
+          blue_node = bpgraph.addBlueNode();
+          typename _BpGraph::Edge edge;
+          edge = bpgraph.addEdge(red_node, blue_node);
+          edge = bpgraph.addEdge(blue_node, red_node);
+        }
+
+        _BpGraph& bpgraph;
+      };
+    };
+
     /// \brief Skeleton class for erasable directed graphs.
     ///
@@ -1478 +2072 @@
     };
 
+    /// \brief Skeleton class for erasable undirected graphs.
+    ///
+    /// This class describes the interface of erasable undirected
+    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
+    /// functions for removing nodes and edges from the graph. This
+    /// concept requires \ref AlterableBpGraphComponent.
+    template <typename BAS = BaseBpGraphComponent>
+    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
+
     /// \brief Skeleton class for clearable directed graphs.
     ///
@@ -1514 +2117 @@
     /// This concept requires \ref AlterableGraphComponent.
     template <typename BAS = BaseGraphComponent>
-    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
-    public:
-
-      typedef BAS Base;
-
-      /// \brief Erase all nodes and edges from the graph.
-      ///
-      /// This function erases all nodes and edges from the graph.
-      void clear() {}
-
-      template <typename _Graph>
-      struct Constraints {
-        void constraints() {
-          checkConcept<Base, _Graph>();
-          graph.clear();
-        }
-
-        _Graph& graph;
-        Constraints() {}
-      };
-    };
+    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
+
+    /// \brief Skeleton class for clearable undirected biparite graphs.
+    ///
+    /// This class describes the interface of clearable undirected
+    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
+    /// function for clearing the graph.  This concept requires \ref
+    /// AlterableBpGraphComponent.
+    template <typename BAS = BaseBpGraphComponent>
+    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
 
   }

lemon/core.h

@@ -160 +160 @@
   typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
 
+  ///Create convenience typedefs for the bipartite graph types and iterators
+
+  ///This \c \#define creates the same convenient type definitions as
+  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
+  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
+  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
+  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
+  ///
+  ///\note If the graph type is a dependent type, ie. the graph type depend
+  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
+  ///macro.
+#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
+  GRAPH_TYPEDEFS(BpGraph);                                              \
+  typedef BpGraph::RedNode RedNode;                                     \
+  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
+  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
+  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
+  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
+  typedef BpGraph::BlueNode BlueNode;                                   \
+  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
+  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
+  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
+  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
+
+  ///Create convenience typedefs for the bipartite graph types and iterators
+
+  ///\see BPGRAPH_TYPEDEFS
+  ///
+  ///\note Use this macro, if the graph type is a dependent type,
+  ///ie. the graph type depend on a template parameter.
+#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
+  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
+  typedef typename BpGraph::RedNode RedNode;                                \
+  typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
+  typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
+  typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
+  typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
+  typedef typename BpGraph::BlueNode BlueNode;                              \
+  typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
+  typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
+  typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
+  typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
+
   /// \brief Function to count the items in a graph.
   ///
@@ -211 +254 @@
   }
 
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct CountRedNodesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::RedNode>(g);
+      }
+    };
+
+    template <typename Graph>
+    struct CountRedNodesSelector<
+      Graph, typename 
+      enable_if<typename Graph::NodeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.redNum();
+      }
+    };    
+  }
+
+  /// \brief Function to count the red nodes in the graph.
+  ///
+  /// This function counts the red nodes in the graph.
+  /// The complexity of the function is O(n) but for some
+  /// graph structures it is specialized to run in O(1).
+  ///
+  /// If the graph contains a \e redNum() member function and a 
+  /// \e NodeNumTag tag then this function calls directly the member
+  /// function to query the cardinality of the node set.
+  template <typename Graph>
+  inline int countRedNodes(const Graph& g) {
+    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
+  }
+
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct CountBlueNodesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::BlueNode>(g);
+      }
+    };
+
+    template <typename Graph>
+    struct CountBlueNodesSelector<
+      Graph, typename 
+      enable_if<typename Graph::NodeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.blueNum();
+      }
+    };    
+  }
+
+  /// \brief Function to count the blue nodes in the graph.
+  ///
+  /// This function counts the blue nodes in the graph.
+  /// The complexity of the function is O(n) but for some
+  /// graph structures it is specialized to run in O(1).
+  ///
+  /// If the graph contains a \e blueNum() member function and a 
+  /// \e NodeNumTag tag then this function calls directly the member
+  /// function to query the cardinality of the node set.
+  template <typename Graph>
+  inline int countBlueNodes(const Graph& g) {
+    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
+  }
+
   // Arc counting:
 
@@ -452 +563 @@
       template <typename From, typename NodeRefMap, typename EdgeRefMap>
       static void copy(const From& from, Graph &to,
-                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+                       NodeRefMap& nodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
         to.build(from, nodeRefMap, edgeRefMap);
       }
     };
 
+    template <typename BpGraph, typename Enable = void>
+    struct BpGraphCopySelector {
+      template <typename From, typename RedNodeRefMap,
+                typename BlueNodeRefMap, typename EdgeRefMap>
+      static void copy(const From& from, BpGraph &to,
+                       RedNodeRefMap& redNodeRefMap,
+                       BlueNodeRefMap& blueNodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
+        to.clear();
+        for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
+          redNodeRefMap[it] = to.addRedNode();
+        }
+        for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
+          blueNodeRefMap[it] = to.addBlueNode();
+        }
+        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
+          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
+                                      blueNodeRefMap[from.blueNode(it)]);
+        }
+      }
+    };
+
+    template <typename BpGraph>
+    struct BpGraphCopySelector<
+      BpGraph,
+      typename enable_if<typename BpGraph::BuildTag, void>::type>
+    {
+      template <typename From, typename RedNodeRefMap,
+                typename BlueNodeRefMap, typename EdgeRefMap>
+      static void copy(const From& from, BpGraph &to,
+                       RedNodeRefMap& redNodeRefMap,
+                       BlueNodeRefMap& blueNodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
+        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
+      }
+    };
+
   }
+
+  /// \brief Check whether a graph is undirected.
+  ///
+  /// This function returns \c true if the given graph is undirected.
+#ifdef DOXYGEN
+  template <typename GR>
+  bool undirected(const GR& g) { return false; }
+#else
+  template <typename GR>
+  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
+  undirected(const GR&) {
+    return true;
+  }
+  template <typename GR>
+  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
+  undirected(const GR&) {
+    return false;
+  }
+#endif
 
   /// \brief Class to copy a digraph.
@@ -982 +1150 @@
   graphCopy(const From& from, To& to) {
     return GraphCopy<From, To>(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<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
+  ///  // Create references for the nodes
+  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
+  ///  cg.nodeRef(nr);
+  ///  // Create cross references (inverse) for the edges
+  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
+  ///  cg.edgeCrossRef(ecr);
+  ///  // Copy a red node map
+  ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
+  ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
+  ///  cg.redNodeMap(ormap, nrmap);
+  ///  // Copy a node
+  ///  OrigBpGraph::Node on;
+  ///  NewBpGraph::Node nn;
+  ///  cg.node(on, nn);
+  ///  // Execute copying
+  ///  cg.run();
+  ///\endcode
+  template <typename From, typename To>
+  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::RedNode TRedNode;
+    typedef typename To::BlueNode TBlueNode;
+    typedef typename To::Arc TArc;
+    typedef typename To::Edge TEdge;
+
+    typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
+    typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
+    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
+
+    struct NodeRefMap {
+      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
+                 const BlueNodeRefMap& blue_node_ref)
+        : _from(from), _red_node_ref(red_node_ref),
+          _blue_node_ref(blue_node_ref) {}
+
+      typedef typename From::Node Key;
+      typedef typename To::Node Value;
+
+      Value operator[](const Key& key) const {
+        if (_from.red(key)) {
+          return _red_node_ref[_from.asRedNodeUnsafe(key)];
+        } else {
+          return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
+        }
+      }
+
+      const From& _from;
+      const RedNodeRefMap& _red_node_ref;
+      const BlueNodeRefMap& _blue_node_ref;
+    };
+
+    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 <typename NodeRef>
+    BpGraphCopy& nodeRef(NodeRef& map) {
+      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
+                           NodeRefMap, NodeRef>(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 <typename NodeCrossRef>
+    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
+      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
+                           NodeRefMap, NodeCrossRef>(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 <typename FromMap, typename ToMap>
+    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
+      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
+                           NodeRefMap, FromMap, ToMap>(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<From, Node,
+                           NodeRefMap, TNode>(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 <typename RedRef>
+    BpGraphCopy& redRef(RedRef& map) {
+      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
+                          RedNodeRefMap, RedRef>(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 <typename RedCrossRef>
+    BpGraphCopy& redCrossRef(RedCrossRef& map) {
+      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
+                          RedNodeRefMap, RedCrossRef>(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 <typename FromMap, typename ToMap>
+    BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
+      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
+                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given red node.
+    ///
+    /// This function makes a copy of the given red node.
+    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
+      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
+                          RedNodeRefMap, TRedNode>(node, tnode));
+      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 <typename BlueRef>
+    BpGraphCopy& blueRef(BlueRef& map) {
+      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
+                           BlueNodeRefMap, BlueRef>(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 <typename BlueCrossRef>
+    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
+      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
+                           BlueNodeRefMap, BlueCrossRef>(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 <typename FromMap, typename ToMap>
+    BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
+      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
+                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+
+    /// \brief Make a copy of the given blue node.
+    ///
+    /// This function makes a copy of the given blue node.
+    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
+      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
+                           BlueNodeRefMap, TBlueNode>(node, tnode));
+      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 <typename ArcRef>
+    BpGraphCopy& arcRef(ArcRef& map) {
+      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
+                          ArcRefMap, ArcRef>(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 <typename ArcCrossRef>
+    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
+      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
+                          ArcRefMap, ArcCrossRef>(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 <typename FromMap, typename ToMap>
+    BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
+      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
+                          ArcRefMap, FromMap, ToMap>(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<From, Arc,
+                          ArcRefMap, TArc>(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 <typename EdgeRef>
+    BpGraphCopy& edgeRef(EdgeRef& map) {
+      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
+                           EdgeRefMap, EdgeRef>(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 <typename EdgeCrossRef>
+    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
+      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
+                           Edge, EdgeRefMap, EdgeCrossRef>(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 <typename FromMap, typename ToMap>
+    BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
+      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
+                           EdgeRefMap, FromMap, ToMap>(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<From, Edge,
+                           EdgeRefMap, TEdge>(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() {
+      RedNodeRefMap redNodeRefMap(_from);
+      BlueNodeRefMap blueNodeRefMap(_from);
+      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
+      EdgeRefMap edgeRefMap(_from);
+      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
+      _core_bits::BpGraphCopySelector<To>::
+        copy(_from, _to, redNodeRefMap, blueNodeRefMap, 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, redNodeRefMap);
+      }
+      for (int i = 0; i < int(_blue_maps.size()); ++i) {
+        _blue_maps[i]->copy(_from, blueNodeRefMap);
+      }
+      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<From, Node, NodeRefMap>* >
+      _node_maps;
+
+    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
+      _red_maps;
+
+    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
+      _blue_maps;
+
+    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
+      _arc_maps;
+
+    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
+      _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 <typename From, typename To>
+  BpGraphCopy<From, To>
+  bpGraphCopy(const From& from, To& to) {
+    return BpGraphCopy<From, To>(from, to);
   }
 
@@ -1250 +1866 @@
     /// The Digraph type
     typedef GR Digraph;
-
+    
   protected:
 

test/dfs_test.cc

@@ -68 +68 @@
   int l, i;
   bool b;
-  ignore_unused_variable_warning(l,i,b);
+  ::lemon::ignore_unused_variable_warning(l,i,b);
 
   DType::DistMap d(G);
@@ -154 +154 @@
   Digraph g;
   bool b;
-  ignore_unused_variable_warning(b);
+  ::lemon::ignore_unused_variable_warning(b);
 
   dfs(g).run(Node());

test/maps_test.cc

@@ -104 +104 @@
     NullMap<A,B> map1;
     NullMap<A,B> map2 = map1;
-    ignore_unused_variable_warning(map2);
+    ::lemon::ignore_unused_variable_warning(map2);
     map1 = nullMap<A,B>();
   }
@@ -115 +115 @@
     ConstMap<A,B> map2 = B();
     ConstMap<A,B> map3 = map1;
-    ignore_unused_variable_warning(map2,map3);
+    ::lemon::ignore_unused_variable_warning(map2,map3);
 
     map1 = constMap<A>(B());
@@ -122 +122 @@
     ConstMap<A,C> map4(C(1));
     ConstMap<A,C> map5 = map4;
-    ignore_unused_variable_warning(map5);
+    ::lemon::ignore_unused_variable_warning(map5);
 
     map4 = constMap<A>(C(2));
@@ -144 +144 @@
     IdentityMap<A> map1;
     IdentityMap<A> map2 = map1;
-    ignore_unused_variable_warning(map2);
+    ::lemon::ignore_unused_variable_warning(map2);
 
     map1 = identityMap<A>();
@@ -205 +205 @@
     checkConcept<ReadMap<B,double>, CompMap>();
     CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
-    ignore_unused_variable_warning(map1);
+    ::lemon::ignore_unused_variable_warning(map1);
     CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
-    ignore_unused_variable_warning(map2);
+    ::lemon::ignore_unused_variable_warning(map2);
 
     SparseMap<double, bool> m1(false); m1[3.14] = true;
@@ -220 +220 @@
     checkConcept<ReadMap<A,double>, CombMap>();
     CombMap map1 = CombMap(DoubleMap(), DoubleMap());
-    ignore_unused_variable_warning(map1);
+    ::lemon::ignore_unused_variable_warning(map1);
     CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
-    ignore_unused_variable_warning(map2);
+    ::lemon::ignore_unused_variable_warning(map2);
 
     check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
@@ -234 +234 @@
     FunctorToMap<F> map1;
     FunctorToMap<F> map2 = FunctorToMap<F>(F());
-    ignore_unused_variable_warning(map2);
+    ::lemon::ignore_unused_variable_warning(map2);
 
     B b = functorToMap(F())[A()];
-    ignore_unused_variable_warning(b);
+    ::lemon::ignore_unused_variable_warning(b);
 
     checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
     MapToFunctor<ReadMap<A,B> > map =
       MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
-    ignore_unused_variable_warning(map);
+    ::lemon::ignore_unused_variable_warning(map);
 
     check(functorToMap(&func)[A()] == 3,
@@ -260 +260 @@
       ConvertMap<ReadMap<double, int>, double> >();
     ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
-    ignore_unused_variable_warning(map1);
+    ::lemon::ignore_unused_variable_warning(map1);
     ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
-    ignore_unused_variable_warning(map2);
+    ::lemon::ignore_unused_variable_warning(map2);
 
   }

test/maps_test.cc

@@ -536 +536 @@
 
     typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
-    Digraph dgr(gr, constMap<Edge, bool>(true));
+    ConstMap<Edge, bool> true_edge_map(true);
+    Digraph dgr(gr, true_edge_map);
     OutDegMap<Digraph> odm(dgr);
     InDegMap<Digraph> idm(dgr);