Changeset 397:b4d7b19b6740 in lemon-0.x for src/work/alpar/list_graph.h

Timestamp:

04/25/04 18:53:38 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

I hope it works. The 'erase' functions hasn't been tested yet.

File:

• src/work/alpar/list_graph.h (modified) (21 diffs)

src/work/alpar/list_graph.h

@@ -5 +5 @@
 
 ///\file
-///\brief SmartGraph and SymSmartGraph classes.
+///\brief ListGraph and SymListGraph classes.
 
 #include <vector>
@@ -14 +14 @@
 namespace hugo {
 
-  class SymSmartGraph;
+  class SymListGraph;
 
   ///A smart graph class.
 
-  ///This is a simple and fast graph implementation.
-  ///It is also quite memory efficient, but at the price
-  ///that <b> it does not support node and edge deletion</b>.
+  ///This is a simple and fast erasable graph implementation.
+  ///
   ///It conforms to the graph interface documented under
   ///the description of \ref GraphSkeleton.
   ///\sa \ref GraphSkeleton.
-  class SmartGraph {
-
+  class ListGraph {
+
+    //Nodes are double linked.
+    //The free nodes are only single linked using the "next" field.
     struct NodeT 
     {
-      int first_in,first_out;      
-      NodeT() : first_in(-1), first_out(-1) {}
-    };
+      int first_in,first_out;
+      int prev, next;
+      //      NodeT() {}
+    };
+    //Edges are double linked.
+    //The free edges are only single linked using the "next_in" field.
     struct EdgeT 
     {
-      int head, tail, next_in, next_out;      
+      int head, tail;
+      int prev_in, prev_out;
+      int next_in, next_out;
       //FIXME: is this necessary?
-      EdgeT() : next_in(-1), next_out(-1) {}  
+      //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}  
     };
 
     std::vector<NodeT> nodes;
-
+    //The first node
+    int first_node;
+    //The first free node
+    int first_free_node;
     std::vector<EdgeT> edges;
-    
+    //The first free edge
+    int first_free_edge;
+    
+  protected:
+    
+    template <typename Key> class DynMapBase
+    {
     protected:
-    
-    template <typename Key> class DynMapBase
-    {
-    protected:
-      const SmartGraph* G; 
+      const ListGraph* G; 
     public:
       virtual void add(const Key k) = NULL;
       virtual void erase(const Key k) = NULL;
-      DynMapBase(const SmartGraph &_G) : G(&_G) {}
+      DynMapBase(const ListGraph &_G) : G(&_G) {}
       virtual ~DynMapBase() {}
-      friend class SmartGraph;
+      friend class ListGraph;
     };
     
@@ -59 +70 @@
     template <typename T> class EdgeMap;
     template <typename T> class EdgeMap;
-
+    
     class Node;
     class Edge;
@@ -85 +96 @@
   public:
 
-    SmartGraph() : nodes(), edges() { }
-    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
-    
-    ~SmartGraph()
+    ListGraph() : nodes(), first_node(-1),
+                  first_free_node(-1), edges(), first_free_edge(-1) {}
+    ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
+                                     first_free_node(_g.first_free_node),
+                                     edges(_g.edges),
+                                     first_free_edge(_g.first_free_edge) {}
+    
+    ~ListGraph()
     {
       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
@@ -140 +155 @@
 
     NodeIt& next(NodeIt& it) const { 
-      it.n=(it.n+2)%(nodes.size()+1)-1; 
+      it.n=nodes[it.n].next; 
       return it; 
     }
@@ -147 +162 @@
     InEdgeIt& next(InEdgeIt& it) const
     { it.n=edges[it.n].next_in; return it; }
-    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
+    EdgeIt& next(EdgeIt& it) const {
+      if(edges[it.n].next_in!=-1) { 
+        it.n=edges[it.n].next_in;
+      }
+      else {
+        int n;
+        for(n=nodes[edges[it.n].head].next;
+            n!=-1 && nodes[n].first_in == -1;
+            n = nodes[n].next) ;
+        it.n = (n==-1)?-1:nodes[n].first_in;
+      }
+      return it;
+    }
 
     int id(Node v) const { return v.n; }
     int id(Edge e) const { return e.n; }
 
+    /// Adds a new node to the graph.
+
+    /// \todo It adds the nodes in a reversed order.
+    /// (i.e. the lastly added node becomes the first.)
     Node addNode() {
-      Node n; n.n=nodes.size();
-      nodes.push_back(NodeT()); //FIXME: Hmmm...
-
+      int n;
+      
+      if(first_free_node==-1)
+        {
+          n = nodes.size();
+          nodes.push_back(NodeT());
+        }
+      else {
+        n = first_free_node;
+        first_free_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_node;
+      if(first_node != -1) nodes[first_node].prev = n;
+      first_node = n;
+      nodes[n].prev = -1;
+      
+      nodes[n].first_in = nodes[n].first_out = -1;
+      
+      Node nn; nn.n=n;
+
+      //Update dynamic maps
       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
-          i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
-
-      return n;
+          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
+
+      return nn;
     }
     
     Edge addEdge(Node u, Node v) {
-      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
-      edges[e.n].tail=u.n; edges[e.n].head=v.n;
-      edges[e.n].next_out=nodes[u.n].first_out;
-      edges[e.n].next_in=nodes[v.n].first_in;
-      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
-
+      int n;
+      
+      if(first_free_edge==-1)
+        {
+          n = edges.size();
+          edges.push_back(EdgeT());
+        }
+      else {
+        n = first_free_edge;
+        first_free_edge = edges[n].next_in;
+      }
+      
+      edges[n].tail = u.n; edges[n].head = v.n;
+
+      edges[n].next_out = nodes[u.n].first_out;
+      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
+      edges[n].next_in = nodes[v.n].first_in;
+      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
+      edges[n].prev_in = edges[n].prev_out = -1;
+        
+      nodes[u.n].first_out = nodes[v.n].first_in = n;
+
+      Edge e; e.n=n;
+
+      //Update dynamic maps
       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
           i!=dyn_edge_maps.end(); ++i) (**i).add(e);
@@ -175 +244 @@
     }
 
-    void clear() {nodes.clear();edges.clear();}
+  private:
+    void eraseEdge(int n) {
+      
+      if(edges[n].next_in!=-1)
+        edges[edges[n].next_in].prev_in = edges[n].prev_in;
+      if(edges[n].prev_in!=-1)
+        edges[edges[n].prev_in].next_in = edges[n].next_in;
+      else nodes[edges[n].head].first_in = edges[n].next_in;
+      
+      if(edges[n].next_out!=-1)
+        edges[edges[n].next_out].prev_out = edges[n].prev_out;
+      if(edges[n].prev_out!=-1)
+        edges[edges[n].prev_out].next_out = edges[n].next_out;
+      else nodes[edges[n].tail].first_out = edges[n].next_out;
+      
+      edges[n].next_in = first_free_edge;
+      first_free_edge = -1;      
+
+      //Update dynamic maps
+      Edge e; e.n=n;
+      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
+          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
+    }
+      
+  public:
+
+    void erase(Node nn) {
+      int n=nn.n;
+      
+      int m;
+      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
+      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
+
+      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
+      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
+      else first_node = nodes[n].next;
+      
+      nodes[n].next = first_free_node;
+      first_free_node = n;
+
+      //Update dynamic maps
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
+    }
+    
+    void erase(Edge e) { eraseEdge(e.n); }
+
+    ///\bug Dynamic maps must be updated!
+    ///
+    void clear() {
+      nodes.clear();edges.clear();
+      first_node=first_free_node=first_free_edge=-1;
+    }
 
     class Node {
-      friend class SmartGraph;
+      friend class ListGraph;
       template <typename T> friend class NodeMap;
       
@@ -188 +309 @@
     protected:
       int n;
-      friend int SmartGraph::id(Node v) const; 
+      friend int ListGraph::id(Node v) const; 
       Node(int nn) {n=nn;}
     public:
@@ -199 +320 @@
     
     class NodeIt : public Node {
-      friend class SmartGraph;
+      friend class ListGraph;
     public:
-      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
+      NodeIt(const ListGraph& G) : Node(G.first_node) { }
       NodeIt() : Node() { }
     };
 
     class Edge {
-      friend class SmartGraph;
+      friend class ListGraph;
       template <typename T> friend class EdgeMap;
 
-      //template <typename T> friend class SymSmartGraph::SymEdgeMap;      
-      //friend Edge SymSmartGraph::opposite(Edge) const;
+      //template <typename T> friend class SymListGraph::SymEdgeMap;      
+      //friend Edge SymListGraph::opposite(Edge) const;
       
       friend class Node;
@@ -216 +337 @@
     protected:
       int n;
-      friend int SmartGraph::id(Edge e) const;
+      friend int ListGraph::id(Edge e) const;
 
       Edge(int nn) {n=nn;}
@@ -226 +347 @@
       bool operator<(const Edge i) const {return n<i.n;}
       ///\bug This is a workaround until somebody tells me how to
-      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
+      ///make class \c SymListGraph::SymEdgeMap friend of Edge
       int &idref() {return n;}
       const int &idref() const {return n;}
@@ -232 +353 @@
     
     class EdgeIt : public Edge {
-      friend class SmartGraph;
+      friend class ListGraph;
     public:
-      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
+      EdgeIt(const ListGraph& G) : Edge() {
+        int m;
+        for(m=G.first_node;
+            m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
+        n = (m==-1)?-1:G.nodes[m].first_in;
+      }
       EdgeIt (Invalid i) : Edge(i) { }
       EdgeIt() : Edge() { }
       ///\bug This is a workaround until somebody tells me how to
-      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
+      ///make class \c SymListGraph::SymEdgeMap friend of Edge
       int &idref() {return n;}
     };
     
     class OutEdgeIt : public Edge {
-      friend class SmartGraph;
+      friend class ListGraph;
     public: 
       OutEdgeIt() : Edge() { }
       OutEdgeIt (Invalid i) : Edge(i) { }
 
-      OutEdgeIt(const SmartGraph& G,const Node v)
+      OutEdgeIt(const ListGraph& G,const Node v)
         : Edge(G.nodes[v.n].first_out) {}
     };
     
     class InEdgeIt : public Edge {
-      friend class SmartGraph;
+      friend class ListGraph;
     public: 
       InEdgeIt() : Edge() { }
       InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
+      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
     };
 
@@ -268 +394 @@
       typedef Node KeyType;
 
-      NodeMap(const SmartGraph &_G) :
+      NodeMap(const ListGraph &_G) :
         DynMapBase<Node>(_G), container(_G.maxNodeId())
       {
         G->dyn_node_maps.push_back(this);
       }
-      NodeMap(const SmartGraph &_G,const T &t) :
+      NodeMap(const ListGraph &_G,const T &t) :
         DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
       {
@@ -358 +484 @@
       typedef Edge KeyType;
 
-      EdgeMap(const SmartGraph &_G) :
+      EdgeMap(const ListGraph &_G) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId())
       {
@@ -365 +491 @@
         G->dyn_edge_maps.push_back(this);
       }
-      EdgeMap(const SmartGraph &_G,const T &t) :
+      EdgeMap(const ListGraph &_G,const T &t) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
       {
@@ -447 +573 @@
   ///of oppositely directed edges.
   ///There is a new edge map type called
-  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
+  ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
   ///that complements this
   ///feature by
@@ -457 +583 @@
   ///The oppositely directed edge can also be obtained easily
   ///using \ref opposite.
-  ///\warning It shares the similarity with \ref SmartGraph that
-  ///it is not possible to delete edges or nodes from the graph.
-  //\sa \ref SmartGraph.
-
-  class SymSmartGraph : public SmartGraph
+  ///
+  ///Here erase(Edge) deletes a pair of edges.
+  ///
+  ///\todo this date structure need some reconsiderations. Maybe it
+  ///should be implemented independently from ListGraph.
+
+  class SymListGraph : public ListGraph
   {
   public:
@@ -467 +595 @@
     template<typename T> friend class SymEdgeMap;
 
-    SymSmartGraph() : SmartGraph() { }
-    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
+    SymListGraph() : ListGraph() { }
+    SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
+    ///Adds a pair of oppositely directed edges to the graph.
     Edge addEdge(Node u, Node v)
     {
-      Edge e = SmartGraph::addEdge(u,v);
-      SmartGraph::addEdge(v,u);
+      Edge e = ListGraph::addEdge(u,v);
+      ListGraph::addEdge(v,u);
       return e;
     }
 
+    void erase(Node n) { ListGraph::erase(n); }
     ///The oppositely directed edge.
 
@@ -487 +617 @@
     }
     
+    ///Removes a pair of oppositely directed edges to the graph.
+    void erase(Edge e) {
+      ListGraph::erase(opposite(e));
+      ListGraph::erase(e);
+    }
+    
     ///Common data storage for the edge pairs.
 
@@ -499 +635 @@
       typedef Edge KeyType;
 
-      SymEdgeMap(const SymSmartGraph &_G) :
+      SymEdgeMap(const SymListGraph &_G) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
       {
-        static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
-      }
-      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
+        static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
+      }
+      SymEdgeMap(const SymListGraph &_G,const T &t) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
       {
@@ -536 +672 @@
         if(G) {
           std::vector<DynMapBase<Edge>* >::iterator i;
-          for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
-              i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
+          for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
+              i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
                 && *i!=this; ++i) ;
           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
           //A better way to do that: (Is this really important?)
           if(*i==this) {
-            *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
-            static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
+            *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
+            static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
           }
         }