1.1 --- a/src/lemon/concept/graph.h Sat Nov 13 17:47:44 2004 +0000
1.2 +++ b/src/lemon/concept/graph.h Sat Nov 13 21:37:54 2004 +0000
1.3 @@ -101,14 +101,6 @@
1.4 // ///
1.5 // bool operator!=(Node) const { return true; }
1.6
1.7 -// ///Comparison operator.
1.8 -
1.9 -// ///This is a strict ordering between the nodes.
1.10 -// ///
1.11 -// ///This ordering can be different from the order in which NodeIt
1.12 -// ///goes through the nodes.
1.13 -// ///\todo Possibly we don't need it.
1.14 -// bool operator<(Node) const { return true; }
1.15 // };
1.16
1.17 // /// This iterator goes through each node.
1.18 @@ -188,14 +180,6 @@
1.19 // /// \sa operator==(Node n)
1.20 // ///
1.21 // bool operator!=(Edge) const { return true; }
1.22 -// ///Comparison operator.
1.23 -
1.24 -// ///This is a strict ordering between the nodes.
1.25 -// ///
1.26 -// ///This ordering can be different from the order in which NodeIt
1.27 -// ///goes through the nodes.
1.28 -// ///\todo Possibly we don't need it.
1.29 -// bool operator<(Edge) const { return true; }
1.30 // };
1.31
1.32 // /// This iterator goes trough the outgoing edges of a node.
1.33 @@ -339,30 +323,6 @@
1.34 // /// edge of the corresponding node.
1.35 // EdgeIt& operator++() { return *this; }
1.36 // };
1.37 -
1.38 -// /// First node of the graph.
1.39 -
1.40 -// /// \retval i the first node.
1.41 -// /// \return the first node.
1.42 -// ///
1.43 -// NodeIt& first(NodeIt& i) const { return i; }
1.44 -
1.45 -// /// The first incoming edge.
1.46 -
1.47 -// /// The first incoming edge.
1.48 -// ///
1.49 -// InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
1.50 -// /// The first outgoing edge.
1.51 -
1.52 -// /// The first outgoing edge.
1.53 -// ///
1.54 -// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
1.55 -// /// The first edge of the Graph.
1.56 -
1.57 -// /// The first edge of the Graph.
1.58 -// ///
1.59 -// EdgeIt& first(EdgeIt& i) const { return i; }
1.60 -
1.61 // ///Gives back the target node of an edge.
1.62
1.63 // ///Gives back the target node of an edge.
1.64 @@ -373,40 +333,15 @@
1.65 // ///Gives back the source node of an edge.
1.66 // ///
1.67 // Node source(Edge) const { return INVALID; }
1.68 -
1.69 -// ///Gives back the \e id of a node.
1.70 -
1.71 -// ///\warning Not all graph structures provide this feature.
1.72 -// ///
1.73 -// ///\todo Should each graph provide \c id?
1.74 -// int id(const Node&) const { return 0; }
1.75 -// ///Gives back the \e id of an edge.
1.76 -
1.77 -// ///\warning Not all graph structures provide this feature.
1.78 -// ///
1.79 -// ///\todo Should each graph provide \c id?
1.80 -// int id(const Edge&) const { return 0; }
1.81 -
1.82 -// ///\e
1.83 -
1.84 -// ///\todo Should it be in the concept?
1.85 -// ///
1.86 -// int nodeNum() const { return 0; }
1.87 -// ///\e
1.88 -
1.89 -// ///\todo Should it be in the concept?
1.90 -// ///
1.91 -// int edgeNum() const { return 0; }
1.92 -
1.93 -
1.94 -// ///Reference map of the nodes to type \c T.
1.95 +// /// Read write map of the nodes to type \c T.
1.96
1.97 // /// \ingroup concept
1.98 -// ///Reference map of the nodes to type \c T.
1.99 +// /// ReadWrite map of the nodes to type \c T.
1.100 // /// \sa Reference
1.101 // /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.102 // /// needs some extra attention!
1.103 -// template<class T> class NodeMap : public ReferenceMap< Node, T >
1.104 +// template<class T>
1.105 +// class NodeMap : public ReadWriteMap< Node, T >
1.106 // {
1.107 // public:
1.108
1.109 @@ -416,21 +351,21 @@
1.110 // NodeMap(const StaticGraph&, T) { }
1.111
1.112 // ///Copy constructor
1.113 -// template<typename TT> NodeMap(const NodeMap<TT>&) { }
1.114 +// NodeMap(const NodeMap&) { }
1.115 // ///Assignment operator
1.116 -// template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
1.117 -// { return *this; }
1.118 +// NodeMap& operator=(const NodeMap&) { return *this; }
1.119 +// // \todo fix this concept
1.120 // };
1.121
1.122 -// ///Reference map of the edges to type \c T.
1.123 +// /// Read write map of the edges to type \c T.
1.124
1.125 // /// \ingroup concept
1.126 // ///Reference map of the edges to type \c T.
1.127 // /// \sa Reference
1.128 // /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.129 // /// needs some extra attention!
1.130 -// template<class T> class EdgeMap
1.131 -// : public ReferenceMap<Edge,T>
1.132 +// template<class T>
1.133 +// class EdgeMap : public ReadWriteMap<Edge,T>
1.134 // {
1.135 // public:
1.136
1.137 @@ -438,213 +373,14 @@
1.138 // EdgeMap(const StaticGraph&) { }
1.139 // ///\e
1.140 // EdgeMap(const StaticGraph&, T) { }
1.141 -
1.142 // ///Copy constructor
1.143 -// template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
1.144 +// EdgeMap(const EdgeMap&) { }
1.145 // ///Assignment operator
1.146 -// template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
1.147 -// { return *this; }
1.148 +// EdgeMap& operator=(const EdgeMap&) { return *this; }
1.149 +// // \todo fix this concept
1.150 // };
1.151 // };
1.152
1.153 -// struct DummyType {
1.154 -// int value;
1.155 -// DummyType() {}
1.156 -// DummyType(int p) : value(p) {}
1.157 -// DummyType& operator=(int p) { value = p; return *this;}
1.158 -// };
1.159 -
1.160 -// ///\brief Checks whether \c G meets the
1.161 -// ///\ref lemon::concept::StaticGraph "StaticGraph" concept
1.162 -// template<class Graph> void checkCompileStaticGraph(Graph &G)
1.163 -// {
1.164 -// typedef typename Graph::Node Node;
1.165 -// typedef typename Graph::NodeIt NodeIt;
1.166 -// typedef typename Graph::Edge Edge;
1.167 -// typedef typename Graph::EdgeIt EdgeIt;
1.168 -// typedef typename Graph::InEdgeIt InEdgeIt;
1.169 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.170 -
1.171 -// {
1.172 -// Node i; Node j(i); Node k(INVALID);
1.173 -// i=j;
1.174 -// bool b; b=true;
1.175 -// b=(i==INVALID); b=(i!=INVALID);
1.176 -// b=(i==j); b=(i!=j); b=(i<j);
1.177 -// }
1.178 -// {
1.179 -// NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
1.180 -// i=j;
1.181 -// j=G.first(i);
1.182 -// j=++i;
1.183 -// bool b; b=true;
1.184 -// b=(i==INVALID); b=(i!=INVALID);
1.185 -// Node n(i);
1.186 -// n=i;
1.187 -// b=(i==j); b=(i!=j); b=(i<j);
1.188 -// //Node ->NodeIt conversion
1.189 -// NodeIt ni(G,n);
1.190 -// }
1.191 -// {
1.192 -// Edge i; Edge j(i); Edge k(INVALID);
1.193 -// i=j;
1.194 -// bool b; b=true;
1.195 -// b=(i==INVALID); b=(i!=INVALID);
1.196 -// b=(i==j); b=(i!=j); b=(i<j);
1.197 -// }
1.198 -// {
1.199 -// EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
1.200 -// i=j;
1.201 -// j=G.first(i);
1.202 -// j=++i;
1.203 -// bool b; b=true;
1.204 -// b=(i==INVALID); b=(i!=INVALID);
1.205 -// Edge e(i);
1.206 -// e=i;
1.207 -// b=(i==j); b=(i!=j); b=(i<j);
1.208 -// //Edge ->EdgeIt conversion
1.209 -// EdgeIt ei(G,e);
1.210 -// }
1.211 -// {
1.212 -// Node n;
1.213 -// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
1.214 -// i=j;
1.215 -// j=G.first(i,n);
1.216 -// j=++i;
1.217 -// bool b; b=true;
1.218 -// b=(i==INVALID); b=(i!=INVALID);
1.219 -// Edge e(i);
1.220 -// e=i;
1.221 -// b=(i==j); b=(i!=j); b=(i<j);
1.222 -// //Edge ->InEdgeIt conversion
1.223 -// InEdgeIt ei(G,e);
1.224 -// }
1.225 -// {
1.226 -// Node n;
1.227 -// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
1.228 -// i=j;
1.229 -// j=G.first(i,n);
1.230 -// j=++i;
1.231 -// bool b; b=true;
1.232 -// b=(i==INVALID); b=(i!=INVALID);
1.233 -// Edge e(i);
1.234 -// e=i;
1.235 -// b=(i==j); b=(i!=j); b=(i<j);
1.236 -// //Edge ->OutEdgeIt conversion
1.237 -// OutEdgeIt ei(G,e);
1.238 -// }
1.239 -// {
1.240 -// Node n,m;
1.241 -// n=m=INVALID;
1.242 -// Edge e;
1.243 -// e=INVALID;
1.244 -// n=G.source(e);
1.245 -// n=G.target(e);
1.246 -// }
1.247 -// // id tests
1.248 -// { Node n; int i=G.id(n); i=i; }
1.249 -// { Edge e; int i=G.id(e); i=i; }
1.250 -// //NodeMap tests
1.251 -// {
1.252 -// Node k;
1.253 -// typename Graph::template NodeMap<int> m(G);
1.254 -// //Const map
1.255 -// typename Graph::template NodeMap<int> const &cm = m;
1.256 -// //Inicialize with default value
1.257 -// typename Graph::template NodeMap<int> mdef(G,12);
1.258 -// //Copy
1.259 -// typename Graph::template NodeMap<int> mm(cm);
1.260 -// //Copy from another type
1.261 -// typename Graph::template NodeMap<double> dm(cm);
1.262 -// //Copy to more complex type
1.263 -// typename Graph::template NodeMap<DummyType> em(cm);
1.264 -// int v;
1.265 -// v=m[k]; m[k]=v; m.set(k,v);
1.266 -// v=cm[k];
1.267 -
1.268 -// m=cm;
1.269 -// dm=cm; //Copy from another type
1.270 -// em=cm; //Copy to more complex type
1.271 -// {
1.272 -// //Check the typedef's
1.273 -// typename Graph::template NodeMap<int>::Value val;
1.274 -// val=1;
1.275 -// typename Graph::template NodeMap<int>::Key key;
1.276 -// key = typename Graph::NodeIt(G);
1.277 -// }
1.278 -// }
1.279 -// { //bool NodeMap
1.280 -// Node k;
1.281 -// typename Graph::template NodeMap<bool> m(G);
1.282 -// typename Graph::template NodeMap<bool> const &cm = m; //Const map
1.283 -// //Inicialize with default value
1.284 -// typename Graph::template NodeMap<bool> mdef(G,12);
1.285 -// typename Graph::template NodeMap<bool> mm(cm); //Copy
1.286 -// typename Graph::template NodeMap<int> dm(cm); //Copy from another type
1.287 -// bool v;
1.288 -// v=m[k]; m[k]=v; m.set(k,v);
1.289 -// v=cm[k];
1.290 -
1.291 -// m=cm;
1.292 -// dm=cm; //Copy from another type
1.293 -// m=dm; //Copy to another type
1.294 -
1.295 -// {
1.296 -// //Check the typedef's
1.297 -// typename Graph::template NodeMap<bool>::Value val;
1.298 -// val=true;
1.299 -// typename Graph::template NodeMap<bool>::Key key;
1.300 -// key= typename Graph::NodeIt(G);
1.301 -// }
1.302 -// }
1.303 -// //EdgeMap tests
1.304 -// {
1.305 -// Edge k;
1.306 -// typename Graph::template EdgeMap<int> m(G);
1.307 -// typename Graph::template EdgeMap<int> const &cm = m; //Const map
1.308 -// //Inicialize with default value
1.309 -// typename Graph::template EdgeMap<int> mdef(G,12);
1.310 -// typename Graph::template EdgeMap<int> mm(cm); //Copy
1.311 -// typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
1.312 -// int v;
1.313 -// v=m[k]; m[k]=v; m.set(k,v);
1.314 -// v=cm[k];
1.315 -
1.316 -// m=cm;
1.317 -// dm=cm; //Copy from another type
1.318 -// {
1.319 -// //Check the typedef's
1.320 -// typename Graph::template EdgeMap<int>::Value val;
1.321 -// val=1;
1.322 -// typename Graph::template EdgeMap<int>::Key key;
1.323 -// key= typename Graph::EdgeIt(G);
1.324 -// }
1.325 -// }
1.326 -// { //bool EdgeMap
1.327 -// Edge k;
1.328 -// typename Graph::template EdgeMap<bool> m(G);
1.329 -// typename Graph::template EdgeMap<bool> const &cm = m; //Const map
1.330 -// //Inicialize with default value
1.331 -// typename Graph::template EdgeMap<bool> mdef(G,12);
1.332 -// typename Graph::template EdgeMap<bool> mm(cm); //Copy
1.333 -// typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
1.334 -// bool v;
1.335 -// v=m[k]; m[k]=v; m.set(k,v);
1.336 -// v=cm[k];
1.337 -
1.338 -// m=cm;
1.339 -// dm=cm; //Copy from another type
1.340 -// m=dm; //Copy to another type
1.341 -// {
1.342 -// //Check the typedef's
1.343 -// typename Graph::template EdgeMap<bool>::Value val;
1.344 -// val=true;
1.345 -// typename Graph::template EdgeMap<bool>::Key key;
1.346 -// key= typename Graph::EdgeIt(G);
1.347 -// }
1.348 -// }
1.349 -// }
1.350 -
1.351 // /// An empty non-static graph class.
1.352
1.353 // /// This class provides everything that \ref StaticGraph
1.354 @@ -665,10 +401,10 @@
1.355 // Node addNode() { return INVALID; }
1.356 // ///Add a new edge to the graph.
1.357
1.358 -// ///Add a new edge to the graph with source node \c t
1.359 -// ///and target node \c h.
1.360 +// ///Add a new edge to the graph with source node \c s
1.361 +// ///and target node \c t.
1.362 // ///\return the new edge.
1.363 -// Edge addEdge(Node h, Node t) { return INVALID; }
1.364 +// Edge addEdge(Node s, Node t) { return INVALID; }
1.365
1.366 // /// Resets the graph.
1.367
1.368 @@ -678,30 +414,6 @@
1.369 // void clear() { }
1.370 // };
1.371
1.372 -
1.373 -// ///\brief Checks whether \c G meets the
1.374 -// ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept
1.375 -// template<class Graph> void checkCompileExtendableGraph(Graph &G)
1.376 -// {
1.377 -// checkCompileStaticGraph(G);
1.378 -
1.379 -// typedef typename Graph::Node Node;
1.380 -// typedef typename Graph::NodeIt NodeIt;
1.381 -// typedef typename Graph::Edge Edge;
1.382 -// typedef typename Graph::EdgeIt EdgeIt;
1.383 -// typedef typename Graph::InEdgeIt InEdgeIt;
1.384 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.385 -
1.386 -// Node n,m;
1.387 -// n=G.addNode();
1.388 -// m=G.addNode();
1.389 -// Edge e;
1.390 -// e=G.addEdge(n,m);
1.391 -
1.392 -// // G.clear();
1.393 -// }
1.394 -
1.395 -
1.396 // /// An empty erasable graph class.
1.397
1.398 // /// This class is an extension of \ref ExtendableGraph. It also makes it
1.399 @@ -725,43 +437,8 @@
1.400 // ///
1.401 // void erase(Edge e) { }
1.402 // };
1.403 +
1.404
1.405 -// template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
1.406 -// {
1.407 -// typename Graph::Edge e;
1.408 -// G.erase(e);
1.409 -// }
1.410 -
1.411 -// template<class Graph> void checkCompileGraphEraseNode(Graph &G)
1.412 -// {
1.413 -// typename Graph::Node n;
1.414 -// G.erase(n);
1.415 -// }
1.416 -
1.417 -// ///\brief Checks whether \c G meets the
1.418 -// ///\ref lemon::concept::EresableGraph "EresableGraph" concept
1.419 -// template<class Graph> void checkCompileErasableGraph(Graph &G)
1.420 -// {
1.421 -// checkCompileExtendableGraph(G);
1.422 -// checkCompileGraphEraseNode(G);
1.423 -// checkCompileGraphEraseEdge(G);
1.424 -// }
1.425 -
1.426 -// ///Checks whether a graph has findEdge() member function.
1.427 -
1.428 -// ///\todo findEdge() might be a global function.
1.429 -// ///
1.430 -// template<class Graph> void checkCompileGraphFindEdge(Graph &G)
1.431 -// {
1.432 -// typedef typename Graph::NodeIt Node;
1.433 -// typedef typename Graph::NodeIt NodeIt;
1.434 -
1.435 -// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
1.436 -// G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
1.437 -// }
1.438 -
1.439 -
1.440 -
1.441 /************* New GraphBase stuff **************/
1.442
1.443
1.444 @@ -815,10 +492,10 @@
1.445 // a required...)
1.446
1.447 template<typename T>
1.448 - class NodeMap : public GraphMap<Node, T, GraphBase> {};
1.449 + class NodeMap : public GraphMap<GraphBase, Node, T> {};
1.450
1.451 template<typename T>
1.452 - class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
1.453 + class EdgeMap : public GraphMap<GraphBase, Node, T> {};
1.454 };
1.455
1.456
1.457 @@ -833,14 +510,14 @@
1.458 public:
1.459 typedef BaseGraphComponent::Node Node;
1.460 typedef BaseGraphComponent::Edge Edge;
1.461 - };
1.462
1.463 - template <typename Graph>
1.464 - struct StaticGraphConcept {
1.465 - void constraints() {
1.466 - function_requires<IterableGraphComponentConcept<Graph> >();
1.467 - function_requires<MappableGraphComponentConcept<Graph> >();
1.468 - }
1.469 + template <typename _Graph>
1.470 + struct Constraints {
1.471 + void constraints() {
1.472 + checkConcept<IterableGraphComponent, _Graph>();
1.473 + checkConcept<MappableGraphComponent, _Graph>();
1.474 + }
1.475 + };
1.476 };
1.477
1.478 class ExtendableGraph
1.479 @@ -849,15 +526,15 @@
1.480 public:
1.481 typedef BaseGraphComponent::Node Node;
1.482 typedef BaseGraphComponent::Edge Edge;
1.483 - };
1.484
1.485 - template <typename Graph>
1.486 - struct ExtendableGraphConcept {
1.487 - void constraints() {
1.488 - function_requires<StaticGraphConcept<Graph> >();
1.489 - function_requires<ExtendableGraphComponentConcept<Graph> >();
1.490 - function_requires<ClearableGraphComponentConcept<Graph> >();
1.491 - }
1.492 + template <typename _Graph>
1.493 + struct Constraints {
1.494 + void constraints() {
1.495 + checkConcept<StaticGraph, _Graph >();
1.496 + checkConcept<ExtendableGraphComponent, _Graph >();
1.497 + checkConcept<ClearableGraphComponent, _Graph >();
1.498 + }
1.499 + };
1.500 };
1.501
1.502 class ErasableGraph
1.503 @@ -866,14 +543,14 @@
1.504 public:
1.505 typedef BaseGraphComponent::Node Node;
1.506 typedef BaseGraphComponent::Edge Edge;
1.507 - };
1.508
1.509 - template <typename Graph>
1.510 - struct ErasableGraphConcept {
1.511 - void constraints() {
1.512 - function_requires<ExtendableGraphConcept<Graph> >();
1.513 - function_requires<ErasableGraphComponentConcept<Graph> >();
1.514 - }
1.515 + template <typename _Graph>
1.516 + struct Constraints {
1.517 + void constraints() {
1.518 + checkConcept<ExtendableGraph, _Graph >();
1.519 + checkConcept<ErasableGraphComponent, _Graph >();
1.520 + }
1.521 + };
1.522 };
1.523
1.524 // @}