lemon-0.x: src/work/alpar/graph.h@89d5c283a485

     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 EdgeIt

    22     {

    23     public:

    24       NEGRO::EdgePoint e;

    25       bool valid() { return e; }

    26     };

    28     class InEdgeIt : public EdgeIt {};

    29     class OutEdgeIt : public EdgeIt {};

    30     class BiEdgeIt : public EdgeIt {};

    31     class SymEdgeIt : public EdgeIt {};

    33     typedef int NodeIt;

    35     typedef NodeIt EachNodeIt;

    37     class NodeIterator;

    39     class EdgeIterator;

    40     class InEdgeIterator;

    41     class OutEdgeIterator;

    42     class BiEdgeIterator;

    43     class SymEdgeIterator;

    44     class AllEdgeIterator;

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

    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;

    56     class NodeIterator

    57     {

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

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

    60     public:

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

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

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

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

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

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

    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;

    90       //Nem kellene egy:

    91       //      static NodeIterator &GetInvalid();  ?

    92     };

    94     class EdgeIterator

    95     {

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

    98       //Ez csak kicsit baj, de:

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

   101       NEGRO::EdgeIt e;

   103     public:

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

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

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

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

   114       bool valid() {return e;}

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

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

   118       //operator const OutEdgeIterator ();

   119       //operator const InEdgeIterator ();

   120       //operator const BiEdgeIterator ();

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

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

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

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

   127       //If the edges are indexable

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

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

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

   151       friend class Graph;

   152     };

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

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

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

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

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

   177       friend class Graph;

   178     };

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

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

   193       NodeIterator aNode() const {return tail();}

   194       NodeIterator bNode() const {return head();}

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

   202       friend class Graph;

   203     };

   205     class SymEdgeIterator : public EdgeIterator

   206     {

   207       NodeIterator n;  // Itt ketszer van a G

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

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

   220       NodeIterator aNode() const {return n;}

   221       NodeIterator bNode() const {return n.n==tail().n?head():tail();}

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

   230       friend class Graph;

   231     };

   233     class EachEdgeIterator : public EdgeIterator

   234     {

   235       NodeIterator n;  // Itt ketszer van a G

   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       }

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

   256       NodeIterator aNode() const {return n;}

   257       NodeIterator bNode() const {return n.n==tail().n?head():tail();}

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

   268       friend class Graph;

   269     };

   271     typedef NodeIterator DeletingNodeIterator;

   272     typedef EdgeIterator DeletingEdgeIterator;

   273     typedef BiEdgeIterator DeletingBiEdgeIterator;

   274     typedef OutEdgeIterator DeletingOutEdgeIterator;

   275     typedef InEdgeIterator DeletingInEdgeIterator;

   276     typedef SymEdgeIterator DeletingSymEdgeIterator;

   278     const NodeIterator firstNode()

   279     {

   280       NodeIterator i;

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

   282       return i;

   283     }

   285     void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }

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

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

   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     }

   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     }

   334     //    class FirstAnythingType;

   335     //    friend class FirstAnythingType;

   337     class FirstAnythingTypeNode

   338     {

   339       NodeIterator n;

   340     public:

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

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

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

   358     class FirstAnythingType

   359     {

   360       Graph<N,E> *G;

   361     public:

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

   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;

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

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

   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     }

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

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

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

   400     Graph() : _FST(this) {}

   402     // MAPS:

   403     template<class T> class NodeMap

   404     {

   405       Graph<N,E> *G;

   406       vector<T> map;

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

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

   416       NodeMap() {}

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

   418     };

   420     template<class T> class EdgeMap

   421     {

   422       Graph<N,E> *G;

   423       vector<T> map;

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

   431       void update()

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

   434       EdgeMap() {}

   435       void setG(Graph<N,E> &Gr)

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

   438     };

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

   442     int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}

   444   };

   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;

   455   private:

   456     std::vector<EdgeIterator> path;

   457     std::vector<bool> reversed;

   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     }

   481     NodeIterator tail() { return getNode(0); }

   482     NodeIterator head() { return getNode(getLength()); }

   483   };

   485   /*   Ez itt a fiam kommentje:

   486        <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv

   487        vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz

   488        <<  < < <  < <  <   .cx..x.c.cc.c

   489        mcmn

   490   */

   491 };

   493 #endif

author	marci
	Tue, 21 Sep 2004 21:10:26 +0000
changeset 893	89d5c283a485
parent 70	851ca9a60e90
child 986	e997802b855c
permissions	-rw-r--r--