1 /* -*- C++ -*- |
|
2 * |
|
3 * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic |
|
4 * C++ optimization library |
|
5 * |
|
6 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi |
|
7 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization, |
|
8 * EGRES). |
|
9 * |
|
10 * Permission to use, modify and distribute this software is granted |
|
11 * provided that this copyright notice appears in all copies. For |
|
12 * precise terms see the accompanying LICENSE file. |
|
13 * |
|
14 * This software is provided "AS IS" with no warranty of any kind, |
|
15 * express or implied, and with no claim as to its suitability for any |
|
16 * purpose. |
|
17 * |
|
18 */ |
|
19 |
|
20 ///\ingroup graph_concepts |
|
21 ///\file |
|
22 ///\brief Undirected graphs and components of. |
|
23 |
|
24 |
|
25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H |
|
26 #define LEMON_CONCEPT_UNDIR_GRAPH_H |
|
27 |
|
28 #include <lemon/concept/graph_component.h> |
|
29 |
|
30 namespace lemon { |
|
31 namespace concept { |
|
32 |
|
33 /// \addtogroup graph_concepts |
|
34 /// @{ |
|
35 |
|
36 |
|
37 /// Skeleton class which describes an edge with direction in \ref |
|
38 /// UndirGraph "undirected graph". |
|
39 template <typename UndirGraph> |
|
40 class UndirGraphEdge : public UndirGraph::UndirEdge { |
|
41 typedef typename UndirGraph::UndirEdge UndirEdge; |
|
42 typedef typename UndirGraph::Node Node; |
|
43 public: |
|
44 |
|
45 /// \e |
|
46 UndirGraphEdge() {} |
|
47 |
|
48 /// \e |
|
49 UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {} |
|
50 |
|
51 /// \e |
|
52 UndirGraphEdge(Invalid) {} |
|
53 |
|
54 /// \brief Directed edge from undirected edge and a source node. |
|
55 /// |
|
56 /// Constructs a directed edge from undirected edge and a source node. |
|
57 /// |
|
58 /// \note You have to specify the graph for this constructor. |
|
59 UndirGraphEdge(const UndirGraph &g, |
|
60 UndirEdge undir_edge, Node n) { |
|
61 ignore_unused_variable_warning(undir_edge); |
|
62 ignore_unused_variable_warning(g); |
|
63 ignore_unused_variable_warning(n); |
|
64 } |
|
65 |
|
66 /// \e |
|
67 UndirGraphEdge& operator=(UndirGraphEdge) { return *this; } |
|
68 |
|
69 /// \e |
|
70 bool operator==(UndirGraphEdge) const { return true; } |
|
71 /// \e |
|
72 bool operator!=(UndirGraphEdge) const { return false; } |
|
73 |
|
74 /// \e |
|
75 bool operator<(UndirGraphEdge) const { return false; } |
|
76 |
|
77 template <typename Edge> |
|
78 struct Constraints { |
|
79 void constraints() { |
|
80 const_constraints(); |
|
81 } |
|
82 void const_constraints() const { |
|
83 /// \bug This should be is_base_and_derived ... |
|
84 UndirEdge ue = e; |
|
85 ue = e; |
|
86 |
|
87 Edge e_with_source(graph,ue,n); |
|
88 ignore_unused_variable_warning(e_with_source); |
|
89 } |
|
90 Edge e; |
|
91 UndirEdge ue; |
|
92 UndirGraph graph; |
|
93 Node n; |
|
94 }; |
|
95 }; |
|
96 |
|
97 |
|
98 struct BaseIterableUndirGraphConcept { |
|
99 |
|
100 template <typename Graph> |
|
101 struct Constraints { |
|
102 |
|
103 typedef typename Graph::UndirEdge UndirEdge; |
|
104 typedef typename Graph::Edge Edge; |
|
105 typedef typename Graph::Node Node; |
|
106 |
|
107 void constraints() { |
|
108 checkConcept<BaseIterableGraphComponent, Graph>(); |
|
109 checkConcept<GraphItem<>, UndirEdge>(); |
|
110 checkConcept<UndirGraphEdge<Graph>, Edge>(); |
|
111 |
|
112 graph.first(ue); |
|
113 graph.next(ue); |
|
114 |
|
115 const_constraints(); |
|
116 } |
|
117 void const_constraints() { |
|
118 Node n; |
|
119 n = graph.target(ue); |
|
120 n = graph.source(ue); |
|
121 n = graph.oppositeNode(n0, ue); |
|
122 |
|
123 bool b; |
|
124 b = graph.forward(e); |
|
125 ignore_unused_variable_warning(b); |
|
126 } |
|
127 |
|
128 Graph graph; |
|
129 Edge e; |
|
130 Node n0; |
|
131 UndirEdge ue; |
|
132 }; |
|
133 |
|
134 }; |
|
135 |
|
136 |
|
137 struct IterableUndirGraphConcept { |
|
138 |
|
139 template <typename Graph> |
|
140 struct Constraints { |
|
141 void constraints() { |
|
142 /// \todo we don't need the iterable component to be base iterable |
|
143 /// Don't we really??? |
|
144 //checkConcept< BaseIterableUndirGraphConcept, Graph > (); |
|
145 |
|
146 checkConcept<IterableGraphComponent, Graph> (); |
|
147 |
|
148 typedef typename Graph::UndirEdge UndirEdge; |
|
149 typedef typename Graph::UndirEdgeIt UndirEdgeIt; |
|
150 typedef typename Graph::IncEdgeIt IncEdgeIt; |
|
151 |
|
152 checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>(); |
|
153 checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>(); |
|
154 } |
|
155 }; |
|
156 |
|
157 }; |
|
158 |
|
159 struct MappableUndirGraphConcept { |
|
160 |
|
161 template <typename Graph> |
|
162 struct Constraints { |
|
163 |
|
164 struct Dummy { |
|
165 int value; |
|
166 Dummy() : value(0) {} |
|
167 Dummy(int _v) : value(_v) {} |
|
168 }; |
|
169 |
|
170 void constraints() { |
|
171 checkConcept<MappableGraphComponent, Graph>(); |
|
172 |
|
173 typedef typename Graph::template UndirEdgeMap<int> IntMap; |
|
174 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>, |
|
175 IntMap >(); |
|
176 |
|
177 typedef typename Graph::template UndirEdgeMap<bool> BoolMap; |
|
178 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>, |
|
179 BoolMap >(); |
|
180 |
|
181 typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap; |
|
182 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>, |
|
183 DummyMap >(); |
|
184 } |
|
185 }; |
|
186 |
|
187 }; |
|
188 |
|
189 struct ExtendableUndirGraphConcept { |
|
190 |
|
191 template <typename Graph> |
|
192 struct Constraints { |
|
193 void constraints() { |
|
194 node_a = graph.addNode(); |
|
195 uedge = graph.addEdge(node_a, node_b); |
|
196 } |
|
197 typename Graph::Node node_a, node_b; |
|
198 typename Graph::UndirEdge uedge; |
|
199 Graph graph; |
|
200 }; |
|
201 |
|
202 }; |
|
203 |
|
204 struct ErasableUndirGraphConcept { |
|
205 |
|
206 template <typename Graph> |
|
207 struct Constraints { |
|
208 void constraints() { |
|
209 graph.erase(n); |
|
210 graph.erase(e); |
|
211 } |
|
212 Graph graph; |
|
213 typename Graph::Node n; |
|
214 typename Graph::UndirEdge e; |
|
215 }; |
|
216 |
|
217 }; |
|
218 |
|
219 /// Class describing the concept of Undirected Graphs. |
|
220 |
|
221 /// This class describes the common interface of all Undirected |
|
222 /// Graphs. |
|
223 /// |
|
224 /// As all concept describing classes it provides only interface |
|
225 /// without any sensible implementation. So any algorithm for |
|
226 /// undirected graph should compile with this class, but it will not |
|
227 /// run properly, of couse. |
|
228 /// |
|
229 /// In LEMON undirected graphs also fulfill the concept of directed |
|
230 /// graphs (\ref lemon::concept::Graph "Graph Concept"). For |
|
231 /// explanation of this and more see also the page \ref undir_graphs, |
|
232 /// a tutorial about undirected graphs. |
|
233 |
|
234 class UndirGraph { |
|
235 public: |
|
236 |
|
237 /// Type describing a node in the graph |
|
238 typedef GraphNode Node; |
|
239 |
|
240 /// Type describing an undirected edge |
|
241 typedef GraphItem<'u'> UndirEdge; |
|
242 |
|
243 /// Type describing an UndirEdge with direction |
|
244 #ifndef DOXYGEN |
|
245 typedef UndirGraphEdge<UndirGraph> Edge; |
|
246 #else |
|
247 typedef UndirGraphEdge Edge; |
|
248 #endif |
|
249 |
|
250 /// Iterator type which iterates over all nodes |
|
251 #ifndef DOXYGEN |
|
252 typedef GraphIterator<UndirGraph, Node> NodeIt; |
|
253 #else |
|
254 typedef GraphIterator NodeIt; |
|
255 #endif |
|
256 |
|
257 /// Iterator type which iterates over all undirected edges |
|
258 #ifndef DOXYGEN |
|
259 typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt; |
|
260 #else |
|
261 typedef GraphIterator UndirEdgeIt; |
|
262 #endif |
|
263 |
|
264 /// Iterator type which iterates over all directed edges. |
|
265 |
|
266 /// Iterator type which iterates over all edges (each undirected |
|
267 /// edge occurs twice with both directions. |
|
268 #ifndef DOXYGEN |
|
269 typedef GraphIterator<UndirGraph, Edge> EdgeIt; |
|
270 #else |
|
271 typedef GraphIterator EdgeIt; |
|
272 #endif |
|
273 |
|
274 |
|
275 /// Iterator of undirected edges incident to a node |
|
276 #ifndef DOXYGEN |
|
277 typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt; |
|
278 #else |
|
279 typedef GraphIncIterator IncEdgeIt; |
|
280 #endif |
|
281 |
|
282 /// Iterator of edges incoming to a node |
|
283 #ifndef DOXYGEN |
|
284 typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt; |
|
285 #else |
|
286 typedef GraphIncIterator InEdgeIt; |
|
287 #endif |
|
288 |
|
289 /// Iterator of edges outgoing from a node |
|
290 #ifndef DOXYGEN |
|
291 typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt; |
|
292 #else |
|
293 typedef GraphIncIterator OutEdgeIt; |
|
294 #endif |
|
295 |
|
296 /// NodeMap template |
|
297 #ifdef DOXYGEN |
|
298 typedef GraphMap NodeMap<T>; |
|
299 #endif |
|
300 |
|
301 /// UndirEdgeMap template |
|
302 #ifdef DOXYGEN |
|
303 typedef GraphMap UndirEdgeMap<T>; |
|
304 #endif |
|
305 |
|
306 /// EdgeMap template |
|
307 #ifdef DOXYGEN |
|
308 typedef GraphMap EdgeMap<T>; |
|
309 #endif |
|
310 |
|
311 template <typename T> |
|
312 class NodeMap : public GraphMap<UndirGraph, Node, T> { |
|
313 typedef GraphMap<UndirGraph, Node, T> Parent; |
|
314 public: |
|
315 |
|
316 explicit NodeMap(const UndirGraph &g) : Parent(g) {} |
|
317 NodeMap(const UndirGraph &g, T t) : Parent(g, t) {} |
|
318 }; |
|
319 |
|
320 template <typename T> |
|
321 class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> { |
|
322 typedef GraphMap<UndirGraph, UndirEdge, T> Parent; |
|
323 public: |
|
324 |
|
325 explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {} |
|
326 UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} |
|
327 }; |
|
328 |
|
329 template <typename T> |
|
330 class EdgeMap : public GraphMap<UndirGraph, Edge, T> { |
|
331 typedef GraphMap<UndirGraph, Edge, T> Parent; |
|
332 public: |
|
333 |
|
334 explicit EdgeMap(const UndirGraph &g) : Parent(g) {} |
|
335 EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} |
|
336 }; |
|
337 |
|
338 /// Is the Edge oriented "forward"? |
|
339 |
|
340 /// Returns whether the given directed edge is same orientation as |
|
341 /// the corresponding undirected edge. |
|
342 /// |
|
343 /// \todo "What does the direction of an undirected edge mean?" |
|
344 bool forward(Edge) const { return true; } |
|
345 |
|
346 /// Opposite node on an edge |
|
347 |
|
348 /// \return the opposite of the given Node on the given Edge |
|
349 /// |
|
350 /// \todo What should we do if given Node and Edge are not incident? |
|
351 Node oppositeNode(Node, UndirEdge) const { return INVALID; } |
|
352 |
|
353 /// First node of the undirected edge. |
|
354 |
|
355 /// \return the first node of the given UndirEdge. |
|
356 /// |
|
357 /// Naturally undirectected edges don't have direction and thus |
|
358 /// don't have source and target node. But we use these two methods |
|
359 /// to query the two endnodes of the edge. The direction of the edge |
|
360 /// which arises this way is called the inherent direction of the |
|
361 /// undirected edge, and is used to define the "forward" direction |
|
362 /// of the directed versions of the edges. |
|
363 /// \sa forward |
|
364 Node source(UndirEdge) const { return INVALID; } |
|
365 |
|
366 /// Second node of the undirected edge. |
|
367 Node target(UndirEdge) const { return INVALID; } |
|
368 |
|
369 /// Source node of the directed edge. |
|
370 Node source(Edge) const { return INVALID; } |
|
371 |
|
372 /// Target node of the directed edge. |
|
373 Node target(Edge) const { return INVALID; } |
|
374 |
|
375 /// First node of the graph |
|
376 |
|
377 /// \note This method is part of so called \ref |
|
378 /// developpers_interface "Developpers' interface", so it shouldn't |
|
379 /// be used in an end-user program. |
|
380 void first(Node&) const {} |
|
381 /// Next node of the graph |
|
382 |
|
383 /// \note This method is part of so called \ref |
|
384 /// developpers_interface "Developpers' interface", so it shouldn't |
|
385 /// be used in an end-user program. |
|
386 void next(Node&) const {} |
|
387 |
|
388 /// First undirected edge of the graph |
|
389 |
|
390 /// \note This method is part of so called \ref |
|
391 /// developpers_interface "Developpers' interface", so it shouldn't |
|
392 /// be used in an end-user program. |
|
393 void first(UndirEdge&) const {} |
|
394 /// Next undirected edge of the graph |
|
395 |
|
396 /// \note This method is part of so called \ref |
|
397 /// developpers_interface "Developpers' interface", so it shouldn't |
|
398 /// be used in an end-user program. |
|
399 void next(UndirEdge&) const {} |
|
400 |
|
401 /// First directed edge of the graph |
|
402 |
|
403 /// \note This method is part of so called \ref |
|
404 /// developpers_interface "Developpers' interface", so it shouldn't |
|
405 /// be used in an end-user program. |
|
406 void first(Edge&) const {} |
|
407 /// Next directed edge of the graph |
|
408 |
|
409 /// \note This method is part of so called \ref |
|
410 /// developpers_interface "Developpers' interface", so it shouldn't |
|
411 /// be used in an end-user program. |
|
412 void next(Edge&) const {} |
|
413 |
|
414 /// First outgoing edge from a given node |
|
415 |
|
416 /// \note This method is part of so called \ref |
|
417 /// developpers_interface "Developpers' interface", so it shouldn't |
|
418 /// be used in an end-user program. |
|
419 void firstOut(Edge&, Node) const {} |
|
420 /// Next outgoing edge to a node |
|
421 |
|
422 /// \note This method is part of so called \ref |
|
423 /// developpers_interface "Developpers' interface", so it shouldn't |
|
424 /// be used in an end-user program. |
|
425 void nextOut(Edge&) const {} |
|
426 |
|
427 /// First incoming edge to a given node |
|
428 |
|
429 /// \note This method is part of so called \ref |
|
430 /// developpers_interface "Developpers' interface", so it shouldn't |
|
431 /// be used in an end-user program. |
|
432 void firstIn(Edge&, Node) const {} |
|
433 /// Next incoming edge to a node |
|
434 |
|
435 /// \note This method is part of so called \ref |
|
436 /// developpers_interface "Developpers' interface", so it shouldn't |
|
437 /// be used in an end-user program. |
|
438 void nextIn(Edge&) const {} |
|
439 |
|
440 |
|
441 /// Base node of the iterator |
|
442 /// |
|
443 /// Returns the base node (the source in this case) of the iterator |
|
444 Node baseNode(OutEdgeIt e) const { |
|
445 return source(e); |
|
446 } |
|
447 /// Running node of the iterator |
|
448 /// |
|
449 /// Returns the running node (the target in this case) of the |
|
450 /// iterator |
|
451 Node runningNode(OutEdgeIt e) const { |
|
452 return target(e); |
|
453 } |
|
454 |
|
455 /// Base node of the iterator |
|
456 /// |
|
457 /// Returns the base node (the target in this case) of the iterator |
|
458 Node baseNode(InEdgeIt e) const { |
|
459 return target(e); |
|
460 } |
|
461 /// Running node of the iterator |
|
462 /// |
|
463 /// Returns the running node (the source in this case) of the |
|
464 /// iterator |
|
465 Node runningNode(InEdgeIt e) const { |
|
466 return source(e); |
|
467 } |
|
468 |
|
469 /// Base node of the iterator |
|
470 /// |
|
471 /// Returns the base node of the iterator |
|
472 Node baseNode(IncEdgeIt) const { |
|
473 return INVALID; |
|
474 } |
|
475 /// Running node of the iterator |
|
476 /// |
|
477 /// Returns the running node of the iterator |
|
478 Node runningNode(IncEdgeIt) const { |
|
479 return INVALID; |
|
480 } |
|
481 |
|
482 |
|
483 template <typename Graph> |
|
484 struct Constraints { |
|
485 void constraints() { |
|
486 checkConcept<BaseIterableUndirGraphConcept, Graph>(); |
|
487 checkConcept<IterableUndirGraphConcept, Graph>(); |
|
488 checkConcept<MappableUndirGraphConcept, Graph>(); |
|
489 } |
|
490 }; |
|
491 |
|
492 }; |
|
493 |
|
494 class ExtendableUndirGraph : public UndirGraph { |
|
495 public: |
|
496 |
|
497 template <typename Graph> |
|
498 struct Constraints { |
|
499 void constraints() { |
|
500 checkConcept<BaseIterableUndirGraphConcept, Graph>(); |
|
501 checkConcept<IterableUndirGraphConcept, Graph>(); |
|
502 checkConcept<MappableUndirGraphConcept, Graph>(); |
|
503 |
|
504 checkConcept<UndirGraph, Graph>(); |
|
505 checkConcept<ExtendableUndirGraphConcept, Graph>(); |
|
506 checkConcept<ClearableGraphComponent, Graph>(); |
|
507 } |
|
508 }; |
|
509 |
|
510 }; |
|
511 |
|
512 class ErasableUndirGraph : public ExtendableUndirGraph { |
|
513 public: |
|
514 |
|
515 template <typename Graph> |
|
516 struct Constraints { |
|
517 void constraints() { |
|
518 checkConcept<ExtendableUndirGraph, Graph>(); |
|
519 checkConcept<ErasableUndirGraphConcept, Graph>(); |
|
520 } |
|
521 }; |
|
522 |
|
523 }; |
|
524 |
|
525 /// @} |
|
526 |
|
527 } |
|
528 |
|
529 } |
|
530 |
|
531 #endif |
|