COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/undir_graph.h @ 1448:0274acee0e35

Last change on this file since 1448:0274acee0e35 was 1448:0274acee0e35, checked in by Alpar Juttner, 15 years ago

UndirTag? added to the graphs

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