COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/undir_graph.h @ 1875:98698b69a902

Last change on this file since 1875:98698b69a902 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

File size: 30.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) 2006 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.direction(e);
123          Edge e = graph.direct(UndirEdge(), true);
124          e = graph.direct(UndirEdge(), n);
125 
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    /// \addtogroup graph_concepts
221    /// @{
222
223
224    /// Class describing the concept of Undirected Graphs.
225
226    /// This class describes the common interface of all Undirected
227    /// Graphs.
228    ///
229    /// As all concept describing classes it provides only interface
230    /// without any sensible implementation. So any algorithm for
231    /// undirected graph should compile with this class, but it will not
232    /// run properly, of couse.
233    ///
234    /// In LEMON undirected graphs also fulfill the concept of directed
235    /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
236    /// explanation of this and more see also the page \ref undir_graphs,
237    /// a tutorial about undirected graphs.
238    ///
239    /// You can assume that all undirected graph can be handled
240    /// as a static directed graph. This way it is fully conform
241    /// to the StaticGraph concept.
242
243    class UndirGraph {
244    public:
245      ///\e
246
247      ///\todo undocumented
248      ///
249      typedef True UndirTag;
250
251      /// \brief The base type of node iterators,
252      /// or in other words, the trivial node iterator.
253      ///
254      /// This is the base type of each node iterator,
255      /// thus each kind of node iterator converts to this.
256      /// More precisely each kind of node iterator should be inherited
257      /// from the trivial node iterator.
258      class Node {
259      public:
260        /// Default constructor
261
262        /// @warning The default constructor sets the iterator
263        /// to an undefined value.
264        Node() { }
265        /// Copy constructor.
266
267        /// Copy constructor.
268        ///
269        Node(const Node&) { }
270
271        /// Invalid constructor \& conversion.
272
273        /// This constructor initializes the iterator to be invalid.
274        /// \sa Invalid for more details.
275        Node(Invalid) { }
276        /// Equality operator
277
278        /// Two iterators are equal if and only if they point to the
279        /// same object or both are invalid.
280        bool operator==(Node) const { return true; }
281
282        /// Inequality operator
283       
284        /// \sa operator==(Node n)
285        ///
286        bool operator!=(Node) const { return true; }
287
288        /// Artificial ordering operator.
289       
290        /// To allow the use of graph descriptors as key type in std::map or
291        /// similar associative container we require this.
292        ///
293        /// \note This operator only have to define some strict ordering of
294        /// the items; this order has nothing to do with the iteration
295        /// ordering of the items.
296        ///
297        /// \bug This is a technical requirement. Do we really need this?
298        bool operator<(Node) const { return false; }
299
300      };
301   
302      /// This iterator goes through each node.
303
304      /// This iterator goes through each node.
305      /// Its usage is quite simple, for example you can count the number
306      /// of nodes in graph \c g of type \c Graph like this:
307      /// \code
308      /// int count=0;
309      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
310      /// \endcode
311      class NodeIt : public Node {
312      public:
313        /// Default constructor
314
315        /// @warning The default constructor sets the iterator
316        /// to an undefined value.
317        NodeIt() { }
318        /// Copy constructor.
319       
320        /// Copy constructor.
321        ///
322        NodeIt(const NodeIt& n) : Node(n) { }
323        /// Invalid constructor \& conversion.
324
325        /// Initialize the iterator to be invalid.
326        /// \sa Invalid for more details.
327        NodeIt(Invalid) { }
328        /// Sets the iterator to the first node.
329
330        /// Sets the iterator to the first node of \c g.
331        ///
332        NodeIt(const UndirGraph&) { }
333        /// Node -> NodeIt conversion.
334
335        /// Sets the iterator to the node of \c the graph pointed by
336        /// the trivial iterator.
337        /// This feature necessitates that each time we
338        /// iterate the edge-set, the iteration order is the same.
339        NodeIt(const UndirGraph&, const Node&) { }
340        /// Next node.
341
342        /// Assign the iterator to the next node.
343        ///
344        NodeIt& operator++() { return *this; }
345      };
346   
347   
348      /// The base type of the undirected edge iterators.
349
350      /// The base type of the undirected edge iterators.
351      ///
352      class UndirEdge {
353      public:
354        /// Default constructor
355
356        /// @warning The default constructor sets the iterator
357        /// to an undefined value.
358        UndirEdge() { }
359        /// Copy constructor.
360
361        /// Copy constructor.
362        ///
363        UndirEdge(const UndirEdge&) { }
364        /// Initialize the iterator to be invalid.
365
366        /// Initialize the iterator to be invalid.
367        ///
368        UndirEdge(Invalid) { }
369        /// Equality operator
370
371        /// Two iterators are equal if and only if they point to the
372        /// same object or both are invalid.
373        bool operator==(UndirEdge) const { return true; }
374        /// Inequality operator
375
376        /// \sa operator==(UndirEdge n)
377        ///
378        bool operator!=(UndirEdge) const { return true; }
379
380        /// Artificial ordering operator.
381       
382        /// To allow the use of graph descriptors as key type in std::map or
383        /// similar associative container we require this.
384        ///
385        /// \note This operator only have to define some strict ordering of
386        /// the items; this order has nothing to do with the iteration
387        /// ordering of the items.
388        ///
389        /// \bug This is a technical requirement. Do we really need this?
390        bool operator<(UndirEdge) const { return false; }
391      };
392
393      /// This iterator goes through each undirected edge.
394
395      /// This iterator goes through each undirected edge of a graph.
396      /// Its usage is quite simple, for example you can count the number
397      /// of undirected edges in a graph \c g of type \c Graph as follows:
398      /// \code
399      /// int count=0;
400      /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
401      /// \endcode
402      class UndirEdgeIt : public UndirEdge {
403      public:
404        /// Default constructor
405
406        /// @warning The default constructor sets the iterator
407        /// to an undefined value.
408        UndirEdgeIt() { }
409        /// Copy constructor.
410
411        /// Copy constructor.
412        ///
413        UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
414        /// Initialize the iterator to be invalid.
415
416        /// Initialize the iterator to be invalid.
417        ///
418        UndirEdgeIt(Invalid) { }
419        /// This constructor sets the iterator to the first undirected edge.
420   
421        /// This constructor sets the iterator to the first undirected edge.
422        UndirEdgeIt(const UndirGraph&) { }
423        /// UndirEdge -> UndirEdgeIt conversion
424
425        /// Sets the iterator to the value of the trivial iterator.
426        /// This feature necessitates that each time we
427        /// iterate the undirected edge-set, the iteration order is the
428        /// same.
429        UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
430        /// Next undirected edge
431       
432        /// Assign the iterator to the next undirected edge.
433        UndirEdgeIt& operator++() { return *this; }
434      };
435
436      /// \brief This iterator goes trough the incident undirected
437      /// edges of a node.
438      ///
439      /// This iterator goes trough the incident undirected edges
440      /// of a certain node
441      /// of a graph.
442      /// Its usage is quite simple, for example you can compute the
443      /// degree (i.e. count the number
444      /// of incident edges of a node \c n
445      /// in graph \c g of type \c Graph as follows.
446      /// \code
447      /// int count=0;
448      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
449      /// \endcode
450      class IncEdgeIt : public UndirEdge {
451      public:
452        /// Default constructor
453
454        /// @warning The default constructor sets the iterator
455        /// to an undefined value.
456        IncEdgeIt() { }
457        /// Copy constructor.
458
459        /// Copy constructor.
460        ///
461        IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
462        /// Initialize the iterator to be invalid.
463
464        /// Initialize the iterator to be invalid.
465        ///
466        IncEdgeIt(Invalid) { }
467        /// This constructor sets the iterator to first incident edge.
468   
469        /// This constructor set the iterator to the first incident edge of
470        /// the node.
471        IncEdgeIt(const UndirGraph&, const Node&) { }
472        /// UndirEdge -> IncEdgeIt conversion
473
474        /// Sets the iterator to the value of the trivial iterator \c e.
475        /// This feature necessitates that each time we
476        /// iterate the edge-set, the iteration order is the same.
477        IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
478        /// Next incident edge
479
480        /// Assign the iterator to the next incident edge
481        /// of the corresponding node.
482        IncEdgeIt& operator++() { return *this; }
483      };
484
485      /// The directed edge type.
486
487      /// The directed edge type. It can be converted to the
488      /// undirected edge.
489      class Edge : public UndirEdge {
490      public:
491        /// Default constructor
492
493        /// @warning The default constructor sets the iterator
494        /// to an undefined value.
495        Edge() { }
496        /// Copy constructor.
497
498        /// Copy constructor.
499        ///
500        Edge(const Edge& e) : UndirEdge(e) { }
501        /// Initialize the iterator to be invalid.
502
503        /// Initialize the iterator to be invalid.
504        ///
505        Edge(Invalid) { }
506        /// Equality operator
507
508        /// Two iterators are equal if and only if they point to the
509        /// same object or both are invalid.
510        bool operator==(Edge) const { return true; }
511        /// Inequality operator
512
513        /// \sa operator==(Edge n)
514        ///
515        bool operator!=(Edge) const { return true; }
516
517        /// Artificial ordering operator.
518       
519        /// To allow the use of graph descriptors as key type in std::map or
520        /// similar associative container we require this.
521        ///
522        /// \note This operator only have to define some strict ordering of
523        /// the items; this order has nothing to do with the iteration
524        /// ordering of the items.
525        ///
526        /// \bug This is a technical requirement. Do we really need this?
527        bool operator<(Edge) const { return false; }
528       
529      };
530      /// This iterator goes through each directed edge.
531
532      /// This iterator goes through each edge of a graph.
533      /// Its usage is quite simple, for example you can count the number
534      /// of edges in a graph \c g of type \c Graph as follows:
535      /// \code
536      /// int count=0;
537      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
538      /// \endcode
539      class EdgeIt : public Edge {
540      public:
541        /// Default constructor
542
543        /// @warning The default constructor sets the iterator
544        /// to an undefined value.
545        EdgeIt() { }
546        /// Copy constructor.
547
548        /// Copy constructor.
549        ///
550        EdgeIt(const EdgeIt& e) : Edge(e) { }
551        /// Initialize the iterator to be invalid.
552
553        /// Initialize the iterator to be invalid.
554        ///
555        EdgeIt(Invalid) { }
556        /// This constructor sets the iterator to the first edge.
557   
558        /// This constructor sets the iterator to the first edge of \c g.
559        ///@param g the graph
560        EdgeIt(const UndirGraph &g) { ignore_unused_variable_warning(g); }
561        /// Edge -> EdgeIt conversion
562
563        /// Sets the iterator to the value of the trivial iterator \c e.
564        /// This feature necessitates that each time we
565        /// iterate the edge-set, the iteration order is the same.
566        EdgeIt(const UndirGraph&, const Edge&) { }
567        ///Next edge
568       
569        /// Assign the iterator to the next edge.
570        EdgeIt& operator++() { return *this; }
571      };
572   
573      /// This iterator goes trough the outgoing directed edges of a node.
574
575      /// This iterator goes trough the \e outgoing edges of a certain node
576      /// of a graph.
577      /// Its usage is quite simple, for example you can count the number
578      /// of outgoing edges of a node \c n
579      /// in graph \c g of type \c Graph as follows.
580      /// \code
581      /// int count=0;
582      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
583      /// \endcode
584   
585      class OutEdgeIt : public Edge {
586      public:
587        /// Default constructor
588
589        /// @warning The default constructor sets the iterator
590        /// to an undefined value.
591        OutEdgeIt() { }
592        /// Copy constructor.
593
594        /// Copy constructor.
595        ///
596        OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
597        /// Initialize the iterator to be invalid.
598
599        /// Initialize the iterator to be invalid.
600        ///
601        OutEdgeIt(Invalid) { }
602        /// This constructor sets the iterator to the first outgoing edge.
603   
604        /// This constructor sets the iterator to the first outgoing edge of
605        /// the node.
606        ///@param n the node
607        ///@param g the graph
608        OutEdgeIt(const UndirGraph& n, const Node& g) {
609          ignore_unused_variable_warning(n);
610          ignore_unused_variable_warning(g);
611        }
612        /// Edge -> OutEdgeIt conversion
613
614        /// Sets the iterator to the value of the trivial iterator.
615        /// This feature necessitates that each time we
616        /// iterate the edge-set, the iteration order is the same.
617        OutEdgeIt(const UndirGraph&, const Edge&) { }
618        ///Next outgoing edge
619       
620        /// Assign the iterator to the next
621        /// outgoing edge of the corresponding node.
622        OutEdgeIt& operator++() { return *this; }
623      };
624
625      /// This iterator goes trough the incoming directed edges of a node.
626
627      /// This iterator goes trough the \e incoming edges of a certain node
628      /// of a graph.
629      /// Its usage is quite simple, for example you can count the number
630      /// of outgoing edges of a node \c n
631      /// in graph \c g of type \c Graph as follows.
632      /// \code
633      /// int count=0;
634      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
635      /// \endcode
636
637      class InEdgeIt : public Edge {
638      public:
639        /// Default constructor
640
641        /// @warning The default constructor sets the iterator
642        /// to an undefined value.
643        InEdgeIt() { }
644        /// Copy constructor.
645
646        /// Copy constructor.
647        ///
648        InEdgeIt(const InEdgeIt& e) : Edge(e) { }
649        /// Initialize the iterator to be invalid.
650
651        /// Initialize the iterator to be invalid.
652        ///
653        InEdgeIt(Invalid) { }
654        /// This constructor sets the iterator to first incoming edge.
655   
656        /// This constructor set the iterator to the first incoming edge of
657        /// the node.
658        ///@param n the node
659        ///@param g the graph
660        InEdgeIt(const UndirGraph& g, const Node& n) {
661          ignore_unused_variable_warning(n);
662          ignore_unused_variable_warning(g);
663        }
664        /// Edge -> InEdgeIt conversion
665
666        /// Sets the iterator to the value of the trivial iterator \c e.
667        /// This feature necessitates that each time we
668        /// iterate the edge-set, the iteration order is the same.
669        InEdgeIt(const UndirGraph&, const Edge&) { }
670        /// Next incoming edge
671
672        /// Assign the iterator to the next inedge of the corresponding node.
673        ///
674        InEdgeIt& operator++() { return *this; }
675      };
676
677      /// \brief Read write map of the nodes to type \c T.
678      ///
679      /// ReadWrite map of the nodes to type \c T.
680      /// \sa Reference
681      /// \warning Making maps that can handle bool type (NodeMap<bool>)
682      /// needs some extra attention!
683      /// \todo Wrong documentation
684      template<class T>
685      class NodeMap : public ReadWriteMap< Node, T >
686      {
687      public:
688
689        ///\e
690        NodeMap(const UndirGraph&) { }
691        ///\e
692        NodeMap(const UndirGraph&, T) { }
693
694        ///Copy constructor
695        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
696        ///Assignment operator
697        NodeMap& operator=(const NodeMap&) { return *this; }
698        // \todo fix this concept
699      };
700
701      /// \brief Read write map of the directed edges to type \c T.
702      ///
703      /// Reference map of the directed edges to type \c T.
704      /// \sa Reference
705      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
706      /// needs some extra attention!
707      /// \todo Wrong documentation
708      template<class T>
709      class EdgeMap : public ReadWriteMap<Edge,T>
710      {
711      public:
712
713        ///\e
714        EdgeMap(const UndirGraph&) { }
715        ///\e
716        EdgeMap(const UndirGraph&, T) { }
717        ///Copy constructor
718        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
719        ///Assignment operator
720        EdgeMap& operator=(const EdgeMap&) { return *this; }
721        // \todo fix this concept   
722      };
723
724      /// Read write map of the undirected edges to type \c T.
725
726      /// Reference map of the edges to type \c T.
727      /// \sa Reference
728      /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
729      /// needs some extra attention!
730      /// \todo Wrong documentation
731      template<class T>
732      class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
733      {
734      public:
735
736        ///\e
737        UndirEdgeMap(const UndirGraph&) { }
738        ///\e
739        UndirEdgeMap(const UndirGraph&, T) { }
740        ///Copy constructor
741        UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}
742        ///Assignment operator
743        UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
744        // \todo fix this concept   
745      };
746
747      /// \brief Direct the given undirected edge.
748      ///
749      /// Direct the given undirected edge. The returned edge source
750      /// will be the given edge.
751      Edge direct(const UndirEdge&, const Node&) const {
752        return INVALID;
753      }
754
755      /// \brief Direct the given undirected edge.
756      ///
757      /// Direct the given undirected edge. The returned edge source
758      /// will be the source of the undirected edge if the given bool
759      /// is true.
760      Edge direct(const UndirEdge&, bool) const {
761        return INVALID;
762      }
763
764      /// \brief Returns true if the edge has default orientation.
765      ///
766      /// Returns whether the given directed edge is same orientation as
767      /// the corresponding undirected edge.
768      bool direction(Edge) const { return true; }
769
770      /// \brief Returns the opposite directed edge.
771      ///
772      /// Returns the opposite directed edge.
773      Edge oppositeEdge(Edge) const { return INVALID; }
774
775      /// \brief Opposite node on an edge
776      ///
777      /// \return the opposite of the given Node on the given Edge
778      Node oppositeNode(Node, UndirEdge) const { return INVALID; }
779
780      /// \brief First node of the undirected edge.
781      ///
782      /// \return the first node of the given UndirEdge.
783      ///
784      /// Naturally undirectected edges don't have direction and thus
785      /// don't have source and target node. But we use these two methods
786      /// to query the two endnodes of the edge. The direction of the edge
787      /// which arises this way is called the inherent direction of the
788      /// undirected edge, and is used to define the "default" direction
789      /// of the directed versions of the edges.
790      /// \sa direction
791      Node source(UndirEdge) const { return INVALID; }
792
793      /// \brief Second node of the undirected edge.
794      Node target(UndirEdge) const { return INVALID; }
795
796      /// \brief Source node of the directed edge.
797      Node source(Edge) const { return INVALID; }
798
799      /// \brief Target node of the directed edge.
800      Node target(Edge) const { return INVALID; }
801
802//       /// \brief First node of the graph
803//       ///
804//       /// \note This method is part of so called \ref
805//       /// developpers_interface "Developpers' interface", so it shouldn't
806//       /// be used in an end-user program.
807      void first(Node&) const {}
808//       /// \brief Next node of the graph
809//       ///
810//       /// \note This method is part of so called \ref
811//       /// developpers_interface "Developpers' interface", so it shouldn't
812//       /// be used in an end-user program.
813      void next(Node&) const {}
814
815//       /// \brief First undirected edge of the graph
816//       ///
817//       /// \note This method is part of so called \ref
818//       /// developpers_interface "Developpers' interface", so it shouldn't
819//       /// be used in an end-user program.
820      void first(UndirEdge&) const {}
821//       /// \brief Next undirected edge of the graph
822//       ///
823//       /// \note This method is part of so called \ref
824//       /// developpers_interface "Developpers' interface", so it shouldn't
825//       /// be used in an end-user program.
826      void next(UndirEdge&) const {}
827
828//       /// \brief First directed edge of the graph
829//       ///
830//       /// \note This method is part of so called \ref
831//       /// developpers_interface "Developpers' interface", so it shouldn't
832//       /// be used in an end-user program.
833      void first(Edge&) const {}
834//       /// \brief Next directed edge of the graph
835//       ///
836//       /// \note This method is part of so called \ref
837//       /// developpers_interface "Developpers' interface", so it shouldn't
838//       /// be used in an end-user program.
839      void next(Edge&) const {}
840
841//       /// \brief First outgoing edge from a given node
842//       ///
843//       /// \note This method is part of so called \ref
844//       /// developpers_interface "Developpers' interface", so it shouldn't
845//       /// be used in an end-user program.
846      void firstOut(Edge&, Node) const {}
847//       /// \brief Next outgoing edge to a node
848//       ///
849//       /// \note This method is part of so called \ref
850//       /// developpers_interface "Developpers' interface", so it shouldn't
851//       /// be used in an end-user program.
852      void nextOut(Edge&) const {}
853
854//       /// \brief First incoming edge to a given node
855//       ///
856//       /// \note This method is part of so called \ref
857//       /// developpers_interface "Developpers' interface", so it shouldn't
858//       /// be used in an end-user program.
859      void firstIn(Edge&, Node) const {}
860//       /// \brief Next incoming edge to a node
861//       ///
862//       /// \note This method is part of so called \ref
863//       /// developpers_interface "Developpers' interface", so it shouldn't
864//       /// be used in an end-user program.
865      void nextIn(Edge&) const {}
866
867
868      /// \brief Base node of the iterator
869      ///
870      /// Returns the base node (the source in this case) of the iterator
871      Node baseNode(OutEdgeIt e) const {
872        return source(e);
873      }
874      /// \brief Running node of the iterator
875      ///
876      /// Returns the running node (the target in this case) of the
877      /// iterator
878      Node runningNode(OutEdgeIt e) const {
879        return target(e);
880      }
881
882      /// \brief Base node of the iterator
883      ///
884      /// Returns the base node (the target in this case) of the iterator
885      Node baseNode(InEdgeIt e) const {
886        return target(e);
887      }
888      /// \brief Running node of the iterator
889      ///
890      /// Returns the running node (the source in this case) of the
891      /// iterator
892      Node runningNode(InEdgeIt e) const {
893        return source(e);
894      }
895
896      /// \brief Base node of the iterator
897      ///
898      /// Returns the base node of the iterator
899      Node baseNode(IncEdgeIt) const {
900        return INVALID;
901      }
902     
903      /// \brief Running node of the iterator
904      ///
905      /// Returns the running node of the iterator
906      Node runningNode(IncEdgeIt) const {
907        return INVALID;
908      }
909
910      template <typename Graph>
911      struct Constraints {
912        void constraints() {
913          checkConcept<BaseIterableUndirGraphConcept, Graph>();
914          checkConcept<IterableUndirGraphConcept, Graph>();
915          checkConcept<MappableUndirGraphConcept, Graph>();
916        }
917      };
918
919    };
920
921    /// \brief An empty non-static undirected graph class.
922    ///   
923    /// This class provides everything that \ref UndirGraph does.
924    /// Additionally it enables building graphs from scratch.
925    class ExtendableUndirGraph : public UndirGraph {
926    public:
927     
928      /// \brief Add a new node to the graph.
929      ///
930      /// Add a new node to the graph.
931      /// \return the new node.
932      Node addNode();
933
934      /// \brief Add a new undirected edge to the graph.
935      ///
936      /// Add a new undirected edge to the graph.
937      /// \return the new edge.
938      UndirEdge addEdge(const Node& from, const Node& to);
939
940      /// \brief Resets the graph.
941      ///
942      /// This function deletes all undirected edges and nodes of the graph.
943      /// It also frees the memory allocated to store them.
944      void clear() { }
945
946      template <typename Graph>
947      struct Constraints {
948        void constraints() {
949          checkConcept<BaseIterableUndirGraphConcept, Graph>();
950          checkConcept<IterableUndirGraphConcept, Graph>();
951          checkConcept<MappableUndirGraphConcept, Graph>();
952
953          checkConcept<UndirGraph, Graph>();
954          checkConcept<ExtendableUndirGraphConcept, Graph>();
955          checkConcept<ClearableGraphComponent, Graph>();
956        }
957      };
958
959    };
960
961    /// \brief An empty erasable undirected graph class.
962    ///
963    /// This class is an extension of \ref ExtendableUndirGraph. It makes it
964    /// possible to erase undirected edges or nodes.
965    class ErasableUndirGraph : public ExtendableUndirGraph {
966    public:
967
968      /// \brief Deletes a node.
969      ///
970      /// Deletes a node.
971      ///
972      void erase(Node) { }
973      /// \brief Deletes an undirected edge.
974      ///
975      /// Deletes an undirected edge.
976      ///
977      void erase(UndirEdge) { }
978
979      template <typename Graph>
980      struct Constraints {
981        void constraints() {
982          checkConcept<ExtendableUndirGraph, Graph>();
983          checkConcept<ErasableUndirGraphConcept, Graph>();
984        }
985      };
986
987    };
988
989    /// @}
990
991  }
992
993}
994
995#endif
Note: See TracBrowser for help on using the repository browser.