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

     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     ///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 	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     class Node;

  1157     //Edges are double linked.

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

  1159     struct NodeT

  1160     {

  1161       int first_in,first_out;

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

  1163     };

  1165     struct EdgeT

  1166     {

  1167       Node head, tail;

  1168       int prev_in, prev_out;

  1169       int next_in, next_out;

  1170     };

  1173     typename NodeGraphType::NodeMap<NodeT> nodes;

  1175     std::vector<EdgeT> edges;

  1176     //The first free edge

  1177     int first_free_edge;

  1179   protected:

  1181     template <typename Key> class DynMapBase

  1182     {

  1183     protected:

  1184       const EdgeSet* G;

  1185     public:

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

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

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

  1189       virtual ~DynMapBase() {}

  1190       friend class EdgeSet;

  1191     };

  1193   public:

  1194     //template <typename T> class NodeMap;

  1195     template <typename T> class EdgeMap;

  1197     class Node;

  1198     class Edge;

  1200     //  protected:

  1201     // HELPME:

  1202   protected:

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

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

  1205     ///

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

  1208   public:

  1210     class NodeIt;

  1211     class EdgeIt;

  1212     class OutEdgeIt;

  1213     class InEdgeIt;

  1215     template <typename T> class NodeMap;

  1216     template <typename T> class EdgeMap;

  1218   public:

  1220     ///Constructor

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

  1223     ///\param _G the base graph.

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

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

  1226 				 nodes(_G), edges(),

  1227 				 first_free_edge(-1) { }

  1228     ///Copy constructor

  1230     ///Makes a copy of an EdgeSet.

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

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

  1233 				 first_free_edge(_g.first_free_edge) { }

  1235     ~EdgeSet()

  1236     {

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

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

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

  1240 	    i=dyn_edge_maps.begin();

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

  1242     }

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

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

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

  1248     ///its name would suggests...

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

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

  1251     ///its name would suggests...

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

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

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

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

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

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

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

  1263     NodeIt& first(NodeIt& v) const {

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

  1265     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

  1272 //     template< typename It >

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

  1275 //     template< typename It >

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

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

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

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

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

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

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

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

  1288     OutEdgeIt& next(OutEdgeIt& it) const

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

  1290     InEdgeIt& next(InEdgeIt& it) const

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

  1292     EdgeIt& next(EdgeIt& it) const {

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

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

  1295       }

  1296       else {

  1297 	typename NodeGraphType::Node n;

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

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

  1300 	    G.next(n)) ;

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

  1302       }

  1303       return it;

  1304     }

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

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

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

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

  1312     Edge addEdge(Node u, Node v) {

  1313       int n;

  1315       if(first_free_edge==-1)

  1316 	{

  1317 	  n = edges.size();

  1318 	  edges.push_back(EdgeT());

  1319 	}

  1320       else {

  1321 	n = first_free_edge;

  1322 	first_free_edge = edges[n].next_in;

  1323       }

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

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

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

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

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

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

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

  1335       Edge e; e.n=n;

  1337       //Update dynamic maps

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

  1339 	    i=dyn_edge_maps.begin();

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

  1342       return e;

  1343     }

  1345   private:

  1346     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

  1360       edges[n].next_in = first_free_edge;

  1361       first_free_edge = -1;

  1363       //Update dynamic maps

  1364       Edge e; e.n=n;

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

  1366 	    i=dyn_edge_maps.begin();

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

  1368     }

  1370   public:

  1372 //     void erase(Node nn) {

  1373 //       int n=nn.n;

  1374 //       int m;

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

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

  1377 //     }

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

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

  1382 //     //

  1383 //     void clear() {

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

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

  1386 //     }

  1388     class Node : public NodeGraphType::Node {

  1389       friend class EdgeSet;

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

  1392       friend class Edge;

  1393       friend class OutEdgeIt;

  1394       friend class InEdgeIt;

  1395       friend class SymEdge;

  1397     protected:

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

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

  1400     public:

  1401       Node() : NodeGraphType::Node() {}

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

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

  1404     };

  1406     class NodeIt : public NodeGraphType::NodeIt {

  1407       friend class EdgeSet;

  1408     public:

  1409       NodeIt() : NodeGraphType::NodeIt() { }

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

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

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

  1413 	: NodeGraphType::NodeIt(n) {}

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

  1415     };

  1417     class Edge {

  1418       friend class EdgeSet;

  1419       template <typename T> friend class EdgeMap;

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

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

  1424       friend class Node;

  1425       friend class NodeIt;

  1426     protected:

  1427       int n;

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

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

  1431     public:

  1432       Edge() { }

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

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

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

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

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

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

  1439       int &idref() {return n;}

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

  1441     };

  1443     class EdgeIt : public Edge {

  1444       friend class EdgeSet;

  1445     public:

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

  1447       	typename NodeGraphType::Node m;

  1448 	for(G.first(m);

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

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

  1451       }

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

  1453       EdgeIt() : Edge() { }

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

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

  1456       int &idref() {return n;}

  1457     };

  1459     class OutEdgeIt : public Edge {

  1460       friend class EdgeSet;

  1461     public:

  1462       OutEdgeIt() : Edge() { }

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

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

  1466     };

  1468     class InEdgeIt : public Edge {

  1469       friend class EdgeSet;

  1470     public:

  1471       InEdgeIt() : Edge() { }

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

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

  1474     };

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

  1477     {

  1478     public:

  1479       NodeMap(const EdgeSet &_G) :

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

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

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

  1483       //It is unnecessary

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

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

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

  1488       ///

  1489       template<typename TT>

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

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

  1492     };

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

  1495     {

  1496       std::vector<T> container;

  1498     public:

  1499       typedef T ValueType;

  1500       typedef Edge KeyType;

  1502       EdgeMap(const EdgeSet &_G) :

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

  1504       {

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

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

  1507 	G->dyn_edge_maps.push_back(this);

  1508       }

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

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

  1511       {

  1512 	G->dyn_edge_maps.push_back(this);

  1513       }

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

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

  1516       {

  1517  	G->dyn_node_maps.push_back(this);

  1518       }

  1520       template<typename TT> friend class EdgeMap;

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

  1523       ///

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

  1525 	DynMapBase<Edge>(*m.G)

  1526       {

  1527 	G->dyn_node_maps.push_back(this);

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

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

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

  1531 	    i++)

  1532 	  container.push_back(*i);

  1533       }

  1534       ~EdgeMap()

  1535       {

  1536 	if(G) {

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

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

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

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

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

  1542 	  if(*i==this) {

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

  1544 	    G->dyn_edge_maps.pop_back();

  1545 	  }

  1546 	}

  1547       }

  1549       void add(const Edge k)

  1550       {

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

  1552       }

  1553       void erase(const Edge) { }

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

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

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

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

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

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

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

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

  1564       ///cause serious problem.

  1565       ///\todo Is this really so?

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

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

  1568       {

  1569 	container = m.container;

  1570 	return *this;

  1571       }

  1572       template<typename TT>

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

  1574       {

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

  1576 	return *this;

  1577       }

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

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

  1581     };

  1583   };

  1585 /// @}

  1587 } //namespace hugo

  1589 #endif //HUGO_LIST_GRAPH_H

author	beckerjc
	Thu, 29 Apr 2004 16:45:40 +0000
changeset 481	54d8feda437b
parent 406	e8377ac921b6
child 491	4804c967543d
permissions	-rw-r--r--