1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 ///\ingroup graph_concepts
21 ///\brief The concept of undirected graphs.
23 #ifndef LEMON_CONCEPTS_GRAPH_H
24 #define LEMON_CONCEPTS_GRAPH_H
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>
35 /// \ingroup graph_concepts
37 /// \brief Class describing the concept of undirected graphs.
39 /// This class describes the common interface of all undirected
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.
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,
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.
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.
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&) {}
83 /// Default constructor.
86 /// \brief Undirected graphs should be tagged with \c UndirectedTag.
88 /// Undirected graphs should be tagged with \c UndirectedTag.
90 /// This tag helps the \c enable_if technics to make compile time
91 /// specializations for undirected graphs.
92 typedef True UndirectedTag;
94 /// The node type of the graph
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.
101 /// Default constructor
103 /// Default constructor.
104 /// \warning It sets the object to an undefined value.
106 /// Copy constructor.
108 /// Copy constructor.
110 Node(const Node&) { }
111 /// Assignment operator
113 /// Assignment operator.
115 const Node &operator=(const Node&) { return *this; }
117 /// %Invalid constructor \& conversion.
119 /// Initializes the object to be invalid.
120 /// \sa Invalid for more details.
122 /// Equality operator
124 /// Equality operator.
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; }
130 /// Inequality operator
132 /// Inequality operator.
133 bool operator!=(Node) const { return true; }
135 /// Artificial ordering operator.
137 /// Artificial ordering operator.
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; }
146 /// Iterator class for the nodes.
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:
153 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
155 class NodeIt : public Node {
157 /// Default constructor
159 /// Default constructor.
160 /// \warning It sets the iterator to an undefined value.
162 /// Copy constructor.
164 /// Copy constructor.
166 NodeIt(const NodeIt& n) : Node(n) { }
167 /// Assignment operator
169 /// Assignment operator.
171 const NodeIt &operator=(const NodeIt&) { return *this; }
173 /// %Invalid constructor \& conversion.
175 /// Initializes the iterator to be invalid.
176 /// \sa Invalid for more details.
178 /// Sets the iterator to the first node.
180 /// Sets the iterator to the first node of the given digraph.
182 explicit NodeIt(const Graph&) { }
183 /// Sets the iterator to the given node.
185 /// Sets the iterator to the given node of the given digraph.
187 NodeIt(const Graph&, const Node&) { }
190 /// Assign the iterator to the next node.
192 NodeIt& operator++() { return *this; }
195 /// \brief Gets the collection of the nodes of the graph.
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:
204 /// for(auto v: g.nodes())
207 /// //Using an STL algorithm:
208 /// copy(g.nodes().begin(), g.nodes().end(), vect.begin());
210 LemonRangeWrapper1<NodeIt, Graph> nodes() const {
211 return LemonRangeWrapper1<NodeIt, Graph>(*this);
215 /// The edge type of the graph
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.
222 /// Default constructor
224 /// Default constructor.
225 /// \warning It sets the object to an undefined value.
227 /// Copy constructor.
229 /// Copy constructor.
231 Edge(const Edge&) { }
232 /// Assignment operator
234 /// Assignment operator.
236 const Edge &operator=(const Edge&) { return *this; }
238 /// %Invalid constructor \& conversion.
240 /// Initializes the object to be invalid.
241 /// \sa Invalid for more details.
243 /// Equality operator
245 /// Equality operator.
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
252 /// Inequality operator.
253 bool operator!=(Edge) const { return true; }
255 /// Artificial ordering operator.
257 /// Artificial ordering operator.
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; }
265 /// Iterator class for the edges.
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:
272 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
274 class EdgeIt : public Edge {
276 /// Default constructor
278 /// Default constructor.
279 /// \warning It sets the iterator to an undefined value.
281 /// Copy constructor.
283 /// Copy constructor.
285 EdgeIt(const EdgeIt& e) : Edge(e) { }
286 /// Assignment operator
288 /// Assignment operator.
290 const EdgeIt &operator=(const EdgeIt&) { return *this; }
292 /// %Invalid constructor \& conversion.
294 /// Initializes the iterator to be invalid.
295 /// \sa Invalid for more details.
297 /// Sets the iterator to the first edge.
299 /// Sets the iterator to the first edge of the given graph.
301 explicit EdgeIt(const Graph&) { }
302 /// Sets the iterator to the given edge.
304 /// Sets the iterator to the given edge of the given graph.
306 EdgeIt(const Graph&, const Edge&) { }
309 /// Assign the iterator to the next edge.
311 EdgeIt& operator++() { return *this; }
314 /// \brief Gets the collection of the edges of the graph.
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:
324 /// for(auto e: g.edges())
327 /// //Using an STL algorithm:
328 /// copy(g.edges().begin(), g.edges().end(), vect.begin());
330 LemonRangeWrapper1<EdgeIt, Graph> edges() const {
331 return LemonRangeWrapper1<EdgeIt, Graph>(*this);
335 /// Iterator class for the incident edges of a node.
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.
345 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
348 /// \warning Loop edges will be iterated twice.
349 class IncEdgeIt : public Edge {
351 /// Default constructor
353 /// Default constructor.
354 /// \warning It sets the iterator to an undefined value.
356 /// Copy constructor.
358 /// Copy constructor.
360 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
361 /// Assignment operator
363 /// Assignment operator.
365 const IncEdgeIt &operator=(const IncEdgeIt&) { return *this; }
367 /// %Invalid constructor \& conversion.
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.
374 /// Sets the iterator to the first incident edge of the given node.
376 IncEdgeIt(const Graph&, const Node&) { }
377 /// Sets the iterator to the given edge.
379 /// Sets the iterator to the given edge of the given graph.
381 IncEdgeIt(const Graph&, const Edge&) { }
382 /// Next incident edge
384 /// Assign the iterator to the next incident edge
385 /// of the corresponding node.
386 IncEdgeIt& operator++() { return *this; }
389 /// \brief Gets the collection of the incident undirected edges
390 /// of a certain node of the graph.
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:
400 /// for(auto e: g.incEdges(u))
403 /// //Using an STL algorithm:
404 /// copy(g.incEdges(u).begin(), g.incEdges(u).end(), vect.begin());
406 LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
407 return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
411 /// The arc type of the graph
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.
418 /// Default constructor
420 /// Default constructor.
421 /// \warning It sets the object to an undefined value.
423 /// Copy constructor.
425 /// Copy constructor.
428 /// Assignment operator
430 /// Assignment operator.
432 const Arc &operator=(const Arc&) { return *this; }
434 /// %Invalid constructor \& conversion.
436 /// Initializes the object to be invalid.
437 /// \sa Invalid for more details.
439 /// Equality operator
441 /// Equality operator.
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
448 /// Inequality operator.
449 bool operator!=(Arc) const { return true; }
451 /// Artificial ordering operator.
453 /// Artificial ordering operator.
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; }
460 /// Converison to \c Edge
462 /// Converison to \c Edge.
464 operator Edge() const { return Edge(); }
467 /// Iterator class for the arcs.
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:
474 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
476 class ArcIt : public Arc {
478 /// Default constructor
480 /// Default constructor.
481 /// \warning It sets the iterator to an undefined value.
483 /// Copy constructor.
485 /// Copy constructor.
487 ArcIt(const ArcIt& e) : Arc(e) { }
488 /// Assignment operator
490 /// Assignment operator.
492 const ArcIt &operator=(const ArcIt&) { return *this; }
494 /// %Invalid constructor \& conversion.
496 /// Initializes the iterator to be invalid.
497 /// \sa Invalid for more details.
499 /// Sets the iterator to the first arc.
501 /// Sets the iterator to the first arc of the given graph.
503 explicit ArcIt(const Graph &g) {
504 ::lemon::ignore_unused_variable_warning(g);
506 /// Sets the iterator to the given arc.
508 /// Sets the iterator to the given arc of the given graph.
510 ArcIt(const Graph&, const Arc&) { }
513 /// Assign the iterator to the next arc.
515 ArcIt& operator++() { return *this; }
518 /// \brief Gets the collection of the directed arcs of the graph.
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:
528 /// for(auto a: g.arcs())
531 /// //Using an STL algorithm:
532 /// copy(g.arcs().begin(), g.arcs().end(), vect.begin());
534 LemonRangeWrapper1<ArcIt, Graph> arcs() const {
535 return LemonRangeWrapper1<ArcIt, Graph>(*this);
539 /// Iterator class for the outgoing arcs of a node.
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.
548 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
550 class OutArcIt : public Arc {
552 /// Default constructor
554 /// Default constructor.
555 /// \warning It sets the iterator to an undefined value.
557 /// Copy constructor.
559 /// Copy constructor.
561 OutArcIt(const OutArcIt& e) : Arc(e) { }
562 /// Assignment operator
564 /// Assignment operator.
566 const OutArcIt &operator=(const OutArcIt&) { return *this; }
568 /// %Invalid constructor \& conversion.
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.
575 /// Sets the iterator to the first outgoing arc of the given node.
577 OutArcIt(const Graph& n, const Node& g) {
578 ::lemon::ignore_unused_variable_warning(n);
579 ::lemon::ignore_unused_variable_warning(g);
581 /// Sets the iterator to the given arc.
583 /// Sets the iterator to the given arc of the given graph.
585 OutArcIt(const Graph&, const Arc&) { }
586 /// Next outgoing arc
588 /// Assign the iterator to the next
589 /// outgoing arc of the corresponding node.
590 OutArcIt& operator++() { return *this; }
593 /// \brief Gets the collection of the outgoing directed arcs of a
594 /// certain node of the graph.
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:
603 /// for(auto a: g.outArcs(u))
606 /// //Using an STL algorithm:
607 /// copy(g.outArcs(u).begin(), g.outArcs(u).end(), vect.begin());
609 LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
610 return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
614 /// Iterator class for the incoming arcs of a node.
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.
623 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
625 class InArcIt : public Arc {
627 /// Default constructor
629 /// Default constructor.
630 /// \warning It sets the iterator to an undefined value.
632 /// Copy constructor.
634 /// Copy constructor.
636 InArcIt(const InArcIt& e) : Arc(e) { }
637 /// Assignment operator
639 /// Assignment operator.
641 const InArcIt &operator=(const InArcIt&) { return *this; }
643 /// %Invalid constructor \& conversion.
645 /// Initializes the iterator to be invalid.
646 /// \sa Invalid for more details.
648 /// Sets the iterator to the first incoming arc.
650 /// Sets the iterator to the first incoming arc of the given node.
652 InArcIt(const Graph& g, const Node& n) {
653 ::lemon::ignore_unused_variable_warning(n);
654 ::lemon::ignore_unused_variable_warning(g);
656 /// Sets the iterator to the given arc.
658 /// Sets the iterator to the given arc of the given graph.
660 InArcIt(const Graph&, const Arc&) { }
661 /// Next incoming arc
663 /// Assign the iterator to the next
664 /// incoming arc of the corresponding node.
665 InArcIt& operator++() { return *this; }
668 /// \brief Gets the collection of the incoming directed arcs of
669 /// a certain node of the graph.
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:
678 /// for(auto a: g.inArcs(u))
681 /// //Using an STL algorithm:
682 /// copy(g.inArcs(u).begin(), g.inArcs(u).end(), vect.begin());
684 LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
685 return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
688 /// \brief Standard graph map type for the nodes.
690 /// Standard graph map type for the nodes.
691 /// It conforms to the ReferenceMap concept.
693 class NodeMap : public ReferenceMap<Node, T, T&, const T&>
698 explicit NodeMap(const Graph&) { }
699 /// Constructor with given initial value
700 NodeMap(const Graph&, T) { }
704 NodeMap(const NodeMap& nm) :
705 ReferenceMap<Node, T, T&, const T&>(nm) { }
706 ///Assignment operator
707 NodeMap& operator=(const NodeMap&) {
710 ///Template Assignment operator
711 template <typename CMap>
712 NodeMap& operator=(const CMap&) {
713 checkConcept<ReadMap<Node, T>, CMap>();
718 /// \brief Standard graph map type for the arcs.
720 /// Standard graph map type for the arcs.
721 /// It conforms to the ReferenceMap concept.
723 class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
728 explicit ArcMap(const Graph&) { }
729 /// Constructor with given initial value
730 ArcMap(const Graph&, T) { }
734 ArcMap(const ArcMap& em) :
735 ReferenceMap<Arc, T, T&, const T&>(em) { }
736 ///Assignment operator
737 ArcMap& operator=(const ArcMap&) {
740 ///Template Assignment operator
741 template <typename CMap>
742 ArcMap& operator=(const CMap&) {
743 checkConcept<ReadMap<Arc, T>, CMap>();
748 /// \brief Standard graph map type for the edges.
750 /// Standard graph map type for the edges.
751 /// It conforms to the ReferenceMap concept.
753 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
758 explicit EdgeMap(const Graph&) { }
759 /// Constructor with given initial value
760 EdgeMap(const Graph&, T) { }
764 EdgeMap(const EdgeMap& em) :
765 ReferenceMap<Edge, T, T&, const T&>(em) {}
766 ///Assignment operator
767 EdgeMap& operator=(const EdgeMap&) {
770 ///Template Assignment operator
771 template <typename CMap>
772 EdgeMap& operator=(const CMap&) {
773 checkConcept<ReadMap<Edge, T>, CMap>();
778 /// \brief The first node of the edge.
780 /// Returns the first node of the given edge.
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.
789 Node u(Edge) const { return INVALID; }
791 /// \brief The second node of the edge.
793 /// Returns the second node of the given edge.
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.
802 Node v(Edge) const { return INVALID; }
804 /// \brief The source node of the arc.
806 /// Returns the source node of the given arc.
807 Node source(Arc) const { return INVALID; }
809 /// \brief The target node of the arc.
811 /// Returns the target node of the given arc.
812 Node target(Arc) const { return INVALID; }
814 /// \brief The ID of the node.
816 /// Returns the ID of the given node.
817 int id(Node) const { return -1; }
819 /// \brief The ID of the edge.
821 /// Returns the ID of the given edge.
822 int id(Edge) const { return -1; }
824 /// \brief The ID of the arc.
826 /// Returns the ID of the given arc.
827 int id(Arc) const { return -1; }
829 /// \brief The node with the given ID.
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; }
835 /// \brief The edge with the given ID.
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; }
841 /// \brief The arc with the given ID.
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; }
847 /// \brief An upper bound on the node IDs.
849 /// Returns an upper bound on the node IDs.
850 int maxNodeId() const { return -1; }
852 /// \brief An upper bound on the edge IDs.
854 /// Returns an upper bound on the edge IDs.
855 int maxEdgeId() const { return -1; }
857 /// \brief An upper bound on the arc IDs.
859 /// Returns an upper bound on the arc IDs.
860 int maxArcId() const { return -1; }
862 /// \brief The direction of the arc.
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; }
868 /// \brief Direct the edge.
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 {
878 /// \brief Direct the edge.
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 {
886 /// \brief The oppositely directed arc.
888 /// Returns the oppositely directed arc representing the same edge.
889 Arc oppositeArc(Arc) const { return INVALID; }
891 /// \brief The opposite node on the edge.
893 /// Returns the opposite node on the given edge.
894 Node oppositeNode(Node, Edge) const { return INVALID; }
896 void first(Node&) const {}
897 void next(Node&) const {}
899 void first(Edge&) const {}
900 void next(Edge&) const {}
902 void first(Arc&) const {}
903 void next(Arc&) const {}
905 void firstOut(Arc&, Node) const {}
906 void nextOut(Arc&) const {}
908 void firstIn(Arc&, Node) const {}
909 void nextIn(Arc&) const {}
911 void firstInc(Edge &, bool &, const Node &) const {}
912 void nextInc(Edge &, bool &) const {}
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; }
922 int maxId(Node) const { return -1; }
924 int maxId(Edge) const { return -1; }
926 int maxId(Arc) const { return -1; }
928 /// \brief The base node of the iterator.
930 /// Returns the base node of the given incident edge iterator.
931 Node baseNode(IncEdgeIt) const { return INVALID; }
933 /// \brief The running node of the iterator.
935 /// Returns the running node of the given incident edge iterator.
936 Node runningNode(IncEdgeIt) const { return INVALID; }
938 /// \brief The base node of the iterator.
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; }
944 /// \brief The running node of the iterator.
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; }
950 /// \brief The base node of the iterator.
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; }
956 /// \brief The running node of the iterator.
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; }
962 template <typename _Graph>
965 checkConcept<BaseGraphComponent, _Graph>();
966 checkConcept<IterableGraphComponent<>, _Graph>();
967 checkConcept<IDableGraphComponent<>, _Graph>();
968 checkConcept<MappableGraphComponent<>, _Graph>();