28 #include <lemon/concept/graph_component.h> |
28 #include <lemon/concept/graph_component.h> |
29 |
29 |
30 namespace lemon { |
30 namespace lemon { |
31 namespace concept { |
31 namespace concept { |
32 |
32 |
33 /// \todo to be done |
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 UndirEdge> |
|
40 class UndirGraphEdge : public UndirEdge { |
|
41 public: |
|
42 |
|
43 /// \e |
|
44 UndirGraphEdge() {} |
|
45 |
|
46 /// \e |
|
47 UndirGraphEdge(const UndirGraphEdge&) {} |
|
48 |
|
49 /// \e |
|
50 UndirGraphEdge(Invalid) {} |
|
51 |
|
52 /// \brief Constructs a directed version of an undirected edge |
|
53 /// |
|
54 /// \param forward If \c true the direction of the contructed edge |
|
55 /// is the same as the inherent direction of the \c undir_edge; if |
|
56 /// \c false --- the opposite. |
|
57 UndirGraphEdge(UndirEdge undir_edge, bool forward) { |
|
58 ignore_unused_variable_warning(undir_edge); |
|
59 ignore_unused_variable_warning(forward); |
|
60 } |
|
61 |
|
62 /// \e |
|
63 UndirGraphEdge& operator=(UndirGraphEdge) { return *this; } |
|
64 |
|
65 /// \e |
|
66 bool operator==(UndirGraphEdge) const { return true; } |
|
67 /// \e |
|
68 bool operator!=(UndirGraphEdge) const { return false; } |
|
69 |
|
70 /// \e |
|
71 bool operator<(UndirGraphEdge) const { return false; } |
|
72 |
|
73 template <typename Edge> |
|
74 struct Constraints { |
|
75 void constraints() { |
|
76 /// \bug This should be is_base_and_derived ... |
|
77 UndirEdge ue = e; |
|
78 ue = e; |
|
79 Edge forward(ue, true); |
|
80 Edge backward(ue, false); |
|
81 |
|
82 ignore_unused_variable_warning(forward); |
|
83 ignore_unused_variable_warning(backward); |
|
84 } |
|
85 Edge e; |
|
86 }; |
|
87 }; |
|
88 |
34 |
89 |
35 struct BaseIterableUndirGraphConcept { |
90 struct BaseIterableUndirGraphConcept { |
36 |
91 |
37 template <typename Graph> |
92 template <typename Graph> |
38 struct Constraints { |
93 struct Constraints { |
143 typename Graph::UndirEdge e; |
206 typename Graph::UndirEdge e; |
144 }; |
207 }; |
145 |
208 |
146 }; |
209 }; |
147 |
210 |
|
211 /// Class describing the concept of Undirected Graphs. |
|
212 |
|
213 /// This class describes the common interface of all Undirected |
|
214 /// Graphs. |
|
215 /// |
|
216 /// As all concept describing classes it provides only interface |
|
217 /// without any sensible implementation. So any algorithm for |
|
218 /// undirected graph should compile with this class, but it will not |
|
219 /// run properly, of couse. |
|
220 /// |
|
221 /// In LEMON undirected graphs also fulfill the concept of directed |
|
222 /// graphs (\ref lemon::concept::Graph "Graph Concept"). For |
|
223 /// explanation of this and more see also the page \ref undir_graphs, |
|
224 /// a tutorial about undirected graphs. |
|
225 |
148 class UndirGraph { |
226 class UndirGraph { |
149 public: |
227 public: |
|
228 |
|
229 /// Type describing a node in the graph |
|
230 typedef GraphNode Node; |
|
231 |
|
232 /// Type describing an undirected edge |
|
233 typedef GraphItem<'u'> UndirEdge; |
|
234 |
|
235 /// Type describing an UndirEdge with direction |
|
236 #ifndef DOXYGEN |
|
237 typedef UndirGraphEdge<UndirEdge> Edge; |
|
238 #else |
|
239 typedef UndirGraphEdge Edge; |
|
240 #endif |
|
241 |
|
242 /// Iterator type which iterates over all nodes |
|
243 #ifndef DOXYGEN |
|
244 typedef GraphIterator<UndirGraph, Node> NodeIt; |
|
245 #else |
|
246 typedef GraphIterator NodeIt; |
|
247 #endif |
|
248 |
|
249 /// Iterator type which iterates over all undirected edges |
|
250 #ifndef DOXYGEN |
|
251 typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt; |
|
252 #else |
|
253 typedef GraphIterator UndirEdgeIt; |
|
254 #endif |
|
255 |
|
256 /// Iterator type which iterates over all directed edges. |
|
257 |
|
258 /// Iterator type which iterates over all edges (each undirected |
|
259 /// edge occurs twice with both directions. |
|
260 #ifndef DOXYGEN |
|
261 typedef GraphIterator<UndirGraph, Edge> EdgeIt; |
|
262 #else |
|
263 typedef GraphIterator EdgeIt; |
|
264 #endif |
|
265 |
|
266 |
|
267 /// Iterator of undirected edges incident to a node |
|
268 #ifndef DOXYGEN |
|
269 typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt; |
|
270 #else |
|
271 typedef GraphIncIterator IncEdgeIt; |
|
272 #endif |
|
273 |
|
274 /// Iterator of edges incoming to a node |
|
275 #ifndef DOXYGEN |
|
276 typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt; |
|
277 #else |
|
278 typedef GraphIncIterator InEdgeIt; |
|
279 #endif |
|
280 |
|
281 /// Iterator of edges outgoing from a node |
|
282 #ifndef DOXYGEN |
|
283 typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt; |
|
284 #else |
|
285 typedef GraphIncIterator OutEdgeIt; |
|
286 #endif |
|
287 |
|
288 /// NodeMap template |
|
289 #ifdef DOXYGEN |
|
290 typedef GraphMap NodeMap<T>; |
|
291 #endif |
|
292 |
|
293 /// UndirEdgeMap template |
|
294 #ifdef DOXYGEN |
|
295 typedef GraphMap UndirEdgeMap<T>; |
|
296 #endif |
|
297 |
|
298 /// EdgeMap template |
|
299 #ifdef DOXYGEN |
|
300 typedef GraphMap EdgeMap<T>; |
|
301 #endif |
|
302 |
|
303 template <typename T> |
|
304 class NodeMap : public GraphMap<UndirGraph, Node, T> { |
|
305 typedef GraphMap<UndirGraph, Node, T> Parent; |
|
306 public: |
|
307 |
|
308 explicit NodeMap(const UndirGraph &g) : Parent(g) {} |
|
309 NodeMap(const UndirGraph &g, T t) : Parent(g, t) {} |
|
310 }; |
|
311 |
|
312 template <typename T> |
|
313 class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> { |
|
314 typedef GraphMap<UndirGraph, UndirEdge, T> Parent; |
|
315 public: |
|
316 |
|
317 explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {} |
|
318 UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} |
|
319 }; |
|
320 |
|
321 template <typename T> |
|
322 class EdgeMap : public GraphMap<UndirGraph, Edge, T> { |
|
323 typedef GraphMap<UndirGraph, Edge, T> Parent; |
|
324 public: |
|
325 |
|
326 explicit EdgeMap(const UndirGraph &g) : Parent(g) {} |
|
327 EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} |
|
328 }; |
|
329 |
|
330 /// Is the Edge oriented "forward"? |
|
331 |
|
332 /// Returns whether the given directed edge is same orientation as |
|
333 /// the corresponding undirected edge. |
|
334 /// |
|
335 /// \todo "What does the direction of an undirected edge mean?" |
|
336 bool forward(Edge) const { return true; } |
|
337 |
|
338 /// Opposite node on an edge |
|
339 |
|
340 /// \return the opposite of the given Node on the given Edge |
|
341 /// |
|
342 /// \todo What should we do if given Node and Edge are not incident? |
|
343 Node oppositeNode(Node, UndirEdge) const { return INVALID; } |
|
344 |
|
345 /// First node of the undirected edge. |
|
346 |
|
347 /// \return the first node of the given UndirEdge. |
|
348 /// |
|
349 /// Naturally undirectected edges don't have direction and thus |
|
350 /// don't have source and target node. But we use these two methods |
|
351 /// to query the two endnodes of the edge. The direction of the edge |
|
352 /// which arises this way is called the inherent direction of the |
|
353 /// undirected edge, and is used to define the "forward" direction |
|
354 /// of the directed versions of the edges. |
|
355 /// \sa forward |
|
356 Node source(UndirEdge) const { return INVALID; } |
|
357 |
|
358 /// Second node of the undirected edge. |
|
359 Node target(UndirEdge) const { return INVALID; } |
|
360 |
|
361 /// Source node of the directed edge. |
|
362 Node source(Edge) const { return INVALID; } |
|
363 |
|
364 /// Target node of the directed edge. |
|
365 Node target(Edge) const { return INVALID; } |
|
366 |
|
367 /// First node of the graph |
|
368 |
|
369 /// \note This method is part of so called \ref |
|
370 /// developpers_interface "Developpers' interface", so it shouldn't |
|
371 /// be used in an end-user program. |
|
372 void first(Node&) const {} |
|
373 /// Next node of the graph |
|
374 |
|
375 /// \note This method is part of so called \ref |
|
376 /// developpers_interface "Developpers' interface", so it shouldn't |
|
377 /// be used in an end-user program. |
|
378 void next(Node&) const {} |
|
379 |
|
380 /// First undirected edge of the graph |
|
381 |
|
382 /// \note This method is part of so called \ref |
|
383 /// developpers_interface "Developpers' interface", so it shouldn't |
|
384 /// be used in an end-user program. |
|
385 void first(UndirEdge&) const {} |
|
386 /// Next undirected edge of the graph |
|
387 |
|
388 /// \note This method is part of so called \ref |
|
389 /// developpers_interface "Developpers' interface", so it shouldn't |
|
390 /// be used in an end-user program. |
|
391 void next(UndirEdge&) const {} |
|
392 |
|
393 /// First directed edge of the graph |
|
394 |
|
395 /// \note This method is part of so called \ref |
|
396 /// developpers_interface "Developpers' interface", so it shouldn't |
|
397 /// be used in an end-user program. |
|
398 void first(Edge&) const {} |
|
399 /// Next directed edge of the graph |
|
400 |
|
401 /// \note This method is part of so called \ref |
|
402 /// developpers_interface "Developpers' interface", so it shouldn't |
|
403 /// be used in an end-user program. |
|
404 void next(Edge&) const {} |
|
405 |
|
406 /// First outgoing edge from a given node |
|
407 |
|
408 /// \note This method is part of so called \ref |
|
409 /// developpers_interface "Developpers' interface", so it shouldn't |
|
410 /// be used in an end-user program. |
|
411 void firstOut(Edge&, Node) const {} |
|
412 /// Next outgoing edge to a node |
|
413 |
|
414 /// \note This method is part of so called \ref |
|
415 /// developpers_interface "Developpers' interface", so it shouldn't |
|
416 /// be used in an end-user program. |
|
417 void nextOut(Edge&) const {} |
|
418 |
|
419 /// First incoming edge to a given node |
|
420 |
|
421 /// \note This method is part of so called \ref |
|
422 /// developpers_interface "Developpers' interface", so it shouldn't |
|
423 /// be used in an end-user program. |
|
424 void firstIn(Edge&, Node) const {} |
|
425 /// Next incoming edge to a node |
|
426 |
|
427 /// \note This method is part of so called \ref |
|
428 /// developpers_interface "Developpers' interface", so it shouldn't |
|
429 /// be used in an end-user program. |
|
430 void nextIn(Edge&) const {} |
|
431 |
150 |
432 |
151 template <typename Graph> |
433 template <typename Graph> |
152 struct Constraints { |
434 struct Constraints { |
153 void constraints() { |
435 void constraints() { |
154 checkConcept<BaseIterableUndirGraphConcept, Graph>(); |
436 checkConcept<BaseIterableUndirGraphConcept, Graph>(); |