# HG changeset patch
# User deba
# Date 1151669745 0
# Node ID b6a68c15a6a3d6f929b60a55992a9e46982d85e0
# Parent  4cd528a30ec1274b6b0e266527396f26de8c2002
Revert splitted files

diff -r 4cd528a30ec1 -r b6a68c15a6a3 demo/coloring.cc
--- a/demo/coloring.cc	Fri Jun 30 12:14:36 2006 +0000
+++ b/demo/coloring.cc	Fri Jun 30 12:15:45 2006 +0000
@@ -29,7 +29,7 @@
 
 #include <iostream>
 
-#include <lemon/smart_ugraph.h>
+#include <lemon/smart_graph.h>
 #include <lemon/bucket_heap.h>
 #include <lemon/graph_reader.h>
 #include <lemon/graph_to_eps.h>
diff -r 4cd528a30ec1 -r b6a68c15a6a3 demo/strongly_connected_orientation.cc
--- a/demo/strongly_connected_orientation.cc	Fri Jun 30 12:14:36 2006 +0000
+++ b/demo/strongly_connected_orientation.cc	Fri Jun 30 12:15:45 2006 +0000
@@ -18,7 +18,7 @@
 
 #include <iostream>
 
-#include <lemon/smart_ugraph.h>
+#include <lemon/smart_graph.h>
 #include <lemon/graph_reader.h>
 #include <lemon/ugraph_adaptor.h>
 #include <lemon/graph_to_eps.h>
diff -r 4cd528a30ec1 -r b6a68c15a6a3 demo/topology_demo.cc
--- a/demo/topology_demo.cc	Fri Jun 30 12:14:36 2006 +0000
+++ b/demo/topology_demo.cc	Fri Jun 30 12:15:45 2006 +0000
@@ -17,7 +17,6 @@
  */
 
 #include <lemon/list_graph.h>
-#include <lemon/list_ugraph.h>
 #include <lemon/topology.h>
 #include <lemon/graph_to_eps.h>
 #include <lemon/graph_reader.h>
diff -r 4cd528a30ec1 -r b6a68c15a6a3 doc/graphs.dox
--- a/doc/graphs.dox	Fri Jun 30 12:14:36 2006 +0000
+++ b/doc/graphs.dox	Fri Jun 30 12:15:45 2006 +0000
@@ -9,20 +9,20 @@
 The primary data structures of LEMON are the graph classes. They all
 provide a node list - edge list interface, i.e. they have
 functionalities to list the nodes and the edges of the graph as well
-as  incoming and outgoing edges of a given node. This functionalities
-are defined in the \ref lemon::concept::Graph "Graph" concept.
+as  incoming and outgoing edges of a given node. 
 
-The next important graph type concept is the undirected graph concept
-what is defined in the \ref lemon::concept::UGraph "UGraph" concept class.
-Each undirected graphs provide node - undirected edge list interfaces.
-In addition the undirected graphs can be used as directed graphs so
-they are also conform to the \ref lemon::concept::Graph "Graph" concept.
+Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
+This concept does not make it possible to change the graph (i.e. it is
+not possible to add or delete edges or nodes). Most of the graph
+algorithms will run on these graphs.
 
-Usually the graphs can be sorted to two group, the first is the
-general topology graph types which can store any graph and the second
-are the special topology graphs like the \ref FullUGraph or the \ref
-GridUGraph.
 
+In case of graphs meeting the full feature
+\ref lemon::concept::ErasableGraph "ErasableGraph"
+concept
+you can also erase individual edges and nodes in arbitrary order.
+
+The implemented graph structures are the following.
 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
 the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
 and it also has some convenient extra features.
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/Makefile.am
--- a/lemon/Makefile.am	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/Makefile.am	Fri Jun 30 12:15:45 2006 +0000
@@ -43,9 +43,7 @@
 	lemon/fib_heap.h \
 	lemon/floyd_warshall.h \
 	lemon/fredman_tarjan.h \
-	lemon/full_bpugraph.h \
 	lemon/full_graph.h \
-	lemon/full_ugraph.h \
 	lemon/graph_adaptor.h \
 	lemon/graph_reader.h \
 	lemon/graph_to_eps.h \
@@ -58,9 +56,7 @@
 	lemon/kruskal.h \
 	lemon/lemon_reader.h \
 	lemon/lemon_writer.h \
-	lemon/list_bpugraph.h \
 	lemon/list_graph.h \
-	lemon/list_ugraph.h \
 	lemon/lp.h \
 	lemon/lp_base.h \
 	lemon/lp_cplex.h \
@@ -81,9 +77,7 @@
 	lemon/radix_sort.h \
 	lemon/refptr.h \
 	lemon/simann.h \
-	lemon/smart_bpugraph.h \
 	lemon/smart_graph.h \
-	lemon/smart_ugraph.h \
 	lemon/sub_graph.h \
 	lemon/suurballe.h \
 	lemon/tabu_search.h \
@@ -98,7 +92,6 @@
 	lemon/bits/alteration_notifier.h \
 	lemon/bits/array_map.h \
 	lemon/bits/base_extender.h \
-	lemon/bits/bpugraph_extender.h \
 	lemon/bits/default_map.h \
 	lemon/bits/edge_set_extender.h \
 	lemon/bits/graph_adaptor_extender.h \
@@ -110,7 +103,6 @@
 	lemon/bits/mingw32_rand.h \
 	lemon/bits/mingw32_time.h \
 	lemon/bits/traits.h \
-	lemon/bits/ugraph_extender.h \
 	lemon/bits/utility.h \
 	lemon/bits/vector_map.h
 
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/bits/bpugraph_extender.h
--- a/lemon/bits/bpugraph_extender.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,838 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_BITS_BPUGRAPH_EXTENDER_H
-#define LEMON_BITS_BPUGRAPH_EXTENDER_H
-
-#include <lemon/bits/invalid.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/map_extender.h>
-#include <lemon/bits/default_map.h>
-
-#include <lemon/concept_check.h>
-#include <lemon/concept/maps.h>
-
-///\ingroup graphbits
-///\file
-///\brief Extenders for the graph types
-namespace lemon {
-
-  /// \ingroup graphbits
-  ///
-  /// \brief Extender for the BpUGraphs
-  template <typename Base>
-  class BpUGraphExtender : public Base {
-  public:
-    typedef Base Parent;
-    typedef BpUGraphExtender 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 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));
-    }
-
-    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);
-    }
-
-    Edge direct(const UEdge& edge, const Node& node) const {
-      return Edge(edge, node == Parent::source(edge));
-    }
-
-    Edge oppositeEdge(const Edge& edge) const {
-      return Parent::direct(edge, !Parent::direction(edge));
-    }
-
-
-    int maxId(Node) const {
-      return Parent::maxNodeId();
-    }
-    int maxId(BNode) const {
-      return Parent::maxBNodeId();
-    }
-    int maxId(ANode) const {
-      return Parent::maxANodeId();
-    }
-    int maxId(Edge) const {
-      return maxEdgeId();
-    }
-    int maxId(UEdge) const {
-      return Parent::maxUEdgeId();
-    }
-
-
-    Node fromId(int id, Node) const {
-      return Parent::nodeFromId(id);
-    }
-    ANode fromId(int id, ANode) const {
-      return Parent::fromANodeId(id);
-    }
-    BNode fromId(int id, BNode) const {
-      return Parent::fromBNodeId(id);
-    }
-    Edge fromId(int id, Edge) const {
-      return Parent::edgeFromId(id);
-    }
-    UEdge fromId(int id, UEdge) const {
-      return Parent::uEdgeFromId(id);
-    }  
-  
-    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
-    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
-    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
-    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
-    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
-
-  protected:
-
-    mutable ANodeNotifier anode_notifier;
-    mutable BNodeNotifier bnode_notifier;
-    mutable NodeNotifier node_notifier;
-    mutable EdgeNotifier edge_notifier;
-    mutable UEdgeNotifier uedge_notifier;
-
-  public:
-
-    NodeNotifier& getNotifier(Node) const {
-      return node_notifier;
-    }
-
-    ANodeNotifier& getNotifier(ANode) const {
-      return anode_notifier;
-    }
-
-    BNodeNotifier& getNotifier(BNode) const {
-      return bnode_notifier;
-    }
-
-    EdgeNotifier& getNotifier(Edge) const {
-      return edge_notifier;
-    }
-
-    UEdgeNotifier& getNotifier(UEdge) const {
-      return uedge_notifier;
-    }
-
-    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 ANodeIt : public Node { 
-      friend class BpUGraphExtender;
-      const Graph* graph;
-    public:
-    
-      ANodeIt() { }
-    
-      ANodeIt(Invalid i) : Node(INVALID) { }
-    
-      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
-	graph->firstANode(static_cast<Node&>(*this));
-      }
-
-      ANodeIt(const Graph& _graph, const Node& node) 
-	: Node(node), graph(&_graph) {}
-    
-      ANodeIt& operator++() { 
-	graph->nextANode(*this);
-	return *this; 
-      }
-    };
-
-    class BNodeIt : public Node { 
-      friend class BpUGraphExtender;
-      const Graph* graph;
-    public:
-    
-      BNodeIt() { }
-    
-      BNodeIt(Invalid i) : Node(INVALID) { }
-    
-      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
-	graph->firstBNode(static_cast<Node&>(*this));
-      }
-
-      BNodeIt(const Graph& _graph, const Node& node) 
-	: Node(node), graph(&_graph) {}
-    
-      BNodeIt& operator++() { 
-	graph->nextBNode(*this);
-	return *this; 
-      }
-    };
-
-    class EdgeIt : public Edge { 
-      friend class BpUGraphExtender;
-      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 UEdgeIt : public UEdge { 
-      friend class BpUGraphExtender;
-      const Graph* graph;
-    public:
-    
-      UEdgeIt() { }
-    
-      UEdgeIt(Invalid i) : UEdge(INVALID) { }
-    
-      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
-	graph->first(static_cast<UEdge&>(*this));
-      }
-
-      UEdgeIt(const Graph& _graph, const UEdge& edge) 
-	: UEdge(edge), graph(&_graph) { }
-    
-      UEdgeIt& operator++() { 
-	graph->next(*this);
-	return *this; 
-      }
-    };
-
-    class OutEdgeIt : public Edge { 
-      friend class BpUGraphExtender;
-      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 BpUGraphExtender;
-      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::UEdge { 
-      friend class BpUGraphExtender;
-      const Graph* graph;
-      bool direction;
-    public:
-    
-      IncEdgeIt() { }
-    
-      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
-    
-      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
-	graph->firstInc(*this, direction, n);
-      }
-
-      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
-	: graph(&_graph), UEdge(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);
-    }
-
-    template <typename _Value>
-    class ANodeMap 
-      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
-    public:
-      typedef BpUGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
-    
-      ANodeMap(const Graph& graph) 
-	: Parent(graph) {}
-      ANodeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-    
-      ANodeMap& operator=(const ANodeMap& cmap) {
-	return operator=<ANodeMap>(cmap);
-      }
-    
-      template <typename CMap>
-      ANodeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-    
-    };
-
-    template <typename _Value>
-    class BNodeMap 
-      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
-    public:
-      typedef BpUGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
-    
-      BNodeMap(const Graph& graph) 
-	: Parent(graph) {}
-      BNodeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-    
-      BNodeMap& operator=(const BNodeMap& cmap) {
-	return operator=<BNodeMap>(cmap);
-      }
-    
-      template <typename CMap>
-      BNodeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-    
-    };
-
-  public:
-
-    template <typename _Value>
-    class NodeMap {
-    public:
-      typedef BpUGraphExtender Graph;
-
-      typedef Node Key;
-      typedef _Value Value;
-
-      /// The reference type of the map;
-      typedef typename ANodeMap<_Value>::Reference Reference;
-      /// The const reference type of the map;
-      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
-
-      typedef True ReferenceMapTag;
-
-      NodeMap(const Graph& _graph) 
-	: graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
-      NodeMap(const Graph& _graph, const _Value& _value) 
-	: graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
-
-      NodeMap& operator=(const NodeMap& cmap) {
-	return operator=<NodeMap>(cmap);
-      }
-    
-      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;
-      }
-
-      ConstReference operator[](const Key& node) const {
-	if (Parent::aNode(node)) {
-	  return aNodeMap[node];
-	} else {
-	  return bNodeMap[node];
-	}
-      } 
-
-      Reference operator[](const Key& node) {
-	if (Parent::aNode(node)) {
-	  return aNodeMap[node];
-	} else {
-	  return bNodeMap[node];
-	}
-      }
-
-      void set(const Key& node, const Value& value) {
-	if (Parent::aNode(node)) {
-	  aNodeMap.set(node, value);
-	} else {
-	  bNodeMap.set(node, value);
-	}
-      }
-
-      class MapIt : public NodeIt {
-      public:
-
-        typedef NodeIt Parent;
-        
-        explicit MapIt(NodeMap& _map) 
-          : Parent(_map.graph), map(_map) {}
-        
-        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
-          return map[*this];
-        }
-        
-        typename MapTraits<NodeMap>::ReturnValue operator*() {
-          return map[*this];
-        }
-        
-        void set(const Value& value) {
-          map.set(*this, value);
-        }
-
-      private:
-        NodeMap& map;
-      };
-
-      class ConstMapIt : public NodeIt {
-      public:
-
-        typedef NodeIt Parent;
-        
-        explicit ConstMapIt(const NodeMap& _map) 
-          : Parent(_map.graph), map(_map) {}
-        
-        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
-          return map[*this];
-        }
-        
-      private:
-        const NodeMap& map;
-      };
-
-      class ItemIt : public NodeIt {
-      public:
-
-        typedef NodeIt Parent;
-
-        explicit ItemIt(const NodeMap& _map)
-          : Parent(_map.graph) {}
-        
-      };
-      
-    private:
-      const Graph& graph;
-      ANodeMap<_Value> aNodeMap;
-      BNodeMap<_Value> bNodeMap;
-    };
-    
-
-    template <typename _Value>
-    class EdgeMap 
-      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
-    public:
-      typedef BpUGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
-    
-      EdgeMap(const Graph& graph) 
-	: Parent(graph) {}
-      EdgeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-    
-      EdgeMap& operator=(const EdgeMap& cmap) {
-	return operator=<EdgeMap>(cmap);
-      }
-    
-      template <typename CMap>
-      EdgeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-    };
-
-    template <typename _Value>
-    class UEdgeMap 
-      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
-    public:
-      typedef BpUGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
-    
-      UEdgeMap(const Graph& graph) 
-	: Parent(graph) {}
-      UEdgeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-    
-      UEdgeMap& operator=(const UEdgeMap& cmap) {
-	return operator=<UEdgeMap>(cmap);
-      }
-    
-      template <typename CMap>
-      UEdgeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-    };
-
-  
-    Node addANode() {
-      Node node = Parent::addANode();
-      getNotifier(ANode()).add(node);
-      getNotifier(Node()).add(node);
-      return node;
-    }
-
-    Node addBNode() {
-      Node node = Parent::addBNode();
-      getNotifier(BNode()).add(node);
-      getNotifier(Node()).add(node);
-      return node;
-    }
-  
-    UEdge addEdge(const Node& source, const Node& target) {
-      UEdge uedge = Parent::addEdge(source, target);
-      getNotifier(UEdge()).add(uedge);
-    
-      std::vector<Edge> edges;
-      edges.push_back(direct(uedge, true));
-      edges.push_back(direct(uedge, false));
-      getNotifier(Edge()).add(edges);
-    
-      return uedge;
-    }
-
-    void clear() {
-      getNotifier(Edge()).clear();
-      getNotifier(UEdge()).clear();
-      getNotifier(Node()).clear();
-      getNotifier(BNode()).clear();
-      getNotifier(ANode()).clear();
-      Parent::clear();
-    }
-
-    void erase(const Node& node) {
-      UEdge uedge;
-      if (Parent::aNode(node)) {
-        Parent::firstFromANode(uedge, node);
-        while (uedge != INVALID) {
-          erase(uedge);
-          Parent::firstFromANode(uedge, node);
-        }
-      } else {
-        Parent::firstFromBNode(uedge, node);
-        while (uedge != INVALID) {
-          erase(uedge);
-          Parent::firstFromBNode(uedge, node);
-        }
-      }
-
-      getNotifier(Node()).erase(node);
-      Parent::erase(node);
-    }
-    
-    void erase(const UEdge& uedge) {
-      std::vector<Edge> edges;
-      edges.push_back(direct(uedge, true));
-      edges.push_back(direct(uedge, false));
-      getNotifier(Edge()).erase(edges);
-      getNotifier(UEdge()).erase(uedge);
-      Parent::erase(uedge);
-    }
-
-
-    BpUGraphExtender() {
-      anode_notifier.setContainer(*this); 
-      bnode_notifier.setContainer(*this); 
-      node_notifier.setContainer(*this); 
-      edge_notifier.setContainer(*this); 
-      uedge_notifier.setContainer(*this);
-    } 
-
-    ~BpUGraphExtender() {
-      uedge_notifier.clear();
-      edge_notifier.clear(); 
-      node_notifier.clear(); 
-      anode_notifier.clear(); 
-      bnode_notifier.clear(); 
-    }
-
-
-  };
-
-}
-
-#endif
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/bits/graph_extender.h	Fri Jun 30 12:15:45 2006 +0000
@@ -20,10 +20,14 @@
 #define LEMON_BITS_GRAPH_EXTENDER_H
 
 #include <lemon/bits/invalid.h>
+#include <lemon/error.h>
 
 #include <lemon/bits/map_extender.h>
 #include <lemon/bits/default_map.h>
 
+#include <lemon/concept_check.h>
+#include <lemon/concept/maps.h>
+
 ///\ingroup graphbits
 ///\file
 ///\brief Extenders for the graph types
@@ -314,6 +318,1212 @@
     }
   };
 
+  /// \ingroup graphbits
+  ///
+  /// \brief Extender for the UGraphs
+  template <typename Base> 
+  class UGraphExtender : public Base {
+  public:
+    
+    typedef Base Parent;
+    typedef UGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
+
+    // UGraph extension    
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    int maxId(UEdge) const {
+      return Parent::maxUEdgeId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+
+    UEdge fromId(int id, UEdge) const {
+      return Parent::uEdgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const UEdge &e) const {
+      if( n == Parent::source(e))
+	return Parent::target(e);
+      else if( n == Parent::target(e))
+	return Parent::source(e);
+      else
+	return INVALID;
+    }
+
+    Edge oppositeEdge(const Edge &e) const {
+      return Parent::direct(e, !Parent::direction(e));
+    }
+
+    using Parent::direct;
+    Edge direct(const UEdge &ue, const Node &s) const {
+      return Parent::direct(ue, Parent::source(ue) == s);
+    }
+
+    // Alterable extension
+
+    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
+    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
+
+
+  protected:
+
+    mutable NodeNotifier node_notifier;
+    mutable EdgeNotifier edge_notifier;
+    mutable UEdgeNotifier uedge_notifier;
+
+  public:
+
+    NodeNotifier& getNotifier(Node) const {
+      return node_notifier;
+    }
+    
+    EdgeNotifier& getNotifier(Edge) const {
+      return edge_notifier;
+    }
+
+    UEdgeNotifier& getNotifier(UEdge) const {
+      return uedge_notifier;
+    }
+
+
+
+    class NodeIt : public Node { 
+      const Graph* graph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      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 EdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
+	_graph.first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& e) : 
+	Edge(e), graph(&_graph) { }
+
+      EdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class OutEdgeIt : public Edge { 
+      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 { 
+      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; 
+      }
+
+    };
+
+
+    class UEdgeIt : public Parent::UEdge { 
+      const Graph* graph;
+    public:
+
+      UEdgeIt() { }
+
+      UEdgeIt(Invalid i) : UEdge(i) { }
+
+      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
+	_graph.first(static_cast<UEdge&>(*this));
+      }
+
+      UEdgeIt(const Graph& _graph, const UEdge& e) : 
+	UEdge(e), graph(&_graph) { }
+
+      UEdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+    class IncEdgeIt : public Parent::UEdge {
+      friend class UGraphExtender;
+      const Graph* graph;
+      bool direction;
+    public:
+
+      IncEdgeIt() { }
+
+      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
+
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+	_graph.firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
+	: graph(&_graph), UEdge(ue) {
+	direction = (_graph.source(ue) == n);
+      }
+
+      IncEdgeIt& operator++() {
+	graph->nextInc(*this, direction);
+	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);
+    }
+
+    /// 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);
+    }
+
+    // Mappable extension
+
+    template <typename _Value>
+    class NodeMap 
+      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
+    public:
+      typedef UGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
+
+      NodeMap(const Graph& graph) 
+	: Parent(graph) {}
+      NodeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+
+      NodeMap& operator=(const NodeMap& cmap) {
+	return operator=<NodeMap>(cmap);
+      }
+
+      template <typename CMap>
+      NodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+
+    };
+
+    template <typename _Value>
+    class EdgeMap 
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
+    public:
+      typedef UGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+
+      EdgeMap(const Graph& graph) 
+	: Parent(graph) {}
+      EdgeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+
+      EdgeMap& operator=(const EdgeMap& cmap) {
+	return operator=<EdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+    };
+
+
+    template <typename _Value>
+    class UEdgeMap 
+      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
+    public:
+      typedef UGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
+
+      UEdgeMap(const Graph& graph) 
+	: Parent(graph) {}
+
+      UEdgeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+
+      UEdgeMap& operator=(const UEdgeMap& cmap) {
+	return operator=<UEdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      UEdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+
+    };
+
+    // Alteration extension
+
+    Node addNode() {
+      Node node = Parent::addNode();
+      getNotifier(Node()).add(node);
+      return node;
+    }
+
+    UEdge addEdge(const Node& from, const Node& to) {
+      UEdge uedge = Parent::addEdge(from, to);
+      getNotifier(UEdge()).add(uedge);
+      getNotifier(Edge()).add(Parent::direct(uedge, true));
+      getNotifier(Edge()).add(Parent::direct(uedge, false));
+      return uedge;
+    }
+    
+    void clear() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+      Parent::clear();
+    }
+
+    void erase(const Node& node) {
+      Edge edge;
+      Parent::firstOut(edge, node);
+      while (edge != INVALID ) {
+	erase(edge);
+	Parent::firstOut(edge, node);
+      } 
+
+      Parent::firstIn(edge, node);
+      while (edge != INVALID ) {
+	erase(edge);
+	Parent::firstIn(edge, node);
+      }
+
+      getNotifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+
+    void erase(const UEdge& uedge) {
+      getNotifier(Edge()).erase(Parent::direct(uedge, true));
+      getNotifier(Edge()).erase(Parent::direct(uedge, false));
+      getNotifier(UEdge()).erase(uedge);
+      Parent::erase(uedge);
+    }
+
+    UGraphExtender() {
+      node_notifier.setContainer(*this); 
+      edge_notifier.setContainer(*this);
+      uedge_notifier.setContainer(*this);
+    } 
+
+    ~UGraphExtender() {
+      uedge_notifier.clear();
+      edge_notifier.clear();
+      node_notifier.clear(); 
+    } 
+
+  };
+
+  /// \ingroup graphbits
+  ///
+  /// \brief Extender for the BpUGraphs
+  template <typename Base>
+  class BpUGraphExtender : public Base {
+  public:
+    typedef Base Parent;
+    typedef BpUGraphExtender 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 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));
+    }
+
+    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);
+    }
+
+    Edge direct(const UEdge& edge, const Node& node) const {
+      return Edge(edge, node == Parent::source(edge));
+    }
+
+    Edge oppositeEdge(const Edge& edge) const {
+      return Parent::direct(edge, !Parent::direction(edge));
+    }
+
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+    int maxId(BNode) const {
+      return Parent::maxBNodeId();
+    }
+    int maxId(ANode) const {
+      return Parent::maxANodeId();
+    }
+    int maxId(Edge) const {
+      return maxEdgeId();
+    }
+    int maxId(UEdge) const {
+      return Parent::maxUEdgeId();
+    }
+
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+    ANode fromId(int id, ANode) const {
+      return Parent::fromANodeId(id);
+    }
+    BNode fromId(int id, BNode) const {
+      return Parent::fromBNodeId(id);
+    }
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+    UEdge fromId(int id, UEdge) const {
+      return Parent::uEdgeFromId(id);
+    }  
+  
+    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
+
+  protected:
+
+    mutable ANodeNotifier anode_notifier;
+    mutable BNodeNotifier bnode_notifier;
+    mutable NodeNotifier node_notifier;
+    mutable EdgeNotifier edge_notifier;
+    mutable UEdgeNotifier uedge_notifier;
+
+  public:
+
+    NodeNotifier& getNotifier(Node) const {
+      return node_notifier;
+    }
+
+    ANodeNotifier& getNotifier(ANode) const {
+      return anode_notifier;
+    }
+
+    BNodeNotifier& getNotifier(BNode) const {
+      return bnode_notifier;
+    }
+
+    EdgeNotifier& getNotifier(Edge) const {
+      return edge_notifier;
+    }
+
+    UEdgeNotifier& getNotifier(UEdge) const {
+      return uedge_notifier;
+    }
+
+    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 ANodeIt : public Node { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      ANodeIt() { }
+    
+      ANodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
+	graph->firstANode(static_cast<Node&>(*this));
+      }
+
+      ANodeIt(const Graph& _graph, const Node& node) 
+	: Node(node), graph(&_graph) {}
+    
+      ANodeIt& operator++() { 
+	graph->nextANode(*this);
+	return *this; 
+      }
+    };
+
+    class BNodeIt : public Node { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      BNodeIt() { }
+    
+      BNodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
+	graph->firstBNode(static_cast<Node&>(*this));
+      }
+
+      BNodeIt(const Graph& _graph, const Node& node) 
+	: Node(node), graph(&_graph) {}
+    
+      BNodeIt& operator++() { 
+	graph->nextBNode(*this);
+	return *this; 
+      }
+    };
+
+    class EdgeIt : public Edge { 
+      friend class BpUGraphExtender;
+      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 UEdgeIt : public UEdge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      UEdgeIt() { }
+    
+      UEdgeIt(Invalid i) : UEdge(INVALID) { }
+    
+      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
+	graph->first(static_cast<UEdge&>(*this));
+      }
+
+      UEdgeIt(const Graph& _graph, const UEdge& edge) 
+	: UEdge(edge), graph(&_graph) { }
+    
+      UEdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+    };
+
+    class OutEdgeIt : public Edge { 
+      friend class BpUGraphExtender;
+      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 BpUGraphExtender;
+      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::UEdge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+      bool direction;
+    public:
+    
+      IncEdgeIt() { }
+    
+      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
+    
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+	graph->firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
+	: graph(&_graph), UEdge(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);
+    }
+
+    template <typename _Value>
+    class ANodeMap 
+      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
+    public:
+      typedef BpUGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
+    
+      ANodeMap(const Graph& graph) 
+	: Parent(graph) {}
+      ANodeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+    
+      ANodeMap& operator=(const ANodeMap& cmap) {
+	return operator=<ANodeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      ANodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+    
+    };
+
+    template <typename _Value>
+    class BNodeMap 
+      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
+    public:
+      typedef BpUGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
+    
+      BNodeMap(const Graph& graph) 
+	: Parent(graph) {}
+      BNodeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+    
+      BNodeMap& operator=(const BNodeMap& cmap) {
+	return operator=<BNodeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      BNodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+    
+    };
+
+  public:
+
+    template <typename _Value>
+    class NodeMap {
+    public:
+      typedef BpUGraphExtender Graph;
+
+      typedef Node Key;
+      typedef _Value Value;
+
+      /// The reference type of the map;
+      typedef typename ANodeMap<_Value>::Reference Reference;
+      /// The const reference type of the map;
+      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
+
+      typedef True ReferenceMapTag;
+
+      NodeMap(const Graph& _graph) 
+	: graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
+      NodeMap(const Graph& _graph, const _Value& _value) 
+	: graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
+
+      NodeMap& operator=(const NodeMap& cmap) {
+	return operator=<NodeMap>(cmap);
+      }
+    
+      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;
+      }
+
+      ConstReference operator[](const Key& node) const {
+	if (Parent::aNode(node)) {
+	  return aNodeMap[node];
+	} else {
+	  return bNodeMap[node];
+	}
+      } 
+
+      Reference operator[](const Key& node) {
+	if (Parent::aNode(node)) {
+	  return aNodeMap[node];
+	} else {
+	  return bNodeMap[node];
+	}
+      }
+
+      void set(const Key& node, const Value& value) {
+	if (Parent::aNode(node)) {
+	  aNodeMap.set(node, value);
+	} else {
+	  bNodeMap.set(node, value);
+	}
+      }
+
+      class MapIt : public NodeIt {
+      public:
+
+        typedef NodeIt Parent;
+        
+        explicit MapIt(NodeMap& _map) 
+          : Parent(_map.graph), map(_map) {}
+        
+        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
+          return map[*this];
+        }
+        
+        typename MapTraits<NodeMap>::ReturnValue operator*() {
+          return map[*this];
+        }
+        
+        void set(const Value& value) {
+          map.set(*this, value);
+        }
+
+      private:
+        NodeMap& map;
+      };
+
+      class ConstMapIt : public NodeIt {
+      public:
+
+        typedef NodeIt Parent;
+        
+        explicit ConstMapIt(const NodeMap& _map) 
+          : Parent(_map.graph), map(_map) {}
+        
+        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
+          return map[*this];
+        }
+        
+      private:
+        const NodeMap& map;
+      };
+
+      class ItemIt : public NodeIt {
+      public:
+
+        typedef NodeIt Parent;
+
+        explicit ItemIt(const NodeMap& _map)
+          : Parent(_map.graph) {}
+        
+      };
+      
+    private:
+      const Graph& graph;
+      ANodeMap<_Value> aNodeMap;
+      BNodeMap<_Value> bNodeMap;
+    };
+    
+
+    template <typename _Value>
+    class EdgeMap 
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
+    public:
+      typedef BpUGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+    
+      EdgeMap(const Graph& graph) 
+	: Parent(graph) {}
+      EdgeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+    
+      EdgeMap& operator=(const EdgeMap& cmap) {
+	return operator=<EdgeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+    };
+
+    template <typename _Value>
+    class UEdgeMap 
+      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
+    public:
+      typedef BpUGraphExtender Graph;
+      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
+    
+      UEdgeMap(const Graph& graph) 
+	: Parent(graph) {}
+      UEdgeMap(const Graph& graph, const _Value& value) 
+	: Parent(graph, value) {}
+    
+      UEdgeMap& operator=(const UEdgeMap& cmap) {
+	return operator=<UEdgeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      UEdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+    };
+
+  
+    Node addANode() {
+      Node node = Parent::addANode();
+      getNotifier(ANode()).add(node);
+      getNotifier(Node()).add(node);
+      return node;
+    }
+
+    Node addBNode() {
+      Node node = Parent::addBNode();
+      getNotifier(BNode()).add(node);
+      getNotifier(Node()).add(node);
+      return node;
+    }
+  
+    UEdge addEdge(const Node& source, const Node& target) {
+      UEdge uedge = Parent::addEdge(source, target);
+      getNotifier(UEdge()).add(uedge);
+    
+      std::vector<Edge> edges;
+      edges.push_back(direct(uedge, true));
+      edges.push_back(direct(uedge, false));
+      getNotifier(Edge()).add(edges);
+    
+      return uedge;
+    }
+
+    void clear() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+      getNotifier(BNode()).clear();
+      getNotifier(ANode()).clear();
+      Parent::clear();
+    }
+
+    void erase(const Node& node) {
+      UEdge uedge;
+      if (Parent::aNode(node)) {
+        Parent::firstFromANode(uedge, node);
+        while (uedge != INVALID) {
+          erase(uedge);
+          Parent::firstFromANode(uedge, node);
+        }
+      } else {
+        Parent::firstFromBNode(uedge, node);
+        while (uedge != INVALID) {
+          erase(uedge);
+          Parent::firstFromBNode(uedge, node);
+        }
+      }
+
+      getNotifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+    
+    void erase(const UEdge& uedge) {
+      std::vector<Edge> edges;
+      edges.push_back(direct(uedge, true));
+      edges.push_back(direct(uedge, false));
+      getNotifier(Edge()).erase(edges);
+      getNotifier(UEdge()).erase(uedge);
+      Parent::erase(uedge);
+    }
+
+
+    BpUGraphExtender() {
+      anode_notifier.setContainer(*this); 
+      bnode_notifier.setContainer(*this); 
+      node_notifier.setContainer(*this); 
+      edge_notifier.setContainer(*this); 
+      uedge_notifier.setContainer(*this);
+    } 
+
+    ~BpUGraphExtender() {
+      uedge_notifier.clear();
+      edge_notifier.clear(); 
+      node_notifier.clear(); 
+      anode_notifier.clear(); 
+      bnode_notifier.clear(); 
+    }
+
+
+  };
+
 }
 
 #endif
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/bits/ugraph_extender.h
--- a/lemon/bits/ugraph_extender.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,444 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_BITS_UGRAPH_EXTENDER_H
-#define LEMON_BITS_UGRAPH_EXTENDER_H
-
-#include <lemon/bits/invalid.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/map_extender.h>
-#include <lemon/bits/default_map.h>
-
-#include <lemon/concept_check.h>
-#include <lemon/concept/maps.h>
-
-///\ingroup graphbits
-///\file
-///\brief Extenders for the graph types
-namespace lemon {
-
-  /// \ingroup graphbits
-  ///
-  /// \brief Extender for the UGraphs
-  template <typename Base> 
-  class UGraphExtender : public Base {
-  public:
-    
-    typedef Base Parent;
-    typedef UGraphExtender Graph;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-
-    // UGraph extension    
-
-    int maxId(Node) const {
-      return Parent::maxNodeId();
-    }
-
-    int maxId(Edge) const {
-      return Parent::maxEdgeId();
-    }
-
-    int maxId(UEdge) const {
-      return Parent::maxUEdgeId();
-    }
-
-    Node fromId(int id, Node) const {
-      return Parent::nodeFromId(id);
-    }
-
-    Edge fromId(int id, Edge) const {
-      return Parent::edgeFromId(id);
-    }
-
-    UEdge fromId(int id, UEdge) const {
-      return Parent::uEdgeFromId(id);
-    }
-
-    Node oppositeNode(const Node &n, const UEdge &e) const {
-      if( n == Parent::source(e))
-	return Parent::target(e);
-      else if( n == Parent::target(e))
-	return Parent::source(e);
-      else
-	return INVALID;
-    }
-
-    Edge oppositeEdge(const Edge &e) const {
-      return Parent::direct(e, !Parent::direction(e));
-    }
-
-    using Parent::direct;
-    Edge direct(const UEdge &ue, const Node &s) const {
-      return Parent::direct(ue, Parent::source(ue) == s);
-    }
-
-    // Alterable extension
-
-    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
-    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
-    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
-
-
-  protected:
-
-    mutable NodeNotifier node_notifier;
-    mutable EdgeNotifier edge_notifier;
-    mutable UEdgeNotifier uedge_notifier;
-
-  public:
-
-    NodeNotifier& getNotifier(Node) const {
-      return node_notifier;
-    }
-    
-    EdgeNotifier& getNotifier(Edge) const {
-      return edge_notifier;
-    }
-
-    UEdgeNotifier& getNotifier(UEdge) const {
-      return uedge_notifier;
-    }
-
-
-
-    class NodeIt : public Node { 
-      const Graph* graph;
-    public:
-
-      NodeIt() {}
-
-      NodeIt(Invalid i) : Node(i) { }
-
-      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 EdgeIt : public Edge { 
-      const Graph* graph;
-    public:
-
-      EdgeIt() { }
-
-      EdgeIt(Invalid i) : Edge(i) { }
-
-      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
-	_graph.first(static_cast<Edge&>(*this));
-      }
-
-      EdgeIt(const Graph& _graph, const Edge& e) : 
-	Edge(e), graph(&_graph) { }
-
-      EdgeIt& operator++() { 
-	graph->next(*this);
-	return *this; 
-      }
-
-    };
-
-
-    class OutEdgeIt : public Edge { 
-      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 { 
-      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; 
-      }
-
-    };
-
-
-    class UEdgeIt : public Parent::UEdge { 
-      const Graph* graph;
-    public:
-
-      UEdgeIt() { }
-
-      UEdgeIt(Invalid i) : UEdge(i) { }
-
-      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
-	_graph.first(static_cast<UEdge&>(*this));
-      }
-
-      UEdgeIt(const Graph& _graph, const UEdge& e) : 
-	UEdge(e), graph(&_graph) { }
-
-      UEdgeIt& operator++() { 
-	graph->next(*this);
-	return *this; 
-      }
-
-    };
-
-    class IncEdgeIt : public Parent::UEdge {
-      friend class UGraphExtender;
-      const Graph* graph;
-      bool direction;
-    public:
-
-      IncEdgeIt() { }
-
-      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
-
-      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
-	_graph.firstInc(*this, direction, n);
-      }
-
-      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
-	: graph(&_graph), UEdge(ue) {
-	direction = (_graph.source(ue) == n);
-      }
-
-      IncEdgeIt& operator++() {
-	graph->nextInc(*this, direction);
-	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);
-    }
-
-    /// 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);
-    }
-
-    // Mappable extension
-
-    template <typename _Value>
-    class NodeMap 
-      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
-    public:
-      typedef UGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
-
-      NodeMap(const Graph& graph) 
-	: Parent(graph) {}
-      NodeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-
-      NodeMap& operator=(const NodeMap& cmap) {
-	return operator=<NodeMap>(cmap);
-      }
-
-      template <typename CMap>
-      NodeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-
-    };
-
-    template <typename _Value>
-    class EdgeMap 
-      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
-    public:
-      typedef UGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
-
-      EdgeMap(const Graph& graph) 
-	: Parent(graph) {}
-      EdgeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-
-      EdgeMap& operator=(const EdgeMap& cmap) {
-	return operator=<EdgeMap>(cmap);
-      }
-
-      template <typename CMap>
-      EdgeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-    };
-
-
-    template <typename _Value>
-    class UEdgeMap 
-      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
-    public:
-      typedef UGraphExtender Graph;
-      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
-
-      UEdgeMap(const Graph& graph) 
-	: Parent(graph) {}
-
-      UEdgeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-
-      UEdgeMap& operator=(const UEdgeMap& cmap) {
-	return operator=<UEdgeMap>(cmap);
-      }
-
-      template <typename CMap>
-      UEdgeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-
-    };
-
-    // Alteration extension
-
-    Node addNode() {
-      Node node = Parent::addNode();
-      getNotifier(Node()).add(node);
-      return node;
-    }
-
-    UEdge addEdge(const Node& from, const Node& to) {
-      UEdge uedge = Parent::addEdge(from, to);
-      getNotifier(UEdge()).add(uedge);
-      getNotifier(Edge()).add(Parent::direct(uedge, true));
-      getNotifier(Edge()).add(Parent::direct(uedge, false));
-      return uedge;
-    }
-    
-    void clear() {
-      getNotifier(Edge()).clear();
-      getNotifier(UEdge()).clear();
-      getNotifier(Node()).clear();
-      Parent::clear();
-    }
-
-    void erase(const Node& node) {
-      Edge edge;
-      Parent::firstOut(edge, node);
-      while (edge != INVALID ) {
-	erase(edge);
-	Parent::firstOut(edge, node);
-      } 
-
-      Parent::firstIn(edge, node);
-      while (edge != INVALID ) {
-	erase(edge);
-	Parent::firstIn(edge, node);
-      }
-
-      getNotifier(Node()).erase(node);
-      Parent::erase(node);
-    }
-
-    void erase(const UEdge& uedge) {
-      getNotifier(Edge()).erase(Parent::direct(uedge, true));
-      getNotifier(Edge()).erase(Parent::direct(uedge, false));
-      getNotifier(UEdge()).erase(uedge);
-      Parent::erase(uedge);
-    }
-
-    UGraphExtender() {
-      node_notifier.setContainer(*this); 
-      edge_notifier.setContainer(*this);
-      uedge_notifier.setContainer(*this);
-    } 
-
-    ~UGraphExtender() {
-      uedge_notifier.clear();
-      edge_notifier.clear();
-      node_notifier.clear(); 
-    } 
-
-  };
-
-}
-
-#endif
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/edge_set.h
--- a/lemon/edge_set.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/edge_set.h	Fri Jun 30 12:15:45 2006 +0000
@@ -22,7 +22,6 @@
 
 #include <lemon/bits/default_map.h>
 #include <lemon/bits/edge_set_extender.h>
-#include <lemon/bits/base_extender.h>
 
 /// \ingroup graphs
 /// \file
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/full_bpugraph.h
--- a/lemon/full_bpugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,266 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_FULL_BPUGRAPH_H
-#define LEMON_FULL_BPUGRAPH_H
-
-#include <cmath>
-
-#include <lemon/bits/bpugraph_extender.h>
-
-#include <lemon/bits/invalid.h>
-#include <lemon/bits/utility.h>
-
-
-///\ingroup graphs
-///\file
-///\brief FullBpUGraph class.
-
-
-namespace lemon {
-
-  class FullBpUGraphBase {
-  protected:
-
-    int _aNodeNum;
-    int _bNodeNum;
-
-    int _edgeNum;
-
-  public:
-
-    class NodeSetError : public LogicError {
-      virtual const char* exceptionName() const { 
-	return "lemon::FullBpUGraph::NodeSetError";
-      }
-    };
-  
-    class Node {
-      friend class FullBpUGraphBase;
-    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 UEdge {
-      friend class FullBpUGraphBase;
-    protected:
-      int id;
-
-      UEdge(int _id) { id = _id;}
-    public:
-      UEdge() {}
-      UEdge (Invalid) { id = -1; }
-      bool operator==(const UEdge i) const {return id==i.id;}
-      bool operator!=(const UEdge i) const {return id!=i.id;}
-      bool operator<(const UEdge i) const {return id<i.id;}
-    };
-
-    void construct(int aNodeNum, int bNodeNum) {
-      _aNodeNum = aNodeNum;
-      _bNodeNum = bNodeNum;
-      _edgeNum = aNodeNum * bNodeNum;
-    }
-
-    void firstANode(Node& node) const {
-      node.id = 2 * _aNodeNum - 2;
-      if (node.id < 0) node.id = -1; 
-    }
-    void nextANode(Node& node) const {
-      node.id -= 2;
-      if (node.id < 0) node.id = -1; 
-    }
-
-    void firstBNode(Node& node) const {
-      node.id = 2 * _bNodeNum - 1;
-    }
-    void nextBNode(Node& node) const {
-      node.id -= 2;
-    }
-
-    void first(Node& node) const {
-      if (_aNodeNum > 0) {
-	node.id = 2 * _aNodeNum - 2;
-      } else {
-	node.id = 2 * _bNodeNum - 1;
-      }
-    }
-    void next(Node& node) const {
-      node.id -= 2;
-      if (node.id == -2) {
-	node.id = 2 * _bNodeNum - 1;
-      }
-    }
-  
-    void first(UEdge& edge) const {
-      edge.id = _edgeNum - 1;
-    }
-    void next(UEdge& edge) const {
-      --edge.id;
-    }
-
-    void firstFromANode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
-      edge.id = (node.id >> 1) * _bNodeNum;
-    }
-    void nextFromANode(UEdge& edge) const {
-      ++(edge.id);
-      if (edge.id % _bNodeNum == 0) edge.id = -1;
-    }
-
-    void firstFromBNode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
-      edge.id = (node.id >> 1);
-    }
-    void nextFromBNode(UEdge& edge) const {
-      edge.id += _bNodeNum;
-      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 _aNodeNum > _bNodeNum ? 
-	_aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
-    }
-  
-    static int id(const UEdge& edge) {
-      return edge.id;
-    }
-    static UEdge uEdgeFromId(int id) {
-      return UEdge(id);
-    }
-    int maxUEdgeId() const {
-      return _edgeNum - 1;
-    }
-  
-    static int aNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromANodeId(int id) {
-      return Node(id << 1);
-    }
-    int maxANodeId() const {
-      return _aNodeNum;
-    }
-
-    static int bNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromBNodeId(int id) {
-      return Node((id << 1) + 1);
-    }
-    int maxBNodeId() const {
-      return _bNodeNum;
-    }
-
-    Node aNode(const UEdge& edge) const {
-      return Node((edge.id / _bNodeNum) << 1);
-    }
-    Node bNode(const UEdge& edge) const {
-      return Node(((edge.id % _bNodeNum) << 1) + 1);
-    }
-
-    static bool aNode(const Node& node) {
-      return (node.id & 1) == 0;
-    }
-
-    static bool bNode(const Node& node) {
-      return (node.id & 1) == 1;
-    }
-
-    static Node aNode(int index) {
-      return Node(index << 1);
-    }
-
-    static Node bNode(int index) {
-      return Node((index << 1) + 1);
-    }
-
-    typedef True NodeNumTag;
-    int nodeNum() const { return _aNodeNum + _bNodeNum; }
-    int aNodeNum() const { return _aNodeNum; }
-    int bNodeNum() const { return _bNodeNum; }
-
-    typedef True EdgeNumTag;
-    int uEdgeNum() const { return _edgeNum; }
-
-  };
-
-
-  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
-
-
-  /// \ingroup graphs
-  ///
-  /// \brief An undirected full bipartite graph class.
-  ///
-  /// This is a simple and fast bipartite undirected full graph implementation.
-  /// It is completely static, so you can neither add nor delete either
-  /// edges or nodes.
-  ///
-  /// \sa FullUGraphBase
-  /// \sa FullGraph
-  ///
-  /// \author Balazs Dezso
-  class FullBpUGraph : 
-    public ExtendedFullBpUGraphBase {
-  public:
-
-    typedef ExtendedFullBpUGraphBase Parent;
-
-    FullBpUGraph() {
-      Parent::construct(0, 0);
-    }
-
-    FullBpUGraph(int aNodeNum, int bNodeNum) {
-      Parent::construct(aNodeNum, bNodeNum);
-    }
-
-    /// \brief Resize the graph
-    ///
-    void resize(int n, int m) {
-      Parent::getNotifier(Edge()).clear();
-      Parent::getNotifier(UEdge()).clear();
-      Parent::getNotifier(Node()).clear();
-      Parent::getNotifier(ANode()).clear();
-      Parent::getNotifier(BNode()).clear();
-      construct(n, m);
-      Parent::getNotifier(ANode()).build();
-      Parent::getNotifier(BNode()).build();
-      Parent::getNotifier(Node()).build();
-      Parent::getNotifier(UEdge()).build();
-      Parent::getNotifier(Edge()).build();
-    }
-  };
-
-} //namespace lemon
-
-
-#endif //LEMON_FULL_GRAPH_H
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/full_graph.h
--- a/lemon/full_graph.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/full_graph.h	Fri Jun 30 12:15:45 2006 +0000
@@ -21,6 +21,7 @@
 
 #include <cmath>
 
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 
 #include <lemon/bits/invalid.h>
@@ -29,7 +30,7 @@
 
 ///\ingroup graphs
 ///\file
-///\brief FullGraph class.
+///\brief FullGraph and FullUGraph classes.
 
 
 namespace lemon {
@@ -246,6 +247,473 @@
     }
   };
 
+
+  /// \brief Base of the FullUGrpah.
+  ///
+  /// Base of the FullUGrpah.
+  class FullUGraphBase {
+    int _nodeNum;
+    int _edgeNum;
+  public:
+
+    typedef FullUGraphBase Graph;
+
+    class Node;
+    class Edge;
+
+  public:
+
+    FullUGraphBase() {}
+
+
+    ///Creates a full graph with \c n nodes.
+    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
+
+    /// \brief Returns the node with the given index.
+    ///
+    /// Returns the node with the given index. Because it is a
+    /// static size graph the node's of the graph can be indiced
+    /// by the range from 0 to \e nodeNum()-1 and the index of
+    /// the node can accessed by the \e index() member.
+    Node operator()(int index) const { return Node(index); }
+
+    /// \brief Returns the index of the node.
+    ///
+    /// Returns the index of the node. Because it is a
+    /// static size graph the node's of the graph can be indiced
+    /// by the range from 0 to \e nodeNum()-1 and the index of
+    /// the node can accessed by the \e index() member.
+    int index(const Node& node) const { return node.id; }
+
+    typedef True NodeNumTag;
+    typedef True EdgeNumTag;
+
+    ///Number of nodes.
+    int nodeNum() const { return _nodeNum; }
+    ///Number of edges.
+    int edgeNum() const { return _edgeNum; }
+
+    /// Maximum node ID.
+    
+    /// Maximum node ID.
+    ///\sa id(Node)
+    int maxNodeId() const { return _nodeNum-1; }
+    /// Maximum edge ID.
+    
+    /// Maximum edge ID.
+    ///\sa id(Edge)
+    int maxEdgeId() const { return _edgeNum-1; }
+
+    /// \brief Returns the node from its \c id.
+    ///
+    /// Returns the node from its \c id. If there is not node
+    /// with the given id the effect of the function is undefinied.
+    static Node nodeFromId(int id) { return Node(id);}
+
+    /// \brief Returns the edge from its \c id.
+    ///
+    /// Returns the edge from its \c id. If there is not edge
+    /// with the given id the effect of the function is undefinied.
+    static Edge edgeFromId(int id) { return Edge(id);}
+
+    Node source(Edge e) const { 
+      /// \todo we may do it faster
+      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
+    }
+
+    Node target(Edge e) const { 
+      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
+      return Node(e.id - (source) * (source - 1) / 2);
+    }
+
+
+    /// \brief Node ID.
+    ///
+    /// The ID of a valid Node is a nonnegative integer not greater than
+    /// \ref maxNodeId(). The range of the ID's is not surely continuous
+    /// and the greatest node ID can be actually less then \ref maxNodeId().
+    ///
+    /// The ID of the \ref INVALID node is -1.
+    /// \return The ID of the node \c v. 
+
+    static int id(Node v) { return v.id; }
+
+    /// \brief Edge ID.
+    ///
+    /// The ID of a valid Edge is a nonnegative integer not greater than
+    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
+    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
+    ///
+    /// The ID of the \ref INVALID edge is -1.
+    ///\return The ID of the edge \c e. 
+    static int id(Edge e) { return e.id; }
+
+    /// \brief Finds an edge between two nodes.
+    ///
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
+      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
+      return Edge(u.id * (u.id - 1) / 2 + v.id);
+    }
+
+    typedef True FindEdgeTag;
+    
+      
+    class Node {
+      friend class FullUGraphBase;
+
+    protected:
+      int id;
+      Node(int _id) { id = _id;}
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node node) const {return id == node.id;}
+      bool operator!=(const Node node) const {return id != node.id;}
+      bool operator<(const Node node) const {return id < node.id;}
+    };
+    
+
+
+    class Edge {
+      friend class FullUGraphBase;
+      
+    protected:
+      int id;  // _nodeNum * target + source;
+
+      Edge(int _id) : id(_id) {}
+
+    public:
+      Edge() { }
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge edge) const {return id == edge.id;}
+      bool operator!=(const Edge edge) const {return id != edge.id;}
+      bool operator<(const Edge edge) const {return id < edge.id;}
+    };
+
+    void first(Node& node) const {
+      node.id = _nodeNum - 1;
+    }
+
+    static void next(Node& node) {
+      --node.id;
+    }
+
+    void first(Edge& edge) const {
+      edge.id = _edgeNum - 1;
+    }
+
+    static void next(Edge& edge) {
+      --edge.id;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {      
+      int src = node.id;
+      int trg = 0;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
+    }
+
+    /// \todo with specialized iterators we can make faster iterating
+    void nextOut(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++trg;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      int src = node.id + 1;
+      int trg = node.id;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
+    }
+    
+    void nextIn(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++src;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
+    }
+
+  };
+
+  typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> > 
+  ExtendedFullUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief An undirected full graph class.
+  ///
+  /// This is a simple and fast undirected full graph implementation.
+  /// It is completely static, so you can neither add nor delete either
+  /// edges or nodes.
+  ///
+  /// The main difference beetween the \e FullGraph and \e FullUGraph class
+  /// is that this class conforms to the undirected graph concept and
+  /// it does not contain the loop edges.
+  ///
+  /// \sa FullUGraphBase
+  /// \sa FullGraph
+  ///
+  /// \author Balazs Dezso
+  class FullUGraph : public ExtendedFullUGraphBase {
+  public:
+
+    typedef ExtendedFullUGraphBase Parent;
+
+    /// \brief Constructor
+    FullUGraph() { construct(0); }
+
+    /// \brief Constructor
+    FullUGraph(int n) { construct(n); }
+
+    /// \brief Resize the graph
+    ///
+    /// Resize the graph. The function will fully destroy and build the graph.
+    /// This cause that the maps of the graph will reallocated
+    /// automatically and the previous values will be lost.
+    void resize(int n) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      construct(n);
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
+  };
+
+
+  class FullBpUGraphBase {
+  protected:
+
+    int _aNodeNum;
+    int _bNodeNum;
+
+    int _edgeNum;
+
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+	return "lemon::FullBpUGraph::NodeSetError";
+      }
+    };
+  
+    class Node {
+      friend class FullBpUGraphBase;
+    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 UEdge {
+      friend class FullBpUGraphBase;
+    protected:
+      int id;
+
+      UEdge(int _id) { id = _id;}
+    public:
+      UEdge() {}
+      UEdge (Invalid) { id = -1; }
+      bool operator==(const UEdge i) const {return id==i.id;}
+      bool operator!=(const UEdge i) const {return id!=i.id;}
+      bool operator<(const UEdge i) const {return id<i.id;}
+    };
+
+    void construct(int aNodeNum, int bNodeNum) {
+      _aNodeNum = aNodeNum;
+      _bNodeNum = bNodeNum;
+      _edgeNum = aNodeNum * bNodeNum;
+    }
+
+    void firstANode(Node& node) const {
+      node.id = 2 * _aNodeNum - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextANode(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    void firstBNode(Node& node) const {
+      node.id = 2 * _bNodeNum - 1;
+    }
+    void nextBNode(Node& node) const {
+      node.id -= 2;
+    }
+
+    void first(Node& node) const {
+      if (_aNodeNum > 0) {
+	node.id = 2 * _aNodeNum - 2;
+      } else {
+	node.id = 2 * _bNodeNum - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+	node.id = 2 * _bNodeNum - 1;
+      }
+    }
+  
+    void first(UEdge& edge) const {
+      edge.id = _edgeNum - 1;
+    }
+    void next(UEdge& edge) const {
+      --edge.id;
+    }
+
+    void firstFromANode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = (node.id >> 1) * _bNodeNum;
+    }
+    void nextFromANode(UEdge& edge) const {
+      ++(edge.id);
+      if (edge.id % _bNodeNum == 0) edge.id = -1;
+    }
+
+    void firstFromBNode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = (node.id >> 1);
+    }
+    void nextFromBNode(UEdge& edge) const {
+      edge.id += _bNodeNum;
+      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 _aNodeNum > _bNodeNum ? 
+	_aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
+    }
+  
+    static int id(const UEdge& edge) {
+      return edge.id;
+    }
+    static UEdge uEdgeFromId(int id) {
+      return UEdge(id);
+    }
+    int maxUEdgeId() const {
+      return _edgeNum - 1;
+    }
+  
+    static int aNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromANodeId(int id) {
+      return Node(id << 1);
+    }
+    int maxANodeId() const {
+      return _aNodeNum;
+    }
+
+    static int bNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromBNodeId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxBNodeId() const {
+      return _bNodeNum;
+    }
+
+    Node aNode(const UEdge& edge) const {
+      return Node((edge.id / _bNodeNum) << 1);
+    }
+    Node bNode(const UEdge& edge) const {
+      return Node(((edge.id % _bNodeNum) << 1) + 1);
+    }
+
+    static bool aNode(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool bNode(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    static Node aNode(int index) {
+      return Node(index << 1);
+    }
+
+    static Node bNode(int index) {
+      return Node((index << 1) + 1);
+    }
+
+    typedef True NodeNumTag;
+    int nodeNum() const { return _aNodeNum + _bNodeNum; }
+    int aNodeNum() const { return _aNodeNum; }
+    int bNodeNum() const { return _bNodeNum; }
+
+    typedef True EdgeNumTag;
+    int uEdgeNum() const { return _edgeNum; }
+
+  };
+
+
+  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
+
+
+  /// \ingroup graphs
+  ///
+  /// \brief An undirected full bipartite graph class.
+  ///
+  /// This is a simple and fast bipartite undirected full graph implementation.
+  /// It is completely static, so you can neither add nor delete either
+  /// edges or nodes.
+  ///
+  /// \sa FullUGraphBase
+  /// \sa FullGraph
+  ///
+  /// \author Balazs Dezso
+  class FullBpUGraph : 
+    public ExtendedFullBpUGraphBase {
+  public:
+
+    typedef ExtendedFullBpUGraphBase Parent;
+
+    FullBpUGraph() {
+      Parent::construct(0, 0);
+    }
+
+    FullBpUGraph(int aNodeNum, int bNodeNum) {
+      Parent::construct(aNodeNum, bNodeNum);
+    }
+
+    /// \brief Resize the graph
+    ///
+    void resize(int n, int m) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      Parent::getNotifier(ANode()).clear();
+      Parent::getNotifier(BNode()).clear();
+      construct(n, m);
+      Parent::getNotifier(ANode()).build();
+      Parent::getNotifier(BNode()).build();
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
+  };
+
 } //namespace lemon
 
 
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/full_ugraph.h
--- a/lemon/full_ugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,280 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_FULL_UGRAPH_H
-#define LEMON_FULL_UGRAPH_H
-
-#include <cmath>
-
-#include <lemon/bits/base_extender.h>
-#include <lemon/bits/ugraph_extender.h>
-
-#include <lemon/bits/invalid.h>
-#include <lemon/bits/utility.h>
-
-
-///\ingroup graphs
-///\file
-///\brief FullUGraph classes.
-
-
-namespace lemon {
-
-  /// \brief Base of the FullUGrpah.
-  ///
-  /// Base of the FullUGrpah.
-  class FullUGraphBase {
-    int _nodeNum;
-    int _edgeNum;
-  public:
-
-    typedef FullUGraphBase Graph;
-
-    class Node;
-    class Edge;
-
-  public:
-
-    FullUGraphBase() {}
-
-
-    ///Creates a full graph with \c n nodes.
-    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
-
-    /// \brief Returns the node with the given index.
-    ///
-    /// Returns the node with the given index. Because it is a
-    /// static size graph the node's of the graph can be indiced
-    /// by the range from 0 to \e nodeNum()-1 and the index of
-    /// the node can accessed by the \e index() member.
-    Node operator()(int index) const { return Node(index); }
-
-    /// \brief Returns the index of the node.
-    ///
-    /// Returns the index of the node. Because it is a
-    /// static size graph the node's of the graph can be indiced
-    /// by the range from 0 to \e nodeNum()-1 and the index of
-    /// the node can accessed by the \e index() member.
-    int index(const Node& node) const { return node.id; }
-
-    typedef True NodeNumTag;
-    typedef True EdgeNumTag;
-
-    ///Number of nodes.
-    int nodeNum() const { return _nodeNum; }
-    ///Number of edges.
-    int edgeNum() const { return _edgeNum; }
-
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
-    int maxNodeId() const { return _nodeNum-1; }
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
-    int maxEdgeId() const { return _edgeNum-1; }
-
-    /// \brief Returns the node from its \c id.
-    ///
-    /// Returns the node from its \c id. If there is not node
-    /// with the given id the effect of the function is undefinied.
-    static Node nodeFromId(int id) { return Node(id);}
-
-    /// \brief Returns the edge from its \c id.
-    ///
-    /// Returns the edge from its \c id. If there is not edge
-    /// with the given id the effect of the function is undefinied.
-    static Edge edgeFromId(int id) { return Edge(id);}
-
-    Node source(Edge e) const { 
-      /// \todo we may do it faster
-      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
-    }
-
-    Node target(Edge e) const { 
-      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
-      return Node(e.id - (source) * (source - 1) / 2);
-    }
-
-
-    /// \brief Node ID.
-    ///
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    /// \return The ID of the node \c v. 
-
-    static int id(Node v) { return v.id; }
-
-    /// \brief Edge ID.
-    ///
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.id; }
-
-    /// \brief Finds an edge between two nodes.
-    ///
-    /// Finds an edge from node \c u to node \c v.
-    ///
-    /// If \c prev is \ref INVALID (this is the default value), then
-    /// It finds the first edge from \c u to \c v. Otherwise it looks for
-    /// the next edge from \c u to \c v after \c prev.
-    /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
-      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
-      return Edge(u.id * (u.id - 1) / 2 + v.id);
-    }
-
-    typedef True FindEdgeTag;
-    
-      
-    class Node {
-      friend class FullUGraphBase;
-
-    protected:
-      int id;
-      Node(int _id) { id = _id;}
-    public:
-      Node() {}
-      Node (Invalid) { id = -1; }
-      bool operator==(const Node node) const {return id == node.id;}
-      bool operator!=(const Node node) const {return id != node.id;}
-      bool operator<(const Node node) const {return id < node.id;}
-    };
-    
-
-
-    class Edge {
-      friend class FullUGraphBase;
-      
-    protected:
-      int id;  // _nodeNum * target + source;
-
-      Edge(int _id) : id(_id) {}
-
-    public:
-      Edge() { }
-      Edge (Invalid) { id = -1; }
-      bool operator==(const Edge edge) const {return id == edge.id;}
-      bool operator!=(const Edge edge) const {return id != edge.id;}
-      bool operator<(const Edge edge) const {return id < edge.id;}
-    };
-
-    void first(Node& node) const {
-      node.id = _nodeNum - 1;
-    }
-
-    static void next(Node& node) {
-      --node.id;
-    }
-
-    void first(Edge& edge) const {
-      edge.id = _edgeNum - 1;
-    }
-
-    static void next(Edge& edge) {
-      --edge.id;
-    }
-
-    void firstOut(Edge& edge, const Node& node) const {      
-      int src = node.id;
-      int trg = 0;
-      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
-    }
-
-    /// \todo with specialized iterators we can make faster iterating
-    void nextOut(Edge& edge) const {
-      int src = source(edge).id;
-      int trg = target(edge).id;
-      ++trg;
-      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
-    }
-
-    void firstIn(Edge& edge, const Node& node) const {
-      int src = node.id + 1;
-      int trg = node.id;
-      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
-    }
-    
-    void nextIn(Edge& edge) const {
-      int src = source(edge).id;
-      int trg = target(edge).id;
-      ++src;
-      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
-    }
-
-  };
-
-  typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> > 
-  ExtendedFullUGraphBase;
-
-  /// \ingroup graphs
-  ///
-  /// \brief An undirected full graph class.
-  ///
-  /// This is a simple and fast undirected full graph implementation.
-  /// It is completely static, so you can neither add nor delete either
-  /// edges or nodes.
-  ///
-  /// The main difference beetween the \e FullGraph and \e FullUGraph class
-  /// is that this class conforms to the undirected graph concept and
-  /// it does not contain the loop edges.
-  ///
-  /// \sa FullUGraphBase
-  /// \sa FullGraph
-  ///
-  /// \author Balazs Dezso
-  class FullUGraph : public ExtendedFullUGraphBase {
-  public:
-
-    typedef ExtendedFullUGraphBase Parent;
-
-    /// \brief Constructor
-    FullUGraph() { construct(0); }
-
-    /// \brief Constructor
-    FullUGraph(int n) { construct(n); }
-
-    /// \brief Resize the graph
-    ///
-    /// Resize the graph. The function will fully destroy and build the graph.
-    /// This cause that the maps of the graph will reallocated
-    /// automatically and the previous values will be lost.
-    void resize(int n) {
-      Parent::getNotifier(Edge()).clear();
-      Parent::getNotifier(UEdge()).clear();
-      Parent::getNotifier(Node()).clear();
-      construct(n);
-      Parent::getNotifier(Node()).build();
-      Parent::getNotifier(UEdge()).build();
-      Parent::getNotifier(Edge()).build();
-    }
-  };
-
-} //namespace lemon
-
-
-#endif //LEMON_FULL_GRAPH_H
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/grid_ugraph.h
--- a/lemon/grid_ugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/grid_ugraph.h	Fri Jun 30 12:15:45 2006 +0000
@@ -24,7 +24,7 @@
 #include <lemon/bits/utility.h>
 
 #include <lemon/bits/base_extender.h>
-#include <lemon/bits/ugraph_extender.h>
+#include <lemon/bits/graph_extender.h>
 
 #include <lemon/xy.h>
 
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/list_bpugraph.h
--- a/lemon/list_bpugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,398 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_LIST_BPUGRAPH_H
-#define LEMON_LIST_BPUGRAPH_H
-
-///\ingroup graphs
-///\file
-///\brief ListBpUGraph classes.
-
-#include <lemon/bits/bpugraph_extender.h>
-
-#include <lemon/error.h>
-
-#include <vector>
-#include <list>
-
-namespace lemon {
-
-  class ListBpUGraphBase {
-  public:
-
-    class NodeSetError : public LogicError {
-      virtual const char* exceptionName() const { 
-	return "lemon::ListBpUGraph::NodeSetError";
-      }
-    };
-
-  protected:
-
-    struct NodeT {
-      int first_edge, prev, next;
-    };
-
-    struct UEdgeT {
-      int aNode, prev_out, next_out;
-      int bNode, prev_in, next_in;
-    };
-
-    std::vector<NodeT> aNodes;
-    std::vector<NodeT> bNodes;
-
-    std::vector<UEdgeT> edges;
-
-    int first_anode;
-    int first_free_anode;
-
-    int first_bnode;
-    int first_free_bnode;
-
-    int first_free_edge;
-
-  public:
-  
-    class Node {
-      friend class ListBpUGraphBase;
-    protected:
-      int id;
-
-      explicit 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 UEdge {
-      friend class ListBpUGraphBase;
-    protected:
-      int id;
-
-      explicit UEdge(int _id) { id = _id;}
-    public:
-      UEdge() {}
-      UEdge (Invalid) { id = -1; }
-      bool operator==(const UEdge i) const {return id==i.id;}
-      bool operator!=(const UEdge i) const {return id!=i.id;}
-      bool operator<(const UEdge i) const {return id<i.id;}
-    };
-
-    ListBpUGraphBase()
-      : first_anode(-1), first_free_anode(-1),
-        first_bnode(-1), first_free_bnode(-1),
-        first_free_edge(-1) {}
-
-    void firstANode(Node& node) const {
-      node.id = first_anode != -1 ? (first_anode << 1) : -1;
-    }
-    void nextANode(Node& node) const {
-      node.id = aNodes[node.id >> 1].next;
-    }
-
-    void firstBNode(Node& node) const {
-      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
-    }
-    void nextBNode(Node& node) const {
-      node.id = bNodes[node.id >> 1].next;
-    }
-
-    void first(Node& node) const {
-      if (first_anode != -1) {
-        node.id = (first_anode << 1);
-      } else if (first_bnode != -1) {
-        node.id = (first_bnode << 1) + 1;
-      } else {
-        node.id = -1;
-      }
-    }
-    void next(Node& node) const {
-      if (aNode(node)) {
-        node.id = aNodes[node.id >> 1].next;
-        if (node.id == -1) {
-          if (first_bnode != -1) {
-            node.id = (first_bnode << 1) + 1;
-          }
-        }
-      } else {
-        node.id = bNodes[node.id >> 1].next;
-      }
-    }
-  
-    void first(UEdge& edge) const {
-      int aNodeId = first_anode;
-      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
-        aNodeId = aNodes[aNodeId].next != -1 ? 
-          aNodes[aNodeId].next >> 1 : -1;
-      }
-      if (aNodeId != -1) {
-        edge.id = aNodes[aNodeId].first_edge;
-      } else {
-        edge.id = -1;
-      }
-    }
-    void next(UEdge& edge) const {
-      int aNodeId = edges[edge.id].aNode >> 1;
-      edge.id = edges[edge.id].next_out;
-      if (edge.id == -1) {
-        aNodeId = aNodes[aNodeId].next != -1 ? 
-          aNodes[aNodeId].next >> 1 : -1;
-        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
-          aNodeId = aNodes[aNodeId].next != -1 ? 
-          aNodes[aNodeId].next >> 1 : -1;
-        }
-        if (aNodeId != -1) {
-          edge.id = aNodes[aNodeId].first_edge;
-        } else {
-          edge.id = -1;
-        }
-      }
-    }
-
-    void firstFromANode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
-      edge.id = aNodes[node.id >> 1].first_edge;
-    }
-    void nextFromANode(UEdge& edge) const {
-      edge.id = edges[edge.id].next_out;
-    }
-
-    void firstFromBNode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
-      edge.id = bNodes[node.id >> 1].first_edge;
-    }
-    void nextFromBNode(UEdge& edge) const {
-      edge.id = edges[edge.id].next_in;
-    }
-
-    static int id(const Node& node) {
-      return node.id;
-    }
-    static Node nodeFromId(int id) {
-      return Node(id);
-    }
-    int maxNodeId() const {
-      return aNodes.size() > bNodes.size() ?
-	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
-    }
-  
-    static int id(const UEdge& edge) {
-      return edge.id;
-    }
-    static UEdge uEdgeFromId(int id) {
-      return UEdge(id);
-    }
-    int maxUEdgeId() const {
-      return edges.size();
-    }
-  
-    static int aNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromANodeId(int id) {
-      return Node(id << 1);
-    }
-    int maxANodeId() const {
-      return aNodes.size();
-    }
-
-    static int bNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromBNodeId(int id) {
-      return Node((id << 1) + 1);
-    }
-    int maxBNodeId() const {
-      return bNodes.size();
-    }
-
-    Node aNode(const UEdge& edge) const {
-      return Node(edges[edge.id].aNode);
-    }
-    Node bNode(const UEdge& edge) const {
-      return Node(edges[edge.id].bNode);
-    }
-
-    static bool aNode(const Node& node) {
-      return (node.id & 1) == 0;
-    }
-
-    static bool bNode(const Node& node) {
-      return (node.id & 1) == 1;
-    }
-
-    Node addANode() {
-      int aNodeId;
-      if (first_free_anode == -1) {
-        aNodeId = aNodes.size();
-        aNodes.push_back(NodeT());
-      } else {
-        aNodeId = first_free_anode;
-        first_free_anode = aNodes[first_free_anode].next;
-      }
-      if (first_anode != -1) {
-        aNodes[aNodeId].next = first_anode << 1;
-        aNodes[first_anode].prev = aNodeId << 1;
-      } else {
-        aNodes[aNodeId].next = -1;
-      }
-      aNodes[aNodeId].prev = -1;
-      first_anode = aNodeId;
-      aNodes[aNodeId].first_edge = -1;
-      return Node(aNodeId << 1);
-    }
-
-    Node addBNode() {
-      int bNodeId;
-      if (first_free_bnode == -1) {
-        bNodeId = bNodes.size();
-        bNodes.push_back(NodeT());
-      } else {
-        bNodeId = first_free_bnode;
-        first_free_bnode = bNodes[first_free_bnode].next;
-      }
-      if (first_bnode != -1) {
-        bNodes[bNodeId].next = (first_bnode << 1) + 1;
-        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
-      } else {
-        bNodes[bNodeId].next = -1;
-      }
-      first_bnode = bNodeId;
-      bNodes[bNodeId].first_edge = -1;
-      return Node((bNodeId << 1) + 1);
-    }
-
-    UEdge addEdge(const Node& source, const Node& target) {
-      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
-      int edgeId;
-      if (first_free_edge != -1) {
-        edgeId = first_free_edge;
-        first_free_edge = edges[edgeId].next_out;
-      } else {
-        edgeId = edges.size();
-        edges.push_back(UEdgeT());
-      }
-      if ((source.id & 1) == 0) {
-	edges[edgeId].aNode = source.id;
-	edges[edgeId].bNode = target.id;
-      } else {
-	edges[edgeId].aNode = target.id;
-	edges[edgeId].bNode = source.id;
-      }
-      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
-      edges[edgeId].prev_out = -1;
-      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
-        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
-      }
-      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
-      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
-      edges[edgeId].prev_in = -1;
-      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
-        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
-      }
-      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
-      return UEdge(edgeId);
-    }
-
-    void erase(const Node& node) {
-      if (aNode(node)) {
-        int aNodeId = node.id >> 1;
-        if (aNodes[aNodeId].prev != -1) {
-          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
-        } else {
-          first_anode = aNodes[aNodeId].next >> 1;
-        }
-        if (aNodes[aNodeId].next != -1) {
-          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
-        }
-        aNodes[aNodeId].next = first_free_anode;
-        first_free_anode = aNodeId;
-      } else {
-        int bNodeId = node.id >> 1;
-        if (bNodes[bNodeId].prev != -1) {
-          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
-        } else {
-          first_bnode = bNodes[bNodeId].next >> 1;
-        }
-        if (bNodes[bNodeId].next != -1) {
-          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
-        }
-        bNodes[bNodeId].next = first_free_bnode;
-        first_free_bnode = bNodeId;
-      }
-    }
-
-    void erase(const UEdge& edge) {
-
-      if (edges[edge.id].prev_out != -1) {
-        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
-      } else {
-        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
-      }
-      if (edges[edge.id].next_out != -1) {
-        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
-      }
-
-      if (edges[edge.id].prev_in != -1) {
-        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
-      } else {
-        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
-      }
-      if (edges[edge.id].next_in != -1) {
-        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
-      }
-
-      edges[edge.id].next_out = first_free_edge;
-      first_free_edge = edge.id;
-    }
-
-    void clear() {
-      aNodes.clear();
-      bNodes.clear();
-      edges.clear();
-      first_anode = -1;
-      first_free_anode = -1;
-      first_bnode = -1;
-      first_free_bnode = -1;
-      first_free_edge = -1;
-    }
-
-  };
-
-
-  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
-
-  /// \ingroup graphs
-  ///
-  /// \brief A smart bipartite undirected graph class.
-  ///
-  /// This is a bipartite undirected graph implementation.
-  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 
-  /// concept.
-  /// \sa concept::BpUGraph.
-  ///
-  class ListBpUGraph : public ExtendedListBpUGraphBase {};
-
-  
-  /// @}  
-} //namespace lemon
-  
-
-#endif
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/list_graph.h
--- a/lemon/list_graph.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/list_graph.h	Fri Jun 30 12:15:45 2006 +0000
@@ -21,10 +21,13 @@
 
 ///\ingroup graphs
 ///\file
-///\brief ListGraph class.
+///\brief ListGraph, ListUGraph classes.
 
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 
+#include <lemon/error.h>
+
 #include <vector>
 #include <list>
 
@@ -306,7 +309,8 @@
 
   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
 
-  /// \ingroup graphs
+  /// \addtogroup graphs
+  /// @{
 
   ///A list graph class.
 
@@ -701,6 +705,454 @@
     
   };
 
+  ///@}
+
+  /**************** Undirected List Graph ****************/
+
+  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
+  ExtendedListUGraphBase;
+
+  /// \addtogroup graphs
+  /// @{
+
+  ///An undirected list graph class.
+
+  ///This is a simple and fast erasable undirected graph implementation.
+  ///
+  ///It conforms to the
+  ///\ref concept::UGraph "UGraph" concept.
+  ///
+  ///\sa concept::UGraph.
+  ///
+  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
+  ///haven't been implemented yet.
+  ///
+  class ListUGraph : public ExtendedListUGraphBase {
+  public:
+    typedef ExtendedListUGraphBase Parent;
+    /// \brief Add a new node to the graph.
+    ///
+    /// \return the new node.
+    ///
+    Node addNode() { return Parent::addNode(); }
+
+    /// \brief Add a new edge to the graph.
+    ///
+    /// Add a new edge to the graph with source node \c s
+    /// and target node \c t.
+    /// \return the new undirected edge.
+    UEdge addEdge(const Node& s, const Node& t) { 
+      return Parent::addEdge(s, t); 
+    }
+    /// \brief Changes the target of \c e to \c n
+    ///
+    /// Changes the target of \c e to \c n
+    ///
+    /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
+    /// referencing the changed edge remain
+    /// valid. However <tt>InEdge</tt>'s are invalidated.
+    void changeTarget(UEdge e, Node n) { 
+      Parent::changeTarget(e,n); 
+    }
+    /// Changes the source of \c e to \c n
+    ///
+    /// Changes the source of \c e to \c n
+    ///
+    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
+    ///referencing the changed edge remain
+    ///valid. However <tt>OutEdge</tt>'s are invalidated.
+    void changeSource(UEdge e, Node n) { 
+      Parent::changeSource(e,n); 
+    }
+    /// \brief Contract two nodes.
+    ///
+    /// This function contracts two nodes.
+    ///
+    /// Node \p b will be removed but instead of deleting
+    /// its neighboring edges, they will be joined to \p a.
+    /// The last parameter \p r controls whether to remove loops. \c true
+    /// means that loops will be removed.
+    ///
+    /// \note The <tt>Edge</tt>s
+    /// referencing a moved edge remain
+    /// valid.
+    void contract(Node a, Node b, bool r = true) {
+      for(IncEdgeIt e(*this, b); e!=INVALID;) {
+	IncEdgeIt f = e; ++f;
+	if (r && runningNode(e) == a) {
+	  erase(e);
+	} else if (source(e) == b) {
+	  changeSource(e, a);
+	} else {
+	  changeTarget(e, a);
+	}
+	e = f;
+      }
+      erase(b);
+    }
+  };
+
+
+  class ListBpUGraphBase {
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+	return "lemon::ListBpUGraph::NodeSetError";
+      }
+    };
+
+  protected:
+
+    struct NodeT {
+      int first_edge, prev, next;
+    };
+
+    struct UEdgeT {
+      int aNode, prev_out, next_out;
+      int bNode, prev_in, next_in;
+    };
+
+    std::vector<NodeT> aNodes;
+    std::vector<NodeT> bNodes;
+
+    std::vector<UEdgeT> edges;
+
+    int first_anode;
+    int first_free_anode;
+
+    int first_bnode;
+    int first_free_bnode;
+
+    int first_free_edge;
+
+  public:
+  
+    class Node {
+      friend class ListBpUGraphBase;
+    protected:
+      int id;
+
+      explicit 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 UEdge {
+      friend class ListBpUGraphBase;
+    protected:
+      int id;
+
+      explicit UEdge(int _id) { id = _id;}
+    public:
+      UEdge() {}
+      UEdge (Invalid) { id = -1; }
+      bool operator==(const UEdge i) const {return id==i.id;}
+      bool operator!=(const UEdge i) const {return id!=i.id;}
+      bool operator<(const UEdge i) const {return id<i.id;}
+    };
+
+    ListBpUGraphBase()
+      : first_anode(-1), first_free_anode(-1),
+        first_bnode(-1), first_free_bnode(-1),
+        first_free_edge(-1) {}
+
+    void firstANode(Node& node) const {
+      node.id = first_anode != -1 ? (first_anode << 1) : -1;
+    }
+    void nextANode(Node& node) const {
+      node.id = aNodes[node.id >> 1].next;
+    }
+
+    void firstBNode(Node& node) const {
+      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
+    }
+    void nextBNode(Node& node) const {
+      node.id = bNodes[node.id >> 1].next;
+    }
+
+    void first(Node& node) const {
+      if (first_anode != -1) {
+        node.id = (first_anode << 1);
+      } else if (first_bnode != -1) {
+        node.id = (first_bnode << 1) + 1;
+      } else {
+        node.id = -1;
+      }
+    }
+    void next(Node& node) const {
+      if (aNode(node)) {
+        node.id = aNodes[node.id >> 1].next;
+        if (node.id == -1) {
+          if (first_bnode != -1) {
+            node.id = (first_bnode << 1) + 1;
+          }
+        }
+      } else {
+        node.id = bNodes[node.id >> 1].next;
+      }
+    }
+  
+    void first(UEdge& edge) const {
+      int aNodeId = first_anode;
+      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
+        aNodeId = aNodes[aNodeId].next != -1 ? 
+          aNodes[aNodeId].next >> 1 : -1;
+      }
+      if (aNodeId != -1) {
+        edge.id = aNodes[aNodeId].first_edge;
+      } else {
+        edge.id = -1;
+      }
+    }
+    void next(UEdge& edge) const {
+      int aNodeId = edges[edge.id].aNode >> 1;
+      edge.id = edges[edge.id].next_out;
+      if (edge.id == -1) {
+        aNodeId = aNodes[aNodeId].next != -1 ? 
+          aNodes[aNodeId].next >> 1 : -1;
+        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
+          aNodeId = aNodes[aNodeId].next != -1 ? 
+          aNodes[aNodeId].next >> 1 : -1;
+        }
+        if (aNodeId != -1) {
+          edge.id = aNodes[aNodeId].first_edge;
+        } else {
+          edge.id = -1;
+        }
+      }
+    }
+
+    void firstFromANode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = aNodes[node.id >> 1].first_edge;
+    }
+    void nextFromANode(UEdge& edge) const {
+      edge.id = edges[edge.id].next_out;
+    }
+
+    void firstFromBNode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = bNodes[node.id >> 1].first_edge;
+    }
+    void nextFromBNode(UEdge& edge) const {
+      edge.id = edges[edge.id].next_in;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return aNodes.size() > bNodes.size() ?
+	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
+    }
+  
+    static int id(const UEdge& edge) {
+      return edge.id;
+    }
+    static UEdge uEdgeFromId(int id) {
+      return UEdge(id);
+    }
+    int maxUEdgeId() const {
+      return edges.size();
+    }
+  
+    static int aNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromANodeId(int id) {
+      return Node(id << 1);
+    }
+    int maxANodeId() const {
+      return aNodes.size();
+    }
+
+    static int bNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromBNodeId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxBNodeId() const {
+      return bNodes.size();
+    }
+
+    Node aNode(const UEdge& edge) const {
+      return Node(edges[edge.id].aNode);
+    }
+    Node bNode(const UEdge& edge) const {
+      return Node(edges[edge.id].bNode);
+    }
+
+    static bool aNode(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool bNode(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    Node addANode() {
+      int aNodeId;
+      if (first_free_anode == -1) {
+        aNodeId = aNodes.size();
+        aNodes.push_back(NodeT());
+      } else {
+        aNodeId = first_free_anode;
+        first_free_anode = aNodes[first_free_anode].next;
+      }
+      if (first_anode != -1) {
+        aNodes[aNodeId].next = first_anode << 1;
+        aNodes[first_anode].prev = aNodeId << 1;
+      } else {
+        aNodes[aNodeId].next = -1;
+      }
+      aNodes[aNodeId].prev = -1;
+      first_anode = aNodeId;
+      aNodes[aNodeId].first_edge = -1;
+      return Node(aNodeId << 1);
+    }
+
+    Node addBNode() {
+      int bNodeId;
+      if (first_free_bnode == -1) {
+        bNodeId = bNodes.size();
+        bNodes.push_back(NodeT());
+      } else {
+        bNodeId = first_free_bnode;
+        first_free_bnode = bNodes[first_free_bnode].next;
+      }
+      if (first_bnode != -1) {
+        bNodes[bNodeId].next = (first_bnode << 1) + 1;
+        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
+      } else {
+        bNodes[bNodeId].next = -1;
+      }
+      first_bnode = bNodeId;
+      bNodes[bNodeId].first_edge = -1;
+      return Node((bNodeId << 1) + 1);
+    }
+
+    UEdge addEdge(const Node& source, const Node& target) {
+      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
+      int edgeId;
+      if (first_free_edge != -1) {
+        edgeId = first_free_edge;
+        first_free_edge = edges[edgeId].next_out;
+      } else {
+        edgeId = edges.size();
+        edges.push_back(UEdgeT());
+      }
+      if ((source.id & 1) == 0) {
+	edges[edgeId].aNode = source.id;
+	edges[edgeId].bNode = target.id;
+      } else {
+	edges[edgeId].aNode = target.id;
+	edges[edgeId].bNode = source.id;
+      }
+      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
+      edges[edgeId].prev_out = -1;
+      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
+        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
+      }
+      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
+      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
+      edges[edgeId].prev_in = -1;
+      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
+        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
+      }
+      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
+      return UEdge(edgeId);
+    }
+
+    void erase(const Node& node) {
+      if (aNode(node)) {
+        int aNodeId = node.id >> 1;
+        if (aNodes[aNodeId].prev != -1) {
+          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
+        } else {
+          first_anode = aNodes[aNodeId].next >> 1;
+        }
+        if (aNodes[aNodeId].next != -1) {
+          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
+        }
+        aNodes[aNodeId].next = first_free_anode;
+        first_free_anode = aNodeId;
+      } else {
+        int bNodeId = node.id >> 1;
+        if (bNodes[bNodeId].prev != -1) {
+          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
+        } else {
+          first_bnode = bNodes[bNodeId].next >> 1;
+        }
+        if (bNodes[bNodeId].next != -1) {
+          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
+        }
+        bNodes[bNodeId].next = first_free_bnode;
+        first_free_bnode = bNodeId;
+      }
+    }
+
+    void erase(const UEdge& edge) {
+
+      if (edges[edge.id].prev_out != -1) {
+        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
+      } else {
+        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
+      }
+      if (edges[edge.id].next_out != -1) {
+        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
+      }
+
+      if (edges[edge.id].prev_in != -1) {
+        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
+      } else {
+        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
+      }
+      if (edges[edge.id].next_in != -1) {
+        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
+      }
+
+      edges[edge.id].next_out = first_free_edge;
+      first_free_edge = edge.id;
+    }
+
+    void clear() {
+      aNodes.clear();
+      bNodes.clear();
+      edges.clear();
+      first_anode = -1;
+      first_free_anode = -1;
+      first_bnode = -1;
+      first_free_bnode = -1;
+      first_free_edge = -1;
+    }
+
+  };
+
+
+  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief A smart bipartite undirected graph class.
+  ///
+  /// This is a bipartite undirected graph implementation.
+  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" 
+  /// concept.
+  /// \sa concept::BpUGraph.
+  ///
+  class ListBpUGraph : public ExtendedListBpUGraphBase {};
+
+  
+  /// @}  
 } //namespace lemon
   
 
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/list_ugraph.h
--- a/lemon/list_ugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,120 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_LIST_UGRAPH_H
-#define LEMON_LIST_UGRAPH_H
-
-///\ingroup graphs
-///\file
-///\brief ListUGraph classes.
-
-#include <lemon/list_graph.h>
-#include <lemon/bits/base_extender.h>
-#include <lemon/bits/ugraph_extender.h>
-
-#include <vector>
-#include <list>
-
-namespace lemon {
-
-  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
-  ExtendedListUGraphBase;
-
-  /// \ingroup graphs
-
-  ///An undirected list graph class.
-
-  ///This is a simple and fast erasable undirected graph implementation.
-  ///
-  ///It conforms to the
-  ///\ref concept::UGraph "UGraph" concept.
-  ///
-  ///\sa concept::UGraph.
-  ///
-  ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
-  ///haven't been implemented yet.
-  ///
-  class ListUGraph : public ExtendedListUGraphBase {
-  public:
-    typedef ExtendedListUGraphBase Parent;
-    /// \brief Add a new node to the graph.
-    ///
-    /// \return the new node.
-    ///
-    Node addNode() { return Parent::addNode(); }
-
-    /// \brief Add a new edge to the graph.
-    ///
-    /// Add a new edge to the graph with source node \c s
-    /// and target node \c t.
-    /// \return the new undirected edge.
-    UEdge addEdge(const Node& s, const Node& t) { 
-      return Parent::addEdge(s, t); 
-    }
-    /// \brief Changes the target of \c e to \c n
-    ///
-    /// Changes the target of \c e to \c n
-    ///
-    /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
-    /// referencing the changed edge remain
-    /// valid. However <tt>InEdge</tt>'s are invalidated.
-    void changeTarget(UEdge e, Node n) { 
-      Parent::changeTarget(e,n); 
-    }
-    /// Changes the source of \c e to \c n
-    ///
-    /// Changes the source of \c e to \c n
-    ///
-    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
-    ///referencing the changed edge remain
-    ///valid. However <tt>OutEdge</tt>'s are invalidated.
-    void changeSource(UEdge e, Node n) { 
-      Parent::changeSource(e,n); 
-    }
-    /// \brief Contract two nodes.
-    ///
-    /// This function contracts two nodes.
-    ///
-    /// Node \p b will be removed but instead of deleting
-    /// its neighboring edges, they will be joined to \p a.
-    /// The last parameter \p r controls whether to remove loops. \c true
-    /// means that loops will be removed.
-    ///
-    /// \note The <tt>Edge</tt>s
-    /// referencing a moved edge remain
-    /// valid.
-    void contract(Node a, Node b, bool r = true) {
-      for(IncEdgeIt e(*this, b); e!=INVALID;) {
-	IncEdgeIt f = e; ++f;
-	if (r && runningNode(e) == a) {
-	  erase(e);
-	} else if (source(e) == b) {
-	  changeSource(e, a);
-	} else {
-	  changeTarget(e, a);
-	}
-	e = f;
-      }
-      erase(b);
-    }
-  };
-
-} //namespace lemon
-  
-
-#endif
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/min_cut.h
--- a/lemon/min_cut.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/min_cut.h	Fri Jun 30 12:15:45 2006 +0000
@@ -23,7 +23,6 @@
 /// \brief Maximum cardinality search and min cut in undirected graphs.
 
 #include <lemon/list_graph.h>
-#include <lemon/list_ugraph.h>
 #include <lemon/bin_heap.h>
 #include <lemon/bucket_heap.h>
 
@@ -195,7 +194,7 @@
 #ifdef DOXYGEN
   template <typename _Graph, typename _CapacityMap, typename _Traits>
 #else
-  template <typename _Graph = ListGraph,
+  template <typename _Graph = ListUGraph,
 	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,
 	    typename _Traits = 
             MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/smart_bpugraph.h
--- a/lemon/smart_bpugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,273 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_SMART_BPUGRAPH_H
-#define LEMON_SMART_BPUGRAPH_H
-
-///\ingroup graphs
-///\file
-///\brief SmartBpUGraph class.
-
-#include <vector>
-
-#include <lemon/bits/invalid.h>
-
-#include <lemon/bits/bpugraph_extender.h>
-
-#include <lemon/bits/utility.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/graph_extender.h>
-
-namespace lemon {
-
-  class SmartBpUGraphBase {
-  public:
-
-    class NodeSetError : public LogicError {
-      virtual const char* exceptionName() const { 
-	return "lemon::SmartBpUGraph::NodeSetError";
-      }
-    };
-
-  protected:
-
-    struct NodeT {
-      int first;
-      NodeT() {}
-      NodeT(int _first) : first(_first) {}
-    };
-
-    struct UEdgeT {
-      int aNode, next_out;
-      int bNode, next_in;
-    };
-
-    std::vector<NodeT> aNodes;
-    std::vector<NodeT> bNodes;
-
-    std::vector<UEdgeT> edges;
-
-  public:
-  
-    class Node {
-      friend class SmartBpUGraphBase;
-    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 UEdge {
-      friend class SmartBpUGraphBase;
-    protected:
-      int id;
-
-      UEdge(int _id) { id = _id;}
-    public:
-      UEdge() {}
-      UEdge (Invalid) { id = -1; }
-      bool operator==(const UEdge i) const {return id==i.id;}
-      bool operator!=(const UEdge i) const {return id!=i.id;}
-      bool operator<(const UEdge i) const {return id<i.id;}
-    };
-
-    void firstANode(Node& node) const {
-      node.id = 2 * aNodes.size() - 2;
-      if (node.id < 0) node.id = -1; 
-    }
-    void nextANode(Node& node) const {
-      node.id -= 2;
-      if (node.id < 0) node.id = -1; 
-    }
-
-    void firstBNode(Node& node) const {
-      node.id = 2 * bNodes.size() - 1;
-    }
-    void nextBNode(Node& node) const {
-      node.id -= 2;
-    }
-
-    void first(Node& node) const {
-      if (aNodes.size() > 0) {
-	node.id = 2 * aNodes.size() - 2;
-      } else {
-	node.id = 2 * bNodes.size() - 1;
-      }
-    }
-    void next(Node& node) const {
-      node.id -= 2;
-      if (node.id == -2) {
-	node.id = 2 * bNodes.size() - 1;
-      }
-    }
-  
-    void first(UEdge& edge) const {
-      edge.id = edges.size() - 1;
-    }
-    void next(UEdge& edge) const {
-      --edge.id;
-    }
-
-    void firstFromANode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
-      edge.id = aNodes[node.id >> 1].first;
-    }
-    void nextFromANode(UEdge& edge) const {
-      edge.id = edges[edge.id].next_out;
-    }
-
-    void firstFromBNode(UEdge& edge, const Node& node) const {
-      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
-      edge.id = bNodes[node.id >> 1].first;
-    }
-    void nextFromBNode(UEdge& edge) const {
-      edge.id = edges[edge.id].next_in;
-    }
-
-    static int id(const Node& node) {
-      return node.id;
-    }
-    static Node nodeFromId(int id) {
-      return Node(id);
-    }
-    int maxNodeId() const {
-      return aNodes.size() > bNodes.size() ?
-	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
-    }
-  
-    static int id(const UEdge& edge) {
-      return edge.id;
-    }
-    static UEdge uEdgeFromId(int id) {
-      return UEdge(id);
-    }
-    int maxUEdgeId() const {
-      return edges.size();
-    }
-  
-    static int aNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromANodeId(int id) {
-      return Node(id << 1);
-    }
-    int maxANodeId() const {
-      return aNodes.size();
-    }
-
-    static int bNodeId(const Node& node) {
-      return node.id >> 1;
-    }
-    static Node fromBNodeId(int id) {
-      return Node((id << 1) + 1);
-    }
-    int maxBNodeId() const {
-      return bNodes.size();
-    }
-
-    Node aNode(const UEdge& edge) const {
-      return Node(edges[edge.id].aNode);
-    }
-    Node bNode(const UEdge& edge) const {
-      return Node(edges[edge.id].bNode);
-    }
-
-    static bool aNode(const Node& node) {
-      return (node.id & 1) == 0;
-    }
-
-    static bool bNode(const Node& node) {
-      return (node.id & 1) == 1;
-    }
-
-    Node addANode() {
-      NodeT nodeT;
-      nodeT.first = -1;
-      aNodes.push_back(nodeT);
-      return Node(aNodes.size() * 2 - 2);
-    }
-
-    Node addBNode() {
-      NodeT nodeT;
-      nodeT.first = -1;
-      bNodes.push_back(nodeT);
-      return Node(bNodes.size() * 2 - 1);
-    }
-
-    UEdge addEdge(const Node& source, const Node& target) {
-      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
-      UEdgeT edgeT;
-      if ((source.id & 1) == 0) {
-	edgeT.aNode = source.id;
-	edgeT.bNode = target.id;
-      } else {
-	edgeT.aNode = target.id;
-	edgeT.bNode = source.id;
-      }
-      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
-      aNodes[edgeT.aNode >> 1].first = edges.size();
-      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
-      bNodes[edgeT.bNode >> 1].first = edges.size();
-      edges.push_back(edgeT);
-      return UEdge(edges.size() - 1);
-    }
-
-    void clear() {
-      aNodes.clear();
-      bNodes.clear();
-      edges.clear();
-    }
-
-    typedef True NodeNumTag;
-    int nodeNum() const { return aNodes.size() + bNodes.size(); }
-    int aNodeNum() const { return aNodes.size(); }
-    int bNodeNum() const { return bNodes.size(); }
-
-    typedef True EdgeNumTag;
-    int uEdgeNum() const { return edges.size(); }
-
-  };
-
-
-  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
-
-  /// \ingroup graphs
-  ///
-  /// \brief A smart bipartite undirected graph class.
-  ///
-  /// This is a simple and fast bipartite undirected graph implementation.
-  /// It is also quite memory efficient, but at the price
-  /// that <b> it does not support node and edge deletions</b>.
-  /// Except from this it conforms to 
-  /// the \ref concept::BpUGraph "BpUGraph" concept.
-  /// \sa concept::BpUGraph.
-  ///
-  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
-
-  
-} //namespace lemon
-
-
-#endif //LEMON_SMART_GRAPH_H
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/smart_graph.h
--- a/lemon/smart_graph.h	Fri Jun 30 12:14:36 2006 +0000
+++ b/lemon/smart_graph.h	Fri Jun 30 12:15:45 2006 +0000
@@ -21,15 +21,17 @@
 
 ///\ingroup graphs
 ///\file
-///\brief SmartGraph class.
+///\brief SmartGraph and SmartUGraph classes.
 
 #include <vector>
 
 #include <lemon/bits/invalid.h>
 
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 
 #include <lemon/bits/utility.h>
+#include <lemon/error.h>
 
 #include <lemon/bits/graph_extender.h>
 
@@ -354,6 +356,261 @@
   };
 
 
+  /**************** Undirected List Graph ****************/
+
+  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
+  ExtendedSmartUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief A smart undirected graph class.
+  ///
+  /// This is a simple and fast undirected graph implementation.
+  /// It is also quite memory efficient, but at the price
+  /// that <b> it does support only limited (only stack-like)
+  /// node and edge deletions</b>.
+  /// Except from this it conforms to 
+  /// the \ref concept::UGraph "UGraph" concept.
+  /// \sa concept::UGraph.
+  ///
+  /// \todo Snapshot hasn't been implemented yet.
+  ///
+  class SmartUGraph : public ExtendedSmartUGraphBase {
+  };
+
+
+  class SmartBpUGraphBase {
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+	return "lemon::SmartBpUGraph::NodeSetError";
+      }
+    };
+
+  protected:
+
+    struct NodeT {
+      int first;
+      NodeT() {}
+      NodeT(int _first) : first(_first) {}
+    };
+
+    struct UEdgeT {
+      int aNode, next_out;
+      int bNode, next_in;
+    };
+
+    std::vector<NodeT> aNodes;
+    std::vector<NodeT> bNodes;
+
+    std::vector<UEdgeT> edges;
+
+  public:
+  
+    class Node {
+      friend class SmartBpUGraphBase;
+    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 UEdge {
+      friend class SmartBpUGraphBase;
+    protected:
+      int id;
+
+      UEdge(int _id) { id = _id;}
+    public:
+      UEdge() {}
+      UEdge (Invalid) { id = -1; }
+      bool operator==(const UEdge i) const {return id==i.id;}
+      bool operator!=(const UEdge i) const {return id!=i.id;}
+      bool operator<(const UEdge i) const {return id<i.id;}
+    };
+
+    void firstANode(Node& node) const {
+      node.id = 2 * aNodes.size() - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextANode(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    void firstBNode(Node& node) const {
+      node.id = 2 * bNodes.size() - 1;
+    }
+    void nextBNode(Node& node) const {
+      node.id -= 2;
+    }
+
+    void first(Node& node) const {
+      if (aNodes.size() > 0) {
+	node.id = 2 * aNodes.size() - 2;
+      } else {
+	node.id = 2 * bNodes.size() - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+	node.id = 2 * bNodes.size() - 1;
+      }
+    }
+  
+    void first(UEdge& edge) const {
+      edge.id = edges.size() - 1;
+    }
+    void next(UEdge& edge) const {
+      --edge.id;
+    }
+
+    void firstFromANode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = aNodes[node.id >> 1].first;
+    }
+    void nextFromANode(UEdge& edge) const {
+      edge.id = edges[edge.id].next_out;
+    }
+
+    void firstFromBNode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = bNodes[node.id >> 1].first;
+    }
+    void nextFromBNode(UEdge& edge) const {
+      edge.id = edges[edge.id].next_in;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return aNodes.size() > bNodes.size() ?
+	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
+    }
+  
+    static int id(const UEdge& edge) {
+      return edge.id;
+    }
+    static UEdge uEdgeFromId(int id) {
+      return UEdge(id);
+    }
+    int maxUEdgeId() const {
+      return edges.size();
+    }
+  
+    static int aNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromANodeId(int id) {
+      return Node(id << 1);
+    }
+    int maxANodeId() const {
+      return aNodes.size();
+    }
+
+    static int bNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromBNodeId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxBNodeId() const {
+      return bNodes.size();
+    }
+
+    Node aNode(const UEdge& edge) const {
+      return Node(edges[edge.id].aNode);
+    }
+    Node bNode(const UEdge& edge) const {
+      return Node(edges[edge.id].bNode);
+    }
+
+    static bool aNode(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool bNode(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    Node addANode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      aNodes.push_back(nodeT);
+      return Node(aNodes.size() * 2 - 2);
+    }
+
+    Node addBNode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      bNodes.push_back(nodeT);
+      return Node(bNodes.size() * 2 - 1);
+    }
+
+    UEdge addEdge(const Node& source, const Node& target) {
+      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
+      UEdgeT edgeT;
+      if ((source.id & 1) == 0) {
+	edgeT.aNode = source.id;
+	edgeT.bNode = target.id;
+      } else {
+	edgeT.aNode = target.id;
+	edgeT.bNode = source.id;
+      }
+      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
+      aNodes[edgeT.aNode >> 1].first = edges.size();
+      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
+      bNodes[edgeT.bNode >> 1].first = edges.size();
+      edges.push_back(edgeT);
+      return UEdge(edges.size() - 1);
+    }
+
+    void clear() {
+      aNodes.clear();
+      bNodes.clear();
+      edges.clear();
+    }
+
+    typedef True NodeNumTag;
+    int nodeNum() const { return aNodes.size() + bNodes.size(); }
+    int aNodeNum() const { return aNodes.size(); }
+    int bNodeNum() const { return bNodes.size(); }
+
+    typedef True EdgeNumTag;
+    int uEdgeNum() const { return edges.size(); }
+
+  };
+
+
+  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief A smart bipartite undirected graph class.
+  ///
+  /// This is a simple and fast bipartite undirected graph implementation.
+  /// It is also quite memory efficient, but at the price
+  /// that <b> it does not support node and edge deletions</b>.
+  /// Except from this it conforms to 
+  /// the \ref concept::BpUGraph "BpUGraph" concept.
+  /// \sa concept::BpUGraph.
+  ///
+  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
+
+  
+  /// @}  
 } //namespace lemon
 
 
diff -r 4cd528a30ec1 -r b6a68c15a6a3 lemon/smart_ugraph.h
--- a/lemon/smart_ugraph.h	Fri Jun 30 12:14:36 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,68 +0,0 @@
-/* -*- 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.
- *
- */
-
-#ifndef LEMON_SMART_UGRAPH_H
-#define LEMON_SMART_UGRAPH_H
-
-///\ingroup graphs
-///\file
-///\brief SmartUGraph class.
-
-#include <vector>
-
-#include <lemon/bits/invalid.h>
-
-#include <lemon/smart_graph.h>
-#include <lemon/bits/base_extender.h>
-#include <lemon/bits/ugraph_extender.h>
-
-#include <lemon/bits/utility.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/graph_extender.h>
-
-namespace lemon {
-
-
-  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
-  ExtendedSmartUGraphBase;
-
-  /// \ingroup graphs
-  ///
-  /// \brief A smart undirected graph class.
-  ///
-  /// This is a simple and fast undirected graph implementation.
-  /// It is also quite memory efficient, but at the price
-  /// that <b> it does support only limited (only stack-like)
-  /// node and edge deletions</b>.
-  /// Except from this it conforms to 
-  /// the \ref concept::UGraph "UGraph" concept.
-  /// \sa concept::UGraph.
-  ///
-  /// \todo Snapshot hasn't been implemented yet.
-  ///
-  class SmartUGraph : public ExtendedSmartUGraphBase {
-  };
-
-
-  
-  /// @}  
-} //namespace lemon
-
-
-#endif //LEMON_SMART_GRAPH_H
diff -r 4cd528a30ec1 -r b6a68c15a6a3 test/bipartite_matching_test.cc
--- a/test/bipartite_matching_test.cc	Fri Jun 30 12:14:36 2006 +0000
+++ b/test/bipartite_matching_test.cc	Fri Jun 30 12:15:45 2006 +0000
@@ -2,7 +2,7 @@
 #include <iostream>
 #include <sstream>
 
-#include <lemon/list_bpugraph.h>
+#include <lemon/list_graph.h>
 
 #include <lemon/bpugraph_adaptor.h>
 #include <lemon/bipartite_matching.h>
diff -r 4cd528a30ec1 -r b6a68c15a6a3 test/max_matching_test.cc
--- a/test/max_matching_test.cc	Fri Jun 30 12:14:36 2006 +0000
+++ b/test/max_matching_test.cc	Fri Jun 30 12:15:45 2006 +0000
@@ -23,7 +23,7 @@
 #include <cstdlib>
 
 #include "test_tools.h"
-#include <lemon/list_ugraph.h>
+#include <lemon/list_graph.h>
 #include <lemon/max_matching.h>
 
 using namespace std;
diff -r 4cd528a30ec1 -r b6a68c15a6a3 test/ugraph_test.cc
--- a/test/ugraph_test.cc	Fri Jun 30 12:14:36 2006 +0000
+++ b/test/ugraph_test.cc	Fri Jun 30 12:15:45 2006 +0000
@@ -18,9 +18,9 @@
 
 #include <lemon/bits/graph_extender.h>
 #include <lemon/concept/ugraph.h>
-#include <lemon/list_ugraph.h>
-#include <lemon/smart_ugraph.h>
-#include <lemon/full_ugraph.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>