COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/graph.h @ 30:10a3f2e0928c

Last change on this file since 30:10a3f2e0928c was 8:cd54905012bc, checked in by Alpar Juttner, 21 years ago

-New test: bfsdemo2.cc added

  • Graph class has a NodeMap? and an EdgeMap? member class
  • default_bfs_T uning the above Maps is added
  • a (property)map must provide a member function SetG() to attach the map to a graph
File size: 13.7 KB
Line 
1// -*-mode: c++; -*-
2#ifndef __GRAPH_H_
3#define __GRAPH_H_
4
5//inline void *operator new(size_t s, void *p) { return p; }
6#include <new>
7#include <vector>
8
9namespace NEGRO
10{
11  using namespace std;
12 
13#include "oldgraph.h"
14 
15  template <class N, class E> class Graph : protected OldGraph<N,E>
16  {
17  public:
18    typedef E EdgeType;
19    typedef N NodeType;
20   
21    class EdgePoint
22    {
23    public:
24      NEGRO::EdgePoint e;
25      bool isValid() { return e; }
26    };
27   
28    class InEdgePoint : public EdgePoint {};
29    class OutEdgePoint : public EdgePoint {};
30    class BiEdgePoint : public EdgePoint {};
31    class SymEdgePoint : public EdgePoint {};
32   
33    typedef int NodePoint;
34   
35    class NodeIterator;
36   
37    class EdgeIterator;
38    class InEdgeIterator;
39    class OutEdgeIterator;
40    class BiEdgeIterator;
41    class SymEdgeIterator;
42    class AllEdgeIterator;
43   
44    class FirstAnythingTypeNode; //Required by the unified First() function.
45
46    friend class NodeIterator;
47    friend class EdgeIterator;
48    friend class InEdgeIterator;
49    friend class OutEdgeIterator;
50    friend class BiEdgeIterator;
51    friend class SymEdgeIterator;
52    friend class AllEdgeIterator;
53   
54    class NodeIterator
55    {
56      Graph<N,E> *G;  //operator*() miatt kell!!!
57      int n;     //nem kellene, ha itt mutato lenne!!
58    public:   
59     
60      NodeIterator() {;}
61      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
62      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
63      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
64     
65      NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
66      NodeIterator Next() const { return NodeIterator(*this).GoNext();}
67      NodeIterator &operator++() { return GoNext();}
68      NodeIterator operator++(int)
69      {NodeIterator tmp(*this); GoNext(); return tmp;}
70      bool isValid() { return n!=INVALID; }
71     
72      N &operator*() const { return G->Data(n); }
73      N *operator->() const { return &G->Data(n); }
74     
75      bool operator==(const NodeIterator &i) const {return n==i.n;}
76      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
77     
78      int Index() const { return n; } //If the nodes are indexable
79      friend class Graph;
80      friend class EdgeIterator;
81      friend class InEdgeIterator;
82      friend class OutEdgeIterator;
83      friend class BiEdgeIterator;
84      friend class SymEdgeIterator;
85      friend class AllEdgeIterator;
86      friend class FirstAnythingTypeNode;
87
88      //Nem kellene egy:
89      //      static NodeIterator &GetInvalid();  ?
90    };
91   
92    class EdgeIterator
93    {
94     
95      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
96      //Ez csak kicsit baj, de:
97      // Meg a From() es To() miatt!!!!!!!!!!
98     
99      NEGRO::EdgePoint e;
100     
101    public:
102      EdgeIterator() {;} //Kell inicializalni? (Nem)
103      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
104     
105      // Lehet, hogy ez a ketto nem kell!!!
106     
107      NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
108      NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
109     
110      bool isValid() {return e;}
111      E &operator*() const { return G->Data(e); }
112      E *operator->() const { return &G->Data(e); }
113     
114      //operator const OutEdgeIterator ();
115      //operator const InEdgeIterator ();
116      //operator const BiEdgeIterator ();
117      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
118     
119      bool operator==(const EdgeIterator &i) const {return e==i.e;}
120      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
121       
122      int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
123      //If the edges are indexable
124
125      friend class Graph;
126      friend class InEdgeIterator;
127      friend class OutEdgeIterator;
128      friend class BiEdgeIterator;
129      friend class SymEdgeIterator;
130      friend class AllEdgeIterator;
131    };
132   
133    class BiEdgeIterator : public EdgeIterator
134    {
135    public:
136      BiEdgeIterator &GoNextIn()  { e=e->NextIn(); return *this;}
137      BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
138      BiEdgeIterator NextIn() const  {return BiEdgeIterator(*this).GoNextIn();}
139      BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
140     
141      operator InEdgeIterator ()
142      {InEdgeIterator i; i.G=G;i.e=e;return i;}
143      operator OutEdgeIterator ()
144      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
145      //operator const SymEdgeIterator ()
146     
147      friend class Graph;
148    };
149   
150    class InEdgeIterator : public EdgeIterator
151    //Ne a BiEdgeIterator-bol szarmazzon?
152    {
153    public:
154      InEdgeIterator() {}
155      InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
156      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
157
158      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
159      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
160      InEdgeIterator &operator++() { return GoNext();}
161      InEdgeIterator operator++(int)
162      {InEdgeIterator tmp(*this); GoNext(); return tmp;}
163     
164      operator const OutEdgeIterator ()
165      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
166      operator const BiEdgeIterator ()
167      {EdgeIterator i; i.G=G;i.e=e;return i;}
168      //      operator const SymEdgeIterator ();
169     
170      NodeIterator Anode() const {return To();}
171      NodeIterator Bnode() const {return From();}
172     
173      friend class Graph;
174    };
175   
176    class OutEdgeIterator : public EdgeIterator
177    {
178    public:
179      OutEdgeIterator() {}
180      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
181      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
182
183      OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
184      OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
185      OutEdgeIterator &operator++() { return GoNext();}
186      OutEdgeIterator operator++(int)
187      {OutEdgeIterator tmp(*this); GoNext(); return tmp;}
188     
189      NodeIterator Anode() const {return From();}
190      NodeIterator Bnode() const {return To();}
191     
192      operator const InEdgeIterator ()
193      {InEdgeIterator i; i.G=G;i.e=e;return i;}
194      operator const BiEdgeIterator ()
195      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
196      //operator const SymEdgeIterator();
197     
198      friend class Graph;
199    };
200   
201    class SymEdgeIterator : public EdgeIterator
202    {
203      NodeIterator n;  // Itt ketszer van a G
204     
205    public:
206      SymEdgeIterator() {}
207      SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
208      { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
209
210      SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
211      SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
212      SymEdgeIterator &operator++() { return GoNext();}
213      SymEdgeIterator operator++(int)
214      {SymEdgeIterator tmp(*this); GoNext(); return tmp;}
215     
216      NodeIterator Anode() const {return n;}
217      NodeIterator Bnode() const {return n.n==From().n?To():From();}
218     
219      operator const InEdgeIterator ()
220      {InEdgeIterator i; i.G=G;i.e=e;return i;}
221      operator const OutEdgeIterator ()
222      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
223      operator const BiEdgeIterator ()
224      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
225     
226      friend class Graph;
227    };
228   
229    class AllEdgeIterator : public EdgeIterator
230    {
231      NodeIterator n;  // Itt ketszer van a G
232     
233    public:
234      AllEdgeIterator() {}
235      AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
236      {
237        e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
238      } 
239
240      AllEdgeIterator &GoNext()
241      {
242        e=e->NextOut();
243        if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
244        return *this;
245      }
246      AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
247      AllEdgeIterator &operator++() { return GoNext();}
248      AllEdgeIterator operator++(int)
249        {AllEdgeIterator tmp(*this); GoNext(); return tmp;}
250     
251     
252      NodeIterator Anode() const {return n;}
253      NodeIterator Bnode() const {return n.n==From().n?To():From();}
254     
255      operator const InEdgeIterator ()
256      {InEdgeIterator i; i.G=G;i.e=e;return i;}
257      operator const OutEdgeIterator ()
258      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
259      operator const BiEdgeIterator ()
260      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
261     
262      friend class Graph;
263    };
264   
265    typedef NodeIterator DeletingNodeIterator;
266    typedef EdgeIterator DeletingEdgeIterator;
267    typedef BiEdgeIterator DeletingBiEdgeIterator;
268    typedef OutEdgeIterator DeletingOutEdgeIterator;
269    typedef InEdgeIterator DeletingInEdgeIterator;
270    typedef SymEdgeIterator DeletingSymEdgeIterator;
271   
272    const NodeIterator FirstNode()
273    {
274      NodeIterator i;
275      i.G=this;i.n=OldGraph<N,E>::FirstNode();
276      return i;
277    }
278   
279    void GetFirst(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }
280   
281    void GetFirst(InEdgePoint &p,const NodePoint &n)
282    { p=OldGraph<N,E>::FirstIn(n); }
283    void GetFirst(OutEdgePoint &p,const NodePoint &n)
284    { p=OldGraph<N,E>::FirstOut(n); }
285    void GetFirst(SymEdgePoint &p,const NodePoint &n)
286    { p=OldGraph<N,E>::FirstEdge(n); }
287    void GetFirst(EdgePoint &p) //Vegigmegy mindenen
288    { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
289
290    void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
291   
292    void GetFirst(InEdgeIterator &i,const NodeIterator &n)
293    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
294    void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
295    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
296    void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
297    { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
298    void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
299    {
300      i.G=this;
301      GetFirst(i.n);
302      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
303    } 
304   
305   
306   
307    //Vagy beginnode()?
308    const DeletingEdgeIterator FirstOut(const NodeIterator &n)
309    {
310      EdgeIterator i;
311      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
312      return i;
313    }
314    const DeletingEdgeIterator FirstIn(const NodeIterator &n)
315    {
316      EdgeIterator i;
317      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
318      return i;
319    }
320    const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
321    {
322      EdgeIterator i;
323      i.G=n.G;i.n=n.n;
324      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
325      return i;
326    }
327   
328    //    class FirstAnythingType;
329    //    friend class FirstAnythingType;
330
331    class FirstAnythingTypeNode
332    {
333      NodeIterator n;
334    public:
335      FirstAnythingTypeNode(NodeIterator i) : n(i) {}
336
337      operator const InEdgeIterator () const
338      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
339      operator const OutEdgeIterator () const
340      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
341      operator const SymEdgeIterator () const
342      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
343 
344      operator const InEdgePoint () const
345      {InEdgePoint i; n.G->GetFirst(i,n);return i;}
346      operator const OutEdgePoint () const
347      {OutEdgePoint i; n.G->GetFirst(i,n);return i;}
348      operator const SymEdgePoint () const
349      {SymEdgePoint i; n.G->GetFirst(i,n);return i;}
350    };
351   
352    class FirstAnythingType
353    {
354      Graph<N,E> *G;
355    public:
356      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
357
358      operator const AllEdgeIterator () const
359      {AllEdgeIterator i; G->GetFirst(i);return i;} 
360      operator const EdgePoint () const
361      {EdgePoint i; G->GetFirst(i);return i;}
362      operator const NodeIterator () const
363      {NodeIterator i; G->GetFirst(i);return i;} 
364      operator const NodePoint () const
365      {NodePoint i; G->GetFirst(i);return i;}
366    } _FST;
367   
368    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
369    FirstAnythingTypeNode First(NodeIterator &i)
370    {FirstAnythingTypeNode t(i); return t;}
371    const FirstAnythingType &First() {return _FST;}
372   
373    // LastNode() vagy endnode() stb. Nem kell?
374   
375    DeletingNodeIterator AddNode()
376    {
377      DeletingNodeIterator i;
378      i.G=this; i.n=OldGraph<N,E>::AddNode();
379      return i;
380    }
381    DeletingEdgeIterator
382    AddEdge(const NodeIterator from,const NodeIterator to)
383    {
384      DeletingEdgeIterator i;
385      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
386    }
387   
388    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
389    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
390   
391    int NodeNum() { OldGraph<N,E>::NodeNum(); }
392    void Clean() { OldGraph<N,E>::Clean(); }
393
394    Graph() : _FST(this) {}
395
396    // MAPS:
397    template<class T> class NodeMap
398    {
399      Graph<N,E> *G;
400      vector<T> map;
401
402    public:
403      typedef T value_type;
404      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
405      T Get(const NodeIterator i) const {return map[i.Index()];}
406      T operator[](NodeIterator i) {return map[i.Index()];}
407
408      void update() { map.resize(G->MaxNode());}
409
410      NodeMap() {}
411      void SetG(Graph<N,E> &Gr) { G=&Gr; update();}     
412    };
413
414    template<class T> class EdgeMap
415    {
416      Graph<N,E> *G;
417      vector<T> map;
418
419    public:
420      typedef T value_type;
421      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
422      T &Get(const NodeIterator i) {return map[i.Index()];}
423      T &operator[](NodeIterator i) {return map[i.Index()];}
424     
425      void update()
426        { map.resize(G->MaxEdge());}
427     
428      EdgeMap() {}
429      void SetG(Graph<N,E> &Gr)
430      { G=&Gr ;update();}
431     
432    };
433   
434
435    int MaxNode() { return OldGraph<N,E>::MaxNode();}
436    int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
437   
438  };
439 
440  /*   Ez itt a fiam kommentje:
441       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
442       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
443       <<  < < <  < <  <   .cx..x.c.cc.c         
444       mcmn   
445  */
446 
447}
448
449#endif
Note: See TracBrowser for help on using the repository browser.