COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/deba/list_graph.h @ 698:625de6f1e766

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