1.1 --- a/src/lemon/skeletons/graph.h Mon Oct 25 13:29:46 2004 +0000
1.2 +++ b/src/lemon/skeletons/graph.h Wed Oct 27 22:38:50 2004 +0000
1.3 @@ -23,6 +23,8 @@
1.4
1.5 #include <lemon/invalid.h>
1.6 #include <lemon/skeletons/maps.h>
1.7 +#include <lemon/concept_check.h>
1.8 +#include <lemon/skeletons/graph_component.h>
1.9
1.10 namespace lemon {
1.11 namespace skeleton {
1.12 @@ -30,734 +32,883 @@
1.13 /// \addtogroup skeletons
1.14 /// @{
1.15
1.16 - /// An empty static graph class.
1.17 +// /// An empty static graph class.
1.18
1.19 - /// This class provides all the common features of a graph structure,
1.20 - /// however completely without implementations and real data structures
1.21 - /// behind the interface.
1.22 - /// All graph algorithms should compile with this class, but it will not
1.23 - /// run properly, of course.
1.24 - ///
1.25 - /// It can be used for checking the interface compatibility,
1.26 - /// or it can serve as a skeleton of a new graph structure.
1.27 - ///
1.28 - /// Also, you will find here the full documentation of a certain graph
1.29 - /// feature, the documentation of a real graph imlementation
1.30 - /// like @ref ListGraph or
1.31 - /// @ref SmartGraph will just refer to this structure.
1.32 - ///
1.33 - /// \todo A pages describing the concept of concept description would
1.34 - /// be nice.
1.35 - class StaticGraph
1.36 - {
1.37 +// /// This class provides all the common features of a graph structure,
1.38 +// /// however completely without implementations and real data structures
1.39 +// /// behind the interface.
1.40 +// /// All graph algorithms should compile with this class, but it will not
1.41 +// /// run properly, of course.
1.42 +// ///
1.43 +// /// It can be used for checking the interface compatibility,
1.44 +// /// or it can serve as a skeleton of a new graph structure.
1.45 +// ///
1.46 +// /// Also, you will find here the full documentation of a certain graph
1.47 +// /// feature, the documentation of a real graph imlementation
1.48 +// /// like @ref ListGraph or
1.49 +// /// @ref SmartGraph will just refer to this structure.
1.50 +// ///
1.51 +// /// \todo A pages describing the concept of concept description would
1.52 +// /// be nice.
1.53 +// class StaticGraph
1.54 +// {
1.55 +// public:
1.56 +// /// Defalult constructor.
1.57 +
1.58 +// /// Defalult constructor.
1.59 +// ///
1.60 +// StaticGraph() { }
1.61 +// ///Copy consructor.
1.62 +
1.63 +// // ///\todo It is not clear, what we expect from a copy constructor.
1.64 +// // ///E.g. How to assign the nodes/edges to each other? What about maps?
1.65 +// // StaticGraph(const StaticGraph& g) { }
1.66 +
1.67 +// /// The base type of node iterators,
1.68 +// /// or in other words, the trivial node iterator.
1.69 +
1.70 +// /// This is the base type of each node iterator,
1.71 +// /// thus each kind of node iterator converts to this.
1.72 +// /// More precisely each kind of node iterator should be inherited
1.73 +// /// from the trivial node iterator.
1.74 +// class Node {
1.75 +// public:
1.76 +// /// Default constructor
1.77 +
1.78 +// /// @warning The default constructor sets the iterator
1.79 +// /// to an undefined value.
1.80 +// Node() { }
1.81 +// /// Copy constructor.
1.82 +
1.83 +// /// Copy constructor.
1.84 +// ///
1.85 +// Node(const Node&) { }
1.86 +
1.87 +// /// Invalid constructor \& conversion.
1.88 +
1.89 +// /// This constructor initializes the iterator to be invalid.
1.90 +// /// \sa Invalid for more details.
1.91 +// Node(Invalid) { }
1.92 +// /// Equality operator
1.93 +
1.94 +// /// Two iterators are equal if and only if they point to the
1.95 +// /// same object or both are invalid.
1.96 +// bool operator==(Node) const { return true; }
1.97 +
1.98 +// /// Inequality operator
1.99 +
1.100 +// /// \sa operator==(Node n)
1.101 +// ///
1.102 +// bool operator!=(Node) const { return true; }
1.103 +
1.104 +// ///Comparison operator.
1.105 +
1.106 +// ///This is a strict ordering between the nodes.
1.107 +// ///
1.108 +// ///This ordering can be different from the order in which NodeIt
1.109 +// ///goes through the nodes.
1.110 +// ///\todo Possibly we don't need it.
1.111 +// bool operator<(Node) const { return true; }
1.112 +// };
1.113 +
1.114 +// /// This iterator goes through each node.
1.115 +
1.116 +// /// This iterator goes through each node.
1.117 +// /// Its usage is quite simple, for example you can count the number
1.118 +// /// of nodes in graph \c g of type \c Graph like this:
1.119 +// /// \code
1.120 +// /// int count=0;
1.121 +// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
1.122 +// /// \endcode
1.123 +// class NodeIt : public Node {
1.124 +// public:
1.125 +// /// Default constructor
1.126 +
1.127 +// /// @warning The default constructor sets the iterator
1.128 +// /// to an undefined value.
1.129 +// NodeIt() { }
1.130 +// /// Copy constructor.
1.131 +
1.132 +// /// Copy constructor.
1.133 +// ///
1.134 +// NodeIt(const NodeIt&) { }
1.135 +// /// Invalid constructor \& conversion.
1.136 +
1.137 +// /// Initialize the iterator to be invalid.
1.138 +// /// \sa Invalid for more details.
1.139 +// NodeIt(Invalid) { }
1.140 +// /// Sets the iterator to the first node.
1.141 +
1.142 +// /// Sets the iterator to the first node of \c g.
1.143 +// ///
1.144 +// NodeIt(const StaticGraph& g) { }
1.145 +// /// Node -> NodeIt conversion.
1.146 +
1.147 +// /// Sets the iterator to the node of \c g pointed by the trivial
1.148 +// /// iterator n.
1.149 +// /// This feature necessitates that each time we
1.150 +// /// iterate the edge-set, the iteration order is the same.
1.151 +// NodeIt(const StaticGraph& g, const Node& n) { }
1.152 +// /// Next node.
1.153 +
1.154 +// /// Assign the iterator to the next node.
1.155 +// ///
1.156 +// NodeIt& operator++() { return *this; }
1.157 +// };
1.158 +
1.159 +
1.160 +// /// The base type of the edge iterators.
1.161 +
1.162 +// /// The base type of the edge iterators.
1.163 +// ///
1.164 +// class Edge {
1.165 +// public:
1.166 +// /// Default constructor
1.167 +
1.168 +// /// @warning The default constructor sets the iterator
1.169 +// /// to an undefined value.
1.170 +// Edge() { }
1.171 +// /// Copy constructor.
1.172 +
1.173 +// /// Copy constructor.
1.174 +// ///
1.175 +// Edge(const Edge&) { }
1.176 +// /// Initialize the iterator to be invalid.
1.177 +
1.178 +// /// Initialize the iterator to be invalid.
1.179 +// ///
1.180 +// Edge(Invalid) { }
1.181 +// /// Equality operator
1.182 +
1.183 +// /// Two iterators are equal if and only if they point to the
1.184 +// /// same object or both are invalid.
1.185 +// bool operator==(Edge) const { return true; }
1.186 +// /// Inequality operator
1.187 +
1.188 +// /// \sa operator==(Node n)
1.189 +// ///
1.190 +// bool operator!=(Edge) const { return true; }
1.191 +// ///Comparison operator.
1.192 +
1.193 +// ///This is a strict ordering between the nodes.
1.194 +// ///
1.195 +// ///This ordering can be different from the order in which NodeIt
1.196 +// ///goes through the nodes.
1.197 +// ///\todo Possibly we don't need it.
1.198 +// bool operator<(Edge) const { return true; }
1.199 +// };
1.200 +
1.201 +// /// This iterator goes trough the outgoing edges of a node.
1.202 +
1.203 +// /// This iterator goes trough the \e outgoing edges of a certain node
1.204 +// /// of a graph.
1.205 +// /// Its usage is quite simple, for example you can count the number
1.206 +// /// of outgoing edges of a node \c n
1.207 +// /// in graph \c g of type \c Graph as follows.
1.208 +// /// \code
1.209 +// /// int count=0;
1.210 +// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.211 +// /// \endcode
1.212 +
1.213 +// class OutEdgeIt : public Edge {
1.214 +// public:
1.215 +// /// Default constructor
1.216 +
1.217 +// /// @warning The default constructor sets the iterator
1.218 +// /// to an undefined value.
1.219 +// OutEdgeIt() { }
1.220 +// /// Copy constructor.
1.221 +
1.222 +// /// Copy constructor.
1.223 +// ///
1.224 +// OutEdgeIt(const OutEdgeIt&) { }
1.225 +// /// Initialize the iterator to be invalid.
1.226 +
1.227 +// /// Initialize the iterator to be invalid.
1.228 +// ///
1.229 +// OutEdgeIt(Invalid) { }
1.230 +// /// This constructor sets the iterator to first outgoing edge.
1.231 +
1.232 +// /// This constructor set the iterator to the first outgoing edge of
1.233 +// /// node
1.234 +// ///@param n the node
1.235 +// ///@param g the graph
1.236 +// OutEdgeIt(const StaticGraph& g, const Node& n) { }
1.237 +// /// Edge -> OutEdgeIt conversion
1.238 +
1.239 +// /// Sets the iterator to the value of the trivial iterator \c e.
1.240 +// /// This feature necessitates that each time we
1.241 +// /// iterate the edge-set, the iteration order is the same.
1.242 +// OutEdgeIt(const StaticGraph& g, const Edge& e) { }
1.243 +// ///Next outgoing edge
1.244 +
1.245 +// /// Assign the iterator to the next
1.246 +// /// outgoing edge of the corresponding node.
1.247 +// OutEdgeIt& operator++() { return *this; }
1.248 +// };
1.249 +
1.250 +// /// This iterator goes trough the incoming edges of a node.
1.251 +
1.252 +// /// This iterator goes trough the \e incoming edges of a certain node
1.253 +// /// of a graph.
1.254 +// /// Its usage is quite simple, for example you can count the number
1.255 +// /// of outgoing edges of a node \c n
1.256 +// /// in graph \c g of type \c Graph as follows.
1.257 +// /// \code
1.258 +// /// int count=0;
1.259 +// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.260 +// /// \endcode
1.261 +
1.262 +// class InEdgeIt : public Edge {
1.263 +// public:
1.264 +// /// Default constructor
1.265 +
1.266 +// /// @warning The default constructor sets the iterator
1.267 +// /// to an undefined value.
1.268 +// InEdgeIt() { }
1.269 +// /// Copy constructor.
1.270 +
1.271 +// /// Copy constructor.
1.272 +// ///
1.273 +// InEdgeIt(const InEdgeIt&) { }
1.274 +// /// Initialize the iterator to be invalid.
1.275 +
1.276 +// /// Initialize the iterator to be invalid.
1.277 +// ///
1.278 +// InEdgeIt(Invalid) { }
1.279 +// /// This constructor sets the iterator to first incoming edge.
1.280 +
1.281 +// /// This constructor set the iterator to the first incoming edge of
1.282 +// /// node
1.283 +// ///@param n the node
1.284 +// ///@param g the graph
1.285 +// InEdgeIt(const StaticGraph& g, const Node& n) { }
1.286 +// /// Edge -> InEdgeIt conversion
1.287 +
1.288 +// /// Sets the iterator to the value of the trivial iterator \c e.
1.289 +// /// This feature necessitates that each time we
1.290 +// /// iterate the edge-set, the iteration order is the same.
1.291 +// InEdgeIt(const StaticGraph& g, const Edge& n) { }
1.292 +// /// Next incoming edge
1.293 +
1.294 +// /// Assign the iterator to the next inedge of the corresponding node.
1.295 +// ///
1.296 +// InEdgeIt& operator++() { return *this; }
1.297 +// };
1.298 +// /// This iterator goes through each edge.
1.299 +
1.300 +// /// This iterator goes through each edge of a graph.
1.301 +// /// Its usage is quite simple, for example you can count the number
1.302 +// /// of edges in a graph \c g of type \c Graph as follows:
1.303 +// /// \code
1.304 +// /// int count=0;
1.305 +// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.306 +// /// \endcode
1.307 +// class EdgeIt : public Edge {
1.308 +// public:
1.309 +// /// Default constructor
1.310 +
1.311 +// /// @warning The default constructor sets the iterator
1.312 +// /// to an undefined value.
1.313 +// EdgeIt() { }
1.314 +// /// Copy constructor.
1.315 +
1.316 +// /// Copy constructor.
1.317 +// ///
1.318 +// EdgeIt(const EdgeIt&) { }
1.319 +// /// Initialize the iterator to be invalid.
1.320 +
1.321 +// /// Initialize the iterator to be invalid.
1.322 +// ///
1.323 +// EdgeIt(Invalid) { }
1.324 +// /// This constructor sets the iterator to first edge.
1.325 +
1.326 +// /// This constructor set the iterator to the first edge of
1.327 +// /// node
1.328 +// ///@param g the graph
1.329 +// EdgeIt(const StaticGraph& g) { }
1.330 +// /// Edge -> EdgeIt conversion
1.331 +
1.332 +// /// Sets the iterator to the value of the trivial iterator \c e.
1.333 +// /// This feature necessitates that each time we
1.334 +// /// iterate the edge-set, the iteration order is the same.
1.335 +// EdgeIt(const StaticGraph&, const Edge&) { }
1.336 +// ///Next edge
1.337 +
1.338 +// /// Assign the iterator to the next
1.339 +// /// edge of the corresponding node.
1.340 +// EdgeIt& operator++() { return *this; }
1.341 +// };
1.342 +
1.343 +// /// First node of the graph.
1.344 +
1.345 +// /// \retval i the first node.
1.346 +// /// \return the first node.
1.347 +// ///
1.348 +// NodeIt& first(NodeIt& i) const { return i; }
1.349 +
1.350 +// /// The first incoming edge.
1.351 +
1.352 +// /// The first incoming edge.
1.353 +// ///
1.354 +// InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
1.355 +// /// The first outgoing edge.
1.356 +
1.357 +// /// The first outgoing edge.
1.358 +// ///
1.359 +// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
1.360 +// /// The first edge of the Graph.
1.361 +
1.362 +// /// The first edge of the Graph.
1.363 +// ///
1.364 +// EdgeIt& first(EdgeIt& i) const { return i; }
1.365 +
1.366 +// ///Gives back the head node of an edge.
1.367 +
1.368 +// ///Gives back the head node of an edge.
1.369 +// ///
1.370 +// Node head(Edge) const { return INVALID; }
1.371 +// ///Gives back the tail node of an edge.
1.372 +
1.373 +// ///Gives back the tail node of an edge.
1.374 +// ///
1.375 +// Node tail(Edge) const { return INVALID; }
1.376 +
1.377 +// ///Gives back the \e id of a node.
1.378 +
1.379 +// ///\warning Not all graph structures provide this feature.
1.380 +// ///
1.381 +// ///\todo Should each graph provide \c id?
1.382 +// int id(const Node&) const { return 0; }
1.383 +// ///Gives back the \e id of an edge.
1.384 +
1.385 +// ///\warning Not all graph structures provide this feature.
1.386 +// ///
1.387 +// ///\todo Should each graph provide \c id?
1.388 +// int id(const Edge&) const { return 0; }
1.389 +
1.390 +// ///\e
1.391 +
1.392 +// ///\todo Should it be in the concept?
1.393 +// ///
1.394 +// int nodeNum() const { return 0; }
1.395 +// ///\e
1.396 +
1.397 +// ///\todo Should it be in the concept?
1.398 +// ///
1.399 +// int edgeNum() const { return 0; }
1.400 +
1.401 +
1.402 +// ///Reference map of the nodes to type \c T.
1.403 +
1.404 +// /// \ingroup skeletons
1.405 +// ///Reference map of the nodes to type \c T.
1.406 +// /// \sa Reference
1.407 +// /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.408 +// /// needs some extra attention!
1.409 +// template<class T> class NodeMap : public ReferenceMap< Node, T >
1.410 +// {
1.411 +// public:
1.412 +
1.413 +// ///\e
1.414 +// NodeMap(const StaticGraph&) { }
1.415 +// ///\e
1.416 +// NodeMap(const StaticGraph&, T) { }
1.417 +
1.418 +// ///Copy constructor
1.419 +// template<typename TT> NodeMap(const NodeMap<TT>&) { }
1.420 +// ///Assignment operator
1.421 +// template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
1.422 +// { return *this; }
1.423 +// };
1.424 +
1.425 +// ///Reference map of the edges to type \c T.
1.426 +
1.427 +// /// \ingroup skeletons
1.428 +// ///Reference map of the edges to type \c T.
1.429 +// /// \sa Reference
1.430 +// /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.431 +// /// needs some extra attention!
1.432 +// template<class T> class EdgeMap
1.433 +// : public ReferenceMap<Edge,T>
1.434 +// {
1.435 +// public:
1.436 +
1.437 +// ///\e
1.438 +// EdgeMap(const StaticGraph&) { }
1.439 +// ///\e
1.440 +// EdgeMap(const StaticGraph&, T) { }
1.441 +
1.442 +// ///Copy constructor
1.443 +// template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
1.444 +// ///Assignment operator
1.445 +// template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
1.446 +// { return *this; }
1.447 +// };
1.448 +// };
1.449 +
1.450 +// struct DummyType {
1.451 +// int value;
1.452 +// DummyType() {}
1.453 +// DummyType(int p) : value(p) {}
1.454 +// DummyType& operator=(int p) { value = p; return *this;}
1.455 +// };
1.456 +
1.457 +// ///\brief Checks whether \c G meets the
1.458 +// ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
1.459 +// template<class Graph> void checkCompileStaticGraph(Graph &G)
1.460 +// {
1.461 +// typedef typename Graph::Node Node;
1.462 +// typedef typename Graph::NodeIt NodeIt;
1.463 +// typedef typename Graph::Edge Edge;
1.464 +// typedef typename Graph::EdgeIt EdgeIt;
1.465 +// typedef typename Graph::InEdgeIt InEdgeIt;
1.466 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.467 +
1.468 +// {
1.469 +// Node i; Node j(i); Node k(INVALID);
1.470 +// i=j;
1.471 +// bool b; b=true;
1.472 +// b=(i==INVALID); b=(i!=INVALID);
1.473 +// b=(i==j); b=(i!=j); b=(i<j);
1.474 +// }
1.475 +// {
1.476 +// NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
1.477 +// i=j;
1.478 +// j=G.first(i);
1.479 +// j=++i;
1.480 +// bool b; b=true;
1.481 +// b=(i==INVALID); b=(i!=INVALID);
1.482 +// Node n(i);
1.483 +// n=i;
1.484 +// b=(i==j); b=(i!=j); b=(i<j);
1.485 +// //Node ->NodeIt conversion
1.486 +// NodeIt ni(G,n);
1.487 +// }
1.488 +// {
1.489 +// Edge i; Edge j(i); Edge k(INVALID);
1.490 +// i=j;
1.491 +// bool b; b=true;
1.492 +// b=(i==INVALID); b=(i!=INVALID);
1.493 +// b=(i==j); b=(i!=j); b=(i<j);
1.494 +// }
1.495 +// {
1.496 +// EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
1.497 +// i=j;
1.498 +// j=G.first(i);
1.499 +// j=++i;
1.500 +// bool b; b=true;
1.501 +// b=(i==INVALID); b=(i!=INVALID);
1.502 +// Edge e(i);
1.503 +// e=i;
1.504 +// b=(i==j); b=(i!=j); b=(i<j);
1.505 +// //Edge ->EdgeIt conversion
1.506 +// EdgeIt ei(G,e);
1.507 +// }
1.508 +// {
1.509 +// Node n;
1.510 +// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
1.511 +// i=j;
1.512 +// j=G.first(i,n);
1.513 +// j=++i;
1.514 +// bool b; b=true;
1.515 +// b=(i==INVALID); b=(i!=INVALID);
1.516 +// Edge e(i);
1.517 +// e=i;
1.518 +// b=(i==j); b=(i!=j); b=(i<j);
1.519 +// //Edge ->InEdgeIt conversion
1.520 +// InEdgeIt ei(G,e);
1.521 +// }
1.522 +// {
1.523 +// Node n;
1.524 +// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
1.525 +// i=j;
1.526 +// j=G.first(i,n);
1.527 +// j=++i;
1.528 +// bool b; b=true;
1.529 +// b=(i==INVALID); b=(i!=INVALID);
1.530 +// Edge e(i);
1.531 +// e=i;
1.532 +// b=(i==j); b=(i!=j); b=(i<j);
1.533 +// //Edge ->OutEdgeIt conversion
1.534 +// OutEdgeIt ei(G,e);
1.535 +// }
1.536 +// {
1.537 +// Node n,m;
1.538 +// n=m=INVALID;
1.539 +// Edge e;
1.540 +// e=INVALID;
1.541 +// n=G.tail(e);
1.542 +// n=G.head(e);
1.543 +// }
1.544 +// // id tests
1.545 +// { Node n; int i=G.id(n); i=i; }
1.546 +// { Edge e; int i=G.id(e); i=i; }
1.547 +// //NodeMap tests
1.548 +// {
1.549 +// Node k;
1.550 +// typename Graph::template NodeMap<int> m(G);
1.551 +// //Const map
1.552 +// typename Graph::template NodeMap<int> const &cm = m;
1.553 +// //Inicialize with default value
1.554 +// typename Graph::template NodeMap<int> mdef(G,12);
1.555 +// //Copy
1.556 +// typename Graph::template NodeMap<int> mm(cm);
1.557 +// //Copy from another type
1.558 +// typename Graph::template NodeMap<double> dm(cm);
1.559 +// //Copy to more complex type
1.560 +// typename Graph::template NodeMap<DummyType> em(cm);
1.561 +// int v;
1.562 +// v=m[k]; m[k]=v; m.set(k,v);
1.563 +// v=cm[k];
1.564 +
1.565 +// m=cm;
1.566 +// dm=cm; //Copy from another type
1.567 +// em=cm; //Copy to more complex type
1.568 +// {
1.569 +// //Check the typedef's
1.570 +// typename Graph::template NodeMap<int>::ValueType val;
1.571 +// val=1;
1.572 +// typename Graph::template NodeMap<int>::KeyType key;
1.573 +// key = typename Graph::NodeIt(G);
1.574 +// }
1.575 +// }
1.576 +// { //bool NodeMap
1.577 +// Node k;
1.578 +// typename Graph::template NodeMap<bool> m(G);
1.579 +// typename Graph::template NodeMap<bool> const &cm = m; //Const map
1.580 +// //Inicialize with default value
1.581 +// typename Graph::template NodeMap<bool> mdef(G,12);
1.582 +// typename Graph::template NodeMap<bool> mm(cm); //Copy
1.583 +// typename Graph::template NodeMap<int> dm(cm); //Copy from another type
1.584 +// bool v;
1.585 +// v=m[k]; m[k]=v; m.set(k,v);
1.586 +// v=cm[k];
1.587 +
1.588 +// m=cm;
1.589 +// dm=cm; //Copy from another type
1.590 +// m=dm; //Copy to another type
1.591 +
1.592 +// {
1.593 +// //Check the typedef's
1.594 +// typename Graph::template NodeMap<bool>::ValueType val;
1.595 +// val=true;
1.596 +// typename Graph::template NodeMap<bool>::KeyType key;
1.597 +// key= typename Graph::NodeIt(G);
1.598 +// }
1.599 +// }
1.600 +// //EdgeMap tests
1.601 +// {
1.602 +// Edge k;
1.603 +// typename Graph::template EdgeMap<int> m(G);
1.604 +// typename Graph::template EdgeMap<int> const &cm = m; //Const map
1.605 +// //Inicialize with default value
1.606 +// typename Graph::template EdgeMap<int> mdef(G,12);
1.607 +// typename Graph::template EdgeMap<int> mm(cm); //Copy
1.608 +// typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
1.609 +// int v;
1.610 +// v=m[k]; m[k]=v; m.set(k,v);
1.611 +// v=cm[k];
1.612 +
1.613 +// m=cm;
1.614 +// dm=cm; //Copy from another type
1.615 +// {
1.616 +// //Check the typedef's
1.617 +// typename Graph::template EdgeMap<int>::ValueType val;
1.618 +// val=1;
1.619 +// typename Graph::template EdgeMap<int>::KeyType key;
1.620 +// key= typename Graph::EdgeIt(G);
1.621 +// }
1.622 +// }
1.623 +// { //bool EdgeMap
1.624 +// Edge k;
1.625 +// typename Graph::template EdgeMap<bool> m(G);
1.626 +// typename Graph::template EdgeMap<bool> const &cm = m; //Const map
1.627 +// //Inicialize with default value
1.628 +// typename Graph::template EdgeMap<bool> mdef(G,12);
1.629 +// typename Graph::template EdgeMap<bool> mm(cm); //Copy
1.630 +// typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
1.631 +// bool v;
1.632 +// v=m[k]; m[k]=v; m.set(k,v);
1.633 +// v=cm[k];
1.634 +
1.635 +// m=cm;
1.636 +// dm=cm; //Copy from another type
1.637 +// m=dm; //Copy to another type
1.638 +// {
1.639 +// //Check the typedef's
1.640 +// typename Graph::template EdgeMap<bool>::ValueType val;
1.641 +// val=true;
1.642 +// typename Graph::template EdgeMap<bool>::KeyType key;
1.643 +// key= typename Graph::EdgeIt(G);
1.644 +// }
1.645 +// }
1.646 +// }
1.647 +
1.648 +// /// An empty non-static graph class.
1.649 +
1.650 +// /// This class provides everything that \ref StaticGraph
1.651 +// /// with additional functionality which enables to build a
1.652 +// /// graph from scratch.
1.653 +// class ExtendableGraph : public StaticGraph
1.654 +// {
1.655 +// public:
1.656 +// /// Defalult constructor.
1.657 +
1.658 +// /// Defalult constructor.
1.659 +// ///
1.660 +// ExtendableGraph() { }
1.661 +// ///Add a new node to the graph.
1.662 +
1.663 +// /// \return the new node.
1.664 +// ///
1.665 +// Node addNode() { return INVALID; }
1.666 +// ///Add a new edge to the graph.
1.667 +
1.668 +// ///Add a new edge to the graph with tail node \c t
1.669 +// ///and head node \c h.
1.670 +// ///\return the new edge.
1.671 +// Edge addEdge(Node h, Node t) { return INVALID; }
1.672 +
1.673 +// /// Resets the graph.
1.674 +
1.675 +// /// This function deletes all edges and nodes of the graph.
1.676 +// /// It also frees the memory allocated to store them.
1.677 +// /// \todo It might belong to \ref ErasableGraph.
1.678 +// void clear() { }
1.679 +// };
1.680 +
1.681 +
1.682 +// ///\brief Checks whether \c G meets the
1.683 +// ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
1.684 +// template<class Graph> void checkCompileExtendableGraph(Graph &G)
1.685 +// {
1.686 +// checkCompileStaticGraph(G);
1.687 +
1.688 +// typedef typename Graph::Node Node;
1.689 +// typedef typename Graph::NodeIt NodeIt;
1.690 +// typedef typename Graph::Edge Edge;
1.691 +// typedef typename Graph::EdgeIt EdgeIt;
1.692 +// typedef typename Graph::InEdgeIt InEdgeIt;
1.693 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.694 +
1.695 +// Node n,m;
1.696 +// n=G.addNode();
1.697 +// m=G.addNode();
1.698 +// Edge e;
1.699 +// e=G.addEdge(n,m);
1.700 +
1.701 +// // G.clear();
1.702 +// }
1.703 +
1.704 +
1.705 +// /// An empty erasable graph class.
1.706 +
1.707 +// /// This class is an extension of \ref ExtendableGraph. It also makes it
1.708 +// /// possible to erase edges or nodes.
1.709 +// class ErasableGraph : public ExtendableGraph
1.710 +// {
1.711 +// public:
1.712 +// /// Defalult constructor.
1.713 +
1.714 +// /// Defalult constructor.
1.715 +// ///
1.716 +// ErasableGraph() { }
1.717 +// /// Deletes a node.
1.718 +
1.719 +// /// Deletes node \c n node.
1.720 +// ///
1.721 +// void erase(Node n) { }
1.722 +// /// Deletes an edge.
1.723 +
1.724 +// /// Deletes edge \c e edge.
1.725 +// ///
1.726 +// void erase(Edge e) { }
1.727 +// };
1.728 +
1.729 +// template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
1.730 +// {
1.731 +// typename Graph::Edge e;
1.732 +// G.erase(e);
1.733 +// }
1.734 +
1.735 +// template<class Graph> void checkCompileGraphEraseNode(Graph &G)
1.736 +// {
1.737 +// typename Graph::Node n;
1.738 +// G.erase(n);
1.739 +// }
1.740 +
1.741 +// ///\brief Checks whether \c G meets the
1.742 +// ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
1.743 +// template<class Graph> void checkCompileErasableGraph(Graph &G)
1.744 +// {
1.745 +// checkCompileExtendableGraph(G);
1.746 +// checkCompileGraphEraseNode(G);
1.747 +// checkCompileGraphEraseEdge(G);
1.748 +// }
1.749 +
1.750 +// ///Checks whether a graph has findEdge() member function.
1.751 +
1.752 +// ///\todo findEdge() might be a global function.
1.753 +// ///
1.754 +// template<class Graph> void checkCompileGraphFindEdge(Graph &G)
1.755 +// {
1.756 +// typedef typename Graph::NodeIt Node;
1.757 +// typedef typename Graph::NodeIt NodeIt;
1.758 +
1.759 +// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
1.760 +// G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
1.761 +// }
1.762 +
1.763 +
1.764 +
1.765 + /************* New GraphBase stuff **************/
1.766 +
1.767 +
1.768 + /// \bug The nodes and edges are not allowed to inherit from the
1.769 + /// same baseclass.
1.770 +
1.771 + class BaseGraphItem {
1.772 public:
1.773 - /// Defalult constructor.
1.774 + BaseGraphItem() {}
1.775 + BaseGraphItem(Invalid) {}
1.776
1.777 - /// Defalult constructor.
1.778 - ///
1.779 - StaticGraph() { }
1.780 - ///Copy consructor.
1.781 + // We explicitely list these:
1.782 + BaseGraphItem(BaseGraphItem const&) {}
1.783 + BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
1.784
1.785 -// ///\todo It is not clear, what we expect from a copy constructor.
1.786 -// ///E.g. How to assign the nodes/edges to each other? What about maps?
1.787 -// StaticGraph(const StaticGraph& g) { }
1.788 + bool operator==(BaseGraphItem) const { return false; }
1.789 + bool operator!=(BaseGraphItem) const { return false; }
1.790
1.791 - /// The base type of node iterators,
1.792 - /// or in other words, the trivial node iterator.
1.793 -
1.794 - /// This is the base type of each node iterator,
1.795 - /// thus each kind of node iterator converts to this.
1.796 - /// More precisely each kind of node iterator should be inherited
1.797 - /// from the trivial node iterator.
1.798 - class Node {
1.799 - public:
1.800 - /// Default constructor
1.801 -
1.802 - /// @warning The default constructor sets the iterator
1.803 - /// to an undefined value.
1.804 - Node() { }
1.805 - /// Copy constructor.
1.806 -
1.807 - /// Copy constructor.
1.808 - ///
1.809 - Node(const Node&) { }
1.810 -
1.811 - /// Invalid constructor \& conversion.
1.812 -
1.813 - /// This constructor initializes the iterator to be invalid.
1.814 - /// \sa Invalid for more details.
1.815 - Node(Invalid) { }
1.816 - /// Equality operator
1.817 -
1.818 - /// Two iterators are equal if and only if they point to the
1.819 - /// same object or both are invalid.
1.820 - bool operator==(Node) const { return true; }
1.821 -
1.822 - /// Inequality operator
1.823 -
1.824 - /// \sa operator==(Node n)
1.825 - ///
1.826 - bool operator!=(Node) const { return true; }
1.827 -
1.828 - ///Comparison operator.
1.829 -
1.830 - ///This is a strict ordering between the nodes.
1.831 - ///
1.832 - ///This ordering can be different from the order in which NodeIt
1.833 - ///goes through the nodes.
1.834 - ///\todo Possibly we don't need it.
1.835 - bool operator<(Node) const { return true; }
1.836 - };
1.837 -
1.838 - /// This iterator goes through each node.
1.839 -
1.840 - /// This iterator goes through each node.
1.841 - /// Its usage is quite simple, for example you can count the number
1.842 - /// of nodes in graph \c g of type \c Graph like this:
1.843 - /// \code
1.844 - /// int count=0;
1.845 - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.846 - /// \endcode
1.847 - class NodeIt : public Node {
1.848 - public:
1.849 - /// Default constructor
1.850 -
1.851 - /// @warning The default constructor sets the iterator
1.852 - /// to an undefined value.
1.853 - NodeIt() { }
1.854 - /// Copy constructor.
1.855 -
1.856 - /// Copy constructor.
1.857 - ///
1.858 - NodeIt(const NodeIt&) { }
1.859 - /// Invalid constructor \& conversion.
1.860 -
1.861 - /// Initialize the iterator to be invalid.
1.862 - /// \sa Invalid for more details.
1.863 - NodeIt(Invalid) { }
1.864 - /// Sets the iterator to the first node.
1.865 -
1.866 - /// Sets the iterator to the first node of \c g.
1.867 - ///
1.868 - NodeIt(const StaticGraph& g) { }
1.869 - /// Node -> NodeIt conversion.
1.870 -
1.871 - /// Sets the iterator to the node of \c g pointed by the trivial
1.872 - /// iterator n.
1.873 - /// This feature necessitates that each time we
1.874 - /// iterate the edge-set, the iteration order is the same.
1.875 - NodeIt(const StaticGraph& g, const Node& n) { }
1.876 - /// Next node.
1.877 -
1.878 - /// Assign the iterator to the next node.
1.879 - ///
1.880 - NodeIt& operator++() { return *this; }
1.881 - };
1.882 -
1.883 -
1.884 - /// The base type of the edge iterators.
1.885 -
1.886 - /// The base type of the edge iterators.
1.887 - ///
1.888 - class Edge {
1.889 - public:
1.890 - /// Default constructor
1.891 -
1.892 - /// @warning The default constructor sets the iterator
1.893 - /// to an undefined value.
1.894 - Edge() { }
1.895 - /// Copy constructor.
1.896 -
1.897 - /// Copy constructor.
1.898 - ///
1.899 - Edge(const Edge&) { }
1.900 - /// Initialize the iterator to be invalid.
1.901 -
1.902 - /// Initialize the iterator to be invalid.
1.903 - ///
1.904 - Edge(Invalid) { }
1.905 - /// Equality operator
1.906 -
1.907 - /// Two iterators are equal if and only if they point to the
1.908 - /// same object or both are invalid.
1.909 - bool operator==(Edge) const { return true; }
1.910 - /// Inequality operator
1.911 -
1.912 - /// \sa operator==(Node n)
1.913 - ///
1.914 - bool operator!=(Edge) const { return true; }
1.915 - ///Comparison operator.
1.916 -
1.917 - ///This is a strict ordering between the nodes.
1.918 - ///
1.919 - ///This ordering can be different from the order in which NodeIt
1.920 - ///goes through the nodes.
1.921 - ///\todo Possibly we don't need it.
1.922 - bool operator<(Edge) const { return true; }
1.923 - };
1.924 -
1.925 - /// This iterator goes trough the outgoing edges of a node.
1.926 -
1.927 - /// This iterator goes trough the \e outgoing edges of a certain node
1.928 - /// of a graph.
1.929 - /// Its usage is quite simple, for example you can count the number
1.930 - /// of outgoing edges of a node \c n
1.931 - /// in graph \c g of type \c Graph as follows.
1.932 - /// \code
1.933 - /// int count=0;
1.934 - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.935 - /// \endcode
1.936 -
1.937 - class OutEdgeIt : public Edge {
1.938 - public:
1.939 - /// Default constructor
1.940 -
1.941 - /// @warning The default constructor sets the iterator
1.942 - /// to an undefined value.
1.943 - OutEdgeIt() { }
1.944 - /// Copy constructor.
1.945 -
1.946 - /// Copy constructor.
1.947 - ///
1.948 - OutEdgeIt(const OutEdgeIt&) { }
1.949 - /// Initialize the iterator to be invalid.
1.950 -
1.951 - /// Initialize the iterator to be invalid.
1.952 - ///
1.953 - OutEdgeIt(Invalid) { }
1.954 - /// This constructor sets the iterator to first outgoing edge.
1.955 -
1.956 - /// This constructor set the iterator to the first outgoing edge of
1.957 - /// node
1.958 - ///@param n the node
1.959 - ///@param g the graph
1.960 - OutEdgeIt(const StaticGraph& g, const Node& n) { }
1.961 - /// Edge -> OutEdgeIt conversion
1.962 -
1.963 - /// Sets the iterator to the value of the trivial iterator \c e.
1.964 - /// This feature necessitates that each time we
1.965 - /// iterate the edge-set, the iteration order is the same.
1.966 - OutEdgeIt(const StaticGraph& g, const Edge& e) { }
1.967 - ///Next outgoing edge
1.968 -
1.969 - /// Assign the iterator to the next
1.970 - /// outgoing edge of the corresponding node.
1.971 - OutEdgeIt& operator++() { return *this; }
1.972 - };
1.973 -
1.974 - /// This iterator goes trough the incoming edges of a node.
1.975 -
1.976 - /// This iterator goes trough the \e incoming edges of a certain node
1.977 - /// of a graph.
1.978 - /// Its usage is quite simple, for example you can count the number
1.979 - /// of outgoing edges of a node \c n
1.980 - /// in graph \c g of type \c Graph as follows.
1.981 - /// \code
1.982 - /// int count=0;
1.983 - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.984 - /// \endcode
1.985 -
1.986 - class InEdgeIt : public Edge {
1.987 - public:
1.988 - /// Default constructor
1.989 -
1.990 - /// @warning The default constructor sets the iterator
1.991 - /// to an undefined value.
1.992 - InEdgeIt() { }
1.993 - /// Copy constructor.
1.994 -
1.995 - /// Copy constructor.
1.996 - ///
1.997 - InEdgeIt(const InEdgeIt&) { }
1.998 - /// Initialize the iterator to be invalid.
1.999 -
1.1000 - /// Initialize the iterator to be invalid.
1.1001 - ///
1.1002 - InEdgeIt(Invalid) { }
1.1003 - /// This constructor sets the iterator to first incoming edge.
1.1004 -
1.1005 - /// This constructor set the iterator to the first incoming edge of
1.1006 - /// node
1.1007 - ///@param n the node
1.1008 - ///@param g the graph
1.1009 - InEdgeIt(const StaticGraph& g, const Node& n) { }
1.1010 - /// Edge -> InEdgeIt conversion
1.1011 -
1.1012 - /// Sets the iterator to the value of the trivial iterator \c e.
1.1013 - /// This feature necessitates that each time we
1.1014 - /// iterate the edge-set, the iteration order is the same.
1.1015 - InEdgeIt(const StaticGraph& g, const Edge& n) { }
1.1016 - /// Next incoming edge
1.1017 -
1.1018 - /// Assign the iterator to the next inedge of the corresponding node.
1.1019 - ///
1.1020 - InEdgeIt& operator++() { return *this; }
1.1021 - };
1.1022 - /// This iterator goes through each edge.
1.1023 -
1.1024 - /// This iterator goes through each edge of a graph.
1.1025 - /// Its usage is quite simple, for example you can count the number
1.1026 - /// of edges in a graph \c g of type \c Graph as follows:
1.1027 - /// \code
1.1028 - /// int count=0;
1.1029 - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.1030 - /// \endcode
1.1031 - class EdgeIt : public Edge {
1.1032 - public:
1.1033 - /// Default constructor
1.1034 -
1.1035 - /// @warning The default constructor sets the iterator
1.1036 - /// to an undefined value.
1.1037 - EdgeIt() { }
1.1038 - /// Copy constructor.
1.1039 -
1.1040 - /// Copy constructor.
1.1041 - ///
1.1042 - EdgeIt(const EdgeIt&) { }
1.1043 - /// Initialize the iterator to be invalid.
1.1044 -
1.1045 - /// Initialize the iterator to be invalid.
1.1046 - ///
1.1047 - EdgeIt(Invalid) { }
1.1048 - /// This constructor sets the iterator to first edge.
1.1049 -
1.1050 - /// This constructor set the iterator to the first edge of
1.1051 - /// node
1.1052 - ///@param g the graph
1.1053 - EdgeIt(const StaticGraph& g) { }
1.1054 - /// Edge -> EdgeIt conversion
1.1055 -
1.1056 - /// Sets the iterator to the value of the trivial iterator \c e.
1.1057 - /// This feature necessitates that each time we
1.1058 - /// iterate the edge-set, the iteration order is the same.
1.1059 - EdgeIt(const StaticGraph&, const Edge&) { }
1.1060 - ///Next edge
1.1061 -
1.1062 - /// Assign the iterator to the next
1.1063 - /// edge of the corresponding node.
1.1064 - EdgeIt& operator++() { return *this; }
1.1065 - };
1.1066 -
1.1067 - /// First node of the graph.
1.1068 -
1.1069 - /// \retval i the first node.
1.1070 - /// \return the first node.
1.1071 - ///
1.1072 - NodeIt& first(NodeIt& i) const { return i; }
1.1073 -
1.1074 - /// The first incoming edge.
1.1075 -
1.1076 - /// The first incoming edge.
1.1077 - ///
1.1078 - InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
1.1079 - /// The first outgoing edge.
1.1080 -
1.1081 - /// The first outgoing edge.
1.1082 - ///
1.1083 - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
1.1084 - /// The first edge of the Graph.
1.1085 -
1.1086 - /// The first edge of the Graph.
1.1087 - ///
1.1088 - EdgeIt& first(EdgeIt& i) const { return i; }
1.1089 -
1.1090 - ///Gives back the head node of an edge.
1.1091 -
1.1092 - ///Gives back the head node of an edge.
1.1093 - ///
1.1094 - Node head(Edge) const { return INVALID; }
1.1095 - ///Gives back the tail node of an edge.
1.1096 -
1.1097 - ///Gives back the tail node of an edge.
1.1098 - ///
1.1099 - Node tail(Edge) const { return INVALID; }
1.1100 -
1.1101 - ///Gives back the \e id of a node.
1.1102 -
1.1103 - ///\warning Not all graph structures provide this feature.
1.1104 - ///
1.1105 - ///\todo Should each graph provide \c id?
1.1106 - int id(const Node&) const { return 0; }
1.1107 - ///Gives back the \e id of an edge.
1.1108 -
1.1109 - ///\warning Not all graph structures provide this feature.
1.1110 - ///
1.1111 - ///\todo Should each graph provide \c id?
1.1112 - int id(const Edge&) const { return 0; }
1.1113 -
1.1114 - ///\e
1.1115 -
1.1116 - ///\todo Should it be in the concept?
1.1117 - ///
1.1118 - int nodeNum() const { return 0; }
1.1119 - ///\e
1.1120 -
1.1121 - ///\todo Should it be in the concept?
1.1122 - ///
1.1123 - int edgeNum() const { return 0; }
1.1124 -
1.1125 -
1.1126 - ///Reference map of the nodes to type \c T.
1.1127 -
1.1128 - /// \ingroup skeletons
1.1129 - ///Reference map of the nodes to type \c T.
1.1130 - /// \sa Reference
1.1131 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.1132 - /// needs some extra attention!
1.1133 - template<class T> class NodeMap : public ReferenceMap< Node, T >
1.1134 - {
1.1135 - public:
1.1136 -
1.1137 - ///\e
1.1138 - NodeMap(const StaticGraph&) { }
1.1139 - ///\e
1.1140 - NodeMap(const StaticGraph&, T) { }
1.1141 -
1.1142 - ///Copy constructor
1.1143 - template<typename TT> NodeMap(const NodeMap<TT>&) { }
1.1144 - ///Assignment operator
1.1145 - template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
1.1146 - { return *this; }
1.1147 - };
1.1148 -
1.1149 - ///Reference map of the edges to type \c T.
1.1150 -
1.1151 - /// \ingroup skeletons
1.1152 - ///Reference map of the edges to type \c T.
1.1153 - /// \sa Reference
1.1154 - /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.1155 - /// needs some extra attention!
1.1156 - template<class T> class EdgeMap
1.1157 - : public ReferenceMap<Edge,T>
1.1158 - {
1.1159 - public:
1.1160 -
1.1161 - ///\e
1.1162 - EdgeMap(const StaticGraph&) { }
1.1163 - ///\e
1.1164 - EdgeMap(const StaticGraph&, T) { }
1.1165 -
1.1166 - ///Copy constructor
1.1167 - template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
1.1168 - ///Assignment operator
1.1169 - template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
1.1170 - { return *this; }
1.1171 - };
1.1172 + // Technical requirement. Do we really need this?
1.1173 + bool operator<(BaseGraphItem) const { return false; }
1.1174 };
1.1175
1.1176 - struct DummyType {
1.1177 - int value;
1.1178 - DummyType() {}
1.1179 - DummyType(int p) : value(p) {}
1.1180 - DummyType& operator=(int p) { value = p; return *this;}
1.1181 +
1.1182 + /// A minimal GraphBase concept
1.1183 +
1.1184 + /// This class describes a minimal concept which can be extended to a
1.1185 + /// full-featured graph with \ref GraphFactory.
1.1186 + class GraphBase {
1.1187 + public:
1.1188 +
1.1189 + GraphBase() {}
1.1190 +
1.1191 +
1.1192 + /// \bug Nodes and Edges are comparable each other
1.1193 +
1.1194 + class Node : public BaseGraphItem {};
1.1195 + class Edge : public BaseGraphItem {};
1.1196 +
1.1197 + // Graph operation
1.1198 + void firstNode(Node &n) const { }
1.1199 + void firstEdge(Edge &e) const { }
1.1200 +
1.1201 + void firstOutEdge(Edge &e, Node) const { }
1.1202 + void firstInEdge(Edge &e, Node) const { }
1.1203 +
1.1204 + void nextNode(Node &n) const { }
1.1205 + void nextEdge(Edge &e) const { }
1.1206 +
1.1207 +
1.1208 + // Question: isn't it reasonable if this methods have a Node
1.1209 + // parameter? Like this:
1.1210 + // Edge& nextOut(Edge &e, Node) const { return e; }
1.1211 + void nextOutEdge(Edge &e) const { }
1.1212 + void nextInEdge(Edge &e) const { }
1.1213 +
1.1214 + Node head(Edge) const { return Node(); }
1.1215 + Node tail(Edge) const { return Node(); }
1.1216 +
1.1217 +
1.1218 + // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
1.1219 + // concept?
1.1220 +
1.1221 +
1.1222 + // Maps.
1.1223 + //
1.1224 + // We need a special slimer concept which does not provide maps (it
1.1225 + // wouldn't be strictly slimer, cause for map-factory id() & friends
1.1226 + // a required...)
1.1227 +
1.1228 + template<typename T>
1.1229 + class NodeMap : public GraphMap<Node, T, GraphBase> {};
1.1230 +
1.1231 + template<typename T>
1.1232 + class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
1.1233 };
1.1234 -
1.1235 - ///\brief Checks whether \c G meets the
1.1236 - ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
1.1237 - template<class Graph> void checkCompileStaticGraph(Graph &G)
1.1238 - {
1.1239 - typedef typename Graph::Node Node;
1.1240 - typedef typename Graph::NodeIt NodeIt;
1.1241 - typedef typename Graph::Edge Edge;
1.1242 - typedef typename Graph::EdgeIt EdgeIt;
1.1243 - typedef typename Graph::InEdgeIt InEdgeIt;
1.1244 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1245 -
1.1246 - {
1.1247 - Node i; Node j(i); Node k(INVALID);
1.1248 - i=j;
1.1249 - bool b; b=true;
1.1250 - b=(i==INVALID); b=(i!=INVALID);
1.1251 - b=(i==j); b=(i!=j); b=(i<j);
1.1252 - }
1.1253 - {
1.1254 - NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
1.1255 - i=j;
1.1256 - j=G.first(i);
1.1257 - j=++i;
1.1258 - bool b; b=true;
1.1259 - b=(i==INVALID); b=(i!=INVALID);
1.1260 - Node n(i);
1.1261 - n=i;
1.1262 - b=(i==j); b=(i!=j); b=(i<j);
1.1263 - //Node ->NodeIt conversion
1.1264 - NodeIt ni(G,n);
1.1265 - }
1.1266 - {
1.1267 - Edge i; Edge j(i); Edge k(INVALID);
1.1268 - i=j;
1.1269 - bool b; b=true;
1.1270 - b=(i==INVALID); b=(i!=INVALID);
1.1271 - b=(i==j); b=(i!=j); b=(i<j);
1.1272 - }
1.1273 - {
1.1274 - EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
1.1275 - i=j;
1.1276 - j=G.first(i);
1.1277 - j=++i;
1.1278 - bool b; b=true;
1.1279 - b=(i==INVALID); b=(i!=INVALID);
1.1280 - Edge e(i);
1.1281 - e=i;
1.1282 - b=(i==j); b=(i!=j); b=(i<j);
1.1283 - //Edge ->EdgeIt conversion
1.1284 - EdgeIt ei(G,e);
1.1285 - }
1.1286 - {
1.1287 - Node n;
1.1288 - InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
1.1289 - i=j;
1.1290 - j=G.first(i,n);
1.1291 - j=++i;
1.1292 - bool b; b=true;
1.1293 - b=(i==INVALID); b=(i!=INVALID);
1.1294 - Edge e(i);
1.1295 - e=i;
1.1296 - b=(i==j); b=(i!=j); b=(i<j);
1.1297 - //Edge ->InEdgeIt conversion
1.1298 - InEdgeIt ei(G,e);
1.1299 - }
1.1300 - {
1.1301 - Node n;
1.1302 - OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
1.1303 - i=j;
1.1304 - j=G.first(i,n);
1.1305 - j=++i;
1.1306 - bool b; b=true;
1.1307 - b=(i==INVALID); b=(i!=INVALID);
1.1308 - Edge e(i);
1.1309 - e=i;
1.1310 - b=(i==j); b=(i!=j); b=(i<j);
1.1311 - //Edge ->OutEdgeIt conversion
1.1312 - OutEdgeIt ei(G,e);
1.1313 - }
1.1314 - {
1.1315 - Node n,m;
1.1316 - n=m=INVALID;
1.1317 - Edge e;
1.1318 - e=INVALID;
1.1319 - n=G.tail(e);
1.1320 - n=G.head(e);
1.1321 - }
1.1322 - // id tests
1.1323 - { Node n; int i=G.id(n); i=i; }
1.1324 - { Edge e; int i=G.id(e); i=i; }
1.1325 - //NodeMap tests
1.1326 - {
1.1327 - Node k;
1.1328 - typename Graph::template NodeMap<int> m(G);
1.1329 - //Const map
1.1330 - typename Graph::template NodeMap<int> const &cm = m;
1.1331 - //Inicialize with default value
1.1332 - typename Graph::template NodeMap<int> mdef(G,12);
1.1333 - //Copy
1.1334 - typename Graph::template NodeMap<int> mm(cm);
1.1335 - //Copy from another type
1.1336 - typename Graph::template NodeMap<double> dm(cm);
1.1337 - //Copy to more complex type
1.1338 - typename Graph::template NodeMap<DummyType> em(cm);
1.1339 - int v;
1.1340 - v=m[k]; m[k]=v; m.set(k,v);
1.1341 - v=cm[k];
1.1342 -
1.1343 - m=cm;
1.1344 - dm=cm; //Copy from another type
1.1345 - em=cm; //Copy to more complex type
1.1346 - {
1.1347 - //Check the typedef's
1.1348 - typename Graph::template NodeMap<int>::ValueType val;
1.1349 - val=1;
1.1350 - typename Graph::template NodeMap<int>::KeyType key;
1.1351 - key = typename Graph::NodeIt(G);
1.1352 - }
1.1353 - }
1.1354 - { //bool NodeMap
1.1355 - Node k;
1.1356 - typename Graph::template NodeMap<bool> m(G);
1.1357 - typename Graph::template NodeMap<bool> const &cm = m; //Const map
1.1358 - //Inicialize with default value
1.1359 - typename Graph::template NodeMap<bool> mdef(G,12);
1.1360 - typename Graph::template NodeMap<bool> mm(cm); //Copy
1.1361 - typename Graph::template NodeMap<int> dm(cm); //Copy from another type
1.1362 - bool v;
1.1363 - v=m[k]; m[k]=v; m.set(k,v);
1.1364 - v=cm[k];
1.1365 -
1.1366 - m=cm;
1.1367 - dm=cm; //Copy from another type
1.1368 - m=dm; //Copy to another type
1.1369
1.1370 - {
1.1371 - //Check the typedef's
1.1372 - typename Graph::template NodeMap<bool>::ValueType val;
1.1373 - val=true;
1.1374 - typename Graph::template NodeMap<bool>::KeyType key;
1.1375 - key= typename Graph::NodeIt(G);
1.1376 +
1.1377 +
1.1378 + /**************** Concept checking classes ****************/
1.1379 +
1.1380 + template<typename BGI>
1.1381 + struct BaseGraphItemConcept {
1.1382 + void constraints() {
1.1383 + BGI i1;
1.1384 + BGI i2 = i1;
1.1385 + BGI i3 = INVALID;
1.1386 +
1.1387 + i1 = i3;
1.1388 + if( i1 == i3 ) {
1.1389 + if ( i2 != i3 && i3 < i2 )
1.1390 + return;
1.1391 }
1.1392 }
1.1393 - //EdgeMap tests
1.1394 - {
1.1395 - Edge k;
1.1396 - typename Graph::template EdgeMap<int> m(G);
1.1397 - typename Graph::template EdgeMap<int> const &cm = m; //Const map
1.1398 - //Inicialize with default value
1.1399 - typename Graph::template EdgeMap<int> mdef(G,12);
1.1400 - typename Graph::template EdgeMap<int> mm(cm); //Copy
1.1401 - typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
1.1402 - int v;
1.1403 - v=m[k]; m[k]=v; m.set(k,v);
1.1404 - v=cm[k];
1.1405 -
1.1406 - m=cm;
1.1407 - dm=cm; //Copy from another type
1.1408 - {
1.1409 - //Check the typedef's
1.1410 - typename Graph::template EdgeMap<int>::ValueType val;
1.1411 - val=1;
1.1412 - typename Graph::template EdgeMap<int>::KeyType key;
1.1413 - key= typename Graph::EdgeIt(G);
1.1414 - }
1.1415 - }
1.1416 - { //bool EdgeMap
1.1417 - Edge k;
1.1418 - typename Graph::template EdgeMap<bool> m(G);
1.1419 - typename Graph::template EdgeMap<bool> const &cm = m; //Const map
1.1420 - //Inicialize with default value
1.1421 - typename Graph::template EdgeMap<bool> mdef(G,12);
1.1422 - typename Graph::template EdgeMap<bool> mm(cm); //Copy
1.1423 - typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
1.1424 - bool v;
1.1425 - v=m[k]; m[k]=v; m.set(k,v);
1.1426 - v=cm[k];
1.1427 -
1.1428 - m=cm;
1.1429 - dm=cm; //Copy from another type
1.1430 - m=dm; //Copy to another type
1.1431 - {
1.1432 - //Check the typedef's
1.1433 - typename Graph::template EdgeMap<bool>::ValueType val;
1.1434 - val=true;
1.1435 - typename Graph::template EdgeMap<bool>::KeyType key;
1.1436 - key= typename Graph::EdgeIt(G);
1.1437 - }
1.1438 - }
1.1439 - }
1.1440 -
1.1441 - /// An empty non-static graph class.
1.1442 -
1.1443 - /// This class provides everything that \ref StaticGraph
1.1444 - /// with additional functionality which enables to build a
1.1445 - /// graph from scratch.
1.1446 - class ExtendableGraph : public StaticGraph
1.1447 - {
1.1448 - public:
1.1449 - /// Defalult constructor.
1.1450 -
1.1451 - /// Defalult constructor.
1.1452 - ///
1.1453 - ExtendableGraph() { }
1.1454 - ///Add a new node to the graph.
1.1455 -
1.1456 - /// \return the new node.
1.1457 - ///
1.1458 - Node addNode() { return INVALID; }
1.1459 - ///Add a new edge to the graph.
1.1460 -
1.1461 - ///Add a new edge to the graph with tail node \c t
1.1462 - ///and head node \c h.
1.1463 - ///\return the new edge.
1.1464 - Edge addEdge(Node h, Node t) { return INVALID; }
1.1465 -
1.1466 - /// Resets the graph.
1.1467 -
1.1468 - /// This function deletes all edges and nodes of the graph.
1.1469 - /// It also frees the memory allocated to store them.
1.1470 - /// \todo It might belong to \ref ErasableGraph.
1.1471 - void clear() { }
1.1472 };
1.1473
1.1474
1.1475 - ///\brief Checks whether \c G meets the
1.1476 - ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
1.1477 - template<class Graph> void checkCompileExtendableGraph(Graph &G)
1.1478 - {
1.1479 - checkCompileStaticGraph(G);
1.1480 +
1.1481 + class StaticGraph
1.1482 + : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
1.1483 + public:
1.1484 + typedef BaseGraphComponent::Node Node;
1.1485 + typedef BaseGraphComponent::Edge Edge;
1.1486 + };
1.1487
1.1488 - typedef typename Graph::Node Node;
1.1489 - typedef typename Graph::NodeIt NodeIt;
1.1490 - typedef typename Graph::Edge Edge;
1.1491 - typedef typename Graph::EdgeIt EdgeIt;
1.1492 - typedef typename Graph::InEdgeIt InEdgeIt;
1.1493 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1494 -
1.1495 - Node n,m;
1.1496 - n=G.addNode();
1.1497 - m=G.addNode();
1.1498 - Edge e;
1.1499 - e=G.addEdge(n,m);
1.1500 -
1.1501 - // G.clear();
1.1502 - }
1.1503 + template <typename Graph>
1.1504 + struct StaticGraphConcept {
1.1505 + void constraints() {
1.1506 + function_requires<BaseGraphComponentConcept<Graph> >();
1.1507 + function_requires<IterableGraphComponentConcept<Graph> >();
1.1508 + function_requires<MappableGraphComponentConcept<Graph> >();
1.1509 + }
1.1510 + Graph& graph;
1.1511 + };
1.1512
1.1513 + class ExtendableGraph
1.1514 + : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
1.1515 + public:
1.1516 + typedef BaseGraphComponent::Node Node;
1.1517 + typedef BaseGraphComponent::Edge Edge;
1.1518 + };
1.1519
1.1520 - /// An empty erasable graph class.
1.1521 -
1.1522 - /// This class is an extension of \ref ExtendableGraph. It also makes it
1.1523 - /// possible to erase edges or nodes.
1.1524 - class ErasableGraph : public ExtendableGraph
1.1525 - {
1.1526 + template <typename Graph>
1.1527 + struct ExtendableGraphConcept {
1.1528 + void constraints() {
1.1529 + function_requires<StaticGraphConcept<Graph> >();
1.1530 + function_requires<ExtendableGraphComponentConcept<Graph> >();
1.1531 + function_requires<ClearableGraphComponentConcept<Graph> >();
1.1532 + }
1.1533 + Graph& graph;
1.1534 + };
1.1535 +
1.1536 + class ErasableGraph
1.1537 + : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
1.1538 public:
1.1539 - /// Defalult constructor.
1.1540 + typedef BaseGraphComponent::Node Node;
1.1541 + typedef BaseGraphComponent::Edge Edge;
1.1542 + };
1.1543
1.1544 - /// Defalult constructor.
1.1545 - ///
1.1546 - ErasableGraph() { }
1.1547 - /// Deletes a node.
1.1548 + template <typename Graph>
1.1549 + struct ErasableGraphConcept {
1.1550 + void constraints() {
1.1551 + function_requires<ExtendableGraphConcept<Graph> >();
1.1552 + function_requires<ErasableGraphComponentConcept<Graph> >();
1.1553 + }
1.1554 + Graph& graph;
1.1555 + };
1.1556
1.1557 - /// Deletes node \c n node.
1.1558 - ///
1.1559 - void erase(Node n) { }
1.1560 - /// Deletes an edge.
1.1561 -
1.1562 - /// Deletes edge \c e edge.
1.1563 - ///
1.1564 - void erase(Edge e) { }
1.1565 - };
1.1566 -
1.1567 - template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
1.1568 - {
1.1569 - typename Graph::Edge e;
1.1570 - G.erase(e);
1.1571 - }
1.1572 -
1.1573 - template<class Graph> void checkCompileGraphEraseNode(Graph &G)
1.1574 - {
1.1575 - typename Graph::Node n;
1.1576 - G.erase(n);
1.1577 - }
1.1578 -
1.1579 - ///\brief Checks whether \c G meets the
1.1580 - ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
1.1581 - template<class Graph> void checkCompileErasableGraph(Graph &G)
1.1582 - {
1.1583 - checkCompileExtendableGraph(G);
1.1584 - checkCompileGraphEraseNode(G);
1.1585 - checkCompileGraphEraseEdge(G);
1.1586 - }
1.1587 -
1.1588 - ///Checks whether a graph has findEdge() member function.
1.1589 -
1.1590 - ///\todo findEdge() might be a global function.
1.1591 - ///
1.1592 - template<class Graph> void checkCompileGraphFindEdge(Graph &G)
1.1593 - {
1.1594 - typedef typename Graph::NodeIt Node;
1.1595 - typedef typename Graph::NodeIt NodeIt;
1.1596 -
1.1597 - G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
1.1598 - G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
1.1599 - }
1.1600 -
1.1601 // @}
1.1602 } //namespace skeleton
1.1603 } //namespace lemon