diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,982 +0,0 @@ -/* -*- C++ -*- - * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -///\ingroup graph_concepts -///\file -///\brief The graph components. - - -#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H -#define LEMON_CONCEPT_GRAPH_COMPONENT_H - -#include -#include - -#include - -namespace lemon { - namespace concept { - - /// \addtogroup graph_concepts - /// @{ - - /**************** Graph iterator concepts ****************/ - - /// Skeleton class for graph Node and Edge types - - /// This class describes the interface of Node and Edge (and UndirEdge - /// in undirected graphs) subtypes of graph types. - /// - /// \note This class is a template class so that we can use it to - /// create graph skeleton classes. The reason for this is than Node - /// and Edge types should \em not derive from the same base class. - /// For Node you should instantiate it with character 'n' and for Edge - /// with 'e'. - -#ifndef DOXYGEN - template -#endif - class GraphItem { - public: - /// Default constructor. - - /// \warning The default constructor is not required to set - /// the item to some well-defined value. So you should consider it - /// as uninitialized. - GraphItem() {} - /// Copy constructor. - - /// Copy constructor. - /// - GraphItem(GraphItem const&) {} - /// Invalid constructor \& conversion. - - /// This constructor initializes the item to be invalid. - /// \sa Invalid for more details. - GraphItem(Invalid) {} - /// Assign operator for nodes. - - /// The nodes are assignable. - /// - GraphItem& operator=(GraphItem const&) { return *this; } - /// Equality operator. - - /// Two iterators are equal if and only if they represents the - /// same node in the graph or both are invalid. - bool operator==(GraphItem) const { return false; } - /// Inequality operator. - - /// \sa operator==(const Node& n) - /// - bool operator!=(GraphItem) const { return false; } - - /// Artificial ordering operator. - - /// To allow the use of graph descriptors as key type in std::map or - /// similar associative container we require this. - /// - /// \note This operator only have to define some strict ordering of - /// the items; this order has nothing to do with the iteration - /// ordering of the items. - /// - /// \bug This is a technical requirement. Do we really need this? - bool operator<(GraphItem) const { return false; } - - template - struct Constraints { - void constraints() { - _GraphItem i1; - _GraphItem i2 = i1; - _GraphItem i3 = INVALID; - - i1 = i2 = i3; - - bool b; - // b = (ia == ib) && (ia != ib) && (ia < ib); - b = (ia == ib) && (ia != ib); - b = (ia == INVALID) && (ib != INVALID); - // b = (ia < ib); - } - - const _GraphItem &ia; - const _GraphItem &ib; - }; - }; - - /// A type describing the concept of graph node - - /// This is an instantiation of \ref GraphItem which can be used as a - /// Node subtype in graph skeleton definitions - typedef GraphItem<'n'> GraphNode; - - /// A type describing the concept of graph edge - - /// This is an instantiation of \ref GraphItem which can be used as a - /// Edge subtype in graph skeleton definitions - typedef GraphItem<'e'> GraphEdge; - - - /**************** Basic features of graphs ****************/ - - /// An empty base graph class. - - /// This class provides the minimal set of features needed for a graph - /// structure. All graph concepts have to be conform to this base - /// graph. - /// - /// \bug This is not true. The minimal graph concept is the - /// BaseIterableGraphComponent. - - class BaseGraphComponent { - public: - - typedef BaseGraphComponent Graph; - - /// Node class of the graph. - - /// This class represents the Nodes of the graph. - /// - typedef GraphItem<'n'> Node; - - /// Edge class of the graph. - - /// This class represents the Edges of the graph. - /// - typedef GraphItem<'e'> Edge; - - ///Gives back the target node of an edge. - - ///Gives back the target node of an edge. - /// - Node target(const Edge&) const { return INVALID;} - - ///Gives back the source node of an edge. - - ///Gives back the source node of an edge. - /// - Node source(const Edge&) const { return INVALID;} - - - template - struct Constraints { - typedef typename _Graph::Node Node; - typedef typename _Graph::Edge Edge; - - void constraints() { - checkConcept, Node>(); - checkConcept, Edge>(); - { - Node n; - Edge e; - n = graph.source(e); - n = graph.target(e); - } - } - - const _Graph& graph; - }; - }; - - /// An empty iterable base graph class. - - /// This class provides beside the core graph features - /// core iterable interface for the graph structure. - /// Most of the base graphs should be conform to this concept. - - class BaseIterableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Gives back the first Node in the iterating order. - - /// Gives back the first Node in the iterating order. - /// - void first(Node&) const {} - - /// Gives back the next Node in the iterating order. - - /// Gives back the next Node in the iterating order. - /// - void next(Node&) const {} - - /// Gives back the first Edge in the iterating order. - - /// Gives back the first Edge in the iterating order. - /// - void first(Edge&) const {} - /// Gives back the next Edge in the iterating order. - - /// Gives back the next Edge in the iterating order. - /// - void next(Edge&) const {} - - - /// Gives back the first of the Edges point to the given Node. - - /// Gives back the first of the Edges point to the given Node. - /// - void firstIn(Edge&, const Node&) const {} - - /// Gives back the next of the Edges points to the given Node. - - - /// Gives back the next of the Edges points to the given Node. - /// - void nextIn(Edge&) const {} - - /// Gives back the first of the Edges start from the given Node. - - /// Gives back the first of the Edges start from the given Node. - /// - void firstOut(Edge&, const Node&) const {} - - /// Gives back the next of the Edges start from the given Node. - - /// Gives back the next of the Edges start from the given Node. - /// - void nextOut(Edge&) const {} - - - template - struct Constraints { - - void constraints() { - checkConcept< BaseGraphComponent, _Graph >(); - typename _Graph::Node node; - typename _Graph::Edge edge; - { - graph.first(node); - graph.next(node); - } - { - graph.first(edge); - graph.next(edge); - } - { - graph.firstIn(edge, node); - graph.nextIn(edge); - } - { - graph.firstOut(edge, node); - graph.nextOut(edge); - } - } - - const _Graph& graph; - }; - }; - - /// An empty idable base graph class. - - /// This class provides beside the core graph features - /// core id functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - /// The id's are unique and immutable. - class IDableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Gives back an unique integer id for the Node. - - /// Gives back an unique integer id for the Node. - /// - int id(const Node&) const { return -1;} - - /// \brief Gives back the node by the unique id. - /// - /// Gives back the node by the unique id. - /// If the graph does not contain node with the given id - /// then the result of the function is undetermined. - Node fromId(int , Node) const { return INVALID;} - - /// \brief Gives back an unique integer id for the Edge. - /// - /// Gives back an unique integer id for the Edge. - /// - int id(const Edge&) const { return -1;} - - /// \brief Gives back the edge by the unique id. - /// - /// Gives back the edge by the unique id. - /// If the graph does not contain edge with the given id - /// then the result of the function is undetermined. - Edge fromId(int, Edge) const { return INVALID;} - - template - struct Constraints { - - void constraints() { - checkConcept< BaseGraphComponent, _Graph >(); - typename _Graph::Node node; - int nid = graph.id(node); - nid = graph.id(node); - node = graph.fromId(nid, Node()); - typename _Graph::Edge edge; - int eid = graph.id(edge); - eid = graph.id(edge); - edge = graph.fromId(eid, Edge()); - } - - const _Graph& graph; - }; - }; - - - /// An empty max-idable base graph class. - - /// This class provides beside the core graph features - /// core max id functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - /// The id's are unique and immutable. - class MaxIDableGraphComponent : virtual public BaseGraphComponent { - public: - - /// Gives back an integer greater or equal to the maximum Node id. - - /// Gives back an integer greater or equal to the maximum Node id. - /// - int maxId(Node = INVALID) const { return -1;} - - /// Gives back an integer greater or equal to the maximum Edge id. - - /// Gives back an integer greater or equal to the maximum Edge id. - /// - int maxId(Edge = INVALID) const { return -1;} - - template - struct Constraints { - - void constraints() { - checkConcept(); - int nid = graph.maxId(typename _Graph::Node()); - ignore_unused_variable_warning(nid); - int eid = graph.maxId(typename _Graph::Edge()); - ignore_unused_variable_warning(eid); - } - - const _Graph& graph; - }; - }; - - /// An empty extendable base graph class. - - /// This class provides beside the core graph features - /// core graph extend interface for the graph structure. - /// The most of the base graphs should be conform to this concept. - class BaseExtendableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Adds a new Node to the graph. - - /// Adds a new Node to the graph. - /// - Node addNode() { - return INVALID; - } - - /// Adds a new Edge connects the two Nodes to the graph. - - /// Adds a new Edge connects the two Nodes to the graph. - /// - Edge addEdge(const Node&, const Node&) { - return INVALID; - } - - template - struct Constraints { - void constraints() { - checkConcept(); - typename _Graph::Node node_a, node_b; - node_a = graph.addNode(); - typename _Graph::Edge edge; - edge = graph.addEdge(node_a, node_b); - } - - _Graph& graph; - }; - }; - - /// An empty erasable base graph class. - - /// This class provides beside the core graph features - /// core erase functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - class BaseErasableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Erase a Node from the graph. - - /// Erase a Node from the graph. This function should not - /// erase edges connecting to the Node. - void erase(const Node&) {} - - /// Erase an Edge from the graph. - - /// Erase an Edge from the graph. - /// - void erase(const Edge&) {} - - template - struct Constraints { - void constraints() { - checkConcept(); - typename _Graph::Node node; - graph.erase(node); - typename _Graph::Edge edge; - graph.erase(edge); - } - - _Graph& graph; - }; - }; - - /// An empty clearable base graph class. - - /// This class provides beside the core graph features - /// core clear functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - class ClearableGraphComponent : virtual public BaseGraphComponent { - public: - - /// Erase all the Nodes and Edges from the graph. - - /// Erase all the Nodes and Edges from the graph. - /// - void clear() {} - - template - struct Constraints { - void constraints() { - checkConcept(); - graph.clear(); - } - - _Graph graph; - }; - }; - - - /// Skeleton class for graph NodeIt and EdgeIt - - /// Skeleton class for graph NodeIt and EdgeIt. - /// - template - class GraphIterator : public _Item { - public: - /// \todo Don't we need the Item type as typedef? - - /// Default constructor. - - /// @warning The default constructor sets the iterator - /// to an undefined value. - GraphIterator() {} - /// Copy constructor. - - /// Copy constructor. - /// - GraphIterator(GraphIterator const&) {} - /// Sets the iterator to the first item. - - /// Sets the iterator to the first item of \c the graph. - /// - explicit GraphIterator(const _Graph&) {} - /// Invalid constructor \& conversion. - - /// This constructor initializes the item to be invalid. - /// \sa Invalid for more details. - GraphIterator(Invalid) {} - /// Assign operator for items. - - /// The items are assignable. - /// - GraphIterator& operator=(GraphIterator const&) { return *this; } - /// Next item. - - /// Assign the iterator to the next item. - /// - GraphIterator& operator++() { return *this; } - // Node operator*() const { return INVALID; } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(const GraphIterator&) const { return true;} - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(const GraphIterator&) const { return true;} - - template - struct Constraints { - void constraints() { - // checkConcept< Item, _GraphIterator >(); - _GraphIterator it1(g); - - /// \todo Do we need NodeIt(Node) kind of constructor? - // _GraphIterator it2(bj); - _GraphIterator it2; - - it2 = ++it1; - ++it2 = it1; - ++(++it1); - /// \bug This should be: is_base_and_derived - _Item bi = it1; - bi = it2; - } - _Graph& g; - }; - }; - - /// Skeleton class for graph InEdgeIt and OutEdgeIt - - /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same - /// base class, the _selector is a additional template parameter. For - /// InEdgeIt you should instantiate it with character 'i' and for - /// OutEdgeIt with 'o'. - /// \todo Is this a good name for this concept? - template - class GraphIncIterator : public Edge { - public: - /// Default constructor. - - /// @warning The default constructor sets the iterator - /// to an undefined value. - GraphIncIterator() {} - /// Copy constructor. - - /// Copy constructor. - /// - GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {} - /// Sets the iterator to the first edge incoming into or outgoing - /// from the node. - - /// Sets the iterator to the first edge incoming into or outgoing - /// from the node. - /// - explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {} - /// Invalid constructor \& conversion. - - /// This constructor initializes the item to be invalid. - /// \sa Invalid for more details. - GraphIncIterator(Invalid) {} - /// Assign operator for nodes. - - /// The nodes are assignable. - /// - GraphIncIterator& operator=(GraphIncIterator const&) { return *this; } - /// Next edge. - - /// Assign the iterator to the next node. - /// - GraphIncIterator& operator++() { return *this; } - - // Node operator*() const { return INVALID; } - - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(const GraphIncIterator&) const { return true;} - - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(const GraphIncIterator&) const { return true;} - - template - struct Constraints { - typedef typename Graph::Node Node; - void constraints() { - checkConcept, _GraphIncIterator>(); - _GraphIncIterator it1(graph, node); - /// \todo Do we need OutEdgeIt(Edge) kind of constructor? - // _GraphIncIterator it2(edge); - _GraphIncIterator it2; - - it2 = ++it1; - ++it2 = it1; - ++(++it1); - Edge e = it1; - e = it2; - - const_constraits(); - } - - void const_constraits() { - Node n = graph.baseNode(it); - n = graph.runningNode(it); - } - - Edge edge; - Node node; - Graph graph; - _GraphIncIterator it; - }; - }; - - - /// An empty iterable base graph class. - - /// This class provides beside the core graph features - /// iterator based iterable interface for the graph structure. - /// This concept is part of the StaticGraphConcept. - class IterableGraphComponent : virtual public BaseGraphComponent { - - public: - - typedef IterableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// This iterator goes through each node. - - /// This iterator goes through each node. - /// - typedef GraphIterator NodeIt; - /// This iterator goes through each node. - - /// This iterator goes through each node. - /// - typedef GraphIterator EdgeIt; - /// This iterator goes trough the incoming edges of a node. - - /// This iterator goes trough the \e inccoming edges of a certain node - /// of a graph. - typedef GraphIncIterator InEdgeIt; - /// This iterator goes trough the outgoing edges of a node. - - /// This iterator goes trough the \e outgoing edges of a certain node - /// of a graph. - typedef GraphIncIterator OutEdgeIt; - }; - - template - struct Constraints { - void constraints() { - checkConcept< BaseGraphComponent, _Graph>(); - - checkConcept, - typename _Graph::EdgeIt >(); - checkConcept, - typename _Graph::NodeIt >(); - checkConcept, typename _Graph::InEdgeIt >(); - checkConcept, typename _Graph::OutEdgeIt >(); - } - }; - - /// An empty alteration notifier base graph class. - - /// This class provides beside the core graph features - /// alteration notifier interface for the graph structure. - /// This is an observer-notifier pattern. More Obsevers can - /// be registered into the notifier and whenever an alteration - /// occured in the graph all the observers will notified about it. - class AlterableGraphComponent : virtual public BaseGraphComponent { - public: - - /// The edge observer registry. - typedef AlterationNotifier EdgeNotifier; - /// The node observer registry. - typedef AlterationNotifier NodeNotifier; - - /// \brief Gives back the edge alteration notifier. - /// - /// Gives back the edge alteration notifier. - EdgeNotifier getNotifier(Edge) const { - return EdgeNotifier(); - } - - /// \brief Gives back the node alteration notifier. - /// - /// Gives back the node alteration notifier. - NodeNotifier getNotifier(Node) const { - return NodeNotifier(); - } - - }; - - - /// Class describing the concept of graph maps - - /// This class describes the common interface of the graph maps - /// (NodeMap, EdgeMap), that is \ref maps-pages "maps" which can be used to - /// associate data to graph descriptors (nodes or edges). - template - class GraphMap : public ReadWriteMap { - protected: - GraphMap() {} - public: - /// \brief Construct a new map. - /// - /// Construct a new map for the graph. - explicit GraphMap(const Graph&) {} - /// \brief Construct a new map with default value. - /// - /// Construct a new map for the graph and initalise the values. - GraphMap(const Graph&, const _Value&) {} - /// \brief Copy constructor. - /// - /// Copy Constructor. - GraphMap(const GraphMap& gm) :ReadWriteMap(gm) {} - - /// \brief Assign operator. - /// - /// Assign operator. - GraphMap& operator=(const GraphMap&) { return *this;} - - template - struct Constraints { - void constraints() { - checkConcept, _Map >(); - // Construction with a graph parameter - _Map a(g); - // Constructor with a graph and a default value parameter - _Map a2(g,t); - // Copy constructor. Do we need it? - _Map b=c; - // Copy operator. Do we need it? - a=b; - - ignore_unused_variable_warning(a2); - } - - const _Map &c; - const Graph &g; - const typename GraphMap::Value &t; - }; - - }; - - /// An empty mappable base graph class. - - /// This class provides beside the core graph features - /// map interface for the graph structure. - /// This concept is part of the StaticGraphConcept. - class MappableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef MappableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// ReadWrite map of the nodes. - - /// ReadWrite map of the nodes. - /// - template - class NodeMap : public GraphMap { - private: - NodeMap(); - public: - /// \brief Construct a new map. - /// - /// Construct a new map for the graph. - /// \todo call the right parent class constructor - explicit NodeMap(const Graph&) {} - /// \brief Construct a new map with default value. - /// - /// Construct a new map for the graph and initalise the values. - NodeMap(const Graph&, const _Value&) {} - /// \brief Copy constructor. - /// - /// Copy Constructor. - NodeMap(const NodeMap& nm) : GraphMap(nm) {} - - /// \brief Assign operator. - /// - /// Assign operator. - NodeMap& operator=(const NodeMap&) { return *this;} - - }; - - /// ReadWrite map of the edges. - - /// ReadWrite map of the edges. - /// - template - class EdgeMap : public GraphMap { - private: - EdgeMap(); - public: - /// \brief Construct a new map. - /// - /// Construct a new map for the graph. - /// \todo call the right parent class constructor - explicit EdgeMap(const Graph&) {} - /// \brief Construct a new map with default value. - /// - /// Construct a new map for the graph and initalise the values. - EdgeMap(const Graph&, const _Value&) {} - /// \brief Copy constructor. - /// - /// Copy Constructor. - EdgeMap(const EdgeMap& em) :GraphMap(em) {} - - /// \brief Assign operator. - /// - /// Assign operator. - EdgeMap& operator=(const EdgeMap&) { return *this;} - - }; - - template - struct Constraints { - - struct Type { - int value; - Type() : value(0) {} - Type(int _v) : value(_v) {} - }; - - void constraints() { - checkConcept(); - { // int map test - typedef typename _Graph::template NodeMap IntNodeMap; - checkConcept, - IntNodeMap >(); - } { // bool map test - typedef typename _Graph::template NodeMap BoolNodeMap; - checkConcept, - BoolNodeMap >(); - } { // Type map test - typedef typename _Graph::template NodeMap TypeNodeMap; - checkConcept, - TypeNodeMap >(); - } - - { // int map test - typedef typename _Graph::template EdgeMap IntEdgeMap; - checkConcept, - IntEdgeMap >(); - } { // bool map test - typedef typename _Graph::template EdgeMap BoolEdgeMap; - checkConcept, - BoolEdgeMap >(); - } { // Type map test - typedef typename _Graph::template EdgeMap TypeEdgeMap; - checkConcept, - TypeEdgeMap >(); - } - } - - _Graph& graph; - }; - }; - - /// \brief An empty extendable extended graph class. - /// - /// This class provides beside the core graph features - /// item addition interface for the graph structure. - /// The difference between this class and the - /// \c BaseExtendableGraphComponent is that it should - /// notify the item alteration observers. - class ExtendableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef ExtendableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// \brief Add a node to the graph. - /// - /// Add a node to the graph and notify the observers. - Node addNode() { - return INVALID; - } - - /// \brief Add an edge to the graph. - /// - /// Add an edge to the graph and notify the observers. - Edge addEdge(const Node&, const Node&) { - return INVALID; - } - - template - struct Constraints { - void constraints() { - checkConcept(); - typename _Graph::Node node_a, node_b; - node_a = graph.addNode(); - typename _Graph::Edge edge; - edge = graph.addEdge(node_a, node_b); - } - _Graph& graph; - }; - }; - - /// \brief An empty erasable extended graph class. - /// - /// This class provides beside the core graph features - /// item erase interface for the graph structure. - /// The difference between this class and the - /// \c BaseErasableGraphComponent is that it should - /// notify the item alteration observers. - class ErasableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef ErasableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// \brief Erase the Node and notify the node alteration observers. - /// - /// Erase the Node and notify the node alteration observers. - void erase(const Node&) {} - - /// \brief Erase the Edge and notify the edge alteration observers. - /// - /// Erase the Edge and notify the edge alteration observers. - void erase(const Edge&) {} - - template - struct Constraints { - void constraints() { - checkConcept(); - typename _Graph::Node node; - graph.erase(node); - typename _Graph::Edge edge; - graph.erase(edge); - } - - _Graph& graph; - }; - }; - - /// @} - - } - -} - -#endif