1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/graph.h Mon Mar 29 08:16:18 2004 +0000
1.3 @@ -0,0 +1,493 @@
1.4 +// -*-mode: c++; -*-
1.5 +#ifndef __GRAPH_H_
1.6 +#define __GRAPH_H_
1.7 +
1.8 +//inline void *operator new(size_t s, void *p) { return p; }
1.9 +#include <new>
1.10 +#include <vector>
1.11 +
1.12 +namespace NEGRO
1.13 +{
1.14 + using namespace std;
1.15 +
1.16 +#include "oldgraph.h"
1.17 +
1.18 + template <class N, class E> class Graph : protected OldGraph<N,E>
1.19 + {
1.20 + public:
1.21 + typedef E EdgeType;
1.22 + typedef N NodeType;
1.23 +
1.24 + class EdgeIt
1.25 + {
1.26 + public:
1.27 + NEGRO::EdgePoint e;
1.28 + bool valid() { return e; }
1.29 + };
1.30 +
1.31 + class InEdgeIt : public EdgeIt {};
1.32 + class OutEdgeIt : public EdgeIt {};
1.33 + class BiEdgeIt : public EdgeIt {};
1.34 + class SymEdgeIt : public EdgeIt {};
1.35 +
1.36 + typedef int NodeIt;
1.37 +
1.38 + typedef NodeIt EachNodeIt;
1.39 +
1.40 + class NodeIterator;
1.41 +
1.42 + class EdgeIterator;
1.43 + class InEdgeIterator;
1.44 + class OutEdgeIterator;
1.45 + class BiEdgeIterator;
1.46 + class SymEdgeIterator;
1.47 + class AllEdgeIterator;
1.48 +
1.49 + class FirstAnythingTypeNode; //Required by the unified First() function.
1.50 +
1.51 + friend class NodeIterator;
1.52 + friend class EdgeIterator;
1.53 + friend class InEdgeIterator;
1.54 + friend class OutEdgeIterator;
1.55 + friend class BiEdgeIterator;
1.56 + friend class SymEdgeIterator;
1.57 + friend class EachEdgeIterator;
1.58 +
1.59 + class NodeIterator
1.60 + {
1.61 + Graph<N,E> *G; //operator*() miatt kell!!!
1.62 + int n; //nem kellene, ha itt mutato lenne!!
1.63 + public:
1.64 +
1.65 + NodeIterator() {;}
1.66 + NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
1.67 + {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
1.68 + NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
1.69 +
1.70 + NodeIterator &goNext() { n=G->NextNode(n); return *this;}
1.71 + NodeIterator next() const { return NodeIterator(*this).goNext();}
1.72 + NodeIterator &operator++() { return goNext();}
1.73 + NodeIterator operator++(int)
1.74 + {NodeIterator tmp(*this); goNext(); return tmp;}
1.75 + bool valid() { return n!=INVALID; }
1.76 +
1.77 + N &operator*() const { return G->Data(n); }
1.78 + N *operator->() const { return &G->Data(n); }
1.79 +
1.80 + bool operator==(const NodeIterator &i) const {return n==i.n;}
1.81 + bool operator!=(const NodeIterator &i) const {return n!=i.n;}
1.82 +
1.83 + int index() const { return n; } //If the nodes are indexable
1.84 + friend class Graph;
1.85 + friend class EdgeIterator;
1.86 + friend class InEdgeIterator;
1.87 + friend class OutEdgeIterator;
1.88 + friend class BiEdgeIterator;
1.89 + friend class SymEdgeIterator;
1.90 + friend class EachEdgeIterator;
1.91 + friend class FirstAnythingTypeNode;
1.92 +
1.93 + //Nem kellene egy:
1.94 + // static NodeIterator &GetInvalid(); ?
1.95 + };
1.96 +
1.97 + class EdgeIterator
1.98 + {
1.99 +
1.100 + Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
1.101 + //Ez csak kicsit baj, de:
1.102 + // Meg a From() es To() miatt!!!!!!!!!!
1.103 +
1.104 + NEGRO::EdgeIt e;
1.105 +
1.106 + public:
1.107 + EdgeIterator() {;} //Kell inicializalni? (Nem)
1.108 + EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
1.109 +
1.110 + // Lehet, hogy ez a ketto nem kell!!!
1.111 +
1.112 + NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
1.113 + NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
1.114 + NodeIterator opposite(const NodeIterator &n) const
1.115 + {return n==tail()?head():tail();}
1.116 +
1.117 + bool valid() {return e;}
1.118 + E &operator*() const { return G->Data(e); }
1.119 + E *operator->() const { return &G->Data(e); }
1.120 +
1.121 + //operator const OutEdgeIterator ();
1.122 + //operator const InEdgeIterator ();
1.123 + //operator const BiEdgeIterator ();
1.124 + //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
1.125 +
1.126 + bool operator==(const EdgeIterator &i) const {return e==i.e;}
1.127 + bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
1.128 +
1.129 + int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
1.130 + //If the edges are indexable
1.131 +
1.132 + friend class Graph;
1.133 + friend class InEdgeIterator;
1.134 + friend class OutEdgeIterator;
1.135 + friend class BiEdgeIterator;
1.136 + friend class SymEdgeIterator;
1.137 + friend class EachEdgeIterator;
1.138 + };
1.139 +
1.140 + class BiEdgeIterator : public EdgeIterator
1.141 + {
1.142 + public:
1.143 + BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;}
1.144 + BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
1.145 + BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();}
1.146 + BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
1.147 +
1.148 + operator InEdgeIterator ()
1.149 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.150 + operator OutEdgeIterator ()
1.151 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.152 + //operator const SymEdgeIterator ()
1.153 +
1.154 + friend class Graph;
1.155 + };
1.156 +
1.157 + class InEdgeIterator : public EdgeIterator
1.158 + //Ne a BiEdgeIterator-bol szarmazzon?
1.159 + {
1.160 + public:
1.161 + InEdgeIterator() {}
1.162 + InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
1.163 + { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
1.164 +
1.165 + InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
1.166 + InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
1.167 + InEdgeIterator &operator++() { return GoNext();}
1.168 + InEdgeIterator operator++(int)
1.169 + {InEdgeIterator tmp(*this); GoNext(); return tmp;}
1.170 +
1.171 + operator const OutEdgeIterator ()
1.172 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.173 + operator const BiEdgeIterator ()
1.174 + {EdgeIterator i; i.G=G;i.e=e;return i;}
1.175 + // operator const SymEdgeIterator ();
1.176 +
1.177 + NodeIterator Anode() const {return To();}
1.178 + NodeIterator Bnode() const {return From();}
1.179 +
1.180 + friend class Graph;
1.181 + };
1.182 +
1.183 + class OutEdgeIterator : public EdgeIterator
1.184 + {
1.185 + public:
1.186 + OutEdgeIterator() {}
1.187 + OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
1.188 + { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
1.189 +
1.190 + OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
1.191 + OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
1.192 + OutEdgeIterator &operator++() { return goNext();}
1.193 + OutEdgeIterator operator++(int)
1.194 + {OutEdgeIterator tmp(*this); goNext(); return tmp;}
1.195 +
1.196 + NodeIterator aNode() const {return tail();}
1.197 + NodeIterator bNode() const {return head();}
1.198 +
1.199 + operator const InEdgeIterator ()
1.200 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.201 + operator const BiEdgeIterator ()
1.202 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
1.203 + //operator const SymEdgeIterator();
1.204 +
1.205 + friend class Graph;
1.206 + };
1.207 +
1.208 + class SymEdgeIterator : public EdgeIterator
1.209 + {
1.210 + NodeIterator n; // Itt ketszer van a G
1.211 +
1.212 + public:
1.213 + SymEdgeIterator() {}
1.214 + SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
1.215 + { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
1.216 +
1.217 + SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
1.218 + SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
1.219 + SymEdgeIterator &operator++() { return goNext();}
1.220 + SymEdgeIterator operator++(int)
1.221 + {SymEdgeIterator tmp(*this); goNext(); return tmp;}
1.222 +
1.223 + NodeIterator aNode() const {return n;}
1.224 + NodeIterator bNode() const {return n.n==tail().n?head():tail();}
1.225 +
1.226 + operator const InEdgeIterator ()
1.227 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.228 + operator const OutEdgeIterator ()
1.229 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.230 + operator const BiEdgeIterator ()
1.231 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
1.232 +
1.233 + friend class Graph;
1.234 + };
1.235 +
1.236 + class EachEdgeIterator : public EdgeIterator
1.237 + {
1.238 + NodeIterator n; // Itt ketszer van a G
1.239 +
1.240 + public:
1.241 + EachEdgeIterator() {}
1.242 + EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
1.243 + {
1.244 + e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
1.245 + }
1.246 +
1.247 + EachEdgeIterator &goNext()
1.248 + {
1.249 + e=e->NextOut();
1.250 + if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
1.251 + return *this;
1.252 + }
1.253 + EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
1.254 + EachEdgeIterator &operator++() { return goNext();}
1.255 + EachEdgeIterator operator++(int)
1.256 + {EachEdgeIterator tmp(*this); goNext(); return tmp;}
1.257 +
1.258 +
1.259 + NodeIterator aNode() const {return n;}
1.260 + NodeIterator bNode() const {return n.n==tail().n?head():tail();}
1.261 +
1.262 + operator const EdgeIterator ()
1.263 + {EdgeIterator i; i.G=G;i.e=e;return i;}
1.264 + operator const InEdgeIterator ()
1.265 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.266 + operator const OutEdgeIterator ()
1.267 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.268 + operator const BiEdgeIterator ()
1.269 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
1.270 +
1.271 + friend class Graph;
1.272 + };
1.273 +
1.274 + typedef NodeIterator DeletingNodeIterator;
1.275 + typedef EdgeIterator DeletingEdgeIterator;
1.276 + typedef BiEdgeIterator DeletingBiEdgeIterator;
1.277 + typedef OutEdgeIterator DeletingOutEdgeIterator;
1.278 + typedef InEdgeIterator DeletingInEdgeIterator;
1.279 + typedef SymEdgeIterator DeletingSymEdgeIterator;
1.280 +
1.281 + const NodeIterator firstNode()
1.282 + {
1.283 + NodeIterator i;
1.284 + i.G=this;i.n=OldGraph<N,E>::FirstNode();
1.285 + return i;
1.286 + }
1.287 +
1.288 + void getFirst(NodeIt &p) { p=OldGraph<N,E>::FirstNode(); }
1.289 +
1.290 + void getFirst(InEdgeIt &p,const NodeIt &n)
1.291 + { p=OldGraph<N,E>::FirstIn(n); }
1.292 + void getFirst(OutEdgeIt &p,const NodeIt &n)
1.293 + { p=OldGraph<N,E>::FirstOut(n); }
1.294 + void getFirst(SymEdgeIt &p,const NodeIt &n)
1.295 + { p=OldGraph<N,E>::FirstEdge(n); }
1.296 + void getFirst(EdgeIt &p) //Vegigmegy mindenen
1.297 + { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
1.298 +
1.299 + void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
1.300 +
1.301 + void getFirst(InEdgeIterator &i,const NodeIterator &n)
1.302 + { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
1.303 + void getFirst(OutEdgeIterator &i,const NodeIterator &n)
1.304 + { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
1.305 + void getFirst(SymEdgeIterator &i,const NodeIterator &n)
1.306 + { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
1.307 + void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
1.308 + {
1.309 + i.G=this;
1.310 + getFirst(i.n);
1.311 + i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
1.312 + }
1.313 +
1.314 +
1.315 +
1.316 + //Vagy beginnode()?
1.317 + const DeletingEdgeIterator firstOut(const NodeIterator &n)
1.318 + {
1.319 + EdgeIterator i;
1.320 + i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
1.321 + return i;
1.322 + }
1.323 + const DeletingEdgeIterator firstIn(const NodeIterator &n)
1.324 + {
1.325 + EdgeIterator i;
1.326 + i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
1.327 + return i;
1.328 + }
1.329 + const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
1.330 + {
1.331 + EdgeIterator i;
1.332 + i.G=n.G;i.n=n.n;
1.333 + i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
1.334 + return i;
1.335 + }
1.336 +
1.337 + // class FirstAnythingType;
1.338 + // friend class FirstAnythingType;
1.339 +
1.340 + class FirstAnythingTypeNode
1.341 + {
1.342 + NodeIterator n;
1.343 + public:
1.344 + FirstAnythingTypeNode(NodeIterator i) : n(i) {}
1.345 +
1.346 + operator const InEdgeIterator () const
1.347 + {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
1.348 + operator const OutEdgeIterator () const
1.349 + {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
1.350 + operator const SymEdgeIterator () const
1.351 + {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
1.352 +
1.353 + operator const InEdgeIt () const
1.354 + {InEdgeIt i; n.G->GetFirst(i,n);return i;}
1.355 + operator const OutEdgeIt () const
1.356 + {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
1.357 + operator const SymEdgeIt () const
1.358 + {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
1.359 + };
1.360 +
1.361 + class FirstAnythingType
1.362 + {
1.363 + Graph<N,E> *G;
1.364 + public:
1.365 + FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
1.366 +
1.367 + operator const EachEdgeIterator () const
1.368 + {EachEdgeIterator i; G->GetFirst(i);return i;}
1.369 + operator const EdgeIt () const
1.370 + {EdgeIt i; G->GetFirst(i);return i;}
1.371 + operator const NodeIterator () const
1.372 + {NodeIterator i; G->GetFirst(i);return i;}
1.373 + operator const NodeIt () const
1.374 + {NodeIt i; G->GetFirst(i);return i;}
1.375 + } _FST;
1.376 +
1.377 + // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
1.378 + FirstAnythingTypeNode first(NodeIterator &i)
1.379 + {FirstAnythingTypeNode t(i); return t;}
1.380 + const FirstAnythingType &first() {return _FST;}
1.381 +
1.382 + // LastNode() vagy endnode() stb. Nem kell?
1.383 +
1.384 + DeletingNodeIterator addNode()
1.385 + {
1.386 + DeletingNodeIterator i;
1.387 + i.G=this; i.n=OldGraph<N,E>::AddNode();
1.388 + return i;
1.389 + }
1.390 + DeletingEdgeIterator
1.391 + addEdge(const NodeIterator from,const NodeIterator to)
1.392 + {
1.393 + DeletingEdgeIterator i;
1.394 + i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
1.395 + }
1.396 +
1.397 + void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
1.398 + void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
1.399 +
1.400 + int nodeNum() { OldGraph<N,E>::NodeNum(); }
1.401 + void clean() { OldGraph<N,E>::Clean(); }
1.402 +
1.403 + Graph() : _FST(this) {}
1.404 +
1.405 + // MAPS:
1.406 + template<class T> class NodeMap
1.407 + {
1.408 + Graph<N,E> *G;
1.409 + vector<T> map;
1.410 +
1.411 + public:
1.412 + typedef T value_type;
1.413 + void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
1.414 + T get(const NodeIterator i) const {return map[i.Index()];}
1.415 + T operator[](NodeIterator i) {return map[i.Index()];}
1.416 +
1.417 + void update() { map.resize(G->MaxNode());}
1.418 +
1.419 + NodeMap() {}
1.420 + void setG(Graph<N,E> &Gr) { G=&Gr; update();}
1.421 + };
1.422 +
1.423 + template<class T> class EdgeMap
1.424 + {
1.425 + Graph<N,E> *G;
1.426 + vector<T> map;
1.427 +
1.428 + public:
1.429 + typedef T value_type;
1.430 + void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
1.431 + T get(const EdgeIterator i) const {return map[i.Index()];}
1.432 + T &operator[](EdgeIterator i) {return map[i.Index()];}
1.433 +
1.434 + void update()
1.435 + { map.resize(G->MaxEdge());}
1.436 +
1.437 + EdgeMap() {}
1.438 + void setG(Graph<N,E> &Gr)
1.439 + { G=&Gr ;update();}
1.440 +
1.441 + };
1.442 +
1.443 +
1.444 + int maxNode() { return OldGraph<N,E>::MaxNode();}
1.445 + int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
1.446 +
1.447 + };
1.448 +
1.449 + template <class G> //G is a graph-type
1.450 + class Path
1.451 + {
1.452 + public:
1.453 + typedef G Graph;
1.454 + typedef typename G::NodeIterator NodeIterator;
1.455 + typedef typename G::EdgeIterator EdgeIterator;
1.456 + typedef typename G::SymEdgeIterator SymEdgeIterator;
1.457 +
1.458 + private:
1.459 + std::vector<EdgeIterator> path;
1.460 + std::vector<bool> reversed;
1.461 +
1.462 + public:
1.463 + void setLength(int n) { path.resize(n);reversed.resize(n);}
1.464 + int getLength() { return path.size(); }
1.465 + EdgeIterator &operator[](int n) {return path[n];}
1.466 + NodeIterator GetNode(int n) // What about path of length 1?
1.467 + {
1.468 + return n?
1.469 + reversed[n-1]?path[n-1].tail():path[n-1].head():
1.470 + reversed[0]?path[0].head():path[0].tail();
1.471 + }
1.472 + void setRevert(int n,bool r=true) {reversed[n]=r;}
1.473 + void setEdge(int n,SymEdgeIterator i)
1.474 + {
1.475 + path[n]=i;
1.476 + reversed[n] = i.head()==i.aNode();
1.477 + }
1.478 + void setEdge(int n,EdgeIterator i,bool r)
1.479 + {
1.480 + path[n]=i;
1.481 + reversed[n] = r;
1.482 + }
1.483 +
1.484 + NodeIterator tail() { return getNode(0); }
1.485 + NodeIterator head() { return getNode(getLength()); }
1.486 + };
1.487 +
1.488 + /* Ez itt a fiam kommentje:
1.489 + <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
1.490 + vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
1.491 + << < < < < < < .cx..x.c.cc.c
1.492 + mcmn
1.493 + */
1.494 +};
1.495 +
1.496 +#endif