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 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 _GraphItem i3 = INVALID;
111 ignore_unused_variable_warning(b);
113 b = (ia == ib) && (ia != ib);
114 b = (ia == INVALID) && (ib != INVALID);
118 const _GraphItem &ia;
119 const _GraphItem &ib;
124 /// \brief Base skeleton class for directed graphs.
126 /// This class describes the base interface of directed graph types.
127 /// All digraph %concepts have to conform to this class.
128 /// It just provides types for nodes and arcs and functions
129 /// to get the source and the target nodes of arcs.
130 class BaseDigraphComponent {
133 typedef BaseDigraphComponent Digraph;
135 /// \brief Node class of the digraph.
137 /// This class represents the nodes of the digraph.
138 typedef GraphItem<'n'> Node;
140 /// \brief Arc class of the digraph.
142 /// This class represents the arcs of the digraph.
143 typedef GraphItem<'a'> Arc;
145 /// \brief Return the source node of an arc.
147 /// This function returns the source node of an arc.
148 Node source(const Arc&) const { return INVALID; }
150 /// \brief Return the target node of an arc.
152 /// This function returns the target node of an arc.
153 Node target(const Arc&) const { return INVALID; }
155 /// \brief Return the opposite node on the given arc.
157 /// This function returns the opposite node on the given arc.
158 Node oppositeNode(const Node&, const Arc&) const {
162 template <typename _Digraph>
164 typedef typename _Digraph::Node Node;
165 typedef typename _Digraph::Arc Arc;
168 checkConcept<GraphItem<'n'>, Node>();
169 checkConcept<GraphItem<'a'>, Arc>();
173 n = digraph.source(e);
174 n = digraph.target(e);
175 n = digraph.oppositeNode(n, e);
179 const _Digraph& digraph;
184 /// \brief Base skeleton class for undirected graphs.
186 /// This class describes the base interface of undirected graph types.
187 /// All graph %concepts have to conform to this class.
188 /// It extends the interface of \ref BaseDigraphComponent with an
189 /// \c Edge type and functions to get the end nodes of edges,
190 /// to convert from arcs to edges and to get both direction of edges.
191 class BaseGraphComponent : public BaseDigraphComponent {
194 typedef BaseGraphComponent Graph;
196 typedef BaseDigraphComponent::Node Node;
197 typedef BaseDigraphComponent::Arc Arc;
199 /// \brief Undirected edge class of the graph.
201 /// This class represents the undirected edges of the graph.
202 /// Undirected graphs can be used as directed graphs, each edge is
203 /// represented by two opposite directed arcs.
204 class Edge : public GraphItem<'e'> {
205 typedef GraphItem<'e'> Parent;
208 /// \brief Default constructor.
210 /// Default constructor.
211 /// \warning The default constructor is not required to set
212 /// the item to some well-defined value. So you should consider it
213 /// as uninitialized.
216 /// \brief Copy constructor.
218 /// Copy constructor.
219 Edge(const Edge &) : Parent() {}
221 /// \brief Constructor for conversion from \c INVALID.
223 /// Constructor for conversion from \c INVALID.
224 /// It initializes the item to be invalid.
225 /// \sa Invalid for more details.
228 /// \brief Constructor for conversion from an arc.
230 /// Constructor for conversion from an arc.
231 /// Besides the core graph item functionality each arc should
232 /// be convertible to the represented edge.
236 /// \brief Return one end node of an edge.
238 /// This function returns one end node of an edge.
239 Node u(const Edge&) const { return INVALID; }
241 /// \brief Return the other end node of an edge.
243 /// This function returns the other end node of an edge.
244 Node v(const Edge&) const { return INVALID; }
246 /// \brief Return a directed arc related to an edge.
248 /// This function returns a directed arc from its direction and the
249 /// represented edge.
250 Arc direct(const Edge&, bool) const { return INVALID; }
252 /// \brief Return a directed arc related to an edge.
254 /// This function returns a directed arc from its source node and the
255 /// represented edge.
256 Arc direct(const Edge&, const Node&) const { return INVALID; }
258 /// \brief Return the direction of the arc.
260 /// Returns the direction of the arc. Each arc represents an
261 /// edge with a direction. It gives back the
263 bool direction(const Arc&) const { return true; }
265 /// \brief Return the opposite arc.
267 /// This function returns the opposite arc, i.e. the arc representing
268 /// the same edge and has opposite direction.
269 Arc oppositeArc(const Arc&) const { return INVALID; }
271 template <typename _Graph>
273 typedef typename _Graph::Node Node;
274 typedef typename _Graph::Arc Arc;
275 typedef typename _Graph::Edge Edge;
278 checkConcept<BaseDigraphComponent, _Graph>();
279 checkConcept<GraphItem<'e'>, Edge>();
286 e = graph.direct(ue, true);
287 e = graph.direct(ue, false);
288 e = graph.direct(ue, n);
289 e = graph.oppositeArc(e);
291 bool d = graph.direction(e);
292 ignore_unused_variable_warning(d);
302 /// \brief Base skeleton class for undirected bipartite graphs.
304 /// This class describes the base interface of undirected
305 /// bipartite graph types. All bipartite graph %concepts have to
306 /// conform to this class. It extends the interface of \ref
307 /// BaseGraphComponent with an \c Edge type and functions to get
308 /// the end nodes of edges, to convert from arcs to edges and to
309 /// get both direction of edges.
310 class BaseBpGraphComponent : public BaseGraphComponent {
313 typedef BaseBpGraphComponent BpGraph;
315 typedef BaseDigraphComponent::Node Node;
316 typedef BaseDigraphComponent::Arc Arc;
318 /// \brief Class to represent red nodes.
320 /// This class represents the red nodes of the graph. The red
321 /// nodes can be used also as normal nodes.
322 class RedNode : public Node {
326 /// \brief Default constructor.
328 /// Default constructor.
329 /// \warning The default constructor is not required to set
330 /// the item to some well-defined value. So you should consider it
331 /// as uninitialized.
334 /// \brief Copy constructor.
336 /// Copy constructor.
337 RedNode(const RedNode &) : Parent() {}
339 /// \brief Constructor for conversion from \c INVALID.
341 /// Constructor for conversion from \c INVALID.
342 /// It initializes the item to be invalid.
343 /// \sa Invalid for more details.
347 /// \brief Class to represent blue nodes.
349 /// This class represents the blue nodes of the graph. The blue
350 /// nodes can be used also as normal nodes.
351 class BlueNode : public Node {
355 /// \brief Default constructor.
357 /// Default constructor.
358 /// \warning The default constructor is not required to set
359 /// the item to some well-defined value. So you should consider it
360 /// as uninitialized.
363 /// \brief Copy constructor.
365 /// Copy constructor.
366 BlueNode(const BlueNode &) : Parent() {}
368 /// \brief Constructor for conversion from \c INVALID.
370 /// Constructor for conversion from \c INVALID.
371 /// It initializes the item to be invalid.
372 /// \sa Invalid for more details.
375 /// \brief Constructor for conversion from a node.
377 /// Constructor for conversion from a node. The conversion can
378 /// be invalid, since the Node can be member of the red
380 BlueNode(const Node&) {}
383 /// \brief Gives back %true for red nodes.
385 /// Gives back %true for red nodes.
386 bool red(const Node&) const { return true; }
388 /// \brief Gives back %true for blue nodes.
390 /// Gives back %true for blue nodes.
391 bool blue(const Node&) const { return true; }
393 /// \brief Gives back the red end node of the edge.
395 /// Gives back the red end node of the edge.
396 RedNode redNode(const Edge&) const { return RedNode(); }
398 /// \brief Gives back the blue end node of the edge.
400 /// Gives back the blue end node of the edge.
401 BlueNode blueNode(const Edge&) const { return BlueNode(); }
403 /// \brief Converts the node to red node object.
405 /// This class is converts unsafely the node to red node
406 /// object. It should be called only if the node is from the red
407 /// partition or INVALID.
408 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
410 /// \brief Converts the node to blue node object.
412 /// This class is converts unsafely the node to blue node
413 /// object. It should be called only if the node is from the red
414 /// partition or INVALID.
415 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
417 /// \brief Converts the node to red node object.
419 /// This class is converts safely the node to red node
420 /// object. If the node is not from the red partition, then it
422 RedNode asRedNode(const Node&) const { return RedNode(); }
424 /// \brief Converts the node to blue node object.
426 /// This class is converts unsafely the node to blue node
427 /// object. If the node is not from the blue partition, then it
429 BlueNode asBlueNode(const Node&) const { return BlueNode(); }
431 /// \brief Convert the node to either red or blue node.
433 /// If the node is from the red partition then it is returned in
434 /// first and second is INVALID. If the node is from the blue
435 /// partition then it is returned in second and first is
436 /// INVALID. If the node INVALID then both first and second are
437 /// INVALID in the return value.
438 std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
439 return std::make_pair(RedNode(), BlueNode());
442 template <typename _BpGraph>
444 typedef typename _BpGraph::Node Node;
445 typedef typename _BpGraph::RedNode RedNode;
446 typedef typename _BpGraph::BlueNode BlueNode;
447 typedef typename _BpGraph::Arc Arc;
448 typedef typename _BpGraph::Edge Edge;
451 checkConcept<BaseGraphComponent, _BpGraph>();
452 checkConcept<GraphItem<'n'>, RedNode>();
453 checkConcept<GraphItem<'n'>, BlueNode>();
462 b = bpgraph.red(rnan);
463 b = bpgraph.blue(bnan);
464 rn = bpgraph.redNode(e);
465 bn = bpgraph.blueNode(e);
466 rn = bpgraph.asRedNodeUnsafe(rnan);
467 bn = bpgraph.asBlueNodeUnsafe(bnan);
468 rn = bpgraph.asRedNode(rnan);
469 bn = bpgraph.asBlueNode(bnan);
470 std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan);
471 ignore_unused_variable_warning(b,p);
475 const _BpGraph& bpgraph;
480 /// \brief Skeleton class for \e idable directed graphs.
482 /// This class describes the interface of \e idable directed graphs.
483 /// It extends \ref BaseDigraphComponent with the core ID functions.
484 /// The ids of the items must be unique and immutable.
485 /// This concept is part of the Digraph concept.
486 template <typename BAS = BaseDigraphComponent>
487 class IDableDigraphComponent : public BAS {
491 typedef typename Base::Node Node;
492 typedef typename Base::Arc Arc;
494 /// \brief Return a unique integer id for the given node.
496 /// This function returns a unique integer id for the given node.
497 int id(const Node&) const { return -1; }
499 /// \brief Return the node by its unique id.
501 /// This function returns the node by its unique id.
502 /// If the digraph does not contain a node with the given id,
503 /// then the result of the function is undefined.
504 Node nodeFromId(int) const { return INVALID; }
506 /// \brief Return a unique integer id for the given arc.
508 /// This function returns a unique integer id for the given arc.
509 int id(const Arc&) const { return -1; }
511 /// \brief Return the arc by its unique id.
513 /// This function returns the arc by its unique id.
514 /// If the digraph does not contain an arc with the given id,
515 /// then the result of the function is undefined.
516 Arc arcFromId(int) const { return INVALID; }
518 /// \brief Return an integer greater or equal to the maximum
521 /// This function returns an integer greater or equal to the
523 int maxNodeId() const { return -1; }
525 /// \brief Return an integer greater or equal to the maximum
528 /// This function returns an integer greater or equal to the
530 int maxArcId() const { return -1; }
532 template <typename _Digraph>
536 checkConcept<Base, _Digraph >();
537 typename _Digraph::Node node;
539 int nid = digraph.id(node);
540 nid = digraph.id(node);
541 node = digraph.nodeFromId(nid);
542 typename _Digraph::Arc arc;
544 int eid = digraph.id(arc);
545 eid = digraph.id(arc);
546 arc = digraph.arcFromId(eid);
548 nid = digraph.maxNodeId();
549 ignore_unused_variable_warning(nid);
550 eid = digraph.maxArcId();
551 ignore_unused_variable_warning(eid);
554 const _Digraph& digraph;
559 /// \brief Skeleton class for \e idable undirected graphs.
561 /// This class describes the interface of \e idable undirected
562 /// graphs. It extends \ref IDableDigraphComponent with the core ID
563 /// functions of undirected graphs.
564 /// The ids of the items must be unique and immutable.
565 /// This concept is part of the Graph concept.
566 template <typename BAS = BaseGraphComponent>
567 class IDableGraphComponent : public IDableDigraphComponent<BAS> {
571 typedef typename Base::Edge Edge;
573 using IDableDigraphComponent<Base>::id;
575 /// \brief Return a unique integer id for the given edge.
577 /// This function returns a unique integer id for the given edge.
578 int id(const Edge&) const { return -1; }
580 /// \brief Return the edge by its unique id.
582 /// This function returns the edge by its unique id.
583 /// If the graph does not contain an edge with the given id,
584 /// then the result of the function is undefined.
585 Edge edgeFromId(int) const { return INVALID; }
587 /// \brief Return an integer greater or equal to the maximum
590 /// This function returns an integer greater or equal to the
592 int maxEdgeId() const { return -1; }
594 template <typename _Graph>
598 checkConcept<IDableDigraphComponent<Base>, _Graph >();
599 typename _Graph::Edge edge;
600 int ueid = graph.id(edge);
601 ueid = graph.id(edge);
602 edge = graph.edgeFromId(ueid);
603 ueid = graph.maxEdgeId();
604 ignore_unused_variable_warning(ueid);
612 /// \brief Skeleton class for \e idable undirected bipartite graphs.
614 /// This class describes the interface of \e idable undirected
615 /// bipartite graphs. It extends \ref IDableGraphComponent with
616 /// the core ID functions of undirected bipartite graphs. Beside
617 /// the regular node ids, this class also provides ids within the
618 /// the red and blue sets of the nodes. This concept is part of
619 /// the BpGraph concept.
620 template <typename BAS = BaseBpGraphComponent>
621 class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
625 typedef IDableGraphComponent<BAS> Parent;
626 typedef typename Base::Node Node;
627 typedef typename Base::RedNode RedNode;
628 typedef typename Base::BlueNode BlueNode;
632 /// \brief Return a unique integer id for the given node in the red set.
634 /// Return a unique integer id for the given node in the red set.
635 int id(const RedNode&) const { return -1; }
637 /// \brief Return a unique integer id for the given node in the blue set.
639 /// Return a unique integer id for the given node in the blue set.
640 int id(const BlueNode&) const { return -1; }
642 /// \brief Return an integer greater or equal to the maximum
643 /// node id in the red set.
645 /// Return an integer greater or equal to the maximum
646 /// node id in the red set.
647 int maxRedId() const { return -1; }
649 /// \brief Return an integer greater or equal to the maximum
650 /// node id in the blue set.
652 /// Return an integer greater or equal to the maximum
653 /// node id in the blue set.
654 int maxBlueId() const { return -1; }
656 template <typename _BpGraph>
660 checkConcept<IDableGraphComponent<Base>, _BpGraph>();
661 typename _BpGraph::Node node;
662 typename _BpGraph::RedNode red;
663 typename _BpGraph::BlueNode blue;
664 int rid = bpgraph.id(red);
665 int bid = bpgraph.id(blue);
666 rid = bpgraph.maxRedId();
667 bid = bpgraph.maxBlueId();
668 ignore_unused_variable_warning(rid);
669 ignore_unused_variable_warning(bid);
672 const _BpGraph& bpgraph;
676 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
678 /// This class describes the concept of \c NodeIt, \c ArcIt and
679 /// \c EdgeIt subtypes of digraph and graph types.
680 template <typename GR, typename Item>
681 class GraphItemIt : public Item {
683 /// \brief Default constructor.
685 /// Default constructor.
686 /// \warning The default constructor is not required to set
687 /// the iterator to some well-defined value. So you should consider it
688 /// as uninitialized.
691 /// \brief Copy constructor.
693 /// Copy constructor.
694 GraphItemIt(const GraphItemIt& it) : Item(it) {}
696 /// \brief Constructor that sets the iterator to the first item.
698 /// Constructor that sets the iterator to the first item.
699 explicit GraphItemIt(const GR&) {}
701 /// \brief Constructor for conversion from \c INVALID.
703 /// Constructor for conversion from \c INVALID.
704 /// It initializes the iterator to be invalid.
705 /// \sa Invalid for more details.
706 GraphItemIt(Invalid) {}
708 /// \brief Assignment operator.
710 /// Assignment operator for the iterator.
711 GraphItemIt& operator=(const GraphItemIt&) { return *this; }
713 /// \brief Increment the iterator.
715 /// This operator increments the iterator, i.e. assigns it to the
717 GraphItemIt& operator++() { return *this; }
719 /// \brief Equality operator
721 /// Equality operator.
722 /// Two iterators are equal if and only if they point to the
723 /// same object or both are invalid.
724 bool operator==(const GraphItemIt&) const { return true;}
726 /// \brief Inequality operator
728 /// Inequality operator.
729 /// Two iterators are equal if and only if they point to the
730 /// same object or both are invalid.
731 bool operator!=(const GraphItemIt&) const { return true;}
733 template<typename _GraphItemIt>
736 checkConcept<GraphItem<>, _GraphItemIt>();
739 _GraphItemIt it3 = it1;
740 _GraphItemIt it4 = INVALID;
741 ignore_unused_variable_warning(it3);
742 ignore_unused_variable_warning(it4);
756 /// \brief Concept class for \c InArcIt, \c OutArcIt and
757 /// \c IncEdgeIt types.
759 /// This class describes the concept of \c InArcIt, \c OutArcIt
760 /// and \c IncEdgeIt subtypes of digraph and graph types.
762 /// \note Since these iterator classes do not inherit from the same
763 /// base class, there is an additional template parameter (selector)
764 /// \c sel. For \c InArcIt you should instantiate it with character
765 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
766 template <typename GR,
767 typename Item = typename GR::Arc,
768 typename Base = typename GR::Node,
770 class GraphIncIt : public Item {
772 /// \brief Default constructor.
774 /// Default constructor.
775 /// \warning The default constructor is not required to set
776 /// the iterator to some well-defined value. So you should consider it
777 /// as uninitialized.
780 /// \brief Copy constructor.
782 /// Copy constructor.
783 GraphIncIt(const GraphIncIt& it) : Item(it) {}
785 /// \brief Constructor that sets the iterator to the first
786 /// incoming or outgoing arc.
788 /// Constructor that sets the iterator to the first arc
789 /// incoming to or outgoing from the given node.
790 explicit GraphIncIt(const GR&, const Base&) {}
792 /// \brief Constructor for conversion from \c INVALID.
794 /// Constructor for conversion from \c INVALID.
795 /// It initializes the iterator to be invalid.
796 /// \sa Invalid for more details.
797 GraphIncIt(Invalid) {}
799 /// \brief Assignment operator.
801 /// Assignment operator for the iterator.
802 GraphIncIt& operator=(const GraphIncIt&) { return *this; }
804 /// \brief Increment the iterator.
806 /// This operator increments the iterator, i.e. assigns it to the
807 /// next arc incoming to or outgoing from the given node.
808 GraphIncIt& operator++() { return *this; }
810 /// \brief Equality operator
812 /// Equality operator.
813 /// Two iterators are equal if and only if they point to the
814 /// same object or both are invalid.
815 bool operator==(const GraphIncIt&) const { return true;}
817 /// \brief Inequality operator
819 /// Inequality 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 template <typename _GraphIncIt>
827 checkConcept<GraphItem<sel>, _GraphIncIt>();
828 _GraphIncIt it1(graph, node);
830 _GraphIncIt it3 = it1;
831 _GraphIncIt it4 = INVALID;
832 ignore_unused_variable_warning(it3);
833 ignore_unused_variable_warning(it4);
847 /// \brief Skeleton class for iterable directed graphs.
849 /// This class describes the interface of iterable directed
850 /// graphs. It extends \ref BaseDigraphComponent with the core
851 /// iterable interface.
852 /// This concept is part of the Digraph concept.
853 template <typename BAS = BaseDigraphComponent>
854 class IterableDigraphComponent : public BAS {
859 typedef typename Base::Node Node;
860 typedef typename Base::Arc Arc;
862 typedef IterableDigraphComponent Digraph;
864 /// \name Base Iteration
866 /// This interface provides functions for iteration on digraph items.
870 /// \brief Return the first node.
872 /// This function gives back the first node in the iteration order.
873 void first(Node&) const {}
875 /// \brief Return the next node.
877 /// This function gives back the next node in the iteration order.
878 void next(Node&) const {}
880 /// \brief Return the first arc.
882 /// This function gives back the first arc in the iteration order.
883 void first(Arc&) const {}
885 /// \brief Return the next arc.
887 /// This function gives back the next arc in the iteration order.
888 void next(Arc&) const {}
890 /// \brief Return the first arc incomming to the given node.
892 /// This function gives back the first arc incomming to the
894 void firstIn(Arc&, const Node&) const {}
896 /// \brief Return the next arc incomming to the given node.
898 /// This function gives back the next arc incomming to the
900 void nextIn(Arc&) const {}
902 /// \brief Return the first arc outgoing form the given node.
904 /// This function gives back the first arc outgoing form the
906 void firstOut(Arc&, const Node&) const {}
908 /// \brief Return the next arc outgoing form the given node.
910 /// This function gives back the next arc outgoing form the
912 void nextOut(Arc&) const {}
916 /// \name Class Based Iteration
918 /// This interface provides iterator classes for digraph items.
922 /// \brief This iterator goes through each node.
924 /// This iterator goes through each node.
926 typedef GraphItemIt<Digraph, Node> NodeIt;
928 /// \brief This iterator goes through each arc.
930 /// This iterator goes through each arc.
932 typedef GraphItemIt<Digraph, Arc> ArcIt;
934 /// \brief This iterator goes trough the incoming arcs of a node.
936 /// This iterator goes trough the \e incoming arcs of a certain node
938 typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
940 /// \brief This iterator goes trough the outgoing arcs of a node.
942 /// This iterator goes trough the \e outgoing arcs of a certain node
944 typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
946 /// \brief The base node of the iterator.
948 /// This function gives back the base node of the iterator.
949 /// It is always the target node of the pointed arc.
950 Node baseNode(const InArcIt&) const { return INVALID; }
952 /// \brief The running node of the iterator.
954 /// This function gives back the running node of the iterator.
955 /// It is always the source node of the pointed arc.
956 Node runningNode(const InArcIt&) const { return INVALID; }
958 /// \brief The base node of the iterator.
960 /// This function gives back the base node of the iterator.
961 /// It is always the source node of the pointed arc.
962 Node baseNode(const OutArcIt&) const { return INVALID; }
964 /// \brief The running node of the iterator.
966 /// This function gives back the running node of the iterator.
967 /// It is always the target node of the pointed arc.
968 Node runningNode(const OutArcIt&) const { return INVALID; }
972 template <typename _Digraph>
975 checkConcept<Base, _Digraph>();
978 typename _Digraph::Node node(INVALID);
979 typename _Digraph::Arc arc(INVALID);
989 digraph.firstIn(arc, node);
993 digraph.firstOut(arc, node);
994 digraph.nextOut(arc);
999 checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
1000 typename _Digraph::ArcIt >();
1001 checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
1002 typename _Digraph::NodeIt >();
1003 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
1004 typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
1005 checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
1006 typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
1008 typename _Digraph::Node n;
1009 const typename _Digraph::InArcIt iait(INVALID);
1010 const typename _Digraph::OutArcIt oait(INVALID);
1011 n = digraph.baseNode(iait);
1012 n = digraph.runningNode(iait);
1013 n = digraph.baseNode(oait);
1014 n = digraph.runningNode(oait);
1015 ignore_unused_variable_warning(n);
1019 const _Digraph& digraph;
1024 /// \brief Skeleton class for iterable undirected graphs.
1026 /// This class describes the interface of iterable undirected
1027 /// graphs. It extends \ref IterableDigraphComponent with the core
1028 /// iterable interface of undirected graphs.
1029 /// This concept is part of the Graph concept.
1030 template <typename BAS = BaseGraphComponent>
1031 class IterableGraphComponent : public IterableDigraphComponent<BAS> {
1035 typedef typename Base::Node Node;
1036 typedef typename Base::Arc Arc;
1037 typedef typename Base::Edge Edge;
1040 typedef IterableGraphComponent Graph;
1042 /// \name Base Iteration
1044 /// This interface provides functions for iteration on edges.
1048 using IterableDigraphComponent<Base>::first;
1049 using IterableDigraphComponent<Base>::next;
1051 /// \brief Return the first edge.
1053 /// This function gives back the first edge in the iteration order.
1054 void first(Edge&) const {}
1056 /// \brief Return the next edge.
1058 /// This function gives back the next edge in the iteration order.
1059 void next(Edge&) const {}
1061 /// \brief Return the first edge incident to the given node.
1063 /// This function gives back the first edge incident to the given
1064 /// node. The bool parameter gives back the direction for which the
1065 /// source node of the directed arc representing the edge is the
1067 void firstInc(Edge&, bool&, const Node&) const {}
1069 /// \brief Gives back the next of the edges from the
1072 /// This function gives back the next edge incident to the given
1073 /// node. The bool parameter should be used as \c firstInc() use it.
1074 void nextInc(Edge&, bool&) const {}
1076 using IterableDigraphComponent<Base>::baseNode;
1077 using IterableDigraphComponent<Base>::runningNode;
1081 /// \name Class Based Iteration
1083 /// This interface provides iterator classes for edges.
1087 /// \brief This iterator goes through each edge.
1089 /// This iterator goes through each edge.
1090 typedef GraphItemIt<Graph, Edge> EdgeIt;
1092 /// \brief This iterator goes trough the incident edges of a
1095 /// This iterator goes trough the incident edges of a certain
1096 /// node of a graph.
1097 typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
1099 /// \brief The base node of the iterator.
1101 /// This function gives back the base node of the iterator.
1102 Node baseNode(const IncEdgeIt&) const { return INVALID; }
1104 /// \brief The running node of the iterator.
1106 /// This function gives back the running node of the iterator.
1107 Node runningNode(const IncEdgeIt&) const { return INVALID; }
1111 template <typename _Graph>
1112 struct Constraints {
1113 void constraints() {
1114 checkConcept<IterableDigraphComponent<Base>, _Graph>();
1117 typename _Graph::Node node(INVALID);
1118 typename _Graph::Edge edge(INVALID);
1125 graph.firstInc(edge, dir, node);
1126 graph.nextInc(edge, dir);
1132 checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
1133 typename _Graph::EdgeIt >();
1134 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
1135 typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
1137 typename _Graph::Node n;
1138 const typename _Graph::IncEdgeIt ieit(INVALID);
1139 n = graph.baseNode(ieit);
1140 n = graph.runningNode(ieit);
1144 const _Graph& graph;
1149 /// \brief Skeleton class for iterable undirected bipartite graphs.
1151 /// This class describes the interface of iterable undirected
1152 /// bipartite graphs. It extends \ref IterableGraphComponent with
1153 /// the core iterable interface of undirected bipartite graphs.
1154 /// This concept is part of the BpGraph concept.
1155 template <typename BAS = BaseBpGraphComponent>
1156 class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
1160 typedef typename Base::Node Node;
1161 typedef typename Base::RedNode RedNode;
1162 typedef typename Base::BlueNode BlueNode;
1163 typedef typename Base::Arc Arc;
1164 typedef typename Base::Edge Edge;
1166 typedef IterableBpGraphComponent BpGraph;
1168 using IterableGraphComponent<BAS>::first;
1169 using IterableGraphComponent<BAS>::next;
1171 /// \name Base Iteration
1173 /// This interface provides functions for iteration on red and blue nodes.
1177 /// \brief Return the first red node.
1179 /// This function gives back the first red node in the iteration order.
1180 void first(RedNode&) const {}
1182 /// \brief Return the next red node.
1184 /// This function gives back the next red node in the iteration order.
1185 void next(RedNode&) const {}
1187 /// \brief Return the first blue node.
1189 /// This function gives back the first blue node in the iteration order.
1190 void first(BlueNode&) const {}
1192 /// \brief Return the next blue node.
1194 /// This function gives back the next blue node in the iteration order.
1195 void next(BlueNode&) const {}
1200 /// \name Class Based Iteration
1202 /// This interface provides iterator classes for red and blue nodes.
1206 /// \brief This iterator goes through each red node.
1208 /// This iterator goes through each red node.
1209 typedef GraphItemIt<BpGraph, RedNode> RedIt;
1211 /// \brief This iterator goes through each blue node.
1213 /// This iterator goes through each blue node.
1214 typedef GraphItemIt<BpGraph, BlueNode> BlueIt;
1218 template <typename _BpGraph>
1219 struct Constraints {
1220 void constraints() {
1221 checkConcept<IterableGraphComponent<Base>, _BpGraph>();
1223 typename _BpGraph::RedNode rn(INVALID);
1226 typename _BpGraph::BlueNode bn(INVALID);
1230 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
1231 typename _BpGraph::RedIt>();
1232 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
1233 typename _BpGraph::BlueIt>();
1236 const _BpGraph& bpgraph;
1240 /// \brief Skeleton class for alterable directed graphs.
1242 /// This class describes the interface of alterable directed
1243 /// graphs. It extends \ref BaseDigraphComponent with the alteration
1244 /// notifier interface. It implements
1245 /// an observer-notifier pattern for each digraph item. More
1246 /// obsevers can be registered into the notifier and whenever an
1247 /// alteration occured in the digraph all the observers will be
1248 /// notified about it.
1249 template <typename BAS = BaseDigraphComponent>
1250 class AlterableDigraphComponent : public BAS {
1254 typedef typename Base::Node Node;
1255 typedef typename Base::Arc Arc;
1258 /// Node alteration notifier class.
1259 typedef AlterationNotifier<AlterableDigraphComponent, Node>
1261 /// Arc alteration notifier class.
1262 typedef AlterationNotifier<AlterableDigraphComponent, Arc>
1265 mutable NodeNotifier node_notifier;
1266 mutable ArcNotifier arc_notifier;
1268 /// \brief Return the node alteration notifier.
1270 /// This function gives back the node alteration notifier.
1271 NodeNotifier& notifier(Node) const {
1272 return node_notifier;
1275 /// \brief Return the arc alteration notifier.
1277 /// This function gives back the arc alteration notifier.
1278 ArcNotifier& notifier(Arc) const {
1279 return arc_notifier;
1282 template <typename _Digraph>
1283 struct Constraints {
1284 void constraints() {
1285 checkConcept<Base, _Digraph>();
1286 typename _Digraph::NodeNotifier& nn
1287 = digraph.notifier(typename _Digraph::Node());
1289 typename _Digraph::ArcNotifier& en
1290 = digraph.notifier(typename _Digraph::Arc());
1292 ignore_unused_variable_warning(nn);
1293 ignore_unused_variable_warning(en);
1296 const _Digraph& digraph;
1301 /// \brief Skeleton class for alterable undirected graphs.
1303 /// This class describes the interface of alterable undirected
1304 /// graphs. It extends \ref AlterableDigraphComponent with the alteration
1305 /// notifier interface of undirected graphs. It implements
1306 /// an observer-notifier pattern for the edges. More
1307 /// obsevers can be registered into the notifier and whenever an
1308 /// alteration occured in the graph all the observers will be
1309 /// notified about it.
1310 template <typename BAS = BaseGraphComponent>
1311 class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
1315 typedef AlterableDigraphComponent<Base> Parent;
1316 typedef typename Base::Edge Edge;
1319 /// Edge alteration notifier class.
1320 typedef AlterationNotifier<AlterableGraphComponent, Edge>
1323 mutable EdgeNotifier edge_notifier;
1325 using Parent::notifier;
1327 /// \brief Return the edge alteration notifier.
1329 /// This function gives back the edge alteration notifier.
1330 EdgeNotifier& notifier(Edge) const {
1331 return edge_notifier;
1334 template <typename _Graph>
1335 struct Constraints {
1336 void constraints() {
1337 checkConcept<AlterableDigraphComponent<Base>, _Graph>();
1338 typename _Graph::EdgeNotifier& uen
1339 = graph.notifier(typename _Graph::Edge());
1340 ignore_unused_variable_warning(uen);
1343 const _Graph& graph;
1348 /// \brief Skeleton class for alterable undirected bipartite graphs.
1350 /// This class describes the interface of alterable undirected
1351 /// bipartite graphs. It extends \ref AlterableGraphComponent with
1352 /// the alteration notifier interface of bipartite graphs. It
1353 /// implements an observer-notifier pattern for the red and blue
1354 /// nodes. More obsevers can be registered into the notifier and
1355 /// whenever an alteration occured in the graph all the observers
1356 /// will be notified about it.
1357 template <typename BAS = BaseBpGraphComponent>
1358 class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
1362 typedef AlterableGraphComponent<Base> Parent;
1363 typedef typename Base::RedNode RedNode;
1364 typedef typename Base::BlueNode BlueNode;
1367 /// Red node alteration notifier class.
1368 typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
1371 /// Blue node alteration notifier class.
1372 typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
1375 mutable RedNodeNotifier red_node_notifier;
1376 mutable BlueNodeNotifier blue_node_notifier;
1378 using Parent::notifier;
1380 /// \brief Return the red node alteration notifier.
1382 /// This function gives back the red node alteration notifier.
1383 RedNodeNotifier& notifier(RedNode) const {
1384 return red_node_notifier;
1387 /// \brief Return the blue node alteration notifier.
1389 /// This function gives back the blue node alteration notifier.
1390 BlueNodeNotifier& notifier(BlueNode) const {
1391 return blue_node_notifier;
1394 template <typename _BpGraph>
1395 struct Constraints {
1396 void constraints() {
1397 checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
1398 typename _BpGraph::RedNodeNotifier& rnn
1399 = bpgraph.notifier(typename _BpGraph::RedNode());
1400 typename _BpGraph::BlueNodeNotifier& bnn
1401 = bpgraph.notifier(typename _BpGraph::BlueNode());
1402 ignore_unused_variable_warning(rnn);
1403 ignore_unused_variable_warning(bnn);
1406 const _BpGraph& bpgraph;
1410 /// \brief Concept class for standard graph maps.
1412 /// This class describes the concept of standard graph maps, i.e.
1413 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
1414 /// graph types, which can be used for associating data to graph items.
1415 /// The standard graph maps must conform to the ReferenceMap concept.
1416 template <typename GR, typename K, typename V>
1417 class GraphMap : public ReferenceMap<K, V, V&, const V&> {
1418 typedef ReferenceMap<K, V, V&, const V&> Parent;
1422 /// The key type of the map.
1424 /// The value type of the map.
1426 /// The reference type of the map.
1427 typedef Value& Reference;
1428 /// The const reference type of the map.
1429 typedef const Value& ConstReference;
1431 // The reference map tag.
1432 typedef True ReferenceMapTag;
1434 /// \brief Construct a new map.
1436 /// Construct a new map for the graph.
1437 explicit GraphMap(const GR&) {}
1438 /// \brief Construct a new map with default value.
1440 /// Construct a new map for the graph and initalize the values.
1441 GraphMap(const GR&, const Value&) {}
1444 /// \brief Copy constructor.
1446 /// Copy Constructor.
1447 GraphMap(const GraphMap&) : Parent() {}
1449 /// \brief Assignment operator.
1451 /// Assignment operator. It does not mofify the underlying graph,
1452 /// it just iterates on the current item set and set the map
1453 /// with the value returned by the assigned map.
1454 template <typename CMap>
1455 GraphMap& operator=(const CMap&) {
1456 checkConcept<ReadMap<Key, Value>, CMap>();
1461 template<typename _Map>
1462 struct Constraints {
1463 void constraints() {
1465 <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
1472 // Assignment operator
1473 // ReadMap<Key, Value> cmap;
1476 ignore_unused_variable_warning(m1);
1477 ignore_unused_variable_warning(m2);
1478 // ignore_unused_variable_warning(m3);
1483 const typename GraphMap::Value &t;
1489 /// \brief Skeleton class for mappable directed graphs.
1491 /// This class describes the interface of mappable directed graphs.
1492 /// It extends \ref BaseDigraphComponent with the standard digraph
1493 /// map classes, namely \c NodeMap and \c ArcMap.
1494 /// This concept is part of the Digraph concept.
1495 template <typename BAS = BaseDigraphComponent>
1496 class MappableDigraphComponent : public BAS {
1500 typedef typename Base::Node Node;
1501 typedef typename Base::Arc Arc;
1503 typedef MappableDigraphComponent Digraph;
1505 /// \brief Standard graph map for the nodes.
1507 /// Standard graph map for the nodes.
1508 /// It conforms to the ReferenceMap concept.
1509 template <typename V>
1510 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
1511 typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
1514 /// \brief Construct a new map.
1516 /// Construct a new map for the digraph.
1517 explicit NodeMap(const MappableDigraphComponent& digraph)
1518 : Parent(digraph) {}
1520 /// \brief Construct a new map with default value.
1522 /// Construct a new map for the digraph and initalize the values.
1523 NodeMap(const MappableDigraphComponent& digraph, const V& value)
1524 : Parent(digraph, value) {}
1527 /// \brief Copy constructor.
1529 /// Copy Constructor.
1530 NodeMap(const NodeMap& nm) : Parent(nm) {}
1532 /// \brief Assignment operator.
1534 /// Assignment operator.
1535 template <typename CMap>
1536 NodeMap& operator=(const CMap&) {
1537 checkConcept<ReadMap<Node, V>, CMap>();
1543 /// \brief Standard graph map for the arcs.
1545 /// Standard graph map for the arcs.
1546 /// It conforms to the ReferenceMap concept.
1547 template <typename V>
1548 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
1549 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
1552 /// \brief Construct a new map.
1554 /// Construct a new map for the digraph.
1555 explicit ArcMap(const MappableDigraphComponent& digraph)
1556 : Parent(digraph) {}
1558 /// \brief Construct a new map with default value.
1560 /// Construct a new map for the digraph and initalize the values.
1561 ArcMap(const MappableDigraphComponent& digraph, const V& value)
1562 : Parent(digraph, value) {}
1565 /// \brief Copy constructor.
1567 /// Copy Constructor.
1568 ArcMap(const ArcMap& nm) : Parent(nm) {}
1570 /// \brief Assignment operator.
1572 /// Assignment operator.
1573 template <typename CMap>
1574 ArcMap& operator=(const CMap&) {
1575 checkConcept<ReadMap<Arc, V>, CMap>();
1582 template <typename _Digraph>
1583 struct Constraints {
1587 Dummy() : value(0) {}
1588 Dummy(int _v) : value(_v) {}
1591 void constraints() {
1592 checkConcept<Base, _Digraph>();
1594 typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1595 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1597 } { // bool map test
1598 typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1599 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1601 } { // Dummy map test
1602 typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1603 checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1608 typedef typename _Digraph::template ArcMap<int> IntArcMap;
1609 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1611 } { // bool map test
1612 typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1613 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1615 } { // Dummy map test
1616 typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1617 checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1622 const _Digraph& digraph;
1627 /// \brief Skeleton class for mappable undirected graphs.
1629 /// This class describes the interface of mappable undirected graphs.
1630 /// It extends \ref MappableDigraphComponent with the standard graph
1631 /// map class for edges (\c EdgeMap).
1632 /// This concept is part of the Graph concept.
1633 template <typename BAS = BaseGraphComponent>
1634 class MappableGraphComponent : public MappableDigraphComponent<BAS> {
1638 typedef typename Base::Edge Edge;
1640 typedef MappableGraphComponent Graph;
1642 /// \brief Standard graph map for the edges.
1644 /// Standard graph map for the edges.
1645 /// It conforms to the ReferenceMap concept.
1646 template <typename V>
1647 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
1648 typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
1651 /// \brief Construct a new map.
1653 /// Construct a new map for the graph.
1654 explicit EdgeMap(const MappableGraphComponent& graph)
1657 /// \brief Construct a new map with default value.
1659 /// Construct a new map for the graph and initalize the values.
1660 EdgeMap(const MappableGraphComponent& graph, const V& value)
1661 : Parent(graph, value) {}
1664 /// \brief Copy constructor.
1666 /// Copy Constructor.
1667 EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1669 /// \brief Assignment operator.
1671 /// Assignment operator.
1672 template <typename CMap>
1673 EdgeMap& operator=(const CMap&) {
1674 checkConcept<ReadMap<Edge, V>, CMap>();
1681 template <typename _Graph>
1682 struct Constraints {
1686 Dummy() : value(0) {}
1687 Dummy(int _v) : value(_v) {}
1690 void constraints() {
1691 checkConcept<MappableDigraphComponent<Base>, _Graph>();
1694 typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1695 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1697 } { // bool map test
1698 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1699 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1701 } { // Dummy map test
1702 typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1703 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1708 const _Graph& graph;
1713 /// \brief Skeleton class for mappable undirected bipartite graphs.
1715 /// This class describes the interface of mappable undirected
1716 /// bipartite graphs. It extends \ref MappableGraphComponent with
1717 /// the standard graph map class for red and blue nodes (\c
1718 /// RedMap and BlueMap). This concept is part of the BpGraph concept.
1719 template <typename BAS = BaseBpGraphComponent>
1720 class MappableBpGraphComponent : public MappableGraphComponent<BAS> {
1724 typedef typename Base::Node Node;
1726 typedef MappableBpGraphComponent BpGraph;
1728 /// \brief Standard graph map for the red nodes.
1730 /// Standard graph map for the red nodes.
1731 /// It conforms to the ReferenceMap concept.
1732 template <typename V>
1733 class RedMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1734 typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1737 /// \brief Construct a new map.
1739 /// Construct a new map for the graph.
1740 explicit RedMap(const MappableBpGraphComponent& graph)
1743 /// \brief Construct a new map with default value.
1745 /// Construct a new map for the graph and initalize the values.
1746 RedMap(const MappableBpGraphComponent& graph, const V& value)
1747 : Parent(graph, value) {}
1750 /// \brief Copy constructor.
1752 /// Copy Constructor.
1753 RedMap(const RedMap& nm) : Parent(nm) {}
1755 /// \brief Assignment operator.
1757 /// Assignment operator.
1758 template <typename CMap>
1759 RedMap& operator=(const CMap&) {
1760 checkConcept<ReadMap<Node, V>, CMap>();
1766 /// \brief Standard graph map for the blue nodes.
1768 /// Standard graph map for the blue nodes.
1769 /// It conforms to the ReferenceMap concept.
1770 template <typename V>
1771 class BlueMap : public GraphMap<MappableBpGraphComponent, Node, V> {
1772 typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
1775 /// \brief Construct a new map.
1777 /// Construct a new map for the graph.
1778 explicit BlueMap(const MappableBpGraphComponent& graph)
1781 /// \brief Construct a new map with default value.
1783 /// Construct a new map for the graph and initalize the values.
1784 BlueMap(const MappableBpGraphComponent& graph, const V& value)
1785 : Parent(graph, value) {}
1788 /// \brief Copy constructor.
1790 /// Copy Constructor.
1791 BlueMap(const BlueMap& nm) : Parent(nm) {}
1793 /// \brief Assignment operator.
1795 /// Assignment operator.
1796 template <typename CMap>
1797 BlueMap& operator=(const CMap&) {
1798 checkConcept<ReadMap<Node, V>, CMap>();
1805 template <typename _BpGraph>
1806 struct Constraints {
1810 Dummy() : value(0) {}
1811 Dummy(int _v) : value(_v) {}
1814 void constraints() {
1815 checkConcept<MappableGraphComponent<Base>, _BpGraph>();
1818 typedef typename _BpGraph::template RedMap<int> IntRedMap;
1819 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
1821 } { // bool map test
1822 typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
1823 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
1825 } { // Dummy map test
1826 typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
1827 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
1832 typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
1833 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
1835 } { // bool map test
1836 typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
1837 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
1839 } { // Dummy map test
1840 typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
1841 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
1846 const _BpGraph& bpgraph;
1850 /// \brief Skeleton class for extendable directed graphs.
1852 /// This class describes the interface of extendable directed graphs.
1853 /// It extends \ref BaseDigraphComponent with functions for adding
1854 /// nodes and arcs to the digraph.
1855 /// This concept requires \ref AlterableDigraphComponent.
1856 template <typename BAS = BaseDigraphComponent>
1857 class ExtendableDigraphComponent : public BAS {
1861 typedef typename Base::Node Node;
1862 typedef typename Base::Arc Arc;
1864 /// \brief Add a new node to the digraph.
1866 /// This function adds a new node to the digraph.
1871 /// \brief Add a new arc connecting the given two nodes.
1873 /// This function adds a new arc connecting the given two nodes
1875 Arc addArc(const Node&, const Node&) {
1879 template <typename _Digraph>
1880 struct Constraints {
1881 void constraints() {
1882 checkConcept<Base, _Digraph>();
1883 typename _Digraph::Node node_a, node_b;
1884 node_a = digraph.addNode();
1885 node_b = digraph.addNode();
1886 typename _Digraph::Arc arc;
1887 arc = digraph.addArc(node_a, node_b);
1895 /// \brief Skeleton class for extendable undirected graphs.
1897 /// This class describes the interface of extendable undirected graphs.
1898 /// It extends \ref BaseGraphComponent with functions for adding
1899 /// nodes and edges to the graph.
1900 /// This concept requires \ref AlterableGraphComponent.
1901 template <typename BAS = BaseGraphComponent>
1902 class ExtendableGraphComponent : public BAS {
1906 typedef typename Base::Node Node;
1907 typedef typename Base::Edge Edge;
1909 /// \brief Add a new node to the digraph.
1911 /// This function adds a new node to the digraph.
1916 /// \brief Add a new edge connecting the given two nodes.
1918 /// This function adds a new edge connecting the given two nodes
1920 Edge addEdge(const Node&, const Node&) {
1924 template <typename _Graph>
1925 struct Constraints {
1926 void constraints() {
1927 checkConcept<Base, _Graph>();
1928 typename _Graph::Node node_a, node_b;
1929 node_a = graph.addNode();
1930 node_b = graph.addNode();
1931 typename _Graph::Edge edge;
1932 edge = graph.addEdge(node_a, node_b);
1940 /// \brief Skeleton class for extendable undirected bipartite graphs.
1942 /// This class describes the interface of extendable undirected
1943 /// bipartite graphs. It extends \ref BaseGraphComponent with
1944 /// functions for adding nodes and edges to the graph. This
1945 /// concept requires \ref AlterableBpGraphComponent.
1946 template <typename BAS = BaseBpGraphComponent>
1947 class ExtendableBpGraphComponent : public BAS {
1951 typedef typename Base::Node Node;
1952 typedef typename Base::RedNode RedNode;
1953 typedef typename Base::BlueNode BlueNode;
1954 typedef typename Base::Edge Edge;
1956 /// \brief Add a new red node to the digraph.
1958 /// This function adds a red new node to the digraph.
1959 RedNode addRedNode() {
1963 /// \brief Add a new blue node to the digraph.
1965 /// This function adds a blue new node to the digraph.
1966 BlueNode addBlueNode() {
1970 /// \brief Add a new edge connecting the given two nodes.
1972 /// This function adds a new edge connecting the given two nodes
1973 /// of the graph. The first node has to be a red node, and the
1974 /// second one a blue node.
1975 Edge addEdge(const RedNode&, const BlueNode&) {
1978 Edge addEdge(const BlueNode&, const RedNode&) {
1982 template <typename _BpGraph>
1983 struct Constraints {
1984 void constraints() {
1985 checkConcept<Base, _BpGraph>();
1986 typename _BpGraph::RedNode red_node;
1987 typename _BpGraph::BlueNode blue_node;
1988 red_node = bpgraph.addRedNode();
1989 blue_node = bpgraph.addBlueNode();
1990 typename _BpGraph::Edge edge;
1991 edge = bpgraph.addEdge(red_node, blue_node);
1992 edge = bpgraph.addEdge(blue_node, red_node);
1999 /// \brief Skeleton class for erasable directed graphs.
2001 /// This class describes the interface of erasable directed graphs.
2002 /// It extends \ref BaseDigraphComponent with functions for removing
2003 /// nodes and arcs from the digraph.
2004 /// This concept requires \ref AlterableDigraphComponent.
2005 template <typename BAS = BaseDigraphComponent>
2006 class ErasableDigraphComponent : public BAS {
2010 typedef typename Base::Node Node;
2011 typedef typename Base::Arc Arc;
2013 /// \brief Erase a node from the digraph.
2015 /// This function erases the given node from the digraph and all arcs
2016 /// connected to the node.
2017 void erase(const Node&) {}
2019 /// \brief Erase an arc from the digraph.
2021 /// This function erases the given arc from the digraph.
2022 void erase(const Arc&) {}
2024 template <typename _Digraph>
2025 struct Constraints {
2026 void constraints() {
2027 checkConcept<Base, _Digraph>();
2028 const typename _Digraph::Node node(INVALID);
2029 digraph.erase(node);
2030 const typename _Digraph::Arc arc(INVALID);
2039 /// \brief Skeleton class for erasable undirected graphs.
2041 /// This class describes the interface of erasable undirected graphs.
2042 /// It extends \ref BaseGraphComponent with functions for removing
2043 /// nodes and edges from the graph.
2044 /// This concept requires \ref AlterableGraphComponent.
2045 template <typename BAS = BaseGraphComponent>
2046 class ErasableGraphComponent : public BAS {
2050 typedef typename Base::Node Node;
2051 typedef typename Base::Edge Edge;
2053 /// \brief Erase a node from the graph.
2055 /// This function erases the given node from the graph and all edges
2056 /// connected to the node.
2057 void erase(const Node&) {}
2059 /// \brief Erase an edge from the digraph.
2061 /// This function erases the given edge from the digraph.
2062 void erase(const Edge&) {}
2064 template <typename _Graph>
2065 struct Constraints {
2066 void constraints() {
2067 checkConcept<Base, _Graph>();
2068 const typename _Graph::Node node(INVALID);
2070 const typename _Graph::Edge edge(INVALID);
2079 /// \brief Skeleton class for erasable undirected graphs.
2081 /// This class describes the interface of erasable undirected
2082 /// bipartite graphs. It extends \ref BaseBpGraphComponent with
2083 /// functions for removing nodes and edges from the graph. This
2084 /// concept requires \ref AlterableBpGraphComponent.
2085 template <typename BAS = BaseBpGraphComponent>
2086 class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
2088 /// \brief Skeleton class for clearable directed graphs.
2090 /// This class describes the interface of clearable directed graphs.
2091 /// It extends \ref BaseDigraphComponent with a function for clearing
2093 /// This concept requires \ref AlterableDigraphComponent.
2094 template <typename BAS = BaseDigraphComponent>
2095 class ClearableDigraphComponent : public BAS {
2100 /// \brief Erase all nodes and arcs from the digraph.
2102 /// This function erases all nodes and arcs from the digraph.
2105 template <typename _Digraph>
2106 struct Constraints {
2107 void constraints() {
2108 checkConcept<Base, _Digraph>();
2117 /// \brief Skeleton class for clearable undirected graphs.
2119 /// This class describes the interface of clearable undirected graphs.
2120 /// It extends \ref BaseGraphComponent with a function for clearing
2122 /// This concept requires \ref AlterableGraphComponent.
2123 template <typename BAS = BaseGraphComponent>
2124 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
2126 /// \brief Skeleton class for clearable undirected biparite graphs.
2128 /// This class describes the interface of clearable undirected
2129 /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
2130 /// function for clearing the graph. This concept requires \ref
2131 /// AlterableBpGraphComponent.
2132 template <typename BAS = BaseBpGraphComponent>
2133 class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};