1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
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_BPGRAPH_H
24 #define LEMON_CONCEPTS_BPGRAPH_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>
34 /// \ingroup graph_concepts
36 /// \brief Class describing the concept of undirected bipartite graphs.
38 /// This class describes the common interface of all undirected
41 /// Like all concept classes, it only provides an interface
42 /// without any sensible implementation. So any general algorithm for
43 /// undirected bipartite graphs should compile with this class,
44 /// but it will not run properly, of course.
45 /// An actual graph implementation like \ref ListBpGraph or
46 /// \ref SmartBpGraph may have additional functionality.
48 /// The bipartite graphs also fulfill the concept of \ref Graph
49 /// "undirected graphs". Bipartite graphs provide a bipartition of
50 /// the node set, namely a red and blue set of the nodes. The
51 /// nodes can be iterated with the RedIt and BlueIt in the two
52 /// node sets. With RedMap and BlueMap values can be assigned to
53 /// the nodes in the two sets.
55 /// The edges of the graph cannot connect two nodes of the same
56 /// set. The edges inherent orientation is from the red nodes to
62 /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
63 BpGraph(const BpGraph&) {}
64 /// \brief Assignment of a graph to another one is \e not allowed.
65 /// Use bpGraphCopy instead.
66 void operator=(const BpGraph&) {}
69 /// Default constructor.
72 /// \brief Undirected graphs should be tagged with \c UndirectedTag.
74 /// Undirected graphs should be tagged with \c UndirectedTag.
76 /// This tag helps the \c enable_if technics to make compile time
77 /// specializations for undirected graphs.
78 typedef True UndirectedTag;
80 /// The node type of the graph
82 /// This class identifies a node of the graph. It also serves
83 /// as a base class of the node iterators,
84 /// thus they convert to this type.
87 /// Default constructor
89 /// Default constructor.
90 /// \warning It sets the object to an undefined value.
98 /// %Invalid constructor \& conversion.
100 /// Initializes the object to be invalid.
101 /// \sa Invalid for more details.
103 /// Equality operator
105 /// Equality operator.
107 /// Two iterators are equal if and only if they point to the
108 /// same object or both are \c INVALID.
109 bool operator==(Node) const { return true; }
111 /// Inequality operator
113 /// Inequality operator.
114 bool operator!=(Node) const { return true; }
116 /// Artificial ordering operator.
118 /// Artificial ordering operator.
120 /// \note This operator only has to define some strict ordering of
121 /// the items; this order has nothing to do with the iteration
122 /// ordering of the items.
123 bool operator<(Node) const { return false; }
127 /// Class to represent red nodes.
129 /// This class represents the red nodes of the graph. It does
130 /// not supposed to be used directly, because the nodes can be
131 /// represented as Node instances. This class can be used as
132 /// template parameter for special map classes.
133 class RedNode : public Node {
135 /// Default constructor
137 /// Default constructor.
138 /// \warning It sets the object to an undefined value.
140 /// Copy constructor.
142 /// Copy constructor.
144 RedNode(const RedNode&) : Node() { }
146 /// %Invalid constructor \& conversion.
148 /// Initializes the object to be invalid.
149 /// \sa Invalid for more details.
154 /// Class to represent blue nodes.
156 /// This class represents the blue nodes of the graph. It does
157 /// not supposed to be used directly, because the nodes can be
158 /// represented as Node instances. This class can be used as
159 /// template parameter for special map classes.
160 class BlueNode : public Node {
162 /// Default constructor
164 /// Default constructor.
165 /// \warning It sets the object to an undefined value.
167 /// Copy constructor.
169 /// Copy constructor.
171 BlueNode(const BlueNode&) : Node() { }
173 /// %Invalid constructor \& conversion.
175 /// Initializes the object to be invalid.
176 /// \sa Invalid for more details.
177 BlueNode(Invalid) { }
181 /// Iterator class for the red nodes.
183 /// This iterator goes through each red node of the graph.
184 /// Its usage is quite simple, for example, you can count the number
185 /// of red nodes in a graph \c g of type \c %BpGraph like this:
188 /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
190 class RedIt : public RedNode {
192 /// Default constructor
194 /// Default constructor.
195 /// \warning It sets the iterator to an undefined value.
197 /// Copy constructor.
199 /// Copy constructor.
201 RedIt(const RedIt& n) : RedNode(n) { }
202 /// %Invalid constructor \& conversion.
204 /// Initializes the iterator to be invalid.
205 /// \sa Invalid for more details.
207 /// Sets the iterator to the first red node.
209 /// Sets the iterator to the first red node of the given
211 explicit RedIt(const BpGraph&) { }
212 /// Sets the iterator to the given red node.
214 /// Sets the iterator to the given red node of the given
216 RedIt(const BpGraph&, const RedNode&) { }
219 /// Assign the iterator to the next red node.
221 RedIt& operator++() { return *this; }
224 /// Iterator class for the blue nodes.
226 /// This iterator goes through each blue node of the graph.
227 /// Its usage is quite simple, for example, you can count the number
228 /// of blue nodes in a graph \c g of type \c %BpGraph like this:
231 /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
233 class BlueIt : public BlueNode {
235 /// Default constructor
237 /// Default constructor.
238 /// \warning It sets the iterator to an undefined value.
240 /// Copy constructor.
242 /// Copy constructor.
244 BlueIt(const BlueIt& n) : BlueNode(n) { }
245 /// %Invalid constructor \& conversion.
247 /// Initializes the iterator to be invalid.
248 /// \sa Invalid for more details.
250 /// Sets the iterator to the first blue node.
252 /// Sets the iterator to the first blue node of the given
254 explicit BlueIt(const BpGraph&) { }
255 /// Sets the iterator to the given blue node.
257 /// Sets the iterator to the given blue node of the given
259 BlueIt(const BpGraph&, const BlueNode&) { }
262 /// Assign the iterator to the next blue node.
264 BlueIt& operator++() { return *this; }
267 /// Iterator class for the nodes.
269 /// This iterator goes through each node of the graph.
270 /// Its usage is quite simple, for example, you can count the number
271 /// of nodes in a graph \c g of type \c %BpGraph like this:
274 /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
276 class NodeIt : public Node {
278 /// Default constructor
280 /// Default constructor.
281 /// \warning It sets the iterator to an undefined value.
283 /// Copy constructor.
285 /// Copy constructor.
287 NodeIt(const NodeIt& n) : Node(n) { }
288 /// %Invalid constructor \& conversion.
290 /// Initializes the iterator to be invalid.
291 /// \sa Invalid for more details.
293 /// Sets the iterator to the first node.
295 /// Sets the iterator to the first node of the given digraph.
297 explicit NodeIt(const BpGraph&) { }
298 /// Sets the iterator to the given node.
300 /// Sets the iterator to the given node of the given digraph.
302 NodeIt(const BpGraph&, const Node&) { }
305 /// Assign the iterator to the next node.
307 NodeIt& operator++() { return *this; }
311 /// The edge type of the graph
313 /// This class identifies an edge of the graph. It also serves
314 /// as a base class of the edge iterators,
315 /// thus they will convert to this type.
318 /// Default constructor
320 /// Default constructor.
321 /// \warning It sets the object to an undefined value.
323 /// Copy constructor.
325 /// Copy constructor.
327 Edge(const Edge&) { }
328 /// %Invalid constructor \& conversion.
330 /// Initializes the object to be invalid.
331 /// \sa Invalid for more details.
333 /// Equality operator
335 /// Equality operator.
337 /// Two iterators are equal if and only if they point to the
338 /// same object or both are \c INVALID.
339 bool operator==(Edge) const { return true; }
340 /// Inequality operator
342 /// Inequality operator.
343 bool operator!=(Edge) const { return true; }
345 /// Artificial ordering operator.
347 /// Artificial ordering operator.
349 /// \note This operator only has to define some strict ordering of
350 /// the edges; this order has nothing to do with the iteration
351 /// ordering of the edges.
352 bool operator<(Edge) const { return false; }
355 /// Iterator class for the edges.
357 /// This iterator goes through each edge of the graph.
358 /// Its usage is quite simple, for example, you can count the number
359 /// of edges in a graph \c g of type \c %BpGraph as follows:
362 /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
364 class EdgeIt : public Edge {
366 /// Default constructor
368 /// Default constructor.
369 /// \warning It sets the iterator to an undefined value.
371 /// Copy constructor.
373 /// Copy constructor.
375 EdgeIt(const EdgeIt& e) : Edge(e) { }
376 /// %Invalid constructor \& conversion.
378 /// Initializes the iterator to be invalid.
379 /// \sa Invalid for more details.
381 /// Sets the iterator to the first edge.
383 /// Sets the iterator to the first edge of the given graph.
385 explicit EdgeIt(const BpGraph&) { }
386 /// Sets the iterator to the given edge.
388 /// Sets the iterator to the given edge of the given graph.
390 EdgeIt(const BpGraph&, const Edge&) { }
393 /// Assign the iterator to the next edge.
395 EdgeIt& operator++() { return *this; }
398 /// Iterator class for the incident edges of a node.
400 /// This iterator goes trough the incident undirected edges
401 /// of a certain node of a graph.
402 /// Its usage is quite simple, for example, you can compute the
403 /// degree (i.e. the number of incident edges) of a node \c n
404 /// in a graph \c g of type \c %BpGraph as follows.
408 /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
411 /// \warning Loop edges will be iterated twice.
412 class IncEdgeIt : public Edge {
414 /// Default constructor
416 /// Default constructor.
417 /// \warning It sets the iterator to an undefined value.
419 /// Copy constructor.
421 /// Copy constructor.
423 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
424 /// %Invalid constructor \& conversion.
426 /// Initializes the iterator to be invalid.
427 /// \sa Invalid for more details.
428 IncEdgeIt(Invalid) { }
429 /// Sets the iterator to the first incident edge.
431 /// Sets the iterator to the first incident edge of the given node.
433 IncEdgeIt(const BpGraph&, const Node&) { }
434 /// Sets the iterator to the given edge.
436 /// Sets the iterator to the given edge of the given graph.
438 IncEdgeIt(const BpGraph&, const Edge&) { }
439 /// Next incident edge
441 /// Assign the iterator to the next incident edge
442 /// of the corresponding node.
443 IncEdgeIt& operator++() { return *this; }
446 /// The arc type of the graph
448 /// This class identifies a directed arc of the graph. It also serves
449 /// as a base class of the arc iterators,
450 /// thus they will convert to this type.
453 /// Default constructor
455 /// Default constructor.
456 /// \warning It sets the object to an undefined value.
458 /// Copy constructor.
460 /// Copy constructor.
463 /// %Invalid constructor \& conversion.
465 /// Initializes the object to be invalid.
466 /// \sa Invalid for more details.
468 /// Equality operator
470 /// Equality operator.
472 /// Two iterators are equal if and only if they point to the
473 /// same object or both are \c INVALID.
474 bool operator==(Arc) const { return true; }
475 /// Inequality operator
477 /// Inequality operator.
478 bool operator!=(Arc) const { return true; }
480 /// Artificial ordering operator.
482 /// Artificial ordering operator.
484 /// \note This operator only has to define some strict ordering of
485 /// the arcs; this order has nothing to do with the iteration
486 /// ordering of the arcs.
487 bool operator<(Arc) const { return false; }
489 /// Converison to \c Edge
491 /// Converison to \c Edge.
493 operator Edge() const { return Edge(); }
496 /// Iterator class for the arcs.
498 /// This iterator goes through each directed arc of the graph.
499 /// Its usage is quite simple, for example, you can count the number
500 /// of arcs in a graph \c g of type \c %BpGraph as follows:
503 /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
505 class ArcIt : public Arc {
507 /// Default constructor
509 /// Default constructor.
510 /// \warning It sets the iterator to an undefined value.
512 /// Copy constructor.
514 /// Copy constructor.
516 ArcIt(const ArcIt& e) : Arc(e) { }
517 /// %Invalid constructor \& conversion.
519 /// Initializes the iterator to be invalid.
520 /// \sa Invalid for more details.
522 /// Sets the iterator to the first arc.
524 /// Sets the iterator to the first arc of the given graph.
526 explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
527 /// Sets the iterator to the given arc.
529 /// Sets the iterator to the given arc of the given graph.
531 ArcIt(const BpGraph&, const Arc&) { }
534 /// Assign the iterator to the next arc.
536 ArcIt& operator++() { return *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 %BpGraph 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 /// %Invalid constructor \& conversion.
564 /// Initializes the iterator to be invalid.
565 /// \sa Invalid for more details.
566 OutArcIt(Invalid) { }
567 /// Sets the iterator to the first outgoing arc.
569 /// Sets the iterator to the first outgoing arc of the given node.
571 OutArcIt(const BpGraph& n, const Node& g) {
572 ignore_unused_variable_warning(n);
573 ignore_unused_variable_warning(g);
575 /// Sets the iterator to the given arc.
577 /// Sets the iterator to the given arc of the given graph.
579 OutArcIt(const BpGraph&, const Arc&) { }
580 /// Next outgoing arc
582 /// Assign the iterator to the next
583 /// outgoing arc of the corresponding node.
584 OutArcIt& operator++() { return *this; }
587 /// Iterator class for the incoming arcs of a node.
589 /// This iterator goes trough the \e incoming directed arcs of a
590 /// certain node of a graph.
591 /// Its usage is quite simple, for example, you can count the number
592 /// of incoming arcs of a node \c n
593 /// in a graph \c g of type \c %BpGraph as follows.
596 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
598 class InArcIt : public Arc {
600 /// Default constructor
602 /// Default constructor.
603 /// \warning It sets the iterator to an undefined value.
605 /// Copy constructor.
607 /// Copy constructor.
609 InArcIt(const InArcIt& e) : Arc(e) { }
610 /// %Invalid constructor \& conversion.
612 /// Initializes the iterator to be invalid.
613 /// \sa Invalid for more details.
615 /// Sets the iterator to the first incoming arc.
617 /// Sets the iterator to the first incoming arc of the given node.
619 InArcIt(const BpGraph& g, const Node& n) {
620 ignore_unused_variable_warning(n);
621 ignore_unused_variable_warning(g);
623 /// Sets the iterator to the given arc.
625 /// Sets the iterator to the given arc of the given graph.
627 InArcIt(const BpGraph&, const Arc&) { }
628 /// Next incoming arc
630 /// Assign the iterator to the next
631 /// incoming arc of the corresponding node.
632 InArcIt& operator++() { return *this; }
635 /// \brief Standard graph map type for the nodes.
637 /// Standard graph map type for the nodes.
638 /// It conforms to the ReferenceMap concept.
640 class NodeMap : public ReferenceMap<Node, T, T&, const T&>
645 explicit NodeMap(const BpGraph&) { }
646 /// Constructor with given initial value
647 NodeMap(const BpGraph&, T) { }
651 NodeMap(const NodeMap& nm) :
652 ReferenceMap<Node, T, T&, const T&>(nm) { }
653 ///Assignment operator
654 template <typename CMap>
655 NodeMap& operator=(const CMap&) {
656 checkConcept<ReadMap<Node, T>, CMap>();
661 /// \brief Standard graph map type for the red nodes.
663 /// Standard graph map type for the red nodes.
664 /// It conforms to the ReferenceMap concept.
666 class RedMap : public ReferenceMap<Node, T, T&, const T&>
671 explicit RedMap(const BpGraph&) { }
672 /// Constructor with given initial value
673 RedMap(const BpGraph&, T) { }
677 RedMap(const RedMap& nm) :
678 ReferenceMap<Node, T, T&, const T&>(nm) { }
679 ///Assignment operator
680 template <typename CMap>
681 RedMap& operator=(const CMap&) {
682 checkConcept<ReadMap<Node, T>, CMap>();
687 /// \brief Standard graph map type for the blue nodes.
689 /// Standard graph map type for the blue nodes.
690 /// It conforms to the ReferenceMap concept.
692 class BlueMap : public ReferenceMap<Node, T, T&, const T&>
697 explicit BlueMap(const BpGraph&) { }
698 /// Constructor with given initial value
699 BlueMap(const BpGraph&, T) { }
703 BlueMap(const BlueMap& nm) :
704 ReferenceMap<Node, T, T&, const T&>(nm) { }
705 ///Assignment operator
706 template <typename CMap>
707 BlueMap& operator=(const CMap&) {
708 checkConcept<ReadMap<Node, T>, CMap>();
713 /// \brief Standard graph map type for the arcs.
715 /// Standard graph map type for the arcs.
716 /// It conforms to the ReferenceMap concept.
718 class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
723 explicit ArcMap(const BpGraph&) { }
724 /// Constructor with given initial value
725 ArcMap(const BpGraph&, T) { }
729 ArcMap(const ArcMap& em) :
730 ReferenceMap<Arc, T, T&, const T&>(em) { }
731 ///Assignment operator
732 template <typename CMap>
733 ArcMap& operator=(const CMap&) {
734 checkConcept<ReadMap<Arc, T>, CMap>();
739 /// \brief Standard graph map type for the edges.
741 /// Standard graph map type for the edges.
742 /// It conforms to the ReferenceMap concept.
744 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
749 explicit EdgeMap(const BpGraph&) { }
750 /// Constructor with given initial value
751 EdgeMap(const BpGraph&, T) { }
755 EdgeMap(const EdgeMap& em) :
756 ReferenceMap<Edge, T, T&, const T&>(em) {}
757 ///Assignment operator
758 template <typename CMap>
759 EdgeMap& operator=(const CMap&) {
760 checkConcept<ReadMap<Edge, T>, CMap>();
765 /// \brief Gives back %true for red nodes.
767 /// Gives back %true for red nodes.
768 bool red(const Node&) const { return true; }
770 /// \brief Gives back %true for blue nodes.
772 /// Gives back %true for blue nodes.
773 bool blue(const Node&) const { return true; }
775 /// \brief Converts the node to red node object.
777 /// This class is converts unsafely the node to red node
778 /// object. It should be called only if the node is from the red
779 /// partition or INVALID.
780 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
782 /// \brief Converts the node to blue node object.
784 /// This class is converts unsafely the node to blue node
785 /// object. It should be called only if the node is from the red
786 /// partition or INVALID.
787 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
789 /// \brief Converts the node to red node object.
791 /// This class is converts safely the node to red node
792 /// object. If the node is not from the red partition, then it
794 RedNode asRedNode(const Node&) const { return RedNode(); }
796 /// \brief Converts the node to blue node object.
798 /// This class is converts unsafely the node to blue node
799 /// object. If the node is not from the blue partition, then it
801 BlueNode asBlueNode(const Node&) const { return BlueNode(); }
803 /// \brief Convert the node to either red or blue node.
805 /// If the node is from the red partition then it is returned in
806 /// first and second is INVALID. If the node is from the blue
807 /// partition then it is returned in second and first is
808 /// INVALID. If the node INVALID then both first and second are
809 /// INVALID in the return value.
810 std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
811 return std::make_pair(RedNode(), BlueNode());
814 /// \brief Gives back the red end node of the edge.
816 /// Gives back the red end node of the edge.
817 RedNode redNode(const Edge&) const { return RedNode(); }
819 /// \brief Gives back the blue end node of the edge.
821 /// Gives back the blue end node of the edge.
822 BlueNode blueNode(const Edge&) const { return BlueNode(); }
824 /// \brief The first node of the edge.
826 /// It is a synonim for the \c redNode().
827 Node u(Edge) const { return INVALID; }
829 /// \brief The second node of the edge.
831 /// It is a synonim for the \c blueNode().
832 Node v(Edge) const { return INVALID; }
834 /// \brief The source node of the arc.
836 /// Returns the source node of the given arc.
837 Node source(Arc) const { return INVALID; }
839 /// \brief The target node of the arc.
841 /// Returns the target node of the given arc.
842 Node target(Arc) const { return INVALID; }
844 /// \brief The ID of the node.
846 /// Returns the ID of the given node.
847 int id(Node) const { return -1; }
849 /// \brief The red ID of the node.
851 /// Returns the red ID of the given node.
852 int id(RedNode) const { return -1; }
854 /// \brief The blue ID of the node.
856 /// Returns the blue ID of the given node.
857 int id(BlueNode) const { return -1; }
859 /// \brief The ID of the edge.
861 /// Returns the ID of the given edge.
862 int id(Edge) const { return -1; }
864 /// \brief The ID of the arc.
866 /// Returns the ID of the given arc.
867 int id(Arc) const { return -1; }
869 /// \brief The node with the given ID.
871 /// Returns the node with the given ID.
872 /// \pre The argument should be a valid node ID in the graph.
873 Node nodeFromId(int) const { return INVALID; }
875 /// \brief The edge with the given ID.
877 /// Returns the edge with the given ID.
878 /// \pre The argument should be a valid edge ID in the graph.
879 Edge edgeFromId(int) const { return INVALID; }
881 /// \brief The arc with the given ID.
883 /// Returns the arc with the given ID.
884 /// \pre The argument should be a valid arc ID in the graph.
885 Arc arcFromId(int) const { return INVALID; }
887 /// \brief An upper bound on the node IDs.
889 /// Returns an upper bound on the node IDs.
890 int maxNodeId() const { return -1; }
892 /// \brief An upper bound on the red IDs.
894 /// Returns an upper bound on the red IDs.
895 int maxRedId() const { return -1; }
897 /// \brief An upper bound on the blue IDs.
899 /// Returns an upper bound on the blue IDs.
900 int maxBlueId() const { return -1; }
902 /// \brief An upper bound on the edge IDs.
904 /// Returns an upper bound on the edge IDs.
905 int maxEdgeId() const { return -1; }
907 /// \brief An upper bound on the arc IDs.
909 /// Returns an upper bound on the arc IDs.
910 int maxArcId() const { return -1; }
912 /// \brief The direction of the arc.
914 /// Returns \c true if the given arc goes from a red node to a blue node.
915 bool direction(Arc) const { return true; }
917 /// \brief Direct the edge.
919 /// Direct the given edge. The returned arc
920 /// represents the given edge and its direction comes
921 /// from the bool parameter. If it is \c true, then the source of the node
922 /// will be a red node.
923 Arc direct(Edge, bool) const {
927 /// \brief Direct the edge.
929 /// Direct the given edge. The returned arc represents the given
930 /// edge and its source node is the given node.
931 Arc direct(Edge, Node) const {
935 /// \brief The oppositely directed arc.
937 /// Returns the oppositely directed arc representing the same edge.
938 Arc oppositeArc(Arc) const { return INVALID; }
940 /// \brief The opposite node on the edge.
942 /// Returns the opposite node on the given edge.
943 Node oppositeNode(Node, Edge) const { return INVALID; }
945 void first(Node&) const {}
946 void next(Node&) const {}
948 void firstRed(RedNode&) const {}
949 void nextRed(RedNode&) const {}
951 void firstBlue(BlueNode&) const {}
952 void nextBlue(BlueNode&) const {}
954 void first(Edge&) const {}
955 void next(Edge&) const {}
957 void first(Arc&) const {}
958 void next(Arc&) const {}
960 void firstOut(Arc&, Node) const {}
961 void nextOut(Arc&) const {}
963 void firstIn(Arc&, Node) const {}
964 void nextIn(Arc&) const {}
966 void firstInc(Edge &, bool &, const Node &) const {}
967 void nextInc(Edge &, bool &) const {}
969 // The second parameter is dummy.
970 Node fromId(int, Node) const { return INVALID; }
971 // The second parameter is dummy.
972 Edge fromId(int, Edge) const { return INVALID; }
973 // The second parameter is dummy.
974 Arc fromId(int, Arc) const { return INVALID; }
977 int maxId(Node) const { return -1; }
979 int maxId(RedNode) const { return -1; }
981 int maxId(BlueNode) const { return -1; }
983 int maxId(Edge) const { return -1; }
985 int maxId(Arc) const { return -1; }
987 /// \brief The base node of the iterator.
989 /// Returns the base node of the given incident edge iterator.
990 Node baseNode(IncEdgeIt) const { return INVALID; }
992 /// \brief The running node of the iterator.
994 /// Returns the running node of the given incident edge iterator.
995 Node runningNode(IncEdgeIt) const { return INVALID; }
997 /// \brief The base node of the iterator.
999 /// Returns the base node of the given outgoing arc iterator
1000 /// (i.e. the source node of the corresponding arc).
1001 Node baseNode(OutArcIt) const { return INVALID; }
1003 /// \brief The running node of the iterator.
1005 /// Returns the running node of the given outgoing arc iterator
1006 /// (i.e. the target node of the corresponding arc).
1007 Node runningNode(OutArcIt) const { return INVALID; }
1009 /// \brief The base node of the iterator.
1011 /// Returns the base node of the given incomming arc iterator
1012 /// (i.e. the target node of the corresponding arc).
1013 Node baseNode(InArcIt) const { return INVALID; }
1015 /// \brief The running node of the iterator.
1017 /// Returns the running node of the given incomming arc iterator
1018 /// (i.e. the source node of the corresponding arc).
1019 Node runningNode(InArcIt) const { return INVALID; }
1021 template <typename _BpGraph>
1022 struct Constraints {
1023 void constraints() {
1024 checkConcept<BaseBpGraphComponent, _BpGraph>();
1025 checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1026 checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1027 checkConcept<MappableBpGraphComponent<>, _BpGraph>();