# HG changeset patch
# User klao
# Date 1101659410 0
# Node ID 567f392d1d2e0f32c6825272c2ced1843183971e
# Parent  fd1d073b6557c77d1d7a1b928039ab51849cf52e
UndirGraph implementation nearly complete

diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/alteration_observer_registry.h
--- a/src/lemon/alteration_observer_registry.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/alteration_observer_registry.h	Sun Nov 28 16:30:10 2004 +0000
@@ -364,7 +364,10 @@
 
     mutable UndirEdgeObserverRegistry undir_edge_observers;
 
-    UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge = INVALID) const {
+  public:
+
+    using Parent::getObserverRegistry;
+    UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge) const {
       return undir_edge_observers;
     }
 
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/clearable_graph_extender.h
--- a/src/lemon/clearable_graph_extender.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/clearable_graph_extender.h	Sun Nov 28 16:30:10 2004 +0000
@@ -25,6 +25,25 @@
 
   };
 
+  template <typename _Base> 
+  class ClearableUndirGraphExtender : public _Base {
+  public:
+
+    typedef ClearableUndirGraphExtender Graph;
+    typedef _Base Parent;
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UndirEdge UndirEdge;
+    typedef typename Parent::Edge Edge;
+
+    void clear() {
+      Parent::getObserverRegistry(Node()).clear();
+      Parent::getObserverRegistry(UndirEdge()).clear();
+      Parent::getObserverRegistry(Edge()).clear();
+      Parent::clear();
+    }
+
+  };
+
 }
 
 #endif
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/concept/graph_component.h
--- a/src/lemon/concept/graph_component.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/concept/graph_component.h	Sun Nov 28 16:30:10 2004 +0000
@@ -406,7 +406,7 @@
     /// This class provides beside the core graph features
     /// core clear functions for the graph structure.
     /// The most of the base graphs should be conform to this concept.
-    class BaseClearableGraphComponent : virtual public BaseGraphComponent {
+    class ClearableGraphComponent : virtual public BaseGraphComponent {
     public:
 
       /// Erase all the Nodes and Edges from the graph.
@@ -418,11 +418,11 @@
       template <typename _Graph>
       struct Constraints {
 	void constraints() {
-	  checkConcept< BaseGraphComponent, _Graph>();
+	  checkConcept<BaseGraphComponent, _Graph>();
 	  graph.clear();
 	}
 
-	_Graph& graph;
+	_Graph graph;
       };
     };
 
@@ -804,27 +804,6 @@
       };
     };
 
-    class ClearableGraphComponent : virtual public BaseGraphComponent {
-    public:
-
-      typedef ClearableGraphComponent Graph;
-
-      typedef BaseGraphComponent::Node Node;
-      typedef BaseGraphComponent::Edge Edge;
-
-      void clear() {}    
-
-
-      template <typename _Graph>
-      struct ClearableGraphComponentConcept {
-	void constraints() {
-	  checkConcept< BaseGraphComponent, _Graph >();
-	  graph.clear();
-	}
-	_Graph& graph;
-      };
-    };
-
   }
 
 }
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/concept/undir_graph.h
--- a/src/lemon/concept/undir_graph.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/concept/undir_graph.h	Sun Nov 28 16:30:10 2004 +0000
@@ -31,50 +31,163 @@
   namespace concept {
 
     /// \todo to be done
-    class BaseIterableUndirGraph;
 
-    template <typename Graph>
     struct BaseIterableUndirGraphConcept {
-      typedef typename Graph::UndirEdge UndirEdge;
-      typedef typename Graph::Edge Edge;
-      typedef typename Graph::Node Node;
 
-      void constraints() {
-	checkConcept<BaseIterableGraphComponent, Graph>();
-	checkConcept<GraphItem<'u'>, UndirEdge >();
+      template <typename Graph>
+      struct Constraints {
 
-	/// \bug this should be base_and_derived:
-	UndirEdge ue = e;
-	ue = e;
+	typedef typename Graph::UndirEdge UndirEdge;
+	typedef typename Graph::Edge Edge;
+	typedef typename Graph::Node Node;
 
-	Node n;
-	n = graph.target(ue);
-	n = graph.source(ue);
+	void constraints() {
+	  checkConcept<BaseIterableGraphComponent, Graph>();
+	  checkConcept<GraphItem<'u'>, UndirEdge >();
 
-	graph.first(ue);
-	graph.next(ue);
-      }
-      const Graph &graph;
-      Edge e;
+	  /// \bug this should be base_and_derived:
+	  UndirEdge ue = e;
+	  ue = e;
+
+	  Node n;
+	  n = graph.target(ue);
+	  n = graph.source(ue);
+
+	  graph.first(ue);
+	  graph.next(ue);
+	}
+	const Graph &graph;
+	Edge e;
+      };
+
     };
 
-    template <typename Graph>
+
     struct IterableUndirGraphConcept {
-      void constraints() {
-	/// \todo we don't need the iterable component should base iterable	
-	//	checkConcept< BaseIterableUndirGraph, Graph > ();
-	checkConcept< IterableGraphComponent, Graph > ();
 
-	typedef typename Graph::UndirEdge UndirEdge;
-	typedef typename Graph::UndirEdgeIt UndirEdgeIt;
-	typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
+      template <typename Graph>
+      struct Constraints {
+	void constraints() {
+	  /// \todo we don't need the iterable component to be base iterable
+	  /// Don't we really???
+	  //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
 
-	checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >();
+	  checkConcept<IterableGraphComponent, Graph> ();
 
-	checkConcept<
-	  GraphIncIterator<Graph, UndirEdge>,
-	  UndirIncEdgeIt >();
-      }
+	  typedef typename Graph::UndirEdge UndirEdge;
+	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;
+	  typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
+
+	  checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
+	  checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
+	}
+      };
+
+    };
+
+    struct MappableUndirGraphConcept {
+
+      template <typename Graph>
+      struct Constraints {
+
+	struct Dummy {
+	  int value;
+	  Dummy() : value(0) {}
+	  Dummy(int _v) : value(_v) {}
+	};
+
+	void constraints() {
+	  checkConcept<MappableGraphComponent, Graph>();
+
+	  typedef typename Graph::template UndirEdgeMap<int> IntMap;
+	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
+	    IntMap >();
+
+	  typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
+	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
+	    BoolMap >();
+
+	  typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
+	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
+	    DummyMap >();
+	}
+      };
+
+    };
+
+    struct ExtendableUndirGraphConcept {
+
+      template <typename Graph>
+      struct Constraints {
+	void constraints() {
+	  node_a = graph.addNode();
+	  uedge = graph.addEdge(node_a, node_b);
+	}
+	typename Graph::Node node_a, node_b;
+	typename Graph::UndirEdge uedge;
+	Graph graph;
+      };
+
+    };
+
+    struct ErasableUndirGraphConcept {
+
+      template <typename Graph>
+      struct Constraints {
+	void constraints() {
+	  graph.erase(n);
+	  graph.erase(e);
+	}
+	Graph graph;
+	typename Graph::Node n;
+	typename Graph::UndirEdge e;
+      };
+
+    };
+
+    class UndirGraph {
+    public:
+
+      template <typename Graph>
+      struct Constraints {
+	void constraints() {
+	  checkConcept<BaseIterableUndirGraphConcept, Graph>();
+	  checkConcept<IterableUndirGraphConcept, Graph>();
+	  checkConcept<MappableUndirGraphConcept, Graph>();
+	}
+      };
+
+    };
+
+    class ExtendableUndirGraph : public UndirGraph {
+    public:
+
+      template <typename Graph>
+      struct Constraints {
+	void constraints() {
+	  checkConcept<BaseIterableUndirGraphConcept, Graph>();
+	  checkConcept<IterableUndirGraphConcept, Graph>();
+	  checkConcept<MappableUndirGraphConcept, Graph>();
+
+	  checkConcept<UndirGraph, Graph>();
+	  checkConcept<ExtendableUndirGraphConcept, Graph>();
+	  checkConcept<ClearableGraphComponent, Graph>();
+	}
+      };
+
+    };
+
+    class ErasableUndirGraph : public ExtendableUndirGraph {
+    public:
+
+      template <typename Graph>
+      struct Constraints {
+	void constraints() {
+	  checkConcept<ExtendableUndirGraph, Graph>();
+	  checkConcept<ErasableUndirGraphConcept, Graph>();
+	}
+      };
+
     };
 
   }
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/concept_check.h
--- a/src/lemon/concept_check.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/concept_check.h	Sun Nov 28 16:30:10 2004 +0000
@@ -41,7 +41,11 @@
 
   template <typename Concept, typename Type>
   inline void checkConcept() {
-    function_requires<typename Concept::template Constraints<Type> >();
+#if !defined(NDEBUG)
+    typedef typename Concept::template Constraints<Type> ConceptCheck;
+    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
+    ignore_unused_variable_warning(x);
+#endif
   }
 
 #define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/default_map.h
--- a/src/lemon/default_map.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/default_map.h	Sun Nov 28 16:30:10 2004 +0000
@@ -172,45 +172,55 @@
     template <typename _Value>
     class NodeMap : public DefaultMap<Graph, Node, NodeIt, _Value> {
     public:
-      typedef DefaultMappableGraphExtender<_Base> Graph;
-
-      typedef typename Graph::Node Node;
-      typedef typename Graph::NodeIt NodeIt;
-
+      typedef DefaultMappableGraphExtender Graph;
       typedef DefaultMap<Graph, Node, NodeIt, _Value> Parent;
 
-      //typedef typename Parent::Graph Graph;
-      typedef typename Parent::Value Value;
-
       NodeMap(const Graph& _g) 
 	: Parent(_g) {}
-      NodeMap(const Graph& _g, const Value& _v) 
+      NodeMap(const Graph& _g, const _Value& _v) 
 	: Parent(_g, _v) {}
-
     };
 
     template <typename _Value>
     class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, _Value> {
     public:
-      typedef DefaultMappableGraphExtender<_Base> Graph;
-
-      typedef typename Graph::Edge Edge;
-      typedef typename Graph::EdgeIt EdgeIt;
-
+      typedef DefaultMappableGraphExtender Graph;
       typedef DefaultMap<Graph, Edge, EdgeIt, _Value> Parent;
 
-      //typedef typename Parent::Graph Graph;
-      typedef typename Parent::Value Value;
-
       EdgeMap(const Graph& _g) 
 	: Parent(_g) {}
-      EdgeMap(const Graph& _g, const Value& _v) 
+      EdgeMap(const Graph& _g, const _Value& _v) 
 	: Parent(_g, _v) {}
-
     };
     
   };
 
+  template <typename _Base> 
+  class MappableUndirGraphExtender : 
+    public DefaultMappableGraphExtender<_Base> {
+  public:
+
+    typedef MappableUndirGraphExtender Graph;
+    typedef DefaultMappableGraphExtender<_Base> Parent;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+    typedef typename Parent::UndirEdgeIt UndirEdgeIt;
+
+    template <typename _Value>
+    class UndirEdgeMap :
+      public DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> {
+    public:
+      typedef MappableUndirGraphExtender Graph;
+      typedef DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> Parent;
+
+      UndirEdgeMap(const Graph& _g) 
+	: Parent(_g) {}
+      UndirEdgeMap(const Graph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+    };
+
+
+  };
 
 }
 
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/erasable_graph_extender.h
--- a/src/lemon/erasable_graph_extender.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/erasable_graph_extender.h	Sun Nov 28 16:30:10 2004 +0000
@@ -43,6 +43,38 @@
 
   };
 
+  template <typename _Base> 
+  class ErasableUndirGraphExtender : public _Base {
+  public:
+
+    typedef ErasableUndirGraphExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::UndirEdge UndirEdge;
+    typedef typename Parent::Edge Edge;
+
+    void erase(const Node& node) {
+      Edge edge;
+      Parent::firstOut(edge, node);
+      while (edge != INVALID ) {
+	erase(edge);
+	Parent::firstOut(edge, node);
+      } 
+
+      Parent::getObserverRegistry(Node()).erase(node);
+      Parent::erase(node);
+    }
+    
+    void erase(const UndirEdge& uedge) {
+      Parent::getObserverRegistry(Edge()).erase(Edge(uedge,true));
+      Parent::getObserverRegistry(Edge()).erase(Edge(uedge,false));
+      Parent::getObserverRegistry(UndirEdge()).erase(uedge);
+      Parent::erase(uedge);
+    }
+
+  };
+
 }
 
 #endif
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/extendable_graph_extender.h
--- a/src/lemon/extendable_graph_extender.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/extendable_graph_extender.h	Sun Nov 28 16:30:10 2004 +0000
@@ -29,6 +29,37 @@
 
   };
 
+  template <typename _Base> 
+  class ExtendableUndirGraphExtender : public _Base {
+  public:
+
+    typedef ExtendableUndirGraphExtender Graph;
+    typedef _Base Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    Node addNode() {
+      Node node = Parent::addNode();
+      Parent::getObserverRegistry(Node()).add(node);
+      return node;
+    }
+
+    UndirEdge addEdge(const Node& from, const Node& to) {
+      UndirEdge uedge = Parent::addEdge(from, to);
+      Parent::getObserverRegistry(UndirEdge()).add(uedge);
+
+      Edge edge_forward(uedge, true);
+      Edge edge_backward(uedge, false);
+      Parent::getObserverRegistry(Edge()).add(edge_forward);
+      Parent::getObserverRegistry(Edge()).add(edge_backward);
+
+      return uedge;
+    }
+
+  };
+
 }
 
 #endif
diff -r fd1d073b6557 -r 567f392d1d2e src/lemon/iterable_graph_extender.h
--- a/src/lemon/iterable_graph_extender.h	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/lemon/iterable_graph_extender.h	Sun Nov 28 16:30:10 2004 +0000
@@ -176,8 +176,11 @@
       }
 
       // FIXME: Do we need this type of constructor here?
-      // UndirIncEdgeIt(const Graph& _graph, const UndirEdge& e) : 
-      //   UndirEdge(e), graph(&_graph) { }
+      // UndirIncEdgeIt(const Graph& _graph, const Edge& e) : 
+      //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
+      // or
+      // UndirIncEdgeIt(const Graph& _graph, const Node& n,
+      //    Const UndirEdge &e) ... ?
 
       UndirIncEdgeIt& operator++() {
 	graph->_dirNextOut(*this);
diff -r fd1d073b6557 -r 567f392d1d2e src/test/graph_test.cc
--- a/src/test/graph_test.cc	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/test/graph_test.cc	Sun Nov 28 16:30:10 2004 +0000
@@ -29,7 +29,6 @@
 
     checkConcept<BaseExtendableGraphComponent, BaseExtendableGraphComponent >();
     checkConcept<BaseErasableGraphComponent, BaseErasableGraphComponent >();
-    checkConcept<BaseClearableGraphComponent, BaseClearableGraphComponent >();
 
     checkConcept<IterableGraphComponent, IterableGraphComponent >();
 
diff -r fd1d073b6557 -r 567f392d1d2e src/test/undir_graph_test.cc
--- a/src/test/undir_graph_test.cc	Thu Nov 25 14:48:24 2004 +0000
+++ b/src/test/undir_graph_test.cc	Sun Nov 28 16:30:10 2004 +0000
@@ -16,12 +16,22 @@
 int main() {
   typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
 
-  function_requires< BaseIterableUndirGraphConcept<UndirListGraphBase> >();
-
   typedef IterableUndirGraphExtender<
     AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;
 
-  function_requires< IterableUndirGraphConcept<IterableUndirListGraph> >();
+  typedef MappableUndirGraphExtender<IterableUndirListGraph>
+    MappableUndirListGraph;
+
+  typedef ErasableUndirGraphExtender<
+    ClearableUndirGraphExtender<
+    ExtendableUndirGraphExtender<MappableUndirListGraph> > > Graph;
+
+  checkConcept<BaseIterableUndirGraphConcept, Graph>();
+  checkConcept<IterableUndirGraphConcept, Graph>();
+  checkConcept<MappableUndirGraphConcept, Graph>();
+
+  checkConcept<UndirGraph, Graph>();
+  checkConcept<ErasableUndirGraph, Graph>();
 
   return 0;
 }