COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/list_graph.h @ 404:d888ca4e6c00

Last change on this file since 404:d888ca4e6c00 was 404:d888ca4e6c00, checked in by Alpar Juttner, 17 years ago

More docs.

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