1.1 --- a/src/lemon/concept/graph.h Mon Feb 07 10:50:05 2005 +0000
1.2 +++ b/src/lemon/concept/graph.h Mon Feb 07 11:28:37 2005 +0000
1.3 @@ -28,483 +28,18 @@
1.4
1.5 namespace lemon {
1.6 namespace concept {
1.7 +
1.8
1.9 /// \addtogroup graph_concepts
1.10 /// @{
1.11
1.12 -// /// An empty static graph class.
1.13 -
1.14 -// /// This class provides all the common features of a graph structure,
1.15 -// /// however completely without implementations and real data structures
1.16 -// /// behind the interface.
1.17 -// /// All graph algorithms should compile with this class, but it will not
1.18 -// /// run properly, of course.
1.19 -// ///
1.20 -// /// It can be used for checking the interface compatibility,
1.21 -// /// or it can serve as a skeleton of a new graph structure.
1.22 -// ///
1.23 -// /// Also, you will find here the full documentation of a certain graph
1.24 -// /// feature, the documentation of a real graph imlementation
1.25 -// /// like @ref ListGraph or
1.26 -// /// @ref SmartGraph will just refer to this structure.
1.27 -// ///
1.28 -// /// \todo A pages describing the concept of concept description would
1.29 -// /// be nice.
1.30 -// class StaticGraph
1.31 -// {
1.32 -// public:
1.33 -// /// Defalult constructor.
1.34 -
1.35 -// /// Defalult constructor.
1.36 -// ///
1.37 -// StaticGraph() { }
1.38 -// ///Copy consructor.
1.39 -
1.40 -// // ///\todo It is not clear, what we expect from a copy constructor.
1.41 -// // ///E.g. How to assign the nodes/edges to each other? What about maps?
1.42 -// // StaticGraph(const StaticGraph& g) { }
1.43 -
1.44 -// /// The base type of node iterators,
1.45 -// /// or in other words, the trivial node iterator.
1.46 -
1.47 -// /// This is the base type of each node iterator,
1.48 -// /// thus each kind of node iterator converts to this.
1.49 -// /// More precisely each kind of node iterator should be inherited
1.50 -// /// from the trivial node iterator.
1.51 -// class Node {
1.52 -// public:
1.53 -// /// Default constructor
1.54 -
1.55 -// /// @warning The default constructor sets the iterator
1.56 -// /// to an undefined value.
1.57 -// Node() { }
1.58 -// /// Copy constructor.
1.59 -
1.60 -// /// Copy constructor.
1.61 -// ///
1.62 -// Node(const Node&) { }
1.63 -
1.64 -// /// Invalid constructor \& conversion.
1.65 -
1.66 -// /// This constructor initializes the iterator to be invalid.
1.67 -// /// \sa Invalid for more details.
1.68 -// Node(Invalid) { }
1.69 -// /// Equality operator
1.70 -
1.71 -// /// Two iterators are equal if and only if they point to the
1.72 -// /// same object or both are invalid.
1.73 -// bool operator==(Node) const { return true; }
1.74 -
1.75 -// /// Inequality operator
1.76 -
1.77 -// /// \sa operator==(Node n)
1.78 -// ///
1.79 -// bool operator!=(Node) const { return true; }
1.80 -
1.81 -// };
1.82 -
1.83 -// /// This iterator goes through each node.
1.84 -
1.85 -// /// This iterator goes through each node.
1.86 -// /// Its usage is quite simple, for example you can count the number
1.87 -// /// of nodes in graph \c g of type \c Graph like this:
1.88 -// /// \code
1.89 -// /// int count=0;
1.90 -// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
1.91 -// /// \endcode
1.92 -// class NodeIt : public Node {
1.93 -// public:
1.94 -// /// Default constructor
1.95 -
1.96 -// /// @warning The default constructor sets the iterator
1.97 -// /// to an undefined value.
1.98 -// NodeIt() { }
1.99 -// /// Copy constructor.
1.100 -
1.101 -// /// Copy constructor.
1.102 -// ///
1.103 -// NodeIt(const NodeIt&) { }
1.104 -// /// Invalid constructor \& conversion.
1.105 -
1.106 -// /// Initialize the iterator to be invalid.
1.107 -// /// \sa Invalid for more details.
1.108 -// NodeIt(Invalid) { }
1.109 -// /// Sets the iterator to the first node.
1.110 -
1.111 -// /// Sets the iterator to the first node of \c g.
1.112 -// ///
1.113 -// NodeIt(const StaticGraph& g) { }
1.114 -// /// Node -> NodeIt conversion.
1.115 -
1.116 -// /// Sets the iterator to the node of \c g pointed by the trivial
1.117 -// /// iterator n.
1.118 -// /// This feature necessitates that each time we
1.119 -// /// iterate the edge-set, the iteration order is the same.
1.120 -// NodeIt(const StaticGraph& g, const Node& n) { }
1.121 -// /// Next node.
1.122 -
1.123 -// /// Assign the iterator to the next node.
1.124 -// ///
1.125 -// NodeIt& operator++() { return *this; }
1.126 -// };
1.127 -
1.128 -
1.129 -// /// The base type of the edge iterators.
1.130 -
1.131 -// /// The base type of the edge iterators.
1.132 -// ///
1.133 -// class Edge {
1.134 -// public:
1.135 -// /// Default constructor
1.136 -
1.137 -// /// @warning The default constructor sets the iterator
1.138 -// /// to an undefined value.
1.139 -// Edge() { }
1.140 -// /// Copy constructor.
1.141 -
1.142 -// /// Copy constructor.
1.143 -// ///
1.144 -// Edge(const Edge&) { }
1.145 -// /// Initialize the iterator to be invalid.
1.146 -
1.147 -// /// Initialize the iterator to be invalid.
1.148 -// ///
1.149 -// Edge(Invalid) { }
1.150 -// /// Equality operator
1.151 -
1.152 -// /// Two iterators are equal if and only if they point to the
1.153 -// /// same object or both are invalid.
1.154 -// bool operator==(Edge) const { return true; }
1.155 -// /// Inequality operator
1.156 -
1.157 -// /// \sa operator==(Node n)
1.158 -// ///
1.159 -// bool operator!=(Edge) const { return true; }
1.160 -// };
1.161 -
1.162 -// /// This iterator goes trough the outgoing edges of a node.
1.163 -
1.164 -// /// This iterator goes trough the \e outgoing edges of a certain node
1.165 -// /// of a graph.
1.166 -// /// Its usage is quite simple, for example you can count the number
1.167 -// /// of outgoing edges of a node \c n
1.168 -// /// in graph \c g of type \c Graph as follows.
1.169 -// /// \code
1.170 -// /// int count=0;
1.171 -// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.172 -// /// \endcode
1.173 -
1.174 -// class OutEdgeIt : public Edge {
1.175 -// public:
1.176 -// /// Default constructor
1.177 -
1.178 -// /// @warning The default constructor sets the iterator
1.179 -// /// to an undefined value.
1.180 -// OutEdgeIt() { }
1.181 -// /// Copy constructor.
1.182 -
1.183 -// /// Copy constructor.
1.184 -// ///
1.185 -// OutEdgeIt(const OutEdgeIt&) { }
1.186 -// /// Initialize the iterator to be invalid.
1.187 -
1.188 -// /// Initialize the iterator to be invalid.
1.189 -// ///
1.190 -// OutEdgeIt(Invalid) { }
1.191 -// /// This constructor sets the iterator to first outgoing edge.
1.192 -
1.193 -// /// This constructor set the iterator to the first outgoing edge of
1.194 -// /// node
1.195 -// ///@param n the node
1.196 -// ///@param g the graph
1.197 -// OutEdgeIt(const StaticGraph& g, const Node& n) { }
1.198 -// /// Edge -> OutEdgeIt conversion
1.199 -
1.200 -// /// Sets the iterator to the value of the trivial iterator \c e.
1.201 -// /// This feature necessitates that each time we
1.202 -// /// iterate the edge-set, the iteration order is the same.
1.203 -// OutEdgeIt(const StaticGraph& g, const Edge& e) { }
1.204 -// ///Next outgoing edge
1.205 -
1.206 -// /// Assign the iterator to the next
1.207 -// /// outgoing edge of the corresponding node.
1.208 -// OutEdgeIt& operator++() { return *this; }
1.209 -// };
1.210 -
1.211 -// /// This iterator goes trough the incoming edges of a node.
1.212 -
1.213 -// /// This iterator goes trough the \e incoming edges of a certain node
1.214 -// /// of a graph.
1.215 -// /// Its usage is quite simple, for example you can count the number
1.216 -// /// of outgoing edges of a node \c n
1.217 -// /// in graph \c g of type \c Graph as follows.
1.218 -// /// \code
1.219 -// /// int count=0;
1.220 -// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.221 -// /// \endcode
1.222 -
1.223 -// class InEdgeIt : public Edge {
1.224 -// public:
1.225 -// /// Default constructor
1.226 -
1.227 -// /// @warning The default constructor sets the iterator
1.228 -// /// to an undefined value.
1.229 -// InEdgeIt() { }
1.230 -// /// Copy constructor.
1.231 -
1.232 -// /// Copy constructor.
1.233 -// ///
1.234 -// InEdgeIt(const InEdgeIt&) { }
1.235 -// /// Initialize the iterator to be invalid.
1.236 -
1.237 -// /// Initialize the iterator to be invalid.
1.238 -// ///
1.239 -// InEdgeIt(Invalid) { }
1.240 -// /// This constructor sets the iterator to first incoming edge.
1.241 -
1.242 -// /// This constructor set the iterator to the first incoming edge of
1.243 -// /// node
1.244 -// ///@param n the node
1.245 -// ///@param g the graph
1.246 -// InEdgeIt(const StaticGraph& g, const Node& n) { }
1.247 -// /// Edge -> InEdgeIt conversion
1.248 -
1.249 -// /// Sets the iterator to the value of the trivial iterator \c e.
1.250 -// /// This feature necessitates that each time we
1.251 -// /// iterate the edge-set, the iteration order is the same.
1.252 -// InEdgeIt(const StaticGraph& g, const Edge& n) { }
1.253 -// /// Next incoming edge
1.254 -
1.255 -// /// Assign the iterator to the next inedge of the corresponding node.
1.256 -// ///
1.257 -// InEdgeIt& operator++() { return *this; }
1.258 -// };
1.259 -// /// This iterator goes through each edge.
1.260 -
1.261 -// /// This iterator goes through each edge of a graph.
1.262 -// /// Its usage is quite simple, for example you can count the number
1.263 -// /// of edges in a graph \c g of type \c Graph as follows:
1.264 -// /// \code
1.265 -// /// int count=0;
1.266 -// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.267 -// /// \endcode
1.268 -// class EdgeIt : public Edge {
1.269 -// public:
1.270 -// /// Default constructor
1.271 -
1.272 -// /// @warning The default constructor sets the iterator
1.273 -// /// to an undefined value.
1.274 -// EdgeIt() { }
1.275 -// /// Copy constructor.
1.276 -
1.277 -// /// Copy constructor.
1.278 -// ///
1.279 -// EdgeIt(const EdgeIt&) { }
1.280 -// /// Initialize the iterator to be invalid.
1.281 -
1.282 -// /// Initialize the iterator to be invalid.
1.283 -// ///
1.284 -// EdgeIt(Invalid) { }
1.285 -// /// This constructor sets the iterator to first edge.
1.286 -
1.287 -// /// This constructor set the iterator to the first edge of
1.288 -// /// node
1.289 -// ///@param g the graph
1.290 -// EdgeIt(const StaticGraph& g) { }
1.291 -// /// Edge -> EdgeIt conversion
1.292 -
1.293 -// /// Sets the iterator to the value of the trivial iterator \c e.
1.294 -// /// This feature necessitates that each time we
1.295 -// /// iterate the edge-set, the iteration order is the same.
1.296 -// EdgeIt(const StaticGraph&, const Edge&) { }
1.297 -// ///Next edge
1.298 -
1.299 -// /// Assign the iterator to the next
1.300 -// /// edge of the corresponding node.
1.301 -// EdgeIt& operator++() { return *this; }
1.302 -// };
1.303 -// ///Gives back the target node of an edge.
1.304 -
1.305 -// ///Gives back the target node of an edge.
1.306 -// ///
1.307 -// Node target(Edge) const { return INVALID; }
1.308 -// ///Gives back the source node of an edge.
1.309 -
1.310 -// ///Gives back the source node of an edge.
1.311 -// ///
1.312 -// Node source(Edge) const { return INVALID; }
1.313 -// /// Read write map of the nodes to type \c T.
1.314 -
1.315 -// /// \ingroup concept
1.316 -// /// ReadWrite map of the nodes to type \c T.
1.317 -// /// \sa Reference
1.318 -// /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.319 -// /// needs some extra attention!
1.320 -// template<class T>
1.321 -// class NodeMap : public ReadWriteMap< Node, T >
1.322 -// {
1.323 -// public:
1.324 -
1.325 -// ///\e
1.326 -// NodeMap(const StaticGraph&) { }
1.327 -// ///\e
1.328 -// NodeMap(const StaticGraph&, T) { }
1.329 -
1.330 -// ///Copy constructor
1.331 -// NodeMap(const NodeMap&) { }
1.332 -// ///Assignment operator
1.333 -// NodeMap& operator=(const NodeMap&) { return *this; }
1.334 -// // \todo fix this concept
1.335 -// };
1.336 -
1.337 -// /// Read write map of the edges to type \c T.
1.338 -
1.339 -// /// \ingroup concept
1.340 -// ///Reference map of the edges to type \c T.
1.341 -// /// \sa Reference
1.342 -// /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.343 -// /// needs some extra attention!
1.344 -// template<class T>
1.345 -// class EdgeMap : public ReadWriteMap<Edge,T>
1.346 -// {
1.347 -// public:
1.348 -
1.349 -// ///\e
1.350 -// EdgeMap(const StaticGraph&) { }
1.351 -// ///\e
1.352 -// EdgeMap(const StaticGraph&, T) { }
1.353 -// ///Copy constructor
1.354 -// EdgeMap(const EdgeMap&) { }
1.355 -// ///Assignment operator
1.356 -// EdgeMap& operator=(const EdgeMap&) { return *this; }
1.357 -// // \todo fix this concept
1.358 -// };
1.359 -// };
1.360 -
1.361 -// /// An empty non-static graph class.
1.362 -
1.363 -// /// This class provides everything that \ref StaticGraph
1.364 -// /// with additional functionality which enables to build a
1.365 -// /// graph from scratch.
1.366 -// class ExtendableGraph : public StaticGraph
1.367 -// {
1.368 -// public:
1.369 -// /// Defalult constructor.
1.370 -
1.371 -// /// Defalult constructor.
1.372 -// ///
1.373 -// ExtendableGraph() { }
1.374 -// ///Add a new node to the graph.
1.375 -
1.376 -// /// \return the new node.
1.377 -// ///
1.378 -// Node addNode() { return INVALID; }
1.379 -// ///Add a new edge to the graph.
1.380 -
1.381 -// ///Add a new edge to the graph with source node \c s
1.382 -// ///and target node \c t.
1.383 -// ///\return the new edge.
1.384 -// Edge addEdge(Node s, Node t) { return INVALID; }
1.385 -
1.386 -// /// Resets the graph.
1.387 -
1.388 -// /// This function deletes all edges and nodes of the graph.
1.389 -// /// It also frees the memory allocated to store them.
1.390 -// /// \todo It might belong to \ref ErasableGraph.
1.391 -// void clear() { }
1.392 -// };
1.393 -
1.394 -// /// An empty erasable graph class.
1.395 -
1.396 -// /// This class is an extension of \ref ExtendableGraph. It also makes it
1.397 -// /// possible to erase edges or nodes.
1.398 -// class ErasableGraph : public ExtendableGraph
1.399 -// {
1.400 -// public:
1.401 -// /// Defalult constructor.
1.402 -
1.403 -// /// Defalult constructor.
1.404 -// ///
1.405 -// ErasableGraph() { }
1.406 -// /// Deletes a node.
1.407 -
1.408 -// /// Deletes node \c n node.
1.409 -// ///
1.410 -// void erase(Node n) { }
1.411 -// /// Deletes an edge.
1.412 -
1.413 -// /// Deletes edge \c e edge.
1.414 -// ///
1.415 -// void erase(Edge e) { }
1.416 -// };
1.417 -
1.418 -
1.419 - /************* New GraphBase stuff **************/
1.420 -
1.421 -
1.422 - /// A minimal GraphBase concept
1.423 -
1.424 - /// This class describes a minimal concept which can be extended to a
1.425 - /// full-featured graph with \ref GraphFactory.
1.426 - class GraphBase {
1.427 - public:
1.428 -
1.429 - GraphBase() {}
1.430 -
1.431 - /// \bug Should we demand that Node and Edge be subclasses of the
1.432 - /// Graph class???
1.433 -
1.434 - typedef GraphItem<'n'> Node;
1.435 - typedef GraphItem<'e'> Edge;
1.436 -
1.437 -// class Node : public BaseGraphItem<'n'> {};
1.438 -// class Edge : public BaseGraphItem<'e'> {};
1.439 -
1.440 - // Graph operation
1.441 - void firstNode(Node &n) const { }
1.442 - void firstEdge(Edge &e) const { }
1.443 -
1.444 - void firstOutEdge(Edge &e, Node) const { }
1.445 - void firstInEdge(Edge &e, Node) const { }
1.446 -
1.447 - void nextNode(Node &n) const { }
1.448 - void nextEdge(Edge &e) const { }
1.449 -
1.450 -
1.451 - // Question: isn't it reasonable if this methods have a Node
1.452 - // parameter? Like this:
1.453 - // Edge& nextOut(Edge &e, Node) const { return e; }
1.454 - void nextOutEdge(Edge &e) const { }
1.455 - void nextInEdge(Edge &e) const { }
1.456 -
1.457 - Node target(Edge) const { return Node(); }
1.458 - Node source(Edge) const { return Node(); }
1.459 -
1.460 -
1.461 - // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
1.462 - // concept?
1.463 -
1.464 -
1.465 - // Maps.
1.466 - //
1.467 - // We need a special slimer concept which does not provide maps (it
1.468 - // wouldn't be strictly slimer, cause for map-factory id() & friends
1.469 - // a required...)
1.470 -
1.471 - template<typename T>
1.472 - class NodeMap : public GraphMap<GraphBase, Node, T> {};
1.473 -
1.474 - template<typename T>
1.475 - class EdgeMap : public GraphMap<GraphBase, Node, T> {};
1.476 - };
1.477 -
1.478 -
1.479 -
1.480 -
1.481 /**************** The full-featured graph concepts ****************/
1.482
1.483 -
1.484 - class StaticGraph
1.485 +
1.486 + /// \brief Modular builded static graph class.
1.487 + ///
1.488 + /// It should be the same as the \c StaticGraph class.
1.489 + class _StaticGraph
1.490 : virtual public BaseGraphComponent,
1.491 public IterableGraphComponent, public MappableGraphComponent {
1.492 public:
1.493 @@ -520,8 +55,11 @@
1.494 };
1.495 };
1.496
1.497 - class ExtendableGraph
1.498 - : virtual public BaseGraphComponent, public StaticGraph,
1.499 + /// \brief Modular builded extendable graph class.
1.500 + ///
1.501 + /// It should be the same as the \c ExtendableGraph class.
1.502 + class _ExtendableGraph
1.503 + : virtual public BaseGraphComponent, public _StaticGraph,
1.504 public ExtendableGraphComponent, public ClearableGraphComponent {
1.505 public:
1.506 typedef BaseGraphComponent::Node Node;
1.507 @@ -530,15 +68,18 @@
1.508 template <typename _Graph>
1.509 struct Constraints {
1.510 void constraints() {
1.511 - checkConcept<StaticGraph, _Graph >();
1.512 + checkConcept<_StaticGraph, _Graph >();
1.513 checkConcept<ExtendableGraphComponent, _Graph >();
1.514 checkConcept<ClearableGraphComponent, _Graph >();
1.515 }
1.516 };
1.517 };
1.518
1.519 - class ErasableGraph
1.520 - : virtual public BaseGraphComponent, public ExtendableGraph,
1.521 + /// \brief Modular builded erasable graph class.
1.522 + ///
1.523 + /// It should be the same as the \c ErasableGraph class.
1.524 + class _ErasableGraph
1.525 + : virtual public BaseGraphComponent, public _ExtendableGraph,
1.526 public ErasableGraphComponent {
1.527 public:
1.528 typedef BaseGraphComponent::Node Node;
1.529 @@ -547,12 +88,490 @@
1.530 template <typename _Graph>
1.531 struct Constraints {
1.532 void constraints() {
1.533 - checkConcept<ExtendableGraph, _Graph >();
1.534 + checkConcept<_ExtendableGraph, _Graph >();
1.535 checkConcept<ErasableGraphComponent, _Graph >();
1.536 }
1.537 };
1.538 };
1.539
1.540 + /// An empty static graph class.
1.541 +
1.542 + /// This class provides all the common features of a graph structure,
1.543 + /// however completely without implementations and real data structures
1.544 + /// behind the interface.
1.545 + /// All graph algorithms should compile with this class, but it will not
1.546 + /// run properly, of course.
1.547 + ///
1.548 + /// It can be used for checking the interface compatibility,
1.549 + /// or it can serve as a skeleton of a new graph structure.
1.550 + ///
1.551 + /// Also, you will find here the full documentation of a certain graph
1.552 + /// feature, the documentation of a real graph imlementation
1.553 + /// like @ref ListGraph or
1.554 + /// @ref SmartGraph will just refer to this structure.
1.555 + ///
1.556 + /// \todo A pages describing the concept of concept description would
1.557 + /// be nice.
1.558 + class StaticGraph
1.559 + {
1.560 + public:
1.561 + /// Defalult constructor.
1.562 +
1.563 + /// Defalult constructor.
1.564 + ///
1.565 + StaticGraph() { }
1.566 + ///Copy consructor.
1.567 +
1.568 +// ///\todo It is not clear, what we expect from a copy constructor.
1.569 +// ///E.g. How to assign the nodes/edges to each other? What about maps?
1.570 +// StaticGraph(const StaticGraph& g) { }
1.571 +
1.572 + /// The base type of node iterators,
1.573 + /// or in other words, the trivial node iterator.
1.574 +
1.575 + /// This is the base type of each node iterator,
1.576 + /// thus each kind of node iterator converts to this.
1.577 + /// More precisely each kind of node iterator should be inherited
1.578 + /// from the trivial node iterator.
1.579 + class Node {
1.580 + public:
1.581 + /// Default constructor
1.582 +
1.583 + /// @warning The default constructor sets the iterator
1.584 + /// to an undefined value.
1.585 + Node() { }
1.586 + /// Copy constructor.
1.587 +
1.588 + /// Copy constructor.
1.589 + ///
1.590 + Node(const Node&) { }
1.591 +
1.592 + /// Invalid constructor \& conversion.
1.593 +
1.594 + /// This constructor initializes the iterator to be invalid.
1.595 + /// \sa Invalid for more details.
1.596 + Node(Invalid) { }
1.597 + /// Equality operator
1.598 +
1.599 + /// Two iterators are equal if and only if they point to the
1.600 + /// same object or both are invalid.
1.601 + bool operator==(Node) const { return true; }
1.602 +
1.603 + /// Inequality operator
1.604 +
1.605 + /// \sa operator==(Node n)
1.606 + ///
1.607 + bool operator!=(Node) const { return true; }
1.608 +
1.609 + };
1.610 +
1.611 + /// This iterator goes through each node.
1.612 +
1.613 + /// This iterator goes through each node.
1.614 + /// Its usage is quite simple, for example you can count the number
1.615 + /// of nodes in graph \c g of type \c Graph like this:
1.616 + /// \code
1.617 + /// int count=0;
1.618 + /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
1.619 + /// \endcode
1.620 + class NodeIt : public Node {
1.621 + public:
1.622 + /// Default constructor
1.623 +
1.624 + /// @warning The default constructor sets the iterator
1.625 + /// to an undefined value.
1.626 + NodeIt() { }
1.627 + /// Copy constructor.
1.628 +
1.629 + /// Copy constructor.
1.630 + ///
1.631 + NodeIt(const NodeIt&) { }
1.632 + /// Invalid constructor \& conversion.
1.633 +
1.634 + /// Initialize the iterator to be invalid.
1.635 + /// \sa Invalid for more details.
1.636 + NodeIt(Invalid) { }
1.637 + /// Sets the iterator to the first node.
1.638 +
1.639 + /// Sets the iterator to the first node of \c g.
1.640 + ///
1.641 + NodeIt(const StaticGraph& g) { }
1.642 + /// Node -> NodeIt conversion.
1.643 +
1.644 + /// Sets the iterator to the node of \c g pointed by the trivial
1.645 + /// iterator n.
1.646 + /// This feature necessitates that each time we
1.647 + /// iterate the edge-set, the iteration order is the same.
1.648 + NodeIt(const StaticGraph& g, const Node& n) { }
1.649 + /// Next node.
1.650 +
1.651 + /// Assign the iterator to the next node.
1.652 + ///
1.653 + NodeIt& operator++() { return *this; }
1.654 + };
1.655 +
1.656 +
1.657 + /// The base type of the edge iterators.
1.658 +
1.659 + /// The base type of the edge iterators.
1.660 + ///
1.661 + class Edge {
1.662 + public:
1.663 + /// Default constructor
1.664 +
1.665 + /// @warning The default constructor sets the iterator
1.666 + /// to an undefined value.
1.667 + Edge() { }
1.668 + /// Copy constructor.
1.669 +
1.670 + /// Copy constructor.
1.671 + ///
1.672 + Edge(const Edge&) { }
1.673 + /// Initialize the iterator to be invalid.
1.674 +
1.675 + /// Initialize the iterator to be invalid.
1.676 + ///
1.677 + Edge(Invalid) { }
1.678 + /// Equality operator
1.679 +
1.680 + /// Two iterators are equal if and only if they point to the
1.681 + /// same object or both are invalid.
1.682 + bool operator==(Edge) const { return true; }
1.683 + /// Inequality operator
1.684 +
1.685 + /// \sa operator==(Node n)
1.686 + ///
1.687 + bool operator!=(Edge) const { return true; }
1.688 + };
1.689 +
1.690 + /// This iterator goes trough the outgoing edges of a node.
1.691 +
1.692 + /// This iterator goes trough the \e outgoing edges of a certain node
1.693 + /// of a graph.
1.694 + /// Its usage is quite simple, for example you can count the number
1.695 + /// of outgoing edges of a node \c n
1.696 + /// in graph \c g of type \c Graph as follows.
1.697 + /// \code
1.698 + /// int count=0;
1.699 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.700 + /// \endcode
1.701 +
1.702 + class OutEdgeIt : public Edge {
1.703 + public:
1.704 + /// Default constructor
1.705 +
1.706 + /// @warning The default constructor sets the iterator
1.707 + /// to an undefined value.
1.708 + OutEdgeIt() { }
1.709 + /// Copy constructor.
1.710 +
1.711 + /// Copy constructor.
1.712 + ///
1.713 + OutEdgeIt(const OutEdgeIt&) { }
1.714 + /// Initialize the iterator to be invalid.
1.715 +
1.716 + /// Initialize the iterator to be invalid.
1.717 + ///
1.718 + OutEdgeIt(Invalid) { }
1.719 + /// This constructor sets the iterator to first outgoing edge.
1.720 +
1.721 + /// This constructor set the iterator to the first outgoing edge of
1.722 + /// node
1.723 + ///@param n the node
1.724 + ///@param g the graph
1.725 + OutEdgeIt(const StaticGraph& g, const Node& n) { }
1.726 + /// Edge -> OutEdgeIt conversion
1.727 +
1.728 + /// Sets the iterator to the value of the trivial iterator \c e.
1.729 + /// This feature necessitates that each time we
1.730 + /// iterate the edge-set, the iteration order is the same.
1.731 + OutEdgeIt(const StaticGraph& g, const Edge& e) { }
1.732 + ///Next outgoing edge
1.733 +
1.734 + /// Assign the iterator to the next
1.735 + /// outgoing edge of the corresponding node.
1.736 + OutEdgeIt& operator++() { return *this; }
1.737 + };
1.738 +
1.739 + /// This iterator goes trough the incoming edges of a node.
1.740 +
1.741 + /// This iterator goes trough the \e incoming edges of a certain node
1.742 + /// of a graph.
1.743 + /// Its usage is quite simple, for example you can count the number
1.744 + /// of outgoing edges of a node \c n
1.745 + /// in graph \c g of type \c Graph as follows.
1.746 + /// \code
1.747 + /// int count=0;
1.748 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.749 + /// \endcode
1.750 +
1.751 + class InEdgeIt : public Edge {
1.752 + public:
1.753 + /// Default constructor
1.754 +
1.755 + /// @warning The default constructor sets the iterator
1.756 + /// to an undefined value.
1.757 + InEdgeIt() { }
1.758 + /// Copy constructor.
1.759 +
1.760 + /// Copy constructor.
1.761 + ///
1.762 + InEdgeIt(const InEdgeIt&) { }
1.763 + /// Initialize the iterator to be invalid.
1.764 +
1.765 + /// Initialize the iterator to be invalid.
1.766 + ///
1.767 + InEdgeIt(Invalid) { }
1.768 + /// This constructor sets the iterator to first incoming edge.
1.769 +
1.770 + /// This constructor set the iterator to the first incoming edge of
1.771 + /// node
1.772 + ///@param n the node
1.773 + ///@param g the graph
1.774 + InEdgeIt(const StaticGraph& g, const Node& n) { }
1.775 + /// Edge -> InEdgeIt conversion
1.776 +
1.777 + /// Sets the iterator to the value of the trivial iterator \c e.
1.778 + /// This feature necessitates that each time we
1.779 + /// iterate the edge-set, the iteration order is the same.
1.780 + InEdgeIt(const StaticGraph& g, const Edge& n) { }
1.781 + /// Next incoming edge
1.782 +
1.783 + /// Assign the iterator to the next inedge of the corresponding node.
1.784 + ///
1.785 + InEdgeIt& operator++() { return *this; }
1.786 + };
1.787 + /// This iterator goes through each edge.
1.788 +
1.789 + /// This iterator goes through each edge of a graph.
1.790 + /// Its usage is quite simple, for example you can count the number
1.791 + /// of edges in a graph \c g of type \c Graph as follows:
1.792 + /// \code
1.793 + /// int count=0;
1.794 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.795 + /// \endcode
1.796 + class EdgeIt : public Edge {
1.797 + public:
1.798 + /// Default constructor
1.799 +
1.800 + /// @warning The default constructor sets the iterator
1.801 + /// to an undefined value.
1.802 + EdgeIt() { }
1.803 + /// Copy constructor.
1.804 +
1.805 + /// Copy constructor.
1.806 + ///
1.807 + EdgeIt(const EdgeIt&) { }
1.808 + /// Initialize the iterator to be invalid.
1.809 +
1.810 + /// Initialize the iterator to be invalid.
1.811 + ///
1.812 + EdgeIt(Invalid) { }
1.813 + /// This constructor sets the iterator to first edge.
1.814 +
1.815 + /// This constructor set the iterator to the first edge of
1.816 + /// node
1.817 + ///@param g the graph
1.818 + EdgeIt(const StaticGraph& g) { }
1.819 + /// Edge -> EdgeIt conversion
1.820 +
1.821 + /// Sets the iterator to the value of the trivial iterator \c e.
1.822 + /// This feature necessitates that each time we
1.823 + /// iterate the edge-set, the iteration order is the same.
1.824 + EdgeIt(const StaticGraph&, const Edge&) { }
1.825 + ///Next edge
1.826 +
1.827 + /// Assign the iterator to the next
1.828 + /// edge of the corresponding node.
1.829 + EdgeIt& operator++() { return *this; }
1.830 + };
1.831 + ///Gives back the target node of an edge.
1.832 +
1.833 + ///Gives back the target node of an edge.
1.834 + ///
1.835 + Node target(Edge) const { return INVALID; }
1.836 + ///Gives back the source node of an edge.
1.837 +
1.838 + ///Gives back the source node of an edge.
1.839 + ///
1.840 + Node source(Edge) const { return INVALID; }
1.841 + /// Read write map of the nodes to type \c T.
1.842 +
1.843 + /// \ingroup concept
1.844 + /// ReadWrite map of the nodes to type \c T.
1.845 + /// \sa Reference
1.846 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.847 + /// needs some extra attention!
1.848 + template<class T>
1.849 + class NodeMap : public ReadWriteMap< Node, T >
1.850 + {
1.851 + public:
1.852 +
1.853 + ///\e
1.854 + NodeMap(const StaticGraph&) { }
1.855 + ///\e
1.856 + NodeMap(const StaticGraph&, T) { }
1.857 +
1.858 + ///Copy constructor
1.859 + NodeMap(const NodeMap&) { }
1.860 + ///Assignment operator
1.861 + NodeMap& operator=(const NodeMap&) { return *this; }
1.862 + // \todo fix this concept
1.863 + };
1.864 +
1.865 + /// Read write map of the edges to type \c T.
1.866 +
1.867 + /// \ingroup concept
1.868 + ///Reference map of the edges to type \c T.
1.869 + /// \sa Reference
1.870 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.871 + /// needs some extra attention!
1.872 + template<class T>
1.873 + class EdgeMap : public ReadWriteMap<Edge,T>
1.874 + {
1.875 + public:
1.876 +
1.877 + ///\e
1.878 + EdgeMap(const StaticGraph&) { }
1.879 + ///\e
1.880 + EdgeMap(const StaticGraph&, T) { }
1.881 + ///Copy constructor
1.882 + EdgeMap(const EdgeMap&) { }
1.883 + ///Assignment operator
1.884 + EdgeMap& operator=(const EdgeMap&) { return *this; }
1.885 + // \todo fix this concept
1.886 + };
1.887 +
1.888 + template <typename _Graph>
1.889 + struct Constraints : public _StaticGraph::Constraints<_Graph> {};
1.890 +
1.891 + };
1.892 +
1.893 + /// An empty non-static graph class.
1.894 +
1.895 + /// This class provides everything that \ref StaticGraph
1.896 + /// with additional functionality which enables to build a
1.897 + /// graph from scratch.
1.898 + class ExtendableGraph : public StaticGraph
1.899 + {
1.900 + public:
1.901 + /// Defalult constructor.
1.902 +
1.903 + /// Defalult constructor.
1.904 + ///
1.905 + ExtendableGraph() { }
1.906 + ///Add a new node to the graph.
1.907 +
1.908 + /// \return the new node.
1.909 + ///
1.910 + Node addNode() { return INVALID; }
1.911 + ///Add a new edge to the graph.
1.912 +
1.913 + ///Add a new edge to the graph with source node \c s
1.914 + ///and target node \c t.
1.915 + ///\return the new edge.
1.916 + Edge addEdge(Node s, Node t) { return INVALID; }
1.917 +
1.918 + /// Resets the graph.
1.919 +
1.920 + /// This function deletes all edges and nodes of the graph.
1.921 + /// It also frees the memory allocated to store them.
1.922 + /// \todo It might belong to \ref ErasableGraph.
1.923 + void clear() { }
1.924 +
1.925 + template <typename _Graph>
1.926 + struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
1.927 +
1.928 + };
1.929 +
1.930 + /// An empty erasable graph class.
1.931 +
1.932 + /// This class is an extension of \ref ExtendableGraph. It also makes it
1.933 + /// possible to erase edges or nodes.
1.934 + class ErasableGraph : public ExtendableGraph
1.935 + {
1.936 + public:
1.937 + /// Defalult constructor.
1.938 +
1.939 + /// Defalult constructor.
1.940 + ///
1.941 + ErasableGraph() { }
1.942 + /// Deletes a node.
1.943 +
1.944 + /// Deletes node \c n node.
1.945 + ///
1.946 + void erase(Node n) { }
1.947 + /// Deletes an edge.
1.948 +
1.949 + /// Deletes edge \c e edge.
1.950 + ///
1.951 + void erase(Edge e) { }
1.952 +
1.953 + template <typename _Graph>
1.954 + struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
1.955 +
1.956 + };
1.957 +
1.958 +
1.959 + /************* New GraphBase stuff **************/
1.960 +
1.961 +
1.962 +// /// A minimal GraphBase concept
1.963 +
1.964 +// /// This class describes a minimal concept which can be extended to a
1.965 +// /// full-featured graph with \ref GraphFactory.
1.966 +// class GraphBase {
1.967 +// public:
1.968 +
1.969 +// GraphBase() {}
1.970 +
1.971 +// /// \bug Should we demand that Node and Edge be subclasses of the
1.972 +// /// Graph class???
1.973 +
1.974 +// typedef GraphItem<'n'> Node;
1.975 +// typedef GraphItem<'e'> Edge;
1.976 +
1.977 +// // class Node : public BaseGraphItem<'n'> {};
1.978 +// // class Edge : public BaseGraphItem<'e'> {};
1.979 +
1.980 +// // Graph operation
1.981 +// void firstNode(Node &n) const { }
1.982 +// void firstEdge(Edge &e) const { }
1.983 +
1.984 +// void firstOutEdge(Edge &e, Node) const { }
1.985 +// void firstInEdge(Edge &e, Node) const { }
1.986 +
1.987 +// void nextNode(Node &n) const { }
1.988 +// void nextEdge(Edge &e) const { }
1.989 +
1.990 +
1.991 +// // Question: isn't it reasonable if this methods have a Node
1.992 +// // parameter? Like this:
1.993 +// // Edge& nextOut(Edge &e, Node) const { return e; }
1.994 +// void nextOutEdge(Edge &e) const { }
1.995 +// void nextInEdge(Edge &e) const { }
1.996 +
1.997 +// Node target(Edge) const { return Node(); }
1.998 +// Node source(Edge) const { return Node(); }
1.999 +
1.1000 +
1.1001 +// // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
1.1002 +// // concept?
1.1003 +
1.1004 +
1.1005 +// // Maps.
1.1006 +// //
1.1007 +// // We need a special slimer concept which does not provide maps (it
1.1008 +// // wouldn't be strictly slimer, cause for map-factory id() & friends
1.1009 +// // a required...)
1.1010 +
1.1011 +// template<typename T>
1.1012 +// class NodeMap : public GraphMap<GraphBase, Node, T> {};
1.1013 +
1.1014 +// template<typename T>
1.1015 +// class EdgeMap : public GraphMap<GraphBase, Node, T> {};
1.1016 +// };
1.1017 +
1.1018 // @}
1.1019 } //namespace concept
1.1020 } //namespace lemon
2.1 --- a/src/lemon/concept/graph_component.h Mon Feb 07 10:50:05 2005 +0000
2.2 +++ b/src/lemon/concept/graph_component.h Mon Feb 07 11:28:37 2005 +0000
2.3 @@ -108,7 +108,7 @@
2.4 // b = (ia == ib) && (ia != ib) && (ia < ib);
2.5 b = (ia == ib) && (ia != ib);
2.6 b = (ia == INVALID) && (ib != INVALID);
2.7 - b = (ia < ib);
2.8 + // b = (ia < ib);
2.9 }
2.10
2.11 const _GraphItem &ia;