COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/undir_graph.h @ 1630:f67737f5727a

Last change on this file since 1630:f67737f5727a was 1630:f67737f5727a, checked in by Alpar Juttner, 14 years ago

Doc changes:

  • True and False got documented
  • Graph "developper interface" documentation switched off
  • minor fix in graph_to_eps_demo.cc
File size: 30.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * lemon/concept/undir_graph_component.h - Part of LEMON, a generic
4 * C++ optimization library
5 *
6 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
8 * EGRES).
9 *
10 * Permission to use, modify and distribute this software is granted
11 * provided that this copyright notice appears in all copies. For
12 * precise terms see the accompanying LICENSE file.
13 *
14 * This software is provided "AS IS" with no warranty of any kind,
15 * express or implied, and with no claim as to its suitability for any
16 * purpose.
17 *
18 */
19
20///\ingroup graph_concepts
21///\file
22///\brief Undirected graphs and components of.
23
24
25#ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
26#define LEMON_CONCEPT_UNDIR_GRAPH_H
27
28#include <lemon/concept/graph_component.h>
29#include <lemon/concept/graph.h>
30#include <lemon/utility.h>
31
32namespace lemon {
33  namespace concept {
34
35//     /// Skeleton class which describes an edge with direction in \ref
36//     /// UndirGraph "undirected graph".
37    template <typename UndirGraph>
38    class UndirGraphEdge : public UndirGraph::UndirEdge {
39      typedef typename UndirGraph::UndirEdge UndirEdge;
40      typedef typename UndirGraph::Node Node;
41    public:
42
43      /// \e
44      UndirGraphEdge() {}
45
46      /// \e
47      UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}
48
49      /// \e
50      UndirGraphEdge(Invalid) {}
51
52      /// \brief Directed edge from undirected edge and a source node.
53      ///
54      /// Constructs a directed edge from undirected edge and a source node.
55      ///
56      /// \note You have to specify the graph for this constructor.
57      UndirGraphEdge(const UndirGraph &g,
58                     UndirEdge undir_edge, Node n) {
59        ignore_unused_variable_warning(undir_edge);
60        ignore_unused_variable_warning(g);
61        ignore_unused_variable_warning(n);
62      }
63
64      /// \e
65      UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
66
67      /// \e
68      bool operator==(UndirGraphEdge) const { return true; }
69      /// \e
70      bool operator!=(UndirGraphEdge) const { return false; }
71
72      /// \e
73      bool operator<(UndirGraphEdge) const { return false; }
74
75      template <typename Edge>
76      struct Constraints {
77        void constraints() {
78          const_constraints();
79        }
80        void const_constraints() const {
81          /// \bug This should be is_base_and_derived ...
82          UndirEdge ue = e;
83          ue = e;
84
85          Edge e_with_source(graph,ue,n);
86          ignore_unused_variable_warning(e_with_source);
87        }
88        Edge e;
89        UndirEdge ue;
90        UndirGraph graph;
91        Node n;
92      };
93    };
94   
95
96    struct BaseIterableUndirGraphConcept {
97
98      template <typename Graph>
99      struct Constraints {
100
101        typedef typename Graph::UndirEdge UndirEdge;
102        typedef typename Graph::Edge Edge;
103        typedef typename Graph::Node Node;
104
105        void constraints() {
106          checkConcept<BaseIterableGraphComponent, Graph>();
107          checkConcept<GraphItem<>, UndirEdge>();
108          //checkConcept<UndirGraphEdge<Graph>, Edge>();
109
110          graph.first(ue);
111          graph.next(ue);
112
113          const_constraints();
114        }
115        void const_constraints() {
116          Node n;
117          n = graph.target(ue);
118          n = graph.source(ue);
119          n = graph.oppositeNode(n0, ue);
120
121          bool b;
122          b = graph.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::Graph "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      /// 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&) { }
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&, const Node&) { }
609        /// Edge -> OutEdgeIt conversion
610
611        /// Sets the iterator to the value of the trivial iterator.
612        /// This feature necessitates that each time we
613        /// iterate the edge-set, the iteration order is the same.
614        OutEdgeIt(const UndirGraph&, const Edge&) { }
615        ///Next outgoing edge
616       
617        /// Assign the iterator to the next
618        /// outgoing edge of the corresponding node.
619        OutEdgeIt& operator++() { return *this; }
620      };
621
622      /// This iterator goes trough the incoming directed edges of a node.
623
624      /// This iterator goes trough the \e incoming edges of a certain node
625      /// of a graph.
626      /// Its usage is quite simple, for example you can count the number
627      /// of outgoing edges of a node \c n
628      /// in graph \c g of type \c Graph as follows.
629      /// \code
630      /// int count=0;
631      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
632      /// \endcode
633
634      class InEdgeIt : public Edge {
635      public:
636        /// Default constructor
637
638        /// @warning The default constructor sets the iterator
639        /// to an undefined value.
640        InEdgeIt() { }
641        /// Copy constructor.
642
643        /// Copy constructor.
644        ///
645        InEdgeIt(const InEdgeIt& e) : Edge(e) { }
646        /// Initialize the iterator to be invalid.
647
648        /// Initialize the iterator to be invalid.
649        ///
650        InEdgeIt(Invalid) { }
651        /// This constructor sets the iterator to first incoming edge.
652   
653        /// This constructor set the iterator to the first incoming edge of
654        /// the node.
655        ///@param n the node
656        ///@param g the graph
657        InEdgeIt(const UndirGraph&, const Node&) { }
658        /// Edge -> InEdgeIt conversion
659
660        /// Sets the iterator to the value of the trivial iterator \c e.
661        /// This feature necessitates that each time we
662        /// iterate the edge-set, the iteration order is the same.
663        InEdgeIt(const UndirGraph&, const Edge&) { }
664        /// Next incoming edge
665
666        /// Assign the iterator to the next inedge of the corresponding node.
667        ///
668        InEdgeIt& operator++() { return *this; }
669      };
670
671      /// \brief Read write map of the nodes to type \c T.
672      ///
673      /// ReadWrite map of the nodes to type \c T.
674      /// \sa Reference
675      /// \warning Making maps that can handle bool type (NodeMap<bool>)
676      /// needs some extra attention!
677      /// \todo Wrong documentation
678      template<class T>
679      class NodeMap : public ReadWriteMap< Node, T >
680      {
681      public:
682
683        ///\e
684        NodeMap(const UndirGraph&) { }
685        ///\e
686        NodeMap(const UndirGraph&, T) { }
687
688        ///Copy constructor
689        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
690        ///Assignment operator
691        NodeMap& operator=(const NodeMap&) { return *this; }
692        // \todo fix this concept
693      };
694
695      /// \brief Read write map of the directed edges to type \c T.
696      ///
697      /// Reference map of the directed edges to type \c T.
698      /// \sa Reference
699      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
700      /// needs some extra attention!
701      /// \todo Wrong documentation
702      template<class T>
703      class EdgeMap : public ReadWriteMap<Edge,T>
704      {
705      public:
706
707        ///\e
708        EdgeMap(const UndirGraph&) { }
709        ///\e
710        EdgeMap(const UndirGraph&, T) { }
711        ///Copy constructor
712        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
713        ///Assignment operator
714        EdgeMap& operator=(const EdgeMap&) { return *this; }
715        // \todo fix this concept   
716      };
717
718      /// Read write map of the undirected edges to type \c T.
719
720      /// Reference map of the edges to type \c T.
721      /// \sa Reference
722      /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
723      /// needs some extra attention!
724      /// \todo Wrong documentation
725      template<class T>
726      class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
727      {
728      public:
729
730        ///\e
731        UndirEdgeMap(const UndirGraph&) { }
732        ///\e
733        UndirEdgeMap(const UndirGraph&, T) { }
734        ///Copy constructor
735        UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}
736        ///Assignment operator
737        UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
738        // \todo fix this concept   
739      };
740
741      /// \brief Direct the given undirected edge.
742      ///
743      /// Direct the given undirected edge. The returned edge source
744      /// will be the given edge.
745      Edge direct(const UndirEdge&, const Node&) const {
746        return INVALID;
747      }
748
749      /// \brief Direct the given undirected edge.
750      ///
751      /// Direct the given undirected edge. The returned edge source
752      /// will be the source of the undirected edge if the given bool
753      /// is true.
754      Edge direct(const UndirEdge&, bool) const {
755        return INVALID;
756      }
757
758      /// \brief Returns true if the edge has default orientation.
759      ///
760      /// Returns whether the given directed edge is same orientation as
761      /// the corresponding undirected edge.
762      bool direction(Edge) const { return true; }
763
764      /// \brief Returns the opposite directed edge.
765      ///
766      /// Returns the opposite directed edge.
767      Edge oppositeEdge(Edge) const { return INVALID; }
768
769      /// \brief Opposite node on an edge
770      ///
771      /// \return the opposite of the given Node on the given Edge
772      Node oppositeNode(Node, UndirEdge) const { return INVALID; }
773
774      /// \brief First node of the undirected edge.
775      ///
776      /// \return the first node of the given UndirEdge.
777      ///
778      /// Naturally undirectected edges don't have direction and thus
779      /// don't have source and target node. But we use these two methods
780      /// to query the two endnodes of the edge. The direction of the edge
781      /// which arises this way is called the inherent direction of the
782      /// undirected edge, and is used to define the "default" direction
783      /// of the directed versions of the edges.
784      /// \sa direction
785      Node source(UndirEdge) const { return INVALID; }
786
787      /// \brief Second node of the undirected edge.
788      Node target(UndirEdge) const { return INVALID; }
789
790      /// \brief Source node of the directed edge.
791      Node source(Edge) const { return INVALID; }
792
793      /// \brief Target node of the directed edge.
794      Node target(Edge) const { return INVALID; }
795
796//       /// \brief First node of the graph
797//       ///
798//       /// \note This method is part of so called \ref
799//       /// developpers_interface "Developpers' interface", so it shouldn't
800//       /// be used in an end-user program.
801      void first(Node&) const {}
802//       /// \brief Next 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 next(Node&) const {}
808
809//       /// \brief First undirected edge of the graph
810//       ///
811//       /// \note This method is part of so called \ref
812//       /// developpers_interface "Developpers' interface", so it shouldn't
813//       /// be used in an end-user program.
814      void first(UndirEdge&) const {}
815//       /// \brief Next 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 next(UndirEdge&) const {}
821
822//       /// \brief First directed edge of the graph
823//       ///
824//       /// \note This method is part of so called \ref
825//       /// developpers_interface "Developpers' interface", so it shouldn't
826//       /// be used in an end-user program.
827      void first(Edge&) const {}
828//       /// \brief Next 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 next(Edge&) const {}
834
835//       /// \brief First outgoing edge from a given node
836//       ///
837//       /// \note This method is part of so called \ref
838//       /// developpers_interface "Developpers' interface", so it shouldn't
839//       /// be used in an end-user program.
840      void firstOut(Edge&, Node) const {}
841//       /// \brief Next outgoing edge to a 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 nextOut(Edge&) const {}
847
848//       /// \brief First incoming edge to a given node
849//       ///
850//       /// \note This method is part of so called \ref
851//       /// developpers_interface "Developpers' interface", so it shouldn't
852//       /// be used in an end-user program.
853      void firstIn(Edge&, Node) const {}
854//       /// \brief Next incoming edge to a 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 nextIn(Edge&) const {}
860
861
862      /// \brief Base node of the iterator
863      ///
864      /// Returns the base node (the source in this case) of the iterator
865      Node baseNode(OutEdgeIt e) const {
866        return source(e);
867      }
868      /// \brief Running node of the iterator
869      ///
870      /// Returns the running node (the target in this case) of the
871      /// iterator
872      Node runningNode(OutEdgeIt e) const {
873        return target(e);
874      }
875
876      /// \brief Base node of the iterator
877      ///
878      /// Returns the base node (the target in this case) of the iterator
879      Node baseNode(InEdgeIt e) const {
880        return target(e);
881      }
882      /// \brief Running node of the iterator
883      ///
884      /// Returns the running node (the source in this case) of the
885      /// iterator
886      Node runningNode(InEdgeIt e) const {
887        return source(e);
888      }
889
890      /// \brief Base node of the iterator
891      ///
892      /// Returns the base node of the iterator
893      Node baseNode(IncEdgeIt) const {
894        return INVALID;
895      }
896     
897      /// \brief Running node of the iterator
898      ///
899      /// Returns the running node of the iterator
900      Node runningNode(IncEdgeIt) const {
901        return INVALID;
902      }
903
904      template <typename Graph>
905      struct Constraints {
906        void constraints() {
907          checkConcept<BaseIterableUndirGraphConcept, Graph>();
908          checkConcept<IterableUndirGraphConcept, Graph>();
909          checkConcept<MappableUndirGraphConcept, Graph>();
910        }
911      };
912
913    };
914
915    /// \brief An empty non-static undirected graph class.
916    ///   
917    /// This class provides everything that \ref UndirGraph does.
918    /// Additionally it enables building graphs from scratch.
919    class ExtendableUndirGraph : public UndirGraph {
920    public:
921     
922      /// \brief Add a new node to the graph.
923      ///
924      /// Add a new node to the graph.
925      /// \return the new node.
926      Node addNode();
927
928      /// \brief Add a new undirected edge to the graph.
929      ///
930      /// Add a new undirected edge to the graph.
931      /// \return the new edge.
932      UndirEdge addEdge(const Node& from, const Node& to);
933
934      /// \brief Resets the graph.
935      ///
936      /// This function deletes all undirected edges and nodes of the graph.
937      /// It also frees the memory allocated to store them.
938      void clear() { }
939
940      template <typename Graph>
941      struct Constraints {
942        void constraints() {
943          checkConcept<BaseIterableUndirGraphConcept, Graph>();
944          checkConcept<IterableUndirGraphConcept, Graph>();
945          checkConcept<MappableUndirGraphConcept, Graph>();
946
947          checkConcept<UndirGraph, Graph>();
948          checkConcept<ExtendableUndirGraphConcept, Graph>();
949          checkConcept<ClearableGraphComponent, Graph>();
950        }
951      };
952
953    };
954
955    /// \brief An empty erasable undirected graph class.
956    ///
957    /// This class is an extension of \ref ExtendableUndirGraph. It makes it
958    /// possible to erase undirected edges or nodes.
959    class ErasableUndirGraph : public ExtendableUndirGraph {
960    public:
961
962      /// \brief Deletes a node.
963      ///
964      /// Deletes a node.
965      ///
966      void erase(Node) { }
967      /// \brief Deletes an undirected edge.
968      ///
969      /// Deletes an undirected edge.
970      ///
971      void erase(UndirEdge) { }
972
973      template <typename Graph>
974      struct Constraints {
975        void constraints() {
976          checkConcept<ExtendableUndirGraph, Graph>();
977          checkConcept<ErasableUndirGraphConcept, Graph>();
978        }
979      };
980
981    };
982
983    /// @}
984
985  }
986
987}
988
989#endif
Note: See TracBrowser for help on using the repository browser.