1.1 --- a/src/work/alpar/graph.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,493 +0,0 @@
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 source() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
1.113 - NodeIterator target() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
1.114 - NodeIterator opposite(const NodeIterator &n) const
1.115 - {return n==source()?target():source();}
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 source();}
1.197 - NodeIterator bNode() const {return target();}
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==source().n?target():source();}
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==source().n?target():source();}
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].source():path[n-1].target():
1.470 - reversed[0]?path[0].target():path[0].source();
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.target()==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 source() { return getNode(0); }
1.485 - NodeIterator target() { 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