COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 579:859f8c7e2a40

Last change on this file since 579:859f8c7e2a40 was 579:859f8c7e2a40, checked in by Alpar Juttner, 20 years ago

EdgeSet? is more or less working.

File size: 45.9 KB
RevLine 
[395]1// -*- mode:C++ -*-
2
[405]3#ifndef HUGO_LIST_GRAPH_H
4#define HUGO_LIST_GRAPH_H
[395]5
[491]6///\ingroup graphs
[395]7///\file
[405]8///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
[395]9
10#include <vector>
11#include <limits.h>
12
[542]13#include <hugo/invalid.h>
[395]14
15namespace hugo {
16
[406]17/// \addtogroup graphs
18/// @{
19
[397]20  class SymListGraph;
[395]21
[401]22  ///A list graph class.
[395]23
[397]24  ///This is a simple and fast erasable graph implementation.
25  ///
[395]26  ///It conforms to the graph interface documented under
27  ///the description of \ref GraphSkeleton.
28  ///\sa \ref GraphSkeleton.
[397]29  class ListGraph {
[395]30
[397]31    //Nodes are double linked.
32    //The free nodes are only single linked using the "next" field.
[395]33    struct NodeT
34    {
[397]35      int first_in,first_out;
36      int prev, next;
37      //      NodeT() {}
[395]38    };
[397]39    //Edges are double linked.
40    //The free edges are only single linked using the "next_in" field.
[395]41    struct EdgeT
42    {
[397]43      int head, tail;
44      int prev_in, prev_out;
45      int next_in, next_out;
[395]46      //FIXME: is this necessary?
[397]47      //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {} 
[395]48    };
49
50    std::vector<NodeT> nodes;
[397]51    //The first node
52    int first_node;
53    //The first free node
54    int first_free_node;
[395]55    std::vector<EdgeT> edges;
[397]56    //The first free edge
57    int first_free_edge;
[395]58   
[397]59  protected:
[395]60   
61    template <typename Key> class DynMapBase
62    {
63    protected:
[397]64      const ListGraph* G;
[395]65    public:
[515]66      virtual void add(const Key k) = 0;
67      virtual void erase(const Key k) = 0;
[397]68      DynMapBase(const ListGraph &_G) : G(&_G) {}
[395]69      virtual ~DynMapBase() {}
[397]70      friend class ListGraph;
[395]71    };
72   
73  public:
74    template <typename T> class EdgeMap;
[400]75    template <typename T> class NodeMap;
[397]76   
[395]77    class Node;
78    class Edge;
79
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;
89   
90  public:
91
92    class NodeIt;
93    class EdgeIt;
94    class OutEdgeIt;
95    class InEdgeIt;
96   
97  public:
98
[397]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) {}
[395]105   
[397]106    ~ListGraph()
[395]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    }
113
114    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
115    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
116
117    ///\bug This function does something different than
118    ///its name would suggests...
119    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
120    ///\bug This function does something different than
121    ///its name would suggests...
122    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
123
124    Node tail(Edge e) const { return edges[e.n].tail; }
125    Node head(Edge e) const { return edges[e.n].head; }
126
127    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
128    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
129
130    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
131    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
132
133    NodeIt& first(NodeIt& v) const {
134      v=NodeIt(*this); return v; }
135    EdgeIt& first(EdgeIt& e) const {
136      e=EdgeIt(*this); return e; }
137    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
138      e=OutEdgeIt(*this,v); return e; }
139    InEdgeIt& first(InEdgeIt& e, const Node v) const {
140      e=InEdgeIt(*this,v); return e; }
141
142//     template< typename It >
143//     It first() const { It e; first(e); return e; }
144
145//     template< typename It >
146//     It first(Node v) const { It e; first(e,v); return e; }
147
148    bool valid(Edge e) const { return e.n!=-1; }
149    bool valid(Node n) const { return n.n!=-1; }
150   
151    void setInvalid(Edge &e) { e.n=-1; }
152    void setInvalid(Node &n) { n.n=-1; }
153   
154    template <typename It> It getNext(It it) const
155    { It tmp(it); return next(tmp); }
156
157    NodeIt& next(NodeIt& it) const {
[397]158      it.n=nodes[it.n].next;
[395]159      return it;
160    }
161    OutEdgeIt& next(OutEdgeIt& it) const
162    { it.n=edges[it.n].next_out; return it; }
163    InEdgeIt& next(InEdgeIt& it) const
164    { it.n=edges[it.n].next_in; return it; }
[397]165    EdgeIt& next(EdgeIt& it) const {
166      if(edges[it.n].next_in!=-1) {
167        it.n=edges[it.n].next_in;
168      }
169      else {
170        int n;
171        for(n=nodes[edges[it.n].head].next;
172            n!=-1 && nodes[n].first_in == -1;
173            n = nodes[n].next) ;
174        it.n = (n==-1)?-1:nodes[n].first_in;
175      }
176      return it;
177    }
[395]178
179    int id(Node v) const { return v.n; }
180    int id(Edge e) const { return e.n; }
181
[397]182    /// Adds a new node to the graph.
183
184    /// \todo It adds the nodes in a reversed order.
185    /// (i.e. the lastly added node becomes the first.)
[395]186    Node addNode() {
[397]187      int n;
188     
189      if(first_free_node==-1)
190        {
191          n = nodes.size();
192          nodes.push_back(NodeT());
193        }
194      else {
195        n = first_free_node;
196        first_free_node = nodes[n].next;
197      }
198     
199      nodes[n].next = first_node;
200      if(first_node != -1) nodes[first_node].prev = n;
201      first_node = n;
202      nodes[n].prev = -1;
203     
204      nodes[n].first_in = nodes[n].first_out = -1;
205     
206      Node nn; nn.n=n;
[395]207
[397]208      //Update dynamic maps
[395]209      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
[397]210          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
[395]211
[397]212      return nn;
[395]213    }
214   
215    Edge addEdge(Node u, Node v) {
[397]216      int n;
217     
218      if(first_free_edge==-1)
219        {
220          n = edges.size();
221          edges.push_back(EdgeT());
222        }
223      else {
224        n = first_free_edge;
225        first_free_edge = edges[n].next_in;
226      }
227     
228      edges[n].tail = u.n; edges[n].head = v.n;
[395]229
[397]230      edges[n].next_out = nodes[u.n].first_out;
231      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
232      edges[n].next_in = nodes[v.n].first_in;
233      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
234      edges[n].prev_in = edges[n].prev_out = -1;
235       
236      nodes[u.n].first_out = nodes[v.n].first_in = n;
237
238      Edge e; e.n=n;
239
240      //Update dynamic maps
[395]241      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
242          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
243
244      return e;
245    }
246
[397]247  private:
248    void eraseEdge(int n) {
249     
250      if(edges[n].next_in!=-1)
251        edges[edges[n].next_in].prev_in = edges[n].prev_in;
252      if(edges[n].prev_in!=-1)
253        edges[edges[n].prev_in].next_in = edges[n].next_in;
254      else nodes[edges[n].head].first_in = edges[n].next_in;
255     
256      if(edges[n].next_out!=-1)
257        edges[edges[n].next_out].prev_out = edges[n].prev_out;
258      if(edges[n].prev_out!=-1)
259        edges[edges[n].prev_out].next_out = edges[n].next_out;
260      else nodes[edges[n].tail].first_out = edges[n].next_out;
261     
262      edges[n].next_in = first_free_edge;
263      first_free_edge = -1;     
264
265      //Update dynamic maps
266      Edge e; e.n=n;
267      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
268          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
269    }
270     
271  public:
272
273    void erase(Node nn) {
274      int n=nn.n;
275     
276      int m;
277      while((m=nodes[n].first_in)!=-1) eraseEdge(m);
278      while((m=nodes[n].first_out)!=-1) eraseEdge(m);
279
280      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
281      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
282      else first_node = nodes[n].next;
283     
284      nodes[n].next = first_free_node;
285      first_free_node = n;
286
287      //Update dynamic maps
288      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
289          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
290    }
291   
292    void erase(Edge e) { eraseEdge(e.n); }
293
294    ///\bug Dynamic maps must be updated!
295    ///
296    void clear() {
297      nodes.clear();edges.clear();
298      first_node=first_free_node=first_free_edge=-1;
299    }
[395]300
301    class Node {
[397]302      friend class ListGraph;
[395]303      template <typename T> friend class NodeMap;
[400]304       
[395]305      friend class Edge;
306      friend class OutEdgeIt;
307      friend class InEdgeIt;
308      friend class SymEdge;
309
310    protected:
311      int n;
[397]312      friend int ListGraph::id(Node v) const;
[395]313      Node(int nn) {n=nn;}
314    public:
315      Node() {}
[503]316      Node (Invalid) { n=-1; }
[395]317      bool operator==(const Node i) const {return n==i.n;}
318      bool operator!=(const Node i) const {return n!=i.n;}
319      bool operator<(const Node i) const {return n<i.n;}
320    };
321   
322    class NodeIt : public Node {
[397]323      friend class ListGraph;
[395]324    public:
[400]325      NodeIt() : Node() { }
326      NodeIt(Invalid i) : Node(i) { }
[397]327      NodeIt(const ListGraph& G) : Node(G.first_node) { }
[579]328      ///\todo Undocumented conversion Node -\> NodeIt.
329      NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
[395]330    };
331
332    class Edge {
[397]333      friend class ListGraph;
[395]334      template <typename T> friend class EdgeMap;
335
[397]336      //template <typename T> friend class SymListGraph::SymEdgeMap;     
337      //friend Edge SymListGraph::opposite(Edge) const;
[395]338     
339      friend class Node;
340      friend class NodeIt;
341    protected:
342      int n;
[397]343      friend int ListGraph::id(Edge e) const;
[395]344
345      Edge(int nn) {n=nn;}
346    public:
347      Edge() { }
348      Edge (Invalid) { n=-1; }
349      bool operator==(const Edge i) const {return n==i.n;}
350      bool operator!=(const Edge i) const {return n!=i.n;}
351      bool operator<(const Edge i) const {return n<i.n;}
352      ///\bug This is a workaround until somebody tells me how to
[397]353      ///make class \c SymListGraph::SymEdgeMap friend of Edge
[395]354      int &idref() {return n;}
355      const int &idref() const {return n;}
356    };
357   
358    class EdgeIt : public Edge {
[397]359      friend class ListGraph;
[395]360    public:
[397]361      EdgeIt(const ListGraph& G) : Edge() {
362        int m;
363        for(m=G.first_node;
364            m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
365        n = (m==-1)?-1:G.nodes[m].first_in;
366      }
[395]367      EdgeIt (Invalid i) : Edge(i) { }
368      EdgeIt() : Edge() { }
369      ///\bug This is a workaround until somebody tells me how to
[397]370      ///make class \c SymListGraph::SymEdgeMap friend of Edge
[395]371      int &idref() {return n;}
372    };
373   
374    class OutEdgeIt : public Edge {
[397]375      friend class ListGraph;
[395]376    public:
377      OutEdgeIt() : Edge() { }
378      OutEdgeIt (Invalid i) : Edge(i) { }
379
[397]380      OutEdgeIt(const ListGraph& G,const Node v)
[395]381        : Edge(G.nodes[v.n].first_out) {}
382    };
383   
384    class InEdgeIt : public Edge {
[397]385      friend class ListGraph;
[395]386    public:
387      InEdgeIt() : Edge() { }
388      InEdgeIt (Invalid i) : Edge(i) { }
[397]389      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
[395]390    };
391
392    template <typename T> class NodeMap : public DynMapBase<Node>
393    {
394      std::vector<T> container;
395
396    public:
397      typedef T ValueType;
398      typedef Node KeyType;
399
[397]400      NodeMap(const ListGraph &_G) :
[395]401        DynMapBase<Node>(_G), container(_G.maxNodeId())
402      {
403        G->dyn_node_maps.push_back(this);
404      }
[397]405      NodeMap(const ListGraph &_G,const T &t) :
[395]406        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
407      {
408        G->dyn_node_maps.push_back(this);
409      }
410     
411      NodeMap(const NodeMap<T> &m) :
412        DynMapBase<Node>(*m.G), container(m.container)
413      {
414        G->dyn_node_maps.push_back(this);
415      }
416
417      template<typename TT> friend class NodeMap;
418 
419      ///\todo It can copy between different types.
420      ///
421      template<typename TT> NodeMap(const NodeMap<TT> &m) :
422        DynMapBase<Node>(*m.G)
423      {
424        G->dyn_node_maps.push_back(this);
425        typename std::vector<TT>::const_iterator i;
426        for(typename std::vector<TT>::const_iterator i=m.container.begin();
427            i!=m.container.end();
428            i++)
429          container.push_back(*i);
430      }
431      ~NodeMap()
432      {
433        if(G) {
434          std::vector<DynMapBase<Node>* >::iterator i;
435          for(i=G->dyn_node_maps.begin();
436              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
437          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
438          //A better way to do that: (Is this really important?)
439          if(*i==this) {
440            *i=G->dyn_node_maps.back();
441            G->dyn_node_maps.pop_back();
442          }
443        }
444      }
445
446      void add(const Node k)
447      {
448        if(k.n>=int(container.size())) container.resize(k.n+1);
449      }
450
451      void erase(const Node) { }
452     
453      void set(Node n, T a) { container[n.n]=a; }
454      //'T& operator[](Node n)' would be wrong here
455      typename std::vector<T>::reference
456      operator[](Node n) { return container[n.n]; }
457      //'const T& operator[](Node n)' would be wrong here
458      typename std::vector<T>::const_reference
459      operator[](Node n) const { return container[n.n]; }
460
461      ///\warning There is no safety check at all!
462      ///Using operator = between maps attached to different graph may
463      ///cause serious problem.
464      ///\todo Is this really so?
465      ///\todo It can copy between different types.
466      const NodeMap<T>& operator=(const NodeMap<T> &m)
467      {
468        container = m.container;
469        return *this;
470      }
471      template<typename TT>
472      const NodeMap<T>& operator=(const NodeMap<TT> &m)
473      {
[531]474        std::copy(m.container.begin(), m.container.end(), container.begin());
[395]475        return *this;
476      }
477     
478      void update() {}    //Useless for Dynamic Maps
479      void update(T a) {}  //Useless for Dynamic Maps
480    };
481   
482    template <typename T> class EdgeMap : public DynMapBase<Edge>
483    {
[579]484    protected:
[395]485      std::vector<T> container;
486
487    public:
488      typedef T ValueType;
489      typedef Edge KeyType;
490
[397]491      EdgeMap(const ListGraph &_G) :
[395]492        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
493      {
494        //FIXME: What if there are empty Id's?
495        //FIXME: Can I use 'this' in a constructor?
496        G->dyn_edge_maps.push_back(this);
497      }
[397]498      EdgeMap(const ListGraph &_G,const T &t) :
[395]499        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
500      {
501        G->dyn_edge_maps.push_back(this);
502      }
503      EdgeMap(const EdgeMap<T> &m) :
504        DynMapBase<Edge>(*m.G), container(m.container)
505      {
[503]506        G->dyn_edge_maps.push_back(this);
[395]507      }
508
509      template<typename TT> friend class EdgeMap;
510
511      ///\todo It can copy between different types.
512      ///
513      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
514        DynMapBase<Edge>(*m.G)
515      {
[503]516        G->dyn_edge_maps.push_back(this);
[395]517        typename std::vector<TT>::const_iterator i;
518        for(typename std::vector<TT>::const_iterator i=m.container.begin();
519            i!=m.container.end();
520            i++)
521          container.push_back(*i);
522      }
523      ~EdgeMap()
524      {
525        if(G) {
526          std::vector<DynMapBase<Edge>* >::iterator i;
527          for(i=G->dyn_edge_maps.begin();
528              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
529          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
530          //A better way to do that: (Is this really important?)
531          if(*i==this) {
532            *i=G->dyn_edge_maps.back();
533            G->dyn_edge_maps.pop_back();
534          }
535        }
536      }
537     
538      void add(const Edge k)
539      {
540        if(k.n>=int(container.size())) container.resize(k.n+1);
541      }
542      void erase(const Edge) { }
543     
544      void set(Edge n, T a) { container[n.n]=a; }
545      //T get(Edge n) const { return container[n.n]; }
546      typename std::vector<T>::reference
547      operator[](Edge n) { return container[n.n]; }
548      typename std::vector<T>::const_reference
549      operator[](Edge n) const { return container[n.n]; }
550
551      ///\warning There is no safety check at all!
552      ///Using operator = between maps attached to different graph may
553      ///cause serious problem.
554      ///\todo Is this really so?
555      ///\todo It can copy between different types.
556      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
557      {
558        container = m.container;
559        return *this;
560      }
561      template<typename TT>
562      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
563      {
[531]564        std::copy(m.container.begin(), m.container.end(), container.begin());
[395]565        return *this;
566      }
567     
568      void update() {}    //Useless for DynMaps
569      void update(T a) {}  //Useless for DynMaps
570    };
571
572  };
573
574  ///Graph for bidirectional edges.
575
576  ///The purpose of this graph structure is to handle graphs
577  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
578  ///of oppositely directed edges.
579  ///There is a new edge map type called
[397]580  ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
[395]581  ///that complements this
582  ///feature by
583  ///storing shared values for the edge pairs. The usual
584  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
585  ///can be used
586  ///as well.
587  ///
588  ///The oppositely directed edge can also be obtained easily
589  ///using \ref opposite.
[397]590  ///
591  ///Here erase(Edge) deletes a pair of edges.
592  ///
593  ///\todo this date structure need some reconsiderations. Maybe it
594  ///should be implemented independently from ListGraph.
[395]595
[397]596  class SymListGraph : public ListGraph
[395]597  {
598  public:
599    template<typename T> class SymEdgeMap;
600    template<typename T> friend class SymEdgeMap;
601
[397]602    SymListGraph() : ListGraph() { }
603    SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
604    ///Adds a pair of oppositely directed edges to the graph.
[395]605    Edge addEdge(Node u, Node v)
606    {
[397]607      Edge e = ListGraph::addEdge(u,v);
608      ListGraph::addEdge(v,u);
[395]609      return e;
610    }
611
[397]612    void erase(Node n) { ListGraph::erase(n); }
[395]613    ///The oppositely directed edge.
614
615    ///Returns the oppositely directed
616    ///pair of the edge \c e.
617    Edge opposite(Edge e) const
618    {
619      Edge f;
620      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
621      return f;
622    }
623   
[397]624    ///Removes a pair of oppositely directed edges to the graph.
625    void erase(Edge e) {
626      ListGraph::erase(opposite(e));
627      ListGraph::erase(e);
628    }
629   
[395]630    ///Common data storage for the edge pairs.
631
632    ///This map makes it possible to store data shared by the oppositely
633    ///directed pairs of edges.
634    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
635    {
636      std::vector<T> container;
637     
638    public:
639      typedef T ValueType;
640      typedef Edge KeyType;
641
[397]642      SymEdgeMap(const SymListGraph &_G) :
[395]643        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
644      {
[397]645        static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
[395]646      }
[397]647      SymEdgeMap(const SymListGraph &_G,const T &t) :
[395]648        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
649      {
650        G->dyn_edge_maps.push_back(this);
651      }
652
653      SymEdgeMap(const SymEdgeMap<T> &m) :
654        DynMapBase<SymEdge>(*m.G), container(m.container)
655      {
656        G->dyn_node_maps.push_back(this);
657      }
658
659      //      template<typename TT> friend class SymEdgeMap;
660
661      ///\todo It can copy between different types.
662      ///
663
664      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
665        DynMapBase<SymEdge>(*m.G)
666      {
667        G->dyn_node_maps.push_back(this);
668        typename std::vector<TT>::const_iterator i;
669        for(typename std::vector<TT>::const_iterator i=m.container.begin();
670            i!=m.container.end();
671            i++)
672          container.push_back(*i);
673      }
674 
675      ~SymEdgeMap()
676      {
677        if(G) {
678          std::vector<DynMapBase<Edge>* >::iterator i;
[397]679          for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
680              i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
[395]681                && *i!=this; ++i) ;
682          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
683          //A better way to do that: (Is this really important?)
684          if(*i==this) {
[397]685            *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
686            static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
[395]687          }
688        }
689      }
690     
691      void add(const Edge k)
692      {
693        if(!k.idref()%2&&k.idref()/2>=int(container.size()))
694          container.resize(k.idref()/2+1);
695      }
696      void erase(const Edge k) { }
697     
698      void set(Edge n, T a) { container[n.idref()/2]=a; }
699      //T get(Edge n) const { return container[n.idref()/2]; }
700      typename std::vector<T>::reference
701      operator[](Edge n) { return container[n.idref()/2]; }
702      typename std::vector<T>::const_reference
703      operator[](Edge n) const { return container[n.idref()/2]; }
704
705      ///\warning There is no safety check at all!
706      ///Using operator = between maps attached to different graph may
707      ///cause serious problem.
708      ///\todo Is this really so?
709      ///\todo It can copy between different types.
710      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
711      {
712        container = m.container;
713        return *this;
714      }
715      template<typename TT>
716      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
717      {
[531]718        std::copy(m.container.begin(), m.container.end(), container.begin());
[395]719        return *this;
720      }
721     
722      void update() {}    //Useless for DynMaps
723      void update(T a) {}  //Useless for DynMaps
724
725    };
726
727  };
728 
[400]729
[401]730  ///A graph class containing only nodes.
[400]731
[401]732  ///This class implements a graph structure without edges.
733  ///The most useful application of this class is to be the node set of an
734  ///\ref EdgeSet class.
[400]735  ///
736  ///It conforms to the graph interface documented under
[401]737  ///the description of \ref GraphSkeleton with the exception that you cannot
738  ///add (or delete) edges. The usual edge iterators are exists, but they are
739  ///always \ref INVALID.
740  ///\sa \ref GraphSkeleton
[508]741  ///\sa \ref EdgeSet
[400]742  class NodeSet {
743
744    //Nodes are double linked.
745    //The free nodes are only single linked using the "next" field.
746    struct NodeT
747    {
748      int first_in,first_out;
749      int prev, next;
750      //      NodeT() {}
751    };
752
753    std::vector<NodeT> nodes;
754    //The first node
755    int first_node;
756    //The first free node
757    int first_free_node;
758   
759  protected:
760   
761    template <typename Key> class DynMapBase
762    {
763    protected:
764      const NodeSet* G;
765    public:
[515]766      virtual void add(const Key k) = 0;
767      virtual void erase(const Key k) = 0;
[400]768      DynMapBase(const NodeSet &_G) : G(&_G) {}
769      virtual ~DynMapBase() {}
770      friend class NodeSet;
771    };
772   
773  public:
774    template <typename T> class EdgeMap;
775    template <typename T> class NodeMap;
776   
777    class Node;
778    class Edge;
779
780    //  protected:
781    // HELPME:
782  protected:
783    ///\bug It must be public because of SymEdgeMap.
784    ///
785    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
786    //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
787   
788  public:
789
790    class NodeIt;
791    class EdgeIt;
792    class OutEdgeIt;
793    class InEdgeIt;
794   
795    template <typename T> class NodeMap;
796    template <typename T> class EdgeMap;
797   
798  public:
799
[408]800    ///Default constructor
[400]801    NodeSet() : nodes(), first_node(-1),
802                  first_free_node(-1) {}
[408]803    ///Copy constructor
[400]804    NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
805                                     first_free_node(_g.first_free_node) {}
806   
807    ~NodeSet()
808    {
809      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
810          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
811      //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
812      //          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
813    }
814
815    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
816    int edgeNum() const { return 0; }  //FIXME: What is this?
817
818    ///\bug This function does something different than
819    ///its name would suggests...
820    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
821    ///\bug This function does something different than
822    ///its name would suggests...
823    int maxEdgeId() const { return 0; }  //FIXME: What is this?
824
825    Node tail(Edge e) const { return INVALID; }
826    Node head(Edge e) const { return INVALID; }
827
828    Node aNode(OutEdgeIt e) const { return INVALID; }
829    Node aNode(InEdgeIt e) const { return INVALID; }
830
831    Node bNode(OutEdgeIt e) const { return INVALID; }
832    Node bNode(InEdgeIt e) const { return INVALID; }
833
834    NodeIt& first(NodeIt& v) const {
835      v=NodeIt(*this); return v; }
836    EdgeIt& first(EdgeIt& e) const {
837      e=EdgeIt(*this); return e; }
838    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
839      e=OutEdgeIt(*this,v); return e; }
840    InEdgeIt& first(InEdgeIt& e, const Node v) const {
841      e=InEdgeIt(*this,v); return e; }
842
843//     template< typename It >
844//     It first() const { It e; first(e); return e; }
845
846//     template< typename It >
847//     It first(Node v) const { It e; first(e,v); return e; }
848
849    bool valid(Edge e) const { return false; }
850    bool valid(Node n) const { return n.n!=-1; }
851   
852    void setInvalid(Edge &e) { }
853    void setInvalid(Node &n) { n.n=-1; }
854   
855    template <typename It> It getNext(It it) const
856    { It tmp(it); return next(tmp); }
857
858    NodeIt& next(NodeIt& it) const {
859      it.n=nodes[it.n].next;
860      return it;
861    }
862    OutEdgeIt& next(OutEdgeIt& it) const { return it; }
863    InEdgeIt& next(InEdgeIt& it) const { return it; }
864    EdgeIt& next(EdgeIt& it) const { return it; }
865
866    int id(Node v) const { return v.n; }
867    int id(Edge e) const { return -1; }
868
869    /// Adds a new node to the graph.
870
871    /// \todo It adds the nodes in a reversed order.
872    /// (i.e. the lastly added node becomes the first.)
873    Node addNode() {
874      int n;
875     
876      if(first_free_node==-1)
877        {
878          n = nodes.size();
879          nodes.push_back(NodeT());
880        }
881      else {
882        n = first_free_node;
883        first_free_node = nodes[n].next;
884      }
885     
886      nodes[n].next = first_node;
887      if(first_node != -1) nodes[first_node].prev = n;
888      first_node = n;
889      nodes[n].prev = -1;
890     
891      nodes[n].first_in = nodes[n].first_out = -1;
892     
893      Node nn; nn.n=n;
894
895      //Update dynamic maps
896      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
897          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
898
899      return nn;
900    }
901   
902    void erase(Node nn) {
903      int n=nn.n;
904     
905      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
906      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
907      else first_node = nodes[n].next;
908     
909      nodes[n].next = first_free_node;
910      first_free_node = n;
911
912      //Update dynamic maps
913      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
914          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
915    }
916   
917    ///\bug Dynamic maps must be updated!
918    ///
919    void clear() {
920      nodes.clear();
921      first_node = first_free_node = -1;
922    }
923
924    class Node {
925      friend class NodeSet;
926      template <typename T> friend class NodeMap;
927     
928      friend class Edge;
929      friend class OutEdgeIt;
930      friend class InEdgeIt;
931
932    protected:
933      int n;
934      friend int NodeSet::id(Node v) const;
935      Node(int nn) {n=nn;}
936    public:
937      Node() {}
938      Node (Invalid i) { n=-1; }
939      bool operator==(const Node i) const {return n==i.n;}
940      bool operator!=(const Node i) const {return n!=i.n;}
941      bool operator<(const Node i) const {return n<i.n;}
942    };
943   
944    class NodeIt : public Node {
945      friend class NodeSet;
946    public:
[579]947      NodeIt() : Node() { }
948      NodeIt(Invalid i) : Node(i) { }
[400]949      NodeIt(const NodeSet& G) : Node(G.first_node) { }
[579]950      ///\todo Undocumented conversion Node -\> NodeIt.
951      NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
952
[400]953    };
954
955    class Edge {
956      //friend class NodeSet;
957      //template <typename T> friend class EdgeMap;
958
959      //template <typename T> friend class SymNodeSet::SymEdgeMap;     
960      //friend Edge SymNodeSet::opposite(Edge) const;
961     
962      //      friend class Node;
963      //      friend class NodeIt;
964    protected:
965      //friend int NodeSet::id(Edge e) const;
966      //      Edge(int nn) {}
967    public:
968      Edge() { }
969      Edge (Invalid) { }
970      bool operator==(const Edge i) const {return true;}
971      bool operator!=(const Edge i) const {return false;}
972      bool operator<(const Edge i) const {return false;}
973      ///\bug This is a workaround until somebody tells me how to
974      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
975      //      int idref() {return -1;}
976      //      int idref() const {return -1;}
977    };
978   
979    class EdgeIt : public Edge {
980      //friend class NodeSet;
981    public:
982      EdgeIt(const NodeSet& G) : Edge() { }
983      EdgeIt (Invalid i) : Edge(i) { }
984      EdgeIt() : Edge() { }
985      ///\bug This is a workaround until somebody tells me how to
986      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
987      //      int idref() {return -1;}
988    };
989   
990    class OutEdgeIt : public Edge {
991      friend class NodeSet;
992    public:
993      OutEdgeIt() : Edge() { }
994      OutEdgeIt (Invalid i) : Edge(i) { }
995      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
996    };
997   
998    class InEdgeIt : public Edge {
999      friend class NodeSet;
1000    public:
1001      InEdgeIt() : Edge() { }
1002      InEdgeIt (Invalid i) : Edge(i) { }
1003      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
1004    };
1005
1006    template <typename T> class NodeMap : public DynMapBase<Node>
1007    {
1008      std::vector<T> container;
1009
1010    public:
1011      typedef T ValueType;
1012      typedef Node KeyType;
1013
1014      NodeMap(const NodeSet &_G) :
1015        DynMapBase<Node>(_G), container(_G.maxNodeId())
1016      {
1017        G->dyn_node_maps.push_back(this);
1018      }
1019      NodeMap(const NodeSet &_G,const T &t) :
1020        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1021      {
1022        G->dyn_node_maps.push_back(this);
1023      }
1024     
1025      NodeMap(const NodeMap<T> &m) :
1026        DynMapBase<Node>(*m.G), container(m.container)
1027      {
1028        G->dyn_node_maps.push_back(this);
1029      }
1030
1031      template<typename TT> friend class NodeMap;
1032 
1033      ///\todo It can copy between different types.
1034      ///
1035      template<typename TT> NodeMap(const NodeMap<TT> &m) :
1036        DynMapBase<Node>(*m.G)
1037      {
1038        G->dyn_node_maps.push_back(this);
1039        typename std::vector<TT>::const_iterator i;
1040        for(typename std::vector<TT>::const_iterator i=m.container.begin();
1041            i!=m.container.end();
1042            i++)
1043          container.push_back(*i);
1044      }
1045      ~NodeMap()
1046      {
1047        if(G) {
1048          std::vector<DynMapBase<Node>* >::iterator i;
1049          for(i=G->dyn_node_maps.begin();
1050              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1051          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1052          //A better way to do that: (Is this really important?)
1053          if(*i==this) {
1054            *i=G->dyn_node_maps.back();
1055            G->dyn_node_maps.pop_back();
1056          }
1057        }
1058      }
1059
1060      void add(const Node k)
1061      {
1062        if(k.n>=int(container.size())) container.resize(k.n+1);
1063      }
1064
1065      void erase(const Node) { }
1066     
1067      void set(Node n, T a) { container[n.n]=a; }
1068      //'T& operator[](Node n)' would be wrong here
1069      typename std::vector<T>::reference
1070      operator[](Node n) { return container[n.n]; }
1071      //'const T& operator[](Node n)' would be wrong here
1072      typename std::vector<T>::const_reference
1073      operator[](Node n) const { return container[n.n]; }
1074
1075      ///\warning There is no safety check at all!
1076      ///Using operator = between maps attached to different graph may
1077      ///cause serious problem.
1078      ///\todo Is this really so?
1079      ///\todo It can copy between different types.
1080      const NodeMap<T>& operator=(const NodeMap<T> &m)
1081      {
1082        container = m.container;
1083        return *this;
1084      }
1085      template<typename TT>
1086      const NodeMap<T>& operator=(const NodeMap<TT> &m)
1087      {
[531]1088        std::copy(m.container.begin(), m.container.end(), container.begin());
[400]1089        return *this;
1090      }
1091     
1092      void update() {}    //Useless for Dynamic Maps
1093      void update(T a) {}  //Useless for Dynamic Maps
1094    };
1095   
1096    template <typename T> class EdgeMap
1097    {
1098    public:
1099      typedef T ValueType;
1100      typedef Edge KeyType;
1101
1102      EdgeMap(const NodeSet &) { }
1103      EdgeMap(const NodeSet &,const T &) { }
1104      EdgeMap(const EdgeMap<T> &) { }
1105      //      template<typename TT> friend class EdgeMap;
1106
1107      ///\todo It can copy between different types.
1108      ///
1109      template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1110      ~EdgeMap() { }
1111
1112      void add(const Edge  ) { }
1113      void erase(const Edge) { }
1114     
1115      void set(Edge, T) { }
1116      //T get(Edge n) const { return container[n.n]; }
1117      ValueType &operator[](Edge) { return *((T*)(NULL)); }
1118      const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1119
1120      const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1121   
1122      template<typename TT>
1123      const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1124     
1125      void update() {}
1126      void update(T a) {}
1127    };
1128  };
1129
1130
1131
[401]1132  ///Graph structure using a node set of another graph.
1133
1134  ///This structure can be used to establish another graph over a node set
1135  /// of an existing one. The node iterator will go through the nodes of the
1136  /// original graph, and the NodeMap's of both graphs will convert to
1137  /// each other.
1138  ///
[404]1139  ///\warning Adding or deleting nodes from the graph is not safe if an
1140  ///\ref EdgeSet is currently attached to it!
1141  ///
1142  ///\todo Make it possible to add/delete edges from the base graph
1143  ///(and from \ref EdgeSet, as well)
1144  ///
[401]1145  ///\param GG The type of the graph which shares its node set with this class.
1146  ///Its interface must conform with \ref GraphSkeleton.
[400]1147  ///
1148  ///It conforms to the graph interface documented under
1149  ///the description of \ref GraphSkeleton.
1150  ///\sa \ref GraphSkeleton.
[401]1151  ///\sa \ref NodeSet.
[400]1152  template<typename GG>
1153  class EdgeSet {
1154
1155    typedef GG NodeGraphType;
1156
1157    NodeGraphType &G;
1158
[515]1159  public:
[400]1160    class Node;
[531]1161    int id(Node v) const;
1162
1163    class Node : public NodeGraphType::Node {
1164      friend class EdgeSet;
1165      //      template <typename T> friend class NodeMap;
1166     
1167      friend class Edge;
1168      friend class OutEdgeIt;
1169      friend class InEdgeIt;
1170      friend class SymEdge;
1171
1172    public:
1173      friend int EdgeSet::id(Node v) const;
1174      //      Node(int nn) {n=nn;}
1175    public:
1176      Node() : NodeGraphType::Node() {}
1177      Node (Invalid i) : NodeGraphType::Node(i) {}
1178      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1179    };
1180   
1181    class NodeIt : public NodeGraphType::NodeIt {
1182      friend class EdgeSet;
1183    public:
1184      NodeIt() : NodeGraphType::NodeIt() { }
1185      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1186      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
1187      NodeIt(const typename NodeGraphType::NodeIt &n)
1188        : NodeGraphType::NodeIt(n) {}
[579]1189      ///\todo Undocumented conversion Node -\> NodeIt.
1190      NodeIt(const EdgeSet& _G, const Node &n)
1191        : NodeGraphType::NodeIt(_G.G,n) { }
1192
[531]1193      operator Node() { return Node(*this);}
1194    };
[515]1195
1196  private:
[400]1197    //Edges are double linked.
1198    //The free edges are only single linked using the "next_in" field.
1199    struct NodeT
1200    {
1201      int first_in,first_out;
1202      NodeT() : first_in(-1), first_out(-1) { }
1203    };
1204
1205    struct EdgeT
1206    {
1207      Node head, tail;
1208      int prev_in, prev_out;
1209      int next_in, next_out;
1210    };
1211
1212   
[515]1213    typename NodeGraphType::template NodeMap<NodeT> nodes;
[400]1214   
1215    std::vector<EdgeT> edges;
1216    //The first free edge
1217    int first_free_edge;
1218   
1219  protected:
1220   
1221    template <typename Key> class DynMapBase
1222    {
1223    protected:
1224      const EdgeSet* G;
1225    public:
[515]1226      virtual void add(const Key k) = 0;
1227      virtual void erase(const Key k) = 0;
[400]1228      DynMapBase(const EdgeSet &_G) : G(&_G) {}
1229      virtual ~DynMapBase() {}
1230      friend class EdgeSet;
1231    };
1232   
1233  public:
1234    //template <typename T> class NodeMap;
1235    template <typename T> class EdgeMap;
1236   
1237    class Node;
1238    class Edge;
1239
1240    //  protected:
1241    // HELPME:
1242  protected:
1243    // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1244    ///\bug It must be public because of SymEdgeMap.
1245    ///
1246    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1247   
1248  public:
1249
1250    class NodeIt;
1251    class EdgeIt;
1252    class OutEdgeIt;
1253    class InEdgeIt;
1254   
1255    template <typename T> class NodeMap;
1256    template <typename T> class EdgeMap;
1257   
1258  public:
1259
[408]1260    ///Constructor
1261   
1262    ///Construates a new graph based on the nodeset of an existing one.
1263    ///\param _G the base graph.
1264    ///\todo It looks like a copy constructor, but it isn't.
[401]1265    EdgeSet(NodeGraphType &_G) : G(_G),
1266                                 nodes(_G), edges(),
1267                                 first_free_edge(-1) { }
[408]1268    ///Copy constructor
1269
1270    ///Makes a copy of an EdgeSet.
1271    ///It will be based on the same graph.
[400]1272    EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
[401]1273                                 first_free_edge(_g.first_free_edge) { }
[400]1274   
1275    ~EdgeSet()
1276    {
1277      // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1278      //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1279      for(typename std::vector<DynMapBase<Edge> * >::iterator
1280            i=dyn_edge_maps.begin();
1281          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1282    }
1283
1284    int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
1285    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
1286
1287    ///\bug This function does something different than
1288    ///its name would suggests...
1289    int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?
1290    ///\bug This function does something different than
1291    ///its name would suggests...
1292    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
1293
1294    Node tail(Edge e) const { return edges[e.n].tail; }
1295    Node head(Edge e) const { return edges[e.n].head; }
1296
1297    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1298    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1299
1300    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1301    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1302
1303    NodeIt& first(NodeIt& v) const {
1304      v=NodeIt(*this); return v; }
1305    EdgeIt& first(EdgeIt& e) const {
1306      e=EdgeIt(*this); return e; }
1307    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1308      e=OutEdgeIt(*this,v); return e; }
1309    InEdgeIt& first(InEdgeIt& e, const Node v) const {
1310      e=InEdgeIt(*this,v); return e; }
1311
1312//     template< typename It >
1313//     It first() const { It e; first(e); return e; }
1314
1315//     template< typename It >
1316//     It first(Node v) const { It e; first(e,v); return e; }
1317
1318    bool valid(Edge e) const { return e.n!=-1; }
1319    bool valid(Node n) const { return G.valid(n); }
1320   
1321    void setInvalid(Edge &e) { e.n=-1; }
1322    void setInvalid(Node &n) { G.setInvalid(n); }
1323   
1324    template <typename It> It getNext(It it) const
1325    { It tmp(it); return next(tmp); }
1326
1327    NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1328    OutEdgeIt& next(OutEdgeIt& it) const
1329    { it.n=edges[it.n].next_out; return it; }
1330    InEdgeIt& next(InEdgeIt& it) const
1331    { it.n=edges[it.n].next_in; return it; }
1332    EdgeIt& next(EdgeIt& it) const {
1333      if(edges[it.n].next_in!=-1) {
1334        it.n=edges[it.n].next_in;
1335      }
1336      else {
[579]1337        NodeIt n(*this,edges[it.n].head);
1338        for(n=next(n);
[503]1339            valid(n) && nodes[n].first_in == -1;
1340            next(n)) ;
1341        it.n = (valid(n))?-1:nodes[n].first_in;
[400]1342      }
1343      return it;
1344    }
1345
1346    int id(Edge e) const { return e.n; }
1347
1348    /// Adds a new node to the graph.
[579]1349    Node addNode() { return G.addNode(); }
[400]1350   
1351    Edge addEdge(Node u, Node v) {
1352      int n;
1353     
1354      if(first_free_edge==-1)
1355        {
1356          n = edges.size();
1357          edges.push_back(EdgeT());
1358        }
1359      else {
1360        n = first_free_edge;
1361        first_free_edge = edges[n].next_in;
1362      }
1363     
[401]1364      edges[n].tail = u; edges[n].head = v;
[400]1365
[401]1366      edges[n].next_out = nodes[u].first_out;
1367      if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
1368      edges[n].next_in = nodes[v].first_in;
1369      if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
[400]1370      edges[n].prev_in = edges[n].prev_out = -1;
1371       
[401]1372      nodes[u].first_out = nodes[v].first_in = n;
[400]1373
1374      Edge e; e.n=n;
1375
1376      //Update dynamic maps
1377      for(typename std::vector<DynMapBase<Edge> * >::iterator
1378            i=dyn_edge_maps.begin();
1379          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1380
1381      return e;
1382    }
1383
1384  private:
1385    void eraseEdge(int n) {
1386     
1387      if(edges[n].next_in!=-1)
1388        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1389      if(edges[n].prev_in!=-1)
1390        edges[edges[n].prev_in].next_in = edges[n].next_in;
1391      else nodes[edges[n].head].first_in = edges[n].next_in;
1392     
1393      if(edges[n].next_out!=-1)
1394        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1395      if(edges[n].prev_out!=-1)
1396        edges[edges[n].prev_out].next_out = edges[n].next_out;
1397      else nodes[edges[n].tail].first_out = edges[n].next_out;
1398     
1399      edges[n].next_in = first_free_edge;
1400      first_free_edge = -1;     
1401
1402      //Update dynamic maps
1403      Edge e; e.n=n;
1404      for(typename std::vector<DynMapBase<Edge> * >::iterator
1405            i=dyn_edge_maps.begin();
1406          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1407    }
1408     
1409  public:
1410
1411//     void erase(Node nn) {
1412//       int n=nn.n;
1413//       int m;
1414//       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1415//       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1416//     }
1417   
1418    void erase(Edge e) { eraseEdge(e.n); }
1419
[579]1420    ///Clear all edges. (Doesn't clear the nodes!)
1421    void clear() {
1422      edges.clear();
1423      first_free_edge=-1;
1424    }
1425
1426
[400]1427//     //\bug Dynamic maps must be updated!
1428//     //
1429//     void clear() {
1430//       nodes.clear();edges.clear();
1431//       first_node=first_free_node=first_free_edge=-1;
1432//     }
1433
[579]1434  public:
1435    template <typename T> class EdgeMap;
1436   
1437    ///
[400]1438    class Edge {
[579]1439    public:
[400]1440      friend class EdgeSet;
1441      template <typename T> friend class EdgeMap;
1442
1443      friend class Node;
1444      friend class NodeIt;
[579]1445    public:
1446      ///\bug It shoud be at least protected
1447      ///
1448      int n;
[400]1449    protected:
1450      friend int EdgeSet::id(Edge e) const;
1451
1452      Edge(int nn) {n=nn;}
1453    public:
1454      Edge() { }
1455      Edge (Invalid) { n=-1; }
1456      bool operator==(const Edge i) const {return n==i.n;}
1457      bool operator!=(const Edge i) const {return n!=i.n;}
1458      bool operator<(const Edge i) const {return n<i.n;}
1459      ///\bug This is a workaround until somebody tells me how to
1460      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1461      int &idref() {return n;}
1462      const int &idref() const {return n;}
1463    };
1464   
1465    class EdgeIt : public Edge {
1466      friend class EdgeSet;
[579]1467      template <typename T> friend class EdgeMap;
1468   
1469     
[400]1470    public:
1471      EdgeIt(const EdgeSet& G) : Edge() {
[503]1472        //              typename NodeGraphType::Node m;
1473        NodeIt m;
[400]1474        for(G.first(m);
[503]1475            G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
[515]1476        //AJJAJ! This is a non sense!!!!!!!
1477        this->n = G.valid(m)?-1:G.nodes[m].first_in;
[400]1478      }
1479      EdgeIt (Invalid i) : Edge(i) { }
1480      EdgeIt() : Edge() { }
1481      ///\bug This is a workaround until somebody tells me how to
1482      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
[515]1483      int &idref() {return this->n;}
[400]1484    };
1485   
1486    class OutEdgeIt : public Edge {
1487      friend class EdgeSet;
1488    public:
1489      OutEdgeIt() : Edge() { }
1490      OutEdgeIt (Invalid i) : Edge(i) { }
1491
[579]1492      OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
[400]1493    };
1494   
1495    class InEdgeIt : public Edge {
1496      friend class EdgeSet;
1497    public:
1498      InEdgeIt() : Edge() { }
1499      InEdgeIt (Invalid i) : Edge(i) { }
[579]1500      InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
[400]1501    };
1502
[515]1503    template <typename T> class NodeMap :
1504      public NodeGraphType::template NodeMap<T>
[400]1505    {
[579]1506      //This is a must, the constructors need it.
1507      typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
[400]1508    public:
[579]1509      NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
1510      NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
[400]1511      //It is unnecessary
[515]1512      NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
[579]1513        ParentNodeMap(m) { }
[400]1514
1515      ///\todo It can copy between different types.
1516      ///
[401]1517      template<typename TT>
[515]1518      NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
[579]1519        : ParentNodeMap(m) { }
[400]1520    };
1521   
[579]1522    ///
[400]1523    template <typename T> class EdgeMap : public DynMapBase<Edge>
1524    {
[579]1525    protected:
1526    public:
1527      ///\bug It should be at least protected
1528      ///
[400]1529      std::vector<T> container;
1530
1531    public:
1532      typedef T ValueType;
1533      typedef Edge KeyType;
1534
1535      EdgeMap(const EdgeSet &_G) :
1536        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1537      {
1538        //FIXME: What if there are empty Id's?
1539        //FIXME: Can I use 'this' in a constructor?
1540        G->dyn_edge_maps.push_back(this);
1541      }
1542      EdgeMap(const EdgeSet &_G,const T &t) :
1543        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1544      {
1545        G->dyn_edge_maps.push_back(this);
1546      }
1547      EdgeMap(const EdgeMap<T> &m) :
1548        DynMapBase<Edge>(*m.G), container(m.container)
1549      {
[503]1550        G->dyn_edge_maps.push_back(this);
[400]1551      }
1552
1553      template<typename TT> friend class EdgeMap;
1554
1555      ///\todo It can copy between different types.
1556      ///
1557      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1558        DynMapBase<Edge>(*m.G)
1559      {
[503]1560        G->dyn_edge_maps.push_back(this);
[400]1561        typename std::vector<TT>::const_iterator i;
1562        for(typename std::vector<TT>::const_iterator i=m.container.begin();
1563            i!=m.container.end();
1564            i++)
1565          container.push_back(*i);
1566      }
1567      ~EdgeMap()
1568      {
1569        if(G) {
1570          typename std::vector<DynMapBase<Edge>* >::iterator i;
1571          for(i=G->dyn_edge_maps.begin();
1572              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1573          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1574          //A better way to do that: (Is this really important?)
1575          if(*i==this) {
1576            *i=G->dyn_edge_maps.back();
1577            G->dyn_edge_maps.pop_back();
1578          }
1579        }
1580      }
1581     
1582      void add(const Edge k)
1583      {
1584        if(k.n>=int(container.size())) container.resize(k.n+1);
1585      }
1586      void erase(const Edge) { }
1587     
[579]1588      ///\bug This doesn't work. Why?
1589      ///      void set(Edge n, T a) { container[n.n]=a; }
1590      void set(Edge n, T a) { container[G->id(n)]=a; }
[400]1591      //T get(Edge n) const { return container[n.n]; }
1592      typename std::vector<T>::reference
[579]1593      ///\bug This doesn't work. Why?
1594      ///      operator[](Edge n) { return container[n.n]; }
1595      operator[](Edge n) { return container[G->id(n)]; }
[400]1596      typename std::vector<T>::const_reference
[579]1597      ///\bug This doesn't work. Why?
1598      ///      operator[](Edge n) const { return container[n.n]; }
1599      operator[](Edge n) const { return container[G->id(n)]; }
[400]1600
1601      ///\warning There is no safety check at all!
1602      ///Using operator = between maps attached to different graph may
1603      ///cause serious problem.
1604      ///\todo Is this really so?
1605      ///\todo It can copy between different types.
1606      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1607      {
1608        container = m.container;
1609        return *this;
1610      }
[579]1611     
1612      template<typename TT> friend class EdgeMap;
1613
[400]1614      template<typename TT>
1615      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1616      {
[531]1617        std::copy(m.container.begin(), m.container.end(), container.begin());
[400]1618        return *this;
1619      }
1620     
1621      void update() {}    //Useless for DynMaps
1622      void update(T a) {}  //Useless for DynMaps
1623    };
1624
1625  };
[406]1626
[579]1627  template<typename GG>
1628  inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
[531]1629
[406]1630/// @} 
1631
[395]1632} //namespace hugo
1633
[405]1634#endif //HUGO_LIST_GRAPH_H
Note: See TracBrowser for help on using the repository browser.