# HG changeset patch # User deba # Date 1152558257 0 # Node ID 09a07a8515068df66fd08453bee9e76b5d20535e # Parent a907fb95f1e00e4d6c69be8052c5a7a8eec93985 Modifications in the Graph Component concepts diff -r a907fb95f1e0 -r 09a07a851506 lemon/concept/graph.h --- a/lemon/concept/graph.h Wed Jul 05 16:59:45 2006 +0000 +++ b/lemon/concept/graph.h Mon Jul 10 19:04:17 2006 +0000 @@ -32,30 +32,6 @@ namespace lemon { namespace concept { - - /**************** The full-featured graph concepts ****************/ - - - // \brief Modular static graph class. - // - // It should be the same as the \c Graph class. - class _Graph - : virtual public BaseGraphComponent, - public IterableGraphComponent, public MappableGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - template - struct Constraints { - void constraints() { - checkConcept(); - checkConcept(); - } - }; - }; - /// \addtogroup graph_concepts /// @{ @@ -410,10 +386,8 @@ /// \sa Reference /// \warning Making maps that can handle bool type (NodeMap) /// needs some extra attention! - /// \todo Wrong documentation template - class NodeMap : public ReadWriteMap< Node, T > - { + class NodeMap : public ReadWriteMap< Node, T > { public: ///\e @@ -424,8 +398,11 @@ ///Copy constructor NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } ///Assignment operator - NodeMap& operator=(const NodeMap&) { return *this; } - // \todo fix this concept + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; /// \brief Read write map of the edges to type \c T. @@ -434,10 +411,8 @@ /// \sa Reference /// \warning Making maps that can handle bool type (EdgeMap) /// needs some extra attention! - /// \todo Wrong documentation template - class EdgeMap : public ReadWriteMap - { + class EdgeMap : public ReadWriteMap { public: ///\e @@ -447,12 +422,21 @@ ///Copy constructor EdgeMap(const EdgeMap& em) : ReadWriteMap(em) { } ///Assignment operator - EdgeMap& operator=(const EdgeMap&) { return *this; } - // \todo fix this concept + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; template - struct Constraints : public _Graph::Constraints {}; + struct Constraints { + void constraints() { + checkConcept, Graph>(); + checkConcept, Graph>(); + checkConcept, Graph>(); + } + }; }; diff -r a907fb95f1e0 -r 09a07a851506 lemon/concept/graph_component.h --- a/lemon/concept/graph_component.h Wed Jul 05 16:59:45 2006 +0000 +++ b/lemon/concept/graph_component.h Mon Jul 10 19:04:17 2006 +0000 @@ -32,10 +32,8 @@ namespace lemon { namespace concept { - /**************** Graph iterator concepts ****************/ - - /// Skeleton class for graph Node and Edge types - + /// \brief Skeleton class for graph Node and Edge types + /// /// This class describes the interface of Node and Edge (and UEdge /// in undirected graphs) subtypes of graph types. /// @@ -50,48 +48,46 @@ #endif class GraphItem { public: - /// Default constructor. - + /// \brief 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. - + /// \brief Copy constructor. + /// /// Copy constructor. /// - GraphItem(GraphItem const&) {} - /// Invalid constructor \& conversion. - + GraphItem(const GraphItem &) {} + /// \brief Invalid constructor \& conversion. + /// /// This constructor initializes the item to be invalid. /// \sa Invalid for more details. GraphItem(Invalid) {} - /// Assign operator for nodes. - + /// \brief Assign operator for nodes. + /// /// The nodes are assignable. /// GraphItem& operator=(GraphItem const&) { return *this; } - /// Equality operator. - + /// \brief 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. - + /// \brief Inequality operator. + /// /// \sa operator==(const Node& n) /// bool operator!=(GraphItem) const { return false; } - /// Artificial ordering operator. - + /// \brief 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 @@ -107,7 +103,7 @@ // b = (ia == ib) && (ia != ib) && (ia < ib); b = (ia == ib) && (ia != ib); b = (ia == INVALID) && (ib != INVALID); - // b = (ia < ib); + b = (ia < ib); } const _GraphItem &ia; @@ -115,59 +111,47 @@ }; }; - /// 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. - + /// \brief 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. - + /// graph. It just provides types for nodes and edges and functions to + /// get the source and the target of the edges. class BaseGraphComponent { public: typedef BaseGraphComponent Graph; - /// Node class of the graph. - + /// \brief Node class of the graph. + /// /// This class represents the Nodes of the graph. /// typedef GraphItem<'n'> Node; - /// Edge class of the graph. - + /// \brief 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. + /// \brief 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. + /// \brief Gives back the source node of an edge. + /// + /// Gives back the source node of an edge. /// Node source(const Edge&) const { return INVALID;} + /// \brief Gives back the opposite node on the given edge. + /// + /// Gives back the opposite node on the given edge. + Node oppositeNode(const Node&, const Edge&) const { + return INVALID; + } template struct Constraints { @@ -182,6 +166,7 @@ Edge e(INVALID); n = graph.source(e); n = graph.target(e); + n = graph.oppositeNode(n, e); } } @@ -189,64 +174,185 @@ }; }; - /// An empty iterable base graph class. - + /// \brief An empty base undirected graph class. + /// + /// This class provides the minimal set of features needed for an + /// undirected graph structure. All undirected graph concepts have + /// to be conform to this base graph. It just provides types for + /// nodes, edges and undirected edges and functions to get the + /// source and the target of the edges and undirected edges, + /// conversion from edges to undirected edges and function to get + /// both direction of the undirected edges. + class BaseUGraphComponent : public BaseGraphComponent { + public: + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + /// \brief Undirected edge class of the graph. + /// + /// This class represents the undirected edges of the graph. + /// The undirected graphs can be used as a directed graph which + /// for each edge contains the opposite edge too so the graph is + /// bidirected. The undirected edge represents two opposite + /// directed edges. + class UEdge : public GraphItem<'u'> { + public: + typedef GraphItem<'u'> Parent; + /// \brief 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. + UEdge() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + UEdge(const UEdge &) : Parent() {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + UEdge(Invalid) {} + /// \brief Converter from edge to undirected edge. + /// + /// Besides the core graph item functionality each edge should + /// be convertible to the represented undirected edge. + UEdge(const Edge&) {} + }; + + /// \brief Returns the direction of the edge. + /// + /// Returns the direction of the edge. Each edge represents an + /// undirected edge with a direction. It gives back the + /// direction. + bool direction(const Edge&) const { return true; } + + /// \brief Returns the directed edge. + /// + /// Returns the directed edge from its direction and the + /// represented undirected edge. + Edge direct(const UEdge&, bool) const { return INVALID;} + + /// \brief Returns the directed edge. + /// + /// Returns the directed edge from its source and the + /// represented undirected edge. + Edge direct(const UEdge&, const Node&) const { return INVALID;} + + /// \brief Returns the opposite edge. + /// + /// Returns the opposite edge. It is the edge representing the + /// same undirected edge and has opposite direction. + Edge oppositeEdge(const Edge&) const { return INVALID;} + + /// \brief Gives back the target node of an undirected edge. + /// + /// Gives back the target node of an undirected edge. The name + /// target is a little confusing because the undirected edge + /// does not have target but it just means that one of the end + /// node. + Node target(const UEdge&) const { return INVALID;} + + /// \brief Gives back the source node of an undirected edge. + /// + /// Gives back the source node of an undirected edge. The name + /// source is a little confusing because the undirected edge + /// does not have source but it just means that one of the end + /// node. + Node source(const UEdge&) const { return INVALID;} + + template + struct Constraints { + typedef typename _Graph::Node Node; + typedef typename _Graph::Edge Edge; + typedef typename _Graph::UEdge UEdge; + + void constraints() { + checkConcept(); + checkConcept, UEdge>(); + { + Node n; + UEdge ue(INVALID); + Edge e; + n = graph.source(ue); + n = graph.target(ue); + e = graph.direct(ue, true); + e = graph.direct(ue, n); + e = graph.oppositeEdge(e); + ue = e; + bool d = graph.direction(e); + ignore_unused_variable_warning(d); + } + } + + const _Graph& graph; + }; + + }; + + /// \brief 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 { + template + class BaseIterableGraphComponent : public _Base { public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; - /// Gives back the first Node in the iterating order. - - /// Gives back the first Node in the iterating order. + /// \brief 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. + /// \brief 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. + /// \brief 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. + + /// \brief 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. + /// \brief 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. + /// \brief 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. + /// \brief 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. + /// \brief 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 {} @@ -280,20 +386,95 @@ }; }; - /// An empty idable base graph class. - + /// \brief An empty iterable base undirected graph class. + /// + /// This class provides beside the core undirceted graph features + /// core iterable interface for the undirected graph structure. + /// Most of the base undirected graphs should be conform to this + /// concept. + template + class BaseIterableUGraphComponent + : public BaseIterableGraphComponent<_Base> { + public: + + typedef _Base Base; + typedef typename Base::UEdge UEdge; + typedef typename Base::Node Node; + + using BaseIterableGraphComponent<_Base>::first; + using BaseIterableGraphComponent<_Base>::next; + + /// \brief Gives back the first undirected edge in the iterating + /// order. + /// + /// Gives back the first undirected edge in the iterating order. + /// + void first(UEdge&) const {} + + /// \brief Gives back the next undirected edge in the iterating + /// order. + /// + /// Gives back the next undirected edge in the iterating order. + /// + void next(UEdge&) const {} + + + /// \brief Gives back the first of the undirected edges from the + /// given node. + /// + /// Gives back the first of the undirected edges from the given + /// node. The bool parameter gives back that direction which + /// gives a good direction of the uedge so the source of the + /// directed edge is the given node. + void firstInc(UEdge&, bool&, const Node&) const {} + + /// \brief Gives back the next of the undirected edges from the + /// given node. + /// + /// Gives back the next of the undirected edges from the given + /// node. The bool parameter should be used as the \c firstInc() + /// use it. + void nextInc(UEdge&, bool&) const {} + + template + struct Constraints { + + void constraints() { + checkConcept(); + checkConcept, _Graph>(); + typename _Graph::Node node; + typename _Graph::UEdge uedge; + bool dir; + { + graph.first(uedge); + graph.next(uedge); + } + { + graph.firstInc(uedge, dir, node); + graph.nextInc(uedge, dir); + } + } + + const _Graph& graph; + }; + }; + + /// \brief 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 { + template + class IDableGraphComponent : public _Base { public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; - /// Gives back an unique integer id for the Node. - + /// \brief 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;} @@ -303,7 +484,7 @@ /// 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;} + Node nodeFromId(int) const { return INVALID;} /// \brief Gives back an unique integer id for the Edge. /// @@ -316,7 +497,21 @@ /// 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;} + Edge edgeFromId(int) const { return INVALID;} + + /// \brief 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 maxNodeId() const { return -1;} + + /// \brief 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 maxEdgeId() const { return -1;} template struct Constraints { @@ -326,77 +521,98 @@ typename _Graph::Node node; int nid = graph.id(node); nid = graph.id(node); - node = graph.fromId(nid, Node()); + node = graph.nodeFromId(nid); typename _Graph::Edge edge; int eid = graph.id(edge); eid = graph.id(edge); - edge = graph.fromId(eid, Edge()); + edge = graph.edgeFromId(eid); + + nid = graph.maxNodeId(); + ignore_unused_variable_warning(nid); + eid = graph.maxEdgeId(); + ignore_unused_variable_warning(eid); } 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 { + /// \brief An empty idable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core id functions for the undirected graph structure. The + /// most of the base undirected graphs should be conform to this + /// concept. The id's are unique and immutable. + template + class IDableUGraphComponent : public IDableGraphComponent<_Base> { public: - /// Gives back an integer greater or equal to the maximum Node id. + typedef _Base Base; + typedef typename Base::UEdge UEdge; - /// Gives back an integer greater or equal to the maximum Node id. + using IDableGraphComponent<_Base>::id; + + /// \brief Gives back an unique integer id for the UEdge. /// - int maxId(Node = INVALID) const { return -1;} + /// Gives back an unique integer id for the UEdge. + /// + int id(const UEdge&) const { return -1;} - /// Gives back an integer greater or equal to the maximum Edge id. + /// \brief Gives back the undirected edge by the unique id. + /// + /// Gives back the undirected edge by the unique id. If the + /// graph does not contain edge with the given id then the + /// result of the function is undetermined. + UEdge uEdgeFromId(int) const { return INVALID;} - /// Gives back an integer greater or equal to the maximum Edge id. + /// \brief Gives back an integer greater or equal to the maximum + /// UEdge id. /// - int maxId(Edge = INVALID) const { return -1;} + /// Gives back an integer greater or equal to the maximum UEdge + /// id. + int maxUEdgeId() 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); + checkConcept(); + checkConcept, _Graph >(); + typename _Graph::UEdge uedge; + int ueid = graph.id(uedge); + ueid = graph.id(uedge); + uedge = graph.uEdgeFromId(ueid); + ueid = graph.maxUEdgeId(); + ignore_unused_variable_warning(ueid); } - + const _Graph& graph; }; }; - /// An empty extendable base graph class. - + /// \brief 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 { + template + class BaseExtendableGraphComponent : public _Base { public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; + typedef typename _Base::Node Node; + typedef typename _Base::Edge Edge; - /// Adds a new Node to the graph. - - /// Adds a new Node to the graph. + /// \brief 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. + /// \brief Adds a new edge connects the given two nodes. /// + /// Adds a new edge connects the the given two nodes. Edge addEdge(const Node&, const Node&) { return INVALID; } @@ -404,7 +620,6 @@ template struct Constraints { void constraints() { - checkConcept(); typename _Graph::Node node_a, node_b; node_a = graph.addNode(); node_b = graph.addNode(); @@ -416,33 +631,75 @@ }; }; - /// An empty erasable base graph class. - + /// \brief An empty extendable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core undircted graph extend interface for the graph structure. + /// The most of the base graphs should be conform to this concept. + template + class BaseExtendableUGraphComponent : public _Base { + public: + + typedef typename _Base::Node Node; + typedef typename _Base::UEdge UEdge; + + /// \brief Adds a new node to the graph. + /// + /// Adds a new node to the graph. + /// + Node addNode() { + return INVALID; + } + + /// \brief Adds a new edge connects the given two nodes. + /// + /// Adds a new edge connects the the given two nodes. + UEdge addEdge(const Node&, const Node&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + typename _Graph::Node node_a, node_b; + node_a = graph.addNode(); + node_b = graph.addNode(); + typename _Graph::UEdge uedge; + uedge = graph.addUEdge(node_a, node_b); + } + + _Graph& graph; + }; + }; + + /// \brief 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 { + template + class BaseErasableGraphComponent : public _Base { public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; - /// Erase a Node from the graph. - - /// Erase a Node from the graph. This function should not + /// \brief 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. + /// \brief 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; @@ -453,24 +710,61 @@ }; }; - /// An empty clearable base graph class. - + /// \brief An empty erasable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core erase functions for the undirceted graph structure. + template + class BaseErasableUGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::UEdge UEdge; + + /// \brief 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&) {} + + /// \brief Erase an edge from the graph. + /// + /// Erase an edge from the graph. + /// + void erase(const UEdge&) {} + + template + struct Constraints { + void constraints() { + typename _Graph::Node node; + graph.erase(node); + typename _Graph::Edge edge; + graph.erase(edge); + } + + _Graph& graph; + }; + }; + + /// \brief 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 BaseClearableGraphComponent : virtual public BaseGraphComponent { + template + class BaseClearableGraphComponent : public _Base { public: - /// Erase all the Nodes and Edges from the graph. - - /// Erase all the Nodes and Edges from the graph. + /// \brief 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(); } @@ -478,72 +772,90 @@ }; }; + /// \brief An empty clearable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core clear functions for the undirected graph structure. + /// The most of the base graphs should be conform to this concept. + template + class BaseClearableUGraphComponent : public _Base { + public: - /// Skeleton class for graph NodeIt and EdgeIt + /// \brief Erase all the nodes and undirected edges from the graph. + /// + /// Erase all the nodes and undirected edges from the graph. + /// + void clear() {} + template + struct Constraints { + void constraints() { + graph.clear(); + } + + _Graph graph; + }; + }; + + + /// \brief Skeleton class for graph NodeIt and EdgeIt + /// /// Skeleton class for graph NodeIt and EdgeIt. /// template - class GraphIterator : public _Item { + class GraphItemIt : public _Item { public: - /// \todo Don't we need the Item type as typedef? - - /// Default constructor. - + /// \brief Default constructor. + /// /// @warning The default constructor sets the iterator /// to an undefined value. - GraphIterator() {} - /// Copy constructor. - + GraphItemIt() {} + /// \brief Copy constructor. + /// /// Copy constructor. /// - GraphIterator(GraphIterator const&) {} - /// Sets the iterator to the first item. - + GraphItemIt(const GraphItemIt& ) {} + /// \brief 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. - + explicit GraphItemIt(const _Graph&) {} + /// \brief Invalid constructor \& conversion. + /// /// This constructor initializes the item to be invalid. /// \sa Invalid for more details. - GraphIterator(Invalid) {} - /// Assign operator for items. - + GraphItemIt(Invalid) {} + /// \brief Assign operator for items. + /// /// The items are assignable. /// - GraphIterator& operator=(GraphIterator const&) { return *this; } - /// Next item. - + GraphItemIt& operator=(const GraphItemIt&) { return *this; } + /// \brief Next item. + /// /// Assign the iterator to the next item. /// - GraphIterator& operator++() { return *this; } - // Node operator*() const { return INVALID; } - /// Equality operator - + GraphItemIt& operator++() { return *this; } + /// \brief 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 - + bool operator==(const GraphItemIt&) const { return true;} + /// \brief Inequality operator + /// /// \sa operator==(Node n) /// - bool operator!=(const GraphIterator&) const { return true;} + bool operator!=(const GraphItemIt&) const { return true;} - template + 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; + _GraphItemIt it1(g); + _GraphItemIt it2; it2 = ++it1; ++it2 = it1; ++(++it1); - /// \bug This should be: is_base_and_derived + _Item bi = it1; bi = it2; } @@ -551,131 +863,126 @@ }; }; - /// Skeleton class for graph InEdgeIt and OutEdgeIt - + /// \brief 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 { + class GraphIncIt : public _Item { public: - /// Default constructor. - + /// \brief Default constructor. + /// /// @warning The default constructor sets the iterator /// to an undefined value. - GraphIncIterator() {} - /// Copy constructor. - + GraphIncIt() {} + /// \brief Copy constructor. + /// /// Copy constructor. /// - GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {} - /// Sets the iterator to the first edge incoming into or outgoing + GraphIncIt(GraphIncIt const& gi) : _Item(gi) {} + /// \brief 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. - + explicit GraphIncIt(const _Graph&, const _Base&) {} + /// \brief Invalid constructor \& conversion. + /// /// This constructor initializes the item to be invalid. /// \sa Invalid for more details. - GraphIncIterator(Invalid) {} - /// Assign operator for nodes. + GraphIncIt(Invalid) {} + /// \brief Assign operator for iterators. + /// + /// The iterators are assignable. + /// + GraphIncIt& operator=(GraphIncIt const&) { return *this; } + /// \brief Next item. + /// + /// Assign the iterator to the next item. + /// + GraphIncIt& operator++() { return *this; } - /// The nodes are assignable. + /// \brief Equality operator /// - 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;} + bool operator==(const GraphIncIt&) const { return true;} - /// Inequality operator - + /// \brief Inequality operator + /// /// \sa operator==(Node n) /// - bool operator!=(const GraphIncIterator&) const { return true;} + bool operator!=(const GraphIncIt&) const { return true;} - template + 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; + checkConcept, _GraphIncIt>(); + _GraphIncIt it1(graph, node); + _GraphIncIt it2; it2 = ++it1; ++it2 = it1; ++(++it1); - Edge e = it1; + _Item 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; + _Item edge; + _Base node; + _Graph graph; + _GraphIncIt it; }; }; - /// An empty iterable base graph class. - + /// \brief An empty iterable graph class. + /// /// This class provides beside the core graph features /// iterator based iterable interface for the graph structure. /// This concept is part of the GraphConcept. - class IterableGraphComponent : virtual public BaseGraphComponent { + template + class IterableGraphComponent : public _Base { public: + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + typedef IterableGraphComponent Graph; - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - /// This iterator goes through each node. - + /// \brief This iterator goes through each node. + /// /// This iterator goes through each node. /// - typedef GraphIterator NodeIt; - /// This iterator goes through each node. + typedef GraphItemIt NodeIt; + /// \brief 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. + typedef GraphItemIt EdgeIt; + /// \brief 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. + typedef GraphIncIt InEdgeIt; + /// \brief 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; + typedef GraphIncIt OutEdgeIt; /// \brief The base node of the iterator. /// @@ -711,18 +1018,87 @@ template struct Constraints { void constraints() { - checkConcept< BaseGraphComponent, _Graph>(); + checkConcept(); - checkConcept, + checkConcept, typename _Graph::EdgeIt >(); - checkConcept, + checkConcept, typename _Graph::NodeIt >(); - checkConcept, typename _Graph::InEdgeIt>(); - checkConcept, typename _Graph::OutEdgeIt>(); + checkConcept, typename _Graph::InEdgeIt>(); + checkConcept, typename _Graph::OutEdgeIt>(); - typename _Graph::Node n(INVALID); - typename _Graph::Edge e(INVALID); - n = graph.oppositeNode(n, e); + typename _Graph::Node n; + typename _Graph::InEdgeIt ieit(INVALID); + typename _Graph::OutEdgeIt oeit(INVALID); + n = graph.baseNode(ieit); + n = graph.runningNode(ieit); + n = graph.baseNode(oeit); + n = graph.runningNode(oeit); + ignore_unused_variable_warning(n); + } + + const _Graph& graph; + + }; + }; + + /// \brief An empty iterable undirected graph class. + /// + /// This class provides beside the core graph features iterator + /// based iterable interface for the undirected graph structure. + /// This concept is part of the GraphConcept. + template + class IterableUGraphComponent : public IterableGraphComponent<_Base> { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + typedef typename Base::UEdge UEdge; + + + typedef IterableUGraphComponent Graph; + using IterableGraphComponent<_Base>::baseNode; + using IterableGraphComponent<_Base>::runningNode; + + + /// \brief This iterator goes through each node. + /// + /// This iterator goes through each node. + typedef GraphItemIt UEdgeIt; + /// \brief This iterator goes trough the incident edges of a + /// node. + /// + /// This iterator goes trough the incident edges of a certain + /// node of a graph. + typedef GraphIncIt IncEdgeIt; + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + Node baseNode(const IncEdgeIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + Node runningNode(const IncEdgeIt&) const { return INVALID; } + + template + struct Constraints { + void constraints() { + checkConcept(); + checkConcept, _Graph>(); + + checkConcept, + typename _Graph::UEdgeIt >(); + checkConcept, typename _Graph::IncEdgeIt>(); + + typename _Graph::Node n; + typename _Graph::IncEdgeIt ueit(INVALID); + n = graph.baseNode(ueit); + n = graph.runningNode(ueit); } const _Graph& graph; @@ -730,50 +1106,126 @@ }; }; - /// 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 BaseIterableGraphComponent { + /// \brief An empty alteration notifier graph class. + /// + /// This class provides beside the core graph features alteration + /// notifier interface for the graph structure. This implements + /// an observer-notifier pattern for each graph item. More + /// obsevers can be registered into the notifier and whenever an + /// alteration occured in the graph all the observers will + /// notified about it. + template + class AlterableGraphComponent : public _Base { public: + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + + /// The node observer registry. + typedef AlterationNotifier + NodeNotifier; /// The edge observer registry. typedef AlterationNotifier EdgeNotifier; - /// The node observer registry. - typedef AlterationNotifier - NodeNotifier; + + /// \brief Gives back the node alteration notifier. + /// + /// Gives back the node alteration notifier. + NodeNotifier& getNotifier(Node) const { + return NodeNotifier(); + } /// \brief Gives back the edge alteration notifier. /// /// Gives back the edge alteration notifier. - EdgeNotifier getNotifier(Edge) const { + 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(); - } + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _Graph::NodeNotifier& nn + = graph.getNotifier(typename _Graph::Node()); + + typename _Graph::EdgeNotifier& en + = graph.getNotifier(typename _Graph::Edge()); + + ignore_unused_variable_warning(nn); + ignore_unused_variable_warning(en); + } + + const _Graph& graph; + + }; }; + /// \brief An empty alteration notifier undirected graph class. + /// + /// This class provides beside the core graph features alteration + /// notifier interface for the graph structure. This implements + /// an observer-notifier pattern for each graph item. More + /// obsevers can be registered into the notifier and whenever an + /// alteration occured in the graph all the observers will + /// notified about it. + template + class AlterableUGraphComponent : public AlterableGraphComponent<_Base> { + public: - /// Class describing the concept of graph maps + typedef _Base Base; + typedef typename Base::UEdge UEdge; + + /// The edge observer registry. + typedef AlterationNotifier + UEdgeNotifier; + + /// \brief Gives back the edge alteration notifier. + /// + /// Gives back the edge alteration notifier. + UEdgeNotifier& getNotifier(UEdge) const { + return UEdgeNotifier(); + } + + template + struct Constraints { + void constraints() { + checkConcept(); + checkConcept(); + typename _Graph::UEdgeNotifier& uen + = graph.getNotifier(typename _Graph::UEdge()); + ignore_unused_variable_warning(uen); + } + + const _Graph& graph; + + }; + + }; + + + /// \brief Class describing the concept of graph maps + /// /// This class describes the common interface of the graph maps /// (NodeMap, EdgeMap), that is \ref maps-page "maps" which can be used to /// associate data to graph descriptors (nodes or edges). - template - class GraphMap : public ReadWriteMap { - protected: - GraphMap() {} + template + class GraphMap : public ReadWriteMap<_Item, _Value> { public: + + typedef ReadWriteMap<_Item, _Value> Parent; + + /// The graph type of the map. + typedef _Graph Graph; + /// The key type of the map. + typedef _Item Key; + /// The value type of the map. + typedef _Value Value; + /// \brief Construct a new map. /// /// Construct a new map for the graph. @@ -781,29 +1233,39 @@ /// \brief Construct a new map with default value. /// /// Construct a new map for the graph and initalise the values. - GraphMap(const Graph&, const _Value&) {} + GraphMap(const Graph&, const Value&) {} /// \brief Copy constructor. /// /// Copy Constructor. - GraphMap(const GraphMap& gm) :ReadWriteMap(gm) {} + GraphMap(const GraphMap&) : Parent() {} /// \brief Assign operator. /// - /// Assign operator. - GraphMap& operator=(const GraphMap&) { return *this;} + /// Assign operator. It does not mofify the underlying graph, + /// it just iterates on the current item set and set the map + /// with the value returned by the assigned map. + template + GraphMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } template struct Constraints { void constraints() { - checkConcept, _Map >(); + 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 constructor. + _Map b(c); + + ReadMap cmap; + b = cmap; ignore_unused_variable_warning(a2); + ignore_unused_variable_warning(b); } const _Map &c; @@ -813,90 +1275,111 @@ }; - /// An empty mappable base graph class. - + /// \brief An empty mappable graph class. + /// /// This class provides beside the core graph features /// map interface for the graph structure. - /// This concept is part of the GraphConcept. - class MappableGraphComponent : virtual public BaseGraphComponent { + /// This concept is part of the Graph concept. + template + class MappableGraphComponent : public _Base { public: + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + typedef MappableGraphComponent Graph; - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// ReadWrite map of the nodes. - + /// \brief ReadWrite map of the nodes. + /// /// ReadWrite map of the nodes. /// - template - class NodeMap : public GraphMap { + template + class NodeMap : public GraphMap { private: NodeMap(); public: + typedef GraphMap Parent; + /// \brief Construct a new map. /// /// Construct a new map for the graph. /// \todo call the right parent class constructor - explicit NodeMap(const Graph&) {} + explicit NodeMap(const Graph& graph) : Parent(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&) {} + NodeMap(const Graph& graph, const Value& value) + : Parent(graph, value) {} + /// \brief Copy constructor. /// /// Copy Constructor. - NodeMap(const NodeMap& nm) : GraphMap(nm) {} + NodeMap(const NodeMap& nm) : Parent(nm) {} /// \brief Assign operator. /// /// Assign operator. - NodeMap& operator=(const NodeMap&) { return *this;} + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; - /// ReadWrite map of the edges. - + /// \brief ReadWrite map of the edges. + /// /// ReadWrite map of the edges. /// - template - class EdgeMap : public GraphMap { + template + class EdgeMap : public GraphMap { private: EdgeMap(); public: + typedef GraphMap Parent; + /// \brief Construct a new map. /// /// Construct a new map for the graph. /// \todo call the right parent class constructor - explicit EdgeMap(const Graph&) {} + explicit EdgeMap(const Graph& graph) : Parent(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&) {} + EdgeMap(const Graph& graph, const Value& value) + : Parent(graph, value) {} + /// \brief Copy constructor. /// /// Copy Constructor. - EdgeMap(const EdgeMap& em) :GraphMap(em) {} + EdgeMap(const EdgeMap& nm) : Parent(nm) {} /// \brief Assign operator. /// /// Assign operator. - EdgeMap& operator=(const EdgeMap&) { return *this;} + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; + template struct Constraints { - struct Type { + struct Dummy { int value; - Type() : value(0) {} - Type(int _v) : value(_v) {} + Dummy() : value(0) {} + Dummy(int _v) : value(_v) {} }; void constraints() { - checkConcept(); + checkConcept(); { // int map test typedef typename _Graph::template NodeMap IntNodeMap; checkConcept, @@ -905,10 +1388,10 @@ typedef typename _Graph::template NodeMap BoolNodeMap; checkConcept, BoolNodeMap >(); - } { // Type map test - typedef typename _Graph::template NodeMap TypeNodeMap; - checkConcept, - TypeNodeMap >(); + } { // Dummy map test + typedef typename _Graph::template NodeMap DummyNodeMap; + checkConcept, + DummyNodeMap >(); } { // int map test @@ -919,10 +1402,10 @@ typedef typename _Graph::template EdgeMap BoolEdgeMap; checkConcept, BoolEdgeMap >(); - } { // Type map test - typedef typename _Graph::template EdgeMap TypeEdgeMap; - checkConcept, - TypeEdgeMap >(); + } { // Dummy map test + typedef typename _Graph::template EdgeMap DummyEdgeMap; + checkConcept, + DummyEdgeMap >(); } } @@ -930,135 +1413,59 @@ }; }; - -// /// Skeleton class which describes an edge with direction in \ref -// /// UGraph "undirected graph". - template - class UGraphEdge : public UGraph::UEdge { - typedef typename UGraph::UEdge UEdge; - typedef typename UGraph::Node Node; + /// \brief 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 UGraph concept. + template + class MappableUGraphComponent : public MappableGraphComponent<_Base> { public: - /// \e - UGraphEdge() {} + typedef _Base Base; + typedef typename Base::UEdge UEdge; - /// \e - UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {} + typedef MappableUGraphComponent Graph; - /// \e - UGraphEdge(Invalid) {} + /// \brief ReadWrite map of the uedges. + /// + /// ReadWrite map of the uedges. + /// + template + class UEdgeMap : public GraphMap { + public: + typedef GraphMap Parent; - /// \brief Directed edge from undirected edge and a source node. - /// - /// Constructs a directed edge from undirected edge and a source node. - /// - /// \note You have to specify the graph for this constructor. - UGraphEdge(const UGraph &g, - UEdge u_edge, Node n) { - ignore_unused_variable_warning(u_edge); - ignore_unused_variable_warning(g); - ignore_unused_variable_warning(n); - } + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + /// \todo call the right parent class constructor + explicit UEdgeMap(const Graph& graph) : Parent(graph) {} - /// \e - UGraphEdge& operator=(UGraphEdge) { return *this; } + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalise the values. + UEdgeMap(const Graph& graph, const Value& value) + : Parent(graph, value) {} - /// \e - bool operator==(UGraphEdge) const { return true; } - /// \e - bool operator!=(UGraphEdge) const { return false; } + /// \brief Copy constructor. + /// + /// Copy Constructor. + UEdgeMap(const UEdgeMap& nm) : Parent(nm) {} - /// \e - bool operator<(UGraphEdge) const { return false; } + /// \brief Assign operator. + /// + /// Assign operator. + template + UEdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } - template - struct Constraints { - void constraints() { - const_constraints(); - } - void const_constraints() const { - /// \bug This should be is_base_and_derived ... - UEdge ue = e; - ue = e; - - Edge e_with_source(graph,ue,n); - ignore_unused_variable_warning(e_with_source); - } - Edge e; - UEdge ue; - UGraph graph; - Node n; - }; - }; - - - struct BaseIterableUGraphConcept { - - template - struct Constraints { - - typedef typename Graph::UEdge UEdge; - typedef typename Graph::Edge Edge; - typedef typename Graph::Node Node; - - void constraints() { - checkConcept(); - checkConcept, UEdge>(); - //checkConcept, Edge>(); - - graph.first(ue); - graph.next(ue); - - const_constraints(); - } - void const_constraints() { - Node n; - n = graph.target(ue); - n = graph.source(ue); - n = graph.oppositeNode(n0, ue); - - bool b; - b = graph.direction(e); - Edge e = graph.direct(UEdge(), true); - e = graph.direct(UEdge(), n); - - ignore_unused_variable_warning(b); - } - - Graph graph; - Edge e; - Node n0; - UEdge ue; }; - }; - - struct IterableUGraphConcept { - - template - struct Constraints { - void constraints() { - /// \todo we don't need the iterable component to be base iterable - /// Don't we really??? - //checkConcept< BaseIterableUGraphConcept, Graph > (); - - checkConcept (); - - typedef typename Graph::UEdge UEdge; - typedef typename Graph::UEdgeIt UEdgeIt; - typedef typename Graph::IncEdgeIt IncEdgeIt; - - checkConcept, UEdgeIt>(); - checkConcept, IncEdgeIt>(); - } - }; - - }; - - struct MappableUGraphConcept { - - template + template struct Constraints { struct Dummy { @@ -1068,22 +1475,242 @@ }; void constraints() { - checkConcept(); + checkConcept(); + checkConcept, _Graph>(); - typedef typename Graph::template UEdgeMap IntMap; - checkConcept, - IntMap >(); + { // int map test + typedef typename _Graph::template UEdgeMap IntUEdgeMap; + checkConcept, + IntUEdgeMap >(); + } { // bool map test + typedef typename _Graph::template UEdgeMap BoolUEdgeMap; + checkConcept, + BoolUEdgeMap >(); + } { // Dummy map test + typedef typename _Graph::template UEdgeMap DummyUEdgeMap; + checkConcept, + DummyUEdgeMap >(); + } + } - typedef typename Graph::template UEdgeMap BoolMap; - checkConcept, - BoolMap >(); + _Graph& graph; + }; + }; - typedef typename Graph::template UEdgeMap DummyMap; - checkConcept, - DummyMap >(); + + /// \brief An empty extendable graph class. + /// + /// This class provides beside the core graph features graph + /// extendable interface for the graph structure. The main + /// difference between the base and this interface is that the + /// graph alterations should handled already on this level. + template + class ExtendableGraphComponent : public _Base { + public: + + typedef typename _Base::Node Node; + typedef typename _Base::Edge Edge; + + /// \brief Adds a new node to the graph. + /// + /// Adds a new node to the graph. + /// + Node addNode() { + return INVALID; + } + + /// \brief Adds a new edge connects the given two nodes. + /// + /// Adds a new edge connects the the given two nodes. + Edge addEdge(const Node&, const Node&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + typename _Graph::Node node_a, node_b; + node_a = graph.addNode(); + node_b = graph.addNode(); + typename _Graph::Edge edge; + edge = graph.addEdge(node_a, node_b); } + + _Graph& graph; }; + }; + /// \brief An empty extendable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core undircted graph extend interface for the graph structure. + /// The main difference between the base and this interface is + /// that the graph alterations should handled already on this + /// level. + template + class ExtendableUGraphComponent : public _Base { + public: + + typedef typename _Base::Node Node; + typedef typename _Base::UEdge UEdge; + + /// \brief Adds a new node to the graph. + /// + /// Adds a new node to the graph. + /// + Node addNode() { + return INVALID; + } + + /// \brief Adds a new edge connects the given two nodes. + /// + /// Adds a new edge connects the the given two nodes. + UEdge addEdge(const Node&, const Node&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + typename _Graph::Node node_a, node_b; + node_a = graph.addNode(); + node_b = graph.addNode(); + typename _Graph::UEdge uedge; + uedge = graph.addUEdge(node_a, node_b); + } + + _Graph& graph; + }; + }; + + /// \brief An empty erasable graph class. + /// + /// This class provides beside the core graph features core erase + /// functions for the graph structure. The main difference between + /// the base and this interface is that the graph alterations + /// should handled already on this level. + template + class ErasableGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + /// \brief Erase a node from the graph. + /// + /// Erase a node from the graph. This function should + /// erase all edges connecting to the node. + void erase(const Node&) {} + + /// \brief Erase an edge from the graph. + /// + /// Erase an edge from the graph. + /// + void erase(const Edge&) {} + + template + struct Constraints { + void constraints() { + typename _Graph::Node node; + graph.erase(node); + typename _Graph::Edge edge; + graph.erase(edge); + } + + _Graph& graph; + }; + }; + + /// \brief An empty erasable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core erase functions for the undirceted graph structure. The + /// main difference between the base and this interface is that + /// the graph alterations should handled already on this level. + template + class ErasableUGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::UEdge UEdge; + + /// \brief Erase a node from the graph. + /// + /// Erase a node from the graph. This function should erase + /// edges connecting to the node. + void erase(const Node&) {} + + /// \brief Erase an edge from the graph. + /// + /// Erase an edge from the graph. + /// + void erase(const UEdge&) {} + + template + struct Constraints { + void constraints() { + typename _Graph::Node node; + graph.erase(node); + typename _Graph::Edge edge; + graph.erase(edge); + } + + _Graph& graph; + }; + }; + + /// \brief An empty clearable base graph class. + /// + /// This class provides beside the core graph features core clear + /// functions for the graph structure. The main difference between + /// the base and this interface is that the graph alterations + /// should handled already on this level. + template + class ClearableGraphComponent : public _Base { + public: + + /// \brief Erase all nodes and edges from the graph. + /// + /// Erase all nodes and edges from the graph. + /// + void clear() {} + + template + struct Constraints { + void constraints() { + graph.clear(); + } + + _Graph graph; + }; + }; + + /// \brief An empty clearable base undirected graph class. + /// + /// This class provides beside the core undirected graph features + /// core clear functions for the undirected graph structure. The + /// main difference between the base and this interface is that + /// the graph alterations should handled already on this level. + template + class ClearableUGraphComponent : public _Base { + public: + + /// \brief Erase all nodes and undirected edges from the graph. + /// + /// Erase all nodes and undirected edges from the graph. + /// + void clear() {} + + template + struct Constraints { + void constraints() { + graph.clear(); + } + + _Graph graph; + }; }; } diff -r a907fb95f1e0 -r 09a07a851506 lemon/concept/ugraph.h --- a/lemon/concept/ugraph.h Wed Jul 05 16:59:45 2006 +0000 +++ b/lemon/concept/ugraph.h Mon Jul 10 19:04:17 2006 +0000 @@ -489,7 +489,6 @@ /// \sa Reference /// \warning Making maps that can handle bool type (NodeMap) /// needs some extra attention! - /// \todo Wrong documentation template class NodeMap : public ReadWriteMap< Node, T > { @@ -503,8 +502,11 @@ ///Copy constructor NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } ///Assignment operator - NodeMap& operator=(const NodeMap&) { return *this; } - // \todo fix this concept + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; /// \brief Read write map of the directed edges to type \c T. @@ -513,7 +515,6 @@ /// \sa Reference /// \warning Making maps that can handle bool type (EdgeMap) /// needs some extra attention! - /// \todo Wrong documentation template class EdgeMap : public ReadWriteMap { @@ -526,8 +527,11 @@ ///Copy constructor EdgeMap(const EdgeMap& em) : ReadWriteMap(em) { } ///Assignment operator - EdgeMap& operator=(const EdgeMap&) { return *this; } - // \todo fix this concept + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; /// Read write map of the undirected edges to type \c T. @@ -536,7 +540,6 @@ /// \sa Reference /// \warning Making maps that can handle bool type (UEdgeMap) /// needs some extra attention! - /// \todo Wrong documentation template class UEdgeMap : public ReadWriteMap { @@ -549,8 +552,11 @@ ///Copy constructor UEdgeMap(const UEdgeMap& em) : ReadWriteMap(em) {} ///Assignment operator - UEdgeMap &operator=(const UEdgeMap&) { return *this; } - // \todo fix this concept + template + UEdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } }; /// \brief Direct the given undirected edge. @@ -672,9 +678,9 @@ template struct Constraints { void constraints() { - checkConcept(); - checkConcept(); - checkConcept(); + checkConcept, Graph>(); + checkConcept, Graph>(); + checkConcept, Graph>(); } }; diff -r a907fb95f1e0 -r 09a07a851506 test/graph_test.cc --- a/test/graph_test.cc Wed Jul 05 16:59:45 2006 +0000 +++ b/test/graph_test.cc Mon Jul 10 19:04:17 2006 +0000 @@ -38,21 +38,28 @@ { // checking graph components checkConcept(); - checkConcept(); + checkConcept, + BaseIterableGraphComponent<> >(); - checkConcept(); - checkConcept(); + checkConcept, + IDableGraphComponent<> >(); - checkConcept(); + checkConcept, + IterableGraphComponent<> >(); - checkConcept(); + checkConcept, + MappableGraphComponent<> >(); } { // checking skeleton graphs - checkConcept(); + checkConcept(); } { // checking list graph checkConcept(); + checkConcept, ListGraph>(); + checkConcept, ListGraph>(); + checkConcept, ListGraph>(); + checkConcept, ListGraph>(); checkGraph(); checkGraphNodeMap(); diff -r a907fb95f1e0 -r 09a07a851506 test/ugraph_test.cc --- a/test/ugraph_test.cc Wed Jul 05 16:59:45 2006 +0000 +++ b/test/ugraph_test.cc Mon Jul 10 19:04:17 2006 +0000 @@ -32,15 +32,34 @@ using namespace lemon::concept; void check_concepts() { - checkConcept(); - checkConcept(); + { // checking graph components + checkConcept(); - checkConcept(); + checkConcept, + BaseIterableUGraphComponent<> >(); - checkConcept(); + checkConcept, + IDableUGraphComponent<> >(); - checkConcept(); + checkConcept, + IterableUGraphComponent<> >(); + + checkConcept, + MappableUGraphComponent<> >(); + + } + { + checkConcept(); + + checkConcept(); + + checkConcept(); + + checkConcept(); + + checkConcept(); + } } template