lemon-0.x: comparison src/work/alpar/list

equal deleted inserted replaced

-:6af55c42621b
+:5e08a51a0375
 #ifndef HUGO_SMART_GRAPH_H
 #define HUGO_SMART_GRAPH_H
 ///\file
-///\brief SmartGraph and SymSmartGraph classes.
+///\brief ListGraph and SymListGraph classes.
 #include <vector>
 #include <limits.h>
 #include "invalid.h"
 namespace hugo {
-class SymSmartGraph;
+class SymListGraph;
 ///A smart graph class.
-///This is a simple and fast graph implementation.
+///This is a simple and fast erasable graph implementation.
-///It is also quite memory efficient, but at the price
+///
-///that <b> it does not support node and edge deletion</b>.
 ///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 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:
+const ListGraph* G;
-template <typename Key> class DynMapBase
-{
-protected:
-const SmartGraph* 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;
 //  protected:
 // HELPME:
 template <typename T> class NodeMap;
 template <typename T> class EdgeMap;
 public:
-SmartGraph() : nodes(), edges() { }
+ListGraph() : nodes(), first_node(-1),
-SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
+		  first_free_node(-1), edges(), first_free_edge(-1) {}
+ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
-~SmartGraph()
+				     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();
 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
 template <typename It> It getNext(It it) const
 { 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();
+int n;
-nodes.push_back(NodeT()); //FIXME: Hmmm...
+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...
+int n;
-edges[e.n].tail=u.n; edges[e.n].head=v.n;
-edges[e.n].next_out=nodes[u.n].first_out;
+if(first_free_edge==-1)
-edges[e.n].next_in=nodes[v.n].first_in;
+	{
-nodes[u.n].first_out=nodes[v.n].first_in=e.n;
+	  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;
 friend class OutEdgeIt;
 friend class InEdgeIt;
 friend class SymEdge;
 protected:
 int n;
-friend int SmartGraph::id(Node v) const;
+friend int ListGraph::id(Node v) const;
 Node(int nn) {n=nn;}
 public:
 Node() {}
 Node (Invalid i) { n=-1; }
 bool operator==(const Node i) const {return n==i.n;}
 bool operator!=(const Node i) const {return n!=i.n;}
 bool operator<(const Node i) const {return n<i.n;}
 };
 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;
+//template <typename T> friend class SymListGraph::SymEdgeMap;
-//friend Edge SymSmartGraph::opposite(Edge) const;
+//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:
 Edge() { }
 Edge (Invalid) { n=-1; }
 bool operator==(const Edge i) const {return n==i.n;}
 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>
 {
 std::vector<T> container;
 public:
 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);
 }
 public:
 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);
 }
 EdgeMap(const EdgeMap<T> &m) :
 ///The purpose of this graph structure is to handle graphs
 ///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
 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
 ///can be used
 ///as well.
 ///
 ///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.
+///Here erase(Edge) deletes a pair of edges.
-//\sa \ref SmartGraph.
+///
+///\todo this date structure need some reconsiderations. Maybe it
-class SymSmartGraph : public SmartGraph
+///should be implemented independently from ListGraph.
+class SymListGraph : public ListGraph
 {
 public:
 template<typename T> class SymEdgeMap;
 template<typename T> friend class SymEdgeMap;
-SymSmartGraph() : SmartGraph() { }
+SymListGraph() : ListGraph() { }
-SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
+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);
+Edge e = ListGraph::addEdge(u,v);
-SmartGraph::addEdge(v,u);
+ListGraph::addEdge(v,u);
 return e;
 }
+void erase(Node n) { ListGraph::erase(n); }
 ///The oppositely directed edge.
 ///Returns the oppositely directed
 ///pair of the edge \c e.
 Edge opposite(Edge e) const
 Edge f;
 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
 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
 ///directed pairs of edges.
 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
 public:
 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);
 }
 ~SymEdgeMap()
 {
 	if(G) {
 	  std::vector<DynMapBase<Edge>* >::iterator i;
-	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
+	  for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
-	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
+	      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();
+	    *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
-	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
+	    static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
 	  }
 	}
 }
 void add(const Edge k)

changeset 398	ecebcedd8960
parent 396	639c9daed784
child 400	cb377609cf1d