COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/graph.h @ 242:b255f25ad394

Last change on this file since 242:b255f25ad394 was 70:851ca9a60e90, checked in by Alpar Juttner, 20 years ago

.

File size: 14.9 KB
RevLine 
[1]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>
[6]7#include <vector>
[1]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   
[70]21    class EdgeIt
[1]22    {
23    public:
24      NEGRO::EdgePoint e;
[70]25      bool valid() { return e; }
[1]26    };
27   
[70]28    class InEdgeIt : public EdgeIt {};
29    class OutEdgeIt : public EdgeIt {};
30    class BiEdgeIt : public EdgeIt {};
31    class SymEdgeIt : public EdgeIt {};
[1]32   
[70]33    typedef int NodeIt;
34   
35    typedef NodeIt EachNodeIt;
[1]36   
37    class NodeIterator;
38   
39    class EdgeIterator;
40    class InEdgeIterator;
41    class OutEdgeIterator;
42    class BiEdgeIterator;
43    class SymEdgeIterator;
44    class AllEdgeIterator;
45   
[6]46    class FirstAnythingTypeNode; //Required by the unified First() function.
[1]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;
[70]54    friend class EachEdgeIterator;
[1]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() {;}
[3]63      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
64      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
[1]65      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
66     
[70]67      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
68      NodeIterator next() const { return NodeIterator(*this).goNext();}
69      NodeIterator &operator++() { return goNext();}
[1]70      NodeIterator operator++(int)
[70]71      {NodeIterator tmp(*this); goNext(); return tmp;}
72      bool valid() { return n!=INVALID; }
[1]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     
[70]80      int index() const { return n; } //If the nodes are indexable
[1]81      friend class Graph;
82      friend class EdgeIterator;
83      friend class InEdgeIterator;
84      friend class OutEdgeIterator;
85      friend class BiEdgeIterator;
86      friend class SymEdgeIterator;
[70]87      friend class EachEdgeIterator;
[1]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     
[70]101      NEGRO::EdgeIt e;
[1]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     
[70]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();}
[1]113     
[70]114      bool valid() {return e;}
[1]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;}
[2]125       
[70]126      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
[2]127      //If the edges are indexable
128
[1]129      friend class Graph;
130      friend class InEdgeIterator;
131      friend class OutEdgeIterator;
132      friend class BiEdgeIterator;
133      friend class SymEdgeIterator;
[70]134      friend class EachEdgeIterator;
[1]135    };
136   
137    class BiEdgeIterator : public EdgeIterator
138    {
139    public:
[70]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();}
[1]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:
[3]158      InEdgeIterator() {}
[70]159      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
[3]160      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
161
[1]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:
[3]183      OutEdgeIterator() {}
184      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
185      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
186
[70]187      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
188      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
189      OutEdgeIterator &operator++() { return goNext();}
[1]190      OutEdgeIterator operator++(int)
[70]191      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
[1]192     
[70]193      NodeIterator aNode() const {return tail();}
194      NodeIterator bNode() const {return head();}
[1]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:
[3]210      SymEdgeIterator() {}
[70]211      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
212      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
[3]213
[70]214      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
215      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
216      SymEdgeIterator &operator++() { return goNext();}
[1]217      SymEdgeIterator operator++(int)
[70]218      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
[1]219     
[70]220      NodeIterator aNode() const {return n;}
221      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
[1]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   
[70]233    class EachEdgeIterator : public EdgeIterator
[1]234    {
235      NodeIterator n;  // Itt ketszer van a G
236     
237    public:
[70]238      EachEdgeIterator() {}
239      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
[3]240      {
[70]241        e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
[3]242      } 
243
[70]244      EachEdgeIterator &goNext()
[1]245      {
246        e=e->NextOut();
[70]247        if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
[1]248        return *this;
249      }
[70]250      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
251      EachEdgeIterator &operator++() { return goNext();}
252      EachEdgeIterator operator++(int)
253        {EachEdgeIterator tmp(*this); goNext(); return tmp;}
[1]254     
255     
[70]256      NodeIterator aNode() const {return n;}
257      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
[1]258     
[70]259      operator const EdgeIterator ()
260      {EdgeIterator i; i.G=G;i.e=e;return i;}
[1]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   
[70]278    const NodeIterator firstNode()
[1]279    {
280      NodeIterator i;
281      i.G=this;i.n=OldGraph<N,E>::FirstNode();
282      return i;
283    }
284   
[70]285    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
[1]286   
[70]287    void getFirst(InEdgeIt &p,const NodeIt &n)
[1]288    { p=OldGraph<N,E>::FirstIn(n); }
[70]289    void getFirst(OutEdgeIt &p,const NodeIt &n)
[1]290    { p=OldGraph<N,E>::FirstOut(n); }
[70]291    void getFirst(SymEdgeIt &p,const NodeIt &n)
[1]292    { p=OldGraph<N,E>::FirstEdge(n); }
[70]293    void getFirst(EdgeIt &p) //Vegigmegy mindenen
294    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
[1]295
[70]296    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
[1]297   
[70]298    void getFirst(InEdgeIterator &i,const NodeIterator &n)
[1]299    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
[70]300    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
[1]301    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
[70]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
[1]305    {
306      i.G=this;
[70]307      getFirst(i.n);
[1]308      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
309    } 
310   
311   
312   
313    //Vagy beginnode()?
[70]314    const DeletingEdgeIterator firstOut(const NodeIterator &n)
[1]315    {
316      EdgeIterator i;
317      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
318      return i;
319    }
[70]320    const DeletingEdgeIterator firstIn(const NodeIterator &n)
[1]321    {
322      EdgeIterator i;
323      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
324      return i;
325    }
[70]326    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
[1]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 
[70]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;}
[1]356    };
357   
358    class FirstAnythingType
359    {
360      Graph<N,E> *G;
361    public:
362      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
363
[70]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;}
[1]368      operator const NodeIterator () const
369      {NodeIterator i; G->GetFirst(i);return i;} 
[70]370      operator const NodeIt () const
371      {NodeIt i; G->GetFirst(i);return i;}
[1]372    } _FST;
373   
374    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
[70]375    FirstAnythingTypeNode first(NodeIterator &i)
[1]376    {FirstAnythingTypeNode t(i); return t;}
[70]377    const FirstAnythingType &first() {return _FST;}
[1]378   
379    // LastNode() vagy endnode() stb. Nem kell?
380   
[70]381    DeletingNodeIterator addNode()
[1]382    {
383      DeletingNodeIterator i;
384      i.G=this; i.n=OldGraph<N,E>::AddNode();
385      return i;
386    }
387    DeletingEdgeIterator
[70]388    addEdge(const NodeIterator from,const NodeIterator to)
[1]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   
[70]397    int nodeNum() { OldGraph<N,E>::NodeNum(); }
398    void clean() { OldGraph<N,E>::Clean(); }
[1]399
400    Graph() : _FST(this) {}
[6]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;
[70]410      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
411      T get(const NodeIterator i) const {return map[i.Index()];}
[8]412      T operator[](NodeIterator i) {return map[i.Index()];}
[6]413
[8]414      void update() { map.resize(G->MaxNode());}
[6]415
[8]416      NodeMap() {}
[70]417      void setG(Graph<N,E> &Gr) { G=&Gr; update();}     
[6]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;
[70]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()];}
[6]430     
431      void update()
[8]432        { map.resize(G->MaxEdge());}
[6]433     
[8]434      EdgeMap() {}
[70]435      void setG(Graph<N,E> &Gr)
[8]436      { G=&Gr ;update();}
[6]437     
438    };
439   
[8]440
[70]441    int maxNode() { return OldGraph<N,E>::MaxNode();}
442    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
[8]443   
[1]444  };
445 
[70]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 
[1]485  /*   Ez itt a fiam kommentje:
486       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
487       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
488       <<  < < <  < <  <   .cx..x.c.cc.c         
489       mcmn   
490  */
[70]491};
[1]492
493#endif
Note: See TracBrowser for help on using the repository browser.