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 concepts of graph components.
23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
26 #include <lemon/core.h>
27 #include <lemon/concepts/maps.h>
29 #include <lemon/bits/alteration_notifier.h>
34 /// \brief Concept class for \c Node, \c Arc and \c Edge types.
36 /// This class describes the concept of \c Node, \c Arc and \c Edge
37 /// subtypes of digraph and graph types.
39 /// \note This class is a template class so that we can use it to
40 /// create graph skeleton classes. The reason for this is that \c Node
41 /// and \c Arc (or \c Edge) types should \e not derive from the same
42 /// base class. For \c Node you should instantiate it with character
43 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
45 template <char sel = '0'>
49 /// \brief Default constructor.
51 /// Default constructor.
52 /// \warning The default constructor is not required to set
53 /// the item to some well-defined value. So you should consider it
57 /// \brief Copy constructor.
60 GraphItem(const GraphItem &) {}
62 /// \brief Constructor for conversion from \c INVALID.
64 /// Constructor for conversion from \c INVALID.
65 /// It initializes the item to be invalid.
66 /// \sa Invalid for more details.
69 /// \brief Assignment operator.
71 /// Assignment operator for the item.
72 GraphItem& operator=(const GraphItem&) { return *this; }
74 /// \brief Assignment operator for INVALID.
76 /// This operator makes the item invalid.
77 GraphItem& operator=(Invalid) { return *this; }
79 /// \brief Equality operator.
81 /// Equality operator.
82 bool operator==(const GraphItem&) const { return false; }
84 /// \brief Inequality operator.
86 /// Inequality operator.
87 bool operator!=(const GraphItem&) const { return false; }
89 /// \brief Ordering operator.
91 /// This operator defines an ordering of the items.
92 /// It makes possible to use graph item types as key types in
93 /// associative containers (e.g. \c std::map).
95 /// \note This operator only has to define some strict ordering of
96 /// the items; this order has nothing to do with the iteration
97 /// ordering of the items.
98 bool operator<(const GraphItem&) const { return false; }
100 template<typename _GraphItem>
106 ::lemon::ignore_unused_variable_warning(i2);
107 _GraphItem i3 = INVALID;
112 ::lemon::ignore_unused_variable_warning(b);
114 b = (ia == ib) && (ia != ib);
115 b = (ia == INVALID) && (ib != INVALID);
119 const _GraphItem &ia;
120 const _GraphItem &ib;
125 /// \brief Base skeleton class for directed graphs.
127 /// This class describes the base interface of directed graph types.
128 /// All digraph %concepts have to conform to this class.
129 /// It just provides types for nodes and arcs and functions
130 /// to get the source and the target nodes of arcs.
131 class BaseDigraphComponent {
134 typedef BaseDigraphComponent Digraph;
136 /// \brief Node class of the digraph.
138 /// This class represents the nodes of the digraph.
139 typedef GraphItem<'n'> Node;
141 /// \brief Arc class of the digraph.
143 /// This class represents the arcs of the digraph.
144 typedef GraphItem<'a'> Arc;
146 /// \brief Return the source node of an arc.
148 /// This function returns the source node of an arc.
149 Node source(const Arc&) const { return INVALID; }
151 /// \brief Return the target node of an arc.
153 /// This function returns the target node of an arc.
154 Node target(const Arc&) const { return INVALID; }
156 /// \brief Return the opposite node on the given arc.
158 /// This function returns the opposite node on the given arc.
159 Node oppositeNode(const Node&, const Arc&) const {
163 template <typename _Digraph>
165 typedef typename _Digraph::Node Node;
166 typedef typename _Digraph::Arc Arc;
169 checkConcept<GraphItem<'n'>, Node>();
170 checkConcept<GraphItem<'a'>, Arc>();
174 n = digraph.source(e);
175 n = digraph.target(e);
176 n = digraph.oppositeNode(n, e);
180 const _Digraph& digraph;
185 /// \brief Base skeleton class for undirected graphs.
187 /// This class describes the base interface of undirected graph types.
188 /// All graph %concepts have to conform to this class.
189 /// It extends the interface of \ref BaseDigraphComponent with an
190 /// \c Edge type and functions to get the end nodes of edges,
191 /// to convert from arcs to edges and to get both direction of edges.
192 class BaseGraphComponent : public BaseDigraphComponent {
195 typedef BaseGraphComponent Graph;
197 typedef BaseDigraphComponent::Node Node;
198 typedef BaseDigraphComponent::Arc Arc;
200 /// \brief Undirected edge class of the graph.
202 /// This class represents the undirected edges of the graph.
203 /// Undirected graphs can be used as directed graphs, each edge is
204 /// represented by two opposite directed arcs.
205 class Edge : public GraphItem<'e'> {
206 typedef GraphItem<'e'> Parent;
209 /// \brief Default constructor.
211 /// Default constructor.
212 /// \warning The default constructor is not required to set
213 /// the item to some well-defined value. So you should consider it
214 /// as uninitialized.
217 /// \brief Copy constructor.
219 /// Copy constructor.
220 Edge(const Edge &) : Parent() {}
222 /// Assignment operator
224 /// Assignment operator.
226 const Edge &operator=(const Edge&) { return *this; }
228 /// \brief Constructor for conversion from \c INVALID.
230 /// Constructor for conversion from \c INVALID.
231 /// It initializes the item to be invalid.
232 /// \sa Invalid for more details.
235 /// \brief Constructor for conversion from an arc.
237 /// Constructor for conversion from an arc.
238 /// Besides the core graph item functionality each arc should
239 /// be convertible to the represented edge.
243 /// \brief Return one end node of an edge.
245 /// This function returns one end node of an edge.
246 Node u(const Edge&) const { return INVALID; }
248 /// \brief Return the other end node of an edge.
250 /// This function returns the other end node of an edge.
251 Node v(const Edge&) const { return INVALID; }
253 /// \brief Return a directed arc related to an edge.
255 /// This function returns a directed arc from its direction and the
256 /// represented edge.
257 Arc direct(const Edge&, bool) const { return INVALID; }
259 /// \brief Return a directed arc related to an edge.
261 /// This function returns a directed arc from its source node and the
262 /// represented edge.
263 Arc direct(const Edge&, const Node&) const { return INVALID; }
265 /// \brief Return the direction of the arc.
267 /// Returns the direction of the arc. Each arc represents an
268 /// edge with a direction. It gives back the
270 bool direction(const Arc&) const { return true; }
272 /// \brief Return the opposite arc.
274 /// This function returns the opposite arc, i.e. the arc representing
275 /// the same edge and has opposite direction.
276 Arc oppositeArc(const Arc&) const { return INVALID; }
278 template <typename _Graph>
280 typedef typename _Graph::Node Node;
281 typedef typename _Graph::Arc Arc;
282 typedef typename _Graph::Edge Edge;
285 checkConcept<BaseDigraphComponent, _Graph>();
286 checkConcept<GraphItem<'e'>, Edge>();
293 e = graph.direct(ue, true);
294 e = graph.direct(ue, false);
295 e = graph.direct(ue, n);
296 e = graph.oppositeArc(e);
298 bool d = graph.direction(e);
299 ::lemon::ignore_unused_variable_warning(d);
309 /// \brief Base skeleton class for undirected bipartite graphs.
311 /// This class describes the base interface of undirected
312 /// bipartite graph types. All bipartite graph %concepts have to
313 /// conform to this class. It extends the interface of \ref
314 /// BaseGraphComponent with an \c Edge type and functions to get
315 /// the end nodes of edges, to convert from arcs to edges and to
316 /// get both direction of edges.
317 class BaseBpGraphComponent : public BaseGraphComponent {
320 typedef BaseBpGraphComponent BpGraph;
322 typedef BaseDigraphComponent::Node Node;
323 typedef BaseDigraphComponent::Arc Arc;
325 /// \brief Class to represent red nodes.
327 /// This class represents the red nodes of the graph. The red
328 /// nodes can also be used as normal nodes.
329 class RedNode : public Node {
333 /// \brief Default constructor.
335 /// Default constructor.
336 /// \warning The default constructor is not required to set
337 /// the item to some well-defined value. So you should consider it
338 /// as uninitialized.
341 /// \brief Copy constructor.
343 /// Copy constructor.
344 RedNode(const RedNode &) : Parent() {}
345 /// Assignment operator
347 /// Assignment operator.
349 const RedNode &operator=(const RedNode&) { return *this; }
351 /// \brief Constructor for conversion from \c INVALID.
353 /// Constructor for conversion from \c INVALID.
354 /// It initializes the item to be invalid.
355 /// \sa Invalid for more details.
359 /// \brief Class to represent blue nodes.
361 /// This class represents the blue nodes of the graph. The blue
362 /// nodes can also be used as normal nodes.
363 class BlueNode : public Node {
367 /// \brief Default constructor.
369 /// Default constructor.
370 /// \warning The default constructor is not required to set
371 /// the item to some well-defined value. So you should consider it
372 /// as uninitialized.
375 /// \brief Copy constructor.
377 /// Copy constructor.
378 BlueNode(const BlueNode &) : Parent() {}
379 /// Assignment operator
381 /// Assignment operator.
383 const BlueNode &operator=(const BlueNode&) { return *this; }
386 /// \brief Constructor for conversion from \c INVALID.
388 /// Constructor for conversion from \c INVALID.
389 /// It initializes the item to be invalid.
390 /// \sa Invalid for more details.
393 /// \brief Constructor for conversion from a node.
395 /// Constructor for conversion from a node. The conversion can
396 /// be invalid, since the Node can be member of the red
398 BlueNode(const Node&) {}
401 /// \brief Gives back %true for red nodes.
403 /// Gives back %true for red nodes.
404 bool red(const Node&) const { return true; }
406 /// \brief Gives back %true for blue nodes.
408 /// Gives back %true for blue nodes.
409 bool blue(const Node&) const { return true; }
411 /// \brief Gives back the red end node of the edge.
413 /// Gives back the red end node of the edge.
414 RedNode redNode(const Edge&) const { return RedNode(); }
416 /// \brief Gives back the blue end node of the edge.
418 /// Gives back the blue end node of the edge.
419 BlueNode blueNode(const Edge&) const { return BlueNode(); }
421 /// \brief Converts the node to red node object.
423 /// This function converts unsafely the node to red node
424 /// object. It should be called only if the node is from the red
425 /// partition or INVALID.
426 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
428 /// \brief Converts the node to blue node object.
430 /// This function converts unsafely the node to blue node
431 /// object. It should be called only if the node is from the red
432 /// partition or INVALID.
433 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
435 /// \brief Converts the node to red node object.
437 /// This function converts safely the node to red node
438 /// object. If the node is not from the red partition, then it
440 RedNode asRedNode(const Node&) const { return RedNode(); }
442 /// \brief Converts the node to blue node object.
444 /// This function converts unsafely the node to blue node
445 /// object. If the node is not from the blue partition, then it
447 BlueNode asBlueNode(const Node&) const { return BlueNode(); }
449 template <typename _BpGraph>
451 typedef typename _BpGraph::Node Node;
452 typedef typename _BpGraph::RedNode RedNode;
453 typedef typename _BpGraph::BlueNode BlueNode;
454 typedef typename _BpGraph::Arc Arc;
455 typedef typename _BpGraph::Edge Edge;
458 checkConcept<BaseGraphComponent, _BpGraph>();
459 checkConcept<GraphItem<'n'>, RedNode>();
460 checkConcept<GraphItem<'n'>, BlueNode>();
469 b = bpgraph.red(rnan);
470 b = bpgraph.blue(bnan);
471 rn = bpgraph.redNode(e);
472 bn = bpgraph.blueNode(e);
473 rn = bpgraph.asRedNodeUnsafe(rnan);
474 bn = bpgraph.asBlueNodeUnsafe(bnan);
475 rn = bpgraph.asRedNode(rnan);
476 bn = bpgraph.asBlueNode(bnan);
477 ::lemon::ignore_unused_variable_warning(b);
481 const _BpGraph& bpgraph;
486 /// \brief Skeleton class for \e idable directed graphs.
488 /// This class describes the interface of \e idable directed graphs.
489 /// It extends \ref BaseDigraphComponent with the core ID functions.
490 /// The ids of the items must be unique and immutable.
491 /// This concept is part of the Digraph concept.
492 template <typename BAS = BaseDigraphComponent>
493 class IDableDigraphComponent : public BAS {
497 typedef typename Base::Node Node;
498 typedef typename Base::Arc Arc;
500 /// \brief Return a unique integer id for the given node.
502 /// This function returns a unique integer id for the given node.
503 int id(const Node&) const { return -1; }
505 /// \brief Return the node by its unique id.
507 /// This function returns the node by its unique id.
508 /// If the digraph does not contain a node with the given id,
509 /// then the result of the function is undefined.
510 Node nodeFromId(int) const { return INVALID; }
512 /// \brief Return a unique integer id for the given arc.
514 /// This function returns a unique integer id for the given arc.
515 int id(const Arc&) const { return -1; }
517 /// \brief Return the arc by its unique id.
519 /// This function returns the arc by its unique id.
520 /// If the digraph does not contain an arc with the given id,
521 /// then the result of the function is undefined.
522 Arc arcFromId(int) const { return INVALID; }
524 /// \brief Return an integer greater or equal to the maximum
527 /// This function returns an integer greater or equal to the
529 int maxNodeId() const { return -1; }
531 /// \brief Return an integer greater or equal to the maximum
534 /// This function returns an integer greater or equal to the
536 int maxArcId() const { return -1; }
538 template <typename _Digraph>
542 checkConcept<Base, _Digraph >();
543 typename _Digraph::Node node;
545 int nid = digraph.id(node);
546 nid = digraph.id(node);
547 node = digraph.nodeFromId(nid);
548 typename _Digraph::Arc arc;
550 int eid = digraph.id(arc);
551 eid = digraph.id(arc);
552 arc = digraph.arcFromId(eid);
554 nid = digraph.maxNodeId();
555 ::lemon::ignore_unused_variable_warning(nid);
556 eid = digraph.maxArcId();
557 ::lemon::ignore_unused_variable_warning(eid);
560 const _Digraph& digraph;
565 /// \brief Skeleton class for \e idable undirected graphs.
567 /// This class describes the interface of \e idable undirected
568 /// graphs. It extends \ref IDableDigraphComponent with the core ID
569 /// functions of undirected graphs.
570 /// The ids of the items must be unique and immutable.
571 /// This concept is part of the Graph concept.
572 template <typename BAS = BaseGraphComponent>
573 class IDableGraphComponent : public IDableDigraphComponent<BAS> {
577 typedef typename Base::Edge Edge;
579 using IDableDigraphComponent<Base>::id;
581 /// \brief Return a unique integer id for the given edge.
583 /// This function returns a unique integer id for the given edge.
584 int id(const Edge&) const { return -1; }
586 /// \brief Return the edge by its unique id.
588 /// This function returns the edge by its unique id.
589 /// If the graph does not contain an edge with the given id,
590 /// then the result of the function is undefined.
591 Edge edgeFromId(int) const { return INVALID; }
593 /// \brief Return an integer greater or equal to the maximum
596 /// This function returns an integer greater or equal to the
598 int maxEdgeId() const { return -1; }
600 template <typename _Graph>
604 checkConcept<IDableDigraphComponent<Base>, _Graph >();
605 typename _Graph::Edge edge;
606 int ueid = graph.id(edge);
607 ueid = graph.id(edge);
608 edge = graph.edgeFromId(ueid);
609 ueid = graph.maxEdgeId();
610 ::lemon::ignore_unused_variable_warning(ueid);
618 /// \brief Skeleton class for \e idable undirected bipartite graphs.
620 /// This class describes the interface of \e idable undirected
621 /// bipartite graphs. It extends \ref IDableGraphComponent with
622 /// the core ID functions of undirected bipartite graphs. Beside
623 /// the regular node ids, this class also provides ids within the
624 /// the red and blue sets of the nodes. This concept is part of
625 /// the BpGraph concept.
626 template <typename BAS = BaseBpGraphComponent>
627 class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
631 typedef IDableGraphComponent<BAS> Parent;
632 typedef typename Base::Node Node;
633 typedef typename Base::RedNode RedNode;
634 typedef typename Base::BlueNode BlueNode;
638 /// \brief Return a unique integer id for the given node in the red set.
640 /// Return a unique integer id for the given node in the red set.
641 int id(const RedNode&) const { return -1; }
643 /// \brief Return a unique integer id for the given node in the blue set.
645 /// Return a unique integer id for the given node in the blue set.
646 int id(const BlueNode&) const { return -1; }
648 /// \brief Return an integer greater or equal to the maximum
649 /// node id in the red set.
651 /// Return an integer greater or equal to the maximum
652 /// node id in the red set.
653 int maxRedId() const { return -1; }
655 /// \brief Return an integer greater or equal to the maximum
656 /// node id in the blue set.
658 /// Return an integer greater or equal to the maximum
659 /// node id in the blue set.
660 int maxBlueId() const { return -1; }
662 template <typename _BpGraph>
666 checkConcept<IDableGraphComponent<Base>, _BpGraph>();
667 typename _BpGraph::Node node;
668 typename _BpGraph::RedNode red;
669 typename _BpGraph::BlueNode blue;
670 int rid = bpgraph.id(red);
671 int bid = bpgraph.id(blue);
672 rid = bpgraph.maxRedId();
673 bid = bpgraph.maxBlueId();
674 ::lemon::ignore_unused_variable_warning(rid);
675 ::lemon::ignore_unused_variable_warning(bid);
678 const _BpGraph& bpgraph;
682 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
684 /// This class describes the concept of \c NodeIt, \c ArcIt and
685 /// \c EdgeIt subtypes of digraph and graph types.
686 template <typename GR, typename Item>
687 class GraphItemIt : public Item {
689 /// \brief Default constructor.
691 /// Default constructor.
692 /// \warning The default constructor is not required to set
693 /// the iterator to some well-defined value. So you should consider it
694 /// as uninitialized.
697 /// \brief Copy constructor.
699 /// Copy constructor.
700 GraphItemIt(const GraphItemIt& it) : Item(it) {}
702 /// \brief Constructor that sets the iterator to the first item.
704 /// Constructor that sets the iterator to the first item.
705 explicit GraphItemIt(const GR&) {}
707 /// \brief Constructor for conversion from \c INVALID.
709 /// Constructor for conversion from \c INVALID.
710 /// It initializes the iterator to be invalid.
711 /// \sa Invalid for more details.
712 GraphItemIt(Invalid) {}
714 /// \brief Assignment operator.
716 /// Assignment operator for the iterator.
717 GraphItemIt& operator=(const GraphItemIt&) { return *this; }
719 /// \brief Increment the iterator.
721 /// This operator increments the iterator, i.e. assigns it to the
723 GraphItemIt& operator++() { return *this; }
725 /// \brief Equality operator
727 /// Equality operator.
728 /// Two iterators are equal if and only if they point to the
729 /// same object or both are invalid.
730 bool operator==(const GraphItemIt&) const { return true;}
732 /// \brief Inequality operator
734 /// Inequality operator.
735 /// Two iterators are equal if and only if they point to the
736 /// same object or both are invalid.
737 bool operator!=(const GraphItemIt&) const { return true;}
739 template<typename _GraphItemIt>
742 checkConcept<GraphItem<>, _GraphItemIt>();
745 _GraphItemIt it3 = it1;
746 _GraphItemIt it4 = INVALID;
747 ::lemon::ignore_unused_variable_warning(it3);
748 ::lemon::ignore_unused_variable_warning(it4);
755 ::lemon::ignore_unused_variable_warning(bi);
763 /// \brief Concept class for \c InArcIt, \c OutArcIt and
764 /// \c IncEdgeIt types.
766 /// This class describes the concept of \c InArcIt, \c OutArcIt
767 /// and \c IncEdgeIt subtypes of digraph and graph types.
769 /// \note Since these iterator classes do not inherit from the same
770 /// base class, there is an additional template parameter (selector)
771 /// \c sel. For \c InArcIt you should instantiate it with character
772 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
773 template <typename GR,
774 typename Item = typename GR::Arc,
775 typename Base = typename GR::Node,
777 class GraphIncIt : public Item {
779 /// \brief Default constructor.
781 /// Default constructor.
782 /// \warning The default constructor is not required to set
783 /// the iterator to some well-defined value. So you should consider it
784 /// as uninitialized.
787 /// \brief Copy constructor.
789 /// Copy constructor.
790 GraphIncIt(const GraphIncIt& it) : Item(it) {}
792 /// \brief Constructor that sets the iterator to the first
793 /// incoming or outgoing arc.
795 /// Constructor that sets the iterator to the first arc
796 /// incoming to or outgoing from the given node.
797 explicit GraphIncIt(const GR&, const Base&) {}
799 /// \brief Constructor for conversion from \c INVALID.
801 /// Constructor for conversion from \c INVALID.
802 /// It initializes the iterator to be invalid.
803 /// \sa Invalid for more details.
804 GraphIncIt(Invalid) {}
806 /// \brief Assignment operator.
808 /// Assignment operator for the iterator.
809 GraphIncIt& operator=(const GraphIncIt&) { return *this; }
811 /// \brief Increment the iterator.
813 /// This operator increments the iterator, i.e. assigns it to the
814 /// next arc incoming to or outgoing from the given node.
815 GraphIncIt& operator++() { return *this; }
817 /// \brief Equality operator
819 /// Equality operator.
820 /// Two iterators are equal if and only if they point to the
821 /// same object or both are invalid.
822 bool operator==(const GraphIncIt&) const { return true;}
824 /// \brief Inequality operator
826 /// Inequality operator.
827 /// Two iterators are equal if and only if they point to the
828 /// same object or both are invalid.
829 bool operator!=(const GraphIncIt&) const { return true;}
831 template <typename _GraphIncIt>
834 checkConcept<GraphItem<sel>, _GraphIncIt>();
835 _GraphIncIt it1(graph, node);
837 _GraphIncIt it3 = it1;
838 _GraphIncIt it4 = INVALID;
839 ::lemon::ignore_unused_variable_warning(it3);
840 ::lemon::ignore_unused_variable_warning(it4);
846 ::lemon::ignore_unused_variable_warning(e);
855 /// \brief Skeleton class for iterable directed graphs.
857 /// This class describes the interface of iterable directed
858 /// graphs. It extends \ref BaseDigraphComponent with the core
859 /// iterable interface.
860 /// This concept is part of the Digraph concept.
861 template <typename BAS = BaseDigraphComponent>
862 class IterableDigraphComponent : public BAS {
867 typedef typename Base::Node Node;
868 typedef typename Base::Arc Arc;
870 typedef IterableDigraphComponent Digraph;
872 /// \name Base Iteration
874 /// This interface provides functions for iteration on digraph items.
878 /// \brief Return the first node.
880 /// This function gives back the first node in the iteration order.
881 void first(Node&) const {}
883 /// \brief Return the next node.
885 /// This function gives back the next node in the iteration order.
886 void next(Node&) const {}
888 /// \brief Return the first arc.
890 /// This function gives back the first arc in the iteration order.
891 void first(Arc&) const {}
893 /// \brief Return the next arc.
895 /// This function gives back the next arc in the iteration order.
896 void next(Arc&) const {}
898 /// \brief Return the first arc incoming to the given node.
900 /// This function gives back the first arc incoming to the
902 void firstIn(Arc&, const Node&) const {}
904 /// \brief Return the next arc incoming to the given node.
906 /// This function gives back the next arc incoming to the
908 void nextIn(Arc&) const {}
910 /// \brief Return the first arc outgoing form the given node.
912 /// This function gives back the first arc outgoing form the
914 void firstOut(Arc&, const Node&) const {}
916 /// \brief Return the next arc outgoing form the given node.
918 /// This function gives back the next arc outgoing form the
920 void nextOut(Arc&) const {}
924 /// \name Class Based Iteration
926 /// This interface provides iterator classes for digraph items.
930 /// \brief This iterator goes through each node.
932 /// This iterator goes through each node.
934 typedef GraphItemIt<Digraph, Node> NodeIt;
936 /// \brief This iterator goes through each arc.
938 /// This iterator goes through each arc.
940 typedef GraphItemIt<Digraph, Arc> ArcIt;
942 /// \brief This iterator goes trough the incoming arcs of a node.
944 /// This iterator goes trough the \e incoming arcs of a certain node
946 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
948 /// \brief This iterator goes trough the outgoing arcs of a node.
950 /// This iterator goes trough the \e outgoing arcs of a certain node
952 typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
954 /// \brief The base node of the iterator.
956 /// This function gives back the base node of the iterator.
957 /// It is always the target node of the pointed arc.
958 Node baseNode(const InArcIt&) const { return INVALID; }
960 /// \brief The running node of the iterator.
962 /// This function gives back the running node of the iterator.
963 /// It is always the source node of the pointed arc.
964 Node runningNode(const InArcIt&) const { return INVALID; }
966 /// \brief The base node of the iterator.
968 /// This function gives back the base node of the iterator.
969 /// It is always the source node of the pointed arc.
970 Node baseNode(const OutArcIt&) const { return INVALID; }
972 /// \brief The running node of the iterator.
974 /// This function gives back the running node of the iterator.
975 /// It is always the target node of the pointed arc.
976 Node runningNode(const OutArcIt&) const { return INVALID; }
980 template <typename _Digraph>
983 checkConcept<Base, _Digraph>();
986 typename _Digraph::Node node(INVALID);
987 typename _Digraph::Arc arc(INVALID);
997 digraph.firstIn(arc, node);
1001 digraph.firstOut(arc, node);
1002 digraph.nextOut(arc);
1007 checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
1008 typename _Digraph::ArcIt >();
1009 checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
1010 typename _Digraph::NodeIt >();
1011 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
1012 typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
1013 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
1014 typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
1016 typename _Digraph::Node n;
1017 const typename _Digraph::InArcIt iait(INVALID);
1018 const typename _Digraph::OutArcIt oait(INVALID);
1019 n = digraph.baseNode(iait);
1020 n = digraph.runningNode(iait);
1021 n = digraph.baseNode(oait);
1022 n = digraph.runningNode(oait);
1023 ::lemon::ignore_unused_variable_warning(n);
1027 const _Digraph& digraph;
1032 /// \brief Skeleton class for iterable undirected graphs.
1034 /// This class describes the interface of iterable undirected
1035 /// graphs. It extends \ref IterableDigraphComponent with the core
1036 /// iterable interface of undirected graphs.
1037 /// This concept is part of the Graph concept.
1038 template <typename BAS = BaseGraphComponent>
1039 class IterableGraphComponent : public IterableDigraphComponent<BAS> {
1043 typedef typename Base::Node Node;
1044 typedef typename Base::Arc Arc;
1045 typedef typename Base::Edge Edge;
1048 typedef IterableGraphComponent Graph;
1050 /// \name Base Iteration
1052 /// This interface provides functions for iteration on edges.
1056 using IterableDigraphComponent<Base>::first;
1057 using IterableDigraphComponent<Base>::next;
1059 /// \brief Return the first edge.
1061 /// This function gives back the first edge in the iteration order.
1062 void first(Edge&) const {}
1064 /// \brief Return the next edge.
1066 /// This function gives back the next edge in the iteration order.
1067 void next(Edge&) const {}
1069 /// \brief Return the first edge incident to the given node.
1071 /// This function gives back the first edge incident to the given
1072 /// node. The bool parameter gives back the direction for which the
1073 /// source node of the directed arc representing the edge is the
1075 void firstInc(Edge&, bool&, const Node&) const {}
1077 /// \brief Gives back the next of the edges from the
1080 /// This function gives back the next edge incident to the given
1081 /// node. The bool parameter should be used as \c firstInc() use it.
1082 void nextInc(Edge&, bool&) const {}
1084 using IterableDigraphComponent<Base>::baseNode;
1085 using IterableDigraphComponent<Base>::runningNode;
1089 /// \name Class Based Iteration
1091 /// This interface provides iterator classes for edges.
1095 /// \brief This iterator goes through each edge.
1097 /// This iterator goes through each edge.
1098 typedef GraphItemIt<Graph, Edge> EdgeIt;
1100 /// \brief This iterator goes trough the incident edges of a
1103 /// This iterator goes trough the incident edges of a certain
1104 /// node of a graph.
1105 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
1107 /// \brief The base node of the iterator.
1109 /// This function gives back the base node of the iterator.
1110 Node baseNode(const IncEdgeIt&) const { return INVALID; }
1112 /// \brief The running node of the iterator.
1114 /// This function gives back the running node of the iterator.
1115 Node runningNode(const IncEdgeIt&) const { return INVALID; }
1119 template <typename _Graph>
1120 struct Constraints {
1121 void constraints() {
1122 checkConcept<IterableDigraphComponent<Base>, _Graph>();
1125 typename _Graph::Node node(INVALID);
1126 typename _Graph::Edge edge(INVALID);
1133 graph.firstInc(edge, dir, node);
1134 graph.nextInc(edge, dir);
1140 checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1141 typename _Graph::EdgeIt >();
1142 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1143 typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
1145 typename _Graph::Node n;
1146 const typename _Graph::IncEdgeIt ieit(INVALID);
1147 n = graph.baseNode(ieit);
1148 n = graph.runningNode(ieit);
1152 const _Graph& graph;
1157 /// \brief Skeleton class for iterable undirected bipartite graphs.
1159 /// This class describes the interface of iterable undirected
1160 /// bipartite graphs. It extends \ref IterableGraphComponent with
1161 /// the core iterable interface of undirected bipartite graphs.
1162 /// This concept is part of the BpGraph concept.
1163 template <typename BAS = BaseBpGraphComponent>
1164 class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
1168 typedef typename Base::Node Node;
1169 typedef typename Base::RedNode RedNode;
1170 typedef typename Base::BlueNode BlueNode;
1171 typedef typename Base::Arc Arc;
1172 typedef typename Base::Edge Edge;
1174 typedef IterableBpGraphComponent BpGraph;
1176 using IterableGraphComponent<BAS>::first;
1177 using IterableGraphComponent<BAS>::next;
1179 /// \name Base Iteration
1181 /// This interface provides functions for iteration on red and blue nodes.
1185 /// \brief Return the first red node.
1187 /// This function gives back the first red node in the iteration order.
1188 void first(RedNode&) const {}
1190 /// \brief Return the next red node.
1192 /// This function gives back the next red node in the iteration order.
1193 void next(RedNode&) const {}
1195 /// \brief Return the first blue node.
1197 /// This function gives back the first blue node in the iteration order.
1198 void first(BlueNode&) const {}
1200 /// \brief Return the next blue node.
1202 /// This function gives back the next blue node in the iteration order.
1203 void next(BlueNode&) const {}
1208 /// \name Class Based Iteration
1210 /// This interface provides iterator classes for red and blue nodes.
1214 /// \brief This iterator goes through each red node.
1216 /// This iterator goes through each red node.
1217 typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
1219 /// \brief This iterator goes through each blue node.
1221 /// This iterator goes through each blue node.
1222 typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
1226 template <typename _BpGraph>
1227 struct Constraints {
1228 void constraints() {
1229 checkConcept<IterableGraphComponent<Base>, _BpGraph>();
1231 typename _BpGraph::RedNode rn(INVALID);
1234 typename _BpGraph::BlueNode bn(INVALID);
1238 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
1239 typename _BpGraph::RedNodeIt>();
1240 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
1241 typename _BpGraph::BlueNodeIt>();
1244 const _BpGraph& bpgraph;
1248 /// \brief Skeleton class for alterable directed graphs.
1250 /// This class describes the interface of alterable directed
1251 /// graphs. It extends \ref BaseDigraphComponent with the alteration
1252 /// notifier interface. It implements
1253 /// an observer-notifier pattern for each digraph item. More
1254 /// obsevers can be registered into the notifier and whenever an
1255 /// alteration occured in the digraph all the observers will be
1256 /// notified about it.
1257 template <typename BAS = BaseDigraphComponent>
1258 class AlterableDigraphComponent : public BAS {
1262 typedef typename Base::Node Node;
1263 typedef typename Base::Arc Arc;
1266 /// Node alteration notifier class.
1267 typedef AlterationNotifier<AlterableDigraphComponent, Node>
1269 /// Arc alteration notifier class.
1270 typedef AlterationNotifier<AlterableDigraphComponent, Arc>
1273 mutable NodeNotifier node_notifier;
1274 mutable ArcNotifier arc_notifier;
1276 /// \brief Return the node alteration notifier.
1278 /// This function gives back the node alteration notifier.
1279 NodeNotifier& notifier(Node) const {
1280 return node_notifier;
1283 /// \brief Return the arc alteration notifier.
1285 /// This function gives back the arc alteration notifier.
1286 ArcNotifier& notifier(Arc) const {
1287 return arc_notifier;
1290 template <typename _Digraph>
1291 struct Constraints {
1292 void constraints() {
1293 checkConcept<Base, _Digraph>();
1294 typename _Digraph::NodeNotifier& nn
1295 = digraph.notifier(typename _Digraph::Node());
1297 typename _Digraph::ArcNotifier& en
1298 = digraph.notifier(typename _Digraph::Arc());
1300 ::lemon::ignore_unused_variable_warning(nn);
1301 ::lemon::ignore_unused_variable_warning(en);
1304 const _Digraph& digraph;
1309 /// \brief Skeleton class for alterable undirected graphs.
1311 /// This class describes the interface of alterable undirected
1312 /// graphs. It extends \ref AlterableDigraphComponent with the alteration
1313 /// notifier interface of undirected graphs. It implements
1314 /// an observer-notifier pattern for the edges. More
1315 /// obsevers can be registered into the notifier and whenever an
1316 /// alteration occured in the graph all the observers will be
1317 /// notified about it.
1318 template <typename BAS = BaseGraphComponent>
1319 class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
1323 typedef AlterableDigraphComponent<Base> Parent;
1324 typedef typename Base::Edge Edge;
1327 /// Edge alteration notifier class.
1328 typedef AlterationNotifier<AlterableGraphComponent, Edge>
1331 mutable EdgeNotifier edge_notifier;
1333 using Parent::notifier;
1335 /// \brief Return the edge alteration notifier.
1337 /// This function gives back the edge alteration notifier.
1338 EdgeNotifier& notifier(Edge) const {
1339 return edge_notifier;
1342 template <typename _Graph>
1343 struct Constraints {
1344 void constraints() {
1345 checkConcept<AlterableDigraphComponent<Base>, _Graph>();
1346 typename _Graph::EdgeNotifier& uen
1347 = graph.notifier(typename _Graph::Edge());
1348 ::lemon::ignore_unused_variable_warning(uen);
1351 const _Graph& graph;
1356 /// \brief Skeleton class for alterable undirected bipartite graphs.
1358 /// This class describes the interface of alterable undirected
1359 /// bipartite graphs. It extends \ref AlterableGraphComponent with
1360 /// the alteration notifier interface of bipartite graphs. It
1361 /// implements an observer-notifier pattern for the red and blue
1362 /// nodes. More obsevers can be registered into the notifier and
1363 /// whenever an alteration occured in the graph all the observers
1364 /// will be notified about it.
1365 template <typename BAS = BaseBpGraphComponent>
1366 class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
1370 typedef AlterableGraphComponent<Base> Parent;
1371 typedef typename Base::RedNode RedNode;
1372 typedef typename Base::BlueNode BlueNode;
1375 /// Red node alteration notifier class.
1376 typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
1379 /// Blue node alteration notifier class.
1380 typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
1383 mutable RedNodeNotifier red_node_notifier;
1384 mutable BlueNodeNotifier blue_node_notifier;
1386 using Parent::notifier;
1388 /// \brief Return the red node alteration notifier.
1390 /// This function gives back the red node alteration notifier.
1391 RedNodeNotifier& notifier(RedNode) const {
1392 return red_node_notifier;
1395 /// \brief Return the blue node alteration notifier.
1397 /// This function gives back the blue node alteration notifier.
1398 BlueNodeNotifier& notifier(BlueNode) const {
1399 return blue_node_notifier;
1402 template <typename _BpGraph>
1403 struct Constraints {
1404 void constraints() {
1405 checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
1406 typename _BpGraph::RedNodeNotifier& rnn
1407 = bpgraph.notifier(typename _BpGraph::RedNode());
1408 typename _BpGraph::BlueNodeNotifier& bnn
1409 = bpgraph.notifier(typename _BpGraph::BlueNode());
1410 ::lemon::ignore_unused_variable_warning(rnn);
1411 ::lemon::ignore_unused_variable_warning(bnn);
1414 const _BpGraph& bpgraph;
1418 /// \brief Concept class for standard graph maps.
1420 /// This class describes the concept of standard graph maps, i.e.
1421 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
1422 /// graph types, which can be used for associating data to graph items.
1423 /// The standard graph maps must conform to the ReferenceMap concept.
1424 template <typename GR, typename K, typename V>
1425 class GraphMap : public ReferenceMap<K, V, V&, const V&> {
1426 typedef ReferenceMap<K, V, V&, const V&> Parent;
1430 /// The key type of the map.
1432 /// The value type of the map.
1434 /// The reference type of the map.
1435 typedef Value& Reference;
1436 /// The const reference type of the map.
1437 typedef const Value& ConstReference;
1439 // The reference map tag.
1440 typedef True ReferenceMapTag;
1442 /// \brief Construct a new map.
1444 /// Construct a new map for the graph.
1445 explicit GraphMap(const GR&) {}
1446 /// \brief Construct a new map with default value.
1448 /// Construct a new map for the graph and initalize the values.
1449 GraphMap(const GR&, const Value&) {}
1452 /// \brief Copy constructor.
1454 /// Copy Constructor.
1455 GraphMap(const GraphMap&) : Parent() {}
1457 /// \brief Assignment operator.
1459 /// Assignment operator. It does not mofify the underlying graph,
1460 /// it just iterates on the current item set and set the map
1461 /// with the value returned by the assigned map.
1462 template <typename CMap>
1463 GraphMap& operator=(const CMap&) {
1464 checkConcept<ReadMap<Key, Value>, CMap>();
1469 template<typename _Map>
1470 struct Constraints {
1471 void constraints() {
1473 <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
1480 // Assignment operator
1481 // ReadMap<Key, Value> cmap;
1484 ::lemon::ignore_unused_variable_warning(m1);
1485 ::lemon::ignore_unused_variable_warning(m2);
1486 // ::lemon::ignore_unused_variable_warning(m3);
1491 const typename GraphMap::Value &t;
1497 /// \brief Skeleton class for mappable directed graphs.
1499 /// This class describes the interface of mappable directed graphs.
1500 /// It extends \ref BaseDigraphComponent with the standard digraph
1501 /// map classes, namely \c NodeMap and \c ArcMap.
1502 /// This concept is part of the Digraph concept.
1503 template <typename BAS = BaseDigraphComponent>
1504 class MappableDigraphComponent : public BAS {
1508 typedef typename Base::Node Node;
1509 typedef typename Base::Arc Arc;
1511 typedef MappableDigraphComponent Digraph;
1513 /// \brief Standard graph map for the nodes.
1515 /// Standard graph map for the nodes.
1516 /// It conforms to the ReferenceMap concept.
1517 template <typename V>
1518 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
1519 typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
1522 /// \brief Construct a new map.
1524 /// Construct a new map for the digraph.
1525 explicit NodeMap(const MappableDigraphComponent& digraph)
1526 : Parent(digraph) {}
1528 /// \brief Construct a new map with default value.
1530 /// Construct a new map for the digraph and initalize the values.
1531 NodeMap(const MappableDigraphComponent& digraph, const V& value)
1532 : Parent(digraph, value) {}
1535 /// \brief Copy constructor.
1537 /// Copy Constructor.
1538 NodeMap(const NodeMap& nm) : Parent(nm) {}
1540 /// \brief Assignment operator.
1542 /// Assignment operator.
1543 template <typename CMap>
1544 NodeMap& operator=(const CMap&) {
1545 checkConcept<ReadMap<Node, V>, CMap>();
1551 /// \brief Standard graph map for the arcs.
1553 /// Standard graph map for the arcs.
1554 /// It conforms to the ReferenceMap concept.
1555 template <typename V>
1556 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
1557 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
1560 /// \brief Construct a new map.
1562 /// Construct a new map for the digraph.
1563 explicit ArcMap(const MappableDigraphComponent& digraph)
1564 : Parent(digraph) {}
1566 /// \brief Construct a new map with default value.
1568 /// Construct a new map for the digraph and initalize the values.
1569 ArcMap(const MappableDigraphComponent& digraph, const V& value)
1570 : Parent(digraph, value) {}
1573 /// \brief Copy constructor.
1575 /// Copy Constructor.
1576 ArcMap(const ArcMap& nm) : Parent(nm) {}
1578 /// \brief Assignment operator.
1580 /// Assignment operator.
1581 template <typename CMap>
1582 ArcMap& operator=(const CMap&) {
1583 checkConcept<ReadMap<Arc, V>, CMap>();
1590 template <typename _Digraph>
1591 struct Constraints {
1595 Dummy() : value(0) {}
1596 Dummy(int _v) : value(_v) {}
1599 void constraints() {
1600 checkConcept<Base, _Digraph>();
1602 typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1603 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1605 } { // bool map test
1606 typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1607 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1609 } { // Dummy map test
1610 typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1611 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1616 typedef typename _Digraph::template ArcMap<int> IntArcMap;
1617 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1619 } { // bool map test
1620 typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1621 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1623 } { // Dummy map test
1624 typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1625 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1630 const _Digraph& digraph;
1635 /// \brief Skeleton class for mappable undirected graphs.
1637 /// This class describes the interface of mappable undirected graphs.
1638 /// It extends \ref MappableDigraphComponent with the standard graph
1639 /// map class for edges (\c EdgeMap).
1640 /// This concept is part of the Graph concept.
1641 template <typename BAS = BaseGraphComponent>
1642 class MappableGraphComponent : public MappableDigraphComponent<BAS> {
1646 typedef typename Base::Edge Edge;
1648 typedef MappableGraphComponent Graph;
1650 /// \brief Standard graph map for the edges.
1652 /// Standard graph map for the edges.
1653 /// It conforms to the ReferenceMap concept.
1654 template <typename V>
1655 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
1656 typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
1659 /// \brief Construct a new map.
1661 /// Construct a new map for the graph.
1662 explicit EdgeMap(const MappableGraphComponent& graph)
1665 /// \brief Construct a new map with default value.
1667 /// Construct a new map for the graph and initalize the values.
1668 EdgeMap(const MappableGraphComponent& graph, const V& value)
1669 : Parent(graph, value) {}
1672 /// \brief Copy constructor.
1674 /// Copy Constructor.
1675 EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1677 /// \brief Assignment operator.
1679 /// Assignment operator.
1680 template <typename CMap>
1681 EdgeMap& operator=(const CMap&) {
1682 checkConcept<ReadMap<Edge, V>, CMap>();
1689 template <typename _Graph>
1690 struct Constraints {
1694 Dummy() : value(0) {}
1695 Dummy(int _v) : value(_v) {}
1698 void constraints() {
1699 checkConcept<MappableDigraphComponent<Base>, _Graph>();
1702 typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1703 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1705 } { // bool map test
1706 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1707 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1709 } { // Dummy map test
1710 typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1711 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1716 const _Graph& graph;
1721 /// \brief Skeleton class for mappable undirected bipartite graphs.
1723 /// This class describes the interface of mappable undirected
1724 /// bipartite graphs. It extends \ref MappableGraphComponent with
1725 /// the standard graph map class for red and blue nodes (\c
1726 /// RedNodeMap and BlueNodeMap). This concept is part of the
1727 /// BpGraph concept.
1728 template <typename BAS = BaseBpGraphComponent>
1729 class MappableBpGraphComponent : public MappableGraphComponent<BAS> {
1733 typedef typename Base::Node Node;
1735 typedef MappableBpGraphComponent BpGraph;
1737 /// \brief Standard graph map for the red nodes.
1739 /// Standard graph map for the red nodes.
1740 /// It conforms to the ReferenceMap concept.
1741 template <typename V>
1742 class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1743 typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1746 /// \brief Construct a new map.
1748 /// Construct a new map for the graph.
1749 explicit RedNodeMap(const MappableBpGraphComponent& graph)
1752 /// \brief Construct a new map with default value.
1754 /// Construct a new map for the graph and initalize the values.
1755 RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
1756 : Parent(graph, value) {}
1759 /// \brief Copy constructor.
1761 /// Copy Constructor.
1762 RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
1764 /// \brief Assignment operator.
1766 /// Assignment operator.
1767 template <typename CMap>
1768 RedNodeMap& operator=(const CMap&) {
1769 checkConcept<ReadMap<Node, V>, CMap>();
1775 /// \brief Standard graph map for the blue nodes.
1777 /// Standard graph map for the blue nodes.
1778 /// It conforms to the ReferenceMap concept.
1779 template <typename V>
1780 class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1781 typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1784 /// \brief Construct a new map.
1786 /// Construct a new map for the graph.
1787 explicit BlueNodeMap(const MappableBpGraphComponent& graph)
1790 /// \brief Construct a new map with default value.
1792 /// Construct a new map for the graph and initalize the values.
1793 BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
1794 : Parent(graph, value) {}
1797 /// \brief Copy constructor.
1799 /// Copy Constructor.
1800 BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
1802 /// \brief Assignment operator.
1804 /// Assignment operator.
1805 template <typename CMap>
1806 BlueNodeMap& operator=(const CMap&) {
1807 checkConcept<ReadMap<Node, V>, CMap>();
1814 template <typename _BpGraph>
1815 struct Constraints {
1819 Dummy() : value(0) {}
1820 Dummy(int _v) : value(_v) {}
1823 void constraints() {
1824 checkConcept<MappableGraphComponent<Base>, _BpGraph>();
1827 typedef typename _BpGraph::template RedNodeMap<int>
1829 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
1831 } { // bool map test
1832 typedef typename _BpGraph::template RedNodeMap<bool>
1834 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
1836 } { // Dummy map test
1837 typedef typename _BpGraph::template RedNodeMap<Dummy>
1839 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
1840 DummyRedNodeMap >();
1844 typedef typename _BpGraph::template BlueNodeMap<int>
1846 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
1848 } { // bool map test
1849 typedef typename _BpGraph::template BlueNodeMap<bool>
1851 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
1852 BoolBlueNodeMap >();
1853 } { // Dummy map test
1854 typedef typename _BpGraph::template BlueNodeMap<Dummy>
1856 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
1857 DummyBlueNodeMap >();
1861 const _BpGraph& bpgraph;
1865 /// \brief Skeleton class for extendable directed graphs.
1867 /// This class describes the interface of extendable directed graphs.
1868 /// It extends \ref BaseDigraphComponent with functions for adding
1869 /// nodes and arcs to the digraph.
1870 /// This concept requires \ref AlterableDigraphComponent.
1871 template <typename BAS = BaseDigraphComponent>
1872 class ExtendableDigraphComponent : public BAS {
1876 typedef typename Base::Node Node;
1877 typedef typename Base::Arc Arc;
1879 /// \brief Add a new node to the digraph.
1881 /// This function adds a new node to the digraph.
1886 /// \brief Add a new arc connecting the given two nodes.
1888 /// This function adds a new arc connecting the given two nodes
1890 Arc addArc(const Node&, const Node&) {
1894 template <typename _Digraph>
1895 struct Constraints {
1896 void constraints() {
1897 checkConcept<Base, _Digraph>();
1898 typename _Digraph::Node node_a, node_b;
1899 node_a = digraph.addNode();
1900 node_b = digraph.addNode();
1901 typename _Digraph::Arc arc;
1902 arc = digraph.addArc(node_a, node_b);
1910 /// \brief Skeleton class for extendable undirected graphs.
1912 /// This class describes the interface of extendable undirected graphs.
1913 /// It extends \ref BaseGraphComponent with functions for adding
1914 /// nodes and edges to the graph.
1915 /// This concept requires \ref AlterableGraphComponent.
1916 template <typename BAS = BaseGraphComponent>
1917 class ExtendableGraphComponent : public BAS {
1921 typedef typename Base::Node Node;
1922 typedef typename Base::Edge Edge;
1924 /// \brief Add a new node to the digraph.
1926 /// This function adds a new node to the digraph.
1931 /// \brief Add a new edge connecting the given two nodes.
1933 /// This function adds a new edge connecting the given two nodes
1935 Edge addEdge(const Node&, const Node&) {
1939 template <typename _Graph>
1940 struct Constraints {
1941 void constraints() {
1942 checkConcept<Base, _Graph>();
1943 typename _Graph::Node node_a, node_b;
1944 node_a = graph.addNode();
1945 node_b = graph.addNode();
1946 typename _Graph::Edge edge;
1947 edge = graph.addEdge(node_a, node_b);
1955 /// \brief Skeleton class for extendable undirected bipartite graphs.
1957 /// This class describes the interface of extendable undirected
1958 /// bipartite graphs. It extends \ref BaseGraphComponent with
1959 /// functions for adding nodes and edges to the graph. This
1960 /// concept requires \ref AlterableBpGraphComponent.
1961 template <typename BAS = BaseBpGraphComponent>
1962 class ExtendableBpGraphComponent : public BAS {
1966 typedef typename Base::Node Node;
1967 typedef typename Base::RedNode RedNode;
1968 typedef typename Base::BlueNode BlueNode;
1969 typedef typename Base::Edge Edge;
1971 /// \brief Add a new red node to the digraph.
1973 /// This function adds a red new node to the digraph.
1974 RedNode addRedNode() {
1978 /// \brief Add a new blue node to the digraph.
1980 /// This function adds a blue new node to the digraph.
1981 BlueNode addBlueNode() {
1985 /// \brief Add a new edge connecting the given two nodes.
1987 /// This function adds a new edge connecting the given two nodes
1988 /// of the graph. The first node has to be a red node, and the
1989 /// second one a blue node.
1990 Edge addEdge(const RedNode&, const BlueNode&) {
1993 Edge addEdge(const BlueNode&, const RedNode&) {
1997 template <typename _BpGraph>
1998 struct Constraints {
1999 void constraints() {
2000 checkConcept<Base, _BpGraph>();
2001 typename _BpGraph::RedNode red_node;
2002 typename _BpGraph::BlueNode blue_node;
2003 red_node = bpgraph.addRedNode();
2004 blue_node = bpgraph.addBlueNode();
2005 typename _BpGraph::Edge edge;
2006 edge = bpgraph.addEdge(red_node, blue_node);
2007 edge = bpgraph.addEdge(blue_node, red_node);
2014 /// \brief Skeleton class for erasable directed graphs.
2016 /// This class describes the interface of erasable directed graphs.
2017 /// It extends \ref BaseDigraphComponent with functions for removing
2018 /// nodes and arcs from the digraph.
2019 /// This concept requires \ref AlterableDigraphComponent.
2020 template <typename BAS = BaseDigraphComponent>
2021 class ErasableDigraphComponent : public BAS {
2025 typedef typename Base::Node Node;
2026 typedef typename Base::Arc Arc;
2028 /// \brief Erase a node from the digraph.
2030 /// This function erases the given node from the digraph and all arcs
2031 /// connected to the node.
2032 void erase(const Node&) {}
2034 /// \brief Erase an arc from the digraph.
2036 /// This function erases the given arc from the digraph.
2037 void erase(const Arc&) {}
2039 template <typename _Digraph>
2040 struct Constraints {
2041 void constraints() {
2042 checkConcept<Base, _Digraph>();
2043 const typename _Digraph::Node node(INVALID);
2044 digraph.erase(node);
2045 const typename _Digraph::Arc arc(INVALID);
2054 /// \brief Skeleton class for erasable undirected graphs.
2056 /// This class describes the interface of erasable undirected graphs.
2057 /// It extends \ref BaseGraphComponent with functions for removing
2058 /// nodes and edges from the graph.
2059 /// This concept requires \ref AlterableGraphComponent.
2060 template <typename BAS = BaseGraphComponent>
2061 class ErasableGraphComponent : public BAS {
2065 typedef typename Base::Node Node;
2066 typedef typename Base::Edge Edge;
2068 /// \brief Erase a node from the graph.
2070 /// This function erases the given node from the graph and all edges
2071 /// connected to the node.
2072 void erase(const Node&) {}
2074 /// \brief Erase an edge from the digraph.
2076 /// This function erases the given edge from the digraph.
2077 void erase(const Edge&) {}
2079 template <typename _Graph>
2080 struct Constraints {
2081 void constraints() {
2082 checkConcept<Base, _Graph>();
2083 const typename _Graph::Node node(INVALID);
2085 const typename _Graph::Edge edge(INVALID);
2094 /// \brief Skeleton class for erasable undirected graphs.
2096 /// This class describes the interface of erasable undirected
2097 /// bipartite graphs. It extends \ref BaseBpGraphComponent with
2098 /// functions for removing nodes and edges from the graph. This
2099 /// concept requires \ref AlterableBpGraphComponent.
2100 template <typename BAS = BaseBpGraphComponent>
2101 class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
2103 /// \brief Skeleton class for clearable directed graphs.
2105 /// This class describes the interface of clearable directed graphs.
2106 /// It extends \ref BaseDigraphComponent with a function for clearing
2108 /// This concept requires \ref AlterableDigraphComponent.
2109 template <typename BAS = BaseDigraphComponent>
2110 class ClearableDigraphComponent : public BAS {
2115 /// \brief Erase all nodes and arcs from the digraph.
2117 /// This function erases all nodes and arcs from the digraph.
2120 template <typename _Digraph>
2121 struct Constraints {
2122 void constraints() {
2123 checkConcept<Base, _Digraph>();
2132 /// \brief Skeleton class for clearable undirected graphs.
2134 /// This class describes the interface of clearable undirected graphs.
2135 /// It extends \ref BaseGraphComponent with a function for clearing
2137 /// This concept requires \ref AlterableGraphComponent.
2138 template <typename BAS = BaseGraphComponent>
2139 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
2141 /// \brief Skeleton class for clearable undirected biparite graphs.
2143 /// This class describes the interface of clearable undirected
2144 /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
2145 /// function for clearing the graph. This concept requires \ref
2146 /// AlterableBpGraphComponent.
2147 template <typename BAS = BaseBpGraphComponent>
2148 class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};