# HG changeset patch # User deba # Date 1152632535 0 # Node ID 2c8adbee9fa644379c0941236895585dd41b3d4c # Parent 2f2cbe4e78a811ec55977ff8112399d8b0c2dc12 Renameing file: graph_component.h => graph_components.h diff -r 2f2cbe4e78a8 -r 2c8adbee9fa6 lemon/Makefile.am --- a/lemon/Makefile.am Tue Jul 11 14:42:06 2006 +0000 +++ b/lemon/Makefile.am Tue Jul 11 15:42:15 2006 +0000 @@ -114,7 +114,7 @@ lemon/concept_check.h \ lemon/concept/bpugraph.h \ lemon/concept/graph.h \ - lemon/concept/graph_component.h \ + lemon/concept/graph_components.h \ lemon/concept/heap.h \ lemon/concept/maps.h \ lemon/concept/matrix_maps.h \ diff -r 2f2cbe4e78a8 -r 2c8adbee9fa6 lemon/concept/bpugraph.h --- a/lemon/concept/bpugraph.h Tue Jul 11 14:42:06 2006 +0000 +++ b/lemon/concept/bpugraph.h Tue Jul 11 15:42:15 2006 +0000 @@ -24,7 +24,7 @@ #ifndef LEMON_CONCEPT_BPUGRAPH_H #define LEMON_CONCEPT_BPUGRAPH_H -#include +#include #include #include diff -r 2f2cbe4e78a8 -r 2c8adbee9fa6 lemon/concept/graph.h --- a/lemon/concept/graph.h Tue Jul 11 14:42:06 2006 +0000 +++ b/lemon/concept/graph.h Tue Jul 11 15:42:15 2006 +0000 @@ -27,7 +27,7 @@ #include #include #include -#include +#include namespace lemon { namespace concept { diff -r 2f2cbe4e78a8 -r 2c8adbee9fa6 lemon/concept/graph_component.h --- a/lemon/concept/graph_component.h Tue Jul 11 14:42:06 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1720 +0,0 @@ -/* -*- C++ -*- - * - * This file is a part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2003-2006 - * 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 { - - /// \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. - /// - /// \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: - /// \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() {} - /// \brief Copy constructor. - /// - /// Copy constructor. - /// - GraphItem(const GraphItem &) {} - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the item to be invalid. - /// \sa Invalid for more details. - GraphItem(Invalid) {} - /// \brief Assign operator for nodes. - /// - /// The nodes are assignable. - /// - GraphItem& operator=(GraphItem const&) { return *this; } - /// \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; } - /// \brief Inequality operator. - /// - /// \sa operator==(const Node& n) - /// - bool operator!=(GraphItem) const { return false; } - - /// \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. - 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; - }; - }; - - /// \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. 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; - - /// \brief Node class of the graph. - /// - /// This class represents the Nodes of the graph. - /// - typedef GraphItem<'n'> Node; - - /// \brief Edge class of the graph. - /// - /// This class represents the Edges of the graph. - /// - typedef GraphItem<'e'> 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;} - - /// \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 { - typedef typename _Graph::Node Node; - typedef typename _Graph::Edge Edge; - - void constraints() { - checkConcept, Node>(); - checkConcept, Edge>(); - { - Node n; - Edge e(INVALID); - n = graph.source(e); - n = graph.target(e); - n = graph.oppositeNode(n, e); - } - } - - const _Graph& graph; - }; - }; - - /// \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. - template - class BaseIterableGraphComponent : public _Base { - public: - - typedef _Base Base; - typedef typename Base::Node Node; - typedef typename Base::Edge Edge; - - /// \brief Gives back the first node in the iterating order. - /// - /// Gives back the first node in the iterating order. - /// - void first(Node&) const {} - - /// \brief Gives back the next node in the iterating order. - /// - /// Gives back the next node in the iterating order. - /// - void next(Node&) const {} - - /// \brief Gives back the first edge in the iterating order. - /// - /// Gives back the first edge in the iterating order. - /// - void first(Edge&) const {} - - /// \brief Gives back the next edge in the iterating order. - /// - /// Gives back the next edge in the iterating order. - /// - void next(Edge&) const {} - - - /// \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 {} - - /// \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 {} - - /// \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 {} - - /// \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 {} - - - 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; - }; - }; - - /// \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. - template - class IDableGraphComponent : public _Base { - public: - - typedef _Base Base; - typedef typename Base::Node Node; - typedef typename Base::Edge Edge; - - /// \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;} - - /// \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 nodeFromId(int) 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 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 { - - void constraints() { - checkConcept< BaseGraphComponent, _Graph >(); - typename _Graph::Node node; - int nid = graph.id(node); - nid = graph.id(node); - node = graph.nodeFromId(nid); - typename _Graph::Edge edge; - int eid = graph.id(edge); - eid = graph.id(edge); - edge = graph.edgeFromId(eid); - - nid = graph.maxNodeId(); - ignore_unused_variable_warning(nid); - eid = graph.maxEdgeId(); - ignore_unused_variable_warning(eid); - } - - const _Graph& graph; - }; - }; - - /// \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: - - typedef _Base Base; - typedef typename Base::UEdge UEdge; - - using IDableGraphComponent<_Base>::id; - - /// \brief Gives back an unique integer id for the UEdge. - /// - /// Gives back an unique integer id for the UEdge. - /// - int id(const UEdge&) const { return -1;} - - /// \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;} - - /// \brief Gives back an integer greater or equal to the maximum - /// UEdge id. - /// - /// Gives back an integer greater or equal to the maximum UEdge - /// id. - int maxUEdgeId() const { return -1;} - - template - struct Constraints { - - void constraints() { - 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; - }; - }; - - /// \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. - template - class BaseExtendableGraphComponent : 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 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. - template - class BaseErasableGraphComponent : 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 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 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. - 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. - template - class BaseClearableGraphComponent : public _Base { - public: - - /// \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() { - 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 most of the base graphs should be conform to this concept. - template - class BaseClearableUGraphComponent : public _Base { - public: - - /// \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 GraphItemIt : public _Item { - public: - /// \brief Default constructor. - /// - /// @warning The default constructor sets the iterator - /// to an undefined value. - GraphItemIt() {} - /// \brief Copy constructor. - /// - /// Copy constructor. - /// - GraphItemIt(const GraphItemIt& ) {} - /// \brief Sets the iterator to the first item. - /// - /// Sets the iterator to the first item of \c the graph. - /// - explicit GraphItemIt(const _Graph&) {} - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the item to be invalid. - /// \sa Invalid for more details. - GraphItemIt(Invalid) {} - /// \brief Assign operator for items. - /// - /// The items are assignable. - /// - GraphItemIt& operator=(const GraphItemIt&) { return *this; } - /// \brief Next item. - /// - /// Assign the iterator to the next item. - /// - 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 GraphItemIt&) const { return true;} - /// \brief Inequality operator - /// - /// \sa operator==(Node n) - /// - bool operator!=(const GraphItemIt&) const { return true;} - - template - struct Constraints { - void constraints() { - _GraphItemIt it1(g); - _GraphItemIt it2; - - it2 = ++it1; - ++it2 = it1; - ++(++it1); - - _Item bi = it1; - bi = it2; - } - _Graph& g; - }; - }; - - /// \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'. - template - class GraphIncIt : public _Item { - public: - /// \brief Default constructor. - /// - /// @warning The default constructor sets the iterator - /// to an undefined value. - GraphIncIt() {} - /// \brief Copy constructor. - /// - /// Copy constructor. - /// - 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 GraphIncIt(const _Graph&, const _Base&) {} - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the item to be invalid. - /// \sa Invalid for more details. - 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; } - - /// \brief Equality operator - /// - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(const GraphIncIt&) const { return true;} - - /// \brief Inequality operator - /// - /// \sa operator==(Node n) - /// - bool operator!=(const GraphIncIt&) const { return true;} - - template - struct Constraints { - void constraints() { - checkConcept, _GraphIncIt>(); - _GraphIncIt it1(graph, node); - _GraphIncIt it2; - - it2 = ++it1; - ++it2 = it1; - ++(++it1); - _Item e = it1; - e = it2; - - } - - _Item edge; - _Base node; - _Graph graph; - _GraphIncIt it; - }; - }; - - - /// \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. - template - class IterableGraphComponent : public _Base { - - public: - - typedef _Base Base; - typedef typename Base::Node Node; - typedef typename Base::Edge Edge; - - typedef IterableGraphComponent Graph; - - - /// \brief This iterator goes through each node. - /// - /// This iterator goes through each node. - /// - typedef GraphItemIt NodeIt; - - /// \brief This iterator goes through each node. - /// - /// This iterator goes through each 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 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 GraphIncIt OutEdgeIt; - - /// \brief The base node of the iterator. - /// - /// Gives back the base node of the iterator. - /// It is always the target of the pointed edge. - Node baseNode(const InEdgeIt&) const { return INVALID; } - - /// \brief The running node of the iterator. - /// - /// Gives back the running node of the iterator. - /// It is always the source of the pointed edge. - Node runningNode(const InEdgeIt&) const { return INVALID; } - - /// \brief The base node of the iterator. - /// - /// Gives back the base node of the iterator. - /// It is always the source of the pointed edge. - Node baseNode(const OutEdgeIt&) const { return INVALID; } - - /// \brief The running node of the iterator. - /// - /// Gives back the running node of the iterator. - /// It is always the target of the pointed edge. - Node runningNode(const OutEdgeIt&) const { return INVALID; } - - /// \brief The opposite node on the given edge. - /// - /// Gives back the opposite on the given edge. - /// \todo It should not be here. - Node oppositeNode(const Node&, const Edge&) const { return INVALID; } - - - template - struct Constraints { - void constraints() { - checkConcept(); - - checkConcept, - typename _Graph::EdgeIt >(); - checkConcept, - typename _Graph::NodeIt >(); - checkConcept, typename _Graph::InEdgeIt>(); - checkConcept, typename _Graph::OutEdgeIt>(); - - 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; - - }; - }; - - /// \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; - - /// \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 { - return EdgeNotifier(); - } - - 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: - - 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<_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. - 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&) : Parent() {} - - /// \brief Assign operator. - /// - /// 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 >(); - // Construction with a graph parameter - _Map a(g); - // Constructor with a graph and a default value parameter - _Map a2(g,t); - // Copy constructor. - _Map b(c); - - ReadMap cmap; - b = cmap; - - ignore_unused_variable_warning(a2); - ignore_unused_variable_warning(b); - } - - const _Map &c; - const Graph &g; - const typename GraphMap::Value &t; - }; - - }; - - /// \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 Graph concept. - template - class MappableGraphComponent : public _Base { - public: - - typedef _Base Base; - typedef typename Base::Node Node; - typedef typename Base::Edge Edge; - - typedef MappableGraphComponent Graph; - - /// \brief ReadWrite map of the nodes. - /// - /// ReadWrite map of the nodes. - /// - 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& 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& graph, const Value& value) - : Parent(graph, value) {} - - /// \brief Copy constructor. - /// - /// Copy Constructor. - NodeMap(const NodeMap& nm) : Parent(nm) {} - - /// \brief Assign operator. - /// - /// Assign operator. - template - NodeMap& operator=(const CMap&) { - checkConcept, CMap>(); - return *this; - } - - }; - - /// \brief ReadWrite map of the edges. - /// - /// ReadWrite map of the edges. - /// - 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& 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& graph, const Value& value) - : Parent(graph, value) {} - - /// \brief Copy constructor. - /// - /// Copy Constructor. - EdgeMap(const EdgeMap& nm) : Parent(nm) {} - - /// \brief Assign operator. - /// - /// Assign operator. - template - EdgeMap& operator=(const CMap&) { - checkConcept, CMap>(); - return *this; - } - - }; - - - template - struct Constraints { - - struct Dummy { - int value; - Dummy() : value(0) {} - Dummy(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 >(); - } { // Dummy map test - typedef typename _Graph::template NodeMap DummyNodeMap; - checkConcept, - DummyNodeMap >(); - } - - { // int map test - typedef typename _Graph::template EdgeMap IntEdgeMap; - checkConcept, - IntEdgeMap >(); - } { // bool map test - typedef typename _Graph::template EdgeMap BoolEdgeMap; - checkConcept, - BoolEdgeMap >(); - } { // Dummy map test - typedef typename _Graph::template EdgeMap DummyEdgeMap; - checkConcept, - DummyEdgeMap >(); - } - } - - _Graph& graph; - }; - }; - - /// \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: - - typedef _Base Base; - typedef typename Base::UEdge UEdge; - - typedef MappableUGraphComponent Graph; - - /// \brief ReadWrite map of the uedges. - /// - /// ReadWrite map of the uedges. - /// - template - class UEdgeMap : public GraphMap { - public: - typedef GraphMap Parent; - - /// \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) {} - - /// \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) {} - - /// \brief Copy constructor. - /// - /// Copy Constructor. - UEdgeMap(const UEdgeMap& nm) : Parent(nm) {} - - /// \brief Assign operator. - /// - /// Assign operator. - template - UEdgeMap& operator=(const CMap&) { - checkConcept, CMap>(); - return *this; - } - - }; - - - template - struct Constraints { - - struct Dummy { - int value; - Dummy() : value(0) {} - Dummy(int _v) : value(_v) {} - }; - - void constraints() { - checkConcept(); - checkConcept, _Graph>(); - - { // 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 >(); - } - } - - _Graph& graph; - }; - }; - - - /// \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; - }; - }; - - } - -} - -#endif diff -r 2f2cbe4e78a8 -r 2c8adbee9fa6 lemon/concept/graph_components.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/concept/graph_components.h Tue Jul 11 15:42:15 2006 +0000 @@ -0,0 +1,1720 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * 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 concept of the graph components. + + +#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H +#define LEMON_CONCEPT_GRAPH_COMPONENTS_H + +#include +#include + +#include + +namespace lemon { + namespace concept { + + /// \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. + /// + /// \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: + /// \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() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + GraphItem(const GraphItem &) {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + GraphItem(Invalid) {} + /// \brief Assign operator for nodes. + /// + /// The nodes are assignable. + /// + GraphItem& operator=(GraphItem const&) { return *this; } + /// \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; } + /// \brief Inequality operator. + /// + /// \sa operator==(const Node& n) + /// + bool operator!=(GraphItem) const { return false; } + + /// \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. + 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; + }; + }; + + /// \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. 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; + + /// \brief Node class of the graph. + /// + /// This class represents the Nodes of the graph. + /// + typedef GraphItem<'n'> Node; + + /// \brief Edge class of the graph. + /// + /// This class represents the Edges of the graph. + /// + typedef GraphItem<'e'> 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;} + + /// \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 { + typedef typename _Graph::Node Node; + typedef typename _Graph::Edge Edge; + + void constraints() { + checkConcept, Node>(); + checkConcept, Edge>(); + { + Node n; + Edge e(INVALID); + n = graph.source(e); + n = graph.target(e); + n = graph.oppositeNode(n, e); + } + } + + const _Graph& graph; + }; + }; + + /// \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. + template + class BaseIterableGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + /// \brief Gives back the first node in the iterating order. + /// + /// Gives back the first node in the iterating order. + /// + void first(Node&) const {} + + /// \brief Gives back the next node in the iterating order. + /// + /// Gives back the next node in the iterating order. + /// + void next(Node&) const {} + + /// \brief Gives back the first edge in the iterating order. + /// + /// Gives back the first edge in the iterating order. + /// + void first(Edge&) const {} + + /// \brief Gives back the next edge in the iterating order. + /// + /// Gives back the next edge in the iterating order. + /// + void next(Edge&) const {} + + + /// \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 {} + + /// \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 {} + + /// \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 {} + + /// \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 {} + + + 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; + }; + }; + + /// \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. + template + class IDableGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + /// \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;} + + /// \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 nodeFromId(int) 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 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 { + + void constraints() { + checkConcept< BaseGraphComponent, _Graph >(); + typename _Graph::Node node; + int nid = graph.id(node); + nid = graph.id(node); + node = graph.nodeFromId(nid); + typename _Graph::Edge edge; + int eid = graph.id(edge); + eid = graph.id(edge); + edge = graph.edgeFromId(eid); + + nid = graph.maxNodeId(); + ignore_unused_variable_warning(nid); + eid = graph.maxEdgeId(); + ignore_unused_variable_warning(eid); + } + + const _Graph& graph; + }; + }; + + /// \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: + + typedef _Base Base; + typedef typename Base::UEdge UEdge; + + using IDableGraphComponent<_Base>::id; + + /// \brief Gives back an unique integer id for the UEdge. + /// + /// Gives back an unique integer id for the UEdge. + /// + int id(const UEdge&) const { return -1;} + + /// \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;} + + /// \brief Gives back an integer greater or equal to the maximum + /// UEdge id. + /// + /// Gives back an integer greater or equal to the maximum UEdge + /// id. + int maxUEdgeId() const { return -1;} + + template + struct Constraints { + + void constraints() { + 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; + }; + }; + + /// \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. + template + class BaseExtendableGraphComponent : 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 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. + template + class BaseErasableGraphComponent : 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 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 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. + 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. + template + class BaseClearableGraphComponent : public _Base { + public: + + /// \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() { + 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 most of the base graphs should be conform to this concept. + template + class BaseClearableUGraphComponent : public _Base { + public: + + /// \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 GraphItemIt : public _Item { + public: + /// \brief Default constructor. + /// + /// @warning The default constructor sets the iterator + /// to an undefined value. + GraphItemIt() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + GraphItemIt(const GraphItemIt& ) {} + /// \brief Sets the iterator to the first item. + /// + /// Sets the iterator to the first item of \c the graph. + /// + explicit GraphItemIt(const _Graph&) {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + GraphItemIt(Invalid) {} + /// \brief Assign operator for items. + /// + /// The items are assignable. + /// + GraphItemIt& operator=(const GraphItemIt&) { return *this; } + /// \brief Next item. + /// + /// Assign the iterator to the next item. + /// + 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 GraphItemIt&) const { return true;} + /// \brief Inequality operator + /// + /// \sa operator==(Node n) + /// + bool operator!=(const GraphItemIt&) const { return true;} + + template + struct Constraints { + void constraints() { + _GraphItemIt it1(g); + _GraphItemIt it2; + + it2 = ++it1; + ++it2 = it1; + ++(++it1); + + _Item bi = it1; + bi = it2; + } + _Graph& g; + }; + }; + + /// \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'. + template + class GraphIncIt : public _Item { + public: + /// \brief Default constructor. + /// + /// @warning The default constructor sets the iterator + /// to an undefined value. + GraphIncIt() {} + /// \brief Copy constructor. + /// + /// Copy constructor. + /// + 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 GraphIncIt(const _Graph&, const _Base&) {} + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the item to be invalid. + /// \sa Invalid for more details. + 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; } + + /// \brief Equality operator + /// + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(const GraphIncIt&) const { return true;} + + /// \brief Inequality operator + /// + /// \sa operator==(Node n) + /// + bool operator!=(const GraphIncIt&) const { return true;} + + template + struct Constraints { + void constraints() { + checkConcept, _GraphIncIt>(); + _GraphIncIt it1(graph, node); + _GraphIncIt it2; + + it2 = ++it1; + ++it2 = it1; + ++(++it1); + _Item e = it1; + e = it2; + + } + + _Item edge; + _Base node; + _Graph graph; + _GraphIncIt it; + }; + }; + + + /// \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. + template + class IterableGraphComponent : public _Base { + + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + typedef IterableGraphComponent Graph; + + + /// \brief This iterator goes through each node. + /// + /// This iterator goes through each node. + /// + typedef GraphItemIt NodeIt; + + /// \brief This iterator goes through each node. + /// + /// This iterator goes through each 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 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 GraphIncIt OutEdgeIt; + + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + /// It is always the target of the pointed edge. + Node baseNode(const InEdgeIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + /// It is always the source of the pointed edge. + Node runningNode(const InEdgeIt&) const { return INVALID; } + + /// \brief The base node of the iterator. + /// + /// Gives back the base node of the iterator. + /// It is always the source of the pointed edge. + Node baseNode(const OutEdgeIt&) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Gives back the running node of the iterator. + /// It is always the target of the pointed edge. + Node runningNode(const OutEdgeIt&) const { return INVALID; } + + /// \brief The opposite node on the given edge. + /// + /// Gives back the opposite on the given edge. + /// \todo It should not be here. + Node oppositeNode(const Node&, const Edge&) const { return INVALID; } + + + template + struct Constraints { + void constraints() { + checkConcept(); + + checkConcept, + typename _Graph::EdgeIt >(); + checkConcept, + typename _Graph::NodeIt >(); + checkConcept, typename _Graph::InEdgeIt>(); + checkConcept, typename _Graph::OutEdgeIt>(); + + 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; + + }; + }; + + /// \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; + + /// \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 { + return EdgeNotifier(); + } + + 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: + + 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<_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. + 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&) : Parent() {} + + /// \brief Assign operator. + /// + /// 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 >(); + // Construction with a graph parameter + _Map a(g); + // Constructor with a graph and a default value parameter + _Map a2(g,t); + // Copy constructor. + _Map b(c); + + ReadMap cmap; + b = cmap; + + ignore_unused_variable_warning(a2); + ignore_unused_variable_warning(b); + } + + const _Map &c; + const Graph &g; + const typename GraphMap::Value &t; + }; + + }; + + /// \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 Graph concept. + template + class MappableGraphComponent : public _Base { + public: + + typedef _Base Base; + typedef typename Base::Node Node; + typedef typename Base::Edge Edge; + + typedef MappableGraphComponent Graph; + + /// \brief ReadWrite map of the nodes. + /// + /// ReadWrite map of the nodes. + /// + 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& 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& graph, const Value& value) + : Parent(graph, value) {} + + /// \brief Copy constructor. + /// + /// Copy Constructor. + NodeMap(const NodeMap& nm) : Parent(nm) {} + + /// \brief Assign operator. + /// + /// Assign operator. + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + /// \brief ReadWrite map of the edges. + /// + /// ReadWrite map of the edges. + /// + 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& 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& graph, const Value& value) + : Parent(graph, value) {} + + /// \brief Copy constructor. + /// + /// Copy Constructor. + EdgeMap(const EdgeMap& nm) : Parent(nm) {} + + /// \brief Assign operator. + /// + /// Assign operator. + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + + template + struct Constraints { + + struct Dummy { + int value; + Dummy() : value(0) {} + Dummy(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 >(); + } { // Dummy map test + typedef typename _Graph::template NodeMap DummyNodeMap; + checkConcept, + DummyNodeMap >(); + } + + { // int map test + typedef typename _Graph::template EdgeMap IntEdgeMap; + checkConcept, + IntEdgeMap >(); + } { // bool map test + typedef typename _Graph::template EdgeMap BoolEdgeMap; + checkConcept, + BoolEdgeMap >(); + } { // Dummy map test + typedef typename _Graph::template EdgeMap DummyEdgeMap; + checkConcept, + DummyEdgeMap >(); + } + } + + _Graph& graph; + }; + }; + + /// \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: + + typedef _Base Base; + typedef typename Base::UEdge UEdge; + + typedef MappableUGraphComponent Graph; + + /// \brief ReadWrite map of the uedges. + /// + /// ReadWrite map of the uedges. + /// + template + class UEdgeMap : public GraphMap { + public: + typedef GraphMap Parent; + + /// \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) {} + + /// \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) {} + + /// \brief Copy constructor. + /// + /// Copy Constructor. + UEdgeMap(const UEdgeMap& nm) : Parent(nm) {} + + /// \brief Assign operator. + /// + /// Assign operator. + template + UEdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + + template + struct Constraints { + + struct Dummy { + int value; + Dummy() : value(0) {} + Dummy(int _v) : value(_v) {} + }; + + void constraints() { + checkConcept(); + checkConcept, _Graph>(); + + { // 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 >(); + } + } + + _Graph& graph; + }; + }; + + + /// \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; + }; + }; + + } + +} + +#endif diff -r 2f2cbe4e78a8 -r 2c8adbee9fa6 lemon/concept/ugraph.h --- a/lemon/concept/ugraph.h Tue Jul 11 14:42:06 2006 +0000 +++ b/lemon/concept/ugraph.h Tue Jul 11 15:42:15 2006 +0000 @@ -24,7 +24,7 @@ #ifndef LEMON_CONCEPT_UGRAPH_H #define LEMON_CONCEPT_UGRAPH_H -#include +#include #include #include