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

     1 // -*-mode: c++; -*-

     2 #ifndef __GRAPH_H_

     3 #define __GRAPH_H_

     5 //inline void *operator new(size_t s, void *p) { return p; }

     6 #include <new>

     8 namespace NEGRO

9 {

    10   using namespace std;

    12 #include "oldgraph.h"

    14   template <class N, class E> class Graph : protected OldGraph<N,E>

    15   {

    16   public:

    17     typedef E EdgeType;

    18     typedef N NodeType;

    20     class EdgePoint

    21     {

    22     public:

    23       NEGRO::EdgePoint e;

    24       bool isValid() { return e; }

    25     };

    27     class InEdgePoint : public EdgePoint {};

    28     class OutEdgePoint : public EdgePoint {};

    29     class BiEdgePoint : public EdgePoint {};

    30     class SymEdgePoint : public EdgePoint {};

    32     typedef int NodePoint;

    34     class NodeIterator;

    36     class EdgeIterator;

    37     class InEdgeIterator;

    38     class OutEdgeIterator;

    39     class BiEdgeIterator;

    40     class SymEdgeIterator;

    41     class AllEdgeIterator;

    43     class FirstAnythingTypeNode;

    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;

    53     class NodeIterator

    54     {

    55       Graph<N,E> *G;  //operator*() miatt kell!!!

    56       int n;     //nem kellene, ha itt mutato lenne!!

    57     public:

    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;}

    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; }

    71       N &operator*() const { return G->Data(n); }

    72       N *operator->() const { return &G->Data(n); }

    74       bool operator==(const NodeIterator &i) const {return n==i.n;}

    75       bool operator!=(const NodeIterator &i) const {return n!=i.n;}

    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;

    87       //Nem kellene egy:

    88       //      static NodeIterator &GetInvalid();  ?

    89     };

    91     class EdgeIterator

    92     {

    94       Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!

    95       //Ez csak kicsit baj, de:

    96       // Meg a From() es To() miatt!!!!!!!!!!

    98       NEGRO::EdgePoint e;

   100     public:

   101       EdgeIterator() {;} //Kell inicializalni? (Nem)

   102       EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}

   104       // Lehet, hogy ez a ketto nem kell!!!

   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;}

   109       bool isValid() {return e;}

   110       E &operator*() const { return G->Data(e); }

   111       E *operator->() const { return &G->Data(e); }

   113       //operator const OutEdgeIterator ();

   114       //operator const InEdgeIterator ();

   115       //operator const BiEdgeIterator ();

   116       //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal

   118       bool operator==(const EdgeIterator &i) const {return e==i.e;}

   119       bool operator!=(const EdgeIterator &i) const {return e!=i.e;}

   121       int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }

   122       //If the edges are indexable

   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     };

   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();}

   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 ()

   146       friend class Graph;

   147     };

   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);}

   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;}

   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 ();

   169       NodeIterator Anode() const {return To();}

   170       NodeIterator Bnode() const {return From();}

   172       friend class Graph;

   173     };

   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);}

   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;}

   188       NodeIterator Anode() const {return From();}

   189       NodeIterator Bnode() const {return To();}

   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();

   197       friend class Graph;

   198     };

   200     class SymEdgeIterator : public EdgeIterator

   201     {

   202       NodeIterator n;  // Itt ketszer van a G

   204     public:

   205       SymEdgeIterator() {}

   206       SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)

   207       { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }

   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;}

   215       NodeIterator Anode() const {return n;}

   216       NodeIterator Bnode() const {return n.n==From().n?To():From();}

   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;}

   225       friend class Graph;

   226     };

   228     class AllEdgeIterator : public EdgeIterator

   229     {

   230       NodeIterator n;  // Itt ketszer van a G

   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       }

   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;}

   251       NodeIterator Anode() const {return n;}

   252       NodeIterator Bnode() const {return n.n==From().n?To():From();}

   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;}

   261       friend class Graph;

   262     };

   264     typedef NodeIterator DeletingNodeIterator;

   265     typedef EdgeIterator DeletingEdgeIterator;

   266     typedef BiEdgeIterator DeletingBiEdgeIterator;

   267     typedef OutEdgeIterator DeletingOutEdgeIterator;

   268     typedef InEdgeIterator DeletingInEdgeIterator;

   269     typedef SymEdgeIterator DeletingSymEdgeIterator;

   271     const NodeIterator FirstNode()

   272     {

   273       NodeIterator i;

   274       i.G=this;i.n=OldGraph<N,E>::FirstNode();

   275       return i;

   276     }

   278     void GetFirst(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }

   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;}

   289     void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}

   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     }

   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     }

   327     //    class FirstAnythingType;

   328     //    friend class FirstAnythingType;

   330     class FirstAnythingTypeNode

   331     {

   332       NodeIterator n;

   333     public:

   334       FirstAnythingTypeNode(NodeIterator i) : n(i) {}

   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;}

   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     };

   351     class FirstAnythingType

   352     {

   353       Graph<N,E> *G;

   354     public:

   355       FirstAnythingType(Graph<N,E> *gg) : G(gg) {}

   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;

   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;}

   372     // LastNode() vagy endnode() stb. Nem kell?

   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     }

   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);}

   390     int NodeNum() { OldGraph<N,E>::NodeNum(); }

   391     void Clean() { OldGraph<N,E>::Clean(); }

   393     Graph() : _FST(this) {}

   394   };

   396   /*   Ez itt a fiam kommentje:

   397        <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv

   398        vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz

   399        <<  < < <  < <  <   .cx..x.c.cc.c

   400        mcmn

   401   */

   403 }

   405 #endif

author	alpar
	Sun, 14 Dec 2003 15:32:46 +0000
changeset 4	8009bb5ddd09
parent 2	37117ebbabe2
child 6	b63d1bc367f7
permissions	-rw-r--r--