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@440: * Copyright (C) 2003-2009 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 deba@57: ///\brief The concept of graph components. deba@57: deba@514: #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H deba@514: #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@571: /// \brief Concept class for \c Node, \c Arc and \c Edge types. deba@57: /// kpeter@571: /// This class describes the concept of \c Node, \c Arc and \c Edge kpeter@571: /// 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@571: /// create graph skeleton classes. The reason for this is that \c Node kpeter@571: /// and \c Arc (or \c Edge) types should \e not derive from the same kpeter@571: /// base class. For \c Node you should instantiate it with character kpeter@571: /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. deba@57: #ifndef DOXYGEN kpeter@550: template deba@57: #endif deba@57: class GraphItem { deba@57: public: deba@57: /// \brief Default constructor. alpar@209: /// kpeter@571: /// 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@571: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@571: GraphItem(const GraphItem &) {} kpeter@571: kpeter@571: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@571: /// Constructor for conversion from \c INVALID. kpeter@571: /// It initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphItem(Invalid) {} kpeter@571: kpeter@571: /// \brief Assignment operator. deba@57: /// kpeter@571: /// Assignment operator for the item. kpeter@571: GraphItem& operator=(const GraphItem&) { return *this; } kpeter@571: deba@57: /// \brief Equality operator. deba@57: /// kpeter@571: /// Equality operator. kpeter@571: bool operator==(const GraphItem&) const { return false; } kpeter@571: deba@57: /// \brief Inequality operator. deba@57: /// kpeter@571: /// Inequality operator. kpeter@571: bool operator!=(const GraphItem&) const { return false; } kpeter@571: kpeter@571: /// \brief Ordering operator. deba@57: /// kpeter@571: /// This operator defines an ordering of the items. kpeter@571: /// It makes possible to use graph item types as key types in kpeter@571: /// associative containers (e.g. \c std::map). deba@57: /// deba@57: /// \note This operator only have 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@571: 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@209: _GraphItem i2 = i1; alpar@209: _GraphItem i3 = INVALID; deba@57: alpar@209: i1 = i2 = i3; alpar@209: alpar@209: bool b; 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; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Base skeleton class for directed graphs. alpar@209: /// kpeter@571: /// This class describes the base interface of directed graph types. kpeter@571: /// All digraph %concepts have to conform to this class. kpeter@571: /// It just provides types for nodes and arcs and functions kpeter@571: /// 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@571: /// 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@571: /// This class represents the arcs of the digraph. kpeter@571: typedef GraphItem<'a'> Arc; kpeter@571: kpeter@571: /// \brief Return the source node of an arc. deba@57: /// kpeter@571: /// This function returns the source node of an arc. kpeter@571: Node source(const Arc&) const { return INVALID; } deba@57: kpeter@571: /// \brief Return the target node of an arc. deba@57: /// kpeter@571: /// This function returns the target node of an arc. kpeter@571: Node target(const Arc&) const { return INVALID; } kpeter@571: kpeter@571: /// \brief Return the opposite node on the given arc. deba@57: /// kpeter@571: /// 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; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Base skeleton class for undirected graphs. alpar@209: /// kpeter@571: /// This class describes the base interface of undirected graph types. kpeter@571: /// All graph %concepts have to conform to this class. kpeter@571: /// It extends the interface of \ref BaseDigraphComponent with an kpeter@571: /// \c Edge type and functions to get the end nodes of edges, kpeter@571: /// to convert from arcs to edges and to get both direction of edges. deba@57: class BaseGraphComponent : public BaseDigraphComponent { deba@57: public: kpeter@609: kpeter@609: typedef BaseGraphComponent Graph; kpeter@609: deba@57: typedef BaseDigraphComponent::Node Node; deba@57: typedef BaseDigraphComponent::Arc Arc; kpeter@571: kpeter@571: /// \brief Undirected edge class of the graph. deba@57: /// kpeter@571: /// This class represents the undirected edges of the graph. kpeter@571: /// Undirected graphs can be used as directed graphs, each edge is kpeter@571: /// represented by two opposite directed arcs. kpeter@571: class Edge : public GraphItem<'e'> { kpeter@571: typedef GraphItem<'e'> Parent; kpeter@571: kpeter@609: public: deba@57: /// \brief Default constructor. alpar@209: /// kpeter@571: /// 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@571: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@571: Edge(const Edge &) : Parent() {} kpeter@571: kpeter@571: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@571: /// Constructor for conversion from \c INVALID. kpeter@571: /// It initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: Edge(Invalid) {} kpeter@571: kpeter@571: /// \brief Constructor for conversion from an arc. deba@57: /// kpeter@571: /// 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&) {} kpeter@571: kpeter@571: /// \brief Assign an arc to an edge. deba@57: /// kpeter@571: /// This function assigns an arc to an edge. deba@57: /// Besides the core graph item functionality each arc should alpar@209: /// be convertible to the represented edge. deba@57: Edge& operator=(const Arc&) { return *this; } deba@57: }; deba@57: kpeter@571: /// \brief Return one end node of an edge. kpeter@571: /// kpeter@571: /// This function returns one end node of an edge. kpeter@571: Node u(const Edge&) const { return INVALID; } kpeter@571: kpeter@571: /// \brief Return the other end node of an edge. kpeter@571: /// kpeter@571: /// This function returns the other end node of an edge. kpeter@571: Node v(const Edge&) const { return INVALID; } kpeter@571: kpeter@571: /// \brief Return a directed arc related to an edge. kpeter@571: /// kpeter@571: /// This function returns a directed arc from its direction and the kpeter@571: /// represented edge. kpeter@571: Arc direct(const Edge&, bool) const { return INVALID; } kpeter@571: kpeter@571: /// \brief Return a directed arc related to an edge. kpeter@571: /// kpeter@571: /// This function returns a directed arc from its source node and the kpeter@571: /// represented edge. kpeter@571: Arc direct(const Edge&, const Node&) const { return INVALID; } kpeter@571: kpeter@571: /// \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@571: /// \brief Return the opposite arc. deba@57: /// kpeter@571: /// This function returns the opposite arc, i.e. the arc representing kpeter@571: /// the same edge and has opposite direction. kpeter@571: 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@571: 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@571: 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); deba@57: ignore_unused_variable_warning(d); alpar@209: } alpar@209: } alpar@209: alpar@209: const _Graph& graph; deba@57: }; deba@57: deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for \e idable directed graphs. alpar@209: /// kpeter@571: /// This class describes the interface of \e idable directed graphs. kpeter@571: /// It extends \ref BaseDigraphComponent with the core ID functions. kpeter@571: /// The ids of the items must be unique and immutable. kpeter@571: /// This concept is part of the Digraph concept. kpeter@550: template kpeter@550: class IDableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: kpeter@571: /// \brief Return a unique integer id for the given node. deba@57: /// kpeter@571: /// This function returns a unique integer id for the given node. kpeter@571: int id(const Node&) const { return -1; } kpeter@571: kpeter@571: /// \brief Return the node by its unique id. deba@57: /// kpeter@571: /// This function returns the node by its unique id. kpeter@571: /// If the digraph does not contain a node with the given id, kpeter@571: /// then the result of the function is undefined. kpeter@571: Node nodeFromId(int) const { return INVALID; } deba@57: kpeter@571: /// \brief Return a unique integer id for the given arc. deba@57: /// kpeter@571: /// This function returns a unique integer id for the given arc. kpeter@571: int id(const Arc&) const { return -1; } deba@57: kpeter@571: /// \brief Return the arc by its unique id. deba@57: /// kpeter@571: /// This function returns the arc by its unique id. kpeter@571: /// If the digraph does not contain an arc with the given id, kpeter@571: /// then the result of the function is undefined. kpeter@571: Arc arcFromId(int) const { return INVALID; } kpeter@571: kpeter@571: /// \brief Return an integer greater or equal to the maximum kpeter@571: /// node id. deba@57: /// kpeter@571: /// This function returns an integer greater or equal to the kpeter@571: /// maximum node id. kpeter@571: int maxNodeId() const { return -1; } deba@57: kpeter@571: /// \brief Return an integer greater or equal to the maximum kpeter@571: /// arc id. deba@57: /// kpeter@571: /// This function returns an integer greater or equal to the kpeter@571: /// maximum arc id. kpeter@571: 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@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@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@209: ignore_unused_variable_warning(nid); alpar@209: eid = digraph.maxArcId(); alpar@209: ignore_unused_variable_warning(eid); alpar@209: } deba@57: alpar@209: const _Digraph& digraph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for \e idable undirected graphs. alpar@209: /// kpeter@571: /// This class describes the interface of \e idable undirected kpeter@571: /// graphs. It extends \ref IDableDigraphComponent with the core ID kpeter@571: /// functions of undirected graphs. kpeter@571: /// The ids of the items must be unique and immutable. kpeter@571: /// This concept is part of the Graph concept. kpeter@550: template kpeter@550: class IDableGraphComponent : public IDableDigraphComponent { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: typedef typename Base::Edge Edge; deba@57: kpeter@550: using IDableDigraphComponent::id; deba@57: kpeter@571: /// \brief Return a unique integer id for the given edge. deba@57: /// kpeter@571: /// This function returns a unique integer id for the given edge. kpeter@571: int id(const Edge&) const { return -1; } kpeter@571: kpeter@571: /// \brief Return the edge by its unique id. deba@57: /// kpeter@571: /// This function returns the edge by its unique id. kpeter@571: /// If the graph does not contain an edge with the given id, kpeter@571: /// then the result of the function is undefined. kpeter@571: Edge edgeFromId(int) const { return INVALID; } deba@57: kpeter@571: /// \brief Return an integer greater or equal to the maximum kpeter@571: /// edge id. deba@57: /// kpeter@571: /// This function returns an integer greater or equal to the kpeter@571: /// maximum edge id. kpeter@571: 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@209: ignore_unused_variable_warning(ueid); alpar@209: } deba@57: alpar@209: const _Graph& graph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. deba@57: /// kpeter@571: /// This class describes the concept of \c NodeIt, \c ArcIt and kpeter@571: /// \c EdgeIt subtypes of digraph and graph types. kpeter@550: template kpeter@550: class GraphItemIt : public Item { deba@57: public: deba@57: /// \brief Default constructor. deba@57: /// kpeter@571: /// Default constructor. kpeter@571: /// \warning The default constructor is not required to set kpeter@571: /// the iterator to some well-defined value. So you should consider it kpeter@571: /// as uninitialized. deba@57: GraphItemIt() {} kpeter@571: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@571: GraphItemIt(const GraphItemIt& it) : Item(it) {} kpeter@571: kpeter@571: /// \brief Constructor that sets the iterator to the first item. deba@57: /// kpeter@571: /// Constructor that sets the iterator to the first item. kpeter@571: explicit GraphItemIt(const GR&) {} kpeter@571: kpeter@571: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@571: /// Constructor for conversion from \c INVALID. kpeter@571: /// It initializes the iterator to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphItemIt(Invalid) {} kpeter@571: kpeter@571: /// \brief Assignment operator. deba@57: /// kpeter@571: /// Assignment operator for the iterator. kpeter@571: GraphItemIt& operator=(const GraphItemIt&) { return *this; } kpeter@571: kpeter@571: /// \brief Increment the iterator. deba@57: /// kpeter@571: /// This operator increments the iterator, i.e. assigns it to the kpeter@571: /// next item. deba@57: GraphItemIt& operator++() { return *this; } kpeter@571: deba@57: /// \brief Equality operator alpar@209: /// kpeter@571: /// 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@571: deba@57: /// \brief Inequality operator alpar@209: /// kpeter@571: /// Inequality operator. kpeter@571: /// Two iterators are equal if and only if they point to the kpeter@571: /// 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@571: checkConcept, _GraphItemIt>(); alpar@209: _GraphItemIt it1(g); alpar@209: _GraphItemIt it2; kpeter@571: _GraphItemIt it3 = it1; kpeter@571: _GraphItemIt it4 = INVALID; deba@57: alpar@209: it2 = ++it1; alpar@209: ++it2 = it1; alpar@209: ++(++it1); deba@57: kpeter@550: Item bi = it1; alpar@209: bi = it2; alpar@209: } kpeter@571: const GR& g; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Concept class for \c InArcIt, \c OutArcIt and kpeter@571: /// \c IncEdgeIt types. deba@57: /// kpeter@571: /// This class describes the concept of \c InArcIt, \c OutArcIt kpeter@571: /// and \c IncEdgeIt subtypes of digraph and graph types. kpeter@571: /// kpeter@571: /// \note Since these iterator classes do not inherit from the same kpeter@571: /// base class, there is an additional template parameter (selector) kpeter@571: /// \c sel. For \c InArcIt you should instantiate it with character kpeter@571: /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. kpeter@550: template kpeter@550: class GraphIncIt : public Item { deba@57: public: deba@57: /// \brief Default constructor. deba@57: /// kpeter@571: /// Default constructor. kpeter@571: /// \warning The default constructor is not required to set kpeter@571: /// the iterator to some well-defined value. So you should consider it kpeter@571: /// as uninitialized. deba@57: GraphIncIt() {} kpeter@571: deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. kpeter@571: GraphIncIt(const GraphIncIt& it) : Item(it) {} kpeter@571: kpeter@571: /// \brief Constructor that sets the iterator to the first kpeter@571: /// incoming or outgoing arc. deba@57: /// kpeter@571: /// Constructor that sets the iterator to the first arc kpeter@571: /// incoming to or outgoing from the given node. kpeter@571: explicit GraphIncIt(const GR&, const Base&) {} kpeter@571: kpeter@571: /// \brief Constructor for conversion from \c INVALID. deba@57: /// kpeter@571: /// Constructor for conversion from \c INVALID. kpeter@571: /// It initializes the iterator to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphIncIt(Invalid) {} kpeter@571: kpeter@571: /// \brief Assignment operator. deba@57: /// kpeter@571: /// Assignment operator for the iterator. kpeter@571: GraphIncIt& operator=(const GraphIncIt&) { return *this; } kpeter@571: kpeter@571: /// \brief Increment the iterator. deba@57: /// kpeter@571: /// This operator increments the iterator, i.e. assigns it to the kpeter@571: /// 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@571: /// 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@571: /// Inequality operator. kpeter@571: /// Two iterators are equal if and only if they point to the kpeter@571: /// 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@550: checkConcept, _GraphIncIt>(); alpar@209: _GraphIncIt it1(graph, node); alpar@209: _GraphIncIt it2; kpeter@571: _GraphIncIt it3 = it1; kpeter@571: _GraphIncIt it4 = INVALID; deba@57: alpar@209: it2 = ++it1; alpar@209: ++it2 = it1; alpar@209: ++(++it1); kpeter@550: Item e = it1; alpar@209: e = it2; alpar@209: } kpeter@571: const Base& node; kpeter@571: const GR& graph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for iterable directed graphs. deba@57: /// kpeter@571: /// This class describes the interface of iterable directed kpeter@571: /// graphs. It extends \ref BaseDigraphComponent with the core kpeter@571: /// iterable interface. deba@57: /// This concept is part of the Digraph concept. kpeter@550: template kpeter@550: class IterableDigraphComponent : public BAS { deba@57: deba@57: public: alpar@209: kpeter@550: 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@576: /// \name Base Iteration alpar@209: /// kpeter@571: /// This interface provides functions for iteration on digraph items. deba@57: /// alpar@209: /// @{ deba@57: kpeter@571: /// \brief Return the first node. alpar@209: /// kpeter@571: /// This function gives back the first node in the iteration order. deba@57: void first(Node&) const {} deba@57: kpeter@571: /// \brief Return the next node. deba@57: /// kpeter@571: /// This function gives back the next node in the iteration order. deba@57: void next(Node&) const {} deba@57: kpeter@571: /// \brief Return the first arc. deba@57: /// kpeter@571: /// This function gives back the first arc in the iteration order. deba@57: void first(Arc&) const {} deba@57: kpeter@571: /// \brief Return the next arc. deba@57: /// kpeter@571: /// This function gives back the next arc in the iteration order. deba@57: void next(Arc&) const {} deba@57: kpeter@571: /// \brief Return the first arc incomming to the given node. deba@57: /// kpeter@571: /// This function gives back the first arc incomming to the kpeter@571: /// given node. deba@57: void firstIn(Arc&, const Node&) const {} deba@57: kpeter@571: /// \brief Return the next arc incomming to the given node. deba@57: /// kpeter@571: /// This function gives back the next arc incomming to the kpeter@571: /// given node. deba@57: void nextIn(Arc&) const {} deba@57: kpeter@571: /// \brief Return the first arc outgoing form the given node. kpeter@571: /// kpeter@571: /// 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@571: /// \brief Return the next arc outgoing form the given node. deba@57: /// kpeter@571: /// This function gives back the next arc outgoing form the kpeter@571: /// given node. deba@57: void nextOut(Arc&) const {} deba@57: deba@57: /// @} deba@57: kpeter@576: /// \name Class Based Iteration alpar@209: /// kpeter@571: /// 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@571: /// \brief This iterator goes through each arc. deba@57: /// kpeter@571: /// 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@571: /// 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@571: /// This function gives back the base node of the iterator. kpeter@571: /// 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@571: /// This function gives back the running node of the iterator. kpeter@571: /// 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@571: /// This function gives back the base node of the iterator. kpeter@571: /// 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@571: /// This function gives back the running node of the iterator. kpeter@571: /// 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@571: const typename _Digraph::InArcIt iait(INVALID); kpeter@571: const typename _Digraph::OutArcIt oait(INVALID); kpeter@571: n = digraph.baseNode(iait); kpeter@571: n = digraph.runningNode(iait); kpeter@571: n = digraph.baseNode(oait); kpeter@571: n = digraph.runningNode(oait); deba@57: ignore_unused_variable_warning(n); deba@57: } deba@57: } alpar@209: alpar@209: const _Digraph& digraph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for iterable undirected graphs. deba@57: /// kpeter@571: /// This class describes the interface of iterable undirected kpeter@571: /// graphs. It extends \ref IterableDigraphComponent with the core kpeter@571: /// iterable interface of undirected graphs. deba@57: /// This concept is part of the Graph concept. kpeter@550: template kpeter@550: class IterableGraphComponent : public IterableDigraphComponent { deba@57: public: deba@57: kpeter@550: 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@576: /// \name Base Iteration alpar@209: /// kpeter@571: /// This interface provides functions for iteration on edges. kpeter@571: /// alpar@209: /// @{ deba@57: kpeter@550: using IterableDigraphComponent::first; kpeter@550: using IterableDigraphComponent::next; deba@57: kpeter@571: /// \brief Return the first edge. deba@57: /// kpeter@571: /// This function gives back the first edge in the iteration order. deba@57: void first(Edge&) const {} deba@57: kpeter@571: /// \brief Return the next edge. deba@57: /// kpeter@571: /// This function gives back the next edge in the iteration order. deba@57: void next(Edge&) const {} deba@57: kpeter@571: /// \brief Return the first edge incident to the given node. kpeter@571: /// kpeter@571: /// This function gives back the first edge incident to the given kpeter@571: /// node. The bool parameter gives back the direction for which the kpeter@571: /// 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: /// kpeter@571: /// This function gives back the next edge incident to the given kpeter@571: /// node. The bool parameter should be used as \c firstInc() use it. deba@57: void nextInc(Edge&, bool&) const {} deba@57: kpeter@550: using IterableDigraphComponent::baseNode; kpeter@550: using IterableDigraphComponent::runningNode; deba@57: deba@57: /// @} deba@57: kpeter@576: /// \name Class Based Iteration alpar@209: /// kpeter@571: /// This interface provides iterator classes for edges. deba@57: /// deba@57: /// @{ deba@57: kpeter@571: /// \brief This iterator goes through each edge. deba@57: /// kpeter@571: /// This iterator goes through each edge. deba@57: typedef GraphItemIt EdgeIt; kpeter@571: kpeter@571: /// \brief This iterator goes trough the incident edges of a deba@57: /// node. deba@57: /// kpeter@571: /// This iterator goes trough the incident edges of a certain deba@57: /// node of a graph. kpeter@571: typedef GraphIncIt IncEdgeIt; kpeter@571: deba@57: /// \brief The base node of the iterator. deba@57: /// kpeter@571: /// 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@571: /// 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@571: const typename _Graph::IncEdgeIt ieit(INVALID); kpeter@571: n = graph.baseNode(ieit); kpeter@571: n = graph.runningNode(ieit); deba@57: } deba@57: } alpar@209: alpar@209: const _Graph& graph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for alterable directed graphs. alpar@209: /// kpeter@571: /// This class describes the interface of alterable directed kpeter@571: /// graphs. It extends \ref BaseDigraphComponent with the alteration kpeter@571: /// 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@571: /// alteration occured in the digraph all the observers will be deba@57: /// notified about it. kpeter@550: template kpeter@550: class AlterableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: typedef typename Base::Node Node; deba@57: typedef typename Base::Arc Arc; deba@57: deba@57: kpeter@571: /// Node alteration notifier class. alpar@209: typedef AlterationNotifier deba@57: NodeNotifier; kpeter@571: /// Arc alteration notifier class. alpar@209: typedef AlterationNotifier deba@57: ArcNotifier; alpar@209: kpeter@571: /// \brief Return the node alteration notifier. deba@57: /// kpeter@571: /// This function gives back the node alteration notifier. deba@57: NodeNotifier& notifier(Node) const { kpeter@571: return NodeNotifier(); deba@57: } alpar@209: kpeter@571: /// \brief Return the arc alteration notifier. deba@57: /// kpeter@571: /// This function gives back the arc alteration notifier. deba@57: ArcNotifier& notifier(Arc) const { alpar@209: return ArcNotifier(); 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: deba@57: ignore_unused_variable_warning(nn); deba@57: ignore_unused_variable_warning(en); alpar@209: } alpar@209: alpar@209: const _Digraph& digraph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for alterable undirected graphs. alpar@209: /// kpeter@571: /// This class describes the interface of alterable undirected kpeter@571: /// graphs. It extends \ref AlterableDigraphComponent with the alteration kpeter@571: /// notifier interface of undirected graphs. It implements kpeter@571: /// an observer-notifier pattern for the edges. More deba@57: /// obsevers can be registered into the notifier and whenever an kpeter@571: /// alteration occured in the graph all the observers will be deba@57: /// notified about it. kpeter@550: template kpeter@550: class AlterableGraphComponent : public AlterableDigraphComponent { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: typedef typename Base::Edge Edge; deba@57: deba@57: kpeter@571: /// Edge alteration notifier class. alpar@209: typedef AlterationNotifier deba@57: EdgeNotifier; alpar@209: kpeter@571: /// \brief Return the edge alteration notifier. deba@57: /// kpeter@571: /// This function gives back the edge alteration notifier. deba@57: EdgeNotifier& notifier(Edge) const { alpar@209: return EdgeNotifier(); deba@57: } deba@57: alpar@209: template deba@57: struct Constraints { alpar@209: void constraints() { kpeter@571: checkConcept, _Graph>(); alpar@209: typename _Graph::EdgeNotifier& uen deba@57: = graph.notifier(typename _Graph::Edge()); deba@57: ignore_unused_variable_warning(uen); alpar@209: } alpar@209: alpar@209: const _Graph& graph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Concept class for standard graph maps. alpar@209: /// kpeter@571: /// This class describes the concept of standard graph maps, i.e. kpeter@571: /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and kpeter@571: /// graph types, which can be used for associating data to graph items. kpeter@572: /// The standard graph maps must conform to the ReferenceMap concept. kpeter@550: template kpeter@572: class GraphMap : public ReferenceMap { kpeter@609: typedef ReferenceMap Parent; kpeter@609: deba@57: public: deba@57: deba@57: /// The key type of the map. kpeter@550: typedef K Key; deba@57: /// The value type of the map. kpeter@550: typedef V Value; kpeter@572: /// The reference type of the map. kpeter@572: typedef Value& Reference; kpeter@572: /// The const reference type of the map. kpeter@572: typedef const Value& ConstReference; kpeter@572: kpeter@572: // The reference map tag. kpeter@572: typedef True ReferenceMapTag; deba@57: deba@57: /// \brief Construct a new map. deba@57: /// deba@57: /// Construct a new map for the graph. kpeter@609: explicit GraphMap(const GR&) {} deba@57: /// \brief Construct a new map with default value. deba@57: /// kpeter@571: /// Construct a new map for the graph and initalize the values. kpeter@609: 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@571: /// \brief Assignment operator. deba@57: /// kpeter@571: /// 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@572: checkConcept kpeter@572: , _Map>(); kpeter@571: _Map m1(g); kpeter@571: _Map m2(g,t); kpeter@571: kpeter@571: // Copy constructor kpeter@571: // _Map m3(m); alpar@209: kpeter@571: // Assignment operator kpeter@263: // ReadMap cmap; kpeter@571: // m3 = cmap; deba@57: kpeter@571: ignore_unused_variable_warning(m1); kpeter@571: ignore_unused_variable_warning(m2); kpeter@571: // ignore_unused_variable_warning(m3); alpar@209: } deba@57: kpeter@571: const _Map &m; kpeter@609: const GR &g; alpar@209: const typename GraphMap::Value &t; deba@57: }; deba@57: deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for mappable directed graphs. deba@57: /// kpeter@571: /// This class describes the interface of mappable directed graphs. kpeter@571: /// It extends \ref BaseDigraphComponent with the standard digraph kpeter@571: /// map classes, namely \c NodeMap and \c ArcMap. deba@57: /// This concept is part of the Digraph concept. kpeter@550: template kpeter@550: class MappableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: 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@571: /// \brief Standard graph map for the nodes. deba@57: /// kpeter@571: /// Standard graph map for the nodes. kpeter@572: /// It conforms to the ReferenceMap concept. kpeter@550: template kpeter@571: class NodeMap : public GraphMap { kpeter@550: typedef GraphMap Parent; deba@57: kpeter@609: 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@571: /// Construct a new map for the digraph and initalize the values. kpeter@550: 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@571: /// \brief Assignment operator. alpar@209: /// kpeter@571: /// Assignment operator. deba@57: template alpar@209: NodeMap& operator=(const CMap&) { kpeter@550: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: deba@57: }; deba@57: kpeter@571: /// \brief Standard graph map for the arcs. deba@57: /// kpeter@571: /// Standard graph map for the arcs. kpeter@572: /// It conforms to the ReferenceMap concept. kpeter@550: template kpeter@571: class ArcMap : public GraphMap { kpeter@550: typedef GraphMap Parent; deba@57: kpeter@609: 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@571: /// Construct a new map for the digraph and initalize the values. kpeter@550: 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@571: /// \brief Assignment operator. alpar@209: /// kpeter@571: /// Assignment operator. deba@57: template alpar@209: ArcMap& operator=(const CMap&) { kpeter@550: 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@571: const _Digraph& digraph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for mappable undirected graphs. deba@57: /// kpeter@571: /// This class describes the interface of mappable undirected graphs. kpeter@571: /// It extends \ref MappableDigraphComponent with the standard graph kpeter@571: /// map class for edges (\c EdgeMap). deba@57: /// This concept is part of the Graph concept. kpeter@550: template kpeter@550: class MappableGraphComponent : public MappableDigraphComponent { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: typedef typename Base::Edge Edge; deba@57: deba@57: typedef MappableGraphComponent Graph; deba@57: kpeter@571: /// \brief Standard graph map for the edges. deba@57: /// kpeter@571: /// Standard graph map for the edges. kpeter@572: /// It conforms to the ReferenceMap concept. kpeter@550: template kpeter@571: class EdgeMap : public GraphMap { kpeter@550: typedef GraphMap Parent; deba@57: kpeter@609: 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@571: /// Construct a new map for the graph and initalize the values. kpeter@550: 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@571: /// \brief Assignment operator. alpar@209: /// kpeter@571: /// Assignment operator. deba@57: template alpar@209: EdgeMap& operator=(const CMap&) { kpeter@550: 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@571: 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@571: const _Graph& graph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for extendable directed graphs. deba@57: /// kpeter@571: /// This class describes the interface of extendable directed graphs. kpeter@571: /// It extends \ref BaseDigraphComponent with functions for adding kpeter@571: /// nodes and arcs to the digraph. kpeter@571: /// This concept requires \ref AlterableDigraphComponent. kpeter@550: template kpeter@550: class ExtendableDigraphComponent : public BAS { deba@57: public: kpeter@550: typedef BAS Base; deba@57: kpeter@550: typedef typename Base::Node Node; kpeter@550: typedef typename Base::Arc Arc; deba@57: kpeter@571: /// \brief Add a new node to the digraph. deba@57: /// kpeter@571: /// This function adds a new node to the digraph. deba@57: Node addNode() { alpar@209: return INVALID; deba@57: } alpar@209: kpeter@571: /// \brief Add a new arc connecting the given two nodes. deba@57: /// kpeter@571: /// This function adds a new arc connecting the given two nodes kpeter@571: /// 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; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for extendable undirected graphs. deba@57: /// kpeter@571: /// This class describes the interface of extendable undirected graphs. kpeter@571: /// It extends \ref BaseGraphComponent with functions for adding kpeter@571: /// nodes and edges to the graph. kpeter@571: /// This concept requires \ref AlterableGraphComponent. kpeter@550: template kpeter@550: class ExtendableGraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: typedef BAS Base; kpeter@550: typedef typename Base::Node Node; kpeter@550: typedef typename Base::Edge Edge; deba@57: kpeter@571: /// \brief Add a new node to the digraph. deba@57: /// kpeter@571: /// This function adds a new node to the digraph. deba@57: Node addNode() { alpar@209: return INVALID; deba@57: } alpar@209: kpeter@571: /// \brief Add a new edge connecting the given two nodes. deba@57: /// kpeter@571: /// This function adds a new edge connecting the given two nodes kpeter@571: /// of the graph. kpeter@571: 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; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for erasable directed graphs. alpar@209: /// kpeter@571: /// This class describes the interface of erasable directed graphs. kpeter@571: /// It extends \ref BaseDigraphComponent with functions for removing kpeter@571: /// nodes and arcs from the digraph. kpeter@571: /// This concept requires \ref AlterableDigraphComponent. kpeter@550: template kpeter@550: class ErasableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: 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: /// kpeter@571: /// This function erases the given node from the digraph and all arcs kpeter@571: /// connected to the node. alpar@209: void erase(const Node&) {} deba@57: deba@57: /// \brief Erase an arc from the digraph. deba@57: /// kpeter@571: /// 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@571: const typename _Digraph::Node node(INVALID); alpar@209: digraph.erase(node); kpeter@571: const typename _Digraph::Arc arc(INVALID); alpar@209: digraph.erase(arc); alpar@209: } deba@57: alpar@209: _Digraph& digraph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for erasable undirected graphs. alpar@209: /// kpeter@571: /// This class describes the interface of erasable undirected graphs. kpeter@571: /// It extends \ref BaseGraphComponent with functions for removing kpeter@571: /// nodes and edges from the graph. kpeter@571: /// This concept requires \ref AlterableGraphComponent. kpeter@550: template kpeter@550: class ErasableGraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: 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@571: /// This function erases the given node from the graph and all edges kpeter@571: /// connected to the node. alpar@209: void erase(const Node&) {} deba@57: kpeter@571: /// \brief Erase an edge from the digraph. deba@57: /// kpeter@571: /// 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@571: const typename _Graph::Node node(INVALID); alpar@209: graph.erase(node); kpeter@571: const typename _Graph::Edge edge(INVALID); alpar@209: graph.erase(edge); alpar@209: } deba@57: alpar@209: _Graph& graph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for clearable directed graphs. deba@57: /// kpeter@571: /// This class describes the interface of clearable directed graphs. kpeter@571: /// It extends \ref BaseDigraphComponent with a function for clearing kpeter@571: /// the digraph. kpeter@571: /// This concept requires \ref AlterableDigraphComponent. kpeter@550: template kpeter@550: class ClearableDigraphComponent : public BAS { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: deba@57: /// \brief Erase all nodes and arcs from the digraph. deba@57: /// kpeter@571: /// 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@571: _Digraph& digraph; deba@57: }; deba@57: }; deba@57: kpeter@571: /// \brief Skeleton class for clearable undirected graphs. deba@57: /// kpeter@571: /// This class describes the interface of clearable undirected graphs. kpeter@571: /// It extends \ref BaseGraphComponent with a function for clearing kpeter@571: /// the graph. kpeter@571: /// This concept requires \ref AlterableGraphComponent. kpeter@550: template kpeter@550: class ClearableGraphComponent : public ClearableDigraphComponent { deba@57: public: deba@57: kpeter@550: typedef BAS Base; deba@57: kpeter@571: /// \brief Erase all nodes and edges from the graph. kpeter@571: /// kpeter@571: /// This function erases all nodes and edges from the graph. kpeter@571: void clear() {} kpeter@571: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { kpeter@571: checkConcept(); kpeter@571: graph.clear(); alpar@209: } deba@57: kpeter@571: _Graph& graph; deba@57: }; deba@57: }; deba@57: deba@57: } deba@57: deba@57: } deba@57: deba@57: #endif