COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/list_graph.h @ 705:9d9557b56eb7

Last change on this file since 705:9d9557b56eb7 was 705:9d9557b56eb7, checked in by Alpar Juttner, 17 years ago

Unnecessary friend declaration removed.

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