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

     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     static bool valid(Edge e) { return e.n!=-1; }

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

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

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

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

   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     static int id(Node v) { return v.n; }

   187     static int id(Edge e) { 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);

   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);

   352     public:

   353       /// An Edge with id \c n.

   355       /// \bug It should be

   356       /// obtained by a member function of the Graph.

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

   359       Edge() { }

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

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

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

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

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

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

   366       int &idref() {return n;}

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

   368     };

   370     class EdgeIt : public Edge {

   371       friend class ListGraph;

   372     public:

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

   374       	int m;

   375 	for(m=G.first_node;

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

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

   378       }

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

   380       EdgeIt() : Edge() { }

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

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

   383       int &idref() {return n;}

   384     };

   386     class OutEdgeIt : public Edge {

   387       friend class ListGraph;

   388     public:

   389       OutEdgeIt() : Edge() { }

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

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

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

   394     };

   396     class InEdgeIt : public Edge {

   397       friend class ListGraph;

   398     public:

   399       InEdgeIt() : Edge() { }

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

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

   402     };

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

   405     {

   406       std::vector<T> container;

   408     public:

   409       typedef T ValueType;

   410       typedef Node KeyType;

   412       NodeMap(const ListGraph &_G) :

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

   414       {

   415 	G->dyn_node_maps.push_back(this);

   416       }

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

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

   419       {

   420 	G->dyn_node_maps.push_back(this);

   421       }

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

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

   425       {

   426  	G->dyn_node_maps.push_back(this);

   427       }

   429       template<typename TT> friend class NodeMap;

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

   432       ///

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

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

   436       {

   437 	G->dyn_node_maps.push_back(this);

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

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

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

   441 	    i++)

   442 	  container.push_back(*i);

   443       }

   444       ~NodeMap()

   445       {

   446 	if(G) {

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

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

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

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

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

   452 	  if(*i==this) {

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

   454 	    G->dyn_node_maps.pop_back();

   455 	  }

   456 	}

   457       }

   459       void add(const Node k)

   460       {

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

   462       }

   464       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   476       ///cause serious problem.

   477       ///\todo Is this really so?

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

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

   480       {

   481 	container = m.container;

   482 	return *this;

   483       }

   484       template<typename TT>

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

   486       {

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

   488 	return *this;

   489       }

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

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

   493     };

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

   496     {

   497     protected:

   498       std::vector<T> container;

   500     public:

   501       typedef T ValueType;

   502       typedef Edge KeyType;

   504       EdgeMap(const ListGraph &_G) :

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

   506       {

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

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

   509 	G->dyn_edge_maps.push_back(this);

   510       }

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

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

   513       {

   514 	G->dyn_edge_maps.push_back(this);

   515       }

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

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

   518       {

   519  	G->dyn_edge_maps.push_back(this);

   520       }

   522       template<typename TT> friend class EdgeMap;

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

   525       ///

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

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

   528       {

   529 	G->dyn_edge_maps.push_back(this);

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

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

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

   533 	    i++)

   534 	  container.push_back(*i);

   535       }

   536       ~EdgeMap()

   537       {

   538 	if(G) {

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

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

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

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

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

   544 	  if(*i==this) {

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

   546 	    G->dyn_edge_maps.pop_back();

   547 	  }

   548 	}

   549       }

   551       void add(const Edge k)

   552       {

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

   554       }

   555       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   566       ///cause serious problem.

   567       ///\todo Is this really so?

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

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

   570       {

   571 	container = m.container;

   572 	return *this;

   573       }

   574       template<typename TT>

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

   576       {

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

   578 	return *this;

   579       }

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

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

   583     };

   585   };

   587   ///Graph for bidirectional edges.

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

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

   591   ///of oppositely directed edges.

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

   593   ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"

   594   ///that complements this

   595   ///feature by

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

   597   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   598   ///can be used

   599   ///as well.

   600   ///

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

   602   ///using \ref opposite.

   603   ///

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

   605   ///

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

   607   ///should be implemented independently from ListGraph.

   609   class SymListGraph : public ListGraph

   610   {

   611   public:

   612     template<typename T> class SymEdgeMap;

   613     template<typename T> friend class SymEdgeMap;

   615     SymListGraph() : ListGraph() { }

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

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

   618     Edge addEdge(Node u, Node v)

   619     {

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

   621       ListGraph::addEdge(v,u);

   622       return e;

   623     }

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

   626     ///The oppositely directed edge.

   628     ///Returns the oppositely directed

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

   630     static Edge opposite(Edge e)

   631     {

   632       Edge f;

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

   634       return f;

   635     }

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

   638     void erase(Edge e) {

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

   640       ListGraph::erase(e);

   641     }

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

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

   646     ///directed pairs of edges.

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

   648     {

   649       std::vector<T> container;

   651     public:

   652       typedef T ValueType;

   653       typedef Edge KeyType;

   655       SymEdgeMap(const SymListGraph &_G) :

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

   657       {

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

   659       }

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

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

   662       {

   663 	G->dyn_edge_maps.push_back(this);

   664       }

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

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

   668       {

   669  	G->dyn_node_maps.push_back(this);

   670       }

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

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

   675       ///

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

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

   679       {

   680 	G->dyn_node_maps.push_back(this);

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

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

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

   684 	    i++)

   685 	  container.push_back(*i);

   686       }

   688       ~SymEdgeMap()

   689       {

   690 	if(G) {

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

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

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

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

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

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

   697 	  if(*i==this) {

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

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

   700 	  }

   701 	}

   702       }

   704       void add(const Edge k)

   705       {

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

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

   708       }

   709       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   720       ///cause serious problem.

   721       ///\todo Is this really so?

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

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

   724       {

   725 	container = m.container;

   726 	return *this;

   727       }

   728       template<typename TT>

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

   730       {

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

   732 	return *this;

   733       }

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

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

   738     };

   740   };

   743   ///A graph class containing only nodes.

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

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

   747   ///\ref EdgeSet class.

   748   ///

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

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

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

   752   ///always \ref INVALID.

   753   ///\sa \ref GraphSkeleton

   754   ///\sa \ref EdgeSet

   755   class NodeSet {

   757     //Nodes are double linked.

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

   759     struct NodeT

   760     {

   761       int first_in,first_out;

   762       int prev, next;

   763       //      NodeT() {}

   764     };

   766     std::vector<NodeT> nodes;

   767     //The first node

   768     int first_node;

   769     //The first free node

   770     int first_free_node;

   772   protected:

   774     template <typename Key> class DynMapBase

   775     {

   776     protected:

   777       const NodeSet* G;

   778     public:

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

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

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

   782       virtual ~DynMapBase() {}

   783       friend class NodeSet;

   784     };

   786   public:

   787     template <typename T> class EdgeMap;

   788     template <typename T> class NodeMap;

   790     class Node;

   791     class Edge;

   793     //  protected:

   794     // HELPME:

   795   protected:

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

   797     ///

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

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

   801   public:

   803     class NodeIt;

   804     class EdgeIt;

   805     class OutEdgeIt;

   806     class InEdgeIt;

   808     template <typename T> class NodeMap;

   809     template <typename T> class EdgeMap;

   811   public:

   813     ///Default constructor

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

   815 		  first_free_node(-1) {}

   816     ///Copy constructor

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

   818 				     first_free_node(_g.first_free_node) {}

   820     ~NodeSet()

   821     {

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

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

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

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

   826     }

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

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

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

   832     ///its name would suggests...

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

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

   835     ///its name would suggests...

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

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

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

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

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

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

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

   847     NodeIt& first(NodeIt& v) const {

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

   849     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   856 //     template< typename It >

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

   859 //     template< typename It >

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

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

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

   865     void setInvalid(Edge &e) { }

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

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

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

   871     NodeIt& next(NodeIt& it) const {

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

   873       return it;

   874     }

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

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

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

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

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

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

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

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

   886     Node addNode() {

   887       int n;

   889       if(first_free_node==-1)

   890 	{

   891 	  n = nodes.size();

   892 	  nodes.push_back(NodeT());

   893 	}

   894       else {

   895 	n = first_free_node;

   896 	first_free_node = nodes[n].next;

   897       }

   899       nodes[n].next = first_node;

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

   901       first_node = n;

   902       nodes[n].prev = -1;

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

   906       Node nn; nn.n=n;

   908       //Update dynamic maps

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

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

   912       return nn;

   913     }

   915     void erase(Node nn) {

   916       int n=nn.n;

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

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

   920       else first_node = nodes[n].next;

   922       nodes[n].next = first_free_node;

   923       first_free_node = n;

   925       //Update dynamic maps

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

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

   928     }

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

   931     ///

   932     void clear() {

   933       nodes.clear();

   934       first_node = first_free_node = -1;

   935     }

   937     class Node {

   938       friend class NodeSet;

   939       template <typename T> friend class NodeMap;

   941       friend class Edge;

   942       friend class OutEdgeIt;

   943       friend class InEdgeIt;

   945     protected:

   946       int n;

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

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

   949     public:

   950       Node() {}

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

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

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

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

   955     };

   957     class NodeIt : public Node {

   958       friend class NodeSet;

   959     public:

   960       NodeIt() : Node() { }

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

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

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

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

   966     };

   968     class Edge {

   969       //friend class NodeSet;

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

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

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

   975       //      friend class Node;

   976       //      friend class NodeIt;

   977     protected:

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

   979       //      Edge(int nn) {}

   980     public:

   981       Edge() { }

   982       Edge (Invalid) { }

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

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

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

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

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

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

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

   990     };

   992     class EdgeIt : public Edge {

   993       //friend class NodeSet;

   994     public:

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

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

   997       EdgeIt() : Edge() { }

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

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

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

  1001     };

  1003     class OutEdgeIt : public Edge {

  1004       friend class NodeSet;

  1005     public:

  1006       OutEdgeIt() : Edge() { }

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

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

  1009     };

  1011     class InEdgeIt : public Edge {

  1012       friend class NodeSet;

  1013     public:

  1014       InEdgeIt() : Edge() { }

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

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

  1017     };

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

  1020     {

  1021       std::vector<T> container;

  1023     public:

  1024       typedef T ValueType;

  1025       typedef Node KeyType;

  1027       NodeMap(const NodeSet &_G) :

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

  1029       {

  1030 	G->dyn_node_maps.push_back(this);

  1031       }

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

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

  1034       {

  1035 	G->dyn_node_maps.push_back(this);

  1036       }

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

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

  1040       {

  1041  	G->dyn_node_maps.push_back(this);

  1042       }

  1044       template<typename TT> friend class NodeMap;

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

  1047       ///

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

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

  1050       {

  1051 	G->dyn_node_maps.push_back(this);

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

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

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

  1055 	    i++)

  1056 	  container.push_back(*i);

  1057       }

  1058       ~NodeMap()

  1059       {

  1060 	if(G) {

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

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

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

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

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

  1066 	  if(*i==this) {

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

  1068 	    G->dyn_node_maps.pop_back();

  1069 	  }

  1070 	}

  1071       }

  1073       void add(const Node k)

  1074       {

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

  1076       }

  1078       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

  1090       ///cause serious problem.

  1091       ///\todo Is this really so?

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

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

  1094       {

  1095 	container = m.container;

  1096 	return *this;

  1097       }

  1098       template<typename TT>

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

  1100       {

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

  1102 	return *this;

  1103       }

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

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

  1107     };

  1109     template <typename T> class EdgeMap

  1110     {

  1111     public:

  1112       typedef T ValueType;

  1113       typedef Edge KeyType;

  1115       EdgeMap(const NodeSet &) { }

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

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

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

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

  1121       ///

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

  1123       ~EdgeMap() { }

  1125       void add(const Edge  ) { }

  1126       void erase(const Edge) { }

  1128       void set(Edge, T) { }

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

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

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

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

  1135       template<typename TT>

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

  1138       void update() {}

  1139       void update(T a) {}

  1140     };

  1141   };

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

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

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

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

  1150   /// each other.

  1151   ///

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

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

  1154   ///

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

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

  1157   ///

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

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

  1160   ///

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

  1162   ///the description of \ref GraphSkeleton.

  1163   ///\sa \ref GraphSkeleton.

  1164   ///\sa \ref NodeSet.

  1165   template<typename GG>

  1166   class EdgeSet {

  1168     typedef GG NodeGraphType;

  1170     NodeGraphType &G;

  1172   public:

  1173     class Node;

  1174     class Edge;

  1175     class OutEdgeIt;

  1176     class InEdgeIt;

  1177     class SymEdge;

  1178     int id(Node v) const;

  1180     class Node : public NodeGraphType::Node {

  1181       friend class EdgeSet;

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

  1184       friend class Edge;

  1185       friend class OutEdgeIt;

  1186       friend class InEdgeIt;

  1187       friend class SymEdge;

  1189     public:

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

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

  1192     public:

  1193       Node() : NodeGraphType::Node() {}

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

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

  1196     };

  1198     class NodeIt : public NodeGraphType::NodeIt {

  1199       friend class EdgeSet;

  1200     public:

  1201       NodeIt() : NodeGraphType::NodeIt() { }

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

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

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

  1205 	: NodeGraphType::NodeIt(n) {}

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

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

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

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

  1211     };

  1213   private:

  1214     //Edges are double linked.

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

  1216     struct NodeT

  1217     {

  1218       int first_in,first_out;

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

  1220     };

  1222     struct EdgeT

  1223     {

  1224       Node head, tail;

  1225       int prev_in, prev_out;

  1226       int next_in, next_out;

  1227     };

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

  1232     std::vector<EdgeT> edges;

  1233     //The first free edge

  1234     int first_free_edge;

  1236   protected:

  1238     template <typename Key> class DynMapBase

  1239     {

  1240     protected:

  1241       const EdgeSet* G;

  1242     public:

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

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

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

  1246       virtual ~DynMapBase() {}

  1247       friend class EdgeSet;

  1248     };

  1250   public:

  1251     //template <typename T> class NodeMap;

  1252     template <typename T> class EdgeMap;

  1254     class Node;

  1255     class Edge;

  1257     //  protected:

  1258     // HELPME:

  1259   protected:

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

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

  1262     ///

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

  1265   public:

  1267     class NodeIt;

  1268     class EdgeIt;

  1269     class OutEdgeIt;

  1270     class InEdgeIt;

  1272     template <typename T> class NodeMap;

  1273     template <typename T> class EdgeMap;

  1275   public:

  1277     ///Constructor

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

  1280     ///\param _G the base graph.

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

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

  1283 				 nodes(_G), edges(),

  1284 				 first_free_edge(-1) { }

  1285     ///Copy constructor

  1287     ///Makes a copy of an EdgeSet.

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

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

  1290 				 first_free_edge(_g.first_free_edge) { }

  1292     ~EdgeSet()

  1293     {

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

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

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

  1297 	    i=dyn_edge_maps.begin();

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

  1299     }

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

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

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

  1305     ///its name would suggests...

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

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

  1308     ///its name would suggests...

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

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

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

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

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

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

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

  1320     NodeIt& first(NodeIt& v) const {

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

  1322     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

  1329 //     template< typename It >

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

  1332 //     template< typename It >

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

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

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

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

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

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

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

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

  1345     OutEdgeIt& next(OutEdgeIt& it) const

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

  1347     InEdgeIt& next(InEdgeIt& it) const

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

  1349     EdgeIt& next(EdgeIt& it) const {

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

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

  1352       }

  1353       else {

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

  1355 	for(n=next(n);

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

  1357 	    next(n)) ;

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

  1359       }

  1360       return it;

  1361     }

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

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

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

  1368     Edge addEdge(Node u, Node v) {

  1369       int n;

  1371       if(first_free_edge==-1)

  1372 	{

  1373 	  n = edges.size();

  1374 	  edges.push_back(EdgeT());

  1375 	}

  1376       else {

  1377 	n = first_free_edge;

  1378 	first_free_edge = edges[n].next_in;

  1379       }

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

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

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

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

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

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

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

  1391       Edge e; e.n=n;

  1393       //Update dynamic maps

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

  1395 	    i=dyn_edge_maps.begin();

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

  1398       return e;

  1399     }

  1401   private:

  1402     void eraseEdge(int n) {

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

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

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

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

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

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

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

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

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

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

  1416       edges[n].next_in = first_free_edge;

  1417       first_free_edge = -1;

  1419       //Update dynamic maps

  1420       Edge e; e.n=n;

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

  1422 	    i=dyn_edge_maps.begin();

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

  1424     }

  1426   public:

  1428 //     void erase(Node nn) {

  1429 //       int n=nn.n;

  1430 //       int m;

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

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

  1433 //     }

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

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

  1438     void clear() {

  1439       edges.clear();

  1440       first_free_edge=-1;

  1441     }

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

  1445 //     //

  1446 //     void clear() {

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

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

  1449 //     }

  1451   public:

  1452     template <typename T> class EdgeMap;

  1454     ///

  1455     class Edge {

  1456     public:

  1457       friend class EdgeSet;

  1458       template <typename T> friend class EdgeMap;

  1460       friend class Node;

  1461       friend class NodeIt;

  1462     public:

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

  1464       ///

  1465       int n;

  1466     protected:

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

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

  1470     public:

  1471       Edge() { }

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

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

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

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

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

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

  1478       int &idref() {return n;}

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

  1480     };

  1482     class EdgeIt : public Edge {

  1483       friend class EdgeSet;

  1484       template <typename T> friend class EdgeMap;

  1487     public:

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

  1489 	//      	typename NodeGraphType::Node m;

  1490         NodeIt m;

  1491 	for(G.first(m);

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

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

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

  1495       }

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

  1497       EdgeIt() : Edge() { }

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

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

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

  1501     };

  1503     class OutEdgeIt : public Edge {

  1504       friend class EdgeSet;

  1505     public:

  1506       OutEdgeIt() : Edge() { }

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

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

  1510     };

  1512     class InEdgeIt : public Edge {

  1513       friend class EdgeSet;

  1514     public:

  1515       InEdgeIt() : Edge() { }

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

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

  1518     };

  1520     template <typename T> class NodeMap :

  1521       public NodeGraphType::template NodeMap<T>

  1522     {

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

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

  1525     public:

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

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

  1528       //It is unnecessary

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

  1530 	ParentNodeMap(m) { }

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

  1533       ///

  1534       template<typename TT>

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

  1536 	: ParentNodeMap(m) { }

  1537     };

  1539     ///

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

  1541     {

  1542     protected:

  1543     public:

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

  1545       ///

  1546       std::vector<T> container;

  1548     public:

  1549       typedef T ValueType;

  1550       typedef Edge KeyType;

  1552       EdgeMap(const EdgeSet &_G) :

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

  1554       {

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

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

  1557 	G->dyn_edge_maps.push_back(this);

  1558       }

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

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

  1561       {

  1562 	G->dyn_edge_maps.push_back(this);

  1563       }

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

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

  1566       {

  1567  	G->dyn_edge_maps.push_back(this);

  1568       }

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

  1571       ///

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

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

  1574       {

  1575 	G->dyn_edge_maps.push_back(this);

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

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

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

  1579 	    i++)

  1580 	  container.push_back(*i);

  1581       }

  1582       ~EdgeMap()

  1583       {

  1584 	if(G) {

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

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

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

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

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

  1590 	  if(*i==this) {

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

  1592 	    G->dyn_edge_maps.pop_back();

  1593 	  }

  1594 	}

  1595       }

  1597       void add(const Edge k)

  1598       {

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

  1600       }

  1601       void erase(const Edge) { }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1618       ///cause serious problem.

  1619       ///\todo Is this really so?

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

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

  1622       {

  1623 	container = m.container;

  1624 	return *this;

  1625       }

  1627       template<typename TT> friend class EdgeMap;

  1629       template<typename TT>

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

  1631       {

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

  1633 	return *this;

  1634       }

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

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

  1638     };

  1640   };

  1642   template<typename GG>

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

  1645 /// @}

  1647 } //namespace hugo

  1649 #endif //HUGO_LIST_GRAPH_H

author	alpar
	Wed, 04 Aug 2004 18:55:24 +0000
changeset 753	f5382a084c07
parent 713	57c0b110b31e
child 774	4297098d9677
permissions	-rw-r--r--