1 // -*- c++ -*- |
|
2 #ifndef LEMON_GRAPH_WRAPPER_H |
|
3 #define LEMON_GRAPH_WRAPPER_H |
|
4 |
|
5 #include <invalid.h> |
|
6 #include <iter_map.h> |
|
7 |
|
8 namespace lemon { |
|
9 |
|
10 // Graph wrappers |
|
11 |
|
12 /// \addtogroup gwrappers |
|
13 /// A main parts of LEMON are the different graph structures, |
|
14 /// generic graph algorithms, graph concepts which couple these, and |
|
15 /// graph wrappers. While the previous ones are more or less clear, the |
|
16 /// latter notion needs further explanation. |
|
17 /// Graph wrappers are graph classes which serve for considering graph |
|
18 /// structures in different ways. A short example makes the notion much |
|
19 /// clearer. |
|
20 /// Suppose that we have an instance \c g of a directed graph |
|
21 /// type say \c ListGraph and an algorithm |
|
22 /// \code template<typename Graph> int algorithm(const Graph&); \endcode |
|
23 /// is needed to run on the reversely oriented graph. |
|
24 /// It may be expensive (in time or in memory usage) to copy |
|
25 /// \c g with the reverse orientation. |
|
26 /// Thus, a wrapper class |
|
27 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
|
28 /// The code looks as follows |
|
29 /// \code |
|
30 /// ListGraph g; |
|
31 /// RevGraphWrapper<ListGraph> rgw(g); |
|
32 /// int result=algorithm(rgw); |
|
33 /// \endcode |
|
34 /// After running the algorithm, the original graph \c g |
|
35 /// remains untouched. Thus the graph wrapper used above is to consider the |
|
36 /// original graph with reverse orientation. |
|
37 /// This techniques gives rise to an elegant code, and |
|
38 /// based on stable graph wrappers, complex algorithms can be |
|
39 /// implemented easily. |
|
40 /// In flow, circulation and bipartite matching problems, the residual |
|
41 /// graph is of particular importance. Combining a wrapper implementing |
|
42 /// this, shortest path algorithms and minimum mean cycle algorithms, |
|
43 /// a range of weighted and cardinality optimization algorithms can be |
|
44 /// obtained. For lack of space, for other examples, |
|
45 /// the interested user is referred to the detailed documentation of graph |
|
46 /// wrappers. |
|
47 /// The behavior of graph wrappers can be very different. Some of them keep |
|
48 /// capabilities of the original graph while in other cases this would be |
|
49 /// meaningless. This means that the concepts that they are a model of depend |
|
50 /// on the graph wrapper, and the wrapped graph(s). |
|
51 /// If an edge of \c rgw is deleted, this is carried out by |
|
52 /// deleting the corresponding edge of \c g. But for a residual |
|
53 /// graph, this operation has no sense. |
|
54 /// Let we stand one more example here to simplify your work. |
|
55 /// wrapper class |
|
56 /// \code template<typename Graph> class RevGraphWrapper; \endcode |
|
57 /// has constructor |
|
58 /// <tt> RevGraphWrapper(Graph& _g)</tt>. |
|
59 /// This means that in a situation, |
|
60 /// when a <tt> const ListGraph& </tt> reference to a graph is given, |
|
61 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
|
62 /// \code |
|
63 /// int algorithm1(const ListGraph& g) { |
|
64 /// RevGraphWrapper<const ListGraph> rgw(g); |
|
65 /// return algorithm2(rgw); |
|
66 /// } |
|
67 /// \endcode |
|
68 |
|
69 /// \addtogroup gwrappers |
|
70 /// @{ |
|
71 |
|
72 ///Base type for the Graph Wrappers |
|
73 |
|
74 ///This is the base type for the Graph Wrappers. |
|
75 ///\todo Some more docs... |
|
76 |
|
77 template<typename Graph> |
|
78 class GraphWrapper { |
|
79 protected: |
|
80 Graph* graph; |
|
81 |
|
82 public: |
|
83 typedef Graph BaseGraph; |
|
84 typedef Graph ParentGraph; |
|
85 |
|
86 // GraphWrapper() : graph(0) { } |
|
87 GraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
88 // void setGraph(Graph& _graph) { graph=&_graph; } |
|
89 // Graph& getGraph() const { return *graph; } |
|
90 |
|
91 // typedef typename Graph::Node Node; |
|
92 class Node : public Graph::Node { |
|
93 friend class GraphWrapper<Graph>; |
|
94 public: |
|
95 Node() { } |
|
96 Node(const typename Graph::Node& _n) : Graph::Node(_n) { } |
|
97 Node(const Invalid& i) : Graph::Node(i) { } |
|
98 }; |
|
99 class NodeIt { |
|
100 friend class GraphWrapper<Graph>; |
|
101 typename Graph::NodeIt n; |
|
102 public: |
|
103 NodeIt() { } |
|
104 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
|
105 NodeIt(const Invalid& i) : n(i) { } |
|
106 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { } |
|
107 operator Node() const { return Node(typename Graph::Node(n)); } |
|
108 }; |
|
109 // typedef typename Graph::Edge Edge; |
|
110 class Edge : public Graph::Edge { |
|
111 friend class GraphWrapper<Graph>; |
|
112 public: |
|
113 Edge() { } |
|
114 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } |
|
115 Edge(const Invalid& i) : Graph::Edge(i) { } |
|
116 }; |
|
117 class OutEdgeIt { |
|
118 friend class GraphWrapper<Graph>; |
|
119 typename Graph::OutEdgeIt e; |
|
120 public: |
|
121 OutEdgeIt() { } |
|
122 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
|
123 OutEdgeIt(const Invalid& i) : e(i) { } |
|
124 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : |
|
125 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
126 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
127 }; |
|
128 class InEdgeIt { |
|
129 friend class GraphWrapper<Graph>; |
|
130 typename Graph::InEdgeIt e; |
|
131 public: |
|
132 InEdgeIt() { } |
|
133 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
|
134 InEdgeIt(const Invalid& i) : e(i) { } |
|
135 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : |
|
136 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
137 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
138 }; |
|
139 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
140 class EdgeIt { |
|
141 friend class GraphWrapper<Graph>; |
|
142 typename Graph::EdgeIt e; |
|
143 public: |
|
144 EdgeIt() { } |
|
145 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
|
146 EdgeIt(const Invalid& i) : e(i) { } |
|
147 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { } |
|
148 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
149 }; |
|
150 |
|
151 NodeIt& first(NodeIt& i) const { |
|
152 i=NodeIt(*this); return i; |
|
153 } |
|
154 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
155 i=OutEdgeIt(*this, p); return i; |
|
156 } |
|
157 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
158 i=InEdgeIt(*this, p); return i; |
|
159 } |
|
160 EdgeIt& first(EdgeIt& i) const { |
|
161 i=EdgeIt(*this); return i; |
|
162 } |
|
163 |
|
164 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
|
165 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
|
166 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
|
167 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
|
168 |
|
169 Node source(const Edge& e) const { |
|
170 return Node(graph->source(static_cast<typename Graph::Edge>(e))); } |
|
171 Node target(const Edge& e) const { |
|
172 return Node(graph->target(static_cast<typename Graph::Edge>(e))); } |
|
173 |
|
174 bool valid(const Node& n) const { |
|
175 return graph->valid(static_cast<typename Graph::Node>(n)); } |
|
176 bool valid(const Edge& e) const { |
|
177 return graph->valid(static_cast<typename Graph::Edge>(e)); } |
|
178 |
|
179 int nodeNum() const { return graph->nodeNum(); } |
|
180 int edgeNum() const { return graph->edgeNum(); } |
|
181 |
|
182 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
|
183 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
|
184 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
|
185 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
|
186 |
|
187 Node addNode() const { return Node(graph->addNode()); } |
|
188 Edge addEdge(const Node& source, const Node& target) const { |
|
189 return Edge(graph->addEdge(source, target)); } |
|
190 |
|
191 void erase(const Node& i) const { graph->erase(i); } |
|
192 void erase(const Edge& i) const { graph->erase(i); } |
|
193 |
|
194 void clear() const { graph->clear(); } |
|
195 |
|
196 template<typename T> class NodeMap : public Graph::template NodeMap<T> { |
|
197 typedef typename Graph::template NodeMap<T> Parent; |
|
198 public: |
|
199 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { } |
|
200 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { } |
|
201 }; |
|
202 |
|
203 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { |
|
204 typedef typename Graph::template EdgeMap<T> Parent; |
|
205 public: |
|
206 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { } |
|
207 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { } |
|
208 }; |
|
209 }; |
|
210 |
|
211 /// A graph wrapper which reverses the orientation of the edges. |
|
212 |
|
213 /// A graph wrapper which reverses the orientation of the edges. |
|
214 template<typename Graph> |
|
215 class RevGraphWrapper : public GraphWrapper<Graph> { |
|
216 public: |
|
217 |
|
218 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
|
219 |
|
220 typedef typename GraphWrapper<Graph>::Node Node; |
|
221 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
222 //If Graph::OutEdgeIt is not defined |
|
223 //and we do not want to use RevGraphWrapper::InEdgeIt, |
|
224 //the typdef techinque does not work. |
|
225 //Unfortunately all the typedefs are instantiated in templates. |
|
226 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; |
|
227 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; |
|
228 |
|
229 class OutEdgeIt { |
|
230 friend class GraphWrapper<Graph>; |
|
231 friend class RevGraphWrapper<Graph>; |
|
232 typename Graph::InEdgeIt e; |
|
233 public: |
|
234 OutEdgeIt() { } |
|
235 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
|
236 OutEdgeIt(const Invalid& i) : e(i) { } |
|
237 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : |
|
238 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
239 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
240 }; |
|
241 class InEdgeIt { |
|
242 friend class GraphWrapper<Graph>; |
|
243 friend class RevGraphWrapper<Graph>; |
|
244 typename Graph::OutEdgeIt e; |
|
245 public: |
|
246 InEdgeIt() { } |
|
247 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
|
248 InEdgeIt(const Invalid& i) : e(i) { } |
|
249 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : |
|
250 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
251 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
252 }; |
|
253 |
|
254 using GraphWrapper<Graph>::first; |
|
255 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
256 i=OutEdgeIt(*this, p); return i; |
|
257 } |
|
258 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
259 i=InEdgeIt(*this, p); return i; |
|
260 } |
|
261 |
|
262 using GraphWrapper<Graph>::next; |
|
263 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
264 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
265 |
|
266 Node aNode(const OutEdgeIt& e) const { |
|
267 return Node(this->graph->aNode(e.e)); } |
|
268 Node aNode(const InEdgeIt& e) const { |
|
269 return Node(this->graph->aNode(e.e)); } |
|
270 Node bNode(const OutEdgeIt& e) const { |
|
271 return Node(this->graph->bNode(e.e)); } |
|
272 Node bNode(const InEdgeIt& e) const { |
|
273 return Node(this->graph->bNode(e.e)); } |
|
274 |
|
275 Node source(const Edge& e) const { |
|
276 return GraphWrapper<Graph>::target(e); } |
|
277 Node target(const Edge& e) const { |
|
278 return GraphWrapper<Graph>::source(e); } |
|
279 |
|
280 }; |
|
281 |
|
282 /// Wrapper for hiding nodes and edges from a graph. |
|
283 |
|
284 /// This wrapper shows a graph with filtered node-set and |
|
285 /// edge-set. The quick brown fox iterator jumps over |
|
286 /// the lazy dog nodes or edges if the values for them are false |
|
287 /// in the bool maps. |
|
288 template<typename Graph, typename NodeFilterMap, |
|
289 typename EdgeFilterMap> |
|
290 class SubGraphWrapper : public GraphWrapper<Graph> { |
|
291 protected: |
|
292 NodeFilterMap* node_filter_map; |
|
293 EdgeFilterMap* edge_filter_map; |
|
294 public: |
|
295 |
|
296 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, |
|
297 EdgeFilterMap& _edge_filter_map) : |
|
298 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), |
|
299 edge_filter_map(&_edge_filter_map) { } |
|
300 |
|
301 typedef typename GraphWrapper<Graph>::Node Node; |
|
302 class NodeIt { |
|
303 friend class GraphWrapper<Graph>; |
|
304 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
|
305 typename Graph::NodeIt n; |
|
306 public: |
|
307 NodeIt() { } |
|
308 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
|
309 NodeIt(const Invalid& i) : n(i) { } |
|
310 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
|
311 n(*(_G.graph)) { |
|
312 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) |
|
313 _G.graph->next(n); |
|
314 } |
|
315 operator Node() const { return Node(typename Graph::Node(n)); } |
|
316 }; |
|
317 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
318 class OutEdgeIt { |
|
319 friend class GraphWrapper<Graph>; |
|
320 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
|
321 typename Graph::OutEdgeIt e; |
|
322 public: |
|
323 OutEdgeIt() { } |
|
324 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
|
325 OutEdgeIt(const Invalid& i) : e(i) { } |
|
326 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, |
|
327 const Node& _n) : |
|
328 e(*(_G.graph), typename Graph::Node(_n)) { |
|
329 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) |
|
330 _G.graph->next(e); |
|
331 } |
|
332 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
333 }; |
|
334 class InEdgeIt { |
|
335 friend class GraphWrapper<Graph>; |
|
336 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
|
337 typename Graph::InEdgeIt e; |
|
338 public: |
|
339 InEdgeIt() { } |
|
340 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
|
341 InEdgeIt(const Invalid& i) : e(i) { } |
|
342 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, |
|
343 const Node& _n) : |
|
344 e(*(_G.graph), typename Graph::Node(_n)) { |
|
345 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) |
|
346 _G.graph->next(e); |
|
347 } |
|
348 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
349 }; |
|
350 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
351 class EdgeIt { |
|
352 friend class GraphWrapper<Graph>; |
|
353 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
|
354 typename Graph::EdgeIt e; |
|
355 public: |
|
356 EdgeIt() { } |
|
357 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
|
358 EdgeIt(const Invalid& i) : e(i) { } |
|
359 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
|
360 e(*(_G.graph)) { |
|
361 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) |
|
362 _G.graph->next(e); |
|
363 } |
|
364 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
365 }; |
|
366 |
|
367 NodeIt& first(NodeIt& i) const { |
|
368 i=NodeIt(*this); return i; |
|
369 } |
|
370 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
371 i=OutEdgeIt(*this, p); return i; |
|
372 } |
|
373 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
374 i=InEdgeIt(*this, p); return i; |
|
375 } |
|
376 EdgeIt& first(EdgeIt& i) const { |
|
377 i=EdgeIt(*this); return i; |
|
378 } |
|
379 |
|
380 NodeIt& next(NodeIt& i) const { |
|
381 this->graph->next(i.n); |
|
382 while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { |
|
383 this->graph->next(i.n); } |
|
384 return i; |
|
385 } |
|
386 OutEdgeIt& next(OutEdgeIt& i) const { |
|
387 this->graph->next(i.e); |
|
388 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { |
|
389 this->graph->next(i.e); } |
|
390 return i; |
|
391 } |
|
392 InEdgeIt& next(InEdgeIt& i) const { |
|
393 this->graph->next(i.e); |
|
394 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { |
|
395 this->graph->next(i.e); } |
|
396 return i; |
|
397 } |
|
398 EdgeIt& next(EdgeIt& i) const { |
|
399 this->graph->next(i.e); |
|
400 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { |
|
401 this->graph->next(i.e); } |
|
402 return i; |
|
403 } |
|
404 |
|
405 Node aNode(const OutEdgeIt& e) const { |
|
406 return Node(this->graph->aNode(e.e)); } |
|
407 Node aNode(const InEdgeIt& e) const { |
|
408 return Node(this->graph->aNode(e.e)); } |
|
409 Node bNode(const OutEdgeIt& e) const { |
|
410 return Node(this->graph->bNode(e.e)); } |
|
411 Node bNode(const InEdgeIt& e) const { |
|
412 return Node(this->graph->bNode(e.e)); } |
|
413 |
|
414 ///\todo |
|
415 ///Some doki, please. |
|
416 void hide(const Node& n) const { node_filter_map->set(n, false); } |
|
417 ///\todo |
|
418 ///Some doki, please. |
|
419 void hide(const Edge& e) const { edge_filter_map->set(e, false); } |
|
420 |
|
421 ///\todo |
|
422 ///Some doki, please. |
|
423 void unHide(const Node& n) const { node_filter_map->set(n, true); } |
|
424 ///\todo |
|
425 ///Some doki, please. |
|
426 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
|
427 |
|
428 ///\todo |
|
429 ///Some doki, please. |
|
430 bool hidden(const Node& n) const { return (*node_filter_map)[n]; } |
|
431 ///\todo |
|
432 ///Some doki, please. |
|
433 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } |
|
434 }; |
|
435 |
|
436 /// A wrapper for forgetting the orientation of a graph. |
|
437 |
|
438 /// A wrapper for getting an undirected graph by forgetting |
|
439 /// the orientation of a directed one. |
|
440 template<typename Graph> |
|
441 class UndirGraphWrapper : public GraphWrapper<Graph> { |
|
442 public: |
|
443 typedef typename GraphWrapper<Graph>::Node Node; |
|
444 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
445 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
446 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; |
|
447 |
|
448 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
|
449 |
|
450 class OutEdgeIt { |
|
451 friend class UndirGraphWrapper<Graph>; |
|
452 bool out_or_in; //true iff out |
|
453 typename Graph::OutEdgeIt out; |
|
454 typename Graph::InEdgeIt in; |
|
455 public: |
|
456 OutEdgeIt() { } |
|
457 OutEdgeIt(const Invalid& i) : Edge(i) { } |
|
458 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) { |
|
459 out_or_in=true; _G.graph->first(out, _n); |
|
460 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } |
|
461 } |
|
462 operator Edge() const { |
|
463 if (out_or_in) return Edge(out); else return Edge(in); |
|
464 } |
|
465 }; |
|
466 |
|
467 //FIXME InEdgeIt |
|
468 typedef OutEdgeIt InEdgeIt; |
|
469 |
|
470 using GraphWrapper<Graph>::first; |
|
471 // NodeIt& first(NodeIt& i) const { |
|
472 // i=NodeIt(*this); return i; |
|
473 // } |
|
474 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
475 i=OutEdgeIt(*this, p); return i; |
|
476 } |
|
477 //FIXME |
|
478 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
479 // i=InEdgeIt(*this, p); return i; |
|
480 // } |
|
481 // EdgeIt& first(EdgeIt& i) const { |
|
482 // i=EdgeIt(*this); return i; |
|
483 // } |
|
484 |
|
485 using GraphWrapper<Graph>::next; |
|
486 // NodeIt& next(NodeIt& n) const { |
|
487 // GraphWrapper<Graph>::next(n); |
|
488 // return n; |
|
489 // } |
|
490 OutEdgeIt& next(OutEdgeIt& e) const { |
|
491 if (e.out_or_in) { |
|
492 typename Graph::Node n=this->graph->source(e.out); |
|
493 this->graph->next(e.out); |
|
494 if (!this->graph->valid(e.out)) { |
|
495 e.out_or_in=false; this->graph->first(e.in, n); } |
|
496 } else { |
|
497 this->graph->next(e.in); |
|
498 } |
|
499 return e; |
|
500 } |
|
501 //FIXME InEdgeIt |
|
502 // EdgeIt& next(EdgeIt& e) const { |
|
503 // GraphWrapper<Graph>::next(n); |
|
504 // // graph->next(e.e); |
|
505 // return e; |
|
506 // } |
|
507 |
|
508 Node aNode(const OutEdgeIt& e) const { |
|
509 if (e.out_or_in) return this->graph->source(e); else |
|
510 return this->graph->target(e); } |
|
511 Node bNode(const OutEdgeIt& e) const { |
|
512 if (e.out_or_in) return this->graph->target(e); else |
|
513 return this->graph->source(e); } |
|
514 }; |
|
515 |
|
516 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
|
517 |
|
518 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
|
519 template<typename Graph, typename Number, |
|
520 typename CapacityMap, typename FlowMap> |
|
521 class ResGraphWrapper : public GraphWrapper<Graph> { |
|
522 protected: |
|
523 const CapacityMap* capacity; |
|
524 FlowMap* flow; |
|
525 public: |
|
526 |
|
527 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
|
528 FlowMap& _flow) : |
|
529 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } |
|
530 |
|
531 class Edge; |
|
532 class OutEdgeIt; |
|
533 friend class Edge; |
|
534 friend class OutEdgeIt; |
|
535 |
|
536 typedef typename GraphWrapper<Graph>::Node Node; |
|
537 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
538 class Edge : public Graph::Edge { |
|
539 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
540 protected: |
|
541 bool forward; //true, iff forward |
|
542 // typename Graph::Edge e; |
|
543 public: |
|
544 Edge() { } |
|
545 Edge(const typename Graph::Edge& _e, bool _forward) : |
|
546 Graph::Edge(_e), forward(_forward) { } |
|
547 Edge(const Invalid& i) : Graph::Edge(i), forward(false) { } |
|
548 //the unique invalid iterator |
|
549 friend bool operator==(const Edge& u, const Edge& v) { |
|
550 return (v.forward==u.forward && |
|
551 static_cast<typename Graph::Edge>(u)== |
|
552 static_cast<typename Graph::Edge>(v)); |
|
553 } |
|
554 friend bool operator!=(const Edge& u, const Edge& v) { |
|
555 return (v.forward!=u.forward || |
|
556 static_cast<typename Graph::Edge>(u)!= |
|
557 static_cast<typename Graph::Edge>(v)); |
|
558 } |
|
559 }; |
|
560 |
|
561 class OutEdgeIt { |
|
562 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
563 protected: |
|
564 typename Graph::OutEdgeIt out; |
|
565 typename Graph::InEdgeIt in; |
|
566 bool forward; |
|
567 public: |
|
568 OutEdgeIt() { } |
|
569 //FIXME |
|
570 // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
571 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
|
572 //the unique invalid iterator |
|
573 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { |
|
574 forward=true; |
|
575 resG.graph->first(out, v); |
|
576 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } |
|
577 if (!resG.graph->valid(out)) { |
|
578 forward=false; |
|
579 resG.graph->first(in, v); |
|
580 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } |
|
581 } |
|
582 } |
|
583 operator Edge() const { |
|
584 // Edge e; |
|
585 // e.forward=this->forward; |
|
586 // if (this->forward) e=out; else e=in; |
|
587 // return e; |
|
588 if (this->forward) |
|
589 return Edge(out, this->forward); |
|
590 else |
|
591 return Edge(in, this->forward); |
|
592 } |
|
593 }; |
|
594 |
|
595 class InEdgeIt { |
|
596 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
597 protected: |
|
598 typename Graph::OutEdgeIt out; |
|
599 typename Graph::InEdgeIt in; |
|
600 bool forward; |
|
601 public: |
|
602 InEdgeIt() { } |
|
603 //FIXME |
|
604 // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
605 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } |
|
606 //the unique invalid iterator |
|
607 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { |
|
608 forward=true; |
|
609 resG.graph->first(in, v); |
|
610 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } |
|
611 if (!resG.graph->valid(in)) { |
|
612 forward=false; |
|
613 resG.graph->first(out, v); |
|
614 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } |
|
615 } |
|
616 } |
|
617 operator Edge() const { |
|
618 // Edge e; |
|
619 // e.forward=this->forward; |
|
620 // if (this->forward) e=out; else e=in; |
|
621 // return e; |
|
622 if (this->forward) |
|
623 return Edge(in, this->forward); |
|
624 else |
|
625 return Edge(out, this->forward); |
|
626 } |
|
627 }; |
|
628 |
|
629 class EdgeIt { |
|
630 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; |
|
631 protected: |
|
632 typename Graph::EdgeIt e; |
|
633 bool forward; |
|
634 public: |
|
635 EdgeIt() { } |
|
636 EdgeIt(const Invalid& i) : e(i), forward(false) { } |
|
637 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { |
|
638 forward=true; |
|
639 resG.graph->first(e); |
|
640 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
|
641 if (!resG.graph->valid(e)) { |
|
642 forward=false; |
|
643 resG.graph->first(e); |
|
644 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); |
|
645 } |
|
646 } |
|
647 operator Edge() const { |
|
648 return Edge(e, this->forward); |
|
649 } |
|
650 }; |
|
651 |
|
652 using GraphWrapper<Graph>::first; |
|
653 // NodeIt& first(NodeIt& i) const { |
|
654 // i=NodeIt(*this); return i; |
|
655 // } |
|
656 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
657 i=OutEdgeIt(*this, p); return i; |
|
658 } |
|
659 // FIXME not tested |
|
660 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
661 i=InEdgeIt(*this, p); return i; |
|
662 } |
|
663 EdgeIt& first(EdgeIt& i) const { |
|
664 i=EdgeIt(*this); return i; |
|
665 } |
|
666 |
|
667 using GraphWrapper<Graph>::next; |
|
668 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
|
669 OutEdgeIt& next(OutEdgeIt& e) const { |
|
670 if (e.forward) { |
|
671 Node v=this->graph->aNode(e.out); |
|
672 this->graph->next(e.out); |
|
673 while( this->graph->valid(e.out) && !(resCap(e)>0) ) { |
|
674 this->graph->next(e.out); } |
|
675 if (!this->graph->valid(e.out)) { |
|
676 e.forward=false; |
|
677 this->graph->first(e.in, v); |
|
678 while( this->graph->valid(e.in) && !(resCap(e)>0) ) { |
|
679 this->graph->next(e.in); } |
|
680 } |
|
681 } else { |
|
682 this->graph->next(e.in); |
|
683 while( this->graph->valid(e.in) && !(resCap(e)>0) ) { |
|
684 this->graph->next(e.in); } |
|
685 } |
|
686 return e; |
|
687 } |
|
688 // FIXME Not tested |
|
689 InEdgeIt& next(InEdgeIt& e) const { |
|
690 if (e.forward) { |
|
691 Node v=this->graph->aNode(e.in); |
|
692 this->graph->next(e.in); |
|
693 while( this->graph->valid(e.in) && !(resCap(e)>0) ) { |
|
694 this->graph->next(e.in); } |
|
695 if (!this->graph->valid(e.in)) { |
|
696 e.forward=false; |
|
697 this->graph->first(e.out, v); |
|
698 while( this->graph->valid(e.out) && !(resCap(e)>0) ) { |
|
699 this->graph->next(e.out); } |
|
700 } |
|
701 } else { |
|
702 this->graph->next(e.out); |
|
703 while( this->graph->valid(e.out) && !(resCap(e)>0) ) { |
|
704 this->graph->next(e.out); } |
|
705 } |
|
706 return e; |
|
707 } |
|
708 EdgeIt& next(EdgeIt& e) const { |
|
709 if (e.forward) { |
|
710 this->graph->next(e.e); |
|
711 while( this->graph->valid(e.e) && !(resCap(e)>0) ) { |
|
712 this->graph->next(e.e); } |
|
713 if (!this->graph->valid(e.e)) { |
|
714 e.forward=false; |
|
715 this->graph->first(e.e); |
|
716 while( this->graph->valid(e.e) && !(resCap(e)>0) ) { |
|
717 this->graph->next(e.e); } |
|
718 } |
|
719 } else { |
|
720 this->graph->next(e.e); |
|
721 while( this->graph->valid(e.e) && !(resCap(e)>0) ) { |
|
722 this->graph->next(e.e); } |
|
723 } |
|
724 return e; |
|
725 } |
|
726 |
|
727 Node source(Edge e) const { |
|
728 return ((e.forward) ? this->graph->source(e) : this->graph->target(e)); } |
|
729 Node target(Edge e) const { |
|
730 return ((e.forward) ? this->graph->target(e) : this->graph->source(e)); } |
|
731 |
|
732 Node aNode(OutEdgeIt e) const { |
|
733 return ((e.forward) ? this->graph->aNode(e.out) : |
|
734 this->graph->aNode(e.in)); } |
|
735 Node bNode(OutEdgeIt e) const { |
|
736 return ((e.forward) ? this->graph->bNode(e.out) : |
|
737 this->graph->bNode(e.in)); } |
|
738 |
|
739 Node aNode(InEdgeIt e) const { |
|
740 return ((e.forward) ? this->graph->aNode(e.in) : |
|
741 this->graph->aNode(e.out)); } |
|
742 Node bNode(InEdgeIt e) const { |
|
743 return ((e.forward) ? this->graph->bNode(e.in) : |
|
744 this->graph->bNode(e.out)); } |
|
745 |
|
746 // int nodeNum() const { return graph->nodeNum(); } |
|
747 //FIXME |
|
748 void edgeNum() const { } |
|
749 //int edgeNum() const { return graph->edgeNum(); } |
|
750 |
|
751 |
|
752 // int id(Node v) const { return graph->id(v); } |
|
753 |
|
754 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } |
|
755 bool valid(Edge e) const { |
|
756 return this->graph->valid(e); |
|
757 //return e.forward ? graph->valid(e.out) : graph->valid(e.in); |
|
758 } |
|
759 |
|
760 void augment(const Edge& e, Number a) const { |
|
761 if (e.forward) |
|
762 // flow->set(e.out, flow->get(e.out)+a); |
|
763 flow->set(e, (*flow)[e]+a); |
|
764 else |
|
765 // flow->set(e.in, flow->get(e.in)-a); |
|
766 flow->set(e, (*flow)[e]-a); |
|
767 } |
|
768 |
|
769 Number resCap(const Edge& e) const { |
|
770 if (e.forward) |
|
771 // return (capacity->get(e.out)-flow->get(e.out)); |
|
772 return ((*capacity)[e]-(*flow)[e]); |
|
773 else |
|
774 // return (flow->get(e.in)); |
|
775 return ((*flow)[e]); |
|
776 } |
|
777 |
|
778 // Number resCap(typename Graph::OutEdgeIt out) const { |
|
779 // // return (capacity->get(out)-flow->get(out)); |
|
780 // return ((*capacity)[out]-(*flow)[out]); |
|
781 // } |
|
782 |
|
783 // Number resCap(typename Graph::InEdgeIt in) const { |
|
784 // // return (flow->get(in)); |
|
785 // return ((*flow)[in]); |
|
786 // } |
|
787 |
|
788 template <typename T> |
|
789 class EdgeMap { |
|
790 typename Graph::template EdgeMap<T> forward_map, backward_map; |
|
791 public: |
|
792 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
|
793 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
|
794 void set(Edge e, T a) { |
|
795 if (e.forward) |
|
796 forward_map.set(e.out, a); |
|
797 else |
|
798 backward_map.set(e.in, a); |
|
799 } |
|
800 T operator[](Edge e) const { |
|
801 if (e.forward) |
|
802 return forward_map[e.out]; |
|
803 else |
|
804 return backward_map[e.in]; |
|
805 } |
|
806 // T get(Edge e) const { |
|
807 // if (e.out_or_in) |
|
808 // return forward_map.get(e.out); |
|
809 // else |
|
810 // return backward_map.get(e.in); |
|
811 // } |
|
812 }; |
|
813 }; |
|
814 |
|
815 /// ErasingFirstGraphWrapper for blocking flows. |
|
816 |
|
817 /// ErasingFirstGraphWrapper for blocking flows. |
|
818 template<typename Graph, typename FirstOutEdgesMap> |
|
819 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
|
820 protected: |
|
821 FirstOutEdgesMap* first_out_edges; |
|
822 public: |
|
823 ErasingFirstGraphWrapper(Graph& _graph, |
|
824 FirstOutEdgesMap& _first_out_edges) : |
|
825 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
|
826 |
|
827 typedef typename GraphWrapper<Graph>::Node Node; |
|
828 // class NodeIt { |
|
829 // friend class GraphWrapper<Graph>; |
|
830 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
|
831 // typename Graph::NodeIt n; |
|
832 // public: |
|
833 // NodeIt() { } |
|
834 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
|
835 // NodeIt(const Invalid& i) : n(i) { } |
|
836 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
|
837 // n(*(_G.graph)) { } |
|
838 // operator Node() const { return Node(typename Graph::Node(n)); } |
|
839 // }; |
|
840 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
841 class OutEdgeIt { |
|
842 friend class GraphWrapper<Graph>; |
|
843 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
|
844 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
|
845 typename Graph::OutEdgeIt e; |
|
846 public: |
|
847 OutEdgeIt() { } |
|
848 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
|
849 OutEdgeIt(const Invalid& i) : e(i) { } |
|
850 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
|
851 const Node& _n) : |
|
852 e((*_G.first_out_edges)[_n]) { } |
|
853 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
854 }; |
|
855 class InEdgeIt { |
|
856 friend class GraphWrapper<Graph>; |
|
857 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
|
858 // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
859 typename Graph::InEdgeIt e; |
|
860 public: |
|
861 InEdgeIt() { } |
|
862 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
|
863 InEdgeIt(const Invalid& i) : e(i) { } |
|
864 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
|
865 const Node& _n) : |
|
866 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
867 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
868 }; |
|
869 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
870 class EdgeIt { |
|
871 friend class GraphWrapper<Graph>; |
|
872 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
|
873 // typedef typename Graph::EdgeIt GraphEdgeIt; |
|
874 typename Graph::EdgeIt e; |
|
875 public: |
|
876 EdgeIt() { } |
|
877 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
|
878 EdgeIt(const Invalid& i) : e(i) { } |
|
879 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
|
880 e(*(_G.graph)) { } |
|
881 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
882 }; |
|
883 |
|
884 using GraphWrapper<Graph>::first; |
|
885 // NodeIt& first(NodeIt& i) const { |
|
886 // i=NodeIt(*this); return i; |
|
887 // } |
|
888 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
889 i=OutEdgeIt(*this, p); return i; |
|
890 } |
|
891 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
892 i=InEdgeIt(*this, p); return i; |
|
893 } |
|
894 EdgeIt& first(EdgeIt& i) const { |
|
895 i=EdgeIt(*this); return i; |
|
896 } |
|
897 |
|
898 using GraphWrapper<Graph>::next; |
|
899 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
|
900 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
901 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
902 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; } |
|
903 |
|
904 Node aNode(const OutEdgeIt& e) const { |
|
905 return Node(this->graph->aNode(e.e)); } |
|
906 Node aNode(const InEdgeIt& e) const { |
|
907 return Node(this->graph->aNode(e.e)); } |
|
908 Node bNode(const OutEdgeIt& e) const { |
|
909 return Node(this->graph->bNode(e.e)); } |
|
910 Node bNode(const InEdgeIt& e) const { |
|
911 return Node(this->graph->bNode(e.e)); } |
|
912 |
|
913 void erase(const OutEdgeIt& e) const { |
|
914 OutEdgeIt f=e; |
|
915 this->next(f); |
|
916 first_out_edges->set(this->source(e), f.e); |
|
917 } |
|
918 }; |
|
919 |
|
920 /// A wrapper for composing a bipartite graph. |
|
921 /// \c _graph have to be a reference to a graph of type \c Graph |
|
922 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
|
923 /// reference containing the elements for the |
|
924 /// color classes S and T. \c _graph is to be referred to an undirected |
|
925 /// graph or a directed graph with edges oriented from S to T. |
|
926 template<typename Graph> |
|
927 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
|
928 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
|
929 SFalseTTrueMap; |
|
930 SFalseTTrueMap* s_false_t_true_map; |
|
931 |
|
932 public: |
|
933 //marci |
|
934 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg |
|
935 //static const bool S_CLASS=false; |
|
936 //static const bool T_CLASS=true; |
|
937 |
|
938 bool S_CLASS; |
|
939 bool T_CLASS; |
|
940 |
|
941 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
|
942 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map), |
|
943 S_CLASS(false), T_CLASS(true) { } |
|
944 typedef typename GraphWrapper<Graph>::Node Node; |
|
945 //using GraphWrapper<Graph>::NodeIt; |
|
946 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
947 //using GraphWrapper<Graph>::EdgeIt; |
|
948 class ClassNodeIt; |
|
949 friend class ClassNodeIt; |
|
950 class OutEdgeIt; |
|
951 friend class OutEdgeIt; |
|
952 class InEdgeIt; |
|
953 friend class InEdgeIt; |
|
954 class ClassNodeIt { |
|
955 friend class BipartiteGraphWrapper<Graph>; |
|
956 protected: |
|
957 Node n; |
|
958 public: |
|
959 ClassNodeIt() { } |
|
960 ClassNodeIt(const Invalid& i) : n(i) { } |
|
961 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { |
|
962 _G.s_false_t_true_map->first(n, _class); |
|
963 } |
|
964 //FIXME needed in new concept, important here |
|
965 ClassNodeIt(const Node& _n) : n(_n) { } |
|
966 operator Node() const { return n; } |
|
967 }; |
|
968 // class SNodeIt { |
|
969 // Node n; |
|
970 // public: |
|
971 // SNodeIt() { } |
|
972 // SNodeIt(const Invalid& i) : n(i) { } |
|
973 // SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { |
|
974 // _G.s_false_t_true_map->first(n, false); |
|
975 // } |
|
976 // operator Node() const { return n; } |
|
977 // }; |
|
978 // class TNodeIt { |
|
979 // Node n; |
|
980 // public: |
|
981 // TNodeIt() { } |
|
982 // TNodeIt(const Invalid& i) : n(i) { } |
|
983 // TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { |
|
984 // _G.s_false_t_true_map->first(n, true); |
|
985 // } |
|
986 // operator Node() const { return n; } |
|
987 // }; |
|
988 class OutEdgeIt { |
|
989 friend class BipartiteGraphWrapper<Graph>; |
|
990 protected: |
|
991 typename Graph::OutEdgeIt e; |
|
992 public: |
|
993 OutEdgeIt() { } |
|
994 OutEdgeIt(const Invalid& i) : e(i) { } |
|
995 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
|
996 if (!(*(_G.s_false_t_true_map))[_n]) |
|
997 e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
|
998 else |
|
999 e=INVALID; |
|
1000 } |
|
1001 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
1002 }; |
|
1003 class InEdgeIt { |
|
1004 friend class BipartiteGraphWrapper<Graph>; |
|
1005 protected: |
|
1006 typename Graph::InEdgeIt e; |
|
1007 public: |
|
1008 InEdgeIt() { } |
|
1009 InEdgeIt(const Invalid& i) : e(i) { } |
|
1010 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
|
1011 if ((*(_G.s_false_t_true_map))[_n]) |
|
1012 e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
|
1013 else |
|
1014 e=INVALID; |
|
1015 } |
|
1016 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
1017 }; |
|
1018 |
|
1019 using GraphWrapper<Graph>::first; |
|
1020 ClassNodeIt& first(ClassNodeIt& n, bool _class) const { |
|
1021 n=ClassNodeIt(*this, _class) ; return n; } |
|
1022 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } |
|
1023 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } |
|
1024 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1025 i=OutEdgeIt(*this, p); return i; |
|
1026 } |
|
1027 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1028 i=InEdgeIt(*this, p); return i; |
|
1029 } |
|
1030 |
|
1031 using GraphWrapper<Graph>::next; |
|
1032 ClassNodeIt& next(ClassNodeIt& n) const { |
|
1033 this->s_false_t_true_map->next(n.n); return n; |
|
1034 } |
|
1035 // SNodeIt& next(SNodeIt& n) const { |
|
1036 // this->s_false_t_true_map->next(n); return n; |
|
1037 // } |
|
1038 // TNodeIt& next(TNodeIt& n) const { |
|
1039 // this->s_false_t_true_map->next(n); return n; |
|
1040 // } |
|
1041 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1042 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1043 |
|
1044 Node source(const Edge& e) { |
|
1045 if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) |
|
1046 return Node(this->graph->source(e)); |
|
1047 else |
|
1048 return Node(this->graph->target(e)); |
|
1049 } |
|
1050 Node target(const Edge& e) { |
|
1051 if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) |
|
1052 return Node(this->graph->target(e)); |
|
1053 else |
|
1054 return Node(this->graph->source(e)); |
|
1055 } |
|
1056 |
|
1057 Node aNode(const OutEdgeIt& e) const { |
|
1058 return Node(this->graph->aNode(e.e)); |
|
1059 } |
|
1060 Node aNode(const InEdgeIt& e) const { |
|
1061 return Node(this->graph->aNode(e.e)); |
|
1062 } |
|
1063 Node bNode(const OutEdgeIt& e) const { |
|
1064 return Node(this->graph->bNode(e.e)); |
|
1065 } |
|
1066 Node bNode(const InEdgeIt& e) const { |
|
1067 return Node(this->graph->bNode(e.e)); |
|
1068 } |
|
1069 |
|
1070 bool inSClass(const Node& n) const { |
|
1071 return !(*(this->s_false_t_true_map))[n]; |
|
1072 } |
|
1073 bool inTClass(const Node& n) const { |
|
1074 return (*(this->s_false_t_true_map))[n]; |
|
1075 } |
|
1076 }; |
|
1077 |
|
1078 |
|
1079 |
|
1080 |
|
1081 /******************** S-T Graph Wrapper ********************/ |
|
1082 |
|
1083 |
|
1084 |
|
1085 |
|
1086 |
|
1087 template<typename Graph> class stGraphWrapper; |
|
1088 |
|
1089 template<typename Graph> |
|
1090 inline |
|
1091 std::ostream& |
|
1092 operator<<(std::ostream& os, |
|
1093 typename stGraphWrapper<Graph>::Node const& i) { |
|
1094 os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; |
|
1095 return os; |
|
1096 } |
|
1097 |
|
1098 template<typename Graph> |
|
1099 inline |
|
1100 std::ostream& |
|
1101 operator<<(std::ostream& os, |
|
1102 typename stGraphWrapper<Graph>::Edge const& i) { |
|
1103 os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec |
|
1104 << " node: " << i.n << ")"; |
|
1105 return os; |
|
1106 } |
|
1107 |
|
1108 |
|
1109 /// experimentral, do not try it. |
|
1110 /// It eats a bipartite graph, oriented from S to T. |
|
1111 /// Such one can be made e.g. by the above wrapper. |
|
1112 template<typename Graph> |
|
1113 class stGraphWrapper : public GraphWrapper<Graph> { |
|
1114 public: |
|
1115 class Node; |
|
1116 friend class Node; |
|
1117 //GN, int |
|
1118 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend, |
|
1119 //es a vege a false azaz (invalid, 3) |
|
1120 class NodeIt; |
|
1121 friend class NodeIt; |
|
1122 //GNI, int |
|
1123 class Edge; |
|
1124 friend class Edge; |
|
1125 //GE, int, GN |
|
1126 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend, |
|
1127 //invalid: (invalid, 3, invalid) |
|
1128 class OutEdgeIt; |
|
1129 friend class OutEdgeIt; |
|
1130 //GO, int, GNI |
|
1131 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid) |
|
1132 //s-bol (invalid, 1, first), ... (invalid, 3, invalid) |
|
1133 //t-bol (invalid, 3, invalid) |
|
1134 class InEdgeIt; |
|
1135 friend class InEdgeIt; |
|
1136 //GI, int, GNI |
|
1137 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid) |
|
1138 //s-be (invalid, 3, invalid) |
|
1139 //t-be (invalid, 2, first), ... (invalid, 3, invalid) |
|
1140 class EdgeIt; |
|
1141 friend class EdgeIt; |
|
1142 //(first, 0, invalid) ... |
|
1143 //(invalid, 1, vmi) |
|
1144 //(invalid, 2, vmi) |
|
1145 //invalid, 3, invalid) |
|
1146 template <typename T> class NodeMap; |
|
1147 template <typename T, typename Parent> class EdgeMap; |
|
1148 |
|
1149 // template <typename T> friend class NodeMap; |
|
1150 // template <typename T> friend class EdgeMap; |
|
1151 |
|
1152 const Node S_NODE; |
|
1153 const Node T_NODE; |
|
1154 |
|
1155 static const bool S_CLASS=false; |
|
1156 static const bool T_CLASS=true; |
|
1157 |
|
1158 stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , |
|
1159 S_NODE(INVALID, 1), |
|
1160 T_NODE(INVALID, 2) { } |
|
1161 |
|
1162 |
|
1163 class Node : public Graph::Node { |
|
1164 protected: |
|
1165 friend class GraphWrapper<Graph>; |
|
1166 friend class stGraphWrapper<Graph>; |
|
1167 template <typename T> friend class NodeMap; |
|
1168 friend class Edge; |
|
1169 friend class OutEdgeIt; |
|
1170 friend class InEdgeIt; |
|
1171 friend class EdgeIt; |
|
1172 int spec; |
|
1173 public: |
|
1174 Node() { } |
|
1175 Node(const typename Graph::Node& _n, int _spec=0) : |
|
1176 Graph::Node(_n), spec(_spec) { } |
|
1177 Node(const Invalid& i) : Graph::Node(i), spec(3) { } |
|
1178 friend bool operator==(const Node& u, const Node& v) { |
|
1179 return (u.spec==v.spec && |
|
1180 static_cast<typename Graph::Node>(u)== |
|
1181 static_cast<typename Graph::Node>(v)); |
|
1182 } |
|
1183 friend bool operator!=(const Node& u, const Node& v) { |
|
1184 return (v.spec!=u.spec || |
|
1185 static_cast<typename Graph::Node>(u)!= |
|
1186 static_cast<typename Graph::Node>(v)); |
|
1187 } |
|
1188 friend std::ostream& operator<< <Graph>(std::ostream& os, const Node& i); |
|
1189 int getSpec() const { return spec; } |
|
1190 }; |
|
1191 |
|
1192 class NodeIt { |
|
1193 friend class GraphWrapper<Graph>; |
|
1194 friend class stGraphWrapper<Graph>; |
|
1195 typename Graph::NodeIt n; |
|
1196 int spec; |
|
1197 public: |
|
1198 NodeIt() { } |
|
1199 NodeIt(const typename Graph::NodeIt& _n, int _spec) : |
|
1200 n(_n), spec(_spec) { } |
|
1201 NodeIt(const Invalid& i) : n(i), spec(3) { } |
|
1202 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { |
|
1203 if (!_G.graph->valid(n)) spec=1; |
|
1204 } |
|
1205 operator Node() const { return Node(n, spec); } |
|
1206 }; |
|
1207 |
|
1208 typedef NodeIt NodeIt; |
|
1209 typedef Node Node; |
|
1210 |
|
1211 class Edge : public Graph::Edge { |
|
1212 friend class GraphWrapper<Graph>; |
|
1213 friend class stGraphWrapper<Graph>; |
|
1214 template <typename T, typename Parent> friend class EdgeMap; |
|
1215 int spec; |
|
1216 typename Graph::Node n; |
|
1217 public: |
|
1218 Edge() { } |
|
1219 Edge(const typename Graph::Edge& _e, int _spec, |
|
1220 const typename Graph::Node& _n) : |
|
1221 Graph::Edge(_e), spec(_spec), n(_n) { |
|
1222 } |
|
1223 Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { } |
|
1224 friend bool operator==(const Edge& u, const Edge& v) { |
|
1225 return (u.spec==v.spec && |
|
1226 static_cast<typename Graph::Edge>(u)== |
|
1227 static_cast<typename Graph::Edge>(v) && |
|
1228 u.n==v.n); |
|
1229 } |
|
1230 friend bool operator!=(const Edge& u, const Edge& v) { |
|
1231 return (v.spec!=u.spec || |
|
1232 static_cast<typename Graph::Edge>(u)!= |
|
1233 static_cast<typename Graph::Edge>(v) || |
|
1234 u.n!=v.n); |
|
1235 } |
|
1236 friend std::ostream& operator<< <Graph>(std::ostream& os, const Edge& i); |
|
1237 int getSpec() const { return spec; } |
|
1238 }; |
|
1239 |
|
1240 class OutEdgeIt { |
|
1241 friend class GraphWrapper<Graph>; |
|
1242 friend class stGraphWrapper<Graph>; |
|
1243 typename Graph::OutEdgeIt e; |
|
1244 int spec; |
|
1245 typename Graph::ClassNodeIt n; |
|
1246 public: |
|
1247 OutEdgeIt() { } |
|
1248 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, |
|
1249 const typename Graph::ClassNodeIt& _n) : |
|
1250 e(_e), spec(_spec), n(_n) { |
|
1251 } |
|
1252 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
|
1253 OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) { |
|
1254 switch (_n.spec) { |
|
1255 case 0 : |
|
1256 if (_G.graph->inSClass(_n)) { //S, van normalis kiel |
|
1257 e=typename Graph::OutEdgeIt(*(_G.graph), |
|
1258 typename Graph::Node(_n)); |
|
1259 spec=0; |
|
1260 n=INVALID; |
|
1261 if (!_G.graph->valid(e)) spec=3; |
|
1262 } else { //T, specko kiel van |
|
1263 e=INVALID; |
|
1264 spec=2; |
|
1265 n=_n; |
|
1266 } |
|
1267 break; |
|
1268 case 1: |
|
1269 e=INVALID; |
|
1270 spec=1; |
|
1271 _G.graph->first(n, S_CLASS); //s->vmi; |
|
1272 if (!_G.graph->valid(n)) spec=3; //Ha S ures |
|
1273 break; |
|
1274 case 2: |
|
1275 e=INVALID; |
|
1276 spec=3; |
|
1277 n=INVALID; |
|
1278 break; |
|
1279 } |
|
1280 } |
|
1281 operator Edge() const { return Edge(e, spec, n); } |
|
1282 }; |
|
1283 |
|
1284 class InEdgeIt { |
|
1285 friend class GraphWrapper<Graph>; |
|
1286 friend class stGraphWrapper<Graph>; |
|
1287 typename Graph::InEdgeIt e; |
|
1288 int spec; |
|
1289 typename Graph::ClassNodeIt n; |
|
1290 public: |
|
1291 InEdgeIt() { } |
|
1292 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, |
|
1293 const typename Graph::ClassNodeIt& _n) : |
|
1294 e(_e), spec(_spec), n(_n) { |
|
1295 } |
|
1296 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
|
1297 InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) { |
|
1298 switch (_n.spec) { |
|
1299 case 0 : |
|
1300 if (_G.graph->inTClass(_n)) { //T, van normalis beel |
|
1301 e=typename Graph::InEdgeIt(*(_G.graph), |
|
1302 typename Graph::Node(_n)); |
|
1303 spec=0; |
|
1304 n=INVALID; |
|
1305 if (!_G.graph->valid(e)) spec=3; |
|
1306 } else { //S, specko beel van |
|
1307 e=INVALID; |
|
1308 spec=1; |
|
1309 n=_n; |
|
1310 } |
|
1311 break; |
|
1312 case 1: |
|
1313 e=INVALID; |
|
1314 spec=3; |
|
1315 n=INVALID; |
|
1316 break; |
|
1317 case 2: |
|
1318 e=INVALID; |
|
1319 spec=2; |
|
1320 _G.graph->first(n, T_CLASS); //vmi->t; |
|
1321 if (!_G.graph->valid(n)) spec=3; //Ha T ures |
|
1322 break; |
|
1323 } |
|
1324 } |
|
1325 operator Edge() const { return Edge(e, spec, n); } |
|
1326 }; |
|
1327 |
|
1328 class EdgeIt { |
|
1329 friend class GraphWrapper<Graph>; |
|
1330 friend class stGraphWrapper<Graph>; |
|
1331 typename Graph::EdgeIt e; |
|
1332 int spec; |
|
1333 typename Graph::ClassNodeIt n; |
|
1334 public: |
|
1335 EdgeIt() { } |
|
1336 EdgeIt(const typename Graph::EdgeIt& _e, int _spec, |
|
1337 const typename Graph::ClassNodeIt& _n) : |
|
1338 e(_e), spec(_spec), n(_n) { } |
|
1339 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
|
1340 EdgeIt(const stGraphWrapper<Graph>& _G) : |
|
1341 e(*(_G.graph)), spec(0), n(INVALID) { |
|
1342 if (!_G.graph->valid(e)) { |
|
1343 spec=1; |
|
1344 _G.graph->first(n, S_CLASS); |
|
1345 if (!_G.graph->valid(n)) { //Ha S ures |
|
1346 spec=2; |
|
1347 _G.graph->first(n, T_CLASS); |
|
1348 if (!_G.graph->valid(n)) { //Ha T ures |
|
1349 spec=3; |
|
1350 } |
|
1351 } |
|
1352 } |
|
1353 } |
|
1354 operator Edge() const { return Edge(e, spec, n); } |
|
1355 }; |
|
1356 |
|
1357 NodeIt& first(NodeIt& i) const { |
|
1358 i=NodeIt(*this); return i; |
|
1359 } |
|
1360 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1361 i=OutEdgeIt(*this, p); return i; |
|
1362 } |
|
1363 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1364 i=InEdgeIt(*this, p); return i; |
|
1365 } |
|
1366 EdgeIt& first(EdgeIt& i) const { |
|
1367 i=EdgeIt(*this); return i; |
|
1368 } |
|
1369 |
|
1370 NodeIt& next(NodeIt& i) const { |
|
1371 switch (i.spec) { |
|
1372 case 0: |
|
1373 this->graph->next(i.n); |
|
1374 if (!this->graph->valid(i.n)) { |
|
1375 i.spec=1; |
|
1376 } |
|
1377 break; |
|
1378 case 1: |
|
1379 i.spec=2; |
|
1380 break; |
|
1381 case 2: |
|
1382 i.spec=3; |
|
1383 break; |
|
1384 } |
|
1385 return i; |
|
1386 } |
|
1387 OutEdgeIt& next(OutEdgeIt& i) const { |
|
1388 typename Graph::Node v; |
|
1389 switch (i.spec) { |
|
1390 case 0: //normal edge |
|
1391 v=this->graph->aNode(i.e); |
|
1392 this->graph->next(i.e); |
|
1393 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
|
1394 if (this->graph->inSClass(v)) { //S, nincs kiel |
|
1395 i.spec=3; |
|
1396 i.n=INVALID; |
|
1397 } else { //T, van kiel |
|
1398 i.spec=2; |
|
1399 i.n=v; |
|
1400 } |
|
1401 } |
|
1402 break; |
|
1403 case 1: //s->vmi |
|
1404 this->graph->next(i.n); |
|
1405 if (!this->graph->valid(i.n)) i.spec=3; |
|
1406 break; |
|
1407 case 2: //vmi->t |
|
1408 i.spec=3; |
|
1409 i.n=INVALID; |
|
1410 break; |
|
1411 } |
|
1412 return i; |
|
1413 } |
|
1414 InEdgeIt& next(InEdgeIt& i) const { |
|
1415 typename Graph::Node v; |
|
1416 switch (i.spec) { |
|
1417 case 0: //normal edge |
|
1418 v=this->graph->aNode(i.e); |
|
1419 this->graph->next(i.e); |
|
1420 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
|
1421 if (this->graph->inTClass(v)) { //S, nincs beel |
|
1422 i.spec=3; |
|
1423 i.n=INVALID; |
|
1424 } else { //S, van beel |
|
1425 i.spec=1; |
|
1426 i.n=v; |
|
1427 } |
|
1428 } |
|
1429 break; |
|
1430 case 1: //s->vmi |
|
1431 i.spec=3; |
|
1432 i.n=INVALID; |
|
1433 break; |
|
1434 case 2: //vmi->t |
|
1435 this->graph->next(i.n); |
|
1436 if (!this->graph->valid(i.n)) i.spec=3; |
|
1437 break; |
|
1438 } |
|
1439 return i; |
|
1440 } |
|
1441 |
|
1442 EdgeIt& next(EdgeIt& i) const { |
|
1443 switch (i.spec) { |
|
1444 case 0: |
|
1445 this->graph->next(i.e); |
|
1446 if (!this->graph->valid(i.e)) { |
|
1447 i.spec=1; |
|
1448 this->graph->first(i.n, S_CLASS); |
|
1449 if (!this->graph->valid(i.n)) { |
|
1450 i.spec=2; |
|
1451 this->graph->first(i.n, T_CLASS); |
|
1452 if (!this->graph->valid(i.n)) i.spec=3; |
|
1453 } |
|
1454 } |
|
1455 break; |
|
1456 case 1: |
|
1457 this->graph->next(i.n); |
|
1458 if (!this->graph->valid(i.n)) { |
|
1459 i.spec=2; |
|
1460 this->graph->first(i.n, T_CLASS); |
|
1461 if (!this->graph->valid(i.n)) i.spec=3; |
|
1462 } |
|
1463 break; |
|
1464 case 2: |
|
1465 this->graph->next(i.n); |
|
1466 if (!this->graph->valid(i.n)) i.spec=3; |
|
1467 break; |
|
1468 } |
|
1469 return i; |
|
1470 } |
|
1471 |
|
1472 Node source(const Edge& e) const { |
|
1473 switch (e.spec) { |
|
1474 case 0: |
|
1475 return Node(this->graph->source(e)); |
|
1476 break; |
|
1477 case 1: |
|
1478 return S_NODE; |
|
1479 break; |
|
1480 case 2: |
|
1481 default: |
|
1482 return Node(e.n); |
|
1483 break; |
|
1484 } |
|
1485 } |
|
1486 Node target(const Edge& e) const { |
|
1487 switch (e.spec) { |
|
1488 case 0: |
|
1489 return Node(this->graph->target(e)); |
|
1490 break; |
|
1491 case 1: |
|
1492 return Node(e.n); |
|
1493 break; |
|
1494 case 2: |
|
1495 default: |
|
1496 return T_NODE; |
|
1497 break; |
|
1498 } |
|
1499 } |
|
1500 |
|
1501 bool valid(const Node& n) const { return (n.spec<3); } |
|
1502 bool valid(const Edge& e) const { return (e.spec<3); } |
|
1503 |
|
1504 int nodeNum() const { return this->graph->nodeNum()+2; } |
|
1505 int edgeNum() const { |
|
1506 return this->graph->edgeNum()+this->graph->nodeNum(); |
|
1507 } |
|
1508 |
|
1509 Node aNode(const OutEdgeIt& e) const { return source(e); } |
|
1510 Node aNode(const InEdgeIt& e) const { return target(e); } |
|
1511 Node bNode(const OutEdgeIt& e) const { return target(e); } |
|
1512 Node bNode(const InEdgeIt& e) const { return source(e); } |
|
1513 |
|
1514 void addNode() const { } |
|
1515 void addEdge() const { } |
|
1516 |
|
1517 // Node addNode() const { return Node(this->graph->addNode()); } |
|
1518 // Edge addEdge(const Node& source, const Node& target) const { |
|
1519 // return Edge(this->graph->addEdge(source, target)); } |
|
1520 |
|
1521 // void erase(const Node& i) const { this->graph->erase(i); } |
|
1522 // void erase(const Edge& i) const { this->graph->erase(i); } |
|
1523 |
|
1524 // void clear() const { this->graph->clear(); } |
|
1525 |
|
1526 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { |
|
1527 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent; |
|
1528 T s_value, t_value; |
|
1529 public: |
|
1530 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
|
1531 s_value(), |
|
1532 t_value() { } |
|
1533 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
|
1534 s_value(a), |
|
1535 t_value(a) { } |
|
1536 T operator[](const Node& n) const { |
|
1537 switch (n.spec) { |
|
1538 case 0: |
|
1539 return Parent::operator[](n); |
|
1540 break; |
|
1541 case 1: |
|
1542 return s_value; |
|
1543 break; |
|
1544 case 2: |
|
1545 default: |
|
1546 return t_value; |
|
1547 break; |
|
1548 } |
|
1549 } |
|
1550 void set(const Node& n, T t) { |
|
1551 switch (n.spec) { |
|
1552 case 0: |
|
1553 GraphWrapper<Graph>::template NodeMap<T>::set(n, t); |
|
1554 break; |
|
1555 case 1: |
|
1556 s_value=t; |
|
1557 break; |
|
1558 case 2: |
|
1559 default: |
|
1560 t_value=t; |
|
1561 break; |
|
1562 } |
|
1563 } |
|
1564 }; |
|
1565 |
|
1566 template<typename T, |
|
1567 typename Parent= |
|
1568 typename GraphWrapper<Graph>::template EdgeMap<T> > |
|
1569 class EdgeMap : public Parent { |
|
1570 //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
|
1571 typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
|
1572 public: |
|
1573 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
|
1574 node_value(_G) { } |
|
1575 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
|
1576 node_value(_G, a) { } |
|
1577 T operator[](const Edge& e) const { |
|
1578 switch (e.spec) { |
|
1579 case 0: |
|
1580 return Parent::operator[](e); |
|
1581 break; |
|
1582 case 1: |
|
1583 return node_value[e.n]; |
|
1584 break; |
|
1585 case 2: |
|
1586 default: |
|
1587 return node_value[e.n]; |
|
1588 break; |
|
1589 } |
|
1590 } |
|
1591 void set(const Edge& e, T t) { |
|
1592 switch (e.spec) { |
|
1593 case 0: |
|
1594 Parent::set(e, t); |
|
1595 break; |
|
1596 case 1: |
|
1597 node_value.set(e.n, t); |
|
1598 break; |
|
1599 case 2: |
|
1600 default: |
|
1601 node_value.set(e.n, t); |
|
1602 break; |
|
1603 } |
|
1604 } |
|
1605 }; |
|
1606 |
|
1607 // template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { |
|
1608 // typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
|
1609 // typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
|
1610 // public: |
|
1611 // EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
|
1612 // node_value(_G) { } |
|
1613 // EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
|
1614 // node_value(_G, a) { } |
|
1615 // T operator[](const Edge& e) const { |
|
1616 // switch (e.spec) { |
|
1617 // case 0: |
|
1618 // return Parent::operator[](e); |
|
1619 // break; |
|
1620 // case 1: |
|
1621 // return node_value[e.n]; |
|
1622 // break; |
|
1623 // case 2: |
|
1624 // default: |
|
1625 // return node_value[e.n]; |
|
1626 // break; |
|
1627 // } |
|
1628 // } |
|
1629 // void set(const Edge& e, T t) { |
|
1630 // switch (e.spec) { |
|
1631 // case 0: |
|
1632 // GraphWrapper<Graph>::template EdgeMap<T>::set(e, t); |
|
1633 // break; |
|
1634 // case 1: |
|
1635 // node_value.set(e.n, t); |
|
1636 // break; |
|
1637 // case 2: |
|
1638 // default: |
|
1639 // node_value.set(e.n, t); |
|
1640 // break; |
|
1641 // } |
|
1642 // } |
|
1643 // }; |
|
1644 |
|
1645 }; |
|
1646 |
|
1647 ///@} |
|
1648 |
|
1649 } //namespace lemon |
|
1650 |
|
1651 |
|
1652 #endif //LEMON_GRAPH_WRAPPER_H |
|
1653 |
|