# HG changeset patch # User klao # Date 1099599899 0 # Node ID c80ef591290308dfac499a89c3d815f6bb50afc8 # Parent 75f7496822405f39f0ae98b20d2a049866124659 skeleton(s) -> concept renaming diff -r 75f749682240 -r c80ef5912903 doc/Doxyfile --- a/doc/Doxyfile Thu Nov 04 18:52:31 2004 +0000 +++ b/doc/Doxyfile Thu Nov 04 20:24:59 2004 +0000 @@ -431,7 +431,7 @@ groups.dox \ namespaces.dox \ ../src/lemon \ - ../src/lemon/skeletons \ + ../src/lemon/concept \ ../src/test/test_tools.h # If the value of the INPUT tag contains directories, you can use the diff -r 75f749682240 -r c80ef5912903 doc/graphs.dox --- a/doc/graphs.dox Thu Nov 04 18:52:31 2004 +0000 +++ b/doc/graphs.dox Thu Nov 04 20:24:59 2004 +0000 @@ -9,31 +9,31 @@ Each graph should meet the -\ref lemon::skeleton::StaticGraph "StaticGraph" concept. +\ref lemon::concept::StaticGraph "StaticGraph" concept. This concept does not makes it possible to change the graph (i.e. it is not possible to add or delete edges or nodes). Most of the graph algorithms will run on these graphs. The graphs meeting the -\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" +\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept allow node and edge addition. You can also "clear" (i.e. erase all edges and nodes) such a graph. In case of graphs meeting the full feature -\ref lemon::skeleton::ErasableGraph "ErasableGraph" +\ref lemon::concept::ErasableGraph "ErasableGraph" concept you can also erase individual edges and node in arbitrary order. The implemented graph structures are the following. \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets -the \ref lemon::skeleton::ErasableGraph "ErasableGraph" concept +the \ref lemon::concept::ErasableGraph "ErasableGraph" concept and it also have some convenience features. \li \ref lemon::SmartGraph "SmartGraph" is a more memory efficient version of \ref lemon::ListGraph "ListGraph". The price of it is that it only meets the -\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept, +\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept, so you cannot delete individual edges or nodes. \li \ref lemon::SymListGraph "SymListGraph" and \ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to @@ -45,7 +45,7 @@ attach data to the edges in such a way that the stored data are shared by the edge pairs. \li \ref lemon::FullGraph "FullGraph" -implements a full graph. It is a \ref lemon::skeleton::StaticGraph, so you cannot +implements a full graph. It is a \ref lemon::concept::StaticGraph, so you cannot change the number of nodes once it is constructed. It is extremely memory efficient: it uses constant amount of memory independently from the number of the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and diff -r 75f749682240 -r c80ef5912903 doc/groups.dox --- a/doc/groups.dox Thu Nov 04 18:52:31 2004 +0000 +++ b/doc/groups.dox Thu Nov 04 20:24:59 2004 +0000 @@ -80,12 +80,13 @@ */ /** -@defgroup skeletons Skeletons -\brief Skeletons (a.k.a. concept checking classes) +@defgroup concept Concept +\brief Skeleton classes and concept checking classes -This group describes the data/algorithm skeletons implemented in LEMON in -order to make it easier to check if a certain template class or -template function is correctly implemented. +This group describes the data/algorithm skeletons and concept checking +classes implemented in LEMON. These classes exist in order to make it +easier to check if a certain template class or template function is +correctly implemented. */ diff -r 75f749682240 -r c80ef5912903 doc/namespaces.dox --- a/doc/namespaces.dox Thu Nov 04 18:52:31 2004 +0000 +++ b/doc/namespaces.dox Thu Nov 04 20:24:59 2004 +0000 @@ -8,5 +8,5 @@ /// \todo Some more detailed description would be nice here. /// - namespace skeleton {} + namespace concept {} } diff -r 75f749682240 -r c80ef5912903 src/lemon/Makefile.am --- a/src/lemon/Makefile.am Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/Makefile.am Thu Nov 04 20:24:59 2004 +0000 @@ -36,8 +36,8 @@ erasable_graph_extender.h noinst_HEADERS = \ - skeletons/graph.h \ - skeletons/graph_component.h \ - skeletons/sym_graph.h \ - skeletons/maps.h \ - skeletons/path.h + concept/graph.h \ + concept/graph_component.h \ + concept/sym_graph.h \ + concept/maps.h \ + concept/path.h diff -r 75f749682240 -r c80ef5912903 src/lemon/concept/graph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/concept/graph.h Thu Nov 04 20:24:59 2004 +0000 @@ -0,0 +1,918 @@ +/* -*- C++ -*- + * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, 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. + * + */ + +#ifndef LEMON_CONCEPT_GRAPH_H +#define LEMON_CONCEPT_GRAPH_H + +///\ingroup concept +///\file +///\brief Declaration of Graph. + +#include +#include +#include +#include + +namespace lemon { + namespace concept { + + /// \addtogroup concept + /// @{ + +// /// An empty static graph class. + +// /// This class provides all the common features of a graph structure, +// /// however completely without implementations and real data structures +// /// behind the interface. +// /// All graph algorithms should compile with this class, but it will not +// /// run properly, of course. +// /// +// /// It can be used for checking the interface compatibility, +// /// or it can serve as a skeleton of a new graph structure. +// /// +// /// Also, you will find here the full documentation of a certain graph +// /// feature, the documentation of a real graph imlementation +// /// like @ref ListGraph or +// /// @ref SmartGraph will just refer to this structure. +// /// +// /// \todo A pages describing the concept of concept description would +// /// be nice. +// class StaticGraph +// { +// public: +// /// Defalult constructor. + +// /// Defalult constructor. +// /// +// StaticGraph() { } +// ///Copy consructor. + +// // ///\todo It is not clear, what we expect from a copy constructor. +// // ///E.g. How to assign the nodes/edges to each other? What about maps? +// // StaticGraph(const StaticGraph& g) { } + +// /// The base type of node iterators, +// /// or in other words, the trivial node iterator. + +// /// This is the base type of each node iterator, +// /// thus each kind of node iterator converts to this. +// /// More precisely each kind of node iterator should be inherited +// /// from the trivial node iterator. +// class Node { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// Node() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// Node(const Node&) { } + +// /// Invalid constructor \& conversion. + +// /// This constructor initializes the iterator to be invalid. +// /// \sa Invalid for more details. +// Node(Invalid) { } +// /// Equality operator + +// /// Two iterators are equal if and only if they point to the +// /// same object or both are invalid. +// bool operator==(Node) const { return true; } + +// /// Inequality operator + +// /// \sa operator==(Node n) +// /// +// bool operator!=(Node) const { return true; } + +// ///Comparison operator. + +// ///This is a strict ordering between the nodes. +// /// +// ///This ordering can be different from the order in which NodeIt +// ///goes through the nodes. +// ///\todo Possibly we don't need it. +// bool operator<(Node) const { return true; } +// }; + +// /// This iterator goes through each node. + +// /// This iterator goes through each node. +// /// Its usage is quite simple, for example you can count the number +// /// of nodes in graph \c g of type \c Graph like this: +// /// \code +// /// int count=0; +// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; +// /// \endcode +// class NodeIt : public Node { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// NodeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// NodeIt(const NodeIt&) { } +// /// Invalid constructor \& conversion. + +// /// Initialize the iterator to be invalid. +// /// \sa Invalid for more details. +// NodeIt(Invalid) { } +// /// Sets the iterator to the first node. + +// /// Sets the iterator to the first node of \c g. +// /// +// NodeIt(const StaticGraph& g) { } +// /// Node -> NodeIt conversion. + +// /// Sets the iterator to the node of \c g pointed by the trivial +// /// iterator n. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// NodeIt(const StaticGraph& g, const Node& n) { } +// /// Next node. + +// /// Assign the iterator to the next node. +// /// +// NodeIt& operator++() { return *this; } +// }; + + +// /// The base type of the edge iterators. + +// /// The base type of the edge iterators. +// /// +// class Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// Edge() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// Edge(const Edge&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// Edge(Invalid) { } +// /// Equality operator + +// /// Two iterators are equal if and only if they point to the +// /// same object or both are invalid. +// bool operator==(Edge) const { return true; } +// /// Inequality operator + +// /// \sa operator==(Node n) +// /// +// bool operator!=(Edge) const { return true; } +// ///Comparison operator. + +// ///This is a strict ordering between the nodes. +// /// +// ///This ordering can be different from the order in which NodeIt +// ///goes through the nodes. +// ///\todo Possibly we don't need it. +// bool operator<(Edge) const { return true; } +// }; + +// /// 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. +// /// Its usage is quite simple, for example you can count the number +// /// of outgoing edges of a node \c n +// /// in graph \c g of type \c Graph as follows. +// /// \code +// /// int count=0; +// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; +// /// \endcode + +// class OutEdgeIt : public Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// OutEdgeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// OutEdgeIt(const OutEdgeIt&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// OutEdgeIt(Invalid) { } +// /// This constructor sets the iterator to first outgoing edge. + +// /// This constructor set the iterator to the first outgoing edge of +// /// node +// ///@param n the node +// ///@param g the graph +// OutEdgeIt(const StaticGraph& g, const Node& n) { } +// /// Edge -> OutEdgeIt conversion + +// /// Sets the iterator to the value of the trivial iterator \c e. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// OutEdgeIt(const StaticGraph& g, const Edge& e) { } +// ///Next outgoing edge + +// /// Assign the iterator to the next +// /// outgoing edge of the corresponding node. +// OutEdgeIt& operator++() { return *this; } +// }; + +// /// This iterator goes trough the incoming edges of a node. + +// /// This iterator goes trough the \e incoming edges of a certain node +// /// of a graph. +// /// Its usage is quite simple, for example you can count the number +// /// of outgoing edges of a node \c n +// /// in graph \c g of type \c Graph as follows. +// /// \code +// /// int count=0; +// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; +// /// \endcode + +// class InEdgeIt : public Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// InEdgeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// InEdgeIt(const InEdgeIt&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// InEdgeIt(Invalid) { } +// /// This constructor sets the iterator to first incoming edge. + +// /// This constructor set the iterator to the first incoming edge of +// /// node +// ///@param n the node +// ///@param g the graph +// InEdgeIt(const StaticGraph& g, const Node& n) { } +// /// Edge -> InEdgeIt conversion + +// /// Sets the iterator to the value of the trivial iterator \c e. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// InEdgeIt(const StaticGraph& g, const Edge& n) { } +// /// Next incoming edge + +// /// Assign the iterator to the next inedge of the corresponding node. +// /// +// InEdgeIt& operator++() { return *this; } +// }; +// /// This iterator goes through each edge. + +// /// This iterator goes through each edge of a graph. +// /// Its usage is quite simple, for example you can count the number +// /// of edges in a graph \c g of type \c Graph as follows: +// /// \code +// /// int count=0; +// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; +// /// \endcode +// class EdgeIt : public Edge { +// public: +// /// Default constructor + +// /// @warning The default constructor sets the iterator +// /// to an undefined value. +// EdgeIt() { } +// /// Copy constructor. + +// /// Copy constructor. +// /// +// EdgeIt(const EdgeIt&) { } +// /// Initialize the iterator to be invalid. + +// /// Initialize the iterator to be invalid. +// /// +// EdgeIt(Invalid) { } +// /// This constructor sets the iterator to first edge. + +// /// This constructor set the iterator to the first edge of +// /// node +// ///@param g the graph +// EdgeIt(const StaticGraph& g) { } +// /// Edge -> EdgeIt conversion + +// /// Sets the iterator to the value of the trivial iterator \c e. +// /// This feature necessitates that each time we +// /// iterate the edge-set, the iteration order is the same. +// EdgeIt(const StaticGraph&, const Edge&) { } +// ///Next edge + +// /// Assign the iterator to the next +// /// edge of the corresponding node. +// EdgeIt& operator++() { return *this; } +// }; + +// /// First node of the graph. + +// /// \retval i the first node. +// /// \return the first node. +// /// +// NodeIt& first(NodeIt& i) const { return i; } + +// /// The first incoming edge. + +// /// The first incoming edge. +// /// +// InEdgeIt& first(InEdgeIt &i, Node) const { return i; } +// /// The first outgoing edge. + +// /// The first outgoing edge. +// /// +// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } +// /// The first edge of the Graph. + +// /// The first edge of the Graph. +// /// +// EdgeIt& first(EdgeIt& i) const { return i; } + +// ///Gives back the head node of an edge. + +// ///Gives back the head node of an edge. +// /// +// Node head(Edge) const { return INVALID; } +// ///Gives back the tail node of an edge. + +// ///Gives back the tail node of an edge. +// /// +// Node tail(Edge) const { return INVALID; } + +// ///Gives back the \e id of a node. + +// ///\warning Not all graph structures provide this feature. +// /// +// ///\todo Should each graph provide \c id? +// int id(const Node&) const { return 0; } +// ///Gives back the \e id of an edge. + +// ///\warning Not all graph structures provide this feature. +// /// +// ///\todo Should each graph provide \c id? +// int id(const Edge&) const { return 0; } + +// ///\e + +// ///\todo Should it be in the concept? +// /// +// int nodeNum() const { return 0; } +// ///\e + +// ///\todo Should it be in the concept? +// /// +// int edgeNum() const { return 0; } + + +// ///Reference map of the nodes to type \c T. + +// /// \ingroup concept +// ///Reference map of the nodes to type \c T. +// /// \sa Reference +// /// \warning Making maps that can handle bool type (NodeMap) +// /// needs some extra attention! +// template class NodeMap : public ReferenceMap< Node, T > +// { +// public: + +// ///\e +// NodeMap(const StaticGraph&) { } +// ///\e +// NodeMap(const StaticGraph&, T) { } + +// ///Copy constructor +// template NodeMap(const NodeMap&) { } +// ///Assignment operator +// template NodeMap& operator=(const NodeMap&) +// { return *this; } +// }; + +// ///Reference map of the edges to type \c T. + +// /// \ingroup concept +// ///Reference map of the edges to type \c T. +// /// \sa Reference +// /// \warning Making maps that can handle bool type (EdgeMap) +// /// needs some extra attention! +// template class EdgeMap +// : public ReferenceMap +// { +// public: + +// ///\e +// EdgeMap(const StaticGraph&) { } +// ///\e +// EdgeMap(const StaticGraph&, T) { } + +// ///Copy constructor +// template EdgeMap(const EdgeMap&) { } +// ///Assignment operator +// template EdgeMap &operator=(const EdgeMap&) +// { return *this; } +// }; +// }; + +// struct DummyType { +// int value; +// DummyType() {} +// DummyType(int p) : value(p) {} +// DummyType& operator=(int p) { value = p; return *this;} +// }; + +// ///\brief Checks whether \c G meets the +// ///\ref lemon::concept::StaticGraph "StaticGraph" concept +// template void checkCompileStaticGraph(Graph &G) +// { +// typedef typename Graph::Node Node; +// typedef typename Graph::NodeIt NodeIt; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::EdgeIt EdgeIt; +// typedef typename Graph::InEdgeIt InEdgeIt; +// typedef typename Graph::OutEdgeIt OutEdgeIt; + +// { +// Node i; Node j(i); Node k(INVALID); +// i=j; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// b=(i==j); b=(i!=j); b=(iNodeIt conversion +// NodeIt ni(G,n); +// } +// { +// Edge i; Edge j(i); Edge k(INVALID); +// i=j; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// b=(i==j); b=(i!=j); b=(iEdgeIt conversion +// EdgeIt ei(G,e); +// } +// { +// Node n; +// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); +// i=j; +// j=G.first(i,n); +// j=++i; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// Edge e(i); +// e=i; +// b=(i==j); b=(i!=j); b=(iInEdgeIt conversion +// InEdgeIt ei(G,e); +// } +// { +// Node n; +// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); +// i=j; +// j=G.first(i,n); +// j=++i; +// bool b; b=true; +// b=(i==INVALID); b=(i!=INVALID); +// Edge e(i); +// e=i; +// b=(i==j); b=(i!=j); b=(iOutEdgeIt conversion +// OutEdgeIt ei(G,e); +// } +// { +// Node n,m; +// n=m=INVALID; +// Edge e; +// e=INVALID; +// n=G.tail(e); +// n=G.head(e); +// } +// // id tests +// { Node n; int i=G.id(n); i=i; } +// { Edge e; int i=G.id(e); i=i; } +// //NodeMap tests +// { +// Node k; +// typename Graph::template NodeMap m(G); +// //Const map +// typename Graph::template NodeMap const &cm = m; +// //Inicialize with default value +// typename Graph::template NodeMap mdef(G,12); +// //Copy +// typename Graph::template NodeMap mm(cm); +// //Copy from another type +// typename Graph::template NodeMap dm(cm); +// //Copy to more complex type +// typename Graph::template NodeMap em(cm); +// int v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// em=cm; //Copy to more complex type +// { +// //Check the typedef's +// typename Graph::template NodeMap::ValueType val; +// val=1; +// typename Graph::template NodeMap::KeyType key; +// key = typename Graph::NodeIt(G); +// } +// } +// { //bool NodeMap +// Node k; +// typename Graph::template NodeMap m(G); +// typename Graph::template NodeMap const &cm = m; //Const map +// //Inicialize with default value +// typename Graph::template NodeMap mdef(G,12); +// typename Graph::template NodeMap mm(cm); //Copy +// typename Graph::template NodeMap dm(cm); //Copy from another type +// bool v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// m=dm; //Copy to another type + +// { +// //Check the typedef's +// typename Graph::template NodeMap::ValueType val; +// val=true; +// typename Graph::template NodeMap::KeyType key; +// key= typename Graph::NodeIt(G); +// } +// } +// //EdgeMap tests +// { +// Edge k; +// typename Graph::template EdgeMap m(G); +// typename Graph::template EdgeMap const &cm = m; //Const map +// //Inicialize with default value +// typename Graph::template EdgeMap mdef(G,12); +// typename Graph::template EdgeMap mm(cm); //Copy +// typename Graph::template EdgeMap dm(cm);//Copy from another type +// int v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// { +// //Check the typedef's +// typename Graph::template EdgeMap::ValueType val; +// val=1; +// typename Graph::template EdgeMap::KeyType key; +// key= typename Graph::EdgeIt(G); +// } +// } +// { //bool EdgeMap +// Edge k; +// typename Graph::template EdgeMap m(G); +// typename Graph::template EdgeMap const &cm = m; //Const map +// //Inicialize with default value +// typename Graph::template EdgeMap mdef(G,12); +// typename Graph::template EdgeMap mm(cm); //Copy +// typename Graph::template EdgeMap dm(cm); //Copy from another type +// bool v; +// v=m[k]; m[k]=v; m.set(k,v); +// v=cm[k]; + +// m=cm; +// dm=cm; //Copy from another type +// m=dm; //Copy to another type +// { +// //Check the typedef's +// typename Graph::template EdgeMap::ValueType val; +// val=true; +// typename Graph::template EdgeMap::KeyType key; +// key= typename Graph::EdgeIt(G); +// } +// } +// } + +// /// An empty non-static graph class. + +// /// This class provides everything that \ref StaticGraph +// /// with additional functionality which enables to build a +// /// graph from scratch. +// class ExtendableGraph : public StaticGraph +// { +// public: +// /// Defalult constructor. + +// /// Defalult constructor. +// /// +// ExtendableGraph() { } +// ///Add a new node to the graph. + +// /// \return the new node. +// /// +// Node addNode() { return INVALID; } +// ///Add a new edge to the graph. + +// ///Add a new edge to the graph with tail node \c t +// ///and head node \c h. +// ///\return the new edge. +// Edge addEdge(Node h, Node t) { return INVALID; } + +// /// Resets the graph. + +// /// This function deletes all edges and nodes of the graph. +// /// It also frees the memory allocated to store them. +// /// \todo It might belong to \ref ErasableGraph. +// void clear() { } +// }; + + +// ///\brief Checks whether \c G meets the +// ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept +// template void checkCompileExtendableGraph(Graph &G) +// { +// checkCompileStaticGraph(G); + +// typedef typename Graph::Node Node; +// typedef typename Graph::NodeIt NodeIt; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::EdgeIt EdgeIt; +// typedef typename Graph::InEdgeIt InEdgeIt; +// typedef typename Graph::OutEdgeIt OutEdgeIt; + +// Node n,m; +// n=G.addNode(); +// m=G.addNode(); +// Edge e; +// e=G.addEdge(n,m); + +// // G.clear(); +// } + + +// /// An empty erasable graph class. + +// /// This class is an extension of \ref ExtendableGraph. It also makes it +// /// possible to erase edges or nodes. +// class ErasableGraph : public ExtendableGraph +// { +// public: +// /// Defalult constructor. + +// /// Defalult constructor. +// /// +// ErasableGraph() { } +// /// Deletes a node. + +// /// Deletes node \c n node. +// /// +// void erase(Node n) { } +// /// Deletes an edge. + +// /// Deletes edge \c e edge. +// /// +// void erase(Edge e) { } +// }; + +// template void checkCompileGraphEraseEdge(Graph &G) +// { +// typename Graph::Edge e; +// G.erase(e); +// } + +// template void checkCompileGraphEraseNode(Graph &G) +// { +// typename Graph::Node n; +// G.erase(n); +// } + +// ///\brief Checks whether \c G meets the +// ///\ref lemon::concept::EresableGraph "EresableGraph" concept +// template void checkCompileErasableGraph(Graph &G) +// { +// checkCompileExtendableGraph(G); +// checkCompileGraphEraseNode(G); +// checkCompileGraphEraseEdge(G); +// } + +// ///Checks whether a graph has findEdge() member function. + +// ///\todo findEdge() might be a global function. +// /// +// template void checkCompileGraphFindEdge(Graph &G) +// { +// typedef typename Graph::NodeIt Node; +// typedef typename Graph::NodeIt NodeIt; + +// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); +// G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); +// } + + + + /************* New GraphBase stuff **************/ + + + /// \bug The nodes and edges are not allowed to inherit from the + /// same baseclass. + + class BaseGraphItem { + public: + BaseGraphItem() {} + BaseGraphItem(Invalid) {} + + // We explicitely list these: + BaseGraphItem(BaseGraphItem const&) {} + BaseGraphItem& operator=(BaseGraphItem const&) { return *this; } + + bool operator==(BaseGraphItem) const { return false; } + bool operator!=(BaseGraphItem) const { return false; } + + // Technical requirement. Do we really need this? + bool operator<(BaseGraphItem) const { return false; } + }; + + + /// A minimal GraphBase concept + + /// This class describes a minimal concept which can be extended to a + /// full-featured graph with \ref GraphFactory. + class GraphBase { + public: + + GraphBase() {} + + + /// \bug Nodes and Edges are comparable each other + + class Node : public BaseGraphItem {}; + class Edge : public BaseGraphItem {}; + + // Graph operation + void firstNode(Node &n) const { } + void firstEdge(Edge &e) const { } + + void firstOutEdge(Edge &e, Node) const { } + void firstInEdge(Edge &e, Node) const { } + + void nextNode(Node &n) const { } + void nextEdge(Edge &e) const { } + + + // Question: isn't it reasonable if this methods have a Node + // parameter? Like this: + // Edge& nextOut(Edge &e, Node) const { return e; } + void nextOutEdge(Edge &e) const { } + void nextInEdge(Edge &e) const { } + + Node head(Edge) const { return Node(); } + Node tail(Edge) const { return Node(); } + + + // Do we need id, nodeNum, edgeNum and co. in this basic graphbase + // concept? + + + // Maps. + // + // We need a special slimer concept which does not provide maps (it + // wouldn't be strictly slimer, cause for map-factory id() & friends + // a required...) + + template + class NodeMap : public GraphMap {}; + + template + class EdgeMap : public GraphMap {}; + }; + + + + /**************** Concept checking classes ****************/ + + template + struct BaseGraphItemConcept { + void constraints() { + BGI i1; + BGI i2 = i1; + BGI i3 = INVALID; + + i1 = i3; + if( i1 == i3 ) { + if ( i2 != i3 && i3 < i2 ) + return; + } + } + }; + + + + class StaticGraph + : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { + public: + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + }; + + template + struct StaticGraphConcept { + void constraints() { + function_requires >(); + function_requires >(); + function_requires >(); + } + Graph& graph; + }; + + class ExtendableGraph + : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { + public: + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + }; + + template + struct ExtendableGraphConcept { + void constraints() { + function_requires >(); + function_requires >(); + function_requires >(); + } + Graph& graph; + }; + + class ErasableGraph + : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent { + public: + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + }; + + template + struct ErasableGraphConcept { + void constraints() { + function_requires >(); + function_requires >(); + } + Graph& graph; + }; + + // @} + } //namespace concept +} //namespace lemon + + + +#endif // LEMON_CONCEPT_GRAPH_H diff -r 75f749682240 -r c80ef5912903 src/lemon/concept/graph_component.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/concept/graph_component.h Thu Nov 04 20:24:59 2004 +0000 @@ -0,0 +1,827 @@ +/* -*- C++ -*- + * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, 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 concept +///\file +///\brief The graph components. + + +#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H +#define LEMON_CONCEPT_GRAPH_COMPONENT_H + +#include +#include + +namespace lemon { + namespace concept { + + /// An empty base graph class. + + /// This class provides the most minimal features of a graph structure. + /// All the graph concepts have to be conform to this base graph. + + class BaseGraphComponent { + public: + + typedef BaseGraphComponent Graph; + + /// Node class of the graph. + + /// This class represents the Nodes of the graph. + /// + class Node { + public: + + /// Default constructor. + + /// @warning The default constructor sets the iterator + /// to an undefined value. + + Node() {} + /// Copy constructor. + + /// Copy constructor. + /// + Node(const Node&) {} + + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + Node(Invalid) {} + + + Node& operator=(const Node&) { return *this;} + + /// Equality operator. + + /// Two iterators are equal if and only if they represents the + /// same node in the graph or both are invalid. + bool operator==(const Node&) { return true;} + + + /// Inequality operator. + + /// \sa operator==(const Node& n) + /// + bool operator!=(const Node&) { return true;} + + /// Comparison operator. + + /// This is a strict ordering between the nodes. + /// + /// This ordering can be different from the iterating order of nodes. + /// \todo Possibly we don't need it. + bool operator<(const Node&) { return true;} + }; + + /// Edge class of the graph. + + /// This class represents the Edges of the graph. + /// + class Edge { + public: + + /// Default constructor. + + /// @warning The default constructor sets the iterator + /// to an undefined value. + + Edge() {} + /// Copy constructor. + + /// Copy constructor. + /// + Edge(const Edge&) {} + + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + Edge(Invalid) {} + + + Edge& operator=(const Edge&) { return *this;} + + /// Equality operator. + + /// Two iterators are equal if and only if they represents the + /// same edge in the graph or both are invalid. + bool operator==(const Edge&) { return true;} + + + /// Inequality operator. + + /// \sa operator==(const Edge& n) + /// + bool operator!=(const Edge&) { return true;} + + /// Comparison operator. + + /// This is a strict ordering between the edges. + /// + /// This ordering can be different from the iterating order of edges. + /// \todo Possibly we don't need it. + bool operator<(const Edge&) { return true;} + }; + + ///Gives back the head node of an edge. + + ///Gives back the head node of an edge. + /// + Node head(const Edge&) const { return INVALID;} + + ///Gives back the tail node of an edge. + + ///Gives back the tail node of an edge. + /// + Node tail(const Edge&) const { return INVALID;} + }; + + /// Concept check structure for BaseGraph. + + /// Concept check structure for BaseGraph. + /// + + template + struct BaseGraphComponentConcept { + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + + void constraints() { + { + Node ni; + Node nj(ni); + Node nk(INVALID); + ni = nj; + bool b; b = true; + b = (ni == INVALID); b = (ni != INVALID); + b = (ni==nj); b = (ni != nj); b=( ni < nj); + } + { + Edge ei; + Edge ej(ei); + Edge ek(INVALID); + ei = ej; + bool b; b = true; + b = (ei == INVALID); b = (ei != INVALID); + b = (ei==ej); b = (ei != ej); b=( ei < ej); + } + { + const Graph& const_graph = graph; + Node n; + Edge e; + n = const_graph.tail(e); + n = const_graph.head(e); + } + } + + Graph& graph; + }; + + /// An empty iterable base graph class. + + /// This class provides beside the core graph features + /// core iterable interface for the graph structure. + /// Most of the base graphs should be conform to this concept. + + class BaseIterableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Gives back the first Node in the iterating order. + + /// Gives back the first Node in the iterating order. + /// + void first(Node&) const {} + + /// Gives back the next Node in the iterating order. + + /// Gives back the next Node in the iterating order. + /// + void next(Node&) const {} + + /// Gives back the first Edge in the iterating order. + + /// Gives back the first Edge in the iterating order. + /// + void first(Edge&) const {} + /// Gives back the next Edge in the iterating order. + + /// Gives back the next Edge in the iterating order. + /// + void next(Edge&) const {} + + + /// Gives back the first of the Edges point to the given Node. + + /// Gives back the first of the Edges point to the given Node. + /// + void firstIn(Edge&, const Node&) const {} + + /// Gives back the next of the Edges points to the given Node. + + + /// Gives back the next of the Edges points to the given Node. + /// + void nextIn(Edge&) const {} + + /// Gives back the first of the Edges start from the given Node. + + /// Gives back the first of the Edges start from the given Node. + /// + void firstOut(Edge&, const Node&) const {} + + /// Gives back the next of the Edges start from the given Node. + + /// Gives back the next of the Edges start from the given Node. + /// + void nextOut(Edge&) const {} + }; + + + /// Concept check structure for IterableBaseGraph. + + /// Concept check structure for IterableBaseGraph. + /// + template + struct BaseIterableGraphComponentConcept { + + void constraints() { + const Graph& const_graph = graph; + typename Graph::Node node; + typename Graph::Edge edge; + { + const_graph.first(node); + const_graph.next(node); + } + { + const_graph.first(edge); + const_graph.next(edge); + } + { + const_graph.firstIn(edge, node); + const_graph.nextIn(edge); + } + { + const_graph.firstOut(edge, node); + const_graph.nextOut(edge); + } + } + + Graph& graph; + }; + + /// An empty idable base graph class. + + /// This class provides beside the core graph features + /// core id functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + /// The id's are unique and immutable. + + class IDableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Gives back an unique integer id for the Node. + + /// Gives back an unique integer id for the Node. + /// + int id(const Node&) const { return -1;} + + /// 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;} + }; + + + /// Concept check structure for IdableBaseGraph. + + /// Concept check structure for IdableBaseGraph. + /// + template + struct IDableGraphComponentConcept { + + void constraints() { + const Graph& const_graph = graph; + typename Graph::Node node; + int nid = const_graph.id(node); + nid = const_graph.id(node); + typename Graph::Edge edge; + int eid = const_graph.id(edge); + eid = const_graph.id(edge); + } + + Graph& graph; + }; + + + /// An empty max-idable base graph class. + + /// This class provides beside the core graph features + /// core max id functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + /// The id's are unique and immutable. + class MaxIDableGraphComponent : virtual public BaseGraphComponent { + public: + + /// Gives back an integer greater or equal to the maximum Node id. + + /// Gives back an integer greater or equal to the maximum Node id. + /// + int maxEdgeId() const { return -1;} + + /// Gives back an integer greater or equal to the maximum Edge id. + + /// Gives back an integer greater or equal to the maximum Edge id. + /// + int maxNodeId() const { return -1;} + }; + + /// Concept check structure for MaxIdableBaseGraph. + + /// Concept check structure for MaxIdableBaseGraph. + /// + template + struct MaxIDableGraphComponentConcept { + + void constraints() { + const Graph& const_graph = graph; + int nid = const_graph.maxEdgeId(); + ignore_unused_variable_warning(nid); + int eid = const_graph.maxNodeId(); + ignore_unused_variable_warning(eid); + } + + Graph& graph; + }; + + /// An empty extendable base graph class. + + /// This class provides beside the core graph features + /// core graph extend interface for the graph structure. + /// The most of the base graphs should be conform to this concept. + class BaseExtendableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Adds a new Node to the graph. + + /// Adds a new Node to the graph. + /// + Node addNode() { + return INVALID; + } + + /// Adds a new Edge connects the two Nodes to the graph. + + /// Adds a new Edge connects the two Nodes to the graph. + /// + Edge addEdge(const Node& from, const Node& to) { + return INVALID; + } + + }; + + /// Concept check structure for ExtendableBaseGraph. + + /// Concept check structure for ExtendableBaseGraph. + /// + template + struct BaseExtendableGraphComponentConcept { + void constraints() { + typename Graph::Node node_a, node_b; + node_a = graph.addNode(); + typename Graph::Edge edge; + edge = graph.addEdge(node_a, node_b); + } + + Graph& graph; + }; + + /// An empty erasable base graph class. + + /// This class provides beside the core graph features + /// core erase functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + class BaseErasableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + /// Erase a Node from the graph. + + /// Erase a Node from the graph. This function should not + /// erase edges connecting to the Node. + void erase(const Node&) {} + + /// Erase an Edge from the graph. + + /// Erase an Edge from the graph. + /// + void erase(const Edge&) {} + + }; + + /// Concept check structure for ErasableBaseGraph. + + /// Concept check structure for ErasableBaseGraph. + /// + template + struct BaseErasableGraphComponentConcept { + void constraints() { + typename Graph::Node node; + graph.erase(node); + typename Graph::Edge edge; + graph.erase(edge); + } + + Graph& graph; + }; + + /// An empty clearable base graph class. + + /// This class provides beside the core graph features + /// core clear functions for the graph structure. + /// The most of the base graphs should be conform to this concept. + class BaseClearableGraphComponent : virtual public BaseGraphComponent { + public: + + /// Erase all the Nodes and Edges from the graph. + + /// Erase all the Nodes and Edges from the graph. + /// + void clear() {} + }; + + /// Concept check function for ErasableBaseGraph. + + /// Concept check function for ErasableBaseGraph. + /// + template + struct BaseClearableGraphComponentConcept { + void constraints() { + graph.clear(); + } + + Graph& graph; + }; + + + class IterableGraphComponent : virtual public BaseGraphComponent { + + public: + + typedef IterableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + class NodeIt : public Node { + public: + NodeIt() {} + NodeIt(Invalid) {} + NodeIt(const Graph&) {} + + NodeIt& operator++() { return *this; } + // Node operator*() const { return INVALID; } + + bool operator==(const NodeIt&) { return true;} + bool operator!=(const NodeIt&) { return true;} + }; + + class EdgeIt : public Edge { + public: + EdgeIt() {} + EdgeIt(Invalid) {} + EdgeIt(const Graph&) {} + + EdgeIt& operator++() { return *this; } + // Edge operator*() const { return INVALID; } + + bool operator==(const EdgeIt&) { return true;} + bool operator!=(const EdgeIt&) { return true;} + }; + + class InEdgeIt : public Edge { + public: + InEdgeIt() {} + InEdgeIt(Invalid) {} + InEdgeIt(const Graph&, const Node&) {} + + InEdgeIt& operator++() { return *this; } + // Edge operator*() const { return INVALID; } + + bool operator==(const InEdgeIt&) { return true;} + bool operator!=(const InEdgeIt&) { return true;} + }; + + class OutEdgeIt : public Edge { + public: + OutEdgeIt() {} + OutEdgeIt(Invalid) {} + OutEdgeIt(const Graph&, const Node&) {} + + OutEdgeIt& operator++() { return *this; } + // Edge operator*() const { return INVALID; } + + bool operator==(const OutEdgeIt&) { return true;} + bool operator!=(const OutEdgeIt&) { return true;} + }; + + }; + + template + struct IterableGraphComponentConcept { + + void constraints() { + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::InEdgeIt InEdgeIt; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + { + NodeIt it; + NodeIt jt(it); + NodeIt kt(INVALID); + NodeIt lt(graph); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Node node = it; + node = it; + } + { + EdgeIt it; + EdgeIt jt(it); + EdgeIt kt(INVALID); + EdgeIt lt(graph); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Edge edge = it; + edge = it; + } + { + InEdgeIt it; + InEdgeIt jt(it); + InEdgeIt kt(INVALID); + Node node; + InEdgeIt lt(graph, node); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Edge edge = it; + edge = it; + } + { + OutEdgeIt it; + OutEdgeIt jt(it); + OutEdgeIt kt(INVALID); + Node node; + OutEdgeIt lt(graph, node); + it = jt; + jt = ++it; + bool b; + b = (it == INVALID); + b = (it != INVALID); + b = (it == jt); + b = (it != jt); + Edge edge = it; + edge = it; + } + } + Graph& graph; + }; + + + class IdMappableGraphComponent : virtual public BaseGraphComponent { + + typedef IdMappableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + public: + + class NodeIdMap : public ReadMap { + public: + NodeIdMap(const Graph&) {} + int maxId() const { return -1;} + }; + + class EdgeIdMap : public ReadMap { + public: + EdgeIdMap(const Graph&) {} + int maxId() const { return -1;} + }; + + }; + + template + struct IdMappableGraphComponentConcept { + void constraints() { + { + typedef typename Graph::EdgeIdMap EdgeIdMap; + function_requires >(); + EdgeIdMap edge_map(graph); + int n = edge_map.maxId(); + ignore_unused_variable_warning(n); + } + { + typedef typename Graph::NodeIdMap NodeIdMap; + function_requires >(); + NodeIdMap node_map(graph); + int n = node_map.maxId(); + ignore_unused_variable_warning(n); + } + } + Graph& graph; + }; + + + class MappableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef MappableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + template + class NodeMap : public ReferenceMap { + public: + NodeMap(const Graph&) {} + NodeMap(const Graph&, const Value&) {} + NodeMap(const NodeMap&) {} + + NodeMap& operator=(const NodeMap&) { return *this;} + + }; + + template + class EdgeMap : public ReferenceMap { + public: + EdgeMap(const Graph&) {} + EdgeMap(const Graph&, const Value&) {} + EdgeMap(const EdgeMap&) {} + + EdgeMap& operator=(const EdgeMap&) { return *this;} + + }; + + }; + + template + struct MappableGraphComponentConcept { + + struct Type { + int value; + Type() : value(0) {} + Type(int _v) : value(_v) {} + }; + + void constraints() { + { // int map test + typedef typename Graph::template NodeMap IntNodeMap; + function_requires >(); + } { // bool map test + typedef typename Graph::template NodeMap BoolNodeMap; + function_requires >(); + } { // Type map test + typedef typename Graph::template NodeMap TypeNodeMap; + function_requires >(); + } + + { // int map test + typedef typename Graph::template EdgeMap IntEdgeMap; + function_requires >(); + } { // bool map test + typedef typename Graph::template EdgeMap BoolEdgeMap; + function_requires >(); + } { // Type map test + typedef typename Graph::template EdgeMap TypeEdgeMap; + function_requires >(); + } + } + + Graph& graph; + }; + + + class ExtendableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef ExtendableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + Node addNode() { + return INVALID; + } + + Edge addEdge(const Node& from, const Node& to) { + return INVALID; + } + + }; + + template + struct ExtendableGraphComponentConcept { + void constraints() { + typename Graph::Node node_a, node_b; + node_a = graph.addNode(); + typename Graph::Edge edge; + edge = graph.addEdge(node_a, node_b); + } + Graph& graph; + }; + + class ErasableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef ErasableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + void erase(const Node&) {} + void erase(const Edge&) {} + + }; + + template + struct ErasableGraphComponentConcept { + void constraints() { + typename Graph::Node node; + graph.erase(node); + typename Graph::Edge edge; + graph.erase(edge); + } + + Graph& graph; + }; + + class ClearableGraphComponent : virtual public BaseGraphComponent { + public: + + typedef ClearableGraphComponent Graph; + + typedef BaseGraphComponent::Node Node; + typedef BaseGraphComponent::Edge Edge; + + void clear() {} + + }; + + template + struct ClearableGraphComponentConcept { + void constraints() { + graph.clear(); + } + Graph& graph; + }; + + } + +} + +#endif diff -r 75f749682240 -r c80ef5912903 src/lemon/concept/maps.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/concept/maps.h Thu Nov 04 20:24:59 2004 +0000 @@ -0,0 +1,246 @@ +/* -*- C++ -*- + * src/lemon/concept/maps.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, 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. + * + */ + +#ifndef LEMON_CONCEPT_MAPS_H +#define LEMON_CONCEPT_MAPS_H + +#include + +///\ingroup concept +///\file +///\brief Map concepts checking classes for testing and documenting. + +namespace lemon { + + namespace concept { + + /// \addtogroup concept + /// @{ + + /// Readable map concept + template + class ReadMap + { + public: + /// Map's key type. + typedef K KeyType; + /// Map's value type. (The type of objects associated with the keys). + typedef T ValueType; + + /// Returns the value associated with a key. + ValueType operator[](const KeyType &k) const {return ValueType();} + + ///Default constructor + ReadMap() {} + }; + + + /// Writable map concept + template + class WriteMap + { + public: + /// Map's key type. + typedef K KeyType; + /// Map's value type. (The type of objects associated with the keys). + typedef T ValueType; + + /// Sets the value associated with a key. + void set(const KeyType &k,const ValueType &t) {} + + ///Default constructor + WriteMap() {} + }; + + ///Read/Writable map concept + template + class ReadWriteMap : public ReadMap, + public WriteMap + { + public: + /// Map's key type. + typedef K KeyType; + /// Map's value type. (The type of objects associated with the keys). + typedef T ValueType; + + /// Returns the value associated with a key. + ValueType operator[](const KeyType &k) const {return ValueType();} + /// Sets the value associated with a key. + void set(const KeyType &k,const ValueType &t) {} + + ///Default constructor + ReadWriteMap() {} + }; + + + ///Dereferable map concept + template + class ReferenceMap : public ReadWriteMap + { + public: + /// Map's key type. + typedef K KeyType; + /// Map's value type. (The type of objects associated with the keys). + typedef T ValueType; + + protected: + ValueType tmp; + public: + typedef ValueType& ReferenceType; + /// Map's const reference type. + typedef const ValueType& ConstReferenceType; + + ///Returns a reference to the value associated to a key. + ReferenceType operator[](const KeyType &i) { return tmp; } + ///Returns a const reference to the value associated to a key. + ConstReferenceType operator[](const KeyType &i) const + { return tmp; } + /// Sets the value associated with a key. + void set(const KeyType &k,const ValueType &t) { operator[](k)=t; } + + ///Default constructor + ReferenceMap() {} + }; + + + template + class GraphMap : public ReadWriteMap { + // I really, really don't like the idea that every graph should have + // reference maps! --klao + + private: + // We state explicitly that graph maps have no default constructor? + GraphMap(); + + public: + explicit GraphMap(Graph const&) {} + // value for initializing + GraphMap(Graph const&, T) {} + + // this probably should be required: + GraphMap(GraphMap const&) {} + GraphMap& operator=(GraphMap const&) { return *this; } + + // but this is a absolute no-op! We should provide a more generic + // graph-map-copy operation. + // + // template + // GraphMap(GraphMap const&); + // + // template + // GraphMap& operator=(const GraphMap&); + }; + + + /**************** Concept-checking classes ****************/ + + template + struct ReadMapConcept { + typedef typename ReadMap::KeyType KeyType; + typedef typename ReadMap::ValueType ValueType; + + void constraints() { + // No constraints for constructor. + + // What are the requirement for the ValueType? + // CopyConstructible? Assignable? None of these? + ValueType v = m[k]; + v = m[k]; + + // FIXME: + ignore_unused_variable_warning(v); + } + + ReadMap m; + KeyType k; + }; + + template + struct WriteMapConcept { + typedef typename WriteMap::KeyType KeyType; + typedef typename WriteMap::ValueType ValueType; + + void constraints() { + // No constraints for constructor. + + m.set(k, v); + } + + WriteMap m; + KeyType k; + ValueType v; + }; + + template + struct ReadWriteMapConcept { + void constraints() { + function_requires< ReadMapConcept >(); + function_requires< WriteMapConcept >(); + } + }; + + template + struct ReferenceMapConcept { + typedef typename ReferenceMap::KeyType KeyType; + typedef typename ReferenceMap::ValueType ValueType; + typedef typename ReferenceMap::ReferenceType ReferenceType; + + // What for is this? + typedef typename ReferenceMap::ConstReferenceType ConstReferenceType; + + void constraints() { + function_requires< ReadWriteMapConcept >(); + + m[k] = v; + // Or should we require real reference? + // Like this: + // ValueType &vv = m[k]; + // ignore_unused_variable_warning(vv); + } + + ReferenceMap m; + KeyType k; + ValueType v; + }; + + /// \todo GraphMapConceptCheck + + template + struct GraphMapConcept { + void constraints() { + function_requires< ReadWriteMapConcept >(); + // Construction with a graph parameter + GraphMap a(g); + // Ctor with a graph and a default value parameter + GraphMap a2(g,t); + // Copy ctor. Do we need it? + GraphMap b=c; + // Copy operator. Do we need it? + a=b; + + ignore_unused_variable_warning(a2); + } + const GraphMap &c; + const Graph &g; + const typename GraphMap::ValueType &t; + }; + + + // @} + + } //namespace concept +} //namespace lemon +#endif // LEMON_CONCEPT_MAPS_H diff -r 75f749682240 -r c80ef5912903 src/lemon/concept/path.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/concept/path.h Thu Nov 04 20:24:59 2004 +0000 @@ -0,0 +1,236 @@ +/* -*- C++ -*- + * src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, 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 concept +///\file +///\brief Classes for representing paths in graphs. + +#ifndef LEMON_CONCEPT_PATH_H +#define LEMON_CONCEPT_PATH_H + +#include + +namespace lemon { + namespace concept { + /// \addtogroup concept + /// @{ + + + //! \brief A skeletom structure for representing directed paths in a graph. + //! + //! A skeleton structure for representing directed paths in a graph. + //! \param GR The graph type in which the path is. + //! + //! In a sense, the path can be treated as a graph, for is has \c NodeIt + //! and \c EdgeIt with the same usage. These types converts to the \c Node + //! and \c Edge of the original graph. + template + class Path { + public: + + /// Type of the underlying graph. + typedef /*typename*/ GR Graph; + /// Edge type of the underlying graph. + typedef typename Graph::Edge GraphEdge; + /// Node type of the underlying graph. + typedef typename Graph::Node GraphNode; + class NodeIt; + class EdgeIt; + + /// \param _G The graph in which the path is. + /// + Path(const Graph &_G) {} + + /// Length of the path. + size_t length() const {return 0;} + /// Returns whether the path is empty. + bool empty() const { return true;} + + /// Resets the path to an empty path. + void clear() {} + + /// \brief Starting point of the path. + /// + /// Starting point of the path. + /// Returns INVALID if the path is empty. + GraphNode/*It*/ head() const {return INVALID;} + /// \brief End point of the path. + /// + /// End point of the path. + /// Returns INVALID if the path is empty. + GraphNode/*It*/ tail() const {return INVALID;} + + /// \brief First NodeIt/EdgeIt. + /// + /// Initializes node or edge iterator to point to the first + /// node or edge. + template + It& first(It &i) const { return i=It(*this); } + + /// \brief The head of an edge. + /// + /// Returns node iterator pointing to the head node of the + /// given edge iterator. + NodeIt head(const EdgeIt& e) const {return INVALID;} + + /// \brief The tail of an edge. + /// + /// Returns node iterator pointing to the tail node of the + /// given edge iterator. + NodeIt tail(const EdgeIt& e) const {return INVALID;} + + + /* Iterator classes */ + + /** + * \brief Iterator class to iterate on the edges of the paths + * + * \ingroup concept + * This class is used to iterate on the edges of the paths + * + * Of course it converts to Graph::Edge + * + */ + class EdgeIt { + public: + /// Default constructor + EdgeIt() {} + /// Invalid constructor + EdgeIt(Invalid) {} + /// Constructor with starting point + EdgeIt(const Path &_p) {} + + operator GraphEdge () const {} + + /// Next edge + EdgeIt& operator++() {return *this;} + + /// Comparison operator + bool operator==(const EdgeIt& e) const {return true;} + /// Comparison operator + bool operator!=(const EdgeIt& e) const {return true;} +// /// Comparison operator +// /// \todo It is not clear what is the "natural" ordering. +// bool operator<(const EdgeIt& e) const {} + + }; + + /** + * \brief Iterator class to iterate on the nodes of the paths + * + * \ingroup concept + * This class is used to iterate on the nodes of the paths + * + * Of course it converts to Graph::Node. + * + */ + class NodeIt { + public: + /// Default constructor + NodeIt() {} + /// Invalid constructor + NodeIt(Invalid) {} + /// Constructor with starting point + NodeIt(const Path &_p) {} + + ///Conversion to Graph::Node + operator const GraphNode& () const {} + /// Next node + NodeIt& operator++() {return *this;} + + /// Comparison operator + bool operator==(const NodeIt& e) const {return true;} + /// Comparison operator + bool operator!=(const NodeIt& e) const {return true;} +// /// Comparison operator +// /// \todo It is not clear what is the "natural" ordering. +// bool operator<(const NodeIt& e) const {} + + }; + + friend class Builder; + + /** + * \brief Class to build paths + * + * \ingroup concept + * This class is used to fill a path with edges. + * + * You can push new edges to the front and to the back of the path in + * arbitrary order then you should commit these changes to the graph. + * + * While the builder is active (after the first modifying + * operation and until the call of \ref commit()) + * the underlining Path is in a + * "transitional" state (operations on it have undefined result). + */ + class Builder { + public: + + Path &P; + + ///\param _P the path you want to fill in. + /// + Builder(Path &_P) : P(_P) {} + + /// Sets the starting node of the path. + + /// Sets the starting node of the path. Edge added to the path + /// afterwards have to be incident to this node. + /// You \em must start building an empry path with this functions. + /// (And you \em must \em not use it later). + /// \sa pushFront() + /// \sa pushBack() + void setStartNode(const GraphNode &) {} + + ///Push a new edge to the front of the path + + ///Push a new edge to the front of the path. + ///If the path is empty, you \em must call \ref setStartNode() before + ///the first use of \ref pushFront(). + void pushFront(const GraphEdge& e) {} + + ///Push a new edge to the back of the path + + ///Push a new edge to the back of the path. + ///If the path is empty, you \em must call \ref setStartNode() before + ///the first use of \ref pushBack(). + void pushBack(const GraphEdge& e) {} + + ///Commit the changes to the path. + void commit() {} + + ///Reserve (front) storage for the builder in advance. + + ///If you know an reasonable upper bound of the number of the edges + ///to add to the front of the path, + ///using this function you may speed up the building. + void reserveFront(size_t r) {} + ///Reserve (back) storage for the builder in advance. + + ///If you know an reasonable upper bound of the number of the edges + ///to add to the back of the path, + ///using this function you may speed up the building. + void reserveBack(size_t r) {} + }; + }; + + ///@} + } + +} // namespace lemon + +#endif // LEMON_CONCEPT_PATH_H diff -r 75f749682240 -r c80ef5912903 src/lemon/concept/sym_graph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/concept/sym_graph.h Thu Nov 04 20:24:59 2004 +0000 @@ -0,0 +1,653 @@ +/* -*- C++ -*- + * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, 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. + * + */ + +#ifndef LEMON_CONCEPT_SYM_GRAPH_H +#define LEMON_CONCEPT_SYM_GRAPH_H + +///\ingroup concept +///\file +///\brief Declaration of SymGraph. + +#include +#include +#include + +namespace lemon { + namespace concept { + + /// \addtogroup concept + /// @{ + + /// An empty static graph class. + + /// This class provides all the common features of a symmetric + /// graph structure, however completely without implementations and + /// real data structures behind the interface. + /// All graph algorithms should compile with this class, but it will not + /// run properly, of course. + /// + /// It can be used for checking the interface compatibility, + /// or it can serve as a skeleton of a new symmetric graph structure. + /// + /// Also, you will find here the full documentation of a certain graph + /// feature, the documentation of a real symmetric graph imlementation + /// like @ref SymListGraph or + /// @ref lemon::SymSmartGraph will just refer to this structure. + class StaticSymGraph + { + public: + /// Defalult constructor. + + /// Defalult constructor. + /// + StaticSymGraph() { } + ///Copy consructor. + +// ///\todo It is not clear, what we expect from a copy constructor. +// ///E.g. How to assign the nodes/edges to each other? What about maps? +// StaticGraph(const StaticGraph& g) { } + + /// The base type of node iterators, + /// or in other words, the trivial node iterator. + + /// This is the base type of each node iterator, + /// thus each kind of node iterator converts to this. + /// More precisely each kind of node iterator should be inherited + /// from the trivial node iterator. + class Node { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Node() { } + /// Copy constructor. + + /// Copy constructor. + /// + Node(const Node&) { } + + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + Node(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(Node) const { return true; } + + /// Inequality operator + + /// \sa operator==(Node n) + /// + bool operator!=(Node) const { return true; } + + ///Comparison operator. + + ///This is a strict ordering between the nodes. + /// + ///This ordering can be different from the order in which NodeIt + ///goes through the nodes. + ///\todo Possibly we don't need it. + bool operator<(Node) const { return true; } + }; + + /// This iterator goes through each node. + + /// This iterator goes through each node. + /// Its usage is quite simple, for example you can count the number + /// of nodes in graph \c g of type \c Graph like this: + /// \code + /// int count=0; + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; + /// \endcode + class NodeIt : public Node { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + NodeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + NodeIt(const NodeIt&) { } + /// Invalid constructor \& conversion. + + /// Initialize the iterator to be invalid. + /// \sa Invalid for more details. + NodeIt(Invalid) { } + /// Sets the iterator to the first node. + + /// Sets the iterator to the first node of \c g. + /// + NodeIt(const StaticSymGraph& g) { } + /// Node -> NodeIt conversion. + + /// Sets the iterator to the node of \c g pointed by the trivial + /// iterator n. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + NodeIt(const StaticSymGraph& g, const Node& n) { } + /// Next node. + + /// Assign the iterator to the next node. + /// + NodeIt& operator++() { return *this; } + }; + + + /// The base type of the symmetric edge iterators. + + /// The base type of the symmetric edge iterators. + /// + class SymEdge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + SymEdge() { } + /// Copy constructor. + + /// Copy constructor. + /// + SymEdge(const SymEdge&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + SymEdge(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(SymEdge) const { return true; } + /// Inequality operator + + /// \sa operator==(Node n) + /// + bool operator!=(SymEdge) const { return true; } + ///Comparison operator. + + ///This is a strict ordering between the nodes. + /// + ///This ordering can be different from the order in which NodeIt + ///goes through the nodes. + ///\todo Possibly we don't need it. + bool operator<(SymEdge) const { return true; } + }; + + + /// The base type of the edge iterators. + + /// The base type of the edge iterators. + /// + class Edge : public SymEdge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Edge() { } + /// Copy constructor. + + /// Copy constructor. + /// + Edge(const Edge&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + Edge(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(Edge) const { return true; } + /// Inequality operator + + /// \sa operator==(Node n) + /// + bool operator!=(Edge) const { return true; } + ///Comparison operator. + + ///This is a strict ordering between the nodes. + /// + ///This ordering can be different from the order in which NodeIt + ///goes through the nodes. + ///\todo Possibly we don't need it. + bool operator<(Edge) const { return true; } + }; + + /// 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. + /// Its usage is quite simple, for example you can count the number + /// of outgoing edges of a node \c n + /// in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; + /// \endcode + + class OutEdgeIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + OutEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + OutEdgeIt(const OutEdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + OutEdgeIt(Invalid) { } + /// This constructor sets the iterator to first outgoing edge. + + /// This constructor set the iterator to the first outgoing edge of + /// node + ///@param n the node + ///@param g the graph + OutEdgeIt(const StaticSymGraph& g, const Node& n) { } + /// Edge -> OutEdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + OutEdgeIt(const StaticSymGraph& g, const Edge& e) { } + ///Next outgoing edge + + /// Assign the iterator to the next + /// outgoing edge of the corresponding node. + OutEdgeIt& operator++() { return *this; } + }; + + /// This iterator goes trough the incoming edges of a node. + + /// This iterator goes trough the \e incoming edges of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing edges of a node \c n + /// in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; + /// \endcode + + class InEdgeIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + InEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + InEdgeIt(const InEdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + InEdgeIt(Invalid) { } + /// This constructor sets the iterator to first incoming edge. + + /// This constructor set the iterator to the first incoming edge of + /// node + ///@param n the node + ///@param g the graph + InEdgeIt(const StaticSymGraph& g, const Node& n) { } + /// Edge -> InEdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + InEdgeIt(const StaticSymGraph& g, const Edge& n) { } + /// Next incoming edge + + /// Assign the iterator to the next inedge of the corresponding node. + /// + InEdgeIt& operator++() { return *this; } + }; + /// This iterator goes through each symmetric edge. + + /// This iterator goes through each symmetric edge of a graph. + /// Its usage is quite simple, for example you can count the number + /// of symmetric edges in a graph \c g of type \c Graph as follows: + /// \code + /// int count=0; + /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count; + /// \endcode + class SymEdgeIt : public SymEdge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + SymEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + SymEdgeIt(const SymEdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + SymEdgeIt(Invalid) { } + /// This constructor sets the iterator to first edge. + + /// This constructor set the iterator to the first edge of + /// node + ///@param g the graph + SymEdgeIt(const StaticSymGraph& g) { } + /// Edge -> EdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + SymEdgeIt(const StaticSymGraph&, const SymEdge&) { } + ///Next edge + + /// Assign the iterator to the next + /// edge of the corresponding node. + SymEdgeIt& operator++() { return *this; } + }; + /// This iterator goes through each edge. + + /// This iterator goes through each edge of a graph. + /// Its usage is quite simple, for example you can count the number + /// of edges in a graph \c g of type \c Graph as follows: + /// \code + /// int count=0; + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; + /// \endcode + class EdgeIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + EdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + EdgeIt(const EdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + EdgeIt(Invalid) { } + /// This constructor sets the iterator to first edge. + + /// This constructor set the iterator to the first edge of + /// node + ///@param g the graph + EdgeIt(const StaticSymGraph& g) { } + /// Edge -> EdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + EdgeIt(const StaticSymGraph&, const Edge&) { } + ///Next edge + + /// Assign the iterator to the next + /// edge of the corresponding node. + EdgeIt& operator++() { return *this; } + }; + + /// First node of the graph. + + /// \retval i the first node. + /// \return the first node. + /// + NodeIt& first(NodeIt& i) const { return i; } + + /// The first incoming edge. + + /// The first incoming edge. + /// + InEdgeIt& first(InEdgeIt &i, Node) const { return i; } + /// The first outgoing edge. + + /// The first outgoing edge. + /// + OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } + /// The first edge of the Graph. + + /// The first edge of the Graph. + /// + EdgeIt& first(EdgeIt& i) const { return i; } + /// The first symmetric edge of the Graph. + + /// The first symmetric edge of the Graph. + /// + SymEdgeIt& first(SymEdgeIt& i) const { return i; } + + ///Gives back the head node of an edge. + + ///Gives back the head node of an edge. + /// + Node head(Edge) const { return INVALID; } + ///Gives back the tail node of an edge. + + ///Gives back the tail node of an edge. + /// + Node tail(Edge) const { return INVALID; } + + ///Gives back the first node of an symmetric edge. + + ///Gives back the first node of an symmetric edge. + /// + Node head(SymEdge) const { return INVALID; } + ///Gives back the second node of an symmetric edge. + + ///Gives back the second node of an symmetric edge. + /// + Node tail(SymEdge) const { return INVALID; } + ///Gives back the \e id of a node. + + ///\warning Not all graph structures provide this feature. + /// + ///\todo Should each graph provide \c id? + int id(const Node&) const { return 0; } + ///Gives back the \e id of an edge. + + ///\warning Not all graph structures provide this feature. + /// + ///\todo Should each graph provide \c id? + int id(const Edge&) const { return 0; } + + ///\warning Not all graph structures provide this feature. + /// + ///\todo Should each graph provide \c id? + int id(const SymEdge&) const { return 0; } + + ///\e + + ///\todo Should it be in the concept? + /// + int nodeNum() const { return 0; } + ///\e + + ///\todo Should it be in the concept? + /// + int edgeNum() const { return 0; } + + ///\todo Should it be in the concept? + /// + int symEdgeNum() const { return 0; } + + + /// Gives back the forward directed edge of the symmetric edge. + Edge forward(SymEdge) const {return INVALID;} + + /// Gives back the backward directed edge of the symmetric edge. + Edge backward(SymEdge) const {return INVALID;}; + + /// Gives back the opposite of the edge. + Edge opposite(Edge) const {return INVALID;} + + ///Reference map of the nodes to type \c T. + /// \ingroup concept + ///Reference map of the nodes to type \c T. + /// \sa Reference + /// \warning Making maps that can handle bool type (NodeMap) + /// needs some extra attention! + template class NodeMap : public ReferenceMap< Node, T > + { + public: + + ///\e + NodeMap(const StaticSymGraph&) { } + ///\e + NodeMap(const StaticSymGraph&, T) { } + + ///Copy constructor + template NodeMap(const NodeMap&) { } + ///Assignment operator + template NodeMap& operator=(const NodeMap&) + { return *this; } + }; + + ///Reference map of the edges to type \c T. + + /// \ingroup concept + ///Reference map of the edges to type \c T. + /// \sa Reference + /// \warning Making maps that can handle bool type (EdgeMap) + /// needs some extra attention! + template class EdgeMap + : public ReferenceMap + { + public: + + ///\e + EdgeMap(const StaticSymGraph&) { } + ///\e + EdgeMap(const StaticSymGraph&, T) { } + + ///Copy constructor + template EdgeMap(const EdgeMap&) { } + ///Assignment operator + template EdgeMap &operator=(const EdgeMap&) + { return *this; } + }; + + ///Reference map of the edges to type \c T. + + /// \ingroup concept + ///Reference map of the symmetric edges to type \c T. + /// \sa Reference + /// \warning Making maps that can handle bool type (EdgeMap) + /// needs some extra attention! + template class SymEdgeMap + : public ReferenceMap + { + public: + + ///\e + SymEdgeMap(const StaticSymGraph&) { } + ///\e + SymEdgeMap(const StaticSymGraph&, T) { } + + ///Copy constructor + template SymEdgeMap(const SymEdgeMap&) { } + ///Assignment operator + template SymEdgeMap &operator=(const SymEdgeMap&) + { return *this; } + }; + }; + + + + /// An empty non-static graph class. + + /// This class provides everything that \ref StaticGraph + /// with additional functionality which enables to build a + /// graph from scratch. + class ExtendableSymGraph : public StaticSymGraph + { + public: + /// Defalult constructor. + + /// Defalult constructor. + /// + ExtendableSymGraph() { } + ///Add a new node to the graph. + + /// \return the new node. + /// + Node addNode() { return INVALID; } + ///Add a new edge to the graph. + + ///Add a new symmetric edge to the graph with tail node \c t + ///and head node \c h. + ///\return the new edge. + SymEdge addEdge(Node h, Node t) { return INVALID; } + + /// Resets the graph. + + /// This function deletes all edges and nodes of the graph. + /// It also frees the memory allocated to store them. + /// \todo It might belong to \ref ErasableGraph. + void clear() { } + }; + + /// An empty erasable graph class. + + /// This class is an extension of \ref ExtendableGraph. It also makes it + /// possible to erase edges or nodes. + class ErasableSymGraph : public ExtendableSymGraph + { + public: + /// Defalult constructor. + + /// Defalult constructor. + /// + ErasableSymGraph() { } + /// Deletes a node. + + /// Deletes node \c n node. + /// + void erase(Node n) { } + /// Deletes an edge. + + /// Deletes edge \c e edge. + /// + void erase(SymEdge e) { } + }; + + // @} + } //namespace concept +} //namespace lemon + + + +#endif // LEMON_CONCEPT_GRAPH_H diff -r 75f749682240 -r c80ef5912903 src/lemon/dijkstra.h --- a/src/lemon/dijkstra.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/dijkstra.h Thu Nov 04 20:24:59 2004 +0000 @@ -33,11 +33,11 @@ ///This class provides an efficient implementation of %Dijkstra algorithm. ///The edge lengths are passed to the algorithm using a - ///\ref skeleton::ReadMap "ReadMap", + ///\ref concept::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. /// ///The type of the length is determined by the - ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. + ///\ref concept::ReadMap::ValueType "ValueType" of the length map. /// ///It is also possible to change the underlying priority heap. /// @@ -48,7 +48,7 @@ ///lengths of the edges. It is read once for each edge, so the map ///may involve in relatively time consuming process to compute the edge ///length if it is necessary. The default map type is - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap" + ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap" ///\param Heap The heap type used by the %Dijkstra ///algorithm. The default ///is using \ref BinHeap "binary heap". diff -r 75f749682240 -r c80ef5912903 src/lemon/full_graph.h --- a/src/lemon/full_graph.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/full_graph.h Thu Nov 04 20:24:59 2004 +0000 @@ -194,8 +194,8 @@ ///It is completely static, so you can neither add nor delete either ///edges or nodes. ///Thus it conforms to - ///the \ref skeleton::StaticGraph "StaticGraph" concept - ///\sa skeleton::StaticGraph. + ///the \ref concept::StaticGraph "StaticGraph" concept + ///\sa concept::StaticGraph. ///\todo What about loops? ///\todo Don't we need SymEdgeMap? /// diff -r 75f749682240 -r c80ef5912903 src/lemon/list_graph.h --- a/src/lemon/list_graph.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/list_graph.h Thu Nov 04 20:24:59 2004 +0000 @@ -317,8 +317,8 @@ ///This is a simple and fast erasable graph implementation. /// ///It conforms to the - ///\ref skeleton::ErasableGraph "ErasableGraph" concept. - ///\sa skeleton::ErasableGraph. + ///\ref concept::ErasableGraph "ErasableGraph" concept. + ///\sa concept::ErasableGraph. class ListGraph : public ErasableListGraphBase { diff -r 75f749682240 -r c80ef5912903 src/lemon/maps.h --- a/src/lemon/maps.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/maps.h Thu Nov 04 20:24:59 2004 +0000 @@ -20,7 +20,7 @@ ///\file ///\brief Miscellaneous property maps /// -///\todo This file has the same name as the concept file in skeletons, +///\todo This file has the same name as the concept file in concept/, /// and this is not easily detectable in docs... #include diff -r 75f749682240 -r c80ef5912903 src/lemon/path.h --- a/src/lemon/path.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/path.h Thu Nov 04 20:24:59 2004 +0000 @@ -26,7 +26,7 @@ using a standard Builder subclass. This make is easy to have e.g. the Dijkstra algorithm to store its result in any kind of path structure. -\sa lemon::skeleton::Path +\sa lemon::concept::Path */ diff -r 75f749682240 -r c80ef5912903 src/lemon/skeletons/graph.h --- a/src/lemon/skeletons/graph.h Thu Nov 04 18:52:31 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,918 +0,0 @@ -/* -*- C++ -*- - * src/lemon/skeletons/graph.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - * - */ - -#ifndef LEMON_SKELETON_GRAPH_H -#define LEMON_SKELETON_GRAPH_H - -///\ingroup skeletons -///\file -///\brief Declaration of Graph. - -#include -#include -#include -#include - -namespace lemon { - namespace skeleton { - - /// \addtogroup skeletons - /// @{ - -// /// An empty static graph class. - -// /// This class provides all the common features of a graph structure, -// /// however completely without implementations and real data structures -// /// behind the interface. -// /// All graph algorithms should compile with this class, but it will not -// /// run properly, of course. -// /// -// /// It can be used for checking the interface compatibility, -// /// or it can serve as a skeleton of a new graph structure. -// /// -// /// Also, you will find here the full documentation of a certain graph -// /// feature, the documentation of a real graph imlementation -// /// like @ref ListGraph or -// /// @ref SmartGraph will just refer to this structure. -// /// -// /// \todo A pages describing the concept of concept description would -// /// be nice. -// class StaticGraph -// { -// public: -// /// Defalult constructor. - -// /// Defalult constructor. -// /// -// StaticGraph() { } -// ///Copy consructor. - -// // ///\todo It is not clear, what we expect from a copy constructor. -// // ///E.g. How to assign the nodes/edges to each other? What about maps? -// // StaticGraph(const StaticGraph& g) { } - -// /// The base type of node iterators, -// /// or in other words, the trivial node iterator. - -// /// This is the base type of each node iterator, -// /// thus each kind of node iterator converts to this. -// /// More precisely each kind of node iterator should be inherited -// /// from the trivial node iterator. -// class Node { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// Node() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// Node(const Node&) { } - -// /// Invalid constructor \& conversion. - -// /// This constructor initializes the iterator to be invalid. -// /// \sa Invalid for more details. -// Node(Invalid) { } -// /// Equality operator - -// /// Two iterators are equal if and only if they point to the -// /// same object or both are invalid. -// bool operator==(Node) const { return true; } - -// /// Inequality operator - -// /// \sa operator==(Node n) -// /// -// bool operator!=(Node) const { return true; } - -// ///Comparison operator. - -// ///This is a strict ordering between the nodes. -// /// -// ///This ordering can be different from the order in which NodeIt -// ///goes through the nodes. -// ///\todo Possibly we don't need it. -// bool operator<(Node) const { return true; } -// }; - -// /// This iterator goes through each node. - -// /// This iterator goes through each node. -// /// Its usage is quite simple, for example you can count the number -// /// of nodes in graph \c g of type \c Graph like this: -// /// \code -// /// int count=0; -// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; -// /// \endcode -// class NodeIt : public Node { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// NodeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// NodeIt(const NodeIt&) { } -// /// Invalid constructor \& conversion. - -// /// Initialize the iterator to be invalid. -// /// \sa Invalid for more details. -// NodeIt(Invalid) { } -// /// Sets the iterator to the first node. - -// /// Sets the iterator to the first node of \c g. -// /// -// NodeIt(const StaticGraph& g) { } -// /// Node -> NodeIt conversion. - -// /// Sets the iterator to the node of \c g pointed by the trivial -// /// iterator n. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// NodeIt(const StaticGraph& g, const Node& n) { } -// /// Next node. - -// /// Assign the iterator to the next node. -// /// -// NodeIt& operator++() { return *this; } -// }; - - -// /// The base type of the edge iterators. - -// /// The base type of the edge iterators. -// /// -// class Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// Edge() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// Edge(const Edge&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// Edge(Invalid) { } -// /// Equality operator - -// /// Two iterators are equal if and only if they point to the -// /// same object or both are invalid. -// bool operator==(Edge) const { return true; } -// /// Inequality operator - -// /// \sa operator==(Node n) -// /// -// bool operator!=(Edge) const { return true; } -// ///Comparison operator. - -// ///This is a strict ordering between the nodes. -// /// -// ///This ordering can be different from the order in which NodeIt -// ///goes through the nodes. -// ///\todo Possibly we don't need it. -// bool operator<(Edge) const { return true; } -// }; - -// /// 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. -// /// Its usage is quite simple, for example you can count the number -// /// of outgoing edges of a node \c n -// /// in graph \c g of type \c Graph as follows. -// /// \code -// /// int count=0; -// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; -// /// \endcode - -// class OutEdgeIt : public Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// OutEdgeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// OutEdgeIt(const OutEdgeIt&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// OutEdgeIt(Invalid) { } -// /// This constructor sets the iterator to first outgoing edge. - -// /// This constructor set the iterator to the first outgoing edge of -// /// node -// ///@param n the node -// ///@param g the graph -// OutEdgeIt(const StaticGraph& g, const Node& n) { } -// /// Edge -> OutEdgeIt conversion - -// /// Sets the iterator to the value of the trivial iterator \c e. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// OutEdgeIt(const StaticGraph& g, const Edge& e) { } -// ///Next outgoing edge - -// /// Assign the iterator to the next -// /// outgoing edge of the corresponding node. -// OutEdgeIt& operator++() { return *this; } -// }; - -// /// This iterator goes trough the incoming edges of a node. - -// /// This iterator goes trough the \e incoming edges of a certain node -// /// of a graph. -// /// Its usage is quite simple, for example you can count the number -// /// of outgoing edges of a node \c n -// /// in graph \c g of type \c Graph as follows. -// /// \code -// /// int count=0; -// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; -// /// \endcode - -// class InEdgeIt : public Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// InEdgeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// InEdgeIt(const InEdgeIt&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// InEdgeIt(Invalid) { } -// /// This constructor sets the iterator to first incoming edge. - -// /// This constructor set the iterator to the first incoming edge of -// /// node -// ///@param n the node -// ///@param g the graph -// InEdgeIt(const StaticGraph& g, const Node& n) { } -// /// Edge -> InEdgeIt conversion - -// /// Sets the iterator to the value of the trivial iterator \c e. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// InEdgeIt(const StaticGraph& g, const Edge& n) { } -// /// Next incoming edge - -// /// Assign the iterator to the next inedge of the corresponding node. -// /// -// InEdgeIt& operator++() { return *this; } -// }; -// /// This iterator goes through each edge. - -// /// This iterator goes through each edge of a graph. -// /// Its usage is quite simple, for example you can count the number -// /// of edges in a graph \c g of type \c Graph as follows: -// /// \code -// /// int count=0; -// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; -// /// \endcode -// class EdgeIt : public Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// EdgeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// EdgeIt(const EdgeIt&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// EdgeIt(Invalid) { } -// /// This constructor sets the iterator to first edge. - -// /// This constructor set the iterator to the first edge of -// /// node -// ///@param g the graph -// EdgeIt(const StaticGraph& g) { } -// /// Edge -> EdgeIt conversion - -// /// Sets the iterator to the value of the trivial iterator \c e. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// EdgeIt(const StaticGraph&, const Edge&) { } -// ///Next edge - -// /// Assign the iterator to the next -// /// edge of the corresponding node. -// EdgeIt& operator++() { return *this; } -// }; - -// /// First node of the graph. - -// /// \retval i the first node. -// /// \return the first node. -// /// -// NodeIt& first(NodeIt& i) const { return i; } - -// /// The first incoming edge. - -// /// The first incoming edge. -// /// -// InEdgeIt& first(InEdgeIt &i, Node) const { return i; } -// /// The first outgoing edge. - -// /// The first outgoing edge. -// /// -// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } -// /// The first edge of the Graph. - -// /// The first edge of the Graph. -// /// -// EdgeIt& first(EdgeIt& i) const { return i; } - -// ///Gives back the head node of an edge. - -// ///Gives back the head node of an edge. -// /// -// Node head(Edge) const { return INVALID; } -// ///Gives back the tail node of an edge. - -// ///Gives back the tail node of an edge. -// /// -// Node tail(Edge) const { return INVALID; } - -// ///Gives back the \e id of a node. - -// ///\warning Not all graph structures provide this feature. -// /// -// ///\todo Should each graph provide \c id? -// int id(const Node&) const { return 0; } -// ///Gives back the \e id of an edge. - -// ///\warning Not all graph structures provide this feature. -// /// -// ///\todo Should each graph provide \c id? -// int id(const Edge&) const { return 0; } - -// ///\e - -// ///\todo Should it be in the concept? -// /// -// int nodeNum() const { return 0; } -// ///\e - -// ///\todo Should it be in the concept? -// /// -// int edgeNum() const { return 0; } - - -// ///Reference map of the nodes to type \c T. - -// /// \ingroup skeletons -// ///Reference map of the nodes to type \c T. -// /// \sa Reference -// /// \warning Making maps that can handle bool type (NodeMap) -// /// needs some extra attention! -// template class NodeMap : public ReferenceMap< Node, T > -// { -// public: - -// ///\e -// NodeMap(const StaticGraph&) { } -// ///\e -// NodeMap(const StaticGraph&, T) { } - -// ///Copy constructor -// template NodeMap(const NodeMap&) { } -// ///Assignment operator -// template NodeMap& operator=(const NodeMap&) -// { return *this; } -// }; - -// ///Reference map of the edges to type \c T. - -// /// \ingroup skeletons -// ///Reference map of the edges to type \c T. -// /// \sa Reference -// /// \warning Making maps that can handle bool type (EdgeMap) -// /// needs some extra attention! -// template class EdgeMap -// : public ReferenceMap -// { -// public: - -// ///\e -// EdgeMap(const StaticGraph&) { } -// ///\e -// EdgeMap(const StaticGraph&, T) { } - -// ///Copy constructor -// template EdgeMap(const EdgeMap&) { } -// ///Assignment operator -// template EdgeMap &operator=(const EdgeMap&) -// { return *this; } -// }; -// }; - -// struct DummyType { -// int value; -// DummyType() {} -// DummyType(int p) : value(p) {} -// DummyType& operator=(int p) { value = p; return *this;} -// }; - -// ///\brief Checks whether \c G meets the -// ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept -// template void checkCompileStaticGraph(Graph &G) -// { -// typedef typename Graph::Node Node; -// typedef typename Graph::NodeIt NodeIt; -// typedef typename Graph::Edge Edge; -// typedef typename Graph::EdgeIt EdgeIt; -// typedef typename Graph::InEdgeIt InEdgeIt; -// typedef typename Graph::OutEdgeIt OutEdgeIt; - -// { -// Node i; Node j(i); Node k(INVALID); -// i=j; -// bool b; b=true; -// b=(i==INVALID); b=(i!=INVALID); -// b=(i==j); b=(i!=j); b=(iNodeIt conversion -// NodeIt ni(G,n); -// } -// { -// Edge i; Edge j(i); Edge k(INVALID); -// i=j; -// bool b; b=true; -// b=(i==INVALID); b=(i!=INVALID); -// b=(i==j); b=(i!=j); b=(iEdgeIt conversion -// EdgeIt ei(G,e); -// } -// { -// Node n; -// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); -// i=j; -// j=G.first(i,n); -// j=++i; -// bool b; b=true; -// b=(i==INVALID); b=(i!=INVALID); -// Edge e(i); -// e=i; -// b=(i==j); b=(i!=j); b=(iInEdgeIt conversion -// InEdgeIt ei(G,e); -// } -// { -// Node n; -// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); -// i=j; -// j=G.first(i,n); -// j=++i; -// bool b; b=true; -// b=(i==INVALID); b=(i!=INVALID); -// Edge e(i); -// e=i; -// b=(i==j); b=(i!=j); b=(iOutEdgeIt conversion -// OutEdgeIt ei(G,e); -// } -// { -// Node n,m; -// n=m=INVALID; -// Edge e; -// e=INVALID; -// n=G.tail(e); -// n=G.head(e); -// } -// // id tests -// { Node n; int i=G.id(n); i=i; } -// { Edge e; int i=G.id(e); i=i; } -// //NodeMap tests -// { -// Node k; -// typename Graph::template NodeMap m(G); -// //Const map -// typename Graph::template NodeMap const &cm = m; -// //Inicialize with default value -// typename Graph::template NodeMap mdef(G,12); -// //Copy -// typename Graph::template NodeMap mm(cm); -// //Copy from another type -// typename Graph::template NodeMap dm(cm); -// //Copy to more complex type -// typename Graph::template NodeMap em(cm); -// int v; -// v=m[k]; m[k]=v; m.set(k,v); -// v=cm[k]; - -// m=cm; -// dm=cm; //Copy from another type -// em=cm; //Copy to more complex type -// { -// //Check the typedef's -// typename Graph::template NodeMap::ValueType val; -// val=1; -// typename Graph::template NodeMap::KeyType key; -// key = typename Graph::NodeIt(G); -// } -// } -// { //bool NodeMap -// Node k; -// typename Graph::template NodeMap m(G); -// typename Graph::template NodeMap const &cm = m; //Const map -// //Inicialize with default value -// typename Graph::template NodeMap mdef(G,12); -// typename Graph::template NodeMap mm(cm); //Copy -// typename Graph::template NodeMap dm(cm); //Copy from another type -// bool v; -// v=m[k]; m[k]=v; m.set(k,v); -// v=cm[k]; - -// m=cm; -// dm=cm; //Copy from another type -// m=dm; //Copy to another type - -// { -// //Check the typedef's -// typename Graph::template NodeMap::ValueType val; -// val=true; -// typename Graph::template NodeMap::KeyType key; -// key= typename Graph::NodeIt(G); -// } -// } -// //EdgeMap tests -// { -// Edge k; -// typename Graph::template EdgeMap m(G); -// typename Graph::template EdgeMap const &cm = m; //Const map -// //Inicialize with default value -// typename Graph::template EdgeMap mdef(G,12); -// typename Graph::template EdgeMap mm(cm); //Copy -// typename Graph::template EdgeMap dm(cm);//Copy from another type -// int v; -// v=m[k]; m[k]=v; m.set(k,v); -// v=cm[k]; - -// m=cm; -// dm=cm; //Copy from another type -// { -// //Check the typedef's -// typename Graph::template EdgeMap::ValueType val; -// val=1; -// typename Graph::template EdgeMap::KeyType key; -// key= typename Graph::EdgeIt(G); -// } -// } -// { //bool EdgeMap -// Edge k; -// typename Graph::template EdgeMap m(G); -// typename Graph::template EdgeMap const &cm = m; //Const map -// //Inicialize with default value -// typename Graph::template EdgeMap mdef(G,12); -// typename Graph::template EdgeMap mm(cm); //Copy -// typename Graph::template EdgeMap dm(cm); //Copy from another type -// bool v; -// v=m[k]; m[k]=v; m.set(k,v); -// v=cm[k]; - -// m=cm; -// dm=cm; //Copy from another type -// m=dm; //Copy to another type -// { -// //Check the typedef's -// typename Graph::template EdgeMap::ValueType val; -// val=true; -// typename Graph::template EdgeMap::KeyType key; -// key= typename Graph::EdgeIt(G); -// } -// } -// } - -// /// An empty non-static graph class. - -// /// This class provides everything that \ref StaticGraph -// /// with additional functionality which enables to build a -// /// graph from scratch. -// class ExtendableGraph : public StaticGraph -// { -// public: -// /// Defalult constructor. - -// /// Defalult constructor. -// /// -// ExtendableGraph() { } -// ///Add a new node to the graph. - -// /// \return the new node. -// /// -// Node addNode() { return INVALID; } -// ///Add a new edge to the graph. - -// ///Add a new edge to the graph with tail node \c t -// ///and head node \c h. -// ///\return the new edge. -// Edge addEdge(Node h, Node t) { return INVALID; } - -// /// Resets the graph. - -// /// This function deletes all edges and nodes of the graph. -// /// It also frees the memory allocated to store them. -// /// \todo It might belong to \ref ErasableGraph. -// void clear() { } -// }; - - -// ///\brief Checks whether \c G meets the -// ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept -// template void checkCompileExtendableGraph(Graph &G) -// { -// checkCompileStaticGraph(G); - -// typedef typename Graph::Node Node; -// typedef typename Graph::NodeIt NodeIt; -// typedef typename Graph::Edge Edge; -// typedef typename Graph::EdgeIt EdgeIt; -// typedef typename Graph::InEdgeIt InEdgeIt; -// typedef typename Graph::OutEdgeIt OutEdgeIt; - -// Node n,m; -// n=G.addNode(); -// m=G.addNode(); -// Edge e; -// e=G.addEdge(n,m); - -// // G.clear(); -// } - - -// /// An empty erasable graph class. - -// /// This class is an extension of \ref ExtendableGraph. It also makes it -// /// possible to erase edges or nodes. -// class ErasableGraph : public ExtendableGraph -// { -// public: -// /// Defalult constructor. - -// /// Defalult constructor. -// /// -// ErasableGraph() { } -// /// Deletes a node. - -// /// Deletes node \c n node. -// /// -// void erase(Node n) { } -// /// Deletes an edge. - -// /// Deletes edge \c e edge. -// /// -// void erase(Edge e) { } -// }; - -// template void checkCompileGraphEraseEdge(Graph &G) -// { -// typename Graph::Edge e; -// G.erase(e); -// } - -// template void checkCompileGraphEraseNode(Graph &G) -// { -// typename Graph::Node n; -// G.erase(n); -// } - -// ///\brief Checks whether \c G meets the -// ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept -// template void checkCompileErasableGraph(Graph &G) -// { -// checkCompileExtendableGraph(G); -// checkCompileGraphEraseNode(G); -// checkCompileGraphEraseEdge(G); -// } - -// ///Checks whether a graph has findEdge() member function. - -// ///\todo findEdge() might be a global function. -// /// -// template void checkCompileGraphFindEdge(Graph &G) -// { -// typedef typename Graph::NodeIt Node; -// typedef typename Graph::NodeIt NodeIt; - -// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); -// G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); -// } - - - - /************* New GraphBase stuff **************/ - - - /// \bug The nodes and edges are not allowed to inherit from the - /// same baseclass. - - class BaseGraphItem { - public: - BaseGraphItem() {} - BaseGraphItem(Invalid) {} - - // We explicitely list these: - BaseGraphItem(BaseGraphItem const&) {} - BaseGraphItem& operator=(BaseGraphItem const&) { return *this; } - - bool operator==(BaseGraphItem) const { return false; } - bool operator!=(BaseGraphItem) const { return false; } - - // Technical requirement. Do we really need this? - bool operator<(BaseGraphItem) const { return false; } - }; - - - /// A minimal GraphBase concept - - /// This class describes a minimal concept which can be extended to a - /// full-featured graph with \ref GraphFactory. - class GraphBase { - public: - - GraphBase() {} - - - /// \bug Nodes and Edges are comparable each other - - class Node : public BaseGraphItem {}; - class Edge : public BaseGraphItem {}; - - // Graph operation - void firstNode(Node &n) const { } - void firstEdge(Edge &e) const { } - - void firstOutEdge(Edge &e, Node) const { } - void firstInEdge(Edge &e, Node) const { } - - void nextNode(Node &n) const { } - void nextEdge(Edge &e) const { } - - - // Question: isn't it reasonable if this methods have a Node - // parameter? Like this: - // Edge& nextOut(Edge &e, Node) const { return e; } - void nextOutEdge(Edge &e) const { } - void nextInEdge(Edge &e) const { } - - Node head(Edge) const { return Node(); } - Node tail(Edge) const { return Node(); } - - - // Do we need id, nodeNum, edgeNum and co. in this basic graphbase - // concept? - - - // Maps. - // - // We need a special slimer concept which does not provide maps (it - // wouldn't be strictly slimer, cause for map-factory id() & friends - // a required...) - - template - class NodeMap : public GraphMap {}; - - template - class EdgeMap : public GraphMap {}; - }; - - - - /**************** Concept checking classes ****************/ - - template - struct BaseGraphItemConcept { - void constraints() { - BGI i1; - BGI i2 = i1; - BGI i3 = INVALID; - - i1 = i3; - if( i1 == i3 ) { - if ( i2 != i3 && i3 < i2 ) - return; - } - } - }; - - - - class StaticGraph - : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { - public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - }; - - template - struct StaticGraphConcept { - void constraints() { - function_requires >(); - function_requires >(); - function_requires >(); - } - Graph& graph; - }; - - class ExtendableGraph - : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { - public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - }; - - template - struct ExtendableGraphConcept { - void constraints() { - function_requires >(); - function_requires >(); - function_requires >(); - } - Graph& graph; - }; - - class ErasableGraph - : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent { - public: - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - }; - - template - struct ErasableGraphConcept { - void constraints() { - function_requires >(); - function_requires >(); - } - Graph& graph; - }; - - // @} - } //namespace skeleton -} //namespace lemon - - - -#endif // LEMON_SKELETON_GRAPH_H diff -r 75f749682240 -r c80ef5912903 src/lemon/skeletons/graph_component.h --- a/src/lemon/skeletons/graph_component.h Thu Nov 04 18:52:31 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,827 +0,0 @@ -/* -*- C++ -*- - * src/lemon/skeletons/graph_component.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 skeletons -///\file -///\brief The graph components. - - -#ifndef LEMON_SKELETON_GRAPH_COMPONENT_H -#define LEMON_SKELETON_GRAPH_COMPONENT_H - -#include -#include - -namespace lemon { - namespace skeleton { - - /// An empty base graph class. - - /// This class provides the most minimal features of a graph structure. - /// All the graph concepts have to be conform to this base graph. - - class BaseGraphComponent { - public: - - typedef BaseGraphComponent Graph; - - /// Node class of the graph. - - /// This class represents the Nodes of the graph. - /// - class Node { - public: - - /// Default constructor. - - /// @warning The default constructor sets the iterator - /// to an undefined value. - - Node() {} - /// Copy constructor. - - /// Copy constructor. - /// - Node(const Node&) {} - - /// Invalid constructor \& conversion. - - /// This constructor initializes the iterator to be invalid. - /// \sa Invalid for more details. - Node(Invalid) {} - - - Node& operator=(const Node&) { return *this;} - - /// Equality operator. - - /// Two iterators are equal if and only if they represents the - /// same node in the graph or both are invalid. - bool operator==(const Node&) { return true;} - - - /// Inequality operator. - - /// \sa operator==(const Node& n) - /// - bool operator!=(const Node&) { return true;} - - /// Comparison operator. - - /// This is a strict ordering between the nodes. - /// - /// This ordering can be different from the iterating order of nodes. - /// \todo Possibly we don't need it. - bool operator<(const Node&) { return true;} - }; - - /// Edge class of the graph. - - /// This class represents the Edges of the graph. - /// - class Edge { - public: - - /// Default constructor. - - /// @warning The default constructor sets the iterator - /// to an undefined value. - - Edge() {} - /// Copy constructor. - - /// Copy constructor. - /// - Edge(const Edge&) {} - - /// Invalid constructor \& conversion. - - /// This constructor initializes the iterator to be invalid. - /// \sa Invalid for more details. - Edge(Invalid) {} - - - Edge& operator=(const Edge&) { return *this;} - - /// Equality operator. - - /// Two iterators are equal if and only if they represents the - /// same edge in the graph or both are invalid. - bool operator==(const Edge&) { return true;} - - - /// Inequality operator. - - /// \sa operator==(const Edge& n) - /// - bool operator!=(const Edge&) { return true;} - - /// Comparison operator. - - /// This is a strict ordering between the edges. - /// - /// This ordering can be different from the iterating order of edges. - /// \todo Possibly we don't need it. - bool operator<(const Edge&) { return true;} - }; - - ///Gives back the head node of an edge. - - ///Gives back the head node of an edge. - /// - Node head(const Edge&) const { return INVALID;} - - ///Gives back the tail node of an edge. - - ///Gives back the tail node of an edge. - /// - Node tail(const Edge&) const { return INVALID;} - }; - - /// Concept check structure for BaseGraph. - - /// Concept check structure for BaseGraph. - /// - - template - struct BaseGraphComponentConcept { - typedef typename Graph::Node Node; - typedef typename Graph::Edge Edge; - - void constraints() { - { - Node ni; - Node nj(ni); - Node nk(INVALID); - ni = nj; - bool b; b = true; - b = (ni == INVALID); b = (ni != INVALID); - b = (ni==nj); b = (ni != nj); b=( ni < nj); - } - { - Edge ei; - Edge ej(ei); - Edge ek(INVALID); - ei = ej; - bool b; b = true; - b = (ei == INVALID); b = (ei != INVALID); - b = (ei==ej); b = (ei != ej); b=( ei < ej); - } - { - const Graph& const_graph = graph; - Node n; - Edge e; - n = const_graph.tail(e); - n = const_graph.head(e); - } - } - - Graph& graph; - }; - - /// An empty iterable base graph class. - - /// This class provides beside the core graph features - /// core iterable interface for the graph structure. - /// Most of the base graphs should be conform to this concept. - - class BaseIterableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Gives back the first Node in the iterating order. - - /// Gives back the first Node in the iterating order. - /// - void first(Node&) const {} - - /// Gives back the next Node in the iterating order. - - /// Gives back the next Node in the iterating order. - /// - void next(Node&) const {} - - /// Gives back the first Edge in the iterating order. - - /// Gives back the first Edge in the iterating order. - /// - void first(Edge&) const {} - /// Gives back the next Edge in the iterating order. - - /// Gives back the next Edge in the iterating order. - /// - void next(Edge&) const {} - - - /// Gives back the first of the Edges point to the given Node. - - /// Gives back the first of the Edges point to the given Node. - /// - void firstIn(Edge&, const Node&) const {} - - /// Gives back the next of the Edges points to the given Node. - - - /// Gives back the next of the Edges points to the given Node. - /// - void nextIn(Edge&) const {} - - /// Gives back the first of the Edges start from the given Node. - - /// Gives back the first of the Edges start from the given Node. - /// - void firstOut(Edge&, const Node&) const {} - - /// Gives back the next of the Edges start from the given Node. - - /// Gives back the next of the Edges start from the given Node. - /// - void nextOut(Edge&) const {} - }; - - - /// Concept check structure for IterableBaseGraph. - - /// Concept check structure for IterableBaseGraph. - /// - template - struct BaseIterableGraphComponentConcept { - - void constraints() { - const Graph& const_graph = graph; - typename Graph::Node node; - typename Graph::Edge edge; - { - const_graph.first(node); - const_graph.next(node); - } - { - const_graph.first(edge); - const_graph.next(edge); - } - { - const_graph.firstIn(edge, node); - const_graph.nextIn(edge); - } - { - const_graph.firstOut(edge, node); - const_graph.nextOut(edge); - } - } - - Graph& graph; - }; - - /// An empty idable base graph class. - - /// This class provides beside the core graph features - /// core id functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - /// The id's are unique and immutable. - - class IDableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Gives back an unique integer id for the Node. - - /// Gives back an unique integer id for the Node. - /// - int id(const Node&) const { return -1;} - - /// 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;} - }; - - - /// Concept check structure for IdableBaseGraph. - - /// Concept check structure for IdableBaseGraph. - /// - template - struct IDableGraphComponentConcept { - - void constraints() { - const Graph& const_graph = graph; - typename Graph::Node node; - int nid = const_graph.id(node); - nid = const_graph.id(node); - typename Graph::Edge edge; - int eid = const_graph.id(edge); - eid = const_graph.id(edge); - } - - Graph& graph; - }; - - - /// An empty max-idable base graph class. - - /// This class provides beside the core graph features - /// core max id functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - /// The id's are unique and immutable. - class MaxIDableGraphComponent : virtual public BaseGraphComponent { - public: - - /// Gives back an integer greater or equal to the maximum Node id. - - /// Gives back an integer greater or equal to the maximum Node id. - /// - int maxEdgeId() const { return -1;} - - /// Gives back an integer greater or equal to the maximum Edge id. - - /// Gives back an integer greater or equal to the maximum Edge id. - /// - int maxNodeId() const { return -1;} - }; - - /// Concept check structure for MaxIdableBaseGraph. - - /// Concept check structure for MaxIdableBaseGraph. - /// - template - struct MaxIDableGraphComponentConcept { - - void constraints() { - const Graph& const_graph = graph; - int nid = const_graph.maxEdgeId(); - ignore_unused_variable_warning(nid); - int eid = const_graph.maxNodeId(); - ignore_unused_variable_warning(eid); - } - - Graph& graph; - }; - - /// An empty extendable base graph class. - - /// This class provides beside the core graph features - /// core graph extend interface for the graph structure. - /// The most of the base graphs should be conform to this concept. - class BaseExtendableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Adds a new Node to the graph. - - /// Adds a new Node to the graph. - /// - Node addNode() { - return INVALID; - } - - /// Adds a new Edge connects the two Nodes to the graph. - - /// Adds a new Edge connects the two Nodes to the graph. - /// - Edge addEdge(const Node& from, const Node& to) { - return INVALID; - } - - }; - - /// Concept check structure for ExtendableBaseGraph. - - /// Concept check structure for ExtendableBaseGraph. - /// - template - struct BaseExtendableGraphComponentConcept { - void constraints() { - typename Graph::Node node_a, node_b; - node_a = graph.addNode(); - typename Graph::Edge edge; - edge = graph.addEdge(node_a, node_b); - } - - Graph& graph; - }; - - /// An empty erasable base graph class. - - /// This class provides beside the core graph features - /// core erase functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - class BaseErasableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - /// Erase a Node from the graph. - - /// Erase a Node from the graph. This function should not - /// erase edges connecting to the Node. - void erase(const Node&) {} - - /// Erase an Edge from the graph. - - /// Erase an Edge from the graph. - /// - void erase(const Edge&) {} - - }; - - /// Concept check structure for ErasableBaseGraph. - - /// Concept check structure for ErasableBaseGraph. - /// - template - struct BaseErasableGraphComponentConcept { - void constraints() { - typename Graph::Node node; - graph.erase(node); - typename Graph::Edge edge; - graph.erase(edge); - } - - Graph& graph; - }; - - /// An empty clearable base graph class. - - /// This class provides beside the core graph features - /// core clear functions for the graph structure. - /// The most of the base graphs should be conform to this concept. - class BaseClearableGraphComponent : virtual public BaseGraphComponent { - public: - - /// Erase all the Nodes and Edges from the graph. - - /// Erase all the Nodes and Edges from the graph. - /// - void clear() {} - }; - - /// Concept check function for ErasableBaseGraph. - - /// Concept check function for ErasableBaseGraph. - /// - template - struct BaseClearableGraphComponentConcept { - void constraints() { - graph.clear(); - } - - Graph& graph; - }; - - - class IterableGraphComponent : virtual public BaseGraphComponent { - - public: - - typedef IterableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - class NodeIt : public Node { - public: - NodeIt() {} - NodeIt(Invalid) {} - NodeIt(const Graph&) {} - - NodeIt& operator++() { return *this; } - // Node operator*() const { return INVALID; } - - bool operator==(const NodeIt&) { return true;} - bool operator!=(const NodeIt&) { return true;} - }; - - class EdgeIt : public Edge { - public: - EdgeIt() {} - EdgeIt(Invalid) {} - EdgeIt(const Graph&) {} - - EdgeIt& operator++() { return *this; } - // Edge operator*() const { return INVALID; } - - bool operator==(const EdgeIt&) { return true;} - bool operator!=(const EdgeIt&) { return true;} - }; - - class InEdgeIt : public Edge { - public: - InEdgeIt() {} - InEdgeIt(Invalid) {} - InEdgeIt(const Graph&, const Node&) {} - - InEdgeIt& operator++() { return *this; } - // Edge operator*() const { return INVALID; } - - bool operator==(const InEdgeIt&) { return true;} - bool operator!=(const InEdgeIt&) { return true;} - }; - - class OutEdgeIt : public Edge { - public: - OutEdgeIt() {} - OutEdgeIt(Invalid) {} - OutEdgeIt(const Graph&, const Node&) {} - - OutEdgeIt& operator++() { return *this; } - // Edge operator*() const { return INVALID; } - - bool operator==(const OutEdgeIt&) { return true;} - bool operator!=(const OutEdgeIt&) { return true;} - }; - - }; - - template - struct IterableGraphComponentConcept { - - void constraints() { - - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - - { - NodeIt it; - NodeIt jt(it); - NodeIt kt(INVALID); - NodeIt lt(graph); - it = jt; - jt = ++it; - bool b; - b = (it == INVALID); - b = (it != INVALID); - b = (it == jt); - b = (it != jt); - Node node = it; - node = it; - } - { - EdgeIt it; - EdgeIt jt(it); - EdgeIt kt(INVALID); - EdgeIt lt(graph); - it = jt; - jt = ++it; - bool b; - b = (it == INVALID); - b = (it != INVALID); - b = (it == jt); - b = (it != jt); - Edge edge = it; - edge = it; - } - { - InEdgeIt it; - InEdgeIt jt(it); - InEdgeIt kt(INVALID); - Node node; - InEdgeIt lt(graph, node); - it = jt; - jt = ++it; - bool b; - b = (it == INVALID); - b = (it != INVALID); - b = (it == jt); - b = (it != jt); - Edge edge = it; - edge = it; - } - { - OutEdgeIt it; - OutEdgeIt jt(it); - OutEdgeIt kt(INVALID); - Node node; - OutEdgeIt lt(graph, node); - it = jt; - jt = ++it; - bool b; - b = (it == INVALID); - b = (it != INVALID); - b = (it == jt); - b = (it != jt); - Edge edge = it; - edge = it; - } - } - Graph& graph; - }; - - - class IdMappableGraphComponent : virtual public BaseGraphComponent { - - typedef IdMappableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - public: - - class NodeIdMap : public ReadMap { - public: - NodeIdMap(const Graph&) {} - int maxId() const { return -1;} - }; - - class EdgeIdMap : public ReadMap { - public: - EdgeIdMap(const Graph&) {} - int maxId() const { return -1;} - }; - - }; - - template - struct IdMappableGraphComponentConcept { - void constraints() { - { - typedef typename Graph::EdgeIdMap EdgeIdMap; - function_requires >(); - EdgeIdMap edge_map(graph); - int n = edge_map.maxId(); - ignore_unused_variable_warning(n); - } - { - typedef typename Graph::NodeIdMap NodeIdMap; - function_requires >(); - NodeIdMap node_map(graph); - int n = node_map.maxId(); - ignore_unused_variable_warning(n); - } - } - Graph& graph; - }; - - - class MappableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef MappableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - template - class NodeMap : public ReferenceMap { - public: - NodeMap(const Graph&) {} - NodeMap(const Graph&, const Value&) {} - NodeMap(const NodeMap&) {} - - NodeMap& operator=(const NodeMap&) { return *this;} - - }; - - template - class EdgeMap : public ReferenceMap { - public: - EdgeMap(const Graph&) {} - EdgeMap(const Graph&, const Value&) {} - EdgeMap(const EdgeMap&) {} - - EdgeMap& operator=(const EdgeMap&) { return *this;} - - }; - - }; - - template - struct MappableGraphComponentConcept { - - struct Type { - int value; - Type() : value(0) {} - Type(int _v) : value(_v) {} - }; - - void constraints() { - { // int map test - typedef typename Graph::template NodeMap IntNodeMap; - function_requires >(); - } { // bool map test - typedef typename Graph::template NodeMap BoolNodeMap; - function_requires >(); - } { // Type map test - typedef typename Graph::template NodeMap TypeNodeMap; - function_requires >(); - } - - { // int map test - typedef typename Graph::template EdgeMap IntEdgeMap; - function_requires >(); - } { // bool map test - typedef typename Graph::template EdgeMap BoolEdgeMap; - function_requires >(); - } { // Type map test - typedef typename Graph::template EdgeMap TypeEdgeMap; - function_requires >(); - } - } - - Graph& graph; - }; - - - class ExtendableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef ExtendableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - Node addNode() { - return INVALID; - } - - Edge addEdge(const Node& from, const Node& to) { - return INVALID; - } - - }; - - template - struct ExtendableGraphComponentConcept { - void constraints() { - typename Graph::Node node_a, node_b; - node_a = graph.addNode(); - typename Graph::Edge edge; - edge = graph.addEdge(node_a, node_b); - } - Graph& graph; - }; - - class ErasableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef ErasableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - void erase(const Node&) {} - void erase(const Edge&) {} - - }; - - template - struct ErasableGraphComponentConcept { - void constraints() { - typename Graph::Node node; - graph.erase(node); - typename Graph::Edge edge; - graph.erase(edge); - } - - Graph& graph; - }; - - class ClearableGraphComponent : virtual public BaseGraphComponent { - public: - - typedef ClearableGraphComponent Graph; - - typedef BaseGraphComponent::Node Node; - typedef BaseGraphComponent::Edge Edge; - - void clear() {} - - }; - - template - struct ClearableGraphComponentConcept { - void constraints() { - graph.clear(); - } - Graph& graph; - }; - - } - -} - -#endif diff -r 75f749682240 -r c80ef5912903 src/lemon/skeletons/maps.h --- a/src/lemon/skeletons/maps.h Thu Nov 04 18:52:31 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,246 +0,0 @@ -/* -*- C++ -*- - * src/lemon/skeletons/maps.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - * - */ - -#ifndef LEMON_MAPSKELETON_H -#define LEMON_MAPSKELETON_H - -#include - -///\ingroup skeletons -///\file -///\brief Map concepts checking classes for testing and documenting. - -namespace lemon { - - namespace skeleton { - - /// \addtogroup skeletons - /// @{ - - /// Readable map concept - template - class ReadMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - /// Returns the value associated with a key. - ValueType operator[](const KeyType &k) const {return ValueType();} - - ///Default constructor - ReadMap() {} - }; - - - /// Writable map concept - template - class WriteMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - /// Sets the value associated with a key. - void set(const KeyType &k,const ValueType &t) {} - - ///Default constructor - WriteMap() {} - }; - - ///Read/Writable map concept - template - class ReadWriteMap : public ReadMap, - public WriteMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - /// Returns the value associated with a key. - ValueType operator[](const KeyType &k) const {return ValueType();} - /// Sets the value associated with a key. - void set(const KeyType &k,const ValueType &t) {} - - ///Default constructor - ReadWriteMap() {} - }; - - - ///Dereferable map concept - template - class ReferenceMap : public ReadWriteMap - { - public: - /// Map's key type. - typedef K KeyType; - /// Map's value type. (The type of objects associated with the keys). - typedef T ValueType; - - protected: - ValueType tmp; - public: - typedef ValueType& ReferenceType; - /// Map's const reference type. - typedef const ValueType& ConstReferenceType; - - ///Returns a reference to the value associated to a key. - ReferenceType operator[](const KeyType &i) { return tmp; } - ///Returns a const reference to the value associated to a key. - ConstReferenceType operator[](const KeyType &i) const - { return tmp; } - /// Sets the value associated with a key. - void set(const KeyType &k,const ValueType &t) { operator[](k)=t; } - - ///Default constructor - ReferenceMap() {} - }; - - - template - class GraphMap : public ReadWriteMap { - // I really, really don't like the idea that every graph should have - // reference maps! --klao - - private: - // We state explicitly that graph maps have no default constructor? - GraphMap(); - - public: - explicit GraphMap(Graph const&) {} - // value for initializing - GraphMap(Graph const&, T) {} - - // this probably should be required: - GraphMap(GraphMap const&) {} - GraphMap& operator=(GraphMap const&) { return *this; } - - // but this is a absolute no-op! We should provide a more generic - // graph-map-copy operation. - // - // template - // GraphMap(GraphMap const&); - // - // template - // GraphMap& operator=(const GraphMap&); - }; - - - /**************** Concept-checking classes ****************/ - - template - struct ReadMapConcept { - typedef typename ReadMap::KeyType KeyType; - typedef typename ReadMap::ValueType ValueType; - - void constraints() { - // No constraints for constructor. - - // What are the requirement for the ValueType? - // CopyConstructible? Assignable? None of these? - ValueType v = m[k]; - v = m[k]; - - // FIXME: - ignore_unused_variable_warning(v); - } - - ReadMap m; - KeyType k; - }; - - template - struct WriteMapConcept { - typedef typename WriteMap::KeyType KeyType; - typedef typename WriteMap::ValueType ValueType; - - void constraints() { - // No constraints for constructor. - - m.set(k, v); - } - - WriteMap m; - KeyType k; - ValueType v; - }; - - template - struct ReadWriteMapConcept { - void constraints() { - function_requires< ReadMapConcept >(); - function_requires< WriteMapConcept >(); - } - }; - - template - struct ReferenceMapConcept { - typedef typename ReferenceMap::KeyType KeyType; - typedef typename ReferenceMap::ValueType ValueType; - typedef typename ReferenceMap::ReferenceType ReferenceType; - - // What for is this? - typedef typename ReferenceMap::ConstReferenceType ConstReferenceType; - - void constraints() { - function_requires< ReadWriteMapConcept >(); - - m[k] = v; - // Or should we require real reference? - // Like this: - // ValueType &vv = m[k]; - // ignore_unused_variable_warning(vv); - } - - ReferenceMap m; - KeyType k; - ValueType v; - }; - - /// \todo GraphMapConceptCheck - - template - struct GraphMapConcept { - void constraints() { - function_requires< ReadWriteMapConcept >(); - // Construction with a graph parameter - GraphMap a(g); - // Ctor with a graph and a default value parameter - GraphMap a2(g,t); - // Copy ctor. Do we need it? - GraphMap b=c; - // Copy operator. Do we need it? - a=b; - - ignore_unused_variable_warning(a2); - } - const GraphMap &c; - const Graph &g; - const typename GraphMap::ValueType &t; - }; - - - // @} - - } //namespace skeleton -} //namespace lemon -#endif // LEMON_MAPSKELETON_H diff -r 75f749682240 -r c80ef5912903 src/lemon/skeletons/path.h --- a/src/lemon/skeletons/path.h Thu Nov 04 18:52:31 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,236 +0,0 @@ -/* -*- C++ -*- - * src/lemon/skeletons/path.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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 skeletons -///\file -///\brief Classes for representing paths in graphs. - -#ifndef LEMON_SKELETON_PATH_H -#define LEMON_SKELETON_PATH_H - -#include - -namespace lemon { - namespace skeleton { - /// \addtogroup skeletons - /// @{ - - - //! \brief A skeletom structure for representing directed paths in a graph. - //! - //! A skeleton structure for representing directed paths in a graph. - //! \param GR The graph type in which the path is. - //! - //! In a sense, the path can be treated as a graph, for is has \c NodeIt - //! and \c EdgeIt with the same usage. These types converts to the \c Node - //! and \c Edge of the original graph. - template - class Path { - public: - - /// Type of the underlying graph. - typedef /*typename*/ GR Graph; - /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; - /// Node type of the underlying graph. - typedef typename Graph::Node GraphNode; - class NodeIt; - class EdgeIt; - - /// \param _G The graph in which the path is. - /// - Path(const Graph &_G) {} - - /// Length of the path. - size_t length() const {return 0;} - /// Returns whether the path is empty. - bool empty() const { return true;} - - /// Resets the path to an empty path. - void clear() {} - - /// \brief Starting point of the path. - /// - /// Starting point of the path. - /// Returns INVALID if the path is empty. - GraphNode/*It*/ head() const {return INVALID;} - /// \brief End point of the path. - /// - /// End point of the path. - /// Returns INVALID if the path is empty. - GraphNode/*It*/ tail() const {return INVALID;} - - /// \brief First NodeIt/EdgeIt. - /// - /// Initializes node or edge iterator to point to the first - /// node or edge. - template - It& first(It &i) const { return i=It(*this); } - - /// \brief The head of an edge. - /// - /// Returns node iterator pointing to the head node of the - /// given edge iterator. - NodeIt head(const EdgeIt& e) const {return INVALID;} - - /// \brief The tail of an edge. - /// - /// Returns node iterator pointing to the tail node of the - /// given edge iterator. - NodeIt tail(const EdgeIt& e) const {return INVALID;} - - - /* Iterator classes */ - - /** - * \brief Iterator class to iterate on the edges of the paths - * - * \ingroup skeletons - * This class is used to iterate on the edges of the paths - * - * Of course it converts to Graph::Edge - * - */ - class EdgeIt { - public: - /// Default constructor - EdgeIt() {} - /// Invalid constructor - EdgeIt(Invalid) {} - /// Constructor with starting point - EdgeIt(const Path &_p) {} - - operator GraphEdge () const {} - - /// Next edge - EdgeIt& operator++() {return *this;} - - /// Comparison operator - bool operator==(const EdgeIt& e) const {return true;} - /// Comparison operator - bool operator!=(const EdgeIt& e) const {return true;} -// /// Comparison operator -// /// \todo It is not clear what is the "natural" ordering. -// bool operator<(const EdgeIt& e) const {} - - }; - - /** - * \brief Iterator class to iterate on the nodes of the paths - * - * \ingroup skeletons - * This class is used to iterate on the nodes of the paths - * - * Of course it converts to Graph::Node. - * - */ - class NodeIt { - public: - /// Default constructor - NodeIt() {} - /// Invalid constructor - NodeIt(Invalid) {} - /// Constructor with starting point - NodeIt(const Path &_p) {} - - ///Conversion to Graph::Node - operator const GraphNode& () const {} - /// Next node - NodeIt& operator++() {return *this;} - - /// Comparison operator - bool operator==(const NodeIt& e) const {return true;} - /// Comparison operator - bool operator!=(const NodeIt& e) const {return true;} -// /// Comparison operator -// /// \todo It is not clear what is the "natural" ordering. -// bool operator<(const NodeIt& e) const {} - - }; - - friend class Builder; - - /** - * \brief Class to build paths - * - * \ingroup skeletons - * This class is used to fill a path with edges. - * - * You can push new edges to the front and to the back of the path in - * arbitrary order then you should commit these changes to the graph. - * - * While the builder is active (after the first modifying - * operation and until the call of \ref commit()) - * the underlining Path is in a - * "transitional" state (operations on it have undefined result). - */ - class Builder { - public: - - Path &P; - - ///\param _P the path you want to fill in. - /// - Builder(Path &_P) : P(_P) {} - - /// Sets the starting node of the path. - - /// Sets the starting node of the path. Edge added to the path - /// afterwards have to be incident to this node. - /// You \em must start building an empry path with this functions. - /// (And you \em must \em not use it later). - /// \sa pushFront() - /// \sa pushBack() - void setStartNode(const GraphNode &) {} - - ///Push a new edge to the front of the path - - ///Push a new edge to the front of the path. - ///If the path is empty, you \em must call \ref setStartNode() before - ///the first use of \ref pushFront(). - void pushFront(const GraphEdge& e) {} - - ///Push a new edge to the back of the path - - ///Push a new edge to the back of the path. - ///If the path is empty, you \em must call \ref setStartNode() before - ///the first use of \ref pushBack(). - void pushBack(const GraphEdge& e) {} - - ///Commit the changes to the path. - void commit() {} - - ///Reserve (front) storage for the builder in advance. - - ///If you know an reasonable upper bound of the number of the edges - ///to add to the front of the path, - ///using this function you may speed up the building. - void reserveFront(size_t r) {} - ///Reserve (back) storage for the builder in advance. - - ///If you know an reasonable upper bound of the number of the edges - ///to add to the back of the path, - ///using this function you may speed up the building. - void reserveBack(size_t r) {} - }; - }; - - ///@} - } - -} // namespace lemon - -#endif // LEMON_SKELETON_PATH_H diff -r 75f749682240 -r c80ef5912903 src/lemon/skeletons/sym_graph.h --- a/src/lemon/skeletons/sym_graph.h Thu Nov 04 18:52:31 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,653 +0,0 @@ -/* -*- C++ -*- - * src/lemon/skeletons/graph.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, 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. - * - */ - -#ifndef LEMON_SKELETON_SYM_GRAPH_H -#define LEMON_SKELETON_SYM_GRAPH_H - -///\ingroup skeletons -///\file -///\brief Declaration of SymGraph. - -#include -#include -#include - -namespace lemon { - namespace skeleton { - - /// \addtogroup skeletons - /// @{ - - /// An empty static graph class. - - /// This class provides all the common features of a symmetric - /// graph structure, however completely without implementations and - /// real data structures behind the interface. - /// All graph algorithms should compile with this class, but it will not - /// run properly, of course. - /// - /// It can be used for checking the interface compatibility, - /// or it can serve as a skeleton of a new symmetric graph structure. - /// - /// Also, you will find here the full documentation of a certain graph - /// feature, the documentation of a real symmetric graph imlementation - /// like @ref SymListGraph or - /// @ref lemon::SymSmartGraph will just refer to this structure. - class StaticSymGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - StaticSymGraph() { } - ///Copy consructor. - -// ///\todo It is not clear, what we expect from a copy constructor. -// ///E.g. How to assign the nodes/edges to each other? What about maps? -// StaticGraph(const StaticGraph& g) { } - - /// The base type of node iterators, - /// or in other words, the trivial node iterator. - - /// This is the base type of each node iterator, - /// thus each kind of node iterator converts to this. - /// More precisely each kind of node iterator should be inherited - /// from the trivial node iterator. - class Node { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - Node() { } - /// Copy constructor. - - /// Copy constructor. - /// - Node(const Node&) { } - - /// Invalid constructor \& conversion. - - /// This constructor initializes the iterator to be invalid. - /// \sa Invalid for more details. - Node(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Node) const { return true; } - - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(Node) const { return true; } - - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(Node) const { return true; } - }; - - /// This iterator goes through each node. - - /// This iterator goes through each node. - /// Its usage is quite simple, for example you can count the number - /// of nodes in graph \c g of type \c Graph like this: - /// \code - /// int count=0; - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; - /// \endcode - class NodeIt : public Node { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - NodeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - NodeIt(const NodeIt&) { } - /// Invalid constructor \& conversion. - - /// Initialize the iterator to be invalid. - /// \sa Invalid for more details. - NodeIt(Invalid) { } - /// Sets the iterator to the first node. - - /// Sets the iterator to the first node of \c g. - /// - NodeIt(const StaticSymGraph& g) { } - /// Node -> NodeIt conversion. - - /// Sets the iterator to the node of \c g pointed by the trivial - /// iterator n. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - NodeIt(const StaticSymGraph& g, const Node& n) { } - /// Next node. - - /// Assign the iterator to the next node. - /// - NodeIt& operator++() { return *this; } - }; - - - /// The base type of the symmetric edge iterators. - - /// The base type of the symmetric edge iterators. - /// - class SymEdge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - SymEdge() { } - /// Copy constructor. - - /// Copy constructor. - /// - SymEdge(const SymEdge&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - SymEdge(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(SymEdge) const { return true; } - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(SymEdge) const { return true; } - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(SymEdge) const { return true; } - }; - - - /// The base type of the edge iterators. - - /// The base type of the edge iterators. - /// - class Edge : public SymEdge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - Edge() { } - /// Copy constructor. - - /// Copy constructor. - /// - Edge(const Edge&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - Edge(Invalid) { } - /// Equality operator - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Edge) const { return true; } - /// Inequality operator - - /// \sa operator==(Node n) - /// - bool operator!=(Edge) const { return true; } - ///Comparison operator. - - ///This is a strict ordering between the nodes. - /// - ///This ordering can be different from the order in which NodeIt - ///goes through the nodes. - ///\todo Possibly we don't need it. - bool operator<(Edge) const { return true; } - }; - - /// 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. - /// Its usage is quite simple, for example you can count the number - /// of outgoing edges of a node \c n - /// in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; - /// \endcode - - class OutEdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - OutEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - OutEdgeIt(const OutEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - OutEdgeIt(Invalid) { } - /// This constructor sets the iterator to first outgoing edge. - - /// This constructor set the iterator to the first outgoing edge of - /// node - ///@param n the node - ///@param g the graph - OutEdgeIt(const StaticSymGraph& g, const Node& n) { } - /// Edge -> OutEdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - OutEdgeIt(const StaticSymGraph& g, const Edge& e) { } - ///Next outgoing edge - - /// Assign the iterator to the next - /// outgoing edge of the corresponding node. - OutEdgeIt& operator++() { return *this; } - }; - - /// This iterator goes trough the incoming edges of a node. - - /// This iterator goes trough the \e incoming edges of a certain node - /// of a graph. - /// Its usage is quite simple, for example you can count the number - /// of outgoing edges of a node \c n - /// in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; - /// \endcode - - class InEdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - InEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - InEdgeIt(const InEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - InEdgeIt(Invalid) { } - /// This constructor sets the iterator to first incoming edge. - - /// This constructor set the iterator to the first incoming edge of - /// node - ///@param n the node - ///@param g the graph - InEdgeIt(const StaticSymGraph& g, const Node& n) { } - /// Edge -> InEdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - InEdgeIt(const StaticSymGraph& g, const Edge& n) { } - /// Next incoming edge - - /// Assign the iterator to the next inedge of the corresponding node. - /// - InEdgeIt& operator++() { return *this; } - }; - /// This iterator goes through each symmetric edge. - - /// This iterator goes through each symmetric edge of a graph. - /// Its usage is quite simple, for example you can count the number - /// of symmetric edges in a graph \c g of type \c Graph as follows: - /// \code - /// int count=0; - /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count; - /// \endcode - class SymEdgeIt : public SymEdge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - SymEdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - SymEdgeIt(const SymEdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - SymEdgeIt(Invalid) { } - /// This constructor sets the iterator to first edge. - - /// This constructor set the iterator to the first edge of - /// node - ///@param g the graph - SymEdgeIt(const StaticSymGraph& g) { } - /// Edge -> EdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - SymEdgeIt(const StaticSymGraph&, const SymEdge&) { } - ///Next edge - - /// Assign the iterator to the next - /// edge of the corresponding node. - SymEdgeIt& operator++() { return *this; } - }; - /// This iterator goes through each edge. - - /// This iterator goes through each edge of a graph. - /// Its usage is quite simple, for example you can count the number - /// of edges in a graph \c g of type \c Graph as follows: - /// \code - /// int count=0; - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; - /// \endcode - class EdgeIt : public Edge { - public: - /// Default constructor - - /// @warning The default constructor sets the iterator - /// to an undefined value. - EdgeIt() { } - /// Copy constructor. - - /// Copy constructor. - /// - EdgeIt(const EdgeIt&) { } - /// Initialize the iterator to be invalid. - - /// Initialize the iterator to be invalid. - /// - EdgeIt(Invalid) { } - /// This constructor sets the iterator to first edge. - - /// This constructor set the iterator to the first edge of - /// node - ///@param g the graph - EdgeIt(const StaticSymGraph& g) { } - /// Edge -> EdgeIt conversion - - /// Sets the iterator to the value of the trivial iterator \c e. - /// This feature necessitates that each time we - /// iterate the edge-set, the iteration order is the same. - EdgeIt(const StaticSymGraph&, const Edge&) { } - ///Next edge - - /// Assign the iterator to the next - /// edge of the corresponding node. - EdgeIt& operator++() { return *this; } - }; - - /// First node of the graph. - - /// \retval i the first node. - /// \return the first node. - /// - NodeIt& first(NodeIt& i) const { return i; } - - /// The first incoming edge. - - /// The first incoming edge. - /// - InEdgeIt& first(InEdgeIt &i, Node) const { return i; } - /// The first outgoing edge. - - /// The first outgoing edge. - /// - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } - /// The first edge of the Graph. - - /// The first edge of the Graph. - /// - EdgeIt& first(EdgeIt& i) const { return i; } - /// The first symmetric edge of the Graph. - - /// The first symmetric edge of the Graph. - /// - SymEdgeIt& first(SymEdgeIt& i) const { return i; } - - ///Gives back the head node of an edge. - - ///Gives back the head node of an edge. - /// - Node head(Edge) const { return INVALID; } - ///Gives back the tail node of an edge. - - ///Gives back the tail node of an edge. - /// - Node tail(Edge) const { return INVALID; } - - ///Gives back the first node of an symmetric edge. - - ///Gives back the first node of an symmetric edge. - /// - Node head(SymEdge) const { return INVALID; } - ///Gives back the second node of an symmetric edge. - - ///Gives back the second node of an symmetric edge. - /// - Node tail(SymEdge) const { return INVALID; } - ///Gives back the \e id of a node. - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const Node&) const { return 0; } - ///Gives back the \e id of an edge. - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const Edge&) const { return 0; } - - ///\warning Not all graph structures provide this feature. - /// - ///\todo Should each graph provide \c id? - int id(const SymEdge&) const { return 0; } - - ///\e - - ///\todo Should it be in the concept? - /// - int nodeNum() const { return 0; } - ///\e - - ///\todo Should it be in the concept? - /// - int edgeNum() const { return 0; } - - ///\todo Should it be in the concept? - /// - int symEdgeNum() const { return 0; } - - - /// Gives back the forward directed edge of the symmetric edge. - Edge forward(SymEdge) const {return INVALID;} - - /// Gives back the backward directed edge of the symmetric edge. - Edge backward(SymEdge) const {return INVALID;}; - - /// Gives back the opposite of the edge. - Edge opposite(Edge) const {return INVALID;} - - ///Reference map of the nodes to type \c T. - /// \ingroup skeletons - ///Reference map of the nodes to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (NodeMap) - /// needs some extra attention! - template class NodeMap : public ReferenceMap< Node, T > - { - public: - - ///\e - NodeMap(const StaticSymGraph&) { } - ///\e - NodeMap(const StaticSymGraph&, T) { } - - ///Copy constructor - template NodeMap(const NodeMap&) { } - ///Assignment operator - template NodeMap& operator=(const NodeMap&) - { return *this; } - }; - - ///Reference map of the edges to type \c T. - - /// \ingroup skeletons - ///Reference map of the edges to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (EdgeMap) - /// needs some extra attention! - template class EdgeMap - : public ReferenceMap - { - public: - - ///\e - EdgeMap(const StaticSymGraph&) { } - ///\e - EdgeMap(const StaticSymGraph&, T) { } - - ///Copy constructor - template EdgeMap(const EdgeMap&) { } - ///Assignment operator - template EdgeMap &operator=(const EdgeMap&) - { return *this; } - }; - - ///Reference map of the edges to type \c T. - - /// \ingroup skeletons - ///Reference map of the symmetric edges to type \c T. - /// \sa Reference - /// \warning Making maps that can handle bool type (EdgeMap) - /// needs some extra attention! - template class SymEdgeMap - : public ReferenceMap - { - public: - - ///\e - SymEdgeMap(const StaticSymGraph&) { } - ///\e - SymEdgeMap(const StaticSymGraph&, T) { } - - ///Copy constructor - template SymEdgeMap(const SymEdgeMap&) { } - ///Assignment operator - template SymEdgeMap &operator=(const SymEdgeMap&) - { return *this; } - }; - }; - - - - /// An empty non-static graph class. - - /// This class provides everything that \ref StaticGraph - /// with additional functionality which enables to build a - /// graph from scratch. - class ExtendableSymGraph : public StaticSymGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - ExtendableSymGraph() { } - ///Add a new node to the graph. - - /// \return the new node. - /// - Node addNode() { return INVALID; } - ///Add a new edge to the graph. - - ///Add a new symmetric edge to the graph with tail node \c t - ///and head node \c h. - ///\return the new edge. - SymEdge addEdge(Node h, Node t) { return INVALID; } - - /// Resets the graph. - - /// This function deletes all edges and nodes of the graph. - /// It also frees the memory allocated to store them. - /// \todo It might belong to \ref ErasableGraph. - void clear() { } - }; - - /// An empty erasable graph class. - - /// This class is an extension of \ref ExtendableGraph. It also makes it - /// possible to erase edges or nodes. - class ErasableSymGraph : public ExtendableSymGraph - { - public: - /// Defalult constructor. - - /// Defalult constructor. - /// - ErasableSymGraph() { } - /// Deletes a node. - - /// Deletes node \c n node. - /// - void erase(Node n) { } - /// Deletes an edge. - - /// Deletes edge \c e edge. - /// - void erase(SymEdge e) { } - }; - - // @} - } //namespace skeleton -} //namespace lemon - - - -#endif // LEMON_SKELETON_GRAPH_H diff -r 75f749682240 -r c80ef5912903 src/lemon/smart_graph.h --- a/src/lemon/smart_graph.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/lemon/smart_graph.h Thu Nov 04 20:24:59 2004 +0000 @@ -229,8 +229,8 @@ ///It is also quite memory efficient, but at the price ///that it does not support node and edge deletion. ///It conforms to - ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept. - ///\sa skeleton::ExtendableGraph. + ///the \ref concept::ExtendableGraph "ExtendableGraph" concept. + ///\sa concept::ExtendableGraph. /// ///\todo Some member functions could be \c static. /// diff -r 75f749682240 -r c80ef5912903 src/test/bfs_test.cc --- a/src/test/bfs_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/bfs_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -17,7 +17,7 @@ #include "test_tools.h" #include #include -#include +#include using namespace lemon; @@ -26,7 +26,7 @@ void check_Bfs_Compile() { - typedef skeleton::StaticGraph Graph; + typedef concept::StaticGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; diff -r 75f749682240 -r c80ef5912903 src/test/dfs_test.cc --- a/src/test/dfs_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/dfs_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -17,7 +17,7 @@ #include "test_tools.h" #include #include -#include +#include using namespace lemon; @@ -26,7 +26,7 @@ void check_Dfs_SmartGraph_Compile() { - typedef skeleton::StaticGraph Graph; + typedef concept::StaticGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; diff -r 75f749682240 -r c80ef5912903 src/test/dijkstra_test.cc --- a/src/test/dijkstra_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/dijkstra_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -17,8 +17,8 @@ #include "test_tools.h" #include #include -#include -#include +#include +#include using namespace lemon; const int PET_SIZE =5; @@ -27,13 +27,13 @@ void check_Dijkstra_BinHeap_Compile() { typedef int VType; - typedef skeleton::StaticGraph Graph; + typedef concept::StaticGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; typedef Graph::EdgeIt EdgeIt; typedef Graph::NodeIt NodeIt; - typedef skeleton::ReadMap LengthMap; + typedef concept::ReadMap LengthMap; typedef Dijkstra DType; diff -r 75f749682240 -r c80ef5912903 src/test/graph_factory_test.cc --- a/src/test/graph_factory_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/graph_factory_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -16,8 +16,8 @@ #include #include -#include -#include +#include +#include #include #include @@ -68,22 +68,22 @@ } //Compile Graph -template void lemon::skeleton::checkCompileStaticGraph -(skeleton::StaticGraph &); +template void lemon::concept::checkCompileStaticGraph +(concept::StaticGraph &); template -void lemon::skeleton::checkCompileExtendableGraph -(skeleton::ExtendableGraph &); +void lemon::concept::checkCompileExtendableGraph +(concept::ExtendableGraph &); template -void lemon::skeleton::checkCompileErasableGraph -(skeleton::ErasableGraph &); +void lemon::concept::checkCompileErasableGraph +(concept::ErasableGraph &); //Compile SmartGraph template -void lemon::skeleton::checkCompileExtendableGraph(SmartGraph &); +void lemon::concept::checkCompileExtendableGraph(SmartGraph &); template -void lemon::skeleton::checkCompileGraphFindEdge(SmartGraph &); +void lemon::concept::checkCompileGraphFindEdge(SmartGraph &); //Compile SymSmartGraph //template void hugo::checkCompileGraph(SymSmartGraph &); @@ -91,11 +91,11 @@ //Compile ListGraph template -void lemon::skeleton::checkCompileExtendableGraph(ListGraph &); +void lemon::concept::checkCompileExtendableGraph(ListGraph &); template -void lemon::skeleton::checkCompileErasableGraph(ListGraph &); +void lemon::concept::checkCompileErasableGraph(ListGraph &); template -void lemon::skeleton::checkCompileGraphFindEdge(ListGraph &); +void lemon::concept::checkCompileGraphFindEdge(ListGraph &); //Compile SymListGraph @@ -104,9 +104,9 @@ //template void hugo::checkCompileGraphFindEdge(SymListGraph &); //Compile FullGraph -template void lemon::skeleton::checkCompileStaticGraph(FullGraph &); +template void lemon::concept::checkCompileStaticGraph(FullGraph &); template -void lemon::skeleton::checkCompileGraphFindEdge(FullGraph &); +void lemon::concept::checkCompileGraphFindEdge(FullGraph &); int main() @@ -141,7 +141,7 @@ // Some map tests. // FIXME: These shouldn't be here. - using namespace skeleton; + using namespace concept; function_requires< ReadMapConcept< ReadMap > >(); function_requires< WriteMapConcept< WriteMap > >(); function_requires< ReadWriteMapConcept< ReadWriteMap > >(); diff -r 75f749682240 -r c80ef5912903 src/test/graph_test.cc --- a/src/test/graph_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/graph_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -3,7 +3,7 @@ #include #include -#include +#include #include #include #include @@ -14,7 +14,7 @@ using namespace lemon; -using namespace lemon::skeleton; +using namespace lemon::concept; int main() { diff -r 75f749682240 -r c80ef5912903 src/test/graph_wrapper_test.cc --- a/src/test/graph_wrapper_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/graph_wrapper_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -18,7 +18,7 @@ #include #include -#include +#include #include #include @@ -35,7 +35,7 @@ */ using namespace lemon; -using namespace lemon::skeleton; +using namespace lemon::concept; typedef SmartGraph Graph; diff -r 75f749682240 -r c80ef5912903 src/test/kruskal_test.cc --- a/src/test/kruskal_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/kruskal_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -21,8 +21,8 @@ #include #include #include -#include -#include +#include +#include using namespace std; @@ -30,10 +30,10 @@ void checkCompileKruskal() { - skeleton::WriteMap w; + concept::WriteMap w; - kruskalEdgeMap(skeleton::StaticGraph(), - skeleton::ReadMap(), + kruskalEdgeMap(concept::StaticGraph(), + concept::ReadMap(), w); } diff -r 75f749682240 -r c80ef5912903 src/test/new_graph_test.cc --- a/src/test/new_graph_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/new_graph_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -14,10 +14,10 @@ * */ -#include +#include // #include -using namespace lemon::skeleton; +using namespace lemon::concept; // Borrowed from boost: template inline void ignore_unused_variable_warning(const T&) { } diff -r 75f749682240 -r c80ef5912903 src/test/path_test.cc --- a/src/test/path_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/path_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -16,13 +16,13 @@ #include #include -#include +#include #include #include using namespace std; using namespace lemon; -using namespace skeleton; +using namespace lemon::concept; template void checkCompilePath(Path &P) { @@ -86,7 +86,7 @@ } -template void checkCompilePath< skeleton::Path >(skeleton::Path &); +template void checkCompilePath< concept::Path >(concept::Path &); template void checkCompilePath< DirPath >(DirPath &); template void checkCompilePath< UndirPath >(UndirPath &); diff -r 75f749682240 -r c80ef5912903 src/test/preflow_test.cc --- a/src/test/preflow_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/preflow_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -21,21 +21,21 @@ #include #include #include -#include -#include +#include +#include using namespace lemon; void check_Preflow() { typedef int VType; - typedef skeleton::StaticGraph Graph; + typedef concept::StaticGraph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; - typedef skeleton::ReadMap CapMap; - typedef skeleton::ReadWriteMap FlowMap; - typedef skeleton::ReadWriteMap CutMap; + typedef concept::ReadMap CapMap; + typedef concept::ReadWriteMap FlowMap; + typedef concept::ReadWriteMap CutMap; typedef Preflow PType; diff -r 75f749682240 -r c80ef5912903 src/test/sym_graph_test.cc --- a/src/test/sym_graph_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/sym_graph_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -16,7 +16,7 @@ #include -#include +#include #include #include @@ -54,26 +54,26 @@ } //Compile Graph -template void lemon::checkCompileStaticSymGraph -(skeleton::StaticSymGraph &); +template void lemon::checkCompileStaticSymGraph +(concept::StaticSymGraph &); -template void lemon::checkCompileSymGraph -(skeleton::ExtendableSymGraph &); +template void lemon::checkCompileSymGraph +(concept::ExtendableSymGraph &); -template void lemon::checkCompileErasableSymGraph -(skeleton::ErasableSymGraph &); +template void lemon::checkCompileErasableSymGraph +(concept::ErasableSymGraph &); //Compile SymSmartGraph template void lemon::checkCompileSymGraph(SymSmartGraph &); template -void lemon::skeleton::checkCompileGraphFindEdge(SymSmartGraph &); +void lemon::concept::checkCompileGraphFindEdge(SymSmartGraph &); //Compile SymListGraph template void lemon::checkCompileSymGraph(SymListGraph &); template void lemon::checkCompileErasableSymGraph(SymListGraph &); template -void lemon::skeleton::checkCompileGraphFindEdge(SymListGraph &); +void lemon::concept::checkCompileGraphFindEdge(SymListGraph &); int main() { diff -r 75f749682240 -r c80ef5912903 src/test/sym_graph_test.h --- a/src/test/sym_graph_test.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/test/sym_graph_test.h Thu Nov 04 20:24:59 2004 +0000 @@ -27,7 +27,7 @@ /// \e - /// \todo This should go to lemon/skeleton/symgraph.h + /// \todo This should go to lemon/concept/symgraph.h /// template void checkCompileStaticSymGraph(Graph &G) { @@ -40,7 +40,7 @@ typedef typename Graph::InEdgeIt InEdgeIt; typedef typename Graph::OutEdgeIt OutEdgeIt; - lemon::skeleton::checkCompileStaticGraph(G); + lemon::concept::checkCompileStaticGraph(G); { SymEdge i; SymEdge j(i); SymEdge k(INVALID); @@ -157,7 +157,7 @@ template void checkCompileErasableSymGraph(Graph &G) { checkCompileSymGraph(G); - lemon::skeleton::checkCompileGraphEraseNode(G); + lemon::concept::checkCompileGraphEraseNode(G); checkCompileSymGraphEraseSymEdge(G); } diff -r 75f749682240 -r c80ef5912903 src/work/Doxyfile --- a/src/work/Doxyfile Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/Doxyfile Thu Nov 04 20:24:59 2004 +0000 @@ -396,7 +396,7 @@ ../../doc/maps.dox ../../doc/coding_style.dox \ ../../doc/groups.dox \ ../lemon \ - ../lemon/skeletons \ + ../lemon/concept \ ../test/test_tools.h \ klao/path.h \ klao/debug.h \ diff -r 75f749682240 -r c80ef5912903 src/work/alpar/dijkstra.h --- a/src/work/alpar/dijkstra.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/alpar/dijkstra.h Thu Nov 04 20:24:59 2004 +0000 @@ -100,11 +100,11 @@ ///This class provides an efficient implementation of %Dijkstra algorithm. ///The edge lengths are passed to the algorithm using a - ///\ref skeleton::ReadMap "ReadMap", + ///\ref concept::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. /// ///The type of the length is determined by the - ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. + ///\ref concept::ReadMap::ValueType "ValueType" of the length map. /// ///It is also possible to change the underlying priority heap. /// @@ -117,7 +117,7 @@ ///lengths of the edges. It is read once for each edge, so the map ///may involve in relatively time consuming process to compute the edge ///length if it is necessary. The default map type is - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap". + ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap". ///The value of LM is not used directly by Dijkstra, it ///is only passed to \ref DijkstraDefaultTraits. ///\param TR Traits class to set various data types used by the algorithm. diff -r 75f749682240 -r c80ef5912903 src/work/alpar/list_graph_demo.cc --- a/src/work/alpar/list_graph_demo.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/alpar/list_graph_demo.cc Thu Nov 04 20:24:59 2004 +0000 @@ -1,5 +1,5 @@ #include -#include +#include #include #include diff -r 75f749682240 -r c80ef5912903 src/work/marci/bfs_mm_test.cc --- a/src/work/marci/bfs_mm_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/marci/bfs_mm_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -17,7 +17,7 @@ #include #include #include -#include +#include using namespace lemon; @@ -26,7 +26,7 @@ void check_Bfs_Compile() { - typedef skeleton::StaticGraph Graph; + typedef concept::StaticGraph Graph; typedef Graph::Edge Edge; typedef Graph::Node Node; diff -r 75f749682240 -r c80ef5912903 src/work/peter/path/path.h --- a/src/work/peter/path/path.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/peter/path/path.h Thu Nov 04 20:24:59 2004 +0000 @@ -12,7 +12,7 @@ using a standard Builder subclass. This make is easy to have e.g. the Dijkstra algorithm to store its result in any kind of path structure. -\sa lemon::skeleton::Path +\sa lemon::concept::Path */ diff -r 75f749682240 -r c80ef5912903 src/work/peter/path/path_skeleton.h --- a/src/work/peter/path/path_skeleton.h Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/peter/path/path_skeleton.h Thu Nov 04 20:24:59 2004 +0000 @@ -1,7 +1,7 @@ #define SKELETON // -*- c++ -*- // -///\ingroup skeletons +///\ingroup concept ///\file ///\brief Classes for representing paths in graphs. @@ -11,12 +11,12 @@ #include namespace lemon { - namespace skeleton { - /// \addtogroup skeletons + namespace concept { + /// \addtogroup concept /// @{ - //! \brief A skeletom structure for representing directed paths in a graph. + //! \brief A skeleton structure for representing directed paths in a graph. //! //! A skeleton structure for representing directed paths in a graph. //! \param GR The graph type in which the path is. @@ -85,7 +85,7 @@ /** * \brief Iterator class to iterate on the edges of the paths * - * \ingroup skeletons + * \ingroup concept * This class is used to iterate on the edges of the paths * * Of course it converts to Graph::Edge @@ -118,7 +118,7 @@ /** * \brief Iterator class to iterate on the nodes of the paths * - * \ingroup skeletons + * \ingroup concept * This class is used to iterate on the nodes of the paths * * Of course it converts to Graph::Node. @@ -153,7 +153,7 @@ /** * \brief Class to build paths * - * \ingroup skeletons + * \ingroup concept * This class is used to fill a path with edges. * * You can push new edges to the front and to the back of the path in diff -r 75f749682240 -r c80ef5912903 src/work/peter/path/path_test.cc --- a/src/work/peter/path/path_test.cc Thu Nov 04 18:52:31 2004 +0000 +++ b/src/work/peter/path/path_test.cc Thu Nov 04 20:24:59 2004 +0000 @@ -6,7 +6,7 @@ using namespace std; using namespace lemon; -using namespace skeleton; +using namespace concept; bool passed = true;