Changeset 1022:567f392d1d2e in lemon-0.x for src/lemon

Timestamp:

11/28/04 17:30:10 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1412

Message:

UndirGraph? implementation nearly complete

Location:

src/lemon

Files:

• alteration_observer_registry.h (modified) (1 diff)
• clearable_graph_extender.h (modified) (1 diff)
• concept/graph_component.h (modified) (3 diffs)
• concept/undir_graph.h (modified) (1 diff)
• concept_check.h (modified) (1 diff)
• default_map.h (modified) (2 diffs)
• erasable_graph_extender.h (modified) (1 diff)
• extendable_graph_extender.h (modified) (1 diff)
• iterable_graph_extender.h (modified) (1 diff)

src/lemon/alteration_observer_registry.h

@@ -365 +365 @@
     mutable UndirEdgeObserverRegistry undir_edge_observers;
 
-    UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge = INVALID) const {
+  public:
+
+    using Parent::getObserverRegistry;
+    UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge) const {
       return undir_edge_observers;
     }

src/lemon/clearable_graph_extender.h

@@ -26 +26 @@
   };
 
+  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();
+    }
+
+  };
+
 }
 

src/lemon/concept/graph_component.h

@@ -407 +407 @@
     /// 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:
 
@@ -419 +419 @@
       struct Constraints {
         void constraints() {
-          checkConcept< BaseGraphComponent, _Graph>();
+          checkConcept<BaseGraphComponent, _Graph>();
           graph.clear();
         }
 
-        _Graph& graph;
+        _Graph graph;
       };
     };
@@ -805 +805 @@
     };
 
-    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;
-      };
-    };
-
   }
 

src/lemon/concept/undir_graph.h

@@ -32 +32 @@
 
     /// \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>();
+        }
+      };
+
     };
 

src/lemon/concept_check.h

@@ -42 +42 @@
   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
   }
 

src/lemon/default_map.h

@@ -173 +173 @@
     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) {}
-
     };
 
@@ -193 +185 @@
     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) {}
+    };
+
+
+  };
 
 }

src/lemon/erasable_graph_extender.h

@@ -44 +44 @@
   };
 
+  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);
+    }
+
+  };
+
 }
 

src/lemon/extendable_graph_extender.h

@@ -30 +30 @@
   };
 
+  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;
+    }
+
+  };
+
 }
 

src/lemon/iterable_graph_extender.h

@@ -177 +177 @@
 
       // 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++() {