Changeset 962:1a770e9f80b2 in lemon-0.x for src/lemon

Timestamp:

11/05/04 01:31:49 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

Undirect graph implementation.
Not yet done, untested.

Location:

src/lemon

Files:

• Makefile.am (modified) (1 diff)
• alteration_observer_registry.h (modified) (4 diffs)
• concept/graph_component.h (modified) (3 diffs)
• concept/undir_graph.h (added)
• iterable_graph_extender.h (modified) (6 diffs)
• undir_graph_extender.h (added)

src/lemon/Makefile.am

@@ -34 +34 @@
         extendable_graph_extender.h                                     \
         clearable_graph_extender.h                                      \
-        erasable_graph_extender.h
+        erasable_graph_extender.h                                       \
+        undir_graph_extender.h
 
 noinst_HEADERS =                                                        \
         concept/graph.h                                                 \
         concept/graph_component.h                                       \
+        concept/undir_graph.h                                           \
         concept/sym_graph.h                                             \
         concept/maps.h                                                  \

src/lemon/alteration_observer_registry.h

@@ -279 +279 @@
 
 
-  /// Class to extend a graph functionality with the possibility of alteration observing.
-
-  /// AlterableGraphExtender extends the _Base graphs functionality with the possibility of 
-  /// alteration observing. It defines two observer registrys for the nodes and mapes.
+  /// \brief Class to extend a graph with the functionality of alteration
+  /// observing.
+  ///
+  /// AlterableGraphExtender extends the _Base graphs functionality with
+  /// the possibility of alteration observing. It defines two observer
+  /// registrys for the nodes and mapes.
+  /// 
+  /// \todo Document what "alteration observing" is. And probably find a
+  /// better (shorter) name.
   ///
   /// \param _Base is the base class to extend.
@@ -288 +293 @@
   /// \pre _Base is conform to the BaseGraphComponent concept.
   ///
-  /// \post AlterableGraphExtender<_Base> is conform to the AlterableGraphComponent concept.
+  /// \post AlterableGraphExtender<_Base> is conform to the
+  /// AlterableGraphComponent concept.
   ///
   /// \author Balazs Dezso
@@ -302 +308 @@
     typedef typename Parent::Edge Edge;
 
+    /// The edge observer registry.
+    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
     /// The node observer registry.
-    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
-    /// The edge observer registry.
     typedef AlterationObserverRegistry<Node> NodeObserverRegistry;
 
@@ -331 +337 @@
   };
 
+  /// \brief Class to extend an undirected graph with the functionality of
+  /// alteration observing.
+  ///
+  /// \todo Document.
+  ///
+  /// \sa AlterableGraphExtender
+  ///
+  /// \bug This should be done some other way. Possibilities: template
+  /// specialization (not very easy, if at all possible); some kind of
+  /// enable_if boost technique?
+
+  template <typename _Base> 
+  class AlterableUndirGraphExtender
+    : public AlterableGraphExtender<_Base> {
+  public:
+
+    typedef AlterableUndirGraphExtender Graph;
+    typedef AlterableGraphExtender<_Base> Parent;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    /// The edge observer registry.
+    typedef AlterationObserverRegistry<UndirEdge> UndirEdgeObserverRegistry;
+
+  protected:
+
+    mutable UndirEdgeObserverRegistry undir_edge_observers;
+
+    UndirEdgeObserverRegistry& getUndirEdgeObserverRegistry() const {
+      return undir_edge_observers;
+    }
+
+    ~AlterableUndirGraphExtender() {
+      undir_edge_observers.clear();
+    }
+  };
   
 /// @}

src/lemon/concept/graph_component.h

@@ -264 +264 @@
         function_requires< GraphItemConcept<Edge> >();
         {
-          const Graph& const_graph = graph;
           Node n;
           Edge e;
-          n = const_graph.tail(e);
-          n = const_graph.head(e);
+          n = graph.tail(e);
+          n = graph.head(e);
         }      
       }
       
-      Graph& graph;
+      const Graph& graph;
     };
 
@@ -646 +645 @@
     template <typename Graph> 
     struct IterableGraphComponentConcept {
-
       void constraints() {
         function_requires< BaseIterableGraphComponentConcept<Graph> >();
@@ -662 +660 @@
         function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
       }
-      Graph& graph;
     };
 

src/lemon/iterable_graph_extender.h

@@ -9 +9 @@
   template <typename _Base>
   class IterableGraphExtender : public _Base {
+  public:
 
     typedef _Base Parent;
     typedef IterableGraphExtender<_Base> Graph;
-
-  public:
 
     typedef typename Parent::Node Node;
@@ -27 +26 @@
       NodeIt(Invalid i) : Node(i) { }
 
-      explicit NodeIt(const Graph& _graph) : Node(), graph(&_graph) {
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
         _graph.first(*static_cast<Node*>(this));
       }
@@ -50 +49 @@
       EdgeIt(Invalid i) : Edge(i) { }
 
-      explicit EdgeIt(const Graph& _graph) : Edge(), graph(&_graph) {
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
         _graph.first(*static_cast<Edge*>(this));
       }
@@ -74 +73 @@
 
       OutEdgeIt(const Graph& _graph, const Node& node) 
-        : Edge(), graph(&_graph) {
+        : graph(&_graph) {
         _graph.firstOut(*this, node);
       }
@@ -98 +97 @@
 
       InEdgeIt(const Graph& _graph, const Node& node) 
-        : Edge(), graph(&_graph) {
+        : graph(&_graph) {
         _graph.firstIn(*this, node);
       }
@@ -127 +126 @@
   };
   
+  template <typename _Base>
+  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
+  public:
+
+    typedef IterableGraphExtender<_Base> Parent;
+    typedef IterableUndirGraphExtender<_Base> Graph;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    class UndirEdgeIt : public UndirEdge { 
+      const Graph* graph;
+    public:
+
+      UndirEdgeIt() { }
+
+      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
+
+      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(*static_cast<UndirEdge*>(this));
+      }
+
+      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : 
+        UndirEdge(e), graph(&_graph) { }
+
+      UndirEdgeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+
+  };
 }