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

     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     ///Set the expected number of edges

   119     ///With this function, it is possible to set the expected number of edges.

   120     ///The use of this fasten the building of the graph and makes

   121     ///it possible to avoid the superfluous memory allocation.

   122     void reserveEdge(int n) { edges.reserve(n); };

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

   125     ///its name would suggests...

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

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

   128     ///its name would suggests...

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

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

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

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

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

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

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

   140     NodeIt& first(NodeIt& v) const {

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

   142     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   149 //     template< typename It >

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

   152 //     template< typename It >

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

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

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

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

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

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

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

   164     NodeIt& next(NodeIt& it) const {

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

   166       return it;

   167     }

   168     OutEdgeIt& next(OutEdgeIt& it) const

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

   170     InEdgeIt& next(InEdgeIt& it) const

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

   172     EdgeIt& next(EdgeIt& it) const {

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

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

   175       }

   176       else {

   177 	int n;

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

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

   180 	    n = nodes[n].next) ;

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

   182       }

   183       return it;

   184     }

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

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

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

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

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

   193     Node addNode() {

   194       int n;

   196       if(first_free_node==-1)

   197 	{

   198 	  n = nodes.size();

   199 	  nodes.push_back(NodeT());

   200 	}

   201       else {

   202 	n = first_free_node;

   203 	first_free_node = nodes[n].next;

   204       }

   206       nodes[n].next = first_node;

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

   208       first_node = n;

   209       nodes[n].prev = -1;

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

   213       Node nn; nn.n=n;

   215       //Update dynamic maps

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

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

   219       return nn;

   220     }

   222     Edge addEdge(Node u, Node v) {

   223       int n;

   225       if(first_free_edge==-1)

   226 	{

   227 	  n = edges.size();

   228 	  edges.push_back(EdgeT());

   229 	}

   230       else {

   231 	n = first_free_edge;

   232 	first_free_edge = edges[n].next_in;

   233       }

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

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

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

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

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

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

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

   245       Edge e; e.n=n;

   247       //Update dynamic maps

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

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

   251       return e;

   252     }

   254   private:

   255     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

   269       edges[n].next_in = first_free_edge;

   270       first_free_edge = n;

   272       //Update dynamic maps

   273       Edge e; e.n=n;

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

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

   276     }

   278   public:

   280     void erase(Node nn) {

   281       int n=nn.n;

   283       int m;

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

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

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

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

   289       else first_node = nodes[n].next;

   291       nodes[n].next = first_free_node;

   292       first_free_node = n;

   294       //Update dynamic maps

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

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

   297     }

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

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

   302     ///

   303     void clear() {

   304       nodes.clear();edges.clear();

   305       first_node=first_free_node=first_free_edge=-1;

   306     }

   308     class Node {

   309       friend class ListGraph;

   310       template <typename T> friend class NodeMap;

   312       friend class Edge;

   313       friend class OutEdgeIt;

   314       friend class InEdgeIt;

   315       friend class SymEdge;

   317     protected:

   318       int n;

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

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

   321     public:

   322       Node() {}

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

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

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

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

   327     };

   329     class NodeIt : public Node {

   330       friend class ListGraph;

   331     public:

   332       NodeIt() : Node() { }

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

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

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

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

   337     };

   339     class Edge {

   340       friend class ListGraph;

   341       template <typename T> friend class EdgeMap;

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

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

   346       friend class Node;

   347       friend class NodeIt;

   348     protected:

   349       int n;

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

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

   353     public:

   354       Edge() { }

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

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

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

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

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

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

   361       int &idref() {return n;}

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

   363     };

   365     class EdgeIt : public Edge {

   366       friend class ListGraph;

   367     public:

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

   369       	int m;

   370 	for(m=G.first_node;

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

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

   373       }

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

   375       EdgeIt() : Edge() { }

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

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

   378       int &idref() {return n;}

   379     };

   381     class OutEdgeIt : public Edge {

   382       friend class ListGraph;

   383     public:

   384       OutEdgeIt() : Edge() { }

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

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

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

   389     };

   391     class InEdgeIt : public Edge {

   392       friend class ListGraph;

   393     public:

   394       InEdgeIt() : Edge() { }

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

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

   397     };

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

   400     {

   401       std::vector<T> container;

   403     public:

   404       typedef T ValueType;

   405       typedef Node KeyType;

   407       NodeMap(const ListGraph &_G) :

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

   409       {

   410 	G->dyn_node_maps.push_back(this);

   411       }

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

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

   414       {

   415 	G->dyn_node_maps.push_back(this);

   416       }

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

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

   420       {

   421  	G->dyn_node_maps.push_back(this);

   422       }

   424       template<typename TT> friend class NodeMap;

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

   427       ///

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

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

   431       {

   432 	G->dyn_node_maps.push_back(this);

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

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

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

   436 	    i++)

   437 	  container.push_back(*i);

   438       }

   439       ~NodeMap()

   440       {

   441 	if(G) {

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

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

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

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

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

   447 	  if(*i==this) {

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

   449 	    G->dyn_node_maps.pop_back();

   450 	  }

   451 	}

   452       }

   454       void add(const Node k)

   455       {

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

   457       }

   459       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   471       ///cause serious problem.

   472       ///\todo Is this really so?

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

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

   475       {

   476 	container = m.container;

   477 	return *this;

   478       }

   479       template<typename TT>

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

   481       {

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

   483 	return *this;

   484       }

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

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

   488     };

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

   491     {

   492     protected:

   493       std::vector<T> container;

   495     public:

   496       typedef T ValueType;

   497       typedef Edge KeyType;

   499       EdgeMap(const ListGraph &_G) :

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

   501       {

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

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

   504 	G->dyn_edge_maps.push_back(this);

   505       }

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

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

   508       {

   509 	G->dyn_edge_maps.push_back(this);

   510       }

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

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

   513       {

   514  	G->dyn_edge_maps.push_back(this);

   515       }

   517       template<typename TT> friend class EdgeMap;

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

   520       ///

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

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

   523       {

   524 	G->dyn_edge_maps.push_back(this);

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

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

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

   528 	    i++)

   529 	  container.push_back(*i);

   530       }

   531       ~EdgeMap()

   532       {

   533 	if(G) {

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

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

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

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

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

   539 	  if(*i==this) {

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

   541 	    G->dyn_edge_maps.pop_back();

   542 	  }

   543 	}

   544       }

   546       void add(const Edge k)

   547       {

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

   549       }

   550       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   561       ///cause serious problem.

   562       ///\todo Is this really so?

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

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

   565       {

   566 	container = m.container;

   567 	return *this;

   568       }

   569       template<typename TT>

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

   571       {

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

   573 	return *this;

   574       }

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

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

   578     };

   580   };

   582   ///Graph for bidirectional edges.

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

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

   586   ///of oppositely directed edges.

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

   588   ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"

   589   ///that complements this

   590   ///feature by

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

   592   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   593   ///can be used

   594   ///as well.

   595   ///

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

   597   ///using \ref opposite.

   598   ///

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

   600   ///

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

   602   ///should be implemented independently from ListGraph.

   604   class SymListGraph : public ListGraph

   605   {

   606   public:

   607     template<typename T> class SymEdgeMap;

   608     template<typename T> friend class SymEdgeMap;

   610     SymListGraph() : ListGraph() { }

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

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

   613     Edge addEdge(Node u, Node v)

   614     {

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

   616       ListGraph::addEdge(v,u);

   617       return e;

   618     }

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

   621     ///The oppositely directed edge.

   623     ///Returns the oppositely directed

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

   625     Edge opposite(Edge e) const

   626     {

   627       Edge f;

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

   629       return f;

   630     }

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

   633     void erase(Edge e) {

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

   635       ListGraph::erase(e);

   636     }

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

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

   641     ///directed pairs of edges.

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

   643     {

   644       std::vector<T> container;

   646     public:

   647       typedef T ValueType;

   648       typedef Edge KeyType;

   650       SymEdgeMap(const SymListGraph &_G) :

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

   652       {

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

   654       }

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

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

   657       {

   658 	G->dyn_edge_maps.push_back(this);

   659       }

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

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

   663       {

   664  	G->dyn_node_maps.push_back(this);

   665       }

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

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

   670       ///

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

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

   674       {

   675 	G->dyn_node_maps.push_back(this);

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

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

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

   679 	    i++)

   680 	  container.push_back(*i);

   681       }

   683       ~SymEdgeMap()

   684       {

   685 	if(G) {

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

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

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

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

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

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

   692 	  if(*i==this) {

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

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

   695 	  }

   696 	}

   697       }

   699       void add(const Edge k)

   700       {

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

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

   703       }

   704       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   715       ///cause serious problem.

   716       ///\todo Is this really so?

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

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

   719       {

   720 	container = m.container;

   721 	return *this;

   722       }

   723       template<typename TT>

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

   725       {

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

   727 	return *this;

   728       }

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

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

   733     };

   735   };

   738   ///A graph class containing only nodes.

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

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

   742   ///\ref EdgeSet class.

   743   ///

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

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

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

   747   ///always \ref INVALID.

   748   ///\sa \ref GraphSkeleton

   749   ///\sa \ref EdgeSet

   750   class NodeSet {

   752     //Nodes are double linked.

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

   754     struct NodeT

   755     {

   756       int first_in,first_out;

   757       int prev, next;

   758       //      NodeT() {}

   759     };

   761     std::vector<NodeT> nodes;

   762     //The first node

   763     int first_node;

   764     //The first free node

   765     int first_free_node;

   767   protected:

   769     template <typename Key> class DynMapBase

   770     {

   771     protected:

   772       const NodeSet* G;

   773     public:

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

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

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

   777       virtual ~DynMapBase() {}

   778       friend class NodeSet;

   779     };

   781   public:

   782     template <typename T> class EdgeMap;

   783     template <typename T> class NodeMap;

   785     class Node;

   786     class Edge;

   788     //  protected:

   789     // HELPME:

   790   protected:

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

   792     ///

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

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

   796   public:

   798     class NodeIt;

   799     class EdgeIt;

   800     class OutEdgeIt;

   801     class InEdgeIt;

   803     template <typename T> class NodeMap;

   804     template <typename T> class EdgeMap;

   806   public:

   808     ///Default constructor

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

   810 		  first_free_node(-1) {}

   811     ///Copy constructor

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

   813 				     first_free_node(_g.first_free_node) {}

   815     ~NodeSet()

   816     {

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

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

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

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

   821     }

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

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

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

   827     ///its name would suggests...

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

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

   830     ///its name would suggests...

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

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

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

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

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

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

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

   842     NodeIt& first(NodeIt& v) const {

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

   844     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   851 //     template< typename It >

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

   854 //     template< typename It >

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

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

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

   860     void setInvalid(Edge &e) { }

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

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

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

   866     NodeIt& next(NodeIt& it) const {

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

   868       return it;

   869     }

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

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

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

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

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

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

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

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

   881     Node addNode() {

   882       int n;

   884       if(first_free_node==-1)

   885 	{

   886 	  n = nodes.size();

   887 	  nodes.push_back(NodeT());

   888 	}

   889       else {

   890 	n = first_free_node;

   891 	first_free_node = nodes[n].next;

   892       }

   894       nodes[n].next = first_node;

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

   896       first_node = n;

   897       nodes[n].prev = -1;

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

   901       Node nn; nn.n=n;

   903       //Update dynamic maps

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

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

   907       return nn;

   908     }

   910     void erase(Node nn) {

   911       int n=nn.n;

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

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

   915       else first_node = nodes[n].next;

   917       nodes[n].next = first_free_node;

   918       first_free_node = n;

   920       //Update dynamic maps

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

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

   923     }

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

   926     ///

   927     void clear() {

   928       nodes.clear();

   929       first_node = first_free_node = -1;

   930     }

   932     class Node {

   933       friend class NodeSet;

   934       template <typename T> friend class NodeMap;

   936       friend class Edge;

   937       friend class OutEdgeIt;

   938       friend class InEdgeIt;

   940     protected:

   941       int n;

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

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

   944     public:

   945       Node() {}

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

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

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

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

   950     };

   952     class NodeIt : public Node {

   953       friend class NodeSet;

   954     public:

   955       NodeIt() : Node() { }

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

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

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

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

   961     };

   963     class Edge {

   964       //friend class NodeSet;

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

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

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

   970       //      friend class Node;

   971       //      friend class NodeIt;

   972     protected:

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

   974       //      Edge(int nn) {}

   975     public:

   976       Edge() { }

   977       Edge (Invalid) { }

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

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

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

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

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

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

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

   985     };

   987     class EdgeIt : public Edge {

   988       //friend class NodeSet;

   989     public:

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

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

   992       EdgeIt() : Edge() { }

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

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

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

   996     };

   998     class OutEdgeIt : public Edge {

   999       friend class NodeSet;

  1000     public:

  1001       OutEdgeIt() : Edge() { }

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

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

  1004     };

  1006     class InEdgeIt : public Edge {

  1007       friend class NodeSet;

  1008     public:

  1009       InEdgeIt() : Edge() { }

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

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

  1012     };

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

  1015     {

  1016       std::vector<T> container;

  1018     public:

  1019       typedef T ValueType;

  1020       typedef Node KeyType;

  1022       NodeMap(const NodeSet &_G) :

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

  1024       {

  1025 	G->dyn_node_maps.push_back(this);

  1026       }

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

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

  1029       {

  1030 	G->dyn_node_maps.push_back(this);

  1031       }

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

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

  1035       {

  1036  	G->dyn_node_maps.push_back(this);

  1037       }

  1039       template<typename TT> friend class NodeMap;

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

  1042       ///

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

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

  1045       {

  1046 	G->dyn_node_maps.push_back(this);

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

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

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

  1050 	    i++)

  1051 	  container.push_back(*i);

  1052       }

  1053       ~NodeMap()

  1054       {

  1055 	if(G) {

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

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

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

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

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

  1061 	  if(*i==this) {

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

  1063 	    G->dyn_node_maps.pop_back();

  1064 	  }

  1065 	}

  1066       }

  1068       void add(const Node k)

  1069       {

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

  1071       }

  1073       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

  1085       ///cause serious problem.

  1086       ///\todo Is this really so?

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

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

  1089       {

  1090 	container = m.container;

  1091 	return *this;

  1092       }

  1093       template<typename TT>

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

  1095       {

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

  1097 	return *this;

  1098       }

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

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

  1102     };

  1104     template <typename T> class EdgeMap

  1105     {

  1106     public:

  1107       typedef T ValueType;

  1108       typedef Edge KeyType;

  1110       EdgeMap(const NodeSet &) { }

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

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

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

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

  1116       ///

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

  1118       ~EdgeMap() { }

  1120       void add(const Edge  ) { }

  1121       void erase(const Edge) { }

  1123       void set(Edge, T) { }

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

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

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

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

  1130       template<typename TT>

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

  1133       void update() {}

  1134       void update(T a) {}

  1135     };

  1136   };

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

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

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

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

  1145   /// each other.

  1146   ///

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

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

  1149   ///

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

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

  1152   ///

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

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

  1155   ///

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

  1157   ///the description of \ref GraphSkeleton.

  1158   ///\sa \ref GraphSkeleton.

  1159   ///\sa \ref NodeSet.

  1160   template<typename GG>

  1161   class EdgeSet {

  1163     typedef GG NodeGraphType;

  1165     NodeGraphType &G;

  1167   public:

  1168     class Node;

  1169     int id(Node v) const;

  1171     class Node : public NodeGraphType::Node {

  1172       friend class EdgeSet;

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

  1175       friend class Edge;

  1176       friend class OutEdgeIt;

  1177       friend class InEdgeIt;

  1178       friend class SymEdge;

  1180     public:

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

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

  1183     public:

  1184       Node() : NodeGraphType::Node() {}

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

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

  1187     };

  1189     class NodeIt : public NodeGraphType::NodeIt {

  1190       friend class EdgeSet;

  1191     public:

  1192       NodeIt() : NodeGraphType::NodeIt() { }

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

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

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

  1196 	: NodeGraphType::NodeIt(n) {}

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

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

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

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

  1202     };

  1204   private:

  1205     //Edges are double linked.

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

  1207     struct NodeT

  1208     {

  1209       int first_in,first_out;

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

  1211     };

  1213     struct EdgeT

  1214     {

  1215       Node head, tail;

  1216       int prev_in, prev_out;

  1217       int next_in, next_out;

  1218     };

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

  1223     std::vector<EdgeT> edges;

  1224     //The first free edge

  1225     int first_free_edge;

  1227   protected:

  1229     template <typename Key> class DynMapBase

  1230     {

  1231     protected:

  1232       const EdgeSet* G;

  1233     public:

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

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

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

  1237       virtual ~DynMapBase() {}

  1238       friend class EdgeSet;

  1239     };

  1241   public:

  1242     //template <typename T> class NodeMap;

  1243     template <typename T> class EdgeMap;

  1245     class Node;

  1246     class Edge;

  1248     //  protected:

  1249     // HELPME:

  1250   protected:

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

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

  1253     ///

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

  1256   public:

  1258     class NodeIt;

  1259     class EdgeIt;

  1260     class OutEdgeIt;

  1261     class InEdgeIt;

  1263     template <typename T> class NodeMap;

  1264     template <typename T> class EdgeMap;

  1266   public:

  1268     ///Constructor

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

  1271     ///\param _G the base graph.

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

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

  1274 				 nodes(_G), edges(),

  1275 				 first_free_edge(-1) { }

  1276     ///Copy constructor

  1278     ///Makes a copy of an EdgeSet.

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

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

  1281 				 first_free_edge(_g.first_free_edge) { }

  1283     ~EdgeSet()

  1284     {

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

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

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

  1288 	    i=dyn_edge_maps.begin();

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

  1290     }

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

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

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

  1296     ///its name would suggests...

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

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

  1299     ///its name would suggests...

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

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

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

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

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

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

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

  1311     NodeIt& first(NodeIt& v) const {

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

  1313     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

  1320 //     template< typename It >

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

  1323 //     template< typename It >

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

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

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

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

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

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

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

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

  1336     OutEdgeIt& next(OutEdgeIt& it) const

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

  1338     InEdgeIt& next(InEdgeIt& it) const

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

  1340     EdgeIt& next(EdgeIt& it) const {

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

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

  1343       }

  1344       else {

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

  1346 	for(n=next(n);

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

  1348 	    next(n)) ;

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

  1350       }

  1351       return it;

  1352     }

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

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

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

  1359     Edge addEdge(Node u, Node v) {

  1360       int n;

  1362       if(first_free_edge==-1)

  1363 	{

  1364 	  n = edges.size();

  1365 	  edges.push_back(EdgeT());

  1366 	}

  1367       else {

  1368 	n = first_free_edge;

  1369 	first_free_edge = edges[n].next_in;

  1370       }

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

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

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

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

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

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

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

  1382       Edge e; e.n=n;

  1384       //Update dynamic maps

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

  1386 	    i=dyn_edge_maps.begin();

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

  1389       return e;

  1390     }

  1392   private:

  1393     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

  1407       edges[n].next_in = first_free_edge;

  1408       first_free_edge = -1;

  1410       //Update dynamic maps

  1411       Edge e; e.n=n;

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

  1413 	    i=dyn_edge_maps.begin();

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

  1415     }

  1417   public:

  1419 //     void erase(Node nn) {

  1420 //       int n=nn.n;

  1421 //       int m;

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

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

  1424 //     }

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

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

  1429     void clear() {

  1430       edges.clear();

  1431       first_free_edge=-1;

  1432     }

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

  1436 //     //

  1437 //     void clear() {

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

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

  1440 //     }

  1442   public:

  1443     template <typename T> class EdgeMap;

  1445     ///

  1446     class Edge {

  1447     public:

  1448       friend class EdgeSet;

  1449       template <typename T> friend class EdgeMap;

  1451       friend class Node;

  1452       friend class NodeIt;

  1453     public:

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

  1455       ///

  1456       int n;

  1457     protected:

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

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

  1461     public:

  1462       Edge() { }

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

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

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

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

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

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

  1469       int &idref() {return n;}

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

  1471     };

  1473     class EdgeIt : public Edge {

  1474       friend class EdgeSet;

  1475       template <typename T> friend class EdgeMap;

  1478     public:

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

  1480 	//      	typename NodeGraphType::Node m;

  1481         NodeIt m;

  1482 	for(G.first(m);

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

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

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

  1486       }

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

  1488       EdgeIt() : Edge() { }

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

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

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

  1492     };

  1494     class OutEdgeIt : public Edge {

  1495       friend class EdgeSet;

  1496     public:

  1497       OutEdgeIt() : Edge() { }

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

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

  1501     };

  1503     class InEdgeIt : public Edge {

  1504       friend class EdgeSet;

  1505     public:

  1506       InEdgeIt() : Edge() { }

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

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

  1509     };

  1511     template <typename T> class NodeMap :

  1512       public NodeGraphType::template NodeMap<T>

  1513     {

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

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

  1516     public:

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

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

  1519       //It is unnecessary

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

  1521 	ParentNodeMap(m) { }

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

  1524       ///

  1525       template<typename TT>

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

  1527 	: ParentNodeMap(m) { }

  1528     };

  1530     ///

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

  1532     {

  1533     protected:

  1534     public:

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

  1536       ///

  1537       std::vector<T> container;

  1539     public:

  1540       typedef T ValueType;

  1541       typedef Edge KeyType;

  1543       EdgeMap(const EdgeSet &_G) :

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

  1545       {

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

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

  1548 	G->dyn_edge_maps.push_back(this);

  1549       }

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

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

  1552       {

  1553 	G->dyn_edge_maps.push_back(this);

  1554       }

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

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

  1557       {

  1558  	G->dyn_edge_maps.push_back(this);

  1559       }

  1561       template<typename TT> friend class EdgeMap;

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

  1564       ///

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

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

  1567       {

  1568 	G->dyn_edge_maps.push_back(this);

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

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

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

  1572 	    i++)

  1573 	  container.push_back(*i);

  1574       }

  1575       ~EdgeMap()

  1576       {

  1577 	if(G) {

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

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

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

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

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

  1583 	  if(*i==this) {

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

  1585 	    G->dyn_edge_maps.pop_back();

  1586 	  }

  1587 	}

  1588       }

  1590       void add(const Edge k)

  1591       {

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

  1593       }

  1594       void erase(const Edge) { }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1611       ///cause serious problem.

  1612       ///\todo Is this really so?

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

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

  1615       {

  1616 	container = m.container;

  1617 	return *this;

  1618       }

  1620       template<typename TT> friend class EdgeMap;

  1622       template<typename TT>

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

  1624       {

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

  1626 	return *this;

  1627       }

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

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

  1631     };

  1633   };

  1635   template<typename GG>

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

  1638 /// @}

  1640 } //namespace hugo

  1642 #endif //HUGO_LIST_GRAPH_H

author	alpar
	Tue, 06 Jul 2004 11:27:36 +0000
changeset 695	887c551fb0aa
parent 681	06a3cba90f94
child 705	9d9557b56eb7
permissions	-rw-r--r--