COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/undir_graph.h @ 1624:61cc647dac99

Last change on this file since 1624:61cc647dac99 was 1624:61cc647dac99, checked in by Alpar Juttner, 19 years ago

Several docfices

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