COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/undir_graph.h @ 1620:09feafe81053

Last change on this file since 1620:09feafe81053 was 1620:09feafe81053, checked in by Alpar Juttner, 14 years ago

Start working on UndirGraph? concept clarification and its harmonization with
the directed graph concept.
Not yet done!!!

File size: 17.0 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        ///@param g the graph
318        UndirEdgeIt(const UndirGraph&) { }
319        /// UndirEdge -> UndirEdgeIt conversion
320
321        /// Sets the iterator to the value of the trivial iterator \c e.
322        /// This feature necessitates that each time we
323        /// iterate the edge-set, the iteration order is the same.
324        UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
325        ///Next edge
326       
327        /// Assign the iterator to the next edge.
328        UndirEdgeIt& operator++() { return *this; }
329      };
330
331      /// This iterator goes trough the incident undirected edges of a node.
332
333      /// This iterator goes trough the incident undirected edges
334      /// of a certain node
335      /// of a graph.
336      /// Its usage is quite simple, for example you can compute the
337      /// degree (i.e. count the number
338      /// of incident edges of a node \c n
339      /// in graph \c g of type \c Graph as follows.
340      /// \code
341      /// int count=0;
342      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
343      /// \endcode
344      class IncEdgeIt : public UndirEdge {
345      public:
346        /// Default constructor
347
348        /// @warning The default constructor sets the iterator
349        /// to an undefined value.
350        IncEdgeIt() { }
351        /// Copy constructor.
352
353        /// Copy constructor.
354        ///
355        IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
356        /// Initialize the iterator to be invalid.
357
358        /// Initialize the iterator to be invalid.
359        ///
360        IncEdgeIt(Invalid) { }
361        /// This constructor sets the iterator to first incident edge.
362   
363        /// This constructor set the iterator to the first incident edge of
364        /// the node.
365        ///@param n the node
366        ///@param g the graph
367        IncEdgeIt(const UndirGraph&, const Node&) { }
368        /// UndirEdge -> IncEdgeIt conversion
369
370        /// Sets the iterator to the value of the trivial iterator \c e.
371        /// This feature necessitates that each time we
372        /// iterate the edge-set, the iteration order is the same.
373        IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
374        /// Next incident edge
375
376        /// Assign the iterator to the next incident edge
377        /// of the corresponding node.
378        IncEdgeIt& operator++() { return *this; }
379      };
380
381      /// Read write map of the undirected edges to type \c T.
382
383      /// Reference map of the edges to type \c T.
384      /// \sa Reference
385      /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
386      /// needs some extra attention!
387      template<class T>
388      class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
389      {
390      public:
391
392        ///\e
393        UndirEdgeMap(const UndirGraph&) { }
394        ///\e
395        UndirEdgeMap(const UndirGraph&, T) { }
396        ///Copy constructor
397        UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
398        ///Assignment operator
399        UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
400        // \todo fix this concept   
401      };
402
403      /// Is the Edge oriented "forward"?
404
405      /// Returns whether the given directed edge is same orientation as
406      /// the corresponding undirected edge.
407      ///
408      /// \todo "What does the direction of an undirected edge mean?"
409      bool forward(Edge) const { return true; }
410
411      /// Opposite node on an edge
412
413      /// \return the opposite of the given Node on the given Edge
414      ///
415      /// \todo What should we do if given Node and Edge are not incident?
416      Node oppositeNode(Node, UndirEdge) const { return INVALID; }
417
418      /// First node of the undirected edge.
419
420      /// \return the first node of the given UndirEdge.
421      ///
422      /// Naturally undirectected edges don't have direction and thus
423      /// don't have source and target node. But we use these two methods
424      /// to query the two endnodes of the edge. The direction of the edge
425      /// which arises this way is called the inherent direction of the
426      /// undirected edge, and is used to define the "forward" direction
427      /// of the directed versions of the edges.
428      /// \sa forward
429      Node source(UndirEdge) const { return INVALID; }
430
431      /// Second node of the undirected edge.
432      Node target(UndirEdge) const { return INVALID; }
433
434      /// Source node of the directed edge.
435      Node source(Edge) const { return INVALID; }
436
437      /// Target node of the directed edge.
438      Node target(Edge) const { return INVALID; }
439
440      /// First node of the graph
441
442      /// \note This method is part of so called \ref
443      /// developpers_interface "Developpers' interface", so it shouldn't
444      /// be used in an end-user program.
445      void first(Node&) const {}
446      /// Next node of the graph
447
448      /// \note This method is part of so called \ref
449      /// developpers_interface "Developpers' interface", so it shouldn't
450      /// be used in an end-user program.
451      void next(Node&) const {}
452
453      /// First undirected edge of the graph
454
455      /// \note This method is part of so called \ref
456      /// developpers_interface "Developpers' interface", so it shouldn't
457      /// be used in an end-user program.
458      void first(UndirEdge&) const {}
459      /// Next undirected edge of the graph
460
461      /// \note This method is part of so called \ref
462      /// developpers_interface "Developpers' interface", so it shouldn't
463      /// be used in an end-user program.
464      void next(UndirEdge&) const {}
465
466      /// First directed edge of the graph
467
468      /// \note This method is part of so called \ref
469      /// developpers_interface "Developpers' interface", so it shouldn't
470      /// be used in an end-user program.
471      void first(Edge&) const {}
472      /// Next directed edge of the graph
473
474      /// \note This method is part of so called \ref
475      /// developpers_interface "Developpers' interface", so it shouldn't
476      /// be used in an end-user program.
477      void next(Edge&) const {}
478
479      /// First outgoing edge from a given node
480
481      /// \note This method is part of so called \ref
482      /// developpers_interface "Developpers' interface", so it shouldn't
483      /// be used in an end-user program.
484      void firstOut(Edge&, Node) const {}
485      /// Next outgoing edge to a node
486
487      /// \note This method is part of so called \ref
488      /// developpers_interface "Developpers' interface", so it shouldn't
489      /// be used in an end-user program.
490      void nextOut(Edge&) const {}
491
492      /// First incoming edge to a given node
493
494      /// \note This method is part of so called \ref
495      /// developpers_interface "Developpers' interface", so it shouldn't
496      /// be used in an end-user program.
497      void firstIn(Edge&, Node) const {}
498      /// Next incoming edge to a node
499
500      /// \note This method is part of so called \ref
501      /// developpers_interface "Developpers' interface", so it shouldn't
502      /// be used in an end-user program.
503      void nextIn(Edge&) const {}
504
505
506      /// Base node of the iterator
507      ///
508      /// Returns the base node (the source in this case) of the iterator
509      Node baseNode(OutEdgeIt e) const {
510        return source(e);
511      }
512      /// Running node of the iterator
513      ///
514      /// Returns the running node (the target in this case) of the
515      /// iterator
516      Node runningNode(OutEdgeIt e) const {
517        return target(e);
518      }
519
520      /// Base node of the iterator
521      ///
522      /// Returns the base node (the target in this case) of the iterator
523      Node baseNode(InEdgeIt e) const {
524        return target(e);
525      }
526      /// Running node of the iterator
527      ///
528      /// Returns the running node (the source in this case) of the
529      /// iterator
530      Node runningNode(InEdgeIt e) const {
531        return source(e);
532      }
533
534      /// Base node of the iterator
535      ///
536      /// Returns the base node of the iterator
537      Node baseNode(IncEdgeIt) const {
538        return INVALID;
539      }
540      /// Running node of the iterator
541      ///
542      /// Returns the running node of the iterator
543      Node runningNode(IncEdgeIt) const {
544        return INVALID;
545      }
546
547
548      template <typename Graph>
549      struct Constraints {
550        void constraints() {
551          checkConcept<BaseIterableUndirGraphConcept, Graph>();
552          checkConcept<IterableUndirGraphConcept, Graph>();
553          checkConcept<MappableUndirGraphConcept, Graph>();
554        }
555      };
556
557    };
558
559    class ExtendableUndirGraph : public UndirGraph {
560    public:
561
562      template <typename Graph>
563      struct Constraints {
564        void constraints() {
565          checkConcept<BaseIterableUndirGraphConcept, Graph>();
566          checkConcept<IterableUndirGraphConcept, Graph>();
567          checkConcept<MappableUndirGraphConcept, Graph>();
568
569          checkConcept<UndirGraph, Graph>();
570          checkConcept<ExtendableUndirGraphConcept, Graph>();
571          checkConcept<ClearableGraphComponent, Graph>();
572        }
573      };
574
575    };
576
577    class ErasableUndirGraph : public ExtendableUndirGraph {
578    public:
579
580      template <typename Graph>
581      struct Constraints {
582        void constraints() {
583          checkConcept<ExtendableUndirGraph, Graph>();
584          checkConcept<ErasableUndirGraphConcept, Graph>();
585        }
586      };
587
588    };
589
590    /// @}
591
592  }
593
594}
595
596#endif
Note: See TracBrowser for help on using the repository browser.