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@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: deba@57: /// \brief Skeleton class for graph Node and Arc types deba@57: /// deba@57: /// This class describes the interface of Node and Arc (and Edge deba@57: /// in undirected graphs) subtypes of graph types. deba@57: /// deba@57: /// \note This class is a template class so that we can use it to deba@57: /// create graph skeleton classes. The reason for this is than Node deba@57: /// and Arc types should \em not derive from the same base class. deba@57: /// For Node you should instantiate it with character 'n' and for Arc deba@57: /// with 'a'. deba@57: deba@57: #ifndef DOXYGEN kpeter@559: template deba@57: #endif deba@57: class GraphItem { deba@57: public: deba@57: /// \brief Default constructor. alpar@209: /// 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() {} deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. deba@57: /// deba@57: GraphItem(const GraphItem &) {} deba@57: /// \brief Invalid constructor \& conversion. deba@57: /// deba@57: /// This constructor initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphItem(Invalid) {} deba@57: /// \brief Assign operator for nodes. deba@57: /// alpar@209: /// The nodes are assignable. deba@57: /// deba@57: GraphItem& operator=(GraphItem const&) { return *this; } deba@57: /// \brief Equality operator. deba@57: /// deba@57: /// Two iterators are equal if and only if they represents the deba@57: /// same node in the graph or both are invalid. deba@57: bool operator==(GraphItem) const { return false; } deba@57: /// \brief Inequality operator. deba@57: /// deba@57: /// \sa operator==(const Node& n) deba@57: /// deba@57: bool operator!=(GraphItem) const { return false; } deba@57: deba@57: /// \brief Artificial ordering operator. deba@57: /// deba@57: /// To allow the use of graph descriptors as key type in std::map or deba@57: /// similar associative container we require this. 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. deba@57: bool operator<(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) && (ia < ib); 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: deba@57: /// \brief An empty base directed graph class. alpar@209: /// deba@57: /// This class provides the minimal set of features needed for a kpeter@503: /// directed graph structure. All digraph concepts have to deba@57: /// conform to this base directed graph. It just provides types deba@57: /// for nodes and arcs and functions to get the source and the deba@57: /// target of the 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: /// alpar@209: /// This class represents the Nodes of the digraph. deba@57: /// deba@57: typedef GraphItem<'n'> Node; deba@57: deba@57: /// \brief Arc class of the digraph. deba@57: /// alpar@209: /// This class represents the Arcs of the digraph. deba@57: /// deba@57: typedef GraphItem<'e'> Arc; deba@57: deba@57: /// \brief Gives back the target node of an arc. deba@57: /// deba@57: /// Gives back the target node of an arc. deba@57: /// deba@57: Node target(const Arc&) const { return INVALID;} deba@57: deba@57: /// \brief Gives back the source node of an arc. deba@57: /// deba@57: /// Gives back the source node of an arc. deba@57: /// deba@57: Node source(const Arc&) const { return INVALID;} deba@57: deba@57: /// \brief Gives back the opposite node on the given arc. deba@57: /// deba@57: /// Gives back 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: deba@57: /// \brief An empty base undirected graph class. alpar@209: /// deba@57: /// This class provides the minimal set of features needed for an deba@57: /// undirected graph structure. All undirected graph concepts have kpeter@503: /// to conform to this base graph. It just provides types for deba@57: /// nodes, arcs and edges and functions to get the deba@57: /// source and the target of the arcs and edges, deba@57: /// conversion from arcs to edges and function to get deba@57: /// both direction of the edges. deba@57: class BaseGraphComponent : public BaseDigraphComponent { deba@57: public: deba@57: typedef BaseDigraphComponent::Node Node; deba@57: typedef BaseDigraphComponent::Arc Arc; deba@57: /// \brief Undirected arc class of the graph. deba@57: /// deba@57: /// This class represents the edges of the graph. deba@57: /// The undirected graphs can be used as a directed graph which deba@57: /// for each arc contains the opposite arc too so the graph is deba@57: /// bidirected. The edge represents two opposite deba@57: /// directed arcs. deba@57: class Edge : public GraphItem<'u'> { deba@57: public: deba@57: typedef GraphItem<'u'> Parent; deba@57: /// \brief Default constructor. alpar@209: /// 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() {} deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. deba@57: /// deba@57: Edge(const Edge &) : Parent() {} deba@57: /// \brief Invalid constructor \& conversion. deba@57: /// deba@57: /// This constructor initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: Edge(Invalid) {} deba@57: /// \brief Converter from arc to edge. deba@57: /// deba@57: /// Besides the core graph item functionality each arc should alpar@209: /// be convertible to the represented edge. deba@57: Edge(const Arc&) {} deba@57: /// \brief Assign arc to edge. deba@57: /// 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: deba@57: /// \brief Returns 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: deba@57: /// \brief Returns the directed arc. deba@57: /// deba@57: /// Returns the directed arc from its direction and the deba@57: /// represented edge. alpar@209: Arc direct(const Edge&, bool) const { return INVALID;} deba@57: deba@57: /// \brief Returns the directed arc. deba@57: /// deba@57: /// Returns the directed arc from its source and the deba@57: /// represented edge. alpar@209: Arc direct(const Edge&, const Node&) const { return INVALID;} deba@57: deba@57: /// \brief Returns the opposite arc. deba@57: /// deba@57: /// Returns the opposite arc. It is the arc representing the deba@57: /// same edge and has opposite direction. deba@57: Arc oppositeArc(const Arc&) const { return INVALID;} deba@57: deba@57: /// \brief Gives back one ending of an edge. deba@57: /// deba@57: /// Gives back one ending of an edge. deba@57: Node u(const Edge&) const { return INVALID;} deba@57: deba@57: /// \brief Gives back the other ending of an edge. deba@57: /// deba@57: /// Gives back the other ending of an edge. deba@57: Node v(const Edge&) 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(); alpar@209: 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); 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: deba@57: /// \brief An empty idable base digraph class. alpar@209: /// deba@57: /// This class provides beside the core digraph features deba@57: /// core id functions for the digraph structure. kpeter@503: /// The most of the base digraphs should conform to this concept. deba@57: /// The id's are unique and immutable. 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: alpar@209: /// \brief Gives back an unique integer id for the Node. deba@57: /// alpar@209: /// Gives back an unique integer id for the Node. deba@57: /// deba@57: int id(const Node&) const { return -1;} deba@57: deba@57: /// \brief Gives back the node by the unique id. deba@57: /// deba@57: /// Gives back the node by the unique id. deba@57: /// If the digraph does not contain node with the given id alpar@209: /// then the result of the function is undetermined. deba@57: Node nodeFromId(int) const { return INVALID;} deba@57: alpar@209: /// \brief Gives back an unique integer id for the Arc. deba@57: /// alpar@209: /// Gives back an unique integer id for the Arc. deba@57: /// deba@57: int id(const Arc&) const { return -1;} deba@57: deba@57: /// \brief Gives back the arc by the unique id. deba@57: /// deba@57: /// Gives back the arc by the unique id. deba@57: /// If the digraph does not contain arc with the given id alpar@209: /// then the result of the function is undetermined. deba@57: Arc arcFromId(int) const { return INVALID;} deba@57: deba@57: /// \brief Gives back an integer greater or equal to the maximum deba@57: /// Node id. deba@57: /// deba@57: /// Gives back an integer greater or equal to the maximum Node deba@57: /// id. deba@57: int maxNodeId() const { return -1;} deba@57: deba@57: /// \brief Gives back an integer greater or equal to the maximum deba@57: /// Arc id. deba@57: /// deba@57: /// Gives back an integer greater or equal to the maximum Arc deba@57: /// id. deba@57: 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: deba@57: /// \brief An empty idable base undirected graph class. alpar@209: /// deba@57: /// This class provides beside the core undirected graph features deba@57: /// core id functions for the undirected graph structure. The kpeter@503: /// most of the base undirected graphs should conform to this deba@57: /// concept. The id's are unique and immutable. 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: alpar@209: /// \brief Gives back an unique integer id for the Edge. deba@57: /// alpar@209: /// Gives back an unique integer id for the Edge. deba@57: /// deba@57: int id(const Edge&) const { return -1;} deba@57: deba@57: /// \brief Gives back the edge by the unique id. deba@57: /// deba@57: /// Gives back the edge by the unique id. If the deba@57: /// graph does not contain arc with the given id then the deba@57: /// result of the function is undetermined. deba@57: Edge edgeFromId(int) const { return INVALID;} deba@57: deba@57: /// \brief Gives back an integer greater or equal to the maximum deba@57: /// Edge id. deba@57: /// deba@57: /// Gives back an integer greater or equal to the maximum Edge deba@57: /// id. deba@57: int maxEdgeId() const { return -1;} deba@57: deba@57: template deba@57: struct Constraints { deba@57: alpar@209: void constraints() { alpar@209: checkConcept(); 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: deba@57: /// \brief Skeleton class for graph NodeIt and ArcIt deba@57: /// deba@57: /// Skeleton class for graph NodeIt and ArcIt. deba@57: /// kpeter@559: template kpeter@559: class GraphItemIt : public Item { deba@57: public: deba@57: /// \brief Default constructor. deba@57: /// deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: GraphItemIt() {} deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. deba@57: /// deba@57: GraphItemIt(const GraphItemIt& ) {} deba@57: /// \brief Sets the iterator to the first item. deba@57: /// deba@57: /// Sets the iterator to the first item of \c the graph. deba@57: /// kpeter@559: explicit GraphItemIt(const GR&) {} deba@57: /// \brief Invalid constructor \& conversion. deba@57: /// deba@57: /// This constructor initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphItemIt(Invalid) {} deba@57: /// \brief Assign operator for items. deba@57: /// alpar@209: /// The items are assignable. deba@57: /// alpar@209: GraphItemIt& operator=(const GraphItemIt&) { return *this; } deba@57: /// \brief Next item. alpar@209: /// deba@57: /// Assign the iterator to the next item. deba@57: /// deba@57: GraphItemIt& operator++() { return *this; } deba@57: /// \brief Equality operator alpar@209: /// 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;} deba@57: /// \brief Inequality operator alpar@209: /// deba@57: /// \sa operator==(Node n) deba@57: /// deba@57: bool operator!=(const GraphItemIt&) const { return true;} alpar@209: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { alpar@209: _GraphItemIt it1(g); alpar@209: _GraphItemIt it2; deba@57: alpar@209: it2 = ++it1; alpar@209: ++it2 = it1; alpar@209: ++(++it1); deba@57: kpeter@559: Item bi = it1; alpar@209: bi = it2; alpar@209: } kpeter@559: GR& g; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief Skeleton class for graph InArcIt and OutArcIt deba@57: /// deba@57: /// \note Because InArcIt and OutArcIt may not inherit from the same kpeter@559: /// base class, the \c sel is a additional template parameter (selector). kpeter@559: /// For InArcIt you should instantiate it with character 'i' and for deba@57: /// OutArcIt with 'o'. kpeter@559: template kpeter@559: class GraphIncIt : public Item { deba@57: public: deba@57: /// \brief Default constructor. deba@57: /// deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: GraphIncIt() {} deba@57: /// \brief Copy constructor. deba@57: /// deba@57: /// Copy constructor. deba@57: /// kpeter@559: GraphIncIt(GraphIncIt const& gi) : Item(gi) {} alpar@209: /// \brief Sets the iterator to the first arc incoming into or outgoing deba@57: /// from the node. deba@57: /// alpar@209: /// Sets the iterator to the first arc incoming into or outgoing deba@57: /// from the node. deba@57: /// kpeter@559: explicit GraphIncIt(const GR&, const Base&) {} deba@57: /// \brief Invalid constructor \& conversion. deba@57: /// deba@57: /// This constructor initializes the item to be invalid. deba@57: /// \sa Invalid for more details. deba@57: GraphIncIt(Invalid) {} deba@57: /// \brief Assign operator for iterators. deba@57: /// alpar@209: /// The iterators are assignable. deba@57: /// alpar@209: GraphIncIt& operator=(GraphIncIt const&) { return *this; } deba@57: /// \brief Next item. deba@57: /// deba@57: /// Assign the iterator to the next item. deba@57: /// deba@57: GraphIncIt& operator++() { return *this; } deba@57: deba@57: /// \brief Equality operator deba@57: /// 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: /// deba@57: /// \sa operator==(Node n) deba@57: /// 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; deba@57: alpar@209: it2 = ++it1; alpar@209: ++it2 = it1; alpar@209: ++(++it1); kpeter@559: Item e = it1; alpar@209: e = it2; deba@57: alpar@209: } deba@57: kpeter@559: Item arc; kpeter@559: Base node; kpeter@559: GR graph; alpar@209: _GraphIncIt it; deba@57: }; deba@57: }; deba@57: deba@57: deba@57: /// \brief An empty iterable digraph class. deba@57: /// deba@57: /// This class provides beside the core digraph features deba@57: /// iterator based iterable interface for the digraph structure. 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: deba@57: /// \name Base iteration alpar@209: /// deba@57: /// This interface provides functions for iteration on digraph items deba@57: /// alpar@209: /// @{ deba@57: deba@57: /// \brief Gives back the first node in the iterating order. alpar@209: /// deba@57: /// Gives back the first node in the iterating order. alpar@209: /// deba@57: void first(Node&) const {} deba@57: deba@57: /// \brief Gives back the next node in the iterating order. deba@57: /// deba@57: /// Gives back the next node in the iterating order. alpar@209: /// deba@57: void next(Node&) const {} deba@57: deba@57: /// \brief Gives back the first arc in the iterating order. deba@57: /// deba@57: /// Gives back the first arc in the iterating order. alpar@209: /// deba@57: void first(Arc&) const {} deba@57: deba@57: /// \brief Gives back the next arc in the iterating order. deba@57: /// deba@57: /// Gives back the next arc in the iterating order. alpar@209: /// deba@57: void next(Arc&) const {} deba@57: deba@57: deba@57: /// \brief Gives back the first of the arcs point to the given deba@57: /// node. deba@57: /// deba@57: /// Gives back the first of the arcs point to the given node. alpar@209: /// deba@57: void firstIn(Arc&, const Node&) const {} deba@57: deba@57: /// \brief Gives back the next of the arcs points to the given deba@57: /// node. deba@57: /// deba@57: /// Gives back the next of the arcs points to the given node. deba@57: /// deba@57: void nextIn(Arc&) const {} deba@57: deba@57: /// \brief Gives back the first of the arcs start from the deba@57: /// given node. alpar@209: /// deba@57: /// Gives back the first of the arcs start from the given node. alpar@209: /// deba@57: void firstOut(Arc&, const Node&) const {} deba@57: deba@57: /// \brief Gives back the next of the arcs start from the given deba@57: /// node. deba@57: /// deba@57: /// Gives back the next of the arcs start from the given node. alpar@209: /// deba@57: void nextOut(Arc&) const {} deba@57: deba@57: /// @} deba@57: deba@57: /// \name Class based iteration alpar@209: /// deba@57: /// This interface provides functions for iteration on 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: 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 ArcIt; deba@57: deba@57: /// \brief This iterator goes trough the incoming arcs of a node. deba@57: /// deba@57: /// This iterator goes trough the \e inccoming 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: /// deba@57: /// Gives back the base node of the iterator. deba@57: /// It is always the target 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: /// deba@57: /// Gives back the running node of the iterator. deba@57: /// It is always the source 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: /// deba@57: /// Gives back the base node of the iterator. deba@57: /// It is always the source 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: /// deba@57: /// Gives back the running node of the iterator. deba@57: /// It is always the target 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; deba@57: typename _Digraph::InArcIt ieit(INVALID); deba@57: typename _Digraph::OutArcIt oeit(INVALID); deba@57: n = digraph.baseNode(ieit); deba@57: n = digraph.runningNode(ieit); deba@57: n = digraph.baseNode(oeit); deba@57: n = digraph.runningNode(oeit); deba@57: ignore_unused_variable_warning(n); deba@57: } deba@57: } alpar@209: alpar@209: const _Digraph& digraph; alpar@209: deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty iterable undirected graph class. deba@57: /// deba@57: /// This class provides beside the core graph features iterator deba@57: /// based iterable interface for the undirected graph structure. 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: deba@57: /// \name Base iteration alpar@209: /// deba@57: /// This interface provides functions for iteration on graph items alpar@209: /// @{ deba@57: kpeter@559: using IterableDigraphComponent::first; kpeter@559: using IterableDigraphComponent::next; deba@57: deba@57: /// \brief Gives back the first edge in the iterating deba@57: /// order. deba@57: /// deba@57: /// Gives back the first edge in the iterating order. alpar@209: /// deba@57: void first(Edge&) const {} deba@57: deba@57: /// \brief Gives back the next edge in the iterating deba@57: /// order. deba@57: /// deba@57: /// Gives back the next edge in the iterating order. alpar@209: /// deba@57: void next(Edge&) const {} deba@57: deba@57: deba@57: /// \brief Gives back the first of the edges from the deba@57: /// given node. deba@57: /// deba@57: /// Gives back the first of the edges from the given deba@57: /// node. The bool parameter gives back that direction which deba@57: /// gives a good direction of the edge so the source of the deba@57: /// directed arc is the 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: /// deba@57: /// Gives back the next of the edges from the given deba@57: /// node. The bool parameter should be used as the \c firstInc() deba@57: /// 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: deba@57: /// \name Class based iteration alpar@209: /// deba@57: /// This interface provides functions for iteration on graph 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: typedef GraphItemIt EdgeIt; deba@57: /// \brief This iterator goes trough the incident arcs of a deba@57: /// node. deba@57: /// deba@57: /// This iterator goes trough the incident arcs of a certain deba@57: /// node of a graph. deba@78: typedef GraphIncIt IncEdgeIt; deba@57: /// \brief The base node of the iterator. deba@57: /// deba@57: /// 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: /// deba@57: /// 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; deba@78: typename _Graph::IncEdgeIt ueit(INVALID); deba@57: n = graph.baseNode(ueit); deba@57: n = graph.runningNode(ueit); deba@57: } deba@57: } alpar@209: alpar@209: const _Graph& graph; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty alteration notifier digraph class. alpar@209: /// deba@57: /// This class provides beside the core digraph features alteration deba@57: /// notifier interface for the digraph structure. This implements deba@57: /// an observer-notifier pattern for each digraph item. More deba@57: /// obsevers can be registered into the notifier and whenever an deba@57: /// alteration occured in the digraph all the observers will 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: deba@57: /// The node observer registry. alpar@209: typedef AlterationNotifier deba@57: NodeNotifier; deba@57: /// The arc observer registry. alpar@209: typedef AlterationNotifier deba@57: ArcNotifier; alpar@209: deba@57: /// \brief Gives back the node alteration notifier. deba@57: /// deba@57: /// Gives back the node alteration notifier. deba@57: NodeNotifier& notifier(Node) const { alpar@209: return NodeNotifier(); deba@57: } alpar@209: deba@57: /// \brief Gives back the arc alteration notifier. deba@57: /// deba@57: /// 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; alpar@209: deba@57: }; alpar@209: deba@57: }; deba@57: deba@57: /// \brief An empty alteration notifier undirected graph class. alpar@209: /// deba@57: /// This class provides beside the core graph features alteration deba@57: /// notifier interface for the graph structure. This implements deba@57: /// an observer-notifier pattern for each graph item. More deba@57: /// obsevers can be registered into the notifier and whenever an deba@57: /// alteration occured in the graph all the observers will 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@57: typedef typename Base::Edge Edge; deba@57: deba@57: deba@57: /// The arc observer registry. alpar@209: typedef AlterationNotifier deba@57: EdgeNotifier; alpar@209: deba@57: /// \brief Gives back the arc alteration notifier. deba@57: /// deba@57: /// Gives back the arc 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() { alpar@209: 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: deba@57: /// \brief Class describing the concept of graph maps alpar@209: /// deba@57: /// This class describes the common interface of the graph maps kpeter@313: /// (NodeMap, ArcMap), that is maps that can be used to deba@57: /// associate data to graph descriptors (nodes or arcs). kpeter@559: template kpeter@559: class GraphMap : public ReadWriteMap { deba@57: public: deba@57: kpeter@559: typedef ReadWriteMap Parent; deba@57: deba@57: /// The graph type of the map. kpeter@559: typedef GR Graph; 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; deba@57: deba@57: /// \brief Construct a new map. deba@57: /// deba@57: /// Construct a new map for the graph. deba@57: explicit GraphMap(const Graph&) {} deba@57: /// \brief Construct a new map with default value. deba@57: /// deba@57: /// Construct a new map for the graph and initalise the values. deba@57: GraphMap(const Graph&, 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: deba@57: /// \brief Assign operator. deba@57: /// deba@57: /// Assign 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() { alpar@209: checkConcept, _Map >(); alpar@209: // Construction with a graph parameter alpar@209: _Map a(g); alpar@209: // Constructor with a graph and a default value parameter alpar@209: _Map a2(g,t); alpar@209: // Copy constructor. kpeter@263: // _Map b(c); alpar@209: kpeter@263: // ReadMap cmap; kpeter@263: // b = cmap; deba@57: kpeter@263: ignore_unused_variable_warning(a); alpar@209: ignore_unused_variable_warning(a2); kpeter@263: // ignore_unused_variable_warning(b); alpar@209: } deba@57: alpar@209: const _Map &c; alpar@209: const Graph &g; alpar@209: const typename GraphMap::Value &t; deba@57: }; deba@57: deba@57: }; deba@57: deba@57: /// \brief An empty mappable digraph class. deba@57: /// deba@57: /// This class provides beside the core digraph features deba@57: /// map interface for the digraph structure. 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: deba@57: /// \brief ReadWrite map of the nodes. deba@57: /// deba@57: /// ReadWrite map of the nodes. deba@57: /// kpeter@559: template kpeter@559: class NodeMap : public GraphMap { deba@57: public: kpeter@559: typedef GraphMap Parent; deba@57: 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: /// alpar@209: /// Construct a new map for the digraph and initalise 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: alpar@209: /// \brief Assign operator. alpar@209: /// alpar@209: /// Assign 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: deba@57: /// \brief ReadWrite map of the arcs. deba@57: /// deba@57: /// ReadWrite map of the arcs. deba@57: /// kpeter@559: template kpeter@559: class ArcMap : public GraphMap { deba@57: public: kpeter@559: typedef GraphMap Parent; deba@57: 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: /// alpar@209: /// Construct a new map for the digraph and initalise 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: alpar@209: /// \brief Assign operator. alpar@209: /// alpar@209: /// Assign 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: alpar@209: _Digraph& digraph; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty mappable base bipartite graph class. deba@57: /// deba@57: /// This class provides beside the core graph features deba@57: /// map interface for the graph structure. 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: deba@57: /// \brief ReadWrite map of the edges. deba@57: /// deba@57: /// ReadWrite map of the edges. deba@57: /// kpeter@559: template kpeter@559: class EdgeMap : public GraphMap { deba@57: public: kpeter@559: typedef GraphMap Parent; deba@57: 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: /// alpar@209: /// Construct a new map for the graph and initalise 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: alpar@209: /// \brief Assign operator. alpar@209: /// alpar@209: /// Assign 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() { alpar@209: 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: alpar@209: _Graph& graph; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty extendable digraph class. deba@57: /// deba@57: /// This class provides beside the core digraph features digraph deba@57: /// extendable interface for the digraph structure. The main deba@57: /// difference between the base and this interface is that the deba@57: /// digraph alterations should handled already on this level. 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: deba@57: /// \brief Adds a new node to the digraph. deba@57: /// deba@57: /// Adds a new node to the digraph. deba@57: /// deba@57: Node addNode() { alpar@209: return INVALID; deba@57: } alpar@209: deba@57: /// \brief Adds a new arc connects the given two nodes. deba@57: /// deba@57: /// Adds a new arc connects the the given two nodes. 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: deba@57: /// \brief An empty extendable base undirected graph class. deba@57: /// deba@57: /// This class provides beside the core undirected graph features deba@57: /// core undircted graph extend interface for the graph structure. deba@57: /// The main difference between the base and this interface is deba@57: /// that the graph alterations should handled already on this deba@57: /// level. 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: deba@57: /// \brief Adds a new node to the graph. deba@57: /// deba@57: /// Adds a new node to the graph. deba@57: /// deba@57: Node addNode() { alpar@209: return INVALID; deba@57: } alpar@209: deba@57: /// \brief Adds a new arc connects the given two nodes. deba@57: /// deba@57: /// Adds a new arc connects the the given two nodes. deba@57: Edge addArc(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: deba@57: /// \brief An empty erasable digraph class. alpar@209: /// deba@57: /// This class provides beside the core digraph features core erase deba@57: /// functions for the digraph structure. The main difference between deba@57: /// the base and this interface is that the digraph alterations deba@57: /// should handled already on this level. 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@209: /// Erase a node from the digraph. This function should deba@57: /// erase all arcs connecting to the node. alpar@209: void erase(const Node&) {} deba@57: deba@57: /// \brief Erase an arc from the digraph. deba@57: /// deba@57: /// Erase an arc from the digraph. deba@57: /// deba@57: void erase(const Arc&) {} deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept(); alpar@209: typename _Digraph::Node node; alpar@209: digraph.erase(node); alpar@209: typename _Digraph::Arc arc; alpar@209: digraph.erase(arc); alpar@209: } deba@57: alpar@209: _Digraph& digraph; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty erasable base undirected graph class. alpar@209: /// deba@57: /// This class provides beside the core undirected graph features deba@57: /// core erase functions for the undirceted graph structure. The deba@57: /// main difference between the base and this interface is that deba@57: /// the graph alterations should handled already on this level. 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: /// deba@57: /// Erase a node from the graph. This function should erase deba@57: /// arcs connecting to the node. alpar@209: void erase(const Node&) {} deba@57: deba@57: /// \brief Erase an arc from the graph. deba@57: /// deba@57: /// Erase an arc from the graph. deba@57: /// deba@57: void erase(const Edge&) {} deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept(); alpar@209: typename _Graph::Node node; alpar@209: graph.erase(node); alpar@209: typename _Graph::Edge edge; alpar@209: graph.erase(edge); alpar@209: } deba@57: alpar@209: _Graph& graph; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty clearable base digraph class. deba@57: /// deba@57: /// This class provides beside the core digraph features core clear deba@57: /// functions for the digraph structure. The main difference between deba@57: /// the base and this interface is that the digraph alterations deba@57: /// should handled already on this level. 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: /// deba@57: /// Erase all nodes and arcs from the digraph. deba@57: /// 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: alpar@209: _Digraph digraph; deba@57: }; deba@57: }; deba@57: deba@57: /// \brief An empty clearable base undirected graph class. deba@57: /// deba@57: /// This class provides beside the core undirected graph features deba@57: /// core clear functions for the undirected graph structure. The deba@57: /// main difference between the base and this interface is that deba@57: /// the graph alterations should handled already on this level. kpeter@559: template kpeter@559: class ClearableGraphComponent : public ClearableDigraphComponent { deba@57: public: deba@57: kpeter@559: typedef BAS Base; deba@57: deba@57: template deba@57: struct Constraints { alpar@209: void constraints() { deba@57: checkConcept, _Graph>(); alpar@209: } deba@57: alpar@209: _Graph graph; deba@57: }; deba@57: }; deba@57: deba@57: } deba@57: deba@57: } deba@57: deba@57: #endif