1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/include/graph.h Sat Dec 06 19:32:27 2003 +0000
1.3 @@ -0,0 +1,381 @@
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 +
1.11 +namespace NEGRO
1.12 +{
1.13 + using namespace std;
1.14 +
1.15 +#include "oldgraph.h"
1.16 +
1.17 + template <class N, class E> class Graph : protected OldGraph<N,E>
1.18 + {
1.19 + public:
1.20 + typedef E EdgeType;
1.21 + typedef N NodeType;
1.22 +
1.23 + class EdgePoint
1.24 + {
1.25 + public:
1.26 + NEGRO::EdgePoint e;
1.27 + bool isValid() { return e; }
1.28 + };
1.29 +
1.30 + class InEdgePoint : public EdgePoint {};
1.31 + class OutEdgePoint : public EdgePoint {};
1.32 + class BiEdgePoint : public EdgePoint {};
1.33 + class SymEdgePoint : public EdgePoint {};
1.34 +
1.35 + typedef int NodePoint;
1.36 +
1.37 + class NodeIterator;
1.38 +
1.39 + class EdgeIterator;
1.40 + class InEdgeIterator;
1.41 + class OutEdgeIterator;
1.42 + class BiEdgeIterator;
1.43 + class SymEdgeIterator;
1.44 + class AllEdgeIterator;
1.45 +
1.46 + class FirstAnythingTypeNode;
1.47 +
1.48 + friend class NodeIterator;
1.49 + friend class EdgeIterator;
1.50 + friend class InEdgeIterator;
1.51 + friend class OutEdgeIterator;
1.52 + friend class BiEdgeIterator;
1.53 + friend class SymEdgeIterator;
1.54 + friend class AllEdgeIterator;
1.55 +
1.56 + class NodeIterator
1.57 + {
1.58 + Graph<N,E> *G; //operator*() miatt kell!!!
1.59 + int n; //nem kellene, ha itt mutato lenne!!
1.60 + public:
1.61 +
1.62 + NodeIterator() {;}
1.63 + NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
1.64 +
1.65 + NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
1.66 + NodeIterator Next() const { return NodeIterator(*this).GoNext();}
1.67 + NodeIterator &operator++() { return GoNext();}
1.68 + NodeIterator operator++(int)
1.69 + {NodeIterator tmp(*this); GoNext(); return tmp;}
1.70 + bool isValid() { return n!=INVALID; }
1.71 +
1.72 + N &operator*() const { return G->Data(n); }
1.73 + N *operator->() const { return &G->Data(n); }
1.74 +
1.75 + bool operator==(const NodeIterator &i) const {return n==i.n;}
1.76 + bool operator!=(const NodeIterator &i) const {return n!=i.n;}
1.77 +
1.78 + friend class Graph;
1.79 + friend class EdgeIterator;
1.80 + friend class InEdgeIterator;
1.81 + friend class OutEdgeIterator;
1.82 + friend class BiEdgeIterator;
1.83 + friend class SymEdgeIterator;
1.84 + friend class AllEdgeIterator;
1.85 + friend class FirstAnythingTypeNode;
1.86 +
1.87 + //Nem kellene egy:
1.88 + // static NodeIterator &GetInvalid(); ?
1.89 + };
1.90 +
1.91 + class EdgeIterator
1.92 + {
1.93 +
1.94 + Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
1.95 + //Ez csak kicsit baj, de:
1.96 + // Meg a From() es To() miatt!!!!!!!!!!
1.97 +
1.98 + NEGRO::EdgePoint e;
1.99 +
1.100 + public:
1.101 + EdgeIterator() {;} //Kell inicializalni? (Nem)
1.102 + EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
1.103 +
1.104 + // Lehet, hogy ez a ketto nem kell!!!
1.105 +
1.106 + NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
1.107 + NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
1.108 +
1.109 + bool isValid() {return e;}
1.110 + E &operator*() const { return G->Data(e); }
1.111 + E *operator->() const { return &G->Data(e); }
1.112 +
1.113 + //operator const OutEdgeIterator ();
1.114 + //operator const InEdgeIterator ();
1.115 + //operator const BiEdgeIterator ();
1.116 + //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
1.117 +
1.118 + bool operator==(const EdgeIterator &i) const {return e==i.e;}
1.119 + bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
1.120 +
1.121 + friend class Graph;
1.122 + friend class InEdgeIterator;
1.123 + friend class OutEdgeIterator;
1.124 + friend class BiEdgeIterator;
1.125 + friend class SymEdgeIterator;
1.126 + friend class AllEdgeIterator;
1.127 + };
1.128 +
1.129 + class BiEdgeIterator : public EdgeIterator
1.130 + {
1.131 + public:
1.132 + BiEdgeIterator &GoNextIn() { e=e->NextIn(); return *this;}
1.133 + BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
1.134 + BiEdgeIterator NextIn() const {return BiEdgeIterator(*this).GoNextIn();}
1.135 + BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
1.136 +
1.137 + operator InEdgeIterator ()
1.138 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.139 + operator OutEdgeIterator ()
1.140 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.141 + //operator const SymEdgeIterator ()
1.142 +
1.143 + friend class Graph;
1.144 + };
1.145 +
1.146 + class InEdgeIterator : public EdgeIterator
1.147 + //Ne a BiEdgeIterator-bol szarmazzon?
1.148 + {
1.149 + public:
1.150 + InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
1.151 + InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
1.152 + InEdgeIterator &operator++() { return GoNext();}
1.153 + InEdgeIterator operator++(int)
1.154 + {InEdgeIterator tmp(*this); GoNext(); return tmp;}
1.155 +
1.156 + operator const OutEdgeIterator ()
1.157 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.158 + operator const BiEdgeIterator ()
1.159 + {EdgeIterator i; i.G=G;i.e=e;return i;}
1.160 + // operator const SymEdgeIterator ();
1.161 +
1.162 + NodeIterator Anode() const {return To();}
1.163 + NodeIterator Bnode() const {return From();}
1.164 +
1.165 + friend class Graph;
1.166 + };
1.167 +
1.168 + class OutEdgeIterator : public EdgeIterator
1.169 + {
1.170 + public:
1.171 + OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
1.172 + OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
1.173 + OutEdgeIterator &operator++() { return GoNext();}
1.174 + OutEdgeIterator operator++(int)
1.175 + {OutEdgeIterator tmp(*this); GoNext(); return tmp;}
1.176 +
1.177 + NodeIterator Anode() const {return From();}
1.178 + NodeIterator Bnode() const {return To();}
1.179 +
1.180 + operator const InEdgeIterator ()
1.181 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.182 + operator const BiEdgeIterator ()
1.183 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
1.184 + //operator const SymEdgeIterator();
1.185 +
1.186 + friend class Graph;
1.187 + };
1.188 +
1.189 + class SymEdgeIterator : public EdgeIterator
1.190 + {
1.191 + NodeIterator n; // Itt ketszer van a G
1.192 +
1.193 + public:
1.194 + SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
1.195 + SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
1.196 + SymEdgeIterator &operator++() { return GoNext();}
1.197 + SymEdgeIterator operator++(int)
1.198 + {SymEdgeIterator tmp(*this); GoNext(); return tmp;}
1.199 +
1.200 + NodeIterator Anode() const {return n;}
1.201 + NodeIterator Bnode() const {return n.n==From().n?To():From();}
1.202 +
1.203 + operator const InEdgeIterator ()
1.204 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.205 + operator const OutEdgeIterator ()
1.206 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.207 + operator const BiEdgeIterator ()
1.208 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
1.209 +
1.210 + friend class Graph;
1.211 + };
1.212 +
1.213 + class AllEdgeIterator : public EdgeIterator
1.214 + {
1.215 + NodeIterator n; // Itt ketszer van a G
1.216 +
1.217 + public:
1.218 + AllEdgeIterator &GoNext()
1.219 + {
1.220 + e=e->NextOut();
1.221 + if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
1.222 + return *this;
1.223 + }
1.224 + AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
1.225 + AllEdgeIterator &operator++() { return GoNext();}
1.226 + AllEdgeIterator operator++(int)
1.227 + {AllEdgeIterator tmp(*this); GoNext(); return tmp;}
1.228 +
1.229 +
1.230 + NodeIterator Anode() const {return n;}
1.231 + NodeIterator Bnode() const {return n.n==From().n?To():From();}
1.232 +
1.233 + operator const InEdgeIterator ()
1.234 + {InEdgeIterator i; i.G=G;i.e=e;return i;}
1.235 + operator const OutEdgeIterator ()
1.236 + {OutEdgeIterator i; i.G=G;i.e=e;return i;}
1.237 + operator const BiEdgeIterator ()
1.238 + {BiEdgeIterator i; i.G=G;i.e=e;return i;}
1.239 +
1.240 + friend class Graph;
1.241 + };
1.242 +
1.243 + typedef NodeIterator DeletingNodeIterator;
1.244 + typedef EdgeIterator DeletingEdgeIterator;
1.245 + typedef BiEdgeIterator DeletingBiEdgeIterator;
1.246 + typedef OutEdgeIterator DeletingOutEdgeIterator;
1.247 + typedef InEdgeIterator DeletingInEdgeIterator;
1.248 + typedef SymEdgeIterator DeletingSymEdgeIterator;
1.249 +
1.250 + const NodeIterator &FirstNode()
1.251 + {
1.252 + NodeIterator i;
1.253 + i.G=this;i.n=OldGraph<N,E>::FirstNode();
1.254 + return i;
1.255 + }
1.256 +
1.257 + void GetFirst(NodePoint &p) { p=OldGraph<N,E>::FirstNode(); }
1.258 +
1.259 + void GetFirst(InEdgePoint &p,const NodePoint &n)
1.260 + { p=OldGraph<N,E>::FirstIn(n); }
1.261 + void GetFirst(OutEdgePoint &p,const NodePoint &n)
1.262 + { p=OldGraph<N,E>::FirstOut(n); }
1.263 + void GetFirst(SymEdgePoint &p,const NodePoint &n)
1.264 + { p=OldGraph<N,E>::FirstEdge(n); }
1.265 + void GetFirst(EdgePoint &p) //Vegigmegy mindenen
1.266 + { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
1.267 +
1.268 + void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
1.269 +
1.270 + void GetFirst(InEdgeIterator &i,const NodeIterator &n)
1.271 + { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
1.272 + void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
1.273 + { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
1.274 + void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
1.275 + { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
1.276 + void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
1.277 + {
1.278 + i.G=this;
1.279 + GetFirst(i.n);
1.280 + i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
1.281 + }
1.282 +
1.283 +
1.284 +
1.285 + //Vagy beginnode()?
1.286 + const DeletingEdgeIterator &FirstOut(const NodeIterator &n)
1.287 + {
1.288 + EdgeIterator i;
1.289 + i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
1.290 + return i;
1.291 + }
1.292 + const DeletingEdgeIterator &FirstIn(const NodeIterator &n)
1.293 + {
1.294 + EdgeIterator i;
1.295 + i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
1.296 + return i;
1.297 + }
1.298 + const DeletingSymEdgeIterator &FirstSym(const NodeIterator &n)
1.299 + {
1.300 + EdgeIterator i;
1.301 + i.G=n.G;i.n=n.n;
1.302 + i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
1.303 + return i;
1.304 + }
1.305 +
1.306 + // class FirstAnythingType;
1.307 + // friend class FirstAnythingType;
1.308 +
1.309 + class FirstAnythingTypeNode
1.310 + {
1.311 + NodeIterator n;
1.312 + public:
1.313 + FirstAnythingTypeNode(NodeIterator i) : n(i) {}
1.314 +
1.315 + operator const InEdgeIterator () const
1.316 + {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
1.317 + operator const OutEdgeIterator () const
1.318 + {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
1.319 + operator const SymEdgeIterator () const
1.320 + {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
1.321 +
1.322 + operator const InEdgePoint () const
1.323 + {InEdgePoint i; n.G->GetFirst(i,n);return i;}
1.324 + operator const OutEdgePoint () const
1.325 + {OutEdgePoint i; n.G->GetFirst(i,n);return i;}
1.326 + operator const SymEdgePoint () const
1.327 + {SymEdgePoint i; n.G->GetFirst(i,n);return i;}
1.328 + };
1.329 +
1.330 + class FirstAnythingType
1.331 + {
1.332 + Graph<N,E> *G;
1.333 + public:
1.334 + FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
1.335 +
1.336 + operator const AllEdgeIterator () const
1.337 + {AllEdgeIterator i; G->GetFirst(i);return i;}
1.338 + operator const EdgePoint () const
1.339 + {EdgePoint i; G->GetFirst(i);return i;}
1.340 + operator const NodeIterator () const
1.341 + {NodeIterator i; G->GetFirst(i);return i;}
1.342 + operator const NodePoint () const
1.343 + {NodePoint i; G->GetFirst(i);return i;}
1.344 + } _FST;
1.345 +
1.346 + // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
1.347 + FirstAnythingTypeNode First(NodeIterator &i)
1.348 + {FirstAnythingTypeNode t(i); return t;}
1.349 + const FirstAnythingType &First() {return _FST;}
1.350 +
1.351 + // LastNode() vagy endnode() stb. Nem kell?
1.352 +
1.353 + DeletingNodeIterator AddNode()
1.354 + {
1.355 + DeletingNodeIterator i;
1.356 + i.G=this; i.n=OldGraph<N,E>::AddNode();
1.357 + return i;
1.358 + }
1.359 + DeletingEdgeIterator
1.360 + AddEdge(const NodeIterator from,const NodeIterator to)
1.361 + {
1.362 + DeletingEdgeIterator i;
1.363 + i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
1.364 + }
1.365 +
1.366 + void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
1.367 + void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
1.368 +
1.369 + int NodeNum() { OldGraph<N,E>::NodeNum(); }
1.370 + int Clean() { OldGraph<N,E>::Clean(); }
1.371 +
1.372 + Graph() : _FST(this) {}
1.373 + };
1.374 +
1.375 + /* Ez itt a fiam kommentje:
1.376 + <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
1.377 + vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
1.378 + << < < < < < < .cx..x.c.cc.c
1.379 + mcmn
1.380 + */
1.381 +
1.382 +}
1.383 +
1.384 +#endif
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/include/oldgraph.h Sat Dec 06 19:32:27 2003 +0000
2.3 @@ -0,0 +1,551 @@
2.4 +// -*-mode: c++; -*-
2.5 +#ifndef __OLDGRAPH_H_
2.6 +#define __OLDGRAPH_H_
2.7 +
2.8 +#include <stdio.h>
2.9 +
2.10 +//#include <new>
2.11 +
2.12 +#define INVALID -1
2.13 +#define FREE_NODE INVALID
2.14 +
2.15 +#define EDGE_BLOCK_SIZE 100
2.16 +#define INIT_NODES_SIZE 10
2.17 +#define INIT_EDGES_BLOCK_MAX 10
2.18 +
2.19 +#define foreachNode(n,G) for((n)=(G).FirstNode();(n)!=INVALID;(n)=(G).NextNode(n))
2.20 +#define foreachIn(e,G,n) for((e)=(G).FirstIn(n) ;(e);(e)=(G).NextIn(e) )
2.21 +#define foreachOut(e,G,n) for((e)=(G).FirstOut(n);(e);(e)=(G).NextOut(e))
2.22 +#define foreachEdge(e,G,n) for((e)=(G).FirstEdge(n);(e);(e)=(G).NextEdge((n),(e)))
2.23 +
2.24 +struct EdgeIndex { int block,index; };
2.25 +
2.26 +extern EdgeIndex InvalidIndex;
2.27 +
2.28 +class EdgeCorp;
2.29 +typedef EdgeCorp *EdgePoint;
2.30 +
2.31 +class EdgeCorp {
2.32 + public:
2.33 + int from,to; //from==INVALID <=> this is a free edge.
2.34 + EdgePoint previn,nextin,prevout,nextout;
2.35 + EdgeIndex index;
2.36 +
2.37 + int From() { return from; }
2.38 + int To() { return to; }
2.39 + EdgePoint NextIn() { return nextin; }
2.40 + EdgePoint NextOut() { return nextout; }
2.41 +};
2.42 +
2.43 +inline int From(EdgePoint e) { return e->from; }
2.44 +inline int To(EdgePoint e) { return e->to; }
2.45 +inline EdgePoint NextIn(EdgePoint e) { return e->nextin; }
2.46 +inline EdgePoint NextOut(EdgePoint e) { return e->nextout; }
2.47 +
2.48 +
2.49 +//////////////////////////////////////////////////////////////////////
2.50 +// OLDGRAPH TEMPLATE
2.51 +//////////////////////////////////////////////////////////////////////
2.52 +// Copy Constructor should be provided for N
2.53 +
2.54 +//class Graph;
2.55 +//class Graph::NodeIterator; //Nem megy. Disznosag!
2.56 +template <class N, class E> class OldGraph
2.57 +{
2.58 +
2.59 + // friend class NEGRO::Graph::NodeIterator; //Nem megy. Disznosag!
2.60 +
2.61 +
2.62 + class nodes_t;
2.63 + friend class OldGraph::nodes_t;
2.64 + class edge_block;
2.65 + friend class OldGraph::edge_block;
2.66 +
2.67 + class edge_t : public EdgeCorp {
2.68 + public:
2.69 + //edge_t *previn,*nextin,*prevout,*nextout;
2.70 + union {
2.71 + int _align;
2.72 + char data[sizeof(E)];
2.73 + };
2.74 + };
2.75 +
2.76 + class nodes_t {
2.77 + public:
2.78 + union {
2.79 + int _align;
2.80 + char data[sizeof(N)];
2.81 + };
2.82 + int indeg,outdeg; // indeg==FREE_NODE <=> this node is free.
2.83 + EdgePoint firstin, firstout;
2.84 + int prev,next;
2.85 +
2.86 + void Copy(nodes_t &n)
2.87 + {
2.88 + indeg = n.indeg; outdeg = n.outdeg;
2.89 + firstin = n.firstin; firstout = n.firstout;
2.90 + prev = n.prev; next = n.next;
2.91 + if(n.indeg!=FREE_NODE) new(data) N(*(N*)(n.data));
2.92 + // if(n.indeg!=FREE_NODE) {
2.93 + // new(data) N;
2.94 + // (*(N*)(data))=(*(N*)(n.data));
2.95 + // }
2.96 + }
2.97 +
2.98 + } *nodes;
2.99 + int nodenum, nodes_size;
2.100 + int firstnode, freenodes;
2.101 + class edge_block {
2.102 + public:
2.103 + //edge_block *next;
2.104 + // char fields[sizeof(edge_t)*EDGE_BLOCK_SIZE];
2.105 + edge_t fields[EDGE_BLOCK_SIZE];
2.106 + } **edges;
2.107 + int edge_block_num,edge_block_max;
2.108 + EdgePoint freeedges;
2.109 +
2.110 + void setup(int nosi = INIT_NODES_SIZE);
2.111 + void destroy();
2.112 + void inc_nodes_size(int n);
2.113 +
2.114 + public:
2.115 + int NodeNum() {return nodenum;};
2.116 + int EdgeNum();
2.117 + int MaxNode() {return nodes_size;};
2.118 + int FirstNode() {return firstnode;};
2.119 + int NextNode(int n) {return nodes[n].next;};
2.120 + int PrevNode(int n) {return nodes[n].prev;};
2.121 + N& operator()(int n) {return *(N*)(nodes[n].data);};
2.122 + N& Data (int n) {return *(N*)(nodes[n].data);};
2.123 + int AddNode();
2.124 + void AddNodeBlock(int n) {for(int i=0;i<n;i++) AddNode();}
2.125 + int AddNode(int n);
2.126 + void Delete(int n);
2.127 + int isaNode(int n) {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
2.128 +
2.129 + int InDeg(int n) {return nodes[n].indeg;};
2.130 + int OutDeg(int n) {return nodes[n].outdeg;};
2.131 + EdgePoint FirstIn(int n) {return nodes[n].firstin;};
2.132 + EdgePoint FirstOut(int n) {return nodes[n].firstout;};
2.133 +
2.134 + E& operator()(EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
2.135 + E& Data (EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
2.136 + int From(EdgePoint e) {return e->from;};
2.137 + int To(EdgePoint e) {return e->to;};
2.138 + EdgePoint NextIn(EdgePoint e)
2.139 + {return e->nextin;};
2.140 + EdgePoint NextOut(EdgePoint e)
2.141 + {return e->nextout;};
2.142 + EdgePoint AddEdge(int f, int t);
2.143 + void Delete(EdgePoint e);
2.144 + EdgePoint Edge(int f,int t);
2.145 + // EdgePoint Edge(E &d)
2.146 + // {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
2.147 + E& operator()(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
2.148 + E& Data(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
2.149 + void Delete(int f, int t) {Delete(Edge(f,t));};
2.150 + void Reverse(EdgePoint e);
2.151 +
2.152 + // Functions for EdgeIndex
2.153 +
2.154 + EdgePoint Edge(EdgeIndex i)
2.155 + { return (EdgePoint)(edges[i.block]->fields+i.index);};
2.156 + EdgeIndex Index(EdgePoint e) { return e->index;};
2.157 + EdgeIndex Index(int f, int t) { EdgePoint e; return Edge(f,t)->index; }
2.158 + void Delete(EdgeIndex i) { Delete(Edge(i));};
2.159 + E& operator()(EdgeIndex i)
2.160 + {return *(E*)(edges[i.block]->fields[i.index].data);};
2.161 + E& Data(EdgeIndex i)
2.162 + {return *(E*)(edges[i.block]->fields[i.index].data);};
2.163 + EdgePoint AddEdge(int f, int t,EdgeIndex in);
2.164 +
2.165 +
2.166 +
2.167 + // Operators for symmetric graphs:
2.168 +
2.169 + EdgePoint FirstEdge(int n)
2.170 + { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
2.171 + EdgePoint NextEdge(int n,EdgePoint e)
2.172 + { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
2.173 + int Opposite(EdgePoint e,int n)
2.174 + { return From(e)+To(e)-n; };
2.175 +
2.176 + // Initializers, destructors
2.177 +
2.178 + OldGraph() {setup();};
2.179 + OldGraph(int nosi) {setup(nosi);};
2.180 + OldGraph(OldGraph<N,E> &H) {setup();operator=(H);};
2.181 + ~OldGraph() {destroy();};
2.182 + void Clean(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
2.183 + void Clear(int nosi = INIT_NODES_SIZE) {destroy();setup(nosi);};
2.184 +
2.185 + void DeleteEdges();
2.186 +
2.187 + OldGraph<N,E> &operator=(OldGraph<N,E> &H);
2.188 +};
2.189 +
2.190 +//////////////////////////////////////////////////////////////////////
2.191 +// Template Definitions
2.192 +//////////////////////////////////////////////////////////////////////
2.193 +
2.194 +//#include <stdio.h>
2.195 +
2.196 +//**********************************************************************
2.197 +// OldGraph definitions
2.198 +//**********************************************************************
2.199 +
2.200 +template<class N, class E> void OldGraph<N,E>::setup(int nosi) {
2.201 + int i;
2.202 +
2.203 + //Set up nodes
2.204 + nodenum = 0;
2.205 + nodes_size = nosi;
2.206 + // nodes = (nodes_t*) new char[sizeof(nodes_t)*nodes_size];
2.207 + nodes = (nodes_t*) new nodes_t [nodes_size];
2.208 + for(i=0;i<nodes_size;i++)
2.209 + {
2.210 + nodes[i].prev=i-1;
2.211 + nodes[i].next=i+1;
2.212 + nodes[i].indeg=FREE_NODE;
2.213 + nodes[i].outdeg=0;
2.214 + nodes[i].firstin=nodes[i].firstout=NULL;
2.215 + }
2.216 + firstnode=nodes[0].prev=nodes[nodes_size-1].next=INVALID;
2.217 + freenodes=0;
2.218 + //Set up edge-list_template_type;
2.219 + freeedges = NULL;
2.220 +
2.221 + edges = new edge_block* [edge_block_max=INIT_EDGES_BLOCK_MAX];
2.222 + edge_block_num = 0;
2.223 +
2.224 +}
2.225 +
2.226 +template<class N, class E> void OldGraph<N,E>::destroy()
2.227 +{
2.228 + edge_block *oe;
2.229 + int i;
2.230 +
2.231 + while(firstnode!=INVALID) Delete(firstnode);
2.232 + delete [] nodes;
2.233 + for(i=0;i<edge_block_num;i++) delete edges[i];
2.234 + delete [] edges;
2.235 +}
2.236 +
2.237 +template<class N, class E> void OldGraph<N,E>::inc_nodes_size(int n)
2.238 +{
2.239 + int i;
2.240 + if(n<=nodenum) return;
2.241 +
2.242 + nodes_t *nn;
2.243 +// nn = (nodes_t*) new char [sizeof(nodes_t)*n];
2.244 + nn = (nodes_t*) new nodes_t [n];
2.245 + for(i=0;i<nodes_size;i++)
2.246 + {
2.247 + nn[i].Copy(nodes[i]);
2.248 + if(nodes[i].indeg!=FREE_NODE) ((N*)(nodes[i].data))->~N();
2.249 + }
2.250 +
2.251 + delete [] nodes;
2.252 + nodes = nn;
2.253 + for(i=nodes_size;i<n;i++)
2.254 + {
2.255 + nodes[i].prev=i-1;
2.256 + nodes[i].next=i+1;
2.257 + nodes[i].indeg=FREE_NODE;
2.258 + nodes[i].outdeg=0;
2.259 + nodes[i].firstin=nodes[i].firstout=NULL;
2.260 + }
2.261 + nodes[nodes_size].prev=INVALID;
2.262 + nodes[n-1].next=freenodes;
2.263 + if(freenodes!=INVALID) nodes[freenodes].prev=n-1;
2.264 + freenodes=nodes_size;
2.265 + nodes_size=n;
2.266 +}
2.267 +
2.268 +template<class N, class E> OldGraph<N,E> &OldGraph<N,E>::operator=(OldGraph<N,E> &H)
2.269 +{
2.270 + Clean();
2.271 +
2.272 + int i;
2.273 + EdgePoint e;
2.274 +
2.275 + for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
2.276 + {
2.277 + AddNode(i);
2.278 + operator()(i)=H(i);
2.279 + }
2.280 + for(i=H.FirstNode();i!=INVALID;i=H.NextNode(i))
2.281 + for(e=H.FirstOut(i);e;e=H.NextOut(e))
2.282 + operator()(AddEdge(i,H.To(e),H.Index(e)))=H(e);
2.283 +
2.284 + return *this;
2.285 +}
2.286 +
2.287 +template<class N, class E> int OldGraph<N,E>::EdgeNum()
2.288 +{
2.289 + int n=firstnode, m=0;
2.290 + EdgePoint e;
2.291 + while(n != INVALID)
2.292 + {
2.293 + e=FirstOut(n);
2.294 + while (e != NULL)
2.295 + {
2.296 + m++;
2.297 + e=NextOut(e);
2.298 + }
2.299 + n=nodes[n].next;
2.300 + }
2.301 + return m;
2.302 +}
2.303 +
2.304 +template<class N, class E> int OldGraph<N,E>::AddNode()
2.305 +{
2.306 + int i;
2.307 +
2.308 + if(freenodes==INVALID) inc_nodes_size(2*nodes_size);
2.309 +
2.310 + i=freenodes;
2.311 + if(firstnode!=INVALID) nodes[firstnode].prev=i;
2.312 + freenodes=nodes[i].next;
2.313 + new(nodes[i].data) N; //Explicit constructor call
2.314 + nodes[i].next=firstnode;
2.315 + nodes[i].prev=INVALID;
2.316 + nodes[i].indeg=0;
2.317 + firstnode=i;
2.318 + if(freenodes!=INVALID) nodes[freenodes].prev=INVALID;
2.319 + nodenum++;
2.320 + return i;
2.321 +}
2.322 +
2.323 +template<class N, class E> int OldGraph<N,E>::AddNode(int n)
2.324 +{
2.325 + int i;
2.326 +
2.327 + if(n>=nodes_size)
2.328 + {
2.329 + for(i=INIT_NODES_SIZE;i<=n;i*=2) ;
2.330 + inc_nodes_size(i);
2.331 + }
2.332 +
2.333 + if(nodes[n].indeg==FREE_NODE)
2.334 + {
2.335 + new(nodes[n].data) N; //Explicit constructor call
2.336 + if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev = nodes[n].prev;
2.337 + if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next = nodes[n].next;
2.338 + else freenodes = nodes[n].next;
2.339 +
2.340 + nodes[n].prev = INVALID;
2.341 + if((nodes[n].next = firstnode)!=INVALID) nodes[firstnode].prev=n;
2.342 + firstnode = n;
2.343 + nodenum++;
2.344 + nodes[n].indeg=0;
2.345 + }
2.346 + return n;
2.347 +}
2.348 +
2.349 +template<class N, class E> void OldGraph<N,E>::Delete(int n)
2.350 +{
2.351 + if(n==INVALID||nodes[n].indeg==FREE_NODE) return;
2.352 +
2.353 + EdgePoint e;
2.354 +
2.355 + while(e=FirstIn(n)) Delete(e);
2.356 + while(e=FirstOut(n)) Delete(e);
2.357 +
2.358 + if(n==firstnode) firstnode=nodes[n].next;
2.359 + if(nodes[n].prev!=INVALID) nodes[nodes[n].prev].next=nodes[n].next;
2.360 + if(nodes[n].next!=INVALID) nodes[nodes[n].next].prev=nodes[n].prev;
2.361 + if(freenodes!=INVALID) nodes[freenodes].prev=n;
2.362 + nodes[n].next=freenodes;
2.363 + nodes[n].prev=INVALID;
2.364 + nodes[n].indeg=FREE_NODE;
2.365 + ((N*)(nodes[n].data))->~N(); //Explicit destructor call
2.366 + freenodes=n;
2.367 +
2.368 + nodenum--;
2.369 +}
2.370 +
2.371 +template<class N, class E> EdgePoint OldGraph<N,E>::AddEdge(int f, int t)
2.372 +{
2.373 + int i;
2.374 + edge_block *peb;
2.375 + edge_block **ppeb;
2.376 + edge_t *e;
2.377 +
2.378 + if(!freeedges)
2.379 + {
2.380 + if(edge_block_num>=edge_block_max)
2.381 + {
2.382 + ppeb = new edge_block* [edge_block_max*=2];
2.383 + for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
2.384 + delete [] edges;
2.385 + edges = ppeb;
2.386 + }
2.387 + peb = new edge_block;
2.388 + edges[edge_block_num] = peb;
2.389 +
2.390 + for(i=0;i<EDGE_BLOCK_SIZE;i++)
2.391 + {
2.392 + ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
2.393 + ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
2.394 + ((edge_t*)peb->fields)[i].index.block = edge_block_num;
2.395 + ((edge_t*)peb->fields)[i].index.index = i;
2.396 + ((edge_t*)peb->fields)[i].from = INVALID;
2.397 + }
2.398 + ((edge_t*)peb->fields)[0].previn=
2.399 + ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=NULL;
2.400 + freeedges = (edge_t*)peb->fields;
2.401 + edge_block_num++;
2.402 + }
2.403 +
2.404 + e=(edge_t *)freeedges;
2.405 + new (e->data) E; //Explicit constructor call
2.406 + freeedges=e->nextin;
2.407 + if(freeedges) freeedges->previn=NULL;
2.408 +
2.409 + e->from=f; e->to=t;
2.410 + e->previn=e->prevout=NULL;
2.411 + e->nextin=nodes[t].firstin;
2.412 + e->nextout=nodes[f].firstout;
2.413 + if(nodes[t].firstin) nodes[t].firstin->previn=e;
2.414 + if(nodes[f].firstout) nodes[f].firstout->prevout=e;
2.415 + nodes[t].firstin=nodes[f].firstout=e;
2.416 + nodes[t].indeg++; nodes[f].outdeg++;
2.417 +
2.418 + return (EdgePoint)e;
2.419 +
2.420 +}
2.421 +
2.422 +template<class N, class E>
2.423 +EdgePoint OldGraph<N,E>::AddEdge(int f, int t, EdgeIndex in)
2.424 +{
2.425 + int i;
2.426 + edge_block *peb;
2.427 + edge_block **ppeb;
2.428 + edge_t *e;
2.429 +
2.430 + while(edge_block_num<=in.block)
2.431 + {
2.432 + if(edge_block_num>=edge_block_max)
2.433 + {
2.434 + ppeb = new edge_block* [edge_block_max*=2];
2.435 + for(i=0;i<edge_block_num;i++) ppeb[i]=edges[i];
2.436 + delete [] edges;
2.437 + edges = ppeb;
2.438 + }
2.439 + peb = new edge_block;
2.440 + edges[edge_block_num] = peb;
2.441 +
2.442 + for(i=0;i<EDGE_BLOCK_SIZE;i++)
2.443 + {
2.444 + ((edge_t*)peb->fields)[i].nextin=((edge_t*)peb->fields)+(i+1);
2.445 + ((edge_t*)peb->fields)[i].previn=((edge_t*)peb->fields)+(i-1);
2.446 + ((edge_t*)peb->fields)[i].index.block = edge_block_num;
2.447 + ((edge_t*)peb->fields)[i].index.index = i;
2.448 + ((edge_t*)peb->fields)[i].from = INVALID;
2.449 + }
2.450 + ((edge_t*)peb->fields)[0].previn=NULL;
2.451 + ((edge_t*)peb->fields)[EDGE_BLOCK_SIZE-1].nextin=freeedges;
2.452 + if(freeedges)
2.453 + freeedges->previn = ((edge_t*)peb->fields) + (EDGE_BLOCK_SIZE-1);
2.454 + freeedges = (edge_t*)peb->fields;
2.455 + edge_block_num++;
2.456 + }
2.457 +
2.458 +
2.459 + e=((edge_t*)(edges[in.block]->fields))+in.index;
2.460 + if(e->from==INVALID)
2.461 + {
2.462 + if(e->previn) e->previn->nextin = e->nextin;
2.463 + else freeedges = e->nextin;
2.464 + if(e->nextin) e->nextin->previn = e->previn;
2.465 +
2.466 + new (e->data) E; //Explicit constructor call
2.467 +
2.468 + e->from=f; e->to=t;
2.469 + e->previn=e->prevout=NULL;
2.470 + e->nextin=nodes[t].firstin;
2.471 + e->nextout=nodes[f].firstout;
2.472 + if(nodes[t].firstin) nodes[t].firstin->previn=e;
2.473 + if(nodes[f].firstout) nodes[f].firstout->prevout=e;
2.474 + nodes[t].firstin=nodes[f].firstout=e;
2.475 + nodes[t].indeg++; nodes[f].outdeg++;
2.476 + }
2.477 + return (EdgePoint)e;
2.478 +}
2.479 +
2.480 +template<class N, class E> void OldGraph<N,E>::Delete(EdgePoint e)
2.481 +{
2.482 + if(!e||e->from==INVALID) return;
2.483 +
2.484 + ((E*)(((edge_t*)e)->data))->~E(); //Explicit destructor call
2.485 +
2.486 + nodes[e->from].outdeg--; nodes[e->to].indeg--;
2.487 +
2.488 +
2.489 + if(e->previn)
2.490 + e->previn->nextin=e->nextin;
2.491 + else nodes[e->to].firstin=e->nextin;
2.492 + if(e->prevout)
2.493 + e->prevout->nextout=e->nextout;
2.494 + else nodes[e->from].firstout=e->nextout;
2.495 + if(e->nextin)
2.496 + e->nextin->previn=e->previn;
2.497 + if(e->nextout)
2.498 + e->nextout->prevout=e->prevout;
2.499 +
2.500 + if(freeedges) freeedges->previn=e;
2.501 + e->previn=NULL; e->nextin=freeedges;
2.502 +
2.503 + e->from = INVALID;
2.504 + freeedges=e;
2.505 +}
2.506 +
2.507 +template<class N, class E> EdgePoint OldGraph<N,E>::Edge(int f, int t)
2.508 +{
2.509 + EdgePoint e;
2.510 +
2.511 + for(e=nodes[f].firstout;e&&e->to!=t;e=e->nextout) ;
2.512 +
2.513 + return (EdgePoint) e;
2.514 +}
2.515 +
2.516 +template<class N, class E> void OldGraph<N,E>::Reverse(EdgePoint e)
2.517 +{
2.518 + if(!e) return;
2.519 +
2.520 + nodes[e->from].outdeg--; nodes[e->to].indeg--;
2.521 +
2.522 + if(e->previn)
2.523 + e->previn->nextin=e->nextin;
2.524 + else nodes[e->to].firstin=e->nextin;
2.525 + if(e->prevout)
2.526 + e->prevout->nextout=e->nextout;
2.527 + else nodes[e->from].firstout=e->nextout;
2.528 + if(e->nextin)
2.529 + e->nextin->previn=e->previn;
2.530 + if(e->nextout)
2.531 + e->nextout->prevout=e->prevout;
2.532 +
2.533 + int t,f;
2.534 + f=e->to;e->to=t=e->from;
2.535 + e->from=f;
2.536 +
2.537 + e->previn=e->prevout=NULL;
2.538 + e->nextin=nodes[t].firstin;
2.539 + e->nextout=nodes[f].firstout;
2.540 + if(nodes[t].firstin) nodes[t].firstin->previn=e;
2.541 + if(nodes[f].firstout) nodes[f].firstout->prevout=e;
2.542 + nodes[t].firstin=nodes[f].firstout=e;
2.543 + nodes[t].indeg++; nodes[f].outdeg++;
2.544 +
2.545 +}
2.546 +
2.547 +template<class N, class E> void OldGraph<N,E>::DeleteEdges()
2.548 +{
2.549 + int n;
2.550 + for(n=FirstNode();n!=INVALID;n=NextNode(n))
2.551 + while(FirstOut(n)) Delete(FirstOut(n));
2.552 +}
2.553 +
2.554 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/graphdemo.cc Sat Dec 06 19:32:27 2003 +0000
3.3 @@ -0,0 +1,98 @@
3.4 +#include <iostream>
3.5 +#include <graph.h>
3.6 +
3.7 +using namespace NEGRO;
3.8 +using namespace std;
3.9 +
3.10 +class NodeData;
3.11 +class EdgeData;
3.12 +
3.13 +typedef Graph<NodeData,EdgeData> TestGraph;
3.14 +
3.15 +class NodeData
3.16 +{
3.17 +public:
3.18 + int id;
3.19 + bool isVis;
3.20 +};
3.21 +
3.22 +class EdgeData
3.23 +{
3.24 +public:
3.25 + int id;
3.26 +};
3.27 +
3.28 +
3.29 +typedef Graph<NodeData,EdgeData> TestGraph;
3.30 +
3.31 +void main()
3.32 +{
3.33 + TestGraph G;
3.34 + TestGraph::NodeIterator n,m,o,p,q;
3.35 + TestGraph::OutEdgeIterator e,f,g,h;
3.36 + int i,j,k;
3.37 +
3.38 +
3.39 + //for(i=1;i<=10;i++) G.AddNode().n=i; //Ez nagyon rossz!!!!!!!!
3.40 + for(i=1;i<=10;i++) G.AddNode()->id=i; //Ez a jo!!!!!!!!
3.41 +
3.42 + //n=G.AddNode();
3.43 +
3.44 + //for(i=1;i<=10;i++) cout << (G.AddNode()->n=i) << ' ';
3.45 + //cout << '\n';
3.46 +
3.47 + i=0;
3.48 + for(G.GetFirst(n);n.isValid();n++)
3.49 + for(G.GetFirst(m);m.isValid();++m)
3.50 + if(n!=m) G.AddEdge(n,m)->id=++i;
3.51 +
3.52 + cout << "Number of edges: " << i << "\n\n";
3.53 +
3.54 + TestGraph::AllEdgeIterator a;
3.55 + for(G.GetFirst(a);a.isValid();++a)
3.56 + cout << a->id << ":" << a.From()->id << "->" << a.To()->id << " ";
3.57 +
3.58 + cout << "\n\n\n";
3.59 +
3.60 + for(G.GetFirst(n);n.isValid();++n)
3.61 + {
3.62 + cout << n->id << "->";
3.63 + for(G.GetFirst(e,n);e.isValid();++e)
3.64 + cout << e->id << ":" << e.To()->id << ' ';
3.65 + cout << '\n';
3.66 + }
3.67 +
3.68 + cout << "\n\n\n\nB-verzio:\n\n\n";
3.69 +
3.70 + G.Clean();
3.71 +
3.72 + for(i=1;i<=10;i++) G.AddNode()->id=i;
3.73 +
3.74 + i=0;
3.75 + for(n=G.First();n.isValid();n++)
3.76 + for(m=G.First();m.isValid();++m)
3.77 + if(n!=m) G.AddEdge(n,m)->id=++i;
3.78 +
3.79 + ;
3.80 + for(n=G.First();n.isValid();++n)
3.81 + {
3.82 + e=G.First(n);
3.83 + while(e.isValid())
3.84 + if((e->id)%2) G.Delete(e++);
3.85 + else ++e;
3.86 + }
3.87 +
3.88 + for(a=G.First();a.isValid();++a)
3.89 + cout << a->id << ": " << a.From()->id << "->" << a.To()->id << " ";
3.90 +
3.91 + cout << "\n\n\n";
3.92 +
3.93 + for(n=G.First();n.isValid();++n)
3.94 + {
3.95 + cout << n->id << "->";
3.96 + for(e=G.First(n);e.isValid();++e)
3.97 + cout << e->id << ":" << e.To()->id << ' ';
3.98 + cout << '\n';
3.99 + }
3.100 +
3.101 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/makefile Sat Dec 06 19:32:27 2003 +0000
4.3 @@ -0,0 +1,3 @@
4.4 +graphdemo: graphdemo.cc ../include/graph.h \
4.5 + ../include/oldgraph.h makefile
4.6 + g++ -g -I../include -o graphdemo graphdemo.cc