Index: lemon/concept/graph_components.h
===================================================================
--- lemon/concept/graph_components.h	(revision 2181)
+++ lemon/concept/graph_components.h	(revision 2231)
@@ -219,4 +219,9 @@
         /// be convertible to the represented undirected edge. 
         UEdge(const Edge&) {}
+        /// \brief Assign edge to undirected edge.
+        ///
+        /// Besides the core graph item functionality each edge should
+        /// be convertible to the represented undirected edge. 
+        UEdge& operator=(const Edge&) { return *this; }
       };
 
@@ -291,171 +296,147 @@
     };
 
-    /// \brief An empty iterable base graph class.
+    /// \brief An empty base bipartite undirected graph class.
     ///  
-    /// This class provides beside the core graph features
-    /// core iterable interface for the graph structure.
-    /// Most of the base graphs should be conform to this concept.
-    template <typename _Base = BaseGraphComponent>
-    class BaseIterableGraphComponent : public _Base {
-    public:
-
-      typedef _Base Base; 
-      typedef typename Base::Node Node;
-      typedef typename Base::Edge Edge;
-
-      /// \brief Gives back the first node in the iterating order.
-      ///      
-      /// Gives back the first node in the iterating order.
-      ///     
-      void first(Node&) const {}
-
-      /// \brief Gives back the next node in the iterating order.
-      ///
-      /// Gives back the next node in the iterating order.
-      ///     
-      void next(Node&) const {}
-
-      /// \brief Gives back the first edge in the iterating order.
-      ///
-      /// Gives back the first edge in the iterating order.
-      ///     
-      void first(Edge&) const {}
-
-      /// \brief Gives back the next edge in the iterating order.
-      ///
-      /// Gives back the next edge in the iterating order.
-      ///     
-      void next(Edge&) const {}
-
-
-      /// \brief Gives back the first of the edges point to the given
-      /// node.
-      ///
-      /// Gives back the first of the edges point to the given node.
-      ///     
-      void firstIn(Edge&, const Node&) const {}
-
-      /// \brief Gives back the next of the edges points to the given
-      /// node.
-      ///
-      /// Gives back the next of the edges points to the given node.
-      ///
-      void nextIn(Edge&) const {}
-
-      /// \brief Gives back the first of the edges start from the
-      /// given node.
-      ///      
-      /// Gives back the first of the edges start from the given node.
-      ///     
-      void firstOut(Edge&, const Node&) const {}
-
-      /// \brief Gives back the next of the edges start from the given
-      /// node.
-      ///
-      /// Gives back the next of the edges start from the given node.
-      ///     
-      void nextOut(Edge&) const {}
-
-
+    /// This class provides the minimal set of features needed for an
+    /// bipartite undirected graph structure. All bipartite undirected
+    /// graph concepts have to be conform to this base graph. It just
+    /// provides types for nodes, A-nodes, B-nodes, edges and
+    /// undirected edges and functions to get the source and the
+    /// target of the edges and undirected edges, conversion from
+    /// edges to undirected edges and function to get both direction
+    /// of the undirected edges.
+    class BaseBpUGraphComponent : public BaseUGraphComponent {
+    public:
+      typedef BaseUGraphComponent::Node Node;
+      typedef BaseUGraphComponent::Edge Edge;
+      typedef BaseUGraphComponent::UEdge UEdge;
+
+      /// \brief Helper class for A-nodes.
+      ///
+      /// This class is just a helper class for A-nodes, it is not
+      /// suggested to use it directly. It can be converted easily to
+      /// node and vice versa. The usage of this class is limited
+      /// to use just as template parameters for special map types. 
+      class ANode : public Node {
+      public:
+        typedef Node Parent;
+
+        /// \brief 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.
+        ANode() {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        ///
+        ANode(const ANode &) : Parent() {}
+        /// \brief Invalid constructor \& conversion.
+        ///
+        /// This constructor initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        ANode(Invalid) {}
+        /// \brief Converter from node to A-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented A-node if it is it possible. 
+        ANode(const Node&) {}
+        /// \brief Assign node to A-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented A-node if it is it possible. 
+        ANode& operator=(const Node&) { return *this; }
+      };
+
+      /// \brief Helper class for B-nodes.
+      ///
+      /// This class is just a helper class for B-nodes, it is not
+      /// suggested to use it directly. It can be converted easily to
+      /// node and vice versa. The usage of this class is limited
+      /// to use just as template parameters for special map types. 
+      class BNode : public Node {
+      public:
+        typedef Node Parent;
+
+        /// \brief 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.
+        BNode() {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        ///
+        BNode(const BNode &) : Parent() {}
+        /// \brief Invalid constructor \& conversion.
+        ///
+        /// This constructor initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        BNode(Invalid) {}
+        /// \brief Converter from node to B-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented B-node if it is it possible. 
+        BNode(const Node&) {}
+        /// \brief Assign node to B-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented B-node if it is it possible. 
+        BNode& operator=(const Node&) { return *this; }
+      };
+      
+      /// \brief Gives back %true when the node is A-node.
+      ///
+      /// Gives back %true when the node is A-node.
+      bool aNode(const Node&) const { return false; }
+
+      /// \brief Gives back %true when the node is B-node.
+      ///
+      /// Gives back %true when the node is B-node.
+      bool bNode(const Node&) const { return false; }
+
+      /// \brief Gives back the A-node of the undirected edge.
+      ///
+      /// Gives back the A-node of the undirected edge.
+      Node aNode(const UEdge&) const { return INVALID; }
+
+      /// \brief Gives back the B-node of the undirected edge.
+      ///
+      /// Gives back the B-node of the undirected edge.
+      Node bNode(const UEdge&) const { return INVALID; }
+      
       template <typename _Graph>
       struct Constraints {
+	typedef typename _Graph::Node Node;
+	typedef typename _Graph::ANode ANode;
+	typedef typename _Graph::BNode BNode;
+	typedef typename _Graph::Edge Edge;
+	typedef typename _Graph::UEdge UEdge;
       
 	void constraints() {
-	  checkConcept< BaseGraphComponent, _Graph >();
-	  typename _Graph::Node node(INVALID);      
-	  typename _Graph::Edge edge(INVALID);
+          checkConcept<BaseUGraphComponent, _Graph>();
+	  checkConcept<GraphItem<'a'>, ANode>();
+	  checkConcept<GraphItem<'b'>, BNode>();
 	  {
-	    graph.first(node);
-	    graph.next(node);
-	  }
-	  {
-	    graph.first(edge);
-	    graph.next(edge);
-	  }
-	  {
-	    graph.firstIn(edge, node);
-	    graph.nextIn(edge);
-	  }
-	  {
-	    graph.firstOut(edge, node);
-	    graph.nextOut(edge);
-	  }
-	}
-
+	    Node n;
+	    UEdge ue(INVALID);
+            bool b;
+	    n = graph.aNode(ue);
+	    n = graph.bNode(ue);
+            b = graph.aNode(n);
+            b = graph.bNode(n);
+            ANode an;
+            an = n; n = an;
+            BNode bn;
+            bn = n; n = bn;            
+            ignore_unused_variable_warning(b);
+	  }      
+	}
+      
 	const _Graph& graph;
       };
-    };
-
-    /// \brief An empty iterable base undirected graph class.
-    ///  
-    /// This class provides beside the core undirceted graph features
-    /// core iterable interface for the undirected graph structure.
-    /// Most of the base undirected graphs should be conform to this
-    /// concept.
-    template <typename _Base = BaseUGraphComponent>
-    class BaseIterableUGraphComponent 
-      : public BaseIterableGraphComponent<_Base> {
-    public:
-
-      typedef _Base Base; 
-      typedef typename Base::UEdge UEdge;
-      typedef typename Base::Node Node;
-
-      using BaseIterableGraphComponent<_Base>::first;
-      using BaseIterableGraphComponent<_Base>::next;
-
-      /// \brief Gives back the first undirected edge in the iterating
-      /// order.
-      ///
-      /// Gives back the first undirected edge in the iterating order.
-      ///     
-      void first(UEdge&) const {}
-
-      /// \brief Gives back the next undirected edge in the iterating
-      /// order.
-      ///
-      /// Gives back the next undirected edge in the iterating order.
-      ///     
-      void next(UEdge&) const {}
-
-
-      /// \brief Gives back the first of the undirected edges from the
-      /// given node.
-      ///
-      /// Gives back the first of the undirected edges from the given
-      /// node. The bool parameter gives back that direction which
-      /// gives a good direction of the uedge so the source of the
-      /// directed edge is the given node.
-      void firstInc(UEdge&, bool&, const Node&) const {}
-
-      /// \brief Gives back the next of the undirected edges from the
-      /// given node.
-      ///
-      /// Gives back the next of the undirected edges from the given
-      /// node. The bool parameter should be used as the \c firstInc()
-      /// use it.
-      void nextInc(UEdge&, bool&) const {}
-
-      template <typename _Graph>
-      struct Constraints {
-      
-	void constraints() {
-	  checkConcept<Base, _Graph >();
-	  checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
-	  typename _Graph::Node node(INVALID);
-	  typename _Graph::UEdge uedge(INVALID);
-          bool dir;
-	  {
-	    graph.first(uedge);
-	    graph.next(uedge);
-	  }
-	  {
-	    graph.firstInc(uedge, dir, node);
-	    graph.nextInc(uedge, dir);
-	  }
-	}
-
-	const _Graph& graph;
-      };
+
     };
 
@@ -518,5 +499,5 @@
 
 	void constraints() {
-	  checkConcept< BaseGraphComponent, _Graph >();
+	  checkConcept<Base, _Graph >();
 	  typename _Graph::Node node;
 	  int nid = graph.id(node);
@@ -591,211 +572,78 @@
     };
 
-    /// \brief An empty extendable base graph class.
-    ///
-    /// This class provides beside the core graph features
-    /// core graph extend interface for the graph structure.
-    /// The most of the base graphs should be conform to this concept.
-    template <typename _Base = BaseGraphComponent>
-    class BaseExtendableGraphComponent : public _Base {
-    public:
-
-      typedef typename _Base::Node Node;
-      typedef typename _Base::Edge Edge;
-
-      /// \brief Adds a new node to the graph.
-      ///
-      /// Adds a new node to the graph.
-      ///
-      Node addNode() {
-	return INVALID;
-      }
-    
-      /// \brief Adds a new edge connects the given two nodes.
-      ///
-      /// Adds a new edge connects the the given two nodes.
-      Edge addEdge(const Node&, const Node&) {
-	return INVALID;
-      }
-
-      template <typename _Graph>
-      struct Constraints {
-	void constraints() {
-	  typename _Graph::Node node_a, node_b;
-	  node_a = graph.addNode();
-	  node_b = graph.addNode();
-	  typename _Graph::Edge edge;
-	  edge = graph.addEdge(node_a, node_b);
-	}
-
-	_Graph& graph;
-      };
-    };
-
-    /// \brief An empty extendable base undirected graph class.
-    ///
-    /// This class provides beside the core undirected graph features
-    /// core undircted graph extend interface for the graph structure.
-    /// The most of the base graphs should be conform to this concept.
-    template <typename _Base = BaseUGraphComponent>
-    class BaseExtendableUGraphComponent : public _Base {
-    public:
-
-      typedef typename _Base::Node Node;
-      typedef typename _Base::UEdge UEdge;
-
-      /// \brief Adds a new node to the graph.
-      ///
-      /// Adds a new node to the graph.
-      ///
-      Node addNode() {
-	return INVALID;
-      }
-    
-      /// \brief Adds a new edge connects the given two nodes.
-      ///
-      /// Adds a new edge connects the the given two nodes.
-      UEdge addEdge(const Node&, const Node&) {
-	return INVALID;
-      }
-
-      template <typename _Graph>
-      struct Constraints {
-	void constraints() {
-	  typename _Graph::Node node_a, node_b;
-	  node_a = graph.addNode();
-	  node_b = graph.addNode();
-	  typename _Graph::UEdge uedge;
-	  uedge = graph.addUEdge(node_a, node_b);
-	}
-
-	_Graph& graph;
-      };
-    };
-
-    /// \brief An empty erasable base graph class.
+    /// \brief An empty idable base bipartite undirected graph class.
     ///  
-    /// This class provides beside the core graph features
-    /// core erase functions for the graph structure.
-    /// The most of the base graphs should be conform to this concept.
-    template <typename _Base = BaseGraphComponent>
-    class BaseErasableGraphComponent : public _Base {
+    /// This class provides beside the core bipartite undirected graph
+    /// features core id functions for the bipartite undirected graph
+    /// structure.  The most of the base undirected graphs should be
+    /// conform to this concept.
+    template <typename _Base = BaseBpUGraphComponent>
+    class IDableBpUGraphComponent : public IDableUGraphComponent<_Base> {
     public:
 
       typedef _Base Base;
       typedef typename Base::Node Node;
-      typedef typename Base::Edge Edge;
-
-      /// \brief Erase a node from the graph.
-      ///
-      /// Erase a node from the graph. This function should not
-      /// erase edges connecting to the Node.
-      void erase(const Node&) {}    
-
-      /// \brief Erase an edge from the graph.
-      ///
-      /// Erase an edge from the graph.
-      ///
-      void erase(const Edge&) {}
+
+      using IDableUGraphComponent<_Base>::id;
+
+      /// \brief Gives back an unique integer id for the ANode. 
+      ///
+      /// Gives back an unique integer id for the ANode. 
+      ///
+      int aNodeId(const Node&) const { return -1;}
+
+      /// \brief Gives back the undirected edge by the unique id.
+      ///
+      /// Gives back the undirected edge by the unique id.  If the
+      /// graph does not contain edge with the given id then the
+      /// result of the function is undetermined.
+      Node nodeFromANodeId(int) const { return INVALID;}
+
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// ANode id.
+      ///
+      /// Gives back an integer greater or equal to the maximum ANode
+      /// id.
+      int maxANodeId() const { return -1;}
+
+      /// \brief Gives back an unique integer id for the BNode. 
+      ///
+      /// Gives back an unique integer id for the BNode. 
+      ///
+      int bNodeId(const Node&) const { return -1;}
+
+      /// \brief Gives back the undirected edge by the unique id.
+      ///
+      /// Gives back the undirected edge by the unique id.  If the
+      /// graph does not contain edge with the given id then the
+      /// result of the function is undetermined.
+      Node nodeFromBNodeId(int) const { return INVALID;}
+
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// BNode id.
+      ///
+      /// Gives back an integer greater or equal to the maximum BNode
+      /// id.
+      int maxBNodeId() const { return -1;}
 
       template <typename _Graph>
       struct Constraints {
-	void constraints() {
-	  typename _Graph::Node node;
-	  graph.erase(node);
-	  typename _Graph::Edge edge;
-	  graph.erase(edge);
-	}
-
-	_Graph& graph;
-      };
-    };
-
-    /// \brief An empty erasable base undirected graph class.
-    ///  
-    /// This class provides beside the core undirected graph features
-    /// core erase functions for the undirceted graph structure.
-    template <typename _Base = BaseUGraphComponent>
-    class BaseErasableUGraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
-      typedef typename Base::Node Node;
-      typedef typename Base::UEdge UEdge;
-
-      /// \brief Erase a node from the graph.
-      ///
-      /// Erase a node from the graph. This function should not
-      /// erase edges connecting to the Node.
-      void erase(const Node&) {}    
-
-      /// \brief Erase an edge from the graph.
-      ///
-      /// Erase an edge from the graph.
-      ///
-      void erase(const UEdge&) {}
-
-      template <typename _Graph>
-      struct Constraints {
-	void constraints() {
-	  typename _Graph::Node node;
-	  graph.erase(node);
-	  typename _Graph::Edge edge;
-	  graph.erase(edge);
-	}
-
-	_Graph& graph;
-      };
-    };
-
-    /// \brief An empty clearable base graph class.
-    ///
-    /// This class provides beside the core graph features
-    /// core clear functions for the graph structure.
-    /// The most of the base graphs should be conform to this concept.
-    template <typename _Base = BaseGraphComponent>
-    class BaseClearableGraphComponent : public _Base {
-    public:
-
-      /// \brief Erase all the nodes and edges from the graph.
-      ///
-      /// Erase all the nodes and edges from the graph.
-      ///
-      void clear() {}    
-
-      template <typename _Graph>
-      struct Constraints {
-	void constraints() {
-	  graph.clear();
-	}
-
-	_Graph graph;
-      };
-    };
-
-    /// \brief An empty clearable base undirected graph class.
-    ///
-    /// This class provides beside the core undirected graph features
-    /// core clear functions for the undirected graph structure.
-    /// The most of the base graphs should be conform to this concept.
-    template <typename _Base = BaseUGraphComponent>
-    class BaseClearableUGraphComponent : public _Base {
-    public:
-
-      /// \brief Erase all the nodes and undirected edges from the graph.
-      ///
-      /// Erase all the nodes and undirected edges from the graph.
-      ///
-      void clear() {}    
-
-      template <typename _Graph>
-      struct Constraints {
-	void constraints() {
-	  graph.clear();
-	}
-
-	_Graph graph;
-      };
-    };
-
+
+	void constraints() {
+	  checkConcept<Base, _Graph >();
+	  checkConcept<IDableGraphComponent<Base>, _Graph >();
+	  typename _Graph::Node node(INVALID);
+	  int id;
+          id = graph.aNodeId(node);
+          id = graph.bNodeId(node);
+          node = graph.nodeFromANodeId(id);
+          node = graph.nodeFromBNodeId(id);
+          id = graph.maxANodeId();
+          id = graph.maxBNodeId();
+	}
+
+	const _Graph& graph;
+      };
+    };
 
     /// \brief Skeleton class for graph NodeIt and EdgeIt
@@ -948,5 +796,5 @@
     /// This class provides beside the core graph features
     /// iterator based iterable interface for the graph structure.
-    /// This concept is part of the GraphConcept.
+    /// This concept is part of the Graph concept.
     template <typename _Base = BaseGraphComponent>
     class IterableGraphComponent : public _Base {
@@ -960,4 +808,70 @@
       typedef IterableGraphComponent Graph;
 
+      /// \name Base iteration
+      /// 
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{  
+
+      /// \brief Gives back the first node in the iterating order.
+      ///      
+      /// Gives back the first node in the iterating order.
+      ///     
+      void first(Node&) const {}
+
+      /// \brief Gives back the next node in the iterating order.
+      ///
+      /// Gives back the next node in the iterating order.
+      ///     
+      void next(Node&) const {}
+
+      /// \brief Gives back the first edge in the iterating order.
+      ///
+      /// Gives back the first edge in the iterating order.
+      ///     
+      void first(Edge&) const {}
+
+      /// \brief Gives back the next edge in the iterating order.
+      ///
+      /// Gives back the next edge in the iterating order.
+      ///     
+      void next(Edge&) const {}
+
+
+      /// \brief Gives back the first of the edges point to the given
+      /// node.
+      ///
+      /// Gives back the first of the edges point to the given node.
+      ///     
+      void firstIn(Edge&, const Node&) const {}
+
+      /// \brief Gives back the next of the edges points to the given
+      /// node.
+      ///
+      /// Gives back the next of the edges points to the given node.
+      ///
+      void nextIn(Edge&) const {}
+
+      /// \brief Gives back the first of the edges start from the
+      /// given node.
+      ///      
+      /// Gives back the first of the edges start from the given node.
+      ///     
+      void firstOut(Edge&, const Node&) const {}
+
+      /// \brief Gives back the next of the edges start from the given
+      /// node.
+      ///
+      /// Gives back the next of the edges start from the given node.
+      ///     
+      void nextOut(Edge&) const {}
+
+      /// @}
+
+      /// \name Class based iteration
+      /// 
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
 
       /// \brief This iterator goes through each node.
@@ -1009,33 +923,51 @@
       Node runningNode(const OutEdgeIt&) const { return INVALID; }
 
-      /// \brief The opposite node on the given edge.
-      ///
-      /// Gives back the opposite on the given edge.
-      /// \todo It should not be here.
-      Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
-
-    
+      /// @}
+
       template <typename _Graph> 
       struct Constraints {
 	void constraints() {
 	  checkConcept<Base, _Graph>();
-	  
-	  checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
-	    typename _Graph::EdgeIt >();
-	  checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
-	    typename _Graph::NodeIt >();
-	  checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 
-            typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
-	  checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 
-            typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
-
-          typename _Graph::Node n;
-          typename _Graph::InEdgeIt ieit(INVALID);
-          typename _Graph::OutEdgeIt oeit(INVALID);
-          n = graph.baseNode(ieit);
-          n = graph.runningNode(ieit);
-          n = graph.baseNode(oeit);
-          n = graph.runningNode(oeit);
-          ignore_unused_variable_warning(n);
+
+          {
+            typename _Graph::Node node(INVALID);      
+            typename _Graph::Edge edge(INVALID);
+            {
+              graph.first(node);
+              graph.next(node);
+            }
+            {
+              graph.first(edge);
+              graph.next(edge);
+            }
+            {
+              graph.firstIn(edge, node);
+              graph.nextIn(edge);
+            }
+            {
+              graph.firstOut(edge, node);
+              graph.nextOut(edge);
+            }
+          }           
+
+          {
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
+              typename _Graph::EdgeIt >();
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+              typename _Graph::NodeIt >();
+            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 
+              typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
+            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 
+              typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
+
+            typename _Graph::Node n;
+            typename _Graph::InEdgeIt ieit(INVALID);
+            typename _Graph::OutEdgeIt oeit(INVALID);
+            n = graph.baseNode(ieit);
+            n = graph.runningNode(ieit);
+            n = graph.baseNode(oeit);
+            n = graph.runningNode(oeit);
+            ignore_unused_variable_warning(n);
+          }
         }
 	
@@ -1049,5 +981,5 @@
     /// This class provides beside the core graph features iterator
     /// based iterable interface for the undirected graph structure.
-    /// This concept is part of the GraphConcept.
+    /// This concept is part of the UGraph concept.
     template <typename _Base = BaseUGraphComponent>
     class IterableUGraphComponent : public IterableGraphComponent<_Base> {
@@ -1061,7 +993,55 @@
     
       typedef IterableUGraphComponent Graph;
+
+      /// \name Base iteration
+      /// 
+      /// This interface provides functions for iteration on graph items
+      /// @{  
+
+      using IterableGraphComponent<_Base>::first;
+      using IterableGraphComponent<_Base>::next;
+
+      /// \brief Gives back the first undirected edge in the iterating
+      /// order.
+      ///
+      /// Gives back the first undirected edge in the iterating order.
+      ///     
+      void first(UEdge&) const {}
+
+      /// \brief Gives back the next undirected edge in the iterating
+      /// order.
+      ///
+      /// Gives back the next undirected edge in the iterating order.
+      ///     
+      void next(UEdge&) const {}
+
+
+      /// \brief Gives back the first of the undirected edges from the
+      /// given node.
+      ///
+      /// Gives back the first of the undirected edges from the given
+      /// node. The bool parameter gives back that direction which
+      /// gives a good direction of the uedge so the source of the
+      /// directed edge is the given node.
+      void firstInc(UEdge&, bool&, const Node&) const {}
+
+      /// \brief Gives back the next of the undirected edges from the
+      /// given node.
+      ///
+      /// Gives back the next of the undirected edges from the given
+      /// node. The bool parameter should be used as the \c firstInc()
+      /// use it.
+      void nextInc(UEdge&, bool&) const {}
+
       using IterableGraphComponent<_Base>::baseNode;
       using IterableGraphComponent<_Base>::runningNode;
 
+      /// @}
+
+      /// \name Class based iteration
+      /// 
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
 
       /// \brief This iterator goes through each node.
@@ -1085,19 +1065,168 @@
       Node runningNode(const IncEdgeIt&) const { return INVALID; }
 
+      /// @}
+
       template <typename _Graph> 
       struct Constraints {
 	void constraints() {
-	  checkConcept<Base, _Graph>();
 	  checkConcept<IterableGraphComponent<Base>, _Graph>();
-	  
-	  checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
-	    typename _Graph::UEdgeIt >();
-	  checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge, 
-            typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
-
-          typename _Graph::Node n;
-          typename _Graph::IncEdgeIt ueit(INVALID);
-          n = graph.baseNode(ueit);
-          n = graph.runningNode(ueit);
+
+          {
+            typename _Graph::Node node(INVALID);
+            typename _Graph::UEdge uedge(INVALID);
+            bool dir;
+            {
+              graph.first(uedge);
+              graph.next(uedge);
+            }
+            {
+              graph.firstInc(uedge, dir, node);
+              graph.nextInc(uedge, dir);
+            }
+            
+          }	
+  
+          {
+            checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
+              typename _Graph::UEdgeIt >();
+            checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge, 
+              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
+            
+            typename _Graph::Node n;
+            typename _Graph::IncEdgeIt ueit(INVALID);
+            n = graph.baseNode(ueit);
+            n = graph.runningNode(ueit);
+          }
+        }
+	
+	const _Graph& graph;
+	
+      };
+    };
+
+    /// \brief An empty iterable bipartite undirected graph class.
+    ///
+    /// This class provides beside the core graph features iterator
+    /// based iterable interface for the bipartite undirected graph
+    /// structure. This concept is part of the BpUGraph concept.
+    template <typename _Base = BaseUGraphComponent>
+    class IterableBpUGraphComponent : public IterableUGraphComponent<_Base> {
+    public:
+
+      typedef _Base Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::UEdge UEdge;
+    
+      typedef IterableBpUGraphComponent Graph;
+
+      /// \name Base iteration
+      /// 
+      /// This interface provides functions for iteration on graph items
+      /// @{  
+
+      using IterableUGraphComponent<_Base>::first;
+      using IterableUGraphComponent<_Base>::next;
+
+      /// \brief Gives back the first A-node in the iterating order.
+      ///
+      /// Gives back the first undirected A-node in the iterating
+      /// order.
+      ///     
+      void firstANode(Node&) const {}
+
+      /// \brief Gives back the next A-node in the iterating order.
+      ///
+      /// Gives back the next A-node in the iterating order.
+      ///     
+      void nextANode(Node&) const {}
+
+      /// \brief Gives back the first B-node in the iterating order.
+      ///
+      /// Gives back the first undirected B-node in the iterating
+      /// order.
+      ///     
+      void firstBNode(Node&) const {}
+
+      /// \brief Gives back the next B-node in the iterating order.
+      ///
+      /// Gives back the next B-node in the iterating order.
+      ///     
+      void nextBNode(Node&) const {}
+
+
+      /// \brief Gives back the first of the undirected edges start
+      /// from the given A-node.
+      ///      
+      /// Gives back the first of the undirected edges start from the
+      /// given A-node.
+      void firstFromANode(UEdge&, const Node&) const {}
+
+      /// \brief Gives back the next of the undirected edges start
+      /// from the given A-node.
+      ///      
+      /// Gives back the next of the undirected edges start from the
+      /// given A-node.
+      void nextFromANode(UEdge&) const {}
+
+      /// \brief Gives back the first of the undirected edges start
+      /// from the given B-node.
+      ///      
+      /// Gives back the first of the undirected edges start from the
+      /// given B-node.
+      void firstFromBNode(UEdge&, const Node&) const {}
+
+      /// \brief Gives back the next of the undirected edges start
+      /// from the given B-node.
+      ///      
+      /// Gives back the next of the undirected edges start from the
+      /// given B-node.
+      void nextFromBNode(UEdge&) const {}
+
+
+      /// @}
+
+      /// \name Class based iteration
+      /// 
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
+
+      /// \brief This iterator goes through each A-node.
+      ///
+      /// This iterator goes through each A-node.
+      typedef GraphItemIt<Graph, Node> ANodeIt;
+
+      /// \brief This iterator goes through each B-node.
+      ///
+      /// This iterator goes through each B-node.
+      typedef GraphItemIt<Graph, Node> BNodeIt;
+
+      /// @}
+
+      template <typename _Graph> 
+      struct Constraints {
+	void constraints() {
+	  checkConcept<IterableUGraphComponent<Base>, _Graph>();
+
+          {
+            typename _Graph::Node node(INVALID);
+            typename _Graph::UEdge uedge(INVALID);
+            graph.firstANode(node);
+            graph.nextANode(node);
+            graph.firstBNode(node);
+            graph.nextBNode(node);
+
+            graph.firstFromANode(uedge, node);
+            graph.nextFromANode(uedge);
+            graph.firstFromBNode(uedge, node);
+            graph.nextFromBNode(uedge);
+          }
+          {
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+              typename _Graph::ANodeIt >();
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+              typename _Graph::BNodeIt >();
+          }
+
 	}
 	
@@ -1195,9 +1324,66 @@
       struct Constraints {
 	void constraints() {
-	  checkConcept<Base, _Graph>();
-          checkConcept<AlterableGraphComponent, _Graph>();
+	  checkConcept<AlterableGraphComponent<Base>, _Graph>();
           typename _Graph::UEdgeNotifier& uen 
             = graph.getNotifier(typename _Graph::UEdge());
           ignore_unused_variable_warning(uen);
+	}
+	
+	const _Graph& graph;
+	
+      };
+      
+    };
+
+    /// \brief An empty alteration notifier bipartite undirected graph
+    /// class.
+    ///  
+    /// This class provides beside the core graph features alteration
+    /// notifier interface for the graph structure.  This implements
+    /// an observer-notifier pattern for each graph item. More
+    /// obsevers can be registered into the notifier and whenever an
+    /// alteration occured in the graph all the observers will
+    /// notified about it.
+    template <typename _Base = BaseUGraphComponent>
+    class AlterableBpUGraphComponent : public AlterableUGraphComponent<_Base> {
+    public:
+
+      typedef _Base Base;
+      typedef typename Base::ANode ANode;
+      typedef typename Base::BNode BNode;
+
+
+      /// The A-node observer registry.
+      typedef AlterationNotifier<AlterableBpUGraphComponent, ANode> 
+      ANodeNotifier;
+
+      /// The B-node observer registry.
+      typedef AlterationNotifier<AlterableBpUGraphComponent, BNode> 
+      BNodeNotifier;
+      
+      /// \brief Gives back the A-node alteration notifier.
+      ///
+      /// Gives back the A-node alteration notifier.
+      ANodeNotifier& getNotifier(ANode) const {
+	return ANodeNotifier();
+      }
+
+      /// \brief Gives back the B-node alteration notifier.
+      ///
+      /// Gives back the B-node alteration notifier.
+      BNodeNotifier& getNotifier(BNode) const {
+	return BNodeNotifier();
+      }
+
+      template <typename _Graph> 
+      struct Constraints {
+	void constraints() {
+          checkConcept<AlterableUGraphComponent<Base>, _Graph>();
+          typename _Graph::ANodeNotifier& ann 
+            = graph.getNotifier(typename _Graph::ANode());
+          typename _Graph::BNodeNotifier& bnn 
+            = graph.getNotifier(typename _Graph::BNode());
+          ignore_unused_variable_warning(ann);
+          ignore_unused_variable_warning(bnn);
 	}
 	
@@ -1416,5 +1602,5 @@
     };
 
-    /// \brief An empty mappable base graph class.
+    /// \brief An empty mappable base bipartite undirected graph class.
     ///
     /// This class provides beside the core graph features
@@ -1479,5 +1665,4 @@
 
 	void constraints() {
-	  checkConcept<Base, _Graph>();
 	  checkConcept<MappableGraphComponent<Base>, _Graph>();
 
@@ -1501,4 +1686,127 @@
     };
 
+    /// \brief An empty mappable base bipartite undirected graph
+    /// class.
+    ///
+    /// This class provides beside the core graph features
+    /// map interface for the graph structure.
+    /// This concept is part of the BpUGraph concept.
+    template <typename _Base = BaseBpUGraphComponent>
+    class MappableBpUGraphComponent : public MappableUGraphComponent<_Base>  {
+    public:
+
+      typedef _Base Base;
+      typedef typename Base::Node Node;
+
+      typedef MappableBpUGraphComponent Graph;
+
+      /// \brief ReadWrite map of the A-nodes.
+      ///
+      /// ReadWrite map of the A-nodes.
+      ///
+      template <typename _Value>
+      class ANodeMap : public GraphMap<Graph, Node, _Value> {  
+      public:
+        typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
+
+	/// \brief Construct a new map.
+	///
+	/// Construct a new map for the graph.
+	/// \todo call the right parent class constructor
+	explicit ANodeMap(const MappableBpUGraphComponent& graph) 
+          : Parent(graph) {}
+
+	/// \brief Construct a new map with default value.
+	///
+	/// Construct a new map for the graph and initalise the values.
+	ANodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
+          : Parent(graph, value) {}
+
+	/// \brief Copy constructor.
+	///
+	/// Copy Constructor.
+	ANodeMap(const ANodeMap& nm) : Parent(nm) {}
+
+	/// \brief Assign operator.
+	///
+	/// Assign operator.
+        template <typename CMap>
+        ANodeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<Node, _Value>, CMap>();
+          return *this;
+        }
+
+      };
+
+      /// \brief ReadWrite map of the B-nodes.
+      ///
+      /// ReadWrite map of the A-nodes.
+      ///
+      template <typename _Value>
+      class BNodeMap : public GraphMap<Graph, Node, _Value> {  
+      public:
+        typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
+
+	/// \brief Construct a new map.
+	///
+	/// Construct a new map for the graph.
+	/// \todo call the right parent class constructor
+	explicit BNodeMap(const MappableBpUGraphComponent& graph) 
+          : Parent(graph) {}
+
+	/// \brief Construct a new map with default value.
+	///
+	/// Construct a new map for the graph and initalise the values.
+	BNodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
+          : Parent(graph, value) {}
+
+	/// \brief Copy constructor.
+	///
+	/// Copy Constructor.
+	BNodeMap(const BNodeMap& nm) : Parent(nm) {}
+
+	/// \brief Assign operator.
+	///
+	/// Assign operator.
+        template <typename CMap>
+        BNodeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<Node, _Value>, CMap>();
+          return *this;
+        }
+
+      };
+
+
+      template <typename _Graph>
+      struct Constraints {
+
+	struct Dummy {
+	  int value;
+	  Dummy() : value(0) {}
+	  Dummy(int _v) : value(_v) {}
+	};
+
+	void constraints() {
+	  checkConcept<MappableUGraphComponent<Base>, _Graph>();
+
+	  { // int map test
+	    typedef typename _Graph::template ANodeMap<int> IntANodeMap;
+	    checkConcept<GraphMap<_Graph, typename _Graph::ANode, int>,
+	      IntANodeMap >();
+	  } { // bool map test
+	    typedef typename _Graph::template ANodeMap<bool> BoolANodeMap;
+	    checkConcept<GraphMap<_Graph, typename _Graph::ANode, bool>,
+	      BoolANodeMap >();
+	  } { // Dummy map test
+	    typedef typename _Graph::template ANodeMap<Dummy> DummyANodeMap;
+	    checkConcept<GraphMap<_Graph, typename _Graph::ANode, Dummy>, 
+	      DummyANodeMap >();
+	  } 
+	}
+
+	_Graph& graph;
+      };
+    };
+
 
     /// \brief An empty extendable graph class.
@@ -1511,4 +1819,5 @@
     class ExtendableGraphComponent : public _Base {
     public:
+      typedef _Base Base;
 
       typedef typename _Base::Node Node;
@@ -1533,4 +1842,5 @@
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  typename _Graph::Node node_a, node_b;
 	  node_a = graph.addNode();
@@ -1555,4 +1865,5 @@
     public:
 
+      typedef _Base Base;
       typedef typename _Base::Node Node;
       typedef typename _Base::UEdge UEdge;
@@ -1576,4 +1887,5 @@
       struct Constraints {
 	void constraints() {
+	  checkConcept<Base, _Graph>();
 	  typename _Graph::Node node_a, node_b;
 	  node_a = graph.addNode();
@@ -1584,4 +1896,25 @@
 
 	_Graph& graph;
+      };
+    };
+
+    /// \brief An empty extendable base undirected graph class.
+    ///
+    /// This class provides beside the core bipartite undirected graph
+    /// features core undircted graph extend interface for the graph
+    /// structure.  The main difference between the base and this
+    /// interface is that the graph alterations should handled already
+    /// on this level.
+    template <typename _Base = BaseBpUGraphComponent>
+    class ExtendableBpUGraphComponent 
+      : public ExtendableUGraphComponent<_Base> {
+
+      typedef _Base Base;
+
+      template <typename _Graph>
+      struct Constraints {
+	void constraints() {
+          checkConcept<ExtendableUGraphComponent<Base>, _Graph>();
+	}
       };
     };
@@ -1616,4 +1949,5 @@
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  typename _Graph::Node node;
 	  graph.erase(node);
@@ -1655,4 +1989,5 @@
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  typename _Graph::Node node;
 	  graph.erase(node);
@@ -1662,4 +1997,25 @@
 
 	_Graph& graph;
+      };
+    };
+
+    /// \brief An empty erasable base bipartite undirected graph class.
+    ///  
+    /// This class provides beside the core bipartite undirected graph
+    /// features core erase functions for the undirceted graph
+    /// structure. The main difference between the base and this
+    /// interface is that the graph alterations should handled already
+    /// on this level.
+    template <typename _Base = BaseBpUGraphComponent>
+    class ErasableBpUGraphComponent : public ErasableUGraphComponent<_Base> {
+    public:
+
+      typedef _Base Base;
+
+      template <typename _Graph>
+      struct Constraints {
+	void constraints() {
+          checkConcept<ErasableUGraphComponent<Base>, _Graph>();
+	}
       };
     };
@@ -1675,4 +2031,6 @@
     public:
 
+      typedef _Base Base;
+
       /// \brief Erase all nodes and edges from the graph.
       ///
@@ -1684,4 +2042,5 @@
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  graph.clear();
 	}
@@ -1698,17 +2057,13 @@
     /// the graph alterations should handled already on this level.
     template <typename _Base = BaseUGraphComponent>
-    class ClearableUGraphComponent : public _Base {
-    public:
-
-      /// \brief Erase all nodes and undirected edges from the graph.
-      ///
-      /// Erase all nodes and undirected edges from the graph.
-      ///
-      void clear() {}    
+    class ClearableUGraphComponent : public ClearableUGraphComponent<_Base> {
+    public:
+
+      typedef _Base Base;
 
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
-	  graph.clear();
+          checkConcept<ClearableUGraphComponent<Base>, _Graph>();
 	}
 
@@ -1717,4 +2072,29 @@
     };
 
+    /// \brief An empty clearable base bipartite undirected graph
+    /// class.
+    ///
+    /// This class provides beside the core bipartite undirected graph
+    /// features core clear functions for the undirected graph
+    /// structure. The main difference between the base and this
+    /// interface is that the graph alterations should handled already
+    /// on this level.
+    template <typename _Base = BaseUGraphComponent>
+    class ClearableBpUGraphComponent 
+      : public ClearableBpUGraphComponent<_Base> {
+    public:
+
+      typedef _Base Base;
+
+      template <typename _Graph>
+      struct Constraints {
+	void constraints() {
+          checkConcept<ClearableBpUGraphComponent<Base>, _Graph>();
+	}
+
+      };
+
+    };
+
   }
 
