COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/ugraph.h @ 1992:6e1b62d42d94

Last change on this file since 1992:6e1b62d42d94 was 1980:a954b780e3ab, checked in by Balazs Dezso, 18 years ago

Renaming to be convient to the naming of the adaptors
Concept checking of the ugraph adaptors

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