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_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>
30 #include <lemon/bits/stl_iterators.h>
35 /// \ingroup graph_concepts
37 /// \brief Class describing the concept of undirected bipartite 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 bipartite graphs should compile with this class,
45 /// but it will not run properly, of course.
46 /// An actual graph implementation like \ref ListBpGraph or
47 /// \ref SmartBpGraph may have additional functionality.
49 /// The bipartite graphs also fulfill the concept of \ref Graph
50 /// "undirected graphs". Bipartite graphs provide a bipartition of
51 /// the node set, namely a red and blue set of the nodes. The
52 /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the
53 /// two node sets. With RedNodeMap and BlueNodeMap values can be
54 /// assigned to the nodes in the two sets.
56 /// The edges of the graph cannot connect two nodes of the same
57 /// set. The edges inherent orientation is from the red nodes to
63 /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
64 BpGraph(const BpGraph&) {}
65 /// \brief Assignment of a graph to another one is \e not allowed.
66 /// Use bpGraphCopy instead.
67 void operator=(const BpGraph&) {}
70 /// Default constructor.
73 /// \brief Undirected graphs should be tagged with \c UndirectedTag.
75 /// Undirected graphs should be tagged with \c UndirectedTag.
77 /// This tag helps the \c enable_if technics to make compile time
78 /// specializations for undirected graphs.
79 typedef True UndirectedTag;
81 /// The node type of the graph
83 /// This class identifies a node of the graph. It also serves
84 /// as a base class of the node iterators,
85 /// thus they convert to this type.
88 /// Default constructor
90 /// Default constructor.
91 /// \warning It sets the object to an undefined value.
98 /// Assignment operator
100 /// Assignment operator.
102 const Node &operator=(const Node&) { return *this; }
104 /// %Invalid constructor \& conversion.
106 /// Initializes the object to be invalid.
107 /// \sa Invalid for more details.
109 /// Equality operator
111 /// Equality operator.
113 /// Two iterators are equal if and only if they point to the
114 /// same object or both are \c INVALID.
115 bool operator==(Node) const { return true; }
117 /// Inequality operator
119 /// Inequality operator.
120 bool operator!=(Node) const { return true; }
122 /// Artificial ordering operator.
124 /// Artificial ordering operator.
126 /// \note This operator only has to define some strict ordering of
127 /// the items; this order has nothing to do with the iteration
128 /// ordering of the items.
129 bool operator<(Node) const { return false; }
133 /// Class to represent red nodes.
135 /// This class represents the red nodes of the graph. It does
136 /// not supposed to be used directly, because the nodes can be
137 /// represented as Node instances. This class can be used as
138 /// template parameter for special map classes.
139 class RedNode : public Node {
141 /// Default constructor
143 /// Default constructor.
144 /// \warning It sets the object to an undefined value.
146 /// Copy constructor.
148 /// Copy constructor.
150 RedNode(const RedNode&) : Node() { }
151 /// Assignment operator
153 /// Assignment operator.
155 const RedNode &operator=(const RedNode&) { return *this; }
157 /// %Invalid constructor \& conversion.
159 /// Initializes the object to be invalid.
160 /// \sa Invalid for more details.
165 /// Class to represent blue nodes.
167 /// This class represents the blue nodes of the graph. It does
168 /// not supposed to be used directly, because the nodes can be
169 /// represented as Node instances. This class can be used as
170 /// template parameter for special map classes.
171 class BlueNode : public Node {
173 /// Default constructor
175 /// Default constructor.
176 /// \warning It sets the object to an undefined value.
178 /// Copy constructor.
180 /// Copy constructor.
182 BlueNode(const BlueNode&) : Node() { }
183 /// Assignment operator
185 /// Assignment operator.
187 const BlueNode &operator=(const BlueNode&) { return *this; }
190 /// %Invalid constructor \& conversion.
192 /// Initializes the object to be invalid.
193 /// \sa Invalid for more details.
194 BlueNode(Invalid) { }
198 /// Iterator class for the red nodes.
200 /// This iterator goes through each red node of the graph.
201 /// Its usage is quite simple, for example, you can count the number
202 /// of red nodes in a graph \c g of type \c %BpGraph like this:
205 /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
207 class RedNodeIt : public RedNode {
209 /// Default constructor
211 /// Default constructor.
212 /// \warning It sets the iterator to an undefined value.
214 /// Copy constructor.
216 /// Copy constructor.
218 RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
219 /// Assignment operator
221 /// Assignment operator.
223 const RedNodeIt &operator=(const RedNodeIt&) { return *this; }
224 /// %Invalid constructor \& conversion.
226 /// Initializes the iterator to be invalid.
227 /// \sa Invalid for more details.
228 RedNodeIt(Invalid) { }
229 /// Sets the iterator to the first red node.
231 /// Sets the iterator to the first red node of the given
233 explicit RedNodeIt(const BpGraph&) { }
234 /// Sets the iterator to the given red node.
236 /// Sets the iterator to the given red node of the given
238 RedNodeIt(const BpGraph&, const RedNode&) { }
241 /// Assign the iterator to the next red node.
243 RedNodeIt& operator++() { return *this; }
246 /// \brief Gets the collection of the red nodes of the graph.
248 /// This function can be used for iterating on
249 /// the red nodes of the graph. It returns a wrapped RedNodeIt,
250 /// which looks like an STL container (by having begin() and end())
251 /// which you can use in range-based for loops, stl algorithms, etc.
252 /// For example if g is a BpGraph, you can write:
254 /// for(auto v: g.redNodes())
257 LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
258 return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
262 /// Iterator class for the blue nodes.
264 /// This iterator goes through each blue node of the graph.
265 /// Its usage is quite simple, for example, you can count the number
266 /// of blue nodes in a graph \c g of type \c %BpGraph like this:
269 /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
271 class BlueNodeIt : public BlueNode {
273 /// Default constructor
275 /// Default constructor.
276 /// \warning It sets the iterator to an undefined value.
278 /// Copy constructor.
280 /// Copy constructor.
282 BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
283 /// Assignment operator
285 /// Assignment operator.
287 const BlueNodeIt &operator=(const BlueNodeIt&) { return *this; }
288 /// %Invalid constructor \& conversion.
290 /// Initializes the iterator to be invalid.
291 /// \sa Invalid for more details.
292 BlueNodeIt(Invalid) { }
293 /// Sets the iterator to the first blue node.
295 /// Sets the iterator to the first blue node of the given
297 explicit BlueNodeIt(const BpGraph&) { }
298 /// Sets the iterator to the given blue node.
300 /// Sets the iterator to the given blue node of the given
302 BlueNodeIt(const BpGraph&, const BlueNode&) { }
305 /// Assign the iterator to the next blue node.
307 BlueNodeIt& operator++() { return *this; }
310 /// \brief Gets the collection of the blue nodes of the graph.
312 /// This function can be used for iterating on
313 /// the blue nodes of the graph. It returns a wrapped BlueNodeIt,
314 /// which looks like an STL container (by having begin() and end())
315 /// which you can use in range-based for loops, stl algorithms, etc.
316 /// For example if g is a BpGraph, you can write:
318 /// for(auto v: g.blueNodes())
321 LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
322 return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
326 /// Iterator class for the nodes.
328 /// This iterator goes through each node of the graph.
329 /// Its usage is quite simple, for example, you can count the number
330 /// of nodes in a graph \c g of type \c %BpGraph like this:
333 /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
335 class NodeIt : public Node {
337 /// Default constructor
339 /// Default constructor.
340 /// \warning It sets the iterator to an undefined value.
342 /// Copy constructor.
344 /// Copy constructor.
346 NodeIt(const NodeIt& n) : Node(n) { }
347 /// Assignment operator
349 /// Assignment operator.
351 const NodeIt &operator=(const NodeIt&) { return *this; }
352 /// %Invalid constructor \& conversion.
354 /// Initializes the iterator to be invalid.
355 /// \sa Invalid for more details.
357 /// Sets the iterator to the first node.
359 /// Sets the iterator to the first node of the given digraph.
361 explicit NodeIt(const BpGraph&) { }
362 /// Sets the iterator to the given node.
364 /// Sets the iterator to the given node of the given digraph.
366 NodeIt(const BpGraph&, const Node&) { }
369 /// Assign the iterator to the next node.
371 NodeIt& operator++() { return *this; }
374 /// \brief Gets the collection of the nodes of the graph.
376 /// This function can be used for iterating on
377 /// the nodes of the graph. It returns a wrapped NodeIt,
378 /// which looks like an STL container (by having begin() and end())
379 /// which you can use in range-based for loops, stl algorithms, etc.
380 /// For example if g is a BpGraph, you can write:
382 /// for(auto v: g.nodes())
385 LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
386 return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
391 /// The edge type of the graph
393 /// This class identifies an edge of the graph. It also serves
394 /// as a base class of the edge iterators,
395 /// thus they will convert to this type.
398 /// Default constructor
400 /// Default constructor.
401 /// \warning It sets the object to an undefined value.
403 /// Copy constructor.
405 /// Copy constructor.
407 Edge(const Edge&) { }
408 /// Assignment operator
410 /// Assignment operator.
412 const Edge &operator=(const Edge&) { return *this; }
413 /// %Invalid constructor \& conversion.
415 /// Initializes the object to be invalid.
416 /// \sa Invalid for more details.
418 /// Equality operator
420 /// Equality operator.
422 /// Two iterators are equal if and only if they point to the
423 /// same object or both are \c INVALID.
424 bool operator==(Edge) const { return true; }
425 /// Inequality operator
427 /// Inequality operator.
428 bool operator!=(Edge) const { return true; }
430 /// Artificial ordering operator.
432 /// Artificial ordering operator.
434 /// \note This operator only has to define some strict ordering of
435 /// the edges; this order has nothing to do with the iteration
436 /// ordering of the edges.
437 bool operator<(Edge) const { return false; }
440 /// Iterator class for the edges.
442 /// This iterator goes through each edge of the graph.
443 /// Its usage is quite simple, for example, you can count the number
444 /// of edges in a graph \c g of type \c %BpGraph as follows:
447 /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
449 class EdgeIt : public Edge {
451 /// Default constructor
453 /// Default constructor.
454 /// \warning It sets the iterator to an undefined value.
456 /// Copy constructor.
458 /// Copy constructor.
460 EdgeIt(const EdgeIt& e) : Edge(e) { }
461 /// Assignment operator
463 /// Assignment operator.
465 const EdgeIt &operator=(const EdgeIt&) { return *this; }
466 /// %Invalid constructor \& conversion.
468 /// Initializes the iterator to be invalid.
469 /// \sa Invalid for more details.
471 /// Sets the iterator to the first edge.
473 /// Sets the iterator to the first edge of the given graph.
475 explicit EdgeIt(const BpGraph&) { }
476 /// Sets the iterator to the given edge.
478 /// Sets the iterator to the given edge of the given graph.
480 EdgeIt(const BpGraph&, const Edge&) { }
483 /// Assign the iterator to the next edge.
485 EdgeIt& operator++() { return *this; }
488 /// \brief Gets the collection of the edges of the graph.
490 /// This function can be used for iterating on the
491 /// edges of the graph. It returns a wrapped
492 /// EdgeIt, which looks like an STL container
493 /// (by having begin() and end()) which you can use in range-based
494 /// for loops, stl algorithms, etc.
495 /// For example if g is a BpGraph, you can write:
497 /// for(auto e: g.edges())
500 LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
501 return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
505 /// Iterator class for the incident edges of a node.
507 /// This iterator goes trough the incident undirected edges
508 /// of a certain node of a graph.
509 /// Its usage is quite simple, for example, you can compute the
510 /// degree (i.e. the number of incident edges) of a node \c n
511 /// in a graph \c g of type \c %BpGraph as follows.
515 /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
518 /// \warning Loop edges will be iterated twice.
519 class IncEdgeIt : public Edge {
521 /// Default constructor
523 /// Default constructor.
524 /// \warning It sets the iterator to an undefined value.
526 /// Copy constructor.
528 /// Copy constructor.
530 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
531 /// Assignment operator
533 /// Assignment operator.
535 const IncEdgeIt &operator=(const IncEdgeIt&) { return *this; }
536 /// %Invalid constructor \& conversion.
538 /// Initializes the iterator to be invalid.
539 /// \sa Invalid for more details.
540 IncEdgeIt(Invalid) { }
541 /// Sets the iterator to the first incident edge.
543 /// Sets the iterator to the first incident edge of the given node.
545 IncEdgeIt(const BpGraph&, const Node&) { }
546 /// Sets the iterator to the given edge.
548 /// Sets the iterator to the given edge of the given graph.
550 IncEdgeIt(const BpGraph&, const Edge&) { }
551 /// Next incident edge
553 /// Assign the iterator to the next incident edge
554 /// of the corresponding node.
555 IncEdgeIt& operator++() { return *this; }
558 /// \brief Gets the collection of the incident edges
559 /// of a certain node of the graph.
561 /// This function can be used for iterating on the
562 /// incident undirected edges of a certain node of the graph.
563 /// It returns a wrapped
564 /// IncEdgeIt, which looks like an STL container
565 /// (by having begin() and end()) which you can use in range-based
566 /// for loops, stl algorithms, etc.
567 /// For example if g is a BpGraph and u is a Node, you can write:
569 /// for(auto e: g.incEdges(u))
572 LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
573 return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
577 /// The arc type of the graph
579 /// This class identifies a directed arc of the graph. It also serves
580 /// as a base class of the arc iterators,
581 /// thus they will convert to this type.
584 /// Default constructor
586 /// Default constructor.
587 /// \warning It sets the object to an undefined value.
589 /// Copy constructor.
591 /// Copy constructor.
594 /// Assignment operator
596 /// Assignment operator.
598 const Arc &operator=(const Arc&) { return *this; }
599 /// %Invalid constructor \& conversion.
601 /// Initializes the object to be invalid.
602 /// \sa Invalid for more details.
604 /// Equality operator
606 /// Equality operator.
608 /// Two iterators are equal if and only if they point to the
609 /// same object or both are \c INVALID.
610 bool operator==(Arc) const { return true; }
611 /// Inequality operator
613 /// Inequality operator.
614 bool operator!=(Arc) const { return true; }
616 /// Artificial ordering operator.
618 /// Artificial ordering operator.
620 /// \note This operator only has to define some strict ordering of
621 /// the arcs; this order has nothing to do with the iteration
622 /// ordering of the arcs.
623 bool operator<(Arc) const { return false; }
625 /// Converison to \c Edge
627 /// Converison to \c Edge.
629 operator Edge() const { return Edge(); }
632 /// Iterator class for the arcs.
634 /// This iterator goes through each directed arc of the graph.
635 /// Its usage is quite simple, for example, you can count the number
636 /// of arcs in a graph \c g of type \c %BpGraph as follows:
639 /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
641 class ArcIt : public Arc {
643 /// Default constructor
645 /// Default constructor.
646 /// \warning It sets the iterator to an undefined value.
648 /// Copy constructor.
650 /// Copy constructor.
652 ArcIt(const ArcIt& e) : Arc(e) { }
653 /// Assignment operator
655 /// Assignment operator.
657 const ArcIt &operator=(const ArcIt&) { return *this; }
658 /// %Invalid constructor \& conversion.
660 /// Initializes the iterator to be invalid.
661 /// \sa Invalid for more details.
663 /// Sets the iterator to the first arc.
665 /// Sets the iterator to the first arc of the given graph.
667 explicit ArcIt(const BpGraph &g)
669 ::lemon::ignore_unused_variable_warning(g);
671 /// Sets the iterator to the given arc.
673 /// Sets the iterator to the given arc of the given graph.
675 ArcIt(const BpGraph&, const Arc&) { }
678 /// Assign the iterator to the next arc.
680 ArcIt& operator++() { return *this; }
683 /// \brief Gets the collection of the directed arcs of the graph.
685 /// This function can be used for iterating on the
686 /// arcs of the graph. It returns a wrapped
687 /// ArcIt, which looks like an STL container
688 /// (by having begin() and end()) which you can use in range-based
689 /// for loops, stl algorithms, etc.
690 /// For example if g is a BpGraph you can write:
692 /// for(auto a: g.arcs())
695 LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
696 return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
700 /// Iterator class for the outgoing arcs of a node.
702 /// This iterator goes trough the \e outgoing directed arcs of a
703 /// certain node of a graph.
704 /// Its usage is quite simple, for example, you can count the number
705 /// of outgoing arcs of a node \c n
706 /// in a graph \c g of type \c %BpGraph as follows.
709 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
711 class OutArcIt : public Arc {
713 /// Default constructor
715 /// Default constructor.
716 /// \warning It sets the iterator to an undefined value.
718 /// Copy constructor.
720 /// Copy constructor.
722 OutArcIt(const OutArcIt& e) : Arc(e) { }
723 /// Assignment operator
725 /// Assignment operator.
727 const OutArcIt &operator=(const OutArcIt&) { return *this; }
728 /// %Invalid constructor \& conversion.
730 /// Initializes the iterator to be invalid.
731 /// \sa Invalid for more details.
732 OutArcIt(Invalid) { }
733 /// Sets the iterator to the first outgoing arc.
735 /// Sets the iterator to the first outgoing arc of the given node.
737 OutArcIt(const BpGraph& n, const Node& g) {
738 ::lemon::ignore_unused_variable_warning(n);
739 ::lemon::ignore_unused_variable_warning(g);
741 /// Sets the iterator to the given arc.
743 /// Sets the iterator to the given arc of the given graph.
745 OutArcIt(const BpGraph&, const Arc&) { }
746 /// Next outgoing arc
748 /// Assign the iterator to the next
749 /// outgoing arc of the corresponding node.
750 OutArcIt& operator++() { return *this; }
753 /// \brief Gets the collection of the outgoing directed arcs of a
754 /// certain node of the graph.
756 /// This function can be used for iterating on the
757 /// outgoing arcs of a certain node of the graph. It returns a wrapped
758 /// OutArcIt, which looks like an STL container
759 /// (by having begin() and end()) which you can use in range-based
760 /// for loops, stl algorithms, etc.
761 /// For example if g is a BpGraph and u is a Node, you can write:
763 /// for(auto a: g.outArcs(u))
766 LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
767 return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
771 /// Iterator class for the incoming arcs of a node.
773 /// This iterator goes trough the \e incoming directed arcs of a
774 /// certain node of a graph.
775 /// Its usage is quite simple, for example, you can count the number
776 /// of incoming arcs of a node \c n
777 /// in a graph \c g of type \c %BpGraph as follows.
780 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
782 class InArcIt : public Arc {
784 /// Default constructor
786 /// Default constructor.
787 /// \warning It sets the iterator to an undefined value.
789 /// Copy constructor.
791 /// Copy constructor.
793 InArcIt(const InArcIt& e) : Arc(e) { }
794 /// Assignment operator
796 /// Assignment operator.
798 const InArcIt &operator=(const InArcIt&) { return *this; }
799 /// %Invalid constructor \& conversion.
801 /// Initializes the iterator to be invalid.
802 /// \sa Invalid for more details.
804 /// Sets the iterator to the first incoming arc.
806 /// Sets the iterator to the first incoming arc of the given node.
808 InArcIt(const BpGraph& g, const Node& n) {
809 ::lemon::ignore_unused_variable_warning(n);
810 ::lemon::ignore_unused_variable_warning(g);
812 /// Sets the iterator to the given arc.
814 /// Sets the iterator to the given arc of the given graph.
816 InArcIt(const BpGraph&, const Arc&) { }
817 /// Next incoming arc
819 /// Assign the iterator to the next
820 /// incoming arc of the corresponding node.
821 InArcIt& operator++() { return *this; }
824 /// \brief Gets the collection of the incoming directed arcs of a
825 /// certain node of the graph.
827 /// This function can be used for iterating on the
828 /// incoming arcs of a certain node of the graph. It returns a wrapped
829 /// InArcIt, which looks like an STL container
830 /// (by having begin() and end()) which you can use in range-based
831 /// for loops, stl algorithms, etc.
832 /// For example if g is a BpGraph and u is a Node, you can write:
834 /// for(auto a: g.inArcs(u))
837 LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
838 return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
842 /// \brief Standard graph map type for the nodes.
844 /// Standard graph map type for the nodes.
845 /// It conforms to the ReferenceMap concept.
847 class NodeMap : public ReferenceMap<Node, T, T&, const T&>
852 explicit NodeMap(const BpGraph&) { }
853 /// Constructor with given initial value
854 NodeMap(const BpGraph&, T) { }
858 NodeMap(const NodeMap& nm) :
859 ReferenceMap<Node, T, T&, const T&>(nm) { }
860 ///Assignment operator
861 template <typename CMap>
862 NodeMap& operator=(const CMap&) {
863 checkConcept<ReadMap<Node, T>, CMap>();
868 /// \brief Standard graph map type for the red nodes.
870 /// Standard graph map type for the red nodes.
871 /// It conforms to the ReferenceMap concept.
873 class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
878 explicit RedNodeMap(const BpGraph&) { }
879 /// Constructor with given initial value
880 RedNodeMap(const BpGraph&, T) { }
884 RedNodeMap(const RedNodeMap& nm) :
885 ReferenceMap<Node, T, T&, const T&>(nm) { }
886 ///Assignment operator
887 template <typename CMap>
888 RedNodeMap& operator=(const CMap&) {
889 checkConcept<ReadMap<Node, T>, CMap>();
894 /// \brief Standard graph map type for the blue nodes.
896 /// Standard graph map type for the blue nodes.
897 /// It conforms to the ReferenceMap concept.
899 class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
904 explicit BlueNodeMap(const BpGraph&) { }
905 /// Constructor with given initial value
906 BlueNodeMap(const BpGraph&, T) { }
910 BlueNodeMap(const BlueNodeMap& nm) :
911 ReferenceMap<Node, T, T&, const T&>(nm) { }
912 ///Assignment operator
913 template <typename CMap>
914 BlueNodeMap& operator=(const CMap&) {
915 checkConcept<ReadMap<Node, T>, CMap>();
920 /// \brief Standard graph map type for the arcs.
922 /// Standard graph map type for the arcs.
923 /// It conforms to the ReferenceMap concept.
925 class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
930 explicit ArcMap(const BpGraph&) { }
931 /// Constructor with given initial value
932 ArcMap(const BpGraph&, T) { }
936 ArcMap(const ArcMap& em) :
937 ReferenceMap<Arc, T, T&, const T&>(em) { }
938 ///Assignment operator
939 template <typename CMap>
940 ArcMap& operator=(const CMap&) {
941 checkConcept<ReadMap<Arc, T>, CMap>();
946 /// \brief Standard graph map type for the edges.
948 /// Standard graph map type for the edges.
949 /// It conforms to the ReferenceMap concept.
951 class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
956 explicit EdgeMap(const BpGraph&) { }
957 /// Constructor with given initial value
958 EdgeMap(const BpGraph&, T) { }
962 EdgeMap(const EdgeMap& em) :
963 ReferenceMap<Edge, T, T&, const T&>(em) {}
964 ///Assignment operator
965 template <typename CMap>
966 EdgeMap& operator=(const CMap&) {
967 checkConcept<ReadMap<Edge, T>, CMap>();
972 /// \brief Gives back %true for red nodes.
974 /// Gives back %true for red nodes.
975 bool red(const Node&) const { return true; }
977 /// \brief Gives back %true for blue nodes.
979 /// Gives back %true for blue nodes.
980 bool blue(const Node&) const { return true; }
982 /// \brief Converts the node to red node object.
984 /// This function converts unsafely the node to red node
985 /// object. It should be called only if the node is from the red
986 /// partition or INVALID.
987 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
989 /// \brief Converts the node to blue node object.
991 /// This function converts unsafely the node to blue node
992 /// object. It should be called only if the node is from the red
993 /// partition or INVALID.
994 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
996 /// \brief Converts the node to red node object.
998 /// This function converts safely the node to red node
999 /// object. If the node is not from the red partition, then it
1000 /// returns INVALID.
1001 RedNode asRedNode(const Node&) const { return RedNode(); }
1003 /// \brief Converts the node to blue node object.
1005 /// This function converts unsafely the node to blue node
1006 /// object. If the node is not from the blue partition, then it
1007 /// returns INVALID.
1008 BlueNode asBlueNode(const Node&) const { return BlueNode(); }
1010 /// \brief Gives back the red end node of the edge.
1012 /// Gives back the red end node of the edge.
1013 RedNode redNode(const Edge&) const { return RedNode(); }
1015 /// \brief Gives back the blue end node of the edge.
1017 /// Gives back the blue end node of the edge.
1018 BlueNode blueNode(const Edge&) const { return BlueNode(); }
1020 /// \brief The first node of the edge.
1022 /// It is a synonim for the \c redNode().
1023 Node u(Edge) const { return INVALID; }
1025 /// \brief The second node of the edge.
1027 /// It is a synonim for the \c blueNode().
1028 Node v(Edge) const { return INVALID; }
1030 /// \brief The source node of the arc.
1032 /// Returns the source node of the given arc.
1033 Node source(Arc) const { return INVALID; }
1035 /// \brief The target node of the arc.
1037 /// Returns the target node of the given arc.
1038 Node target(Arc) const { return INVALID; }
1040 /// \brief The ID of the node.
1042 /// Returns the ID of the given node.
1043 int id(Node) const { return -1; }
1045 /// \brief The red ID of the node.
1047 /// Returns the red ID of the given node.
1048 int id(RedNode) const { return -1; }
1050 /// \brief The blue ID of the node.
1052 /// Returns the blue ID of the given node.
1053 int id(BlueNode) const { return -1; }
1055 /// \brief The ID of the edge.
1057 /// Returns the ID of the given edge.
1058 int id(Edge) const { return -1; }
1060 /// \brief The ID of the arc.
1062 /// Returns the ID of the given arc.
1063 int id(Arc) const { return -1; }
1065 /// \brief The node with the given ID.
1067 /// Returns the node with the given ID.
1068 /// \pre The argument should be a valid node ID in the graph.
1069 Node nodeFromId(int) const { return INVALID; }
1071 /// \brief The edge with the given ID.
1073 /// Returns the edge with the given ID.
1074 /// \pre The argument should be a valid edge ID in the graph.
1075 Edge edgeFromId(int) const { return INVALID; }
1077 /// \brief The arc with the given ID.
1079 /// Returns the arc with the given ID.
1080 /// \pre The argument should be a valid arc ID in the graph.
1081 Arc arcFromId(int) const { return INVALID; }
1083 /// \brief An upper bound on the node IDs.
1085 /// Returns an upper bound on the node IDs.
1086 int maxNodeId() const { return -1; }
1088 /// \brief An upper bound on the red IDs.
1090 /// Returns an upper bound on the red IDs.
1091 int maxRedId() const { return -1; }
1093 /// \brief An upper bound on the blue IDs.
1095 /// Returns an upper bound on the blue IDs.
1096 int maxBlueId() const { return -1; }
1098 /// \brief An upper bound on the edge IDs.
1100 /// Returns an upper bound on the edge IDs.
1101 int maxEdgeId() const { return -1; }
1103 /// \brief An upper bound on the arc IDs.
1105 /// Returns an upper bound on the arc IDs.
1106 int maxArcId() const { return -1; }
1108 /// \brief The direction of the arc.
1110 /// Returns \c true if the given arc goes from a red node to a blue node.
1111 bool direction(Arc) const { return true; }
1113 /// \brief Direct the edge.
1115 /// Direct the given edge. The returned arc
1116 /// represents the given edge and its direction comes
1117 /// from the bool parameter. If it is \c true, then the source of the node
1118 /// will be a red node.
1119 Arc direct(Edge, bool) const {
1123 /// \brief Direct the edge.
1125 /// Direct the given edge. The returned arc represents the given
1126 /// edge and its source node is the given node.
1127 Arc direct(Edge, Node) const {
1131 /// \brief The oppositely directed arc.
1133 /// Returns the oppositely directed arc representing the same edge.
1134 Arc oppositeArc(Arc) const { return INVALID; }
1136 /// \brief The opposite node on the edge.
1138 /// Returns the opposite node on the given edge.
1139 Node oppositeNode(Node, Edge) const { return INVALID; }
1141 void first(Node&) const {}
1142 void next(Node&) const {}
1144 void firstRed(RedNode&) const {}
1145 void nextRed(RedNode&) const {}
1147 void firstBlue(BlueNode&) const {}
1148 void nextBlue(BlueNode&) const {}
1150 void first(Edge&) const {}
1151 void next(Edge&) const {}
1153 void first(Arc&) const {}
1154 void next(Arc&) const {}
1156 void firstOut(Arc&, Node) const {}
1157 void nextOut(Arc&) const {}
1159 void firstIn(Arc&, Node) const {}
1160 void nextIn(Arc&) const {}
1162 void firstInc(Edge &, bool &, const Node &) const {}
1163 void nextInc(Edge &, bool &) const {}
1165 // The second parameter is dummy.
1166 Node fromId(int, Node) const { return INVALID; }
1167 // The second parameter is dummy.
1168 Edge fromId(int, Edge) const { return INVALID; }
1169 // The second parameter is dummy.
1170 Arc fromId(int, Arc) const { return INVALID; }
1173 int maxId(Node) const { return -1; }
1175 int maxId(RedNode) const { return -1; }
1177 int maxId(BlueNode) const { return -1; }
1179 int maxId(Edge) const { return -1; }
1181 int maxId(Arc) const { return -1; }
1183 /// \brief The base node of the iterator.
1185 /// Returns the base node of the given incident edge iterator.
1186 Node baseNode(IncEdgeIt) const { return INVALID; }
1188 /// \brief The running node of the iterator.
1190 /// Returns the running node of the given incident edge iterator.
1191 Node runningNode(IncEdgeIt) const { return INVALID; }
1193 /// \brief The base node of the iterator.
1195 /// Returns the base node of the given outgoing arc iterator
1196 /// (i.e. the source node of the corresponding arc).
1197 Node baseNode(OutArcIt) const { return INVALID; }
1199 /// \brief The running node of the iterator.
1201 /// Returns the running node of the given outgoing arc iterator
1202 /// (i.e. the target node of the corresponding arc).
1203 Node runningNode(OutArcIt) const { return INVALID; }
1205 /// \brief The base node of the iterator.
1207 /// Returns the base node of the given incoming arc iterator
1208 /// (i.e. the target node of the corresponding arc).
1209 Node baseNode(InArcIt) const { return INVALID; }
1211 /// \brief The running node of the iterator.
1213 /// Returns the running node of the given incoming arc iterator
1214 /// (i.e. the source node of the corresponding arc).
1215 Node runningNode(InArcIt) const { return INVALID; }
1217 template <typename _BpGraph>
1218 struct Constraints {
1219 void constraints() {
1220 checkConcept<BaseBpGraphComponent, _BpGraph>();
1221 checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1222 checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1223 checkConcept<MappableBpGraphComponent<>, _BpGraph>();