COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/ugraph.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

File size: 29.9 KB
RevLine 
[962]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
[962]4 *
[1956]5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[962]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
[1030]19///\ingroup graph_concepts
[962]20///\file
21///\brief Undirected graphs and components of.
22
23
[1910]24#ifndef LEMON_CONCEPT_UGRAPH_H
25#define LEMON_CONCEPT_UGRAPH_H
[962]26
27#include <lemon/concept/graph_component.h>
[1620]28#include <lemon/concept/graph.h>
[1993]29#include <lemon/bits/utility.h>
[962]30
31namespace lemon {
32  namespace concept {
33
[1630]34//     /// Skeleton class which describes an edge with direction in \ref
[1909]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;
[1030]40    public:
41
42      /// \e
[1909]43      UGraphEdge() {}
[1030]44
45      /// \e
[1909]46      UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
[1030]47
48      /// \e
[1909]49      UGraphEdge(Invalid) {}
[1030]50
[1158]51      /// \brief Directed edge from undirected edge and a source node.
[1030]52      ///
[1158]53      /// Constructs a directed edge from undirected edge and a source node.
54      ///
55      /// \note You have to specify the graph for this constructor.
[1909]56      UGraphEdge(const UGraph &g,
57                     UEdge u_edge, Node n) {
58        ignore_unused_variable_warning(u_edge);
[1158]59        ignore_unused_variable_warning(g);
60        ignore_unused_variable_warning(n);
[1030]61      }
62
63      /// \e
[1909]64      UGraphEdge& operator=(UGraphEdge) { return *this; }
[1030]65
66      /// \e
[1909]67      bool operator==(UGraphEdge) const { return true; }
[1030]68      /// \e
[1909]69      bool operator!=(UGraphEdge) const { return false; }
[1030]70
71      /// \e
[1909]72      bool operator<(UGraphEdge) const { return false; }
[1030]73
74      template <typename Edge>
75      struct Constraints {
76        void constraints() {
[1158]77          const_constraints();
78        }
79        void const_constraints() const {
[1030]80          /// \bug This should be is_base_and_derived ...
[1909]81          UEdge ue = e;
[1030]82          ue = e;
83
[1158]84          Edge e_with_source(graph,ue,n);
85          ignore_unused_variable_warning(e_with_source);
[1030]86        }
87        Edge e;
[1909]88        UEdge ue;
89        UGraph graph;
[1158]90        Node n;
[1030]91      };
92    };
93   
[962]94
[1909]95    struct BaseIterableUGraphConcept {
[989]96
[1022]97      template <typename Graph>
98      struct Constraints {
[962]99
[1909]100        typedef typename Graph::UEdge UEdge;
[1022]101        typedef typename Graph::Edge Edge;
102        typedef typename Graph::Node Node;
[962]103
[1022]104        void constraints() {
105          checkConcept<BaseIterableGraphComponent, Graph>();
[1909]106          checkConcept<GraphItem<>, UEdge>();
107          //checkConcept<UGraphEdge<Graph>, Edge>();
[962]108
[1030]109          graph.first(ue);
110          graph.next(ue);
[1022]111
[1030]112          const_constraints();
113        }
114        void const_constraints() {
[1022]115          Node n;
116          n = graph.target(ue);
117          n = graph.source(ue);
[1030]118          n = graph.oppositeNode(n0, ue);
[1022]119
[1030]120          bool b;
[1627]121          b = graph.direction(e);
[1909]122          Edge e = graph.direct(UEdge(), true);
123          e = graph.direct(UEdge(), n);
[1627]124 
[1030]125          ignore_unused_variable_warning(b);
[1022]126        }
[1030]127
128        Graph graph;
[1022]129        Edge e;
[1030]130        Node n0;
[1909]131        UEdge ue;
[1022]132      };
133
[962]134    };
135
[1022]136
[1909]137    struct IterableUGraphConcept {
[962]138
[1022]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???
[1909]144          //checkConcept< BaseIterableUGraphConcept, Graph > ();
[962]145
[1022]146          checkConcept<IterableGraphComponent, Graph> ();
[1021]147
[1909]148          typedef typename Graph::UEdge UEdge;
149          typedef typename Graph::UEdgeIt UEdgeIt;
[1030]150          typedef typename Graph::IncEdgeIt IncEdgeIt;
[1022]151
[1909]152          checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
153          checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
[1022]154        }
155      };
156
157    };
158
[1909]159    struct MappableUGraphConcept {
[1022]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
[1909]173          typedef typename Graph::template UEdgeMap<int> IntMap;
174          checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
[1022]175            IntMap >();
176
[1909]177          typedef typename Graph::template UEdgeMap<bool> BoolMap;
178          checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
[1022]179            BoolMap >();
180
[1909]181          typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
182          checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
[1022]183            DummyMap >();
184        }
185      };
186
187    };
188
[1909]189    struct ExtendableUGraphConcept {
[1022]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;
[1909]198        typename Graph::UEdge uedge;
[1022]199        Graph graph;
200      };
201
202    };
203
[1909]204    struct ErasableUGraphConcept {
[1022]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;
[1909]214        typename Graph::UEdge e;
[1022]215      };
216
217    };
218
[1620]219    /// \addtogroup graph_concepts
220    /// @{
221
222
[1030]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
[1631]234    /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
[1909]235    /// explanation of this and more see also the page \ref ugraphs,
[1030]236    /// a tutorial about undirected graphs.
[1627]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.
[1030]241
[1909]242    class UGraph {
[1022]243    public:
[1448]244      ///\e
245
246      ///\todo undocumented
247      ///
[1979]248      typedef True UndirectedTag;
[1022]249
[1669]250      /// \brief The base type of node iterators,
[1627]251      /// or in other words, the trivial node iterator.
[1669]252      ///
[1627]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:
[1946]306      ///\code
[1627]307      /// int count=0;
308      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
[1946]309      ///\endcode
[1627]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        ///
[1909]331        NodeIt(const UGraph&) { }
[1627]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.
[1909]338        NodeIt(const UGraph&, const Node&) { }
[1627]339        /// Next node.
340
341        /// Assign the iterator to the next node.
342        ///
343        NodeIt& operator++() { return *this; }
344      };
345   
346   
[1620]347      /// The base type of the undirected edge iterators.
[1627]348
[1620]349      /// The base type of the undirected edge iterators.
350      ///
[1909]351      class UEdge {
[1620]352      public:
353        /// Default constructor
[1030]354
[1620]355        /// @warning The default constructor sets the iterator
356        /// to an undefined value.
[1909]357        UEdge() { }
[1620]358        /// Copy constructor.
[1030]359
[1620]360        /// Copy constructor.
361        ///
[1909]362        UEdge(const UEdge&) { }
[1620]363        /// Initialize the iterator to be invalid.
[1030]364
[1620]365        /// Initialize the iterator to be invalid.
366        ///
[1909]367        UEdge(Invalid) { }
[1620]368        /// Equality operator
[1030]369
[1620]370        /// Two iterators are equal if and only if they point to the
371        /// same object or both are invalid.
[1909]372        bool operator==(UEdge) const { return true; }
[1620]373        /// Inequality operator
[1030]374
[1909]375        /// \sa operator==(UEdge n)
[1620]376        ///
[1909]377        bool operator!=(UEdge) const { return true; }
[1030]378
[1627]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?
[1909]389        bool operator<(UEdge) const { return false; }
[1627]390      };
[1030]391
[1620]392      /// This iterator goes through each undirected edge.
[1030]393
[1620]394      /// This iterator goes through each undirected edge of a graph.
395      /// Its usage is quite simple, for example you can count the number
[1627]396      /// of undirected edges in a graph \c g of type \c Graph as follows:
[1946]397      ///\code
[1620]398      /// int count=0;
[1909]399      /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count;
[1946]400      ///\endcode
[1909]401      class UEdgeIt : public UEdge {
[1620]402      public:
403        /// Default constructor
[1627]404
[1620]405        /// @warning The default constructor sets the iterator
406        /// to an undefined value.
[1909]407        UEdgeIt() { }
[1620]408        /// Copy constructor.
[1627]409
[1620]410        /// Copy constructor.
411        ///
[1909]412        UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
[1620]413        /// Initialize the iterator to be invalid.
[1030]414
[1620]415        /// Initialize the iterator to be invalid.
416        ///
[1909]417        UEdgeIt(Invalid) { }
[1627]418        /// This constructor sets the iterator to the first undirected edge.
[1620]419   
[1627]420        /// This constructor sets the iterator to the first undirected edge.
[1909]421        UEdgeIt(const UGraph&) { }
422        /// UEdge -> UEdgeIt conversion
[1030]423
[1627]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.
[1909]428        UEdgeIt(const UGraph&, const UEdge&) { }
[1627]429        /// Next undirected edge
[1620]430       
[1627]431        /// Assign the iterator to the next undirected edge.
[1909]432        UEdgeIt& operator++() { return *this; }
[1620]433      };
[1030]434
[1627]435      /// \brief This iterator goes trough the incident undirected
436      /// edges of a node.
437      ///
[1620]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.
[1946]445      ///\code
[1620]446      /// int count=0;
447      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
[1946]448      ///\endcode
[1909]449      class IncEdgeIt : public UEdge {
[1620]450      public:
451        /// Default constructor
[1030]452
[1620]453        /// @warning The default constructor sets the iterator
454        /// to an undefined value.
455        IncEdgeIt() { }
456        /// Copy constructor.
457
458        /// Copy constructor.
459        ///
[1909]460        IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
[1620]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.
[1909]470        IncEdgeIt(const UGraph&, const Node&) { }
471        /// UEdge -> IncEdgeIt conversion
[1620]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.
[1909]476        IncEdgeIt(const UGraph&, const UEdge&) { }
[1620]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
[1627]484      /// The directed edge type.
485
486      /// The directed edge type. It can be converted to the
487      /// undirected edge.
[1909]488      class Edge : public UEdge {
[1627]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        ///
[1909]499        Edge(const Edge& e) : UEdge(e) { }
[1627]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:
[1946]534      ///\code
[1627]535      /// int count=0;
536      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
[1946]537      ///\endcode
[1627]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
[1909]559        EdgeIt(const UGraph &g) { ignore_unused_variable_warning(g); }
[1627]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.
[1909]565        EdgeIt(const UGraph&, const Edge&) { }
[1627]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.
[1946]579      ///\code
[1627]580      /// int count=0;
581      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
[1946]582      ///\endcode
[1627]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
[1909]607        OutEdgeIt(const UGraph& n, const Node& g) {
[1643]608          ignore_unused_variable_warning(n);
609          ignore_unused_variable_warning(g);
610        }
[1627]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.
[1909]616        OutEdgeIt(const UGraph&, const Edge&) { }
[1627]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.
[1946]631      ///\code
[1627]632      /// int count=0;
633      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
[1946]634      ///\endcode
[1627]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
[1909]659        InEdgeIt(const UGraph& g, const Node& n) {
[1643]660          ignore_unused_variable_warning(n);
661          ignore_unused_variable_warning(g);
662        }
[1627]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.
[1909]668        InEdgeIt(const UGraph&, const Edge&) { }
[1627]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!
[1630]682      /// \todo Wrong documentation
[1627]683      template<class T>
684      class NodeMap : public ReadWriteMap< Node, T >
685      {
686      public:
687
688        ///\e
[1909]689        NodeMap(const UGraph&) { }
[1627]690        ///\e
[1909]691        NodeMap(const UGraph&, T) { }
[1627]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!
[1630]706      /// \todo Wrong documentation
[1627]707      template<class T>
708      class EdgeMap : public ReadWriteMap<Edge,T>
709      {
710      public:
711
712        ///\e
[1909]713        EdgeMap(const UGraph&) { }
[1627]714        ///\e
[1909]715        EdgeMap(const UGraph&, T) { }
[1627]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
[1620]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
[1909]727      /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
[1620]728      /// needs some extra attention!
[1630]729      /// \todo Wrong documentation
[1620]730      template<class T>
[1909]731      class UEdgeMap : public ReadWriteMap<UEdge,T>
[1620]732      {
[1030]733      public:
734
[1620]735        ///\e
[1909]736        UEdgeMap(const UGraph&) { }
[1620]737        ///\e
[1909]738        UEdgeMap(const UGraph&, T) { }
[1620]739        ///Copy constructor
[1909]740        UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
[1620]741        ///Assignment operator
[1909]742        UEdgeMap &operator=(const UEdgeMap&) { return *this; }
[1620]743        // \todo fix this concept   
[1030]744      };
745
[1627]746      /// \brief Direct the given undirected edge.
747      ///
748      /// Direct the given undirected edge. The returned edge source
749      /// will be the given edge.
[1909]750      Edge direct(const UEdge&, const Node&) const {
[1627]751        return INVALID;
752      }
[1030]753
[1627]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.
[1909]759      Edge direct(const UEdge&, bool) const {
[1627]760        return INVALID;
761      }
762
763      /// \brief Returns true if the edge has default orientation.
764      ///
[1030]765      /// Returns whether the given directed edge is same orientation as
766      /// the corresponding undirected edge.
[1627]767      bool direction(Edge) const { return true; }
768
769      /// \brief Returns the opposite directed edge.
[1030]770      ///
[1627]771      /// Returns the opposite directed edge.
772      Edge oppositeEdge(Edge) const { return INVALID; }
[1030]773
[1627]774      /// \brief Opposite node on an edge
775      ///
[1030]776      /// \return the opposite of the given Node on the given Edge
[1909]777      Node oppositeNode(Node, UEdge) const { return INVALID; }
[1030]778
[1627]779      /// \brief First node of the undirected edge.
780      ///
[1909]781      /// \return the first node of the given UEdge.
[1030]782      ///
[1909]783      /// Naturally uectected edges don't have direction and thus
[1030]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
[1627]787      /// undirected edge, and is used to define the "default" direction
[1030]788      /// of the directed versions of the edges.
[1627]789      /// \sa direction
[1909]790      Node source(UEdge) const { return INVALID; }
[1030]791
[1627]792      /// \brief Second node of the undirected edge.
[1909]793      Node target(UEdge) const { return INVALID; }
[1030]794
[1627]795      /// \brief Source node of the directed edge.
[1030]796      Node source(Edge) const { return INVALID; }
797
[1627]798      /// \brief Target node of the directed edge.
[1030]799      Node target(Edge) const { return INVALID; }
800
[1630]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.
[1030]806      void first(Node&) const {}
[1630]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.
[1030]812      void next(Node&) const {}
813
[1630]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.
[1909]819      void first(UEdge&) const {}
[1630]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.
[1909]825      void next(UEdge&) const {}
[1030]826
[1630]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.
[1030]832      void first(Edge&) const {}
[1630]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.
[1030]838      void next(Edge&) const {}
839
[1630]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.
[1030]845      void firstOut(Edge&, Node) const {}
[1630]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.
[1030]851      void nextOut(Edge&) const {}
852
[1630]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.
[1030]858      void firstIn(Edge&, Node) const {}
[1630]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.
[1030]864      void nextIn(Edge&) const {}
865
866
[1980]867      void firstInc(UEdge &, bool &, const Node &) const {}
868
869      void nextInc(UEdge &, bool &) const {}
870
[1627]871      /// \brief Base node of the iterator
[1158]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      }
[1627]877      /// \brief Running node of the iterator
[1158]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
[1627]885      /// \brief Base node of the iterator
[1158]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      }
[1627]891      /// \brief Running node of the iterator
[1158]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
[1627]899      /// \brief Base node of the iterator
[1158]900      ///
901      /// Returns the base node of the iterator
[1367]902      Node baseNode(IncEdgeIt) const {
[1158]903        return INVALID;
904      }
[1627]905     
906      /// \brief Running node of the iterator
[1158]907      ///
908      /// Returns the running node of the iterator
[1367]909      Node runningNode(IncEdgeIt) const {
[1158]910        return INVALID;
911      }
912
[1022]913      template <typename Graph>
914      struct Constraints {
915        void constraints() {
[1909]916          checkConcept<BaseIterableUGraphConcept, Graph>();
917          checkConcept<IterableUGraphConcept, Graph>();
918          checkConcept<MappableUGraphConcept, Graph>();
[1022]919        }
920      };
921
922    };
923
[1627]924    /// \brief An empty non-static undirected graph class.
925    ///   
[1909]926    /// This class provides everything that \ref UGraph does.
[1627]927    /// Additionally it enables building graphs from scratch.
[1909]928    class ExtendableUGraph : public UGraph {
[1022]929    public:
[1627]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.
[1909]941      UEdge addEdge(const Node& from, const Node& to);
[1627]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() { }
[1022]948
949      template <typename Graph>
950      struct Constraints {
951        void constraints() {
[1909]952          checkConcept<BaseIterableUGraphConcept, Graph>();
953          checkConcept<IterableUGraphConcept, Graph>();
954          checkConcept<MappableUGraphConcept, Graph>();
[1022]955
[1909]956          checkConcept<UGraph, Graph>();
957          checkConcept<ExtendableUGraphConcept, Graph>();
[1022]958          checkConcept<ClearableGraphComponent, Graph>();
959        }
960      };
961
962    };
963
[1627]964    /// \brief An empty erasable undirected graph class.
965    ///
[1909]966    /// This class is an extension of \ref ExtendableUGraph. It makes it
[1627]967    /// possible to erase undirected edges or nodes.
[1909]968    class ErasableUGraph : public ExtendableUGraph {
[1022]969    public:
970
[1627]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      ///
[1909]980      void erase(UEdge) { }
[1627]981
[1022]982      template <typename Graph>
983      struct Constraints {
984        void constraints() {
[1909]985          checkConcept<ExtendableUGraph, Graph>();
986          checkConcept<ErasableUGraphConcept, Graph>();
[1022]987        }
988      };
989
[962]990    };
991
[1030]992    /// @}
993
[962]994  }
995
996}
997
998#endif
Note: See TracBrowser for help on using the repository browser.