COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/include/graph.h @ 4:8009bb5ddd09

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