1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/concept/graph.h Thu Nov 04 20:24:59 2004 +0000
1.3 @@ -0,0 +1,918 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_CONCEPT_GRAPH_H
1.21 +#define LEMON_CONCEPT_GRAPH_H
1.22 +
1.23 +///\ingroup concept
1.24 +///\file
1.25 +///\brief Declaration of Graph.
1.26 +
1.27 +#include <lemon/invalid.h>
1.28 +#include <lemon/concept/maps.h>
1.29 +#include <lemon/concept_check.h>
1.30 +#include <lemon/concept/graph_component.h>
1.31 +
1.32 +namespace lemon {
1.33 + namespace concept {
1.34 +
1.35 + /// \addtogroup concept
1.36 + /// @{
1.37 +
1.38 +// /// An empty static graph class.
1.39 +
1.40 +// /// This class provides all the common features of a graph structure,
1.41 +// /// however completely without implementations and real data structures
1.42 +// /// behind the interface.
1.43 +// /// All graph algorithms should compile with this class, but it will not
1.44 +// /// run properly, of course.
1.45 +// ///
1.46 +// /// It can be used for checking the interface compatibility,
1.47 +// /// or it can serve as a skeleton of a new graph structure.
1.48 +// ///
1.49 +// /// Also, you will find here the full documentation of a certain graph
1.50 +// /// feature, the documentation of a real graph imlementation
1.51 +// /// like @ref ListGraph or
1.52 +// /// @ref SmartGraph will just refer to this structure.
1.53 +// ///
1.54 +// /// \todo A pages describing the concept of concept description would
1.55 +// /// be nice.
1.56 +// class StaticGraph
1.57 +// {
1.58 +// public:
1.59 +// /// Defalult constructor.
1.60 +
1.61 +// /// Defalult constructor.
1.62 +// ///
1.63 +// StaticGraph() { }
1.64 +// ///Copy consructor.
1.65 +
1.66 +// // ///\todo It is not clear, what we expect from a copy constructor.
1.67 +// // ///E.g. How to assign the nodes/edges to each other? What about maps?
1.68 +// // StaticGraph(const StaticGraph& g) { }
1.69 +
1.70 +// /// The base type of node iterators,
1.71 +// /// or in other words, the trivial node iterator.
1.72 +
1.73 +// /// This is the base type of each node iterator,
1.74 +// /// thus each kind of node iterator converts to this.
1.75 +// /// More precisely each kind of node iterator should be inherited
1.76 +// /// from the trivial node iterator.
1.77 +// class Node {
1.78 +// public:
1.79 +// /// Default constructor
1.80 +
1.81 +// /// @warning The default constructor sets the iterator
1.82 +// /// to an undefined value.
1.83 +// Node() { }
1.84 +// /// Copy constructor.
1.85 +
1.86 +// /// Copy constructor.
1.87 +// ///
1.88 +// Node(const Node&) { }
1.89 +
1.90 +// /// Invalid constructor \& conversion.
1.91 +
1.92 +// /// This constructor initializes the iterator to be invalid.
1.93 +// /// \sa Invalid for more details.
1.94 +// Node(Invalid) { }
1.95 +// /// Equality operator
1.96 +
1.97 +// /// Two iterators are equal if and only if they point to the
1.98 +// /// same object or both are invalid.
1.99 +// bool operator==(Node) const { return true; }
1.100 +
1.101 +// /// Inequality operator
1.102 +
1.103 +// /// \sa operator==(Node n)
1.104 +// ///
1.105 +// bool operator!=(Node) const { return true; }
1.106 +
1.107 +// ///Comparison operator.
1.108 +
1.109 +// ///This is a strict ordering between the nodes.
1.110 +// ///
1.111 +// ///This ordering can be different from the order in which NodeIt
1.112 +// ///goes through the nodes.
1.113 +// ///\todo Possibly we don't need it.
1.114 +// bool operator<(Node) const { return true; }
1.115 +// };
1.116 +
1.117 +// /// This iterator goes through each node.
1.118 +
1.119 +// /// This iterator goes through each node.
1.120 +// /// Its usage is quite simple, for example you can count the number
1.121 +// /// of nodes in graph \c g of type \c Graph like this:
1.122 +// /// \code
1.123 +// /// int count=0;
1.124 +// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
1.125 +// /// \endcode
1.126 +// class NodeIt : public Node {
1.127 +// public:
1.128 +// /// Default constructor
1.129 +
1.130 +// /// @warning The default constructor sets the iterator
1.131 +// /// to an undefined value.
1.132 +// NodeIt() { }
1.133 +// /// Copy constructor.
1.134 +
1.135 +// /// Copy constructor.
1.136 +// ///
1.137 +// NodeIt(const NodeIt&) { }
1.138 +// /// Invalid constructor \& conversion.
1.139 +
1.140 +// /// Initialize the iterator to be invalid.
1.141 +// /// \sa Invalid for more details.
1.142 +// NodeIt(Invalid) { }
1.143 +// /// Sets the iterator to the first node.
1.144 +
1.145 +// /// Sets the iterator to the first node of \c g.
1.146 +// ///
1.147 +// NodeIt(const StaticGraph& g) { }
1.148 +// /// Node -> NodeIt conversion.
1.149 +
1.150 +// /// Sets the iterator to the node of \c g pointed by the trivial
1.151 +// /// iterator n.
1.152 +// /// This feature necessitates that each time we
1.153 +// /// iterate the edge-set, the iteration order is the same.
1.154 +// NodeIt(const StaticGraph& g, const Node& n) { }
1.155 +// /// Next node.
1.156 +
1.157 +// /// Assign the iterator to the next node.
1.158 +// ///
1.159 +// NodeIt& operator++() { return *this; }
1.160 +// };
1.161 +
1.162 +
1.163 +// /// The base type of the edge iterators.
1.164 +
1.165 +// /// The base type of the edge iterators.
1.166 +// ///
1.167 +// class Edge {
1.168 +// public:
1.169 +// /// Default constructor
1.170 +
1.171 +// /// @warning The default constructor sets the iterator
1.172 +// /// to an undefined value.
1.173 +// Edge() { }
1.174 +// /// Copy constructor.
1.175 +
1.176 +// /// Copy constructor.
1.177 +// ///
1.178 +// Edge(const Edge&) { }
1.179 +// /// Initialize the iterator to be invalid.
1.180 +
1.181 +// /// Initialize the iterator to be invalid.
1.182 +// ///
1.183 +// Edge(Invalid) { }
1.184 +// /// Equality operator
1.185 +
1.186 +// /// Two iterators are equal if and only if they point to the
1.187 +// /// same object or both are invalid.
1.188 +// bool operator==(Edge) const { return true; }
1.189 +// /// Inequality operator
1.190 +
1.191 +// /// \sa operator==(Node n)
1.192 +// ///
1.193 +// bool operator!=(Edge) const { return true; }
1.194 +// ///Comparison operator.
1.195 +
1.196 +// ///This is a strict ordering between the nodes.
1.197 +// ///
1.198 +// ///This ordering can be different from the order in which NodeIt
1.199 +// ///goes through the nodes.
1.200 +// ///\todo Possibly we don't need it.
1.201 +// bool operator<(Edge) const { return true; }
1.202 +// };
1.203 +
1.204 +// /// This iterator goes trough the outgoing edges of a node.
1.205 +
1.206 +// /// This iterator goes trough the \e outgoing edges of a certain node
1.207 +// /// of a graph.
1.208 +// /// Its usage is quite simple, for example you can count the number
1.209 +// /// of outgoing edges of a node \c n
1.210 +// /// in graph \c g of type \c Graph as follows.
1.211 +// /// \code
1.212 +// /// int count=0;
1.213 +// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.214 +// /// \endcode
1.215 +
1.216 +// class OutEdgeIt : public Edge {
1.217 +// public:
1.218 +// /// Default constructor
1.219 +
1.220 +// /// @warning The default constructor sets the iterator
1.221 +// /// to an undefined value.
1.222 +// OutEdgeIt() { }
1.223 +// /// Copy constructor.
1.224 +
1.225 +// /// Copy constructor.
1.226 +// ///
1.227 +// OutEdgeIt(const OutEdgeIt&) { }
1.228 +// /// Initialize the iterator to be invalid.
1.229 +
1.230 +// /// Initialize the iterator to be invalid.
1.231 +// ///
1.232 +// OutEdgeIt(Invalid) { }
1.233 +// /// This constructor sets the iterator to first outgoing edge.
1.234 +
1.235 +// /// This constructor set the iterator to the first outgoing edge of
1.236 +// /// node
1.237 +// ///@param n the node
1.238 +// ///@param g the graph
1.239 +// OutEdgeIt(const StaticGraph& g, const Node& n) { }
1.240 +// /// Edge -> OutEdgeIt conversion
1.241 +
1.242 +// /// Sets the iterator to the value of the trivial iterator \c e.
1.243 +// /// This feature necessitates that each time we
1.244 +// /// iterate the edge-set, the iteration order is the same.
1.245 +// OutEdgeIt(const StaticGraph& g, const Edge& e) { }
1.246 +// ///Next outgoing edge
1.247 +
1.248 +// /// Assign the iterator to the next
1.249 +// /// outgoing edge of the corresponding node.
1.250 +// OutEdgeIt& operator++() { return *this; }
1.251 +// };
1.252 +
1.253 +// /// This iterator goes trough the incoming edges of a node.
1.254 +
1.255 +// /// This iterator goes trough the \e incoming edges of a certain node
1.256 +// /// of a graph.
1.257 +// /// Its usage is quite simple, for example you can count the number
1.258 +// /// of outgoing edges of a node \c n
1.259 +// /// in graph \c g of type \c Graph as follows.
1.260 +// /// \code
1.261 +// /// int count=0;
1.262 +// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.263 +// /// \endcode
1.264 +
1.265 +// class InEdgeIt : public Edge {
1.266 +// public:
1.267 +// /// Default constructor
1.268 +
1.269 +// /// @warning The default constructor sets the iterator
1.270 +// /// to an undefined value.
1.271 +// InEdgeIt() { }
1.272 +// /// Copy constructor.
1.273 +
1.274 +// /// Copy constructor.
1.275 +// ///
1.276 +// InEdgeIt(const InEdgeIt&) { }
1.277 +// /// Initialize the iterator to be invalid.
1.278 +
1.279 +// /// Initialize the iterator to be invalid.
1.280 +// ///
1.281 +// InEdgeIt(Invalid) { }
1.282 +// /// This constructor sets the iterator to first incoming edge.
1.283 +
1.284 +// /// This constructor set the iterator to the first incoming edge of
1.285 +// /// node
1.286 +// ///@param n the node
1.287 +// ///@param g the graph
1.288 +// InEdgeIt(const StaticGraph& g, const Node& n) { }
1.289 +// /// Edge -> InEdgeIt conversion
1.290 +
1.291 +// /// Sets the iterator to the value of the trivial iterator \c e.
1.292 +// /// This feature necessitates that each time we
1.293 +// /// iterate the edge-set, the iteration order is the same.
1.294 +// InEdgeIt(const StaticGraph& g, const Edge& n) { }
1.295 +// /// Next incoming edge
1.296 +
1.297 +// /// Assign the iterator to the next inedge of the corresponding node.
1.298 +// ///
1.299 +// InEdgeIt& operator++() { return *this; }
1.300 +// };
1.301 +// /// This iterator goes through each edge.
1.302 +
1.303 +// /// This iterator goes through each edge of a graph.
1.304 +// /// Its usage is quite simple, for example you can count the number
1.305 +// /// of edges in a graph \c g of type \c Graph as follows:
1.306 +// /// \code
1.307 +// /// int count=0;
1.308 +// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.309 +// /// \endcode
1.310 +// class EdgeIt : public Edge {
1.311 +// public:
1.312 +// /// Default constructor
1.313 +
1.314 +// /// @warning The default constructor sets the iterator
1.315 +// /// to an undefined value.
1.316 +// EdgeIt() { }
1.317 +// /// Copy constructor.
1.318 +
1.319 +// /// Copy constructor.
1.320 +// ///
1.321 +// EdgeIt(const EdgeIt&) { }
1.322 +// /// Initialize the iterator to be invalid.
1.323 +
1.324 +// /// Initialize the iterator to be invalid.
1.325 +// ///
1.326 +// EdgeIt(Invalid) { }
1.327 +// /// This constructor sets the iterator to first edge.
1.328 +
1.329 +// /// This constructor set the iterator to the first edge of
1.330 +// /// node
1.331 +// ///@param g the graph
1.332 +// EdgeIt(const StaticGraph& g) { }
1.333 +// /// Edge -> EdgeIt conversion
1.334 +
1.335 +// /// Sets the iterator to the value of the trivial iterator \c e.
1.336 +// /// This feature necessitates that each time we
1.337 +// /// iterate the edge-set, the iteration order is the same.
1.338 +// EdgeIt(const StaticGraph&, const Edge&) { }
1.339 +// ///Next edge
1.340 +
1.341 +// /// Assign the iterator to the next
1.342 +// /// edge of the corresponding node.
1.343 +// EdgeIt& operator++() { return *this; }
1.344 +// };
1.345 +
1.346 +// /// First node of the graph.
1.347 +
1.348 +// /// \retval i the first node.
1.349 +// /// \return the first node.
1.350 +// ///
1.351 +// NodeIt& first(NodeIt& i) const { return i; }
1.352 +
1.353 +// /// The first incoming edge.
1.354 +
1.355 +// /// The first incoming edge.
1.356 +// ///
1.357 +// InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
1.358 +// /// The first outgoing edge.
1.359 +
1.360 +// /// The first outgoing edge.
1.361 +// ///
1.362 +// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
1.363 +// /// The first edge of the Graph.
1.364 +
1.365 +// /// The first edge of the Graph.
1.366 +// ///
1.367 +// EdgeIt& first(EdgeIt& i) const { return i; }
1.368 +
1.369 +// ///Gives back the head node of an edge.
1.370 +
1.371 +// ///Gives back the head node of an edge.
1.372 +// ///
1.373 +// Node head(Edge) const { return INVALID; }
1.374 +// ///Gives back the tail node of an edge.
1.375 +
1.376 +// ///Gives back the tail node of an edge.
1.377 +// ///
1.378 +// Node tail(Edge) const { return INVALID; }
1.379 +
1.380 +// ///Gives back the \e id of a node.
1.381 +
1.382 +// ///\warning Not all graph structures provide this feature.
1.383 +// ///
1.384 +// ///\todo Should each graph provide \c id?
1.385 +// int id(const Node&) const { return 0; }
1.386 +// ///Gives back the \e id of an edge.
1.387 +
1.388 +// ///\warning Not all graph structures provide this feature.
1.389 +// ///
1.390 +// ///\todo Should each graph provide \c id?
1.391 +// int id(const Edge&) const { return 0; }
1.392 +
1.393 +// ///\e
1.394 +
1.395 +// ///\todo Should it be in the concept?
1.396 +// ///
1.397 +// int nodeNum() const { return 0; }
1.398 +// ///\e
1.399 +
1.400 +// ///\todo Should it be in the concept?
1.401 +// ///
1.402 +// int edgeNum() const { return 0; }
1.403 +
1.404 +
1.405 +// ///Reference map of the nodes to type \c T.
1.406 +
1.407 +// /// \ingroup concept
1.408 +// ///Reference map of the nodes to type \c T.
1.409 +// /// \sa Reference
1.410 +// /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.411 +// /// needs some extra attention!
1.412 +// template<class T> class NodeMap : public ReferenceMap< Node, T >
1.413 +// {
1.414 +// public:
1.415 +
1.416 +// ///\e
1.417 +// NodeMap(const StaticGraph&) { }
1.418 +// ///\e
1.419 +// NodeMap(const StaticGraph&, T) { }
1.420 +
1.421 +// ///Copy constructor
1.422 +// template<typename TT> NodeMap(const NodeMap<TT>&) { }
1.423 +// ///Assignment operator
1.424 +// template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
1.425 +// { return *this; }
1.426 +// };
1.427 +
1.428 +// ///Reference map of the edges to type \c T.
1.429 +
1.430 +// /// \ingroup concept
1.431 +// ///Reference map of the edges to type \c T.
1.432 +// /// \sa Reference
1.433 +// /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.434 +// /// needs some extra attention!
1.435 +// template<class T> class EdgeMap
1.436 +// : public ReferenceMap<Edge,T>
1.437 +// {
1.438 +// public:
1.439 +
1.440 +// ///\e
1.441 +// EdgeMap(const StaticGraph&) { }
1.442 +// ///\e
1.443 +// EdgeMap(const StaticGraph&, T) { }
1.444 +
1.445 +// ///Copy constructor
1.446 +// template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
1.447 +// ///Assignment operator
1.448 +// template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
1.449 +// { return *this; }
1.450 +// };
1.451 +// };
1.452 +
1.453 +// struct DummyType {
1.454 +// int value;
1.455 +// DummyType() {}
1.456 +// DummyType(int p) : value(p) {}
1.457 +// DummyType& operator=(int p) { value = p; return *this;}
1.458 +// };
1.459 +
1.460 +// ///\brief Checks whether \c G meets the
1.461 +// ///\ref lemon::concept::StaticGraph "StaticGraph" concept
1.462 +// template<class Graph> void checkCompileStaticGraph(Graph &G)
1.463 +// {
1.464 +// typedef typename Graph::Node Node;
1.465 +// typedef typename Graph::NodeIt NodeIt;
1.466 +// typedef typename Graph::Edge Edge;
1.467 +// typedef typename Graph::EdgeIt EdgeIt;
1.468 +// typedef typename Graph::InEdgeIt InEdgeIt;
1.469 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.470 +
1.471 +// {
1.472 +// Node i; Node j(i); Node k(INVALID);
1.473 +// i=j;
1.474 +// bool b; b=true;
1.475 +// b=(i==INVALID); b=(i!=INVALID);
1.476 +// b=(i==j); b=(i!=j); b=(i<j);
1.477 +// }
1.478 +// {
1.479 +// NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
1.480 +// i=j;
1.481 +// j=G.first(i);
1.482 +// j=++i;
1.483 +// bool b; b=true;
1.484 +// b=(i==INVALID); b=(i!=INVALID);
1.485 +// Node n(i);
1.486 +// n=i;
1.487 +// b=(i==j); b=(i!=j); b=(i<j);
1.488 +// //Node ->NodeIt conversion
1.489 +// NodeIt ni(G,n);
1.490 +// }
1.491 +// {
1.492 +// Edge i; Edge j(i); Edge k(INVALID);
1.493 +// i=j;
1.494 +// bool b; b=true;
1.495 +// b=(i==INVALID); b=(i!=INVALID);
1.496 +// b=(i==j); b=(i!=j); b=(i<j);
1.497 +// }
1.498 +// {
1.499 +// EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
1.500 +// i=j;
1.501 +// j=G.first(i);
1.502 +// j=++i;
1.503 +// bool b; b=true;
1.504 +// b=(i==INVALID); b=(i!=INVALID);
1.505 +// Edge e(i);
1.506 +// e=i;
1.507 +// b=(i==j); b=(i!=j); b=(i<j);
1.508 +// //Edge ->EdgeIt conversion
1.509 +// EdgeIt ei(G,e);
1.510 +// }
1.511 +// {
1.512 +// Node n;
1.513 +// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
1.514 +// i=j;
1.515 +// j=G.first(i,n);
1.516 +// j=++i;
1.517 +// bool b; b=true;
1.518 +// b=(i==INVALID); b=(i!=INVALID);
1.519 +// Edge e(i);
1.520 +// e=i;
1.521 +// b=(i==j); b=(i!=j); b=(i<j);
1.522 +// //Edge ->InEdgeIt conversion
1.523 +// InEdgeIt ei(G,e);
1.524 +// }
1.525 +// {
1.526 +// Node n;
1.527 +// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
1.528 +// i=j;
1.529 +// j=G.first(i,n);
1.530 +// j=++i;
1.531 +// bool b; b=true;
1.532 +// b=(i==INVALID); b=(i!=INVALID);
1.533 +// Edge e(i);
1.534 +// e=i;
1.535 +// b=(i==j); b=(i!=j); b=(i<j);
1.536 +// //Edge ->OutEdgeIt conversion
1.537 +// OutEdgeIt ei(G,e);
1.538 +// }
1.539 +// {
1.540 +// Node n,m;
1.541 +// n=m=INVALID;
1.542 +// Edge e;
1.543 +// e=INVALID;
1.544 +// n=G.tail(e);
1.545 +// n=G.head(e);
1.546 +// }
1.547 +// // id tests
1.548 +// { Node n; int i=G.id(n); i=i; }
1.549 +// { Edge e; int i=G.id(e); i=i; }
1.550 +// //NodeMap tests
1.551 +// {
1.552 +// Node k;
1.553 +// typename Graph::template NodeMap<int> m(G);
1.554 +// //Const map
1.555 +// typename Graph::template NodeMap<int> const &cm = m;
1.556 +// //Inicialize with default value
1.557 +// typename Graph::template NodeMap<int> mdef(G,12);
1.558 +// //Copy
1.559 +// typename Graph::template NodeMap<int> mm(cm);
1.560 +// //Copy from another type
1.561 +// typename Graph::template NodeMap<double> dm(cm);
1.562 +// //Copy to more complex type
1.563 +// typename Graph::template NodeMap<DummyType> em(cm);
1.564 +// int v;
1.565 +// v=m[k]; m[k]=v; m.set(k,v);
1.566 +// v=cm[k];
1.567 +
1.568 +// m=cm;
1.569 +// dm=cm; //Copy from another type
1.570 +// em=cm; //Copy to more complex type
1.571 +// {
1.572 +// //Check the typedef's
1.573 +// typename Graph::template NodeMap<int>::ValueType val;
1.574 +// val=1;
1.575 +// typename Graph::template NodeMap<int>::KeyType key;
1.576 +// key = typename Graph::NodeIt(G);
1.577 +// }
1.578 +// }
1.579 +// { //bool NodeMap
1.580 +// Node k;
1.581 +// typename Graph::template NodeMap<bool> m(G);
1.582 +// typename Graph::template NodeMap<bool> const &cm = m; //Const map
1.583 +// //Inicialize with default value
1.584 +// typename Graph::template NodeMap<bool> mdef(G,12);
1.585 +// typename Graph::template NodeMap<bool> mm(cm); //Copy
1.586 +// typename Graph::template NodeMap<int> dm(cm); //Copy from another type
1.587 +// bool v;
1.588 +// v=m[k]; m[k]=v; m.set(k,v);
1.589 +// v=cm[k];
1.590 +
1.591 +// m=cm;
1.592 +// dm=cm; //Copy from another type
1.593 +// m=dm; //Copy to another type
1.594 +
1.595 +// {
1.596 +// //Check the typedef's
1.597 +// typename Graph::template NodeMap<bool>::ValueType val;
1.598 +// val=true;
1.599 +// typename Graph::template NodeMap<bool>::KeyType key;
1.600 +// key= typename Graph::NodeIt(G);
1.601 +// }
1.602 +// }
1.603 +// //EdgeMap tests
1.604 +// {
1.605 +// Edge k;
1.606 +// typename Graph::template EdgeMap<int> m(G);
1.607 +// typename Graph::template EdgeMap<int> const &cm = m; //Const map
1.608 +// //Inicialize with default value
1.609 +// typename Graph::template EdgeMap<int> mdef(G,12);
1.610 +// typename Graph::template EdgeMap<int> mm(cm); //Copy
1.611 +// typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
1.612 +// int v;
1.613 +// v=m[k]; m[k]=v; m.set(k,v);
1.614 +// v=cm[k];
1.615 +
1.616 +// m=cm;
1.617 +// dm=cm; //Copy from another type
1.618 +// {
1.619 +// //Check the typedef's
1.620 +// typename Graph::template EdgeMap<int>::ValueType val;
1.621 +// val=1;
1.622 +// typename Graph::template EdgeMap<int>::KeyType key;
1.623 +// key= typename Graph::EdgeIt(G);
1.624 +// }
1.625 +// }
1.626 +// { //bool EdgeMap
1.627 +// Edge k;
1.628 +// typename Graph::template EdgeMap<bool> m(G);
1.629 +// typename Graph::template EdgeMap<bool> const &cm = m; //Const map
1.630 +// //Inicialize with default value
1.631 +// typename Graph::template EdgeMap<bool> mdef(G,12);
1.632 +// typename Graph::template EdgeMap<bool> mm(cm); //Copy
1.633 +// typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
1.634 +// bool v;
1.635 +// v=m[k]; m[k]=v; m.set(k,v);
1.636 +// v=cm[k];
1.637 +
1.638 +// m=cm;
1.639 +// dm=cm; //Copy from another type
1.640 +// m=dm; //Copy to another type
1.641 +// {
1.642 +// //Check the typedef's
1.643 +// typename Graph::template EdgeMap<bool>::ValueType val;
1.644 +// val=true;
1.645 +// typename Graph::template EdgeMap<bool>::KeyType key;
1.646 +// key= typename Graph::EdgeIt(G);
1.647 +// }
1.648 +// }
1.649 +// }
1.650 +
1.651 +// /// An empty non-static graph class.
1.652 +
1.653 +// /// This class provides everything that \ref StaticGraph
1.654 +// /// with additional functionality which enables to build a
1.655 +// /// graph from scratch.
1.656 +// class ExtendableGraph : public StaticGraph
1.657 +// {
1.658 +// public:
1.659 +// /// Defalult constructor.
1.660 +
1.661 +// /// Defalult constructor.
1.662 +// ///
1.663 +// ExtendableGraph() { }
1.664 +// ///Add a new node to the graph.
1.665 +
1.666 +// /// \return the new node.
1.667 +// ///
1.668 +// Node addNode() { return INVALID; }
1.669 +// ///Add a new edge to the graph.
1.670 +
1.671 +// ///Add a new edge to the graph with tail node \c t
1.672 +// ///and head node \c h.
1.673 +// ///\return the new edge.
1.674 +// Edge addEdge(Node h, Node t) { return INVALID; }
1.675 +
1.676 +// /// Resets the graph.
1.677 +
1.678 +// /// This function deletes all edges and nodes of the graph.
1.679 +// /// It also frees the memory allocated to store them.
1.680 +// /// \todo It might belong to \ref ErasableGraph.
1.681 +// void clear() { }
1.682 +// };
1.683 +
1.684 +
1.685 +// ///\brief Checks whether \c G meets the
1.686 +// ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept
1.687 +// template<class Graph> void checkCompileExtendableGraph(Graph &G)
1.688 +// {
1.689 +// checkCompileStaticGraph(G);
1.690 +
1.691 +// typedef typename Graph::Node Node;
1.692 +// typedef typename Graph::NodeIt NodeIt;
1.693 +// typedef typename Graph::Edge Edge;
1.694 +// typedef typename Graph::EdgeIt EdgeIt;
1.695 +// typedef typename Graph::InEdgeIt InEdgeIt;
1.696 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.697 +
1.698 +// Node n,m;
1.699 +// n=G.addNode();
1.700 +// m=G.addNode();
1.701 +// Edge e;
1.702 +// e=G.addEdge(n,m);
1.703 +
1.704 +// // G.clear();
1.705 +// }
1.706 +
1.707 +
1.708 +// /// An empty erasable graph class.
1.709 +
1.710 +// /// This class is an extension of \ref ExtendableGraph. It also makes it
1.711 +// /// possible to erase edges or nodes.
1.712 +// class ErasableGraph : public ExtendableGraph
1.713 +// {
1.714 +// public:
1.715 +// /// Defalult constructor.
1.716 +
1.717 +// /// Defalult constructor.
1.718 +// ///
1.719 +// ErasableGraph() { }
1.720 +// /// Deletes a node.
1.721 +
1.722 +// /// Deletes node \c n node.
1.723 +// ///
1.724 +// void erase(Node n) { }
1.725 +// /// Deletes an edge.
1.726 +
1.727 +// /// Deletes edge \c e edge.
1.728 +// ///
1.729 +// void erase(Edge e) { }
1.730 +// };
1.731 +
1.732 +// template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
1.733 +// {
1.734 +// typename Graph::Edge e;
1.735 +// G.erase(e);
1.736 +// }
1.737 +
1.738 +// template<class Graph> void checkCompileGraphEraseNode(Graph &G)
1.739 +// {
1.740 +// typename Graph::Node n;
1.741 +// G.erase(n);
1.742 +// }
1.743 +
1.744 +// ///\brief Checks whether \c G meets the
1.745 +// ///\ref lemon::concept::EresableGraph "EresableGraph" concept
1.746 +// template<class Graph> void checkCompileErasableGraph(Graph &G)
1.747 +// {
1.748 +// checkCompileExtendableGraph(G);
1.749 +// checkCompileGraphEraseNode(G);
1.750 +// checkCompileGraphEraseEdge(G);
1.751 +// }
1.752 +
1.753 +// ///Checks whether a graph has findEdge() member function.
1.754 +
1.755 +// ///\todo findEdge() might be a global function.
1.756 +// ///
1.757 +// template<class Graph> void checkCompileGraphFindEdge(Graph &G)
1.758 +// {
1.759 +// typedef typename Graph::NodeIt Node;
1.760 +// typedef typename Graph::NodeIt NodeIt;
1.761 +
1.762 +// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
1.763 +// G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
1.764 +// }
1.765 +
1.766 +
1.767 +
1.768 + /************* New GraphBase stuff **************/
1.769 +
1.770 +
1.771 + /// \bug The nodes and edges are not allowed to inherit from the
1.772 + /// same baseclass.
1.773 +
1.774 + class BaseGraphItem {
1.775 + public:
1.776 + BaseGraphItem() {}
1.777 + BaseGraphItem(Invalid) {}
1.778 +
1.779 + // We explicitely list these:
1.780 + BaseGraphItem(BaseGraphItem const&) {}
1.781 + BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
1.782 +
1.783 + bool operator==(BaseGraphItem) const { return false; }
1.784 + bool operator!=(BaseGraphItem) const { return false; }
1.785 +
1.786 + // Technical requirement. Do we really need this?
1.787 + bool operator<(BaseGraphItem) const { return false; }
1.788 + };
1.789 +
1.790 +
1.791 + /// A minimal GraphBase concept
1.792 +
1.793 + /// This class describes a minimal concept which can be extended to a
1.794 + /// full-featured graph with \ref GraphFactory.
1.795 + class GraphBase {
1.796 + public:
1.797 +
1.798 + GraphBase() {}
1.799 +
1.800 +
1.801 + /// \bug Nodes and Edges are comparable each other
1.802 +
1.803 + class Node : public BaseGraphItem {};
1.804 + class Edge : public BaseGraphItem {};
1.805 +
1.806 + // Graph operation
1.807 + void firstNode(Node &n) const { }
1.808 + void firstEdge(Edge &e) const { }
1.809 +
1.810 + void firstOutEdge(Edge &e, Node) const { }
1.811 + void firstInEdge(Edge &e, Node) const { }
1.812 +
1.813 + void nextNode(Node &n) const { }
1.814 + void nextEdge(Edge &e) const { }
1.815 +
1.816 +
1.817 + // Question: isn't it reasonable if this methods have a Node
1.818 + // parameter? Like this:
1.819 + // Edge& nextOut(Edge &e, Node) const { return e; }
1.820 + void nextOutEdge(Edge &e) const { }
1.821 + void nextInEdge(Edge &e) const { }
1.822 +
1.823 + Node head(Edge) const { return Node(); }
1.824 + Node tail(Edge) const { return Node(); }
1.825 +
1.826 +
1.827 + // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
1.828 + // concept?
1.829 +
1.830 +
1.831 + // Maps.
1.832 + //
1.833 + // We need a special slimer concept which does not provide maps (it
1.834 + // wouldn't be strictly slimer, cause for map-factory id() & friends
1.835 + // a required...)
1.836 +
1.837 + template<typename T>
1.838 + class NodeMap : public GraphMap<Node, T, GraphBase> {};
1.839 +
1.840 + template<typename T>
1.841 + class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
1.842 + };
1.843 +
1.844 +
1.845 +
1.846 + /**************** Concept checking classes ****************/
1.847 +
1.848 + template<typename BGI>
1.849 + struct BaseGraphItemConcept {
1.850 + void constraints() {
1.851 + BGI i1;
1.852 + BGI i2 = i1;
1.853 + BGI i3 = INVALID;
1.854 +
1.855 + i1 = i3;
1.856 + if( i1 == i3 ) {
1.857 + if ( i2 != i3 && i3 < i2 )
1.858 + return;
1.859 + }
1.860 + }
1.861 + };
1.862 +
1.863 +
1.864 +
1.865 + class StaticGraph
1.866 + : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
1.867 + public:
1.868 + typedef BaseGraphComponent::Node Node;
1.869 + typedef BaseGraphComponent::Edge Edge;
1.870 + };
1.871 +
1.872 + template <typename Graph>
1.873 + struct StaticGraphConcept {
1.874 + void constraints() {
1.875 + function_requires<BaseGraphComponentConcept<Graph> >();
1.876 + function_requires<IterableGraphComponentConcept<Graph> >();
1.877 + function_requires<MappableGraphComponentConcept<Graph> >();
1.878 + }
1.879 + Graph& graph;
1.880 + };
1.881 +
1.882 + class ExtendableGraph
1.883 + : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
1.884 + public:
1.885 + typedef BaseGraphComponent::Node Node;
1.886 + typedef BaseGraphComponent::Edge Edge;
1.887 + };
1.888 +
1.889 + template <typename Graph>
1.890 + struct ExtendableGraphConcept {
1.891 + void constraints() {
1.892 + function_requires<StaticGraphConcept<Graph> >();
1.893 + function_requires<ExtendableGraphComponentConcept<Graph> >();
1.894 + function_requires<ClearableGraphComponentConcept<Graph> >();
1.895 + }
1.896 + Graph& graph;
1.897 + };
1.898 +
1.899 + class ErasableGraph
1.900 + : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
1.901 + public:
1.902 + typedef BaseGraphComponent::Node Node;
1.903 + typedef BaseGraphComponent::Edge Edge;
1.904 + };
1.905 +
1.906 + template <typename Graph>
1.907 + struct ErasableGraphConcept {
1.908 + void constraints() {
1.909 + function_requires<ExtendableGraphConcept<Graph> >();
1.910 + function_requires<ErasableGraphComponentConcept<Graph> >();
1.911 + }
1.912 + Graph& graph;
1.913 + };
1.914 +
1.915 + // @}
1.916 + } //namespace concept
1.917 +} //namespace lemon
1.918 +
1.919 +
1.920 +
1.921 +#endif // LEMON_CONCEPT_GRAPH_H