COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/list_graph.h @ 400:cb377609cf1d

Last change on this file since 400:cb377609cf1d was 400:cb377609cf1d, checked in by Alpar Juttner, 16 years ago

class NodeSet?: A graph class with no edges
class EdgeSet?: A graph class using the node set of another graph.
It compiles but untested and undocumented.

File size: 43.4 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 smart 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 smart graph class.
727
728  ///This is a simple and fast erasable graph implementation.
729  ///
730  ///It conforms to the graph interface documented under
731  ///the description of \ref GraphSkeleton.
732  ///\sa \ref GraphSkeleton.
733  class NodeSet {
734
735    //Nodes are double linked.
736    //The free nodes are only single linked using the "next" field.
737    struct NodeT
738    {
739      int first_in,first_out;
740      int prev, next;
741      //      NodeT() {}
742    };
743
744    std::vector<NodeT> nodes;
745    //The first node
746    int first_node;
747    //The first free node
748    int first_free_node;
749   
750  protected:
751   
752    template <typename Key> class DynMapBase
753    {
754    protected:
755      const NodeSet* G;
756    public:
757      virtual void add(const Key k) = NULL;
758      virtual void erase(const Key k) = NULL;
759      DynMapBase(const NodeSet &_G) : G(&_G) {}
760      virtual ~DynMapBase() {}
761      friend class NodeSet;
762    };
763   
764  public:
765    template <typename T> class EdgeMap;
766    template <typename T> class NodeMap;
767   
768    class Node;
769    class Edge;
770
771    //  protected:
772    // HELPME:
773  protected:
774    ///\bug It must be public because of SymEdgeMap.
775    ///
776    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
777    //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
778   
779  public:
780
781    class NodeIt;
782    class EdgeIt;
783    class OutEdgeIt;
784    class InEdgeIt;
785   
786    template <typename T> class NodeMap;
787    template <typename T> class EdgeMap;
788   
789  public:
790
791    NodeSet() : nodes(), first_node(-1),
792                  first_free_node(-1) {}
793    NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
794                                     first_free_node(_g.first_free_node) {}
795   
796    ~NodeSet()
797    {
798      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
799          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
800      //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
801      //          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
802    }
803
804    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
805    int edgeNum() const { return 0; }  //FIXME: What is this?
806
807    ///\bug This function does something different than
808    ///its name would suggests...
809    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
810    ///\bug This function does something different than
811    ///its name would suggests...
812    int maxEdgeId() const { return 0; }  //FIXME: What is this?
813
814    Node tail(Edge e) const { return INVALID; }
815    Node head(Edge e) const { return INVALID; }
816
817    Node aNode(OutEdgeIt e) const { return INVALID; }
818    Node aNode(InEdgeIt e) const { return INVALID; }
819
820    Node bNode(OutEdgeIt e) const { return INVALID; }
821    Node bNode(InEdgeIt e) const { return INVALID; }
822
823    NodeIt& first(NodeIt& v) const {
824      v=NodeIt(*this); return v; }
825    EdgeIt& first(EdgeIt& e) const {
826      e=EdgeIt(*this); return e; }
827    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
828      e=OutEdgeIt(*this,v); return e; }
829    InEdgeIt& first(InEdgeIt& e, const Node v) const {
830      e=InEdgeIt(*this,v); return e; }
831
832//     template< typename It >
833//     It first() const { It e; first(e); return e; }
834
835//     template< typename It >
836//     It first(Node v) const { It e; first(e,v); return e; }
837
838    bool valid(Edge e) const { return false; }
839    bool valid(Node n) const { return n.n!=-1; }
840   
841    void setInvalid(Edge &e) { }
842    void setInvalid(Node &n) { n.n=-1; }
843   
844    template <typename It> It getNext(It it) const
845    { It tmp(it); return next(tmp); }
846
847    NodeIt& next(NodeIt& it) const {
848      it.n=nodes[it.n].next;
849      return it;
850    }
851    OutEdgeIt& next(OutEdgeIt& it) const { return it; }
852    InEdgeIt& next(InEdgeIt& it) const { return it; }
853    EdgeIt& next(EdgeIt& it) const { return it; }
854
855    int id(Node v) const { return v.n; }
856    int id(Edge e) const { return -1; }
857
858    /// Adds a new node to the graph.
859
860    /// \todo It adds the nodes in a reversed order.
861    /// (i.e. the lastly added node becomes the first.)
862    Node addNode() {
863      int n;
864     
865      if(first_free_node==-1)
866        {
867          n = nodes.size();
868          nodes.push_back(NodeT());
869        }
870      else {
871        n = first_free_node;
872        first_free_node = nodes[n].next;
873      }
874     
875      nodes[n].next = first_node;
876      if(first_node != -1) nodes[first_node].prev = n;
877      first_node = n;
878      nodes[n].prev = -1;
879     
880      nodes[n].first_in = nodes[n].first_out = -1;
881     
882      Node nn; nn.n=n;
883
884      //Update dynamic maps
885      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
886          i!=dyn_node_maps.end(); ++i) (**i).add(nn);
887
888      return nn;
889    }
890   
891    void erase(Node nn) {
892      int n=nn.n;
893     
894      if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
895      if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
896      else first_node = nodes[n].next;
897     
898      nodes[n].next = first_free_node;
899      first_free_node = n;
900
901      //Update dynamic maps
902      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
903          i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
904    }
905   
906    ///\bug Dynamic maps must be updated!
907    ///
908    void clear() {
909      nodes.clear();
910      first_node = first_free_node = -1;
911    }
912
913    class Node {
914      friend class NodeSet;
915      template <typename T> friend class NodeMap;
916     
917      friend class Edge;
918      friend class OutEdgeIt;
919      friend class InEdgeIt;
920
921    protected:
922      int n;
923      friend int NodeSet::id(Node v) const;
924      Node(int nn) {n=nn;}
925    public:
926      Node() {}
927      Node (Invalid i) { n=-1; }
928      bool operator==(const Node i) const {return n==i.n;}
929      bool operator!=(const Node i) const {return n!=i.n;}
930      bool operator<(const Node i) const {return n<i.n;}
931    };
932   
933    class NodeIt : public Node {
934      friend class NodeSet;
935    public:
936      NodeIt(const NodeSet& G) : Node(G.first_node) { }
937      NodeIt() : Node() { }
938    };
939
940    class Edge {
941      //friend class NodeSet;
942      //template <typename T> friend class EdgeMap;
943
944      //template <typename T> friend class SymNodeSet::SymEdgeMap;     
945      //friend Edge SymNodeSet::opposite(Edge) const;
946     
947      //      friend class Node;
948      //      friend class NodeIt;
949    protected:
950      //friend int NodeSet::id(Edge e) const;
951      //      Edge(int nn) {}
952    public:
953      Edge() { }
954      Edge (Invalid) { }
955      bool operator==(const Edge i) const {return true;}
956      bool operator!=(const Edge i) const {return false;}
957      bool operator<(const Edge i) const {return false;}
958      ///\bug This is a workaround until somebody tells me how to
959      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
960      //      int idref() {return -1;}
961      //      int idref() const {return -1;}
962    };
963   
964    class EdgeIt : public Edge {
965      //friend class NodeSet;
966    public:
967      EdgeIt(const NodeSet& G) : Edge() { }
968      EdgeIt (Invalid i) : Edge(i) { }
969      EdgeIt() : Edge() { }
970      ///\bug This is a workaround until somebody tells me how to
971      ///make class \c SymNodeSet::SymEdgeMap friend of Edge
972      //      int idref() {return -1;}
973    };
974   
975    class OutEdgeIt : public Edge {
976      friend class NodeSet;
977    public:
978      OutEdgeIt() : Edge() { }
979      OutEdgeIt (Invalid i) : Edge(i) { }
980      OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
981    };
982   
983    class InEdgeIt : public Edge {
984      friend class NodeSet;
985    public:
986      InEdgeIt() : Edge() { }
987      InEdgeIt (Invalid i) : Edge(i) { }
988      InEdgeIt(const NodeSet& G,Node v) :Edge() {}
989    };
990
991    template <typename T> class NodeMap : public DynMapBase<Node>
992    {
993      std::vector<T> container;
994
995    public:
996      typedef T ValueType;
997      typedef Node KeyType;
998
999      NodeMap(const NodeSet &_G) :
1000        DynMapBase<Node>(_G), container(_G.maxNodeId())
1001      {
1002        G->dyn_node_maps.push_back(this);
1003      }
1004      NodeMap(const NodeSet &_G,const T &t) :
1005        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1006      {
1007        G->dyn_node_maps.push_back(this);
1008      }
1009     
1010      NodeMap(const NodeMap<T> &m) :
1011        DynMapBase<Node>(*m.G), container(m.container)
1012      {
1013        G->dyn_node_maps.push_back(this);
1014      }
1015
1016      template<typename TT> friend class NodeMap;
1017 
1018      ///\todo It can copy between different types.
1019      ///
1020      template<typename TT> NodeMap(const NodeMap<TT> &m) :
1021        DynMapBase<Node>(*m.G)
1022      {
1023        G->dyn_node_maps.push_back(this);
1024        typename std::vector<TT>::const_iterator i;
1025        for(typename std::vector<TT>::const_iterator i=m.container.begin();
1026            i!=m.container.end();
1027            i++)
1028          container.push_back(*i);
1029      }
1030      ~NodeMap()
1031      {
1032        if(G) {
1033          std::vector<DynMapBase<Node>* >::iterator i;
1034          for(i=G->dyn_node_maps.begin();
1035              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1036          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1037          //A better way to do that: (Is this really important?)
1038          if(*i==this) {
1039            *i=G->dyn_node_maps.back();
1040            G->dyn_node_maps.pop_back();
1041          }
1042        }
1043      }
1044
1045      void add(const Node k)
1046      {
1047        if(k.n>=int(container.size())) container.resize(k.n+1);
1048      }
1049
1050      void erase(const Node) { }
1051     
1052      void set(Node n, T a) { container[n.n]=a; }
1053      //'T& operator[](Node n)' would be wrong here
1054      typename std::vector<T>::reference
1055      operator[](Node n) { return container[n.n]; }
1056      //'const T& operator[](Node n)' would be wrong here
1057      typename std::vector<T>::const_reference
1058      operator[](Node n) const { return container[n.n]; }
1059
1060      ///\warning There is no safety check at all!
1061      ///Using operator = between maps attached to different graph may
1062      ///cause serious problem.
1063      ///\todo Is this really so?
1064      ///\todo It can copy between different types.
1065      const NodeMap<T>& operator=(const NodeMap<T> &m)
1066      {
1067        container = m.container;
1068        return *this;
1069      }
1070      template<typename TT>
1071      const NodeMap<T>& operator=(const NodeMap<TT> &m)
1072      {
1073        copy(m.container.begin(), m.container.end(), container.begin());
1074        return *this;
1075      }
1076     
1077      void update() {}    //Useless for Dynamic Maps
1078      void update(T a) {}  //Useless for Dynamic Maps
1079    };
1080   
1081    template <typename T> class EdgeMap
1082    {
1083    public:
1084      typedef T ValueType;
1085      typedef Edge KeyType;
1086
1087      EdgeMap(const NodeSet &) { }
1088      EdgeMap(const NodeSet &,const T &) { }
1089      EdgeMap(const EdgeMap<T> &) { }
1090      //      template<typename TT> friend class EdgeMap;
1091
1092      ///\todo It can copy between different types.
1093      ///
1094      template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1095      ~EdgeMap() { }
1096
1097      void add(const Edge  ) { }
1098      void erase(const Edge) { }
1099     
1100      void set(Edge, T) { }
1101      //T get(Edge n) const { return container[n.n]; }
1102      ValueType &operator[](Edge) { return *((T*)(NULL)); }
1103      const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1104
1105      const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1106   
1107      template<typename TT>
1108      const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1109     
1110      void update() {}
1111      void update(T a) {}
1112    };
1113  };
1114
1115
1116
1117  ///This is a simple and fast erasable graph implementation.
1118  ///
1119  ///It conforms to the graph interface documented under
1120  ///the description of \ref GraphSkeleton.
1121  ///\sa \ref GraphSkeleton.
1122  template<typename GG>
1123  class EdgeSet {
1124
1125    typedef GG NodeGraphType;
1126
1127    NodeGraphType &G;
1128
1129    class Node;
1130   
1131    //Edges are double linked.
1132    //The free edges are only single linked using the "next_in" field.
1133    struct NodeT
1134    {
1135      int first_in,first_out;
1136      NodeT() : first_in(-1), first_out(-1) { }
1137    };
1138
1139    struct EdgeT
1140    {
1141      Node head, tail;
1142      int prev_in, prev_out;
1143      int next_in, next_out;
1144    };
1145
1146   
1147    typename NodeGraphType::NodeMap<NodeT> nodes;
1148   
1149    std::vector<EdgeT> edges;
1150    //The first free edge
1151    int first_free_edge;
1152   
1153  protected:
1154   
1155    template <typename Key> class DynMapBase
1156    {
1157    protected:
1158      const EdgeSet* G;
1159    public:
1160      virtual void add(const Key k) = NULL;
1161      virtual void erase(const Key k) = NULL;
1162      DynMapBase(const EdgeSet &_G) : G(&_G) {}
1163      virtual ~DynMapBase() {}
1164      friend class EdgeSet;
1165    };
1166   
1167  public:
1168    //template <typename T> class NodeMap;
1169    template <typename T> class EdgeMap;
1170   
1171    class Node;
1172    class Edge;
1173
1174    //  protected:
1175    // HELPME:
1176  protected:
1177    // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1178    ///\bug It must be public because of SymEdgeMap.
1179    ///
1180    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1181   
1182  public:
1183
1184    class NodeIt;
1185    class EdgeIt;
1186    class OutEdgeIt;
1187    class InEdgeIt;
1188   
1189    template <typename T> class NodeMap;
1190    template <typename T> class EdgeMap;
1191   
1192  public:
1193
1194    EdgeSet(const NodeGraphType &_G) : G(_G),
1195                                       nodes(_G), edges(),
1196                                       first_free_edge(-1) {}
1197    EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1198                                 first_free_edge(_g.first_free_edge) {}
1199   
1200    ~EdgeSet()
1201    {
1202      // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1203      //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1204      for(typename std::vector<DynMapBase<Edge> * >::iterator
1205            i=dyn_edge_maps.begin();
1206          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1207    }
1208
1209    int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
1210    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
1211
1212    ///\bug This function does something different than
1213    ///its name would suggests...
1214    int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?
1215    ///\bug This function does something different than
1216    ///its name would suggests...
1217    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
1218
1219    Node tail(Edge e) const { return edges[e.n].tail; }
1220    Node head(Edge e) const { return edges[e.n].head; }
1221
1222    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1223    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1224
1225    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1226    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1227
1228    NodeIt& first(NodeIt& v) const {
1229      v=NodeIt(*this); return v; }
1230    EdgeIt& first(EdgeIt& e) const {
1231      e=EdgeIt(*this); return e; }
1232    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1233      e=OutEdgeIt(*this,v); return e; }
1234    InEdgeIt& first(InEdgeIt& e, const Node v) const {
1235      e=InEdgeIt(*this,v); return e; }
1236
1237//     template< typename It >
1238//     It first() const { It e; first(e); return e; }
1239
1240//     template< typename It >
1241//     It first(Node v) const { It e; first(e,v); return e; }
1242
1243    bool valid(Edge e) const { return e.n!=-1; }
1244    bool valid(Node n) const { return G.valid(n); }
1245   
1246    void setInvalid(Edge &e) { e.n=-1; }
1247    void setInvalid(Node &n) { G.setInvalid(n); }
1248   
1249    template <typename It> It getNext(It it) const
1250    { It tmp(it); return next(tmp); }
1251
1252    NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1253    OutEdgeIt& next(OutEdgeIt& it) const
1254    { it.n=edges[it.n].next_out; return it; }
1255    InEdgeIt& next(InEdgeIt& it) const
1256    { it.n=edges[it.n].next_in; return it; }
1257    EdgeIt& next(EdgeIt& it) const {
1258      if(edges[it.n].next_in!=-1) {
1259        it.n=edges[it.n].next_in;
1260      }
1261      else {
1262        typename NodeGraphType::Node n;
1263        for(n=G.next(edges[it.n].head);
1264            G.valid(n) && nodes[n].first_in == -1;
1265            G.next(n)) ;
1266        it.n = (G.valid(n))?-1:nodes[n].first_in;
1267      }
1268      return it;
1269    }
1270
1271    int id(Node v) const { return G.id(v); }
1272    int id(Edge e) const { return e.n; }
1273
1274    /// Adds a new node to the graph.
1275    Node addNode() { return G.AddNode(); }
1276   
1277    Edge addEdge(Node u, Node v) {
1278      int n;
1279     
1280      if(first_free_edge==-1)
1281        {
1282          n = edges.size();
1283          edges.push_back(EdgeT());
1284        }
1285      else {
1286        n = first_free_edge;
1287        first_free_edge = edges[n].next_in;
1288      }
1289     
1290      edges[n].tail = u.n; edges[n].head = v.n;
1291
1292      edges[n].next_out = nodes[u.n].first_out;
1293      if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
1294      edges[n].next_in = nodes[v.n].first_in;
1295      if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
1296      edges[n].prev_in = edges[n].prev_out = -1;
1297       
1298      nodes[u.n].first_out = nodes[v.n].first_in = n;
1299
1300      Edge e; e.n=n;
1301
1302      //Update dynamic maps
1303      for(typename std::vector<DynMapBase<Edge> * >::iterator
1304            i=dyn_edge_maps.begin();
1305          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1306
1307      return e;
1308    }
1309
1310  private:
1311    void eraseEdge(int n) {
1312     
1313      if(edges[n].next_in!=-1)
1314        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1315      if(edges[n].prev_in!=-1)
1316        edges[edges[n].prev_in].next_in = edges[n].next_in;
1317      else nodes[edges[n].head].first_in = edges[n].next_in;
1318     
1319      if(edges[n].next_out!=-1)
1320        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1321      if(edges[n].prev_out!=-1)
1322        edges[edges[n].prev_out].next_out = edges[n].next_out;
1323      else nodes[edges[n].tail].first_out = edges[n].next_out;
1324     
1325      edges[n].next_in = first_free_edge;
1326      first_free_edge = -1;     
1327
1328      //Update dynamic maps
1329      Edge e; e.n=n;
1330      for(typename std::vector<DynMapBase<Edge> * >::iterator
1331            i=dyn_edge_maps.begin();
1332          i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1333    }
1334     
1335  public:
1336
1337//     void erase(Node nn) {
1338//       int n=nn.n;
1339//       int m;
1340//       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1341//       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1342//     }
1343   
1344    void erase(Edge e) { eraseEdge(e.n); }
1345
1346//     //\bug Dynamic maps must be updated!
1347//     //
1348//     void clear() {
1349//       nodes.clear();edges.clear();
1350//       first_node=first_free_node=first_free_edge=-1;
1351//     }
1352
1353    class Node : public NodeGraphType::Node {
1354      friend class EdgeSet;
1355      //      template <typename T> friend class NodeMap;
1356     
1357      friend class Edge;
1358      friend class OutEdgeIt;
1359      friend class InEdgeIt;
1360      friend class SymEdge;
1361
1362    protected:
1363      friend int EdgeSet::id(Node v) const;
1364      //      Node(int nn) {n=nn;}
1365    public:
1366      Node() : NodeGraphType::Node() {}
1367      Node (Invalid i) : NodeGraphType::Node(i) {}
1368      Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1369    };
1370   
1371    class NodeIt : public NodeGraphType::NodeIt {
1372      friend class EdgeSet;
1373    public:
1374      NodeIt() : NodeGraphType::NodeIt() { }
1375      NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1376      NodeIt(const EdgeSet& _G) : NodeGraphType::Node(_G.G) { }
1377      NodeIt(const typename NodeGraphType::NodeIt &n)
1378        : NodeGraphType::NodeIt(n) {}
1379      operator Node() { return Node(*this);}
1380    };
1381
1382    class Edge {
1383      friend class EdgeSet;
1384      template <typename T> friend class EdgeMap;
1385
1386      //template <typename T> friend class SymEdgeSet::SymEdgeMap;     
1387      //friend Edge SymEdgeSet::opposite(Edge) const;
1388     
1389      friend class Node;
1390      friend class NodeIt;
1391    protected:
1392      int n;
1393      friend int EdgeSet::id(Edge e) const;
1394
1395      Edge(int nn) {n=nn;}
1396    public:
1397      Edge() { }
1398      Edge (Invalid) { n=-1; }
1399      bool operator==(const Edge i) const {return n==i.n;}
1400      bool operator!=(const Edge i) const {return n!=i.n;}
1401      bool operator<(const Edge i) const {return n<i.n;}
1402      ///\bug This is a workaround until somebody tells me how to
1403      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1404      int &idref() {return n;}
1405      const int &idref() const {return n;}
1406    };
1407   
1408    class EdgeIt : public Edge {
1409      friend class EdgeSet;
1410    public:
1411      EdgeIt(const EdgeSet& G) : Edge() {
1412        typename NodeGraphType::Node m;
1413        for(G.first(m);
1414            G.valid(m) && nodes[m].first_in == -1;  G.next[m]);
1415        n = G.valid(m)?-1:nodes[m].first_in;
1416      }
1417      EdgeIt (Invalid i) : Edge(i) { }
1418      EdgeIt() : Edge() { }
1419      ///\bug This is a workaround until somebody tells me how to
1420      ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1421      int &idref() {return n;}
1422    };
1423   
1424    class OutEdgeIt : public Edge {
1425      friend class EdgeSet;
1426    public:
1427      OutEdgeIt() : Edge() { }
1428      OutEdgeIt (Invalid i) : Edge(i) { }
1429
1430      OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
1431    };
1432   
1433    class InEdgeIt : public Edge {
1434      friend class EdgeSet;
1435    public:
1436      InEdgeIt() : Edge() { }
1437      InEdgeIt (Invalid i) : Edge(i) { }
1438      InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
1439    };
1440
1441    template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
1442    {
1443    public:
1444      NodeMap(const EdgeSet &_G) :
1445        NodeGraphType::NodeMap<T>(_G.G) { }
1446      NodeMap(const EdgeSet &_G,const T &t) :
1447        NodeGraphType::NodeMap<T>(_G.G,t) { }
1448      //It is unnecessary
1449      NodeMap(const typename NodeGraphType::NodeMap<T> &m)
1450        : NodeGraphType::NodeMap<T>(m) { }
1451
1452      ///\todo It can copy between different types.
1453      ///
1454      template<typename TT> friend class NodeMap;
1455      NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
1456        : NodeGraphType::NodeMap<T>(m) { }
1457    };
1458   
1459    template <typename T> class EdgeMap : public DynMapBase<Edge>
1460    {
1461      std::vector<T> container;
1462
1463    public:
1464      typedef T ValueType;
1465      typedef Edge KeyType;
1466
1467      EdgeMap(const EdgeSet &_G) :
1468        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1469      {
1470        //FIXME: What if there are empty Id's?
1471        //FIXME: Can I use 'this' in a constructor?
1472        G->dyn_edge_maps.push_back(this);
1473      }
1474      EdgeMap(const EdgeSet &_G,const T &t) :
1475        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1476      {
1477        G->dyn_edge_maps.push_back(this);
1478      }
1479      EdgeMap(const EdgeMap<T> &m) :
1480        DynMapBase<Edge>(*m.G), container(m.container)
1481      {
1482        G->dyn_node_maps.push_back(this);
1483      }
1484
1485      template<typename TT> friend class EdgeMap;
1486
1487      ///\todo It can copy between different types.
1488      ///
1489      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1490        DynMapBase<Edge>(*m.G)
1491      {
1492        G->dyn_node_maps.push_back(this);
1493        typename std::vector<TT>::const_iterator i;
1494        for(typename std::vector<TT>::const_iterator i=m.container.begin();
1495            i!=m.container.end();
1496            i++)
1497          container.push_back(*i);
1498      }
1499      ~EdgeMap()
1500      {
1501        if(G) {
1502          typename std::vector<DynMapBase<Edge>* >::iterator i;
1503          for(i=G->dyn_edge_maps.begin();
1504              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1505          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1506          //A better way to do that: (Is this really important?)
1507          if(*i==this) {
1508            *i=G->dyn_edge_maps.back();
1509            G->dyn_edge_maps.pop_back();
1510          }
1511        }
1512      }
1513     
1514      void add(const Edge k)
1515      {
1516        if(k.n>=int(container.size())) container.resize(k.n+1);
1517      }
1518      void erase(const Edge) { }
1519     
1520      void set(Edge n, T a) { container[n.n]=a; }
1521      //T get(Edge n) const { return container[n.n]; }
1522      typename std::vector<T>::reference
1523      operator[](Edge n) { return container[n.n]; }
1524      typename std::vector<T>::const_reference
1525      operator[](Edge n) const { return container[n.n]; }
1526
1527      ///\warning There is no safety check at all!
1528      ///Using operator = between maps attached to different graph may
1529      ///cause serious problem.
1530      ///\todo Is this really so?
1531      ///\todo It can copy between different types.
1532      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1533      {
1534        container = m.container;
1535        return *this;
1536      }
1537      template<typename TT>
1538      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1539      {
1540        copy(m.container.begin(), m.container.end(), container.begin());
1541        return *this;
1542      }
1543     
1544      void update() {}    //Useless for DynMaps
1545      void update(T a) {}  //Useless for DynMaps
1546    };
1547
1548  };
1549
1550
1551
1552
1553
1554
1555
1556 
1557} //namespace hugo
1558
1559
1560
1561
1562#endif //SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.