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

     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 "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) = NULL;

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

    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 i) { 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 	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_node_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_node_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 	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 	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   ///\se \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) = NULL;

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

   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     NodeSet() : nodes(), first_node(-1),

   801 		  first_free_node(-1) {}

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

   803 				     first_free_node(_g.first_free_node) {}

   805     ~NodeSet()

   806     {

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

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

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

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

   811     }

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

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

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

   817     ///its name would suggests...

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

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

   820     ///its name would suggests...

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

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

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

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

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

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

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

   832     NodeIt& first(NodeIt& v) const {

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

   834     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   841 //     template< typename It >

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

   844 //     template< typename It >

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

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

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

   850     void setInvalid(Edge &e) { }

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

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

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

   856     NodeIt& next(NodeIt& it) const {

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

   858       return it;

   859     }

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

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

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

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

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

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

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

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

   871     Node addNode() {

   872       int n;

   874       if(first_free_node==-1)

   875 	{

   876 	  n = nodes.size();

   877 	  nodes.push_back(NodeT());

   878 	}

   879       else {

   880 	n = first_free_node;

   881 	first_free_node = nodes[n].next;

   882       }

   884       nodes[n].next = first_node;

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

   886       first_node = n;

   887       nodes[n].prev = -1;

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

   891       Node nn; nn.n=n;

   893       //Update dynamic maps

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

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

   897       return nn;

   898     }

   900     void erase(Node nn) {

   901       int n=nn.n;

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

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

   905       else first_node = nodes[n].next;

   907       nodes[n].next = first_free_node;

   908       first_free_node = n;

   910       //Update dynamic maps

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

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

   913     }

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

   916     ///

   917     void clear() {

   918       nodes.clear();

   919       first_node = first_free_node = -1;

   920     }

   922     class Node {

   923       friend class NodeSet;

   924       template <typename T> friend class NodeMap;

   926       friend class Edge;

   927       friend class OutEdgeIt;

   928       friend class InEdgeIt;

   930     protected:

   931       int n;

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

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

   934     public:

   935       Node() {}

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

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

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

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

   940     };

   942     class NodeIt : public Node {

   943       friend class NodeSet;

   944     public:

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

   946       NodeIt() : Node() { }

   947     };

   949     class Edge {

   950       //friend class NodeSet;

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

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

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

   956       //      friend class Node;

   957       //      friend class NodeIt;

   958     protected:

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

   960       //      Edge(int nn) {}

   961     public:

   962       Edge() { }

   963       Edge (Invalid) { }

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

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

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

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

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

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

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

   971     };

   973     class EdgeIt : public Edge {

   974       //friend class NodeSet;

   975     public:

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

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

   978       EdgeIt() : Edge() { }

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

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

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

   982     };

   984     class OutEdgeIt : public Edge {

   985       friend class NodeSet;

   986     public:

   987       OutEdgeIt() : Edge() { }

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

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

   990     };

   992     class InEdgeIt : public Edge {

   993       friend class NodeSet;

   994     public:

   995       InEdgeIt() : Edge() { }

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

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

   998     };

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

  1001     {

  1002       std::vector<T> container;

  1004     public:

  1005       typedef T ValueType;

  1006       typedef Node KeyType;

  1008       NodeMap(const NodeSet &_G) :

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

  1010       {

  1011 	G->dyn_node_maps.push_back(this);

  1012       }

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

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

  1015       {

  1016 	G->dyn_node_maps.push_back(this);

  1017       }

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

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

  1021       {

  1022  	G->dyn_node_maps.push_back(this);

  1023       }

  1025       template<typename TT> friend class NodeMap;

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

  1028       ///

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

  1030 	DynMapBase<Node>(*m.G)

  1031       {

  1032 	G->dyn_node_maps.push_back(this);

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

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

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

  1036 	    i++)

  1037 	  container.push_back(*i);

  1038       }

  1039       ~NodeMap()

  1040       {

  1041 	if(G) {

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

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

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

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

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

  1047 	  if(*i==this) {

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

  1049 	    G->dyn_node_maps.pop_back();

  1050 	  }

  1051 	}

  1052       }

  1054       void add(const Node k)

  1055       {

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

  1057       }

  1059       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

  1071       ///cause serious problem.

  1072       ///\todo Is this really so?

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

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

  1075       {

  1076 	container = m.container;

  1077 	return *this;

  1078       }

  1079       template<typename TT>

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

  1081       {

  1082 	copy(m.container.begin(), m.container.end(), container.begin());

  1083 	return *this;

  1084       }

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

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

  1088     };

  1090     template <typename T> class EdgeMap

  1091     {

  1092     public:

  1093       typedef T ValueType;

  1094       typedef Edge KeyType;

  1096       EdgeMap(const NodeSet &) { }

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

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

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

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

  1102       ///

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

  1104       ~EdgeMap() { }

  1106       void add(const Edge  ) { }

  1107       void erase(const Edge) { }

  1109       void set(Edge, T) { }

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

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

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

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

  1116       template<typename TT>

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

  1119       void update() {}

  1120       void update(T a) {}

  1121     };

  1122   };

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

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

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

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

  1131   /// each other.

  1132   ///

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

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

  1135   ///

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

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

  1138   ///

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

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

  1141   ///

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

  1143   ///the description of \ref GraphSkeleton.

  1144   ///\sa \ref GraphSkeleton.

  1145   ///\sa \ref NodeSet.

  1146   template<typename GG>

  1147   class EdgeSet {

  1149     typedef GG NodeGraphType;

  1151     NodeGraphType &G;

  1153     class Node;

  1155     //Edges are double linked.

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

  1157     struct NodeT

  1158     {

  1159       int first_in,first_out;

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

  1161     };

  1163     struct EdgeT

  1164     {

  1165       Node head, tail;

  1166       int prev_in, prev_out;

  1167       int next_in, next_out;

  1168     };

  1171     typename NodeGraphType::NodeMap<NodeT> nodes;

  1173     std::vector<EdgeT> edges;

  1174     //The first free edge

  1175     int first_free_edge;

  1177   protected:

  1179     template <typename Key> class DynMapBase

  1180     {

  1181     protected:

  1182       const EdgeSet* G;

  1183     public:

  1184       virtual void add(const Key k) = NULL;

  1185       virtual void erase(const Key k) = NULL;

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

  1187       virtual ~DynMapBase() {}

  1188       friend class EdgeSet;

  1189     };

  1191   public:

  1192     //template <typename T> class NodeMap;

  1193     template <typename T> class EdgeMap;

  1195     class Node;

  1196     class Edge;

  1198     //  protected:

  1199     // HELPME:

  1200   protected:

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

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

  1203     ///

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

  1206   public:

  1208     class NodeIt;

  1209     class EdgeIt;

  1210     class OutEdgeIt;

  1211     class InEdgeIt;

  1213     template <typename T> class NodeMap;

  1214     template <typename T> class EdgeMap;

  1216   public:

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

  1219 				 nodes(_G), edges(),

  1220 				 first_free_edge(-1) { }

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

  1222 				 first_free_edge(_g.first_free_edge) { }

  1224     ~EdgeSet()

  1225     {

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

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

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

  1229 	    i=dyn_edge_maps.begin();

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

  1231     }

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

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

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

  1237     ///its name would suggests...

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

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

  1240     ///its name would suggests...

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

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

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

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

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

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

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

  1252     NodeIt& first(NodeIt& v) const {

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

  1254     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

  1261 //     template< typename It >

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

  1264 //     template< typename It >

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

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

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

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

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

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

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

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

  1277     OutEdgeIt& next(OutEdgeIt& it) const

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

  1279     InEdgeIt& next(InEdgeIt& it) const

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

  1281     EdgeIt& next(EdgeIt& it) const {

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

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

  1284       }

  1285       else {

  1286 	typename NodeGraphType::Node n;

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

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

  1289 	    G.next(n)) ;

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

  1291       }

  1292       return it;

  1293     }

  1295     int id(Node v) const { return G.id(v); }

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

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

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

  1301     Edge addEdge(Node u, Node v) {

  1302       int n;

  1304       if(first_free_edge==-1)

  1305 	{

  1306 	  n = edges.size();

  1307 	  edges.push_back(EdgeT());

  1308 	}

  1309       else {

  1310 	n = first_free_edge;

  1311 	first_free_edge = edges[n].next_in;

  1312       }

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

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

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

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

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

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

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

  1324       Edge e; e.n=n;

  1326       //Update dynamic maps

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

  1328 	    i=dyn_edge_maps.begin();

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

  1331       return e;

  1332     }

  1334   private:

  1335     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

  1349       edges[n].next_in = first_free_edge;

  1350       first_free_edge = -1;

  1352       //Update dynamic maps

  1353       Edge e; e.n=n;

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

  1355 	    i=dyn_edge_maps.begin();

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

  1357     }

  1359   public:

  1361 //     void erase(Node nn) {

  1362 //       int n=nn.n;

  1363 //       int m;

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

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

  1366 //     }

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

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

  1371 //     //

  1372 //     void clear() {

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

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

  1375 //     }

  1377     class Node : public NodeGraphType::Node {

  1378       friend class EdgeSet;

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

  1381       friend class Edge;

  1382       friend class OutEdgeIt;

  1383       friend class InEdgeIt;

  1384       friend class SymEdge;

  1386     protected:

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

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

  1389     public:

  1390       Node() : NodeGraphType::Node() {}

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

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

  1393     };

  1395     class NodeIt : public NodeGraphType::NodeIt {

  1396       friend class EdgeSet;

  1397     public:

  1398       NodeIt() : NodeGraphType::NodeIt() { }

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

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

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

  1402 	: NodeGraphType::NodeIt(n) {}

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

  1404     };

  1406     class Edge {

  1407       friend class EdgeSet;

  1408       template <typename T> friend class EdgeMap;

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

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

  1413       friend class Node;

  1414       friend class NodeIt;

  1415     protected:

  1416       int n;

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

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

  1420     public:

  1421       Edge() { }

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

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

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

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

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

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

  1428       int &idref() {return n;}

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

  1430     };

  1432     class EdgeIt : public Edge {

  1433       friend class EdgeSet;

  1434     public:

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

  1436       	typename NodeGraphType::Node m;

  1437 	for(G.first(m);

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

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

  1440       }

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

  1442       EdgeIt() : Edge() { }

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

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

  1445       int &idref() {return n;}

  1446     };

  1448     class OutEdgeIt : public Edge {

  1449       friend class EdgeSet;

  1450     public:

  1451       OutEdgeIt() : Edge() { }

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

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

  1455     };

  1457     class InEdgeIt : public Edge {

  1458       friend class EdgeSet;

  1459     public:

  1460       InEdgeIt() : Edge() { }

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

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

  1463     };

  1465     template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>

  1466     {

  1467     public:

  1468       NodeMap(const EdgeSet &_G) :

  1469 	NodeGraphType::NodeMap<T>(_G.G) { }

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

  1471 	NodeGraphType::NodeMap<T>(_G.G,t) { }

  1472       //It is unnecessary

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

  1474 	: NodeGraphType::NodeMap<T>(m) { }

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

  1477       ///

  1478       template<typename TT>

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

  1480 	: NodeGraphType::NodeMap<T>(m) { }

  1481     };

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

  1484     {

  1485       std::vector<T> container;

  1487     public:

  1488       typedef T ValueType;

  1489       typedef Edge KeyType;

  1491       EdgeMap(const EdgeSet &_G) :

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

  1493       {

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

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

  1496 	G->dyn_edge_maps.push_back(this);

  1497       }

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

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

  1500       {

  1501 	G->dyn_edge_maps.push_back(this);

  1502       }

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

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

  1505       {

  1506  	G->dyn_node_maps.push_back(this);

  1507       }

  1509       template<typename TT> friend class EdgeMap;

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

  1512       ///

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

  1514 	DynMapBase<Edge>(*m.G)

  1515       {

  1516 	G->dyn_node_maps.push_back(this);

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

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

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

  1520 	    i++)

  1521 	  container.push_back(*i);

  1522       }

  1523       ~EdgeMap()

  1524       {

  1525 	if(G) {

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

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

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

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

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

  1531 	  if(*i==this) {

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

  1533 	    G->dyn_edge_maps.pop_back();

  1534 	  }

  1535 	}

  1536       }

  1538       void add(const Edge k)

  1539       {

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

  1541       }

  1542       void erase(const Edge) { }

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

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

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

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

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

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

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

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

  1553       ///cause serious problem.

  1554       ///\todo Is this really so?

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

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

  1557       {

  1558 	container = m.container;

  1559 	return *this;

  1560       }

  1561       template<typename TT>

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

  1563       {

  1564 	copy(m.container.begin(), m.container.end(), container.begin());

  1565 	return *this;

  1566       }

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

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

  1570     };

  1572   };

  1574 /// @}

  1576 } //namespace hugo

  1578 #endif //HUGO_LIST_GRAPH_H

author	alpar
	Mon, 26 Apr 2004 09:00:12 +0000
changeset 406	e8377ac921b6
parent 405	a2d8ec38e8db
child 408	cc8629dc2935
permissions	-rw-r--r--