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

     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>

     7 #include <vector>

     9 namespace NEGRO

    10 {

    11   using namespace std;

    13 #include "oldgraph.h"

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

    16   {

    17   public:

    18     typedef E EdgeType;

    19     typedef N NodeType;

    21     class EdgePoint

    22     {

    23     public:

    24       NEGRO::EdgePoint e;

    25       bool isValid() { return e; }

    26     };

    28     class InEdgePoint : public EdgePoint {};

    29     class OutEdgePoint : public EdgePoint {};

    30     class BiEdgePoint : public EdgePoint {};

    31     class SymEdgePoint : public EdgePoint {};

    33     typedef int NodePoint;

    35     class NodeIterator;

    37     class EdgeIterator;

    38     class InEdgeIterator;

    39     class OutEdgeIterator;

    40     class BiEdgeIterator;

    41     class SymEdgeIterator;

    42     class AllEdgeIterator;

    44     class FirstAnythingTypeNode; //Required by the unified First() function.

    46     friend class NodeIterator;

    47     friend class EdgeIterator;

    48     friend class InEdgeIterator;

    49     friend class OutEdgeIterator;

    50     friend class BiEdgeIterator;

    51     friend class SymEdgeIterator;

    52     friend class AllEdgeIterator;

    54     class NodeIterator

    55     {

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

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

    58     public:

    60       NodeIterator() {;}

    61       NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.

    62       {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}

    63       NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}

    65       NodeIterator &GoNext() { n=G->NextNode(n); return *this;}

    66       NodeIterator Next() const { return NodeIterator(*this).GoNext();}

    67       NodeIterator &operator++() { return GoNext();}

    68       NodeIterator operator++(int)

    69       {NodeIterator tmp(*this); GoNext(); return tmp;}

    70       bool isValid() { return n!=INVALID; }

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

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

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

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

    78       int Index() const { return n; } //If the nodes are indexable

    79       friend class Graph;

    80       friend class EdgeIterator;

    81       friend class InEdgeIterator;

    82       friend class OutEdgeIterator;

    83       friend class BiEdgeIterator;

    84       friend class SymEdgeIterator;

    85       friend class AllEdgeIterator;

    86       friend class FirstAnythingTypeNode;

    88       //Nem kellene egy:

    89       //      static NodeIterator &GetInvalid();  ?

    90     };

    92     class EdgeIterator

    93     {

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

    96       //Ez csak kicsit baj, de:

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

    99       NEGRO::EdgePoint e;

   101     public:

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

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

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

   107       NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}

   108       NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}

   110       bool isValid() {return e;}

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

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

   114       //operator const OutEdgeIterator ();

   115       //operator const InEdgeIterator ();

   116       //operator const BiEdgeIterator ();

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

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

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

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

   123       //If the edges are indexable

   125       friend class Graph;

   126       friend class InEdgeIterator;

   127       friend class OutEdgeIterator;

   128       friend class BiEdgeIterator;

   129       friend class SymEdgeIterator;

   130       friend class AllEdgeIterator;

   131     };

   133     class BiEdgeIterator : public EdgeIterator

   134     {

   135     public:

   136       BiEdgeIterator &GoNextIn()  { e=e->NextIn(); return *this;}

   137       BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}

   138       BiEdgeIterator NextIn() const  {return BiEdgeIterator(*this).GoNextIn();}

   139       BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}

   141       operator InEdgeIterator ()

   142       {InEdgeIterator i; i.G=G;i.e=e;return i;}

   143       operator OutEdgeIterator ()

   144       {OutEdgeIterator i; i.G=G;i.e=e;return i;}

   145       //operator const SymEdgeIterator ()

   147       friend class Graph;

   148     };

   150     class InEdgeIterator : public EdgeIterator

   151     //Ne a BiEdgeIterator-bol szarmazzon?

   152     {

   153     public:

   154       InEdgeIterator() {}

   155       InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)

   156       { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}

   158       InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}

   159       InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}

   160       InEdgeIterator &operator++() { return GoNext();}

   161       InEdgeIterator operator++(int)

   162       {InEdgeIterator tmp(*this); GoNext(); return tmp;}

   164       operator const OutEdgeIterator ()

   165       {OutEdgeIterator i; i.G=G;i.e=e;return i;}

   166       operator const BiEdgeIterator ()

   167       {EdgeIterator i; i.G=G;i.e=e;return i;}

   168       //      operator const SymEdgeIterator ();

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

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

   173       friend class Graph;

   174     };

   176     class OutEdgeIterator : public EdgeIterator

   177     {

   178     public:

   179       OutEdgeIterator() {}

   180       OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)

   181       { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}

   183       OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}

   184       OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}

   185       OutEdgeIterator &operator++() { return GoNext();}

   186       OutEdgeIterator operator++(int)

   187       {OutEdgeIterator tmp(*this); GoNext(); return tmp;}

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

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

   192       operator const InEdgeIterator ()

   193       {InEdgeIterator i; i.G=G;i.e=e;return i;}

   194       operator const BiEdgeIterator ()

   195       {BiEdgeIterator i; i.G=G;i.e=e;return i;}

   196       //operator const SymEdgeIterator();

   198       friend class Graph;

   199     };

   201     class SymEdgeIterator : public EdgeIterator

   202     {

   203       NodeIterator n;  // Itt ketszer van a G

   205     public:

   206       SymEdgeIterator() {}

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

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

   210       SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}

   211       SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}

   212       SymEdgeIterator &operator++() { return GoNext();}

   213       SymEdgeIterator operator++(int)

   214       {SymEdgeIterator tmp(*this); GoNext(); return tmp;}

   216       NodeIterator Anode() const {return n;}

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

   219       operator const InEdgeIterator ()

   220       {InEdgeIterator i; i.G=G;i.e=e;return i;}

   221       operator const OutEdgeIterator ()

   222       {OutEdgeIterator i; i.G=G;i.e=e;return i;}

   223       operator const BiEdgeIterator ()

   224       {BiEdgeIterator i; i.G=G;i.e=e;return i;}

   226       friend class Graph;

   227     };

   229     class AllEdgeIterator : public EdgeIterator

   230     {

   231       NodeIterator n;  // Itt ketszer van a G

   233     public:

   234       AllEdgeIterator() {}

   235       AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)

   236       {

   237 	e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;

   238       }

   240       AllEdgeIterator &GoNext()

   241       {

   242 	e=e->NextOut();

   243 	if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);

   244 	return *this;

   245       }

   246       AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}

   247       AllEdgeIterator &operator++() { return GoNext();}

   248       AllEdgeIterator operator++(int)

   249 	{AllEdgeIterator tmp(*this); GoNext(); return tmp;}

   252       NodeIterator Anode() const {return n;}

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

   255       operator const InEdgeIterator ()

   256       {InEdgeIterator i; i.G=G;i.e=e;return i;}

   257       operator const OutEdgeIterator ()

   258       {OutEdgeIterator i; i.G=G;i.e=e;return i;}

   259       operator const BiEdgeIterator ()

   260       {BiEdgeIterator i; i.G=G;i.e=e;return i;}

   262       friend class Graph;

   263     };

   265     typedef NodeIterator DeletingNodeIterator;

   266     typedef EdgeIterator DeletingEdgeIterator;

   267     typedef BiEdgeIterator DeletingBiEdgeIterator;

   268     typedef OutEdgeIterator DeletingOutEdgeIterator;

   269     typedef InEdgeIterator DeletingInEdgeIterator;

   270     typedef SymEdgeIterator DeletingSymEdgeIterator;

   272     const NodeIterator FirstNode()

   273     {

   274       NodeIterator i;

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

   276       return i;

   277     }

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

   281     void GetFirst(InEdgePoint &p,const NodePoint &n)

   282     { p=OldGraph<N,E>::FirstIn(n); }

   283     void GetFirst(OutEdgePoint &p,const NodePoint &n)

   284     { p=OldGraph<N,E>::FirstOut(n); }

   285     void GetFirst(SymEdgePoint &p,const NodePoint &n)

   286     { p=OldGraph<N,E>::FirstEdge(n); }

   287     void GetFirst(EdgePoint &p) //Vegigmegy mindenen

   288     { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}

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

   292     void GetFirst(InEdgeIterator &i,const NodeIterator &n)

   293     { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }

   294     void GetFirst(OutEdgeIterator &i,const NodeIterator &n)

   295     { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }

   296     void GetFirst(SymEdgeIterator &i,const NodeIterator &n)

   297     { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }

   298     void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen

   299     {

   300       i.G=this;

   301       GetFirst(i.n);

   302       i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;

   303     }

   307     //Vagy beginnode()?

   308     const DeletingEdgeIterator FirstOut(const NodeIterator &n)

   309     {

   310       EdgeIterator i;

   311       i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);

   312       return i;

   313     }

   314     const DeletingEdgeIterator FirstIn(const NodeIterator &n)

   315     {

   316       EdgeIterator i;

   317       i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);

   318       return i;

   319     }

   320     const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)

   321     {

   322       EdgeIterator i;

   323       i.G=n.G;i.n=n.n;

   324       i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);

   325       return i;

   326     }

   328     //    class FirstAnythingType;

   329     //    friend class FirstAnythingType;

   331     class FirstAnythingTypeNode

   332     {

   333       NodeIterator n;

   334     public:

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

   337       operator const InEdgeIterator () const

   338       {InEdgeIterator i; n.G->GetFirst(i,n);return i;}

   339       operator const OutEdgeIterator () const

   340       {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}

   341       operator const SymEdgeIterator () const

   342       {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}

   344       operator const InEdgePoint () const

   345       {InEdgePoint i; n.G->GetFirst(i,n);return i;}

   346       operator const OutEdgePoint () const

   347       {OutEdgePoint i; n.G->GetFirst(i,n);return i;}

   348       operator const SymEdgePoint () const

   349       {SymEdgePoint i; n.G->GetFirst(i,n);return i;}

   350     };

   352     class FirstAnythingType

   353     {

   354       Graph<N,E> *G;

   355     public:

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

   358       operator const AllEdgeIterator () const

   359       {AllEdgeIterator i; G->GetFirst(i);return i;}

   360       operator const EdgePoint () const

   361       {EdgePoint i; G->GetFirst(i);return i;}

   362       operator const NodeIterator () const

   363       {NodeIterator i; G->GetFirst(i);return i;}

   364       operator const NodePoint () const

   365       {NodePoint i; G->GetFirst(i);return i;}

   366     } _FST;

   368     //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}

   369     FirstAnythingTypeNode First(NodeIterator &i)

   370     {FirstAnythingTypeNode t(i); return t;}

   371     const FirstAnythingType &First() {return _FST;}

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

   375     DeletingNodeIterator AddNode()

   376     {

   377       DeletingNodeIterator i;

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

   379       return i;

   380     }

   381     DeletingEdgeIterator

   382     AddEdge(const NodeIterator from,const NodeIterator to)

   383     {

   384       DeletingEdgeIterator i;

   385       i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;

   386     }

   388     void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}

   389     void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}

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

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

   394     Graph() : _FST(this) {}

   396     // MAPS:

   397     template<class T> class NodeMap

   398     {

   399       Graph<N,E> *G;

   400       vector<T> map;

   402     public:

   403       typedef T value_type;

   404       void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}

   405       T Get(const NodeIterator i) const {return map[i.Index()];}

   406       T operator[](NodeIterator i) {return map[i.Index()];}

   408       void update() { map.resize(G->MaxNode());}

   410       NodeMap() {}

   411       void SetG(Graph<N,E> &Gr) { G=&Gr; update();}

   412     };

   414     template<class T> class EdgeMap

   415     {

   416       Graph<N,E> *G;

   417       vector<T> map;

   419     public:

   420       typedef T value_type;

   421       void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}

   422       T &Get(const NodeIterator i) {return map[i.Index()];}

   423       T &operator[](NodeIterator i) {return map[i.Index()];}

   425       void update()

   426 	{ map.resize(G->MaxEdge());}

   428       EdgeMap() {}

   429       void SetG(Graph<N,E> &Gr)

   430       { G=&Gr ;update();}

   432     };

   435     int MaxNode() { return OldGraph<N,E>::MaxNode();}

   436     int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}

   438   };

   440   /*   Ez itt a fiam kommentje:

   441        <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv

   442        vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz

   443        <<  < < <  < <  <   .cx..x.c.cc.c

   444        mcmn

   445   */

   447 }

   449 #endif

author	marci
	Fri, 16 Jan 2004 11:20:09 +0000
changeset 15	e41c71268807
parent 6	b63d1bc367f7
child 70	851ca9a60e90
permissions	-rw-r--r--