1 // -*-mode: c++; -*- |
1 // -*- c++ -*- |
2 #ifndef GRAPH_WRAPPER_H |
2 #ifndef GRAPH_WRAPPER_H |
3 #define GRAPH_WRAPPER_H |
3 #define GRAPH_WRAPPER_H |
|
4 |
|
5 #include <invalid.h> |
4 |
6 |
5 namespace hugo { |
7 namespace hugo { |
6 |
8 |
7 template<typename Graph> |
9 template<typename Graph> |
8 class TrivGraphWrapper { |
10 class TrivGraphWrapper { |
9 Graph* graph; |
11 Graph* graph; |
10 |
12 |
11 public: |
13 public: |
12 typedef Graph BaseGraph; |
14 typedef Graph BaseGraph; |
13 |
15 |
|
16 typedef typename Graph::Node Node; |
14 typedef typename Graph::NodeIt NodeIt; |
17 typedef typename Graph::NodeIt NodeIt; |
15 typedef typename Graph::EachNodeIt EachNodeIt; |
18 |
16 |
19 typedef typename Graph::Edge Edge; |
17 typedef typename Graph::EdgeIt EdgeIt; |
|
18 typedef typename Graph::OutEdgeIt OutEdgeIt; |
20 typedef typename Graph::OutEdgeIt OutEdgeIt; |
19 typedef typename Graph::InEdgeIt InEdgeIt; |
21 typedef typename Graph::InEdgeIt InEdgeIt; |
20 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
22 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
21 typedef typename Graph::EachEdgeIt EachEdgeIt; |
23 typedef typename Graph::EdgeIt EdgeIt; |
22 |
24 |
23 //TrivGraphWrapper() : graph(0) { } |
25 //TrivGraphWrapper() : graph(0) { } |
24 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
26 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
25 |
27 |
26 void setGraph(Graph& _graph) { graph = &_graph; } |
28 void setGraph(Graph& _graph) { graph = &_graph; } |
27 Graph& getGraph() const { return (*graph); } |
29 Graph& getGraph() const { return (*graph); } |
28 |
30 |
29 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } |
31 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
30 template<typename I, typename P> I& getFirst(I& i, const P& p) const { |
32 template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
31 return graph->getFirst(i, p); } |
33 return graph->/*getF*/first(i, p); } |
32 |
34 |
33 template<typename I> I getNext(const I& i) const { |
35 template<typename I> I getNext(const I& i) const { |
34 return graph->getNext(i); } |
36 return graph->getNext(i); } |
35 template<typename I> I& next(I &i) const { return graph->next(i); } |
37 template<typename I> I& next(I &i) const { return graph->next(i); } |
36 |
38 |
37 template< typename It > It first() const { |
39 template< typename It > It first() const { |
38 It e; getFirst(e); return e; } |
40 It e; /*getF*/first(e); return e; } |
39 |
41 |
40 template< typename It > It first(const NodeIt& v) const { |
42 template< typename It > It first(const Node& v) const { |
41 It e; getFirst(e, v); return e; } |
43 It e; /*getF*/first(e, v); return e; } |
42 |
44 |
43 NodeIt head(const EdgeIt& e) const { return graph->head(e); } |
45 Node head(const Edge& e) const { return graph->head(e); } |
44 NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } |
46 Node tail(const Edge& e) const { return graph->tail(e); } |
45 |
47 |
46 template<typename I> bool valid(const I& i) const |
48 template<typename I> bool valid(const I& i) const |
47 { return graph->valid(i); } |
49 { return graph->valid(i); } |
48 |
50 |
49 //template<typename I> void setInvalid(const I &i); |
51 //template<typename I> void setInvalid(const I &i); |
50 //{ return graph->setInvalid(i); } |
52 //{ return graph->setInvalid(i); } |
51 |
53 |
52 int nodeNum() const { return graph->nodeNum(); } |
54 int nodeNum() const { return graph->nodeNum(); } |
53 int edgeNum() const { return graph->edgeNum(); } |
55 int edgeNum() const { return graph->edgeNum(); } |
54 |
56 |
55 template<typename I> NodeIt aNode(const I& e) const { |
57 template<typename I> Node aNode(const I& e) const { |
56 return graph->aNode(e); } |
58 return graph->aNode(e); } |
57 template<typename I> NodeIt bNode(const I& e) const { |
59 template<typename I> Node bNode(const I& e) const { |
58 return graph->bNode(e); } |
60 return graph->bNode(e); } |
59 |
61 |
60 NodeIt addNode() const { return graph->addNode(); } |
62 Node addNode() const { return graph->addNode(); } |
61 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { |
63 Edge addEdge(const Node& tail, const Node& head) const { |
62 return graph->addEdge(tail, head); } |
64 return graph->addEdge(tail, head); } |
63 |
65 |
64 template<typename I> void erase(const I& i) const { graph->erase(i); } |
66 template<typename I> void erase(const I& i) const { graph->erase(i); } |
65 |
67 |
66 void clear() const { graph->clear(); } |
68 void clear() const { graph->clear(); } |
88 Graph* graph; |
90 Graph* graph; |
89 |
91 |
90 public: |
92 public: |
91 typedef Graph BaseGraph; |
93 typedef Graph BaseGraph; |
92 |
94 |
93 typedef typename Graph::NodeIt NodeIt; |
95 typedef typename Graph::Node Node; |
94 typedef typename Graph::EachNodeIt EachNodeIt; |
96 typedef typename Graph::NodeIt NodeIt; |
95 |
97 |
96 typedef typename Graph::EdgeIt EdgeIt; |
98 typedef typename Graph::Edge Edge; |
97 typedef typename Graph::OutEdgeIt InEdgeIt; |
99 typedef typename Graph::OutEdgeIt InEdgeIt; |
98 typedef typename Graph::InEdgeIt OutEdgeIt; |
100 typedef typename Graph::InEdgeIt OutEdgeIt; |
99 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
101 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
100 typedef typename Graph::EachEdgeIt EachEdgeIt; |
102 typedef typename Graph::EdgeIt EdgeIt; |
101 |
103 |
102 //RevGraphWrapper() : graph(0) { } |
104 //RevGraphWrapper() : graph(0) { } |
103 RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
105 RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
104 |
106 |
105 void setGraph(Graph& _graph) { graph = &_graph; } |
107 void setGraph(Graph& _graph) { graph = &_graph; } |
106 Graph& getGraph() const { return (*graph); } |
108 Graph& getGraph() const { return (*graph); } |
107 |
109 |
108 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } |
110 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
109 template<typename I, typename P> I& getFirst(I& i, const P& p) const { |
111 template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
110 return graph->getFirst(i, p); } |
112 return graph->/*getF*/first(i, p); } |
111 |
113 |
112 template<typename I> I getNext(const I& i) const { |
114 template<typename I> I getNext(const I& i) const { |
113 return graph->getNext(i); } |
115 return graph->getNext(i); } |
114 template<typename I> I& next(I &i) const { return graph->next(i); } |
116 template<typename I> I& next(I &i) const { return graph->next(i); } |
115 |
117 |
116 template< typename It > It first() const { |
118 template< typename It > It first() const { |
117 It e; getFirst(e); return e; } |
119 It e; /*getF*/first(e); return e; } |
118 |
120 |
119 template< typename It > It first(const NodeIt& v) const { |
121 template< typename It > It first(const Node& v) const { |
120 It e; getFirst(e, v); return e; } |
122 It e; /*getF*/first(e, v); return e; } |
121 |
123 |
122 NodeIt head(const EdgeIt& e) const { return graph->tail(e); } |
124 Node head(const Edge& e) const { return graph->tail(e); } |
123 NodeIt tail(const EdgeIt& e) const { return graph->head(e); } |
125 Node tail(const Edge& e) const { return graph->head(e); } |
124 |
126 |
125 template<typename I> bool valid(const I& i) const |
127 template<typename I> bool valid(const I& i) const |
126 { return graph->valid(i); } |
128 { return graph->valid(i); } |
127 |
129 |
128 //template<typename I> void setInvalid(const I &i); |
130 //template<typename I> void setInvalid(const I &i); |
129 //{ return graph->setInvalid(i); } |
131 //{ return graph->setInvalid(i); } |
130 |
132 |
131 template<typename I> NodeIt aNode(const I& e) const { |
133 template<typename I> Node aNode(const I& e) const { |
132 return graph->aNode(e); } |
134 return graph->aNode(e); } |
133 template<typename I> NodeIt bNode(const I& e) const { |
135 template<typename I> Node bNode(const I& e) const { |
134 return graph->bNode(e); } |
136 return graph->bNode(e); } |
135 |
137 |
136 NodeIt addNode() const { return graph->addNode(); } |
138 Node addNode() const { return graph->addNode(); } |
137 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { |
139 Edge addEdge(const Node& tail, const Node& head) const { |
138 return graph->addEdge(tail, head); } |
140 return graph->addEdge(tail, head); } |
139 |
141 |
140 int nodeNum() const { return graph->nodeNum(); } |
142 int nodeNum() const { return graph->nodeNum(); } |
141 int edgeNum() const { return graph->edgeNum(); } |
143 int edgeNum() const { return graph->edgeNum(); } |
142 |
144 |
167 Graph* graph; |
169 Graph* graph; |
168 |
170 |
169 public: |
171 public: |
170 typedef Graph BaseGraph; |
172 typedef Graph BaseGraph; |
171 |
173 |
|
174 typedef typename Graph::Node Node; |
172 typedef typename Graph::NodeIt NodeIt; |
175 typedef typename Graph::NodeIt NodeIt; |
173 typedef typename Graph::EachNodeIt EachNodeIt; |
176 |
174 |
177 //typedef typename Graph::Edge Edge; |
175 //typedef typename Graph::EdgeIt EdgeIt; |
|
176 //typedef typename Graph::OutEdgeIt OutEdgeIt; |
178 //typedef typename Graph::OutEdgeIt OutEdgeIt; |
177 //typedef typename Graph::InEdgeIt InEdgeIt; |
179 //typedef typename Graph::InEdgeIt InEdgeIt; |
178 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
180 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
179 //typedef typename Graph::EachEdgeIt EachEdgeIt; |
181 //typedef typename Graph::EdgeIt EdgeIt; |
180 |
182 |
181 //private: |
183 //private: |
182 typedef typename Graph::EdgeIt GraphEdgeIt; |
184 typedef typename Graph::Edge GraphEdge; |
183 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
185 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
184 typedef typename Graph::InEdgeIt GraphInEdgeIt; |
186 typedef typename Graph::InEdgeIt GraphInEdgeIt; |
185 //public: |
187 //public: |
186 |
188 |
187 //UndirGraphWrapper() : graph(0) { } |
189 //UndirGraphWrapper() : graph(0) { } |
188 UndirGraphWrapper(Graph& _graph) : graph(&_graph) { } |
190 UndirGraphWrapper(Graph& _graph) : graph(&_graph) { } |
189 |
191 |
190 void setGraph(Graph& _graph) { graph = &_graph; } |
192 void setGraph(Graph& _graph) { graph = &_graph; } |
191 Graph& getGraph() const { return (*graph); } |
193 Graph& getGraph() const { return (*graph); } |
192 |
194 |
193 class EdgeIt { |
195 class Edge { |
194 friend class UndirGraphWrapper<Graph>; |
196 friend class UndirGraphWrapper<Graph>; |
195 bool out_or_in; //true iff out |
197 bool out_or_in; //true iff out |
196 GraphOutEdgeIt out; |
198 GraphOutEdgeIt out; |
197 GraphInEdgeIt in; |
199 GraphInEdgeIt in; |
198 public: |
200 public: |
199 EdgeIt() : out_or_in(true), out(), in() { } |
201 Edge() : out_or_in(), out(), in() { } |
200 operator GraphEdgeIt() const { |
202 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
|
203 operator GraphEdge() const { |
201 if (out_or_in) return(out); else return(in); |
204 if (out_or_in) return(out); else return(in); |
202 } |
205 } |
203 }; |
206 friend bool operator==(const Edge& u, const Edge& v) { |
204 |
207 if (v.out_or_in) |
205 class OutEdgeIt : public EdgeIt { |
208 return (u.out_or_in && u.out==v.out); |
|
209 else |
|
210 return (!u.out_or_in && u.in==v.in); |
|
211 } |
|
212 friend bool operator!=(const Edge& u, const Edge& v) { |
|
213 if (v.out_or_in) |
|
214 return (!u.out_or_in || u.out!=v.out); |
|
215 else |
|
216 return (u.out_or_in || u.in!=v.in); |
|
217 } |
|
218 }; |
|
219 |
|
220 class OutEdgeIt : public Edge { |
206 friend class UndirGraphWrapper<Graph>; |
221 friend class UndirGraphWrapper<Graph>; |
207 public: |
222 public: |
208 OutEdgeIt() : EdgeIt() { } |
223 OutEdgeIt() : Edge() { } |
209 OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { |
224 OutEdgeIt(const Invalid& i) : Edge(i) { } |
210 _G.graph->getFirst(out, n); |
225 OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { |
|
226 out_or_in=true; |
|
227 _G.graph->/*getF*/first(out, n); |
211 if (!(_G.graph->valid(out))) { |
228 if (!(_G.graph->valid(out))) { |
212 out_or_in=false; |
229 out_or_in=false; |
213 _G.graph->getFirst(in, n); |
230 _G.graph->/*getF*/first(in, n); |
214 } |
231 } |
215 } |
232 } |
216 }; |
233 }; |
217 |
234 |
218 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { |
235 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { |
219 e.out_or_in=true; |
236 e.out_or_in=true; |
220 graph->getFirst(e.out, n); |
237 graph->/*getF*/first(e.out, n); |
221 if (!(graph->valid(e.out))) { |
238 if (!(graph->valid(e.out))) { |
222 e.out_or_in=false; |
239 e.out_or_in=false; |
223 graph->getFirst(e.in, n); |
240 graph->/*getF*/first(e.in, n); |
224 } |
241 } |
225 return e; |
242 return e; |
226 } |
243 } |
227 |
244 |
228 OutEdgeIt& next(OutEdgeIt& e) const { |
245 OutEdgeIt& next(OutEdgeIt& e) const { |
229 if (e.out_or_in) { |
246 if (e.out_or_in) { |
230 NodeIt n=graph->tail(e.out); |
247 Node n=graph->tail(e.out); |
231 graph->next(e.out); |
248 graph->next(e.out); |
232 if (!graph->valid(e.out)) { |
249 if (!graph->valid(e.out)) { |
233 e.out_or_in=false; |
250 e.out_or_in=false; |
234 graph->getFirst(e.in, n); |
251 graph->/*getF*/first(e.in, n); |
235 } |
252 } |
236 } else { |
253 } else { |
237 graph->next(e.in); |
254 graph->next(e.in); |
238 } |
255 } |
239 return e; |
256 return e; |
240 } |
257 } |
241 |
258 |
242 NodeIt aNode(const OutEdgeIt& e) const { |
259 Node aNode(const OutEdgeIt& e) const { |
243 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } |
260 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } |
244 NodeIt bNode(const OutEdgeIt& e) const { |
261 Node bNode(const OutEdgeIt& e) const { |
245 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
262 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
246 |
263 |
247 typedef OutEdgeIt InEdgeIt; |
264 typedef OutEdgeIt InEdgeIt; |
248 |
265 |
249 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } |
266 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
250 // template<typename I, typename P> I& getFirst(I& i, const P& p) const { |
267 // template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
251 // return graph->getFirst(i, p); } |
268 // return graph->/*getF*/first(i, p); } |
252 |
269 |
253 template<typename I> I getNext(const I& i) const { |
270 template<typename I> I getNext(const I& i) const { |
254 return graph->getNext(i); } |
271 return graph->getNext(i); } |
255 template<typename I> I& next(I &i) const { return graph->next(i); } |
272 template<typename I> I& next(I &i) const { return graph->next(i); } |
256 |
273 |
257 template< typename It > It first() const { |
274 template< typename It > It first() const { |
258 It e; getFirst(e); return e; } |
275 It e; /*getF*/first(e); return e; } |
259 |
276 |
260 template< typename It > It first(const NodeIt& v) const { |
277 template< typename It > It first(const Node& v) const { |
261 It e; getFirst(e, v); return e; } |
278 It e; /*getF*/first(e, v); return e; } |
262 |
279 |
263 NodeIt head(const EdgeIt& e) const { return graph->head(e); } |
280 Node head(const Edge& e) const { return graph->head(e); } |
264 NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } |
281 Node tail(const Edge& e) const { return graph->tail(e); } |
265 |
282 |
266 template<typename I> bool valid(const I& i) const |
283 template<typename I> bool valid(const I& i) const |
267 { return graph->valid(i); } |
284 { return graph->valid(i); } |
268 |
285 |
269 //template<typename I> void setInvalid(const I &i); |
286 //template<typename I> void setInvalid(const I &i); |
270 //{ return graph->setInvalid(i); } |
287 //{ return graph->setInvalid(i); } |
271 |
288 |
272 int nodeNum() const { return graph->nodeNum(); } |
289 int nodeNum() const { return graph->nodeNum(); } |
273 int edgeNum() const { return graph->edgeNum(); } |
290 int edgeNum() const { return graph->edgeNum(); } |
274 |
291 |
275 // template<typename I> NodeIt aNode(const I& e) const { |
292 // template<typename I> Node aNode(const I& e) const { |
276 // return graph->aNode(e); } |
293 // return graph->aNode(e); } |
277 // template<typename I> NodeIt bNode(const I& e) const { |
294 // template<typename I> Node bNode(const I& e) const { |
278 // return graph->bNode(e); } |
295 // return graph->bNode(e); } |
279 |
296 |
280 NodeIt addNode() const { return graph->addNode(); } |
297 Node addNode() const { return graph->addNode(); } |
281 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { |
298 Edge addEdge(const Node& tail, const Node& head) const { |
282 return graph->addEdge(tail, head); } |
299 return graph->addEdge(tail, head); } |
283 |
300 |
284 template<typename I> void erase(const I& i) const { graph->erase(i); } |
301 template<typename I> void erase(const I& i) const { graph->erase(i); } |
285 |
302 |
286 void clear() const { graph->clear(); } |
303 void clear() const { graph->clear(); } |
310 // Graph* graph; |
327 // Graph* graph; |
311 |
328 |
312 // public: |
329 // public: |
313 // typedef Graph BaseGraph; |
330 // typedef Graph BaseGraph; |
314 |
331 |
|
332 // typedef typename Graph::Node Node; |
|
333 // typedef typename Graph::Edge Edge; |
|
334 |
315 // typedef typename Graph::NodeIt NodeIt; |
335 // typedef typename Graph::NodeIt NodeIt; |
316 // typedef typename Graph::EdgeIt EdgeIt; |
|
317 |
|
318 // typedef typename Graph::EachNodeIt EachNodeIt; |
|
319 |
336 |
320 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon |
337 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon |
321 // //iranyitatlant, ami van |
338 // //iranyitatlant, ami van |
322 // //mert csak 1 dolgot lehet be typedef-elni |
339 // //mert csak 1 dolgot lehet be typedef-elni |
323 // typedef typename Graph::OutEdgeIt SymEdgeIt; |
340 // typedef typename Graph::OutEdgeIt SymEdgeIt; |
324 // //typedef typename Graph::InEdgeIt SymEdgeIt; |
341 // //typedef typename Graph::InEdgeIt SymEdgeIt; |
325 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
342 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
326 // typedef typename Graph::EachEdgeIt EachEdgeIt; |
343 // typedef typename Graph::EdgeIt EdgeIt; |
327 |
344 |
328 // int nodeNum() const { return graph->nodeNum(); } |
345 // int nodeNum() const { return graph->nodeNum(); } |
329 // int edgeNum() const { return graph->edgeNum(); } |
346 // int edgeNum() const { return graph->edgeNum(); } |
330 |
347 |
331 // template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } |
348 // template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
332 // template<typename I, typename P> I& getFirst(I& i, const P& p) const { |
349 // template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
333 // return graph->getFirst(i, p); } |
350 // return graph->/*getF*/first(i, p); } |
334 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
351 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
335 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
352 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
336 |
353 |
337 // template< typename It > It first() const { |
354 // template< typename It > It first() const { |
338 // It e; getFirst(e); return e; } |
355 // It e; /*getF*/first(e); return e; } |
339 |
356 |
340 // template< typename It > It first(NodeIt v) const { |
357 // template< typename It > It first(Node v) const { |
341 // It e; getFirst(e, v); return e; } |
358 // It e; /*getF*/first(e, v); return e; } |
342 |
359 |
343 // NodeIt head(const EdgeIt& e) const { return graph->head(e); } |
360 // Node head(const Edge& e) const { return graph->head(e); } |
344 // NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } |
361 // Node tail(const Edge& e) const { return graph->tail(e); } |
345 |
362 |
346 // template<typename I> NodeIt aNode(const I& e) const { |
363 // template<typename I> Node aNode(const I& e) const { |
347 // return graph->aNode(e); } |
364 // return graph->aNode(e); } |
348 // template<typename I> NodeIt bNode(const I& e) const { |
365 // template<typename I> Node bNode(const I& e) const { |
349 // return graph->bNode(e); } |
366 // return graph->bNode(e); } |
350 |
367 |
351 // //template<typename I> bool valid(const I i); |
368 // //template<typename I> bool valid(const I i); |
352 // //{ return graph->valid(i); } |
369 // //{ return graph->valid(i); } |
353 |
370 |
354 // //template<typename I> void setInvalid(const I &i); |
371 // //template<typename I> void setInvalid(const I &i); |
355 // //{ return graph->setInvalid(i); } |
372 // //{ return graph->setInvalid(i); } |
356 |
373 |
357 // NodeIt addNode() { return graph->addNode(); } |
374 // Node addNode() { return graph->addNode(); } |
358 // EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { |
375 // Edge addEdge(const Node& tail, const Node& head) { |
359 // return graph->addEdge(tail, head); } |
376 // return graph->addEdge(tail, head); } |
360 |
377 |
361 // template<typename I> void erase(const I& i) { graph->erase(i); } |
378 // template<typename I> void erase(const I& i) { graph->erase(i); } |
362 |
379 |
363 // void clear() { graph->clear(); } |
380 // void clear() { graph->clear(); } |
375 |
392 |
376 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
393 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
377 class ResGraphWrapper { |
394 class ResGraphWrapper { |
378 public: |
395 public: |
379 typedef Graph BaseGraph; |
396 typedef Graph BaseGraph; |
|
397 typedef typename Graph::Node Node; |
380 typedef typename Graph::NodeIt NodeIt; |
398 typedef typename Graph::NodeIt NodeIt; |
381 typedef typename Graph::EachNodeIt EachNodeIt; |
|
382 private: |
399 private: |
383 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
400 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
384 typedef typename Graph::InEdgeIt OldInEdgeIt; |
401 typedef typename Graph::InEdgeIt OldInEdgeIt; |
385 const Graph* G; |
402 const Graph* graph; |
386 FlowMap* flow; |
403 FlowMap* flow; |
387 const CapacityMap* capacity; |
404 const CapacityMap* capacity; |
388 public: |
405 public: |
389 |
406 |
390 ResGraphWrapper(const Graph& _G, FlowMap& _flow, |
407 ResGraphWrapper(const Graph& _G, FlowMap& _flow, |
391 const CapacityMap& _capacity) : |
408 const CapacityMap& _capacity) : |
392 G(&_G), flow(&_flow), capacity(&_capacity) { } |
409 graph(&_G), flow(&_flow), capacity(&_capacity) { } |
393 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : |
|
394 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } |
|
395 |
410 |
396 void setGraph(const Graph& _graph) { graph = &_graph; } |
411 void setGraph(const Graph& _graph) { graph = &_graph; } |
397 const Graph& getGraph() const { return (*G); } |
412 const Graph& getGraph() const { return (*graph); } |
398 |
413 |
399 class EdgeIt; |
414 class Edge; |
400 class OutEdgeIt; |
415 class OutEdgeIt; |
401 friend class EdgeIt; |
416 friend class Edge; |
402 friend class OutEdgeIt; |
417 friend class OutEdgeIt; |
403 |
418 |
404 class EdgeIt { |
419 class Edge { |
405 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
420 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
406 protected: |
421 protected: |
407 bool out_or_in; //true, iff out |
422 bool out_or_in; //true, iff out |
408 OldOutEdgeIt out; |
423 OldOutEdgeIt out; |
409 OldInEdgeIt in; |
424 OldInEdgeIt in; |
410 public: |
425 public: |
411 EdgeIt() : out_or_in(true) { } |
426 Edge() : out_or_in(true) { } |
|
427 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
412 // bool valid() const { |
428 // bool valid() const { |
413 // return out_or_in && out.valid() || in.valid(); } |
429 // return out_or_in && out.valid() || in.valid(); } |
414 }; |
430 friend bool operator==(const Edge& u, const Edge& v) { |
415 |
431 if (v.out_or_in) |
416 |
432 return (u.out_or_in && u.out==v.out); |
417 class OutEdgeIt : public EdgeIt { |
433 else |
|
434 return (!u.out_or_in && u.in==v.in); |
|
435 } |
|
436 friend bool operator!=(const Edge& u, const Edge& v) { |
|
437 if (v.out_or_in) |
|
438 return (!u.out_or_in || u.out!=v.out); |
|
439 else |
|
440 return (u.out_or_in || u.in!=v.in); |
|
441 } |
|
442 }; |
|
443 |
|
444 |
|
445 class OutEdgeIt : public Edge { |
418 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
446 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
419 public: |
447 public: |
420 OutEdgeIt() { } |
448 OutEdgeIt() { } |
421 //FIXME |
449 //FIXME |
422 OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { } |
450 OutEdgeIt(const Edge& e) : Edge(e) { } |
|
451 OutEdgeIt(const Invalid& i) : Edge(i) { } |
423 private: |
452 private: |
424 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() { |
453 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
425 resG.G->getFirst(out, v); |
454 resG.graph->/*getF*/first(out, v); |
426 while( out.valid() && !(resG.free(out)>0) ) { ++out; } |
455 while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
427 if (!out.valid()) { |
456 if (!resG.graph->valid(out)) { |
428 out_or_in=0; |
457 out_or_in=0; |
429 resG.G->getFirst(in, v); |
458 resG.graph->/*getF*/first(in, v); |
430 while( in.valid() && !(resG.free(in)>0) ) { ++in; } |
459 while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
431 } |
460 } |
432 } |
461 } |
433 // public: |
462 // public: |
434 // OutEdgeIt& operator++() { |
463 // OutEdgeIt& operator++() { |
435 // if (out_or_in) { |
464 // if (out_or_in) { |
436 // NodeIt v=/*resG->*/G->aNode(out); |
465 // Node v=/*resG->*/G->aNode(out); |
437 // ++out; |
466 // ++out; |
438 // while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } |
467 // while( out.valid() && !(Edge::free()>0) ) { ++out; } |
439 // if (!out.valid()) { |
468 // if (!out.valid()) { |
440 // out_or_in=0; |
469 // out_or_in=0; |
441 // G->getFirst(in, v); |
470 // G->/*getF*/first(in, v); |
442 // while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } |
471 // while( in.valid() && !(Edge::free()>0) ) { ++in; } |
443 // } |
472 // } |
444 // } else { |
473 // } else { |
445 // ++in; |
474 // ++in; |
446 // while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } |
475 // while( in.valid() && !(Edge::free()>0) ) { ++in; } |
447 // } |
476 // } |
448 // return *this; |
477 // return *this; |
449 // } |
478 // } |
450 }; |
479 }; |
451 |
480 |
452 class EachEdgeIt : public EdgeIt { |
481 class EdgeIt : public Edge { |
453 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
482 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
454 typename Graph::EachNodeIt v; |
483 typename Graph::NodeIt v; |
455 public: |
484 public: |
456 EachEdgeIt() { } |
485 EdgeIt() { } |
457 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } |
486 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
458 EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() { |
487 EdgeIt(const Invalid& i) : Edge(i) { } |
459 resG.G->getFirst(v); |
488 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
460 if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt(); |
489 resG.graph->/*getF*/first(v); |
461 while (out.valid() && !(resG.free(out)>0) ) { ++out; } |
490 if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID); |
462 while (v.valid() && !out.valid()) { |
491 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
463 ++v; |
492 while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
464 if (v.valid()) resG.G->getFirst(out, v); |
493 resG.graph->next(v); |
465 while (out.valid() && !(resG.free(out)>0) ) { ++out; } |
494 if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); |
|
495 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
466 } |
496 } |
467 if (!out.valid()) { |
497 if (!resG.graph->valid(out)) { |
468 out_or_in=0; |
498 out_or_in=0; |
469 resG.G->getFirst(v); |
499 resG.graph->/*getF*/first(v); |
470 if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt(); |
500 if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID); |
471 while (in.valid() && !(resG.free(in)>0) ) { ++in; } |
501 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
472 while (v.valid() && !in.valid()) { |
502 while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
473 ++v; |
503 resG.graph->next(v); |
474 if (v.valid()) resG.G->getFirst(in, v); |
504 if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); |
475 while (in.valid() && !(resG.free(in)>0) ) { ++in; } |
505 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
476 } |
506 } |
477 } |
507 } |
478 } |
508 } |
479 // EachEdgeIt& operator++() { |
509 // EdgeIt& operator++() { |
480 // if (out_or_in) { |
510 // if (out_or_in) { |
481 // ++out; |
511 // ++out; |
482 // while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } |
512 // while (out.valid() && !(Edge::free()>0) ) { ++out; } |
483 // while (v.valid() && !out.valid()) { |
513 // while (v.valid() && !out.valid()) { |
484 // ++v; |
514 // ++v; |
485 // if (v.valid()) G->getFirst(out, v); |
515 // if (v.valid()) G->/*getF*/first(out, v); |
486 // while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } |
516 // while (out.valid() && !(Edge::free()>0) ) { ++out; } |
487 // } |
517 // } |
488 // if (!out.valid()) { |
518 // if (!out.valid()) { |
489 // out_or_in=0; |
519 // out_or_in=0; |
490 // G->getFirst(v); |
520 // G->/*getF*/first(v); |
491 // if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); |
521 // if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt(); |
492 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } |
522 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
493 // while (v.valid() && !in.valid()) { |
523 // while (v.valid() && !in.valid()) { |
494 // ++v; |
524 // ++v; |
495 // if (v.valid()) G->getFirst(in, v); |
525 // if (v.valid()) G->/*getF*/first(in, v); |
496 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } |
526 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
497 // } |
527 // } |
498 // } |
528 // } |
499 // } else { |
529 // } else { |
500 // ++in; |
530 // ++in; |
501 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } |
531 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
502 // while (v.valid() && !in.valid()) { |
532 // while (v.valid() && !in.valid()) { |
503 // ++v; |
533 // ++v; |
504 // if (v.valid()) G->getFirst(in, v); |
534 // if (v.valid()) G->/*getF*/first(in, v); |
505 // while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } |
535 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
506 // } |
536 // } |
507 // } |
537 // } |
508 // return *this; |
538 // return *this; |
509 // } |
539 // } |
510 }; |
540 }; |
511 |
541 |
512 EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); } |
542 NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); } |
513 OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { |
543 OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { |
514 e=OutEdgeIt(*this, v); |
544 e=OutEdgeIt(*this, v); |
515 } |
545 return e; |
516 EachEdgeIt& getFirst(EachEdgeIt& e) const { |
546 } |
517 e=EachEdgeIt(*this); |
547 EdgeIt& /*getF*/first(EdgeIt& e) const { |
|
548 e=EdgeIt(*this); |
|
549 return e; |
518 } |
550 } |
519 |
551 |
520 EachNodeIt& next(EachNodeIt& n) const { return G->next(n); } |
552 NodeIt& next(NodeIt& n) const { return graph->next(n); } |
521 |
553 |
522 OutEdgeIt& next(OutEdgeIt& e) const { |
554 OutEdgeIt& next(OutEdgeIt& e) const { |
523 if (e.out_or_in) { |
555 if (e.out_or_in) { |
524 NodeIt v=G->aNode(e.out); |
556 Node v=graph->aNode(e.out); |
525 ++(e.out); |
557 graph->next(e.out); |
526 while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } |
558 while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
527 if (!G->valid(e.out)) { |
559 if (!graph->valid(e.out)) { |
528 e.out_or_in=0; |
560 e.out_or_in=0; |
529 G->getFirst(e.in, v); |
561 graph->/*getF*/first(e.in, v); |
530 while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } |
562 while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
531 } |
563 } |
532 } else { |
564 } else { |
533 ++(e.in); |
565 graph->next(e.in); |
534 while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } |
566 while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
535 } |
567 } |
536 return e; |
568 return e; |
537 } |
569 } |
538 |
570 |
539 EachEdgeIt& next(EachEdgeIt& e) const { |
571 EdgeIt& next(EdgeIt& e) const { |
540 if (e.out_or_in) { |
572 if (e.out_or_in) { |
541 ++(e.out); |
573 graph->next(e.out); |
542 while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } |
574 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
543 while (G->valid(e.v) && !G->valid(e.out)) { |
575 while (graph->valid(e.v) && !graph->valid(e.out)) { |
544 ++(e.v); |
576 graph->next(e.v); |
545 if (G->valid(e.v)) G->getFirst(e.out, e.v); |
577 if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v); |
546 while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } |
578 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
547 } |
579 } |
548 if (!G->valid(e.out)) { |
580 if (!graph->valid(e.out)) { |
549 e.out_or_in=0; |
581 e.out_or_in=0; |
550 G->getFirst(e.v); |
582 graph->/*getF*/first(e.v); |
551 if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt(); |
583 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); |
552 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } |
584 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
553 while (G->valid(e.v) && !G->valid(e.in)) { |
585 while (graph->valid(e.v) && !graph->valid(e.in)) { |
554 ++(e.v); |
586 graph->next(e.v); |
555 if (G->valid(e.v)) G->getFirst(e.in, e.v); |
587 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); |
556 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } |
588 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
557 } |
589 } |
558 } |
590 } |
559 } else { |
591 } else { |
560 ++(e.in); |
592 graph->next(e.in); |
561 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } |
593 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
562 while (G->valid(e.v) && !G->valid(e.in)) { |
594 while (graph->valid(e.v) && !graph->valid(e.in)) { |
563 ++(e.v); |
595 graph->next(e.v); |
564 if (G->valid(e.v)) G->getFirst(e.in, e.v); |
596 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); |
565 while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } |
597 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
566 } |
598 } |
567 } |
599 } |
568 return e; |
600 return e; |
569 } |
601 } |
570 |
602 |
571 |
603 |
572 template< typename It > |
604 template< typename It > |
573 It first() const { |
605 It first() const { |
574 It e; |
606 It e; |
575 getFirst(e); |
607 /*getF*/first(e); |
576 return e; |
608 return e; |
577 } |
609 } |
578 |
610 |
579 template< typename It > |
611 template< typename It > |
580 It first(NodeIt v) const { |
612 It first(Node v) const { |
581 It e; |
613 It e; |
582 getFirst(e, v); |
614 /*getF*/first(e, v); |
583 return e; |
615 return e; |
584 } |
616 } |
585 |
617 |
586 NodeIt tail(EdgeIt e) const { |
618 Node tail(Edge e) const { |
587 return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); } |
619 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
588 NodeIt head(EdgeIt e) const { |
620 Node head(Edge e) const { |
589 return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); } |
621 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
590 |
622 |
591 NodeIt aNode(OutEdgeIt e) const { |
623 Node aNode(OutEdgeIt e) const { |
592 return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); } |
624 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
593 NodeIt bNode(OutEdgeIt e) const { |
625 Node bNode(OutEdgeIt e) const { |
594 return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); } |
626 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
595 |
627 |
596 int id(NodeIt v) const { return G->id(v); } |
628 int id(Node v) const { return graph->id(v); } |
597 |
629 |
598 bool valid(NodeIt n) const { return G->valid(n); } |
630 bool valid(Node n) const { return graph->valid(n); } |
599 bool valid(EdgeIt e) const { |
631 bool valid(Edge e) const { |
600 return e.out_or_in ? G->valid(e.out) : G->valid(e.in); } |
632 return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } |
601 |
633 |
602 void augment(const EdgeIt& e, Number a) const { |
634 void augment(const Edge& e, Number a) const { |
603 if (e.out_or_in) |
635 if (e.out_or_in) |
604 flow->set(e.out, flow->get(e.out)+a); |
636 flow->set(e.out, flow->get(e.out)+a); |
605 else |
637 else |
606 flow->set(e.in, flow->get(e.in)-a); |
638 flow->set(e.in, flow->get(e.in)-a); |
607 } |
639 } |
608 |
640 |
609 Number free(const EdgeIt& e) const { |
641 Number free(const Edge& e) const { |
610 if (e.out_or_in) |
642 if (e.out_or_in) |
611 return (capacity->get(e.out)-flow->get(e.out)); |
643 return (capacity->get(e.out)-flow->get(e.out)); |
612 else |
644 else |
613 return (flow->get(e.in)); |
645 return (flow->get(e.in)); |
614 } |
646 } |
683 //TrivGraphWrapper() : graph(0) { } |
715 //TrivGraphWrapper() : graph(0) { } |
684 //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { } |
716 //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { } |
685 |
717 |
686 //typedef Graph BaseGraph; |
718 //typedef Graph BaseGraph; |
687 |
719 |
|
720 //typedef typename Graph::Node Node; |
688 //typedef typename Graph::NodeIt NodeIt; |
721 //typedef typename Graph::NodeIt NodeIt; |
689 //typedef typename Graph::EachNodeIt EachNodeIt; |
722 |
690 |
723 //typedef typename Graph::Edge Edge; |
691 //typedef typename Graph::EdgeIt EdgeIt; |
|
692 //typedef typename Graph::OutEdgeIt OutEdgeIt; |
724 //typedef typename Graph::OutEdgeIt OutEdgeIt; |
693 //typedef typename Graph::InEdgeIt InEdgeIt; |
725 //typedef typename Graph::InEdgeIt InEdgeIt; |
694 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
726 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
695 //typedef typename Graph::EachEdgeIt EachEdgeIt; |
727 //typedef typename Graph::EdgeIt EdgeIt; |
696 |
728 |
|
729 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node; |
697 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; |
730 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; |
698 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt; |
731 |
699 |
732 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge; |
700 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; |
|
701 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; |
733 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; |
702 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; |
734 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; |
703 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
735 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
704 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt; |
736 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; |
705 |
737 |
706 EachNodeIt& getFirst(EachNodeIt& n) const { |
738 NodeIt& /*getF*/first(NodeIt& n) const { |
707 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n); |
739 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n); |
708 } |
740 } |
709 |
741 |
710 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { |
742 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { |
711 e=first_out_edges.get(n); |
743 e=first_out_edges.get(n); |
712 return e; |
744 return e; |
713 } |
745 } |
714 |
746 |
715 //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); } |
747 //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); } |
716 //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const { |
748 //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
717 // return getFirst(i, p); } |
749 // return /*getF*/first(i, p); } |
718 |
750 |
719 //template<typename I> I getNext(const I& i) const { |
751 //template<typename I> I getNext(const I& i) const { |
720 // return graph->getNext(i); } |
752 // return graph->getNext(i); } |
721 //template<typename I> I& next(I &i) const { return graph->next(i); } |
753 //template<typename I> I& next(I &i) const { return graph->next(i); } |
722 |
754 |
723 template< typename It > It first() const { |
755 template< typename It > It first() const { |
724 It e; getFirst(e); return e; } |
756 It e; /*getF*/first(e); return e; } |
725 |
757 |
726 template< typename It > It first(const NodeIt& v) const { |
758 template< typename It > It first(const Node& v) const { |
727 It e; getFirst(e, v); return e; } |
759 It e; /*getF*/first(e, v); return e; } |
728 |
760 |
729 //NodeIt head(const EdgeIt& e) const { return graph->head(e); } |
761 //Node head(const Edge& e) const { return graph->head(e); } |
730 //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } |
762 //Node tail(const Edge& e) const { return graph->tail(e); } |
731 |
763 |
732 //template<typename I> bool valid(const I& i) const |
764 //template<typename I> bool valid(const I& i) const |
733 // { return graph->valid(i); } |
765 // { return graph->valid(i); } |
734 |
766 |
735 //int nodeNum() const { return graph->nodeNum(); } |
767 //int nodeNum() const { return graph->nodeNum(); } |
736 //int edgeNum() const { return graph->edgeNum(); } |
768 //int edgeNum() const { return graph->edgeNum(); } |
737 |
769 |
738 //template<typename I> NodeIt aNode(const I& e) const { |
770 //template<typename I> Node aNode(const I& e) const { |
739 // return graph->aNode(e); } |
771 // return graph->aNode(e); } |
740 //template<typename I> NodeIt bNode(const I& e) const { |
772 //template<typename I> Node bNode(const I& e) const { |
741 // return graph->bNode(e); } |
773 // return graph->bNode(e); } |
742 |
774 |
743 //NodeIt addNode() const { return graph->addNode(); } |
775 //Node addNode() const { return graph->addNode(); } |
744 //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { |
776 //Edge addEdge(const Node& tail, const Node& head) const { |
745 // return graph->addEdge(tail, head); } |
777 // return graph->addEdge(tail, head); } |
746 |
778 |
747 //void erase(const OutEdgeIt& e) { |
779 //void erase(const OutEdgeIt& e) { |
748 // first_out_edge(this->tail(e))=e; |
780 // first_out_edge(this->tail(e))=e; |
749 //} |
781 //} |
750 void erase(const EdgeIt& e) { |
782 void erase(const Edge& e) { |
751 OutEdgeIt f(e); |
783 OutEdgeIt f(e); |
752 next(f); |
784 next(f); |
753 first_out_edges.set(this->tail(e), f); |
785 first_out_edges.set(this->tail(e), f); |
754 } |
786 } |
755 //template<typename I> void erase(const I& i) const { graph->erase(i); } |
787 //template<typename I> void erase(const I& i) const { graph->erase(i); } |
783 //Graph* graph; |
815 //Graph* graph; |
784 |
816 |
785 public: |
817 public: |
786 //typedef Graph BaseGraph; |
818 //typedef Graph BaseGraph; |
787 |
819 |
|
820 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node; |
788 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; |
821 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt; |
789 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt; |
822 |
790 |
823 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge; |
791 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; |
|
792 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; |
824 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; |
793 //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; |
825 //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; |
794 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
826 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
795 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt; |
827 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; |
796 |
828 |
797 //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges; |
829 //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges; |
798 |
830 |
799 public: |
831 public: |
800 FilterGraphWrapper(const Graph& _G, FlowMap& _flow, |
832 FilterGraphWrapper(const Graph& _G, FlowMap& _flow, |
801 const CapacityMap& _capacity) : |
833 const CapacityMap& _capacity) : |
802 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { |
834 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { |
803 } |
835 } |
804 |
836 |
805 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { |
837 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { |
806 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n); |
838 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n); |
807 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) |
839 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) |
808 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
840 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
809 return e; |
841 return e; |
810 } |
842 } |
811 |
843 |
812 EachNodeIt& next(EachNodeIt& e) const { |
844 NodeIt& next(NodeIt& e) const { |
813 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
845 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
814 } |
846 } |
815 |
847 |
816 OutEdgeIt& next(OutEdgeIt& e) const { |
848 OutEdgeIt& next(OutEdgeIt& e) const { |
817 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
849 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
818 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) |
850 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) |
819 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
851 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
820 return e; |
852 return e; |
821 } |
853 } |
822 |
854 |
823 EachNodeIt& getFirst(EachNodeIt& n) const { |
855 NodeIt& /*getF*/first(NodeIt& n) const { |
824 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n); |
856 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n); |
825 } |
857 } |
826 |
858 |
827 void erase(const EdgeIt& e) { |
859 void erase(const Edge& e) { |
828 OutEdgeIt f(e); |
860 OutEdgeIt f(e); |
829 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); |
861 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); |
830 while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) |
862 while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) |
831 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); |
863 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); |
832 first_out_edges.set(this->tail(e), f); |
864 first_out_edges.set(this->tail(e), f); |
836 //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
868 //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
837 |
869 |
838 //void setGraph(Graph& _graph) { graph = &_graph; } |
870 //void setGraph(Graph& _graph) { graph = &_graph; } |
839 //Graph& getGraph() const { return (*graph); } |
871 //Graph& getGraph() const { return (*graph); } |
840 |
872 |
841 //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } |
873 //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
842 //template<typename I, typename P> I& getFirst(I& i, const P& p) const { |
874 //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
843 // return graph->getFirst(i, p); } |
875 // return graph->/*getF*/first(i, p); } |
844 |
876 |
845 //template<typename I> I getNext(const I& i) const { |
877 //template<typename I> I getNext(const I& i) const { |
846 // return graph->getNext(i); } |
878 // return graph->getNext(i); } |
847 //template<typename I> I& next(I &i) const { return graph->next(i); } |
879 //template<typename I> I& next(I &i) const { return graph->next(i); } |
848 |
880 |
849 template< typename It > It first() const { |
881 template< typename It > It first() const { |
850 It e; getFirst(e); return e; } |
882 It e; /*getF*/first(e); return e; } |
851 |
883 |
852 template< typename It > It first(const NodeIt& v) const { |
884 template< typename It > It first(const Node& v) const { |
853 It e; getFirst(e, v); return e; } |
885 It e; /*getF*/first(e, v); return e; } |
854 |
886 |
855 //NodeIt head(const EdgeIt& e) const { return graph->head(e); } |
887 //Node head(const Edge& e) const { return graph->head(e); } |
856 //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } |
888 //Node tail(const Edge& e) const { return graph->tail(e); } |
857 |
889 |
858 //template<typename I> bool valid(const I& i) const |
890 //template<typename I> bool valid(const I& i) const |
859 // { return graph->valid(i); } |
891 // { return graph->valid(i); } |
860 |
892 |
861 //template<typename I> void setInvalid(const I &i); |
893 //template<typename I> void setInvalid(const I &i); |
862 //{ return graph->setInvalid(i); } |
894 //{ return graph->setInvalid(i); } |
863 |
895 |
864 //int nodeNum() const { return graph->nodeNum(); } |
896 //int nodeNum() const { return graph->nodeNum(); } |
865 //int edgeNum() const { return graph->edgeNum(); } |
897 //int edgeNum() const { return graph->edgeNum(); } |
866 |
898 |
867 //template<typename I> NodeIt aNode(const I& e) const { |
899 //template<typename I> Node aNode(const I& e) const { |
868 // return graph->aNode(e); } |
900 // return graph->aNode(e); } |
869 //template<typename I> NodeIt bNode(const I& e) const { |
901 //template<typename I> Node bNode(const I& e) const { |
870 // return graph->bNode(e); } |
902 // return graph->bNode(e); } |
871 |
903 |
872 //NodeIt addNode() const { return graph->addNode(); } |
904 //Node addNode() const { return graph->addNode(); } |
873 //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { |
905 //Edge addEdge(const Node& tail, const Node& head) const { |
874 // return graph->addEdge(tail, head); } |
906 // return graph->addEdge(tail, head); } |
875 |
907 |
876 //template<typename I> void erase(const I& i) const { graph->erase(i); } |
908 //template<typename I> void erase(const I& i) const { graph->erase(i); } |
877 |
909 |
878 //void clear() const { graph->clear(); } |
910 //void clear() const { graph->clear(); } |