lemon-0.x: src/work/alpar/list_graph.h@9632ea8be6ca

     1 // -*- mode:C++ -*-

     3 #ifndef HUGO_LIST_GRAPH_H

     4 #define HUGO_LIST_GRAPH_H

     6 ///\ingroup graphs

     7 ///\file

     8 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.

    10 #include <vector>

    11 #include <limits.h>

    13 #include <hugo/invalid.h>

    15 namespace hugo {

    17 /// \addtogroup graphs

    18 /// @{

    20   class SymListGraph;

    22   ///A list graph class.

    24   ///This is a simple and fast erasable graph implementation.

    25   ///

    26   ///It conforms to the graph interface documented under

    27   ///the description of \ref GraphSkeleton.

    28   ///\sa \ref GraphSkeleton.

    29   class ListGraph {

    31     //Nodes are double linked.

    32     //The free nodes are only single linked using the "next" field.

    33     struct NodeT

    34     {

    35       int first_in,first_out;

    36       int prev, next;

    37       //      NodeT() {}

    38     };

    39     //Edges are double linked.

    40     //The free edges are only single linked using the "next_in" field.

    41     struct EdgeT

    42     {

    43       int head, tail;

    44       int prev_in, prev_out;

    45       int next_in, next_out;

    46       //FIXME: is this necessary?

    47       //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}

    48     };

    50     std::vector<NodeT> nodes;

    51     //The first node

    52     int first_node;

    53     //The first free node

    54     int first_free_node;

    55     std::vector<EdgeT> edges;

    56     //The first free edge

    57     int first_free_edge;

    59   protected:

    61     template <typename Key> class DynMapBase

    62     {

    63     protected:

    64       const ListGraph* G;

    65     public:

    66       virtual void add(const Key k) = 0;

    67       virtual void erase(const Key k) = 0;

    68       DynMapBase(const ListGraph &_G) : G(&_G) {}

    69       virtual ~DynMapBase() {}

    70       friend class ListGraph;

    71     };

    73   public:

    74     template <typename T> class EdgeMap;

    75     template <typename T> class NodeMap;

    77     class Node;

    78     class Edge;

    80     //  protected:

    81     // HELPME:

    82   protected:

    83     ///\bug It must be public because of SymEdgeMap.

    84     ///

    85     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;

    86     ///\bug It must be public because of SymEdgeMap.

    87     ///

    88     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;

    90   public:

    92     class NodeIt;

    93     class EdgeIt;

    94     class OutEdgeIt;

    95     class InEdgeIt;

    97     template <typename T> class NodeMap;

    98     template <typename T> class EdgeMap;

   100   public:

   102     ListGraph() : nodes(), first_node(-1),

   103 		  first_free_node(-1), edges(), first_free_edge(-1) {}

   104     ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),

   105 				     first_free_node(_g.first_free_node),

   106 				     edges(_g.edges),

   107 				     first_free_edge(_g.first_free_edge) {}

   109     ~ListGraph()

   110     {

   111       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   112 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

   113       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

   114 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

   115     }

   117     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?

   118     int edgeNum() const { return edges.size(); }  //FIXME: What is this?

   120     ///\bug This function does something different than

   121     ///its name would suggests...

   122     int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?

   123     ///\bug This function does something different than

   124     ///its name would suggests...

   125     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?

   127     Node tail(Edge e) const { return edges[e.n].tail; }

   128     Node head(Edge e) const { return edges[e.n].head; }

   130     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }

   131     Node aNode(InEdgeIt e) const { return edges[e.n].head; }

   133     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }

   134     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }

   136     NodeIt& first(NodeIt& v) const {

   137       v=NodeIt(*this); return v; }

   138     EdgeIt& first(EdgeIt& e) const {

   139       e=EdgeIt(*this); return e; }

   140     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {

   141       e=OutEdgeIt(*this,v); return e; }

   142     InEdgeIt& first(InEdgeIt& e, const Node v) const {

   143       e=InEdgeIt(*this,v); return e; }

   145 //     template< typename It >

   146 //     It first() const { It e; first(e); return e; }

   148 //     template< typename It >

   149 //     It first(Node v) const { It e; first(e,v); return e; }

   151     bool valid(Edge e) const { return e.n!=-1; }

   152     bool valid(Node n) const { return n.n!=-1; }

   154     void setInvalid(Edge &e) { e.n=-1; }

   155     void setInvalid(Node &n) { n.n=-1; }

   157     template <typename It> It getNext(It it) const

   158     { It tmp(it); return next(tmp); }

   160     NodeIt& next(NodeIt& it) const {

   161       it.n=nodes[it.n].next;

   162       return it;

   163     }

   164     OutEdgeIt& next(OutEdgeIt& it) const

   165     { it.n=edges[it.n].next_out; return it; }

   166     InEdgeIt& next(InEdgeIt& it) const

   167     { it.n=edges[it.n].next_in; return it; }

   168     EdgeIt& next(EdgeIt& it) const {

   169       if(edges[it.n].next_in!=-1) {

   170 	it.n=edges[it.n].next_in;

   171       }

   172       else {

   173 	int n;

   174 	for(n=nodes[edges[it.n].head].next;

   175 	    n!=-1 && nodes[n].first_in == -1;

   176 	    n = nodes[n].next) ;

   177 	it.n = (n==-1)?-1:nodes[n].first_in;

   178       }

   179       return it;

   180     }

   182     int id(Node v) const { return v.n; }

   183     int id(Edge e) const { return e.n; }

   185     /// Adds a new node to the graph.

   187     /// \todo It adds the nodes in a reversed order.

   188     /// (i.e. the lastly added node becomes the first.)

   189     Node addNode() {

   190       int n;

   192       if(first_free_node==-1)

   193 	{

   194 	  n = nodes.size();

   195 	  nodes.push_back(NodeT());

   196 	}

   197       else {

   198 	n = first_free_node;

   199 	first_free_node = nodes[n].next;

   200       }

   202       nodes[n].next = first_node;

   203       if(first_node != -1) nodes[first_node].prev = n;

   204       first_node = n;

   205       nodes[n].prev = -1;

   207       nodes[n].first_in = nodes[n].first_out = -1;

   209       Node nn; nn.n=n;

   211       //Update dynamic maps

   212       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   213 	  i!=dyn_node_maps.end(); ++i) (**i).add(nn);

   215       return nn;

   216     }

   218     Edge addEdge(Node u, Node v) {

   219       int n;

   221       if(first_free_edge==-1)

   222 	{

   223 	  n = edges.size();

   224 	  edges.push_back(EdgeT());

   225 	}

   226       else {

   227 	n = first_free_edge;

   228 	first_free_edge = edges[n].next_in;

   229       }

   231       edges[n].tail = u.n; edges[n].head = v.n;

   233       edges[n].next_out = nodes[u.n].first_out;

   234       if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;

   235       edges[n].next_in = nodes[v.n].first_in;

   236       if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;

   237       edges[n].prev_in = edges[n].prev_out = -1;

   239       nodes[u.n].first_out = nodes[v.n].first_in = n;

   241       Edge e; e.n=n;

   243       //Update dynamic maps

   244       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

   245 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);

   247       return e;

   248     }

   250   private:

   251     void eraseEdge(int n) {

   253       if(edges[n].next_in!=-1)

   254 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

   255       if(edges[n].prev_in!=-1)

   256 	edges[edges[n].prev_in].next_in = edges[n].next_in;

   257       else nodes[edges[n].head].first_in = edges[n].next_in;

   259       if(edges[n].next_out!=-1)

   260 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

   261       if(edges[n].prev_out!=-1)

   262 	edges[edges[n].prev_out].next_out = edges[n].next_out;

   263       else nodes[edges[n].tail].first_out = edges[n].next_out;

   265       edges[n].next_in = first_free_edge;

   266       first_free_edge = -1;

   268       //Update dynamic maps

   269       Edge e; e.n=n;

   270       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

   271 	  i!=dyn_edge_maps.end(); ++i) (**i).erase(e);

   272     }

   274   public:

   276     void erase(Node nn) {

   277       int n=nn.n;

   279       int m;

   280       while((m=nodes[n].first_in)!=-1) eraseEdge(m);

   281       while((m=nodes[n].first_out)!=-1) eraseEdge(m);

   283       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;

   284       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;

   285       else first_node = nodes[n].next;

   287       nodes[n].next = first_free_node;

   288       first_free_node = n;

   290       //Update dynamic maps

   291       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   292 	  i!=dyn_node_maps.end(); ++i) (**i).erase(nn);

   293     }

   295     void erase(Edge e) { eraseEdge(e.n); }

   297     ///\bug Dynamic maps must be updated!

   298     ///

   299     void clear() {

   300       nodes.clear();edges.clear();

   301       first_node=first_free_node=first_free_edge=-1;

   302     }

   304     class Node {

   305       friend class ListGraph;

   306       template <typename T> friend class NodeMap;

   308       friend class Edge;

   309       friend class OutEdgeIt;

   310       friend class InEdgeIt;

   311       friend class SymEdge;

   313     protected:

   314       int n;

   315       friend int ListGraph::id(Node v) const;

   316       Node(int nn) {n=nn;}

   317     public:

   318       Node() {}

   319       Node (Invalid) { n=-1; }

   320       bool operator==(const Node i) const {return n==i.n;}

   321       bool operator!=(const Node i) const {return n!=i.n;}

   322       bool operator<(const Node i) const {return n<i.n;}

   323     };

   325     class NodeIt : public Node {

   326       friend class ListGraph;

   327     public:

   328       NodeIt() : Node() { }

   329       NodeIt(Invalid i) : Node(i) { }

   330       NodeIt(const ListGraph& G) : Node(G.first_node) { }

   331     };

   333     class Edge {

   334       friend class ListGraph;

   335       template <typename T> friend class EdgeMap;

   337       //template <typename T> friend class SymListGraph::SymEdgeMap;

   338       //friend Edge SymListGraph::opposite(Edge) const;

   340       friend class Node;

   341       friend class NodeIt;

   342     protected:

   343       int n;

   344       friend int ListGraph::id(Edge e) const;

   346       Edge(int nn) {n=nn;}

   347     public:

   348       Edge() { }

   349       Edge (Invalid) { n=-1; }

   350       bool operator==(const Edge i) const {return n==i.n;}

   351       bool operator!=(const Edge i) const {return n!=i.n;}

   352       bool operator<(const Edge i) const {return n<i.n;}

   353       ///\bug This is a workaround until somebody tells me how to

   354       ///make class \c SymListGraph::SymEdgeMap friend of Edge

   355       int &idref() {return n;}

   356       const int &idref() const {return n;}

   357     };

   359     class EdgeIt : public Edge {

   360       friend class ListGraph;

   361     public:

   362       EdgeIt(const ListGraph& G) : Edge() {

   363       	int m;

   364 	for(m=G.first_node;

   365 	    m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);

   366 	n = (m==-1)?-1:G.nodes[m].first_in;

   367       }

   368       EdgeIt (Invalid i) : Edge(i) { }

   369       EdgeIt() : Edge() { }

   370       ///\bug This is a workaround until somebody tells me how to

   371       ///make class \c SymListGraph::SymEdgeMap friend of Edge

   372       int &idref() {return n;}

   373     };

   375     class OutEdgeIt : public Edge {

   376       friend class ListGraph;

   377     public:

   378       OutEdgeIt() : Edge() { }

   379       OutEdgeIt (Invalid i) : Edge(i) { }

   381       OutEdgeIt(const ListGraph& G,const Node v)

   382 	: Edge(G.nodes[v.n].first_out) {}

   383     };

   385     class InEdgeIt : public Edge {

   386       friend class ListGraph;

   387     public:

   388       InEdgeIt() : Edge() { }

   389       InEdgeIt (Invalid i) : Edge(i) { }

   390       InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}

   391     };

   393     template <typename T> class NodeMap : public DynMapBase<Node>

   394     {

   395       std::vector<T> container;

   397     public:

   398       typedef T ValueType;

   399       typedef Node KeyType;

   401       NodeMap(const ListGraph &_G) :

   402 	DynMapBase<Node>(_G), container(_G.maxNodeId())

   403       {

   404 	G->dyn_node_maps.push_back(this);

   405       }

   406       NodeMap(const ListGraph &_G,const T &t) :

   407 	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)

   408       {

   409 	G->dyn_node_maps.push_back(this);

   410       }

   412       NodeMap(const NodeMap<T> &m) :

   413  	DynMapBase<Node>(*m.G), container(m.container)

   414       {

   415  	G->dyn_node_maps.push_back(this);

   416       }

   418       template<typename TT> friend class NodeMap;

   420       ///\todo It can copy between different types.

   421       ///

   422       template<typename TT> NodeMap(const NodeMap<TT> &m) :

   423 	DynMapBase<Node>(*m.G)

   424       {

   425 	G->dyn_node_maps.push_back(this);

   426 	typename std::vector<TT>::const_iterator i;

   427 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   428 	    i!=m.container.end();

   429 	    i++)

   430 	  container.push_back(*i);

   431       }

   432       ~NodeMap()

   433       {

   434 	if(G) {

   435 	  std::vector<DynMapBase<Node>* >::iterator i;

   436 	  for(i=G->dyn_node_maps.begin();

   437 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

   438 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

   439 	  //A better way to do that: (Is this really important?)

   440 	  if(*i==this) {

   441 	    *i=G->dyn_node_maps.back();

   442 	    G->dyn_node_maps.pop_back();

   443 	  }

   444 	}

   445       }

   447       void add(const Node k)

   448       {

   449 	if(k.n>=int(container.size())) container.resize(k.n+1);

   450       }

   452       void erase(const Node) { }

   454       void set(Node n, T a) { container[n.n]=a; }

   455       //'T& operator[](Node n)' would be wrong here

   456       typename std::vector<T>::reference

   457       operator[](Node n) { return container[n.n]; }

   458       //'const T& operator[](Node n)' would be wrong here

   459       typename std::vector<T>::const_reference

   460       operator[](Node n) const { return container[n.n]; }

   462       ///\warning There is no safety check at all!

   463       ///Using operator = between maps attached to different graph may

   464       ///cause serious problem.

   465       ///\todo Is this really so?

   466       ///\todo It can copy between different types.

   467       const NodeMap<T>& operator=(const NodeMap<T> &m)

   468       {

   469 	container = m.container;

   470 	return *this;

   471       }

   472       template<typename TT>

   473       const NodeMap<T>& operator=(const NodeMap<TT> &m)

   474       {

   475 	std::copy(m.container.begin(), m.container.end(), container.begin());

   476 	return *this;

   477       }

   479       void update() {}    //Useless for Dynamic Maps

   480       void update(T a) {}  //Useless for Dynamic Maps

   481     };

   483     template <typename T> class EdgeMap : public DynMapBase<Edge>

   484     {

   485       std::vector<T> container;

   487     public:

   488       typedef T ValueType;

   489       typedef Edge KeyType;

   491       EdgeMap(const ListGraph &_G) :

   492 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())

   493       {

   494 	//FIXME: What if there are empty Id's?

   495 	//FIXME: Can I use 'this' in a constructor?

   496 	G->dyn_edge_maps.push_back(this);

   497       }

   498       EdgeMap(const ListGraph &_G,const T &t) :

   499 	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)

   500       {

   501 	G->dyn_edge_maps.push_back(this);

   502       }

   503       EdgeMap(const EdgeMap<T> &m) :

   504  	DynMapBase<Edge>(*m.G), container(m.container)

   505       {

   506  	G->dyn_edge_maps.push_back(this);

   507       }

   509       template<typename TT> friend class EdgeMap;

   511       ///\todo It can copy between different types.

   512       ///

   513       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :

   514 	DynMapBase<Edge>(*m.G)

   515       {

   516 	G->dyn_edge_maps.push_back(this);

   517 	typename std::vector<TT>::const_iterator i;

   518 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   519 	    i!=m.container.end();

   520 	    i++)

   521 	  container.push_back(*i);

   522       }

   523       ~EdgeMap()

   524       {

   525 	if(G) {

   526 	  std::vector<DynMapBase<Edge>* >::iterator i;

   527 	  for(i=G->dyn_edge_maps.begin();

   528 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

   529 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   530 	  //A better way to do that: (Is this really important?)

   531 	  if(*i==this) {

   532 	    *i=G->dyn_edge_maps.back();

   533 	    G->dyn_edge_maps.pop_back();

   534 	  }

   535 	}

   536       }

   538       void add(const Edge k)

   539       {

   540 	if(k.n>=int(container.size())) container.resize(k.n+1);

   541       }

   542       void erase(const Edge) { }

   544       void set(Edge n, T a) { container[n.n]=a; }

   545       //T get(Edge n) const { return container[n.n]; }

   546       typename std::vector<T>::reference

   547       operator[](Edge n) { return container[n.n]; }

   548       typename std::vector<T>::const_reference

   549       operator[](Edge n) const { return container[n.n]; }

   551       ///\warning There is no safety check at all!

   552       ///Using operator = between maps attached to different graph may

   553       ///cause serious problem.

   554       ///\todo Is this really so?

   555       ///\todo It can copy between different types.

   556       const EdgeMap<T>& operator=(const EdgeMap<T> &m)

   557       {

   558 	container = m.container;

   559 	return *this;

   560       }

   561       template<typename TT>

   562       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)

   563       {

   564 	std::copy(m.container.begin(), m.container.end(), container.begin());

   565 	return *this;

   566       }

   568       void update() {}    //Useless for DynMaps

   569       void update(T a) {}  //Useless for DynMaps

   570     };

   572   };

   574   ///Graph for bidirectional edges.

   576   ///The purpose of this graph structure is to handle graphs

   577   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair

   578   ///of oppositely directed edges.

   579   ///There is a new edge map type called

   580   ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"

   581   ///that complements this

   582   ///feature by

   583   ///storing shared values for the edge pairs. The usual

   584   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   585   ///can be used

   586   ///as well.

   587   ///

   588   ///The oppositely directed edge can also be obtained easily

   589   ///using \ref opposite.

   590   ///

   591   ///Here erase(Edge) deletes a pair of edges.

   592   ///

   593   ///\todo this date structure need some reconsiderations. Maybe it

   594   ///should be implemented independently from ListGraph.

   596   class SymListGraph : public ListGraph

   597   {

   598   public:

   599     template<typename T> class SymEdgeMap;

   600     template<typename T> friend class SymEdgeMap;

   602     SymListGraph() : ListGraph() { }

   603     SymListGraph(const ListGraph &_g) : ListGraph(_g) { }

   604     ///Adds a pair of oppositely directed edges to the graph.

   605     Edge addEdge(Node u, Node v)

   606     {

   607       Edge e = ListGraph::addEdge(u,v);

   608       ListGraph::addEdge(v,u);

   609       return e;

   610     }

   612     void erase(Node n) { ListGraph::erase(n); }

   613     ///The oppositely directed edge.

   615     ///Returns the oppositely directed

   616     ///pair of the edge \c e.

   617     Edge opposite(Edge e) const

   618     {

   619       Edge f;

   620       f.idref() = e.idref() - 2*(e.idref()%2) + 1;

   621       return f;

   622     }

   624     ///Removes a pair of oppositely directed edges to the graph.

   625     void erase(Edge e) {

   626       ListGraph::erase(opposite(e));

   627       ListGraph::erase(e);

   628     }

   630     ///Common data storage for the edge pairs.

   632     ///This map makes it possible to store data shared by the oppositely

   633     ///directed pairs of edges.

   634     template <typename T> class SymEdgeMap : public DynMapBase<Edge>

   635     {

   636       std::vector<T> container;

   638     public:

   639       typedef T ValueType;

   640       typedef Edge KeyType;

   642       SymEdgeMap(const SymListGraph &_G) :

   643 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)

   644       {

   645 	static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);

   646       }

   647       SymEdgeMap(const SymListGraph &_G,const T &t) :

   648 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)

   649       {

   650 	G->dyn_edge_maps.push_back(this);

   651       }

   653       SymEdgeMap(const SymEdgeMap<T> &m) :

   654  	DynMapBase<SymEdge>(*m.G), container(m.container)

   655       {

   656  	G->dyn_node_maps.push_back(this);

   657       }

   659       //      template<typename TT> friend class SymEdgeMap;

   661       ///\todo It can copy between different types.

   662       ///

   664       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :

   665 	DynMapBase<SymEdge>(*m.G)

   666       {

   667 	G->dyn_node_maps.push_back(this);

   668 	typename std::vector<TT>::const_iterator i;

   669 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   670 	    i!=m.container.end();

   671 	    i++)

   672 	  container.push_back(*i);

   673       }

   675       ~SymEdgeMap()

   676       {

   677 	if(G) {

   678 	  std::vector<DynMapBase<Edge>* >::iterator i;

   679 	  for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();

   680 	      i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()

   681 		&& *i!=this; ++i) ;

   682 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   683 	  //A better way to do that: (Is this really important?)

   684 	  if(*i==this) {

   685 	    *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();

   686 	    static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();

   687 	  }

   688 	}

   689       }

   691       void add(const Edge k)

   692       {

   693 	if(!k.idref()%2&&k.idref()/2>=int(container.size()))

   694 	  container.resize(k.idref()/2+1);

   695       }

   696       void erase(const Edge k) { }

   698       void set(Edge n, T a) { container[n.idref()/2]=a; }

   699       //T get(Edge n) const { return container[n.idref()/2]; }

   700       typename std::vector<T>::reference

   701       operator[](Edge n) { return container[n.idref()/2]; }

   702       typename std::vector<T>::const_reference

   703       operator[](Edge n) const { return container[n.idref()/2]; }

   705       ///\warning There is no safety check at all!

   706       ///Using operator = between maps attached to different graph may

   707       ///cause serious problem.

   708       ///\todo Is this really so?

   709       ///\todo It can copy between different types.

   710       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)

   711       {

   712 	container = m.container;

   713 	return *this;

   714       }

   715       template<typename TT>

   716       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)

   717       {

   718 	std::copy(m.container.begin(), m.container.end(), container.begin());

   719 	return *this;

   720       }

   722       void update() {}    //Useless for DynMaps

   723       void update(T a) {}  //Useless for DynMaps

   725     };

   727   };

   730   ///A graph class containing only nodes.

   732   ///This class implements a graph structure without edges.

   733   ///The most useful application of this class is to be the node set of an

   734   ///\ref EdgeSet class.

   735   ///

   736   ///It conforms to the graph interface documented under

   737   ///the description of \ref GraphSkeleton with the exception that you cannot

   738   ///add (or delete) edges. The usual edge iterators are exists, but they are

   739   ///always \ref INVALID.

   740   ///\sa \ref GraphSkeleton

   741   ///\sa \ref EdgeSet

   742   class NodeSet {

   744     //Nodes are double linked.

   745     //The free nodes are only single linked using the "next" field.

   746     struct NodeT

   747     {

   748       int first_in,first_out;

   749       int prev, next;

   750       //      NodeT() {}

   751     };

   753     std::vector<NodeT> nodes;

   754     //The first node

   755     int first_node;

   756     //The first free node

   757     int first_free_node;

   759   protected:

   761     template <typename Key> class DynMapBase

   762     {

   763     protected:

   764       const NodeSet* G;

   765     public:

   766       virtual void add(const Key k) = 0;

   767       virtual void erase(const Key k) = 0;

   768       DynMapBase(const NodeSet &_G) : G(&_G) {}

   769       virtual ~DynMapBase() {}

   770       friend class NodeSet;

   771     };

   773   public:

   774     template <typename T> class EdgeMap;

   775     template <typename T> class NodeMap;

   777     class Node;

   778     class Edge;

   780     //  protected:

   781     // HELPME:

   782   protected:

   783     ///\bug It must be public because of SymEdgeMap.

   784     ///

   785     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;

   786     //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;

   788   public:

   790     class NodeIt;

   791     class EdgeIt;

   792     class OutEdgeIt;

   793     class InEdgeIt;

   795     template <typename T> class NodeMap;

   796     template <typename T> class EdgeMap;

   798   public:

   800     ///Default constructor

   801     NodeSet() : nodes(), first_node(-1),

   802 		  first_free_node(-1) {}

   803     ///Copy constructor

   804     NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),

   805 				     first_free_node(_g.first_free_node) {}

   807     ~NodeSet()

   808     {

   809       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   810 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

   811       //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

   812       //	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

   813     }

   815     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?

   816     int edgeNum() const { return 0; }  //FIXME: What is this?

   818     ///\bug This function does something different than

   819     ///its name would suggests...

   820     int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?

   821     ///\bug This function does something different than

   822     ///its name would suggests...

   823     int maxEdgeId() const { return 0; }  //FIXME: What is this?

   825     Node tail(Edge e) const { return INVALID; }

   826     Node head(Edge e) const { return INVALID; }

   828     Node aNode(OutEdgeIt e) const { return INVALID; }

   829     Node aNode(InEdgeIt e) const { return INVALID; }

   831     Node bNode(OutEdgeIt e) const { return INVALID; }

   832     Node bNode(InEdgeIt e) const { return INVALID; }

   834     NodeIt& first(NodeIt& v) const {

   835       v=NodeIt(*this); return v; }

   836     EdgeIt& first(EdgeIt& e) const {

   837       e=EdgeIt(*this); return e; }

   838     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {

   839       e=OutEdgeIt(*this,v); return e; }

   840     InEdgeIt& first(InEdgeIt& e, const Node v) const {

   841       e=InEdgeIt(*this,v); return e; }

   843 //     template< typename It >

   844 //     It first() const { It e; first(e); return e; }

   846 //     template< typename It >

   847 //     It first(Node v) const { It e; first(e,v); return e; }

   849     bool valid(Edge e) const { return false; }

   850     bool valid(Node n) const { return n.n!=-1; }

   852     void setInvalid(Edge &e) { }

   853     void setInvalid(Node &n) { n.n=-1; }

   855     template <typename It> It getNext(It it) const

   856     { It tmp(it); return next(tmp); }

   858     NodeIt& next(NodeIt& it) const {

   859       it.n=nodes[it.n].next;

   860       return it;

   861     }

   862     OutEdgeIt& next(OutEdgeIt& it) const { return it; }

   863     InEdgeIt& next(InEdgeIt& it) const { return it; }

   864     EdgeIt& next(EdgeIt& it) const { return it; }

   866     int id(Node v) const { return v.n; }

   867     int id(Edge e) const { return -1; }

   869     /// Adds a new node to the graph.

   871     /// \todo It adds the nodes in a reversed order.

   872     /// (i.e. the lastly added node becomes the first.)

   873     Node addNode() {

   874       int n;

   876       if(first_free_node==-1)

   877 	{

   878 	  n = nodes.size();

   879 	  nodes.push_back(NodeT());

   880 	}

   881       else {

   882 	n = first_free_node;

   883 	first_free_node = nodes[n].next;

   884       }

   886       nodes[n].next = first_node;

   887       if(first_node != -1) nodes[first_node].prev = n;

   888       first_node = n;

   889       nodes[n].prev = -1;

   891       nodes[n].first_in = nodes[n].first_out = -1;

   893       Node nn; nn.n=n;

   895       //Update dynamic maps

   896       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   897 	  i!=dyn_node_maps.end(); ++i) (**i).add(nn);

   899       return nn;

   900     }

   902     void erase(Node nn) {

   903       int n=nn.n;

   905       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;

   906       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;

   907       else first_node = nodes[n].next;

   909       nodes[n].next = first_free_node;

   910       first_free_node = n;

   912       //Update dynamic maps

   913       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   914 	  i!=dyn_node_maps.end(); ++i) (**i).erase(nn);

   915     }

   917     ///\bug Dynamic maps must be updated!

   918     ///

   919     void clear() {

   920       nodes.clear();

   921       first_node = first_free_node = -1;

   922     }

   924     class Node {

   925       friend class NodeSet;

   926       template <typename T> friend class NodeMap;

   928       friend class Edge;

   929       friend class OutEdgeIt;

   930       friend class InEdgeIt;

   932     protected:

   933       int n;

   934       friend int NodeSet::id(Node v) const;

   935       Node(int nn) {n=nn;}

   936     public:

   937       Node() {}

   938       Node (Invalid i) { n=-1; }

   939       bool operator==(const Node i) const {return n==i.n;}

   940       bool operator!=(const Node i) const {return n!=i.n;}

   941       bool operator<(const Node i) const {return n<i.n;}

   942     };

   944     class NodeIt : public Node {

   945       friend class NodeSet;

   946     public:

   947       NodeIt(const NodeSet& G) : Node(G.first_node) { }

   948       NodeIt() : Node() { }

   949     };

   951     class Edge {

   952       //friend class NodeSet;

   953       //template <typename T> friend class EdgeMap;

   955       //template <typename T> friend class SymNodeSet::SymEdgeMap;

   956       //friend Edge SymNodeSet::opposite(Edge) const;

   958       //      friend class Node;

   959       //      friend class NodeIt;

   960     protected:

   961       //friend int NodeSet::id(Edge e) const;

   962       //      Edge(int nn) {}

   963     public:

   964       Edge() { }

   965       Edge (Invalid) { }

   966       bool operator==(const Edge i) const {return true;}

   967       bool operator!=(const Edge i) const {return false;}

   968       bool operator<(const Edge i) const {return false;}

   969       ///\bug This is a workaround until somebody tells me how to

   970       ///make class \c SymNodeSet::SymEdgeMap friend of Edge

   971       //      int idref() {return -1;}

   972       //      int idref() const {return -1;}

   973     };

   975     class EdgeIt : public Edge {

   976       //friend class NodeSet;

   977     public:

   978       EdgeIt(const NodeSet& G) : Edge() { }

   979       EdgeIt (Invalid i) : Edge(i) { }

   980       EdgeIt() : Edge() { }

   981       ///\bug This is a workaround until somebody tells me how to

   982       ///make class \c SymNodeSet::SymEdgeMap friend of Edge

   983       //      int idref() {return -1;}

   984     };

   986     class OutEdgeIt : public Edge {

   987       friend class NodeSet;

   988     public:

   989       OutEdgeIt() : Edge() { }

   990       OutEdgeIt (Invalid i) : Edge(i) { }

   991       OutEdgeIt(const NodeSet& G,const Node v)	: Edge() {}

   992     };

   994     class InEdgeIt : public Edge {

   995       friend class NodeSet;

   996     public:

   997       InEdgeIt() : Edge() { }

   998       InEdgeIt (Invalid i) : Edge(i) { }

   999       InEdgeIt(const NodeSet& G,Node v) :Edge() {}

  1000     };

  1002     template <typename T> class NodeMap : public DynMapBase<Node>

  1003     {

  1004       std::vector<T> container;

  1006     public:

  1007       typedef T ValueType;

  1008       typedef Node KeyType;

  1010       NodeMap(const NodeSet &_G) :

  1011 	DynMapBase<Node>(_G), container(_G.maxNodeId())

  1012       {

  1013 	G->dyn_node_maps.push_back(this);

  1014       }

  1015       NodeMap(const NodeSet &_G,const T &t) :

  1016 	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)

  1017       {

  1018 	G->dyn_node_maps.push_back(this);

  1019       }

  1021       NodeMap(const NodeMap<T> &m) :

  1022  	DynMapBase<Node>(*m.G), container(m.container)

  1023       {

  1024  	G->dyn_node_maps.push_back(this);

  1025       }

  1027       template<typename TT> friend class NodeMap;

  1029       ///\todo It can copy between different types.

  1030       ///

  1031       template<typename TT> NodeMap(const NodeMap<TT> &m) :

  1032 	DynMapBase<Node>(*m.G)

  1033       {

  1034 	G->dyn_node_maps.push_back(this);

  1035 	typename std::vector<TT>::const_iterator i;

  1036 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

  1037 	    i!=m.container.end();

  1038 	    i++)

  1039 	  container.push_back(*i);

  1040       }

  1041       ~NodeMap()

  1042       {

  1043 	if(G) {

  1044 	  std::vector<DynMapBase<Node>* >::iterator i;

  1045 	  for(i=G->dyn_node_maps.begin();

  1046 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

  1047 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

  1048 	  //A better way to do that: (Is this really important?)

  1049 	  if(*i==this) {

  1050 	    *i=G->dyn_node_maps.back();

  1051 	    G->dyn_node_maps.pop_back();

  1052 	  }

  1053 	}

  1054       }

  1056       void add(const Node k)

  1057       {

  1058 	if(k.n>=int(container.size())) container.resize(k.n+1);

  1059       }

  1061       void erase(const Node) { }

  1063       void set(Node n, T a) { container[n.n]=a; }

  1064       //'T& operator[](Node n)' would be wrong here

  1065       typename std::vector<T>::reference

  1066       operator[](Node n) { return container[n.n]; }

  1067       //'const T& operator[](Node n)' would be wrong here

  1068       typename std::vector<T>::const_reference

  1069       operator[](Node n) const { return container[n.n]; }

  1071       ///\warning There is no safety check at all!

  1072       ///Using operator = between maps attached to different graph may

  1073       ///cause serious problem.

  1074       ///\todo Is this really so?

  1075       ///\todo It can copy between different types.

  1076       const NodeMap<T>& operator=(const NodeMap<T> &m)

  1077       {

  1078 	container = m.container;

  1079 	return *this;

  1080       }

  1081       template<typename TT>

  1082       const NodeMap<T>& operator=(const NodeMap<TT> &m)

  1083       {

  1084 	std::copy(m.container.begin(), m.container.end(), container.begin());

  1085 	return *this;

  1086       }

  1088       void update() {}    //Useless for Dynamic Maps

  1089       void update(T a) {}  //Useless for Dynamic Maps

  1090     };

  1092     template <typename T> class EdgeMap

  1093     {

  1094     public:

  1095       typedef T ValueType;

  1096       typedef Edge KeyType;

  1098       EdgeMap(const NodeSet &) { }

  1099       EdgeMap(const NodeSet &,const T &) { }

  1100       EdgeMap(const EdgeMap<T> &) { }

  1101       //      template<typename TT> friend class EdgeMap;

  1103       ///\todo It can copy between different types.

  1104       ///

  1105       template<typename TT> EdgeMap(const EdgeMap<TT> &) { }

  1106       ~EdgeMap() { }

  1108       void add(const Edge  ) { }

  1109       void erase(const Edge) { }

  1111       void set(Edge, T) { }

  1112       //T get(Edge n) const { return container[n.n]; }

  1113       ValueType &operator[](Edge) { return *((T*)(NULL)); }

  1114       const ValueType &operator[](Edge) const { return *((T*)(NULL)); }

  1116       const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }

  1118       template<typename TT>

  1119       const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }

  1121       void update() {}

  1122       void update(T a) {}

  1123     };

  1124   };

  1128   ///Graph structure using a node set of another graph.

  1130   ///This structure can be used to establish another graph over a node set

  1131   /// of an existing one. The node iterator will go through the nodes of the

  1132   /// original graph, and the NodeMap's of both graphs will convert to

  1133   /// each other.

  1134   ///

  1135   ///\warning Adding or deleting nodes from the graph is not safe if an

  1136   ///\ref EdgeSet is currently attached to it!

  1137   ///

  1138   ///\todo Make it possible to add/delete edges from the base graph

  1139   ///(and from \ref EdgeSet, as well)

  1140   ///

  1141   ///\param GG The type of the graph which shares its node set with this class.

  1142   ///Its interface must conform with \ref GraphSkeleton.

  1143   ///

  1144   ///It conforms to the graph interface documented under

  1145   ///the description of \ref GraphSkeleton.

  1146   ///\sa \ref GraphSkeleton.

  1147   ///\sa \ref NodeSet.

  1148   template<typename GG>

  1149   class EdgeSet {

  1151     typedef GG NodeGraphType;

  1153     NodeGraphType &G;

  1155   public:

  1156     class Node;

  1157     int id(Node v) const;

  1159     class Node : public NodeGraphType::Node {

  1160       friend class EdgeSet;

  1161       //      template <typename T> friend class NodeMap;

  1163       friend class Edge;

  1164       friend class OutEdgeIt;

  1165       friend class InEdgeIt;

  1166       friend class SymEdge;

  1168     public:

  1169       friend int EdgeSet::id(Node v) const;

  1170       //      Node(int nn) {n=nn;}

  1171     public:

  1172       Node() : NodeGraphType::Node() {}

  1173       Node (Invalid i) : NodeGraphType::Node(i) {}

  1174       Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}

  1175     };

  1177     class NodeIt : public NodeGraphType::NodeIt {

  1178       friend class EdgeSet;

  1179     public:

  1180       NodeIt() : NodeGraphType::NodeIt() { }

  1181       NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}

  1182       NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }

  1183       NodeIt(const typename NodeGraphType::NodeIt &n)

  1184 	: NodeGraphType::NodeIt(n) {}

  1185       operator Node() { return Node(*this);}

  1186     };

  1188   private:

  1189     //Edges are double linked.

  1190     //The free edges are only single linked using the "next_in" field.

  1191     struct NodeT

  1192     {

  1193       int first_in,first_out;

  1194       NodeT() : first_in(-1), first_out(-1) { }

  1195     };

  1197     struct EdgeT

  1198     {

  1199       Node head, tail;

  1200       int prev_in, prev_out;

  1201       int next_in, next_out;

  1202     };

  1205     typename NodeGraphType::template NodeMap<NodeT> nodes;

  1207     std::vector<EdgeT> edges;

  1208     //The first free edge

  1209     int first_free_edge;

  1211   protected:

  1213     template <typename Key> class DynMapBase

  1214     {

  1215     protected:

  1216       const EdgeSet* G;

  1217     public:

  1218       virtual void add(const Key k) = 0;

  1219       virtual void erase(const Key k) = 0;

  1220       DynMapBase(const EdgeSet &_G) : G(&_G) {}

  1221       virtual ~DynMapBase() {}

  1222       friend class EdgeSet;

  1223     };

  1225   public:

  1226     //template <typename T> class NodeMap;

  1227     template <typename T> class EdgeMap;

  1229     class Node;

  1230     class Edge;

  1232     //  protected:

  1233     // HELPME:

  1234   protected:

  1235     // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;

  1236     ///\bug It must be public because of SymEdgeMap.

  1237     ///

  1238     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;

  1240   public:

  1242     class NodeIt;

  1243     class EdgeIt;

  1244     class OutEdgeIt;

  1245     class InEdgeIt;

  1247     template <typename T> class NodeMap;

  1248     template <typename T> class EdgeMap;

  1250   public:

  1252     ///Constructor

  1254     ///Construates a new graph based on the nodeset of an existing one.

  1255     ///\param _G the base graph.

  1256     ///\todo It looks like a copy constructor, but it isn't.

  1257     EdgeSet(NodeGraphType &_G) : G(_G),

  1258 				 nodes(_G), edges(),

  1259 				 first_free_edge(-1) { }

  1260     ///Copy constructor

  1262     ///Makes a copy of an EdgeSet.

  1263     ///It will be based on the same graph.

  1264     EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),

  1265 				 first_free_edge(_g.first_free_edge) { }

  1267     ~EdgeSet()

  1268     {

  1269       // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

  1270       //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

  1271       for(typename std::vector<DynMapBase<Edge> * >::iterator

  1272 	    i=dyn_edge_maps.begin();

  1273 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

  1274     }

  1276     int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?

  1277     int edgeNum() const { return edges.size(); }  //FIXME: What is this?

  1279     ///\bug This function does something different than

  1280     ///its name would suggests...

  1281     int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?

  1282     ///\bug This function does something different than

  1283     ///its name would suggests...

  1284     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?

  1286     Node tail(Edge e) const { return edges[e.n].tail; }

  1287     Node head(Edge e) const { return edges[e.n].head; }

  1289     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }

  1290     Node aNode(InEdgeIt e) const { return edges[e.n].head; }

  1292     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }

  1293     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }

  1295     NodeIt& first(NodeIt& v) const {

  1296       v=NodeIt(*this); return v; }

  1297     EdgeIt& first(EdgeIt& e) const {

  1298       e=EdgeIt(*this); return e; }

  1299     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {

  1300       e=OutEdgeIt(*this,v); return e; }

  1301     InEdgeIt& first(InEdgeIt& e, const Node v) const {

  1302       e=InEdgeIt(*this,v); return e; }

  1304 //     template< typename It >

  1305 //     It first() const { It e; first(e); return e; }

  1307 //     template< typename It >

  1308 //     It first(Node v) const { It e; first(e,v); return e; }

  1310     bool valid(Edge e) const { return e.n!=-1; }

  1311     bool valid(Node n) const { return G.valid(n); }

  1313     void setInvalid(Edge &e) { e.n=-1; }

  1314     void setInvalid(Node &n) { G.setInvalid(n); }

  1316     template <typename It> It getNext(It it) const

  1317     { It tmp(it); return next(tmp); }

  1319     NodeIt& next(NodeIt& it) const { G.next(it); return it; }

  1320     OutEdgeIt& next(OutEdgeIt& it) const

  1321     { it.n=edges[it.n].next_out; return it; }

  1322     InEdgeIt& next(InEdgeIt& it) const

  1323     { it.n=edges[it.n].next_in; return it; }

  1324     EdgeIt& next(EdgeIt& it) const {

  1325       if(edges[it.n].next_in!=-1) {

  1326 	it.n=edges[it.n].next_in;

  1327       }

  1328       else {

  1329 	NodeIt n;

  1330 	for(n=next(edges[it.n].head);

  1331 	    valid(n) && nodes[n].first_in == -1;

  1332 	    next(n)) ;

  1333 	it.n = (valid(n))?-1:nodes[n].first_in;

  1334       }

  1335       return it;

  1336     }

  1338     int id(Edge e) const { return e.n; }

  1340     /// Adds a new node to the graph.

  1341     Node addNode() { return G.AddNode(); }

  1343     Edge addEdge(Node u, Node v) {

  1344       int n;

  1346       if(first_free_edge==-1)

  1347 	{

  1348 	  n = edges.size();

  1349 	  edges.push_back(EdgeT());

  1350 	}

  1351       else {

  1352 	n = first_free_edge;

  1353 	first_free_edge = edges[n].next_in;

  1354       }

  1356       edges[n].tail = u; edges[n].head = v;

  1358       edges[n].next_out = nodes[u].first_out;

  1359       if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;

  1360       edges[n].next_in = nodes[v].first_in;

  1361       if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;

  1362       edges[n].prev_in = edges[n].prev_out = -1;

  1364       nodes[u].first_out = nodes[v].first_in = n;

  1366       Edge e; e.n=n;

  1368       //Update dynamic maps

  1369       for(typename std::vector<DynMapBase<Edge> * >::iterator

  1370 	    i=dyn_edge_maps.begin();

  1371 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);

  1373       return e;

  1374     }

  1376   private:

  1377     void eraseEdge(int n) {

  1379       if(edges[n].next_in!=-1)

  1380 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

  1381       if(edges[n].prev_in!=-1)

  1382 	edges[edges[n].prev_in].next_in = edges[n].next_in;

  1383       else nodes[edges[n].head].first_in = edges[n].next_in;

  1385       if(edges[n].next_out!=-1)

  1386 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

  1387       if(edges[n].prev_out!=-1)

  1388 	edges[edges[n].prev_out].next_out = edges[n].next_out;

  1389       else nodes[edges[n].tail].first_out = edges[n].next_out;

  1391       edges[n].next_in = first_free_edge;

  1392       first_free_edge = -1;

  1394       //Update dynamic maps

  1395       Edge e; e.n=n;

  1396       for(typename std::vector<DynMapBase<Edge> * >::iterator

  1397 	    i=dyn_edge_maps.begin();

  1398 	  i!=dyn_edge_maps.end(); ++i) (**i).erase(e);

  1399     }

  1401   public:

  1403 //     void erase(Node nn) {

  1404 //       int n=nn.n;

  1405 //       int m;

  1406 //       while((m=nodes[n].first_in)!=-1) eraseEdge(m);

  1407 //       while((m=nodes[n].first_out)!=-1) eraseEdge(m);

  1408 //     }

  1410     void erase(Edge e) { eraseEdge(e.n); }

  1412 //     //\bug Dynamic maps must be updated!

  1413 //     //

  1414 //     void clear() {

  1415 //       nodes.clear();edges.clear();

  1416 //       first_node=first_free_node=first_free_edge=-1;

  1417 //     }

  1419     class Edge {

  1420       friend class EdgeSet;

  1421       template <typename T> friend class EdgeMap;

  1423       //template <typename T> friend class SymEdgeSet::SymEdgeMap;

  1424       //friend Edge SymEdgeSet::opposite(Edge) const;

  1426       friend class Node;

  1427       friend class NodeIt;

  1428     protected:

  1429       int n;

  1430       friend int EdgeSet::id(Edge e) const;

  1432       Edge(int nn) {n=nn;}

  1433     public:

  1434       Edge() { }

  1435       Edge (Invalid) { n=-1; }

  1436       bool operator==(const Edge i) const {return n==i.n;}

  1437       bool operator!=(const Edge i) const {return n!=i.n;}

  1438       bool operator<(const Edge i) const {return n<i.n;}

  1439       ///\bug This is a workaround until somebody tells me how to

  1440       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge

  1441       int &idref() {return n;}

  1442       const int &idref() const {return n;}

  1443     };

  1445     class EdgeIt : public Edge {

  1446       friend class EdgeSet;

  1447     public:

  1448       EdgeIt(const EdgeSet& G) : Edge() {

  1449 	//      	typename NodeGraphType::Node m;

  1450         NodeIt m;

  1451 	for(G.first(m);

  1452 	    G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));

  1453 	//AJJAJ! This is a non sense!!!!!!!

  1454 	this->n = G.valid(m)?-1:G.nodes[m].first_in;

  1455       }

  1456       EdgeIt (Invalid i) : Edge(i) { }

  1457       EdgeIt() : Edge() { }

  1458       ///\bug This is a workaround until somebody tells me how to

  1459       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge

  1460       int &idref() {return this->n;}

  1461     };

  1463     class OutEdgeIt : public Edge {

  1464       friend class EdgeSet;

  1465     public:

  1466       OutEdgeIt() : Edge() { }

  1467       OutEdgeIt (Invalid i) : Edge(i) { }

  1469       OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }

  1470     };

  1472     class InEdgeIt : public Edge {

  1473       friend class EdgeSet;

  1474     public:

  1475       InEdgeIt() : Edge() { }

  1476       InEdgeIt (Invalid i) : Edge(i) { }

  1477       InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }

  1478     };

  1480     template <typename T> class NodeMap :

  1481       public NodeGraphType::template NodeMap<T>

  1482     {

  1483     public:

  1484       NodeMap(const EdgeSet &_G) :

  1485         NodeGraphType::NodeMap(_G.G) { } //AJAJJ <T> would be wrong!!!

  1486       NodeMap(const EdgeSet &_G,const T &t) :

  1487 	NodeGraphType::NodeMap(_G.G,t) { }

  1488       //It is unnecessary

  1489       NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :

  1490 	NodeGraphType::NodeMap(m) { }

  1492       ///\todo It can copy between different types.

  1493       ///

  1494       template<typename TT>

  1495       NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)

  1496 	: NodeGraphType::NodeMap(m) { }

  1497     };

  1499     template <typename T> class EdgeMap : public DynMapBase<Edge>

  1500     {

  1501       std::vector<T> container;

  1503     public:

  1504       typedef T ValueType;

  1505       typedef Edge KeyType;

  1507       EdgeMap(const EdgeSet &_G) :

  1508 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())

  1509       {

  1510 	//FIXME: What if there are empty Id's?

  1511 	//FIXME: Can I use 'this' in a constructor?

  1512 	G->dyn_edge_maps.push_back(this);

  1513       }

  1514       EdgeMap(const EdgeSet &_G,const T &t) :

  1515 	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)

  1516       {

  1517 	G->dyn_edge_maps.push_back(this);

  1518       }

  1519       EdgeMap(const EdgeMap<T> &m) :

  1520  	DynMapBase<Edge>(*m.G), container(m.container)

  1521       {

  1522  	G->dyn_edge_maps.push_back(this);

  1523       }

  1525       template<typename TT> friend class EdgeMap;

  1527       ///\todo It can copy between different types.

  1528       ///

  1529       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :

  1530 	DynMapBase<Edge>(*m.G)

  1531       {

  1532 	G->dyn_edge_maps.push_back(this);

  1533 	typename std::vector<TT>::const_iterator i;

  1534 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

  1535 	    i!=m.container.end();

  1536 	    i++)

  1537 	  container.push_back(*i);

  1538       }

  1539       ~EdgeMap()

  1540       {

  1541 	if(G) {

  1542 	  typename std::vector<DynMapBase<Edge>* >::iterator i;

  1543 	  for(i=G->dyn_edge_maps.begin();

  1544 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

  1545 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

  1546 	  //A better way to do that: (Is this really important?)

  1547 	  if(*i==this) {

  1548 	    *i=G->dyn_edge_maps.back();

  1549 	    G->dyn_edge_maps.pop_back();

  1550 	  }

  1551 	}

  1552       }

  1554       void add(const Edge k)

  1555       {

  1556 	if(k.n>=int(container.size())) container.resize(k.n+1);

  1557       }

  1558       void erase(const Edge) { }

  1560       void set(Edge n, T a) { container[n.n]=a; }

  1561       //T get(Edge n) const { return container[n.n]; }

  1562       typename std::vector<T>::reference

  1563       operator[](Edge n) { return container[n.n]; }

  1564       typename std::vector<T>::const_reference

  1565       operator[](Edge n) const { return container[n.n]; }

  1567       ///\warning There is no safety check at all!

  1568       ///Using operator = between maps attached to different graph may

  1569       ///cause serious problem.

  1570       ///\todo Is this really so?

  1571       ///\todo It can copy between different types.

  1572       const EdgeMap<T>& operator=(const EdgeMap<T> &m)

  1573       {

  1574 	container = m.container;

  1575 	return *this;

  1576       }

  1577       template<typename TT>

  1578       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)

  1579       {

  1580 	std::copy(m.container.begin(), m.container.end(), container.begin());

  1581 	return *this;

  1582       }

  1584       void update() {}    //Useless for DynMaps

  1585       void update(T a) {}  //Useless for DynMaps

  1586     };

  1588   };

  1590   template< typename GG>

  1591   int EdgeSet<GG>::id(Node v) const { return G.id(v); }

  1593 /// @}

  1595 } //namespace hugo

  1597 #endif //HUGO_LIST_GRAPH_H

author	deba
	Fri, 07 May 2004 08:18:30 +0000
changeset 571	9632ea8be6ca
parent 531	66f1c466889f
permissions	-rw-r--r--