COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 687:6094295ea312

Last change on this file since 687:6094295ea312 was 681:06a3cba90f94, checked in by Alpar Juttner, 17 years ago

Nothing

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