COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/graph.h @ 2:37117ebbabe2

Last change on this file since 2:37117ebbabe2 was 2:37117ebbabe2, checked in by Alpar Juttner, 19 years ago

bfs

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