Changeset 1472:c3bda060cfa3 in lemon-0.x

Timestamp:

06/10/05 14:22:22 (20 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

New EdgeSet? Adaptor

File:

• lemon/graph_adaptor.h (modified) (2 diffs)

lemon/graph_adaptor.h

@@ -28 +28 @@
 #include <lemon/invalid.h>
 #include <lemon/maps.h>
+#include <lemon/bits/erasable_graph_extender.h>
+#include <lemon/bits/clearable_graph_extender.h>
+#include <lemon/bits/extendable_graph_extender.h>
 #include <lemon/bits/iterable_graph_extender.h>
+#include <lemon/bits/alteration_notifier.h>
+#include <lemon/bits/default_map.h>
 #include <lemon/bits/undir_graph_extender.h>
 #include <iostream>
@@ -1211 +1216 @@
   };
 
+  /// \e
+  template <typename _Graph>
+  class NewEdgeSetAdaptorBase {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+
+  protected:
+
+    struct NodeT {
+      int first_out, first_in;
+      NodeT() : first_out(-1), first_in(-1) {}
+    };
+    
+    class NodesImpl : protected Graph::template NodeMap<NodeT> {
+
+      typedef typename Graph::template NodeMap<NodeT> Parent;
+      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
+
+      Adaptor& adaptor;
+
+    public:
+
+      NodesImpl(Adaptor& _adaptor, const Graph& _graph) 
+        : Parent(_graph), adaptor(_adaptor) {}
+
+      virtual ~NodesImpl() {}
+
+      virtual void build() {
+        Parent::build();
+      }
+
+      virtual void clear() {
+        adaptor._clear();
+        Parent::clear();
+      }
+      
+      virtual void add(const Node& node) {
+        Parent::add(node);
+        adaptor._add(node);
+      }
+      
+      virtual void erase(const Node& node) {
+        adaptor._erase(node);
+        Parent::erase(node);
+      }
+
+      NodeT& operator[](const Node& node) {
+        return Parent::operator[](node);
+      }
+
+      const NodeT& operator[](const Node& node) const {
+        return Parent::operator[](node);
+      }
+      
+    };
+
+    NodesImpl* nodes;
+
+    struct EdgeT {
+      Node source, target;
+      int next_out, next_in;
+      int prev_out, prev_in;
+      EdgeT() : prev_out(-1), prev_in(-1) {}
+    };
+
+    std::vector<EdgeT> edges;
+
+    int first_edge;
+    int first_free_edge;
+
+    virtual void _clear() = 0;
+    virtual void _add(const Node& node) = 0;
+    virtual void _erase(const Node& node) = 0;
+    
+    const Graph* graph;
+
+    void initalize(const Graph& _graph, NodesImpl& _nodes) {
+      graph = &_graph;
+      nodes = &_nodes;
+    }
+    
+  public:
+
+    class Edge {
+      friend class NewEdgeSetAdaptorBase<Graph>;
+    protected:
+      Edge(int _id) : id(_id) {}
+      int 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; }
+    };
+
+    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 
+    virtual ~NewEdgeSetAdaptorBase() {}
+
+    Edge addEdge(const Node& source, const Node& target) {
+      int n;
+      if (first_free_edge == -1) {
+        n = edges.size();
+        edges.push_back(EdgeT());
+      } else {
+        n = first_free_edge;
+        first_free_edge = edges[first_free_edge].next_in;
+      }
+      edges[n].next_in = (*nodes)[target].first_in;
+      (*nodes)[target].first_in = n;
+      edges[n].next_out = (*nodes)[source].first_out;
+      (*nodes)[source].first_out = n;
+      edges[n].source = source;
+      edges[n].target = target;
+      return Edge(n);
+    }
+
+    void erase(const Edge& edge) {
+      int n = edge.id;
+      if (edges[n].prev_in != -1) {
+        edges[edges[n].prev_in].next_in = edges[n].next_in;
+      } else {
+        (*nodes)[edges[n].target].first_in = edges[n].next_in;
+      }
+      if (edges[n].next_in != -1) {
+        edges[edges[n].next_in].prev_in = edges[n].prev_in;
+      }
+
+      if (edges[n].prev_out != -1) {
+        edges[edges[n].prev_out].next_out = edges[n].next_out;
+      } else {
+        (*nodes)[edges[n].source].first_out = edges[n].next_out;
+      }
+      if (edges[n].next_out != -1) {
+        edges[edges[n].next_out].prev_out = edges[n].prev_out;
+      }
+           
+    }
+
+    void first(Node& node) const {
+      graph->first(node);
+    }
+
+    void next(Node& node) const {
+      graph->next(node);
+    }
+
+    void first(Edge& edge) const {
+      Node node;
+      for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
+           next(node));
+      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
+    }
+
+    void next(Edge& edge) const {
+      if (edges[edge.id].next_in != -1) {
+        edge.id = edges[edge.id].next_in;
+      } else {
+        Node node = edges[edge.id].target;
+        for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
+             next(node));
+        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
+      }      
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge.id = (*nodes)[node].first_out;    
+    }
+    
+    void nextOut(Edge& edge) const {
+      edge.id = edges[edge.id].next_out;        
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.id = (*nodes)[node].first_in;          
+    }
+
+    void nextIn(Edge& edge) const {
+      edge.id = edges[edge.id].next_in;    
+    }
+
+    int id(const Node& node) const { return graph->id(node); }
+    int id(const Edge& edge) const { return edge.id; }
+
+    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
+    Edge fromId(int id, Edge) const { return Edge(id); }
+
+    int maxId(Node) const { return graph->maxId(Node()); };
+    int maxId(Edge) const { return edges.size() - 1; }
+
+    Node source(const Edge& edge) const { return edges[edge.id].source;}
+    Node target(const Edge& edge) const { return edges[edge.id].target;}
+
+  };
+
+  template <typename _Graph>
+  class NewEdgeSetAdaptor :
+    public ErasableGraphExtender<
+    ClearableGraphExtender<
+    ExtendableGraphExtender<
+    DefaultMappableGraphExtender<
+    IterableGraphExtender<
+    AlterableGraphExtender<
+    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
+
+  public:
+
+    typedef ErasableGraphExtender<
+      ClearableGraphExtender<
+      ExtendableGraphExtender<
+      DefaultMappableGraphExtender<
+      IterableGraphExtender<
+      AlterableGraphExtender<
+      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
+    
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+  private:
+
+    virtual void _clear() {
+      Parent::edges.clear();
+      Parent::first_edge = -1;
+      Parent::first_free_edge = -1;
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(Node()).clear();
+    }
+
+    virtual void _add(const Node& node) {
+      Parent::getNotifier(Node()).add(node);
+    }
+
+    virtual void _erase(const Node& node) {
+      Edge edge;
+      Parent::firstOut(edge, node);
+      while (edge != INVALID) {
+        Parent::erase(edge);
+        Parent::firstOut(edge, node);
+      }
+
+      Parent::firstIn(edge, node);
+      while (edge != INVALID) {
+        Parent::erase(edge);
+        Parent::firstIn(edge, node);
+      }
+      
+      Parent::getNotifier(Node()).erase(node);
+    }
+
+
+    typedef typename Parent::NodesImpl NodesImpl;
+
+    NodesImpl nodes;
+    
+  public:
+
+    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
+      Parent::initalize(_graph, nodes);
+    }
+
+    void clear() {
+      Parent::edges.clear();
+      Parent::first_edge = -1;
+      Parent::first_free_edge = -1;
+
+      Parent::getNotifier(Edge()).clear();      
+    }
+    
+  };
+
   ///@}