diff -r 4e03a355d2ea -r 4c593a4096da lemon/graph_adaptor.h
--- a/lemon/graph_adaptor.h	Mon Oct 03 10:16:45 2005 +0000
+++ b/lemon/graph_adaptor.h	Mon Oct 03 10:17:53 2005 +0000
@@ -65,8 +65,6 @@
   class GraphAdaptorBase {
   public:
     typedef _Graph Graph;
-    /// \todo Is it needed?
-    typedef Graph BaseGraph;
     typedef Graph ParentGraph;
 
   protected:
@@ -93,12 +91,25 @@
     Node source(const Edge& e) const { return graph->source(e); }
     Node target(const Edge& e) const { return graph->target(e); }
 
+    typedef NodeNumTagIndicator<Graph> NodeNumTag;
     int nodeNum() const { return graph->nodeNum(); }
+    
+    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
     int edgeNum() const { return graph->edgeNum(); }
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+		  const Edge& prev = INVALID) {
+      return graph->findEdge(source, target, prev);
+    }
   
-    Node addNode() const { return Node(graph->addNode()); }
+    Node addNode() const { 
+      return Node(graph->addNode()); 
+    }
+
     Edge addEdge(const Node& source, const Node& target) const { 
-      return Edge(graph->addEdge(source, target)); }
+      return Edge(graph->addEdge(source, target)); 
+    }
 
     void erase(const Node& i) const { graph->erase(i); }
     void erase(const Edge& i) const { graph->erase(i); }
@@ -156,11 +167,9 @@
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
 
-    //    using Parent::first;
     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
 
-    //    using Parent::next;
     void nextIn(Edge& i) const { Parent::nextOut(i); }
     void nextOut(Edge& i) const { Parent::nextIn(i); }
 
@@ -304,25 +313,8 @@
     /// Returns true if \c n is hidden.
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
-    /// \warning This is a linear time operation and works only if s
-    /// \c Graph::NodeIt is defined.
-    /// \todo assign tags.
-    int nodeNum() const { 
-      int i=0;
-      Node n;
-      for (first(n); n!=INVALID; next(n)) ++i;
-      return i; 
-    }
-
-    /// \warning This is a linear time operation and works only if 
-    /// \c Graph::EdgeIt is defined.
-    /// \todo assign tags.
-    int edgeNum() const { 
-      int i=0;
-      Edge e;
-      for (first(e); e!=INVALID; next(e)) ++i;
-      return i; 
-    }
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
   };
 
   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
@@ -413,25 +405,8 @@
     /// Returns true if \c n is hidden.
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
-    /// \warning This is a linear time operation and works only if s
-    /// \c Graph::NodeIt is defined.
-    /// \todo assign tags.
-    int nodeNum() const { 
-      int i=0;
-      Node n;
-      for (first(n); n!=INVALID; next(n)) ++i;
-      return i; 
-    }
-
-    /// \warning This is a linear time operation and works only if 
-    /// \c Graph::EdgeIt is defined.
-    /// \todo assign tags.
-    int edgeNum() const { 
-      int i=0;
-      Edge e;
-      for (first(e); e!=INVALID; next(e)) ++i;
-      return i; 
-    }
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
   };
 
   /*! \brief A graph adaptor for hiding nodes and edges from a graph.
@@ -440,7 +415,8 @@
   parts of the lib. Use them at you own risk.
   
   SubGraphAdaptor shows the graph with filtered node-set and 
-  edge-set. 
+  edge-set. If the \c checked parameter is true then it filters the edgeset
+  to do not get invalid edges without source or target.
   Let \f$G=(V, A)\f$ be a directed graph 
   and suppose that the graph instance \c g of type ListGraph implements 
   \f$G\f$. 
@@ -453,10 +429,11 @@
   SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates 
   only on edges leaving and entering a specific node which have true value.
 
-  We have to note that this does not mean that an 
-  induced subgraph is obtained, the node-iterator cares only the filter 
-  on the node-set, and the edge-iterators care only the filter on the 
-  edge-set. 
+  If the \c checked template parameter is false then we have to note that 
+  the node-iterator cares only the filter on the node-set, and the 
+  edge-iterator cares only the filter on the edge-set. This way the edge-map
+  should filter all edges which's source or target is filtered by the 
+  node-filter.
   \code
   typedef ListGraph Graph;
   Graph g;
@@ -519,8 +496,9 @@
   
   An adaptor for hiding nodes from a graph.
   This adaptor specializes SubGraphAdaptor in the way that only the node-set 
-  can be filtered. Note that this does not mean of considering induced 
-  subgraph, the edge-iterators consider the original edge-set.
+  can be filtered. In usual case the checked parameter is true, we get the
+  induced subgraph. But if the checked parameter is false then we can only
+  filter only isolated nodes.
   \author Marton Makai
   */
   template<typename Graph, typename NodeFilterMap, bool checked = true>
@@ -703,9 +681,6 @@
     typedef typename Parent::UndirEdge UndirEdge;
     typedef typename Parent::Edge Edge;
     
-    /// \bug Why cant an edge say that it is forward or not??? 
-    /// By this, a pointer to the graph have to be stored
-    /// The implementation
     template <typename T>
     class EdgeMap {
     protected:
@@ -1122,7 +1097,6 @@
     int edgeNum() const { 
       return 2*this->graph->edgeNum();
     }
-    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
   };
 
 
@@ -1331,6 +1305,371 @@
   };
 
   template <typename _Graph>
+  class SplitGraphAdaptorBase 
+    : public GraphAdaptorBase<_Graph> {
+  public:
+    typedef GraphAdaptorBase<_Graph> Parent;
+
+    class Node;
+    class Edge;
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    
+
+    class Node : public Parent::Node {
+      friend class SplitGraphAdaptorBase;
+      template <typename T> friend class NodeMap;
+      typedef typename Parent::Node NodeParent;
+    private:
+
+      bool entry;
+      Node(typename Parent::Node _node, bool _entry)
+	: Parent::Node(_node), entry(_entry) {}
+      
+    public:
+      Node() {}
+      Node(Invalid) : NodeParent(INVALID), entry(true) {}
+
+      bool operator==(const Node& node) const {
+	return NodeParent::operator==(node) && entry == node.entry;
+      }
+      
+      bool operator!=(const Node& node) const {
+	return !(*this == node);
+      }
+      
+      bool operator<(const Node& node) const {
+	return NodeParent::operator<(node) || 
+	  (NodeParent::operator==(node) && entry < node.entry);
+      }
+    };
+
+    /// \todo May we want VARIANT/union type
+    class Edge : public Parent::Edge {
+      friend class SplitGraphAdaptorBase;
+      template <typename T> friend class EdgeMap;
+    private:
+      typedef typename Parent::Edge EdgeParent;
+      typedef typename Parent::Node NodeParent;
+      NodeParent bind;
+
+      Edge(const EdgeParent& edge, const NodeParent& node)
+	: EdgeParent(edge), bind(node) {}
+    public:
+      Edge() {}
+      Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
+
+      bool operator==(const Edge& edge) const {
+	return EdgeParent::operator==(edge) && bind == edge.bind;
+      }
+      
+      bool operator!=(const Edge& edge) const {
+	return !(*this == edge);
+      }
+      
+      bool operator<(const Edge& edge) const {
+	return EdgeParent::operator<(edge) || 
+	  (EdgeParent::operator==(edge) && bind < edge.bind);
+      }
+    };
+
+    void first(Node& node) const {
+      Parent::first(node);
+      node.entry = true;
+    } 
+
+    void next(Node& node) const {
+      if (node.entry) {
+	node.entry = false;
+      } else {
+	node.entry = true;
+	Parent::next(node);
+      }
+    }
+
+    void first(Edge& edge) const {
+      Parent::first(edge);
+      if ((typename Parent::Edge&)edge == INVALID) {
+	Parent::first(edge.bind);
+      } else {
+	edge.bind = INVALID;
+      }
+    }
+
+    void next(Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+	Parent::next(edge);
+	if ((typename Parent::Edge&)edge == INVALID) {
+	  Parent::first(edge.bind);
+	}
+      } else {
+	Parent::next(edge.bind);
+      }      
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (node.entry) {
+	Parent::firstIn(edge, node);
+	edge.bind = INVALID;
+      } else {
+	(typename Parent::Edge&)edge = INVALID;
+	edge.bind = node;
+      }
+    }
+
+    void nextIn(Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+	Parent::nextIn(edge);
+      } else {
+	edge.bind = INVALID;
+      }      
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (!node.entry) {
+	Parent::firstOut(edge, node);
+	edge.bind = INVALID;
+      } else {
+	(typename Parent::Edge&)edge = INVALID;
+	edge.bind = node;
+      }
+    }
+
+    void nextOut(Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+	Parent::nextOut(edge);
+      } else {
+	edge.bind = INVALID;
+      }
+    }
+
+    Node source(const Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+	return Node(Parent::source(edge), false);
+      } else {
+	return Node(edge.bind, true);
+      }
+    }
+
+    Node target(const Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+	return Node(Parent::target(edge), true);
+      } else {
+	return Node(edge.bind, false);
+      }
+    }
+
+    static bool entryNode(const Node& node) {
+      return node.entry;
+    }
+
+    static bool exitNode(const Node& node) {
+      return !node.entry;
+    }
+
+    static Node getEntry(const typename Parent::Node& node) {
+      return Node(node, true);
+    }
+
+    static Node getExit(const typename Parent::Node& node) {
+      return Node(node, false);
+    }
+
+    static bool originalEdge(const Edge& edge) {
+      return (typename Parent::Edge&)edge != INVALID;
+    }
+
+    static bool bindingEdge(const Edge& edge) {
+      return edge.bind != INVALID;
+    }
+
+    static Node getBindedNode(const Edge& edge) {
+      return edge.bind;
+    }
+
+    int nodeNum() const {
+      return Parent::nodeNum() * 2;
+    }
+
+    typedef CompileTimeAnd<typename Parent::NodeNumTag, 
+    			   typename Parent::EdgeNumTag> EdgeNumTag;
+    
+    int edgeNum() const {
+      return Parent::edgeNum() + Parent::nodeNum();
+    }
+
+    Edge findEdge(const Node& source, const Node& target, 
+		  const Edge& prev = INVALID) const {
+      if (exitNode(source) && entryNode(target)) {
+	return Parent::findEdge(source, target, prev);
+      } else {
+	if (prev == INVALID && entryNode(source) && exitNode(target) && 
+	    (typename Parent::Node&)source == (typename Parent::Node&)target) {
+	  return Edge(INVALID, source);
+	} else {
+	  return INVALID;
+	}
+      }
+    }
+    
+    template <typename T>
+    class NodeMap : public MapBase<Node, T> {
+      typedef typename Parent::template NodeMap<T> NodeImpl;
+    public:
+      NodeMap(const SplitGraphAdaptorBase& _graph) 
+	: entry(_graph), exit(_graph) {}
+      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
+	: entry(_graph, t), exit(_graph, t) {}
+      
+      void set(const Node& key, const T& val) {
+	if (key.entry) { entry.set(key, val); }
+	else {exit.set(key, val); }
+      }
+      
+      typename ReferenceMapTraits<NodeImpl>::Reference 
+      operator[](const Node& key) {
+	if (key.entry) { return entry[key]; }
+	else { return exit[key]; }
+      }
+
+      T operator[](const Node& key) const {
+	if (key.entry) { return entry[key]; }
+	else { return exit[key]; }
+      }
+
+    private:
+      NodeImpl entry, exit;
+    };
+
+    template <typename T>
+    class EdgeMap : public MapBase<Edge, T> {
+      typedef typename Parent::template NodeMap<T> NodeImpl;
+      typedef typename Parent::template EdgeMap<T> EdgeImpl;
+    public:
+      EdgeMap(const SplitGraphAdaptorBase& _graph) 
+	: bind(_graph), orig(_graph) {}
+      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
+	: bind(_graph, t), orig(_graph, t) {}
+      
+      void set(const Edge& key, const T& val) {
+	if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
+	else {bind.set(key.bind, val); }
+      }
+      
+      typename ReferenceMapTraits<EdgeImpl>::Reference
+      operator[](const Edge& key) {
+	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
+	else {return bind[key.bind]; }
+      }
+
+      T operator[](const Edge& key) const {
+	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
+	else {return bind[key.bind]; }
+      }
+
+    private:
+      typename Parent::template NodeMap<T> bind;
+      typename Parent::template EdgeMap<T> orig;
+    };
+
+    template <typename EntryMap, typename ExitMap>
+    class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
+    public:
+      typedef MapBase<Node, typename EntryMap::Value> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+
+      CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 
+	: entryMap(_entryMap), exitMap(_exitMap) {}
+
+      Value& operator[](const Key& key) {
+	if (key.entry) {
+	  return entryMap[key];
+	} else {
+	  return exitMap[key];
+	}
+      }
+
+      Value operator[](const Key& key) const {
+	if (key.entry) {
+	  return entryMap[key];
+	} else {
+	  return exitMap[key];
+	}
+      }
+
+      void set(const Key& key, const Value& value) {
+	if (key.entry) {
+	  entryMap.set(key, value);
+	} else {
+	  exitMap.set(key, value);
+	}
+      }
+      
+    private:
+      
+      EntryMap& entryMap;
+      ExitMap& exitMap;
+      
+    };
+
+    template <typename EdgeMap, typename NodeMap>
+    class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
+    public:
+      typedef MapBase<Edge, typename EdgeMap::Value> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+
+      CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 
+	: edgeMap(_edgeMap), nodeMap(_nodeMap) {}
+
+      void set(const Edge& edge, const Value& val) {
+	if (SplitGraphAdaptorBase::originalEdge(edge)) {
+	  edgeMap.set(edge, val);
+	} else {
+	  nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
+	}
+      }
+
+      Value operator[](const Key& edge) const {
+	if (SplitGraphAdaptorBase::originalEdge(edge)) {
+	  return edgeMap[edge];
+	} else {
+	  return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
+	}
+      }      
+
+      Value& operator[](const Key& edge) {
+	if (SplitGraphAdaptorBase::originalEdge(edge)) {
+	  return edgeMap[edge];
+	} else {
+	  return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
+	}
+      }      
+      
+    private:
+      EdgeMap& edgeMap;
+      NodeMap& nodeMap;
+    };
+
+  };
+
+  template <typename _Graph>
+  class SplitGraphAdaptor 
+    : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
+  public:
+    typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+
+    SplitGraphAdaptor(_Graph& graph) {
+      Parent::setGraph(graph);
+    }
+
+
+  };
+
+  template <typename _Graph>
   class NewEdgeSetAdaptorBase {
   public: