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

     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)

   423       {

   424 	G->dyn_node_maps.push_back(this);

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

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

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

   428 	    i++)

   429 	  container.push_back(*i);

   430       }

   431       ~NodeMap()

   432       {

   433 	if(G) {

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

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

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

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

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

   439 	  if(*i==this) {

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

   441 	    G->dyn_node_maps.pop_back();

   442 	  }

   443 	}

   444       }

   446       void add(const Node k)

   447       {

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

   449       }

   451       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   463       ///cause serious problem.

   464       ///\todo Is this really so?

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

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

   467       {

   468 	container = m.container;

   469 	return *this;

   470       }

   471       template<typename TT>

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

   473       {

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

   475 	return *this;

   476       }

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

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

   480     };

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

   483     {

   484     protected:

   485       std::vector<T> container;

   487     public:

   488       typedef T ValueType;

   489       typedef Edge KeyType;

   491       EdgeMap(const ListGraph &_G) :

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

   493       {

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

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

   496 	G->dyn_edge_maps.push_back(this);

   497       }

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

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

   500       {

   501 	G->dyn_edge_maps.push_back(this);

   502       }

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

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

   505       {

   506  	G->dyn_edge_maps.push_back(this);

   507       }

   509       template<typename TT> friend class EdgeMap;

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

   512       ///

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

   514 	DynMapBase<Edge>(*m.G)

   515       {

   516 	G->dyn_edge_maps.push_back(this);

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

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

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

   520 	    i++)

   521 	  container.push_back(*i);

   522       }

   523       ~EdgeMap()

   524       {

   525 	if(G) {

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

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

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

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

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

   531 	  if(*i==this) {

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

   533 	    G->dyn_edge_maps.pop_back();

   534 	  }

   535 	}

   536       }

   538       void add(const Edge k)

   539       {

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

   541       }

   542       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   553       ///cause serious problem.

   554       ///\todo Is this really so?

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

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

   557       {

   558 	container = m.container;

   559 	return *this;

   560       }

   561       template<typename TT>

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

   563       {

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

   565 	return *this;

   566       }

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

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

   570     };

   572   };

   574   ///Graph for bidirectional edges.

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

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

   578   ///of oppositely directed edges.

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

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

   581   ///that complements this

   582   ///feature by

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

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

   585   ///can be used

   586   ///as well.

   587   ///

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

   589   ///using \ref opposite.

   590   ///

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

   592   ///

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

   594   ///should be implemented independently from ListGraph.

   596   class SymListGraph : public ListGraph

   597   {

   598   public:

   599     template<typename T> class SymEdgeMap;

   600     template<typename T> friend class SymEdgeMap;

   602     SymListGraph() : ListGraph() { }

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

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

   605     Edge addEdge(Node u, Node v)

   606     {

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

   608       ListGraph::addEdge(v,u);

   609       return e;

   610     }

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

   613     ///The oppositely directed edge.

   615     ///Returns the oppositely directed

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

   617     Edge opposite(Edge e) const

   618     {

   619       Edge f;

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

   621       return f;

   622     }

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

   625     void erase(Edge e) {

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

   627       ListGraph::erase(e);

   628     }

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

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

   633     ///directed pairs of edges.

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

   635     {

   636       std::vector<T> container;

   638     public:

   639       typedef T ValueType;

   640       typedef Edge KeyType;

   642       SymEdgeMap(const SymListGraph &_G) :

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

   644       {

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

   646       }

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

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

   649       {

   650 	G->dyn_edge_maps.push_back(this);

   651       }

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

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

   655       {

   656  	G->dyn_node_maps.push_back(this);

   657       }

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

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

   662       ///

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

   665 	DynMapBase<SymEdge>(*m.G)

   666       {

   667 	G->dyn_node_maps.push_back(this);

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

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

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

   671 	    i++)

   672 	  container.push_back(*i);

   673       }

   675       ~SymEdgeMap()

   676       {

   677 	if(G) {

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

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

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

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

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

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

   684 	  if(*i==this) {

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

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

   687 	  }

   688 	}

   689       }

   691       void add(const Edge k)

   692       {

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

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

   695       }

   696       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   707       ///cause serious problem.

   708       ///\todo Is this really so?

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

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

   711       {

   712 	container = m.container;

   713 	return *this;

   714       }

   715       template<typename TT>

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

   717       {

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

   719 	return *this;

   720       }

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

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

   725     };

   727   };

   730   ///A graph class containing only nodes.

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

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

   734   ///\ref EdgeSet class.

   735   ///

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

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

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

   739   ///always \ref INVALID.

   740   ///\sa \ref GraphSkeleton

   741   ///\sa \ref EdgeSet

   742   class NodeSet {

   744     //Nodes are double linked.

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

   746     struct NodeT

   747     {

   748       int first_in,first_out;

   749       int prev, next;

   750       //      NodeT() {}

   751     };

   753     std::vector<NodeT> nodes;

   754     //The first node

   755     int first_node;

   756     //The first free node

   757     int first_free_node;

   759   protected:

   761     template <typename Key> class DynMapBase

   762     {

   763     protected:

   764       const NodeSet* G;

   765     public:

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

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

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

   769       virtual ~DynMapBase() {}

   770       friend class NodeSet;

   771     };

   773   public:

   774     template <typename T> class EdgeMap;

   775     template <typename T> class NodeMap;

   777     class Node;

   778     class Edge;

   780     //  protected:

   781     // HELPME:

   782   protected:

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

   784     ///

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

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

   788   public:

   790     class NodeIt;

   791     class EdgeIt;

   792     class OutEdgeIt;

   793     class InEdgeIt;

   795     template <typename T> class NodeMap;

   796     template <typename T> class EdgeMap;

   798   public:

   800     ///Default constructor

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

   802 		  first_free_node(-1) {}

   803     ///Copy constructor

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

   805 				     first_free_node(_g.first_free_node) {}

   807     ~NodeSet()

   808     {

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

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

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

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

   813     }

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

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

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

   819     ///its name would suggests...

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

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

   822     ///its name would suggests...

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

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

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

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

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

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

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

   834     NodeIt& first(NodeIt& v) const {

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

   836     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   843 //     template< typename It >

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

   846 //     template< typename It >

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

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

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

   852     void setInvalid(Edge &e) { }

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

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

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

   858     NodeIt& next(NodeIt& it) const {

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

   860       return it;

   861     }

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

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

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

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

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

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

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

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

   873     Node addNode() {

   874       int n;

   876       if(first_free_node==-1)

   877 	{

   878 	  n = nodes.size();

   879 	  nodes.push_back(NodeT());

   880 	}

   881       else {

   882 	n = first_free_node;

   883 	first_free_node = nodes[n].next;

   884       }

   886       nodes[n].next = first_node;

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

   888       first_node = n;

   889       nodes[n].prev = -1;

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

   893       Node nn; nn.n=n;

   895       //Update dynamic maps

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

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

   899       return nn;

   900     }

   902     void erase(Node nn) {

   903       int n=nn.n;

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

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

   907       else first_node = nodes[n].next;

   909       nodes[n].next = first_free_node;

   910       first_free_node = n;

   912       //Update dynamic maps

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

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

   915     }

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

   918     ///

   919     void clear() {

   920       nodes.clear();

   921       first_node = first_free_node = -1;

   922     }

   924     class Node {

   925       friend class NodeSet;

   926       template <typename T> friend class NodeMap;

   928       friend class Edge;

   929       friend class OutEdgeIt;

   930       friend class InEdgeIt;

   932     protected:

   933       int n;

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

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

   936     public:

   937       Node() {}

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

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

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

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

   942     };

   944     class NodeIt : public Node {

   945       friend class NodeSet;

   946     public:

   947       NodeIt() : Node() { }

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

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

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

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

   953     };

   955     class Edge {

   956       //friend class NodeSet;

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

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

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

   962       //      friend class Node;

   963       //      friend class NodeIt;

   964     protected:

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

   966       //      Edge(int nn) {}

   967     public:

   968       Edge() { }

   969       Edge (Invalid) { }

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

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

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

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

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

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

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

   977     };

   979     class EdgeIt : public Edge {

   980       //friend class NodeSet;

   981     public:

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

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

   984       EdgeIt() : Edge() { }

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

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

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

   988     };

   990     class OutEdgeIt : public Edge {

   991       friend class NodeSet;

   992     public:

   993       OutEdgeIt() : Edge() { }

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

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

   996     };

   998     class InEdgeIt : public Edge {

   999       friend class NodeSet;

  1000     public:

  1001       InEdgeIt() : Edge() { }

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

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

  1004     };

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

  1007     {

  1008       std::vector<T> container;

  1010     public:

  1011       typedef T ValueType;

  1012       typedef Node KeyType;

  1014       NodeMap(const NodeSet &_G) :

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

  1016       {

  1017 	G->dyn_node_maps.push_back(this);

  1018       }

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

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

  1021       {

  1022 	G->dyn_node_maps.push_back(this);

  1023       }

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

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

  1027       {

  1028  	G->dyn_node_maps.push_back(this);

  1029       }

  1031       template<typename TT> friend class NodeMap;

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

  1034       ///

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

  1036 	DynMapBase<Node>(*m.G)

  1037       {

  1038 	G->dyn_node_maps.push_back(this);

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

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

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

  1042 	    i++)

  1043 	  container.push_back(*i);

  1044       }

  1045       ~NodeMap()

  1046       {

  1047 	if(G) {

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

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

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

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

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

  1053 	  if(*i==this) {

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

  1055 	    G->dyn_node_maps.pop_back();

  1056 	  }

  1057 	}

  1058       }

  1060       void add(const Node k)

  1061       {

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

  1063       }

  1065       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

  1077       ///cause serious problem.

  1078       ///\todo Is this really so?

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

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

  1081       {

  1082 	container = m.container;

  1083 	return *this;

  1084       }

  1085       template<typename TT>

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

  1087       {

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

  1089 	return *this;

  1090       }

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

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

  1094     };

  1096     template <typename T> class EdgeMap

  1097     {

  1098     public:

  1099       typedef T ValueType;

  1100       typedef Edge KeyType;

  1102       EdgeMap(const NodeSet &) { }

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

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

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

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

  1108       ///

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

  1110       ~EdgeMap() { }

  1112       void add(const Edge  ) { }

  1113       void erase(const Edge) { }

  1115       void set(Edge, T) { }

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

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

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

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

  1122       template<typename TT>

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

  1125       void update() {}

  1126       void update(T a) {}

  1127     };

  1128   };

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

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

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

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

  1137   /// each other.

  1138   ///

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

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

  1141   ///

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

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

  1144   ///

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

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

  1147   ///

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

  1149   ///the description of \ref GraphSkeleton.

  1150   ///\sa \ref GraphSkeleton.

  1151   ///\sa \ref NodeSet.

  1152   template<typename GG>

  1153   class EdgeSet {

  1155     typedef GG NodeGraphType;

  1157     NodeGraphType &G;

  1159   public:

  1160     class Node;

  1161     int id(Node v) const;

  1163     class Node : public NodeGraphType::Node {

  1164       friend class EdgeSet;

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

  1167       friend class Edge;

  1168       friend class OutEdgeIt;

  1169       friend class InEdgeIt;

  1170       friend class SymEdge;

  1172     public:

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

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

  1175     public:

  1176       Node() : NodeGraphType::Node() {}

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

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

  1179     };

  1181     class NodeIt : public NodeGraphType::NodeIt {

  1182       friend class EdgeSet;

  1183     public:

  1184       NodeIt() : NodeGraphType::NodeIt() { }

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

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

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

  1188 	: NodeGraphType::NodeIt(n) {}

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

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

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

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

  1194     };

  1196   private:

  1197     //Edges are double linked.

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

  1199     struct NodeT

  1200     {

  1201       int first_in,first_out;

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

  1203     };

  1205     struct EdgeT

  1206     {

  1207       Node head, tail;

  1208       int prev_in, prev_out;

  1209       int next_in, next_out;

  1210     };

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

  1215     std::vector<EdgeT> edges;

  1216     //The first free edge

  1217     int first_free_edge;

  1219   protected:

  1221     template <typename Key> class DynMapBase

  1222     {

  1223     protected:

  1224       const EdgeSet* G;

  1225     public:

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

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

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

  1229       virtual ~DynMapBase() {}

  1230       friend class EdgeSet;

  1231     };

  1233   public:

  1234     //template <typename T> class NodeMap;

  1235     template <typename T> class EdgeMap;

  1237     class Node;

  1238     class Edge;

  1240     //  protected:

  1241     // HELPME:

  1242   protected:

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

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

  1245     ///

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

  1248   public:

  1250     class NodeIt;

  1251     class EdgeIt;

  1252     class OutEdgeIt;

  1253     class InEdgeIt;

  1255     template <typename T> class NodeMap;

  1256     template <typename T> class EdgeMap;

  1258   public:

  1260     ///Constructor

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

  1263     ///\param _G the base graph.

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

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

  1266 				 nodes(_G), edges(),

  1267 				 first_free_edge(-1) { }

  1268     ///Copy constructor

  1270     ///Makes a copy of an EdgeSet.

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

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

  1273 				 first_free_edge(_g.first_free_edge) { }

  1275     ~EdgeSet()

  1276     {

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

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

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

  1280 	    i=dyn_edge_maps.begin();

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

  1282     }

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

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

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

  1288     ///its name would suggests...

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

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

  1291     ///its name would suggests...

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

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

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

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

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

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

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

  1303     NodeIt& first(NodeIt& v) const {

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

  1305     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

  1312 //     template< typename It >

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

  1315 //     template< typename It >

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

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

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

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

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

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

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

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

  1328     OutEdgeIt& next(OutEdgeIt& it) const

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

  1330     InEdgeIt& next(InEdgeIt& it) const

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

  1332     EdgeIt& next(EdgeIt& it) const {

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

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

  1335       }

  1336       else {

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

  1338 	for(n=next(n);

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

  1340 	    next(n)) ;

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

  1342       }

  1343       return it;

  1344     }

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

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

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

  1351     Edge addEdge(Node u, Node v) {

  1352       int n;

  1354       if(first_free_edge==-1)

  1355 	{

  1356 	  n = edges.size();

  1357 	  edges.push_back(EdgeT());

  1358 	}

  1359       else {

  1360 	n = first_free_edge;

  1361 	first_free_edge = edges[n].next_in;

  1362       }

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

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

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

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

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

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

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

  1374       Edge e; e.n=n;

  1376       //Update dynamic maps

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

  1378 	    i=dyn_edge_maps.begin();

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

  1381       return e;

  1382     }

  1384   private:

  1385     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

  1399       edges[n].next_in = first_free_edge;

  1400       first_free_edge = -1;

  1402       //Update dynamic maps

  1403       Edge e; e.n=n;

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

  1405 	    i=dyn_edge_maps.begin();

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

  1407     }

  1409   public:

  1411 //     void erase(Node nn) {

  1412 //       int n=nn.n;

  1413 //       int m;

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

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

  1416 //     }

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

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

  1421     void clear() {

  1422       edges.clear();

  1423       first_free_edge=-1;

  1424     }

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

  1428 //     //

  1429 //     void clear() {

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

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

  1432 //     }

  1434   public:

  1435     template <typename T> class EdgeMap;

  1437     ///

  1438     class Edge {

  1439     public:

  1440       friend class EdgeSet;

  1441       template <typename T> friend class EdgeMap;

  1443       friend class Node;

  1444       friend class NodeIt;

  1445     public:

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

  1447       ///

  1448       int n;

  1449     protected:

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

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

  1453     public:

  1454       Edge() { }

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

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

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

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

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

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

  1461       int &idref() {return n;}

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

  1463     };

  1465     class EdgeIt : public Edge {

  1466       friend class EdgeSet;

  1467       template <typename T> friend class EdgeMap;

  1470     public:

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

  1472 	//      	typename NodeGraphType::Node m;

  1473         NodeIt m;

  1474 	for(G.first(m);

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

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

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

  1478       }

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

  1480       EdgeIt() : Edge() { }

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

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

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

  1484     };

  1486     class OutEdgeIt : public Edge {

  1487       friend class EdgeSet;

  1488     public:

  1489       OutEdgeIt() : Edge() { }

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

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

  1493     };

  1495     class InEdgeIt : public Edge {

  1496       friend class EdgeSet;

  1497     public:

  1498       InEdgeIt() : Edge() { }

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

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

  1501     };

  1503     template <typename T> class NodeMap :

  1504       public NodeGraphType::template NodeMap<T>

  1505     {

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

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

  1508     public:

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

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

  1511       //It is unnecessary

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

  1513 	ParentNodeMap(m) { }

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

  1516       ///

  1517       template<typename TT>

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

  1519 	: ParentNodeMap(m) { }

  1520     };

  1522     ///

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

  1524     {

  1525     protected:

  1526     public:

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

  1528       ///

  1529       std::vector<T> container;

  1531     public:

  1532       typedef T ValueType;

  1533       typedef Edge KeyType;

  1535       EdgeMap(const EdgeSet &_G) :

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

  1537       {

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

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

  1540 	G->dyn_edge_maps.push_back(this);

  1541       }

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

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

  1544       {

  1545 	G->dyn_edge_maps.push_back(this);

  1546       }

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

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

  1549       {

  1550  	G->dyn_edge_maps.push_back(this);

  1551       }

  1553       template<typename TT> friend class EdgeMap;

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

  1556       ///

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

  1558 	DynMapBase<Edge>(*m.G)

  1559       {

  1560 	G->dyn_edge_maps.push_back(this);

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

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

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

  1564 	    i++)

  1565 	  container.push_back(*i);

  1566       }

  1567       ~EdgeMap()

  1568       {

  1569 	if(G) {

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

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

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

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

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

  1575 	  if(*i==this) {

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

  1577 	    G->dyn_edge_maps.pop_back();

  1578 	  }

  1579 	}

  1580       }

  1582       void add(const Edge k)

  1583       {

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

  1585       }

  1586       void erase(const Edge) { }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1603       ///cause serious problem.

  1604       ///\todo Is this really so?

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

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

  1607       {

  1608 	container = m.container;

  1609 	return *this;

  1610       }

  1612       template<typename TT> friend class EdgeMap;

  1614       template<typename TT>

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

  1616       {

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

  1618 	return *this;

  1619       }

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

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

  1623     };

  1625   };

  1627   template<typename GG>

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

  1630 /// @}

  1632 } //namespace hugo

  1634 #endif //HUGO_LIST_GRAPH_H

author	alpar
	Fri, 07 May 2004 16:04:39 +0000
changeset 580	a00f9f1cfab8
parent 578	159f1cbf8a45
child 590	5c1465127b79
permissions	-rw-r--r--