COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 706:0fe42b8ec5a6

Last change on this file since 706:0fe42b8ec5a6 was 706:0fe42b8ec5a6, checked in by Alpar Juttner, 20 years ago

Temporal change: public Edge constructor with given ID.

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