Step toward to a standardised graph interface.
5 //inline void *operator new(size_t s, void *p) { return p; }
15 template <class N, class E> class Graph : protected OldGraph<N,E>
25 bool valid() { return e; }
28 class InEdgeIt : public EdgeIt {};
29 class OutEdgeIt : public EdgeIt {};
30 class BiEdgeIt : public EdgeIt {};
31 class SymEdgeIt : public EdgeIt {};
35 typedef NodeIt EachNodeIt;
41 class OutEdgeIterator;
43 class SymEdgeIterator;
44 class AllEdgeIterator;
46 class FirstAnythingTypeNode; //Required by the unified First() function.
48 friend class NodeIterator;
49 friend class EdgeIterator;
50 friend class InEdgeIterator;
51 friend class OutEdgeIterator;
52 friend class BiEdgeIterator;
53 friend class SymEdgeIterator;
54 friend class EachEdgeIterator;
58 Graph<N,E> *G; //operator*() miatt kell!!!
59 int n; //nem kellene, ha itt mutato lenne!!
63 NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
64 {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
65 NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
67 NodeIterator &goNext() { n=G->NextNode(n); return *this;}
68 NodeIterator next() const { return NodeIterator(*this).goNext();}
69 NodeIterator &operator++() { return goNext();}
70 NodeIterator operator++(int)
71 {NodeIterator tmp(*this); goNext(); return tmp;}
72 bool valid() { return n!=INVALID; }
74 N &operator*() const { return G->Data(n); }
75 N *operator->() const { return &G->Data(n); }
77 bool operator==(const NodeIterator &i) const {return n==i.n;}
78 bool operator!=(const NodeIterator &i) const {return n!=i.n;}
80 int index() const { return n; } //If the nodes are indexable
82 friend class EdgeIterator;
83 friend class InEdgeIterator;
84 friend class OutEdgeIterator;
85 friend class BiEdgeIterator;
86 friend class SymEdgeIterator;
87 friend class EachEdgeIterator;
88 friend class FirstAnythingTypeNode;
91 // static NodeIterator &GetInvalid(); ?
97 Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
98 //Ez csak kicsit baj, de:
99 // Meg a From() es To() miatt!!!!!!!!!!
104 EdgeIterator() {;} //Kell inicializalni? (Nem)
105 EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
107 // Lehet, hogy ez a ketto nem kell!!!
109 NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
110 NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
111 NodeIterator opposite(const NodeIterator &n) const
112 {return n==tail()?head():tail();}
114 bool valid() {return e;}
115 E &operator*() const { return G->Data(e); }
116 E *operator->() const { return &G->Data(e); }
118 //operator const OutEdgeIterator ();
119 //operator const InEdgeIterator ();
120 //operator const BiEdgeIterator ();
121 //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
123 bool operator==(const EdgeIterator &i) const {return e==i.e;}
124 bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
126 int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
127 //If the edges are indexable
130 friend class InEdgeIterator;
131 friend class OutEdgeIterator;
132 friend class BiEdgeIterator;
133 friend class SymEdgeIterator;
134 friend class EachEdgeIterator;
137 class BiEdgeIterator : public EdgeIterator
140 BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;}
141 BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
142 BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();}
143 BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
145 operator InEdgeIterator ()
146 {InEdgeIterator i; i.G=G;i.e=e;return i;}
147 operator OutEdgeIterator ()
148 {OutEdgeIterator i; i.G=G;i.e=e;return i;}
149 //operator const SymEdgeIterator ()
154 class InEdgeIterator : public EdgeIterator
155 //Ne a BiEdgeIterator-bol szarmazzon?
159 InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
160 { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
162 InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
163 InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
164 InEdgeIterator &operator++() { return GoNext();}
165 InEdgeIterator operator++(int)
166 {InEdgeIterator tmp(*this); GoNext(); return tmp;}
168 operator const OutEdgeIterator ()
169 {OutEdgeIterator i; i.G=G;i.e=e;return i;}
170 operator const BiEdgeIterator ()
171 {EdgeIterator i; i.G=G;i.e=e;return i;}
172 // operator const SymEdgeIterator ();
174 NodeIterator Anode() const {return To();}
175 NodeIterator Bnode() const {return From();}
180 class OutEdgeIterator : public EdgeIterator
184 OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
185 { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
187 OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
188 OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
189 OutEdgeIterator &operator++() { return goNext();}
190 OutEdgeIterator operator++(int)
191 {OutEdgeIterator tmp(*this); goNext(); return tmp;}
193 NodeIterator aNode() const {return tail();}
194 NodeIterator bNode() const {return head();}
196 operator const InEdgeIterator ()
197 {InEdgeIterator i; i.G=G;i.e=e;return i;}
198 operator const BiEdgeIterator ()
199 {BiEdgeIterator i; i.G=G;i.e=e;return i;}
200 //operator const SymEdgeIterator();
205 class SymEdgeIterator : public EdgeIterator
207 NodeIterator n; // Itt ketszer van a G
211 SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
212 { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
214 SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
215 SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
216 SymEdgeIterator &operator++() { return goNext();}
217 SymEdgeIterator operator++(int)
218 {SymEdgeIterator tmp(*this); goNext(); return tmp;}
220 NodeIterator aNode() const {return n;}
221 NodeIterator bNode() const {return n.n==tail().n?head():tail();}
223 operator const InEdgeIterator ()
224 {InEdgeIterator i; i.G=G;i.e=e;return i;}
225 operator const OutEdgeIterator ()
226 {OutEdgeIterator i; i.G=G;i.e=e;return i;}
227 operator const BiEdgeIterator ()
228 {BiEdgeIterator i; i.G=G;i.e=e;return i;}
233 class EachEdgeIterator : public EdgeIterator
235 NodeIterator n; // Itt ketszer van a G
238 EachEdgeIterator() {}
239 EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
241 e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
244 EachEdgeIterator &goNext()
247 if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
250 EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
251 EachEdgeIterator &operator++() { return goNext();}
252 EachEdgeIterator operator++(int)
253 {EachEdgeIterator tmp(*this); goNext(); return tmp;}
256 NodeIterator aNode() const {return n;}
257 NodeIterator bNode() const {return n.n==tail().n?head():tail();}
259 operator const EdgeIterator ()
260 {EdgeIterator i; i.G=G;i.e=e;return i;}
261 operator const InEdgeIterator ()
262 {InEdgeIterator i; i.G=G;i.e=e;return i;}
263 operator const OutEdgeIterator ()
264 {OutEdgeIterator i; i.G=G;i.e=e;return i;}
265 operator const BiEdgeIterator ()
266 {BiEdgeIterator i; i.G=G;i.e=e;return i;}
271 typedef NodeIterator DeletingNodeIterator;
272 typedef EdgeIterator DeletingEdgeIterator;
273 typedef BiEdgeIterator DeletingBiEdgeIterator;
274 typedef OutEdgeIterator DeletingOutEdgeIterator;
275 typedef InEdgeIterator DeletingInEdgeIterator;
276 typedef SymEdgeIterator DeletingSymEdgeIterator;
278 const NodeIterator firstNode()
281 i.G=this;i.n=OldGraph<N,E>::FirstNode();
285 void getFirst(NodeIt &p) { p=OldGraph<N,E>::FirstNode(); }
287 void getFirst(InEdgeIt &p,const NodeIt &n)
288 { p=OldGraph<N,E>::FirstIn(n); }
289 void getFirst(OutEdgeIt &p,const NodeIt &n)
290 { p=OldGraph<N,E>::FirstOut(n); }
291 void getFirst(SymEdgeIt &p,const NodeIt &n)
292 { p=OldGraph<N,E>::FirstEdge(n); }
293 void getFirst(EdgeIt &p) //Vegigmegy mindenen
294 { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
296 void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
298 void getFirst(InEdgeIterator &i,const NodeIterator &n)
299 { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
300 void getFirst(OutEdgeIterator &i,const NodeIterator &n)
301 { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
302 void getFirst(SymEdgeIterator &i,const NodeIterator &n)
303 { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
304 void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
308 i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
314 const DeletingEdgeIterator firstOut(const NodeIterator &n)
317 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
320 const DeletingEdgeIterator firstIn(const NodeIterator &n)
323 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
326 const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
330 i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
334 // class FirstAnythingType;
335 // friend class FirstAnythingType;
337 class FirstAnythingTypeNode
341 FirstAnythingTypeNode(NodeIterator i) : n(i) {}
343 operator const InEdgeIterator () const
344 {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
345 operator const OutEdgeIterator () const
346 {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
347 operator const SymEdgeIterator () const
348 {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
350 operator const InEdgeIt () const
351 {InEdgeIt i; n.G->GetFirst(i,n);return i;}
352 operator const OutEdgeIt () const
353 {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
354 operator const SymEdgeIt () const
355 {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
358 class FirstAnythingType
362 FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
364 operator const EachEdgeIterator () const
365 {EachEdgeIterator i; G->GetFirst(i);return i;}
366 operator const EdgeIt () const
367 {EdgeIt i; G->GetFirst(i);return i;}
368 operator const NodeIterator () const
369 {NodeIterator i; G->GetFirst(i);return i;}
370 operator const NodeIt () const
371 {NodeIt i; G->GetFirst(i);return i;}
374 // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
375 FirstAnythingTypeNode first(NodeIterator &i)
376 {FirstAnythingTypeNode t(i); return t;}
377 const FirstAnythingType &first() {return _FST;}
379 // LastNode() vagy endnode() stb. Nem kell?
381 DeletingNodeIterator addNode()
383 DeletingNodeIterator i;
384 i.G=this; i.n=OldGraph<N,E>::AddNode();
388 addEdge(const NodeIterator from,const NodeIterator to)
390 DeletingEdgeIterator i;
391 i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
394 void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
395 void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
397 int nodeNum() { OldGraph<N,E>::NodeNum(); }
398 void clean() { OldGraph<N,E>::Clean(); }
400 Graph() : _FST(this) {}
403 template<class T> class NodeMap
409 typedef T value_type;
410 void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
411 T get(const NodeIterator i) const {return map[i.Index()];}
412 T operator[](NodeIterator i) {return map[i.Index()];}
414 void update() { map.resize(G->MaxNode());}
417 void setG(Graph<N,E> &Gr) { G=&Gr; update();}
420 template<class T> class EdgeMap
426 typedef T value_type;
427 void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
428 T get(const EdgeIterator i) const {return map[i.Index()];}
429 T &operator[](EdgeIterator i) {return map[i.Index()];}
432 { map.resize(G->MaxEdge());}
435 void setG(Graph<N,E> &Gr)
441 int maxNode() { return OldGraph<N,E>::MaxNode();}
442 int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
446 template <class G> //G is a graph-type
451 typedef typename G::NodeIterator NodeIterator;
452 typedef typename G::EdgeIterator EdgeIterator;
453 typedef typename G::SymEdgeIterator SymEdgeIterator;
456 std::vector<EdgeIterator> path;
457 std::vector<bool> reversed;
460 void setLength(int n) { path.resize(n);reversed.resize(n);}
461 int getLength() { return path.size(); }
462 EdgeIterator &operator[](int n) {return path[n];}
463 NodeIterator GetNode(int n) // What about path of length 1?
466 reversed[n-1]?path[n-1].tail():path[n-1].head():
467 reversed[0]?path[0].head():path[0].tail();
469 void setRevert(int n,bool r=true) {reversed[n]=r;}
470 void setEdge(int n,SymEdgeIterator i)
473 reversed[n] = i.head()==i.aNode();
475 void setEdge(int n,EdgeIterator i,bool r)
481 NodeIterator tail() { return getNode(0); }
482 NodeIterator head() { return getNode(getLength()); }
485 /* Ez itt a fiam kommentje:
486 <v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
487 vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
488 << < < < < < < .cx..x.c.cc.c