COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/smart_graph.h @ 402:f90f65ba21d5

Last change on this file since 402:f90f65ba21d5 was 402:f90f65ba21d5, checked in by Alpar Juttner, 17 years ago

A missing conversion added

File size: 16.9 KB
Line 
1// -*- mode:C++ -*-
2
3#ifndef HUGO_SMART_GRAPH_H
4#define HUGO_SMART_GRAPH_H
5
6///\file
7///\brief SmartGraph and SymSmartGraph classes.
8
9#include <vector>
10#include <limits.h>
11
12#include "invalid.h"
13
14namespace hugo {
15
16  class SymSmartGraph;
17
18  ///A smart graph class.
19
20  ///This is a simple and fast graph implementation.
21  ///It is also quite memory efficient, but at the price
22  ///that <b> it does not support node and edge deletion</b>.
23  ///It conforms to the graph interface documented under
24  ///the description of \ref GraphSkeleton.
25  ///\sa \ref GraphSkeleton.
26  ///
27  ///\todo Some member functions could be \c static.
28  class SmartGraph {
29
30    struct NodeT
31    {
32      int first_in,first_out;     
33      NodeT() : first_in(-1), first_out(-1) {}
34    };
35    struct EdgeT
36    {
37      int head, tail, next_in, next_out;     
38      //FIXME: is this necessary?
39      EdgeT() : next_in(-1), next_out(-1) {} 
40    };
41
42    std::vector<NodeT> nodes;
43
44    std::vector<EdgeT> edges;
45   
46    protected:
47   
48    template <typename Key> class DynMapBase
49    {
50    protected:
51      const SmartGraph* G;
52    public:
53      virtual void add(const Key k) = NULL;
54      virtual void erase(const Key k) = NULL;
55      DynMapBase(const SmartGraph &_G) : G(&_G) {}
56      virtual ~DynMapBase() {}
57      friend class SmartGraph;
58    };
59   
60  public:
61    template <typename T> class EdgeMap;
62    template <typename T> class EdgeMap;
63
64    class Node;
65    class Edge;
66
67    //  protected:
68    // HELPME:
69  protected:
70    ///\bug It must be public because of SymEdgeMap.
71    ///
72    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
73    ///\bug It must be public because of SymEdgeMap.
74    ///
75    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
76   
77  public:
78
79    class NodeIt;
80    class EdgeIt;
81    class OutEdgeIt;
82    class InEdgeIt;
83   
84    template <typename T> class NodeMap;
85    template <typename T> class EdgeMap;
86   
87  public:
88
89    SmartGraph() : nodes(), edges() { }
90    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
91   
92    ~SmartGraph()
93    {
94      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
95          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
96      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
97          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
98    }
99
100    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
101    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
102
103    ///\bug This function does something different than
104    ///its name would suggests...
105    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
106    ///\bug This function does something different than
107    ///its name would suggests...
108    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
109
110    Node tail(Edge e) const { return edges[e.n].tail; }
111    Node head(Edge e) const { return edges[e.n].head; }
112
113    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
114    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
115
116    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
117    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
118
119    NodeIt& first(NodeIt& v) const {
120      v=NodeIt(*this); return v; }
121    EdgeIt& first(EdgeIt& e) const {
122      e=EdgeIt(*this); return e; }
123    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
124      e=OutEdgeIt(*this,v); return e; }
125    InEdgeIt& first(InEdgeIt& e, const Node v) const {
126      e=InEdgeIt(*this,v); return e; }
127
128//     template< typename It >
129//     It first() const { It e; first(e); return e; }
130
131//     template< typename It >
132//     It first(Node v) const { It e; first(e,v); return e; }
133
134    bool valid(Edge e) const { return e.n!=-1; }
135    bool valid(Node n) const { return n.n!=-1; }
136   
137    void setInvalid(Edge &e) { e.n=-1; }
138    void setInvalid(Node &n) { n.n=-1; }
139   
140    template <typename It> It getNext(It it) const
141    { It tmp(it); return next(tmp); }
142
143    NodeIt& next(NodeIt& it) const {
144      it.n=(it.n+2)%(nodes.size()+1)-1;
145      return it;
146    }
147    OutEdgeIt& next(OutEdgeIt& it) const
148    { it.n=edges[it.n].next_out; return it; }
149    InEdgeIt& next(InEdgeIt& it) const
150    { it.n=edges[it.n].next_in; return it; }
151    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
152
153    int id(Node v) const { return v.n; }
154    int id(Edge e) const { return e.n; }
155
156    Node addNode() {
157      Node n; n.n=nodes.size();
158      nodes.push_back(NodeT()); //FIXME: Hmmm...
159
160      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
161          i!=dyn_node_maps.end(); ++i) (**i).add(n);
162
163      return n;
164    }
165   
166    Edge addEdge(Node u, Node v) {
167      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
168      edges[e.n].tail=u.n; edges[e.n].head=v.n;
169      edges[e.n].next_out=nodes[u.n].first_out;
170      edges[e.n].next_in=nodes[v.n].first_in;
171      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
172
173      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
174          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
175
176      return e;
177    }
178
179    void clear() {nodes.clear();edges.clear();}
180
181    class Node {
182      friend class SmartGraph;
183      template <typename T> friend class NodeMap;
184     
185      friend class Edge;
186      friend class OutEdgeIt;
187      friend class InEdgeIt;
188      friend class SymEdge;
189
190    protected:
191      int n;
192      friend int SmartGraph::id(Node v) const;
193      Node(int nn) {n=nn;}
194    public:
195      Node() {}
196      Node (Invalid i) { n=-1; }
197      bool operator==(const Node i) const {return n==i.n;}
198      bool operator!=(const Node i) const {return n!=i.n;}
199      bool operator<(const Node i) const {return n<i.n;}
200    };
201   
202    class NodeIt : public Node {
203      friend class SmartGraph;
204    public:
205      NodeIt() : Node() { }
206      NodeIt(Invalid i) : Node(i) { }
207      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
208    };
209
210    class Edge {
211      friend class SmartGraph;
212      template <typename T> friend class EdgeMap;
213
214      //template <typename T> friend class SymSmartGraph::SymEdgeMap;     
215      //friend Edge SymSmartGraph::opposite(Edge) const;
216     
217      friend class Node;
218      friend class NodeIt;
219    protected:
220      int n;
221      friend int SmartGraph::id(Edge e) const;
222
223      Edge(int nn) {n=nn;}
224    public:
225      Edge() { }
226      Edge (Invalid) { n=-1; }
227      bool operator==(const Edge i) const {return n==i.n;}
228      bool operator!=(const Edge i) const {return n!=i.n;}
229      bool operator<(const Edge i) const {return n<i.n;}
230      ///\bug This is a workaround until somebody tells me how to
231      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
232      int &idref() {return n;}
233      const int &idref() const {return n;}
234    };
235   
236    class EdgeIt : public Edge {
237      friend class SmartGraph;
238    public:
239      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
240      EdgeIt (Invalid i) : Edge(i) { }
241      EdgeIt() : Edge() { }
242      ///\bug This is a workaround until somebody tells me how to
243      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
244      int &idref() {return n;}
245    };
246   
247    class OutEdgeIt : public Edge {
248      friend class SmartGraph;
249    public:
250      OutEdgeIt() : Edge() { }
251      OutEdgeIt (Invalid i) : Edge(i) { }
252
253      OutEdgeIt(const SmartGraph& G,const Node v)
254        : Edge(G.nodes[v.n].first_out) {}
255    };
256   
257    class InEdgeIt : public Edge {
258      friend class SmartGraph;
259    public:
260      InEdgeIt() : Edge() { }
261      InEdgeIt (Invalid i) : Edge(i) { }
262      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
263    };
264
265    template <typename T> class NodeMap : public DynMapBase<Node>
266    {
267      std::vector<T> container;
268
269    public:
270      typedef T ValueType;
271      typedef Node KeyType;
272
273      NodeMap(const SmartGraph &_G) :
274        DynMapBase<Node>(_G), container(_G.maxNodeId())
275      {
276        G->dyn_node_maps.push_back(this);
277      }
278      NodeMap(const SmartGraph &_G,const T &t) :
279        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
280      {
281        G->dyn_node_maps.push_back(this);
282      }
283     
284      NodeMap(const NodeMap<T> &m) :
285        DynMapBase<Node>(*m.G), container(m.container)
286      {
287        G->dyn_node_maps.push_back(this);
288      }
289
290      template<typename TT> friend class NodeMap;
291 
292      ///\todo It can copy between different types.
293      ///
294      template<typename TT> NodeMap(const NodeMap<TT> &m) :
295        DynMapBase<Node>(*m.G)
296      {
297        G->dyn_node_maps.push_back(this);
298        typename std::vector<TT>::const_iterator i;
299        for(typename std::vector<TT>::const_iterator i=m.container.begin();
300            i!=m.container.end();
301            i++)
302          container.push_back(*i);
303      }
304      ~NodeMap()
305      {
306        if(G) {
307          std::vector<DynMapBase<Node>* >::iterator i;
308          for(i=G->dyn_node_maps.begin();
309              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
310          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
311          //A better way to do that: (Is this really important?)
312          if(*i==this) {
313            *i=G->dyn_node_maps.back();
314            G->dyn_node_maps.pop_back();
315          }
316        }
317      }
318
319      void add(const Node k)
320      {
321        if(k.n>=int(container.size())) container.resize(k.n+1);
322      }
323
324      void erase(const Node) { }
325     
326      void set(Node n, T a) { container[n.n]=a; }
327      //'T& operator[](Node n)' would be wrong here
328      typename std::vector<T>::reference
329      operator[](Node n) { return container[n.n]; }
330      //'const T& operator[](Node n)' would be wrong here
331      typename std::vector<T>::const_reference
332      operator[](Node n) const { return container[n.n]; }
333
334      ///\warning There is no safety check at all!
335      ///Using operator = between maps attached to different graph may
336      ///cause serious problem.
337      ///\todo Is this really so?
338      ///\todo It can copy between different types.
339      const NodeMap<T>& operator=(const NodeMap<T> &m)
340      {
341        container = m.container;
342        return *this;
343      }
344      template<typename TT>
345      const NodeMap<T>& operator=(const NodeMap<TT> &m)
346      {
347        copy(m.container.begin(), m.container.end(), container.begin());
348        return *this;
349      }
350     
351      void update() {}    //Useless for Dynamic Maps
352      void update(T a) {}  //Useless for Dynamic Maps
353    };
354   
355    template <typename T> class EdgeMap : public DynMapBase<Edge>
356    {
357      std::vector<T> container;
358
359    public:
360      typedef T ValueType;
361      typedef Edge KeyType;
362
363      EdgeMap(const SmartGraph &_G) :
364        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
365      {
366        //FIXME: What if there are empty Id's?
367        //FIXME: Can I use 'this' in a constructor?
368        G->dyn_edge_maps.push_back(this);
369      }
370      EdgeMap(const SmartGraph &_G,const T &t) :
371        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
372      {
373        G->dyn_edge_maps.push_back(this);
374      }
375      EdgeMap(const EdgeMap<T> &m) :
376        DynMapBase<Edge>(*m.G), container(m.container)
377      {
378        G->dyn_node_maps.push_back(this);
379      }
380
381      template<typename TT> friend class EdgeMap;
382
383      ///\todo It can copy between different types.
384      ///
385      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
386        DynMapBase<Edge>(*m.G)
387      {
388        G->dyn_node_maps.push_back(this);
389        typename std::vector<TT>::const_iterator i;
390        for(typename std::vector<TT>::const_iterator i=m.container.begin();
391            i!=m.container.end();
392            i++)
393          container.push_back(*i);
394      }
395      ~EdgeMap()
396      {
397        if(G) {
398          std::vector<DynMapBase<Edge>* >::iterator i;
399          for(i=G->dyn_edge_maps.begin();
400              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
401          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
402          //A better way to do that: (Is this really important?)
403          if(*i==this) {
404            *i=G->dyn_edge_maps.back();
405            G->dyn_edge_maps.pop_back();
406          }
407        }
408      }
409     
410      void add(const Edge k)
411      {
412        if(k.n>=int(container.size())) container.resize(k.n+1);
413      }
414      void erase(const Edge) { }
415     
416      void set(Edge n, T a) { container[n.n]=a; }
417      //T get(Edge n) const { return container[n.n]; }
418      typename std::vector<T>::reference
419      operator[](Edge n) { return container[n.n]; }
420      typename std::vector<T>::const_reference
421      operator[](Edge n) const { return container[n.n]; }
422
423      ///\warning There is no safety check at all!
424      ///Using operator = between maps attached to different graph may
425      ///cause serious problem.
426      ///\todo Is this really so?
427      ///\todo It can copy between different types.
428      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
429      {
430        container = m.container;
431        return *this;
432      }
433      template<typename TT>
434      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
435      {
436        copy(m.container.begin(), m.container.end(), container.begin());
437        return *this;
438      }
439     
440      void update() {}    //Useless for DynMaps
441      void update(T a) {}  //Useless for DynMaps
442    };
443
444  };
445
446  ///Graph for bidirectional edges.
447
448  ///The purpose of this graph structure is to handle graphs
449  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
450  ///of oppositely directed edges.
451  ///There is a new edge map type called
452  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
453  ///that complements this
454  ///feature by
455  ///storing shared values for the edge pairs. The usual
456  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
457  ///can be used
458  ///as well.
459  ///
460  ///The oppositely directed edge can also be obtained easily
461  ///using \ref opposite.
462  ///\warning It shares the similarity with \ref SmartGraph that
463  ///it is not possible to delete edges or nodes from the graph.
464  //\sa \ref SmartGraph.
465
466  class SymSmartGraph : public SmartGraph
467  {
468  public:
469    template<typename T> class SymEdgeMap;
470    template<typename T> friend class SymEdgeMap;
471
472    SymSmartGraph() : SmartGraph() { }
473    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
474    ///Adds a pair of oppositely directed edges to the graph.
475    Edge addEdge(Node u, Node v)
476    {
477      Edge e = SmartGraph::addEdge(u,v);
478      SmartGraph::addEdge(v,u);
479      return e;
480    }
481
482    ///The oppositely directed edge.
483
484    ///Returns the oppositely directed
485    ///pair of the edge \c e.
486    Edge opposite(Edge e) const
487    {
488      Edge f;
489      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
490      return f;
491    }
492   
493    ///Common data storage for the edge pairs.
494
495    ///This map makes it possible to store data shared by the oppositely
496    ///directed pairs of edges.
497    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
498    {
499      std::vector<T> container;
500     
501    public:
502      typedef T ValueType;
503      typedef Edge KeyType;
504
505      SymEdgeMap(const SymSmartGraph &_G) :
506        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
507      {
508        static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
509      }
510      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
511        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
512      {
513        G->dyn_edge_maps.push_back(this);
514      }
515
516      SymEdgeMap(const SymEdgeMap<T> &m) :
517        DynMapBase<SymEdge>(*m.G), container(m.container)
518      {
519        G->dyn_node_maps.push_back(this);
520      }
521
522      //      template<typename TT> friend class SymEdgeMap;
523
524      ///\todo It can copy between different types.
525      ///
526
527      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
528        DynMapBase<SymEdge>(*m.G)
529      {
530        G->dyn_node_maps.push_back(this);
531        typename std::vector<TT>::const_iterator i;
532        for(typename std::vector<TT>::const_iterator i=m.container.begin();
533            i!=m.container.end();
534            i++)
535          container.push_back(*i);
536      }
537 
538      ~SymEdgeMap()
539      {
540        if(G) {
541          std::vector<DynMapBase<Edge>* >::iterator i;
542          for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
543              i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
544                && *i!=this; ++i) ;
545          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
546          //A better way to do that: (Is this really important?)
547          if(*i==this) {
548            *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
549            static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
550          }
551        }
552      }
553     
554      void add(const Edge k)
555      {
556        if(!k.idref()%2&&k.idref()/2>=int(container.size()))
557          container.resize(k.idref()/2+1);
558      }
559      void erase(const Edge k) { }
560     
561      void set(Edge n, T a) { container[n.idref()/2]=a; }
562      //T get(Edge n) const { return container[n.idref()/2]; }
563      typename std::vector<T>::reference
564      operator[](Edge n) { return container[n.idref()/2]; }
565      typename std::vector<T>::const_reference
566      operator[](Edge n) const { return container[n.idref()/2]; }
567
568      ///\warning There is no safety check at all!
569      ///Using operator = between maps attached to different graph may
570      ///cause serious problem.
571      ///\todo Is this really so?
572      ///\todo It can copy between different types.
573      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
574      {
575        container = m.container;
576        return *this;
577      }
578      template<typename TT>
579      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
580      {
581        copy(m.container.begin(), m.container.end(), container.begin());
582        return *this;
583      }
584     
585      void update() {}    //Useless for DynMaps
586      void update(T a) {}  //Useless for DynMaps
587
588    };
589
590  };
591 
592 
593} //namespace hugo
594
595
596
597
598#endif //SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.