COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/graph.h @ 941:186aa53d2802

Last change on this file since 941:186aa53d2802 was 253:f45703336699, checked in by Alpar Juttner, 21 years ago

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

File size: 14.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#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 EdgeIt
22    {
23    public:
24      NEGRO::EdgePoint e;
25      bool valid() { return e; }
26    };
27   
28    class InEdgeIt : public EdgeIt {};
29    class OutEdgeIt : public EdgeIt {};
30    class BiEdgeIt : public EdgeIt {};
31    class SymEdgeIt : public EdgeIt {};
32   
33    typedef int NodeIt;
34   
35    typedef NodeIt EachNodeIt;
36   
37    class NodeIterator;
38   
39    class EdgeIterator;
40    class InEdgeIterator;
41    class OutEdgeIterator;
42    class BiEdgeIterator;
43    class SymEdgeIterator;
44    class AllEdgeIterator;
45   
46    class FirstAnythingTypeNode; //Required by the unified First() function.
47
48    friend class NodeIterator;
49    friend class EdgeIterator;
50    friend class InEdgeIterator;
51    friend class OutEdgeIterator;
52    friend class BiEdgeIterator;
53    friend class SymEdgeIterator;
54    friend class EachEdgeIterator;
55   
56    class NodeIterator
57    {
58      Graph<N,E> *G;  //operator*() miatt kell!!!
59      int n;     //nem kellene, ha itt mutato lenne!!
60    public:   
61     
62      NodeIterator() {;}
63      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
64      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
65      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
66     
67      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
68      NodeIterator next() const { return NodeIterator(*this).goNext();}
69      NodeIterator &operator++() { return goNext();}
70      NodeIterator operator++(int)
71      {NodeIterator tmp(*this); goNext(); return tmp;}
72      bool valid() { return n!=INVALID; }
73     
74      N &operator*() const { return G->Data(n); }
75      N *operator->() const { return &G->Data(n); }
76     
77      bool operator==(const NodeIterator &i) const {return n==i.n;}
78      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
79     
80      int index() const { return n; } //If the nodes are indexable
81      friend class Graph;
82      friend class EdgeIterator;
83      friend class InEdgeIterator;
84      friend class OutEdgeIterator;
85      friend class BiEdgeIterator;
86      friend class SymEdgeIterator;
87      friend class EachEdgeIterator;
88      friend class FirstAnythingTypeNode;
89
90      //Nem kellene egy:
91      //      static NodeIterator &GetInvalid();  ?
92    };
93   
94    class EdgeIterator
95    {
96     
97      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
98      //Ez csak kicsit baj, de:
99      // Meg a From() es To() miatt!!!!!!!!!!
100     
101      NEGRO::EdgeIt e;
102     
103    public:
104      EdgeIterator() {;} //Kell inicializalni? (Nem)
105      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
106     
107      // Lehet, hogy ez a ketto nem kell!!!
108     
109      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
110      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
111      NodeIterator opposite(const NodeIterator &n) const
112      {return n==tail()?head():tail();}
113     
114      bool valid() {return e;}
115      E &operator*() const { return G->Data(e); }
116      E *operator->() const { return &G->Data(e); }
117     
118      //operator const OutEdgeIterator ();
119      //operator const InEdgeIterator ();
120      //operator const BiEdgeIterator ();
121      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
122     
123      bool operator==(const EdgeIterator &i) const {return e==i.e;}
124      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
125       
126      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
127      //If the edges are indexable
128
129      friend class Graph;
130      friend class InEdgeIterator;
131      friend class OutEdgeIterator;
132      friend class BiEdgeIterator;
133      friend class SymEdgeIterator;
134      friend class EachEdgeIterator;
135    };
136   
137    class BiEdgeIterator : public EdgeIterator
138    {
139    public:
140      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}
141      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
142      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}
143      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
144     
145      operator InEdgeIterator ()
146      {InEdgeIterator i; i.G=G;i.e=e;return i;}
147      operator OutEdgeIterator ()
148      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
149      //operator const SymEdgeIterator ()
150     
151      friend class Graph;
152    };
153   
154    class InEdgeIterator : public EdgeIterator
155    //Ne a BiEdgeIterator-bol szarmazzon?
156    {
157    public:
158      InEdgeIterator() {}
159      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
160      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
161
162      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
163      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
164      InEdgeIterator &operator++() { return GoNext();}
165      InEdgeIterator operator++(int)
166      {InEdgeIterator tmp(*this); GoNext(); return tmp;}
167     
168      operator const OutEdgeIterator ()
169      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
170      operator const BiEdgeIterator ()
171      {EdgeIterator i; i.G=G;i.e=e;return i;}
172      //      operator const SymEdgeIterator ();
173     
174      NodeIterator Anode() const {return To();}
175      NodeIterator Bnode() const {return From();}
176     
177      friend class Graph;
178    };
179   
180    class OutEdgeIterator : public EdgeIterator
181    {
182    public:
183      OutEdgeIterator() {}
184      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
185      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
186
187      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
188      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
189      OutEdgeIterator &operator++() { return goNext();}
190      OutEdgeIterator operator++(int)
191      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
192     
193      NodeIterator aNode() const {return tail();}
194      NodeIterator bNode() const {return head();}
195     
196      operator const InEdgeIterator ()
197      {InEdgeIterator i; i.G=G;i.e=e;return i;}
198      operator const BiEdgeIterator ()
199      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
200      //operator const SymEdgeIterator();
201     
202      friend class Graph;
203    };
204   
205    class SymEdgeIterator : public EdgeIterator
206    {
207      NodeIterator n;  // Itt ketszer van a G
208     
209    public:
210      SymEdgeIterator() {}
211      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
212      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
213
214      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
215      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
216      SymEdgeIterator &operator++() { return goNext();}
217      SymEdgeIterator operator++(int)
218      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
219     
220      NodeIterator aNode() const {return n;}
221      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
222     
223      operator const InEdgeIterator ()
224      {InEdgeIterator i; i.G=G;i.e=e;return i;}
225      operator const OutEdgeIterator ()
226      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
227      operator const BiEdgeIterator ()
228      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
229     
230      friend class Graph;
231    };
232   
233    class EachEdgeIterator : public EdgeIterator
234    {
235      NodeIterator n;  // Itt ketszer van a G
236     
237    public:
238      EachEdgeIterator() {}
239      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
240      {
241        e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
242      } 
243
244      EachEdgeIterator &goNext()
245      {
246        e=e->NextOut();
247        if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
248        return *this;
249      }
250      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
251      EachEdgeIterator &operator++() { return goNext();}
252      EachEdgeIterator operator++(int)
253        {EachEdgeIterator tmp(*this); goNext(); return tmp;}
254     
255     
256      NodeIterator aNode() const {return n;}
257      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
258     
259      operator const EdgeIterator ()
260      {EdgeIterator i; i.G=G;i.e=e;return i;}
261      operator const InEdgeIterator ()
262      {InEdgeIterator i; i.G=G;i.e=e;return i;}
263      operator const OutEdgeIterator ()
264      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
265      operator const BiEdgeIterator ()
266      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
267     
268      friend class Graph;
269    };
270   
271    typedef NodeIterator DeletingNodeIterator;
272    typedef EdgeIterator DeletingEdgeIterator;
273    typedef BiEdgeIterator DeletingBiEdgeIterator;
274    typedef OutEdgeIterator DeletingOutEdgeIterator;
275    typedef InEdgeIterator DeletingInEdgeIterator;
276    typedef SymEdgeIterator DeletingSymEdgeIterator;
277   
278    const NodeIterator firstNode()
279    {
280      NodeIterator i;
281      i.G=this;i.n=OldGraph<N,E>::FirstNode();
282      return i;
283    }
284   
285    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
286   
287    void getFirst(InEdgeIt &p,const NodeIt &n)
288    { p=OldGraph<N,E>::FirstIn(n); }
289    void getFirst(OutEdgeIt &p,const NodeIt &n)
290    { p=OldGraph<N,E>::FirstOut(n); }
291    void getFirst(SymEdgeIt &p,const NodeIt &n)
292    { p=OldGraph<N,E>::FirstEdge(n); }
293    void getFirst(EdgeIt &p) //Vegigmegy mindenen
294    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
295
296    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
297   
298    void getFirst(InEdgeIterator &i,const NodeIterator &n)
299    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
300    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
301    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
302    void getFirst(SymEdgeIterator &i,const NodeIterator &n)
303    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
304    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
305    {
306      i.G=this;
307      getFirst(i.n);
308      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
309    } 
310   
311   
312   
313    //Vagy beginnode()?
314    const DeletingEdgeIterator firstOut(const NodeIterator &n)
315    {
316      EdgeIterator i;
317      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
318      return i;
319    }
320    const DeletingEdgeIterator firstIn(const NodeIterator &n)
321    {
322      EdgeIterator i;
323      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
324      return i;
325    }
326    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
327    {
328      EdgeIterator i;
329      i.G=n.G;i.n=n.n;
330      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
331      return i;
332    }
333   
334    //    class FirstAnythingType;
335    //    friend class FirstAnythingType;
336
337    class FirstAnythingTypeNode
338    {
339      NodeIterator n;
340    public:
341      FirstAnythingTypeNode(NodeIterator i) : n(i) {}
342
343      operator const InEdgeIterator () const
344      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
345      operator const OutEdgeIterator () const
346      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
347      operator const SymEdgeIterator () const
348      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
349 
350      operator const InEdgeIt () const
351      {InEdgeIt i; n.G->GetFirst(i,n);return i;}
352      operator const OutEdgeIt () const
353      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
354      operator const SymEdgeIt () const
355      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
356    };
357   
358    class FirstAnythingType
359    {
360      Graph<N,E> *G;
361    public:
362      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
363
364      operator const EachEdgeIterator () const
365      {EachEdgeIterator i; G->GetFirst(i);return i;} 
366      operator const EdgeIt () const
367      {EdgeIt i; G->GetFirst(i);return i;}
368      operator const NodeIterator () const
369      {NodeIterator i; G->GetFirst(i);return i;} 
370      operator const NodeIt () const
371      {NodeIt i; G->GetFirst(i);return i;}
372    } _FST;
373   
374    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
375    FirstAnythingTypeNode first(NodeIterator &i)
376    {FirstAnythingTypeNode t(i); return t;}
377    const FirstAnythingType &first() {return _FST;}
378   
379    // LastNode() vagy endnode() stb. Nem kell?
380   
381    DeletingNodeIterator addNode()
382    {
383      DeletingNodeIterator i;
384      i.G=this; i.n=OldGraph<N,E>::AddNode();
385      return i;
386    }
387    DeletingEdgeIterator
388    addEdge(const NodeIterator from,const NodeIterator to)
389    {
390      DeletingEdgeIterator i;
391      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
392    }
393   
394    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
395    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
396   
397    int nodeNum() { OldGraph<N,E>::NodeNum(); }
398    void clean() { OldGraph<N,E>::Clean(); }
399
400    Graph() : _FST(this) {}
401
402    // MAPS:
403    template<class T> class NodeMap
404    {
405      Graph<N,E> *G;
406      vector<T> map;
407
408    public:
409      typedef T value_type;
410      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
411      T get(const NodeIterator i) const {return map[i.Index()];}
412      T operator[](NodeIterator i) {return map[i.Index()];}
413
414      void update() { map.resize(G->MaxNode());}
415
416      NodeMap() {}
417      void setG(Graph<N,E> &Gr) { G=&Gr; update();}     
418    };
419
420    template<class T> class EdgeMap
421    {
422      Graph<N,E> *G;
423      vector<T> map;
424
425    public:
426      typedef T value_type;
427      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
428      T get(const EdgeIterator i) const {return map[i.Index()];}
429      T &operator[](EdgeIterator i) {return map[i.Index()];}
430     
431      void update()
432        { map.resize(G->MaxEdge());}
433     
434      EdgeMap() {}
435      void setG(Graph<N,E> &Gr)
436      { G=&Gr ;update();}
437     
438    };
439   
440
441    int maxNode() { return OldGraph<N,E>::MaxNode();}
442    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
443   
444  };
445 
446  template <class G> //G is a graph-type
447  class Path
448  {
449  public:
450    typedef G Graph;
451    typedef typename G::NodeIterator NodeIterator;
452    typedef typename G::EdgeIterator EdgeIterator;
453    typedef typename G::SymEdgeIterator SymEdgeIterator;
454   
455  private:
456    std::vector<EdgeIterator> path;
457    std::vector<bool> reversed;
458
459  public:
460    void setLength(int n) { path.resize(n);reversed.resize(n);}
461    int getLength() { return path.size(); }
462    EdgeIterator &operator[](int n) {return path[n];}
463    NodeIterator GetNode(int n) // What about path of length 1?
464    {
465      return n?
466        reversed[n-1]?path[n-1].tail():path[n-1].head():
467        reversed[0]?path[0].head():path[0].tail();
468    }
469    void setRevert(int n,bool r=true) {reversed[n]=r;}
470    void setEdge(int n,SymEdgeIterator i)
471    {
472      path[n]=i;
473      reversed[n] = i.head()==i.aNode();
474    }
475    void setEdge(int n,EdgeIterator i,bool r)
476    {
477      path[n]=i;
478      reversed[n] = r;
479    }
480
481    NodeIterator tail() { return getNode(0); }
482    NodeIterator head() { return getNode(getLength()); }
483  };
484 
485  /*   Ez itt a fiam kommentje:
486       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
487       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
488       <<  < < <  < <  <   .cx..x.c.cc.c         
489       mcmn   
490  */
491};
492
493#endif
Note: See TracBrowser for help on using the repository browser.