alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@57: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. deba@57: * alpar@1092: * Copyright (C) 2003-2013 deba@57: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@57: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@57: * deba@57: * Permission to use, modify and distribute this software is granted deba@57: * provided that this copyright notice appears in all copies. For deba@57: * precise terms see the accompanying LICENSE file. deba@57: * deba@57: * This software is provided "AS IS" with no warranty of any kind, deba@57: * express or implied, and with no claim as to its suitability for any deba@57: * purpose. deba@57: * deba@57: */ deba@57: deba@57: ///\ingroup graph_concepts deba@57: ///\file kpeter@786: ///\brief The concepts of graph components. deba@57: deba@529: #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H deba@529: #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H deba@57: deba@220: #include deba@57: #include deba@57: deba@57: #include deba@57: deba@57: namespace lemon { deba@57: namespace concepts { deba@57: kpeter@579: /// \brief Concept class for \c Node, \c Arc and \c Edge types. deba@57: /// kpeter@579: /// This class describes the concept of \c Node, \c Arc and \c Edge kpeter@579: /// subtypes of digraph and graph types. deba@57: /// deba@57: /// \note This class is a template class so that we can use it to kpeter@579: /// create graph skeleton classes. The reason for this is that \c Node alpar@877: /// and \c Arc (or \c Edge) types should \e not derive from the same kpeter@579: /// base class. For \c Node you should instantiate it with character kpeter@579: /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. deba@57: #ifndef DOXYGEN kpeter@559: template deba@57: #endif deba@57: class GraphItem { deba@57: public: deba@57: /// \brief Default constructor. alpar@209: /// kpeter@579: /// Default constructor. deba@57: /// \warning The default constructor is not required to set deba@57: /// the item to some well-defined value. So you should consider it deba@57: /// as uninitialized. deba@57: GraphItem() {} kpeter@579: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@579: GraphItem(const GraphItem &) {} kpeter@579: kpeter@579: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@579: /// Constructor for conversion from \c INVALID. kpeter@579: /// It initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphItem(Invalid) {} kpeter@579: kpeter@579: /// \brief Assignment operator. deba@57: /// kpeter@579: /// Assignment operator for the item. kpeter@579: GraphItem& operator=(const GraphItem&) { return *this; } kpeter@579: alpar@666: /// \brief Assignment operator for INVALID. alpar@666: /// alpar@666: /// This operator makes the item invalid. alpar@666: GraphItem& operator=(Invalid) { return *this; } alpar@666: deba@57: /// \brief Equality operator. deba@57: /// kpeter@579: /// Equality operator. kpeter@579: bool operator==(const GraphItem&) const { return false; } kpeter@579: deba@57: /// \brief Inequality operator. deba@57: /// kpeter@579: /// Inequality operator. kpeter@579: bool operator!=(const GraphItem&) const { return false; } kpeter@579: kpeter@579: /// \brief Ordering operator. deba@57: /// kpeter@579: /// This operator defines an ordering of the items. alpar@877: /// It makes possible to use graph item types as key types in kpeter@579: /// associative containers (e.g. \c std::map). deba@57: /// kpeter@734: /// \note This operator only has to define some strict ordering of deba@57: /// the items; this order has nothing to do with the iteration deba@57: /// ordering of the items. kpeter@579: bool operator<(const GraphItem&) const { return false; } deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { alpar@209: _GraphItem i1; alpar@666: i1=INVALID; alpar@209: _GraphItem i2 = i1; kpeter@1197: ::lemon::ignore_unused_variable_warning(i2); alpar@209: _GraphItem i3 = INVALID; deba@57: alpar@209: i1 = i2 = i3; alpar@209: alpar@209: bool b; alpar@1083: ::lemon::ignore_unused_variable_warning(b); alpar@1007: alpar@209: b = (ia == ib) && (ia != ib); alpar@209: b = (ia == INVALID) && (ib != INVALID); deba@57: b = (ia < ib); alpar@209: } deba@57: alpar@209: const _GraphItem &ia; alpar@209: const _GraphItem &ib; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Base skeleton class for directed graphs. alpar@209: /// kpeter@579: /// This class describes the base interface of directed graph types. kpeter@579: /// All digraph %concepts have to conform to this class. alpar@877: /// It just provides types for nodes and arcs and functions kpeter@579: /// to get the source and the target nodes of arcs. deba@57: class BaseDigraphComponent { deba@57: public: deba@57: deba@57: typedef BaseDigraphComponent Digraph; alpar@209: deba@57: /// \brief Node class of the digraph. deba@57: /// kpeter@579: /// This class represents the nodes of the digraph. deba@57: typedef GraphItem<'n'> Node; deba@57: deba@57: /// \brief Arc class of the digraph. deba@57: /// kpeter@579: /// This class represents the arcs of the digraph. kpeter@579: typedef GraphItem<'a'> Arc; kpeter@579: kpeter@579: /// \brief Return the source node of an arc. deba@57: /// kpeter@579: /// This function returns the source node of an arc. kpeter@579: Node source(const Arc&) const { return INVALID; } deba@57: kpeter@579: /// \brief Return the target node of an arc. deba@57: /// kpeter@579: /// This function returns the target node of an arc. kpeter@579: Node target(const Arc&) const { return INVALID; } kpeter@579: kpeter@579: /// \brief Return the opposite node on the given arc. deba@57: /// kpeter@579: /// This function returns the opposite node on the given arc. deba@57: Node oppositeNode(const Node&, const Arc&) const { deba@57: return INVALID; deba@57: } deba@57: deba@57: template deba@57: struct Constraints { alpar@209: typedef typename _Digraph::Node Node; alpar@209: typedef typename _Digraph::Arc Arc; alpar@209: alpar@209: void constraints() { alpar@209: checkConcept, Node>(); alpar@209: checkConcept, Arc>(); alpar@209: { alpar@209: Node n; alpar@209: Arc e(INVALID); alpar@209: n = digraph.source(e); alpar@209: n = digraph.target(e); deba@57: n = digraph.oppositeNode(n, e); alpar@209: } alpar@209: } alpar@209: alpar@209: const _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Base skeleton class for undirected graphs. alpar@209: /// kpeter@579: /// This class describes the base interface of undirected graph types. kpeter@579: /// All graph %concepts have to conform to this class. kpeter@579: /// It extends the interface of \ref BaseDigraphComponent with an kpeter@579: /// \c Edge type and functions to get the end nodes of edges, kpeter@579: /// to convert from arcs to edges and to get both direction of edges. deba@57: class BaseGraphComponent : public BaseDigraphComponent { deba@57: public: kpeter@617: kpeter@617: typedef BaseGraphComponent Graph; kpeter@617: deba@57: typedef BaseDigraphComponent::Node Node; deba@57: typedef BaseDigraphComponent::Arc Arc; kpeter@579: kpeter@579: /// \brief Undirected edge class of the graph. deba@57: /// kpeter@579: /// This class represents the undirected edges of the graph. kpeter@579: /// Undirected graphs can be used as directed graphs, each edge is kpeter@579: /// represented by two opposite directed arcs. kpeter@579: class Edge : public GraphItem<'e'> { kpeter@579: typedef GraphItem<'e'> Parent; kpeter@579: kpeter@617: public: deba@57: /// \brief Default constructor. alpar@209: /// kpeter@579: /// Default constructor. deba@57: /// \warning The default constructor is not required to set deba@57: /// the item to some well-defined value. So you should consider it deba@57: /// as uninitialized. deba@57: Edge() {} kpeter@579: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@579: Edge(const Edge &) : Parent() {} kpeter@579: kpeter@579: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@579: /// Constructor for conversion from \c INVALID. kpeter@579: /// It initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: Edge(Invalid) {} kpeter@579: kpeter@579: /// \brief Constructor for conversion from an arc. deba@57: /// kpeter@579: /// Constructor for conversion from an arc. deba@57: /// Besides the core graph item functionality each arc should alpar@209: /// be convertible to the represented edge. deba@57: Edge(const Arc&) {} alpar@666: }; deba@57: kpeter@579: /// \brief Return one end node of an edge. kpeter@579: /// kpeter@579: /// This function returns one end node of an edge. kpeter@579: Node u(const Edge&) const { return INVALID; } kpeter@579: kpeter@579: /// \brief Return the other end node of an edge. kpeter@579: /// kpeter@579: /// This function returns the other end node of an edge. kpeter@579: Node v(const Edge&) const { return INVALID; } kpeter@579: kpeter@579: /// \brief Return a directed arc related to an edge. kpeter@579: /// kpeter@579: /// This function returns a directed arc from its direction and the kpeter@579: /// represented edge. kpeter@579: Arc direct(const Edge&, bool) const { return INVALID; } kpeter@579: kpeter@579: /// \brief Return a directed arc related to an edge. kpeter@579: /// kpeter@579: /// This function returns a directed arc from its source node and the kpeter@579: /// represented edge. kpeter@579: Arc direct(const Edge&, const Node&) const { return INVALID; } kpeter@579: kpeter@579: /// \brief Return the direction of the arc. deba@57: /// deba@57: /// Returns the direction of the arc. Each arc represents an deba@57: /// edge with a direction. It gives back the deba@57: /// direction. deba@57: bool direction(const Arc&) const { return true; } deba@57: kpeter@579: /// \brief Return the opposite arc. deba@57: /// kpeter@579: /// This function returns the opposite arc, i.e. the arc representing kpeter@579: /// the same edge and has opposite direction. kpeter@579: Arc oppositeArc(const Arc&) const { return INVALID; } alpar@209: deba@57: template deba@57: struct Constraints { alpar@209: typedef typename _Graph::Node Node; alpar@209: typedef typename _Graph::Arc Arc; alpar@209: typedef typename _Graph::Edge Edge; alpar@209: alpar@209: void constraints() { deba@57: checkConcept(); kpeter@579: checkConcept, Edge>(); alpar@209: { alpar@209: Node n; alpar@209: Edge ue(INVALID); deba@57: Arc e; alpar@209: n = graph.u(ue); alpar@209: n = graph.v(ue); deba@57: e = graph.direct(ue, true); kpeter@579: e = graph.direct(ue, false); deba@57: e = graph.direct(ue, n); deba@57: e = graph.oppositeArc(e); deba@57: ue = e; deba@57: bool d = graph.direction(e); alpar@1083: ::lemon::ignore_unused_variable_warning(d); alpar@209: } alpar@209: } alpar@209: alpar@209: const _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: deba@57: }; deba@57: deba@1018: /// \brief Base skeleton class for undirected bipartite graphs. deba@1018: /// deba@1018: /// This class describes the base interface of undirected deba@1018: /// bipartite graph types. All bipartite graph %concepts have to deba@1018: /// conform to this class. It extends the interface of \ref deba@1018: /// BaseGraphComponent with an \c Edge type and functions to get deba@1018: /// the end nodes of edges, to convert from arcs to edges and to deba@1018: /// get both direction of edges. deba@1018: class BaseBpGraphComponent : public BaseGraphComponent { deba@1018: public: deba@1018: deba@1018: typedef BaseBpGraphComponent BpGraph; deba@1018: deba@1018: typedef BaseDigraphComponent::Node Node; deba@1018: typedef BaseDigraphComponent::Arc Arc; deba@1018: deba@1018: /// \brief Class to represent red nodes. deba@1018: /// deba@1025: /// This class represents the red nodes of the graph. The red deba@1028: /// nodes can also be used as normal nodes. deba@1018: class RedNode : public Node { deba@1018: typedef Node Parent; deba@1018: deba@1018: public: deba@1018: /// \brief Default constructor. deba@1018: /// deba@1018: /// Default constructor. deba@1018: /// \warning The default constructor is not required to set deba@1018: /// the item to some well-defined value. So you should consider it deba@1018: /// as uninitialized. deba@1018: RedNode() {} deba@1018: deba@1018: /// \brief Copy constructor. deba@1018: /// deba@1018: /// Copy constructor. deba@1018: RedNode(const RedNode &) : Parent() {} deba@1018: deba@1018: /// \brief Constructor for conversion from \c INVALID. deba@1018: /// deba@1018: /// Constructor for conversion from \c INVALID. deba@1018: /// It initializes the item to be invalid. deba@1018: /// \sa Invalid for more details. deba@1018: RedNode(Invalid) {} deba@1018: }; deba@1018: deba@1018: /// \brief Class to represent blue nodes. deba@1018: /// deba@1025: /// This class represents the blue nodes of the graph. The blue deba@1028: /// nodes can also be used as normal nodes. deba@1018: class BlueNode : public Node { deba@1018: typedef Node Parent; deba@1018: deba@1018: public: deba@1018: /// \brief Default constructor. deba@1018: /// deba@1018: /// Default constructor. deba@1018: /// \warning The default constructor is not required to set deba@1018: /// the item to some well-defined value. So you should consider it deba@1018: /// as uninitialized. deba@1018: BlueNode() {} deba@1018: deba@1018: /// \brief Copy constructor. deba@1018: /// deba@1018: /// Copy constructor. deba@1018: BlueNode(const BlueNode &) : Parent() {} deba@1018: deba@1018: /// \brief Constructor for conversion from \c INVALID. deba@1018: /// deba@1018: /// Constructor for conversion from \c INVALID. deba@1018: /// It initializes the item to be invalid. deba@1018: /// \sa Invalid for more details. deba@1018: BlueNode(Invalid) {} deba@1018: deba@1018: /// \brief Constructor for conversion from a node. deba@1018: /// deba@1018: /// Constructor for conversion from a node. The conversion can deba@1018: /// be invalid, since the Node can be member of the red deba@1018: /// set. deba@1018: BlueNode(const Node&) {} deba@1018: }; deba@1018: deba@1018: /// \brief Gives back %true for red nodes. deba@1018: /// deba@1018: /// Gives back %true for red nodes. deba@1018: bool red(const Node&) const { return true; } deba@1018: deba@1018: /// \brief Gives back %true for blue nodes. deba@1018: /// deba@1018: /// Gives back %true for blue nodes. deba@1018: bool blue(const Node&) const { return true; } deba@1018: deba@1018: /// \brief Gives back the red end node of the edge. alpar@1092: /// deba@1018: /// Gives back the red end node of the edge. deba@1025: RedNode redNode(const Edge&) const { return RedNode(); } deba@1018: deba@1018: /// \brief Gives back the blue end node of the edge. alpar@1092: /// deba@1018: /// Gives back the blue end node of the edge. deba@1025: BlueNode blueNode(const Edge&) const { return BlueNode(); } deba@1025: deba@1025: /// \brief Converts the node to red node object. deba@1025: /// deba@1028: /// This function converts unsafely the node to red node deba@1025: /// object. It should be called only if the node is from the red deba@1025: /// partition or INVALID. deba@1025: RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); } deba@1025: deba@1025: /// \brief Converts the node to blue node object. deba@1025: /// deba@1028: /// This function converts unsafely the node to blue node deba@1025: /// object. It should be called only if the node is from the red deba@1025: /// partition or INVALID. deba@1025: BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); } deba@1025: deba@1025: /// \brief Converts the node to red node object. deba@1025: /// deba@1028: /// This function converts safely the node to red node deba@1025: /// object. If the node is not from the red partition, then it deba@1025: /// returns INVALID. deba@1025: RedNode asRedNode(const Node&) const { return RedNode(); } deba@1025: deba@1025: /// \brief Converts the node to blue node object. deba@1025: /// deba@1028: /// This function converts unsafely the node to blue node deba@1025: /// object. If the node is not from the blue partition, then it deba@1025: /// returns INVALID. deba@1025: BlueNode asBlueNode(const Node&) const { return BlueNode(); } deba@1025: deba@1018: template deba@1018: struct Constraints { deba@1018: typedef typename _BpGraph::Node Node; deba@1018: typedef typename _BpGraph::RedNode RedNode; deba@1018: typedef typename _BpGraph::BlueNode BlueNode; deba@1018: typedef typename _BpGraph::Arc Arc; deba@1018: typedef typename _BpGraph::Edge Edge; deba@1018: deba@1018: void constraints() { deba@1018: checkConcept(); deba@1018: checkConcept, RedNode>(); deba@1018: checkConcept, BlueNode>(); deba@1018: { deba@1018: Node n; deba@1025: RedNode rn; deba@1025: BlueNode bn; deba@1025: Node rnan = rn; deba@1025: Node bnan = bn; deba@1018: Edge e; deba@1018: bool b; deba@1025: b = bpgraph.red(rnan); deba@1025: b = bpgraph.blue(bnan); deba@1025: rn = bpgraph.redNode(e); deba@1025: bn = bpgraph.blueNode(e); deba@1025: rn = bpgraph.asRedNodeUnsafe(rnan); deba@1025: bn = bpgraph.asBlueNodeUnsafe(bnan); deba@1025: rn = bpgraph.asRedNode(rnan); deba@1025: bn = bpgraph.asBlueNode(bnan); alpar@1087: ::lemon::ignore_unused_variable_warning(b); deba@1018: } deba@1018: } deba@1018: deba@1018: const _BpGraph& bpgraph; deba@1018: }; deba@1018: deba@1018: }; deba@1018: kpeter@579: /// \brief Skeleton class for \e idable directed graphs. alpar@209: /// kpeter@579: /// This class describes the interface of \e idable directed graphs. kpeter@579: /// It extends \ref BaseDigraphComponent with the core ID functions. kpeter@579: /// The ids of the items must be unique and immutable. kpeter@579: /// This concept is part of the Digraph concept. kpeter@559: template kpeter@559: class IDableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: kpeter@579: /// \brief Return a unique integer id for the given node. deba@57: /// kpeter@579: /// This function returns a unique integer id for the given node. kpeter@579: int id(const Node&) const { return -1; } kpeter@579: kpeter@579: /// \brief Return the node by its unique id. deba@57: /// kpeter@579: /// This function returns the node by its unique id. kpeter@579: /// If the digraph does not contain a node with the given id, kpeter@579: /// then the result of the function is undefined. kpeter@579: Node nodeFromId(int) const { return INVALID; } deba@57: kpeter@579: /// \brief Return a unique integer id for the given arc. deba@57: /// kpeter@579: /// This function returns a unique integer id for the given arc. kpeter@579: int id(const Arc&) const { return -1; } deba@57: kpeter@579: /// \brief Return the arc by its unique id. deba@57: /// kpeter@579: /// This function returns the arc by its unique id. kpeter@579: /// If the digraph does not contain an arc with the given id, kpeter@579: /// then the result of the function is undefined. kpeter@579: Arc arcFromId(int) const { return INVALID; } kpeter@579: kpeter@579: /// \brief Return an integer greater or equal to the maximum kpeter@579: /// node id. deba@57: /// kpeter@579: /// This function returns an integer greater or equal to the kpeter@579: /// maximum node id. kpeter@579: int maxNodeId() const { return -1; } deba@57: kpeter@579: /// \brief Return an integer greater or equal to the maximum kpeter@579: /// arc id. deba@57: /// kpeter@579: /// This function returns an integer greater or equal to the kpeter@579: /// maximum arc id. kpeter@579: int maxArcId() const { return -1; } deba@57: deba@57: template deba@57: struct Constraints { deba@57: alpar@209: void constraints() { alpar@209: checkConcept(); alpar@209: typename _Digraph::Node node; alpar@666: node=INVALID; alpar@209: int nid = digraph.id(node); alpar@209: nid = digraph.id(node); alpar@209: node = digraph.nodeFromId(nid); alpar@209: typename _Digraph::Arc arc; alpar@666: arc=INVALID; alpar@209: int eid = digraph.id(arc); alpar@209: eid = digraph.id(arc); alpar@209: arc = digraph.arcFromId(eid); deba@57: alpar@209: nid = digraph.maxNodeId(); alpar@1083: ::lemon::ignore_unused_variable_warning(nid); alpar@209: eid = digraph.maxArcId(); alpar@1083: ::lemon::ignore_unused_variable_warning(eid); alpar@209: } deba@57: alpar@209: const _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for \e idable undirected graphs. alpar@209: /// kpeter@579: /// This class describes the interface of \e idable undirected kpeter@579: /// graphs. It extends \ref IDableDigraphComponent with the core ID kpeter@579: /// functions of undirected graphs. kpeter@579: /// The ids of the items must be unique and immutable. kpeter@579: /// This concept is part of the Graph concept. kpeter@559: template kpeter@559: class IDableGraphComponent : public IDableDigraphComponent { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Edge Edge; deba@57: kpeter@559: using IDableDigraphComponent::id; deba@57: kpeter@579: /// \brief Return a unique integer id for the given edge. deba@57: /// kpeter@579: /// This function returns a unique integer id for the given edge. kpeter@579: int id(const Edge&) const { return -1; } kpeter@579: kpeter@579: /// \brief Return the edge by its unique id. deba@57: /// kpeter@579: /// This function returns the edge by its unique id. kpeter@579: /// If the graph does not contain an edge with the given id, kpeter@579: /// then the result of the function is undefined. kpeter@579: Edge edgeFromId(int) const { return INVALID; } deba@57: kpeter@579: /// \brief Return an integer greater or equal to the maximum kpeter@579: /// edge id. deba@57: /// kpeter@579: /// This function returns an integer greater or equal to the kpeter@579: /// maximum edge id. kpeter@579: int maxEdgeId() const { return -1; } deba@57: deba@57: template deba@57: struct Constraints { deba@57: alpar@209: void constraints() { alpar@209: checkConcept, _Graph >(); alpar@209: typename _Graph::Edge edge; alpar@209: int ueid = graph.id(edge); alpar@209: ueid = graph.id(edge); alpar@209: edge = graph.edgeFromId(ueid); alpar@209: ueid = graph.maxEdgeId(); alpar@1083: ::lemon::ignore_unused_variable_warning(ueid); alpar@209: } deba@57: alpar@209: const _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: deba@1018: /// \brief Skeleton class for \e idable undirected bipartite graphs. deba@1018: /// deba@1018: /// This class describes the interface of \e idable undirected deba@1018: /// bipartite graphs. It extends \ref IDableGraphComponent with deba@1018: /// the core ID functions of undirected bipartite graphs. Beside deba@1018: /// the regular node ids, this class also provides ids within the deba@1018: /// the red and blue sets of the nodes. This concept is part of deba@1018: /// the BpGraph concept. deba@1018: template deba@1018: class IDableBpGraphComponent : public IDableGraphComponent { deba@1018: public: deba@1018: deba@1018: typedef BAS Base; deba@1018: typedef IDableGraphComponent Parent; deba@1018: typedef typename Base::Node Node; deba@1018: typedef typename Base::RedNode RedNode; deba@1018: typedef typename Base::BlueNode BlueNode; deba@1018: deba@1018: using Parent::id; deba@1018: deba@1018: /// \brief Return a unique integer id for the given node in the red set. deba@1018: /// deba@1018: /// Return a unique integer id for the given node in the red set. deba@1018: int id(const RedNode&) const { return -1; } deba@1018: deba@1018: /// \brief Return a unique integer id for the given node in the blue set. deba@1018: /// deba@1018: /// Return a unique integer id for the given node in the blue set. deba@1018: int id(const BlueNode&) const { return -1; } deba@1018: deba@1018: /// \brief Return an integer greater or equal to the maximum deba@1018: /// node id in the red set. deba@1018: /// deba@1018: /// Return an integer greater or equal to the maximum deba@1018: /// node id in the red set. deba@1018: int maxRedId() const { return -1; } deba@1018: deba@1018: /// \brief Return an integer greater or equal to the maximum deba@1018: /// node id in the blue set. deba@1018: /// deba@1018: /// Return an integer greater or equal to the maximum deba@1018: /// node id in the blue set. deba@1018: int maxBlueId() const { return -1; } deba@1018: deba@1018: template deba@1018: struct Constraints { deba@1018: deba@1018: void constraints() { deba@1018: checkConcept, _BpGraph>(); deba@1018: typename _BpGraph::Node node; deba@1018: typename _BpGraph::RedNode red; deba@1018: typename _BpGraph::BlueNode blue; deba@1025: int rid = bpgraph.id(red); deba@1025: int bid = bpgraph.id(blue); deba@1018: rid = bpgraph.maxRedId(); deba@1018: bid = bpgraph.maxBlueId(); alpar@1087: ::lemon::ignore_unused_variable_warning(rid); alpar@1087: ::lemon::ignore_unused_variable_warning(bid); deba@1018: } deba@1018: deba@1018: const _BpGraph& bpgraph; deba@1018: }; deba@1018: }; deba@1018: kpeter@579: /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. deba@57: /// alpar@877: /// This class describes the concept of \c NodeIt, \c ArcIt and kpeter@579: /// \c EdgeIt subtypes of digraph and graph types. kpeter@559: template kpeter@559: class GraphItemIt : public Item { deba@57: public: deba@57: /// \brief Default constructor. deba@57: /// kpeter@579: /// Default constructor. kpeter@579: /// \warning The default constructor is not required to set kpeter@579: /// the iterator to some well-defined value. So you should consider it kpeter@579: /// as uninitialized. deba@57: GraphItemIt() {} kpeter@579: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@579: GraphItemIt(const GraphItemIt& it) : Item(it) {} kpeter@579: kpeter@579: /// \brief Constructor that sets the iterator to the first item. deba@57: /// kpeter@579: /// Constructor that sets the iterator to the first item. kpeter@579: explicit GraphItemIt(const GR&) {} kpeter@579: kpeter@579: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@579: /// Constructor for conversion from \c INVALID. kpeter@579: /// It initializes the iterator to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphItemIt(Invalid) {} kpeter@579: kpeter@579: /// \brief Assignment operator. deba@57: /// kpeter@579: /// Assignment operator for the iterator. kpeter@579: GraphItemIt& operator=(const GraphItemIt&) { return *this; } kpeter@579: kpeter@579: /// \brief Increment the iterator. deba@57: /// kpeter@579: /// This operator increments the iterator, i.e. assigns it to the kpeter@579: /// next item. deba@57: GraphItemIt& operator++() { return *this; } alpar@877: deba@57: /// \brief Equality operator alpar@209: /// kpeter@579: /// Equality operator. deba@57: /// Two iterators are equal if and only if they point to the deba@57: /// same object or both are invalid. deba@57: bool operator==(const GraphItemIt&) const { return true;} kpeter@579: deba@57: /// \brief Inequality operator alpar@209: /// kpeter@579: /// Inequality operator. kpeter@579: /// Two iterators are equal if and only if they point to the kpeter@579: /// same object or both are invalid. deba@57: bool operator!=(const GraphItemIt&) const { return true;} alpar@209: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { kpeter@579: checkConcept, _GraphItemIt>(); alpar@209: _GraphItemIt it1(g); alpar@209: _GraphItemIt it2; kpeter@579: _GraphItemIt it3 = it1; kpeter@579: _GraphItemIt it4 = INVALID; alpar@1083: ::lemon::ignore_unused_variable_warning(it3); alpar@1083: ::lemon::ignore_unused_variable_warning(it4); deba@57: alpar@209: it2 = ++it1; alpar@209: ++it2 = it1; alpar@209: ++(++it1); deba@57: kpeter@559: Item bi = it1; kpeter@1197: ::lemon::ignore_unused_variable_warning(bi); alpar@209: bi = it2; alpar@209: } kpeter@579: const GR& g; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: alpar@877: /// \brief Concept class for \c InArcIt, \c OutArcIt and kpeter@579: /// \c IncEdgeIt types. deba@57: /// alpar@877: /// This class describes the concept of \c InArcIt, \c OutArcIt kpeter@579: /// and \c IncEdgeIt subtypes of digraph and graph types. kpeter@579: /// kpeter@579: /// \note Since these iterator classes do not inherit from the same kpeter@579: /// base class, there is an additional template parameter (selector) alpar@877: /// \c sel. For \c InArcIt you should instantiate it with character kpeter@579: /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. kpeter@559: template kpeter@559: class GraphIncIt : public Item { deba@57: public: deba@57: /// \brief Default constructor. deba@57: /// kpeter@579: /// Default constructor. kpeter@579: /// \warning The default constructor is not required to set kpeter@579: /// the iterator to some well-defined value. So you should consider it kpeter@579: /// as uninitialized. deba@57: GraphIncIt() {} kpeter@579: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@579: GraphIncIt(const GraphIncIt& it) : Item(it) {} kpeter@579: alpar@877: /// \brief Constructor that sets the iterator to the first kpeter@579: /// incoming or outgoing arc. deba@57: /// alpar@877: /// Constructor that sets the iterator to the first arc kpeter@579: /// incoming to or outgoing from the given node. kpeter@579: explicit GraphIncIt(const GR&, const Base&) {} kpeter@579: kpeter@579: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@579: /// Constructor for conversion from \c INVALID. kpeter@579: /// It initializes the iterator to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphIncIt(Invalid) {} kpeter@579: kpeter@579: /// \brief Assignment operator. deba@57: /// kpeter@579: /// Assignment operator for the iterator. kpeter@579: GraphIncIt& operator=(const GraphIncIt&) { return *this; } kpeter@579: kpeter@579: /// \brief Increment the iterator. deba@57: /// kpeter@579: /// This operator increments the iterator, i.e. assigns it to the kpeter@579: /// next arc incoming to or outgoing from the given node. deba@57: GraphIncIt& operator++() { return *this; } deba@57: deba@57: /// \brief Equality operator deba@57: /// kpeter@579: /// Equality operator. deba@57: /// Two iterators are equal if and only if they point to the deba@57: /// same object or both are invalid. deba@57: bool operator==(const GraphIncIt&) const { return true;} deba@57: deba@57: /// \brief Inequality operator deba@57: /// kpeter@579: /// Inequality operator. kpeter@579: /// Two iterators are equal if and only if they point to the kpeter@579: /// same object or both are invalid. deba@57: bool operator!=(const GraphIncIt&) const { return true;} deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { kpeter@559: checkConcept, _GraphIncIt>(); alpar@209: _GraphIncIt it1(graph, node); alpar@209: _GraphIncIt it2; kpeter@579: _GraphIncIt it3 = it1; kpeter@579: _GraphIncIt it4 = INVALID; alpar@1083: ::lemon::ignore_unused_variable_warning(it3); alpar@1083: ::lemon::ignore_unused_variable_warning(it4); deba@57: alpar@209: it2 = ++it1; alpar@209: ++it2 = it1; alpar@209: ++(++it1); kpeter@559: Item e = it1; kpeter@1197: ::lemon::ignore_unused_variable_warning(e); alpar@209: e = it2; alpar@209: } kpeter@579: const Base& node; kpeter@579: const GR& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for iterable directed graphs. deba@57: /// kpeter@579: /// This class describes the interface of iterable directed kpeter@579: /// graphs. It extends \ref BaseDigraphComponent with the core kpeter@579: /// iterable interface. deba@57: /// This concept is part of the Digraph concept. kpeter@559: template kpeter@559: class IterableDigraphComponent : public BAS { deba@57: deba@57: public: alpar@209: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: deba@57: typedef IterableDigraphComponent Digraph; deba@57: kpeter@584: /// \name Base Iteration alpar@209: /// kpeter@579: /// This interface provides functions for iteration on digraph items. deba@57: /// alpar@209: /// @{ deba@57: kpeter@579: /// \brief Return the first node. alpar@209: /// kpeter@579: /// This function gives back the first node in the iteration order. deba@57: void first(Node&) const {} deba@57: kpeter@579: /// \brief Return the next node. deba@57: /// kpeter@579: /// This function gives back the next node in the iteration order. deba@57: void next(Node&) const {} deba@57: kpeter@579: /// \brief Return the first arc. deba@57: /// kpeter@579: /// This function gives back the first arc in the iteration order. deba@57: void first(Arc&) const {} deba@57: kpeter@579: /// \brief Return the next arc. deba@57: /// kpeter@579: /// This function gives back the next arc in the iteration order. deba@57: void next(Arc&) const {} deba@57: kpeter@1049: /// \brief Return the first arc incoming to the given node. deba@57: /// kpeter@1049: /// This function gives back the first arc incoming to the kpeter@579: /// given node. deba@57: void firstIn(Arc&, const Node&) const {} deba@57: kpeter@1049: /// \brief Return the next arc incoming to the given node. deba@57: /// kpeter@1049: /// This function gives back the next arc incoming to the kpeter@579: /// given node. deba@57: void nextIn(Arc&) const {} deba@57: kpeter@579: /// \brief Return the first arc outgoing form the given node. kpeter@579: /// kpeter@579: /// This function gives back the first arc outgoing form the deba@57: /// given node. deba@57: void firstOut(Arc&, const Node&) const {} deba@57: kpeter@579: /// \brief Return the next arc outgoing form the given node. deba@57: /// kpeter@579: /// This function gives back the next arc outgoing form the kpeter@579: /// given node. deba@57: void nextOut(Arc&) const {} deba@57: deba@57: /// @} deba@57: kpeter@584: /// \name Class Based Iteration alpar@209: /// kpeter@579: /// This interface provides iterator classes for digraph items. deba@57: /// deba@57: /// @{ deba@57: deba@57: /// \brief This iterator goes through each node. deba@57: /// deba@57: /// This iterator goes through each node. deba@57: /// deba@57: typedef GraphItemIt NodeIt; deba@57: kpeter@579: /// \brief This iterator goes through each arc. deba@57: /// kpeter@579: /// This iterator goes through each arc. deba@57: /// deba@57: typedef GraphItemIt ArcIt; deba@57: deba@57: /// \brief This iterator goes trough the incoming arcs of a node. deba@57: /// kpeter@579: /// This iterator goes trough the \e incoming arcs of a certain node deba@57: /// of a digraph. deba@57: typedef GraphIncIt InArcIt; deba@57: deba@57: /// \brief This iterator goes trough the outgoing arcs of a node. deba@57: /// deba@57: /// This iterator goes trough the \e outgoing arcs of a certain node deba@57: /// of a digraph. deba@57: typedef GraphIncIt OutArcIt; deba@57: deba@57: /// \brief The base node of the iterator. deba@57: /// kpeter@579: /// This function gives back the base node of the iterator. kpeter@579: /// It is always the target node of the pointed arc. deba@57: Node baseNode(const InArcIt&) const { return INVALID; } deba@57: deba@57: /// \brief The running node of the iterator. deba@57: /// kpeter@579: /// This function gives back the running node of the iterator. kpeter@579: /// It is always the source node of the pointed arc. deba@57: Node runningNode(const InArcIt&) const { return INVALID; } deba@57: deba@57: /// \brief The base node of the iterator. deba@57: /// kpeter@579: /// This function gives back the base node of the iterator. kpeter@579: /// It is always the source node of the pointed arc. deba@57: Node baseNode(const OutArcIt&) const { return INVALID; } deba@57: deba@57: /// \brief The running node of the iterator. deba@57: /// kpeter@579: /// This function gives back the running node of the iterator. kpeter@579: /// It is always the target node of the pointed arc. deba@57: Node runningNode(const OutArcIt&) const { return INVALID; } deba@57: deba@57: /// @} deba@57: alpar@209: template deba@57: struct Constraints { alpar@209: void constraints() { alpar@209: checkConcept(); deba@57: deba@57: { alpar@209: typename _Digraph::Node node(INVALID); deba@57: typename _Digraph::Arc arc(INVALID); deba@57: { deba@57: digraph.first(node); deba@57: digraph.next(node); deba@57: } deba@57: { deba@57: digraph.first(arc); deba@57: digraph.next(arc); deba@57: } deba@57: { deba@57: digraph.firstIn(arc, node); deba@57: digraph.nextIn(arc); deba@57: } deba@57: { deba@57: digraph.firstOut(arc, node); deba@57: digraph.nextOut(arc); deba@57: } alpar@209: } deba@57: deba@57: { deba@57: checkConcept, deba@57: typename _Digraph::ArcIt >(); deba@57: checkConcept, deba@57: typename _Digraph::NodeIt >(); alpar@209: checkConcept, typename _Digraph::InArcIt>(); alpar@209: checkConcept, typename _Digraph::OutArcIt>(); deba@57: deba@57: typename _Digraph::Node n; kpeter@579: const typename _Digraph::InArcIt iait(INVALID); kpeter@579: const typename _Digraph::OutArcIt oait(INVALID); kpeter@579: n = digraph.baseNode(iait); kpeter@579: n = digraph.runningNode(iait); kpeter@579: n = digraph.baseNode(oait); kpeter@579: n = digraph.runningNode(oait); alpar@1083: ::lemon::ignore_unused_variable_warning(n); deba@57: } deba@57: } alpar@209: alpar@209: const _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for iterable undirected graphs. deba@57: /// kpeter@579: /// This class describes the interface of iterable undirected kpeter@579: /// graphs. It extends \ref IterableDigraphComponent with the core kpeter@579: /// iterable interface of undirected graphs. deba@57: /// This concept is part of the Graph concept. kpeter@559: template kpeter@559: class IterableGraphComponent : public IterableDigraphComponent { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: typedef typename Base::Edge Edge; deba@57: alpar@209: deba@57: typedef IterableGraphComponent Graph; deba@57: kpeter@584: /// \name Base Iteration alpar@209: /// kpeter@579: /// This interface provides functions for iteration on edges. kpeter@579: /// alpar@209: /// @{ deba@57: kpeter@559: using IterableDigraphComponent::first; kpeter@559: using IterableDigraphComponent::next; deba@57: kpeter@579: /// \brief Return the first edge. deba@57: /// kpeter@579: /// This function gives back the first edge in the iteration order. deba@57: void first(Edge&) const {} deba@57: kpeter@579: /// \brief Return the next edge. deba@57: /// kpeter@579: /// This function gives back the next edge in the iteration order. deba@57: void next(Edge&) const {} deba@57: kpeter@579: /// \brief Return the first edge incident to the given node. kpeter@579: /// alpar@877: /// This function gives back the first edge incident to the given kpeter@579: /// node. The bool parameter gives back the direction for which the alpar@877: /// source node of the directed arc representing the edge is the deba@57: /// given node. deba@57: void firstInc(Edge&, bool&, const Node&) const {} deba@57: deba@57: /// \brief Gives back the next of the edges from the deba@57: /// given node. deba@57: /// alpar@877: /// This function gives back the next edge incident to the given kpeter@579: /// node. The bool parameter should be used as \c firstInc() use it. deba@57: void nextInc(Edge&, bool&) const {} deba@57: kpeter@559: using IterableDigraphComponent::baseNode; kpeter@559: using IterableDigraphComponent::runningNode; deba@57: deba@57: /// @} deba@57: kpeter@584: /// \name Class Based Iteration alpar@209: /// kpeter@579: /// This interface provides iterator classes for edges. deba@57: /// deba@57: /// @{ deba@57: kpeter@579: /// \brief This iterator goes through each edge. deba@57: /// kpeter@579: /// This iterator goes through each edge. deba@57: typedef GraphItemIt EdgeIt; kpeter@579: kpeter@579: /// \brief This iterator goes trough the incident edges of a deba@57: /// node. deba@57: /// kpeter@579: /// This iterator goes trough the incident edges of a certain deba@57: /// node of a graph. kpeter@579: typedef GraphIncIt IncEdgeIt; kpeter@579: deba@57: /// \brief The base node of the iterator. deba@57: /// kpeter@579: /// This function gives back the base node of the iterator. deba@78: Node baseNode(const IncEdgeIt&) const { return INVALID; } deba@57: deba@57: /// \brief The running node of the iterator. deba@57: /// kpeter@579: /// This function gives back the running node of the iterator. deba@78: Node runningNode(const IncEdgeIt&) const { return INVALID; } deba@57: deba@57: /// @} deba@57: alpar@209: template deba@57: struct Constraints { alpar@209: void constraints() { alpar@209: checkConcept, _Graph>(); deba@57: deba@57: { deba@57: typename _Graph::Node node(INVALID); deba@57: typename _Graph::Edge edge(INVALID); deba@57: bool dir; deba@57: { deba@57: graph.first(edge); deba@57: graph.next(edge); deba@57: } deba@57: { deba@57: graph.firstInc(edge, dir, node); deba@57: graph.nextInc(edge, dir); deba@57: } alpar@209: alpar@209: } alpar@209: deba@57: { deba@57: checkConcept, deba@57: typename _Graph::EdgeIt >(); alpar@209: checkConcept, typename _Graph::IncEdgeIt>(); alpar@209: deba@57: typename _Graph::Node n; kpeter@579: const typename _Graph::IncEdgeIt ieit(INVALID); kpeter@579: n = graph.baseNode(ieit); kpeter@579: n = graph.runningNode(ieit); deba@57: } deba@57: } alpar@209: alpar@209: const _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: deba@1018: /// \brief Skeleton class for iterable undirected bipartite graphs. deba@1018: /// deba@1018: /// This class describes the interface of iterable undirected deba@1018: /// bipartite graphs. It extends \ref IterableGraphComponent with deba@1018: /// the core iterable interface of undirected bipartite graphs. deba@1018: /// This concept is part of the BpGraph concept. deba@1018: template deba@1018: class IterableBpGraphComponent : public IterableGraphComponent { deba@1018: public: deba@1018: deba@1018: typedef BAS Base; deba@1018: typedef typename Base::Node Node; deba@1025: typedef typename Base::RedNode RedNode; deba@1025: typedef typename Base::BlueNode BlueNode; deba@1018: typedef typename Base::Arc Arc; deba@1018: typedef typename Base::Edge Edge; alpar@1092: deba@1025: typedef IterableBpGraphComponent BpGraph; deba@1018: deba@1025: using IterableGraphComponent::first; deba@1025: using IterableGraphComponent::next; deba@1018: deba@1018: /// \name Base Iteration deba@1018: /// deba@1018: /// This interface provides functions for iteration on red and blue nodes. deba@1018: /// deba@1018: /// @{ deba@1018: deba@1018: /// \brief Return the first red node. deba@1018: /// deba@1018: /// This function gives back the first red node in the iteration order. deba@1025: void first(RedNode&) const {} deba@1018: deba@1018: /// \brief Return the next red node. deba@1018: /// deba@1018: /// This function gives back the next red node in the iteration order. deba@1025: void next(RedNode&) const {} deba@1018: deba@1018: /// \brief Return the first blue node. deba@1018: /// deba@1018: /// This function gives back the first blue node in the iteration order. deba@1025: void first(BlueNode&) const {} deba@1018: deba@1018: /// \brief Return the next blue node. deba@1018: /// deba@1018: /// This function gives back the next blue node in the iteration order. deba@1025: void next(BlueNode&) const {} deba@1018: deba@1018: deba@1018: /// @} deba@1018: deba@1018: /// \name Class Based Iteration deba@1018: /// deba@1018: /// This interface provides iterator classes for red and blue nodes. deba@1018: /// deba@1018: /// @{ deba@1018: deba@1018: /// \brief This iterator goes through each red node. deba@1018: /// deba@1018: /// This iterator goes through each red node. deba@1026: typedef GraphItemIt RedNodeIt; deba@1018: deba@1018: /// \brief This iterator goes through each blue node. deba@1018: /// deba@1018: /// This iterator goes through each blue node. deba@1026: typedef GraphItemIt BlueNodeIt; deba@1018: deba@1018: /// @} deba@1018: deba@1018: template deba@1018: struct Constraints { deba@1018: void constraints() { deba@1018: checkConcept, _BpGraph>(); deba@1018: deba@1025: typename _BpGraph::RedNode rn(INVALID); deba@1025: bpgraph.first(rn); alpar@1092: bpgraph.next(rn); deba@1025: typename _BpGraph::BlueNode bn(INVALID); deba@1025: bpgraph.first(bn); deba@1025: bpgraph.next(bn); deba@1018: deba@1025: checkConcept, deba@1026: typename _BpGraph::RedNodeIt>(); deba@1025: checkConcept, deba@1026: typename _BpGraph::BlueNodeIt>(); deba@1018: } deba@1018: deba@1018: const _BpGraph& bpgraph; deba@1018: }; deba@1018: }; deba@1018: kpeter@579: /// \brief Skeleton class for alterable directed graphs. alpar@209: /// kpeter@579: /// This class describes the interface of alterable directed kpeter@579: /// graphs. It extends \ref BaseDigraphComponent with the alteration kpeter@579: /// notifier interface. It implements deba@57: /// an observer-notifier pattern for each digraph item. More deba@57: /// obsevers can be registered into the notifier and whenever an kpeter@579: /// alteration occured in the digraph all the observers will be deba@57: /// notified about it. kpeter@559: template kpeter@559: class AlterableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: deba@57: kpeter@579: /// Node alteration notifier class. alpar@209: typedef AlterationNotifier deba@57: NodeNotifier; kpeter@579: /// Arc alteration notifier class. alpar@209: typedef AlterationNotifier deba@57: ArcNotifier; alpar@209: deba@1018: mutable NodeNotifier node_notifier; deba@1018: mutable ArcNotifier arc_notifier; deba@1018: kpeter@579: /// \brief Return the node alteration notifier. deba@57: /// kpeter@579: /// This function gives back the node alteration notifier. deba@57: NodeNotifier& notifier(Node) const { deba@1018: return node_notifier; deba@57: } alpar@209: kpeter@579: /// \brief Return the arc alteration notifier. deba@57: /// kpeter@579: /// This function gives back the arc alteration notifier. deba@57: ArcNotifier& notifier(Arc) const { deba@1018: return arc_notifier; deba@57: } deba@57: alpar@209: template deba@57: struct Constraints { alpar@209: void constraints() { alpar@209: checkConcept(); alpar@209: typename _Digraph::NodeNotifier& nn deba@57: = digraph.notifier(typename _Digraph::Node()); deba@57: alpar@209: typename _Digraph::ArcNotifier& en deba@57: = digraph.notifier(typename _Digraph::Arc()); alpar@209: alpar@1083: ::lemon::ignore_unused_variable_warning(nn); alpar@1083: ::lemon::ignore_unused_variable_warning(en); alpar@209: } alpar@209: alpar@209: const _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for alterable undirected graphs. alpar@209: /// kpeter@579: /// This class describes the interface of alterable undirected kpeter@579: /// graphs. It extends \ref AlterableDigraphComponent with the alteration kpeter@579: /// notifier interface of undirected graphs. It implements kpeter@579: /// an observer-notifier pattern for the edges. More deba@57: /// obsevers can be registered into the notifier and whenever an kpeter@579: /// alteration occured in the graph all the observers will be deba@57: /// notified about it. kpeter@559: template kpeter@559: class AlterableGraphComponent : public AlterableDigraphComponent { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@1018: typedef AlterableDigraphComponent Parent; deba@57: typedef typename Base::Edge Edge; deba@57: deba@57: kpeter@579: /// Edge alteration notifier class. alpar@209: typedef AlterationNotifier deba@57: EdgeNotifier; alpar@209: deba@1018: mutable EdgeNotifier edge_notifier; deba@1018: deba@1018: using Parent::notifier; deba@1018: kpeter@579: /// \brief Return the edge alteration notifier. deba@57: /// kpeter@579: /// This function gives back the edge alteration notifier. deba@57: EdgeNotifier& notifier(Edge) const { deba@1018: return edge_notifier; deba@57: } deba@57: alpar@209: template deba@57: struct Constraints { alpar@209: void constraints() { kpeter@579: checkConcept, _Graph>(); alpar@209: typename _Graph::EdgeNotifier& uen deba@57: = graph.notifier(typename _Graph::Edge()); alpar@1083: ::lemon::ignore_unused_variable_warning(uen); alpar@209: } alpar@209: alpar@209: const _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: deba@1018: /// \brief Skeleton class for alterable undirected bipartite graphs. deba@1018: /// deba@1018: /// This class describes the interface of alterable undirected deba@1018: /// bipartite graphs. It extends \ref AlterableGraphComponent with deba@1018: /// the alteration notifier interface of bipartite graphs. It deba@1018: /// implements an observer-notifier pattern for the red and blue deba@1018: /// nodes. More obsevers can be registered into the notifier and deba@1018: /// whenever an alteration occured in the graph all the observers deba@1018: /// will be notified about it. deba@1018: template deba@1018: class AlterableBpGraphComponent : public AlterableGraphComponent { deba@1018: public: deba@1018: deba@1018: typedef BAS Base; deba@1018: typedef AlterableGraphComponent Parent; deba@1018: typedef typename Base::RedNode RedNode; deba@1018: typedef typename Base::BlueNode BlueNode; deba@1018: deba@1018: deba@1018: /// Red node alteration notifier class. deba@1018: typedef AlterationNotifier deba@1018: RedNodeNotifier; deba@1018: deba@1018: /// Blue node alteration notifier class. deba@1018: typedef AlterationNotifier deba@1018: BlueNodeNotifier; deba@1018: deba@1018: mutable RedNodeNotifier red_node_notifier; deba@1018: mutable BlueNodeNotifier blue_node_notifier; deba@1018: deba@1018: using Parent::notifier; deba@1018: deba@1018: /// \brief Return the red node alteration notifier. deba@1018: /// deba@1018: /// This function gives back the red node alteration notifier. deba@1018: RedNodeNotifier& notifier(RedNode) const { deba@1018: return red_node_notifier; deba@1018: } deba@1018: deba@1018: /// \brief Return the blue node alteration notifier. deba@1018: /// deba@1018: /// This function gives back the blue node alteration notifier. deba@1018: BlueNodeNotifier& notifier(BlueNode) const { deba@1018: return blue_node_notifier; deba@1018: } deba@1018: deba@1018: template deba@1018: struct Constraints { deba@1018: void constraints() { deba@1018: checkConcept, _BpGraph>(); deba@1018: typename _BpGraph::RedNodeNotifier& rnn deba@1018: = bpgraph.notifier(typename _BpGraph::RedNode()); deba@1018: typename _BpGraph::BlueNodeNotifier& bnn deba@1018: = bpgraph.notifier(typename _BpGraph::BlueNode()); alpar@1087: ::lemon::ignore_unused_variable_warning(rnn); alpar@1087: ::lemon::ignore_unused_variable_warning(bnn); deba@1018: } deba@1018: deba@1018: const _BpGraph& bpgraph; deba@1018: }; deba@1018: }; deba@1018: kpeter@579: /// \brief Concept class for standard graph maps. alpar@209: /// kpeter@579: /// This class describes the concept of standard graph maps, i.e. alpar@877: /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and kpeter@579: /// graph types, which can be used for associating data to graph items. kpeter@580: /// The standard graph maps must conform to the ReferenceMap concept. kpeter@559: template kpeter@580: class GraphMap : public ReferenceMap { kpeter@617: typedef ReferenceMap Parent; kpeter@617: deba@57: public: deba@57: deba@57: /// The key type of the map. kpeter@559: typedef K Key; deba@57: /// The value type of the map. kpeter@559: typedef V Value; kpeter@580: /// The reference type of the map. kpeter@580: typedef Value& Reference; kpeter@580: /// The const reference type of the map. kpeter@580: typedef const Value& ConstReference; kpeter@580: kpeter@580: // The reference map tag. kpeter@580: typedef True ReferenceMapTag; deba@57: deba@57: /// \brief Construct a new map. deba@57: /// deba@57: /// Construct a new map for the graph. kpeter@617: explicit GraphMap(const GR&) {} deba@57: /// \brief Construct a new map with default value. deba@57: /// kpeter@579: /// Construct a new map for the graph and initalize the values. kpeter@617: GraphMap(const GR&, const Value&) {} kpeter@263: kpeter@263: private: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy Constructor. deba@57: GraphMap(const GraphMap&) : Parent() {} alpar@209: kpeter@579: /// \brief Assignment operator. deba@57: /// kpeter@579: /// Assignment operator. It does not mofify the underlying graph, deba@57: /// it just iterates on the current item set and set the map alpar@209: /// with the value returned by the assigned map. deba@57: template alpar@209: GraphMap& operator=(const CMap&) { deba@57: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: kpeter@263: public: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { kpeter@580: checkConcept kpeter@580: , _Map>(); kpeter@579: _Map m1(g); kpeter@579: _Map m2(g,t); alpar@877: kpeter@579: // Copy constructor kpeter@579: // _Map m3(m); alpar@209: kpeter@579: // Assignment operator kpeter@263: // ReadMap cmap; kpeter@579: // m3 = cmap; deba@57: alpar@1083: ::lemon::ignore_unused_variable_warning(m1); alpar@1083: ::lemon::ignore_unused_variable_warning(m2); alpar@1083: // ::lemon::ignore_unused_variable_warning(m3); alpar@209: } deba@57: kpeter@579: const _Map &m; kpeter@617: const GR &g; alpar@209: const typename GraphMap::Value &t; alpar@975: Constraints() {} deba@57: }; deba@57: deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for mappable directed graphs. deba@57: /// kpeter@579: /// This class describes the interface of mappable directed graphs. alpar@877: /// It extends \ref BaseDigraphComponent with the standard digraph kpeter@579: /// map classes, namely \c NodeMap and \c ArcMap. deba@57: /// This concept is part of the Digraph concept. kpeter@559: template kpeter@559: class MappableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: deba@57: typedef MappableDigraphComponent Digraph; deba@57: kpeter@579: /// \brief Standard graph map for the nodes. deba@57: /// kpeter@579: /// Standard graph map for the nodes. kpeter@580: /// It conforms to the ReferenceMap concept. kpeter@559: template kpeter@579: class NodeMap : public GraphMap { kpeter@559: typedef GraphMap Parent; deba@57: kpeter@617: public: alpar@209: /// \brief Construct a new map. alpar@209: /// alpar@209: /// Construct a new map for the digraph. alpar@209: explicit NodeMap(const MappableDigraphComponent& digraph) deba@57: : Parent(digraph) {} deba@57: alpar@209: /// \brief Construct a new map with default value. alpar@209: /// kpeter@579: /// Construct a new map for the digraph and initalize the values. kpeter@559: NodeMap(const MappableDigraphComponent& digraph, const V& value) deba@57: : Parent(digraph, value) {} deba@57: kpeter@263: private: alpar@209: /// \brief Copy constructor. alpar@209: /// alpar@209: /// Copy Constructor. alpar@209: NodeMap(const NodeMap& nm) : Parent(nm) {} deba@57: kpeter@579: /// \brief Assignment operator. alpar@209: /// kpeter@579: /// Assignment operator. deba@57: template alpar@209: NodeMap& operator=(const CMap&) { kpeter@559: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: deba@57: }; deba@57: kpeter@579: /// \brief Standard graph map for the arcs. deba@57: /// kpeter@579: /// Standard graph map for the arcs. kpeter@580: /// It conforms to the ReferenceMap concept. kpeter@559: template kpeter@579: class ArcMap : public GraphMap { kpeter@559: typedef GraphMap Parent; deba@57: kpeter@617: public: alpar@209: /// \brief Construct a new map. alpar@209: /// alpar@209: /// Construct a new map for the digraph. alpar@209: explicit ArcMap(const MappableDigraphComponent& digraph) deba@57: : Parent(digraph) {} deba@57: alpar@209: /// \brief Construct a new map with default value. alpar@209: /// kpeter@579: /// Construct a new map for the digraph and initalize the values. kpeter@559: ArcMap(const MappableDigraphComponent& digraph, const V& value) deba@57: : Parent(digraph, value) {} deba@57: kpeter@263: private: alpar@209: /// \brief Copy constructor. alpar@209: /// alpar@209: /// Copy Constructor. alpar@209: ArcMap(const ArcMap& nm) : Parent(nm) {} deba@57: kpeter@579: /// \brief Assignment operator. alpar@209: /// kpeter@579: /// Assignment operator. deba@57: template alpar@209: ArcMap& operator=(const CMap&) { kpeter@559: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: deba@57: }; deba@57: deba@57: deba@57: template deba@57: struct Constraints { deba@57: alpar@209: struct Dummy { alpar@209: int value; alpar@209: Dummy() : value(0) {} alpar@209: Dummy(int _v) : value(_v) {} alpar@209: }; deba@57: alpar@209: void constraints() { alpar@209: checkConcept(); alpar@209: { // int map test alpar@209: typedef typename _Digraph::template NodeMap IntNodeMap; alpar@209: checkConcept, alpar@209: IntNodeMap >(); alpar@209: } { // bool map test alpar@209: typedef typename _Digraph::template NodeMap BoolNodeMap; alpar@209: checkConcept, alpar@209: BoolNodeMap >(); alpar@209: } { // Dummy map test alpar@209: typedef typename _Digraph::template NodeMap DummyNodeMap; alpar@209: checkConcept, alpar@209: DummyNodeMap >(); alpar@209: } deba@57: alpar@209: { // int map test alpar@209: typedef typename _Digraph::template ArcMap IntArcMap; alpar@209: checkConcept, alpar@209: IntArcMap >(); alpar@209: } { // bool map test alpar@209: typedef typename _Digraph::template ArcMap BoolArcMap; alpar@209: checkConcept, alpar@209: BoolArcMap >(); alpar@209: } { // Dummy map test alpar@209: typedef typename _Digraph::template ArcMap DummyArcMap; alpar@209: checkConcept, alpar@209: DummyArcMap >(); alpar@209: } alpar@209: } deba@57: kpeter@579: const _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for mappable undirected graphs. deba@57: /// kpeter@579: /// This class describes the interface of mappable undirected graphs. alpar@877: /// It extends \ref MappableDigraphComponent with the standard graph kpeter@579: /// map class for edges (\c EdgeMap). deba@57: /// This concept is part of the Graph concept. kpeter@559: template kpeter@559: class MappableGraphComponent : public MappableDigraphComponent { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Edge Edge; deba@57: deba@57: typedef MappableGraphComponent Graph; deba@57: kpeter@579: /// \brief Standard graph map for the edges. deba@57: /// kpeter@579: /// Standard graph map for the edges. kpeter@580: /// It conforms to the ReferenceMap concept. kpeter@559: template kpeter@579: class EdgeMap : public GraphMap { kpeter@559: typedef GraphMap Parent; deba@57: kpeter@617: public: alpar@209: /// \brief Construct a new map. alpar@209: /// alpar@209: /// Construct a new map for the graph. alpar@209: explicit EdgeMap(const MappableGraphComponent& graph) deba@57: : Parent(graph) {} deba@57: alpar@209: /// \brief Construct a new map with default value. alpar@209: /// kpeter@579: /// Construct a new map for the graph and initalize the values. kpeter@559: EdgeMap(const MappableGraphComponent& graph, const V& value) deba@57: : Parent(graph, value) {} deba@57: kpeter@263: private: alpar@209: /// \brief Copy constructor. alpar@209: /// alpar@209: /// Copy Constructor. alpar@209: EdgeMap(const EdgeMap& nm) : Parent(nm) {} deba@57: kpeter@579: /// \brief Assignment operator. alpar@209: /// kpeter@579: /// Assignment operator. deba@57: template alpar@209: EdgeMap& operator=(const CMap&) { kpeter@559: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: deba@57: }; deba@57: deba@57: deba@57: template deba@57: struct Constraints { deba@57: alpar@209: struct Dummy { alpar@209: int value; alpar@209: Dummy() : value(0) {} alpar@209: Dummy(int _v) : value(_v) {} alpar@209: }; deba@57: alpar@209: void constraints() { kpeter@579: checkConcept, _Graph>(); deba@57: alpar@209: { // int map test alpar@209: typedef typename _Graph::template EdgeMap IntEdgeMap; alpar@209: checkConcept, alpar@209: IntEdgeMap >(); alpar@209: } { // bool map test alpar@209: typedef typename _Graph::template EdgeMap BoolEdgeMap; alpar@209: checkConcept, alpar@209: BoolEdgeMap >(); alpar@209: } { // Dummy map test alpar@209: typedef typename _Graph::template EdgeMap DummyEdgeMap; alpar@209: checkConcept, alpar@209: DummyEdgeMap >(); alpar@209: } alpar@209: } deba@57: kpeter@579: const _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: deba@1018: /// \brief Skeleton class for mappable undirected bipartite graphs. deba@1018: /// deba@1018: /// This class describes the interface of mappable undirected deba@1018: /// bipartite graphs. It extends \ref MappableGraphComponent with deba@1018: /// the standard graph map class for red and blue nodes (\c deba@1026: /// RedNodeMap and BlueNodeMap). This concept is part of the deba@1026: /// BpGraph concept. deba@1018: template deba@1018: class MappableBpGraphComponent : public MappableGraphComponent { deba@1018: public: deba@1018: deba@1018: typedef BAS Base; deba@1018: typedef typename Base::Node Node; deba@1018: deba@1018: typedef MappableBpGraphComponent BpGraph; deba@1018: deba@1018: /// \brief Standard graph map for the red nodes. deba@1018: /// deba@1018: /// Standard graph map for the red nodes. deba@1018: /// It conforms to the ReferenceMap concept. deba@1018: template deba@1026: class RedNodeMap : public GraphMap { deba@1018: typedef GraphMap Parent; deba@1018: deba@1018: public: deba@1018: /// \brief Construct a new map. deba@1018: /// deba@1018: /// Construct a new map for the graph. deba@1026: explicit RedNodeMap(const MappableBpGraphComponent& graph) deba@1018: : Parent(graph) {} deba@1018: deba@1018: /// \brief Construct a new map with default value. deba@1018: /// deba@1018: /// Construct a new map for the graph and initalize the values. deba@1026: RedNodeMap(const MappableBpGraphComponent& graph, const V& value) deba@1018: : Parent(graph, value) {} deba@1018: deba@1018: private: deba@1018: /// \brief Copy constructor. deba@1018: /// deba@1018: /// Copy Constructor. deba@1026: RedNodeMap(const RedNodeMap& nm) : Parent(nm) {} deba@1018: deba@1018: /// \brief Assignment operator. deba@1018: /// deba@1018: /// Assignment operator. deba@1018: template deba@1026: RedNodeMap& operator=(const CMap&) { deba@1018: checkConcept, CMap>(); deba@1018: return *this; deba@1018: } deba@1018: deba@1018: }; deba@1018: deba@1018: /// \brief Standard graph map for the blue nodes. deba@1018: /// deba@1018: /// Standard graph map for the blue nodes. deba@1018: /// It conforms to the ReferenceMap concept. deba@1018: template deba@1026: class BlueNodeMap : public GraphMap { deba@1018: typedef GraphMap Parent; deba@1018: deba@1018: public: deba@1018: /// \brief Construct a new map. deba@1018: /// deba@1018: /// Construct a new map for the graph. deba@1026: explicit BlueNodeMap(const MappableBpGraphComponent& graph) deba@1018: : Parent(graph) {} deba@1018: deba@1018: /// \brief Construct a new map with default value. deba@1018: /// deba@1018: /// Construct a new map for the graph and initalize the values. deba@1026: BlueNodeMap(const MappableBpGraphComponent& graph, const V& value) deba@1018: : Parent(graph, value) {} deba@1018: deba@1018: private: deba@1018: /// \brief Copy constructor. deba@1018: /// deba@1018: /// Copy Constructor. deba@1026: BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {} deba@1018: deba@1018: /// \brief Assignment operator. deba@1018: /// deba@1018: /// Assignment operator. deba@1018: template deba@1026: BlueNodeMap& operator=(const CMap&) { deba@1018: checkConcept, CMap>(); deba@1018: return *this; deba@1018: } deba@1018: deba@1018: }; deba@1018: deba@1018: deba@1018: template deba@1018: struct Constraints { deba@1018: deba@1018: struct Dummy { deba@1018: int value; deba@1018: Dummy() : value(0) {} deba@1018: Dummy(int _v) : value(_v) {} deba@1018: }; deba@1018: deba@1018: void constraints() { deba@1018: checkConcept, _BpGraph>(); deba@1018: deba@1018: { // int map test deba@1026: typedef typename _BpGraph::template RedNodeMap deba@1026: IntRedNodeMap; deba@1025: checkConcept, deba@1026: IntRedNodeMap >(); deba@1018: } { // bool map test deba@1026: typedef typename _BpGraph::template RedNodeMap deba@1026: BoolRedNodeMap; deba@1025: checkConcept, deba@1026: BoolRedNodeMap >(); deba@1018: } { // Dummy map test deba@1026: typedef typename _BpGraph::template RedNodeMap deba@1026: DummyRedNodeMap; deba@1025: checkConcept, deba@1026: DummyRedNodeMap >(); deba@1018: } deba@1018: deba@1018: { // int map test deba@1026: typedef typename _BpGraph::template BlueNodeMap deba@1026: IntBlueNodeMap; deba@1025: checkConcept, deba@1026: IntBlueNodeMap >(); deba@1018: } { // bool map test deba@1026: typedef typename _BpGraph::template BlueNodeMap deba@1026: BoolBlueNodeMap; deba@1025: checkConcept, deba@1026: BoolBlueNodeMap >(); deba@1018: } { // Dummy map test deba@1026: typedef typename _BpGraph::template BlueNodeMap deba@1026: DummyBlueNodeMap; deba@1025: checkConcept, deba@1026: DummyBlueNodeMap >(); deba@1018: } deba@1018: } deba@1018: deba@1018: const _BpGraph& bpgraph; deba@1018: }; deba@1018: }; deba@1018: kpeter@579: /// \brief Skeleton class for extendable directed graphs. deba@57: /// kpeter@579: /// This class describes the interface of extendable directed graphs. alpar@877: /// It extends \ref BaseDigraphComponent with functions for adding kpeter@579: /// nodes and arcs to the digraph. kpeter@579: /// This concept requires \ref AlterableDigraphComponent. kpeter@559: template kpeter@559: class ExtendableDigraphComponent : public BAS { deba@57: public: kpeter@559: typedef BAS Base; deba@57: kpeter@559: typedef typename Base::Node Node; kpeter@559: typedef typename Base::Arc Arc; deba@57: kpeter@579: /// \brief Add a new node to the digraph. deba@57: /// kpeter@579: /// This function adds a new node to the digraph. deba@57: Node addNode() { alpar@209: return INVALID; deba@57: } alpar@209: kpeter@579: /// \brief Add a new arc connecting the given two nodes. deba@57: /// kpeter@579: /// This function adds a new arc connecting the given two nodes kpeter@579: /// of the digraph. deba@57: Arc addArc(const Node&, const Node&) { alpar@209: return INVALID; deba@57: } deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept(); alpar@209: typename _Digraph::Node node_a, node_b; alpar@209: node_a = digraph.addNode(); alpar@209: node_b = digraph.addNode(); alpar@209: typename _Digraph::Arc arc; alpar@209: arc = digraph.addArc(node_a, node_b); alpar@209: } deba@57: alpar@209: _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for extendable undirected graphs. deba@57: /// kpeter@579: /// This class describes the interface of extendable undirected graphs. alpar@877: /// It extends \ref BaseGraphComponent with functions for adding kpeter@579: /// nodes and edges to the graph. kpeter@579: /// This concept requires \ref AlterableGraphComponent. kpeter@559: template kpeter@559: class ExtendableGraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; kpeter@559: typedef typename Base::Node Node; kpeter@559: typedef typename Base::Edge Edge; deba@57: kpeter@579: /// \brief Add a new node to the digraph. deba@57: /// kpeter@579: /// This function adds a new node to the digraph. deba@57: Node addNode() { alpar@209: return INVALID; deba@57: } alpar@209: kpeter@579: /// \brief Add a new edge connecting the given two nodes. deba@57: /// kpeter@579: /// This function adds a new edge connecting the given two nodes kpeter@579: /// of the graph. kpeter@579: Edge addEdge(const Node&, const Node&) { alpar@209: return INVALID; deba@57: } deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { alpar@209: checkConcept(); alpar@209: typename _Graph::Node node_a, node_b; alpar@209: node_a = graph.addNode(); alpar@209: node_b = graph.addNode(); alpar@209: typename _Graph::Edge edge; alpar@209: edge = graph.addEdge(node_a, node_b); alpar@209: } deba@57: alpar@209: _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: deba@1018: /// \brief Skeleton class for extendable undirected bipartite graphs. deba@1018: /// deba@1018: /// This class describes the interface of extendable undirected deba@1018: /// bipartite graphs. It extends \ref BaseGraphComponent with deba@1018: /// functions for adding nodes and edges to the graph. This deba@1018: /// concept requires \ref AlterableBpGraphComponent. deba@1018: template deba@1018: class ExtendableBpGraphComponent : public BAS { deba@1018: public: deba@1018: deba@1018: typedef BAS Base; deba@1018: typedef typename Base::Node Node; deba@1025: typedef typename Base::RedNode RedNode; deba@1025: typedef typename Base::BlueNode BlueNode; deba@1018: typedef typename Base::Edge Edge; deba@1018: deba@1018: /// \brief Add a new red node to the digraph. deba@1018: /// deba@1018: /// This function adds a red new node to the digraph. deba@1025: RedNode addRedNode() { deba@1018: return INVALID; deba@1018: } deba@1018: deba@1018: /// \brief Add a new blue node to the digraph. deba@1018: /// deba@1018: /// This function adds a blue new node to the digraph. deba@1025: BlueNode addBlueNode() { deba@1018: return INVALID; deba@1018: } deba@1018: deba@1018: /// \brief Add a new edge connecting the given two nodes. deba@1018: /// deba@1018: /// This function adds a new edge connecting the given two nodes deba@1018: /// of the graph. The first node has to be a red node, and the deba@1018: /// second one a blue node. deba@1025: Edge addEdge(const RedNode&, const BlueNode&) { deba@1025: return INVALID; deba@1025: } deba@1025: Edge addEdge(const BlueNode&, const RedNode&) { deba@1018: return INVALID; deba@1018: } deba@1018: deba@1018: template deba@1018: struct Constraints { deba@1018: void constraints() { deba@1018: checkConcept(); deba@1025: typename _BpGraph::RedNode red_node; deba@1025: typename _BpGraph::BlueNode blue_node; deba@1018: red_node = bpgraph.addRedNode(); deba@1018: blue_node = bpgraph.addBlueNode(); deba@1018: typename _BpGraph::Edge edge; deba@1018: edge = bpgraph.addEdge(red_node, blue_node); deba@1025: edge = bpgraph.addEdge(blue_node, red_node); deba@1018: } deba@1018: deba@1018: _BpGraph& bpgraph; deba@1018: }; deba@1018: }; deba@1018: kpeter@579: /// \brief Skeleton class for erasable directed graphs. alpar@209: /// kpeter@579: /// This class describes the interface of erasable directed graphs. alpar@877: /// It extends \ref BaseDigraphComponent with functions for removing kpeter@579: /// nodes and arcs from the digraph. kpeter@579: /// This concept requires \ref AlterableDigraphComponent. kpeter@559: template kpeter@559: class ErasableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: deba@57: /// \brief Erase a node from the digraph. deba@57: /// alpar@877: /// This function erases the given node from the digraph and all arcs kpeter@579: /// connected to the node. alpar@209: void erase(const Node&) {} deba@57: deba@57: /// \brief Erase an arc from the digraph. deba@57: /// kpeter@579: /// This function erases the given arc from the digraph. deba@57: void erase(const Arc&) {} deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept(); kpeter@579: const typename _Digraph::Node node(INVALID); alpar@209: digraph.erase(node); kpeter@579: const typename _Digraph::Arc arc(INVALID); alpar@209: digraph.erase(arc); alpar@209: } deba@57: alpar@209: _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for erasable undirected graphs. alpar@209: /// kpeter@579: /// This class describes the interface of erasable undirected graphs. alpar@877: /// It extends \ref BaseGraphComponent with functions for removing kpeter@579: /// nodes and edges from the graph. kpeter@579: /// This concept requires \ref AlterableGraphComponent. kpeter@559: template kpeter@559: class ErasableGraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Edge Edge; deba@57: deba@57: /// \brief Erase a node from the graph. deba@57: /// kpeter@579: /// This function erases the given node from the graph and all edges kpeter@579: /// connected to the node. alpar@209: void erase(const Node&) {} deba@57: kpeter@579: /// \brief Erase an edge from the digraph. deba@57: /// kpeter@579: /// This function erases the given edge from the digraph. deba@57: void erase(const Edge&) {} deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept(); kpeter@579: const typename _Graph::Node node(INVALID); alpar@209: graph.erase(node); kpeter@579: const typename _Graph::Edge edge(INVALID); alpar@209: graph.erase(edge); alpar@209: } deba@57: alpar@209: _Graph& graph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: deba@1018: /// \brief Skeleton class for erasable undirected graphs. deba@1018: /// deba@1018: /// This class describes the interface of erasable undirected deba@1018: /// bipartite graphs. It extends \ref BaseBpGraphComponent with deba@1018: /// functions for removing nodes and edges from the graph. This deba@1018: /// concept requires \ref AlterableBpGraphComponent. deba@1018: template deba@1018: class ErasableBpGraphComponent : public ErasableGraphComponent {}; deba@1018: kpeter@579: /// \brief Skeleton class for clearable directed graphs. deba@57: /// kpeter@579: /// This class describes the interface of clearable directed graphs. kpeter@579: /// It extends \ref BaseDigraphComponent with a function for clearing kpeter@579: /// the digraph. kpeter@579: /// This concept requires \ref AlterableDigraphComponent. kpeter@559: template kpeter@559: class ClearableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: deba@57: /// \brief Erase all nodes and arcs from the digraph. deba@57: /// kpeter@579: /// This function erases all nodes and arcs from the digraph. alpar@209: void clear() {} deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept(); alpar@209: digraph.clear(); alpar@209: } deba@57: kpeter@579: _Digraph& digraph; alpar@975: Constraints() {} deba@57: }; deba@57: }; deba@57: kpeter@579: /// \brief Skeleton class for clearable undirected graphs. deba@57: /// kpeter@579: /// This class describes the interface of clearable undirected graphs. kpeter@579: /// It extends \ref BaseGraphComponent with a function for clearing kpeter@579: /// the graph. kpeter@579: /// This concept requires \ref AlterableGraphComponent. kpeter@559: template deba@1018: class ClearableGraphComponent : public ClearableDigraphComponent {}; deba@57: deba@1018: /// \brief Skeleton class for clearable undirected biparite graphs. deba@1018: /// deba@1018: /// This class describes the interface of clearable undirected deba@1018: /// bipartite graphs. It extends \ref BaseBpGraphComponent with a deba@1018: /// function for clearing the graph. This concept requires \ref deba@1018: /// AlterableBpGraphComponent. deba@1018: template deba@1018: class ClearableBpGraphComponent : public ClearableGraphComponent {}; deba@57: deba@57: } deba@57: deba@57: } deba@57: deba@57: #endif