# HG changeset patch
# User deba
# Date 1159875999 0
# Node ID 06faf3f06d67a83a4040a1fecd3921af9a9d210d
# Parent  67af33b34394cfc25f47edffcd0cfca3c3455a3b
Some rearrangement of concepts and extenders
BpUGraph concepts and concept check test

diff -r 67af33b34394 -r 06faf3f06d67 lemon/bits/base_extender.h
--- a/lemon/bits/base_extender.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/bits/base_extender.h	Tue Oct 03 11:46:39 2006 +0000
@@ -279,6 +279,209 @@
     }
   };
 
+  template <typename Base>
+  class BidirBpUGraphExtender : public Base {
+  public:
+    typedef Base Parent;
+    typedef BidirBpUGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UEdge UEdge;
+
+
+    using Parent::first;
+    using Parent::next;
+
+    using Parent::id;
+
+    class ANode : public Node {
+      friend class BidirBpUGraphExtender;
+    public:
+      ANode() {}
+      ANode(const Node& node) : Node(node) {
+	LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
+		     typename Parent::NodeSetError());
+      }
+      ANode& operator=(const Node& node) {
+	LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
+		     typename Parent::NodeSetError());
+        Node::operator=(node);
+        return *this;
+      }
+      ANode(Invalid) : Node(INVALID) {}
+    };
+
+    void first(ANode& node) const {
+      Parent::firstANode(static_cast<Node&>(node));
+    }
+    void next(ANode& node) const {
+      Parent::nextANode(static_cast<Node&>(node));
+    }
+
+    int id(const ANode& node) const {
+      return Parent::aNodeId(node);
+    }
+
+    class BNode : public Node {
+      friend class BidirBpUGraphExtender;
+    public:
+      BNode() {}
+      BNode(const Node& node) : Node(node) {
+	LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
+		     typename Parent::NodeSetError());
+      }
+      BNode& operator=(const Node& node) {
+	LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 
+		     typename Parent::NodeSetError());
+        Node::operator=(node);
+        return *this;
+      }
+      BNode(Invalid) : Node(INVALID) {}
+    };
+
+    void first(BNode& node) const {
+      Parent::firstBNode(static_cast<Node&>(node));
+    }
+    void next(BNode& node) const {
+      Parent::nextBNode(static_cast<Node&>(node));
+    }
+  
+    int id(const BNode& node) const {
+      return Parent::aNodeId(node);
+    }
+
+    Node source(const UEdge& edge) const {
+      return aNode(edge);
+    }
+    Node target(const UEdge& edge) const {
+      return bNode(edge);
+    }
+
+    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
+      if (Parent::aNode(node)) {
+	Parent::firstFromANode(edge, node);
+	direction = true;
+      } else {
+	Parent::firstFromBNode(edge, node);
+	direction = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextInc(UEdge& edge, bool& direction) const {
+      if (direction) {
+	Parent::nextFromANode(edge);
+      } else {
+	Parent::nextFromBNode(edge);
+	if (edge == INVALID) direction = true;
+      }
+    }
+
+    class Edge : public UEdge {
+      friend class BidirBpUGraphExtender;
+    protected:
+      bool forward;
+
+      Edge(const UEdge& edge, bool _forward)
+	: UEdge(edge), forward(_forward) {}
+
+    public:
+      Edge() {}
+      Edge (Invalid) : UEdge(INVALID), forward(true) {}
+      bool operator==(const Edge& i) const {
+	return UEdge::operator==(i) && forward == i.forward;
+      }
+      bool operator!=(const Edge& i) const {
+	return UEdge::operator!=(i) || forward != i.forward;
+      }
+      bool operator<(const Edge& i) const {
+	return UEdge::operator<(i) || 
+	  (!(i.forward<forward) && UEdge(*this)<UEdge(i));
+      }
+    };
+
+    void first(Edge& edge) const {
+      Parent::first(static_cast<UEdge&>(edge));
+      edge.forward = true;
+    }
+
+    void next(Edge& edge) const {
+      if (!edge.forward) {
+	Parent::next(static_cast<UEdge&>(edge));
+      }
+      edge.forward = !edge.forward;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (Parent::aNode(node)) {
+	Parent::firstFromANode(edge, node);
+	edge.forward = true;
+      } else {
+	Parent::firstFromBNode(edge, node);
+	edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextOut(Edge& edge) const {
+      if (edge.forward) {
+	Parent::nextFromANode(edge);
+      } else {
+	Parent::nextFromBNode(edge);
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (Parent::bNode(node)) {
+	Parent::firstFromBNode(edge, node);
+	edge.forward = true;	
+      } else {
+	Parent::firstFromANode(edge, node);
+	edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextIn(Edge& edge) const {
+      if (edge.forward) {
+	Parent::nextFromBNode(edge);
+      } else {
+	Parent::nextFromANode(edge);
+	edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+
+    Node source(const Edge& edge) const {
+      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
+    }
+    Node target(const Edge& edge) const {
+      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
+    }
+
+    int id(const Edge& edge) const {
+      return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 
+        (edge.forward ? 0 : 1);
+    }
+    Edge edgeFromId(int id) const {
+      return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
+    }
+    int maxEdgeId() const {
+      return (Parent::maxUEdgeId() << 1) + 1;
+    }
+
+    bool direction(const Edge& edge) const {
+      return edge.forward;
+    }
+
+    Edge direct(const UEdge& edge, bool direction) const {
+      return Edge(edge, direction);
+    }
+
+    int edgeNum() const {
+      return 2 * Parent::uEdgeNum();
+    }
+
+    int uEdgeNum() const {
+      return Parent::uEdgeNum();
+    }
+
+
+  };
 }
 
 #endif
diff -r 67af33b34394 -r 06faf3f06d67 lemon/bits/graph_adaptor_extender.h
--- a/lemon/bits/graph_adaptor_extender.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/bits/graph_adaptor_extender.h	Tue Oct 03 11:46:39 2006 +0000
@@ -475,10 +475,10 @@
       return Parent::nodeFromId(id);
     }
     ANode fromId(int id, ANode) const {
-      return Parent::fromANodeId(id);
+      return Parent::nodeFromANodeId(id);
     }
     BNode fromId(int id, BNode) const {
-      return Parent::fromBNodeId(id);
+      return Parent::nodeFromBNodeId(id);
     }
     Edge fromId(int id, Edge) const {
       return Parent::edgeFromId(id);
diff -r 67af33b34394 -r 06faf3f06d67 lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/bits/graph_extender.h	Tue Oct 03 11:46:39 2006 +0000
@@ -730,206 +730,31 @@
   template <typename Base>
   class BpUGraphExtender : public Base {
   public:
+
     typedef Base Parent;
     typedef BpUGraphExtender Graph;
 
     typedef typename Parent::Node Node;
+    typedef typename Parent::ANode ANode;
+    typedef typename Parent::BNode BNode;
+    typedef typename Parent::Edge Edge;
     typedef typename Parent::UEdge UEdge;
 
 
-    using Parent::first;
-    using Parent::next;
-
-    using Parent::id;
-
-    class ANode : public Node {
-      friend class BpUGraphExtender;
-    public:
-      ANode() {}
-      ANode(const Node& node) : Node(node) {
-	LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
-		     typename Parent::NodeSetError());
-      }
-      ANode(Invalid) : Node(INVALID) {}
-    };
-
-    void first(ANode& node) const {
-      Parent::firstANode(static_cast<Node&>(node));
-    }
-    void next(ANode& node) const {
-      Parent::nextANode(static_cast<Node&>(node));
+    Node oppositeNode(const Node& node, const UEdge& edge) const {
+      return Parent::aNode(edge) == node ? 
+	Parent::bNode(edge) : Parent::aNode(edge);
     }
 
-    int id(const ANode& node) const {
-      return Parent::aNodeId(node);
-    }
-
-    class BNode : public Node {
-      friend class BpUGraphExtender;
-    public:
-      BNode() {}
-      BNode(const Node& node) : Node(node) {
-	LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
-		     typename Parent::NodeSetError());
-      }
-      BNode(Invalid) : Node(INVALID) {}
-    };
-
-    void first(BNode& node) const {
-      Parent::firstBNode(static_cast<Node&>(node));
-    }
-    void next(BNode& node) const {
-      Parent::nextBNode(static_cast<Node&>(node));
-    }
-  
-    int id(const BNode& node) const {
-      return Parent::aNodeId(node);
-    }
-
-    Node source(const UEdge& edge) const {
-      return aNode(edge);
-    }
-    Node target(const UEdge& edge) const {
-      return bNode(edge);
-    }
-
-    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
-      if (Parent::aNode(node)) {
-	Parent::firstFromANode(edge, node);
-	direction = true;
-      } else {
-	Parent::firstFromBNode(edge, node);
-	direction = static_cast<UEdge&>(edge) == INVALID;
-      }
-    }
-    void nextInc(UEdge& edge, bool& direction) const {
-      if (direction) {
-	Parent::nextFromANode(edge);
-      } else {
-	Parent::nextFromBNode(edge);
-	if (edge == INVALID) direction = true;
-      }
-    }
-
-    class Edge : public UEdge {
-      friend class BpUGraphExtender;
-    protected:
-      bool forward;
-
-      Edge(const UEdge& edge, bool _forward)
-	: UEdge(edge), forward(_forward) {}
-
-    public:
-      Edge() {}
-      Edge (Invalid) : UEdge(INVALID), forward(true) {}
-      bool operator==(const Edge& i) const {
-	return UEdge::operator==(i) && forward == i.forward;
-      }
-      bool operator!=(const Edge& i) const {
-	return UEdge::operator!=(i) || forward != i.forward;
-      }
-      bool operator<(const Edge& i) const {
-	return UEdge::operator<(i) || 
-	  (!(i.forward<forward) && UEdge(*this)<UEdge(i));
-      }
-    };
-
-    void first(Edge& edge) const {
-      Parent::first(static_cast<UEdge&>(edge));
-      edge.forward = true;
-    }
-
-    void next(Edge& edge) const {
-      if (!edge.forward) {
-	Parent::next(static_cast<UEdge&>(edge));
-      }
-      edge.forward = !edge.forward;
-    }
-
-    void firstOut(Edge& edge, const Node& node) const {
-      if (Parent::aNode(node)) {
-	Parent::firstFromANode(edge, node);
-	edge.forward = true;
-      } else {
-	Parent::firstFromBNode(edge, node);
-	edge.forward = static_cast<UEdge&>(edge) == INVALID;
-      }
-    }
-    void nextOut(Edge& edge) const {
-      if (edge.forward) {
-	Parent::nextFromANode(edge);
-      } else {
-	Parent::nextFromBNode(edge);
-        edge.forward = static_cast<UEdge&>(edge) == INVALID;
-      }
-    }
-
-    void firstIn(Edge& edge, const Node& node) const {
-      if (Parent::bNode(node)) {
-	Parent::firstFromBNode(edge, node);
-	edge.forward = true;	
-      } else {
-	Parent::firstFromANode(edge, node);
-	edge.forward = static_cast<UEdge&>(edge) == INVALID;
-      }
-    }
-    void nextIn(Edge& edge) const {
-      if (edge.forward) {
-	Parent::nextFromBNode(edge);
-      } else {
-	Parent::nextFromANode(edge);
-	edge.forward = static_cast<UEdge&>(edge) == INVALID;
-      }
-    }
-
-    Node source(const Edge& edge) const {
-      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
-    }
-    Node target(const Edge& edge) const {
-      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
-    }
-
-    int id(const Edge& edge) const {
-      return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 
-        (edge.forward ? 0 : 1);
-    }
-    Edge edgeFromId(int id) const {
-      return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
-    }
-    int maxEdgeId() const {
-      return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
-    }
-
-    bool direction(const Edge& edge) const {
-      return edge.forward;
-    }
-
-    Edge direct(const UEdge& edge, bool direction) const {
-      return Edge(edge, direction);
-    }
-
-    int edgeNum() const {
-      return 2 * Parent::uEdgeNum();
-    }
-
-    int uEdgeNum() const {
-      return Parent::uEdgeNum();
-    }
-
-    Node oppositeNode(const UEdge& edge, const Node& node) const {
-      return source(edge) == node ? 
-	target(edge) : source(edge);
-    }
-
+    using Parent::direct;
     Edge direct(const UEdge& edge, const Node& node) const {
-      return Edge(edge, node == Parent::source(edge));
+      return Parent::direct(edge, node == Parent::source(edge));
     }
 
     Edge oppositeEdge(const Edge& edge) const {
-      return Parent::direct(edge, !Parent::direction(edge));
+      return direct(edge, !Parent::direction(edge));
     }
-
-
+    
     int maxId(Node) const {
       return Parent::maxNodeId();
     }
@@ -940,7 +765,7 @@
       return Parent::maxANodeId();
     }
     int maxId(Edge) const {
-      return maxEdgeId();
+      return Parent::maxEdgeId();
     }
     int maxId(UEdge) const {
       return Parent::maxUEdgeId();
@@ -951,10 +776,10 @@
       return Parent::nodeFromId(id);
     }
     ANode fromId(int id, ANode) const {
-      return Parent::fromANodeId(id);
+      return Parent::nodeFromANodeId(id);
     }
     BNode fromId(int id, BNode) const {
-      return Parent::fromBNodeId(id);
+      return Parent::nodeFromBNodeId(id);
     }
     Edge fromId(int id, Edge) const {
       return Parent::edgeFromId(id);
@@ -1304,12 +1129,9 @@
       template <typename CMap>
       NodeMap& operator=(const CMap& cmap) {
 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();
-	const typename Parent::Notifier* notifier = Parent::getNotifier();
-	Edge it;
-	for (graph.first(it); it != INVALID; graph.next(it)) {
-	  Parent::set(it, cmap[it]);
-	}
-	return *this;
+        aNodeMap = cmap;
+        bNodeMap = cmap;
+        return *this;
       }
 
       ConstReference operator[](const Key& node) const {
@@ -1459,8 +1281,8 @@
       getNotifier(UEdge()).add(uedge);
     
       std::vector<Edge> edges;
-      edges.push_back(direct(uedge, true));
-      edges.push_back(direct(uedge, false));
+      edges.push_back(Parent::direct(uedge, true));
+      edges.push_back(Parent::direct(uedge, false));
       getNotifier(Edge()).add(edges);
     
       return uedge;
@@ -1499,8 +1321,8 @@
     
     void erase(const UEdge& uedge) {
       std::vector<Edge> edges;
-      edges.push_back(direct(uedge, true));
-      edges.push_back(direct(uedge, false));
+      edges.push_back(Parent::direct(uedge, true));
+      edges.push_back(Parent::direct(uedge, false));
       getNotifier(Edge()).erase(edges);
       getNotifier(UEdge()).erase(uedge);
       Parent::erase(uedge);
@@ -1526,7 +1348,7 @@
     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
       UEdge uedge = Parent::findUEdge(u, v, prev);
       if (uedge != INVALID) {
-        return direct(uedge, Parent::aNode(u));
+        return Parent::direct(uedge, Parent::aNode(u));
       } else {
         return INVALID;
       }
diff -r 67af33b34394 -r 06faf3f06d67 lemon/bpugraph_adaptor.h
--- a/lemon/bpugraph_adaptor.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/bpugraph_adaptor.h	Tue Oct 03 11:46:39 2006 +0000
@@ -87,6 +87,12 @@
     void firstInc(UEdge &i, bool &d, const Node &n) const {
       graph->firstInc(i, d, n);
     }
+    void firstFromANode(UEdge& i, const Node& n) const {
+      graph->firstFromANode(i, n);
+    }
+    void firstFromBNode(UEdge& i, const Node& n) const {
+      graph->firstFromBNode(i, n);
+    }
 
     void next(Node& i) const { graph->next(i); }
     void nextANode(Node& i) const { graph->nextANode(i); }
@@ -96,6 +102,8 @@
     void nextIn(Edge& i) const { graph->nextIn(i); }
     void nextOut(Edge& i) const { graph->nextOut(i); }
     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
+    void nextFromANode(UEdge& i) const { graph->nextFromANode(i); }
+    void nextFromBNode(UEdge& i) const { graph->nextFromBNode(i); }
 
     Node source(const UEdge& e) const { return graph->source(e); }
     Node target(const UEdge& e) const { return graph->target(e); }
@@ -149,8 +157,8 @@
     int id(const UEdge& e) const { return graph->id(e); }
 
     Node fromNodeId(int id) const { return graph->fromNodeId(id); }
-    ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
-    BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
+    ANode nodeFromANodeId(int id) const { return graph->nodeFromANodeId(id); }
+    BNode nodeFromBNodeId(int id) const { return graph->nodeFromBNodeId(id); }
     Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
     UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
 
@@ -340,11 +348,21 @@
     void nextANode(Node& i) const { Parent::nextBNode(i); }
     void nextBNode(Node& i) const { Parent::nextANode(i); }
 
+    void firstFromANode(UEdge& i, const Node& n) const {
+      Parent::firstFromBNode(i, n);
+    }
+    void firstFromBNode(UEdge& i, const Node& n) const {
+      Parent::firstFromANode(i, n);
+    }
+
+    void nextFromANode(UEdge& i) const { Parent::nextFromBNode(i); }
+    void nextFromBNode(UEdge& i) const { Parent::nextFromANode(i); }
+
     int id(const ANode& v) const { return Parent::id(v); }
     int id(const BNode& v) const { return Parent::id(v); }
 
-    ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
-    BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
+    ANode nodeFromANodeId(int id) const { return Parent::nodeFromBNodeId(id); }
+    BNode nodeFromBNodeId(int id) const { return Parent::nodeFromANodeId(id); }
 
     int maxANodeId() const { return Parent::maxBNodeId(); }
     int maxBNodeId() const { return Parent::maxANodeId(); }
@@ -549,7 +567,10 @@
   /// Bipartite graph adaptor to implement matchings. It implements
   /// the residual graph of the matching.
   template <typename _BpUGraph, 
-            typename _ANMatchingMap, typename _BNMatchingMap>
+            typename _ANMatchingMap = 
+            typename _BpUGraph::template ANodeMap<typename _BpUGraph::UEdge>, 
+            typename _BNMatchingMap =
+            typename _BpUGraph::template BNodeMap<typename _BpUGraph::UEdge> >
   class MatchingBpUGraphAdaptor 
     : public BpUGraphAdaptorExtender<
     MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> > 
diff -r 67af33b34394 -r 06faf3f06d67 lemon/concept/bpugraph.h
--- a/lemon/concept/bpugraph.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/concept/bpugraph.h	Tue Oct 03 11:46:39 2006 +0000
@@ -132,25 +132,31 @@
       /// This class is just a helper class for ANodes, 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
-      /// two use just as template parameters for special map types. 
-      class ANode {
+      /// to use just as template parameters for special map types. 
+      class ANode : public Node {
       public:
         /// Default constructor
 
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        ANode() { }
+        ANode() : Node() { }
         /// Copy constructor.
 
         /// Copy constructor.
         ///
-        ANode(const ANode&) { }
+        ANode(const ANode&) : Node() { }
 
         /// Construct the same node as ANode.
 
         /// Construct the same node as ANode. It may throws assertion
         /// when the given node is from the BNode set.
-        ANode(const Node&) { }
+        ANode(const Node&) : Node() { }
+
+        /// 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; }
 
         /// Invalid constructor \& conversion.
 
@@ -186,25 +192,31 @@
       /// This class is just a helper class for BNodes, 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
-      /// two use just as template parameters for special map types. 
-      class BNode {
+      /// to use just as template parameters for special map types. 
+      class BNode : public Node {
       public:
         /// Default constructor
 
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        BNode() { }
+        BNode() : Node() { }
         /// Copy constructor.
 
         /// Copy constructor.
         ///
-        BNode(const BNode&) { }
+        BNode(const BNode&) : Node() { }
 
         /// Construct the same node as BNode.
 
         /// Construct the same node as BNode. It may throws assertion
         /// when the given node is from the ANode set.
-        BNode(const Node&) { }
+        BNode(const Node&) : Node() { }
+
+        /// 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; }
 
         /// Invalid constructor \& conversion.
 
@@ -717,7 +729,12 @@
         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
         ///Assignment operator
         NodeMap& operator=(const NodeMap&) { return *this; }
-        // \todo fix this concept
+        ///Assignment operator
+        template <typename CMap>
+        NodeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<Node, T>, CMap>();
+          return *this; 
+        }
       };
 
       /// \brief Read write map of the ANodes to type \c T.
@@ -738,10 +755,15 @@
         ANodeMap(const BpUGraph&, T) { }
 
         ///Copy constructor
-        ANodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
+        ANodeMap(const ANodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
         ///Assignment operator
-        ANodeMap& operator=(const NodeMap&) { return *this; }
-        // \todo fix this concept
+        ANodeMap& operator=(const ANodeMap&) { return *this; }
+        ///Assignment operator
+        template <typename CMap>
+        ANodeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<Node, T>, CMap>();
+          return *this; 
+        }
       };
 
       /// \brief Read write map of the BNodes to type \c T.
@@ -762,10 +784,15 @@
         BNodeMap(const BpUGraph&, T) { }
 
         ///Copy constructor
-        BNodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
+        BNodeMap(const BNodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
         ///Assignment operator
-        BNodeMap& operator=(const NodeMap&) { return *this; }
-        // \todo fix this concept
+        BNodeMap& operator=(const BNodeMap&) { return *this; }
+        ///Assignment operator
+        template <typename CMap>
+        BNodeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<Node, T>, CMap>();
+          return *this; 
+        }
       };
 
       /// \brief Read write map of the directed edges to type \c T.
@@ -788,7 +815,12 @@
         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
         ///Assignment operator
         EdgeMap& operator=(const EdgeMap&) { return *this; }
-        // \todo fix this concept    
+        ///Assignment operator
+        template <typename CMap>
+        EdgeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<Edge, T>, CMap>();
+          return *this; 
+        }
       };
 
       /// Read write map of the undirected edges to type \c T.
@@ -811,7 +843,12 @@
         UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
         ///Assignment operator
         UEdgeMap &operator=(const UEdgeMap&) { return *this; }
-        // \todo fix this concept    
+        ///Assignment operator
+        template <typename CMap>
+        UEdgeMap& operator=(const CMap&) { 
+          checkConcept<ReadMap<UEdge, T>, CMap>();
+          return *this; 
+        }
       };
 
       /// \brief Direct the given undirected edge.
@@ -933,9 +970,41 @@
 	return INVALID;
       }
 
+      void first(Node&) const {}
+      void next(Node&) const {}
+
+      void first(Edge&) const {}
+      void next(Edge&) const {}
+
+      void first(UEdge&) const {}
+      void next(UEdge&) const {}
+
+      void firstANode(Node&) const {}
+      void nextANode(Node&) const {}
+
+      void firstBNode(Node&) const {}
+      void nextBNode(Node&) const {}
+
+      void firstIn(Edge&, const Node&) const {}
+      void nextIn(Edge&) const {}
+
+      void firstOut(Edge&, const Node&) const {}
+      void nextOut(Edge&) const {}
+
+      void firstInc(UEdge &, bool &, const Node &) const {}
+      void nextInc(UEdge &, bool &) const {}
+
+      void firstFromANode(UEdge&, const Node&) const {}
+      void nextFromANode(UEdge&) const {}
+
+      void firstFromBNode(UEdge&, const Node&) const {}
+      void nextFromBNode(UEdge&) const {}
+
       template <typename Graph>
       struct Constraints {
 	void constraints() {
+	  checkConcept<IterableBpUGraphComponent<>, Graph>();
+	  checkConcept<MappableBpUGraphComponent<>, Graph>();
 	}
       };
 
diff -r 67af33b34394 -r 06faf3f06d67 lemon/concept/graph.h
--- a/lemon/concept/graph.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/concept/graph.h	Tue Oct 03 11:46:39 2006 +0000
@@ -439,7 +439,6 @@
       template <typename RGraph>
       struct Constraints {
         void constraints() {
-          checkConcept<BaseIterableGraphComponent<>, Graph>();
           checkConcept<IterableGraphComponent<>, Graph>();
           checkConcept<MappableGraphComponent<>, Graph>();
         }
diff -r 67af33b34394 -r 06faf3f06d67 lemon/concept/graph_components.h
--- a/lemon/concept/graph_components.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/concept/graph_components.h	Tue Oct 03 11:46:39 2006 +0000
@@ -218,6 +218,11 @@
         /// Besides the core graph item functionality each edge should
         /// 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; }
       };
 
       /// \brief Returns the direction of the edge.
@@ -290,173 +295,149 @@
 
     };
 
-    /// \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 {
+    /// 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;
 
-      typedef _Base Base; 
-      typedef typename Base::Node Node;
-      typedef typename Base::Edge Edge;
+      /// \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 Gives back the first node in the iterating order.
-      ///      
-      /// Gives back the first node in the iterating order.
-      ///     
-      void first(Node&) const {}
+        /// \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 Gives back the next node in the iterating order.
+      /// \brief Helper class for B-nodes.
       ///
-      /// Gives back the next node in the iterating order.
-      ///     
-      void next(Node&) const {}
+      /// 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 Gives back the first edge in the iterating order.
+        /// \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 the first edge in the iterating order.
-      ///     
-      void first(Edge&) const {}
+      /// Gives back %true when the node is A-node.
+      bool aNode(const Node&) const { return false; }
 
-      /// \brief Gives back the next edge in the iterating order.
+      /// \brief Gives back %true when the node is B-node.
       ///
-      /// Gives back the next edge in the iterating order.
-      ///     
-      void next(Edge&) const {}
+      /// 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 first of the edges point to the given
-      /// node.
+      /// \brief Gives back the B-node of the undirected edge.
       ///
-      /// 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 {}
-
-
+      /// 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;
-      };
     };
 
     /// \brief An empty idable base graph class.
@@ -517,7 +498,7 @@
       struct Constraints {
 
 	void constraints() {
-	  checkConcept< BaseGraphComponent, _Graph >();
+	  checkConcept<Base, _Graph >();
 	  typename _Graph::Node node;
 	  int nid = graph.id(node);
 	  nid = graph.id(node);
@@ -590,214 +571,81 @@
       };
     };
 
-    /// \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.
+      using IDableUGraphComponent<_Base>::id;
+
+      /// \brief Gives back an unique integer id for the ANode. 
       ///
-      /// Erase a node from the graph. This function should not
-      /// erase edges connecting to the Node.
-      void erase(const Node&) {}    
+      /// Gives back an unique integer id for the ANode. 
+      ///
+      int aNodeId(const Node&) const { return -1;}
 
-      /// \brief Erase an edge from the graph.
+      /// \brief Gives back the undirected edge by the unique id.
       ///
-      /// Erase an edge from the graph.
+      /// 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.
       ///
-      void erase(const Edge&) {}
+      /// 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);
+	  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();
 	}
 
-	_Graph& graph;
+	const _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;
-      };
-    };
-
-
     /// \brief Skeleton class for graph NodeIt and EdgeIt
     ///
     /// Skeleton class for graph NodeIt and EdgeIt.
@@ -947,7 +795,7 @@
     ///
     /// 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 {
 
@@ -959,6 +807,72 @@
 
       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.
       ///
@@ -1008,35 +922,53 @@
       /// It is always the target of the pointed edge.
       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);
+          }
         }
 	
 	const _Graph& graph;
@@ -1048,7 +980,7 @@
     ///
     /// 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> {
     public:
@@ -1060,9 +992,57 @@
 
     
       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.
       ///
@@ -1084,21 +1064,170 @@
       /// Gives back the running node of the iterator.
       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 >();
+          }
+
 	}
 	
 	const _Graph& graph;
@@ -1194,8 +1323,7 @@
       template <typename _Graph> 
       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);
@@ -1207,6 +1335,64 @@
       
     };
 
+    /// \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);
+	}
+	
+	const _Graph& graph;
+	
+      };
+      
+    };
+
 
     /// \brief Class describing the concept of graph maps
     /// 
@@ -1415,7 +1601,7 @@
       };
     };
 
-    /// \brief An empty mappable base graph class.
+    /// \brief An empty mappable base bipartite undirected graph class.
     ///
     /// This class provides beside the core graph features
     /// map interface for the graph structure.
@@ -1478,7 +1664,6 @@
 	};
 
 	void constraints() {
-	  checkConcept<Base, _Graph>();
 	  checkConcept<MappableGraphComponent<Base>, _Graph>();
 
 	  { // int map test
@@ -1500,6 +1685,129 @@
       };
     };
 
+    /// \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.
     ///
@@ -1510,6 +1818,7 @@
     template <typename _Base = BaseGraphComponent>
     class ExtendableGraphComponent : public _Base {
     public:
+      typedef _Base Base;
 
       typedef typename _Base::Node Node;
       typedef typename _Base::Edge Edge;
@@ -1532,6 +1841,7 @@
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  typename _Graph::Node node_a, node_b;
 	  node_a = graph.addNode();
 	  node_b = graph.addNode();
@@ -1554,6 +1864,7 @@
     class ExtendableUGraphComponent : public _Base {
     public:
 
+      typedef _Base Base;
       typedef typename _Base::Node Node;
       typedef typename _Base::UEdge UEdge;
 
@@ -1575,6 +1886,7 @@
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
+	  checkConcept<Base, _Graph>();
 	  typename _Graph::Node node_a, node_b;
 	  node_a = graph.addNode();
 	  node_b = graph.addNode();
@@ -1586,6 +1898,27 @@
       };
     };
 
+    /// \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>();
+	}
+      };
+    };
+
     /// \brief An empty erasable graph class.
     ///  
     /// This class provides beside the core graph features core erase
@@ -1615,6 +1948,7 @@
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  typename _Graph::Node node;
 	  graph.erase(node);
 	  typename _Graph::Edge edge;
@@ -1654,6 +1988,7 @@
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  typename _Graph::Node node;
 	  graph.erase(node);
 	  typename _Graph::Edge edge;
@@ -1664,6 +1999,27 @@
       };
     };
 
+    /// \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>();
+	}
+      };
+    };
+
     /// \brief An empty clearable base graph class.
     ///
     /// This class provides beside the core graph features core clear
@@ -1674,6 +2030,8 @@
     class ClearableGraphComponent : public _Base {
     public:
 
+      typedef _Base Base;
+
       /// \brief Erase all nodes and edges from the graph.
       ///
       /// Erase all nodes and edges from the graph.
@@ -1683,6 +2041,7 @@
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
+          checkConcept<Base, _Graph>();
 	  graph.clear();
 	}
 
@@ -1697,25 +2056,46 @@
     /// main difference between the base and this interface is that
     /// the graph alterations should handled already on this level.
     template <typename _Base = BaseUGraphComponent>
-    class ClearableUGraphComponent : public _Base {
+    class ClearableUGraphComponent : public ClearableUGraphComponent<_Base> {
     public:
 
-      /// \brief Erase all nodes and undirected edges from the graph.
-      ///
-      /// Erase all nodes and undirected edges from the graph.
-      ///
-      void clear() {}    
+      typedef _Base Base;
 
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
-	  graph.clear();
+          checkConcept<ClearableUGraphComponent<Base>, _Graph>();
 	}
 
 	_Graph graph;
       };
     };
 
+    /// \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>();
+	}
+
+      };
+
+    };
+
   }
 
 }
diff -r 67af33b34394 -r 06faf3f06d67 lemon/concept/ugraph.h
--- a/lemon/concept/ugraph.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/concept/ugraph.h	Tue Oct 03 11:46:39 2006 +0000
@@ -697,7 +697,6 @@
       template <typename Graph>
       struct Constraints {
 	void constraints() {
-	  checkConcept<BaseIterableUGraphComponent<>, Graph>();
 	  checkConcept<IterableUGraphComponent<>, Graph>();
 	  checkConcept<MappableUGraphComponent<>, Graph>();
 	}
diff -r 67af33b34394 -r 06faf3f06d67 lemon/full_graph.h
--- a/lemon/full_graph.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/full_graph.h	Tue Oct 03 11:46:39 2006 +0000
@@ -609,7 +609,7 @@
     static int aNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromANodeId(int id) {
+    static Node nodeFromANodeId(int id) {
       return Node(id << 1);
     }
     int maxANodeId() const {
@@ -619,7 +619,7 @@
     static int bNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromBNodeId(int id) {
+    static Node nodeFromBNodeId(int id) {
       return Node((id << 1) + 1);
     }
     int maxBNodeId() const {
@@ -665,7 +665,8 @@
   };
 
 
-  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
+  typedef BpUGraphExtender<BidirBpUGraphExtender<FullBpUGraphBase> > 
+  ExtendedFullBpUGraphBase;
 
 
   /// \ingroup graphs
diff -r 67af33b34394 -r 06faf3f06d67 lemon/list_graph.h
--- a/lemon/list_graph.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/list_graph.h	Tue Oct 03 11:46:39 2006 +0000
@@ -1270,7 +1270,7 @@
     static int aNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromANodeId(int id) {
+    static Node nodeFromANodeId(int id) {
       return Node(id << 1);
     }
     int maxANodeId() const {
@@ -1280,7 +1280,7 @@
     static int bNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromBNodeId(int id) {
+    static Node nodeFromBNodeId(int id) {
       return Node((id << 1) + 1);
     }
     int maxBNodeId() const {
@@ -1482,7 +1482,8 @@
   };
 
 
-  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
+  typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> > 
+  ExtendedListBpUGraphBase;
 
   /// \ingroup graphs
   ///
diff -r 67af33b34394 -r 06faf3f06d67 lemon/smart_graph.h
--- a/lemon/smart_graph.h	Tue Oct 03 11:24:41 2006 +0000
+++ b/lemon/smart_graph.h	Tue Oct 03 11:46:39 2006 +0000
@@ -662,7 +662,7 @@
     static int aNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromANodeId(int id) {
+    static Node nodeFromANodeId(int id) {
       return Node(id << 1);
     }
     int maxANodeId() const {
@@ -672,7 +672,7 @@
     static int bNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromBNodeId(int id) {
+    static Node nodeFromBNodeId(int id) {
       return Node((id << 1) + 1);
     }
     int maxBNodeId() const {
@@ -743,7 +743,8 @@
   };
 
 
-  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
+  typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
+  ExtendedSmartBpUGraphBase;
 
   /// \ingroup graphs
   ///
@@ -829,13 +830,13 @@
 	edges.pop_back();
       }
       while(s.anode_num<aNodes.size()) {
-        Node node = fromANodeId(aNodes.size() - 1);
+        Node node = nodeFromANodeId(aNodes.size() - 1);
 	Parent::getNotifier(ANode()).erase(node);
 	Parent::getNotifier(Node()).erase(node);
 	aNodes.pop_back();
       }
       while(s.bnode_num<bNodes.size()) {
-        Node node = fromBNodeId(bNodes.size() - 1);
+        Node node = nodeFromBNodeId(bNodes.size() - 1);
 	Parent::getNotifier(BNode()).erase(node);
 	Parent::getNotifier(Node()).erase(node);
 	bNodes.pop_back();
diff -r 67af33b34394 -r 06faf3f06d67 test/Makefile.am
--- a/test/Makefile.am	Tue Oct 03 11:24:41 2006 +0000
+++ b/test/Makefile.am	Tue Oct 03 11:46:39 2006 +0000
@@ -15,6 +15,7 @@
 	test/arborescence_test \
 	test/bfs_test \
 	test/bipartite_matching_test \
+	test/bpugraph_test \
 	test/counter_test \
 	test/dfs_test \
 	test/dijkstra_test \
@@ -57,6 +58,7 @@
 test_arborescence_test_SOURCES = test/arborescence_test.cc
 test_bfs_test_SOURCES = test/bfs_test.cc
 test_bipartite_matching_test_SOURCES = test/bipartite_matching_test.cc
+test_bpugraph_test_SOURCES = test/bpugraph_test.cc
 test_counter_test_SOURCES = test/counter_test.cc
 test_dfs_test_SOURCES = test/dfs_test.cc
 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
diff -r 67af33b34394 -r 06faf3f06d67 test/bpugraph_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/bpugraph_test.cc	Tue Oct 03 11:46:39 2006 +0000
@@ -0,0 +1,146 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <lemon/concept/bpugraph.h>
+#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/full_graph.h>
+#include <lemon/grid_ugraph.h>
+
+#include <lemon/graph_utils.h>
+
+#include "test_tools.h"
+
+
+using namespace lemon;
+using namespace lemon::concept;
+
+void check_concepts() {
+
+  { // checking graph components
+    checkConcept<BaseBpUGraphComponent, BaseBpUGraphComponent >();
+
+    checkConcept<IDableBpUGraphComponent<>, 
+      IDableBpUGraphComponent<> >();
+
+    checkConcept<IterableBpUGraphComponent<>, 
+      IterableBpUGraphComponent<> >();
+
+    checkConcept<MappableBpUGraphComponent<>, 
+      MappableBpUGraphComponent<> >();
+
+  }
+  {
+    checkConcept<BpUGraph, ListBpUGraph>();
+    
+    checkConcept<BpUGraph, SmartBpUGraph>();
+    
+    checkConcept<BpUGraph, FullBpUGraph>();
+    
+    checkConcept<BpUGraph, BpUGraph>();
+    
+  }
+}
+
+template <typename Graph>
+void check_item_counts(Graph &g, int an, int bn, int e) {
+  int nn = 0;
+  for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
+    ++nn;
+  }
+
+  check(nn == an + bn, "Wrong node number.");
+  check(countNodes(g) == an + bn, "Wrong node number.");
+
+  int ann = 0;
+  for (typename Graph::ANodeIt it(g); it != INVALID; ++it) {
+    ++ann;
+  }
+
+  check(ann == an, "Wrong node number.");
+  check(countANodes(g) == an, "Wrong node number.");
+
+  int bnn = 0;
+  for (typename Graph::BNodeIt it(g); it != INVALID; ++it) {
+    ++bnn;
+  }
+
+  check(bnn == bn, "Wrong node number.");
+  check(countBNodes(g) == bn, "Wrong node number.");
+
+  int ee = 0;
+  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
+    ++ee;
+  }
+
+  check(ee == 2*e, "Wrong edge number.");
+  check(countEdges(g) == 2*e, "Wrong edge number.");
+
+  int uee = 0;
+  for (typename Graph::UEdgeIt it(g); it != INVALID; ++it) {
+    ++uee;
+  }
+
+  check(uee == e, "Wrong uedge number.");
+  check(countUEdges(g) == e, "Wrong uedge number.");
+}
+
+template <typename Graph>
+void check_graph() {
+
+  typedef typename Graph::Node Node;
+  typedef typename Graph::UEdge UEdge;
+  typedef typename Graph::Edge Edge;
+  typedef typename Graph::NodeIt NodeIt;
+  typedef typename Graph::UEdgeIt UEdgeIt;
+  typedef typename Graph::EdgeIt EdgeIt;
+
+  Graph g;
+
+  check_item_counts(g, 0, 0, 0);
+
+  Node
+    an1 = g.addANode(),
+    an2 = g.addANode(),
+    an3 = g.addANode(),
+    bn1 = g.addBNode(),
+    bn2 = g.addBNode();
+
+  UEdge
+    e1 = g.addEdge(an1, bn1),
+    e2 = g.addEdge(an2, bn1),
+    e3 = g.addEdge(an3, bn2);
+
+  check_item_counts(g, 3, 2, 3);
+}
+
+int main() {
+  check_concepts();
+
+  check_graph<ListBpUGraph>();
+  check_graph<SmartBpUGraph>();
+
+  {
+    FullBpUGraph g(5, 10);
+    check_item_counts(g, 5, 10, 50);
+  }
+
+  std::cout << __FILE__ ": All tests passed.\n";
+
+  return 0;
+}
diff -r 67af33b34394 -r 06faf3f06d67 test/graph_adaptor_test.cc
--- a/test/graph_adaptor_test.cc	Tue Oct 03 11:24:41 2006 +0000
+++ b/test/graph_adaptor_test.cc	Tue Oct 03 11:46:39 2006 +0000
@@ -22,11 +22,13 @@
 #include<lemon/smart_graph.h>
 #include<lemon/concept/graph.h>
 #include<lemon/concept/ugraph.h>
+#include<lemon/concept/bpugraph.h>
 
 #include<lemon/list_graph.h>
 #include<lemon/full_graph.h>
 #include<lemon/graph_adaptor.h>
 #include<lemon/ugraph_adaptor.h>
+#include<lemon/bpugraph_adaptor.h>
 
 #include"test/test_tools.h"
 #include"test/graph_test.h"
@@ -75,6 +77,11 @@
 
     checkConcept<Graph, DirUGraphAdaptor<UGraph, 
       UGraph::UEdgeMap<bool> > >();
+
+    checkConcept<BpUGraph, BpUGraphAdaptor<BpUGraph> >();
+
+    checkConcept<BpUGraph, SwapBpUGraphAdaptor<BpUGraph> >();
+
   }
   std::cout << __FILE__ ": All tests passed.\n";
 
diff -r 67af33b34394 -r 06faf3f06d67 test/graph_test.cc
--- a/test/graph_test.cc	Tue Oct 03 11:24:41 2006 +0000
+++ b/test/graph_test.cc	Tue Oct 03 11:46:39 2006 +0000
@@ -38,9 +38,6 @@
   { // checking graph components
     checkConcept<BaseGraphComponent, BaseGraphComponent >();
 
-    checkConcept<BaseIterableGraphComponent<>, 
-      BaseIterableGraphComponent<> >();
-
     checkConcept<IDableGraphComponent<>, 
       IDableGraphComponent<> >();
 
diff -r 67af33b34394 -r 06faf3f06d67 test/ugraph_test.cc
--- a/test/ugraph_test.cc	Tue Oct 03 11:24:41 2006 +0000
+++ b/test/ugraph_test.cc	Tue Oct 03 11:46:39 2006 +0000
@@ -36,9 +36,6 @@
   { // checking graph components
     checkConcept<BaseUGraphComponent, BaseUGraphComponent >();
 
-    checkConcept<BaseIterableUGraphComponent<>, 
-      BaseIterableUGraphComponent<> >();
-
     checkConcept<IDableUGraphComponent<>, 
       IDableUGraphComponent<> >();