# HG changeset patch
# User deba
# Date 1132595280 0
# Node ID 22099ef840d750e510d6c77617696769e0d988ea
# Parent  fd82adfbe905d55c0e1a8a4fbf987b5e2a36502c
Undir Bipartite Graph/Full and Smart/ without concept, doc and concept
checking

diff -r fd82adfbe905 -r 22099ef840d7 lemon/bits/alteration_notifier.h
--- a/lemon/bits/alteration_notifier.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/bits/alteration_notifier.h	Mon Nov 21 17:48:00 2005 +0000
@@ -439,6 +439,67 @@
       undir_edge_notifier.clear();
     }
   };
+
+
+  template <typename _Base>
+  class AlterableUndirBipartiteGraphExtender : public _Base {
+  public:
+
+    typedef _Base Parent;
+    typedef AlterableUndirBipartiteGraphExtender Graph;
+  
+    typedef typename Parent::Node Node;
+    typedef typename Parent::LowerNode LowerNode;
+    typedef typename Parent::UpperNode UpperNode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
+  
+  
+    typedef AlterationNotifier<Node> NodeNotifier;
+    typedef AlterationNotifier<LowerNode> LowerNodeNotifier;
+    typedef AlterationNotifier<UpperNode> UpperNodeNotifier;
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
+
+  protected:
+
+    mutable NodeNotifier nodeNotifier;
+    mutable LowerNodeNotifier lowerNodeNotifier;
+    mutable UpperNodeNotifier upperNodeNotifier;
+    mutable EdgeNotifier edgeNotifier;
+    mutable UndirEdgeNotifier undirEdgeNotifier;
+
+  public:
+
+    NodeNotifier& getNotifier(Node) const {
+      return nodeNotifier;
+    }
+
+    LowerNodeNotifier& getNotifier(LowerNode) const {
+      return lowerNodeNotifier;
+    }
+
+    UpperNodeNotifier& getNotifier(UpperNode) const {
+      return upperNodeNotifier;
+    }
+
+    EdgeNotifier& getNotifier(Edge) const {
+      return edgeNotifier;
+    }
+
+    UndirEdgeNotifier& getNotifier(UndirEdge) const {
+      return undirEdgeNotifier;
+    }
+
+    ~AlterableUndirBipartiteGraphExtender() {
+      nodeNotifier.clear();
+      lowerNodeNotifier.clear();
+      upperNodeNotifier.clear();
+      edgeNotifier.clear();
+      undirEdgeNotifier.clear();
+    }
+
+  };
   
 /// @}
   
diff -r fd82adfbe905 -r 22099ef840d7 lemon/bits/clearable_graph_extender.h
--- a/lemon/bits/clearable_graph_extender.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/bits/clearable_graph_extender.h	Mon Nov 21 17:48:00 2005 +0000
@@ -44,6 +44,31 @@
 
   };
 
+
+  template <typename _Base>
+  class ClearableUndirBipartiteGraphExtender : public _Base {
+  public:
+
+    typedef _Base Parent;
+    typedef ClearableUndirBipartiteGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::LowerNode LowerNode;
+    typedef typename Parent::UpperNode UpperNode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    void clear() {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UndirEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      Parent::getNotifier(LowerNode()).clear();
+      Parent::getNotifier(UpperNode()).clear();
+      Parent::clear();
+    }
+
+  };
+
 }
 
 #endif
diff -r fd82adfbe905 -r 22099ef840d7 lemon/bits/default_map.h
--- a/lemon/bits/default_map.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/bits/default_map.h	Mon Nov 21 17:48:00 2005 +0000
@@ -266,6 +266,272 @@
 
   };
 
+
+  template <typename _Base>
+  class MappableUndirBipartiteGraphExtender : public _Base {
+  public:
+
+    typedef _Base Parent;
+    typedef MappableUndirBipartiteGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UpperNode UpperNode;
+    typedef typename Parent::LowerNode LowerNode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
+    
+    template <typename _Value>
+    class UpperNodeMap 
+      : public IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > {
+    public:
+      typedef MappableUndirBipartiteGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > 
+      Parent;
+    
+      UpperNodeMap(const Graph& _g) 
+	: Parent(_g) {}
+      UpperNodeMap(const Graph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+    
+      UpperNodeMap& operator=(const UpperNodeMap& cmap) {
+	return operator=<UpperNodeMap>(cmap);
+      }
+    
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concept and could be indiced by the current item set of
+      /// the UpperNodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename CMap>
+      UpperNodeMap& operator=(const CMap& cmap) {
+	checkConcept<concept::ReadMap<UpperNode, _Value>, CMap>();
+	const typename Parent::Graph* graph = Parent::getGraph();
+	UpperNode it;
+	for (graph->first(it); it != INVALID; graph->next(it)) {
+	  Parent::set(it, cmap[it]);
+	}
+	return *this;
+      }
+    
+    };
+
+    template <typename _Value>
+    class LowerNodeMap 
+      : public IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > {
+    public:
+      typedef MappableUndirBipartiteGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > 
+      Parent;
+    
+      LowerNodeMap(const Graph& _g) 
+	: Parent(_g) {}
+      LowerNodeMap(const Graph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+    
+      LowerNodeMap& operator=(const LowerNodeMap& cmap) {
+	return operator=<LowerNodeMap>(cmap);
+      }
+    
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concept and could be indiced by the current item set of
+      /// the LowerNodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename CMap>
+      LowerNodeMap& operator=(const CMap& cmap) {
+	checkConcept<concept::ReadMap<LowerNode, _Value>, CMap>();
+	const typename Parent::Graph* graph = Parent::getGraph();
+	LowerNode it;
+	for (graph->first(it); it != INVALID; graph->next(it)) {
+	  Parent::set(it, cmap[it]);
+	}
+	return *this;
+      }
+    
+    };
+
+  protected:
+
+    template <typename _Value>
+    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
+    public:
+      typedef MappableUndirBipartiteGraphExtender Graph;
+
+      typedef Node Key;
+      typedef _Value Value;
+
+      /// The reference type of the map;
+      typedef typename LowerNodeMap<_Value>::Reference Reference;
+      /// The pointer type of the map;
+      typedef typename LowerNodeMap<_Value>::Pointer Pointer;
+      
+      /// The const value type of the map.
+      typedef const Value ConstValue;
+      /// The const reference type of the map;
+      typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;
+      /// The pointer type of the map;
+      typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;
+
+      typedef True ReferenceMapTag;
+
+      NodeMapBase(const Graph& _g) 
+	: graph(&_g), lowerMap(_g), upperMap(_g) {
+	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
+      }
+      NodeMapBase(const Graph& _g, const _Value& _v) 
+	: graph(&_g), lowerMap(_g, _v), 
+	  upperMap(_g, _v) {
+	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
+      }
+
+      virtual ~NodeMapBase() {      
+	if (Parent::NodeNotifier::ObserverBase::attached()) {
+	  Parent::NodeNotifier::ObserverBase::detach();
+	}
+      }
+    
+      ConstReference operator[](const Key& node) const {
+	if (Parent::upper(node)) {
+	  return upperMap[node];
+	} else {
+	  return lowerMap[node];
+	}
+      } 
+
+      Reference operator[](const Key& node) {
+	if (Parent::upper(node)) {
+	  return upperMap[node];
+	} else {
+	  return lowerMap[node];
+	}
+      }
+
+      void set(const Key& node, const Value& value) {
+	if (Parent::upper(node)) {
+	  upperMap.set(node, value);
+	} else {
+	  lowerMap.set(node, value);
+	}
+      }
+
+    protected:
+      
+      virtual void add(const Node&) {}
+      virtual void erase(const Node&) {}
+      virtual void clear() {}
+      virtual void build() {}
+
+      const Graph* getGraph() const { return graph; }
+      
+    private:
+      const Graph* graph;
+      LowerNodeMap<_Value> lowerMap;
+      UpperNodeMap<_Value> upperMap;
+    };
+    
+  public:
+
+    template <typename _Value>
+    class NodeMap 
+      : public IterableMapExtender<NodeMapBase<_Value> > {
+    public:
+      typedef MappableUndirBipartiteGraphExtender Graph;
+      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
+    
+      NodeMap(const Graph& _g) 
+	: Parent(_g) {}
+      NodeMap(const Graph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+    
+      NodeMap& operator=(const NodeMap& cmap) {
+	return operator=<NodeMap>(cmap);
+      }
+    
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concept and could be indiced by the current item set of
+      /// the NodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename CMap>
+      NodeMap& operator=(const CMap& cmap) {
+	checkConcept<concept::ReadMap<Node, _Value>, CMap>();
+	const typename Parent::Graph* graph = Parent::getGraph();
+	Node it;
+	for (graph->first(it); it != INVALID; graph->next(it)) {
+	  Parent::set(it, cmap[it]);
+	}
+	return *this;
+      }
+    
+    };
+
+
+
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+    public:
+      typedef MappableUndirBipartiteGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+    
+      EdgeMap(const Graph& _g) 
+	: Parent(_g) {}
+      EdgeMap(const Graph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+    
+      EdgeMap& operator=(const EdgeMap& cmap) {
+	return operator=<EdgeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
+	const typename Parent::Graph* graph = Parent::getGraph();
+	Edge it;
+	for (graph->first(it); it != INVALID; graph->next(it)) {
+	  Parent::set(it, cmap[it]);
+	}
+	return *this;
+      }
+    };
+
+    template <typename _Value>
+    class UndirEdgeMap 
+      : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
+    public:
+      typedef MappableUndirBipartiteGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > 
+      Parent;
+    
+      UndirEdgeMap(const Graph& _g) 
+	: Parent(_g) {}
+      UndirEdgeMap(const Graph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+    
+      UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
+	return operator=<UndirEdgeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      UndirEdgeMap& operator=(const CMap& cmap) {
+	checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
+	const typename Parent::Graph* graph = Parent::getGraph();
+	UndirEdge it;
+	for (graph->first(it); it != INVALID; graph->next(it)) {
+	  Parent::set(it, cmap[it]);
+	}
+	return *this;
+      }
+    };
+  
+  };
+
 }
 
 #endif
diff -r fd82adfbe905 -r 22099ef840d7 lemon/bits/extendable_graph_extender.h
--- a/lemon/bits/extendable_graph_extender.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/bits/extendable_graph_extender.h	Mon Nov 21 17:48:00 2005 +0000
@@ -60,6 +60,48 @@
 
   };
 
+
+  template <typename _Base>
+  class ExtendableUndirBipartiteGraphExtender : public _Base {
+  public:
+
+    typedef _Base Parent;
+    typedef ExtendableUndirBipartiteGraphExtender Graph;
+  
+    typedef typename Parent::Node Node;
+    typedef typename Parent::LowerNode LowerNode;
+    typedef typename Parent::UpperNode UpperNode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
+  
+    Node addUpperNode() {
+      Node node = Parent::addUpperNode();
+      Parent::getNotifier(UpperNode()).add(node);
+      Parent::getNotifier(Node()).add(node);
+      return node;
+    }
+
+    Node addLowerNode() {
+      Node node = Parent::addLowerNode();
+      Parent::getNotifier(LowerNode()).add(node);
+      Parent::getNotifier(Node()).add(node);
+      return node;
+    }
+  
+    UndirEdge addEdge(const Node& source, const Node& target) {
+      UndirEdge undiredge = Parent::addEdge(source, target);
+      Parent::getNotifier(UndirEdge()).add(undiredge);
+    
+      std::vector<Edge> edges;
+      edges.push_back(Parent::direct(undiredge, true));
+      edges.push_back(Parent::direct(undiredge, false));
+      Parent::getNotifier(Edge()).add(edges);
+    
+      return undiredge;
+    }
+
+  };
+
 }
 
 #endif
diff -r fd82adfbe905 -r 22099ef840d7 lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/bits/graph_extender.h	Mon Nov 21 17:48:00 2005 +0000
@@ -19,6 +19,7 @@
 #define LEMON_GRAPH_EXTENDER_H
 
 #include <lemon/invalid.h>
+#include <lemon/error.h>
 
 namespace lemon {
 
@@ -376,6 +377,248 @@
 
   };
 
+
+  template <typename _Base>
+  class UndirBipartiteGraphExtender : public _Base {
+  public:
+    typedef _Base Parent;
+    typedef UndirBipartiteGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge UndirEdge;
+
+    using Parent::first;
+    using Parent::next;
+
+    using Parent::id;
+
+    Node source(const UndirEdge& edge) const {
+      return upperNode(edge);
+    }
+    Node target(const UndirEdge& edge) const {
+      return lowerNode(edge);
+    }
+
+    void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {
+      if (Parent::upper(node)) {
+	Parent::firstDown(edge, node);
+	direction = true;
+      } else {
+	Parent::firstUp(edge, node);
+	direction = static_cast<UndirEdge&>(edge) == INVALID;
+      }
+    }
+    void nextInc(UndirEdge& edge, bool& direction) const {
+      if (direction) {
+	Parent::nextDown(edge);
+      } else {
+	Parent::nextUp(edge);
+	if (edge == INVALID) direction = true;
+      }
+    }
+
+    int maxUndirEdgeId() const {
+      return Parent::maxEdgeId();
+    }
+
+    UndirEdge undirEdgeFromId(int id) const {
+      return Parent::edgeFromId(id);
+    }
+
+    class Edge : public UndirEdge {
+      friend class UndirBipartiteGraphExtender;
+    protected:
+      bool forward;
+
+      Edge(const UndirEdge& edge, bool _forward)
+	: UndirEdge(edge), forward(_forward) {}
+
+    public:
+      Edge() {}
+      Edge (Invalid) : UndirEdge(INVALID), forward(true) {}
+      bool operator==(const Edge& i) const {
+	return UndirEdge::operator==(i) && forward == i.forward;
+      }
+      bool operator!=(const Edge& i) const {
+	return UndirEdge::operator!=(i) || forward != i.forward;
+      }
+      bool operator<(const Edge& i) const {
+	return UndirEdge::operator<(i) || 
+	  (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));
+      }
+    };
+
+    void first(Edge& edge) const {
+      Parent::first(static_cast<UndirEdge&>(edge));
+      edge.forward = true;
+    }
+
+    void next(Edge& edge) const {
+      if (!edge.forward) {
+	Parent::next(static_cast<UndirEdge&>(edge));
+      }
+      edge.forward = !edge.forward;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (Parent::upper(node)) {
+	Parent::firstDown(edge, node);
+	edge.forward = true;
+      } else {
+	Parent::firstUp(edge, node);
+	edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+      }
+    }
+    void nextOut(Edge& edge) const {
+      if (edge.forward) {
+	Parent::nextDown(edge);
+      } else {
+	Parent::nextUp(edge);
+	if (edge == INVALID) {
+	  edge.forward = true;
+	}	
+      }
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (Parent::lower(node)) {
+	Parent::firstUp(edge, node);
+	edge.forward = true;	
+      } else {
+	Parent::firstDown(edge, node);
+	edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+      }
+    }
+    void nextIn(Edge& edge) const {
+      if (edge.forward) {
+	Parent::nextUp(edge);
+      } else {
+	Parent::nextDown(edge);
+	if (edge == INVALID) {
+	  edge.forward = true;
+	}	
+      }
+    }
+
+    Node source(const Edge& edge) const {
+      return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);
+    }
+    Node target(const Edge& edge) const {
+      return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);
+    }
+
+    bool direction(const Edge& edge) const {
+      return edge.forward;
+    }
+
+    Edge direct(const UndirEdge& edge, const Node& node) const {
+      return Edge(edge, node == Parent::source(edge));
+    }
+
+    Edge direct(const UndirEdge& edge, bool direction) const {
+      return Edge(edge, direction);
+    }
+
+    Node oppositeNode(const UndirEdge& edge, const Node& node) const {
+      return source(edge) == node ? 
+	target(edge) : source(edge);
+    }
+
+    Edge oppositeEdge(const Edge& edge) const {
+      return Edge(edge, !edge.forward);
+    }
+
+    int id(const Edge& edge) const {
+      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
+    }
+    Edge edgeFromId(int id) const {
+      return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
+    }
+    int maxEdgeId() const {
+      return (Parent::maxId(UndirEdge()) << 1) + 1;
+    }
+
+    class UpperNode : public Node {
+      friend class UndirBipartiteGraphExtender;
+    public:
+      UpperNode() {}
+      UpperNode(const Node& node) : Node(node) {
+	LEMON_ASSERT(Parent::upper(node) || node == INVALID, 
+		     typename Parent::NodeSetError());
+      }
+      UpperNode(Invalid) : Node(INVALID) {}
+    };
+
+    void first(UpperNode& node) const {
+      Parent::firstUpper(static_cast<Node&>(node));
+    }
+    void next(UpperNode& node) const {
+      Parent::nextUpper(static_cast<Node&>(node));
+    }
+
+    int id(const UpperNode& node) const {
+      return Parent::upperId(node);
+    }
+
+    class LowerNode : public Node {
+      friend class UndirBipartiteGraphExtender;
+    public:
+      LowerNode() {}
+      LowerNode(const Node& node) : Node(node) {
+	LEMON_ASSERT(Parent::lower(node) || node == INVALID,
+		     typename Parent::NodeSetError());
+      }
+      LowerNode(Invalid) : Node(INVALID) {}
+    };
+
+    void first(LowerNode& node) const {
+      Parent::firstLower(static_cast<Node&>(node));
+    }
+    void next(LowerNode& node) const {
+      Parent::nextLower(static_cast<Node&>(node));
+    }
+  
+    int id(const LowerNode& node) const {
+      return Parent::upperId(node);
+    }
+
+
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+    int maxId(LowerNode) const {
+      return Parent::maxLowerId();
+    }
+    int maxId(UpperNode) const {
+      return Parent::maxUpperId();
+    }
+    int maxId(Edge) const {
+      return maxEdgeId();
+    }
+    int maxId(UndirEdge) const {
+      return maxUndirEdgeId();
+    }
+
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+    UpperNode fromId(int id, UpperNode) const {
+      return Parent::fromUpperId(id);
+    }
+    LowerNode fromId(int id, LowerNode) const {
+      return Parent::fromLowerId(id);
+    }
+    Edge fromId(int id, Edge) const {
+      return edgeFromId(id);
+    }
+    UndirEdge fromId(int id, UndirEdge) const {
+      return undirEdgeFromId(id);
+    }
+
+  };
+
 }
 
 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H
diff -r fd82adfbe905 -r 22099ef840d7 lemon/bits/iterable_graph_extender.h
--- a/lemon/bits/iterable_graph_extender.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/bits/iterable_graph_extender.h	Mon Nov 21 17:48:00 2005 +0000
@@ -267,6 +267,250 @@
     }
 
   };
+
+
+  template <typename _Base>
+  class IterableUndirBipartiteGraphExtender : public _Base {
+  public:
+    typedef _Base Parent;
+    typedef IterableUndirBipartiteGraphExtender Graph;
+   
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UpperNode UpperNode;
+    typedef typename Parent::LowerNode LowerNode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
+  
+    class NodeIt : public Node { 
+      const Graph* graph;
+    public:
+    
+      NodeIt() { }
+    
+      NodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
+	graph->first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node) 
+	: Node(node), graph(&_graph) { }
+    
+      NodeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+    class UpperNodeIt : public Node { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+    public:
+    
+      UpperNodeIt() { }
+    
+      UpperNodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {
+	graph->firstUpper(static_cast<Node&>(*this));
+      }
+
+      UpperNodeIt(const Graph& _graph, const Node& node) 
+	: Node(node), graph(&_graph) {}
+    
+      UpperNodeIt& operator++() { 
+	graph->nextUpper(*this);
+	return *this; 
+      }
+    };
+
+    class LowerNodeIt : public Node { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+    public:
+    
+      LowerNodeIt() { }
+    
+      LowerNodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {
+	graph->firstLower(static_cast<Node&>(*this));
+      }
+
+      LowerNodeIt(const Graph& _graph, const Node& node) 
+	: Node(node), graph(&_graph) {}
+    
+      LowerNodeIt& operator++() { 
+	graph->nextLower(*this);
+	return *this; 
+      }
+    };
+
+    class EdgeIt : public Edge { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+    public:
+    
+      EdgeIt() { }
+    
+      EdgeIt(Invalid i) : Edge(INVALID) { }
+    
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
+	graph->first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& edge) 
+	: Edge(edge), graph(&_graph) { }
+    
+      EdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+    class UndirEdgeIt : public UndirEdge { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+    public:
+    
+      UndirEdgeIt() { }
+    
+      UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }
+    
+      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
+	graph->first(static_cast<UndirEdge&>(*this));
+      }
+
+      UndirEdgeIt(const Graph& _graph, const UndirEdge& edge) 
+	: UndirEdge(edge), graph(&_graph) { }
+    
+      UndirEdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+    };
+
+    class OutEdgeIt : public Edge { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+    public:
+    
+      OutEdgeIt() { }
+    
+      OutEdgeIt(Invalid i) : Edge(i) { }
+    
+      OutEdgeIt(const Graph& _graph, const Node& node) 
+	: graph(&_graph) {
+	graph->firstOut(*this, node);
+      }
+    
+      OutEdgeIt(const Graph& _graph, const Edge& edge) 
+	: Edge(edge), graph(&_graph) {}
+    
+      OutEdgeIt& operator++() { 
+	graph->nextOut(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class InEdgeIt : public Edge { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+    public:
+    
+      InEdgeIt() { }
+    
+      InEdgeIt(Invalid i) : Edge(i) { }
+    
+      InEdgeIt(const Graph& _graph, const Node& node) 
+	: graph(&_graph) {
+	graph->firstIn(*this, node);
+      }
+    
+      InEdgeIt(const Graph& _graph, const Edge& edge) : 
+	Edge(edge), graph(&_graph) {}
+    
+      InEdgeIt& operator++() { 
+	graph->nextIn(*this);
+	return *this; 
+      }
+
+    };
+  
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutEdgeIt &e) const {
+      return Parent::source((Edge&)e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the target in this case) of the
+    /// iterator
+    Node runningNode(const OutEdgeIt &e) const {
+      return Parent::target((Edge&)e);
+    }
+  
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InEdgeIt &e) const {
+      return Parent::target((Edge&)e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the source in this case) of the
+    /// iterator
+    Node runningNode(const InEdgeIt &e) const {
+      return Parent::source((Edge&)e);
+    }
+  
+    class IncEdgeIt : public Parent::UndirEdge { 
+      friend class IterableUndirBipartiteGraphExtender;
+      const Graph* graph;
+      bool direction;
+    public:
+    
+      IncEdgeIt() { }
+    
+      IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }
+    
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+	graph->firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
+	: graph(&_graph), UndirEdge(ue) {
+	direction = (graph->source(ue) == n);
+      }
+
+      IncEdgeIt& operator++() {
+	graph->nextInc(*this, direction);
+	return *this; 
+      }
+    };
+  
+
+    /// Base node of the iterator
+    ///
+    /// Returns the base node of the iterator
+    Node baseNode(const IncEdgeIt &e) const {
+      return e.direction ? source(e) : target(e);
+    }
+
+    /// Running node of the iterator
+    ///
+    /// Returns the running node of the iterator
+    Node runningNode(const IncEdgeIt &e) const {
+      return e.direction ? target(e) : source(e);
+    }
+  
+  };
+
 }
 
 #endif // LEMON_GRAPH_EXTENDER_H
diff -r fd82adfbe905 -r 22099ef840d7 lemon/full_graph.h
--- a/lemon/full_graph.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/full_graph.h	Mon Nov 21 17:48:00 2005 +0000
@@ -402,6 +402,196 @@
     UndirFullGraph(int n) { construct(n); }
   };
 
+
+  class FullUndirBipartiteGraphBase {
+  protected:
+
+    int _upperNodeNum;
+    int _lowerNodeNum;
+
+    int _edgeNum;
+
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+	return "lemon::FullUndirBipartiteGraph::NodeSetError";
+      }
+    };
+  
+    class Node {
+      friend class FullUndirBipartiteGraphBase;
+    protected:
+      int id;
+
+      Node(int _id) : id(_id) {}
+    public:
+      Node() {}
+      Node(Invalid) { id = -1; }
+      bool operator==(const Node i) const {return id==i.id;}
+      bool operator!=(const Node i) const {return id!=i.id;}
+      bool operator<(const Node i) const {return id<i.id;}
+    };
+
+    class Edge {
+      friend class FullUndirBipartiteGraphBase;
+    protected:
+      int id;
+
+      Edge(int _id) { id = _id;}
+    public:
+      Edge() {}
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge i) const {return id==i.id;}
+      bool operator!=(const Edge i) const {return id!=i.id;}
+      bool operator<(const Edge i) const {return id<i.id;}
+    };
+
+    void construct(int upperNodeNum, int lowerNodeNum) {
+      _upperNodeNum = upperNodeNum;
+      _lowerNodeNum = lowerNodeNum;
+      _edgeNum = upperNodeNum * lowerNodeNum;
+    }
+
+    void firstUpper(Node& node) const {
+      node.id = 2 * _upperNodeNum - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextUpper(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    void firstLower(Node& node) const {
+      node.id = 2 * _lowerNodeNum - 1;
+    }
+    void nextLower(Node& node) const {
+      node.id -= 2;
+    }
+
+    void first(Node& node) const {
+      if (_upperNodeNum > 0) {
+	node.id = 2 * _upperNodeNum - 2;
+      } else {
+	node.id = 2 * _lowerNodeNum - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+	node.id = 2 * _lowerNodeNum - 1;
+      }
+    }
+  
+    void first(Edge& edge) const {
+      edge.id = _edgeNum - 1;
+    }
+    void next(Edge& edge) const {
+      --edge.id;
+    }
+
+    void firstDown(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = (node.id >> 1) * _lowerNodeNum;
+    }
+    void nextDown(Edge& edge) const {
+      ++(edge.id);
+      if (edge.id % _lowerNodeNum == 0) edge.id = -1;
+    }
+
+    void firstUp(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = (node.id >> 1);
+    }
+    void nextUp(Edge& edge) const {
+      edge.id += _lowerNodeNum;
+      if (edge.id >= _edgeNum) edge.id = -1;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return _upperNodeNum > _lowerNodeNum ? 
+	_upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
+    }
+  
+    static int id(const Edge& edge) {
+      return edge.id;
+    }
+    static Edge edgeFromId(int id) {
+      return Edge(id);
+    }
+    int maxEdgeId() const {
+      return _edgeNum - 1;
+    }
+  
+    static int upperId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromUpperId(int id, Node) {
+      return Node(id << 1);
+    }
+    int maxUpperId() const {
+      return _upperNodeNum;
+    }
+
+    static int lowerId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromLowerId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxLowerId() const {
+      return _lowerNodeNum;
+    }
+
+    Node upperNode(const Edge& edge) const {
+      return Node((edge.id / _lowerNodeNum) << 1);
+    }
+    Node lowerNode(const Edge& edge) const {
+      return Node(((edge.id % _lowerNodeNum) << 1) + 1);
+    }
+
+    static bool upper(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool lower(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    static Node upperNode(int index) {
+      return Node(index << 1);
+    }
+
+    static Node lowerNode(int index) {
+      return Node((index << 1) + 1);
+    }
+
+  };
+
+
+  typedef MappableUndirBipartiteGraphExtender<
+    IterableUndirBipartiteGraphExtender<
+    AlterableUndirBipartiteGraphExtender<
+    UndirBipartiteGraphExtender <
+    FullUndirBipartiteGraphBase> > > >
+  ExtendedFullUndirBipartiteGraphBase;
+
+
+  class FullUndirBipartiteGraph : 
+    public ExtendedFullUndirBipartiteGraphBase {
+  public:
+    typedef ExtendedFullUndirBipartiteGraphBase Parent;
+    FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
+      Parent::construct(upperNodeNum, lowerNodeNum);
+    }
+  };
+
 } //namespace lemon
 
 
diff -r fd82adfbe905 -r 22099ef840d7 lemon/smart_graph.h
--- a/lemon/smart_graph.h	Mon Nov 21 12:07:05 2005 +0000
+++ b/lemon/smart_graph.h	Mon Nov 21 17:48:00 2005 +0000
@@ -33,6 +33,7 @@
 #include <lemon/bits/graph_extender.h>
 
 #include <lemon/utility.h>
+#include <lemon/error.h>
 
 namespace lemon {
 
@@ -374,6 +375,228 @@
   class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
   };
 
+
+  class SmartUndirBipartiteGraphBase {
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+	return "lemon::FullUndirBipartiteGraph::NodeSetError";
+      }
+    };
+
+  protected:
+
+    struct NodeT {
+      int first;
+      NodeT() {}
+      NodeT(int _first) : first(_first) {}
+    };
+
+    struct EdgeT {
+      int upper, next_down;
+      int lower, next_up;
+    };
+
+    std::vector<NodeT> upperNodes;
+    std::vector<NodeT> lowerNodes;
+
+    std::vector<EdgeT> edges;
+
+  public:
+  
+    class Node {
+      friend class SmartUndirBipartiteGraphBase;
+    protected:
+      int id;
+
+      Node(int _id) : id(_id) {}
+    public:
+      Node() {}
+      Node(Invalid) { id = -1; }
+      bool operator==(const Node i) const {return id==i.id;}
+      bool operator!=(const Node i) const {return id!=i.id;}
+      bool operator<(const Node i) const {return id<i.id;}
+    };
+
+    class Edge {
+      friend class SmartUndirBipartiteGraphBase;
+    protected:
+      int id;
+
+      Edge(int _id) { id = _id;}
+    public:
+      Edge() {}
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge i) const {return id==i.id;}
+      bool operator!=(const Edge i) const {return id!=i.id;}
+      bool operator<(const Edge i) const {return id<i.id;}
+    };
+
+    void firstUpper(Node& node) const {
+      node.id = 2 * upperNodes.size() - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextUpper(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    void firstLower(Node& node) const {
+      node.id = 2 * lowerNodes.size() - 1;
+    }
+    void nextLower(Node& node) const {
+      node.id -= 2;
+    }
+
+    void first(Node& node) const {
+      if (upperNodes.size() > 0) {
+	node.id = 2 * upperNodes.size() - 2;
+      } else {
+	node.id = 2 * lowerNodes.size() - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+	node.id = 2 * lowerNodes.size() - 1;
+      }
+    }
+  
+    void first(Edge& edge) const {
+      edge.id = edges.size() - 1;
+    }
+    void next(Edge& edge) const {
+      --edge.id;
+    }
+
+    void firstDown(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = upperNodes[node.id >> 1].first;
+    }
+    void nextDown(Edge& edge) const {
+      edge.id = edges[edge.id].next_down;
+    }
+
+    void firstUp(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = lowerNodes[node.id >> 1].first;
+    }
+    void nextUp(Edge& edge) const {
+      edge.id = edges[edge.id].next_up;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return upperNodes.size() > lowerNodes.size() ?
+	upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
+    }
+  
+    static int id(const Edge& edge) {
+      return edge.id;
+    }
+    static Edge edgeFromId(int id) {
+      return Edge(id);
+    }
+    int maxEdgeId() const {
+      return edges.size();
+    }
+  
+    static int upperId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromUpperId(int id, Node) {
+      return Node(id << 1);
+    }
+    int maxUpperId() const {
+      return upperNodes.size();
+    }
+
+    static int lowerId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromLowerId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxLowerId() const {
+      return lowerNodes.size();
+    }
+
+    Node upperNode(const Edge& edge) const {
+      return Node(edges[edge.id].upper);
+    }
+    Node lowerNode(const Edge& edge) const {
+      return Node(edges[edge.id].lower);
+    }
+
+    static bool upper(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool lower(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    Node addUpperNode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      upperNodes.push_back(nodeT);
+      return Node(upperNodes.size() * 2 - 2);
+    }
+
+    Node addLowerNode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      lowerNodes.push_back(nodeT);
+      return Node(lowerNodes.size() * 2 - 1);
+    }
+
+    Edge addEdge(const Node& source, const Node& target) {
+      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
+      EdgeT edgeT;
+      if ((source.id & 1) == 0) {
+	edgeT.upper = source.id;
+	edgeT.lower = target.id;
+      } else {
+	edgeT.upper = target.id;
+	edgeT.lower = source.id;
+      }
+      edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
+      upperNodes[edgeT.upper >> 1].first = edges.size();
+      edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
+      lowerNodes[edgeT.lower >> 1].first = edges.size();
+      edges.push_back(edgeT);
+      return Edge(edges.size() - 1);
+    }
+
+    void clear() {
+      upperNodes.clear();
+      lowerNodes.clear();
+      edges.clear();
+    }
+
+  };
+
+
+  typedef ClearableUndirBipartiteGraphExtender<
+    ExtendableUndirBipartiteGraphExtender<
+    MappableUndirBipartiteGraphExtender<
+    IterableUndirBipartiteGraphExtender<
+    AlterableUndirBipartiteGraphExtender<
+    UndirBipartiteGraphExtender <
+    SmartUndirBipartiteGraphBase> > > > > >
+  ExtendedSmartUndirBipartiteGraphBase;
+
+
+  class SmartUndirBipartiteGraph : 
+    public ExtendedSmartUndirBipartiteGraphBase {
+  };
+
   
   /// @}  
 } //namespace lemon