# HG changeset patch
# User alpar
# Date 1082912018 0
# Node ID b4d7b19b67401973de72914fa68f09fcab8d90ab
# Parent  639c9daed784c6967fd22040e0796be2b2d49bca
I hope it works. The 'erase' functions hasn't been tested yet.

diff -r 639c9daed784 -r b4d7b19b6740 src/work/alpar/list_graph.h
--- a/src/work/alpar/list_graph.h	Sun Apr 25 14:25:04 2004 +0000
+++ b/src/work/alpar/list_graph.h	Sun Apr 25 16:53:38 2004 +0000
@@ -4,7 +4,7 @@
 #define HUGO_SMART_GRAPH_H
 
 ///\file
-///\brief SmartGraph and SymSmartGraph classes.
+///\brief ListGraph and SymListGraph classes.
 
 #include <vector>
 #include <limits.h>
@@ -13,52 +13,63 @@
 
 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:
+  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;
     };
     
   public:
     template <typename T> class EdgeMap;
     template <typename T> class EdgeMap;
-
+    
     class Node;
     class Edge;
 
@@ -84,10 +95,14 @@
     
   public:
 
-    SmartGraph() : nodes(), edges() { }
-    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
+    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) {}
     
-    ~SmartGraph()
+    ~ListGraph()
     {
       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
@@ -139,45 +154,151 @@
     { It tmp(it); return next(tmp); }
 
     NodeIt& next(NodeIt& it) const { 
-      it.n=(it.n+2)%(nodes.size()+1)-1; 
+      it.n=nodes[it.n].next; 
       return it; 
     }
     OutEdgeIt& next(OutEdgeIt& it) const
     { it.n=edges[it.n].next_out; return it; }
     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);
+	  i!=dyn_node_maps.end(); ++i) (**i).add(nn);
 
-      return n;
+      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);
 
       return e;
     }
 
-    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;
       
       friend class Edge;
@@ -187,7 +308,7 @@
 
     protected:
       int n;
-      friend int SmartGraph::id(Node v) const; 
+      friend int ListGraph::id(Node v) const; 
       Node(int nn) {n=nn;}
     public:
       Node() {}
@@ -198,24 +319,24 @@
     };
     
     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;
       friend class NodeIt;
     protected:
       int n;
-      friend int SmartGraph::id(Edge e) const;
+      friend int ListGraph::id(Edge e) const;
 
       Edge(int nn) {n=nn;}
     public:
@@ -225,38 +346,43 @@
       bool operator!=(const Edge i) const {return n!=i.n;}
       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;}
     };
     
     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){}
     };
 
     template <typename T> class NodeMap : public DynMapBase<Node>
@@ -267,12 +393,12 @@
       typedef T ValueType;
       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)
       {
 	G->dyn_node_maps.push_back(this);
@@ -357,14 +483,14 @@
       typedef T ValueType;
       typedef Edge KeyType;
 
-      EdgeMap(const SmartGraph &_G) :
+      EdgeMap(const ListGraph &_G) :
 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
       {
 	//FIXME: What if there are empty Id's?
 	//FIXME: Can I use 'this' in a constructor?
 	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)
       {
 	G->dyn_edge_maps.push_back(this);
@@ -446,7 +572,7 @@
   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
   ///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
   ///storing shared values for the edge pairs. The usual
@@ -456,25 +582,29 @@
   ///
   ///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.
+  ///
+  ///Here erase(Edge) deletes a pair of edges.
+  ///
+  ///\todo this date structure need some reconsiderations. Maybe it
+  ///should be implemented independently from ListGraph.
 
-  class SymSmartGraph : public SmartGraph
+  class SymListGraph : public ListGraph
   {
   public:
     template<typename T> class SymEdgeMap;
     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.
 
     ///Returns the oppositely directed
@@ -486,6 +616,12 @@
       return f;
     }
     
+    ///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.
 
     ///This map makes it possible to store data shared by the oppositely
@@ -498,12 +634,12 @@
       typedef T ValueType;
       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);
+	static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
       }
-      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
+      SymEdgeMap(const SymListGraph &_G,const T &t) :
 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
       {
 	G->dyn_edge_maps.push_back(this);
@@ -535,14 +671,14 @@
       {
 	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();
 	  }
 	}
       }
diff -r 639c9daed784 -r b4d7b19b6740 src/work/alpar/list_graph_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/alpar/list_graph_demo.cc	Sun Apr 25 16:53:38 2004 +0000
@@ -0,0 +1,124 @@
+#include<list_graph.h>
+#include<skeletons/graph.h>
+
+#include <iostream>
+#include <vector>
+
+using namespace hugo;
+
+typedef ListGraph Graph;
+//typedef GraphSkeleton Graph;
+
+
+Graph::OutEdgeIt safeFirstOut(const Graph &G, Graph::Node n)
+{
+  return G.valid(n) ? Graph::OutEdgeIt(G,n):INVALID;
+}
+
+int main()
+{
+
+  typedef Graph::Edge Edge;
+  typedef Graph::InEdgeIt InEdgeIt;
+  typedef Graph::OutEdgeIt OutEdgeIt;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::Node Node;
+  typedef Graph::NodeIt NodeIt;
+  
+  Graph G;
+  
+  {
+    NodeIt n;
+
+    for(int i=0;i<10;i++) G.addNode();
+    for(G.first(n);G.valid(n);G.next(n)) 
+      for(NodeIt m(G);m!=INVALID;G.next(m)) 
+	if(n!=m) G.addEdge(n,m);
+    
+    OutEdgeIt e = safeFirstOut(G,n);
+    OutEdgeIt f = safeFirstOut(G,NodeIt(G));
+    
+    
+    InEdgeIt i(INVALID), j;
+    InEdgeIt ii(i);
+    ii=G.first(i,n);
+    ii=G.next(i);
+    
+    OutEdgeIt o(INVALID), oo;
+    OutEdgeIt ooo(oo);
+    oo=G.first(o,n);
+    oo=G.next(o);
+    
+    EdgeIt ei(INVALID), eie;
+    EdgeIt eiee(ei);
+    eie=G.first(ei);
+    eie=G.next(ei);
+    
+    Edge eee(i);
+    eee=o;
+    eee=eie;
+    
+    
+    bool tm;
+    tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei);
+    
+    std::vector<InEdgeIt> v(10);
+    std::vector<InEdgeIt> w(10,INVALID);
+    
+  }
+  
+  // Test of maps
+
+  G.clear();
+  
+  for(int i=0;i<10;i++) G.addNode();
+  for(NodeIt i(G);G.valid(i);G.next(i)) 
+    for(NodeIt j(G);G.valid(j);G.next(j)) 
+      if(i<j) G.addEdge(i,j);           //The iterators are comparable
+  
+  Graph::NodeMap<int> n(G);
+  int count=0;
+  for(NodeIt i(G);G.valid(i);G.next(i)) n[i]=count++;
+  
+  Graph::NodeMap<int> nn=n;
+  Graph::NodeMap<double> dd=n;
+
+  n = nn;
+  
+  dd = nn;
+  
+  Graph::EdgeMap<int> emap(G);
+
+  // Test of SymListGraph
+  
+  {
+    typedef SymListGraph Graph;
+    typedef Graph::Edge Edge;
+    typedef Graph::InEdgeIt InEdgeIt;
+    typedef Graph::OutEdgeIt OutEdgeIt;
+    typedef Graph::EdgeIt EdgeIt;
+    typedef Graph::Node Node;
+    typedef Graph::NodeIt NodeIt;
+
+    Graph G;
+
+    for(int i=0;i<10;i++) G.addNode();
+    for(NodeIt i(G);G.valid(i);G.next(i)) 
+      for(NodeIt j(G);G.valid(j);G.next(j)) 
+	if(i<j) G.addEdge(i,j);           //The iterators are comparable
+  
+    Graph::EdgeMap<int> em(G);
+    Graph::SymEdgeMap<int> sm(G);
+    for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e);
+    for(EdgeIt e(G);G.valid(e);G.next(e))
+      if(G.tail(e)<G.head(e)) sm[e]=G.id(e);
+    
+    for(EdgeIt e(G);G.valid(e);G.next(e))
+      std::cout << G.id(G.tail(e)) << "->" << G.id(G.head(e))
+		<< ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e))
+		<< " em=" << em[e]
+		<< " sm=" << sm[e] << "\n";
+    
+  }
+  
+}