COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/undir_graph.h @ 1359:1581f961cfaa

Last change on this file since 1359:1581f961cfaa was 1359:1581f961cfaa, checked in by Alpar Juttner, 19 years ago

Correct the english name of EGRES.

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