1.1 --- a/src/lemon/skeletons/graph.h Thu Nov 04 18:52:31 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,918 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/skeletons/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_SKELETON_GRAPH_H
1.21 -#define LEMON_SKELETON_GRAPH_H
1.22 -
1.23 -///\ingroup skeletons
1.24 -///\file
1.25 -///\brief Declaration of Graph.
1.26 -
1.27 -#include <lemon/invalid.h>
1.28 -#include <lemon/skeletons/maps.h>
1.29 -#include <lemon/concept_check.h>
1.30 -#include <lemon/skeletons/graph_component.h>
1.31 -
1.32 -namespace lemon {
1.33 - namespace skeleton {
1.34 -
1.35 - /// \addtogroup skeletons
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 skeletons
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 skeletons
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::skeleton::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::skeleton::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::skeleton::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 skeleton
1.917 -} //namespace lemon
1.918 -
1.919 -
1.920 -
1.921 -#endif // LEMON_SKELETON_GRAPH_H