lemon-0.x: src/hugo/list_graph.h@2db02d4a9e6e

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

     3 #ifndef HUGO_LIST_GRAPH_H

     4 #define HUGO_LIST_GRAPH_H

     6 ///\ingroup graphs

     7 ///\file

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

    10 #include <vector>

    11 #include <limits.h>

    13 #include <hugo/invalid.h>

    15 namespace hugo {

    17 /// \addtogroup graphs

    18 /// @{

    20   class SymListGraph;

    22   ///A list graph class.

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

    25   ///

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

    27   ///the description of \ref GraphSkeleton.

    28   ///\sa \ref GraphSkeleton.

    29   class ListGraph {

    31     //Nodes are double linked.

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

    33     struct NodeT

    34     {

    35       int first_in,first_out;

    36       int prev, next;

    37       //      NodeT() {}

    38     };

    39     //Edges are double linked.

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

    41     struct EdgeT

    42     {

    43       int head, tail;

    44       int prev_in, prev_out;

    45       int next_in, next_out;

    46       //FIXME: is this necessary?

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

    48     };

    50     std::vector<NodeT> nodes;

    51     //The first node

    52     int first_node;

    53     //The first free node

    54     int first_free_node;

    55     std::vector<EdgeT> edges;

    56     //The first free edge

    57     int first_free_edge;

    59   protected:

    61     template <typename Key> class DynMapBase

    62     {

    63     protected:

    64       const ListGraph* G;

    65     public:

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

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

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

    69       virtual ~DynMapBase() {}

    70       friend class ListGraph;

    71     };

    73   public:

    74     template <typename T> class EdgeMap;

    75     template <typename T> class NodeMap;

    77     class Node;

    78     class Edge;

    80     //  protected:

    81     // HELPME:

    82   protected:

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

    84     ///

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

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

    87     ///

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

    90   public:

    92     class NodeIt;

    93     class EdgeIt;

    94     class OutEdgeIt;

    95     class InEdgeIt;

    97   public:

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

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

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

   102 				     first_free_node(_g.first_free_node),

   103 				     edges(_g.edges),

   104 				     first_free_edge(_g.first_free_edge) {}

   106     ~ListGraph()

   107     {

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

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

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

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

   112     }

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

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

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

   118     ///its name would suggests...

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

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

   121     ///its name would suggests...

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

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

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

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

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

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

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

   133     NodeIt& first(NodeIt& v) const {

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

   135     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   142 //     template< typename It >

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

   145 //     template< typename It >

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

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

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

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

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

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

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

   157     NodeIt& next(NodeIt& it) const {

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

   159       return it;

   160     }

   161     OutEdgeIt& next(OutEdgeIt& it) const

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

   163     InEdgeIt& next(InEdgeIt& it) const

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

   165     EdgeIt& next(EdgeIt& it) const {

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

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

   168       }

   169       else {

   170 	int n;

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

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

   173 	    n = nodes[n].next) ;

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

   175       }

   176       return it;

   177     }

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

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

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

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

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

   186     Node addNode() {

   187       int n;

   189       if(first_free_node==-1)

   190 	{

   191 	  n = nodes.size();

   192 	  nodes.push_back(NodeT());

   193 	}

   194       else {

   195 	n = first_free_node;

   196 	first_free_node = nodes[n].next;

   197       }

   199       nodes[n].next = first_node;

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

   201       first_node = n;

   202       nodes[n].prev = -1;

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

   206       Node nn; nn.n=n;

   208       //Update dynamic maps

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

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

   212       return nn;

   213     }

   215     Edge addEdge(Node u, Node v) {

   216       int n;

   218       if(first_free_edge==-1)

   219 	{

   220 	  n = edges.size();

   221 	  edges.push_back(EdgeT());

   222 	}

   223       else {

   224 	n = first_free_edge;

   225 	first_free_edge = edges[n].next_in;

   226       }

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

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

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

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

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

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

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

   238       Edge e; e.n=n;

   240       //Update dynamic maps

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

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

   244       return e;

   245     }

   247   private:

   248     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

   262       edges[n].next_in = first_free_edge;

   263       first_free_edge = -1;

   265       //Update dynamic maps

   266       Edge e; e.n=n;

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

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

   269     }

   271   public:

   273     void erase(Node nn) {

   274       int n=nn.n;

   276       int m;

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

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

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

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

   282       else first_node = nodes[n].next;

   284       nodes[n].next = first_free_node;

   285       first_free_node = n;

   287       //Update dynamic maps

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

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

   290     }

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

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

   295     ///

   296     void clear() {

   297       nodes.clear();edges.clear();

   298       first_node=first_free_node=first_free_edge=-1;

   299     }

   301     class Node {

   302       friend class ListGraph;

   303       template <typename T> friend class NodeMap;

   305       friend class Edge;

   306       friend class OutEdgeIt;

   307       friend class InEdgeIt;

   308       friend class SymEdge;

   310     protected:

   311       int n;

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

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

   314     public:

   315       Node() {}

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

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

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

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

   320     };

   322     class NodeIt : public Node {

   323       friend class ListGraph;

   324     public:

   325       NodeIt() : Node() { }

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

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

   328       ///\todo Undocumented conversion Node -\> NodeIt.

   329       NodeIt(const ListGraph& G, const Node &n) : Node(n) { }

   330     };

   332     class Edge {

   333       friend class ListGraph;

   334       template <typename T> friend class EdgeMap;

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

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

   339       friend class Node;

   340       friend class NodeIt;

   341     protected:

   342       int n;

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

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

   346     public:

   347       Edge() { }

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

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

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

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

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

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

   354       int &idref() {return n;}

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

   356     };

   358     class EdgeIt : public Edge {

   359       friend class ListGraph;

   360     public:

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

   362       	int m;

   363 	for(m=G.first_node;

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

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

   366       }

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

   368       EdgeIt() : Edge() { }

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

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

   371       int &idref() {return n;}

   372     };

   374     class OutEdgeIt : public Edge {

   375       friend class ListGraph;

   376     public:

   377       OutEdgeIt() : Edge() { }

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

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

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

   382     };

   384     class InEdgeIt : public Edge {

   385       friend class ListGraph;

   386     public:

   387       InEdgeIt() : Edge() { }

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

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

   390     };

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

   393     {

   394       std::vector<T> container;

   396     public:

   397       typedef T ValueType;

   398       typedef Node KeyType;

   400       NodeMap(const ListGraph &_G) :

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

   402       {

   403 	G->dyn_node_maps.push_back(this);

   404       }

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

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

   407       {

   408 	G->dyn_node_maps.push_back(this);

   409       }

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

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

   413       {

   414  	G->dyn_node_maps.push_back(this);

   415       }

   417       template<typename TT> friend class NodeMap;

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

   420       ///

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

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

   424       {

   425 	G->dyn_node_maps.push_back(this);

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

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

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

   429 	    i++)

   430 	  container.push_back(*i);

   431       }

   432       ~NodeMap()

   433       {

   434 	if(G) {

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

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

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

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

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

   440 	  if(*i==this) {

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

   442 	    G->dyn_node_maps.pop_back();

   443 	  }

   444 	}

   445       }

   447       void add(const Node k)

   448       {

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

   450       }

   452       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   464       ///cause serious problem.

   465       ///\todo Is this really so?

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

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

   468       {

   469 	container = m.container;

   470 	return *this;

   471       }

   472       template<typename TT>

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

   474       {

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

   476 	return *this;

   477       }

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

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

   481     };

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

   484     {

   485     protected:

   486       std::vector<T> container;

   488     public:

   489       typedef T ValueType;

   490       typedef Edge KeyType;

   492       EdgeMap(const ListGraph &_G) :

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

   494       {

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

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

   497 	G->dyn_edge_maps.push_back(this);

   498       }

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

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

   501       {

   502 	G->dyn_edge_maps.push_back(this);

   503       }

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

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

   506       {

   507  	G->dyn_edge_maps.push_back(this);

   508       }

   510       template<typename TT> friend class EdgeMap;

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

   513       ///

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

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

   516       {

   517 	G->dyn_edge_maps.push_back(this);

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

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

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

   521 	    i++)

   522 	  container.push_back(*i);

   523       }

   524       ~EdgeMap()

   525       {

   526 	if(G) {

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

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

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

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

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

   532 	  if(*i==this) {

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

   534 	    G->dyn_edge_maps.pop_back();

   535 	  }

   536 	}

   537       }

   539       void add(const Edge k)

   540       {

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

   542       }

   543       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   554       ///cause serious problem.

   555       ///\todo Is this really so?

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

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

   558       {

   559 	container = m.container;

   560 	return *this;

   561       }

   562       template<typename TT>

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

   564       {

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

   566 	return *this;

   567       }

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

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

   571     };

   573   };

   575   ///Graph for bidirectional edges.

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

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

   579   ///of oppositely directed edges.

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

   581   ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"

   582   ///that complements this

   583   ///feature by

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

   585   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   586   ///can be used

   587   ///as well.

   588   ///

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

   590   ///using \ref opposite.

   591   ///

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

   593   ///

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

   595   ///should be implemented independently from ListGraph.

   597   class SymListGraph : public ListGraph

   598   {

   599   public:

   600     template<typename T> class SymEdgeMap;

   601     template<typename T> friend class SymEdgeMap;

   603     SymListGraph() : ListGraph() { }

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

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

   606     Edge addEdge(Node u, Node v)

   607     {

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

   609       ListGraph::addEdge(v,u);

   610       return e;

   611     }

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

   614     ///The oppositely directed edge.

   616     ///Returns the oppositely directed

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

   618     Edge opposite(Edge e) const

   619     {

   620       Edge f;

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

   622       return f;

   623     }

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

   626     void erase(Edge e) {

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

   628       ListGraph::erase(e);

   629     }

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

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

   634     ///directed pairs of edges.

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

   636     {

   637       std::vector<T> container;

   639     public:

   640       typedef T ValueType;

   641       typedef Edge KeyType;

   643       SymEdgeMap(const SymListGraph &_G) :

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

   645       {

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

   647       }

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

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

   650       {

   651 	G->dyn_edge_maps.push_back(this);

   652       }

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

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

   656       {

   657  	G->dyn_node_maps.push_back(this);

   658       }

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

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

   663       ///

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

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

   667       {

   668 	G->dyn_node_maps.push_back(this);

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

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

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

   672 	    i++)

   673 	  container.push_back(*i);

   674       }

   676       ~SymEdgeMap()

   677       {

   678 	if(G) {

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

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

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

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

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

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

   685 	  if(*i==this) {

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

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

   688 	  }

   689 	}

   690       }

   692       void add(const Edge k)

   693       {

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

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

   696       }

   697       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   708       ///cause serious problem.

   709       ///\todo Is this really so?

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

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

   712       {

   713 	container = m.container;

   714 	return *this;

   715       }

   716       template<typename TT>

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

   718       {

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

   720 	return *this;

   721       }

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

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

   726     };

   728   };

   731   ///A graph class containing only nodes.

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

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

   735   ///\ref EdgeSet class.

   736   ///

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

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

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

   740   ///always \ref INVALID.

   741   ///\sa \ref GraphSkeleton

   742   ///\sa \ref EdgeSet

   743   class NodeSet {

   745     //Nodes are double linked.

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

   747     struct NodeT

   748     {

   749       int first_in,first_out;

   750       int prev, next;

   751       //      NodeT() {}

   752     };

   754     std::vector<NodeT> nodes;

   755     //The first node

   756     int first_node;

   757     //The first free node

   758     int first_free_node;

   760   protected:

   762     template <typename Key> class DynMapBase

   763     {

   764     protected:

   765       const NodeSet* G;

   766     public:

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

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

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

   770       virtual ~DynMapBase() {}

   771       friend class NodeSet;

   772     };

   774   public:

   775     template <typename T> class EdgeMap;

   776     template <typename T> class NodeMap;

   778     class Node;

   779     class Edge;

   781     //  protected:

   782     // HELPME:

   783   protected:

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

   785     ///

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

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

   789   public:

   791     class NodeIt;

   792     class EdgeIt;

   793     class OutEdgeIt;

   794     class InEdgeIt;

   796     template <typename T> class NodeMap;

   797     template <typename T> class EdgeMap;

   799   public:

   801     ///Default constructor

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

   803 		  first_free_node(-1) {}

   804     ///Copy constructor

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

   806 				     first_free_node(_g.first_free_node) {}

   808     ~NodeSet()

   809     {

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

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

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

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

   814     }

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

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

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

   820     ///its name would suggests...

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

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

   823     ///its name would suggests...

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

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

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

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

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

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

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

   835     NodeIt& first(NodeIt& v) const {

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

   837     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   844 //     template< typename It >

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

   847 //     template< typename It >

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

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

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

   853     void setInvalid(Edge &e) { }

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

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

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

   859     NodeIt& next(NodeIt& it) const {

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

   861       return it;

   862     }

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

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

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

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

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

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

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

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

   874     Node addNode() {

   875       int n;

   877       if(first_free_node==-1)

   878 	{

   879 	  n = nodes.size();

   880 	  nodes.push_back(NodeT());

   881 	}

   882       else {

   883 	n = first_free_node;

   884 	first_free_node = nodes[n].next;

   885       }

   887       nodes[n].next = first_node;

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

   889       first_node = n;

   890       nodes[n].prev = -1;

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

   894       Node nn; nn.n=n;

   896       //Update dynamic maps

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

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

   900       return nn;

   901     }

   903     void erase(Node nn) {

   904       int n=nn.n;

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

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

   908       else first_node = nodes[n].next;

   910       nodes[n].next = first_free_node;

   911       first_free_node = n;

   913       //Update dynamic maps

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

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

   916     }

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

   919     ///

   920     void clear() {

   921       nodes.clear();

   922       first_node = first_free_node = -1;

   923     }

   925     class Node {

   926       friend class NodeSet;

   927       template <typename T> friend class NodeMap;

   929       friend class Edge;

   930       friend class OutEdgeIt;

   931       friend class InEdgeIt;

   933     protected:

   934       int n;

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

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

   937     public:

   938       Node() {}

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

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

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

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

   943     };

   945     class NodeIt : public Node {

   946       friend class NodeSet;

   947     public:

   948       NodeIt() : Node() { }

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

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

   951       ///\todo Undocumented conversion Node -\> NodeIt.

   952       NodeIt(const NodeSet& G, const Node &n) : Node(n) { }

   954     };

   956     class Edge {

   957       //friend class NodeSet;

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

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

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

   963       //      friend class Node;

   964       //      friend class NodeIt;

   965     protected:

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

   967       //      Edge(int nn) {}

   968     public:

   969       Edge() { }

   970       Edge (Invalid) { }

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

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

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

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

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

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

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

   978     };

   980     class EdgeIt : public Edge {

   981       //friend class NodeSet;

   982     public:

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

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

   985       EdgeIt() : Edge() { }

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

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

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

   989     };

   991     class OutEdgeIt : public Edge {

   992       friend class NodeSet;

   993     public:

   994       OutEdgeIt() : Edge() { }

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

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

   997     };

   999     class InEdgeIt : public Edge {

  1000       friend class NodeSet;

  1001     public:

  1002       InEdgeIt() : Edge() { }

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

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

  1005     };

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

  1008     {

  1009       std::vector<T> container;

  1011     public:

  1012       typedef T ValueType;

  1013       typedef Node KeyType;

  1015       NodeMap(const NodeSet &_G) :

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

  1017       {

  1018 	G->dyn_node_maps.push_back(this);

  1019       }

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

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

  1022       {

  1023 	G->dyn_node_maps.push_back(this);

  1024       }

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

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

  1028       {

  1029  	G->dyn_node_maps.push_back(this);

  1030       }

  1032       template<typename TT> friend class NodeMap;

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

  1035       ///

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

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

  1038       {

  1039 	G->dyn_node_maps.push_back(this);

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

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

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

  1043 	    i++)

  1044 	  container.push_back(*i);

  1045       }

  1046       ~NodeMap()

  1047       {

  1048 	if(G) {

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

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

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

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

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

  1054 	  if(*i==this) {

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

  1056 	    G->dyn_node_maps.pop_back();

  1057 	  }

  1058 	}

  1059       }

  1061       void add(const Node k)

  1062       {

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

  1064       }

  1066       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

  1078       ///cause serious problem.

  1079       ///\todo Is this really so?

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

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

  1082       {

  1083 	container = m.container;

  1084 	return *this;

  1085       }

  1086       template<typename TT>

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

  1088       {

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

  1090 	return *this;

  1091       }

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

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

  1095     };

  1097     template <typename T> class EdgeMap

  1098     {

  1099     public:

  1100       typedef T ValueType;

  1101       typedef Edge KeyType;

  1103       EdgeMap(const NodeSet &) { }

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

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

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

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

  1109       ///

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

  1111       ~EdgeMap() { }

  1113       void add(const Edge  ) { }

  1114       void erase(const Edge) { }

  1116       void set(Edge, T) { }

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

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

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

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

  1123       template<typename TT>

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

  1126       void update() {}

  1127       void update(T a) {}

  1128     };

  1129   };

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

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

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

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

  1138   /// each other.

  1139   ///

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

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

  1142   ///

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

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

  1145   ///

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

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

  1148   ///

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

  1150   ///the description of \ref GraphSkeleton.

  1151   ///\sa \ref GraphSkeleton.

  1152   ///\sa \ref NodeSet.

  1153   template<typename GG>

  1154   class EdgeSet {

  1156     typedef GG NodeGraphType;

  1158     NodeGraphType &G;

  1160   public:

  1161     class Node;

  1162     int id(Node v) const;

  1164     class Node : public NodeGraphType::Node {

  1165       friend class EdgeSet;

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

  1168       friend class Edge;

  1169       friend class OutEdgeIt;

  1170       friend class InEdgeIt;

  1171       friend class SymEdge;

  1173     public:

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

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

  1176     public:

  1177       Node() : NodeGraphType::Node() {}

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

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

  1180     };

  1182     class NodeIt : public NodeGraphType::NodeIt {

  1183       friend class EdgeSet;

  1184     public:

  1185       NodeIt() : NodeGraphType::NodeIt() { }

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

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

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

  1189 	: NodeGraphType::NodeIt(n) {}

  1190       ///\todo Undocumented conversion Node -\> NodeIt.

  1191       NodeIt(const EdgeSet& _G, const Node &n)

  1192 	: NodeGraphType::NodeIt(_G.G,n) { }

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

  1195     };

  1197   private:

  1198     //Edges are double linked.

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

  1200     struct NodeT

  1201     {

  1202       int first_in,first_out;

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

  1204     };

  1206     struct EdgeT

  1207     {

  1208       Node head, tail;

  1209       int prev_in, prev_out;

  1210       int next_in, next_out;

  1211     };

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

  1216     std::vector<EdgeT> edges;

  1217     //The first free edge

  1218     int first_free_edge;

  1220   protected:

  1222     template <typename Key> class DynMapBase

  1223     {

  1224     protected:

  1225       const EdgeSet* G;

  1226     public:

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

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

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

  1230       virtual ~DynMapBase() {}

  1231       friend class EdgeSet;

  1232     };

  1234   public:

  1235     //template <typename T> class NodeMap;

  1236     template <typename T> class EdgeMap;

  1238     class Node;

  1239     class Edge;

  1241     //  protected:

  1242     // HELPME:

  1243   protected:

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

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

  1246     ///

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

  1249   public:

  1251     class NodeIt;

  1252     class EdgeIt;

  1253     class OutEdgeIt;

  1254     class InEdgeIt;

  1256     template <typename T> class NodeMap;

  1257     template <typename T> class EdgeMap;

  1259   public:

  1261     ///Constructor

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

  1264     ///\param _G the base graph.

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

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

  1267 				 nodes(_G), edges(),

  1268 				 first_free_edge(-1) { }

  1269     ///Copy constructor

  1271     ///Makes a copy of an EdgeSet.

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

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

  1274 				 first_free_edge(_g.first_free_edge) { }

  1276     ~EdgeSet()

  1277     {

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

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

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

  1281 	    i=dyn_edge_maps.begin();

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

  1283     }

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

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

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

  1289     ///its name would suggests...

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

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

  1292     ///its name would suggests...

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

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

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

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

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

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

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

  1304     NodeIt& first(NodeIt& v) const {

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

  1306     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

  1313 //     template< typename It >

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

  1316 //     template< typename It >

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

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

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

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

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

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

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

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

  1329     OutEdgeIt& next(OutEdgeIt& it) const

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

  1331     InEdgeIt& next(InEdgeIt& it) const

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

  1333     EdgeIt& next(EdgeIt& it) const {

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

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

  1336       }

  1337       else {

  1338 	NodeIt n(*this,edges[it.n].head);

  1339 	for(n=next(n);

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

  1341 	    next(n)) ;

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

  1343       }

  1344       return it;

  1345     }

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

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

  1350     Node addNode() { return G.addNode(); }

  1352     Edge addEdge(Node u, Node v) {

  1353       int n;

  1355       if(first_free_edge==-1)

  1356 	{

  1357 	  n = edges.size();

  1358 	  edges.push_back(EdgeT());

  1359 	}

  1360       else {

  1361 	n = first_free_edge;

  1362 	first_free_edge = edges[n].next_in;

  1363       }

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

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

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

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

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

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

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

  1375       Edge e; e.n=n;

  1377       //Update dynamic maps

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

  1379 	    i=dyn_edge_maps.begin();

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

  1382       return e;

  1383     }

  1385   private:

  1386     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

  1400       edges[n].next_in = first_free_edge;

  1401       first_free_edge = -1;

  1403       //Update dynamic maps

  1404       Edge e; e.n=n;

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

  1406 	    i=dyn_edge_maps.begin();

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

  1408     }

  1410   public:

  1412 //     void erase(Node nn) {

  1413 //       int n=nn.n;

  1414 //       int m;

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

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

  1417 //     }

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

  1421     ///Clear all edges. (Doesn't clear the nodes!)

  1422     void clear() {

  1423       edges.clear();

  1424       first_free_edge=-1;

  1425     }

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

  1429 //     //

  1430 //     void clear() {

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

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

  1433 //     }

  1435   public:

  1436     template <typename T> class EdgeMap;

  1438     ///

  1439     class Edge {

  1440     public:

  1441       friend class EdgeSet;

  1442       template <typename T> friend class EdgeMap;

  1444       friend class Node;

  1445       friend class NodeIt;

  1446     public:

  1447       ///\bug It shoud be at least protected

  1448       ///

  1449       int n;

  1450     protected:

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

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

  1454     public:

  1455       Edge() { }

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

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

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

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

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

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

  1462       int &idref() {return n;}

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

  1464     };

  1466     class EdgeIt : public Edge {

  1467       friend class EdgeSet;

  1468       template <typename T> friend class EdgeMap;

  1471     public:

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

  1473 	//      	typename NodeGraphType::Node m;

  1474         NodeIt m;

  1475 	for(G.first(m);

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

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

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

  1479       }

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

  1481       EdgeIt() : Edge() { }

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

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

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

  1485     };

  1487     class OutEdgeIt : public Edge {

  1488       friend class EdgeSet;

  1489     public:

  1490       OutEdgeIt() : Edge() { }

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

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

  1494     };

  1496     class InEdgeIt : public Edge {

  1497       friend class EdgeSet;

  1498     public:

  1499       InEdgeIt() : Edge() { }

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

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

  1502     };

  1504     template <typename T> class NodeMap :

  1505       public NodeGraphType::template NodeMap<T>

  1506     {

  1507       //This is a must, the constructors need it.

  1508       typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;

  1509     public:

  1510       NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }

  1511       NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }

  1512       //It is unnecessary

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

  1514 	ParentNodeMap(m) { }

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

  1517       ///

  1518       template<typename TT>

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

  1520 	: ParentNodeMap(m) { }

  1521     };

  1523     ///

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

  1525     {

  1526     protected:

  1527     public:

  1528       ///\bug It should be at least protected

  1529       ///

  1530       std::vector<T> container;

  1532     public:

  1533       typedef T ValueType;

  1534       typedef Edge KeyType;

  1536       EdgeMap(const EdgeSet &_G) :

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

  1538       {

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

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

  1541 	G->dyn_edge_maps.push_back(this);

  1542       }

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

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

  1545       {

  1546 	G->dyn_edge_maps.push_back(this);

  1547       }

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

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

  1550       {

  1551  	G->dyn_edge_maps.push_back(this);

  1552       }

  1554       template<typename TT> friend class EdgeMap;

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

  1557       ///

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

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

  1560       {

  1561 	G->dyn_edge_maps.push_back(this);

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

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

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

  1565 	    i++)

  1566 	  container.push_back(*i);

  1567       }

  1568       ~EdgeMap()

  1569       {

  1570 	if(G) {

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

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

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

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

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

  1576 	  if(*i==this) {

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

  1578 	    G->dyn_edge_maps.pop_back();

  1579 	  }

  1580 	}

  1581       }

  1583       void add(const Edge k)

  1584       {

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

  1586       }

  1587       void erase(const Edge) { }

  1589       ///\bug This doesn't work. Why?

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

  1591       void set(Edge n, T a) { container[G->id(n)]=a; }

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

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

  1594       ///\bug This doesn't work. Why?

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

  1596       operator[](Edge n) { return container[G->id(n)]; }

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

  1598       ///\bug This doesn't work. Why?

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

  1600       operator[](Edge n) const { return container[G->id(n)]; }

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

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

  1604       ///cause serious problem.

  1605       ///\todo Is this really so?

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

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

  1608       {

  1609 	container = m.container;

  1610 	return *this;

  1611       }

  1613       template<typename TT> friend class EdgeMap;

  1615       template<typename TT>

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

  1617       {

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

  1619 	return *this;

  1620       }

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

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

  1624     };

  1626   };

  1628   template<typename GG>

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

  1631 /// @}

  1633 } //namespace hugo

  1635 #endif //HUGO_LIST_GRAPH_H

author	marci
	Wed, 12 May 2004 13:19:32 +0000
changeset 621	2db02d4a9e6e
parent 579	859f8c7e2a40
child 681	06a3cba90f94
permissions	-rw-r--r--