COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/smart_graph.h @ 284:2d4684f76aac

Last change on this file since 284:2d4684f76aac was 253:f45703336699, checked in by Alpar Juttner, 20 years ago

Move invalid.h smart_graph.h maps.h emptygraph.h to include

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