1.1 --- a/doc/Doxyfile Thu Nov 04 18:52:31 2004 +0000
1.2 +++ b/doc/Doxyfile Thu Nov 04 20:24:59 2004 +0000
1.3 @@ -431,7 +431,7 @@
1.4 groups.dox \
1.5 namespaces.dox \
1.6 ../src/lemon \
1.7 - ../src/lemon/skeletons \
1.8 + ../src/lemon/concept \
1.9 ../src/test/test_tools.h
1.10
1.11 # If the value of the INPUT tag contains directories, you can use the
2.1 --- a/doc/graphs.dox Thu Nov 04 18:52:31 2004 +0000
2.2 +++ b/doc/graphs.dox Thu Nov 04 20:24:59 2004 +0000
2.3 @@ -9,31 +9,31 @@
2.4
2.5
2.6 Each graph should meet the
2.7 -\ref lemon::skeleton::StaticGraph "StaticGraph" concept.
2.8 +\ref lemon::concept::StaticGraph "StaticGraph" concept.
2.9 This concept does not
2.10 makes it possible to change the graph (i.e. it is not possible to add
2.11 or delete edges or nodes). Most of the graph algorithms will run on
2.12 these graphs.
2.13
2.14 The graphs meeting the
2.15 -\ref lemon::skeleton::ExtendableGraph "ExtendableGraph"
2.16 +\ref lemon::concept::ExtendableGraph "ExtendableGraph"
2.17 concept allow node and
2.18 edge addition. You can also "clear" (i.e. erase all edges and nodes)
2.19 such a graph.
2.20
2.21 In case of graphs meeting the full feature
2.22 -\ref lemon::skeleton::ErasableGraph "ErasableGraph"
2.23 +\ref lemon::concept::ErasableGraph "ErasableGraph"
2.24 concept
2.25 you can also erase individual edges and node in arbitrary order.
2.26
2.27 The implemented graph structures are the following.
2.28 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
2.29 -the \ref lemon::skeleton::ErasableGraph "ErasableGraph" concept
2.30 +the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
2.31 and it also have some convenience features.
2.32 \li \ref lemon::SmartGraph "SmartGraph" is a more memory
2.33 efficient version of \ref lemon::ListGraph "ListGraph". The
2.34 price of it is that it only meets the
2.35 -\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept,
2.36 +\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept,
2.37 so you cannot delete individual edges or nodes.
2.38 \li \ref lemon::SymListGraph "SymListGraph" and
2.39 \ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to
2.40 @@ -45,7 +45,7 @@
2.41 attach data to the edges in such a way that the stored data
2.42 are shared by the edge pairs.
2.43 \li \ref lemon::FullGraph "FullGraph"
2.44 -implements a full graph. It is a \ref lemon::skeleton::StaticGraph, so you cannot
2.45 +implements a full graph. It is a \ref lemon::concept::StaticGraph, so you cannot
2.46 change the number of nodes once it is constructed. It is extremely memory
2.47 efficient: it uses constant amount of memory independently from the number of
2.48 the nodes of the graph. Of course, the size of the \ref maps "NodeMap"'s and
3.1 --- a/doc/groups.dox Thu Nov 04 18:52:31 2004 +0000
3.2 +++ b/doc/groups.dox Thu Nov 04 20:24:59 2004 +0000
3.3 @@ -80,12 +80,13 @@
3.4 */
3.5
3.6 /**
3.7 -@defgroup skeletons Skeletons
3.8 -\brief Skeletons (a.k.a. concept checking classes)
3.9 +@defgroup concept Concept
3.10 +\brief Skeleton classes and concept checking classes
3.11
3.12 -This group describes the data/algorithm skeletons implemented in LEMON in
3.13 -order to make it easier to check if a certain template class or
3.14 -template function is correctly implemented.
3.15 +This group describes the data/algorithm skeletons and concept checking
3.16 +classes implemented in LEMON. These classes exist in order to make it
3.17 +easier to check if a certain template class or template function is
3.18 +correctly implemented.
3.19 */
3.20
3.21
4.1 --- a/doc/namespaces.dox Thu Nov 04 18:52:31 2004 +0000
4.2 +++ b/doc/namespaces.dox Thu Nov 04 20:24:59 2004 +0000
4.3 @@ -8,5 +8,5 @@
4.4
4.5 /// \todo Some more detailed description would be nice here.
4.6 ///
4.7 - namespace skeleton {}
4.8 + namespace concept {}
4.9 }
5.1 --- a/src/lemon/Makefile.am Thu Nov 04 18:52:31 2004 +0000
5.2 +++ b/src/lemon/Makefile.am Thu Nov 04 20:24:59 2004 +0000
5.3 @@ -36,8 +36,8 @@
5.4 erasable_graph_extender.h
5.5
5.6 noinst_HEADERS = \
5.7 - skeletons/graph.h \
5.8 - skeletons/graph_component.h \
5.9 - skeletons/sym_graph.h \
5.10 - skeletons/maps.h \
5.11 - skeletons/path.h
5.12 + concept/graph.h \
5.13 + concept/graph_component.h \
5.14 + concept/sym_graph.h \
5.15 + concept/maps.h \
5.16 + concept/path.h
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/lemon/concept/graph.h Thu Nov 04 20:24:59 2004 +0000
6.3 @@ -0,0 +1,918 @@
6.4 +/* -*- C++ -*-
6.5 + * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library
6.6 + *
6.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
6.9 + *
6.10 + * Permission to use, modify and distribute this software is granted
6.11 + * provided that this copyright notice appears in all copies. For
6.12 + * precise terms see the accompanying LICENSE file.
6.13 + *
6.14 + * This software is provided "AS IS" with no warranty of any kind,
6.15 + * express or implied, and with no claim as to its suitability for any
6.16 + * purpose.
6.17 + *
6.18 + */
6.19 +
6.20 +#ifndef LEMON_CONCEPT_GRAPH_H
6.21 +#define LEMON_CONCEPT_GRAPH_H
6.22 +
6.23 +///\ingroup concept
6.24 +///\file
6.25 +///\brief Declaration of Graph.
6.26 +
6.27 +#include <lemon/invalid.h>
6.28 +#include <lemon/concept/maps.h>
6.29 +#include <lemon/concept_check.h>
6.30 +#include <lemon/concept/graph_component.h>
6.31 +
6.32 +namespace lemon {
6.33 + namespace concept {
6.34 +
6.35 + /// \addtogroup concept
6.36 + /// @{
6.37 +
6.38 +// /// An empty static graph class.
6.39 +
6.40 +// /// This class provides all the common features of a graph structure,
6.41 +// /// however completely without implementations and real data structures
6.42 +// /// behind the interface.
6.43 +// /// All graph algorithms should compile with this class, but it will not
6.44 +// /// run properly, of course.
6.45 +// ///
6.46 +// /// It can be used for checking the interface compatibility,
6.47 +// /// or it can serve as a skeleton of a new graph structure.
6.48 +// ///
6.49 +// /// Also, you will find here the full documentation of a certain graph
6.50 +// /// feature, the documentation of a real graph imlementation
6.51 +// /// like @ref ListGraph or
6.52 +// /// @ref SmartGraph will just refer to this structure.
6.53 +// ///
6.54 +// /// \todo A pages describing the concept of concept description would
6.55 +// /// be nice.
6.56 +// class StaticGraph
6.57 +// {
6.58 +// public:
6.59 +// /// Defalult constructor.
6.60 +
6.61 +// /// Defalult constructor.
6.62 +// ///
6.63 +// StaticGraph() { }
6.64 +// ///Copy consructor.
6.65 +
6.66 +// // ///\todo It is not clear, what we expect from a copy constructor.
6.67 +// // ///E.g. How to assign the nodes/edges to each other? What about maps?
6.68 +// // StaticGraph(const StaticGraph& g) { }
6.69 +
6.70 +// /// The base type of node iterators,
6.71 +// /// or in other words, the trivial node iterator.
6.72 +
6.73 +// /// This is the base type of each node iterator,
6.74 +// /// thus each kind of node iterator converts to this.
6.75 +// /// More precisely each kind of node iterator should be inherited
6.76 +// /// from the trivial node iterator.
6.77 +// class Node {
6.78 +// public:
6.79 +// /// Default constructor
6.80 +
6.81 +// /// @warning The default constructor sets the iterator
6.82 +// /// to an undefined value.
6.83 +// Node() { }
6.84 +// /// Copy constructor.
6.85 +
6.86 +// /// Copy constructor.
6.87 +// ///
6.88 +// Node(const Node&) { }
6.89 +
6.90 +// /// Invalid constructor \& conversion.
6.91 +
6.92 +// /// This constructor initializes the iterator to be invalid.
6.93 +// /// \sa Invalid for more details.
6.94 +// Node(Invalid) { }
6.95 +// /// Equality operator
6.96 +
6.97 +// /// Two iterators are equal if and only if they point to the
6.98 +// /// same object or both are invalid.
6.99 +// bool operator==(Node) const { return true; }
6.100 +
6.101 +// /// Inequality operator
6.102 +
6.103 +// /// \sa operator==(Node n)
6.104 +// ///
6.105 +// bool operator!=(Node) const { return true; }
6.106 +
6.107 +// ///Comparison operator.
6.108 +
6.109 +// ///This is a strict ordering between the nodes.
6.110 +// ///
6.111 +// ///This ordering can be different from the order in which NodeIt
6.112 +// ///goes through the nodes.
6.113 +// ///\todo Possibly we don't need it.
6.114 +// bool operator<(Node) const { return true; }
6.115 +// };
6.116 +
6.117 +// /// This iterator goes through each node.
6.118 +
6.119 +// /// This iterator goes through each node.
6.120 +// /// Its usage is quite simple, for example you can count the number
6.121 +// /// of nodes in graph \c g of type \c Graph like this:
6.122 +// /// \code
6.123 +// /// int count=0;
6.124 +// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
6.125 +// /// \endcode
6.126 +// class NodeIt : public Node {
6.127 +// public:
6.128 +// /// Default constructor
6.129 +
6.130 +// /// @warning The default constructor sets the iterator
6.131 +// /// to an undefined value.
6.132 +// NodeIt() { }
6.133 +// /// Copy constructor.
6.134 +
6.135 +// /// Copy constructor.
6.136 +// ///
6.137 +// NodeIt(const NodeIt&) { }
6.138 +// /// Invalid constructor \& conversion.
6.139 +
6.140 +// /// Initialize the iterator to be invalid.
6.141 +// /// \sa Invalid for more details.
6.142 +// NodeIt(Invalid) { }
6.143 +// /// Sets the iterator to the first node.
6.144 +
6.145 +// /// Sets the iterator to the first node of \c g.
6.146 +// ///
6.147 +// NodeIt(const StaticGraph& g) { }
6.148 +// /// Node -> NodeIt conversion.
6.149 +
6.150 +// /// Sets the iterator to the node of \c g pointed by the trivial
6.151 +// /// iterator n.
6.152 +// /// This feature necessitates that each time we
6.153 +// /// iterate the edge-set, the iteration order is the same.
6.154 +// NodeIt(const StaticGraph& g, const Node& n) { }
6.155 +// /// Next node.
6.156 +
6.157 +// /// Assign the iterator to the next node.
6.158 +// ///
6.159 +// NodeIt& operator++() { return *this; }
6.160 +// };
6.161 +
6.162 +
6.163 +// /// The base type of the edge iterators.
6.164 +
6.165 +// /// The base type of the edge iterators.
6.166 +// ///
6.167 +// class Edge {
6.168 +// public:
6.169 +// /// Default constructor
6.170 +
6.171 +// /// @warning The default constructor sets the iterator
6.172 +// /// to an undefined value.
6.173 +// Edge() { }
6.174 +// /// Copy constructor.
6.175 +
6.176 +// /// Copy constructor.
6.177 +// ///
6.178 +// Edge(const Edge&) { }
6.179 +// /// Initialize the iterator to be invalid.
6.180 +
6.181 +// /// Initialize the iterator to be invalid.
6.182 +// ///
6.183 +// Edge(Invalid) { }
6.184 +// /// Equality operator
6.185 +
6.186 +// /// Two iterators are equal if and only if they point to the
6.187 +// /// same object or both are invalid.
6.188 +// bool operator==(Edge) const { return true; }
6.189 +// /// Inequality operator
6.190 +
6.191 +// /// \sa operator==(Node n)
6.192 +// ///
6.193 +// bool operator!=(Edge) const { return true; }
6.194 +// ///Comparison operator.
6.195 +
6.196 +// ///This is a strict ordering between the nodes.
6.197 +// ///
6.198 +// ///This ordering can be different from the order in which NodeIt
6.199 +// ///goes through the nodes.
6.200 +// ///\todo Possibly we don't need it.
6.201 +// bool operator<(Edge) const { return true; }
6.202 +// };
6.203 +
6.204 +// /// This iterator goes trough the outgoing edges of a node.
6.205 +
6.206 +// /// This iterator goes trough the \e outgoing edges of a certain node
6.207 +// /// of a graph.
6.208 +// /// Its usage is quite simple, for example you can count the number
6.209 +// /// of outgoing edges of a node \c n
6.210 +// /// in graph \c g of type \c Graph as follows.
6.211 +// /// \code
6.212 +// /// int count=0;
6.213 +// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
6.214 +// /// \endcode
6.215 +
6.216 +// class OutEdgeIt : public Edge {
6.217 +// public:
6.218 +// /// Default constructor
6.219 +
6.220 +// /// @warning The default constructor sets the iterator
6.221 +// /// to an undefined value.
6.222 +// OutEdgeIt() { }
6.223 +// /// Copy constructor.
6.224 +
6.225 +// /// Copy constructor.
6.226 +// ///
6.227 +// OutEdgeIt(const OutEdgeIt&) { }
6.228 +// /// Initialize the iterator to be invalid.
6.229 +
6.230 +// /// Initialize the iterator to be invalid.
6.231 +// ///
6.232 +// OutEdgeIt(Invalid) { }
6.233 +// /// This constructor sets the iterator to first outgoing edge.
6.234 +
6.235 +// /// This constructor set the iterator to the first outgoing edge of
6.236 +// /// node
6.237 +// ///@param n the node
6.238 +// ///@param g the graph
6.239 +// OutEdgeIt(const StaticGraph& g, const Node& n) { }
6.240 +// /// Edge -> OutEdgeIt conversion
6.241 +
6.242 +// /// Sets the iterator to the value of the trivial iterator \c e.
6.243 +// /// This feature necessitates that each time we
6.244 +// /// iterate the edge-set, the iteration order is the same.
6.245 +// OutEdgeIt(const StaticGraph& g, const Edge& e) { }
6.246 +// ///Next outgoing edge
6.247 +
6.248 +// /// Assign the iterator to the next
6.249 +// /// outgoing edge of the corresponding node.
6.250 +// OutEdgeIt& operator++() { return *this; }
6.251 +// };
6.252 +
6.253 +// /// This iterator goes trough the incoming edges of a node.
6.254 +
6.255 +// /// This iterator goes trough the \e incoming edges of a certain node
6.256 +// /// of a graph.
6.257 +// /// Its usage is quite simple, for example you can count the number
6.258 +// /// of outgoing edges of a node \c n
6.259 +// /// in graph \c g of type \c Graph as follows.
6.260 +// /// \code
6.261 +// /// int count=0;
6.262 +// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
6.263 +// /// \endcode
6.264 +
6.265 +// class InEdgeIt : public Edge {
6.266 +// public:
6.267 +// /// Default constructor
6.268 +
6.269 +// /// @warning The default constructor sets the iterator
6.270 +// /// to an undefined value.
6.271 +// InEdgeIt() { }
6.272 +// /// Copy constructor.
6.273 +
6.274 +// /// Copy constructor.
6.275 +// ///
6.276 +// InEdgeIt(const InEdgeIt&) { }
6.277 +// /// Initialize the iterator to be invalid.
6.278 +
6.279 +// /// Initialize the iterator to be invalid.
6.280 +// ///
6.281 +// InEdgeIt(Invalid) { }
6.282 +// /// This constructor sets the iterator to first incoming edge.
6.283 +
6.284 +// /// This constructor set the iterator to the first incoming edge of
6.285 +// /// node
6.286 +// ///@param n the node
6.287 +// ///@param g the graph
6.288 +// InEdgeIt(const StaticGraph& g, const Node& n) { }
6.289 +// /// Edge -> InEdgeIt conversion
6.290 +
6.291 +// /// Sets the iterator to the value of the trivial iterator \c e.
6.292 +// /// This feature necessitates that each time we
6.293 +// /// iterate the edge-set, the iteration order is the same.
6.294 +// InEdgeIt(const StaticGraph& g, const Edge& n) { }
6.295 +// /// Next incoming edge
6.296 +
6.297 +// /// Assign the iterator to the next inedge of the corresponding node.
6.298 +// ///
6.299 +// InEdgeIt& operator++() { return *this; }
6.300 +// };
6.301 +// /// This iterator goes through each edge.
6.302 +
6.303 +// /// This iterator goes through each edge of a graph.
6.304 +// /// Its usage is quite simple, for example you can count the number
6.305 +// /// of edges in a graph \c g of type \c Graph as follows:
6.306 +// /// \code
6.307 +// /// int count=0;
6.308 +// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
6.309 +// /// \endcode
6.310 +// class EdgeIt : public Edge {
6.311 +// public:
6.312 +// /// Default constructor
6.313 +
6.314 +// /// @warning The default constructor sets the iterator
6.315 +// /// to an undefined value.
6.316 +// EdgeIt() { }
6.317 +// /// Copy constructor.
6.318 +
6.319 +// /// Copy constructor.
6.320 +// ///
6.321 +// EdgeIt(const EdgeIt&) { }
6.322 +// /// Initialize the iterator to be invalid.
6.323 +
6.324 +// /// Initialize the iterator to be invalid.
6.325 +// ///
6.326 +// EdgeIt(Invalid) { }
6.327 +// /// This constructor sets the iterator to first edge.
6.328 +
6.329 +// /// This constructor set the iterator to the first edge of
6.330 +// /// node
6.331 +// ///@param g the graph
6.332 +// EdgeIt(const StaticGraph& g) { }
6.333 +// /// Edge -> EdgeIt conversion
6.334 +
6.335 +// /// Sets the iterator to the value of the trivial iterator \c e.
6.336 +// /// This feature necessitates that each time we
6.337 +// /// iterate the edge-set, the iteration order is the same.
6.338 +// EdgeIt(const StaticGraph&, const Edge&) { }
6.339 +// ///Next edge
6.340 +
6.341 +// /// Assign the iterator to the next
6.342 +// /// edge of the corresponding node.
6.343 +// EdgeIt& operator++() { return *this; }
6.344 +// };
6.345 +
6.346 +// /// First node of the graph.
6.347 +
6.348 +// /// \retval i the first node.
6.349 +// /// \return the first node.
6.350 +// ///
6.351 +// NodeIt& first(NodeIt& i) const { return i; }
6.352 +
6.353 +// /// The first incoming edge.
6.354 +
6.355 +// /// The first incoming edge.
6.356 +// ///
6.357 +// InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
6.358 +// /// The first outgoing edge.
6.359 +
6.360 +// /// The first outgoing edge.
6.361 +// ///
6.362 +// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
6.363 +// /// The first edge of the Graph.
6.364 +
6.365 +// /// The first edge of the Graph.
6.366 +// ///
6.367 +// EdgeIt& first(EdgeIt& i) const { return i; }
6.368 +
6.369 +// ///Gives back the head node of an edge.
6.370 +
6.371 +// ///Gives back the head node of an edge.
6.372 +// ///
6.373 +// Node head(Edge) const { return INVALID; }
6.374 +// ///Gives back the tail node of an edge.
6.375 +
6.376 +// ///Gives back the tail node of an edge.
6.377 +// ///
6.378 +// Node tail(Edge) const { return INVALID; }
6.379 +
6.380 +// ///Gives back the \e id of a node.
6.381 +
6.382 +// ///\warning Not all graph structures provide this feature.
6.383 +// ///
6.384 +// ///\todo Should each graph provide \c id?
6.385 +// int id(const Node&) const { return 0; }
6.386 +// ///Gives back the \e id of an edge.
6.387 +
6.388 +// ///\warning Not all graph structures provide this feature.
6.389 +// ///
6.390 +// ///\todo Should each graph provide \c id?
6.391 +// int id(const Edge&) const { return 0; }
6.392 +
6.393 +// ///\e
6.394 +
6.395 +// ///\todo Should it be in the concept?
6.396 +// ///
6.397 +// int nodeNum() const { return 0; }
6.398 +// ///\e
6.399 +
6.400 +// ///\todo Should it be in the concept?
6.401 +// ///
6.402 +// int edgeNum() const { return 0; }
6.403 +
6.404 +
6.405 +// ///Reference map of the nodes to type \c T.
6.406 +
6.407 +// /// \ingroup concept
6.408 +// ///Reference map of the nodes to type \c T.
6.409 +// /// \sa Reference
6.410 +// /// \warning Making maps that can handle bool type (NodeMap<bool>)
6.411 +// /// needs some extra attention!
6.412 +// template<class T> class NodeMap : public ReferenceMap< Node, T >
6.413 +// {
6.414 +// public:
6.415 +
6.416 +// ///\e
6.417 +// NodeMap(const StaticGraph&) { }
6.418 +// ///\e
6.419 +// NodeMap(const StaticGraph&, T) { }
6.420 +
6.421 +// ///Copy constructor
6.422 +// template<typename TT> NodeMap(const NodeMap<TT>&) { }
6.423 +// ///Assignment operator
6.424 +// template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
6.425 +// { return *this; }
6.426 +// };
6.427 +
6.428 +// ///Reference map of the edges to type \c T.
6.429 +
6.430 +// /// \ingroup concept
6.431 +// ///Reference map of the edges to type \c T.
6.432 +// /// \sa Reference
6.433 +// /// \warning Making maps that can handle bool type (EdgeMap<bool>)
6.434 +// /// needs some extra attention!
6.435 +// template<class T> class EdgeMap
6.436 +// : public ReferenceMap<Edge,T>
6.437 +// {
6.438 +// public:
6.439 +
6.440 +// ///\e
6.441 +// EdgeMap(const StaticGraph&) { }
6.442 +// ///\e
6.443 +// EdgeMap(const StaticGraph&, T) { }
6.444 +
6.445 +// ///Copy constructor
6.446 +// template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
6.447 +// ///Assignment operator
6.448 +// template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
6.449 +// { return *this; }
6.450 +// };
6.451 +// };
6.452 +
6.453 +// struct DummyType {
6.454 +// int value;
6.455 +// DummyType() {}
6.456 +// DummyType(int p) : value(p) {}
6.457 +// DummyType& operator=(int p) { value = p; return *this;}
6.458 +// };
6.459 +
6.460 +// ///\brief Checks whether \c G meets the
6.461 +// ///\ref lemon::concept::StaticGraph "StaticGraph" concept
6.462 +// template<class Graph> void checkCompileStaticGraph(Graph &G)
6.463 +// {
6.464 +// typedef typename Graph::Node Node;
6.465 +// typedef typename Graph::NodeIt NodeIt;
6.466 +// typedef typename Graph::Edge Edge;
6.467 +// typedef typename Graph::EdgeIt EdgeIt;
6.468 +// typedef typename Graph::InEdgeIt InEdgeIt;
6.469 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
6.470 +
6.471 +// {
6.472 +// Node i; Node j(i); Node k(INVALID);
6.473 +// i=j;
6.474 +// bool b; b=true;
6.475 +// b=(i==INVALID); b=(i!=INVALID);
6.476 +// b=(i==j); b=(i!=j); b=(i<j);
6.477 +// }
6.478 +// {
6.479 +// NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
6.480 +// i=j;
6.481 +// j=G.first(i);
6.482 +// j=++i;
6.483 +// bool b; b=true;
6.484 +// b=(i==INVALID); b=(i!=INVALID);
6.485 +// Node n(i);
6.486 +// n=i;
6.487 +// b=(i==j); b=(i!=j); b=(i<j);
6.488 +// //Node ->NodeIt conversion
6.489 +// NodeIt ni(G,n);
6.490 +// }
6.491 +// {
6.492 +// Edge i; Edge j(i); Edge k(INVALID);
6.493 +// i=j;
6.494 +// bool b; b=true;
6.495 +// b=(i==INVALID); b=(i!=INVALID);
6.496 +// b=(i==j); b=(i!=j); b=(i<j);
6.497 +// }
6.498 +// {
6.499 +// EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
6.500 +// i=j;
6.501 +// j=G.first(i);
6.502 +// j=++i;
6.503 +// bool b; b=true;
6.504 +// b=(i==INVALID); b=(i!=INVALID);
6.505 +// Edge e(i);
6.506 +// e=i;
6.507 +// b=(i==j); b=(i!=j); b=(i<j);
6.508 +// //Edge ->EdgeIt conversion
6.509 +// EdgeIt ei(G,e);
6.510 +// }
6.511 +// {
6.512 +// Node n;
6.513 +// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
6.514 +// i=j;
6.515 +// j=G.first(i,n);
6.516 +// j=++i;
6.517 +// bool b; b=true;
6.518 +// b=(i==INVALID); b=(i!=INVALID);
6.519 +// Edge e(i);
6.520 +// e=i;
6.521 +// b=(i==j); b=(i!=j); b=(i<j);
6.522 +// //Edge ->InEdgeIt conversion
6.523 +// InEdgeIt ei(G,e);
6.524 +// }
6.525 +// {
6.526 +// Node n;
6.527 +// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
6.528 +// i=j;
6.529 +// j=G.first(i,n);
6.530 +// j=++i;
6.531 +// bool b; b=true;
6.532 +// b=(i==INVALID); b=(i!=INVALID);
6.533 +// Edge e(i);
6.534 +// e=i;
6.535 +// b=(i==j); b=(i!=j); b=(i<j);
6.536 +// //Edge ->OutEdgeIt conversion
6.537 +// OutEdgeIt ei(G,e);
6.538 +// }
6.539 +// {
6.540 +// Node n,m;
6.541 +// n=m=INVALID;
6.542 +// Edge e;
6.543 +// e=INVALID;
6.544 +// n=G.tail(e);
6.545 +// n=G.head(e);
6.546 +// }
6.547 +// // id tests
6.548 +// { Node n; int i=G.id(n); i=i; }
6.549 +// { Edge e; int i=G.id(e); i=i; }
6.550 +// //NodeMap tests
6.551 +// {
6.552 +// Node k;
6.553 +// typename Graph::template NodeMap<int> m(G);
6.554 +// //Const map
6.555 +// typename Graph::template NodeMap<int> const &cm = m;
6.556 +// //Inicialize with default value
6.557 +// typename Graph::template NodeMap<int> mdef(G,12);
6.558 +// //Copy
6.559 +// typename Graph::template NodeMap<int> mm(cm);
6.560 +// //Copy from another type
6.561 +// typename Graph::template NodeMap<double> dm(cm);
6.562 +// //Copy to more complex type
6.563 +// typename Graph::template NodeMap<DummyType> em(cm);
6.564 +// int v;
6.565 +// v=m[k]; m[k]=v; m.set(k,v);
6.566 +// v=cm[k];
6.567 +
6.568 +// m=cm;
6.569 +// dm=cm; //Copy from another type
6.570 +// em=cm; //Copy to more complex type
6.571 +// {
6.572 +// //Check the typedef's
6.573 +// typename Graph::template NodeMap<int>::ValueType val;
6.574 +// val=1;
6.575 +// typename Graph::template NodeMap<int>::KeyType key;
6.576 +// key = typename Graph::NodeIt(G);
6.577 +// }
6.578 +// }
6.579 +// { //bool NodeMap
6.580 +// Node k;
6.581 +// typename Graph::template NodeMap<bool> m(G);
6.582 +// typename Graph::template NodeMap<bool> const &cm = m; //Const map
6.583 +// //Inicialize with default value
6.584 +// typename Graph::template NodeMap<bool> mdef(G,12);
6.585 +// typename Graph::template NodeMap<bool> mm(cm); //Copy
6.586 +// typename Graph::template NodeMap<int> dm(cm); //Copy from another type
6.587 +// bool v;
6.588 +// v=m[k]; m[k]=v; m.set(k,v);
6.589 +// v=cm[k];
6.590 +
6.591 +// m=cm;
6.592 +// dm=cm; //Copy from another type
6.593 +// m=dm; //Copy to another type
6.594 +
6.595 +// {
6.596 +// //Check the typedef's
6.597 +// typename Graph::template NodeMap<bool>::ValueType val;
6.598 +// val=true;
6.599 +// typename Graph::template NodeMap<bool>::KeyType key;
6.600 +// key= typename Graph::NodeIt(G);
6.601 +// }
6.602 +// }
6.603 +// //EdgeMap tests
6.604 +// {
6.605 +// Edge k;
6.606 +// typename Graph::template EdgeMap<int> m(G);
6.607 +// typename Graph::template EdgeMap<int> const &cm = m; //Const map
6.608 +// //Inicialize with default value
6.609 +// typename Graph::template EdgeMap<int> mdef(G,12);
6.610 +// typename Graph::template EdgeMap<int> mm(cm); //Copy
6.611 +// typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
6.612 +// int v;
6.613 +// v=m[k]; m[k]=v; m.set(k,v);
6.614 +// v=cm[k];
6.615 +
6.616 +// m=cm;
6.617 +// dm=cm; //Copy from another type
6.618 +// {
6.619 +// //Check the typedef's
6.620 +// typename Graph::template EdgeMap<int>::ValueType val;
6.621 +// val=1;
6.622 +// typename Graph::template EdgeMap<int>::KeyType key;
6.623 +// key= typename Graph::EdgeIt(G);
6.624 +// }
6.625 +// }
6.626 +// { //bool EdgeMap
6.627 +// Edge k;
6.628 +// typename Graph::template EdgeMap<bool> m(G);
6.629 +// typename Graph::template EdgeMap<bool> const &cm = m; //Const map
6.630 +// //Inicialize with default value
6.631 +// typename Graph::template EdgeMap<bool> mdef(G,12);
6.632 +// typename Graph::template EdgeMap<bool> mm(cm); //Copy
6.633 +// typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
6.634 +// bool v;
6.635 +// v=m[k]; m[k]=v; m.set(k,v);
6.636 +// v=cm[k];
6.637 +
6.638 +// m=cm;
6.639 +// dm=cm; //Copy from another type
6.640 +// m=dm; //Copy to another type
6.641 +// {
6.642 +// //Check the typedef's
6.643 +// typename Graph::template EdgeMap<bool>::ValueType val;
6.644 +// val=true;
6.645 +// typename Graph::template EdgeMap<bool>::KeyType key;
6.646 +// key= typename Graph::EdgeIt(G);
6.647 +// }
6.648 +// }
6.649 +// }
6.650 +
6.651 +// /// An empty non-static graph class.
6.652 +
6.653 +// /// This class provides everything that \ref StaticGraph
6.654 +// /// with additional functionality which enables to build a
6.655 +// /// graph from scratch.
6.656 +// class ExtendableGraph : public StaticGraph
6.657 +// {
6.658 +// public:
6.659 +// /// Defalult constructor.
6.660 +
6.661 +// /// Defalult constructor.
6.662 +// ///
6.663 +// ExtendableGraph() { }
6.664 +// ///Add a new node to the graph.
6.665 +
6.666 +// /// \return the new node.
6.667 +// ///
6.668 +// Node addNode() { return INVALID; }
6.669 +// ///Add a new edge to the graph.
6.670 +
6.671 +// ///Add a new edge to the graph with tail node \c t
6.672 +// ///and head node \c h.
6.673 +// ///\return the new edge.
6.674 +// Edge addEdge(Node h, Node t) { return INVALID; }
6.675 +
6.676 +// /// Resets the graph.
6.677 +
6.678 +// /// This function deletes all edges and nodes of the graph.
6.679 +// /// It also frees the memory allocated to store them.
6.680 +// /// \todo It might belong to \ref ErasableGraph.
6.681 +// void clear() { }
6.682 +// };
6.683 +
6.684 +
6.685 +// ///\brief Checks whether \c G meets the
6.686 +// ///\ref lemon::concept::ExtendableGraph "ExtendableGraph" concept
6.687 +// template<class Graph> void checkCompileExtendableGraph(Graph &G)
6.688 +// {
6.689 +// checkCompileStaticGraph(G);
6.690 +
6.691 +// typedef typename Graph::Node Node;
6.692 +// typedef typename Graph::NodeIt NodeIt;
6.693 +// typedef typename Graph::Edge Edge;
6.694 +// typedef typename Graph::EdgeIt EdgeIt;
6.695 +// typedef typename Graph::InEdgeIt InEdgeIt;
6.696 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
6.697 +
6.698 +// Node n,m;
6.699 +// n=G.addNode();
6.700 +// m=G.addNode();
6.701 +// Edge e;
6.702 +// e=G.addEdge(n,m);
6.703 +
6.704 +// // G.clear();
6.705 +// }
6.706 +
6.707 +
6.708 +// /// An empty erasable graph class.
6.709 +
6.710 +// /// This class is an extension of \ref ExtendableGraph. It also makes it
6.711 +// /// possible to erase edges or nodes.
6.712 +// class ErasableGraph : public ExtendableGraph
6.713 +// {
6.714 +// public:
6.715 +// /// Defalult constructor.
6.716 +
6.717 +// /// Defalult constructor.
6.718 +// ///
6.719 +// ErasableGraph() { }
6.720 +// /// Deletes a node.
6.721 +
6.722 +// /// Deletes node \c n node.
6.723 +// ///
6.724 +// void erase(Node n) { }
6.725 +// /// Deletes an edge.
6.726 +
6.727 +// /// Deletes edge \c e edge.
6.728 +// ///
6.729 +// void erase(Edge e) { }
6.730 +// };
6.731 +
6.732 +// template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
6.733 +// {
6.734 +// typename Graph::Edge e;
6.735 +// G.erase(e);
6.736 +// }
6.737 +
6.738 +// template<class Graph> void checkCompileGraphEraseNode(Graph &G)
6.739 +// {
6.740 +// typename Graph::Node n;
6.741 +// G.erase(n);
6.742 +// }
6.743 +
6.744 +// ///\brief Checks whether \c G meets the
6.745 +// ///\ref lemon::concept::EresableGraph "EresableGraph" concept
6.746 +// template<class Graph> void checkCompileErasableGraph(Graph &G)
6.747 +// {
6.748 +// checkCompileExtendableGraph(G);
6.749 +// checkCompileGraphEraseNode(G);
6.750 +// checkCompileGraphEraseEdge(G);
6.751 +// }
6.752 +
6.753 +// ///Checks whether a graph has findEdge() member function.
6.754 +
6.755 +// ///\todo findEdge() might be a global function.
6.756 +// ///
6.757 +// template<class Graph> void checkCompileGraphFindEdge(Graph &G)
6.758 +// {
6.759 +// typedef typename Graph::NodeIt Node;
6.760 +// typedef typename Graph::NodeIt NodeIt;
6.761 +
6.762 +// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
6.763 +// G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
6.764 +// }
6.765 +
6.766 +
6.767 +
6.768 + /************* New GraphBase stuff **************/
6.769 +
6.770 +
6.771 + /// \bug The nodes and edges are not allowed to inherit from the
6.772 + /// same baseclass.
6.773 +
6.774 + class BaseGraphItem {
6.775 + public:
6.776 + BaseGraphItem() {}
6.777 + BaseGraphItem(Invalid) {}
6.778 +
6.779 + // We explicitely list these:
6.780 + BaseGraphItem(BaseGraphItem const&) {}
6.781 + BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
6.782 +
6.783 + bool operator==(BaseGraphItem) const { return false; }
6.784 + bool operator!=(BaseGraphItem) const { return false; }
6.785 +
6.786 + // Technical requirement. Do we really need this?
6.787 + bool operator<(BaseGraphItem) const { return false; }
6.788 + };
6.789 +
6.790 +
6.791 + /// A minimal GraphBase concept
6.792 +
6.793 + /// This class describes a minimal concept which can be extended to a
6.794 + /// full-featured graph with \ref GraphFactory.
6.795 + class GraphBase {
6.796 + public:
6.797 +
6.798 + GraphBase() {}
6.799 +
6.800 +
6.801 + /// \bug Nodes and Edges are comparable each other
6.802 +
6.803 + class Node : public BaseGraphItem {};
6.804 + class Edge : public BaseGraphItem {};
6.805 +
6.806 + // Graph operation
6.807 + void firstNode(Node &n) const { }
6.808 + void firstEdge(Edge &e) const { }
6.809 +
6.810 + void firstOutEdge(Edge &e, Node) const { }
6.811 + void firstInEdge(Edge &e, Node) const { }
6.812 +
6.813 + void nextNode(Node &n) const { }
6.814 + void nextEdge(Edge &e) const { }
6.815 +
6.816 +
6.817 + // Question: isn't it reasonable if this methods have a Node
6.818 + // parameter? Like this:
6.819 + // Edge& nextOut(Edge &e, Node) const { return e; }
6.820 + void nextOutEdge(Edge &e) const { }
6.821 + void nextInEdge(Edge &e) const { }
6.822 +
6.823 + Node head(Edge) const { return Node(); }
6.824 + Node tail(Edge) const { return Node(); }
6.825 +
6.826 +
6.827 + // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
6.828 + // concept?
6.829 +
6.830 +
6.831 + // Maps.
6.832 + //
6.833 + // We need a special slimer concept which does not provide maps (it
6.834 + // wouldn't be strictly slimer, cause for map-factory id() & friends
6.835 + // a required...)
6.836 +
6.837 + template<typename T>
6.838 + class NodeMap : public GraphMap<Node, T, GraphBase> {};
6.839 +
6.840 + template<typename T>
6.841 + class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
6.842 + };
6.843 +
6.844 +
6.845 +
6.846 + /**************** Concept checking classes ****************/
6.847 +
6.848 + template<typename BGI>
6.849 + struct BaseGraphItemConcept {
6.850 + void constraints() {
6.851 + BGI i1;
6.852 + BGI i2 = i1;
6.853 + BGI i3 = INVALID;
6.854 +
6.855 + i1 = i3;
6.856 + if( i1 == i3 ) {
6.857 + if ( i2 != i3 && i3 < i2 )
6.858 + return;
6.859 + }
6.860 + }
6.861 + };
6.862 +
6.863 +
6.864 +
6.865 + class StaticGraph
6.866 + : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
6.867 + public:
6.868 + typedef BaseGraphComponent::Node Node;
6.869 + typedef BaseGraphComponent::Edge Edge;
6.870 + };
6.871 +
6.872 + template <typename Graph>
6.873 + struct StaticGraphConcept {
6.874 + void constraints() {
6.875 + function_requires<BaseGraphComponentConcept<Graph> >();
6.876 + function_requires<IterableGraphComponentConcept<Graph> >();
6.877 + function_requires<MappableGraphComponentConcept<Graph> >();
6.878 + }
6.879 + Graph& graph;
6.880 + };
6.881 +
6.882 + class ExtendableGraph
6.883 + : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
6.884 + public:
6.885 + typedef BaseGraphComponent::Node Node;
6.886 + typedef BaseGraphComponent::Edge Edge;
6.887 + };
6.888 +
6.889 + template <typename Graph>
6.890 + struct ExtendableGraphConcept {
6.891 + void constraints() {
6.892 + function_requires<StaticGraphConcept<Graph> >();
6.893 + function_requires<ExtendableGraphComponentConcept<Graph> >();
6.894 + function_requires<ClearableGraphComponentConcept<Graph> >();
6.895 + }
6.896 + Graph& graph;
6.897 + };
6.898 +
6.899 + class ErasableGraph
6.900 + : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
6.901 + public:
6.902 + typedef BaseGraphComponent::Node Node;
6.903 + typedef BaseGraphComponent::Edge Edge;
6.904 + };
6.905 +
6.906 + template <typename Graph>
6.907 + struct ErasableGraphConcept {
6.908 + void constraints() {
6.909 + function_requires<ExtendableGraphConcept<Graph> >();
6.910 + function_requires<ErasableGraphComponentConcept<Graph> >();
6.911 + }
6.912 + Graph& graph;
6.913 + };
6.914 +
6.915 + // @}
6.916 + } //namespace concept
6.917 +} //namespace lemon
6.918 +
6.919 +
6.920 +
6.921 +#endif // LEMON_CONCEPT_GRAPH_H
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/lemon/concept/graph_component.h Thu Nov 04 20:24:59 2004 +0000
7.3 @@ -0,0 +1,827 @@
7.4 +/* -*- C++ -*-
7.5 + * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library
7.6 + *
7.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
7.9 + *
7.10 + * Permission to use, modify and distribute this software is granted
7.11 + * provided that this copyright notice appears in all copies. For
7.12 + * precise terms see the accompanying LICENSE file.
7.13 + *
7.14 + * This software is provided "AS IS" with no warranty of any kind,
7.15 + * express or implied, and with no claim as to its suitability for any
7.16 + * purpose.
7.17 + *
7.18 + */
7.19 +
7.20 +///\ingroup concept
7.21 +///\file
7.22 +///\brief The graph components.
7.23 +
7.24 +
7.25 +#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
7.26 +#define LEMON_CONCEPT_GRAPH_COMPONENT_H
7.27 +
7.28 +#include <lemon/invalid.h>
7.29 +#include <lemon/concept/maps.h>
7.30 +
7.31 +namespace lemon {
7.32 + namespace concept {
7.33 +
7.34 + /// An empty base graph class.
7.35 +
7.36 + /// This class provides the most minimal features of a graph structure.
7.37 + /// All the graph concepts have to be conform to this base graph.
7.38 +
7.39 + class BaseGraphComponent {
7.40 + public:
7.41 +
7.42 + typedef BaseGraphComponent Graph;
7.43 +
7.44 + /// Node class of the graph.
7.45 +
7.46 + /// This class represents the Nodes of the graph.
7.47 + ///
7.48 + class Node {
7.49 + public:
7.50 +
7.51 + /// Default constructor.
7.52 +
7.53 + /// @warning The default constructor sets the iterator
7.54 + /// to an undefined value.
7.55 +
7.56 + Node() {}
7.57 + /// Copy constructor.
7.58 +
7.59 + /// Copy constructor.
7.60 + ///
7.61 + Node(const Node&) {}
7.62 +
7.63 + /// Invalid constructor \& conversion.
7.64 +
7.65 + /// This constructor initializes the iterator to be invalid.
7.66 + /// \sa Invalid for more details.
7.67 + Node(Invalid) {}
7.68 +
7.69 +
7.70 + Node& operator=(const Node&) { return *this;}
7.71 +
7.72 + /// Equality operator.
7.73 +
7.74 + /// Two iterators are equal if and only if they represents the
7.75 + /// same node in the graph or both are invalid.
7.76 + bool operator==(const Node&) { return true;}
7.77 +
7.78 +
7.79 + /// Inequality operator.
7.80 +
7.81 + /// \sa operator==(const Node& n)
7.82 + ///
7.83 + bool operator!=(const Node&) { return true;}
7.84 +
7.85 + /// Comparison operator.
7.86 +
7.87 + /// This is a strict ordering between the nodes.
7.88 + ///
7.89 + /// This ordering can be different from the iterating order of nodes.
7.90 + /// \todo Possibly we don't need it.
7.91 + bool operator<(const Node&) { return true;}
7.92 + };
7.93 +
7.94 + /// Edge class of the graph.
7.95 +
7.96 + /// This class represents the Edges of the graph.
7.97 + ///
7.98 + class Edge {
7.99 + public:
7.100 +
7.101 + /// Default constructor.
7.102 +
7.103 + /// @warning The default constructor sets the iterator
7.104 + /// to an undefined value.
7.105 +
7.106 + Edge() {}
7.107 + /// Copy constructor.
7.108 +
7.109 + /// Copy constructor.
7.110 + ///
7.111 + Edge(const Edge&) {}
7.112 +
7.113 + /// Invalid constructor \& conversion.
7.114 +
7.115 + /// This constructor initializes the iterator to be invalid.
7.116 + /// \sa Invalid for more details.
7.117 + Edge(Invalid) {}
7.118 +
7.119 +
7.120 + Edge& operator=(const Edge&) { return *this;}
7.121 +
7.122 + /// Equality operator.
7.123 +
7.124 + /// Two iterators are equal if and only if they represents the
7.125 + /// same edge in the graph or both are invalid.
7.126 + bool operator==(const Edge&) { return true;}
7.127 +
7.128 +
7.129 + /// Inequality operator.
7.130 +
7.131 + /// \sa operator==(const Edge& n)
7.132 + ///
7.133 + bool operator!=(const Edge&) { return true;}
7.134 +
7.135 + /// Comparison operator.
7.136 +
7.137 + /// This is a strict ordering between the edges.
7.138 + ///
7.139 + /// This ordering can be different from the iterating order of edges.
7.140 + /// \todo Possibly we don't need it.
7.141 + bool operator<(const Edge&) { return true;}
7.142 + };
7.143 +
7.144 + ///Gives back the head node of an edge.
7.145 +
7.146 + ///Gives back the head node of an edge.
7.147 + ///
7.148 + Node head(const Edge&) const { return INVALID;}
7.149 +
7.150 + ///Gives back the tail node of an edge.
7.151 +
7.152 + ///Gives back the tail node of an edge.
7.153 + ///
7.154 + Node tail(const Edge&) const { return INVALID;}
7.155 + };
7.156 +
7.157 + /// Concept check structure for BaseGraph.
7.158 +
7.159 + /// Concept check structure for BaseGraph.
7.160 + ///
7.161 +
7.162 + template <typename Graph>
7.163 + struct BaseGraphComponentConcept {
7.164 + typedef typename Graph::Node Node;
7.165 + typedef typename Graph::Edge Edge;
7.166 +
7.167 + void constraints() {
7.168 + {
7.169 + Node ni;
7.170 + Node nj(ni);
7.171 + Node nk(INVALID);
7.172 + ni = nj;
7.173 + bool b; b = true;
7.174 + b = (ni == INVALID); b = (ni != INVALID);
7.175 + b = (ni==nj); b = (ni != nj); b=( ni < nj);
7.176 + }
7.177 + {
7.178 + Edge ei;
7.179 + Edge ej(ei);
7.180 + Edge ek(INVALID);
7.181 + ei = ej;
7.182 + bool b; b = true;
7.183 + b = (ei == INVALID); b = (ei != INVALID);
7.184 + b = (ei==ej); b = (ei != ej); b=( ei < ej);
7.185 + }
7.186 + {
7.187 + const Graph& const_graph = graph;
7.188 + Node n;
7.189 + Edge e;
7.190 + n = const_graph.tail(e);
7.191 + n = const_graph.head(e);
7.192 + }
7.193 + }
7.194 +
7.195 + Graph& graph;
7.196 + };
7.197 +
7.198 + /// An empty iterable base graph class.
7.199 +
7.200 + /// This class provides beside the core graph features
7.201 + /// core iterable interface for the graph structure.
7.202 + /// Most of the base graphs should be conform to this concept.
7.203 +
7.204 + class BaseIterableGraphComponent : virtual public BaseGraphComponent {
7.205 + public:
7.206 +
7.207 + typedef BaseGraphComponent::Node Node;
7.208 + typedef BaseGraphComponent::Edge Edge;
7.209 +
7.210 + /// Gives back the first Node in the iterating order.
7.211 +
7.212 + /// Gives back the first Node in the iterating order.
7.213 + ///
7.214 + void first(Node&) const {}
7.215 +
7.216 + /// Gives back the next Node in the iterating order.
7.217 +
7.218 + /// Gives back the next Node in the iterating order.
7.219 + ///
7.220 + void next(Node&) const {}
7.221 +
7.222 + /// Gives back the first Edge in the iterating order.
7.223 +
7.224 + /// Gives back the first Edge in the iterating order.
7.225 + ///
7.226 + void first(Edge&) const {}
7.227 + /// Gives back the next Edge in the iterating order.
7.228 +
7.229 + /// Gives back the next Edge in the iterating order.
7.230 + ///
7.231 + void next(Edge&) const {}
7.232 +
7.233 +
7.234 + /// Gives back the first of the Edges point to the given Node.
7.235 +
7.236 + /// Gives back the first of the Edges point to the given Node.
7.237 + ///
7.238 + void firstIn(Edge&, const Node&) const {}
7.239 +
7.240 + /// Gives back the next of the Edges points to the given Node.
7.241 +
7.242 +
7.243 + /// Gives back the next of the Edges points to the given Node.
7.244 + ///
7.245 + void nextIn(Edge&) const {}
7.246 +
7.247 + /// Gives back the first of the Edges start from the given Node.
7.248 +
7.249 + /// Gives back the first of the Edges start from the given Node.
7.250 + ///
7.251 + void firstOut(Edge&, const Node&) const {}
7.252 +
7.253 + /// Gives back the next of the Edges start from the given Node.
7.254 +
7.255 + /// Gives back the next of the Edges start from the given Node.
7.256 + ///
7.257 + void nextOut(Edge&) const {}
7.258 + };
7.259 +
7.260 +
7.261 + /// Concept check structure for IterableBaseGraph.
7.262 +
7.263 + /// Concept check structure for IterableBaseGraph.
7.264 + ///
7.265 + template <typename Graph>
7.266 + struct BaseIterableGraphComponentConcept {
7.267 +
7.268 + void constraints() {
7.269 + const Graph& const_graph = graph;
7.270 + typename Graph::Node node;
7.271 + typename Graph::Edge edge;
7.272 + {
7.273 + const_graph.first(node);
7.274 + const_graph.next(node);
7.275 + }
7.276 + {
7.277 + const_graph.first(edge);
7.278 + const_graph.next(edge);
7.279 + }
7.280 + {
7.281 + const_graph.firstIn(edge, node);
7.282 + const_graph.nextIn(edge);
7.283 + }
7.284 + {
7.285 + const_graph.firstOut(edge, node);
7.286 + const_graph.nextOut(edge);
7.287 + }
7.288 + }
7.289 +
7.290 + Graph& graph;
7.291 + };
7.292 +
7.293 + /// An empty idable base graph class.
7.294 +
7.295 + /// This class provides beside the core graph features
7.296 + /// core id functions for the graph structure.
7.297 + /// The most of the base graphs should be conform to this concept.
7.298 + /// The id's are unique and immutable.
7.299 +
7.300 + class IDableGraphComponent : virtual public BaseGraphComponent {
7.301 + public:
7.302 +
7.303 + typedef BaseGraphComponent::Node Node;
7.304 + typedef BaseGraphComponent::Edge Edge;
7.305 +
7.306 + /// Gives back an unique integer id for the Node.
7.307 +
7.308 + /// Gives back an unique integer id for the Node.
7.309 + ///
7.310 + int id(const Node&) const { return -1;}
7.311 +
7.312 + /// Gives back an unique integer id for the Edge.
7.313 +
7.314 + /// Gives back an unique integer id for the Edge.
7.315 + ///
7.316 + int id(const Edge&) const { return -1;}
7.317 + };
7.318 +
7.319 +
7.320 + /// Concept check structure for IdableBaseGraph.
7.321 +
7.322 + /// Concept check structure for IdableBaseGraph.
7.323 + ///
7.324 + template <typename Graph>
7.325 + struct IDableGraphComponentConcept {
7.326 +
7.327 + void constraints() {
7.328 + const Graph& const_graph = graph;
7.329 + typename Graph::Node node;
7.330 + int nid = const_graph.id(node);
7.331 + nid = const_graph.id(node);
7.332 + typename Graph::Edge edge;
7.333 + int eid = const_graph.id(edge);
7.334 + eid = const_graph.id(edge);
7.335 + }
7.336 +
7.337 + Graph& graph;
7.338 + };
7.339 +
7.340 +
7.341 + /// An empty max-idable base graph class.
7.342 +
7.343 + /// This class provides beside the core graph features
7.344 + /// core max id functions for the graph structure.
7.345 + /// The most of the base graphs should be conform to this concept.
7.346 + /// The id's are unique and immutable.
7.347 + class MaxIDableGraphComponent : virtual public BaseGraphComponent {
7.348 + public:
7.349 +
7.350 + /// Gives back an integer greater or equal to the maximum Node id.
7.351 +
7.352 + /// Gives back an integer greater or equal to the maximum Node id.
7.353 + ///
7.354 + int maxEdgeId() const { return -1;}
7.355 +
7.356 + /// Gives back an integer greater or equal to the maximum Edge id.
7.357 +
7.358 + /// Gives back an integer greater or equal to the maximum Edge id.
7.359 + ///
7.360 + int maxNodeId() const { return -1;}
7.361 + };
7.362 +
7.363 + /// Concept check structure for MaxIdableBaseGraph.
7.364 +
7.365 + /// Concept check structure for MaxIdableBaseGraph.
7.366 + ///
7.367 + template <typename Graph>
7.368 + struct MaxIDableGraphComponentConcept {
7.369 +
7.370 + void constraints() {
7.371 + const Graph& const_graph = graph;
7.372 + int nid = const_graph.maxEdgeId();
7.373 + ignore_unused_variable_warning(nid);
7.374 + int eid = const_graph.maxNodeId();
7.375 + ignore_unused_variable_warning(eid);
7.376 + }
7.377 +
7.378 + Graph& graph;
7.379 + };
7.380 +
7.381 + /// An empty extendable base graph class.
7.382 +
7.383 + /// This class provides beside the core graph features
7.384 + /// core graph extend interface for the graph structure.
7.385 + /// The most of the base graphs should be conform to this concept.
7.386 + class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
7.387 + public:
7.388 +
7.389 + typedef BaseGraphComponent::Node Node;
7.390 + typedef BaseGraphComponent::Edge Edge;
7.391 +
7.392 + /// Adds a new Node to the graph.
7.393 +
7.394 + /// Adds a new Node to the graph.
7.395 + ///
7.396 + Node addNode() {
7.397 + return INVALID;
7.398 + }
7.399 +
7.400 + /// Adds a new Edge connects the two Nodes to the graph.
7.401 +
7.402 + /// Adds a new Edge connects the two Nodes to the graph.
7.403 + ///
7.404 + Edge addEdge(const Node& from, const Node& to) {
7.405 + return INVALID;
7.406 + }
7.407 +
7.408 + };
7.409 +
7.410 + /// Concept check structure for ExtendableBaseGraph.
7.411 +
7.412 + /// Concept check structure for ExtendableBaseGraph.
7.413 + ///
7.414 + template <typename Graph>
7.415 + struct BaseExtendableGraphComponentConcept {
7.416 + void constraints() {
7.417 + typename Graph::Node node_a, node_b;
7.418 + node_a = graph.addNode();
7.419 + typename Graph::Edge edge;
7.420 + edge = graph.addEdge(node_a, node_b);
7.421 + }
7.422 +
7.423 + Graph& graph;
7.424 + };
7.425 +
7.426 + /// An empty erasable base graph class.
7.427 +
7.428 + /// This class provides beside the core graph features
7.429 + /// core erase functions for the graph structure.
7.430 + /// The most of the base graphs should be conform to this concept.
7.431 + class BaseErasableGraphComponent : virtual public BaseGraphComponent {
7.432 + public:
7.433 +
7.434 + typedef BaseGraphComponent::Node Node;
7.435 + typedef BaseGraphComponent::Edge Edge;
7.436 +
7.437 + /// Erase a Node from the graph.
7.438 +
7.439 + /// Erase a Node from the graph. This function should not
7.440 + /// erase edges connecting to the Node.
7.441 + void erase(const Node&) {}
7.442 +
7.443 + /// Erase an Edge from the graph.
7.444 +
7.445 + /// Erase an Edge from the graph.
7.446 + ///
7.447 + void erase(const Edge&) {}
7.448 +
7.449 + };
7.450 +
7.451 + /// Concept check structure for ErasableBaseGraph.
7.452 +
7.453 + /// Concept check structure for ErasableBaseGraph.
7.454 + ///
7.455 + template <typename Graph>
7.456 + struct BaseErasableGraphComponentConcept {
7.457 + void constraints() {
7.458 + typename Graph::Node node;
7.459 + graph.erase(node);
7.460 + typename Graph::Edge edge;
7.461 + graph.erase(edge);
7.462 + }
7.463 +
7.464 + Graph& graph;
7.465 + };
7.466 +
7.467 + /// An empty clearable base graph class.
7.468 +
7.469 + /// This class provides beside the core graph features
7.470 + /// core clear functions for the graph structure.
7.471 + /// The most of the base graphs should be conform to this concept.
7.472 + class BaseClearableGraphComponent : virtual public BaseGraphComponent {
7.473 + public:
7.474 +
7.475 + /// Erase all the Nodes and Edges from the graph.
7.476 +
7.477 + /// Erase all the Nodes and Edges from the graph.
7.478 + ///
7.479 + void clear() {}
7.480 + };
7.481 +
7.482 + /// Concept check function for ErasableBaseGraph.
7.483 +
7.484 + /// Concept check function for ErasableBaseGraph.
7.485 + ///
7.486 + template <typename Graph>
7.487 + struct BaseClearableGraphComponentConcept {
7.488 + void constraints() {
7.489 + graph.clear();
7.490 + }
7.491 +
7.492 + Graph& graph;
7.493 + };
7.494 +
7.495 +
7.496 + class IterableGraphComponent : virtual public BaseGraphComponent {
7.497 +
7.498 + public:
7.499 +
7.500 + typedef IterableGraphComponent Graph;
7.501 +
7.502 + typedef BaseGraphComponent::Node Node;
7.503 + typedef BaseGraphComponent::Edge Edge;
7.504 +
7.505 + class NodeIt : public Node {
7.506 + public:
7.507 + NodeIt() {}
7.508 + NodeIt(Invalid) {}
7.509 + NodeIt(const Graph&) {}
7.510 +
7.511 + NodeIt& operator++() { return *this; }
7.512 + // Node operator*() const { return INVALID; }
7.513 +
7.514 + bool operator==(const NodeIt&) { return true;}
7.515 + bool operator!=(const NodeIt&) { return true;}
7.516 + };
7.517 +
7.518 + class EdgeIt : public Edge {
7.519 + public:
7.520 + EdgeIt() {}
7.521 + EdgeIt(Invalid) {}
7.522 + EdgeIt(const Graph&) {}
7.523 +
7.524 + EdgeIt& operator++() { return *this; }
7.525 + // Edge operator*() const { return INVALID; }
7.526 +
7.527 + bool operator==(const EdgeIt&) { return true;}
7.528 + bool operator!=(const EdgeIt&) { return true;}
7.529 + };
7.530 +
7.531 + class InEdgeIt : public Edge {
7.532 + public:
7.533 + InEdgeIt() {}
7.534 + InEdgeIt(Invalid) {}
7.535 + InEdgeIt(const Graph&, const Node&) {}
7.536 +
7.537 + InEdgeIt& operator++() { return *this; }
7.538 + // Edge operator*() const { return INVALID; }
7.539 +
7.540 + bool operator==(const InEdgeIt&) { return true;}
7.541 + bool operator!=(const InEdgeIt&) { return true;}
7.542 + };
7.543 +
7.544 + class OutEdgeIt : public Edge {
7.545 + public:
7.546 + OutEdgeIt() {}
7.547 + OutEdgeIt(Invalid) {}
7.548 + OutEdgeIt(const Graph&, const Node&) {}
7.549 +
7.550 + OutEdgeIt& operator++() { return *this; }
7.551 + // Edge operator*() const { return INVALID; }
7.552 +
7.553 + bool operator==(const OutEdgeIt&) { return true;}
7.554 + bool operator!=(const OutEdgeIt&) { return true;}
7.555 + };
7.556 +
7.557 + };
7.558 +
7.559 + template <typename Graph>
7.560 + struct IterableGraphComponentConcept {
7.561 +
7.562 + void constraints() {
7.563 +
7.564 + typedef typename Graph::Node Node;
7.565 + typedef typename Graph::NodeIt NodeIt;
7.566 + typedef typename Graph::Edge Edge;
7.567 + typedef typename Graph::EdgeIt EdgeIt;
7.568 + typedef typename Graph::InEdgeIt InEdgeIt;
7.569 + typedef typename Graph::OutEdgeIt OutEdgeIt;
7.570 +
7.571 + {
7.572 + NodeIt it;
7.573 + NodeIt jt(it);
7.574 + NodeIt kt(INVALID);
7.575 + NodeIt lt(graph);
7.576 + it = jt;
7.577 + jt = ++it;
7.578 + bool b;
7.579 + b = (it == INVALID);
7.580 + b = (it != INVALID);
7.581 + b = (it == jt);
7.582 + b = (it != jt);
7.583 + Node node = it;
7.584 + node = it;
7.585 + }
7.586 + {
7.587 + EdgeIt it;
7.588 + EdgeIt jt(it);
7.589 + EdgeIt kt(INVALID);
7.590 + EdgeIt lt(graph);
7.591 + it = jt;
7.592 + jt = ++it;
7.593 + bool b;
7.594 + b = (it == INVALID);
7.595 + b = (it != INVALID);
7.596 + b = (it == jt);
7.597 + b = (it != jt);
7.598 + Edge edge = it;
7.599 + edge = it;
7.600 + }
7.601 + {
7.602 + InEdgeIt it;
7.603 + InEdgeIt jt(it);
7.604 + InEdgeIt kt(INVALID);
7.605 + Node node;
7.606 + InEdgeIt lt(graph, node);
7.607 + it = jt;
7.608 + jt = ++it;
7.609 + bool b;
7.610 + b = (it == INVALID);
7.611 + b = (it != INVALID);
7.612 + b = (it == jt);
7.613 + b = (it != jt);
7.614 + Edge edge = it;
7.615 + edge = it;
7.616 + }
7.617 + {
7.618 + OutEdgeIt it;
7.619 + OutEdgeIt jt(it);
7.620 + OutEdgeIt kt(INVALID);
7.621 + Node node;
7.622 + OutEdgeIt lt(graph, node);
7.623 + it = jt;
7.624 + jt = ++it;
7.625 + bool b;
7.626 + b = (it == INVALID);
7.627 + b = (it != INVALID);
7.628 + b = (it == jt);
7.629 + b = (it != jt);
7.630 + Edge edge = it;
7.631 + edge = it;
7.632 + }
7.633 + }
7.634 + Graph& graph;
7.635 + };
7.636 +
7.637 +
7.638 + class IdMappableGraphComponent : virtual public BaseGraphComponent {
7.639 +
7.640 + typedef IdMappableGraphComponent Graph;
7.641 +
7.642 + typedef BaseGraphComponent::Node Node;
7.643 + typedef BaseGraphComponent::Edge Edge;
7.644 +
7.645 + public:
7.646 +
7.647 + class NodeIdMap : public ReadMap<Node, int> {
7.648 + public:
7.649 + NodeIdMap(const Graph&) {}
7.650 + int maxId() const { return -1;}
7.651 + };
7.652 +
7.653 + class EdgeIdMap : public ReadMap<Edge, int> {
7.654 + public:
7.655 + EdgeIdMap(const Graph&) {}
7.656 + int maxId() const { return -1;}
7.657 + };
7.658 +
7.659 + };
7.660 +
7.661 + template <typename Graph>
7.662 + struct IdMappableGraphComponentConcept {
7.663 + void constraints() {
7.664 + {
7.665 + typedef typename Graph::EdgeIdMap EdgeIdMap;
7.666 + function_requires<ReadMapConcept<EdgeIdMap> >();
7.667 + EdgeIdMap edge_map(graph);
7.668 + int n = edge_map.maxId();
7.669 + ignore_unused_variable_warning(n);
7.670 + }
7.671 + {
7.672 + typedef typename Graph::NodeIdMap NodeIdMap;
7.673 + function_requires<ReadMapConcept<NodeIdMap> >();
7.674 + NodeIdMap node_map(graph);
7.675 + int n = node_map.maxId();
7.676 + ignore_unused_variable_warning(n);
7.677 + }
7.678 + }
7.679 + Graph& graph;
7.680 + };
7.681 +
7.682 +
7.683 + class MappableGraphComponent : virtual public BaseGraphComponent {
7.684 + public:
7.685 +
7.686 + typedef MappableGraphComponent Graph;
7.687 +
7.688 + typedef BaseGraphComponent::Node Node;
7.689 + typedef BaseGraphComponent::Edge Edge;
7.690 +
7.691 + template <typename Value>
7.692 + class NodeMap : public ReferenceMap<Node, Value> {
7.693 + public:
7.694 + NodeMap(const Graph&) {}
7.695 + NodeMap(const Graph&, const Value&) {}
7.696 + NodeMap(const NodeMap&) {}
7.697 +
7.698 + NodeMap& operator=(const NodeMap&) { return *this;}
7.699 +
7.700 + };
7.701 +
7.702 + template <typename Value>
7.703 + class EdgeMap : public ReferenceMap<Edge, Value> {
7.704 + public:
7.705 + EdgeMap(const Graph&) {}
7.706 + EdgeMap(const Graph&, const Value&) {}
7.707 + EdgeMap(const EdgeMap&) {}
7.708 +
7.709 + EdgeMap& operator=(const EdgeMap&) { return *this;}
7.710 +
7.711 + };
7.712 +
7.713 + };
7.714 +
7.715 + template <typename Graph>
7.716 + struct MappableGraphComponentConcept {
7.717 +
7.718 + struct Type {
7.719 + int value;
7.720 + Type() : value(0) {}
7.721 + Type(int _v) : value(_v) {}
7.722 + };
7.723 +
7.724 + void constraints() {
7.725 + { // int map test
7.726 + typedef typename Graph::template NodeMap<int> IntNodeMap;
7.727 + function_requires<GraphMapConcept<IntNodeMap,Graph> >();
7.728 + } { // bool map test
7.729 + typedef typename Graph::template NodeMap<bool> BoolNodeMap;
7.730 + function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
7.731 + } { // Type map test
7.732 + typedef typename Graph::template NodeMap<Type> TypeNodeMap;
7.733 + function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
7.734 + }
7.735 +
7.736 + { // int map test
7.737 + typedef typename Graph::template EdgeMap<int> IntEdgeMap;
7.738 + function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
7.739 + } { // bool map test
7.740 + typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
7.741 + function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
7.742 + } { // Type map test
7.743 + typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
7.744 + function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
7.745 + }
7.746 + }
7.747 +
7.748 + Graph& graph;
7.749 + };
7.750 +
7.751 +
7.752 + class ExtendableGraphComponent : virtual public BaseGraphComponent {
7.753 + public:
7.754 +
7.755 + typedef ExtendableGraphComponent Graph;
7.756 +
7.757 + typedef BaseGraphComponent::Node Node;
7.758 + typedef BaseGraphComponent::Edge Edge;
7.759 +
7.760 + Node addNode() {
7.761 + return INVALID;
7.762 + }
7.763 +
7.764 + Edge addEdge(const Node& from, const Node& to) {
7.765 + return INVALID;
7.766 + }
7.767 +
7.768 + };
7.769 +
7.770 + template <typename Graph>
7.771 + struct ExtendableGraphComponentConcept {
7.772 + void constraints() {
7.773 + typename Graph::Node node_a, node_b;
7.774 + node_a = graph.addNode();
7.775 + typename Graph::Edge edge;
7.776 + edge = graph.addEdge(node_a, node_b);
7.777 + }
7.778 + Graph& graph;
7.779 + };
7.780 +
7.781 + class ErasableGraphComponent : virtual public BaseGraphComponent {
7.782 + public:
7.783 +
7.784 + typedef ErasableGraphComponent Graph;
7.785 +
7.786 + typedef BaseGraphComponent::Node Node;
7.787 + typedef BaseGraphComponent::Edge Edge;
7.788 +
7.789 + void erase(const Node&) {}
7.790 + void erase(const Edge&) {}
7.791 +
7.792 + };
7.793 +
7.794 + template <typename Graph>
7.795 + struct ErasableGraphComponentConcept {
7.796 + void constraints() {
7.797 + typename Graph::Node node;
7.798 + graph.erase(node);
7.799 + typename Graph::Edge edge;
7.800 + graph.erase(edge);
7.801 + }
7.802 +
7.803 + Graph& graph;
7.804 + };
7.805 +
7.806 + class ClearableGraphComponent : virtual public BaseGraphComponent {
7.807 + public:
7.808 +
7.809 + typedef ClearableGraphComponent Graph;
7.810 +
7.811 + typedef BaseGraphComponent::Node Node;
7.812 + typedef BaseGraphComponent::Edge Edge;
7.813 +
7.814 + void clear() {}
7.815 +
7.816 + };
7.817 +
7.818 + template <typename Graph>
7.819 + struct ClearableGraphComponentConcept {
7.820 + void constraints() {
7.821 + graph.clear();
7.822 + }
7.823 + Graph& graph;
7.824 + };
7.825 +
7.826 + }
7.827 +
7.828 +}
7.829 +
7.830 +#endif
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/lemon/concept/maps.h Thu Nov 04 20:24:59 2004 +0000
8.3 @@ -0,0 +1,246 @@
8.4 +/* -*- C++ -*-
8.5 + * src/lemon/concept/maps.h - Part of LEMON, a generic C++ optimization library
8.6 + *
8.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
8.9 + *
8.10 + * Permission to use, modify and distribute this software is granted
8.11 + * provided that this copyright notice appears in all copies. For
8.12 + * precise terms see the accompanying LICENSE file.
8.13 + *
8.14 + * This software is provided "AS IS" with no warranty of any kind,
8.15 + * express or implied, and with no claim as to its suitability for any
8.16 + * purpose.
8.17 + *
8.18 + */
8.19 +
8.20 +#ifndef LEMON_CONCEPT_MAPS_H
8.21 +#define LEMON_CONCEPT_MAPS_H
8.22 +
8.23 +#include <lemon/concept_check.h>
8.24 +
8.25 +///\ingroup concept
8.26 +///\file
8.27 +///\brief Map concepts checking classes for testing and documenting.
8.28 +
8.29 +namespace lemon {
8.30 +
8.31 + namespace concept {
8.32 +
8.33 + /// \addtogroup concept
8.34 + /// @{
8.35 +
8.36 + /// Readable map concept
8.37 + template<typename K, typename T>
8.38 + class ReadMap
8.39 + {
8.40 + public:
8.41 + /// Map's key type.
8.42 + typedef K KeyType;
8.43 + /// Map's value type. (The type of objects associated with the keys).
8.44 + typedef T ValueType;
8.45 +
8.46 + /// Returns the value associated with a key.
8.47 + ValueType operator[](const KeyType &k) const {return ValueType();}
8.48 +
8.49 + ///Default constructor
8.50 + ReadMap() {}
8.51 + };
8.52 +
8.53 +
8.54 + /// Writable map concept
8.55 + template<typename K, typename T>
8.56 + class WriteMap
8.57 + {
8.58 + public:
8.59 + /// Map's key type.
8.60 + typedef K KeyType;
8.61 + /// Map's value type. (The type of objects associated with the keys).
8.62 + typedef T ValueType;
8.63 +
8.64 + /// Sets the value associated with a key.
8.65 + void set(const KeyType &k,const ValueType &t) {}
8.66 +
8.67 + ///Default constructor
8.68 + WriteMap() {}
8.69 + };
8.70 +
8.71 + ///Read/Writable map concept
8.72 + template<typename K, typename T>
8.73 + class ReadWriteMap : public ReadMap<K,T>,
8.74 + public WriteMap<K,T>
8.75 + {
8.76 + public:
8.77 + /// Map's key type.
8.78 + typedef K KeyType;
8.79 + /// Map's value type. (The type of objects associated with the keys).
8.80 + typedef T ValueType;
8.81 +
8.82 + /// Returns the value associated with a key.
8.83 + ValueType operator[](const KeyType &k) const {return ValueType();}
8.84 + /// Sets the value associated with a key.
8.85 + void set(const KeyType &k,const ValueType &t) {}
8.86 +
8.87 + ///Default constructor
8.88 + ReadWriteMap() {}
8.89 + };
8.90 +
8.91 +
8.92 + ///Dereferable map concept
8.93 + template<typename K, typename T>
8.94 + class ReferenceMap : public ReadWriteMap<K,T>
8.95 + {
8.96 + public:
8.97 + /// Map's key type.
8.98 + typedef K KeyType;
8.99 + /// Map's value type. (The type of objects associated with the keys).
8.100 + typedef T ValueType;
8.101 +
8.102 + protected:
8.103 + ValueType tmp;
8.104 + public:
8.105 + typedef ValueType& ReferenceType;
8.106 + /// Map's const reference type.
8.107 + typedef const ValueType& ConstReferenceType;
8.108 +
8.109 + ///Returns a reference to the value associated to a key.
8.110 + ReferenceType operator[](const KeyType &i) { return tmp; }
8.111 + ///Returns a const reference to the value associated to a key.
8.112 + ConstReferenceType operator[](const KeyType &i) const
8.113 + { return tmp; }
8.114 + /// Sets the value associated with a key.
8.115 + void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
8.116 +
8.117 + ///Default constructor
8.118 + ReferenceMap() {}
8.119 + };
8.120 +
8.121 +
8.122 + template<typename Item, typename T, typename Graph>
8.123 + class GraphMap : public ReadWriteMap<Item, T> {
8.124 + // I really, really don't like the idea that every graph should have
8.125 + // reference maps! --klao
8.126 +
8.127 + private:
8.128 + // We state explicitly that graph maps have no default constructor?
8.129 + GraphMap();
8.130 +
8.131 + public:
8.132 + explicit GraphMap(Graph const&) {}
8.133 + // value for initializing
8.134 + GraphMap(Graph const&, T) {}
8.135 +
8.136 + // this probably should be required:
8.137 + GraphMap(GraphMap const&) {}
8.138 + GraphMap& operator=(GraphMap const&) { return *this; }
8.139 +
8.140 + // but this is a absolute no-op! We should provide a more generic
8.141 + // graph-map-copy operation.
8.142 + //
8.143 + // template<typename TT>
8.144 + // GraphMap(GraphMap<TT> const&);
8.145 + //
8.146 + // template<typename TT>
8.147 + // GraphMap& operator=(const GraphMap<TT>&);
8.148 + };
8.149 +
8.150 +
8.151 + /**************** Concept-checking classes ****************/
8.152 +
8.153 + template<typename ReadMap>
8.154 + struct ReadMapConcept {
8.155 + typedef typename ReadMap::KeyType KeyType;
8.156 + typedef typename ReadMap::ValueType ValueType;
8.157 +
8.158 + void constraints() {
8.159 + // No constraints for constructor.
8.160 +
8.161 + // What are the requirement for the ValueType?
8.162 + // CopyConstructible? Assignable? None of these?
8.163 + ValueType v = m[k];
8.164 + v = m[k];
8.165 +
8.166 + // FIXME:
8.167 + ignore_unused_variable_warning(v);
8.168 + }
8.169 +
8.170 + ReadMap m;
8.171 + KeyType k;
8.172 + };
8.173 +
8.174 + template<typename WriteMap>
8.175 + struct WriteMapConcept {
8.176 + typedef typename WriteMap::KeyType KeyType;
8.177 + typedef typename WriteMap::ValueType ValueType;
8.178 +
8.179 + void constraints() {
8.180 + // No constraints for constructor.
8.181 +
8.182 + m.set(k, v);
8.183 + }
8.184 +
8.185 + WriteMap m;
8.186 + KeyType k;
8.187 + ValueType v;
8.188 + };
8.189 +
8.190 + template<typename ReadWriteMap>
8.191 + struct ReadWriteMapConcept {
8.192 + void constraints() {
8.193 + function_requires< ReadMapConcept<ReadWriteMap> >();
8.194 + function_requires< WriteMapConcept<ReadWriteMap> >();
8.195 + }
8.196 + };
8.197 +
8.198 + template<typename ReferenceMap>
8.199 + struct ReferenceMapConcept {
8.200 + typedef typename ReferenceMap::KeyType KeyType;
8.201 + typedef typename ReferenceMap::ValueType ValueType;
8.202 + typedef typename ReferenceMap::ReferenceType ReferenceType;
8.203 +
8.204 + // What for is this?
8.205 + typedef typename ReferenceMap::ConstReferenceType ConstReferenceType;
8.206 +
8.207 + void constraints() {
8.208 + function_requires< ReadWriteMapConcept<ReferenceMap> >();
8.209 +
8.210 + m[k] = v;
8.211 + // Or should we require real reference?
8.212 + // Like this:
8.213 + // ValueType &vv = m[k];
8.214 + // ignore_unused_variable_warning(vv);
8.215 + }
8.216 +
8.217 + ReferenceMap m;
8.218 + KeyType k;
8.219 + ValueType v;
8.220 + };
8.221 +
8.222 + /// \todo GraphMapConceptCheck
8.223 +
8.224 + template<typename GraphMap, typename Graph>
8.225 + struct GraphMapConcept {
8.226 + void constraints() {
8.227 + function_requires< ReadWriteMapConcept<GraphMap> >();
8.228 + // Construction with a graph parameter
8.229 + GraphMap a(g);
8.230 + // Ctor with a graph and a default value parameter
8.231 + GraphMap a2(g,t);
8.232 + // Copy ctor. Do we need it?
8.233 + GraphMap b=c;
8.234 + // Copy operator. Do we need it?
8.235 + a=b;
8.236 +
8.237 + ignore_unused_variable_warning(a2);
8.238 + }
8.239 + const GraphMap &c;
8.240 + const Graph &g;
8.241 + const typename GraphMap::ValueType &t;
8.242 + };
8.243 +
8.244 +
8.245 + // @}
8.246 +
8.247 + } //namespace concept
8.248 +} //namespace lemon
8.249 +#endif // LEMON_CONCEPT_MAPS_H
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/src/lemon/concept/path.h Thu Nov 04 20:24:59 2004 +0000
9.3 @@ -0,0 +1,236 @@
9.4 +/* -*- C++ -*-
9.5 + * src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
9.6 + *
9.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
9.9 + *
9.10 + * Permission to use, modify and distribute this software is granted
9.11 + * provided that this copyright notice appears in all copies. For
9.12 + * precise terms see the accompanying LICENSE file.
9.13 + *
9.14 + * This software is provided "AS IS" with no warranty of any kind,
9.15 + * express or implied, and with no claim as to its suitability for any
9.16 + * purpose.
9.17 + *
9.18 + */
9.19 +
9.20 +///\ingroup concept
9.21 +///\file
9.22 +///\brief Classes for representing paths in graphs.
9.23 +
9.24 +#ifndef LEMON_CONCEPT_PATH_H
9.25 +#define LEMON_CONCEPT_PATH_H
9.26 +
9.27 +#include <lemon/invalid.h>
9.28 +
9.29 +namespace lemon {
9.30 + namespace concept {
9.31 + /// \addtogroup concept
9.32 + /// @{
9.33 +
9.34 +
9.35 + //! \brief A skeletom structure for representing directed paths in a graph.
9.36 + //!
9.37 + //! A skeleton structure for representing directed paths in a graph.
9.38 + //! \param GR The graph type in which the path is.
9.39 + //!
9.40 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
9.41 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
9.42 + //! and \c Edge of the original graph.
9.43 + template<typename GR>
9.44 + class Path {
9.45 + public:
9.46 +
9.47 + /// Type of the underlying graph.
9.48 + typedef /*typename*/ GR Graph;
9.49 + /// Edge type of the underlying graph.
9.50 + typedef typename Graph::Edge GraphEdge;
9.51 + /// Node type of the underlying graph.
9.52 + typedef typename Graph::Node GraphNode;
9.53 + class NodeIt;
9.54 + class EdgeIt;
9.55 +
9.56 + /// \param _G The graph in which the path is.
9.57 + ///
9.58 + Path(const Graph &_G) {}
9.59 +
9.60 + /// Length of the path.
9.61 + size_t length() const {return 0;}
9.62 + /// Returns whether the path is empty.
9.63 + bool empty() const { return true;}
9.64 +
9.65 + /// Resets the path to an empty path.
9.66 + void clear() {}
9.67 +
9.68 + /// \brief Starting point of the path.
9.69 + ///
9.70 + /// Starting point of the path.
9.71 + /// Returns INVALID if the path is empty.
9.72 + GraphNode/*It*/ head() const {return INVALID;}
9.73 + /// \brief End point of the path.
9.74 + ///
9.75 + /// End point of the path.
9.76 + /// Returns INVALID if the path is empty.
9.77 + GraphNode/*It*/ tail() const {return INVALID;}
9.78 +
9.79 + /// \brief First NodeIt/EdgeIt.
9.80 + ///
9.81 + /// Initializes node or edge iterator to point to the first
9.82 + /// node or edge.
9.83 + template<typename It>
9.84 + It& first(It &i) const { return i=It(*this); }
9.85 +
9.86 + /// \brief The head of an edge.
9.87 + ///
9.88 + /// Returns node iterator pointing to the head node of the
9.89 + /// given edge iterator.
9.90 + NodeIt head(const EdgeIt& e) const {return INVALID;}
9.91 +
9.92 + /// \brief The tail of an edge.
9.93 + ///
9.94 + /// Returns node iterator pointing to the tail node of the
9.95 + /// given edge iterator.
9.96 + NodeIt tail(const EdgeIt& e) const {return INVALID;}
9.97 +
9.98 +
9.99 + /* Iterator classes */
9.100 +
9.101 + /**
9.102 + * \brief Iterator class to iterate on the edges of the paths
9.103 + *
9.104 + * \ingroup concept
9.105 + * This class is used to iterate on the edges of the paths
9.106 + *
9.107 + * Of course it converts to Graph::Edge
9.108 + *
9.109 + */
9.110 + class EdgeIt {
9.111 + public:
9.112 + /// Default constructor
9.113 + EdgeIt() {}
9.114 + /// Invalid constructor
9.115 + EdgeIt(Invalid) {}
9.116 + /// Constructor with starting point
9.117 + EdgeIt(const Path &_p) {}
9.118 +
9.119 + operator GraphEdge () const {}
9.120 +
9.121 + /// Next edge
9.122 + EdgeIt& operator++() {return *this;}
9.123 +
9.124 + /// Comparison operator
9.125 + bool operator==(const EdgeIt& e) const {return true;}
9.126 + /// Comparison operator
9.127 + bool operator!=(const EdgeIt& e) const {return true;}
9.128 +// /// Comparison operator
9.129 +// /// \todo It is not clear what is the "natural" ordering.
9.130 +// bool operator<(const EdgeIt& e) const {}
9.131 +
9.132 + };
9.133 +
9.134 + /**
9.135 + * \brief Iterator class to iterate on the nodes of the paths
9.136 + *
9.137 + * \ingroup concept
9.138 + * This class is used to iterate on the nodes of the paths
9.139 + *
9.140 + * Of course it converts to Graph::Node.
9.141 + *
9.142 + */
9.143 + class NodeIt {
9.144 + public:
9.145 + /// Default constructor
9.146 + NodeIt() {}
9.147 + /// Invalid constructor
9.148 + NodeIt(Invalid) {}
9.149 + /// Constructor with starting point
9.150 + NodeIt(const Path &_p) {}
9.151 +
9.152 + ///Conversion to Graph::Node
9.153 + operator const GraphNode& () const {}
9.154 + /// Next node
9.155 + NodeIt& operator++() {return *this;}
9.156 +
9.157 + /// Comparison operator
9.158 + bool operator==(const NodeIt& e) const {return true;}
9.159 + /// Comparison operator
9.160 + bool operator!=(const NodeIt& e) const {return true;}
9.161 +// /// Comparison operator
9.162 +// /// \todo It is not clear what is the "natural" ordering.
9.163 +// bool operator<(const NodeIt& e) const {}
9.164 +
9.165 + };
9.166 +
9.167 + friend class Builder;
9.168 +
9.169 + /**
9.170 + * \brief Class to build paths
9.171 + *
9.172 + * \ingroup concept
9.173 + * This class is used to fill a path with edges.
9.174 + *
9.175 + * You can push new edges to the front and to the back of the path in
9.176 + * arbitrary order then you should commit these changes to the graph.
9.177 + *
9.178 + * While the builder is active (after the first modifying
9.179 + * operation and until the call of \ref commit())
9.180 + * the underlining Path is in a
9.181 + * "transitional" state (operations on it have undefined result).
9.182 + */
9.183 + class Builder {
9.184 + public:
9.185 +
9.186 + Path &P;
9.187 +
9.188 + ///\param _P the path you want to fill in.
9.189 + ///
9.190 + Builder(Path &_P) : P(_P) {}
9.191 +
9.192 + /// Sets the starting node of the path.
9.193 +
9.194 + /// Sets the starting node of the path. Edge added to the path
9.195 + /// afterwards have to be incident to this node.
9.196 + /// You \em must start building an empry path with this functions.
9.197 + /// (And you \em must \em not use it later).
9.198 + /// \sa pushFront()
9.199 + /// \sa pushBack()
9.200 + void setStartNode(const GraphNode &) {}
9.201 +
9.202 + ///Push a new edge to the front of the path
9.203 +
9.204 + ///Push a new edge to the front of the path.
9.205 + ///If the path is empty, you \em must call \ref setStartNode() before
9.206 + ///the first use of \ref pushFront().
9.207 + void pushFront(const GraphEdge& e) {}
9.208 +
9.209 + ///Push a new edge to the back of the path
9.210 +
9.211 + ///Push a new edge to the back of the path.
9.212 + ///If the path is empty, you \em must call \ref setStartNode() before
9.213 + ///the first use of \ref pushBack().
9.214 + void pushBack(const GraphEdge& e) {}
9.215 +
9.216 + ///Commit the changes to the path.
9.217 + void commit() {}
9.218 +
9.219 + ///Reserve (front) storage for the builder in advance.
9.220 +
9.221 + ///If you know an reasonable upper bound of the number of the edges
9.222 + ///to add to the front of the path,
9.223 + ///using this function you may speed up the building.
9.224 + void reserveFront(size_t r) {}
9.225 + ///Reserve (back) storage for the builder in advance.
9.226 +
9.227 + ///If you know an reasonable upper bound of the number of the edges
9.228 + ///to add to the back of the path,
9.229 + ///using this function you may speed up the building.
9.230 + void reserveBack(size_t r) {}
9.231 + };
9.232 + };
9.233 +
9.234 + ///@}
9.235 + }
9.236 +
9.237 +} // namespace lemon
9.238 +
9.239 +#endif // LEMON_CONCEPT_PATH_H
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/src/lemon/concept/sym_graph.h Thu Nov 04 20:24:59 2004 +0000
10.3 @@ -0,0 +1,653 @@
10.4 +/* -*- C++ -*-
10.5 + * src/lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library
10.6 + *
10.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
10.9 + *
10.10 + * Permission to use, modify and distribute this software is granted
10.11 + * provided that this copyright notice appears in all copies. For
10.12 + * precise terms see the accompanying LICENSE file.
10.13 + *
10.14 + * This software is provided "AS IS" with no warranty of any kind,
10.15 + * express or implied, and with no claim as to its suitability for any
10.16 + * purpose.
10.17 + *
10.18 + */
10.19 +
10.20 +#ifndef LEMON_CONCEPT_SYM_GRAPH_H
10.21 +#define LEMON_CONCEPT_SYM_GRAPH_H
10.22 +
10.23 +///\ingroup concept
10.24 +///\file
10.25 +///\brief Declaration of SymGraph.
10.26 +
10.27 +#include <lemon/invalid.h>
10.28 +#include <lemon/concept/graph.h>
10.29 +#include <lemon/concept/maps.h>
10.30 +
10.31 +namespace lemon {
10.32 + namespace concept {
10.33 +
10.34 + /// \addtogroup concept
10.35 + /// @{
10.36 +
10.37 + /// An empty static graph class.
10.38 +
10.39 + /// This class provides all the common features of a symmetric
10.40 + /// graph structure, however completely without implementations and
10.41 + /// real data structures behind the interface.
10.42 + /// All graph algorithms should compile with this class, but it will not
10.43 + /// run properly, of course.
10.44 + ///
10.45 + /// It can be used for checking the interface compatibility,
10.46 + /// or it can serve as a skeleton of a new symmetric graph structure.
10.47 + ///
10.48 + /// Also, you will find here the full documentation of a certain graph
10.49 + /// feature, the documentation of a real symmetric graph imlementation
10.50 + /// like @ref SymListGraph or
10.51 + /// @ref lemon::SymSmartGraph will just refer to this structure.
10.52 + class StaticSymGraph
10.53 + {
10.54 + public:
10.55 + /// Defalult constructor.
10.56 +
10.57 + /// Defalult constructor.
10.58 + ///
10.59 + StaticSymGraph() { }
10.60 + ///Copy consructor.
10.61 +
10.62 +// ///\todo It is not clear, what we expect from a copy constructor.
10.63 +// ///E.g. How to assign the nodes/edges to each other? What about maps?
10.64 +// StaticGraph(const StaticGraph& g) { }
10.65 +
10.66 + /// The base type of node iterators,
10.67 + /// or in other words, the trivial node iterator.
10.68 +
10.69 + /// This is the base type of each node iterator,
10.70 + /// thus each kind of node iterator converts to this.
10.71 + /// More precisely each kind of node iterator should be inherited
10.72 + /// from the trivial node iterator.
10.73 + class Node {
10.74 + public:
10.75 + /// Default constructor
10.76 +
10.77 + /// @warning The default constructor sets the iterator
10.78 + /// to an undefined value.
10.79 + Node() { }
10.80 + /// Copy constructor.
10.81 +
10.82 + /// Copy constructor.
10.83 + ///
10.84 + Node(const Node&) { }
10.85 +
10.86 + /// Invalid constructor \& conversion.
10.87 +
10.88 + /// This constructor initializes the iterator to be invalid.
10.89 + /// \sa Invalid for more details.
10.90 + Node(Invalid) { }
10.91 + /// Equality operator
10.92 +
10.93 + /// Two iterators are equal if and only if they point to the
10.94 + /// same object or both are invalid.
10.95 + bool operator==(Node) const { return true; }
10.96 +
10.97 + /// Inequality operator
10.98 +
10.99 + /// \sa operator==(Node n)
10.100 + ///
10.101 + bool operator!=(Node) const { return true; }
10.102 +
10.103 + ///Comparison operator.
10.104 +
10.105 + ///This is a strict ordering between the nodes.
10.106 + ///
10.107 + ///This ordering can be different from the order in which NodeIt
10.108 + ///goes through the nodes.
10.109 + ///\todo Possibly we don't need it.
10.110 + bool operator<(Node) const { return true; }
10.111 + };
10.112 +
10.113 + /// This iterator goes through each node.
10.114 +
10.115 + /// This iterator goes through each node.
10.116 + /// Its usage is quite simple, for example you can count the number
10.117 + /// of nodes in graph \c g of type \c Graph like this:
10.118 + /// \code
10.119 + /// int count=0;
10.120 + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
10.121 + /// \endcode
10.122 + class NodeIt : public Node {
10.123 + public:
10.124 + /// Default constructor
10.125 +
10.126 + /// @warning The default constructor sets the iterator
10.127 + /// to an undefined value.
10.128 + NodeIt() { }
10.129 + /// Copy constructor.
10.130 +
10.131 + /// Copy constructor.
10.132 + ///
10.133 + NodeIt(const NodeIt&) { }
10.134 + /// Invalid constructor \& conversion.
10.135 +
10.136 + /// Initialize the iterator to be invalid.
10.137 + /// \sa Invalid for more details.
10.138 + NodeIt(Invalid) { }
10.139 + /// Sets the iterator to the first node.
10.140 +
10.141 + /// Sets the iterator to the first node of \c g.
10.142 + ///
10.143 + NodeIt(const StaticSymGraph& g) { }
10.144 + /// Node -> NodeIt conversion.
10.145 +
10.146 + /// Sets the iterator to the node of \c g pointed by the trivial
10.147 + /// iterator n.
10.148 + /// This feature necessitates that each time we
10.149 + /// iterate the edge-set, the iteration order is the same.
10.150 + NodeIt(const StaticSymGraph& g, const Node& n) { }
10.151 + /// Next node.
10.152 +
10.153 + /// Assign the iterator to the next node.
10.154 + ///
10.155 + NodeIt& operator++() { return *this; }
10.156 + };
10.157 +
10.158 +
10.159 + /// The base type of the symmetric edge iterators.
10.160 +
10.161 + /// The base type of the symmetric edge iterators.
10.162 + ///
10.163 + class SymEdge {
10.164 + public:
10.165 + /// Default constructor
10.166 +
10.167 + /// @warning The default constructor sets the iterator
10.168 + /// to an undefined value.
10.169 + SymEdge() { }
10.170 + /// Copy constructor.
10.171 +
10.172 + /// Copy constructor.
10.173 + ///
10.174 + SymEdge(const SymEdge&) { }
10.175 + /// Initialize the iterator to be invalid.
10.176 +
10.177 + /// Initialize the iterator to be invalid.
10.178 + ///
10.179 + SymEdge(Invalid) { }
10.180 + /// Equality operator
10.181 +
10.182 + /// Two iterators are equal if and only if they point to the
10.183 + /// same object or both are invalid.
10.184 + bool operator==(SymEdge) const { return true; }
10.185 + /// Inequality operator
10.186 +
10.187 + /// \sa operator==(Node n)
10.188 + ///
10.189 + bool operator!=(SymEdge) const { return true; }
10.190 + ///Comparison operator.
10.191 +
10.192 + ///This is a strict ordering between the nodes.
10.193 + ///
10.194 + ///This ordering can be different from the order in which NodeIt
10.195 + ///goes through the nodes.
10.196 + ///\todo Possibly we don't need it.
10.197 + bool operator<(SymEdge) const { return true; }
10.198 + };
10.199 +
10.200 +
10.201 + /// The base type of the edge iterators.
10.202 +
10.203 + /// The base type of the edge iterators.
10.204 + ///
10.205 + class Edge : public SymEdge {
10.206 + public:
10.207 + /// Default constructor
10.208 +
10.209 + /// @warning The default constructor sets the iterator
10.210 + /// to an undefined value.
10.211 + Edge() { }
10.212 + /// Copy constructor.
10.213 +
10.214 + /// Copy constructor.
10.215 + ///
10.216 + Edge(const Edge&) { }
10.217 + /// Initialize the iterator to be invalid.
10.218 +
10.219 + /// Initialize the iterator to be invalid.
10.220 + ///
10.221 + Edge(Invalid) { }
10.222 + /// Equality operator
10.223 +
10.224 + /// Two iterators are equal if and only if they point to the
10.225 + /// same object or both are invalid.
10.226 + bool operator==(Edge) const { return true; }
10.227 + /// Inequality operator
10.228 +
10.229 + /// \sa operator==(Node n)
10.230 + ///
10.231 + bool operator!=(Edge) const { return true; }
10.232 + ///Comparison operator.
10.233 +
10.234 + ///This is a strict ordering between the nodes.
10.235 + ///
10.236 + ///This ordering can be different from the order in which NodeIt
10.237 + ///goes through the nodes.
10.238 + ///\todo Possibly we don't need it.
10.239 + bool operator<(Edge) const { return true; }
10.240 + };
10.241 +
10.242 + /// This iterator goes trough the outgoing edges of a node.
10.243 +
10.244 + /// This iterator goes trough the \e outgoing edges of a certain node
10.245 + /// of a graph.
10.246 + /// Its usage is quite simple, for example you can count the number
10.247 + /// of outgoing edges of a node \c n
10.248 + /// in graph \c g of type \c Graph as follows.
10.249 + /// \code
10.250 + /// int count=0;
10.251 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
10.252 + /// \endcode
10.253 +
10.254 + class OutEdgeIt : public Edge {
10.255 + public:
10.256 + /// Default constructor
10.257 +
10.258 + /// @warning The default constructor sets the iterator
10.259 + /// to an undefined value.
10.260 + OutEdgeIt() { }
10.261 + /// Copy constructor.
10.262 +
10.263 + /// Copy constructor.
10.264 + ///
10.265 + OutEdgeIt(const OutEdgeIt&) { }
10.266 + /// Initialize the iterator to be invalid.
10.267 +
10.268 + /// Initialize the iterator to be invalid.
10.269 + ///
10.270 + OutEdgeIt(Invalid) { }
10.271 + /// This constructor sets the iterator to first outgoing edge.
10.272 +
10.273 + /// This constructor set the iterator to the first outgoing edge of
10.274 + /// node
10.275 + ///@param n the node
10.276 + ///@param g the graph
10.277 + OutEdgeIt(const StaticSymGraph& g, const Node& n) { }
10.278 + /// Edge -> OutEdgeIt conversion
10.279 +
10.280 + /// Sets the iterator to the value of the trivial iterator \c e.
10.281 + /// This feature necessitates that each time we
10.282 + /// iterate the edge-set, the iteration order is the same.
10.283 + OutEdgeIt(const StaticSymGraph& g, const Edge& e) { }
10.284 + ///Next outgoing edge
10.285 +
10.286 + /// Assign the iterator to the next
10.287 + /// outgoing edge of the corresponding node.
10.288 + OutEdgeIt& operator++() { return *this; }
10.289 + };
10.290 +
10.291 + /// This iterator goes trough the incoming edges of a node.
10.292 +
10.293 + /// This iterator goes trough the \e incoming edges of a certain node
10.294 + /// of a graph.
10.295 + /// Its usage is quite simple, for example you can count the number
10.296 + /// of outgoing edges of a node \c n
10.297 + /// in graph \c g of type \c Graph as follows.
10.298 + /// \code
10.299 + /// int count=0;
10.300 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
10.301 + /// \endcode
10.302 +
10.303 + class InEdgeIt : public Edge {
10.304 + public:
10.305 + /// Default constructor
10.306 +
10.307 + /// @warning The default constructor sets the iterator
10.308 + /// to an undefined value.
10.309 + InEdgeIt() { }
10.310 + /// Copy constructor.
10.311 +
10.312 + /// Copy constructor.
10.313 + ///
10.314 + InEdgeIt(const InEdgeIt&) { }
10.315 + /// Initialize the iterator to be invalid.
10.316 +
10.317 + /// Initialize the iterator to be invalid.
10.318 + ///
10.319 + InEdgeIt(Invalid) { }
10.320 + /// This constructor sets the iterator to first incoming edge.
10.321 +
10.322 + /// This constructor set the iterator to the first incoming edge of
10.323 + /// node
10.324 + ///@param n the node
10.325 + ///@param g the graph
10.326 + InEdgeIt(const StaticSymGraph& g, const Node& n) { }
10.327 + /// Edge -> InEdgeIt conversion
10.328 +
10.329 + /// Sets the iterator to the value of the trivial iterator \c e.
10.330 + /// This feature necessitates that each time we
10.331 + /// iterate the edge-set, the iteration order is the same.
10.332 + InEdgeIt(const StaticSymGraph& g, const Edge& n) { }
10.333 + /// Next incoming edge
10.334 +
10.335 + /// Assign the iterator to the next inedge of the corresponding node.
10.336 + ///
10.337 + InEdgeIt& operator++() { return *this; }
10.338 + };
10.339 + /// This iterator goes through each symmetric edge.
10.340 +
10.341 + /// This iterator goes through each symmetric edge of a graph.
10.342 + /// Its usage is quite simple, for example you can count the number
10.343 + /// of symmetric edges in a graph \c g of type \c Graph as follows:
10.344 + /// \code
10.345 + /// int count=0;
10.346 + /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count;
10.347 + /// \endcode
10.348 + class SymEdgeIt : public SymEdge {
10.349 + public:
10.350 + /// Default constructor
10.351 +
10.352 + /// @warning The default constructor sets the iterator
10.353 + /// to an undefined value.
10.354 + SymEdgeIt() { }
10.355 + /// Copy constructor.
10.356 +
10.357 + /// Copy constructor.
10.358 + ///
10.359 + SymEdgeIt(const SymEdgeIt&) { }
10.360 + /// Initialize the iterator to be invalid.
10.361 +
10.362 + /// Initialize the iterator to be invalid.
10.363 + ///
10.364 + SymEdgeIt(Invalid) { }
10.365 + /// This constructor sets the iterator to first edge.
10.366 +
10.367 + /// This constructor set the iterator to the first edge of
10.368 + /// node
10.369 + ///@param g the graph
10.370 + SymEdgeIt(const StaticSymGraph& g) { }
10.371 + /// Edge -> EdgeIt conversion
10.372 +
10.373 + /// Sets the iterator to the value of the trivial iterator \c e.
10.374 + /// This feature necessitates that each time we
10.375 + /// iterate the edge-set, the iteration order is the same.
10.376 + SymEdgeIt(const StaticSymGraph&, const SymEdge&) { }
10.377 + ///Next edge
10.378 +
10.379 + /// Assign the iterator to the next
10.380 + /// edge of the corresponding node.
10.381 + SymEdgeIt& operator++() { return *this; }
10.382 + };
10.383 + /// This iterator goes through each edge.
10.384 +
10.385 + /// This iterator goes through each edge of a graph.
10.386 + /// Its usage is quite simple, for example you can count the number
10.387 + /// of edges in a graph \c g of type \c Graph as follows:
10.388 + /// \code
10.389 + /// int count=0;
10.390 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
10.391 + /// \endcode
10.392 + class EdgeIt : public Edge {
10.393 + public:
10.394 + /// Default constructor
10.395 +
10.396 + /// @warning The default constructor sets the iterator
10.397 + /// to an undefined value.
10.398 + EdgeIt() { }
10.399 + /// Copy constructor.
10.400 +
10.401 + /// Copy constructor.
10.402 + ///
10.403 + EdgeIt(const EdgeIt&) { }
10.404 + /// Initialize the iterator to be invalid.
10.405 +
10.406 + /// Initialize the iterator to be invalid.
10.407 + ///
10.408 + EdgeIt(Invalid) { }
10.409 + /// This constructor sets the iterator to first edge.
10.410 +
10.411 + /// This constructor set the iterator to the first edge of
10.412 + /// node
10.413 + ///@param g the graph
10.414 + EdgeIt(const StaticSymGraph& g) { }
10.415 + /// Edge -> EdgeIt conversion
10.416 +
10.417 + /// Sets the iterator to the value of the trivial iterator \c e.
10.418 + /// This feature necessitates that each time we
10.419 + /// iterate the edge-set, the iteration order is the same.
10.420 + EdgeIt(const StaticSymGraph&, const Edge&) { }
10.421 + ///Next edge
10.422 +
10.423 + /// Assign the iterator to the next
10.424 + /// edge of the corresponding node.
10.425 + EdgeIt& operator++() { return *this; }
10.426 + };
10.427 +
10.428 + /// First node of the graph.
10.429 +
10.430 + /// \retval i the first node.
10.431 + /// \return the first node.
10.432 + ///
10.433 + NodeIt& first(NodeIt& i) const { return i; }
10.434 +
10.435 + /// The first incoming edge.
10.436 +
10.437 + /// The first incoming edge.
10.438 + ///
10.439 + InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
10.440 + /// The first outgoing edge.
10.441 +
10.442 + /// The first outgoing edge.
10.443 + ///
10.444 + OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
10.445 + /// The first edge of the Graph.
10.446 +
10.447 + /// The first edge of the Graph.
10.448 + ///
10.449 + EdgeIt& first(EdgeIt& i) const { return i; }
10.450 + /// The first symmetric edge of the Graph.
10.451 +
10.452 + /// The first symmetric edge of the Graph.
10.453 + ///
10.454 + SymEdgeIt& first(SymEdgeIt& i) const { return i; }
10.455 +
10.456 + ///Gives back the head node of an edge.
10.457 +
10.458 + ///Gives back the head node of an edge.
10.459 + ///
10.460 + Node head(Edge) const { return INVALID; }
10.461 + ///Gives back the tail node of an edge.
10.462 +
10.463 + ///Gives back the tail node of an edge.
10.464 + ///
10.465 + Node tail(Edge) const { return INVALID; }
10.466 +
10.467 + ///Gives back the first node of an symmetric edge.
10.468 +
10.469 + ///Gives back the first node of an symmetric edge.
10.470 + ///
10.471 + Node head(SymEdge) const { return INVALID; }
10.472 + ///Gives back the second node of an symmetric edge.
10.473 +
10.474 + ///Gives back the second node of an symmetric edge.
10.475 + ///
10.476 + Node tail(SymEdge) const { return INVALID; }
10.477 + ///Gives back the \e id of a node.
10.478 +
10.479 + ///\warning Not all graph structures provide this feature.
10.480 + ///
10.481 + ///\todo Should each graph provide \c id?
10.482 + int id(const Node&) const { return 0; }
10.483 + ///Gives back the \e id of an edge.
10.484 +
10.485 + ///\warning Not all graph structures provide this feature.
10.486 + ///
10.487 + ///\todo Should each graph provide \c id?
10.488 + int id(const Edge&) const { return 0; }
10.489 +
10.490 + ///\warning Not all graph structures provide this feature.
10.491 + ///
10.492 + ///\todo Should each graph provide \c id?
10.493 + int id(const SymEdge&) const { return 0; }
10.494 +
10.495 + ///\e
10.496 +
10.497 + ///\todo Should it be in the concept?
10.498 + ///
10.499 + int nodeNum() const { return 0; }
10.500 + ///\e
10.501 +
10.502 + ///\todo Should it be in the concept?
10.503 + ///
10.504 + int edgeNum() const { return 0; }
10.505 +
10.506 + ///\todo Should it be in the concept?
10.507 + ///
10.508 + int symEdgeNum() const { return 0; }
10.509 +
10.510 +
10.511 + /// Gives back the forward directed edge of the symmetric edge.
10.512 + Edge forward(SymEdge) const {return INVALID;}
10.513 +
10.514 + /// Gives back the backward directed edge of the symmetric edge.
10.515 + Edge backward(SymEdge) const {return INVALID;};
10.516 +
10.517 + /// Gives back the opposite of the edge.
10.518 + Edge opposite(Edge) const {return INVALID;}
10.519 +
10.520 + ///Reference map of the nodes to type \c T.
10.521 + /// \ingroup concept
10.522 + ///Reference map of the nodes to type \c T.
10.523 + /// \sa Reference
10.524 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
10.525 + /// needs some extra attention!
10.526 + template<class T> class NodeMap : public ReferenceMap< Node, T >
10.527 + {
10.528 + public:
10.529 +
10.530 + ///\e
10.531 + NodeMap(const StaticSymGraph&) { }
10.532 + ///\e
10.533 + NodeMap(const StaticSymGraph&, T) { }
10.534 +
10.535 + ///Copy constructor
10.536 + template<typename TT> NodeMap(const NodeMap<TT>&) { }
10.537 + ///Assignment operator
10.538 + template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
10.539 + { return *this; }
10.540 + };
10.541 +
10.542 + ///Reference map of the edges to type \c T.
10.543 +
10.544 + /// \ingroup concept
10.545 + ///Reference map of the edges to type \c T.
10.546 + /// \sa Reference
10.547 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
10.548 + /// needs some extra attention!
10.549 + template<class T> class EdgeMap
10.550 + : public ReferenceMap<Edge,T>
10.551 + {
10.552 + public:
10.553 +
10.554 + ///\e
10.555 + EdgeMap(const StaticSymGraph&) { }
10.556 + ///\e
10.557 + EdgeMap(const StaticSymGraph&, T) { }
10.558 +
10.559 + ///Copy constructor
10.560 + template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
10.561 + ///Assignment operator
10.562 + template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
10.563 + { return *this; }
10.564 + };
10.565 +
10.566 + ///Reference map of the edges to type \c T.
10.567 +
10.568 + /// \ingroup concept
10.569 + ///Reference map of the symmetric edges to type \c T.
10.570 + /// \sa Reference
10.571 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
10.572 + /// needs some extra attention!
10.573 + template<class T> class SymEdgeMap
10.574 + : public ReferenceMap<SymEdge,T>
10.575 + {
10.576 + public:
10.577 +
10.578 + ///\e
10.579 + SymEdgeMap(const StaticSymGraph&) { }
10.580 + ///\e
10.581 + SymEdgeMap(const StaticSymGraph&, T) { }
10.582 +
10.583 + ///Copy constructor
10.584 + template<typename TT> SymEdgeMap(const SymEdgeMap<TT>&) { }
10.585 + ///Assignment operator
10.586 + template<typename TT> SymEdgeMap &operator=(const SymEdgeMap<TT>&)
10.587 + { return *this; }
10.588 + };
10.589 + };
10.590 +
10.591 +
10.592 +
10.593 + /// An empty non-static graph class.
10.594 +
10.595 + /// This class provides everything that \ref StaticGraph
10.596 + /// with additional functionality which enables to build a
10.597 + /// graph from scratch.
10.598 + class ExtendableSymGraph : public StaticSymGraph
10.599 + {
10.600 + public:
10.601 + /// Defalult constructor.
10.602 +
10.603 + /// Defalult constructor.
10.604 + ///
10.605 + ExtendableSymGraph() { }
10.606 + ///Add a new node to the graph.
10.607 +
10.608 + /// \return the new node.
10.609 + ///
10.610 + Node addNode() { return INVALID; }
10.611 + ///Add a new edge to the graph.
10.612 +
10.613 + ///Add a new symmetric edge to the graph with tail node \c t
10.614 + ///and head node \c h.
10.615 + ///\return the new edge.
10.616 + SymEdge addEdge(Node h, Node t) { return INVALID; }
10.617 +
10.618 + /// Resets the graph.
10.619 +
10.620 + /// This function deletes all edges and nodes of the graph.
10.621 + /// It also frees the memory allocated to store them.
10.622 + /// \todo It might belong to \ref ErasableGraph.
10.623 + void clear() { }
10.624 + };
10.625 +
10.626 + /// An empty erasable graph class.
10.627 +
10.628 + /// This class is an extension of \ref ExtendableGraph. It also makes it
10.629 + /// possible to erase edges or nodes.
10.630 + class ErasableSymGraph : public ExtendableSymGraph
10.631 + {
10.632 + public:
10.633 + /// Defalult constructor.
10.634 +
10.635 + /// Defalult constructor.
10.636 + ///
10.637 + ErasableSymGraph() { }
10.638 + /// Deletes a node.
10.639 +
10.640 + /// Deletes node \c n node.
10.641 + ///
10.642 + void erase(Node n) { }
10.643 + /// Deletes an edge.
10.644 +
10.645 + /// Deletes edge \c e edge.
10.646 + ///
10.647 + void erase(SymEdge e) { }
10.648 + };
10.649 +
10.650 + // @}
10.651 + } //namespace concept
10.652 +} //namespace lemon
10.653 +
10.654 +
10.655 +
10.656 +#endif // LEMON_CONCEPT_GRAPH_H
11.1 --- a/src/lemon/dijkstra.h Thu Nov 04 18:52:31 2004 +0000
11.2 +++ b/src/lemon/dijkstra.h Thu Nov 04 20:24:59 2004 +0000
11.3 @@ -33,11 +33,11 @@
11.4
11.5 ///This class provides an efficient implementation of %Dijkstra algorithm.
11.6 ///The edge lengths are passed to the algorithm using a
11.7 - ///\ref skeleton::ReadMap "ReadMap",
11.8 + ///\ref concept::ReadMap "ReadMap",
11.9 ///so it is easy to change it to any kind of length.
11.10 ///
11.11 ///The type of the length is determined by the
11.12 - ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map.
11.13 + ///\ref concept::ReadMap::ValueType "ValueType" of the length map.
11.14 ///
11.15 ///It is also possible to change the underlying priority heap.
11.16 ///
11.17 @@ -48,7 +48,7 @@
11.18 ///lengths of the edges. It is read once for each edge, so the map
11.19 ///may involve in relatively time consuming process to compute the edge
11.20 ///length if it is necessary. The default map type is
11.21 - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>"
11.22 + ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>"
11.23 ///\param Heap The heap type used by the %Dijkstra
11.24 ///algorithm. The default
11.25 ///is using \ref BinHeap "binary heap".
12.1 --- a/src/lemon/full_graph.h Thu Nov 04 18:52:31 2004 +0000
12.2 +++ b/src/lemon/full_graph.h Thu Nov 04 20:24:59 2004 +0000
12.3 @@ -194,8 +194,8 @@
12.4 ///It is completely static, so you can neither add nor delete either
12.5 ///edges or nodes.
12.6 ///Thus it conforms to
12.7 - ///the \ref skeleton::StaticGraph "StaticGraph" concept
12.8 - ///\sa skeleton::StaticGraph.
12.9 + ///the \ref concept::StaticGraph "StaticGraph" concept
12.10 + ///\sa concept::StaticGraph.
12.11 ///\todo What about loops?
12.12 ///\todo Don't we need SymEdgeMap?
12.13 ///
13.1 --- a/src/lemon/list_graph.h Thu Nov 04 18:52:31 2004 +0000
13.2 +++ b/src/lemon/list_graph.h Thu Nov 04 20:24:59 2004 +0000
13.3 @@ -317,8 +317,8 @@
13.4 ///This is a simple and fast erasable graph implementation.
13.5 ///
13.6 ///It conforms to the
13.7 - ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
13.8 - ///\sa skeleton::ErasableGraph.
13.9 + ///\ref concept::ErasableGraph "ErasableGraph" concept.
13.10 + ///\sa concept::ErasableGraph.
13.11
13.12 class ListGraph : public ErasableListGraphBase
13.13 {
14.1 --- a/src/lemon/maps.h Thu Nov 04 18:52:31 2004 +0000
14.2 +++ b/src/lemon/maps.h Thu Nov 04 20:24:59 2004 +0000
14.3 @@ -20,7 +20,7 @@
14.4 ///\file
14.5 ///\brief Miscellaneous property maps
14.6 ///
14.7 -///\todo This file has the same name as the concept file in skeletons,
14.8 +///\todo This file has the same name as the concept file in concept/,
14.9 /// and this is not easily detectable in docs...
14.10
14.11 #include <map>
15.1 --- a/src/lemon/path.h Thu Nov 04 18:52:31 2004 +0000
15.2 +++ b/src/lemon/path.h Thu Nov 04 20:24:59 2004 +0000
15.3 @@ -26,7 +26,7 @@
15.4 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
15.5 algorithm to store its result in any kind of path structure.
15.6
15.7 -\sa lemon::skeleton::Path
15.8 +\sa lemon::concept::Path
15.9
15.10 */
15.11
16.1 --- a/src/lemon/skeletons/graph.h Thu Nov 04 18:52:31 2004 +0000
16.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
16.3 @@ -1,918 +0,0 @@
16.4 -/* -*- C++ -*-
16.5 - * src/lemon/skeletons/graph.h - Part of LEMON, a generic C++ optimization library
16.6 - *
16.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
16.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
16.9 - *
16.10 - * Permission to use, modify and distribute this software is granted
16.11 - * provided that this copyright notice appears in all copies. For
16.12 - * precise terms see the accompanying LICENSE file.
16.13 - *
16.14 - * This software is provided "AS IS" with no warranty of any kind,
16.15 - * express or implied, and with no claim as to its suitability for any
16.16 - * purpose.
16.17 - *
16.18 - */
16.19 -
16.20 -#ifndef LEMON_SKELETON_GRAPH_H
16.21 -#define LEMON_SKELETON_GRAPH_H
16.22 -
16.23 -///\ingroup skeletons
16.24 -///\file
16.25 -///\brief Declaration of Graph.
16.26 -
16.27 -#include <lemon/invalid.h>
16.28 -#include <lemon/skeletons/maps.h>
16.29 -#include <lemon/concept_check.h>
16.30 -#include <lemon/skeletons/graph_component.h>
16.31 -
16.32 -namespace lemon {
16.33 - namespace skeleton {
16.34 -
16.35 - /// \addtogroup skeletons
16.36 - /// @{
16.37 -
16.38 -// /// An empty static graph class.
16.39 -
16.40 -// /// This class provides all the common features of a graph structure,
16.41 -// /// however completely without implementations and real data structures
16.42 -// /// behind the interface.
16.43 -// /// All graph algorithms should compile with this class, but it will not
16.44 -// /// run properly, of course.
16.45 -// ///
16.46 -// /// It can be used for checking the interface compatibility,
16.47 -// /// or it can serve as a skeleton of a new graph structure.
16.48 -// ///
16.49 -// /// Also, you will find here the full documentation of a certain graph
16.50 -// /// feature, the documentation of a real graph imlementation
16.51 -// /// like @ref ListGraph or
16.52 -// /// @ref SmartGraph will just refer to this structure.
16.53 -// ///
16.54 -// /// \todo A pages describing the concept of concept description would
16.55 -// /// be nice.
16.56 -// class StaticGraph
16.57 -// {
16.58 -// public:
16.59 -// /// Defalult constructor.
16.60 -
16.61 -// /// Defalult constructor.
16.62 -// ///
16.63 -// StaticGraph() { }
16.64 -// ///Copy consructor.
16.65 -
16.66 -// // ///\todo It is not clear, what we expect from a copy constructor.
16.67 -// // ///E.g. How to assign the nodes/edges to each other? What about maps?
16.68 -// // StaticGraph(const StaticGraph& g) { }
16.69 -
16.70 -// /// The base type of node iterators,
16.71 -// /// or in other words, the trivial node iterator.
16.72 -
16.73 -// /// This is the base type of each node iterator,
16.74 -// /// thus each kind of node iterator converts to this.
16.75 -// /// More precisely each kind of node iterator should be inherited
16.76 -// /// from the trivial node iterator.
16.77 -// class Node {
16.78 -// public:
16.79 -// /// Default constructor
16.80 -
16.81 -// /// @warning The default constructor sets the iterator
16.82 -// /// to an undefined value.
16.83 -// Node() { }
16.84 -// /// Copy constructor.
16.85 -
16.86 -// /// Copy constructor.
16.87 -// ///
16.88 -// Node(const Node&) { }
16.89 -
16.90 -// /// Invalid constructor \& conversion.
16.91 -
16.92 -// /// This constructor initializes the iterator to be invalid.
16.93 -// /// \sa Invalid for more details.
16.94 -// Node(Invalid) { }
16.95 -// /// Equality operator
16.96 -
16.97 -// /// Two iterators are equal if and only if they point to the
16.98 -// /// same object or both are invalid.
16.99 -// bool operator==(Node) const { return true; }
16.100 -
16.101 -// /// Inequality operator
16.102 -
16.103 -// /// \sa operator==(Node n)
16.104 -// ///
16.105 -// bool operator!=(Node) const { return true; }
16.106 -
16.107 -// ///Comparison operator.
16.108 -
16.109 -// ///This is a strict ordering between the nodes.
16.110 -// ///
16.111 -// ///This ordering can be different from the order in which NodeIt
16.112 -// ///goes through the nodes.
16.113 -// ///\todo Possibly we don't need it.
16.114 -// bool operator<(Node) const { return true; }
16.115 -// };
16.116 -
16.117 -// /// This iterator goes through each node.
16.118 -
16.119 -// /// This iterator goes through each node.
16.120 -// /// Its usage is quite simple, for example you can count the number
16.121 -// /// of nodes in graph \c g of type \c Graph like this:
16.122 -// /// \code
16.123 -// /// int count=0;
16.124 -// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
16.125 -// /// \endcode
16.126 -// class NodeIt : public Node {
16.127 -// public:
16.128 -// /// Default constructor
16.129 -
16.130 -// /// @warning The default constructor sets the iterator
16.131 -// /// to an undefined value.
16.132 -// NodeIt() { }
16.133 -// /// Copy constructor.
16.134 -
16.135 -// /// Copy constructor.
16.136 -// ///
16.137 -// NodeIt(const NodeIt&) { }
16.138 -// /// Invalid constructor \& conversion.
16.139 -
16.140 -// /// Initialize the iterator to be invalid.
16.141 -// /// \sa Invalid for more details.
16.142 -// NodeIt(Invalid) { }
16.143 -// /// Sets the iterator to the first node.
16.144 -
16.145 -// /// Sets the iterator to the first node of \c g.
16.146 -// ///
16.147 -// NodeIt(const StaticGraph& g) { }
16.148 -// /// Node -> NodeIt conversion.
16.149 -
16.150 -// /// Sets the iterator to the node of \c g pointed by the trivial
16.151 -// /// iterator n.
16.152 -// /// This feature necessitates that each time we
16.153 -// /// iterate the edge-set, the iteration order is the same.
16.154 -// NodeIt(const StaticGraph& g, const Node& n) { }
16.155 -// /// Next node.
16.156 -
16.157 -// /// Assign the iterator to the next node.
16.158 -// ///
16.159 -// NodeIt& operator++() { return *this; }
16.160 -// };
16.161 -
16.162 -
16.163 -// /// The base type of the edge iterators.
16.164 -
16.165 -// /// The base type of the edge iterators.
16.166 -// ///
16.167 -// class Edge {
16.168 -// public:
16.169 -// /// Default constructor
16.170 -
16.171 -// /// @warning The default constructor sets the iterator
16.172 -// /// to an undefined value.
16.173 -// Edge() { }
16.174 -// /// Copy constructor.
16.175 -
16.176 -// /// Copy constructor.
16.177 -// ///
16.178 -// Edge(const Edge&) { }
16.179 -// /// Initialize the iterator to be invalid.
16.180 -
16.181 -// /// Initialize the iterator to be invalid.
16.182 -// ///
16.183 -// Edge(Invalid) { }
16.184 -// /// Equality operator
16.185 -
16.186 -// /// Two iterators are equal if and only if they point to the
16.187 -// /// same object or both are invalid.
16.188 -// bool operator==(Edge) const { return true; }
16.189 -// /// Inequality operator
16.190 -
16.191 -// /// \sa operator==(Node n)
16.192 -// ///
16.193 -// bool operator!=(Edge) const { return true; }
16.194 -// ///Comparison operator.
16.195 -
16.196 -// ///This is a strict ordering between the nodes.
16.197 -// ///
16.198 -// ///This ordering can be different from the order in which NodeIt
16.199 -// ///goes through the nodes.
16.200 -// ///\todo Possibly we don't need it.
16.201 -// bool operator<(Edge) const { return true; }
16.202 -// };
16.203 -
16.204 -// /// This iterator goes trough the outgoing edges of a node.
16.205 -
16.206 -// /// This iterator goes trough the \e outgoing edges of a certain node
16.207 -// /// of a graph.
16.208 -// /// Its usage is quite simple, for example you can count the number
16.209 -// /// of outgoing edges of a node \c n
16.210 -// /// in graph \c g of type \c Graph as follows.
16.211 -// /// \code
16.212 -// /// int count=0;
16.213 -// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
16.214 -// /// \endcode
16.215 -
16.216 -// class OutEdgeIt : public Edge {
16.217 -// public:
16.218 -// /// Default constructor
16.219 -
16.220 -// /// @warning The default constructor sets the iterator
16.221 -// /// to an undefined value.
16.222 -// OutEdgeIt() { }
16.223 -// /// Copy constructor.
16.224 -
16.225 -// /// Copy constructor.
16.226 -// ///
16.227 -// OutEdgeIt(const OutEdgeIt&) { }
16.228 -// /// Initialize the iterator to be invalid.
16.229 -
16.230 -// /// Initialize the iterator to be invalid.
16.231 -// ///
16.232 -// OutEdgeIt(Invalid) { }
16.233 -// /// This constructor sets the iterator to first outgoing edge.
16.234 -
16.235 -// /// This constructor set the iterator to the first outgoing edge of
16.236 -// /// node
16.237 -// ///@param n the node
16.238 -// ///@param g the graph
16.239 -// OutEdgeIt(const StaticGraph& g, const Node& n) { }
16.240 -// /// Edge -> OutEdgeIt conversion
16.241 -
16.242 -// /// Sets the iterator to the value of the trivial iterator \c e.
16.243 -// /// This feature necessitates that each time we
16.244 -// /// iterate the edge-set, the iteration order is the same.
16.245 -// OutEdgeIt(const StaticGraph& g, const Edge& e) { }
16.246 -// ///Next outgoing edge
16.247 -
16.248 -// /// Assign the iterator to the next
16.249 -// /// outgoing edge of the corresponding node.
16.250 -// OutEdgeIt& operator++() { return *this; }
16.251 -// };
16.252 -
16.253 -// /// This iterator goes trough the incoming edges of a node.
16.254 -
16.255 -// /// This iterator goes trough the \e incoming edges of a certain node
16.256 -// /// of a graph.
16.257 -// /// Its usage is quite simple, for example you can count the number
16.258 -// /// of outgoing edges of a node \c n
16.259 -// /// in graph \c g of type \c Graph as follows.
16.260 -// /// \code
16.261 -// /// int count=0;
16.262 -// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
16.263 -// /// \endcode
16.264 -
16.265 -// class InEdgeIt : public Edge {
16.266 -// public:
16.267 -// /// Default constructor
16.268 -
16.269 -// /// @warning The default constructor sets the iterator
16.270 -// /// to an undefined value.
16.271 -// InEdgeIt() { }
16.272 -// /// Copy constructor.
16.273 -
16.274 -// /// Copy constructor.
16.275 -// ///
16.276 -// InEdgeIt(const InEdgeIt&) { }
16.277 -// /// Initialize the iterator to be invalid.
16.278 -
16.279 -// /// Initialize the iterator to be invalid.
16.280 -// ///
16.281 -// InEdgeIt(Invalid) { }
16.282 -// /// This constructor sets the iterator to first incoming edge.
16.283 -
16.284 -// /// This constructor set the iterator to the first incoming edge of
16.285 -// /// node
16.286 -// ///@param n the node
16.287 -// ///@param g the graph
16.288 -// InEdgeIt(const StaticGraph& g, const Node& n) { }
16.289 -// /// Edge -> InEdgeIt conversion
16.290 -
16.291 -// /// Sets the iterator to the value of the trivial iterator \c e.
16.292 -// /// This feature necessitates that each time we
16.293 -// /// iterate the edge-set, the iteration order is the same.
16.294 -// InEdgeIt(const StaticGraph& g, const Edge& n) { }
16.295 -// /// Next incoming edge
16.296 -
16.297 -// /// Assign the iterator to the next inedge of the corresponding node.
16.298 -// ///
16.299 -// InEdgeIt& operator++() { return *this; }
16.300 -// };
16.301 -// /// This iterator goes through each edge.
16.302 -
16.303 -// /// This iterator goes through each edge of a graph.
16.304 -// /// Its usage is quite simple, for example you can count the number
16.305 -// /// of edges in a graph \c g of type \c Graph as follows:
16.306 -// /// \code
16.307 -// /// int count=0;
16.308 -// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
16.309 -// /// \endcode
16.310 -// class EdgeIt : public Edge {
16.311 -// public:
16.312 -// /// Default constructor
16.313 -
16.314 -// /// @warning The default constructor sets the iterator
16.315 -// /// to an undefined value.
16.316 -// EdgeIt() { }
16.317 -// /// Copy constructor.
16.318 -
16.319 -// /// Copy constructor.
16.320 -// ///
16.321 -// EdgeIt(const EdgeIt&) { }
16.322 -// /// Initialize the iterator to be invalid.
16.323 -
16.324 -// /// Initialize the iterator to be invalid.
16.325 -// ///
16.326 -// EdgeIt(Invalid) { }
16.327 -// /// This constructor sets the iterator to first edge.
16.328 -
16.329 -// /// This constructor set the iterator to the first edge of
16.330 -// /// node
16.331 -// ///@param g the graph
16.332 -// EdgeIt(const StaticGraph& g) { }
16.333 -// /// Edge -> EdgeIt conversion
16.334 -
16.335 -// /// Sets the iterator to the value of the trivial iterator \c e.
16.336 -// /// This feature necessitates that each time we
16.337 -// /// iterate the edge-set, the iteration order is the same.
16.338 -// EdgeIt(const StaticGraph&, const Edge&) { }
16.339 -// ///Next edge
16.340 -
16.341 -// /// Assign the iterator to the next
16.342 -// /// edge of the corresponding node.
16.343 -// EdgeIt& operator++() { return *this; }
16.344 -// };
16.345 -
16.346 -// /// First node of the graph.
16.347 -
16.348 -// /// \retval i the first node.
16.349 -// /// \return the first node.
16.350 -// ///
16.351 -// NodeIt& first(NodeIt& i) const { return i; }
16.352 -
16.353 -// /// The first incoming edge.
16.354 -
16.355 -// /// The first incoming edge.
16.356 -// ///
16.357 -// InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
16.358 -// /// The first outgoing edge.
16.359 -
16.360 -// /// The first outgoing edge.
16.361 -// ///
16.362 -// OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
16.363 -// /// The first edge of the Graph.
16.364 -
16.365 -// /// The first edge of the Graph.
16.366 -// ///
16.367 -// EdgeIt& first(EdgeIt& i) const { return i; }
16.368 -
16.369 -// ///Gives back the head node of an edge.
16.370 -
16.371 -// ///Gives back the head node of an edge.
16.372 -// ///
16.373 -// Node head(Edge) const { return INVALID; }
16.374 -// ///Gives back the tail node of an edge.
16.375 -
16.376 -// ///Gives back the tail node of an edge.
16.377 -// ///
16.378 -// Node tail(Edge) const { return INVALID; }
16.379 -
16.380 -// ///Gives back the \e id of a node.
16.381 -
16.382 -// ///\warning Not all graph structures provide this feature.
16.383 -// ///
16.384 -// ///\todo Should each graph provide \c id?
16.385 -// int id(const Node&) const { return 0; }
16.386 -// ///Gives back the \e id of an edge.
16.387 -
16.388 -// ///\warning Not all graph structures provide this feature.
16.389 -// ///
16.390 -// ///\todo Should each graph provide \c id?
16.391 -// int id(const Edge&) const { return 0; }
16.392 -
16.393 -// ///\e
16.394 -
16.395 -// ///\todo Should it be in the concept?
16.396 -// ///
16.397 -// int nodeNum() const { return 0; }
16.398 -// ///\e
16.399 -
16.400 -// ///\todo Should it be in the concept?
16.401 -// ///
16.402 -// int edgeNum() const { return 0; }
16.403 -
16.404 -
16.405 -// ///Reference map of the nodes to type \c T.
16.406 -
16.407 -// /// \ingroup skeletons
16.408 -// ///Reference map of the nodes to type \c T.
16.409 -// /// \sa Reference
16.410 -// /// \warning Making maps that can handle bool type (NodeMap<bool>)
16.411 -// /// needs some extra attention!
16.412 -// template<class T> class NodeMap : public ReferenceMap< Node, T >
16.413 -// {
16.414 -// public:
16.415 -
16.416 -// ///\e
16.417 -// NodeMap(const StaticGraph&) { }
16.418 -// ///\e
16.419 -// NodeMap(const StaticGraph&, T) { }
16.420 -
16.421 -// ///Copy constructor
16.422 -// template<typename TT> NodeMap(const NodeMap<TT>&) { }
16.423 -// ///Assignment operator
16.424 -// template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
16.425 -// { return *this; }
16.426 -// };
16.427 -
16.428 -// ///Reference map of the edges to type \c T.
16.429 -
16.430 -// /// \ingroup skeletons
16.431 -// ///Reference map of the edges to type \c T.
16.432 -// /// \sa Reference
16.433 -// /// \warning Making maps that can handle bool type (EdgeMap<bool>)
16.434 -// /// needs some extra attention!
16.435 -// template<class T> class EdgeMap
16.436 -// : public ReferenceMap<Edge,T>
16.437 -// {
16.438 -// public:
16.439 -
16.440 -// ///\e
16.441 -// EdgeMap(const StaticGraph&) { }
16.442 -// ///\e
16.443 -// EdgeMap(const StaticGraph&, T) { }
16.444 -
16.445 -// ///Copy constructor
16.446 -// template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
16.447 -// ///Assignment operator
16.448 -// template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
16.449 -// { return *this; }
16.450 -// };
16.451 -// };
16.452 -
16.453 -// struct DummyType {
16.454 -// int value;
16.455 -// DummyType() {}
16.456 -// DummyType(int p) : value(p) {}
16.457 -// DummyType& operator=(int p) { value = p; return *this;}
16.458 -// };
16.459 -
16.460 -// ///\brief Checks whether \c G meets the
16.461 -// ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
16.462 -// template<class Graph> void checkCompileStaticGraph(Graph &G)
16.463 -// {
16.464 -// typedef typename Graph::Node Node;
16.465 -// typedef typename Graph::NodeIt NodeIt;
16.466 -// typedef typename Graph::Edge Edge;
16.467 -// typedef typename Graph::EdgeIt EdgeIt;
16.468 -// typedef typename Graph::InEdgeIt InEdgeIt;
16.469 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
16.470 -
16.471 -// {
16.472 -// Node i; Node j(i); Node k(INVALID);
16.473 -// i=j;
16.474 -// bool b; b=true;
16.475 -// b=(i==INVALID); b=(i!=INVALID);
16.476 -// b=(i==j); b=(i!=j); b=(i<j);
16.477 -// }
16.478 -// {
16.479 -// NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
16.480 -// i=j;
16.481 -// j=G.first(i);
16.482 -// j=++i;
16.483 -// bool b; b=true;
16.484 -// b=(i==INVALID); b=(i!=INVALID);
16.485 -// Node n(i);
16.486 -// n=i;
16.487 -// b=(i==j); b=(i!=j); b=(i<j);
16.488 -// //Node ->NodeIt conversion
16.489 -// NodeIt ni(G,n);
16.490 -// }
16.491 -// {
16.492 -// Edge i; Edge j(i); Edge k(INVALID);
16.493 -// i=j;
16.494 -// bool b; b=true;
16.495 -// b=(i==INVALID); b=(i!=INVALID);
16.496 -// b=(i==j); b=(i!=j); b=(i<j);
16.497 -// }
16.498 -// {
16.499 -// EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
16.500 -// i=j;
16.501 -// j=G.first(i);
16.502 -// j=++i;
16.503 -// bool b; b=true;
16.504 -// b=(i==INVALID); b=(i!=INVALID);
16.505 -// Edge e(i);
16.506 -// e=i;
16.507 -// b=(i==j); b=(i!=j); b=(i<j);
16.508 -// //Edge ->EdgeIt conversion
16.509 -// EdgeIt ei(G,e);
16.510 -// }
16.511 -// {
16.512 -// Node n;
16.513 -// InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
16.514 -// i=j;
16.515 -// j=G.first(i,n);
16.516 -// j=++i;
16.517 -// bool b; b=true;
16.518 -// b=(i==INVALID); b=(i!=INVALID);
16.519 -// Edge e(i);
16.520 -// e=i;
16.521 -// b=(i==j); b=(i!=j); b=(i<j);
16.522 -// //Edge ->InEdgeIt conversion
16.523 -// InEdgeIt ei(G,e);
16.524 -// }
16.525 -// {
16.526 -// Node n;
16.527 -// OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
16.528 -// i=j;
16.529 -// j=G.first(i,n);
16.530 -// j=++i;
16.531 -// bool b; b=true;
16.532 -// b=(i==INVALID); b=(i!=INVALID);
16.533 -// Edge e(i);
16.534 -// e=i;
16.535 -// b=(i==j); b=(i!=j); b=(i<j);
16.536 -// //Edge ->OutEdgeIt conversion
16.537 -// OutEdgeIt ei(G,e);
16.538 -// }
16.539 -// {
16.540 -// Node n,m;
16.541 -// n=m=INVALID;
16.542 -// Edge e;
16.543 -// e=INVALID;
16.544 -// n=G.tail(e);
16.545 -// n=G.head(e);
16.546 -// }
16.547 -// // id tests
16.548 -// { Node n; int i=G.id(n); i=i; }
16.549 -// { Edge e; int i=G.id(e); i=i; }
16.550 -// //NodeMap tests
16.551 -// {
16.552 -// Node k;
16.553 -// typename Graph::template NodeMap<int> m(G);
16.554 -// //Const map
16.555 -// typename Graph::template NodeMap<int> const &cm = m;
16.556 -// //Inicialize with default value
16.557 -// typename Graph::template NodeMap<int> mdef(G,12);
16.558 -// //Copy
16.559 -// typename Graph::template NodeMap<int> mm(cm);
16.560 -// //Copy from another type
16.561 -// typename Graph::template NodeMap<double> dm(cm);
16.562 -// //Copy to more complex type
16.563 -// typename Graph::template NodeMap<DummyType> em(cm);
16.564 -// int v;
16.565 -// v=m[k]; m[k]=v; m.set(k,v);
16.566 -// v=cm[k];
16.567 -
16.568 -// m=cm;
16.569 -// dm=cm; //Copy from another type
16.570 -// em=cm; //Copy to more complex type
16.571 -// {
16.572 -// //Check the typedef's
16.573 -// typename Graph::template NodeMap<int>::ValueType val;
16.574 -// val=1;
16.575 -// typename Graph::template NodeMap<int>::KeyType key;
16.576 -// key = typename Graph::NodeIt(G);
16.577 -// }
16.578 -// }
16.579 -// { //bool NodeMap
16.580 -// Node k;
16.581 -// typename Graph::template NodeMap<bool> m(G);
16.582 -// typename Graph::template NodeMap<bool> const &cm = m; //Const map
16.583 -// //Inicialize with default value
16.584 -// typename Graph::template NodeMap<bool> mdef(G,12);
16.585 -// typename Graph::template NodeMap<bool> mm(cm); //Copy
16.586 -// typename Graph::template NodeMap<int> dm(cm); //Copy from another type
16.587 -// bool v;
16.588 -// v=m[k]; m[k]=v; m.set(k,v);
16.589 -// v=cm[k];
16.590 -
16.591 -// m=cm;
16.592 -// dm=cm; //Copy from another type
16.593 -// m=dm; //Copy to another type
16.594 -
16.595 -// {
16.596 -// //Check the typedef's
16.597 -// typename Graph::template NodeMap<bool>::ValueType val;
16.598 -// val=true;
16.599 -// typename Graph::template NodeMap<bool>::KeyType key;
16.600 -// key= typename Graph::NodeIt(G);
16.601 -// }
16.602 -// }
16.603 -// //EdgeMap tests
16.604 -// {
16.605 -// Edge k;
16.606 -// typename Graph::template EdgeMap<int> m(G);
16.607 -// typename Graph::template EdgeMap<int> const &cm = m; //Const map
16.608 -// //Inicialize with default value
16.609 -// typename Graph::template EdgeMap<int> mdef(G,12);
16.610 -// typename Graph::template EdgeMap<int> mm(cm); //Copy
16.611 -// typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
16.612 -// int v;
16.613 -// v=m[k]; m[k]=v; m.set(k,v);
16.614 -// v=cm[k];
16.615 -
16.616 -// m=cm;
16.617 -// dm=cm; //Copy from another type
16.618 -// {
16.619 -// //Check the typedef's
16.620 -// typename Graph::template EdgeMap<int>::ValueType val;
16.621 -// val=1;
16.622 -// typename Graph::template EdgeMap<int>::KeyType key;
16.623 -// key= typename Graph::EdgeIt(G);
16.624 -// }
16.625 -// }
16.626 -// { //bool EdgeMap
16.627 -// Edge k;
16.628 -// typename Graph::template EdgeMap<bool> m(G);
16.629 -// typename Graph::template EdgeMap<bool> const &cm = m; //Const map
16.630 -// //Inicialize with default value
16.631 -// typename Graph::template EdgeMap<bool> mdef(G,12);
16.632 -// typename Graph::template EdgeMap<bool> mm(cm); //Copy
16.633 -// typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
16.634 -// bool v;
16.635 -// v=m[k]; m[k]=v; m.set(k,v);
16.636 -// v=cm[k];
16.637 -
16.638 -// m=cm;
16.639 -// dm=cm; //Copy from another type
16.640 -// m=dm; //Copy to another type
16.641 -// {
16.642 -// //Check the typedef's
16.643 -// typename Graph::template EdgeMap<bool>::ValueType val;
16.644 -// val=true;
16.645 -// typename Graph::template EdgeMap<bool>::KeyType key;
16.646 -// key= typename Graph::EdgeIt(G);
16.647 -// }
16.648 -// }
16.649 -// }
16.650 -
16.651 -// /// An empty non-static graph class.
16.652 -
16.653 -// /// This class provides everything that \ref StaticGraph
16.654 -// /// with additional functionality which enables to build a
16.655 -// /// graph from scratch.
16.656 -// class ExtendableGraph : public StaticGraph
16.657 -// {
16.658 -// public:
16.659 -// /// Defalult constructor.
16.660 -
16.661 -// /// Defalult constructor.
16.662 -// ///
16.663 -// ExtendableGraph() { }
16.664 -// ///Add a new node to the graph.
16.665 -
16.666 -// /// \return the new node.
16.667 -// ///
16.668 -// Node addNode() { return INVALID; }
16.669 -// ///Add a new edge to the graph.
16.670 -
16.671 -// ///Add a new edge to the graph with tail node \c t
16.672 -// ///and head node \c h.
16.673 -// ///\return the new edge.
16.674 -// Edge addEdge(Node h, Node t) { return INVALID; }
16.675 -
16.676 -// /// Resets the graph.
16.677 -
16.678 -// /// This function deletes all edges and nodes of the graph.
16.679 -// /// It also frees the memory allocated to store them.
16.680 -// /// \todo It might belong to \ref ErasableGraph.
16.681 -// void clear() { }
16.682 -// };
16.683 -
16.684 -
16.685 -// ///\brief Checks whether \c G meets the
16.686 -// ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
16.687 -// template<class Graph> void checkCompileExtendableGraph(Graph &G)
16.688 -// {
16.689 -// checkCompileStaticGraph(G);
16.690 -
16.691 -// typedef typename Graph::Node Node;
16.692 -// typedef typename Graph::NodeIt NodeIt;
16.693 -// typedef typename Graph::Edge Edge;
16.694 -// typedef typename Graph::EdgeIt EdgeIt;
16.695 -// typedef typename Graph::InEdgeIt InEdgeIt;
16.696 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
16.697 -
16.698 -// Node n,m;
16.699 -// n=G.addNode();
16.700 -// m=G.addNode();
16.701 -// Edge e;
16.702 -// e=G.addEdge(n,m);
16.703 -
16.704 -// // G.clear();
16.705 -// }
16.706 -
16.707 -
16.708 -// /// An empty erasable graph class.
16.709 -
16.710 -// /// This class is an extension of \ref ExtendableGraph. It also makes it
16.711 -// /// possible to erase edges or nodes.
16.712 -// class ErasableGraph : public ExtendableGraph
16.713 -// {
16.714 -// public:
16.715 -// /// Defalult constructor.
16.716 -
16.717 -// /// Defalult constructor.
16.718 -// ///
16.719 -// ErasableGraph() { }
16.720 -// /// Deletes a node.
16.721 -
16.722 -// /// Deletes node \c n node.
16.723 -// ///
16.724 -// void erase(Node n) { }
16.725 -// /// Deletes an edge.
16.726 -
16.727 -// /// Deletes edge \c e edge.
16.728 -// ///
16.729 -// void erase(Edge e) { }
16.730 -// };
16.731 -
16.732 -// template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
16.733 -// {
16.734 -// typename Graph::Edge e;
16.735 -// G.erase(e);
16.736 -// }
16.737 -
16.738 -// template<class Graph> void checkCompileGraphEraseNode(Graph &G)
16.739 -// {
16.740 -// typename Graph::Node n;
16.741 -// G.erase(n);
16.742 -// }
16.743 -
16.744 -// ///\brief Checks whether \c G meets the
16.745 -// ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
16.746 -// template<class Graph> void checkCompileErasableGraph(Graph &G)
16.747 -// {
16.748 -// checkCompileExtendableGraph(G);
16.749 -// checkCompileGraphEraseNode(G);
16.750 -// checkCompileGraphEraseEdge(G);
16.751 -// }
16.752 -
16.753 -// ///Checks whether a graph has findEdge() member function.
16.754 -
16.755 -// ///\todo findEdge() might be a global function.
16.756 -// ///
16.757 -// template<class Graph> void checkCompileGraphFindEdge(Graph &G)
16.758 -// {
16.759 -// typedef typename Graph::NodeIt Node;
16.760 -// typedef typename Graph::NodeIt NodeIt;
16.761 -
16.762 -// G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
16.763 -// G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
16.764 -// }
16.765 -
16.766 -
16.767 -
16.768 - /************* New GraphBase stuff **************/
16.769 -
16.770 -
16.771 - /// \bug The nodes and edges are not allowed to inherit from the
16.772 - /// same baseclass.
16.773 -
16.774 - class BaseGraphItem {
16.775 - public:
16.776 - BaseGraphItem() {}
16.777 - BaseGraphItem(Invalid) {}
16.778 -
16.779 - // We explicitely list these:
16.780 - BaseGraphItem(BaseGraphItem const&) {}
16.781 - BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
16.782 -
16.783 - bool operator==(BaseGraphItem) const { return false; }
16.784 - bool operator!=(BaseGraphItem) const { return false; }
16.785 -
16.786 - // Technical requirement. Do we really need this?
16.787 - bool operator<(BaseGraphItem) const { return false; }
16.788 - };
16.789 -
16.790 -
16.791 - /// A minimal GraphBase concept
16.792 -
16.793 - /// This class describes a minimal concept which can be extended to a
16.794 - /// full-featured graph with \ref GraphFactory.
16.795 - class GraphBase {
16.796 - public:
16.797 -
16.798 - GraphBase() {}
16.799 -
16.800 -
16.801 - /// \bug Nodes and Edges are comparable each other
16.802 -
16.803 - class Node : public BaseGraphItem {};
16.804 - class Edge : public BaseGraphItem {};
16.805 -
16.806 - // Graph operation
16.807 - void firstNode(Node &n) const { }
16.808 - void firstEdge(Edge &e) const { }
16.809 -
16.810 - void firstOutEdge(Edge &e, Node) const { }
16.811 - void firstInEdge(Edge &e, Node) const { }
16.812 -
16.813 - void nextNode(Node &n) const { }
16.814 - void nextEdge(Edge &e) const { }
16.815 -
16.816 -
16.817 - // Question: isn't it reasonable if this methods have a Node
16.818 - // parameter? Like this:
16.819 - // Edge& nextOut(Edge &e, Node) const { return e; }
16.820 - void nextOutEdge(Edge &e) const { }
16.821 - void nextInEdge(Edge &e) const { }
16.822 -
16.823 - Node head(Edge) const { return Node(); }
16.824 - Node tail(Edge) const { return Node(); }
16.825 -
16.826 -
16.827 - // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
16.828 - // concept?
16.829 -
16.830 -
16.831 - // Maps.
16.832 - //
16.833 - // We need a special slimer concept which does not provide maps (it
16.834 - // wouldn't be strictly slimer, cause for map-factory id() & friends
16.835 - // a required...)
16.836 -
16.837 - template<typename T>
16.838 - class NodeMap : public GraphMap<Node, T, GraphBase> {};
16.839 -
16.840 - template<typename T>
16.841 - class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
16.842 - };
16.843 -
16.844 -
16.845 -
16.846 - /**************** Concept checking classes ****************/
16.847 -
16.848 - template<typename BGI>
16.849 - struct BaseGraphItemConcept {
16.850 - void constraints() {
16.851 - BGI i1;
16.852 - BGI i2 = i1;
16.853 - BGI i3 = INVALID;
16.854 -
16.855 - i1 = i3;
16.856 - if( i1 == i3 ) {
16.857 - if ( i2 != i3 && i3 < i2 )
16.858 - return;
16.859 - }
16.860 - }
16.861 - };
16.862 -
16.863 -
16.864 -
16.865 - class StaticGraph
16.866 - : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
16.867 - public:
16.868 - typedef BaseGraphComponent::Node Node;
16.869 - typedef BaseGraphComponent::Edge Edge;
16.870 - };
16.871 -
16.872 - template <typename Graph>
16.873 - struct StaticGraphConcept {
16.874 - void constraints() {
16.875 - function_requires<BaseGraphComponentConcept<Graph> >();
16.876 - function_requires<IterableGraphComponentConcept<Graph> >();
16.877 - function_requires<MappableGraphComponentConcept<Graph> >();
16.878 - }
16.879 - Graph& graph;
16.880 - };
16.881 -
16.882 - class ExtendableGraph
16.883 - : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
16.884 - public:
16.885 - typedef BaseGraphComponent::Node Node;
16.886 - typedef BaseGraphComponent::Edge Edge;
16.887 - };
16.888 -
16.889 - template <typename Graph>
16.890 - struct ExtendableGraphConcept {
16.891 - void constraints() {
16.892 - function_requires<StaticGraphConcept<Graph> >();
16.893 - function_requires<ExtendableGraphComponentConcept<Graph> >();
16.894 - function_requires<ClearableGraphComponentConcept<Graph> >();
16.895 - }
16.896 - Graph& graph;
16.897 - };
16.898 -
16.899 - class ErasableGraph
16.900 - : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
16.901 - public:
16.902 - typedef BaseGraphComponent::Node Node;
16.903 - typedef BaseGraphComponent::Edge Edge;
16.904 - };
16.905 -
16.906 - template <typename Graph>
16.907 - struct ErasableGraphConcept {
16.908 - void constraints() {
16.909 - function_requires<ExtendableGraphConcept<Graph> >();
16.910 - function_requires<ErasableGraphComponentConcept<Graph> >();
16.911 - }
16.912 - Graph& graph;
16.913 - };
16.914 -
16.915 - // @}
16.916 - } //namespace skeleton
16.917 -} //namespace lemon
16.918 -
16.919 -
16.920 -
16.921 -#endif // LEMON_SKELETON_GRAPH_H
17.1 --- a/src/lemon/skeletons/graph_component.h Thu Nov 04 18:52:31 2004 +0000
17.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
17.3 @@ -1,827 +0,0 @@
17.4 -/* -*- C++ -*-
17.5 - * src/lemon/skeletons/graph_component.h - Part of LEMON, a generic C++ optimization library
17.6 - *
17.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
17.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
17.9 - *
17.10 - * Permission to use, modify and distribute this software is granted
17.11 - * provided that this copyright notice appears in all copies. For
17.12 - * precise terms see the accompanying LICENSE file.
17.13 - *
17.14 - * This software is provided "AS IS" with no warranty of any kind,
17.15 - * express or implied, and with no claim as to its suitability for any
17.16 - * purpose.
17.17 - *
17.18 - */
17.19 -
17.20 -///\ingroup skeletons
17.21 -///\file
17.22 -///\brief The graph components.
17.23 -
17.24 -
17.25 -#ifndef LEMON_SKELETON_GRAPH_COMPONENT_H
17.26 -#define LEMON_SKELETON_GRAPH_COMPONENT_H
17.27 -
17.28 -#include <lemon/invalid.h>
17.29 -#include <lemon/skeletons/maps.h>
17.30 -
17.31 -namespace lemon {
17.32 - namespace skeleton {
17.33 -
17.34 - /// An empty base graph class.
17.35 -
17.36 - /// This class provides the most minimal features of a graph structure.
17.37 - /// All the graph concepts have to be conform to this base graph.
17.38 -
17.39 - class BaseGraphComponent {
17.40 - public:
17.41 -
17.42 - typedef BaseGraphComponent Graph;
17.43 -
17.44 - /// Node class of the graph.
17.45 -
17.46 - /// This class represents the Nodes of the graph.
17.47 - ///
17.48 - class Node {
17.49 - public:
17.50 -
17.51 - /// Default constructor.
17.52 -
17.53 - /// @warning The default constructor sets the iterator
17.54 - /// to an undefined value.
17.55 -
17.56 - Node() {}
17.57 - /// Copy constructor.
17.58 -
17.59 - /// Copy constructor.
17.60 - ///
17.61 - Node(const Node&) {}
17.62 -
17.63 - /// Invalid constructor \& conversion.
17.64 -
17.65 - /// This constructor initializes the iterator to be invalid.
17.66 - /// \sa Invalid for more details.
17.67 - Node(Invalid) {}
17.68 -
17.69 -
17.70 - Node& operator=(const Node&) { return *this;}
17.71 -
17.72 - /// Equality operator.
17.73 -
17.74 - /// Two iterators are equal if and only if they represents the
17.75 - /// same node in the graph or both are invalid.
17.76 - bool operator==(const Node&) { return true;}
17.77 -
17.78 -
17.79 - /// Inequality operator.
17.80 -
17.81 - /// \sa operator==(const Node& n)
17.82 - ///
17.83 - bool operator!=(const Node&) { return true;}
17.84 -
17.85 - /// Comparison operator.
17.86 -
17.87 - /// This is a strict ordering between the nodes.
17.88 - ///
17.89 - /// This ordering can be different from the iterating order of nodes.
17.90 - /// \todo Possibly we don't need it.
17.91 - bool operator<(const Node&) { return true;}
17.92 - };
17.93 -
17.94 - /// Edge class of the graph.
17.95 -
17.96 - /// This class represents the Edges of the graph.
17.97 - ///
17.98 - class Edge {
17.99 - public:
17.100 -
17.101 - /// Default constructor.
17.102 -
17.103 - /// @warning The default constructor sets the iterator
17.104 - /// to an undefined value.
17.105 -
17.106 - Edge() {}
17.107 - /// Copy constructor.
17.108 -
17.109 - /// Copy constructor.
17.110 - ///
17.111 - Edge(const Edge&) {}
17.112 -
17.113 - /// Invalid constructor \& conversion.
17.114 -
17.115 - /// This constructor initializes the iterator to be invalid.
17.116 - /// \sa Invalid for more details.
17.117 - Edge(Invalid) {}
17.118 -
17.119 -
17.120 - Edge& operator=(const Edge&) { return *this;}
17.121 -
17.122 - /// Equality operator.
17.123 -
17.124 - /// Two iterators are equal if and only if they represents the
17.125 - /// same edge in the graph or both are invalid.
17.126 - bool operator==(const Edge&) { return true;}
17.127 -
17.128 -
17.129 - /// Inequality operator.
17.130 -
17.131 - /// \sa operator==(const Edge& n)
17.132 - ///
17.133 - bool operator!=(const Edge&) { return true;}
17.134 -
17.135 - /// Comparison operator.
17.136 -
17.137 - /// This is a strict ordering between the edges.
17.138 - ///
17.139 - /// This ordering can be different from the iterating order of edges.
17.140 - /// \todo Possibly we don't need it.
17.141 - bool operator<(const Edge&) { return true;}
17.142 - };
17.143 -
17.144 - ///Gives back the head node of an edge.
17.145 -
17.146 - ///Gives back the head node of an edge.
17.147 - ///
17.148 - Node head(const Edge&) const { return INVALID;}
17.149 -
17.150 - ///Gives back the tail node of an edge.
17.151 -
17.152 - ///Gives back the tail node of an edge.
17.153 - ///
17.154 - Node tail(const Edge&) const { return INVALID;}
17.155 - };
17.156 -
17.157 - /// Concept check structure for BaseGraph.
17.158 -
17.159 - /// Concept check structure for BaseGraph.
17.160 - ///
17.161 -
17.162 - template <typename Graph>
17.163 - struct BaseGraphComponentConcept {
17.164 - typedef typename Graph::Node Node;
17.165 - typedef typename Graph::Edge Edge;
17.166 -
17.167 - void constraints() {
17.168 - {
17.169 - Node ni;
17.170 - Node nj(ni);
17.171 - Node nk(INVALID);
17.172 - ni = nj;
17.173 - bool b; b = true;
17.174 - b = (ni == INVALID); b = (ni != INVALID);
17.175 - b = (ni==nj); b = (ni != nj); b=( ni < nj);
17.176 - }
17.177 - {
17.178 - Edge ei;
17.179 - Edge ej(ei);
17.180 - Edge ek(INVALID);
17.181 - ei = ej;
17.182 - bool b; b = true;
17.183 - b = (ei == INVALID); b = (ei != INVALID);
17.184 - b = (ei==ej); b = (ei != ej); b=( ei < ej);
17.185 - }
17.186 - {
17.187 - const Graph& const_graph = graph;
17.188 - Node n;
17.189 - Edge e;
17.190 - n = const_graph.tail(e);
17.191 - n = const_graph.head(e);
17.192 - }
17.193 - }
17.194 -
17.195 - Graph& graph;
17.196 - };
17.197 -
17.198 - /// An empty iterable base graph class.
17.199 -
17.200 - /// This class provides beside the core graph features
17.201 - /// core iterable interface for the graph structure.
17.202 - /// Most of the base graphs should be conform to this concept.
17.203 -
17.204 - class BaseIterableGraphComponent : virtual public BaseGraphComponent {
17.205 - public:
17.206 -
17.207 - typedef BaseGraphComponent::Node Node;
17.208 - typedef BaseGraphComponent::Edge Edge;
17.209 -
17.210 - /// Gives back the first Node in the iterating order.
17.211 -
17.212 - /// Gives back the first Node in the iterating order.
17.213 - ///
17.214 - void first(Node&) const {}
17.215 -
17.216 - /// Gives back the next Node in the iterating order.
17.217 -
17.218 - /// Gives back the next Node in the iterating order.
17.219 - ///
17.220 - void next(Node&) const {}
17.221 -
17.222 - /// Gives back the first Edge in the iterating order.
17.223 -
17.224 - /// Gives back the first Edge in the iterating order.
17.225 - ///
17.226 - void first(Edge&) const {}
17.227 - /// Gives back the next Edge in the iterating order.
17.228 -
17.229 - /// Gives back the next Edge in the iterating order.
17.230 - ///
17.231 - void next(Edge&) const {}
17.232 -
17.233 -
17.234 - /// Gives back the first of the Edges point to the given Node.
17.235 -
17.236 - /// Gives back the first of the Edges point to the given Node.
17.237 - ///
17.238 - void firstIn(Edge&, const Node&) const {}
17.239 -
17.240 - /// Gives back the next of the Edges points to the given Node.
17.241 -
17.242 -
17.243 - /// Gives back the next of the Edges points to the given Node.
17.244 - ///
17.245 - void nextIn(Edge&) const {}
17.246 -
17.247 - /// Gives back the first of the Edges start from the given Node.
17.248 -
17.249 - /// Gives back the first of the Edges start from the given Node.
17.250 - ///
17.251 - void firstOut(Edge&, const Node&) const {}
17.252 -
17.253 - /// Gives back the next of the Edges start from the given Node.
17.254 -
17.255 - /// Gives back the next of the Edges start from the given Node.
17.256 - ///
17.257 - void nextOut(Edge&) const {}
17.258 - };
17.259 -
17.260 -
17.261 - /// Concept check structure for IterableBaseGraph.
17.262 -
17.263 - /// Concept check structure for IterableBaseGraph.
17.264 - ///
17.265 - template <typename Graph>
17.266 - struct BaseIterableGraphComponentConcept {
17.267 -
17.268 - void constraints() {
17.269 - const Graph& const_graph = graph;
17.270 - typename Graph::Node node;
17.271 - typename Graph::Edge edge;
17.272 - {
17.273 - const_graph.first(node);
17.274 - const_graph.next(node);
17.275 - }
17.276 - {
17.277 - const_graph.first(edge);
17.278 - const_graph.next(edge);
17.279 - }
17.280 - {
17.281 - const_graph.firstIn(edge, node);
17.282 - const_graph.nextIn(edge);
17.283 - }
17.284 - {
17.285 - const_graph.firstOut(edge, node);
17.286 - const_graph.nextOut(edge);
17.287 - }
17.288 - }
17.289 -
17.290 - Graph& graph;
17.291 - };
17.292 -
17.293 - /// An empty idable base graph class.
17.294 -
17.295 - /// This class provides beside the core graph features
17.296 - /// core id functions for the graph structure.
17.297 - /// The most of the base graphs should be conform to this concept.
17.298 - /// The id's are unique and immutable.
17.299 -
17.300 - class IDableGraphComponent : virtual public BaseGraphComponent {
17.301 - public:
17.302 -
17.303 - typedef BaseGraphComponent::Node Node;
17.304 - typedef BaseGraphComponent::Edge Edge;
17.305 -
17.306 - /// Gives back an unique integer id for the Node.
17.307 -
17.308 - /// Gives back an unique integer id for the Node.
17.309 - ///
17.310 - int id(const Node&) const { return -1;}
17.311 -
17.312 - /// Gives back an unique integer id for the Edge.
17.313 -
17.314 - /// Gives back an unique integer id for the Edge.
17.315 - ///
17.316 - int id(const Edge&) const { return -1;}
17.317 - };
17.318 -
17.319 -
17.320 - /// Concept check structure for IdableBaseGraph.
17.321 -
17.322 - /// Concept check structure for IdableBaseGraph.
17.323 - ///
17.324 - template <typename Graph>
17.325 - struct IDableGraphComponentConcept {
17.326 -
17.327 - void constraints() {
17.328 - const Graph& const_graph = graph;
17.329 - typename Graph::Node node;
17.330 - int nid = const_graph.id(node);
17.331 - nid = const_graph.id(node);
17.332 - typename Graph::Edge edge;
17.333 - int eid = const_graph.id(edge);
17.334 - eid = const_graph.id(edge);
17.335 - }
17.336 -
17.337 - Graph& graph;
17.338 - };
17.339 -
17.340 -
17.341 - /// An empty max-idable base graph class.
17.342 -
17.343 - /// This class provides beside the core graph features
17.344 - /// core max id functions for the graph structure.
17.345 - /// The most of the base graphs should be conform to this concept.
17.346 - /// The id's are unique and immutable.
17.347 - class MaxIDableGraphComponent : virtual public BaseGraphComponent {
17.348 - public:
17.349 -
17.350 - /// Gives back an integer greater or equal to the maximum Node id.
17.351 -
17.352 - /// Gives back an integer greater or equal to the maximum Node id.
17.353 - ///
17.354 - int maxEdgeId() const { return -1;}
17.355 -
17.356 - /// Gives back an integer greater or equal to the maximum Edge id.
17.357 -
17.358 - /// Gives back an integer greater or equal to the maximum Edge id.
17.359 - ///
17.360 - int maxNodeId() const { return -1;}
17.361 - };
17.362 -
17.363 - /// Concept check structure for MaxIdableBaseGraph.
17.364 -
17.365 - /// Concept check structure for MaxIdableBaseGraph.
17.366 - ///
17.367 - template <typename Graph>
17.368 - struct MaxIDableGraphComponentConcept {
17.369 -
17.370 - void constraints() {
17.371 - const Graph& const_graph = graph;
17.372 - int nid = const_graph.maxEdgeId();
17.373 - ignore_unused_variable_warning(nid);
17.374 - int eid = const_graph.maxNodeId();
17.375 - ignore_unused_variable_warning(eid);
17.376 - }
17.377 -
17.378 - Graph& graph;
17.379 - };
17.380 -
17.381 - /// An empty extendable base graph class.
17.382 -
17.383 - /// This class provides beside the core graph features
17.384 - /// core graph extend interface for the graph structure.
17.385 - /// The most of the base graphs should be conform to this concept.
17.386 - class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
17.387 - public:
17.388 -
17.389 - typedef BaseGraphComponent::Node Node;
17.390 - typedef BaseGraphComponent::Edge Edge;
17.391 -
17.392 - /// Adds a new Node to the graph.
17.393 -
17.394 - /// Adds a new Node to the graph.
17.395 - ///
17.396 - Node addNode() {
17.397 - return INVALID;
17.398 - }
17.399 -
17.400 - /// Adds a new Edge connects the two Nodes to the graph.
17.401 -
17.402 - /// Adds a new Edge connects the two Nodes to the graph.
17.403 - ///
17.404 - Edge addEdge(const Node& from, const Node& to) {
17.405 - return INVALID;
17.406 - }
17.407 -
17.408 - };
17.409 -
17.410 - /// Concept check structure for ExtendableBaseGraph.
17.411 -
17.412 - /// Concept check structure for ExtendableBaseGraph.
17.413 - ///
17.414 - template <typename Graph>
17.415 - struct BaseExtendableGraphComponentConcept {
17.416 - void constraints() {
17.417 - typename Graph::Node node_a, node_b;
17.418 - node_a = graph.addNode();
17.419 - typename Graph::Edge edge;
17.420 - edge = graph.addEdge(node_a, node_b);
17.421 - }
17.422 -
17.423 - Graph& graph;
17.424 - };
17.425 -
17.426 - /// An empty erasable base graph class.
17.427 -
17.428 - /// This class provides beside the core graph features
17.429 - /// core erase functions for the graph structure.
17.430 - /// The most of the base graphs should be conform to this concept.
17.431 - class BaseErasableGraphComponent : virtual public BaseGraphComponent {
17.432 - public:
17.433 -
17.434 - typedef BaseGraphComponent::Node Node;
17.435 - typedef BaseGraphComponent::Edge Edge;
17.436 -
17.437 - /// Erase a Node from the graph.
17.438 -
17.439 - /// Erase a Node from the graph. This function should not
17.440 - /// erase edges connecting to the Node.
17.441 - void erase(const Node&) {}
17.442 -
17.443 - /// Erase an Edge from the graph.
17.444 -
17.445 - /// Erase an Edge from the graph.
17.446 - ///
17.447 - void erase(const Edge&) {}
17.448 -
17.449 - };
17.450 -
17.451 - /// Concept check structure for ErasableBaseGraph.
17.452 -
17.453 - /// Concept check structure for ErasableBaseGraph.
17.454 - ///
17.455 - template <typename Graph>
17.456 - struct BaseErasableGraphComponentConcept {
17.457 - void constraints() {
17.458 - typename Graph::Node node;
17.459 - graph.erase(node);
17.460 - typename Graph::Edge edge;
17.461 - graph.erase(edge);
17.462 - }
17.463 -
17.464 - Graph& graph;
17.465 - };
17.466 -
17.467 - /// An empty clearable base graph class.
17.468 -
17.469 - /// This class provides beside the core graph features
17.470 - /// core clear functions for the graph structure.
17.471 - /// The most of the base graphs should be conform to this concept.
17.472 - class BaseClearableGraphComponent : virtual public BaseGraphComponent {
17.473 - public:
17.474 -
17.475 - /// Erase all the Nodes and Edges from the graph.
17.476 -
17.477 - /// Erase all the Nodes and Edges from the graph.
17.478 - ///
17.479 - void clear() {}
17.480 - };
17.481 -
17.482 - /// Concept check function for ErasableBaseGraph.
17.483 -
17.484 - /// Concept check function for ErasableBaseGraph.
17.485 - ///
17.486 - template <typename Graph>
17.487 - struct BaseClearableGraphComponentConcept {
17.488 - void constraints() {
17.489 - graph.clear();
17.490 - }
17.491 -
17.492 - Graph& graph;
17.493 - };
17.494 -
17.495 -
17.496 - class IterableGraphComponent : virtual public BaseGraphComponent {
17.497 -
17.498 - public:
17.499 -
17.500 - typedef IterableGraphComponent Graph;
17.501 -
17.502 - typedef BaseGraphComponent::Node Node;
17.503 - typedef BaseGraphComponent::Edge Edge;
17.504 -
17.505 - class NodeIt : public Node {
17.506 - public:
17.507 - NodeIt() {}
17.508 - NodeIt(Invalid) {}
17.509 - NodeIt(const Graph&) {}
17.510 -
17.511 - NodeIt& operator++() { return *this; }
17.512 - // Node operator*() const { return INVALID; }
17.513 -
17.514 - bool operator==(const NodeIt&) { return true;}
17.515 - bool operator!=(const NodeIt&) { return true;}
17.516 - };
17.517 -
17.518 - class EdgeIt : public Edge {
17.519 - public:
17.520 - EdgeIt() {}
17.521 - EdgeIt(Invalid) {}
17.522 - EdgeIt(const Graph&) {}
17.523 -
17.524 - EdgeIt& operator++() { return *this; }
17.525 - // Edge operator*() const { return INVALID; }
17.526 -
17.527 - bool operator==(const EdgeIt&) { return true;}
17.528 - bool operator!=(const EdgeIt&) { return true;}
17.529 - };
17.530 -
17.531 - class InEdgeIt : public Edge {
17.532 - public:
17.533 - InEdgeIt() {}
17.534 - InEdgeIt(Invalid) {}
17.535 - InEdgeIt(const Graph&, const Node&) {}
17.536 -
17.537 - InEdgeIt& operator++() { return *this; }
17.538 - // Edge operator*() const { return INVALID; }
17.539 -
17.540 - bool operator==(const InEdgeIt&) { return true;}
17.541 - bool operator!=(const InEdgeIt&) { return true;}
17.542 - };
17.543 -
17.544 - class OutEdgeIt : public Edge {
17.545 - public:
17.546 - OutEdgeIt() {}
17.547 - OutEdgeIt(Invalid) {}
17.548 - OutEdgeIt(const Graph&, const Node&) {}
17.549 -
17.550 - OutEdgeIt& operator++() { return *this; }
17.551 - // Edge operator*() const { return INVALID; }
17.552 -
17.553 - bool operator==(const OutEdgeIt&) { return true;}
17.554 - bool operator!=(const OutEdgeIt&) { return true;}
17.555 - };
17.556 -
17.557 - };
17.558 -
17.559 - template <typename Graph>
17.560 - struct IterableGraphComponentConcept {
17.561 -
17.562 - void constraints() {
17.563 -
17.564 - typedef typename Graph::Node Node;
17.565 - typedef typename Graph::NodeIt NodeIt;
17.566 - typedef typename Graph::Edge Edge;
17.567 - typedef typename Graph::EdgeIt EdgeIt;
17.568 - typedef typename Graph::InEdgeIt InEdgeIt;
17.569 - typedef typename Graph::OutEdgeIt OutEdgeIt;
17.570 -
17.571 - {
17.572 - NodeIt it;
17.573 - NodeIt jt(it);
17.574 - NodeIt kt(INVALID);
17.575 - NodeIt lt(graph);
17.576 - it = jt;
17.577 - jt = ++it;
17.578 - bool b;
17.579 - b = (it == INVALID);
17.580 - b = (it != INVALID);
17.581 - b = (it == jt);
17.582 - b = (it != jt);
17.583 - Node node = it;
17.584 - node = it;
17.585 - }
17.586 - {
17.587 - EdgeIt it;
17.588 - EdgeIt jt(it);
17.589 - EdgeIt kt(INVALID);
17.590 - EdgeIt lt(graph);
17.591 - it = jt;
17.592 - jt = ++it;
17.593 - bool b;
17.594 - b = (it == INVALID);
17.595 - b = (it != INVALID);
17.596 - b = (it == jt);
17.597 - b = (it != jt);
17.598 - Edge edge = it;
17.599 - edge = it;
17.600 - }
17.601 - {
17.602 - InEdgeIt it;
17.603 - InEdgeIt jt(it);
17.604 - InEdgeIt kt(INVALID);
17.605 - Node node;
17.606 - InEdgeIt lt(graph, node);
17.607 - it = jt;
17.608 - jt = ++it;
17.609 - bool b;
17.610 - b = (it == INVALID);
17.611 - b = (it != INVALID);
17.612 - b = (it == jt);
17.613 - b = (it != jt);
17.614 - Edge edge = it;
17.615 - edge = it;
17.616 - }
17.617 - {
17.618 - OutEdgeIt it;
17.619 - OutEdgeIt jt(it);
17.620 - OutEdgeIt kt(INVALID);
17.621 - Node node;
17.622 - OutEdgeIt lt(graph, node);
17.623 - it = jt;
17.624 - jt = ++it;
17.625 - bool b;
17.626 - b = (it == INVALID);
17.627 - b = (it != INVALID);
17.628 - b = (it == jt);
17.629 - b = (it != jt);
17.630 - Edge edge = it;
17.631 - edge = it;
17.632 - }
17.633 - }
17.634 - Graph& graph;
17.635 - };
17.636 -
17.637 -
17.638 - class IdMappableGraphComponent : virtual public BaseGraphComponent {
17.639 -
17.640 - typedef IdMappableGraphComponent Graph;
17.641 -
17.642 - typedef BaseGraphComponent::Node Node;
17.643 - typedef BaseGraphComponent::Edge Edge;
17.644 -
17.645 - public:
17.646 -
17.647 - class NodeIdMap : public ReadMap<Node, int> {
17.648 - public:
17.649 - NodeIdMap(const Graph&) {}
17.650 - int maxId() const { return -1;}
17.651 - };
17.652 -
17.653 - class EdgeIdMap : public ReadMap<Edge, int> {
17.654 - public:
17.655 - EdgeIdMap(const Graph&) {}
17.656 - int maxId() const { return -1;}
17.657 - };
17.658 -
17.659 - };
17.660 -
17.661 - template <typename Graph>
17.662 - struct IdMappableGraphComponentConcept {
17.663 - void constraints() {
17.664 - {
17.665 - typedef typename Graph::EdgeIdMap EdgeIdMap;
17.666 - function_requires<ReadMapConcept<EdgeIdMap> >();
17.667 - EdgeIdMap edge_map(graph);
17.668 - int n = edge_map.maxId();
17.669 - ignore_unused_variable_warning(n);
17.670 - }
17.671 - {
17.672 - typedef typename Graph::NodeIdMap NodeIdMap;
17.673 - function_requires<ReadMapConcept<NodeIdMap> >();
17.674 - NodeIdMap node_map(graph);
17.675 - int n = node_map.maxId();
17.676 - ignore_unused_variable_warning(n);
17.677 - }
17.678 - }
17.679 - Graph& graph;
17.680 - };
17.681 -
17.682 -
17.683 - class MappableGraphComponent : virtual public BaseGraphComponent {
17.684 - public:
17.685 -
17.686 - typedef MappableGraphComponent Graph;
17.687 -
17.688 - typedef BaseGraphComponent::Node Node;
17.689 - typedef BaseGraphComponent::Edge Edge;
17.690 -
17.691 - template <typename Value>
17.692 - class NodeMap : public ReferenceMap<Node, Value> {
17.693 - public:
17.694 - NodeMap(const Graph&) {}
17.695 - NodeMap(const Graph&, const Value&) {}
17.696 - NodeMap(const NodeMap&) {}
17.697 -
17.698 - NodeMap& operator=(const NodeMap&) { return *this;}
17.699 -
17.700 - };
17.701 -
17.702 - template <typename Value>
17.703 - class EdgeMap : public ReferenceMap<Edge, Value> {
17.704 - public:
17.705 - EdgeMap(const Graph&) {}
17.706 - EdgeMap(const Graph&, const Value&) {}
17.707 - EdgeMap(const EdgeMap&) {}
17.708 -
17.709 - EdgeMap& operator=(const EdgeMap&) { return *this;}
17.710 -
17.711 - };
17.712 -
17.713 - };
17.714 -
17.715 - template <typename Graph>
17.716 - struct MappableGraphComponentConcept {
17.717 -
17.718 - struct Type {
17.719 - int value;
17.720 - Type() : value(0) {}
17.721 - Type(int _v) : value(_v) {}
17.722 - };
17.723 -
17.724 - void constraints() {
17.725 - { // int map test
17.726 - typedef typename Graph::template NodeMap<int> IntNodeMap;
17.727 - function_requires<GraphMapConcept<IntNodeMap,Graph> >();
17.728 - } { // bool map test
17.729 - typedef typename Graph::template NodeMap<bool> BoolNodeMap;
17.730 - function_requires<GraphMapConcept<BoolNodeMap,Graph> >();
17.731 - } { // Type map test
17.732 - typedef typename Graph::template NodeMap<Type> TypeNodeMap;
17.733 - function_requires<GraphMapConcept<TypeNodeMap,Graph> >();
17.734 - }
17.735 -
17.736 - { // int map test
17.737 - typedef typename Graph::template EdgeMap<int> IntEdgeMap;
17.738 - function_requires<GraphMapConcept<IntEdgeMap,Graph> >();
17.739 - } { // bool map test
17.740 - typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;
17.741 - function_requires<GraphMapConcept<BoolEdgeMap,Graph> >();
17.742 - } { // Type map test
17.743 - typedef typename Graph::template EdgeMap<Type> TypeEdgeMap;
17.744 - function_requires<GraphMapConcept<TypeEdgeMap,Graph> >();
17.745 - }
17.746 - }
17.747 -
17.748 - Graph& graph;
17.749 - };
17.750 -
17.751 -
17.752 - class ExtendableGraphComponent : virtual public BaseGraphComponent {
17.753 - public:
17.754 -
17.755 - typedef ExtendableGraphComponent Graph;
17.756 -
17.757 - typedef BaseGraphComponent::Node Node;
17.758 - typedef BaseGraphComponent::Edge Edge;
17.759 -
17.760 - Node addNode() {
17.761 - return INVALID;
17.762 - }
17.763 -
17.764 - Edge addEdge(const Node& from, const Node& to) {
17.765 - return INVALID;
17.766 - }
17.767 -
17.768 - };
17.769 -
17.770 - template <typename Graph>
17.771 - struct ExtendableGraphComponentConcept {
17.772 - void constraints() {
17.773 - typename Graph::Node node_a, node_b;
17.774 - node_a = graph.addNode();
17.775 - typename Graph::Edge edge;
17.776 - edge = graph.addEdge(node_a, node_b);
17.777 - }
17.778 - Graph& graph;
17.779 - };
17.780 -
17.781 - class ErasableGraphComponent : virtual public BaseGraphComponent {
17.782 - public:
17.783 -
17.784 - typedef ErasableGraphComponent Graph;
17.785 -
17.786 - typedef BaseGraphComponent::Node Node;
17.787 - typedef BaseGraphComponent::Edge Edge;
17.788 -
17.789 - void erase(const Node&) {}
17.790 - void erase(const Edge&) {}
17.791 -
17.792 - };
17.793 -
17.794 - template <typename Graph>
17.795 - struct ErasableGraphComponentConcept {
17.796 - void constraints() {
17.797 - typename Graph::Node node;
17.798 - graph.erase(node);
17.799 - typename Graph::Edge edge;
17.800 - graph.erase(edge);
17.801 - }
17.802 -
17.803 - Graph& graph;
17.804 - };
17.805 -
17.806 - class ClearableGraphComponent : virtual public BaseGraphComponent {
17.807 - public:
17.808 -
17.809 - typedef ClearableGraphComponent Graph;
17.810 -
17.811 - typedef BaseGraphComponent::Node Node;
17.812 - typedef BaseGraphComponent::Edge Edge;
17.813 -
17.814 - void clear() {}
17.815 -
17.816 - };
17.817 -
17.818 - template <typename Graph>
17.819 - struct ClearableGraphComponentConcept {
17.820 - void constraints() {
17.821 - graph.clear();
17.822 - }
17.823 - Graph& graph;
17.824 - };
17.825 -
17.826 - }
17.827 -
17.828 -}
17.829 -
17.830 -#endif
18.1 --- a/src/lemon/skeletons/maps.h Thu Nov 04 18:52:31 2004 +0000
18.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
18.3 @@ -1,246 +0,0 @@
18.4 -/* -*- C++ -*-
18.5 - * src/lemon/skeletons/maps.h - Part of LEMON, a generic C++ optimization library
18.6 - *
18.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
18.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
18.9 - *
18.10 - * Permission to use, modify and distribute this software is granted
18.11 - * provided that this copyright notice appears in all copies. For
18.12 - * precise terms see the accompanying LICENSE file.
18.13 - *
18.14 - * This software is provided "AS IS" with no warranty of any kind,
18.15 - * express or implied, and with no claim as to its suitability for any
18.16 - * purpose.
18.17 - *
18.18 - */
18.19 -
18.20 -#ifndef LEMON_MAPSKELETON_H
18.21 -#define LEMON_MAPSKELETON_H
18.22 -
18.23 -#include <lemon/concept_check.h>
18.24 -
18.25 -///\ingroup skeletons
18.26 -///\file
18.27 -///\brief Map concepts checking classes for testing and documenting.
18.28 -
18.29 -namespace lemon {
18.30 -
18.31 - namespace skeleton {
18.32 -
18.33 - /// \addtogroup skeletons
18.34 - /// @{
18.35 -
18.36 - /// Readable map concept
18.37 - template<typename K, typename T>
18.38 - class ReadMap
18.39 - {
18.40 - public:
18.41 - /// Map's key type.
18.42 - typedef K KeyType;
18.43 - /// Map's value type. (The type of objects associated with the keys).
18.44 - typedef T ValueType;
18.45 -
18.46 - /// Returns the value associated with a key.
18.47 - ValueType operator[](const KeyType &k) const {return ValueType();}
18.48 -
18.49 - ///Default constructor
18.50 - ReadMap() {}
18.51 - };
18.52 -
18.53 -
18.54 - /// Writable map concept
18.55 - template<typename K, typename T>
18.56 - class WriteMap
18.57 - {
18.58 - public:
18.59 - /// Map's key type.
18.60 - typedef K KeyType;
18.61 - /// Map's value type. (The type of objects associated with the keys).
18.62 - typedef T ValueType;
18.63 -
18.64 - /// Sets the value associated with a key.
18.65 - void set(const KeyType &k,const ValueType &t) {}
18.66 -
18.67 - ///Default constructor
18.68 - WriteMap() {}
18.69 - };
18.70 -
18.71 - ///Read/Writable map concept
18.72 - template<typename K, typename T>
18.73 - class ReadWriteMap : public ReadMap<K,T>,
18.74 - public WriteMap<K,T>
18.75 - {
18.76 - public:
18.77 - /// Map's key type.
18.78 - typedef K KeyType;
18.79 - /// Map's value type. (The type of objects associated with the keys).
18.80 - typedef T ValueType;
18.81 -
18.82 - /// Returns the value associated with a key.
18.83 - ValueType operator[](const KeyType &k) const {return ValueType();}
18.84 - /// Sets the value associated with a key.
18.85 - void set(const KeyType &k,const ValueType &t) {}
18.86 -
18.87 - ///Default constructor
18.88 - ReadWriteMap() {}
18.89 - };
18.90 -
18.91 -
18.92 - ///Dereferable map concept
18.93 - template<typename K, typename T>
18.94 - class ReferenceMap : public ReadWriteMap<K,T>
18.95 - {
18.96 - public:
18.97 - /// Map's key type.
18.98 - typedef K KeyType;
18.99 - /// Map's value type. (The type of objects associated with the keys).
18.100 - typedef T ValueType;
18.101 -
18.102 - protected:
18.103 - ValueType tmp;
18.104 - public:
18.105 - typedef ValueType& ReferenceType;
18.106 - /// Map's const reference type.
18.107 - typedef const ValueType& ConstReferenceType;
18.108 -
18.109 - ///Returns a reference to the value associated to a key.
18.110 - ReferenceType operator[](const KeyType &i) { return tmp; }
18.111 - ///Returns a const reference to the value associated to a key.
18.112 - ConstReferenceType operator[](const KeyType &i) const
18.113 - { return tmp; }
18.114 - /// Sets the value associated with a key.
18.115 - void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
18.116 -
18.117 - ///Default constructor
18.118 - ReferenceMap() {}
18.119 - };
18.120 -
18.121 -
18.122 - template<typename Item, typename T, typename Graph>
18.123 - class GraphMap : public ReadWriteMap<Item, T> {
18.124 - // I really, really don't like the idea that every graph should have
18.125 - // reference maps! --klao
18.126 -
18.127 - private:
18.128 - // We state explicitly that graph maps have no default constructor?
18.129 - GraphMap();
18.130 -
18.131 - public:
18.132 - explicit GraphMap(Graph const&) {}
18.133 - // value for initializing
18.134 - GraphMap(Graph const&, T) {}
18.135 -
18.136 - // this probably should be required:
18.137 - GraphMap(GraphMap const&) {}
18.138 - GraphMap& operator=(GraphMap const&) { return *this; }
18.139 -
18.140 - // but this is a absolute no-op! We should provide a more generic
18.141 - // graph-map-copy operation.
18.142 - //
18.143 - // template<typename TT>
18.144 - // GraphMap(GraphMap<TT> const&);
18.145 - //
18.146 - // template<typename TT>
18.147 - // GraphMap& operator=(const GraphMap<TT>&);
18.148 - };
18.149 -
18.150 -
18.151 - /**************** Concept-checking classes ****************/
18.152 -
18.153 - template<typename ReadMap>
18.154 - struct ReadMapConcept {
18.155 - typedef typename ReadMap::KeyType KeyType;
18.156 - typedef typename ReadMap::ValueType ValueType;
18.157 -
18.158 - void constraints() {
18.159 - // No constraints for constructor.
18.160 -
18.161 - // What are the requirement for the ValueType?
18.162 - // CopyConstructible? Assignable? None of these?
18.163 - ValueType v = m[k];
18.164 - v = m[k];
18.165 -
18.166 - // FIXME:
18.167 - ignore_unused_variable_warning(v);
18.168 - }
18.169 -
18.170 - ReadMap m;
18.171 - KeyType k;
18.172 - };
18.173 -
18.174 - template<typename WriteMap>
18.175 - struct WriteMapConcept {
18.176 - typedef typename WriteMap::KeyType KeyType;
18.177 - typedef typename WriteMap::ValueType ValueType;
18.178 -
18.179 - void constraints() {
18.180 - // No constraints for constructor.
18.181 -
18.182 - m.set(k, v);
18.183 - }
18.184 -
18.185 - WriteMap m;
18.186 - KeyType k;
18.187 - ValueType v;
18.188 - };
18.189 -
18.190 - template<typename ReadWriteMap>
18.191 - struct ReadWriteMapConcept {
18.192 - void constraints() {
18.193 - function_requires< ReadMapConcept<ReadWriteMap> >();
18.194 - function_requires< WriteMapConcept<ReadWriteMap> >();
18.195 - }
18.196 - };
18.197 -
18.198 - template<typename ReferenceMap>
18.199 - struct ReferenceMapConcept {
18.200 - typedef typename ReferenceMap::KeyType KeyType;
18.201 - typedef typename ReferenceMap::ValueType ValueType;
18.202 - typedef typename ReferenceMap::ReferenceType ReferenceType;
18.203 -
18.204 - // What for is this?
18.205 - typedef typename ReferenceMap::ConstReferenceType ConstReferenceType;
18.206 -
18.207 - void constraints() {
18.208 - function_requires< ReadWriteMapConcept<ReferenceMap> >();
18.209 -
18.210 - m[k] = v;
18.211 - // Or should we require real reference?
18.212 - // Like this:
18.213 - // ValueType &vv = m[k];
18.214 - // ignore_unused_variable_warning(vv);
18.215 - }
18.216 -
18.217 - ReferenceMap m;
18.218 - KeyType k;
18.219 - ValueType v;
18.220 - };
18.221 -
18.222 - /// \todo GraphMapConceptCheck
18.223 -
18.224 - template<typename GraphMap, typename Graph>
18.225 - struct GraphMapConcept {
18.226 - void constraints() {
18.227 - function_requires< ReadWriteMapConcept<GraphMap> >();
18.228 - // Construction with a graph parameter
18.229 - GraphMap a(g);
18.230 - // Ctor with a graph and a default value parameter
18.231 - GraphMap a2(g,t);
18.232 - // Copy ctor. Do we need it?
18.233 - GraphMap b=c;
18.234 - // Copy operator. Do we need it?
18.235 - a=b;
18.236 -
18.237 - ignore_unused_variable_warning(a2);
18.238 - }
18.239 - const GraphMap &c;
18.240 - const Graph &g;
18.241 - const typename GraphMap::ValueType &t;
18.242 - };
18.243 -
18.244 -
18.245 - // @}
18.246 -
18.247 - } //namespace skeleton
18.248 -} //namespace lemon
18.249 -#endif // LEMON_MAPSKELETON_H
19.1 --- a/src/lemon/skeletons/path.h Thu Nov 04 18:52:31 2004 +0000
19.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
19.3 @@ -1,236 +0,0 @@
19.4 -/* -*- C++ -*-
19.5 - * src/lemon/skeletons/path.h - Part of LEMON, a generic C++ optimization library
19.6 - *
19.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
19.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
19.9 - *
19.10 - * Permission to use, modify and distribute this software is granted
19.11 - * provided that this copyright notice appears in all copies. For
19.12 - * precise terms see the accompanying LICENSE file.
19.13 - *
19.14 - * This software is provided "AS IS" with no warranty of any kind,
19.15 - * express or implied, and with no claim as to its suitability for any
19.16 - * purpose.
19.17 - *
19.18 - */
19.19 -
19.20 -///\ingroup skeletons
19.21 -///\file
19.22 -///\brief Classes for representing paths in graphs.
19.23 -
19.24 -#ifndef LEMON_SKELETON_PATH_H
19.25 -#define LEMON_SKELETON_PATH_H
19.26 -
19.27 -#include <lemon/invalid.h>
19.28 -
19.29 -namespace lemon {
19.30 - namespace skeleton {
19.31 - /// \addtogroup skeletons
19.32 - /// @{
19.33 -
19.34 -
19.35 - //! \brief A skeletom structure for representing directed paths in a graph.
19.36 - //!
19.37 - //! A skeleton structure for representing directed paths in a graph.
19.38 - //! \param GR The graph type in which the path is.
19.39 - //!
19.40 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
19.41 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
19.42 - //! and \c Edge of the original graph.
19.43 - template<typename GR>
19.44 - class Path {
19.45 - public:
19.46 -
19.47 - /// Type of the underlying graph.
19.48 - typedef /*typename*/ GR Graph;
19.49 - /// Edge type of the underlying graph.
19.50 - typedef typename Graph::Edge GraphEdge;
19.51 - /// Node type of the underlying graph.
19.52 - typedef typename Graph::Node GraphNode;
19.53 - class NodeIt;
19.54 - class EdgeIt;
19.55 -
19.56 - /// \param _G The graph in which the path is.
19.57 - ///
19.58 - Path(const Graph &_G) {}
19.59 -
19.60 - /// Length of the path.
19.61 - size_t length() const {return 0;}
19.62 - /// Returns whether the path is empty.
19.63 - bool empty() const { return true;}
19.64 -
19.65 - /// Resets the path to an empty path.
19.66 - void clear() {}
19.67 -
19.68 - /// \brief Starting point of the path.
19.69 - ///
19.70 - /// Starting point of the path.
19.71 - /// Returns INVALID if the path is empty.
19.72 - GraphNode/*It*/ head() const {return INVALID;}
19.73 - /// \brief End point of the path.
19.74 - ///
19.75 - /// End point of the path.
19.76 - /// Returns INVALID if the path is empty.
19.77 - GraphNode/*It*/ tail() const {return INVALID;}
19.78 -
19.79 - /// \brief First NodeIt/EdgeIt.
19.80 - ///
19.81 - /// Initializes node or edge iterator to point to the first
19.82 - /// node or edge.
19.83 - template<typename It>
19.84 - It& first(It &i) const { return i=It(*this); }
19.85 -
19.86 - /// \brief The head of an edge.
19.87 - ///
19.88 - /// Returns node iterator pointing to the head node of the
19.89 - /// given edge iterator.
19.90 - NodeIt head(const EdgeIt& e) const {return INVALID;}
19.91 -
19.92 - /// \brief The tail of an edge.
19.93 - ///
19.94 - /// Returns node iterator pointing to the tail node of the
19.95 - /// given edge iterator.
19.96 - NodeIt tail(const EdgeIt& e) const {return INVALID;}
19.97 -
19.98 -
19.99 - /* Iterator classes */
19.100 -
19.101 - /**
19.102 - * \brief Iterator class to iterate on the edges of the paths
19.103 - *
19.104 - * \ingroup skeletons
19.105 - * This class is used to iterate on the edges of the paths
19.106 - *
19.107 - * Of course it converts to Graph::Edge
19.108 - *
19.109 - */
19.110 - class EdgeIt {
19.111 - public:
19.112 - /// Default constructor
19.113 - EdgeIt() {}
19.114 - /// Invalid constructor
19.115 - EdgeIt(Invalid) {}
19.116 - /// Constructor with starting point
19.117 - EdgeIt(const Path &_p) {}
19.118 -
19.119 - operator GraphEdge () const {}
19.120 -
19.121 - /// Next edge
19.122 - EdgeIt& operator++() {return *this;}
19.123 -
19.124 - /// Comparison operator
19.125 - bool operator==(const EdgeIt& e) const {return true;}
19.126 - /// Comparison operator
19.127 - bool operator!=(const EdgeIt& e) const {return true;}
19.128 -// /// Comparison operator
19.129 -// /// \todo It is not clear what is the "natural" ordering.
19.130 -// bool operator<(const EdgeIt& e) const {}
19.131 -
19.132 - };
19.133 -
19.134 - /**
19.135 - * \brief Iterator class to iterate on the nodes of the paths
19.136 - *
19.137 - * \ingroup skeletons
19.138 - * This class is used to iterate on the nodes of the paths
19.139 - *
19.140 - * Of course it converts to Graph::Node.
19.141 - *
19.142 - */
19.143 - class NodeIt {
19.144 - public:
19.145 - /// Default constructor
19.146 - NodeIt() {}
19.147 - /// Invalid constructor
19.148 - NodeIt(Invalid) {}
19.149 - /// Constructor with starting point
19.150 - NodeIt(const Path &_p) {}
19.151 -
19.152 - ///Conversion to Graph::Node
19.153 - operator const GraphNode& () const {}
19.154 - /// Next node
19.155 - NodeIt& operator++() {return *this;}
19.156 -
19.157 - /// Comparison operator
19.158 - bool operator==(const NodeIt& e) const {return true;}
19.159 - /// Comparison operator
19.160 - bool operator!=(const NodeIt& e) const {return true;}
19.161 -// /// Comparison operator
19.162 -// /// \todo It is not clear what is the "natural" ordering.
19.163 -// bool operator<(const NodeIt& e) const {}
19.164 -
19.165 - };
19.166 -
19.167 - friend class Builder;
19.168 -
19.169 - /**
19.170 - * \brief Class to build paths
19.171 - *
19.172 - * \ingroup skeletons
19.173 - * This class is used to fill a path with edges.
19.174 - *
19.175 - * You can push new edges to the front and to the back of the path in
19.176 - * arbitrary order then you should commit these changes to the graph.
19.177 - *
19.178 - * While the builder is active (after the first modifying
19.179 - * operation and until the call of \ref commit())
19.180 - * the underlining Path is in a
19.181 - * "transitional" state (operations on it have undefined result).
19.182 - */
19.183 - class Builder {
19.184 - public:
19.185 -
19.186 - Path &P;
19.187 -
19.188 - ///\param _P the path you want to fill in.
19.189 - ///
19.190 - Builder(Path &_P) : P(_P) {}
19.191 -
19.192 - /// Sets the starting node of the path.
19.193 -
19.194 - /// Sets the starting node of the path. Edge added to the path
19.195 - /// afterwards have to be incident to this node.
19.196 - /// You \em must start building an empry path with this functions.
19.197 - /// (And you \em must \em not use it later).
19.198 - /// \sa pushFront()
19.199 - /// \sa pushBack()
19.200 - void setStartNode(const GraphNode &) {}
19.201 -
19.202 - ///Push a new edge to the front of the path
19.203 -
19.204 - ///Push a new edge to the front of the path.
19.205 - ///If the path is empty, you \em must call \ref setStartNode() before
19.206 - ///the first use of \ref pushFront().
19.207 - void pushFront(const GraphEdge& e) {}
19.208 -
19.209 - ///Push a new edge to the back of the path
19.210 -
19.211 - ///Push a new edge to the back of the path.
19.212 - ///If the path is empty, you \em must call \ref setStartNode() before
19.213 - ///the first use of \ref pushBack().
19.214 - void pushBack(const GraphEdge& e) {}
19.215 -
19.216 - ///Commit the changes to the path.
19.217 - void commit() {}
19.218 -
19.219 - ///Reserve (front) storage for the builder in advance.
19.220 -
19.221 - ///If you know an reasonable upper bound of the number of the edges
19.222 - ///to add to the front of the path,
19.223 - ///using this function you may speed up the building.
19.224 - void reserveFront(size_t r) {}
19.225 - ///Reserve (back) storage for the builder in advance.
19.226 -
19.227 - ///If you know an reasonable upper bound of the number of the edges
19.228 - ///to add to the back of the path,
19.229 - ///using this function you may speed up the building.
19.230 - void reserveBack(size_t r) {}
19.231 - };
19.232 - };
19.233 -
19.234 - ///@}
19.235 - }
19.236 -
19.237 -} // namespace lemon
19.238 -
19.239 -#endif // LEMON_SKELETON_PATH_H
20.1 --- a/src/lemon/skeletons/sym_graph.h Thu Nov 04 18:52:31 2004 +0000
20.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
20.3 @@ -1,653 +0,0 @@
20.4 -/* -*- C++ -*-
20.5 - * src/lemon/skeletons/graph.h - Part of LEMON, a generic C++ optimization library
20.6 - *
20.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
20.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
20.9 - *
20.10 - * Permission to use, modify and distribute this software is granted
20.11 - * provided that this copyright notice appears in all copies. For
20.12 - * precise terms see the accompanying LICENSE file.
20.13 - *
20.14 - * This software is provided "AS IS" with no warranty of any kind,
20.15 - * express or implied, and with no claim as to its suitability for any
20.16 - * purpose.
20.17 - *
20.18 - */
20.19 -
20.20 -#ifndef LEMON_SKELETON_SYM_GRAPH_H
20.21 -#define LEMON_SKELETON_SYM_GRAPH_H
20.22 -
20.23 -///\ingroup skeletons
20.24 -///\file
20.25 -///\brief Declaration of SymGraph.
20.26 -
20.27 -#include <lemon/invalid.h>
20.28 -#include <lemon/skeletons/graph.h>
20.29 -#include <lemon/skeletons/maps.h>
20.30 -
20.31 -namespace lemon {
20.32 - namespace skeleton {
20.33 -
20.34 - /// \addtogroup skeletons
20.35 - /// @{
20.36 -
20.37 - /// An empty static graph class.
20.38 -
20.39 - /// This class provides all the common features of a symmetric
20.40 - /// graph structure, however completely without implementations and
20.41 - /// real data structures behind the interface.
20.42 - /// All graph algorithms should compile with this class, but it will not
20.43 - /// run properly, of course.
20.44 - ///
20.45 - /// It can be used for checking the interface compatibility,
20.46 - /// or it can serve as a skeleton of a new symmetric graph structure.
20.47 - ///
20.48 - /// Also, you will find here the full documentation of a certain graph
20.49 - /// feature, the documentation of a real symmetric graph imlementation
20.50 - /// like @ref SymListGraph or
20.51 - /// @ref lemon::SymSmartGraph will just refer to this structure.
20.52 - class StaticSymGraph
20.53 - {
20.54 - public:
20.55 - /// Defalult constructor.
20.56 -
20.57 - /// Defalult constructor.
20.58 - ///
20.59 - StaticSymGraph() { }
20.60 - ///Copy consructor.
20.61 -
20.62 -// ///\todo It is not clear, what we expect from a copy constructor.
20.63 -// ///E.g. How to assign the nodes/edges to each other? What about maps?
20.64 -// StaticGraph(const StaticGraph& g) { }
20.65 -
20.66 - /// The base type of node iterators,
20.67 - /// or in other words, the trivial node iterator.
20.68 -
20.69 - /// This is the base type of each node iterator,
20.70 - /// thus each kind of node iterator converts to this.
20.71 - /// More precisely each kind of node iterator should be inherited
20.72 - /// from the trivial node iterator.
20.73 - class Node {
20.74 - public:
20.75 - /// Default constructor
20.76 -
20.77 - /// @warning The default constructor sets the iterator
20.78 - /// to an undefined value.
20.79 - Node() { }
20.80 - /// Copy constructor.
20.81 -
20.82 - /// Copy constructor.
20.83 - ///
20.84 - Node(const Node&) { }
20.85 -
20.86 - /// Invalid constructor \& conversion.
20.87 -
20.88 - /// This constructor initializes the iterator to be invalid.
20.89 - /// \sa Invalid for more details.
20.90 - Node(Invalid) { }
20.91 - /// Equality operator
20.92 -
20.93 - /// Two iterators are equal if and only if they point to the
20.94 - /// same object or both are invalid.
20.95 - bool operator==(Node) const { return true; }
20.96 -
20.97 - /// Inequality operator
20.98 -
20.99 - /// \sa operator==(Node n)
20.100 - ///
20.101 - bool operator!=(Node) const { return true; }
20.102 -
20.103 - ///Comparison operator.
20.104 -
20.105 - ///This is a strict ordering between the nodes.
20.106 - ///
20.107 - ///This ordering can be different from the order in which NodeIt
20.108 - ///goes through the nodes.
20.109 - ///\todo Possibly we don't need it.
20.110 - bool operator<(Node) const { return true; }
20.111 - };
20.112 -
20.113 - /// This iterator goes through each node.
20.114 -
20.115 - /// This iterator goes through each node.
20.116 - /// Its usage is quite simple, for example you can count the number
20.117 - /// of nodes in graph \c g of type \c Graph like this:
20.118 - /// \code
20.119 - /// int count=0;
20.120 - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
20.121 - /// \endcode
20.122 - class NodeIt : public Node {
20.123 - public:
20.124 - /// Default constructor
20.125 -
20.126 - /// @warning The default constructor sets the iterator
20.127 - /// to an undefined value.
20.128 - NodeIt() { }
20.129 - /// Copy constructor.
20.130 -
20.131 - /// Copy constructor.
20.132 - ///
20.133 - NodeIt(const NodeIt&) { }
20.134 - /// Invalid constructor \& conversion.
20.135 -
20.136 - /// Initialize the iterator to be invalid.
20.137 - /// \sa Invalid for more details.
20.138 - NodeIt(Invalid) { }
20.139 - /// Sets the iterator to the first node.
20.140 -
20.141 - /// Sets the iterator to the first node of \c g.
20.142 - ///
20.143 - NodeIt(const StaticSymGraph& g) { }
20.144 - /// Node -> NodeIt conversion.
20.145 -
20.146 - /// Sets the iterator to the node of \c g pointed by the trivial
20.147 - /// iterator n.
20.148 - /// This feature necessitates that each time we
20.149 - /// iterate the edge-set, the iteration order is the same.
20.150 - NodeIt(const StaticSymGraph& g, const Node& n) { }
20.151 - /// Next node.
20.152 -
20.153 - /// Assign the iterator to the next node.
20.154 - ///
20.155 - NodeIt& operator++() { return *this; }
20.156 - };
20.157 -
20.158 -
20.159 - /// The base type of the symmetric edge iterators.
20.160 -
20.161 - /// The base type of the symmetric edge iterators.
20.162 - ///
20.163 - class SymEdge {
20.164 - public:
20.165 - /// Default constructor
20.166 -
20.167 - /// @warning The default constructor sets the iterator
20.168 - /// to an undefined value.
20.169 - SymEdge() { }
20.170 - /// Copy constructor.
20.171 -
20.172 - /// Copy constructor.
20.173 - ///
20.174 - SymEdge(const SymEdge&) { }
20.175 - /// Initialize the iterator to be invalid.
20.176 -
20.177 - /// Initialize the iterator to be invalid.
20.178 - ///
20.179 - SymEdge(Invalid) { }
20.180 - /// Equality operator
20.181 -
20.182 - /// Two iterators are equal if and only if they point to the
20.183 - /// same object or both are invalid.
20.184 - bool operator==(SymEdge) const { return true; }
20.185 - /// Inequality operator
20.186 -
20.187 - /// \sa operator==(Node n)
20.188 - ///
20.189 - bool operator!=(SymEdge) const { return true; }
20.190 - ///Comparison operator.
20.191 -
20.192 - ///This is a strict ordering between the nodes.
20.193 - ///
20.194 - ///This ordering can be different from the order in which NodeIt
20.195 - ///goes through the nodes.
20.196 - ///\todo Possibly we don't need it.
20.197 - bool operator<(SymEdge) const { return true; }
20.198 - };
20.199 -
20.200 -
20.201 - /// The base type of the edge iterators.
20.202 -
20.203 - /// The base type of the edge iterators.
20.204 - ///
20.205 - class Edge : public SymEdge {
20.206 - public:
20.207 - /// Default constructor
20.208 -
20.209 - /// @warning The default constructor sets the iterator
20.210 - /// to an undefined value.
20.211 - Edge() { }
20.212 - /// Copy constructor.
20.213 -
20.214 - /// Copy constructor.
20.215 - ///
20.216 - Edge(const Edge&) { }
20.217 - /// Initialize the iterator to be invalid.
20.218 -
20.219 - /// Initialize the iterator to be invalid.
20.220 - ///
20.221 - Edge(Invalid) { }
20.222 - /// Equality operator
20.223 -
20.224 - /// Two iterators are equal if and only if they point to the
20.225 - /// same object or both are invalid.
20.226 - bool operator==(Edge) const { return true; }
20.227 - /// Inequality operator
20.228 -
20.229 - /// \sa operator==(Node n)
20.230 - ///
20.231 - bool operator!=(Edge) const { return true; }
20.232 - ///Comparison operator.
20.233 -
20.234 - ///This is a strict ordering between the nodes.
20.235 - ///
20.236 - ///This ordering can be different from the order in which NodeIt
20.237 - ///goes through the nodes.
20.238 - ///\todo Possibly we don't need it.
20.239 - bool operator<(Edge) const { return true; }
20.240 - };
20.241 -
20.242 - /// This iterator goes trough the outgoing edges of a node.
20.243 -
20.244 - /// This iterator goes trough the \e outgoing edges of a certain node
20.245 - /// of a graph.
20.246 - /// Its usage is quite simple, for example you can count the number
20.247 - /// of outgoing edges of a node \c n
20.248 - /// in graph \c g of type \c Graph as follows.
20.249 - /// \code
20.250 - /// int count=0;
20.251 - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
20.252 - /// \endcode
20.253 -
20.254 - class OutEdgeIt : public Edge {
20.255 - public:
20.256 - /// Default constructor
20.257 -
20.258 - /// @warning The default constructor sets the iterator
20.259 - /// to an undefined value.
20.260 - OutEdgeIt() { }
20.261 - /// Copy constructor.
20.262 -
20.263 - /// Copy constructor.
20.264 - ///
20.265 - OutEdgeIt(const OutEdgeIt&) { }
20.266 - /// Initialize the iterator to be invalid.
20.267 -
20.268 - /// Initialize the iterator to be invalid.
20.269 - ///
20.270 - OutEdgeIt(Invalid) { }
20.271 - /// This constructor sets the iterator to first outgoing edge.
20.272 -
20.273 - /// This constructor set the iterator to the first outgoing edge of
20.274 - /// node
20.275 - ///@param n the node
20.276 - ///@param g the graph
20.277 - OutEdgeIt(const StaticSymGraph& g, const Node& n) { }
20.278 - /// Edge -> OutEdgeIt conversion
20.279 -
20.280 - /// Sets the iterator to the value of the trivial iterator \c e.
20.281 - /// This feature necessitates that each time we
20.282 - /// iterate the edge-set, the iteration order is the same.
20.283 - OutEdgeIt(const StaticSymGraph& g, const Edge& e) { }
20.284 - ///Next outgoing edge
20.285 -
20.286 - /// Assign the iterator to the next
20.287 - /// outgoing edge of the corresponding node.
20.288 - OutEdgeIt& operator++() { return *this; }
20.289 - };
20.290 -
20.291 - /// This iterator goes trough the incoming edges of a node.
20.292 -
20.293 - /// This iterator goes trough the \e incoming edges of a certain node
20.294 - /// of a graph.
20.295 - /// Its usage is quite simple, for example you can count the number
20.296 - /// of outgoing edges of a node \c n
20.297 - /// in graph \c g of type \c Graph as follows.
20.298 - /// \code
20.299 - /// int count=0;
20.300 - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
20.301 - /// \endcode
20.302 -
20.303 - class InEdgeIt : public Edge {
20.304 - public:
20.305 - /// Default constructor
20.306 -
20.307 - /// @warning The default constructor sets the iterator
20.308 - /// to an undefined value.
20.309 - InEdgeIt() { }
20.310 - /// Copy constructor.
20.311 -
20.312 - /// Copy constructor.
20.313 - ///
20.314 - InEdgeIt(const InEdgeIt&) { }
20.315 - /// Initialize the iterator to be invalid.
20.316 -
20.317 - /// Initialize the iterator to be invalid.
20.318 - ///
20.319 - InEdgeIt(Invalid) { }
20.320 - /// This constructor sets the iterator to first incoming edge.
20.321 -
20.322 - /// This constructor set the iterator to the first incoming edge of
20.323 - /// node
20.324 - ///@param n the node
20.325 - ///@param g the graph
20.326 - InEdgeIt(const StaticSymGraph& g, const Node& n) { }
20.327 - /// Edge -> InEdgeIt conversion
20.328 -
20.329 - /// Sets the iterator to the value of the trivial iterator \c e.
20.330 - /// This feature necessitates that each time we
20.331 - /// iterate the edge-set, the iteration order is the same.
20.332 - InEdgeIt(const StaticSymGraph& g, const Edge& n) { }
20.333 - /// Next incoming edge
20.334 -
20.335 - /// Assign the iterator to the next inedge of the corresponding node.
20.336 - ///
20.337 - InEdgeIt& operator++() { return *this; }
20.338 - };
20.339 - /// This iterator goes through each symmetric edge.
20.340 -
20.341 - /// This iterator goes through each symmetric edge of a graph.
20.342 - /// Its usage is quite simple, for example you can count the number
20.343 - /// of symmetric edges in a graph \c g of type \c Graph as follows:
20.344 - /// \code
20.345 - /// int count=0;
20.346 - /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count;
20.347 - /// \endcode
20.348 - class SymEdgeIt : public SymEdge {
20.349 - public:
20.350 - /// Default constructor
20.351 -
20.352 - /// @warning The default constructor sets the iterator
20.353 - /// to an undefined value.
20.354 - SymEdgeIt() { }
20.355 - /// Copy constructor.
20.356 -
20.357 - /// Copy constructor.
20.358 - ///
20.359 - SymEdgeIt(const SymEdgeIt&) { }
20.360 - /// Initialize the iterator to be invalid.
20.361 -
20.362 - /// Initialize the iterator to be invalid.
20.363 - ///
20.364 - SymEdgeIt(Invalid) { }
20.365 - /// This constructor sets the iterator to first edge.
20.366 -
20.367 - /// This constructor set the iterator to the first edge of
20.368 - /// node
20.369 - ///@param g the graph
20.370 - SymEdgeIt(const StaticSymGraph& g) { }
20.371 - /// Edge -> EdgeIt conversion
20.372 -
20.373 - /// Sets the iterator to the value of the trivial iterator \c e.
20.374 - /// This feature necessitates that each time we
20.375 - /// iterate the edge-set, the iteration order is the same.
20.376 - SymEdgeIt(const StaticSymGraph&, const SymEdge&) { }
20.377 - ///Next edge
20.378 -
20.379 - /// Assign the iterator to the next
20.380 - /// edge of the corresponding node.
20.381 - SymEdgeIt& operator++() { return *this; }
20.382 - };
20.383 - /// This iterator goes through each edge.
20.384 -
20.385 - /// This iterator goes through each edge of a graph.
20.386 - /// Its usage is quite simple, for example you can count the number
20.387 - /// of edges in a graph \c g of type \c Graph as follows:
20.388 - /// \code
20.389 - /// int count=0;
20.390 - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
20.391 - /// \endcode
20.392 - class EdgeIt : public Edge {
20.393 - public:
20.394 - /// Default constructor
20.395 -
20.396 - /// @warning The default constructor sets the iterator
20.397 - /// to an undefined value.
20.398 - EdgeIt() { }
20.399 - /// Copy constructor.
20.400 -
20.401 - /// Copy constructor.
20.402 - ///
20.403 - EdgeIt(const EdgeIt&) { }
20.404 - /// Initialize the iterator to be invalid.
20.405 -
20.406 - /// Initialize the iterator to be invalid.
20.407 - ///
20.408 - EdgeIt(Invalid) { }
20.409 - /// This constructor sets the iterator to first edge.
20.410 -
20.411 - /// This constructor set the iterator to the first edge of
20.412 - /// node
20.413 - ///@param g the graph
20.414 - EdgeIt(const StaticSymGraph& g) { }
20.415 - /// Edge -> EdgeIt conversion
20.416 -
20.417 - /// Sets the iterator to the value of the trivial iterator \c e.
20.418 - /// This feature necessitates that each time we
20.419 - /// iterate the edge-set, the iteration order is the same.
20.420 - EdgeIt(const StaticSymGraph&, const Edge&) { }
20.421 - ///Next edge
20.422 -
20.423 - /// Assign the iterator to the next
20.424 - /// edge of the corresponding node.
20.425 - EdgeIt& operator++() { return *this; }
20.426 - };
20.427 -
20.428 - /// First node of the graph.
20.429 -
20.430 - /// \retval i the first node.
20.431 - /// \return the first node.
20.432 - ///
20.433 - NodeIt& first(NodeIt& i) const { return i; }
20.434 -
20.435 - /// The first incoming edge.
20.436 -
20.437 - /// The first incoming edge.
20.438 - ///
20.439 - InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
20.440 - /// The first outgoing edge.
20.441 -
20.442 - /// The first outgoing edge.
20.443 - ///
20.444 - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
20.445 - /// The first edge of the Graph.
20.446 -
20.447 - /// The first edge of the Graph.
20.448 - ///
20.449 - EdgeIt& first(EdgeIt& i) const { return i; }
20.450 - /// The first symmetric edge of the Graph.
20.451 -
20.452 - /// The first symmetric edge of the Graph.
20.453 - ///
20.454 - SymEdgeIt& first(SymEdgeIt& i) const { return i; }
20.455 -
20.456 - ///Gives back the head node of an edge.
20.457 -
20.458 - ///Gives back the head node of an edge.
20.459 - ///
20.460 - Node head(Edge) const { return INVALID; }
20.461 - ///Gives back the tail node of an edge.
20.462 -
20.463 - ///Gives back the tail node of an edge.
20.464 - ///
20.465 - Node tail(Edge) const { return INVALID; }
20.466 -
20.467 - ///Gives back the first node of an symmetric edge.
20.468 -
20.469 - ///Gives back the first node of an symmetric edge.
20.470 - ///
20.471 - Node head(SymEdge) const { return INVALID; }
20.472 - ///Gives back the second node of an symmetric edge.
20.473 -
20.474 - ///Gives back the second node of an symmetric edge.
20.475 - ///
20.476 - Node tail(SymEdge) const { return INVALID; }
20.477 - ///Gives back the \e id of a node.
20.478 -
20.479 - ///\warning Not all graph structures provide this feature.
20.480 - ///
20.481 - ///\todo Should each graph provide \c id?
20.482 - int id(const Node&) const { return 0; }
20.483 - ///Gives back the \e id of an edge.
20.484 -
20.485 - ///\warning Not all graph structures provide this feature.
20.486 - ///
20.487 - ///\todo Should each graph provide \c id?
20.488 - int id(const Edge&) const { return 0; }
20.489 -
20.490 - ///\warning Not all graph structures provide this feature.
20.491 - ///
20.492 - ///\todo Should each graph provide \c id?
20.493 - int id(const SymEdge&) const { return 0; }
20.494 -
20.495 - ///\e
20.496 -
20.497 - ///\todo Should it be in the concept?
20.498 - ///
20.499 - int nodeNum() const { return 0; }
20.500 - ///\e
20.501 -
20.502 - ///\todo Should it be in the concept?
20.503 - ///
20.504 - int edgeNum() const { return 0; }
20.505 -
20.506 - ///\todo Should it be in the concept?
20.507 - ///
20.508 - int symEdgeNum() const { return 0; }
20.509 -
20.510 -
20.511 - /// Gives back the forward directed edge of the symmetric edge.
20.512 - Edge forward(SymEdge) const {return INVALID;}
20.513 -
20.514 - /// Gives back the backward directed edge of the symmetric edge.
20.515 - Edge backward(SymEdge) const {return INVALID;};
20.516 -
20.517 - /// Gives back the opposite of the edge.
20.518 - Edge opposite(Edge) const {return INVALID;}
20.519 -
20.520 - ///Reference map of the nodes to type \c T.
20.521 - /// \ingroup skeletons
20.522 - ///Reference map of the nodes to type \c T.
20.523 - /// \sa Reference
20.524 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
20.525 - /// needs some extra attention!
20.526 - template<class T> class NodeMap : public ReferenceMap< Node, T >
20.527 - {
20.528 - public:
20.529 -
20.530 - ///\e
20.531 - NodeMap(const StaticSymGraph&) { }
20.532 - ///\e
20.533 - NodeMap(const StaticSymGraph&, T) { }
20.534 -
20.535 - ///Copy constructor
20.536 - template<typename TT> NodeMap(const NodeMap<TT>&) { }
20.537 - ///Assignment operator
20.538 - template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
20.539 - { return *this; }
20.540 - };
20.541 -
20.542 - ///Reference map of the edges to type \c T.
20.543 -
20.544 - /// \ingroup skeletons
20.545 - ///Reference map of the edges to type \c T.
20.546 - /// \sa Reference
20.547 - /// \warning Making maps that can handle bool type (EdgeMap<bool>)
20.548 - /// needs some extra attention!
20.549 - template<class T> class EdgeMap
20.550 - : public ReferenceMap<Edge,T>
20.551 - {
20.552 - public:
20.553 -
20.554 - ///\e
20.555 - EdgeMap(const StaticSymGraph&) { }
20.556 - ///\e
20.557 - EdgeMap(const StaticSymGraph&, T) { }
20.558 -
20.559 - ///Copy constructor
20.560 - template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
20.561 - ///Assignment operator
20.562 - template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
20.563 - { return *this; }
20.564 - };
20.565 -
20.566 - ///Reference map of the edges to type \c T.
20.567 -
20.568 - /// \ingroup skeletons
20.569 - ///Reference map of the symmetric edges to type \c T.
20.570 - /// \sa Reference
20.571 - /// \warning Making maps that can handle bool type (EdgeMap<bool>)
20.572 - /// needs some extra attention!
20.573 - template<class T> class SymEdgeMap
20.574 - : public ReferenceMap<SymEdge,T>
20.575 - {
20.576 - public:
20.577 -
20.578 - ///\e
20.579 - SymEdgeMap(const StaticSymGraph&) { }
20.580 - ///\e
20.581 - SymEdgeMap(const StaticSymGraph&, T) { }
20.582 -
20.583 - ///Copy constructor
20.584 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT>&) { }
20.585 - ///Assignment operator
20.586 - template<typename TT> SymEdgeMap &operator=(const SymEdgeMap<TT>&)
20.587 - { return *this; }
20.588 - };
20.589 - };
20.590 -
20.591 -
20.592 -
20.593 - /// An empty non-static graph class.
20.594 -
20.595 - /// This class provides everything that \ref StaticGraph
20.596 - /// with additional functionality which enables to build a
20.597 - /// graph from scratch.
20.598 - class ExtendableSymGraph : public StaticSymGraph
20.599 - {
20.600 - public:
20.601 - /// Defalult constructor.
20.602 -
20.603 - /// Defalult constructor.
20.604 - ///
20.605 - ExtendableSymGraph() { }
20.606 - ///Add a new node to the graph.
20.607 -
20.608 - /// \return the new node.
20.609 - ///
20.610 - Node addNode() { return INVALID; }
20.611 - ///Add a new edge to the graph.
20.612 -
20.613 - ///Add a new symmetric edge to the graph with tail node \c t
20.614 - ///and head node \c h.
20.615 - ///\return the new edge.
20.616 - SymEdge addEdge(Node h, Node t) { return INVALID; }
20.617 -
20.618 - /// Resets the graph.
20.619 -
20.620 - /// This function deletes all edges and nodes of the graph.
20.621 - /// It also frees the memory allocated to store them.
20.622 - /// \todo It might belong to \ref ErasableGraph.
20.623 - void clear() { }
20.624 - };
20.625 -
20.626 - /// An empty erasable graph class.
20.627 -
20.628 - /// This class is an extension of \ref ExtendableGraph. It also makes it
20.629 - /// possible to erase edges or nodes.
20.630 - class ErasableSymGraph : public ExtendableSymGraph
20.631 - {
20.632 - public:
20.633 - /// Defalult constructor.
20.634 -
20.635 - /// Defalult constructor.
20.636 - ///
20.637 - ErasableSymGraph() { }
20.638 - /// Deletes a node.
20.639 -
20.640 - /// Deletes node \c n node.
20.641 - ///
20.642 - void erase(Node n) { }
20.643 - /// Deletes an edge.
20.644 -
20.645 - /// Deletes edge \c e edge.
20.646 - ///
20.647 - void erase(SymEdge e) { }
20.648 - };
20.649 -
20.650 - // @}
20.651 - } //namespace skeleton
20.652 -} //namespace lemon
20.653 -
20.654 -
20.655 -
20.656 -#endif // LEMON_SKELETON_GRAPH_H
21.1 --- a/src/lemon/smart_graph.h Thu Nov 04 18:52:31 2004 +0000
21.2 +++ b/src/lemon/smart_graph.h Thu Nov 04 20:24:59 2004 +0000
21.3 @@ -229,8 +229,8 @@
21.4 ///It is also quite memory efficient, but at the price
21.5 ///that <b> it does not support node and edge deletion</b>.
21.6 ///It conforms to
21.7 - ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept.
21.8 - ///\sa skeleton::ExtendableGraph.
21.9 + ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
21.10 + ///\sa concept::ExtendableGraph.
21.11 ///
21.12 ///\todo Some member functions could be \c static.
21.13 ///
22.1 --- a/src/test/bfs_test.cc Thu Nov 04 18:52:31 2004 +0000
22.2 +++ b/src/test/bfs_test.cc Thu Nov 04 20:24:59 2004 +0000
22.3 @@ -17,7 +17,7 @@
22.4 #include "test_tools.h"
22.5 #include <lemon/smart_graph.h>
22.6 #include <lemon/bfs.h>
22.7 -#include<lemon/skeletons/graph.h>
22.8 +#include<lemon/concept/graph.h>
22.9
22.10 using namespace lemon;
22.11
22.12 @@ -26,7 +26,7 @@
22.13
22.14 void check_Bfs_Compile()
22.15 {
22.16 - typedef skeleton::StaticGraph Graph;
22.17 + typedef concept::StaticGraph Graph;
22.18
22.19 typedef Graph::Edge Edge;
22.20 typedef Graph::Node Node;
23.1 --- a/src/test/dfs_test.cc Thu Nov 04 18:52:31 2004 +0000
23.2 +++ b/src/test/dfs_test.cc Thu Nov 04 20:24:59 2004 +0000
23.3 @@ -17,7 +17,7 @@
23.4 #include "test_tools.h"
23.5 #include <lemon/smart_graph.h>
23.6 #include <lemon/dfs.h>
23.7 -#include<lemon/skeletons/graph.h>
23.8 +#include <lemon/concept/graph.h>
23.9
23.10 using namespace lemon;
23.11
23.12 @@ -26,7 +26,7 @@
23.13
23.14 void check_Dfs_SmartGraph_Compile()
23.15 {
23.16 - typedef skeleton::StaticGraph Graph;
23.17 + typedef concept::StaticGraph Graph;
23.18
23.19 typedef Graph::Edge Edge;
23.20 typedef Graph::Node Node;
24.1 --- a/src/test/dijkstra_test.cc Thu Nov 04 18:52:31 2004 +0000
24.2 +++ b/src/test/dijkstra_test.cc Thu Nov 04 20:24:59 2004 +0000
24.3 @@ -17,8 +17,8 @@
24.4 #include "test_tools.h"
24.5 #include <lemon/smart_graph.h>
24.6 #include <lemon/dijkstra.h>
24.7 -#include<lemon/skeletons/graph.h>
24.8 -#include<lemon/skeletons/maps.h>
24.9 +#include <lemon/concept/graph.h>
24.10 +#include <lemon/concept/maps.h>
24.11 using namespace lemon;
24.12
24.13 const int PET_SIZE =5;
24.14 @@ -27,13 +27,13 @@
24.15 void check_Dijkstra_BinHeap_Compile()
24.16 {
24.17 typedef int VType;
24.18 - typedef skeleton::StaticGraph Graph;
24.19 + typedef concept::StaticGraph Graph;
24.20
24.21 typedef Graph::Edge Edge;
24.22 typedef Graph::Node Node;
24.23 typedef Graph::EdgeIt EdgeIt;
24.24 typedef Graph::NodeIt NodeIt;
24.25 - typedef skeleton::ReadMap<Edge,VType> LengthMap;
24.26 + typedef concept::ReadMap<Edge,VType> LengthMap;
24.27
24.28 typedef Dijkstra<Graph, LengthMap> DType;
24.29
25.1 --- a/src/test/graph_factory_test.cc Thu Nov 04 18:52:31 2004 +0000
25.2 +++ b/src/test/graph_factory_test.cc Thu Nov 04 20:24:59 2004 +0000
25.3 @@ -16,8 +16,8 @@
25.4
25.5 #include<iostream>
25.6 #include<lemon/smart_graph.h>
25.7 -#include<lemon/skeletons/graph.h>
25.8 -#include<lemon/skeletons/maps.h>
25.9 +#include<lemon/concept/graph.h>
25.10 +#include<lemon/concept/maps.h>
25.11 #include<lemon/list_graph_base.h>
25.12 #include<lemon/full_graph.h>
25.13
25.14 @@ -68,22 +68,22 @@
25.15 }
25.16
25.17 //Compile Graph
25.18 -template void lemon::skeleton::checkCompileStaticGraph<skeleton::StaticGraph>
25.19 -(skeleton::StaticGraph &);
25.20 +template void lemon::concept::checkCompileStaticGraph<concept::StaticGraph>
25.21 +(concept::StaticGraph &);
25.22
25.23 template
25.24 -void lemon::skeleton::checkCompileExtendableGraph<skeleton::ExtendableGraph>
25.25 -(skeleton::ExtendableGraph &);
25.26 +void lemon::concept::checkCompileExtendableGraph<concept::ExtendableGraph>
25.27 +(concept::ExtendableGraph &);
25.28
25.29 template
25.30 -void lemon::skeleton::checkCompileErasableGraph<skeleton::ErasableGraph>
25.31 -(skeleton::ErasableGraph &);
25.32 +void lemon::concept::checkCompileErasableGraph<concept::ErasableGraph>
25.33 +(concept::ErasableGraph &);
25.34
25.35 //Compile SmartGraph
25.36 template
25.37 -void lemon::skeleton::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
25.38 +void lemon::concept::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
25.39 template
25.40 -void lemon::skeleton::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
25.41 +void lemon::concept::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
25.42
25.43 //Compile SymSmartGraph
25.44 //template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
25.45 @@ -91,11 +91,11 @@
25.46
25.47 //Compile ListGraph
25.48 template
25.49 -void lemon::skeleton::checkCompileExtendableGraph<ListGraph>(ListGraph &);
25.50 +void lemon::concept::checkCompileExtendableGraph<ListGraph>(ListGraph &);
25.51 template
25.52 -void lemon::skeleton::checkCompileErasableGraph<ListGraph>(ListGraph &);
25.53 +void lemon::concept::checkCompileErasableGraph<ListGraph>(ListGraph &);
25.54 template
25.55 -void lemon::skeleton::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
25.56 +void lemon::concept::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
25.57
25.58
25.59 //Compile SymListGraph
25.60 @@ -104,9 +104,9 @@
25.61 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
25.62
25.63 //Compile FullGraph
25.64 -template void lemon::skeleton::checkCompileStaticGraph<FullGraph>(FullGraph &);
25.65 +template void lemon::concept::checkCompileStaticGraph<FullGraph>(FullGraph &);
25.66 template
25.67 -void lemon::skeleton::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
25.68 +void lemon::concept::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
25.69
25.70
25.71 int main()
25.72 @@ -141,7 +141,7 @@
25.73
25.74 // Some map tests.
25.75 // FIXME: These shouldn't be here.
25.76 - using namespace skeleton;
25.77 + using namespace concept;
25.78 function_requires< ReadMapConcept< ReadMap<int,int> > >();
25.79 function_requires< WriteMapConcept< WriteMap<int,int> > >();
25.80 function_requires< ReadWriteMapConcept< ReadWriteMap<int,int> > >();
26.1 --- a/src/test/graph_test.cc Thu Nov 04 18:52:31 2004 +0000
26.2 +++ b/src/test/graph_test.cc Thu Nov 04 20:24:59 2004 +0000
26.3 @@ -3,7 +3,7 @@
26.4 #include <iostream>
26.5 #include <vector>
26.6
26.7 -#include <lemon/skeletons/graph.h>
26.8 +#include <lemon/concept/graph.h>
26.9 #include <lemon/list_graph.h>
26.10 #include <lemon/smart_graph.h>
26.11 #include <lemon/full_graph.h>
26.12 @@ -14,7 +14,7 @@
26.13
26.14
26.15 using namespace lemon;
26.16 -using namespace lemon::skeleton;
26.17 +using namespace lemon::concept;
26.18
26.19
26.20 int main() {
27.1 --- a/src/test/graph_wrapper_test.cc Thu Nov 04 18:52:31 2004 +0000
27.2 +++ b/src/test/graph_wrapper_test.cc Thu Nov 04 20:24:59 2004 +0000
27.3 @@ -18,7 +18,7 @@
27.4 #include<lemon/concept_check.h>
27.5
27.6 #include<lemon/smart_graph.h>
27.7 -#include<lemon/skeletons/graph.h>
27.8 +#include<lemon/concept/graph.h>
27.9
27.10 #include<lemon/list_graph.h>
27.11 #include<lemon/full_graph.h>
27.12 @@ -35,7 +35,7 @@
27.13 */
27.14
27.15 using namespace lemon;
27.16 -using namespace lemon::skeleton;
27.17 +using namespace lemon::concept;
27.18
27.19
27.20 typedef SmartGraph Graph;
28.1 --- a/src/test/kruskal_test.cc Thu Nov 04 18:52:31 2004 +0000
28.2 +++ b/src/test/kruskal_test.cc Thu Nov 04 20:24:59 2004 +0000
28.3 @@ -21,8 +21,8 @@
28.4 #include <lemon/maps.h>
28.5 #include <lemon/kruskal.h>
28.6 #include <lemon/list_graph.h>
28.7 -#include <lemon/skeletons/maps.h>
28.8 -#include <lemon/skeletons/graph.h>
28.9 +#include <lemon/concept/maps.h>
28.10 +#include <lemon/concept/graph.h>
28.11
28.12
28.13 using namespace std;
28.14 @@ -30,10 +30,10 @@
28.15
28.16 void checkCompileKruskal()
28.17 {
28.18 - skeleton::WriteMap<skeleton::StaticGraph::Edge,bool> w;
28.19 + concept::WriteMap<concept::StaticGraph::Edge,bool> w;
28.20
28.21 - kruskalEdgeMap(skeleton::StaticGraph(),
28.22 - skeleton::ReadMap<skeleton::StaticGraph::Edge,int>(),
28.23 + kruskalEdgeMap(concept::StaticGraph(),
28.24 + concept::ReadMap<concept::StaticGraph::Edge,int>(),
28.25 w);
28.26 }
28.27
29.1 --- a/src/test/new_graph_test.cc Thu Nov 04 18:52:31 2004 +0000
29.2 +++ b/src/test/new_graph_test.cc Thu Nov 04 20:24:59 2004 +0000
29.3 @@ -14,10 +14,10 @@
29.4 *
29.5 */
29.6
29.7 -#include <lemon/skeletons/graph.h>
29.8 +#include <lemon/concept/graph.h>
29.9 // #include <boost/concept_check.hpp>
29.10
29.11 -using namespace lemon::skeleton;
29.12 +using namespace lemon::concept;
29.13
29.14 // Borrowed from boost:
29.15 template <class T> inline void ignore_unused_variable_warning(const T&) { }
30.1 --- a/src/test/path_test.cc Thu Nov 04 18:52:31 2004 +0000
30.2 +++ b/src/test/path_test.cc Thu Nov 04 20:24:59 2004 +0000
30.3 @@ -16,13 +16,13 @@
30.4
30.5 #include <string>
30.6 #include <iostream>
30.7 -#include <lemon/skeletons/path.h>
30.8 +#include <lemon/concept/path.h>
30.9 #include <lemon/path.h>
30.10 #include <lemon/list_graph.h>
30.11
30.12 using namespace std;
30.13 using namespace lemon;
30.14 -using namespace skeleton;
30.15 +using namespace lemon::concept;
30.16
30.17 template<class Path> void checkCompilePath(Path &P)
30.18 {
30.19 @@ -86,7 +86,7 @@
30.20
30.21 }
30.22
30.23 -template void checkCompilePath< skeleton::Path<ListGraph> >(skeleton::Path<ListGraph> &);
30.24 +template void checkCompilePath< concept::Path<ListGraph> >(concept::Path<ListGraph> &);
30.25 template void checkCompilePath< DirPath<ListGraph> >(DirPath<ListGraph> &);
30.26 template void checkCompilePath< UndirPath<ListGraph> >(UndirPath<ListGraph> &);
30.27
31.1 --- a/src/test/preflow_test.cc Thu Nov 04 18:52:31 2004 +0000
31.2 +++ b/src/test/preflow_test.cc Thu Nov 04 20:24:59 2004 +0000
31.3 @@ -21,21 +21,21 @@
31.4 #include <lemon/smart_graph.h>
31.5 #include <lemon/dimacs.h>
31.6 #include <lemon/preflow.h>
31.7 -#include <lemon/skeletons/graph.h>
31.8 -#include <lemon/skeletons/maps.h>
31.9 +#include <lemon/concept/graph.h>
31.10 +#include <lemon/concept/maps.h>
31.11
31.12 using namespace lemon;
31.13
31.14 void check_Preflow()
31.15 {
31.16 typedef int VType;
31.17 - typedef skeleton::StaticGraph Graph;
31.18 + typedef concept::StaticGraph Graph;
31.19
31.20 typedef Graph::Node Node;
31.21 typedef Graph::Edge Edge;
31.22 - typedef skeleton::ReadMap<Edge,VType> CapMap;
31.23 - typedef skeleton::ReadWriteMap<Edge,VType> FlowMap;
31.24 - typedef skeleton::ReadWriteMap<Node,bool> CutMap;
31.25 + typedef concept::ReadMap<Edge,VType> CapMap;
31.26 + typedef concept::ReadWriteMap<Edge,VType> FlowMap;
31.27 + typedef concept::ReadWriteMap<Node,bool> CutMap;
31.28
31.29 typedef Preflow<Graph, int, CapMap, FlowMap> PType;
31.30
32.1 --- a/src/test/sym_graph_test.cc Thu Nov 04 18:52:31 2004 +0000
32.2 +++ b/src/test/sym_graph_test.cc Thu Nov 04 20:24:59 2004 +0000
32.3 @@ -16,7 +16,7 @@
32.4
32.5 #include<iostream>
32.6
32.7 -#include<lemon/skeletons/sym_graph.h>
32.8 +#include<lemon/concept/sym_graph.h>
32.9
32.10 #include<lemon/list_graph.h>
32.11 #include<lemon/smart_graph.h>
32.12 @@ -54,26 +54,26 @@
32.13 }
32.14
32.15 //Compile Graph
32.16 -template void lemon::checkCompileStaticSymGraph<skeleton::StaticSymGraph>
32.17 -(skeleton::StaticSymGraph &);
32.18 +template void lemon::checkCompileStaticSymGraph<concept::StaticSymGraph>
32.19 +(concept::StaticSymGraph &);
32.20
32.21 -template void lemon::checkCompileSymGraph<skeleton::ExtendableSymGraph>
32.22 -(skeleton::ExtendableSymGraph &);
32.23 +template void lemon::checkCompileSymGraph<concept::ExtendableSymGraph>
32.24 +(concept::ExtendableSymGraph &);
32.25
32.26 -template void lemon::checkCompileErasableSymGraph<skeleton::ErasableSymGraph>
32.27 -(skeleton::ErasableSymGraph &);
32.28 +template void lemon::checkCompileErasableSymGraph<concept::ErasableSymGraph>
32.29 +(concept::ErasableSymGraph &);
32.30
32.31
32.32 //Compile SymSmartGraph
32.33 template void lemon::checkCompileSymGraph<SymSmartGraph>(SymSmartGraph &);
32.34 template
32.35 -void lemon::skeleton::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
32.36 +void lemon::concept::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
32.37
32.38 //Compile SymListGraph
32.39 template void lemon::checkCompileSymGraph<SymListGraph>(SymListGraph &);
32.40 template void lemon::checkCompileErasableSymGraph<SymListGraph>(SymListGraph &);
32.41 template
32.42 -void lemon::skeleton::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
32.43 +void lemon::concept::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
32.44
32.45 int main()
32.46 {
33.1 --- a/src/test/sym_graph_test.h Thu Nov 04 18:52:31 2004 +0000
33.2 +++ b/src/test/sym_graph_test.h Thu Nov 04 20:24:59 2004 +0000
33.3 @@ -27,7 +27,7 @@
33.4
33.5 /// \e
33.6
33.7 - /// \todo This should go to lemon/skeleton/symgraph.h
33.8 + /// \todo This should go to lemon/concept/symgraph.h
33.9 ///
33.10 template<class Graph> void checkCompileStaticSymGraph(Graph &G)
33.11 {
33.12 @@ -40,7 +40,7 @@
33.13 typedef typename Graph::InEdgeIt InEdgeIt;
33.14 typedef typename Graph::OutEdgeIt OutEdgeIt;
33.15
33.16 - lemon::skeleton::checkCompileStaticGraph(G);
33.17 + lemon::concept::checkCompileStaticGraph(G);
33.18
33.19 {
33.20 SymEdge i; SymEdge j(i); SymEdge k(INVALID);
33.21 @@ -157,7 +157,7 @@
33.22 template<class Graph> void checkCompileErasableSymGraph(Graph &G)
33.23 {
33.24 checkCompileSymGraph(G);
33.25 - lemon::skeleton::checkCompileGraphEraseNode(G);
33.26 + lemon::concept::checkCompileGraphEraseNode(G);
33.27 checkCompileSymGraphEraseSymEdge(G);
33.28 }
33.29
34.1 --- a/src/work/Doxyfile Thu Nov 04 18:52:31 2004 +0000
34.2 +++ b/src/work/Doxyfile Thu Nov 04 20:24:59 2004 +0000
34.3 @@ -396,7 +396,7 @@
34.4 ../../doc/maps.dox ../../doc/coding_style.dox \
34.5 ../../doc/groups.dox \
34.6 ../lemon \
34.7 - ../lemon/skeletons \
34.8 + ../lemon/concept \
34.9 ../test/test_tools.h \
34.10 klao/path.h \
34.11 klao/debug.h \
35.1 --- a/src/work/alpar/dijkstra.h Thu Nov 04 18:52:31 2004 +0000
35.2 +++ b/src/work/alpar/dijkstra.h Thu Nov 04 20:24:59 2004 +0000
35.3 @@ -100,11 +100,11 @@
35.4
35.5 ///This class provides an efficient implementation of %Dijkstra algorithm.
35.6 ///The edge lengths are passed to the algorithm using a
35.7 - ///\ref skeleton::ReadMap "ReadMap",
35.8 + ///\ref concept::ReadMap "ReadMap",
35.9 ///so it is easy to change it to any kind of length.
35.10 ///
35.11 ///The type of the length is determined by the
35.12 - ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map.
35.13 + ///\ref concept::ReadMap::ValueType "ValueType" of the length map.
35.14 ///
35.15 ///It is also possible to change the underlying priority heap.
35.16 ///
35.17 @@ -117,7 +117,7 @@
35.18 ///lengths of the edges. It is read once for each edge, so the map
35.19 ///may involve in relatively time consuming process to compute the edge
35.20 ///length if it is necessary. The default map type is
35.21 - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
35.22 + ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
35.23 ///The value of LM is not used directly by Dijkstra, it
35.24 ///is only passed to \ref DijkstraDefaultTraits.
35.25 ///\param TR Traits class to set various data types used by the algorithm.
36.1 --- a/src/work/alpar/list_graph_demo.cc Thu Nov 04 18:52:31 2004 +0000
36.2 +++ b/src/work/alpar/list_graph_demo.cc Thu Nov 04 20:24:59 2004 +0000
36.3 @@ -1,5 +1,5 @@
36.4 #include<list_graph.h>
36.5 -#include<skeletons/graph.h>
36.6 +#include<concept/graph.h>
36.7
36.8 #include <iostream>
36.9 #include <vector>
37.1 --- a/src/work/marci/bfs_mm_test.cc Thu Nov 04 18:52:31 2004 +0000
37.2 +++ b/src/work/marci/bfs_mm_test.cc Thu Nov 04 20:24:59 2004 +0000
37.3 @@ -17,7 +17,7 @@
37.4 #include <test/test_tools.h>
37.5 #include <lemon/smart_graph.h>
37.6 #include <bfs_mm.h>
37.7 -#include <lemon/skeletons/graph.h>
37.8 +#include <lemon/concept/graph.h>
37.9
37.10 using namespace lemon;
37.11
37.12 @@ -26,7 +26,7 @@
37.13
37.14 void check_Bfs_Compile()
37.15 {
37.16 - typedef skeleton::StaticGraph Graph;
37.17 + typedef concept::StaticGraph Graph;
37.18
37.19 typedef Graph::Edge Edge;
37.20 typedef Graph::Node Node;
38.1 --- a/src/work/peter/path/path.h Thu Nov 04 18:52:31 2004 +0000
38.2 +++ b/src/work/peter/path/path.h Thu Nov 04 20:24:59 2004 +0000
38.3 @@ -12,7 +12,7 @@
38.4 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
38.5 algorithm to store its result in any kind of path structure.
38.6
38.7 -\sa lemon::skeleton::Path
38.8 +\sa lemon::concept::Path
38.9
38.10 */
38.11
39.1 --- a/src/work/peter/path/path_skeleton.h Thu Nov 04 18:52:31 2004 +0000
39.2 +++ b/src/work/peter/path/path_skeleton.h Thu Nov 04 20:24:59 2004 +0000
39.3 @@ -1,7 +1,7 @@
39.4 #define SKELETON
39.5 // -*- c++ -*- //
39.6
39.7 -///\ingroup skeletons
39.8 +///\ingroup concept
39.9 ///\file
39.10 ///\brief Classes for representing paths in graphs.
39.11
39.12 @@ -11,12 +11,12 @@
39.13 #include <lemon/invalid.h>
39.14
39.15 namespace lemon {
39.16 - namespace skeleton {
39.17 - /// \addtogroup skeletons
39.18 + namespace concept {
39.19 + /// \addtogroup concept
39.20 /// @{
39.21
39.22
39.23 - //! \brief A skeletom structure for representing directed paths in a graph.
39.24 + //! \brief A skeleton structure for representing directed paths in a graph.
39.25 //!
39.26 //! A skeleton structure for representing directed paths in a graph.
39.27 //! \param GR The graph type in which the path is.
39.28 @@ -85,7 +85,7 @@
39.29 /**
39.30 * \brief Iterator class to iterate on the edges of the paths
39.31 *
39.32 - * \ingroup skeletons
39.33 + * \ingroup concept
39.34 * This class is used to iterate on the edges of the paths
39.35 *
39.36 * Of course it converts to Graph::Edge
39.37 @@ -118,7 +118,7 @@
39.38 /**
39.39 * \brief Iterator class to iterate on the nodes of the paths
39.40 *
39.41 - * \ingroup skeletons
39.42 + * \ingroup concept
39.43 * This class is used to iterate on the nodes of the paths
39.44 *
39.45 * Of course it converts to Graph::Node.
39.46 @@ -153,7 +153,7 @@
39.47 /**
39.48 * \brief Class to build paths
39.49 *
39.50 - * \ingroup skeletons
39.51 + * \ingroup concept
39.52 * This class is used to fill a path with edges.
39.53 *
39.54 * You can push new edges to the front and to the back of the path in
40.1 --- a/src/work/peter/path/path_test.cc Thu Nov 04 18:52:31 2004 +0000
40.2 +++ b/src/work/peter/path/path_test.cc Thu Nov 04 20:24:59 2004 +0000
40.3 @@ -6,7 +6,7 @@
40.4
40.5 using namespace std;
40.6 using namespace lemon;
40.7 -using namespace skeleton;
40.8 +using namespace concept;
40.9
40.10 bool passed = true;
40.11