COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/list_graph.h @ 401:2d0cccf7cc94

Last change on this file since 401:2d0cccf7cc94 was 401:2d0cccf7cc94, checked in by Alpar Juttner, 16 years ago

Some bugfixes.
Some more docs.

File size: 44.0 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  ///\param GG The type of the graph which shares its node set with this class.
1130  ///Its interface must conform with \ref GraphSkeleton.
1131  ///
1132  ///It conforms to the graph interface documented under
1133  ///the description of \ref GraphSkeleton.
1134  ///\sa \ref GraphSkeleton.
1135  ///\sa \ref NodeSet.
1136  template<typename GG>
1137  class EdgeSet {
1138
1139    typedef GG NodeGraphType;
1140
1141    NodeGraphType &G;
1142
1143    class Node;
1144   
1145    //Edges are double linked.
1146    //The free edges are only single linked using the "next_in" field.
1147    struct NodeT
1148    {
1149      int first_in,first_out;
1150      NodeT() : first_in(-1), first_out(-1) { }
1151    };
1152
1153    struct EdgeT
1154    {
1155      Node head, tail;
1156      int prev_in, prev_out;
1157      int next_in, next_out;
1158    };
1159
1160   
1161    typename NodeGraphType::NodeMap<NodeT> nodes;
1162   
1163    std::vector<EdgeT> edges;
1164    //The first free edge
1165    int first_free_edge;
1166   
1167  protected:
1168   
1169    template <typename Key> class DynMapBase
1170    {
1171    protected:
1172      const EdgeSet* G;
1173    public:
1174      virtual void add(const Key k) = NULL;
1175      virtual void erase(const Key k) = NULL;
1176      DynMapBase(const EdgeSet &_G) : G(&_G) {}
1177      virtual ~DynMapBase() {}
1178      friend class EdgeSet;
1179    };
1180   
1181  public:
1182    //template <typename T> class NodeMap;
1183    template <typename T> class EdgeMap;
1184   
1185    class Node;
1186    class Edge;
1187
1188    //  protected:
1189    // HELPME:
1190  protected:
1191    // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1192    ///\bug It must be public because of SymEdgeMap.
1193    ///
1194    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1195   
1196  public:
1197
1198    class NodeIt;
1199    class EdgeIt;
1200    class OutEdgeIt;
1201    class InEdgeIt;
1202   
1203    template <typename T> class NodeMap;
1204    template <typename T> class EdgeMap;
1205   
1206  public:
1207
1208    EdgeSet(NodeGraphType &_G) : G(_G),
1209                                 nodes(_G), edges(),
1210                                 first_free_edge(-1) { }
1211    EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1212                                 first_free_edge(_g.first_free_edge) { }
1213   
1214    ~EdgeSet()
1215    {
1216      // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1217      //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1218      for(typename std::vector<DynMapBase<Edge> * >::iterator
1219            i=dyn_edge_maps.begin();
1220          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1221    }
1222
1223    int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
1224    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
1225
1226    ///\bug This function does something different than
1227    ///its name would suggests...
1228    int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?
1229    ///\bug This function does something different than
1230    ///its name would suggests...
1231    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
1232
1233    Node tail(Edge e) const { return edges[e.n].tail; }
1234    Node head(Edge e) const { return edges[e.n].head; }
1235
1236    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1237    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1238
1239    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1240    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1241
1242    NodeIt& first(NodeIt& v) const {
1243      v=NodeIt(*this); return v; }
1244    EdgeIt& first(EdgeIt& e) const {
1245      e=EdgeIt(*this); return e; }
1246    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1247      e=OutEdgeIt(*this,v); return e; }
1248    InEdgeIt& first(InEdgeIt& e, const Node v) const {
1249      e=InEdgeIt(*this,v); return e; }
1250
1251//     template< typename It >
1252//     It first() const { It e; first(e); return e; }
1253
1254//     template< typename It >
1255//     It first(Node v) const { It e; first(e,v); return e; }
1256
1257    bool valid(Edge e) const { return e.n!=-1; }
1258    bool valid(Node n) const { return G.valid(n); }
1259   
1260    void setInvalid(Edge &e) { e.n=-1; }
1261    void setInvalid(Node &n) { G.setInvalid(n); }
1262   
1263    template <typename It> It getNext(It it) const
1264    { It tmp(it); return next(tmp); }
1265
1266    NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1267    OutEdgeIt& next(OutEdgeIt& it) const
1268    { it.n=edges[it.n].next_out; return it; }
1269    InEdgeIt& next(InEdgeIt& it) const
1270    { it.n=edges[it.n].next_in; return it; }
1271    EdgeIt& next(EdgeIt& it) const {
1272      if(edges[it.n].next_in!=-1) {
1273        it.n=edges[it.n].next_in;
1274      }
1275      else {
1276        typename NodeGraphType::Node n;
1277        for(n=G.next(edges[it.n].head);
1278            G.valid(n) && nodes[n].first_in == -1;
1279            G.next(n)) ;
1280        it.n = (G.valid(n))?-1:nodes[n].first_in;
1281      }
1282      return it;
1283    }
1284
1285    int id(Node v) const { return G.id(v); }
1286    int id(Edge e) const { return e.n; }
1287
1288    /// Adds a new node to the graph.
1289    Node addNode() { return G.AddNode(); }
1290   
1291    Edge addEdge(Node u, Node v) {
1292      int n;
1293     
1294      if(first_free_edge==-1)
1295        {
1296          n = edges.size();
1297          edges.push_back(EdgeT());
1298        }
1299      else {
1300        n = first_free_edge;
1301        first_free_edge = edges[n].next_in;
1302      }
1303     
1304      edges[n].tail = u; edges[n].head = v;
1305
1306      edges[n].next_out = nodes[u].first_out;
1307      if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
1308      edges[n].next_in = nodes[v].first_in;
1309      if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
1310      edges[n].prev_in = edges[n].prev_out = -1;
1311       
1312      nodes[u].first_out = nodes[v].first_in = n;
1313
1314      Edge e; e.n=n;
1315
1316      //Update dynamic maps
1317      for(typename std::vector<DynMapBase<Edge> * >::iterator
1318            i=dyn_edge_maps.begin();
1319          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1320
1321      return e;
1322    }
1323
1324  private:
1325    void eraseEdge(int n) {
1326     
1327      if(edges[n].next_in!=-1)
1328        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1329      if(edges[n].prev_in!=-1)
1330        edges[edges[n].prev_in].next_in = edges[n].next_in;
1331      else nodes[edges[n].head].first_in = edges[n].next_in;
1332     
1333      if(edges[n].next_out!=-1)
1334        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1335      if(edges[n].prev_out!=-1)
1336        edges[edges[n].prev_out].next_out = edges[n].next_out;
1337      else nodes[edges[n].tail].first_out = edges[n].next_out;
1338     
1339      edges[n].next_in = first_free_edge;
1340      first_free_edge = -1;     
1341
1342      //Update dynamic maps
1343      Edge e; e.n=n;
1344      for(typename std::vector<DynMapBase<Edge> * >::iterator
1345            i=dyn_edge_maps.begin();
1346          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1347    }
1348     
1349  public:
1350
1351//     void erase(Node nn) {
1352//       int n=nn.n;
1353//       int m;
1354//       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1355//       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1356//     }
1357   
1358    void erase(Edge e) { eraseEdge(e.n); }
1359
1360//     //\bug Dynamic maps must be updated!
1361//     //
1362//     void clear() {
1363//       nodes.clear();edges.clear();
1364//       first_node=first_free_node=first_free_edge=-1;
1365//     }
1366
1367    class Node : public NodeGraphType::Node {
1368      friend class EdgeSet;
1369      //      template <typename T> friend class NodeMap;
1370     
1371      friend class Edge;
1372      friend class OutEdgeIt;
1373      friend class InEdgeIt;
1374      friend class SymEdge;
1375
1376    protected:
1377      friend int EdgeSet::id(Node v) const;
1378      //      Node(int nn) {n=nn;}
1379    public:
1380      Node() : NodeGraphType::Node() {}
1381      Node (Invalid i) : NodeGraphType::Node(i) {}
1382      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1383    };
1384   
1385    class NodeIt : public NodeGraphType::NodeIt {
1386      friend class EdgeSet;
1387    public:
1388      NodeIt() : NodeGraphType::NodeIt() { }
1389      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1390      NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
1391      NodeIt(const typename NodeGraphType::NodeIt &n)
1392        : NodeGraphType::NodeIt(n) {}
1393      operator Node() { return Node(*this);}
1394    };
1395
1396    class Edge {
1397      friend class EdgeSet;
1398      template <typename T> friend class EdgeMap;
1399
1400      //template <typename T> friend class SymEdgeSet::SymEdgeMap;     
1401      //friend Edge SymEdgeSet::opposite(Edge) const;
1402     
1403      friend class Node;
1404      friend class NodeIt;
1405    protected:
1406      int n;
1407      friend int EdgeSet::id(Edge e) const;
1408
1409      Edge(int nn) {n=nn;}
1410    public:
1411      Edge() { }
1412      Edge (Invalid) { n=-1; }
1413      bool operator==(const Edge i) const {return n==i.n;}
1414      bool operator!=(const Edge i) const {return n!=i.n;}
1415      bool operator<(const Edge i) const {return n<i.n;}
1416      ///\bug This is a workaround until somebody tells me how to
1417      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1418      int &idref() {return n;}
1419      const int &idref() const {return n;}
1420    };
1421   
1422    class EdgeIt : public Edge {
1423      friend class EdgeSet;
1424    public:
1425      EdgeIt(const EdgeSet& G) : Edge() {
1426        typename NodeGraphType::Node m;
1427        for(G.first(m);
1428            G.valid(m) && nodes[m].first_in == -1;  G.next[m]);
1429        n = G.valid(m)?-1:nodes[m].first_in;
1430      }
1431      EdgeIt (Invalid i) : Edge(i) { }
1432      EdgeIt() : Edge() { }
1433      ///\bug This is a workaround until somebody tells me how to
1434      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1435      int &idref() {return n;}
1436    };
1437   
1438    class OutEdgeIt : public Edge {
1439      friend class EdgeSet;
1440    public:
1441      OutEdgeIt() : Edge() { }
1442      OutEdgeIt (Invalid i) : Edge(i) { }
1443
1444      OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
1445    };
1446   
1447    class InEdgeIt : public Edge {
1448      friend class EdgeSet;
1449    public:
1450      InEdgeIt() : Edge() { }
1451      InEdgeIt (Invalid i) : Edge(i) { }
1452      InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
1453    };
1454
1455    template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
1456    {
1457    public:
1458      NodeMap(const EdgeSet &_G) :
1459        NodeGraphType::NodeMap<T>(_G.G) { }
1460      NodeMap(const EdgeSet &_G,const T &t) :
1461        NodeGraphType::NodeMap<T>(_G.G,t) { }
1462      //It is unnecessary
1463      NodeMap(const typename NodeGraphType::NodeMap<T> &m)
1464        : NodeGraphType::NodeMap<T>(m) { }
1465
1466      ///\todo It can copy between different types.
1467      ///
1468      template<typename TT>
1469      NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
1470        : NodeGraphType::NodeMap<T>(m) { }
1471    };
1472   
1473    template <typename T> class EdgeMap : public DynMapBase<Edge>
1474    {
1475      std::vector<T> container;
1476
1477    public:
1478      typedef T ValueType;
1479      typedef Edge KeyType;
1480
1481      EdgeMap(const EdgeSet &_G) :
1482        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1483      {
1484        //FIXME: What if there are empty Id's?
1485        //FIXME: Can I use 'this' in a constructor?
1486        G->dyn_edge_maps.push_back(this);
1487      }
1488      EdgeMap(const EdgeSet &_G,const T &t) :
1489        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1490      {
1491        G->dyn_edge_maps.push_back(this);
1492      }
1493      EdgeMap(const EdgeMap<T> &m) :
1494        DynMapBase<Edge>(*m.G), container(m.container)
1495      {
1496        G->dyn_node_maps.push_back(this);
1497      }
1498
1499      template<typename TT> friend class EdgeMap;
1500
1501      ///\todo It can copy between different types.
1502      ///
1503      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1504        DynMapBase<Edge>(*m.G)
1505      {
1506        G->dyn_node_maps.push_back(this);
1507        typename std::vector<TT>::const_iterator i;
1508        for(typename std::vector<TT>::const_iterator i=m.container.begin();
1509            i!=m.container.end();
1510            i++)
1511          container.push_back(*i);
1512      }
1513      ~EdgeMap()
1514      {
1515        if(G) {
1516          typename std::vector<DynMapBase<Edge>* >::iterator i;
1517          for(i=G->dyn_edge_maps.begin();
1518              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1519          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1520          //A better way to do that: (Is this really important?)
1521          if(*i==this) {
1522            *i=G->dyn_edge_maps.back();
1523            G->dyn_edge_maps.pop_back();
1524          }
1525        }
1526      }
1527     
1528      void add(const Edge k)
1529      {
1530        if(k.n>=int(container.size())) container.resize(k.n+1);
1531      }
1532      void erase(const Edge) { }
1533     
1534      void set(Edge n, T a) { container[n.n]=a; }
1535      //T get(Edge n) const { return container[n.n]; }
1536      typename std::vector<T>::reference
1537      operator[](Edge n) { return container[n.n]; }
1538      typename std::vector<T>::const_reference
1539      operator[](Edge n) const { return container[n.n]; }
1540
1541      ///\warning There is no safety check at all!
1542      ///Using operator = between maps attached to different graph may
1543      ///cause serious problem.
1544      ///\todo Is this really so?
1545      ///\todo It can copy between different types.
1546      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1547      {
1548        container = m.container;
1549        return *this;
1550      }
1551      template<typename TT>
1552      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1553      {
1554        copy(m.container.begin(), m.container.end(), container.begin());
1555        return *this;
1556      }
1557     
1558      void update() {}    //Useless for DynMaps
1559      void update(T a) {}  //Useless for DynMaps
1560    };
1561
1562  };
1563
1564
1565
1566
1567
1568
1569
1570 
1571} //namespace hugo
1572
1573
1574
1575
1576#endif //SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.