|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_BITS_UGRAPH_EXTENDER_H |
|
20 #define LEMON_BITS_UGRAPH_EXTENDER_H |
|
21 |
|
22 #include <lemon/bits/invalid.h> |
|
23 #include <lemon/error.h> |
|
24 |
|
25 #include <lemon/bits/map_extender.h> |
|
26 #include <lemon/bits/default_map.h> |
|
27 |
|
28 #include <lemon/concept_check.h> |
|
29 #include <lemon/concept/maps.h> |
|
30 |
|
31 ///\ingroup graphbits |
|
32 ///\file |
|
33 ///\brief Extenders for the graph types |
|
34 namespace lemon { |
|
35 |
|
36 /// \ingroup graphbits |
|
37 /// |
|
38 /// \brief Extender for the UGraphs |
|
39 template <typename Base> |
|
40 class UGraphExtender : public Base { |
|
41 public: |
|
42 |
|
43 typedef Base Parent; |
|
44 typedef UGraphExtender Graph; |
|
45 |
|
46 typedef typename Parent::Node Node; |
|
47 typedef typename Parent::Edge Edge; |
|
48 typedef typename Parent::UEdge UEdge; |
|
49 |
|
50 // UGraph extension |
|
51 |
|
52 int maxId(Node) const { |
|
53 return Parent::maxNodeId(); |
|
54 } |
|
55 |
|
56 int maxId(Edge) const { |
|
57 return Parent::maxEdgeId(); |
|
58 } |
|
59 |
|
60 int maxId(UEdge) const { |
|
61 return Parent::maxUEdgeId(); |
|
62 } |
|
63 |
|
64 Node fromId(int id, Node) const { |
|
65 return Parent::nodeFromId(id); |
|
66 } |
|
67 |
|
68 Edge fromId(int id, Edge) const { |
|
69 return Parent::edgeFromId(id); |
|
70 } |
|
71 |
|
72 UEdge fromId(int id, UEdge) const { |
|
73 return Parent::uEdgeFromId(id); |
|
74 } |
|
75 |
|
76 Node oppositeNode(const Node &n, const UEdge &e) const { |
|
77 if( n == Parent::source(e)) |
|
78 return Parent::target(e); |
|
79 else if( n == Parent::target(e)) |
|
80 return Parent::source(e); |
|
81 else |
|
82 return INVALID; |
|
83 } |
|
84 |
|
85 Edge oppositeEdge(const Edge &e) const { |
|
86 return Parent::direct(e, !Parent::direction(e)); |
|
87 } |
|
88 |
|
89 using Parent::direct; |
|
90 Edge direct(const UEdge &ue, const Node &s) const { |
|
91 return Parent::direct(ue, Parent::source(ue) == s); |
|
92 } |
|
93 |
|
94 // Alterable extension |
|
95 |
|
96 typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier; |
|
97 typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier; |
|
98 typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier; |
|
99 |
|
100 |
|
101 protected: |
|
102 |
|
103 mutable NodeNotifier node_notifier; |
|
104 mutable EdgeNotifier edge_notifier; |
|
105 mutable UEdgeNotifier uedge_notifier; |
|
106 |
|
107 public: |
|
108 |
|
109 NodeNotifier& getNotifier(Node) const { |
|
110 return node_notifier; |
|
111 } |
|
112 |
|
113 EdgeNotifier& getNotifier(Edge) const { |
|
114 return edge_notifier; |
|
115 } |
|
116 |
|
117 UEdgeNotifier& getNotifier(UEdge) const { |
|
118 return uedge_notifier; |
|
119 } |
|
120 |
|
121 |
|
122 |
|
123 class NodeIt : public Node { |
|
124 const Graph* graph; |
|
125 public: |
|
126 |
|
127 NodeIt() {} |
|
128 |
|
129 NodeIt(Invalid i) : Node(i) { } |
|
130 |
|
131 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
132 _graph.first(static_cast<Node&>(*this)); |
|
133 } |
|
134 |
|
135 NodeIt(const Graph& _graph, const Node& node) |
|
136 : Node(node), graph(&_graph) {} |
|
137 |
|
138 NodeIt& operator++() { |
|
139 graph->next(*this); |
|
140 return *this; |
|
141 } |
|
142 |
|
143 }; |
|
144 |
|
145 |
|
146 class EdgeIt : public Edge { |
|
147 const Graph* graph; |
|
148 public: |
|
149 |
|
150 EdgeIt() { } |
|
151 |
|
152 EdgeIt(Invalid i) : Edge(i) { } |
|
153 |
|
154 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
155 _graph.first(static_cast<Edge&>(*this)); |
|
156 } |
|
157 |
|
158 EdgeIt(const Graph& _graph, const Edge& e) : |
|
159 Edge(e), graph(&_graph) { } |
|
160 |
|
161 EdgeIt& operator++() { |
|
162 graph->next(*this); |
|
163 return *this; |
|
164 } |
|
165 |
|
166 }; |
|
167 |
|
168 |
|
169 class OutEdgeIt : public Edge { |
|
170 const Graph* graph; |
|
171 public: |
|
172 |
|
173 OutEdgeIt() { } |
|
174 |
|
175 OutEdgeIt(Invalid i) : Edge(i) { } |
|
176 |
|
177 OutEdgeIt(const Graph& _graph, const Node& node) |
|
178 : graph(&_graph) { |
|
179 _graph.firstOut(*this, node); |
|
180 } |
|
181 |
|
182 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
183 : Edge(edge), graph(&_graph) {} |
|
184 |
|
185 OutEdgeIt& operator++() { |
|
186 graph->nextOut(*this); |
|
187 return *this; |
|
188 } |
|
189 |
|
190 }; |
|
191 |
|
192 |
|
193 class InEdgeIt : public Edge { |
|
194 const Graph* graph; |
|
195 public: |
|
196 |
|
197 InEdgeIt() { } |
|
198 |
|
199 InEdgeIt(Invalid i) : Edge(i) { } |
|
200 |
|
201 InEdgeIt(const Graph& _graph, const Node& node) |
|
202 : graph(&_graph) { |
|
203 _graph.firstIn(*this, node); |
|
204 } |
|
205 |
|
206 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
207 Edge(edge), graph(&_graph) {} |
|
208 |
|
209 InEdgeIt& operator++() { |
|
210 graph->nextIn(*this); |
|
211 return *this; |
|
212 } |
|
213 |
|
214 }; |
|
215 |
|
216 |
|
217 class UEdgeIt : public Parent::UEdge { |
|
218 const Graph* graph; |
|
219 public: |
|
220 |
|
221 UEdgeIt() { } |
|
222 |
|
223 UEdgeIt(Invalid i) : UEdge(i) { } |
|
224 |
|
225 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
226 _graph.first(static_cast<UEdge&>(*this)); |
|
227 } |
|
228 |
|
229 UEdgeIt(const Graph& _graph, const UEdge& e) : |
|
230 UEdge(e), graph(&_graph) { } |
|
231 |
|
232 UEdgeIt& operator++() { |
|
233 graph->next(*this); |
|
234 return *this; |
|
235 } |
|
236 |
|
237 }; |
|
238 |
|
239 class IncEdgeIt : public Parent::UEdge { |
|
240 friend class UGraphExtender; |
|
241 const Graph* graph; |
|
242 bool direction; |
|
243 public: |
|
244 |
|
245 IncEdgeIt() { } |
|
246 |
|
247 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } |
|
248 |
|
249 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { |
|
250 _graph.firstInc(*this, direction, n); |
|
251 } |
|
252 |
|
253 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) |
|
254 : graph(&_graph), UEdge(ue) { |
|
255 direction = (_graph.source(ue) == n); |
|
256 } |
|
257 |
|
258 IncEdgeIt& operator++() { |
|
259 graph->nextInc(*this, direction); |
|
260 return *this; |
|
261 } |
|
262 }; |
|
263 |
|
264 /// \brief Base node of the iterator |
|
265 /// |
|
266 /// Returns the base node (ie. the source in this case) of the iterator |
|
267 Node baseNode(const OutEdgeIt &e) const { |
|
268 return Parent::source((Edge)e); |
|
269 } |
|
270 /// \brief Running node of the iterator |
|
271 /// |
|
272 /// Returns the running node (ie. the target in this case) of the |
|
273 /// iterator |
|
274 Node runningNode(const OutEdgeIt &e) const { |
|
275 return Parent::target((Edge)e); |
|
276 } |
|
277 |
|
278 /// \brief Base node of the iterator |
|
279 /// |
|
280 /// Returns the base node (ie. the target in this case) of the iterator |
|
281 Node baseNode(const InEdgeIt &e) const { |
|
282 return Parent::target((Edge)e); |
|
283 } |
|
284 /// \brief Running node of the iterator |
|
285 /// |
|
286 /// Returns the running node (ie. the source in this case) of the |
|
287 /// iterator |
|
288 Node runningNode(const InEdgeIt &e) const { |
|
289 return Parent::source((Edge)e); |
|
290 } |
|
291 |
|
292 /// Base node of the iterator |
|
293 /// |
|
294 /// Returns the base node of the iterator |
|
295 Node baseNode(const IncEdgeIt &e) const { |
|
296 return e.direction ? source(e) : target(e); |
|
297 } |
|
298 /// Running node of the iterator |
|
299 /// |
|
300 /// Returns the running node of the iterator |
|
301 Node runningNode(const IncEdgeIt &e) const { |
|
302 return e.direction ? target(e) : source(e); |
|
303 } |
|
304 |
|
305 // Mappable extension |
|
306 |
|
307 template <typename _Value> |
|
308 class NodeMap |
|
309 : public MapExtender<DefaultMap<Graph, Node, _Value> > { |
|
310 public: |
|
311 typedef UGraphExtender Graph; |
|
312 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; |
|
313 |
|
314 NodeMap(const Graph& graph) |
|
315 : Parent(graph) {} |
|
316 NodeMap(const Graph& graph, const _Value& value) |
|
317 : Parent(graph, value) {} |
|
318 |
|
319 NodeMap& operator=(const NodeMap& cmap) { |
|
320 return operator=<NodeMap>(cmap); |
|
321 } |
|
322 |
|
323 template <typename CMap> |
|
324 NodeMap& operator=(const CMap& cmap) { |
|
325 Parent::operator=(cmap); |
|
326 return *this; |
|
327 } |
|
328 |
|
329 }; |
|
330 |
|
331 template <typename _Value> |
|
332 class EdgeMap |
|
333 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { |
|
334 public: |
|
335 typedef UGraphExtender Graph; |
|
336 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; |
|
337 |
|
338 EdgeMap(const Graph& graph) |
|
339 : Parent(graph) {} |
|
340 EdgeMap(const Graph& graph, const _Value& value) |
|
341 : Parent(graph, value) {} |
|
342 |
|
343 EdgeMap& operator=(const EdgeMap& cmap) { |
|
344 return operator=<EdgeMap>(cmap); |
|
345 } |
|
346 |
|
347 template <typename CMap> |
|
348 EdgeMap& operator=(const CMap& cmap) { |
|
349 Parent::operator=(cmap); |
|
350 return *this; |
|
351 } |
|
352 }; |
|
353 |
|
354 |
|
355 template <typename _Value> |
|
356 class UEdgeMap |
|
357 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { |
|
358 public: |
|
359 typedef UGraphExtender Graph; |
|
360 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; |
|
361 |
|
362 UEdgeMap(const Graph& graph) |
|
363 : Parent(graph) {} |
|
364 |
|
365 UEdgeMap(const Graph& graph, const _Value& value) |
|
366 : Parent(graph, value) {} |
|
367 |
|
368 UEdgeMap& operator=(const UEdgeMap& cmap) { |
|
369 return operator=<UEdgeMap>(cmap); |
|
370 } |
|
371 |
|
372 template <typename CMap> |
|
373 UEdgeMap& operator=(const CMap& cmap) { |
|
374 Parent::operator=(cmap); |
|
375 return *this; |
|
376 } |
|
377 |
|
378 }; |
|
379 |
|
380 // Alteration extension |
|
381 |
|
382 Node addNode() { |
|
383 Node node = Parent::addNode(); |
|
384 getNotifier(Node()).add(node); |
|
385 return node; |
|
386 } |
|
387 |
|
388 UEdge addEdge(const Node& from, const Node& to) { |
|
389 UEdge uedge = Parent::addEdge(from, to); |
|
390 getNotifier(UEdge()).add(uedge); |
|
391 getNotifier(Edge()).add(Parent::direct(uedge, true)); |
|
392 getNotifier(Edge()).add(Parent::direct(uedge, false)); |
|
393 return uedge; |
|
394 } |
|
395 |
|
396 void clear() { |
|
397 getNotifier(Edge()).clear(); |
|
398 getNotifier(UEdge()).clear(); |
|
399 getNotifier(Node()).clear(); |
|
400 Parent::clear(); |
|
401 } |
|
402 |
|
403 void erase(const Node& node) { |
|
404 Edge edge; |
|
405 Parent::firstOut(edge, node); |
|
406 while (edge != INVALID ) { |
|
407 erase(edge); |
|
408 Parent::firstOut(edge, node); |
|
409 } |
|
410 |
|
411 Parent::firstIn(edge, node); |
|
412 while (edge != INVALID ) { |
|
413 erase(edge); |
|
414 Parent::firstIn(edge, node); |
|
415 } |
|
416 |
|
417 getNotifier(Node()).erase(node); |
|
418 Parent::erase(node); |
|
419 } |
|
420 |
|
421 void erase(const UEdge& uedge) { |
|
422 getNotifier(Edge()).erase(Parent::direct(uedge, true)); |
|
423 getNotifier(Edge()).erase(Parent::direct(uedge, false)); |
|
424 getNotifier(UEdge()).erase(uedge); |
|
425 Parent::erase(uedge); |
|
426 } |
|
427 |
|
428 UGraphExtender() { |
|
429 node_notifier.setContainer(*this); |
|
430 edge_notifier.setContainer(*this); |
|
431 uedge_notifier.setContainer(*this); |
|
432 } |
|
433 |
|
434 ~UGraphExtender() { |
|
435 uedge_notifier.clear(); |
|
436 edge_notifier.clear(); |
|
437 node_notifier.clear(); |
|
438 } |
|
439 |
|
440 }; |
|
441 |
|
442 } |
|
443 |
|
444 #endif |