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

     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(const NodeIterator &i) {G=i.G;n=i.n;}

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

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

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

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

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

    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;

    84       //Nem kellene egy:

    85       //      static NodeIterator &GetInvalid();  ?

    86     };

    88     class EdgeIterator

    89     {

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

    92       //Ez csak kicsit baj, de:

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

    95       NEGRO::EdgePoint e;

    97     public:

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

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

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

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

   106       bool isValid() {return e;}

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

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

   110       //operator const OutEdgeIterator ();

   111       //operator const InEdgeIterator ();

   112       //operator const BiEdgeIterator ();

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

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

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

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

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

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

   140       friend class Graph;

   141     };

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

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

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

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

   162       friend class Graph;

   163     };

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

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

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

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

   183       friend class Graph;

   184     };

   186     class SymEdgeIterator : public EdgeIterator

   187     {

   188       NodeIterator n;  // Itt ketszer van a G

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

   197       NodeIterator Anode() const {return n;}

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

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

   207       friend class Graph;

   208     };

   210     class AllEdgeIterator : public EdgeIterator

   211     {

   212       NodeIterator n;  // Itt ketszer van a G

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

   227       NodeIterator Anode() const {return n;}

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

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

   237       friend class Graph;

   238     };

   240     typedef NodeIterator DeletingNodeIterator;

   241     typedef EdgeIterator DeletingEdgeIterator;

   242     typedef BiEdgeIterator DeletingBiEdgeIterator;

   243     typedef OutEdgeIterator DeletingOutEdgeIterator;

   244     typedef InEdgeIterator DeletingInEdgeIterator;

   245     typedef SymEdgeIterator DeletingSymEdgeIterator;

   247     const NodeIterator &FirstNode()

   248     {

   249       NodeIterator i;

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

   251       return i;

   252     }

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

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

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

   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     }

   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     }

   303     //    class FirstAnythingType;

   304     //    friend class FirstAnythingType;

   306     class FirstAnythingTypeNode

   307     {

   308       NodeIterator n;

   309     public:

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

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

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

   327     class FirstAnythingType

   328     {

   329       Graph<N,E> *G;

   330     public:

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

   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;

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

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

   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     }

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

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

   367     int Clean() { OldGraph<N,E>::Clean(); }

   369     Graph() : _FST(this) {}

   370   };

   372   /*   Ez itt a fiam kommentje:

   373        <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv

   374        vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz

   375        <<  < < <  < <  <   .cx..x.c.cc.c

   376        mcmn

   377   */

   379 }

   381 #endif

author	alpar
	Sat, 06 Dec 2003 19:32:27 +0000
changeset 1	207fb3c727cb
child 2	37117ebbabe2
permissions	-rw-r--r--