COIN-OR::LEMON - Graph Library

Context Navigation

source: lemon-0.x/src/include/graph.h @ 5:f5852ebe00ca

Last change on this file since 5:f5852ebe00ca was 3:272a5677bd6d, checked in by Alpar Juttner, 20 years ago
Marci type iterator constructors src/demo/bfsdemo.cc: demo for bfs.h cosmetical changes
File size: 12.6 KB

Line
1	// --mode: c++; --
2	#ifndef __GRAPH_H_
3	#define __GRAPH_H_
4
5	//inline void operator new(size_t s, void p) { return p; }
6	#include <new>
7
8	namespace NEGRO
9	{
10	using namespace std;
11
12	#include "oldgraph.h"
13
14	template <class N, class E> class Graph : protected OldGraph<N,E>
15	{
16	public:
17	typedef E EdgeType;
18	typedef N NodeType;
19
20	class EdgePoint
21	{
22	public:
23	NEGRO::EdgePoint e;
24	bool isValid() { return e; }
25	};
26
27	class InEdgePoint : public EdgePoint {};
28	class OutEdgePoint : public EdgePoint {};
29	class BiEdgePoint : public EdgePoint {};
30	class SymEdgePoint : public EdgePoint {};
31
32	typedef int NodePoint;
33
34	class NodeIterator;
35
36	class EdgeIterator;
37	class InEdgeIterator;
38	class OutEdgeIterator;
39	class BiEdgeIterator;
40	class SymEdgeIterator;
41	class AllEdgeIterator;
42
43	class FirstAnythingTypeNode;
44
45	friend class NodeIterator;
46	friend class EdgeIterator;
47	friend class InEdgeIterator;
48	friend class OutEdgeIterator;
49	friend class BiEdgeIterator;
50	friend class SymEdgeIterator;
51	friend class AllEdgeIterator;
52
53	class NodeIterator
54	{
55	Graph<N,E> G; //operator() miatt kell!!!
56	int n; //nem kellene, ha itt mutato lenne!!
57	public:
58
59	NodeIterator() {;}
60	NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
61	{G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
62	NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
63
64	NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
65	NodeIterator Next() const { return NodeIterator(*this).GoNext();}
66	NodeIterator &operator++() { return GoNext();}
67	NodeIterator operator++(int)
68	{NodeIterator tmp(*this); GoNext(); return tmp;}
69	bool isValid() { return n!=INVALID; }
70
71	N &operator*() const { return G->Data(n); }
72	N *operator->() const { return &G->Data(n); }
73
74	bool operator==(const NodeIterator &i) const {return n==i.n;}
75	bool operator!=(const NodeIterator &i) const {return n!=i.n;}
76
77	int Index() { return n; } //If the nodes are indexable
78	friend class Graph;
79	friend class EdgeIterator;
80	friend class InEdgeIterator;
81	friend class OutEdgeIterator;
82	friend class BiEdgeIterator;
83	friend class SymEdgeIterator;
84	friend class AllEdgeIterator;
85	friend class FirstAnythingTypeNode;
86
87	//Nem kellene egy:
88	// static NodeIterator &GetInvalid(); ?
89	};
90
91	class EdgeIterator
92	{
93
94	Graph<N,E> G; //Itt baj van!!!!! operator() miatt kell!
95	//Ez csak kicsit baj, de:
96	// Meg a From() es To() miatt!!!!!!!!!!
97
98	NEGRO::EdgePoint e;
99
100	public:
101	EdgeIterator() {;} //Kell inicializalni? (Nem)
102	EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
103
104	// Lehet, hogy ez a ketto nem kell!!!
105
106	NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
107	NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
108
109	bool isValid() {return e;}
110	E &operator*() const { return G->Data(e); }
111	E *operator->() const { return &G->Data(e); }
112
113	//operator const OutEdgeIterator ();
114	//operator const InEdgeIterator ();
115	//operator const BiEdgeIterator ();
116	//operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
117
118	bool operator==(const EdgeIterator &i) const {return e==i.e;}
119	bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
120
121	int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
122	//If the edges are indexable
123
124	friend class Graph;
125	friend class InEdgeIterator;
126	friend class OutEdgeIterator;
127	friend class BiEdgeIterator;
128	friend class SymEdgeIterator;
129	friend class AllEdgeIterator;
130	};
131
132	class BiEdgeIterator : public EdgeIterator
133	{
134	public:
135	BiEdgeIterator &GoNextIn() { e=e->NextIn(); return *this;}
136	BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
137	BiEdgeIterator NextIn() const {return BiEdgeIterator(*this).GoNextIn();}
138	BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
139
140	operator InEdgeIterator ()
141	{InEdgeIterator i; i.G=G;i.e=e;return i;}
142	operator OutEdgeIterator ()
143	{OutEdgeIterator i; i.G=G;i.e=e;return i;}
144	//operator const SymEdgeIterator ()
145
146	friend class Graph;
147	};
148
149	class InEdgeIterator : public EdgeIterator
150	//Ne a BiEdgeIterator-bol szarmazzon?
151	{
152	public:
153	InEdgeIterator() {}
154	InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
155	{ G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
156
157	InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
158	InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
159	InEdgeIterator &operator++() { return GoNext();}
160	InEdgeIterator operator++(int)
161	{InEdgeIterator tmp(*this); GoNext(); return tmp;}
162
163	operator const OutEdgeIterator ()
164	{OutEdgeIterator i; i.G=G;i.e=e;return i;}
165	operator const BiEdgeIterator ()
166	{EdgeIterator i; i.G=G;i.e=e;return i;}
167	// operator const SymEdgeIterator ();
168
169	NodeIterator Anode() const {return To();}
170	NodeIterator Bnode() const {return From();}
171
172	friend class Graph;
173	};
174
175	class OutEdgeIterator : public EdgeIterator
176	{
177	public:
178	OutEdgeIterator() {}
179	OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
180	{ G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
181
182	OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
183	OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
184	OutEdgeIterator &operator++() { return GoNext();}
185	OutEdgeIterator operator++(int)
186	{OutEdgeIterator tmp(*this); GoNext(); return tmp;}
187
188	NodeIterator Anode() const {return From();}
189	NodeIterator Bnode() const {return To();}
190
191	operator const InEdgeIterator ()
192	{InEdgeIterator i; i.G=G;i.e=e;return i;}
193	operator const BiEdgeIterator ()
194	{BiEdgeIterator i; i.G=G;i.e=e;return i;}
195	//operator const SymEdgeIterator();
196
197	friend class Graph;
198	};
199
200	class SymEdgeIterator : public EdgeIterator
201	{
202	NodeIterator n; // Itt ketszer van a G
203
204	public:
205	SymEdgeIterator() {}
206	SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
207	{ G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
208
209	SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
210	SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
211	SymEdgeIterator &operator++() { return GoNext();}
212	SymEdgeIterator operator++(int)
213	{SymEdgeIterator tmp(*this); GoNext(); return tmp;}
214
215	NodeIterator Anode() const {return n;}
216	NodeIterator Bnode() const {return n.n==From().n?To():From();}
217
218	operator const InEdgeIterator ()
219	{InEdgeIterator i; i.G=G;i.e=e;return i;}
220	operator const OutEdgeIterator ()
221	{OutEdgeIterator i; i.G=G;i.e=e;return i;}
222	operator const BiEdgeIterator ()
223	{BiEdgeIterator i; i.G=G;i.e=e;return i;}
224
225	friend class Graph;
226	};
227
228	class AllEdgeIterator : public EdgeIterator
229	{
230	NodeIterator n; // Itt ketszer van a G
231
232	public:
233	AllEdgeIterator() {}
234	AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
235	{
236	e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
237	}
238
239	AllEdgeIterator &GoNext()
240	{
241	e=e->NextOut();
242	if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
243	return *this;
244	}
245	AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
246	AllEdgeIterator &operator++() { return GoNext();}
247	AllEdgeIterator operator++(int)
248	{AllEdgeIterator tmp(*this); GoNext(); return tmp;}
249
250
251	NodeIterator Anode() const {return n;}
252	NodeIterator Bnode() const {return n.n==From().n?To():From();}
253
254	operator const InEdgeIterator ()
255	{InEdgeIterator i; i.G=G;i.e=e;return i;}
256	operator const OutEdgeIterator ()
257	{OutEdgeIterator i; i.G=G;i.e=e;return i;}
258	operator const BiEdgeIterator ()
259	{BiEdgeIterator i; i.G=G;i.e=e;return i;}
260
261	friend class Graph;
262	};
263
264	typedef NodeIterator DeletingNodeIterator;
265	typedef EdgeIterator DeletingEdgeIterator;
266	typedef BiEdgeIterator DeletingBiEdgeIterator;
267	typedef OutEdgeIterator DeletingOutEdgeIterator;
268	typedef InEdgeIterator DeletingInEdgeIterator;
269	typedef SymEdgeIterator DeletingSymEdgeIterator;
270
271	const NodeIterator FirstNode()
272	{
273	NodeIterator i;
274	i.G=this;i.n=OldGraph<N,E>::FirstNode();
275	return i;
276	}
277
278	void GetFirst(NodePoint &p) { p=OldGraph<N,E>::FirstNode(); }
279
280	void GetFirst(InEdgePoint &p,const NodePoint &n)
281	{ p=OldGraph<N,E>::FirstIn(n); }
282	void GetFirst(OutEdgePoint &p,const NodePoint &n)
283	{ p=OldGraph<N,E>::FirstOut(n); }
284	void GetFirst(SymEdgePoint &p,const NodePoint &n)
285	{ p=OldGraph<N,E>::FirstEdge(n); }
286	void GetFirst(EdgePoint &p) //Vegigmegy mindenen
287	{ p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
288
289	void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
290
291	void GetFirst(InEdgeIterator &i,const NodeIterator &n)
292	{ i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
293	void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
294	{ i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
295	void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
296	{ i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
297	void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
298	{
299	i.G=this;
300	GetFirst(i.n);
301	i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
302	}
303
304
305
306	//Vagy beginnode()?
307	const DeletingEdgeIterator FirstOut(const NodeIterator &n)
308	{
309	EdgeIterator i;
310	i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
311	return i;
312	}
313	const DeletingEdgeIterator FirstIn(const NodeIterator &n)
314	{
315	EdgeIterator i;
316	i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
317	return i;
318	}
319	const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
320	{
321	EdgeIterator i;
322	i.G=n.G;i.n=n.n;
323	i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
324	return i;
325	}
326
327	// class FirstAnythingType;
328	// friend class FirstAnythingType;
329
330	class FirstAnythingTypeNode
331	{
332	NodeIterator n;
333	public:
334	FirstAnythingTypeNode(NodeIterator i) : n(i) {}
335
336	operator const InEdgeIterator () const
337	{InEdgeIterator i; n.G->GetFirst(i,n);return i;}
338	operator const OutEdgeIterator () const
339	{OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
340	operator const SymEdgeIterator () const
341	{SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
342
343	operator const InEdgePoint () const
344	{InEdgePoint i; n.G->GetFirst(i,n);return i;}
345	operator const OutEdgePoint () const
346	{OutEdgePoint i; n.G->GetFirst(i,n);return i;}
347	operator const SymEdgePoint () const
348	{SymEdgePoint i; n.G->GetFirst(i,n);return i;}
349	};
350
351	class FirstAnythingType
352	{
353	Graph<N,E> *G;
354	public:
355	FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
356
357	operator const AllEdgeIterator () const
358	{AllEdgeIterator i; G->GetFirst(i);return i;}
359	operator const EdgePoint () const
360	{EdgePoint i; G->GetFirst(i);return i;}
361	operator const NodeIterator () const
362	{NodeIterator i; G->GetFirst(i);return i;}
363	operator const NodePoint () const
364	{NodePoint i; G->GetFirst(i);return i;}
365	} _FST;
366
367	// const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
368	FirstAnythingTypeNode First(NodeIterator &i)
369	{FirstAnythingTypeNode t(i); return t;}
370	const FirstAnythingType &First() {return _FST;}
371
372	// LastNode() vagy endnode() stb. Nem kell?
373
374	DeletingNodeIterator AddNode()
375	{
376	DeletingNodeIterator i;
377	i.G=this; i.n=OldGraph<N,E>::AddNode();
378	return i;
379	}
380	DeletingEdgeIterator
381	AddEdge(const NodeIterator from,const NodeIterator to)
382	{
383	DeletingEdgeIterator i;
384	i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
385	}
386
387	void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
388	void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
389
390	int NodeNum() { OldGraph<N,E>::NodeNum(); }
391	void Clean() { OldGraph<N,E>::Clean(); }
392
393	Graph() : _FST(this) {}
394	};
395
396	/* Ez itt a fiam kommentje:
397	<v n nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
398	vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
399	<< < < < < < < .cx..x.c.cc.c
400	mcmn
401	*/
402
403	}
404
405	#endif

Note: See TracBrowser for help on using the repository browser.

Download in other formats: