COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/undir_graph.h @ 1157:3996d2098090

Last change on this file since 1157:3996d2098090 was 1030:c8a41699e613, checked in by Mihaly Barasz, 15 years ago

Undirected graph documentation and concept refinements.

  • quite a few bug fixes
  • concept::UndirGraph? is almost complete and looks quite good.
File size: 13.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic
4 * C++ optimization library
5 *
6 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
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
30namespace 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 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   
89
90    struct BaseIterableUndirGraphConcept {
91
92      template <typename Graph>
93      struct Constraints {
94
95        typedef typename Graph::UndirEdge UndirEdge;
96        typedef typename Graph::Edge Edge;
97        typedef typename Graph::Node Node;
98
99        void constraints() {
100          checkConcept<BaseIterableGraphComponent, Graph>();
101          checkConcept<GraphItem<>, UndirEdge>();
102          checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
103
104          graph.first(ue);
105          graph.next(ue);
106
107          const_constraints();
108        }
109        void const_constraints() {
110          Node n;
111          n = graph.target(ue);
112          n = graph.source(ue);
113          n = graph.oppositeNode(n0, ue);
114
115          bool b;
116          b = graph.forward(e);
117          ignore_unused_variable_warning(b);
118        }
119
120        Graph graph;
121        Edge e;
122        Node n0;
123        UndirEdge ue;
124      };
125
126    };
127
128
129    struct IterableUndirGraphConcept {
130
131      template <typename Graph>
132      struct Constraints {
133        void constraints() {
134          /// \todo we don't need the iterable component to be base iterable
135          /// Don't we really???
136          //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
137
138          checkConcept<IterableGraphComponent, Graph> ();
139
140          typedef typename Graph::UndirEdge UndirEdge;
141          typedef typename Graph::UndirEdgeIt UndirEdgeIt;
142          typedef typename Graph::IncEdgeIt IncEdgeIt;
143
144          checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
145          checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
146        }
147      };
148
149    };
150
151    struct MappableUndirGraphConcept {
152
153      template <typename Graph>
154      struct Constraints {
155
156        struct Dummy {
157          int value;
158          Dummy() : value(0) {}
159          Dummy(int _v) : value(_v) {}
160        };
161
162        void constraints() {
163          checkConcept<MappableGraphComponent, Graph>();
164
165          typedef typename Graph::template UndirEdgeMap<int> IntMap;
166          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
167            IntMap >();
168
169          typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
170          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
171            BoolMap >();
172
173          typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
174          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
175            DummyMap >();
176        }
177      };
178
179    };
180
181    struct ExtendableUndirGraphConcept {
182
183      template <typename Graph>
184      struct Constraints {
185        void constraints() {
186          node_a = graph.addNode();
187          uedge = graph.addEdge(node_a, node_b);
188        }
189        typename Graph::Node node_a, node_b;
190        typename Graph::UndirEdge uedge;
191        Graph graph;
192      };
193
194    };
195
196    struct ErasableUndirGraphConcept {
197
198      template <typename Graph>
199      struct Constraints {
200        void constraints() {
201          graph.erase(n);
202          graph.erase(e);
203        }
204        Graph graph;
205        typename Graph::Node n;
206        typename Graph::UndirEdge e;
207      };
208
209    };
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
226    class UndirGraph {
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
432
433      template <typename Graph>
434      struct Constraints {
435        void constraints() {
436          checkConcept<BaseIterableUndirGraphConcept, Graph>();
437          checkConcept<IterableUndirGraphConcept, Graph>();
438          checkConcept<MappableUndirGraphConcept, Graph>();
439        }
440      };
441
442    };
443
444    class ExtendableUndirGraph : public UndirGraph {
445    public:
446
447      template <typename Graph>
448      struct Constraints {
449        void constraints() {
450          checkConcept<BaseIterableUndirGraphConcept, Graph>();
451          checkConcept<IterableUndirGraphConcept, Graph>();
452          checkConcept<MappableUndirGraphConcept, Graph>();
453
454          checkConcept<UndirGraph, Graph>();
455          checkConcept<ExtendableUndirGraphConcept, Graph>();
456          checkConcept<ClearableGraphComponent, Graph>();
457        }
458      };
459
460    };
461
462    class ErasableUndirGraph : public ExtendableUndirGraph {
463    public:
464
465      template <typename Graph>
466      struct Constraints {
467        void constraints() {
468          checkConcept<ExtendableUndirGraph, Graph>();
469          checkConcept<ErasableUndirGraphConcept, Graph>();
470        }
471      };
472
473    };
474
475    /// @}
476
477  }
478
479}
480
481#endif
Note: See TracBrowser for help on using the repository browser.