Undirected graph documentation and concept refinements.
* quite a few bug fixes
* concept::UndirGraph is almost complete and looks quite good.
3 * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic
4 * C++ optimization library
6 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
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.
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
20 ///\ingroup graph_concepts
22 ///\brief Undirected graphs and components of.
25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
26 #define LEMON_CONCEPT_UNDIR_GRAPH_H
28 #include <lemon/concept/graph_component.h>
33 /// \addtogroup graph_concepts
37 /// Skeleton class which describes an edge with direction in \ref
38 /// UndirGraph "undirected graph".
39 template <typename UndirEdge>
40 class UndirGraphEdge : public UndirEdge {
47 UndirGraphEdge(const UndirGraphEdge&) {}
50 UndirGraphEdge(Invalid) {}
52 /// \brief Constructs a directed version of an undirected edge
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);
63 UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
66 bool operator==(UndirGraphEdge) const { return true; }
68 bool operator!=(UndirGraphEdge) const { return false; }
71 bool operator<(UndirGraphEdge) const { return false; }
73 template <typename Edge>
76 /// \bug This should be is_base_and_derived ...
79 Edge forward(ue, true);
80 Edge backward(ue, false);
82 ignore_unused_variable_warning(forward);
83 ignore_unused_variable_warning(backward);
90 struct BaseIterableUndirGraphConcept {
92 template <typename Graph>
95 typedef typename Graph::UndirEdge UndirEdge;
96 typedef typename Graph::Edge Edge;
97 typedef typename Graph::Node Node;
100 checkConcept<BaseIterableGraphComponent, Graph>();
101 checkConcept<GraphItem<>, UndirEdge>();
102 checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
109 void const_constraints() {
111 n = graph.target(ue);
112 n = graph.source(ue);
113 n = graph.oppositeNode(n0, ue);
116 b = graph.forward(e);
117 ignore_unused_variable_warning(b);
129 struct IterableUndirGraphConcept {
131 template <typename Graph>
134 /// \todo we don't need the iterable component to be base iterable
135 /// Don't we really???
136 //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
138 checkConcept<IterableGraphComponent, Graph> ();
140 typedef typename Graph::UndirEdge UndirEdge;
141 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
142 typedef typename Graph::IncEdgeIt IncEdgeIt;
144 checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
145 checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
151 struct MappableUndirGraphConcept {
153 template <typename Graph>
158 Dummy() : value(0) {}
159 Dummy(int _v) : value(_v) {}
163 checkConcept<MappableGraphComponent, Graph>();
165 typedef typename Graph::template UndirEdgeMap<int> IntMap;
166 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
169 typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
170 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
173 typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
174 checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
181 struct ExtendableUndirGraphConcept {
183 template <typename Graph>
186 node_a = graph.addNode();
187 uedge = graph.addEdge(node_a, node_b);
189 typename Graph::Node node_a, node_b;
190 typename Graph::UndirEdge uedge;
196 struct ErasableUndirGraphConcept {
198 template <typename Graph>
205 typename Graph::Node n;
206 typename Graph::UndirEdge e;
211 /// Class describing the concept of Undirected Graphs.
213 /// This class describes the common interface of all Undirected
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.
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.
229 /// Type describing a node in the graph
230 typedef GraphNode Node;
232 /// Type describing an undirected edge
233 typedef GraphItem<'u'> UndirEdge;
235 /// Type describing an UndirEdge with direction
237 typedef UndirGraphEdge<UndirEdge> Edge;
239 typedef UndirGraphEdge Edge;
242 /// Iterator type which iterates over all nodes
244 typedef GraphIterator<UndirGraph, Node> NodeIt;
246 typedef GraphIterator NodeIt;
249 /// Iterator type which iterates over all undirected edges
251 typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
253 typedef GraphIterator UndirEdgeIt;
256 /// Iterator type which iterates over all directed edges.
258 /// Iterator type which iterates over all edges (each undirected
259 /// edge occurs twice with both directions.
261 typedef GraphIterator<UndirGraph, Edge> EdgeIt;
263 typedef GraphIterator EdgeIt;
267 /// Iterator of undirected edges incident to a node
269 typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
271 typedef GraphIncIterator IncEdgeIt;
274 /// Iterator of edges incoming to a node
276 typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
278 typedef GraphIncIterator InEdgeIt;
281 /// Iterator of edges outgoing from a node
283 typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
285 typedef GraphIncIterator OutEdgeIt;
290 typedef GraphMap NodeMap<T>;
293 /// UndirEdgeMap template
295 typedef GraphMap UndirEdgeMap<T>;
300 typedef GraphMap EdgeMap<T>;
303 template <typename T>
304 class NodeMap : public GraphMap<UndirGraph, Node, T> {
305 typedef GraphMap<UndirGraph, Node, T> Parent;
308 explicit NodeMap(const UndirGraph &g) : Parent(g) {}
309 NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
312 template <typename T>
313 class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
314 typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
317 explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
318 UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
321 template <typename T>
322 class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
323 typedef GraphMap<UndirGraph, Edge, T> Parent;
326 explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
327 EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
330 /// Is the Edge oriented "forward"?
332 /// Returns whether the given directed edge is same orientation as
333 /// the corresponding undirected edge.
335 /// \todo "What does the direction of an undirected edge mean?"
336 bool forward(Edge) const { return true; }
338 /// Opposite node on an edge
340 /// \return the opposite of the given Node on the given Edge
342 /// \todo What should we do if given Node and Edge are not incident?
343 Node oppositeNode(Node, UndirEdge) const { return INVALID; }
345 /// First node of the undirected edge.
347 /// \return the first node of the given UndirEdge.
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.
356 Node source(UndirEdge) const { return INVALID; }
358 /// Second node of the undirected edge.
359 Node target(UndirEdge) const { return INVALID; }
361 /// Source node of the directed edge.
362 Node source(Edge) const { return INVALID; }
364 /// Target node of the directed edge.
365 Node target(Edge) const { return INVALID; }
367 /// First node of the graph
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
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 {}
380 /// First undirected edge of the graph
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
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 {}
393 /// First directed edge of the graph
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
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 {}
406 /// First outgoing edge from a given node
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
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 {}
419 /// First incoming edge to a given node
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
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 {}
433 template <typename Graph>
436 checkConcept<BaseIterableUndirGraphConcept, Graph>();
437 checkConcept<IterableUndirGraphConcept, Graph>();
438 checkConcept<MappableUndirGraphConcept, Graph>();
444 class ExtendableUndirGraph : public UndirGraph {
447 template <typename Graph>
450 checkConcept<BaseIterableUndirGraphConcept, Graph>();
451 checkConcept<IterableUndirGraphConcept, Graph>();
452 checkConcept<MappableUndirGraphConcept, Graph>();
454 checkConcept<UndirGraph, Graph>();
455 checkConcept<ExtendableUndirGraphConcept, Graph>();
456 checkConcept<ClearableGraphComponent, Graph>();
462 class ErasableUndirGraph : public ExtendableUndirGraph {
465 template <typename Graph>
468 checkConcept<ExtendableUndirGraph, Graph>();
469 checkConcept<ErasableUndirGraphConcept, Graph>();