COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/graph.h @ 1:207fb3c727cb

Last change on this file since 1:207fb3c727cb was 1:207fb3c727cb, checked in by Alpar Juttner, 20 years ago

src/demo/graph.h: a proposal for a graph implementation
src/demo/graphdemo.cc: a simle demo using graph.h

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