COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/concepts/graph.h @ 1210:da87dbdf3daf

Last change on this file since 1210:da87dbdf3daf was 1210:da87dbdf3daf, checked in by Alpar Juttner <alpar@…>, 14 months ago

Resolve deprecation warnings of gcc 9 (#633)

File size: 31.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
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 The concept of undirected graphs.
22
23#ifndef LEMON_CONCEPTS_GRAPH_H
24#define LEMON_CONCEPTS_GRAPH_H
25
26#include <lemon/concepts/graph_components.h>
27#include <lemon/concepts/maps.h>
28#include <lemon/concept_check.h>
29#include <lemon/core.h>
30#include <lemon/bits/stl_iterators.h>
31
32namespace lemon {
33  namespace concepts {
34
35    /// \ingroup graph_concepts
36    ///
37    /// \brief Class describing the concept of undirected graphs.
38    ///
39    /// This class describes the common interface of all undirected
40    /// graphs.
41    ///
42    /// Like all concept classes, it only provides an interface
43    /// without any sensible implementation. So any general algorithm for
44    /// undirected graphs should compile with this class, but it will not
45    /// run properly, of course.
46    /// An actual graph implementation like \ref ListGraph or
47    /// \ref SmartGraph may have additional functionality.
48    ///
49    /// The undirected graphs also fulfill the concept of \ref Digraph
50    /// "directed graphs", since each edge can also be regarded as two
51    /// oppositely directed arcs.
52    /// Undirected graphs provide an Edge type for the undirected edges and
53    /// an Arc type for the directed arcs. The Arc type is convertible to
54    /// Edge or inherited from it, i.e. the corresponding edge can be
55    /// obtained from an arc.
56    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
57    /// and ArcMap classes can be used for the arcs (just like in digraphs).
58    /// Both InArcIt and OutArcIt iterates on the same edges but with
59    /// opposite direction. IncEdgeIt also iterates on the same edges
60    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
61    /// only to Edge.
62    ///
63    /// In LEMON, each undirected edge has an inherent orientation.
64    /// Thus it can defined if an arc is forward or backward oriented in
65    /// an undirected graph with respect to this default oriantation of
66    /// the represented edge.
67    /// With the direction() and direct() functions the direction
68    /// of an arc can be obtained and set, respectively.
69    ///
70    /// Only nodes and edges can be added to or removed from an undirected
71    /// graph and the corresponding arcs are added or removed automatically.
72    ///
73    /// \sa Digraph
74    class Graph {
75    private:
76      /// Graphs are \e not copy constructible. Use GraphCopy instead.
77      Graph(const Graph&) {}
78      /// \brief Assignment of a graph to another one is \e not allowed.
79      /// Use GraphCopy instead.
80      void operator=(const Graph&) {}
81
82    public:
83      /// Default constructor.
84      Graph() {}
85
86      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
87      ///
88      /// Undirected graphs should be tagged with \c UndirectedTag.
89      ///
90      /// This tag helps the \c enable_if technics to make compile time
91      /// specializations for undirected graphs.
92      typedef True UndirectedTag;
93
94      /// The node type of the graph
95
96      /// This class identifies a node of the graph. It also serves
97      /// as a base class of the node iterators,
98      /// thus they convert to this type.
99      class Node {
100      public:
101        /// Default constructor
102
103        /// Default constructor.
104        /// \warning It sets the object to an undefined value.
105        Node() { }
106        /// Copy constructor.
107
108        /// Copy constructor.
109        ///
110        Node(const Node&) { }
111        /// Assignment operator
112
113        /// Assignment operator.
114        ///
115        const Node &operator=(const Node&) { return *this; }
116
117        /// %Invalid constructor \& conversion.
118
119        /// Initializes the object to be invalid.
120        /// \sa Invalid for more details.
121        Node(Invalid) { }
122        /// Equality operator
123
124        /// Equality operator.
125        ///
126        /// Two iterators are equal if and only if they point to the
127        /// same object or both are \c INVALID.
128        bool operator==(Node) const { return true; }
129
130        /// Inequality operator
131
132        /// Inequality operator.
133        bool operator!=(Node) const { return true; }
134
135        /// Artificial ordering operator.
136
137        /// Artificial ordering operator.
138        ///
139        /// \note This operator only has to define some strict ordering of
140        /// the items; this order has nothing to do with the iteration
141        /// ordering of the items.
142        bool operator<(Node) const { return false; }
143
144      };
145
146      /// Iterator class for the nodes.
147
148      /// This iterator goes through each node of the graph.
149      /// Its usage is quite simple, for example, you can count the number
150      /// of nodes in a graph \c g of type \c %Graph like this:
151      ///\code
152      /// int count=0;
153      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
154      ///\endcode
155      class NodeIt : public Node {
156      public:
157        /// Default constructor
158
159        /// Default constructor.
160        /// \warning It sets the iterator to an undefined value.
161        NodeIt() { }
162        /// Copy constructor.
163
164        /// Copy constructor.
165        ///
166        NodeIt(const NodeIt& n) : Node(n) { }
167        /// Assignment operator
168
169        /// Assignment operator.
170        ///
171        const NodeIt &operator=(const NodeIt&) { return *this; }
172
173        /// %Invalid constructor \& conversion.
174
175        /// Initializes the iterator to be invalid.
176        /// \sa Invalid for more details.
177        NodeIt(Invalid) { }
178        /// Sets the iterator to the first node.
179
180        /// Sets the iterator to the first node of the given digraph.
181        ///
182        explicit NodeIt(const Graph&) { }
183        /// Sets the iterator to the given node.
184
185        /// Sets the iterator to the given node of the given digraph.
186        ///
187        NodeIt(const Graph&, const Node&) { }
188        /// Next node.
189
190        /// Assign the iterator to the next node.
191        ///
192        NodeIt& operator++() { return *this; }
193      };
194
195      /// \brief Gets the collection of the nodes of the graph.
196      ///
197      /// This function can be used for iterating on
198      /// the nodes of the graph. It returns a wrapped NodeIt, which looks
199      /// like an STL container (by having begin() and end())
200      /// which you can use in range-based for loops, STL algorithms, etc.
201      /// For example you can write:
202      ///\code
203      /// ListGraph g;
204      /// for(auto v: g.nodes())
205      ///   doSomething(v);
206      ///
207      /// //Using an STL algorithm:
208      /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
209      ///\endcode
210      LemonRangeWrapper1<NodeIt, Graph> nodes() const {
211        return LemonRangeWrapper1<NodeIt, Graph>(*this);
212      }
213
214
215      /// The edge type of the graph
216
217      /// This class identifies an edge of the graph. It also serves
218      /// as a base class of the edge iterators,
219      /// thus they will convert to this type.
220      class Edge {
221      public:
222        /// Default constructor
223
224        /// Default constructor.
225        /// \warning It sets the object to an undefined value.
226        Edge() { }
227        /// Copy constructor.
228
229        /// Copy constructor.
230        ///
231        Edge(const Edge&) { }
232        /// Assignment operator
233
234        /// Assignment operator.
235        ///
236        const Edge &operator=(const Edge&) { return *this; }
237
238        /// %Invalid constructor \& conversion.
239
240        /// Initializes the object to be invalid.
241        /// \sa Invalid for more details.
242        Edge(Invalid) { }
243        /// Equality operator
244
245        /// Equality operator.
246        ///
247        /// Two iterators are equal if and only if they point to the
248        /// same object or both are \c INVALID.
249        bool operator==(Edge) const { return true; }
250        /// Inequality operator
251
252        /// Inequality operator.
253        bool operator!=(Edge) const { return true; }
254
255        /// Artificial ordering operator.
256
257        /// Artificial ordering operator.
258        ///
259        /// \note This operator only has to define some strict ordering of
260        /// the edges; this order has nothing to do with the iteration
261        /// ordering of the edges.
262        bool operator<(Edge) const { return false; }
263      };
264
265      /// Iterator class for the edges.
266
267      /// This iterator goes through each edge of the graph.
268      /// Its usage is quite simple, for example, you can count the number
269      /// of edges in a graph \c g of type \c %Graph as follows:
270      ///\code
271      /// int count=0;
272      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
273      ///\endcode
274      class EdgeIt : public Edge {
275      public:
276        /// Default constructor
277
278        /// Default constructor.
279        /// \warning It sets the iterator to an undefined value.
280        EdgeIt() { }
281        /// Copy constructor.
282
283        /// Copy constructor.
284        ///
285        EdgeIt(const EdgeIt& e) : Edge(e) { }
286        /// Assignment operator
287
288        /// Assignment operator.
289        ///
290        const EdgeIt &operator=(const EdgeIt&) { return *this; }
291
292        /// %Invalid constructor \& conversion.
293
294        /// Initializes the iterator to be invalid.
295        /// \sa Invalid for more details.
296        EdgeIt(Invalid) { }
297        /// Sets the iterator to the first edge.
298
299        /// Sets the iterator to the first edge of the given graph.
300        ///
301        explicit EdgeIt(const Graph&) { }
302        /// Sets the iterator to the given edge.
303
304        /// Sets the iterator to the given edge of the given graph.
305        ///
306        EdgeIt(const Graph&, const Edge&) { }
307        /// Next edge
308
309        /// Assign the iterator to the next edge.
310        ///
311        EdgeIt& operator++() { return *this; }
312      };
313
314      /// \brief Gets the collection of the edges of the graph.
315      ///
316      /// This function can be used for iterating on the
317      /// edges of the graph. It returns a wrapped
318      /// EdgeIt, which looks like an STL container
319      /// (by having begin() and end()) which you can use in range-based
320      /// for loops, STL algorithms, etc.
321      /// For example you can write:
322      ///\code
323      /// ListGraph g;
324      /// for(auto e: g.edges())
325      ///   doSomething(e);
326      ///
327      /// //Using an STL algorithm:
328      /// copy(g.edges().begin(), g.edges().end(), vect.begin());
329      ///\endcode
330      LemonRangeWrapper1<EdgeIt, Graph> edges() const {
331        return LemonRangeWrapper1<EdgeIt, Graph>(*this);
332      }
333
334
335      /// Iterator class for the incident edges of a node.
336
337      /// This iterator goes trough the incident undirected edges
338      /// of a certain node of a graph.
339      /// Its usage is quite simple, for example, you can compute the
340      /// degree (i.e. the number of incident edges) of a node \c n
341      /// in a graph \c g of type \c %Graph as follows.
342      ///
343      ///\code
344      /// int count=0;
345      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
346      ///\endcode
347      ///
348      /// \warning Loop edges will be iterated twice.
349      class IncEdgeIt : public Edge {
350      public:
351        /// Default constructor
352
353        /// Default constructor.
354        /// \warning It sets the iterator to an undefined value.
355        IncEdgeIt() { }
356        /// Copy constructor.
357
358        /// Copy constructor.
359        ///
360        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
361        /// Assignment operator
362
363        /// Assignment operator.
364        ///
365        const IncEdgeIt &operator=(const IncEdgeIt&) { return *this; }
366
367        /// %Invalid constructor \& conversion.
368
369        /// Initializes the iterator to be invalid.
370        /// \sa Invalid for more details.
371        IncEdgeIt(Invalid) { }
372        /// Sets the iterator to the first incident edge.
373
374        /// Sets the iterator to the first incident edge of the given node.
375        ///
376        IncEdgeIt(const Graph&, const Node&) { }
377        /// Sets the iterator to the given edge.
378
379        /// Sets the iterator to the given edge of the given graph.
380        ///
381        IncEdgeIt(const Graph&, const Edge&) { }
382        /// Next incident edge
383
384        /// Assign the iterator to the next incident edge
385        /// of the corresponding node.
386        IncEdgeIt& operator++() { return *this; }
387      };
388
389      /// \brief Gets the collection of the incident undirected edges
390      ///  of a certain node of the graph.
391      ///
392      /// This function can be used for iterating on the
393      /// incident undirected edges of a certain node of the graph.
394      /// It returns a wrapped
395      /// IncEdgeIt, which looks like an STL container
396      /// (by having begin() and end()) which you can use in range-based
397      /// for loops, STL algorithms, etc.
398      /// For example if g is a Graph and u is a Node, you can write:
399      ///\code
400      /// for(auto e: g.incEdges(u))
401      ///   doSomething(e);
402      ///
403      /// //Using an STL algorithm:
404      /// copy(g.incEdges(u).begin(), g.incEdges(u).end(), vect.begin());
405      ///\endcode
406      LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
407        return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
408      }
409
410
411      /// The arc type of the graph
412
413      /// This class identifies a directed arc of the graph. It also serves
414      /// as a base class of the arc iterators,
415      /// thus they will convert to this type.
416      class Arc {
417      public:
418        /// Default constructor
419
420        /// Default constructor.
421        /// \warning It sets the object to an undefined value.
422        Arc() { }
423        /// Copy constructor.
424
425        /// Copy constructor.
426        ///
427        Arc(const Arc&) { }
428        /// Assignment operator
429
430        /// Assignment operator.
431        ///
432        const Arc &operator=(const Arc&) { return *this; }
433
434        /// %Invalid constructor \& conversion.
435
436        /// Initializes the object to be invalid.
437        /// \sa Invalid for more details.
438        Arc(Invalid) { }
439        /// Equality operator
440
441        /// Equality operator.
442        ///
443        /// Two iterators are equal if and only if they point to the
444        /// same object or both are \c INVALID.
445        bool operator==(Arc) const { return true; }
446        /// Inequality operator
447
448        /// Inequality operator.
449        bool operator!=(Arc) const { return true; }
450
451        /// Artificial ordering operator.
452
453        /// Artificial ordering operator.
454        ///
455        /// \note This operator only has to define some strict ordering of
456        /// the arcs; this order has nothing to do with the iteration
457        /// ordering of the arcs.
458        bool operator<(Arc) const { return false; }
459
460        /// Converison to \c Edge
461
462        /// Converison to \c Edge.
463        ///
464        operator Edge() const { return Edge(); }
465      };
466
467      /// Iterator class for the arcs.
468
469      /// This iterator goes through each directed arc of the graph.
470      /// Its usage is quite simple, for example, you can count the number
471      /// of arcs in a graph \c g of type \c %Graph as follows:
472      ///\code
473      /// int count=0;
474      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
475      ///\endcode
476      class ArcIt : public Arc {
477      public:
478        /// Default constructor
479
480        /// Default constructor.
481        /// \warning It sets the iterator to an undefined value.
482        ArcIt() { }
483        /// Copy constructor.
484
485        /// Copy constructor.
486        ///
487        ArcIt(const ArcIt& e) : Arc(e) { }
488        /// Assignment operator
489
490        /// Assignment operator.
491        ///
492        const ArcIt &operator=(const ArcIt&) { return *this; }
493
494        /// %Invalid constructor \& conversion.
495
496        /// Initializes the iterator to be invalid.
497        /// \sa Invalid for more details.
498        ArcIt(Invalid) { }
499        /// Sets the iterator to the first arc.
500
501        /// Sets the iterator to the first arc of the given graph.
502        ///
503        explicit ArcIt(const Graph &g) {
504          ::lemon::ignore_unused_variable_warning(g);
505        }
506        /// Sets the iterator to the given arc.
507
508        /// Sets the iterator to the given arc of the given graph.
509        ///
510        ArcIt(const Graph&, const Arc&) { }
511        /// Next arc
512
513        /// Assign the iterator to the next arc.
514        ///
515        ArcIt& operator++() { return *this; }
516      };
517
518      /// \brief Gets the collection of the directed arcs of the graph.
519      ///
520      /// This function can be used for iterating on the
521      /// arcs of the graph. It returns a wrapped
522      /// ArcIt, which looks like an STL container
523      /// (by having begin() and end()) which you can use in range-based
524      /// for loops, STL algorithms, etc.
525      /// For example you can write:
526      ///\code
527      /// ListGraph g;
528      /// for(auto a: g.arcs())
529      ///   doSomething(a);
530      ///
531      /// //Using an STL algorithm:
532      /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
533      ///\endcode
534      LemonRangeWrapper1<ArcIt, Graph> arcs() const {
535        return LemonRangeWrapper1<ArcIt, Graph>(*this);
536      }
537
538
539      /// Iterator class for the outgoing arcs of a node.
540
541      /// This iterator goes trough the \e outgoing directed arcs of a
542      /// certain node of a graph.
543      /// Its usage is quite simple, for example, you can count the number
544      /// of outgoing arcs of a node \c n
545      /// in a graph \c g of type \c %Graph as follows.
546      ///\code
547      /// int count=0;
548      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
549      ///\endcode
550      class OutArcIt : public Arc {
551      public:
552        /// Default constructor
553
554        /// Default constructor.
555        /// \warning It sets the iterator to an undefined value.
556        OutArcIt() { }
557        /// Copy constructor.
558
559        /// Copy constructor.
560        ///
561        OutArcIt(const OutArcIt& e) : Arc(e) { }
562        /// Assignment operator
563
564        /// Assignment operator.
565        ///
566        const OutArcIt &operator=(const OutArcIt&) { return *this; }
567
568        /// %Invalid constructor \& conversion.
569
570        /// Initializes the iterator to be invalid.
571        /// \sa Invalid for more details.
572        OutArcIt(Invalid) { }
573        /// Sets the iterator to the first outgoing arc.
574
575        /// Sets the iterator to the first outgoing arc of the given node.
576        ///
577        OutArcIt(const Graph& n, const Node& g) {
578          ::lemon::ignore_unused_variable_warning(n);
579          ::lemon::ignore_unused_variable_warning(g);
580        }
581        /// Sets the iterator to the given arc.
582
583        /// Sets the iterator to the given arc of the given graph.
584        ///
585        OutArcIt(const Graph&, const Arc&) { }
586        /// Next outgoing arc
587
588        /// Assign the iterator to the next
589        /// outgoing arc of the corresponding node.
590        OutArcIt& operator++() { return *this; }
591      };
592
593      /// \brief Gets the collection of the outgoing directed arcs of a
594      /// certain node of the graph.
595      ///
596      /// This function can be used for iterating on the
597      /// outgoing arcs of a certain node of the graph. It returns a wrapped
598      /// OutArcIt, which looks like an STL container
599      /// (by having begin() and end()) which you can use in range-based
600      /// for loops, STL algorithms, etc.
601      /// For example if g is a Graph and u is a Node, you can write:
602      ///\code
603      /// for(auto a: g.outArcs(u))
604      ///   doSomething(a);
605      ///
606      /// //Using an STL algorithm:
607      /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
608      ///\endcode
609      LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
610        return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
611      }
612
613
614      /// Iterator class for the incoming arcs of a node.
615
616      /// This iterator goes trough the \e incoming directed arcs of a
617      /// certain node of a graph.
618      /// Its usage is quite simple, for example, you can count the number
619      /// of incoming arcs of a node \c n
620      /// in a graph \c g of type \c %Graph as follows.
621      ///\code
622      /// int count=0;
623      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
624      ///\endcode
625      class InArcIt : public Arc {
626      public:
627        /// Default constructor
628
629        /// Default constructor.
630        /// \warning It sets the iterator to an undefined value.
631        InArcIt() { }
632        /// Copy constructor.
633
634        /// Copy constructor.
635        ///
636        InArcIt(const InArcIt& e) : Arc(e) { }
637        /// Assignment operator
638
639        /// Assignment operator.
640        ///
641        const InArcIt &operator=(const InArcIt&) { return *this; }
642
643        /// %Invalid constructor \& conversion.
644
645        /// Initializes the iterator to be invalid.
646        /// \sa Invalid for more details.
647        InArcIt(Invalid) { }
648        /// Sets the iterator to the first incoming arc.
649
650        /// Sets the iterator to the first incoming arc of the given node.
651        ///
652        InArcIt(const Graph& g, const Node& n) {
653          ::lemon::ignore_unused_variable_warning(n);
654          ::lemon::ignore_unused_variable_warning(g);
655        }
656        /// Sets the iterator to the given arc.
657
658        /// Sets the iterator to the given arc of the given graph.
659        ///
660        InArcIt(const Graph&, const Arc&) { }
661        /// Next incoming arc
662
663        /// Assign the iterator to the next
664        /// incoming arc of the corresponding node.
665        InArcIt& operator++() { return *this; }
666      };
667
668      /// \brief Gets the collection of the incoming directed arcs of
669      /// a certain node of the graph.
670      ///
671      /// This function can be used for iterating on the
672      /// incoming directed arcs of a certain node of the graph. It returns
673      /// a wrapped InArcIt, which looks like an STL container
674      /// (by having begin() and end()) which you can use in range-based
675      /// for loops, STL algorithms, etc.
676      /// For example if g is a Graph and u is a Node, you can write:
677      ///\code
678      /// for(auto a: g.inArcs(u))
679      ///   doSomething(a);
680      ///
681      /// //Using an STL algorithm:
682      /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
683      ///\endcode
684      LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
685        return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
686      }
687
688      /// \brief Standard graph map type for the nodes.
689      ///
690      /// Standard graph map type for the nodes.
691      /// It conforms to the ReferenceMap concept.
692      template<class T>
693      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
694      {
695      public:
696
697        /// Constructor
698        explicit NodeMap(const Graph&) { }
699        /// Constructor with given initial value
700        NodeMap(const Graph&, T) { }
701
702      private:
703        ///Copy constructor
704        NodeMap(const NodeMap& nm) :
705          ReferenceMap<Node, T, T&, const T&>(nm) { }
706        ///Assignment operator
707        NodeMap& operator=(const NodeMap&) {
708          return *this;
709        }
710        ///Template Assignment operator
711        template <typename CMap>
712        NodeMap& operator=(const CMap&) {
713          checkConcept<ReadMap<Node, T>, CMap>();
714          return *this;
715        }
716      };
717
718      /// \brief Standard graph map type for the arcs.
719      ///
720      /// Standard graph map type for the arcs.
721      /// It conforms to the ReferenceMap concept.
722      template<class T>
723      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
724      {
725      public:
726
727        /// Constructor
728        explicit ArcMap(const Graph&) { }
729        /// Constructor with given initial value
730        ArcMap(const Graph&, T) { }
731
732      private:
733        ///Copy constructor
734        ArcMap(const ArcMap& em) :
735          ReferenceMap<Arc, T, T&, const T&>(em) { }
736        ///Assignment operator
737        ArcMap& operator=(const ArcMap&) {
738          return *this;
739        }
740        ///Template Assignment operator
741        template <typename CMap>
742        ArcMap& operator=(const CMap&) {
743          checkConcept<ReadMap<Arc, T>, CMap>();
744          return *this;
745        }
746      };
747
748      /// \brief Standard graph map type for the edges.
749      ///
750      /// Standard graph map type for the edges.
751      /// It conforms to the ReferenceMap concept.
752      template<class T>
753      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
754      {
755      public:
756
757        /// Constructor
758        explicit EdgeMap(const Graph&) { }
759        /// Constructor with given initial value
760        EdgeMap(const Graph&, T) { }
761
762      private:
763        ///Copy constructor
764        EdgeMap(const EdgeMap& em) :
765          ReferenceMap<Edge, T, T&, const T&>(em) {}
766        ///Assignment operator
767        EdgeMap& operator=(const EdgeMap&) {
768          return *this;
769        }
770        ///Template Assignment operator
771        template <typename CMap>
772        EdgeMap& operator=(const CMap&) {
773          checkConcept<ReadMap<Edge, T>, CMap>();
774          return *this;
775        }
776      };
777
778      /// \brief The first node of the edge.
779      ///
780      /// Returns the first node of the given edge.
781      ///
782      /// Edges don't have source and target nodes, however, methods
783      /// u() and v() are used to query the two end-nodes of an edge.
784      /// The orientation of an edge that arises this way is called
785      /// the inherent direction, it is used to define the default
786      /// direction for the corresponding arcs.
787      /// \sa v()
788      /// \sa direction()
789      Node u(Edge) const { return INVALID; }
790
791      /// \brief The second node of the edge.
792      ///
793      /// Returns the second node of the given edge.
794      ///
795      /// Edges don't have source and target nodes, however, methods
796      /// u() and v() are used to query the two end-nodes of an edge.
797      /// The orientation of an edge that arises this way is called
798      /// the inherent direction, it is used to define the default
799      /// direction for the corresponding arcs.
800      /// \sa u()
801      /// \sa direction()
802      Node v(Edge) const { return INVALID; }
803
804      /// \brief The source node of the arc.
805      ///
806      /// Returns the source node of the given arc.
807      Node source(Arc) const { return INVALID; }
808
809      /// \brief The target node of the arc.
810      ///
811      /// Returns the target node of the given arc.
812      Node target(Arc) const { return INVALID; }
813
814      /// \brief The ID of the node.
815      ///
816      /// Returns the ID of the given node.
817      int id(Node) const { return -1; }
818
819      /// \brief The ID of the edge.
820      ///
821      /// Returns the ID of the given edge.
822      int id(Edge) const { return -1; }
823
824      /// \brief The ID of the arc.
825      ///
826      /// Returns the ID of the given arc.
827      int id(Arc) const { return -1; }
828
829      /// \brief The node with the given ID.
830      ///
831      /// Returns the node with the given ID.
832      /// \pre The argument should be a valid node ID in the graph.
833      Node nodeFromId(int) const { return INVALID; }
834
835      /// \brief The edge with the given ID.
836      ///
837      /// Returns the edge with the given ID.
838      /// \pre The argument should be a valid edge ID in the graph.
839      Edge edgeFromId(int) const { return INVALID; }
840
841      /// \brief The arc with the given ID.
842      ///
843      /// Returns the arc with the given ID.
844      /// \pre The argument should be a valid arc ID in the graph.
845      Arc arcFromId(int) const { return INVALID; }
846
847      /// \brief An upper bound on the node IDs.
848      ///
849      /// Returns an upper bound on the node IDs.
850      int maxNodeId() const { return -1; }
851
852      /// \brief An upper bound on the edge IDs.
853      ///
854      /// Returns an upper bound on the edge IDs.
855      int maxEdgeId() const { return -1; }
856
857      /// \brief An upper bound on the arc IDs.
858      ///
859      /// Returns an upper bound on the arc IDs.
860      int maxArcId() const { return -1; }
861
862      /// \brief The direction of the arc.
863      ///
864      /// Returns \c true if the direction of the given arc is the same as
865      /// the inherent orientation of the represented edge.
866      bool direction(Arc) const { return true; }
867
868      /// \brief Direct the edge.
869      ///
870      /// Direct the given edge. The returned arc
871      /// represents the given edge and its direction comes
872      /// from the bool parameter. If it is \c true, then the direction
873      /// of the arc is the same as the inherent orientation of the edge.
874      Arc direct(Edge, bool) const {
875        return INVALID;
876      }
877
878      /// \brief Direct the edge.
879      ///
880      /// Direct the given edge. The returned arc represents the given
881      /// edge and its source node is the given node.
882      Arc direct(Edge, Node) const {
883        return INVALID;
884      }
885
886      /// \brief The oppositely directed arc.
887      ///
888      /// Returns the oppositely directed arc representing the same edge.
889      Arc oppositeArc(Arc) const { return INVALID; }
890
891      /// \brief The opposite node on the edge.
892      ///
893      /// Returns the opposite node on the given edge.
894      Node oppositeNode(Node, Edge) const { return INVALID; }
895
896      void first(Node&) const {}
897      void next(Node&) const {}
898
899      void first(Edge&) const {}
900      void next(Edge&) const {}
901
902      void first(Arc&) const {}
903      void next(Arc&) const {}
904
905      void firstOut(Arc&, Node) const {}
906      void nextOut(Arc&) const {}
907
908      void firstIn(Arc&, Node) const {}
909      void nextIn(Arc&) const {}
910
911      void firstInc(Edge &, bool &, const Node &) const {}
912      void nextInc(Edge &, bool &) const {}
913
914      // The second parameter is dummy.
915      Node fromId(int, Node) const { return INVALID; }
916      // The second parameter is dummy.
917      Edge fromId(int, Edge) const { return INVALID; }
918      // The second parameter is dummy.
919      Arc fromId(int, Arc) const { return INVALID; }
920
921      // Dummy parameter.
922      int maxId(Node) const { return -1; }
923      // Dummy parameter.
924      int maxId(Edge) const { return -1; }
925      // Dummy parameter.
926      int maxId(Arc) const { return -1; }
927
928      /// \brief The base node of the iterator.
929      ///
930      /// Returns the base node of the given incident edge iterator.
931      Node baseNode(IncEdgeIt) const { return INVALID; }
932
933      /// \brief The running node of the iterator.
934      ///
935      /// Returns the running node of the given incident edge iterator.
936      Node runningNode(IncEdgeIt) const { return INVALID; }
937
938      /// \brief The base node of the iterator.
939      ///
940      /// Returns the base node of the given outgoing arc iterator
941      /// (i.e. the source node of the corresponding arc).
942      Node baseNode(OutArcIt) const { return INVALID; }
943
944      /// \brief The running node of the iterator.
945      ///
946      /// Returns the running node of the given outgoing arc iterator
947      /// (i.e. the target node of the corresponding arc).
948      Node runningNode(OutArcIt) const { return INVALID; }
949
950      /// \brief The base node of the iterator.
951      ///
952      /// Returns the base node of the given incoming arc iterator
953      /// (i.e. the target node of the corresponding arc).
954      Node baseNode(InArcIt) const { return INVALID; }
955
956      /// \brief The running node of the iterator.
957      ///
958      /// Returns the running node of the given incoming arc iterator
959      /// (i.e. the source node of the corresponding arc).
960      Node runningNode(InArcIt) const { return INVALID; }
961
962      template <typename _Graph>
963      struct Constraints {
964        void constraints() {
965          checkConcept<BaseGraphComponent, _Graph>();
966          checkConcept<IterableGraphComponent<>, _Graph>();
967          checkConcept<IDableGraphComponent<>, _Graph>();
968          checkConcept<MappableGraphComponent<>, _Graph>();
969        }
970      };
971
972    };
973
974  }
975
976}
977
978#endif
Note: See TracBrowser for help on using the repository browser.