COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/ugraph.h @ 2021:11455e986b95

Last change on this file since 2021:11455e986b95 was 2021:11455e986b95, checked in by Balazs Dezso, 14 years ago

IncEdgeIt? goes through on loop edges twice.

File size: 30.0 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/bits/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 of a graph. You should assume that the
440      /// loop edges will be iterated twice.
441      ///
442      /// Its usage is quite simple, for example you can compute the
443      /// degree (i.e. count the number of incident edges of a node \c n
444      /// in graph \c g of type \c Graph as follows.
445      ///
446      ///\code
447      /// int count=0;
448      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
449      ///\endcode
450      class IncEdgeIt : public UEdge {
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) : UEdge(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 UGraph&, const Node&) { }
472        /// UEdge -> 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 UGraph&, const UEdge&) { }
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 UEdge {
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) : UEdge(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 UGraph &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 UGraph&, 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 UGraph& 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 UGraph&, 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 UGraph& 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 UGraph&, 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 UGraph&) { }
691        ///\e
692        NodeMap(const UGraph&, 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 UGraph&) { }
715        ///\e
716        EdgeMap(const UGraph&, 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 (UEdgeMap<bool>)
729      /// needs some extra attention!
730      /// \todo Wrong documentation
731      template<class T>
732      class UEdgeMap : public ReadWriteMap<UEdge,T>
733      {
734      public:
735
736        ///\e
737        UEdgeMap(const UGraph&) { }
738        ///\e
739        UEdgeMap(const UGraph&, T) { }
740        ///Copy constructor
741        UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
742        ///Assignment operator
743        UEdgeMap &operator=(const UEdgeMap&) { 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 UEdge&, 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 UEdge&, 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, UEdge) const { return INVALID; }
779
780      /// \brief First node of the undirected edge.
781      ///
782      /// \return the first node of the given UEdge.
783      ///
784      /// Naturally uectected 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(UEdge) const { return INVALID; }
792
793      /// \brief Second node of the undirected edge.
794      Node target(UEdge) 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(UEdge&) 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(UEdge&) 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      void firstInc(UEdge &, bool &, const Node &) const {}
869
870      void nextInc(UEdge &, bool &) const {}
871
872      /// \brief Base node of the iterator
873      ///
874      /// Returns the base node (the source in this case) of the iterator
875      Node baseNode(OutEdgeIt e) const {
876        return source(e);
877      }
878      /// \brief Running node of the iterator
879      ///
880      /// Returns the running node (the target in this case) of the
881      /// iterator
882      Node runningNode(OutEdgeIt e) const {
883        return target(e);
884      }
885
886      /// \brief Base node of the iterator
887      ///
888      /// Returns the base node (the target in this case) of the iterator
889      Node baseNode(InEdgeIt e) const {
890        return target(e);
891      }
892      /// \brief Running node of the iterator
893      ///
894      /// Returns the running node (the source in this case) of the
895      /// iterator
896      Node runningNode(InEdgeIt e) const {
897        return source(e);
898      }
899
900      /// \brief Base node of the iterator
901      ///
902      /// Returns the base node of the iterator
903      Node baseNode(IncEdgeIt) const {
904        return INVALID;
905      }
906     
907      /// \brief Running node of the iterator
908      ///
909      /// Returns the running node of the iterator
910      Node runningNode(IncEdgeIt) const {
911        return INVALID;
912      }
913
914      template <typename Graph>
915      struct Constraints {
916        void constraints() {
917          checkConcept<BaseIterableUGraphConcept, Graph>();
918          checkConcept<IterableUGraphConcept, Graph>();
919          checkConcept<MappableUGraphConcept, Graph>();
920        }
921      };
922
923    };
924
925    /// \brief An empty non-static undirected graph class.
926    ///   
927    /// This class provides everything that \ref UGraph does.
928    /// Additionally it enables building graphs from scratch.
929    class ExtendableUGraph : public UGraph {
930    public:
931     
932      /// \brief Add a new node to the graph.
933      ///
934      /// Add a new node to the graph.
935      /// \return the new node.
936      Node addNode();
937
938      /// \brief Add a new undirected edge to the graph.
939      ///
940      /// Add a new undirected edge to the graph.
941      /// \return the new edge.
942      UEdge addEdge(const Node& from, const Node& to);
943
944      /// \brief Resets the graph.
945      ///
946      /// This function deletes all undirected edges and nodes of the graph.
947      /// It also frees the memory allocated to store them.
948      void clear() { }
949
950      template <typename Graph>
951      struct Constraints {
952        void constraints() {
953          checkConcept<BaseIterableUGraphConcept, Graph>();
954          checkConcept<IterableUGraphConcept, Graph>();
955          checkConcept<MappableUGraphConcept, Graph>();
956
957          checkConcept<UGraph, Graph>();
958          checkConcept<ExtendableUGraphConcept, Graph>();
959          checkConcept<ClearableGraphComponent, Graph>();
960        }
961      };
962
963    };
964
965    /// \brief An empty erasable undirected graph class.
966    ///
967    /// This class is an extension of \ref ExtendableUGraph. It makes it
968    /// possible to erase undirected edges or nodes.
969    class ErasableUGraph : public ExtendableUGraph {
970    public:
971
972      /// \brief Deletes a node.
973      ///
974      /// Deletes a node.
975      ///
976      void erase(Node) { }
977      /// \brief Deletes an undirected edge.
978      ///
979      /// Deletes an undirected edge.
980      ///
981      void erase(UEdge) { }
982
983      template <typename Graph>
984      struct Constraints {
985        void constraints() {
986          checkConcept<ExtendableUGraph, Graph>();
987          checkConcept<ErasableUGraphConcept, Graph>();
988        }
989      };
990
991    };
992
993    /// @}
994
995  }
996
997}
998
999#endif
Note: See TracBrowser for help on using the repository browser.