1.1 --- a/doc/Doxyfile Fri Mar 26 23:34:45 2004 +0000
1.2 +++ b/doc/Doxyfile Mon Mar 29 08:16:18 2004 +0000
1.3 @@ -391,10 +391,10 @@
1.4 # directories like "/usr/src/myproject". Separate the files or directories
1.5 # with spaces.
1.6
1.7 -INPUT = ../src/demo/alpar/emptygraph.h \
1.8 - ../src/doxy/invalid.h \
1.9 - ../src/demo/alpar/smart_graph.h \
1.10 - ../src/demo/alpar/mapskeleton.h \
1.11 +INPUT = ../src/include/skeletons/graph.h \
1.12 + ../src/include/invalid.h \
1.13 + ../src/include/smart_graph.h \
1.14 + ../src/include/skeletons/maps.h \
1.15 ../src/demo/alpar/dijkstra/dijkstra.h \
1.16 ../src/demo/alpar/dijkstra/bin_heap.hh \
1.17 ../src/demo/alpar/dijkstra/fib_heap.h \
2.1 --- a/src/include/graph.h Fri Mar 26 23:34:45 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,493 +0,0 @@
2.4 -// -*-mode: c++; -*-
2.5 -#ifndef __GRAPH_H_
2.6 -#define __GRAPH_H_
2.7 -
2.8 -//inline void *operator new(size_t s, void *p) { return p; }
2.9 -#include <new>
2.10 -#include <vector>
2.11 -
2.12 -namespace NEGRO
2.13 -{
2.14 - using namespace std;
2.15 -
2.16 -#include "oldgraph.h"
2.17 -
2.18 - template <class N, class E> class Graph : protected OldGraph<N,E>
2.19 - {
2.20 - public:
2.21 - typedef E EdgeType;
2.22 - typedef N NodeType;
2.23 -
2.24 - class EdgeIt
2.25 - {
2.26 - public:
2.27 - NEGRO::EdgePoint e;
2.28 - bool valid() { return e; }
2.29 - };
2.30 -
2.31 - class InEdgeIt : public EdgeIt {};
2.32 - class OutEdgeIt : public EdgeIt {};
2.33 - class BiEdgeIt : public EdgeIt {};
2.34 - class SymEdgeIt : public EdgeIt {};
2.35 -
2.36 - typedef int NodeIt;
2.37 -
2.38 - typedef NodeIt EachNodeIt;
2.39 -
2.40 - class NodeIterator;
2.41 -
2.42 - class EdgeIterator;
2.43 - class InEdgeIterator;
2.44 - class OutEdgeIterator;
2.45 - class BiEdgeIterator;
2.46 - class SymEdgeIterator;
2.47 - class AllEdgeIterator;
2.48 -
2.49 - class FirstAnythingTypeNode; //Required by the unified First() function.
2.50 -
2.51 - friend class NodeIterator;
2.52 - friend class EdgeIterator;
2.53 - friend class InEdgeIterator;
2.54 - friend class OutEdgeIterator;
2.55 - friend class BiEdgeIterator;
2.56 - friend class SymEdgeIterator;
2.57 - friend class EachEdgeIterator;
2.58 -
2.59 - class NodeIterator
2.60 - {
2.61 - Graph<N,E> *G; //operator*() miatt kell!!!
2.62 - int n; //nem kellene, ha itt mutato lenne!!
2.63 - public:
2.64 -
2.65 - NodeIterator() {;}
2.66 - NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
2.67 - {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
2.68 - NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
2.69 -
2.70 - NodeIterator &goNext() { n=G->NextNode(n); return *this;}
2.71 - NodeIterator next() const { return NodeIterator(*this).goNext();}
2.72 - NodeIterator &operator++() { return goNext();}
2.73 - NodeIterator operator++(int)
2.74 - {NodeIterator tmp(*this); goNext(); return tmp;}
2.75 - bool valid() { return n!=INVALID; }
2.76 -
2.77 - N &operator*() const { return G->Data(n); }
2.78 - N *operator->() const { return &G->Data(n); }
2.79 -
2.80 - bool operator==(const NodeIterator &i) const {return n==i.n;}
2.81 - bool operator!=(const NodeIterator &i) const {return n!=i.n;}
2.82 -
2.83 - int index() const { return n; } //If the nodes are indexable
2.84 - friend class Graph;
2.85 - friend class EdgeIterator;
2.86 - friend class InEdgeIterator;
2.87 - friend class OutEdgeIterator;
2.88 - friend class BiEdgeIterator;
2.89 - friend class SymEdgeIterator;
2.90 - friend class EachEdgeIterator;
2.91 - friend class FirstAnythingTypeNode;
2.92 -
2.93 - //Nem kellene egy:
2.94 - // static NodeIterator &GetInvalid(); ?
2.95 - };
2.96 -
2.97 - class EdgeIterator
2.98 - {
2.99 -
2.100 - Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
2.101 - //Ez csak kicsit baj, de:
2.102 - // Meg a From() es To() miatt!!!!!!!!!!
2.103 -
2.104 - NEGRO::EdgeIt e;
2.105 -
2.106 - public:
2.107 - EdgeIterator() {;} //Kell inicializalni? (Nem)
2.108 - EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
2.109 -
2.110 - // Lehet, hogy ez a ketto nem kell!!!
2.111 -
2.112 - NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
2.113 - NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
2.114 - NodeIterator opposite(const NodeIterator &n) const
2.115 - {return n==tail()?head():tail();}
2.116 -
2.117 - bool valid() {return e;}
2.118 - E &operator*() const { return G->Data(e); }
2.119 - E *operator->() const { return &G->Data(e); }
2.120 -
2.121 - //operator const OutEdgeIterator ();
2.122 - //operator const InEdgeIterator ();
2.123 - //operator const BiEdgeIterator ();
2.124 - //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
2.125 -
2.126 - bool operator==(const EdgeIterator &i) const {return e==i.e;}
2.127 - bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
2.128 -
2.129 - int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
2.130 - //If the edges are indexable
2.131 -
2.132 - friend class Graph;
2.133 - friend class InEdgeIterator;
2.134 - friend class OutEdgeIterator;
2.135 - friend class BiEdgeIterator;
2.136 - friend class SymEdgeIterator;
2.137 - friend class EachEdgeIterator;
2.138 - };
2.139 -
2.140 - class BiEdgeIterator : public EdgeIterator
2.141 - {
2.142 - public:
2.143 - BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;}
2.144 - BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
2.145 - BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();}
2.146 - BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
2.147 -
2.148 - operator InEdgeIterator ()
2.149 - {InEdgeIterator i; i.G=G;i.e=e;return i;}
2.150 - operator OutEdgeIterator ()
2.151 - {OutEdgeIterator i; i.G=G;i.e=e;return i;}
2.152 - //operator const SymEdgeIterator ()
2.153 -
2.154 - friend class Graph;
2.155 - };
2.156 -
2.157 - class InEdgeIterator : public EdgeIterator
2.158 - //Ne a BiEdgeIterator-bol szarmazzon?
2.159 - {
2.160 - public:
2.161 - InEdgeIterator() {}
2.162 - InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
2.163 - { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
2.164 -
2.165 - InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
2.166 - InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
2.167 - InEdgeIterator &operator++() { return GoNext();}
2.168 - InEdgeIterator operator++(int)
2.169 - {InEdgeIterator tmp(*this); GoNext(); return tmp;}
2.170 -
2.171 - operator const OutEdgeIterator ()
2.172 - {OutEdgeIterator i; i.G=G;i.e=e;return i;}
2.173 - operator const BiEdgeIterator ()
2.174 - {EdgeIterator i; i.G=G;i.e=e;return i;}
2.175 - // operator const SymEdgeIterator ();
2.176 -
2.177 - NodeIterator Anode() const {return To();}
2.178 - NodeIterator Bnode() const {return From();}
2.179 -
2.180 - friend class Graph;
2.181 - };
2.182 -
2.183 - class OutEdgeIterator : public EdgeIterator
2.184 - {
2.185 - public:
2.186 - OutEdgeIterator() {}
2.187 - OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
2.188 - { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
2.189 -
2.190 - OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
2.191 - OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
2.192 - OutEdgeIterator &operator++() { return goNext();}
2.193 - OutEdgeIterator operator++(int)
2.194 - {OutEdgeIterator tmp(*this); goNext(); return tmp;}
2.195 -
2.196 - NodeIterator aNode() const {return tail();}
2.197 - NodeIterator bNode() const {return head();}
2.198 -
2.199 - operator const InEdgeIterator ()
2.200 - {InEdgeIterator i; i.G=G;i.e=e;return i;}
2.201 - operator const BiEdgeIterator ()
2.202 - {BiEdgeIterator i; i.G=G;i.e=e;return i;}
2.203 - //operator const SymEdgeIterator();
2.204 -
2.205 - friend class Graph;
2.206 - };
2.207 -
2.208 - class SymEdgeIterator : public EdgeIterator
2.209 - {
2.210 - NodeIterator n; // Itt ketszer van a G
2.211 -
2.212 - public:
2.213 - SymEdgeIterator() {}
2.214 - SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
2.215 - { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
2.216 -
2.217 - SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
2.218 - SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
2.219 - SymEdgeIterator &operator++() { return goNext();}
2.220 - SymEdgeIterator operator++(int)
2.221 - {SymEdgeIterator tmp(*this); goNext(); return tmp;}
2.222 -
2.223 - NodeIterator aNode() const {return n;}
2.224 - NodeIterator bNode() const {return n.n==tail().n?head():tail();}
2.225 -
2.226 - operator const InEdgeIterator ()
2.227 - {InEdgeIterator i; i.G=G;i.e=e;return i;}
2.228 - operator const OutEdgeIterator ()
2.229 - {OutEdgeIterator i; i.G=G;i.e=e;return i;}
2.230 - operator const BiEdgeIterator ()
2.231 - {BiEdgeIterator i; i.G=G;i.e=e;return i;}
2.232 -
2.233 - friend class Graph;
2.234 - };
2.235 -
2.236 - class EachEdgeIterator : public EdgeIterator
2.237 - {
2.238 - NodeIterator n; // Itt ketszer van a G
2.239 -
2.240 - public:
2.241 - EachEdgeIterator() {}
2.242 - EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
2.243 - {
2.244 - e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
2.245 - }
2.246 -
2.247 - EachEdgeIterator &goNext()
2.248 - {
2.249 - e=e->NextOut();
2.250 - if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
2.251 - return *this;
2.252 - }
2.253 - EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
2.254 - EachEdgeIterator &operator++() { return goNext();}
2.255 - EachEdgeIterator operator++(int)
2.256 - {EachEdgeIterator tmp(*this); goNext(); return tmp;}
2.257 -
2.258 -
2.259 - NodeIterator aNode() const {return n;}
2.260 - NodeIterator bNode() const {return n.n==tail().n?head():tail();}
2.261 -
2.262 - operator const EdgeIterator ()
2.263 - {EdgeIterator i; i.G=G;i.e=e;return i;}
2.264 - operator const InEdgeIterator ()
2.265 - {InEdgeIterator i; i.G=G;i.e=e;return i;}
2.266 - operator const OutEdgeIterator ()
2.267 - {OutEdgeIterator i; i.G=G;i.e=e;return i;}
2.268 - operator const BiEdgeIterator ()
2.269 - {BiEdgeIterator i; i.G=G;i.e=e;return i;}
2.270 -
2.271 - friend class Graph;
2.272 - };
2.273 -
2.274 - typedef NodeIterator DeletingNodeIterator;
2.275 - typedef EdgeIterator DeletingEdgeIterator;
2.276 - typedef BiEdgeIterator DeletingBiEdgeIterator;
2.277 - typedef OutEdgeIterator DeletingOutEdgeIterator;
2.278 - typedef InEdgeIterator DeletingInEdgeIterator;
2.279 - typedef SymEdgeIterator DeletingSymEdgeIterator;
2.280 -
2.281 - const NodeIterator firstNode()
2.282 - {
2.283 - NodeIterator i;
2.284 - i.G=this;i.n=OldGraph<N,E>::FirstNode();
2.285 - return i;
2.286 - }
2.287 -
2.288 - void getFirst(NodeIt &p) { p=OldGraph<N,E>::FirstNode(); }
2.289 -
2.290 - void getFirst(InEdgeIt &p,const NodeIt &n)
2.291 - { p=OldGraph<N,E>::FirstIn(n); }
2.292 - void getFirst(OutEdgeIt &p,const NodeIt &n)
2.293 - { p=OldGraph<N,E>::FirstOut(n); }
2.294 - void getFirst(SymEdgeIt &p,const NodeIt &n)
2.295 - { p=OldGraph<N,E>::FirstEdge(n); }
2.296 - void getFirst(EdgeIt &p) //Vegigmegy mindenen
2.297 - { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
2.298 -
2.299 - void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
2.300 -
2.301 - void getFirst(InEdgeIterator &i,const NodeIterator &n)
2.302 - { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
2.303 - void getFirst(OutEdgeIterator &i,const NodeIterator &n)
2.304 - { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
2.305 - void getFirst(SymEdgeIterator &i,const NodeIterator &n)
2.306 - { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
2.307 - void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
2.308 - {
2.309 - i.G=this;
2.310 - getFirst(i.n);
2.311 - i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
2.312 - }
2.313 -
2.314 -
2.315 -
2.316 - //Vagy beginnode()?
2.317 - const DeletingEdgeIterator firstOut(const NodeIterator &n)
2.318 - {
2.319 - EdgeIterator i;
2.320 - i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
2.321 - return i;
2.322 - }
2.323 - const DeletingEdgeIterator firstIn(const NodeIterator &n)
2.324 - {
2.325 - EdgeIterator i;
2.326 - i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
2.327 - return i;
2.328 - }
2.329 - const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
2.330 - {
2.331 - EdgeIterator i;
2.332 - i.G=n.G;i.n=n.n;
2.333 - i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
2.334 - return i;
2.335 - }
2.336 -
2.337 - // class FirstAnythingType;
2.338 - // friend class FirstAnythingType;
2.339 -
2.340 - class FirstAnythingTypeNode
2.341 - {
2.342 - NodeIterator n;
2.343 - public:
2.344 - FirstAnythingTypeNode(NodeIterator i) : n(i) {}
2.345 -
2.346 - operator const InEdgeIterator () const
2.347 - {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
2.348 - operator const OutEdgeIterator () const
2.349 - {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
2.350 - operator const SymEdgeIterator () const
2.351 - {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
2.352 -
2.353 - operator const InEdgeIt () const
2.354 - {InEdgeIt i; n.G->GetFirst(i,n);return i;}
2.355 - operator const OutEdgeIt () const
2.356 - {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
2.357 - operator const SymEdgeIt () const
2.358 - {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
2.359 - };
2.360 -
2.361 - class FirstAnythingType
2.362 - {
2.363 - Graph<N,E> *G;
2.364 - public:
2.365 - FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
2.366 -
2.367 - operator const EachEdgeIterator () const
2.368 - {EachEdgeIterator i; G->GetFirst(i);return i;}
2.369 - operator const EdgeIt () const
2.370 - {EdgeIt i; G->GetFirst(i);return i;}
2.371 - operator const NodeIterator () const
2.372 - {NodeIterator i; G->GetFirst(i);return i;}
2.373 - operator const NodeIt () const
2.374 - {NodeIt i; G->GetFirst(i);return i;}
2.375 - } _FST;
2.376 -
2.377 - // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
2.378 - FirstAnythingTypeNode first(NodeIterator &i)
2.379 - {FirstAnythingTypeNode t(i); return t;}
2.380 - const FirstAnythingType &first() {return _FST;}
2.381 -
2.382 - // LastNode() vagy endnode() stb. Nem kell?
2.383 -
2.384 - DeletingNodeIterator addNode()
2.385 - {
2.386 - DeletingNodeIterator i;
2.387 - i.G=this; i.n=OldGraph<N,E>::AddNode();
2.388 - return i;
2.389 - }
2.390 - DeletingEdgeIterator
2.391 - addEdge(const NodeIterator from,const NodeIterator to)
2.392 - {
2.393 - DeletingEdgeIterator i;
2.394 - i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
2.395 - }
2.396 -
2.397 - void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
2.398 - void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
2.399 -
2.400 - int nodeNum() { OldGraph<N,E>::NodeNum(); }
2.401 - void clean() { OldGraph<N,E>::Clean(); }
2.402 -
2.403 - Graph() : _FST(this) {}
2.404 -
2.405 - // MAPS:
2.406 - template<class T> class NodeMap
2.407 - {
2.408 - Graph<N,E> *G;
2.409 - vector<T> map;
2.410 -
2.411 - public:
2.412 - typedef T value_type;
2.413 - void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
2.414 - T get(const NodeIterator i) const {return map[i.Index()];}
2.415 - T operator[](NodeIterator i) {return map[i.Index()];}
2.416 -
2.417 - void update() { map.resize(G->MaxNode());}
2.418 -
2.419 - NodeMap() {}
2.420 - void setG(Graph<N,E> &Gr) { G=&Gr; update();}
2.421 - };
2.422 -
2.423 - template<class T> class EdgeMap
2.424 - {
2.425 - Graph<N,E> *G;
2.426 - vector<T> map;
2.427 -
2.428 - public:
2.429 - typedef T value_type;
2.430 - void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
2.431 - T get(const EdgeIterator i) const {return map[i.Index()];}
2.432 - T &operator[](EdgeIterator i) {return map[i.Index()];}
2.433 -
2.434 - void update()
2.435 - { map.resize(G->MaxEdge());}
2.436 -
2.437 - EdgeMap() {}
2.438 - void setG(Graph<N,E> &Gr)
2.439 - { G=&Gr ;update();}
2.440 -
2.441 - };
2.442 -
2.443 -
2.444 - int maxNode() { return OldGraph<N,E>::MaxNode();}
2.445 - int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
2.446 -
2.447 - };
2.448 -
2.449 - template <class G> //G is a graph-type
2.450 - class Path
2.451 - {
2.452 - public:
2.453 - typedef G Graph;
2.454 - typedef typename G::NodeIterator NodeIterator;
2.455 - typedef typename G::EdgeIterator EdgeIterator;
2.456 - typedef typename G::SymEdgeIterator SymEdgeIterator;
2.457 -
2.458 - private:
2.459 - std::vector<EdgeIterator> path;
2.460 - std::vector<bool> reversed;
2.461 -
2.462 - public:
2.463 - void setLength(int n) { path.resize(n);reversed.resize(n);}
2.464 - int getLength() { return path.size(); }
2.465 - EdgeIterator &operator[](int n) {return path[n];}
2.466 - NodeIterator GetNode(int n) // What about path of length 1?
2.467 - {
2.468 - return n?
2.469 - reversed[n-1]?path[n-1].tail():path[n-1].head():
2.470 - reversed[0]?path[0].head():path[0].tail();
2.471 - }
2.472 - void setRevert(int n,bool r=true) {reversed[n]=r;}
2.473 - void setEdge(int n,SymEdgeIterator i)
2.474 - {
2.475 - path[n]=i;
2.476 - reversed[n] = i.head()==i.aNode();
2.477 - }
2.478 - void setEdge(int n,EdgeIterator i,bool r)
2.479 - {
2.480 - path[n]=i;
2.481 - reversed[n] = r;
2.482 - }
2.483 -
2.484 - NodeIterator tail() { return getNode(0); }
2.485 - NodeIterator head() { return getNode(getLength()); }
2.486 - };
2.487 -
2.488 - /* Ez itt a fiam kommentje:
2.489 - <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
2.490 - vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
2.491 - << < < < < < < .cx..x.c.cc.c
2.492 - mcmn
2.493 - */
2.494 -};
2.495 -
2.496 -#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/include/invalid.h Mon Mar 29 08:16:18 2004 +0000
3.3 @@ -0,0 +1,33 @@
3.4 +// -*- mode:C++ -*-
3.5 +
3.6 +#ifndef HUGO_INVALID_H
3.7 +#define HUGO_INVALID_H
3.8 +
3.9 +///\file
3.10 +///\brief Definition of INVALID.
3.11 +
3.12 +namespace hugo {
3.13 +
3.14 + /// Dummy type to make it easier to make invalid iterators.
3.15 +
3.16 + /// See \ref INVALID, how to use it.
3.17 +
3.18 + struct Invalid {};
3.19 +
3.20 + /// Invalid iterators.
3.21 +
3.22 + /// \ref Invalid is a global type that converts to each iterator
3.23 + /// in such a way that the value of the target iterator will be invalid.
3.24 +
3.25 + // It is also used to convert the \c INVALID constant to the
3.26 + // node iterator that makes is possible to write
3.27 +
3.28 + //extern Invalid INVALID;
3.29 +
3.30 + //const Invalid &INVALID = *(Invalid *)0;
3.31 + const Invalid INVALID = Invalid();
3.32 +
3.33 +};
3.34 +
3.35 +#endif
3.36 +
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/include/smart_graph.h Mon Mar 29 08:16:18 2004 +0000
4.3 @@ -0,0 +1,649 @@
4.4 +// -*- mode:C++ -*-
4.5 +
4.6 +#ifndef HUGO_SMART_GRAPH_H
4.7 +#define HUGO_SMART_GRAPH_H
4.8 +
4.9 +///\file
4.10 +///\brief SmartGraph and SymSmartGraph classes.
4.11 +
4.12 +#include <vector>
4.13 +#include <limits.h>
4.14 +
4.15 +#include "invalid.h"
4.16 +
4.17 +namespace hugo {
4.18 +
4.19 + class SymSmartGraph;
4.20 +
4.21 + ///A smart graph class.
4.22 +
4.23 + ///This is a simple and fast graph implementation.
4.24 + ///It is also quite memory efficient, but at the price
4.25 + ///that <b> it does not support node and edge deletion</b>.
4.26 + ///It conforms to the graph interface documented under
4.27 + ///the description of \ref GraphSkeleton.
4.28 + ///\sa \ref GraphSkeleton.
4.29 + class SmartGraph {
4.30 +
4.31 + struct NodeT
4.32 + {
4.33 + int first_in,first_out;
4.34 + NodeT() : first_in(-1), first_out(-1) {}
4.35 + };
4.36 + struct EdgeT
4.37 + {
4.38 + int head, tail, next_in, next_out;
4.39 + //FIXME: is this necessary?
4.40 + EdgeT() : next_in(-1), next_out(-1) {}
4.41 + };
4.42 +
4.43 + std::vector<NodeT> nodes;
4.44 +
4.45 + std::vector<EdgeT> edges;
4.46 +
4.47 + protected:
4.48 +
4.49 + template <typename Key> class DynMapBase
4.50 + {
4.51 + protected:
4.52 + const SmartGraph* G;
4.53 + public:
4.54 + virtual void add(const Key k) = NULL;
4.55 + virtual void erase(const Key k) = NULL;
4.56 + DynMapBase(const SmartGraph &_G) : G(&_G) {}
4.57 + virtual ~DynMapBase() {}
4.58 + friend class SmartGraph;
4.59 + };
4.60 +
4.61 + public:
4.62 + template <typename T> class EdgeMap;
4.63 + template <typename T> class EdgeMap;
4.64 +
4.65 + class Node;
4.66 + class Edge;
4.67 +
4.68 + // protected:
4.69 + // HELPME:
4.70 + protected:
4.71 + ///\bug It must be public because of SymEdgeMap.
4.72 + ///
4.73 + mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
4.74 + ///\bug It must be public because of SymEdgeMap.
4.75 + ///
4.76 + mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
4.77 +
4.78 + public:
4.79 +
4.80 + class NodeIt;
4.81 + class EdgeIt;
4.82 + class OutEdgeIt;
4.83 + class InEdgeIt;
4.84 +
4.85 + // class Node { int n; };
4.86 + // class NodeIt : public Node { };
4.87 + // class Edge { int n; };
4.88 + // class EdgeIt : public Edge {};
4.89 + // class OutEdgeIt : public Edge {};
4.90 + // class InEdgeIt : public Edge {};
4.91 + // class SymEdge;
4.92 +
4.93 + template <typename T> class NodeMap;
4.94 + template <typename T> class EdgeMap;
4.95 +
4.96 + public:
4.97 +
4.98 + /* default constructor */
4.99 +
4.100 + SmartGraph() : nodes(), edges() { }
4.101 + SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
4.102 +
4.103 + ~SmartGraph()
4.104 + {
4.105 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.106 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
4.107 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.108 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
4.109 + }
4.110 +
4.111 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
4.112 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
4.113 +
4.114 + ///\bug This function does something different than
4.115 + ///its name would suggests...
4.116 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
4.117 + ///\bug This function does something different than
4.118 + ///its name would suggests...
4.119 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
4.120 +
4.121 + Node tail(Edge e) const { return edges[e.n].tail; }
4.122 + Node head(Edge e) const { return edges[e.n].head; }
4.123 +
4.124 + // Marci
4.125 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
4.126 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
4.127 +// //Node aNode(const SymEdge& e) const { return e.aNode(); }
4.128 +
4.129 + // Marci
4.130 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
4.131 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
4.132 +// //Node bNode(const SymEdge& e) const { return e.bNode(); }
4.133 +
4.134 + NodeIt& first(NodeIt& v) const {
4.135 + v=NodeIt(*this); return v; }
4.136 + EdgeIt& first(EdgeIt& e) const {
4.137 + e=EdgeIt(*this); return e; }
4.138 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
4.139 + e=OutEdgeIt(*this,v); return e; }
4.140 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
4.141 + e=InEdgeIt(*this,v); return e; }
4.142 +
4.143 + template< typename It >
4.144 + It first() const { It e; first(e); return e; }
4.145 +
4.146 + template< typename It >
4.147 + It first(Node v) const { It e; first(e,v); return e; }
4.148 +
4.149 + bool valid(Edge e) const { return e.n!=-1; }
4.150 + bool valid(Node n) const { return n.n!=-1; }
4.151 +
4.152 + void setInvalid(Edge &e) { e.n=-1; }
4.153 + void setInvalid(Node &n) { n.n=-1; }
4.154 +
4.155 + template <typename It> It getNext(It it) const
4.156 + { It tmp(it); return next(tmp); }
4.157 +
4.158 + NodeIt& next(NodeIt& it) const {
4.159 + it.n=(it.n+2)%(nodes.size()+1)-1;
4.160 + return it;
4.161 + }
4.162 + OutEdgeIt& next(OutEdgeIt& it) const
4.163 + { it.n=edges[it.n].next_out; return it; }
4.164 + InEdgeIt& next(InEdgeIt& it) const
4.165 + { it.n=edges[it.n].next_in; return it; }
4.166 + EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
4.167 +
4.168 + int id(Node v) const { return v.n; }
4.169 + int id(Edge e) const { return e.n; }
4.170 +
4.171 + Node addNode() {
4.172 + Node n; n.n=nodes.size();
4.173 + nodes.push_back(NodeT()); //FIXME: Hmmm...
4.174 +
4.175 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.176 + i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
4.177 +
4.178 + return n;
4.179 + }
4.180 +
4.181 + Edge addEdge(Node u, Node v) {
4.182 + Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
4.183 + edges[e.n].tail=u.n; edges[e.n].head=v.n;
4.184 + edges[e.n].next_out=nodes[u.n].first_out;
4.185 + edges[e.n].next_in=nodes[v.n].first_in;
4.186 + nodes[u.n].first_out=nodes[v.n].first_in=e.n;
4.187 +
4.188 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.189 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
4.190 +
4.191 + return e;
4.192 + }
4.193 +
4.194 + void clear() {nodes.clear();edges.clear();}
4.195 +
4.196 + class Node {
4.197 + friend class SmartGraph;
4.198 + template <typename T> friend class NodeMap;
4.199 +
4.200 + friend class Edge;
4.201 + friend class OutEdgeIt;
4.202 + friend class InEdgeIt;
4.203 + friend class SymEdge;
4.204 +
4.205 + protected:
4.206 + int n;
4.207 + friend int SmartGraph::id(Node v) const;
4.208 + Node(int nn) {n=nn;}
4.209 + public:
4.210 + Node() {}
4.211 + Node (Invalid i) { n=-1; }
4.212 + bool operator==(const Node i) const {return n==i.n;}
4.213 + bool operator!=(const Node i) const {return n!=i.n;}
4.214 + bool operator<(const Node i) const {return n<i.n;}
4.215 + };
4.216 +
4.217 + class NodeIt : public Node {
4.218 + friend class SmartGraph;
4.219 + public:
4.220 + NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
4.221 + NodeIt() : Node() { }
4.222 + };
4.223 +
4.224 + class Edge {
4.225 + friend class SmartGraph;
4.226 + template <typename T> friend class EdgeMap;
4.227 +
4.228 + //template <typename T> friend class SymSmartGraph::SymEdgeMap;
4.229 + //friend Edge SymSmartGraph::opposite(Edge) const;
4.230 +
4.231 + friend class Node;
4.232 + friend class NodeIt;
4.233 + protected:
4.234 + int n;
4.235 + friend int SmartGraph::id(Edge e) const;
4.236 +
4.237 + Edge(int nn) {n=nn;}
4.238 + public:
4.239 + Edge() { }
4.240 + Edge (Invalid) { n=-1; }
4.241 + bool operator==(const Edge i) const {return n==i.n;}
4.242 + bool operator!=(const Edge i) const {return n!=i.n;}
4.243 + bool operator<(const Edge i) const {return n<i.n;}
4.244 + ///\bug This is a workaround until somebody tells me how to
4.245 + ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
4.246 + int &idref() {return n;}
4.247 + const int &idref() const {return n;}
4.248 + };
4.249 +
4.250 + class EdgeIt : public Edge {
4.251 + friend class SmartGraph;
4.252 + public:
4.253 + EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
4.254 + EdgeIt (Invalid i) : Edge(i) { }
4.255 + EdgeIt() : Edge() { }
4.256 + ///\bug This is a workaround until somebody tells me how to
4.257 + ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
4.258 + int &idref() {return n;}
4.259 + };
4.260 +
4.261 + class OutEdgeIt : public Edge {
4.262 + friend class SmartGraph;
4.263 + public:
4.264 + OutEdgeIt() : Edge() { }
4.265 + OutEdgeIt (Invalid i) : Edge(i) { }
4.266 +
4.267 + OutEdgeIt(const SmartGraph& G,const Node v)
4.268 + : Edge(G.nodes[v.n].first_out) {}
4.269 + };
4.270 +
4.271 + class InEdgeIt : public Edge {
4.272 + friend class SmartGraph;
4.273 + public:
4.274 + InEdgeIt() : Edge() { }
4.275 + InEdgeIt (Invalid i) : Edge(i) { }
4.276 + InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
4.277 + };
4.278 +
4.279 + // Map types
4.280 +
4.281 +// // Static Maps are not necessary.
4.282 +// template <typename T>
4.283 +// class NodeMap {
4.284 +// const SmartGraph& G;
4.285 +// std::vector<T> container;
4.286 +// public:
4.287 +// typedef T ValueType;
4.288 +// typedef Node KeyType;
4.289 +// NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
4.290 +// NodeMap(const SmartGraph& _G, T a) :
4.291 +// G(_G), container(G.maxNodeId(), a) { }
4.292 +// void set(Node n, T a) { container[n.n]=a; }
4.293 +// T get(Node n) const { return container[n.n]; }
4.294 +// T& operator[](Node n) { return container[n.n]; }
4.295 +// const T& operator[](Node n) const { return container[n.n]; }
4.296 +// void update() { container.resize(G.maxNodeId()); }
4.297 +// void update(T a) { container.resize(G.maxNodeId(), a); }
4.298 +// };
4.299 +
4.300 +// template <typename T>
4.301 +// class EdgeMap {
4.302 +// const SmartGraph& G;
4.303 +// std::vector<T> container;
4.304 +// public:
4.305 +// typedef T ValueType;
4.306 +// typedef Edge KeyType;
4.307 +// EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
4.308 +// EdgeMap(const SmartGraph& _G, T a) :
4.309 +// G(_G), container(G.maxEdgeId(), a) { }
4.310 +// void set(Edge e, T a) { container[e.n]=a; }
4.311 +// T get(Edge e) const { return container[e.n]; }
4.312 +// T& operator[](Edge e) { return container[e.n]; }
4.313 +// const T& operator[](Edge e) const { return container[e.n]; }
4.314 +// void update() { container.resize(G.maxEdgeId()); }
4.315 +// void update(T a) { container.resize(G.maxEdgeId(), a); }
4.316 +// };
4.317 +
4.318 + template <typename T> class NodeMap : public DynMapBase<Node>
4.319 + {
4.320 + std::vector<T> container;
4.321 +
4.322 + public:
4.323 + typedef T ValueType;
4.324 + typedef Node KeyType;
4.325 +
4.326 + NodeMap(const SmartGraph &_G) :
4.327 + DynMapBase<Node>(_G), container(_G.maxNodeId())
4.328 + {
4.329 + G->dyn_node_maps.push_back(this);
4.330 + }
4.331 + NodeMap(const SmartGraph &_G,const T &t) :
4.332 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
4.333 + {
4.334 + G->dyn_node_maps.push_back(this);
4.335 + }
4.336 +
4.337 + NodeMap(const NodeMap<T> &m) :
4.338 + DynMapBase<Node>(*m.G), container(m.container)
4.339 + {
4.340 + G->dyn_node_maps.push_back(this);
4.341 + }
4.342 +
4.343 + template<typename TT> friend class NodeMap;
4.344 +
4.345 + ///\todo It can copy between different types.
4.346 + ///
4.347 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
4.348 + DynMapBase<Node>(*m.G)
4.349 + {
4.350 + G->dyn_node_maps.push_back(this);
4.351 + typename std::vector<TT>::const_iterator i;
4.352 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.353 + i!=m.container.end();
4.354 + i++)
4.355 + container.push_back(*i);
4.356 + }
4.357 + ~NodeMap()
4.358 + {
4.359 + if(G) {
4.360 + std::vector<DynMapBase<Node>* >::iterator i;
4.361 + for(i=G->dyn_node_maps.begin();
4.362 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
4.363 + //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
4.364 + //A better way to do that: (Is this really important?)
4.365 + if(*i==this) {
4.366 + *i=G->dyn_node_maps.back();
4.367 + G->dyn_node_maps.pop_back();
4.368 + }
4.369 + }
4.370 + }
4.371 +
4.372 + void add(const Node k)
4.373 + {
4.374 + if(k.n>=int(container.size())) container.resize(k.n+1);
4.375 + }
4.376 +
4.377 + void erase(const Node) { }
4.378 +
4.379 + void set(Node n, T a) { container[n.n]=a; }
4.380 + //T get(Node n) const { return container[n.n]; }
4.381 + //Hajjaj:
4.382 + //T& operator[](Node n) { return container[n.n]; }
4.383 + typename std::vector<T>::reference
4.384 + operator[](Node n) { return container[n.n]; }
4.385 + //const T& operator[](Node n) const { return container[n.n]; }
4.386 + typename std::vector<T>::const_reference
4.387 + operator[](Node n) const { return container[n.n]; }
4.388 +
4.389 + ///\warning There is no safety check at all!
4.390 + ///Using operator = between maps attached to different graph may
4.391 + ///cause serious problem.
4.392 + ///\todo Is this really so?
4.393 + ///\todo It can copy between different types.
4.394 + const NodeMap<T>& operator=(const NodeMap<T> &m)
4.395 + {
4.396 + container = m.container;
4.397 + return *this;
4.398 + }
4.399 + template<typename TT>
4.400 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
4.401 + {
4.402 + copy(m.container.begin(), m.container.end(), container.begin());
4.403 + return *this;
4.404 + }
4.405 +
4.406 + void update() {} //Useless for DynMaps
4.407 + void update(T a) {} //Useless for DynMaps
4.408 + };
4.409 +
4.410 + template <typename T> class EdgeMap : public DynMapBase<Edge>
4.411 + {
4.412 + std::vector<T> container;
4.413 +
4.414 + public:
4.415 + typedef T ValueType;
4.416 + typedef Edge KeyType;
4.417 +
4.418 + EdgeMap(const SmartGraph &_G) :
4.419 + DynMapBase<Edge>(_G), container(_G.maxEdgeId())
4.420 + {
4.421 + //FIXME: What if there are empty Id's?
4.422 + //FIXME: Can I use 'this' in a constructor?
4.423 + G->dyn_edge_maps.push_back(this);
4.424 + }
4.425 + EdgeMap(const SmartGraph &_G,const T &t) :
4.426 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
4.427 + {
4.428 + G->dyn_edge_maps.push_back(this);
4.429 + }
4.430 + EdgeMap(const EdgeMap<T> &m) :
4.431 + DynMapBase<Edge>(*m.G), container(m.container)
4.432 + {
4.433 + G->dyn_node_maps.push_back(this);
4.434 + }
4.435 +
4.436 + template<typename TT> friend class EdgeMap;
4.437 +
4.438 + ///\todo It can copy between different types.
4.439 + ///
4.440 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
4.441 + DynMapBase<Edge>(*m.G)
4.442 + {
4.443 + G->dyn_node_maps.push_back(this);
4.444 + typename std::vector<TT>::const_iterator i;
4.445 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.446 + i!=m.container.end();
4.447 + i++)
4.448 + container.push_back(*i);
4.449 + }
4.450 + ~EdgeMap()
4.451 + {
4.452 + if(G) {
4.453 + std::vector<DynMapBase<Edge>* >::iterator i;
4.454 + for(i=G->dyn_edge_maps.begin();
4.455 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
4.456 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
4.457 + //A better way to do that: (Is this really important?)
4.458 + if(*i==this) {
4.459 + *i=G->dyn_edge_maps.back();
4.460 + G->dyn_edge_maps.pop_back();
4.461 + }
4.462 + }
4.463 + }
4.464 +
4.465 + void add(const Edge k)
4.466 + {
4.467 + if(k.n>=int(container.size())) container.resize(k.n+1);
4.468 + }
4.469 + void erase(const Edge) { }
4.470 +
4.471 + void set(Edge n, T a) { container[n.n]=a; }
4.472 + //T get(Edge n) const { return container[n.n]; }
4.473 + typename std::vector<T>::reference
4.474 + operator[](Edge n) { return container[n.n]; }
4.475 + typename std::vector<T>::const_reference
4.476 + operator[](Edge n) const { return container[n.n]; }
4.477 +
4.478 + ///\warning There is no safety check at all!
4.479 + ///Using operator = between maps attached to different graph may
4.480 + ///cause serious problem.
4.481 + ///\todo Is this really so?
4.482 + ///\todo It can copy between different types.
4.483 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
4.484 + {
4.485 + container = m.container;
4.486 + return *this;
4.487 + }
4.488 + template<typename TT>
4.489 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
4.490 + {
4.491 + copy(m.container.begin(), m.container.end(), container.begin());
4.492 + return *this;
4.493 + }
4.494 +
4.495 + void update() {} //Useless for DynMaps
4.496 + void update(T a) {} //Useless for DynMaps
4.497 + };
4.498 +
4.499 + };
4.500 +
4.501 + ///Graph for bidirectional edges.
4.502 +
4.503 + ///The purpose of this graph structure is to handle graphs
4.504 + ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
4.505 + ///of oppositely directed edges.
4.506 + ///There is a new edge map type called
4.507 + ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
4.508 + ///that complements this
4.509 + ///feature by
4.510 + ///storing shared values for the edge pairs. The usual
4.511 + ///\ref GraphSkeleton::EdgeMap "EdgeMap"
4.512 + ///can be used
4.513 + ///as well.
4.514 + ///
4.515 + ///The oppositely directed edge can also be obtained easily
4.516 + ///using \ref opposite.
4.517 + ///\warning It shares the similarity with \ref SmartGraph that
4.518 + ///it is not possible to delete edges or nodes from the graph.
4.519 + //\sa \ref SmartGraph.
4.520 +
4.521 + class SymSmartGraph : public SmartGraph
4.522 + {
4.523 + public:
4.524 + template<typename T> class SymEdgeMap;
4.525 + template<typename T> friend class SymEdgeMap;
4.526 +
4.527 + SymSmartGraph() : SmartGraph() { }
4.528 + SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
4.529 + Edge addEdge(Node u, Node v)
4.530 + {
4.531 + Edge e = SmartGraph::addEdge(u,v);
4.532 + SmartGraph::addEdge(v,u);
4.533 + return e;
4.534 + }
4.535 +
4.536 + ///The oppositely directed edge.
4.537 +
4.538 + ///Returns the oppositely directed
4.539 + ///pair of the edge \c e.
4.540 + Edge opposite(Edge e) const
4.541 + {
4.542 + Edge f;
4.543 + f.idref() = e.idref() - 2*(e.idref()%2) + 1;
4.544 + return f;
4.545 + }
4.546 +
4.547 + ///Common data storage for the edge pairs.
4.548 +
4.549 + ///This map makes it possible to store data shared by the oppositely
4.550 + ///directed pairs of edges.
4.551 + template <typename T> class SymEdgeMap : public DynMapBase<Edge>
4.552 + {
4.553 + std::vector<T> container;
4.554 +
4.555 + public:
4.556 + typedef T ValueType;
4.557 + typedef Edge KeyType;
4.558 +
4.559 + SymEdgeMap(const SymSmartGraph &_G) :
4.560 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
4.561 + {
4.562 + static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
4.563 + }
4.564 + SymEdgeMap(const SymSmartGraph &_G,const T &t) :
4.565 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
4.566 + {
4.567 + G->dyn_edge_maps.push_back(this);
4.568 + }
4.569 +
4.570 + SymEdgeMap(const SymEdgeMap<T> &m) :
4.571 + DynMapBase<SymEdge>(*m.G), container(m.container)
4.572 + {
4.573 + G->dyn_node_maps.push_back(this);
4.574 + }
4.575 +
4.576 + // template<typename TT> friend class SymEdgeMap;
4.577 +
4.578 + ///\todo It can copy between different types.
4.579 + ///
4.580 +
4.581 + template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
4.582 + DynMapBase<SymEdge>(*m.G)
4.583 + {
4.584 + G->dyn_node_maps.push_back(this);
4.585 + typename std::vector<TT>::const_iterator i;
4.586 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.587 + i!=m.container.end();
4.588 + i++)
4.589 + container.push_back(*i);
4.590 + }
4.591 +
4.592 + ~SymEdgeMap()
4.593 + {
4.594 + if(G) {
4.595 + std::vector<DynMapBase<Edge>* >::iterator i;
4.596 + for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
4.597 + i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
4.598 + && *i!=this; ++i) ;
4.599 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
4.600 + //A better way to do that: (Is this really important?)
4.601 + if(*i==this) {
4.602 + *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
4.603 + static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
4.604 + }
4.605 + }
4.606 + }
4.607 +
4.608 + void add(const Edge k)
4.609 + {
4.610 + if(!k.idref()%2&&k.idref()/2>=int(container.size()))
4.611 + container.resize(k.idref()/2+1);
4.612 + }
4.613 + void erase(const Edge k) { }
4.614 +
4.615 + void set(Edge n, T a) { container[n.idref()/2]=a; }
4.616 + //T get(Edge n) const { return container[n.idref()/2]; }
4.617 + typename std::vector<T>::reference
4.618 + operator[](Edge n) { return container[n.idref()/2]; }
4.619 + typename std::vector<T>::const_reference
4.620 + operator[](Edge n) const { return container[n.idref()/2]; }
4.621 +
4.622 + ///\warning There is no safety check at all!
4.623 + ///Using operator = between maps attached to different graph may
4.624 + ///cause serious problem.
4.625 + ///\todo Is this really so?
4.626 + ///\todo It can copy between different types.
4.627 + const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
4.628 + {
4.629 + container = m.container;
4.630 + return *this;
4.631 + }
4.632 + template<typename TT>
4.633 + const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
4.634 + {
4.635 + copy(m.container.begin(), m.container.end(), container.begin());
4.636 + return *this;
4.637 + }
4.638 +
4.639 + void update() {} //Useless for DynMaps
4.640 + void update(T a) {} //Useless for DynMaps
4.641 +
4.642 + };
4.643 +
4.644 + };
4.645 +
4.646 +
4.647 +} //namespace hugo
4.648 +
4.649 +
4.650 +
4.651 +
4.652 +#endif //SMART_GRAPH_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/alpar/graph.h Mon Mar 29 08:16:18 2004 +0000
5.3 @@ -0,0 +1,493 @@
5.4 +// -*-mode: c++; -*-
5.5 +#ifndef __GRAPH_H_
5.6 +#define __GRAPH_H_
5.7 +
5.8 +//inline void *operator new(size_t s, void *p) { return p; }
5.9 +#include <new>
5.10 +#include <vector>
5.11 +
5.12 +namespace NEGRO
5.13 +{
5.14 + using namespace std;
5.15 +
5.16 +#include "oldgraph.h"
5.17 +
5.18 + template <class N, class E> class Graph : protected OldGraph<N,E>
5.19 + {
5.20 + public:
5.21 + typedef E EdgeType;
5.22 + typedef N NodeType;
5.23 +
5.24 + class EdgeIt
5.25 + {
5.26 + public:
5.27 + NEGRO::EdgePoint e;
5.28 + bool valid() { return e; }
5.29 + };
5.30 +
5.31 + class InEdgeIt : public EdgeIt {};
5.32 + class OutEdgeIt : public EdgeIt {};
5.33 + class BiEdgeIt : public EdgeIt {};
5.34 + class SymEdgeIt : public EdgeIt {};
5.35 +
5.36 + typedef int NodeIt;
5.37 +
5.38 + typedef NodeIt EachNodeIt;
5.39 +
5.40 + class NodeIterator;
5.41 +
5.42 + class EdgeIterator;
5.43 + class InEdgeIterator;
5.44 + class OutEdgeIterator;
5.45 + class BiEdgeIterator;
5.46 + class SymEdgeIterator;
5.47 + class AllEdgeIterator;
5.48 +
5.49 + class FirstAnythingTypeNode; //Required by the unified First() function.
5.50 +
5.51 + friend class NodeIterator;
5.52 + friend class EdgeIterator;
5.53 + friend class InEdgeIterator;
5.54 + friend class OutEdgeIterator;
5.55 + friend class BiEdgeIterator;
5.56 + friend class SymEdgeIterator;
5.57 + friend class EachEdgeIterator;
5.58 +
5.59 + class NodeIterator
5.60 + {
5.61 + Graph<N,E> *G; //operator*() miatt kell!!!
5.62 + int n; //nem kellene, ha itt mutato lenne!!
5.63 + public:
5.64 +
5.65 + NodeIterator() {;}
5.66 + NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
5.67 + {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
5.68 + NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
5.69 +
5.70 + NodeIterator &goNext() { n=G->NextNode(n); return *this;}
5.71 + NodeIterator next() const { return NodeIterator(*this).goNext();}
5.72 + NodeIterator &operator++() { return goNext();}
5.73 + NodeIterator operator++(int)
5.74 + {NodeIterator tmp(*this); goNext(); return tmp;}
5.75 + bool valid() { return n!=INVALID; }
5.76 +
5.77 + N &operator*() const { return G->Data(n); }
5.78 + N *operator->() const { return &G->Data(n); }
5.79 +
5.80 + bool operator==(const NodeIterator &i) const {return n==i.n;}
5.81 + bool operator!=(const NodeIterator &i) const {return n!=i.n;}
5.82 +
5.83 + int index() const { return n; } //If the nodes are indexable
5.84 + friend class Graph;
5.85 + friend class EdgeIterator;
5.86 + friend class InEdgeIterator;
5.87 + friend class OutEdgeIterator;
5.88 + friend class BiEdgeIterator;
5.89 + friend class SymEdgeIterator;
5.90 + friend class EachEdgeIterator;
5.91 + friend class FirstAnythingTypeNode;
5.92 +
5.93 + //Nem kellene egy:
5.94 + // static NodeIterator &GetInvalid(); ?
5.95 + };
5.96 +
5.97 + class EdgeIterator
5.98 + {
5.99 +
5.100 + Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
5.101 + //Ez csak kicsit baj, de:
5.102 + // Meg a From() es To() miatt!!!!!!!!!!
5.103 +
5.104 + NEGRO::EdgeIt e;
5.105 +
5.106 + public:
5.107 + EdgeIterator() {;} //Kell inicializalni? (Nem)
5.108 + EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
5.109 +
5.110 + // Lehet, hogy ez a ketto nem kell!!!
5.111 +
5.112 + NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
5.113 + NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
5.114 + NodeIterator opposite(const NodeIterator &n) const
5.115 + {return n==tail()?head():tail();}
5.116 +
5.117 + bool valid() {return e;}
5.118 + E &operator*() const { return G->Data(e); }
5.119 + E *operator->() const { return &G->Data(e); }
5.120 +
5.121 + //operator const OutEdgeIterator ();
5.122 + //operator const InEdgeIterator ();
5.123 + //operator const BiEdgeIterator ();
5.124 + //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
5.125 +
5.126 + bool operator==(const EdgeIterator &i) const {return e==i.e;}
5.127 + bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
5.128 +
5.129 + int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
5.130 + //If the edges are indexable
5.131 +
5.132 + friend class Graph;
5.133 + friend class InEdgeIterator;
5.134 + friend class OutEdgeIterator;
5.135 + friend class BiEdgeIterator;
5.136 + friend class SymEdgeIterator;
5.137 + friend class EachEdgeIterator;
5.138 + };
5.139 +
5.140 + class BiEdgeIterator : public EdgeIterator
5.141 + {
5.142 + public:
5.143 + BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;}
5.144 + BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
5.145 + BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();}
5.146 + BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
5.147 +
5.148 + operator InEdgeIterator ()
5.149 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
5.150 + operator OutEdgeIterator ()
5.151 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
5.152 + //operator const SymEdgeIterator ()
5.153 +
5.154 + friend class Graph;
5.155 + };
5.156 +
5.157 + class InEdgeIterator : public EdgeIterator
5.158 + //Ne a BiEdgeIterator-bol szarmazzon?
5.159 + {
5.160 + public:
5.161 + InEdgeIterator() {}
5.162 + InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
5.163 + { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
5.164 +
5.165 + InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
5.166 + InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
5.167 + InEdgeIterator &operator++() { return GoNext();}
5.168 + InEdgeIterator operator++(int)
5.169 + {InEdgeIterator tmp(*this); GoNext(); return tmp;}
5.170 +
5.171 + operator const OutEdgeIterator ()
5.172 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
5.173 + operator const BiEdgeIterator ()
5.174 + {EdgeIterator i; i.G=G;i.e=e;return i;}
5.175 + // operator const SymEdgeIterator ();
5.176 +
5.177 + NodeIterator Anode() const {return To();}
5.178 + NodeIterator Bnode() const {return From();}
5.179 +
5.180 + friend class Graph;
5.181 + };
5.182 +
5.183 + class OutEdgeIterator : public EdgeIterator
5.184 + {
5.185 + public:
5.186 + OutEdgeIterator() {}
5.187 + OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
5.188 + { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
5.189 +
5.190 + OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
5.191 + OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
5.192 + OutEdgeIterator &operator++() { return goNext();}
5.193 + OutEdgeIterator operator++(int)
5.194 + {OutEdgeIterator tmp(*this); goNext(); return tmp;}
5.195 +
5.196 + NodeIterator aNode() const {return tail();}
5.197 + NodeIterator bNode() const {return head();}
5.198 +
5.199 + operator const InEdgeIterator ()
5.200 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
5.201 + operator const BiEdgeIterator ()
5.202 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
5.203 + //operator const SymEdgeIterator();
5.204 +
5.205 + friend class Graph;
5.206 + };
5.207 +
5.208 + class SymEdgeIterator : public EdgeIterator
5.209 + {
5.210 + NodeIterator n; // Itt ketszer van a G
5.211 +
5.212 + public:
5.213 + SymEdgeIterator() {}
5.214 + SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
5.215 + { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
5.216 +
5.217 + SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
5.218 + SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
5.219 + SymEdgeIterator &operator++() { return goNext();}
5.220 + SymEdgeIterator operator++(int)
5.221 + {SymEdgeIterator tmp(*this); goNext(); return tmp;}
5.222 +
5.223 + NodeIterator aNode() const {return n;}
5.224 + NodeIterator bNode() const {return n.n==tail().n?head():tail();}
5.225 +
5.226 + operator const InEdgeIterator ()
5.227 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
5.228 + operator const OutEdgeIterator ()
5.229 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
5.230 + operator const BiEdgeIterator ()
5.231 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
5.232 +
5.233 + friend class Graph;
5.234 + };
5.235 +
5.236 + class EachEdgeIterator : public EdgeIterator
5.237 + {
5.238 + NodeIterator n; // Itt ketszer van a G
5.239 +
5.240 + public:
5.241 + EachEdgeIterator() {}
5.242 + EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
5.243 + {
5.244 + e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
5.245 + }
5.246 +
5.247 + EachEdgeIterator &goNext()
5.248 + {
5.249 + e=e->NextOut();
5.250 + if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
5.251 + return *this;
5.252 + }
5.253 + EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
5.254 + EachEdgeIterator &operator++() { return goNext();}
5.255 + EachEdgeIterator operator++(int)
5.256 + {EachEdgeIterator tmp(*this); goNext(); return tmp;}
5.257 +
5.258 +
5.259 + NodeIterator aNode() const {return n;}
5.260 + NodeIterator bNode() const {return n.n==tail().n?head():tail();}
5.261 +
5.262 + operator const EdgeIterator ()
5.263 + {EdgeIterator i; i.G=G;i.e=e;return i;}
5.264 + operator const InEdgeIterator ()
5.265 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
5.266 + operator const OutEdgeIterator ()
5.267 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
5.268 + operator const BiEdgeIterator ()
5.269 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
5.270 +
5.271 + friend class Graph;
5.272 + };
5.273 +
5.274 + typedef NodeIterator DeletingNodeIterator;
5.275 + typedef EdgeIterator DeletingEdgeIterator;
5.276 + typedef BiEdgeIterator DeletingBiEdgeIterator;
5.277 + typedef OutEdgeIterator DeletingOutEdgeIterator;
5.278 + typedef InEdgeIterator DeletingInEdgeIterator;
5.279 + typedef SymEdgeIterator DeletingSymEdgeIterator;
5.280 +
5.281 + const NodeIterator firstNode()
5.282 + {
5.283 + NodeIterator i;
5.284 + i.G=this;i.n=OldGraph<N,E>::FirstNode();
5.285 + return i;
5.286 + }
5.287 +
5.288 + void getFirst(NodeIt &p) { p=OldGraph<N,E>::FirstNode(); }
5.289 +
5.290 + void getFirst(InEdgeIt &p,const NodeIt &n)
5.291 + { p=OldGraph<N,E>::FirstIn(n); }
5.292 + void getFirst(OutEdgeIt &p,const NodeIt &n)
5.293 + { p=OldGraph<N,E>::FirstOut(n); }
5.294 + void getFirst(SymEdgeIt &p,const NodeIt &n)
5.295 + { p=OldGraph<N,E>::FirstEdge(n); }
5.296 + void getFirst(EdgeIt &p) //Vegigmegy mindenen
5.297 + { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
5.298 +
5.299 + void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
5.300 +
5.301 + void getFirst(InEdgeIterator &i,const NodeIterator &n)
5.302 + { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
5.303 + void getFirst(OutEdgeIterator &i,const NodeIterator &n)
5.304 + { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
5.305 + void getFirst(SymEdgeIterator &i,const NodeIterator &n)
5.306 + { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
5.307 + void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
5.308 + {
5.309 + i.G=this;
5.310 + getFirst(i.n);
5.311 + i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
5.312 + }
5.313 +
5.314 +
5.315 +
5.316 + //Vagy beginnode()?
5.317 + const DeletingEdgeIterator firstOut(const NodeIterator &n)
5.318 + {
5.319 + EdgeIterator i;
5.320 + i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
5.321 + return i;
5.322 + }
5.323 + const DeletingEdgeIterator firstIn(const NodeIterator &n)
5.324 + {
5.325 + EdgeIterator i;
5.326 + i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
5.327 + return i;
5.328 + }
5.329 + const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
5.330 + {
5.331 + EdgeIterator i;
5.332 + i.G=n.G;i.n=n.n;
5.333 + i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
5.334 + return i;
5.335 + }
5.336 +
5.337 + // class FirstAnythingType;
5.338 + // friend class FirstAnythingType;
5.339 +
5.340 + class FirstAnythingTypeNode
5.341 + {
5.342 + NodeIterator n;
5.343 + public:
5.344 + FirstAnythingTypeNode(NodeIterator i) : n(i) {}
5.345 +
5.346 + operator const InEdgeIterator () const
5.347 + {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
5.348 + operator const OutEdgeIterator () const
5.349 + {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
5.350 + operator const SymEdgeIterator () const
5.351 + {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
5.352 +
5.353 + operator const InEdgeIt () const
5.354 + {InEdgeIt i; n.G->GetFirst(i,n);return i;}
5.355 + operator const OutEdgeIt () const
5.356 + {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
5.357 + operator const SymEdgeIt () const
5.358 + {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
5.359 + };
5.360 +
5.361 + class FirstAnythingType
5.362 + {
5.363 + Graph<N,E> *G;
5.364 + public:
5.365 + FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
5.366 +
5.367 + operator const EachEdgeIterator () const
5.368 + {EachEdgeIterator i; G->GetFirst(i);return i;}
5.369 + operator const EdgeIt () const
5.370 + {EdgeIt i; G->GetFirst(i);return i;}
5.371 + operator const NodeIterator () const
5.372 + {NodeIterator i; G->GetFirst(i);return i;}
5.373 + operator const NodeIt () const
5.374 + {NodeIt i; G->GetFirst(i);return i;}
5.375 + } _FST;
5.376 +
5.377 + // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
5.378 + FirstAnythingTypeNode first(NodeIterator &i)
5.379 + {FirstAnythingTypeNode t(i); return t;}
5.380 + const FirstAnythingType &first() {return _FST;}
5.381 +
5.382 + // LastNode() vagy endnode() stb. Nem kell?
5.383 +
5.384 + DeletingNodeIterator addNode()
5.385 + {
5.386 + DeletingNodeIterator i;
5.387 + i.G=this; i.n=OldGraph<N,E>::AddNode();
5.388 + return i;
5.389 + }
5.390 + DeletingEdgeIterator
5.391 + addEdge(const NodeIterator from,const NodeIterator to)
5.392 + {
5.393 + DeletingEdgeIterator i;
5.394 + i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
5.395 + }
5.396 +
5.397 + void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
5.398 + void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
5.399 +
5.400 + int nodeNum() { OldGraph<N,E>::NodeNum(); }
5.401 + void clean() { OldGraph<N,E>::Clean(); }
5.402 +
5.403 + Graph() : _FST(this) {}
5.404 +
5.405 + // MAPS:
5.406 + template<class T> class NodeMap
5.407 + {
5.408 + Graph<N,E> *G;
5.409 + vector<T> map;
5.410 +
5.411 + public:
5.412 + typedef T value_type;
5.413 + void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
5.414 + T get(const NodeIterator i) const {return map[i.Index()];}
5.415 + T operator[](NodeIterator i) {return map[i.Index()];}
5.416 +
5.417 + void update() { map.resize(G->MaxNode());}
5.418 +
5.419 + NodeMap() {}
5.420 + void setG(Graph<N,E> &Gr) { G=&Gr; update();}
5.421 + };
5.422 +
5.423 + template<class T> class EdgeMap
5.424 + {
5.425 + Graph<N,E> *G;
5.426 + vector<T> map;
5.427 +
5.428 + public:
5.429 + typedef T value_type;
5.430 + void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
5.431 + T get(const EdgeIterator i) const {return map[i.Index()];}
5.432 + T &operator[](EdgeIterator i) {return map[i.Index()];}
5.433 +
5.434 + void update()
5.435 + { map.resize(G->MaxEdge());}
5.436 +
5.437 + EdgeMap() {}
5.438 + void setG(Graph<N,E> &Gr)
5.439 + { G=&Gr ;update();}
5.440 +
5.441 + };
5.442 +
5.443 +
5.444 + int maxNode() { return OldGraph<N,E>::MaxNode();}
5.445 + int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
5.446 +
5.447 + };
5.448 +
5.449 + template <class G> //G is a graph-type
5.450 + class Path
5.451 + {
5.452 + public:
5.453 + typedef G Graph;
5.454 + typedef typename G::NodeIterator NodeIterator;
5.455 + typedef typename G::EdgeIterator EdgeIterator;
5.456 + typedef typename G::SymEdgeIterator SymEdgeIterator;
5.457 +
5.458 + private:
5.459 + std::vector<EdgeIterator> path;
5.460 + std::vector<bool> reversed;
5.461 +
5.462 + public:
5.463 + void setLength(int n) { path.resize(n);reversed.resize(n);}
5.464 + int getLength() { return path.size(); }
5.465 + EdgeIterator &operator[](int n) {return path[n];}
5.466 + NodeIterator GetNode(int n) // What about path of length 1?
5.467 + {
5.468 + return n?
5.469 + reversed[n-1]?path[n-1].tail():path[n-1].head():
5.470 + reversed[0]?path[0].head():path[0].tail();
5.471 + }
5.472 + void setRevert(int n,bool r=true) {reversed[n]=r;}
5.473 + void setEdge(int n,SymEdgeIterator i)
5.474 + {
5.475 + path[n]=i;
5.476 + reversed[n] = i.head()==i.aNode();
5.477 + }
5.478 + void setEdge(int n,EdgeIterator i,bool r)
5.479 + {
5.480 + path[n]=i;
5.481 + reversed[n] = r;
5.482 + }
5.483 +
5.484 + NodeIterator tail() { return getNode(0); }
5.485 + NodeIterator head() { return getNode(getLength()); }
5.486 + };
5.487 +
5.488 + /* Ez itt a fiam kommentje:
5.489 + <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
5.490 + vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
5.491 + << < < < < < < .cx..x.c.cc.c
5.492 + mcmn
5.493 + */
5.494 +};
5.495 +
5.496 +#endif
6.1 --- a/src/work/alpar/invalid.h Fri Mar 26 23:34:45 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,33 +0,0 @@
6.4 -// -*- mode:C++ -*-
6.5 -
6.6 -#ifndef HUGO_INVALID_H
6.7 -#define HUGO_INVALID_H
6.8 -
6.9 -///\file
6.10 -///\brief Definition of INVALID.
6.11 -
6.12 -namespace hugo {
6.13 -
6.14 - /// Dummy type to make it easier to make invalid iterators.
6.15 -
6.16 - /// See \ref INVALID, how to use it.
6.17 -
6.18 - struct Invalid {};
6.19 -
6.20 - /// Invalid iterators.
6.21 -
6.22 - /// \ref Invalid is a global type that converts to each iterator
6.23 - /// in such a way that the value of the target iterator will be invalid.
6.24 -
6.25 - // It is also used to convert the \c INVALID constant to the
6.26 - // node iterator that makes is possible to write
6.27 -
6.28 - //extern Invalid INVALID;
6.29 -
6.30 - //const Invalid &INVALID = *(Invalid *)0;
6.31 - const Invalid INVALID = Invalid();
6.32 -
6.33 -};
6.34 -
6.35 -#endif
6.36 -
7.1 --- a/src/work/alpar/smart_graph.h Fri Mar 26 23:34:45 2004 +0000
7.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
7.3 @@ -1,649 +0,0 @@
7.4 -// -*- mode:C++ -*-
7.5 -
7.6 -#ifndef HUGO_SMART_GRAPH_H
7.7 -#define HUGO_SMART_GRAPH_H
7.8 -
7.9 -///\file
7.10 -///\brief SmartGraph and SymSmartGraph classes.
7.11 -
7.12 -#include <vector>
7.13 -#include <limits.h>
7.14 -
7.15 -#include <invalid.h>
7.16 -
7.17 -namespace hugo {
7.18 -
7.19 - class SymSmartGraph;
7.20 -
7.21 - ///A smart graph class.
7.22 -
7.23 - ///This is a simple and fast graph implementation.
7.24 - ///It is also quite memory efficient, but at the price
7.25 - ///that <b> it does not support node and edge deletion</b>.
7.26 - ///It conforms to the graph interface documented under
7.27 - ///the description of \ref GraphSkeleton.
7.28 - ///\sa \ref GraphSkeleton.
7.29 - class SmartGraph {
7.30 -
7.31 - struct NodeT
7.32 - {
7.33 - int first_in,first_out;
7.34 - NodeT() : first_in(-1), first_out(-1) {}
7.35 - };
7.36 - struct EdgeT
7.37 - {
7.38 - int head, tail, next_in, next_out;
7.39 - //FIXME: is this necessary?
7.40 - EdgeT() : next_in(-1), next_out(-1) {}
7.41 - };
7.42 -
7.43 - std::vector<NodeT> nodes;
7.44 -
7.45 - std::vector<EdgeT> edges;
7.46 -
7.47 - protected:
7.48 -
7.49 - template <typename Key> class DynMapBase
7.50 - {
7.51 - protected:
7.52 - const SmartGraph* G;
7.53 - public:
7.54 - virtual void add(const Key k) = NULL;
7.55 - virtual void erase(const Key k) = NULL;
7.56 - DynMapBase(const SmartGraph &_G) : G(&_G) {}
7.57 - virtual ~DynMapBase() {}
7.58 - friend class SmartGraph;
7.59 - };
7.60 -
7.61 - public:
7.62 - template <typename T> class EdgeMap;
7.63 - template <typename T> class EdgeMap;
7.64 -
7.65 - class Node;
7.66 - class Edge;
7.67 -
7.68 - // protected:
7.69 - // HELPME:
7.70 - protected:
7.71 - ///\bug It must be public because of SymEdgeMap.
7.72 - ///
7.73 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
7.74 - ///\bug It must be public because of SymEdgeMap.
7.75 - ///
7.76 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
7.77 -
7.78 - public:
7.79 -
7.80 - class NodeIt;
7.81 - class EdgeIt;
7.82 - class OutEdgeIt;
7.83 - class InEdgeIt;
7.84 -
7.85 - // class Node { int n; };
7.86 - // class NodeIt : public Node { };
7.87 - // class Edge { int n; };
7.88 - // class EdgeIt : public Edge {};
7.89 - // class OutEdgeIt : public Edge {};
7.90 - // class InEdgeIt : public Edge {};
7.91 - // class SymEdge;
7.92 -
7.93 - template <typename T> class NodeMap;
7.94 - template <typename T> class EdgeMap;
7.95 -
7.96 - public:
7.97 -
7.98 - /* default constructor */
7.99 -
7.100 - SmartGraph() : nodes(), edges() { }
7.101 - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
7.102 -
7.103 - ~SmartGraph()
7.104 - {
7.105 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
7.106 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
7.107 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
7.108 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
7.109 - }
7.110 -
7.111 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
7.112 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
7.113 -
7.114 - ///\bug This function does something different than
7.115 - ///its name would suggests...
7.116 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
7.117 - ///\bug This function does something different than
7.118 - ///its name would suggests...
7.119 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
7.120 -
7.121 - Node tail(Edge e) const { return edges[e.n].tail; }
7.122 - Node head(Edge e) const { return edges[e.n].head; }
7.123 -
7.124 - // Marci
7.125 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
7.126 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
7.127 -// //Node aNode(const SymEdge& e) const { return e.aNode(); }
7.128 -
7.129 - // Marci
7.130 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
7.131 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
7.132 -// //Node bNode(const SymEdge& e) const { return e.bNode(); }
7.133 -
7.134 - NodeIt& first(NodeIt& v) const {
7.135 - v=NodeIt(*this); return v; }
7.136 - EdgeIt& first(EdgeIt& e) const {
7.137 - e=EdgeIt(*this); return e; }
7.138 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
7.139 - e=OutEdgeIt(*this,v); return e; }
7.140 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
7.141 - e=InEdgeIt(*this,v); return e; }
7.142 -
7.143 - template< typename It >
7.144 - It first() const { It e; first(e); return e; }
7.145 -
7.146 - template< typename It >
7.147 - It first(Node v) const { It e; first(e,v); return e; }
7.148 -
7.149 - bool valid(Edge e) const { return e.n!=-1; }
7.150 - bool valid(Node n) const { return n.n!=-1; }
7.151 -
7.152 - void setInvalid(Edge &e) { e.n=-1; }
7.153 - void setInvalid(Node &n) { n.n=-1; }
7.154 -
7.155 - template <typename It> It getNext(It it) const
7.156 - { It tmp(it); return next(tmp); }
7.157 -
7.158 - NodeIt& next(NodeIt& it) const {
7.159 - it.n=(it.n+2)%(nodes.size()+1)-1;
7.160 - return it;
7.161 - }
7.162 - OutEdgeIt& next(OutEdgeIt& it) const
7.163 - { it.n=edges[it.n].next_out; return it; }
7.164 - InEdgeIt& next(InEdgeIt& it) const
7.165 - { it.n=edges[it.n].next_in; return it; }
7.166 - EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
7.167 -
7.168 - int id(Node v) const { return v.n; }
7.169 - int id(Edge e) const { return e.n; }
7.170 -
7.171 - Node addNode() {
7.172 - Node n; n.n=nodes.size();
7.173 - nodes.push_back(NodeT()); //FIXME: Hmmm...
7.174 -
7.175 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
7.176 - i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
7.177 -
7.178 - return n;
7.179 - }
7.180 -
7.181 - Edge addEdge(Node u, Node v) {
7.182 - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
7.183 - edges[e.n].tail=u.n; edges[e.n].head=v.n;
7.184 - edges[e.n].next_out=nodes[u.n].first_out;
7.185 - edges[e.n].next_in=nodes[v.n].first_in;
7.186 - nodes[u.n].first_out=nodes[v.n].first_in=e.n;
7.187 -
7.188 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
7.189 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
7.190 -
7.191 - return e;
7.192 - }
7.193 -
7.194 - void clear() {nodes.clear();edges.clear();}
7.195 -
7.196 - class Node {
7.197 - friend class SmartGraph;
7.198 - template <typename T> friend class NodeMap;
7.199 -
7.200 - friend class Edge;
7.201 - friend class OutEdgeIt;
7.202 - friend class InEdgeIt;
7.203 - friend class SymEdge;
7.204 -
7.205 - protected:
7.206 - int n;
7.207 - friend int SmartGraph::id(Node v) const;
7.208 - Node(int nn) {n=nn;}
7.209 - public:
7.210 - Node() {}
7.211 - Node (Invalid i) { n=-1; }
7.212 - bool operator==(const Node i) const {return n==i.n;}
7.213 - bool operator!=(const Node i) const {return n!=i.n;}
7.214 - bool operator<(const Node i) const {return n<i.n;}
7.215 - };
7.216 -
7.217 - class NodeIt : public Node {
7.218 - friend class SmartGraph;
7.219 - public:
7.220 - NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
7.221 - NodeIt() : Node() { }
7.222 - };
7.223 -
7.224 - class Edge {
7.225 - friend class SmartGraph;
7.226 - template <typename T> friend class EdgeMap;
7.227 -
7.228 - //template <typename T> friend class SymSmartGraph::SymEdgeMap;
7.229 - //friend Edge SymSmartGraph::opposite(Edge) const;
7.230 -
7.231 - friend class Node;
7.232 - friend class NodeIt;
7.233 - protected:
7.234 - int n;
7.235 - friend int SmartGraph::id(Edge e) const;
7.236 -
7.237 - Edge(int nn) {n=nn;}
7.238 - public:
7.239 - Edge() { }
7.240 - Edge (Invalid) { n=-1; }
7.241 - bool operator==(const Edge i) const {return n==i.n;}
7.242 - bool operator!=(const Edge i) const {return n!=i.n;}
7.243 - bool operator<(const Edge i) const {return n<i.n;}
7.244 - ///\bug This is a workaround until somebody tells me how to
7.245 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
7.246 - int &idref() {return n;}
7.247 - const int &idref() const {return n;}
7.248 - };
7.249 -
7.250 - class EdgeIt : public Edge {
7.251 - friend class SmartGraph;
7.252 - public:
7.253 - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
7.254 - EdgeIt (Invalid i) : Edge(i) { }
7.255 - EdgeIt() : Edge() { }
7.256 - ///\bug This is a workaround until somebody tells me how to
7.257 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
7.258 - int &idref() {return n;}
7.259 - };
7.260 -
7.261 - class OutEdgeIt : public Edge {
7.262 - friend class SmartGraph;
7.263 - public:
7.264 - OutEdgeIt() : Edge() { }
7.265 - OutEdgeIt (Invalid i) : Edge(i) { }
7.266 -
7.267 - OutEdgeIt(const SmartGraph& G,const Node v)
7.268 - : Edge(G.nodes[v.n].first_out) {}
7.269 - };
7.270 -
7.271 - class InEdgeIt : public Edge {
7.272 - friend class SmartGraph;
7.273 - public:
7.274 - InEdgeIt() : Edge() { }
7.275 - InEdgeIt (Invalid i) : Edge(i) { }
7.276 - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
7.277 - };
7.278 -
7.279 - // Map types
7.280 -
7.281 -// // Static Maps are not necessary.
7.282 -// template <typename T>
7.283 -// class NodeMap {
7.284 -// const SmartGraph& G;
7.285 -// std::vector<T> container;
7.286 -// public:
7.287 -// typedef T ValueType;
7.288 -// typedef Node KeyType;
7.289 -// NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
7.290 -// NodeMap(const SmartGraph& _G, T a) :
7.291 -// G(_G), container(G.maxNodeId(), a) { }
7.292 -// void set(Node n, T a) { container[n.n]=a; }
7.293 -// T get(Node n) const { return container[n.n]; }
7.294 -// T& operator[](Node n) { return container[n.n]; }
7.295 -// const T& operator[](Node n) const { return container[n.n]; }
7.296 -// void update() { container.resize(G.maxNodeId()); }
7.297 -// void update(T a) { container.resize(G.maxNodeId(), a); }
7.298 -// };
7.299 -
7.300 -// template <typename T>
7.301 -// class EdgeMap {
7.302 -// const SmartGraph& G;
7.303 -// std::vector<T> container;
7.304 -// public:
7.305 -// typedef T ValueType;
7.306 -// typedef Edge KeyType;
7.307 -// EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
7.308 -// EdgeMap(const SmartGraph& _G, T a) :
7.309 -// G(_G), container(G.maxEdgeId(), a) { }
7.310 -// void set(Edge e, T a) { container[e.n]=a; }
7.311 -// T get(Edge e) const { return container[e.n]; }
7.312 -// T& operator[](Edge e) { return container[e.n]; }
7.313 -// const T& operator[](Edge e) const { return container[e.n]; }
7.314 -// void update() { container.resize(G.maxEdgeId()); }
7.315 -// void update(T a) { container.resize(G.maxEdgeId(), a); }
7.316 -// };
7.317 -
7.318 - template <typename T> class NodeMap : public DynMapBase<Node>
7.319 - {
7.320 - std::vector<T> container;
7.321 -
7.322 - public:
7.323 - typedef T ValueType;
7.324 - typedef Node KeyType;
7.325 -
7.326 - NodeMap(const SmartGraph &_G) :
7.327 - DynMapBase<Node>(_G), container(_G.maxNodeId())
7.328 - {
7.329 - G->dyn_node_maps.push_back(this);
7.330 - }
7.331 - NodeMap(const SmartGraph &_G,const T &t) :
7.332 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
7.333 - {
7.334 - G->dyn_node_maps.push_back(this);
7.335 - }
7.336 -
7.337 - NodeMap(const NodeMap<T> &m) :
7.338 - DynMapBase<Node>(*m.G), container(m.container)
7.339 - {
7.340 - G->dyn_node_maps.push_back(this);
7.341 - }
7.342 -
7.343 - template<typename TT> friend class NodeMap;
7.344 -
7.345 - ///\todo It can copy between different types.
7.346 - ///
7.347 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
7.348 - DynMapBase<Node>(*m.G)
7.349 - {
7.350 - G->dyn_node_maps.push_back(this);
7.351 - typename std::vector<TT>::const_iterator i;
7.352 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
7.353 - i!=m.container.end();
7.354 - i++)
7.355 - container.push_back(*i);
7.356 - }
7.357 - ~NodeMap()
7.358 - {
7.359 - if(G) {
7.360 - std::vector<DynMapBase<Node>* >::iterator i;
7.361 - for(i=G->dyn_node_maps.begin();
7.362 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
7.363 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
7.364 - //A better way to do that: (Is this really important?)
7.365 - if(*i==this) {
7.366 - *i=G->dyn_node_maps.back();
7.367 - G->dyn_node_maps.pop_back();
7.368 - }
7.369 - }
7.370 - }
7.371 -
7.372 - void add(const Node k)
7.373 - {
7.374 - if(k.n>=int(container.size())) container.resize(k.n+1);
7.375 - }
7.376 -
7.377 - void erase(const Node) { }
7.378 -
7.379 - void set(Node n, T a) { container[n.n]=a; }
7.380 - //T get(Node n) const { return container[n.n]; }
7.381 - //Hajjaj:
7.382 - //T& operator[](Node n) { return container[n.n]; }
7.383 - typename std::vector<T>::reference
7.384 - operator[](Node n) { return container[n.n]; }
7.385 - //const T& operator[](Node n) const { return container[n.n]; }
7.386 - typename std::vector<T>::const_reference
7.387 - operator[](Node n) const { return container[n.n]; }
7.388 -
7.389 - ///\warning There is no safety check at all!
7.390 - ///Using operator = between maps attached to different graph may
7.391 - ///cause serious problem.
7.392 - ///\todo Is this really so?
7.393 - ///\todo It can copy between different types.
7.394 - const NodeMap<T>& operator=(const NodeMap<T> &m)
7.395 - {
7.396 - container = m.container;
7.397 - return *this;
7.398 - }
7.399 - template<typename TT>
7.400 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
7.401 - {
7.402 - copy(m.container.begin(), m.container.end(), container.begin());
7.403 - return *this;
7.404 - }
7.405 -
7.406 - void update() {} //Useless for DynMaps
7.407 - void update(T a) {} //Useless for DynMaps
7.408 - };
7.409 -
7.410 - template <typename T> class EdgeMap : public DynMapBase<Edge>
7.411 - {
7.412 - std::vector<T> container;
7.413 -
7.414 - public:
7.415 - typedef T ValueType;
7.416 - typedef Edge KeyType;
7.417 -
7.418 - EdgeMap(const SmartGraph &_G) :
7.419 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
7.420 - {
7.421 - //FIXME: What if there are empty Id's?
7.422 - //FIXME: Can I use 'this' in a constructor?
7.423 - G->dyn_edge_maps.push_back(this);
7.424 - }
7.425 - EdgeMap(const SmartGraph &_G,const T &t) :
7.426 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
7.427 - {
7.428 - G->dyn_edge_maps.push_back(this);
7.429 - }
7.430 - EdgeMap(const EdgeMap<T> &m) :
7.431 - DynMapBase<Edge>(*m.G), container(m.container)
7.432 - {
7.433 - G->dyn_node_maps.push_back(this);
7.434 - }
7.435 -
7.436 - template<typename TT> friend class EdgeMap;
7.437 -
7.438 - ///\todo It can copy between different types.
7.439 - ///
7.440 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
7.441 - DynMapBase<Edge>(*m.G)
7.442 - {
7.443 - G->dyn_node_maps.push_back(this);
7.444 - typename std::vector<TT>::const_iterator i;
7.445 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
7.446 - i!=m.container.end();
7.447 - i++)
7.448 - container.push_back(*i);
7.449 - }
7.450 - ~EdgeMap()
7.451 - {
7.452 - if(G) {
7.453 - std::vector<DynMapBase<Edge>* >::iterator i;
7.454 - for(i=G->dyn_edge_maps.begin();
7.455 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
7.456 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
7.457 - //A better way to do that: (Is this really important?)
7.458 - if(*i==this) {
7.459 - *i=G->dyn_edge_maps.back();
7.460 - G->dyn_edge_maps.pop_back();
7.461 - }
7.462 - }
7.463 - }
7.464 -
7.465 - void add(const Edge k)
7.466 - {
7.467 - if(k.n>=int(container.size())) container.resize(k.n+1);
7.468 - }
7.469 - void erase(const Edge) { }
7.470 -
7.471 - void set(Edge n, T a) { container[n.n]=a; }
7.472 - //T get(Edge n) const { return container[n.n]; }
7.473 - typename std::vector<T>::reference
7.474 - operator[](Edge n) { return container[n.n]; }
7.475 - typename std::vector<T>::const_reference
7.476 - operator[](Edge n) const { return container[n.n]; }
7.477 -
7.478 - ///\warning There is no safety check at all!
7.479 - ///Using operator = between maps attached to different graph may
7.480 - ///cause serious problem.
7.481 - ///\todo Is this really so?
7.482 - ///\todo It can copy between different types.
7.483 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
7.484 - {
7.485 - container = m.container;
7.486 - return *this;
7.487 - }
7.488 - template<typename TT>
7.489 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
7.490 - {
7.491 - copy(m.container.begin(), m.container.end(), container.begin());
7.492 - return *this;
7.493 - }
7.494 -
7.495 - void update() {} //Useless for DynMaps
7.496 - void update(T a) {} //Useless for DynMaps
7.497 - };
7.498 -
7.499 - };
7.500 -
7.501 - ///Graph for bidirectional edges.
7.502 -
7.503 - ///The purpose of this graph structure is to handle graphs
7.504 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
7.505 - ///of oppositely directed edges.
7.506 - ///There is a new edge map type called
7.507 - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
7.508 - ///that complements this
7.509 - ///feature by
7.510 - ///storing shared values for the edge pairs. The usual
7.511 - ///\ref GraphSkeleton::EdgeMap "EdgeMap"
7.512 - ///can be used
7.513 - ///as well.
7.514 - ///
7.515 - ///The oppositely directed edge can also be obtained easily
7.516 - ///using \ref opposite.
7.517 - ///\warning It shares the similarity with \ref SmartGraph that
7.518 - ///it is not possible to delete edges or nodes from the graph.
7.519 - //\sa \ref SmartGraph.
7.520 -
7.521 - class SymSmartGraph : public SmartGraph
7.522 - {
7.523 - public:
7.524 - template<typename T> class SymEdgeMap;
7.525 - template<typename T> friend class SymEdgeMap;
7.526 -
7.527 - SymSmartGraph() : SmartGraph() { }
7.528 - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
7.529 - Edge addEdge(Node u, Node v)
7.530 - {
7.531 - Edge e = SmartGraph::addEdge(u,v);
7.532 - SmartGraph::addEdge(v,u);
7.533 - return e;
7.534 - }
7.535 -
7.536 - ///The oppositely directed edge.
7.537 -
7.538 - ///Returns the oppositely directed
7.539 - ///pair of the edge \c e.
7.540 - Edge opposite(Edge e) const
7.541 - {
7.542 - Edge f;
7.543 - f.idref() = e.idref() - 2*(e.idref()%2) + 1;
7.544 - return f;
7.545 - }
7.546 -
7.547 - ///Common data storage for the edge pairs.
7.548 -
7.549 - ///This map makes it possible to store data shared by the oppositely
7.550 - ///directed pairs of edges.
7.551 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
7.552 - {
7.553 - std::vector<T> container;
7.554 -
7.555 - public:
7.556 - typedef T ValueType;
7.557 - typedef Edge KeyType;
7.558 -
7.559 - SymEdgeMap(const SymSmartGraph &_G) :
7.560 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
7.561 - {
7.562 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
7.563 - }
7.564 - SymEdgeMap(const SymSmartGraph &_G,const T &t) :
7.565 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
7.566 - {
7.567 - G->dyn_edge_maps.push_back(this);
7.568 - }
7.569 -
7.570 - SymEdgeMap(const SymEdgeMap<T> &m) :
7.571 - DynMapBase<SymEdge>(*m.G), container(m.container)
7.572 - {
7.573 - G->dyn_node_maps.push_back(this);
7.574 - }
7.575 -
7.576 - // template<typename TT> friend class SymEdgeMap;
7.577 -
7.578 - ///\todo It can copy between different types.
7.579 - ///
7.580 -
7.581 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
7.582 - DynMapBase<SymEdge>(*m.G)
7.583 - {
7.584 - G->dyn_node_maps.push_back(this);
7.585 - typename std::vector<TT>::const_iterator i;
7.586 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
7.587 - i!=m.container.end();
7.588 - i++)
7.589 - container.push_back(*i);
7.590 - }
7.591 -
7.592 - ~SymEdgeMap()
7.593 - {
7.594 - if(G) {
7.595 - std::vector<DynMapBase<Edge>* >::iterator i;
7.596 - for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
7.597 - i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
7.598 - && *i!=this; ++i) ;
7.599 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
7.600 - //A better way to do that: (Is this really important?)
7.601 - if(*i==this) {
7.602 - *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
7.603 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
7.604 - }
7.605 - }
7.606 - }
7.607 -
7.608 - void add(const Edge k)
7.609 - {
7.610 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
7.611 - container.resize(k.idref()/2+1);
7.612 - }
7.613 - void erase(const Edge k) { }
7.614 -
7.615 - void set(Edge n, T a) { container[n.idref()/2]=a; }
7.616 - //T get(Edge n) const { return container[n.idref()/2]; }
7.617 - typename std::vector<T>::reference
7.618 - operator[](Edge n) { return container[n.idref()/2]; }
7.619 - typename std::vector<T>::const_reference
7.620 - operator[](Edge n) const { return container[n.idref()/2]; }
7.621 -
7.622 - ///\warning There is no safety check at all!
7.623 - ///Using operator = between maps attached to different graph may
7.624 - ///cause serious problem.
7.625 - ///\todo Is this really so?
7.626 - ///\todo It can copy between different types.
7.627 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
7.628 - {
7.629 - container = m.container;
7.630 - return *this;
7.631 - }
7.632 - template<typename TT>
7.633 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
7.634 - {
7.635 - copy(m.container.begin(), m.container.end(), container.begin());
7.636 - return *this;
7.637 - }
7.638 -
7.639 - void update() {} //Useless for DynMaps
7.640 - void update(T a) {} //Useless for DynMaps
7.641 -
7.642 - };
7.643 -
7.644 - };
7.645 -
7.646 -
7.647 -} //namespace hugo
7.648 -
7.649 -
7.650 -
7.651 -
7.652 -#endif //SMART_GRAPH_H