COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/list_graph.h @ 542:69bde1d90c04

Last change on this file since 542:69bde1d90c04 was 542:69bde1d90c04, checked in by Akos Ladanyi, 20 years ago

Set up automake environment.

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