1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concepts/bpugraph.h Tue Oct 24 17:19:16 2006 +0000
1.3 @@ -0,0 +1,1020 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +/// \ingroup graph_concepts
1.23 +/// \file
1.24 +/// \brief Undirected bipartite graphs and components of.
1.25 +
1.26 +
1.27 +#ifndef LEMON_CONCEPT_BPUGRAPH_H
1.28 +#define LEMON_CONCEPT_BPUGRAPH_H
1.29 +
1.30 +#include <lemon/concepts/graph_components.h>
1.31 +
1.32 +#include <lemon/concepts/graph.h>
1.33 +#include <lemon/concepts/ugraph.h>
1.34 +
1.35 +#include <lemon/bits/utility.h>
1.36 +
1.37 +namespace lemon {
1.38 + namespace concepts {
1.39 +
1.40 + /// \addtogroup graph_concepts
1.41 + /// @{
1.42 +
1.43 +
1.44 + /// \brief Class describing the concept of Bipartite Undirected Graphs.
1.45 + ///
1.46 + /// This class describes the common interface of all
1.47 + /// Undirected Bipartite Graphs.
1.48 + ///
1.49 + /// As all concept describing classes it provides only interface
1.50 + /// without any sensible implementation. So any algorithm for
1.51 + /// bipartite undirected graph should compile with this class, but it
1.52 + /// will not run properly, of course.
1.53 + ///
1.54 + /// In LEMON bipartite undirected graphs also fulfill the concept of
1.55 + /// the undirected graphs (\ref lemon::concepts::UGraph "UGraph Concept").
1.56 + ///
1.57 + /// You can assume that all undirected bipartite graph can be handled
1.58 + /// as an undirected graph and consequently as a static graph.
1.59 + ///
1.60 + /// The bipartite graph stores two types of nodes which are named
1.61 + /// ANode and BNode. The graph type contains two types ANode and
1.62 + /// BNode which are inherited from Node type. Moreover they have
1.63 + /// constructor which converts Node to either ANode or BNode when
1.64 + /// it is possible. Therefor everywhere the Node type can be used
1.65 + /// instead of ANode and BNode. So the usage of the ANode and
1.66 + /// BNode is not suggested.
1.67 + ///
1.68 + /// The iteration on the partition can be done with the ANodeIt and
1.69 + /// BNodeIt classes. The node map can be used to map values to the nodes
1.70 + /// and similarly we can use to map values for just the ANodes and
1.71 + /// BNodes the ANodeMap and BNodeMap template classes.
1.72 +
1.73 + class BpUGraph {
1.74 + public:
1.75 + /// \brief The undirected graph should be tagged by the
1.76 + /// UndirectedTag.
1.77 + ///
1.78 + /// The undirected graph should be tagged by the UndirectedTag. This
1.79 + /// tag helps the enable_if technics to make compile time
1.80 + /// specializations for undirected graphs.
1.81 + typedef True UndirectedTag;
1.82 +
1.83 + /// \brief The base type of node iterators,
1.84 + /// or in other words, the trivial node iterator.
1.85 + ///
1.86 + /// This is the base type of each node iterator,
1.87 + /// thus each kind of node iterator converts to this.
1.88 + /// More precisely each kind of node iterator should be inherited
1.89 + /// from the trivial node iterator. The Node class represents
1.90 + /// both of two types of nodes.
1.91 + class Node {
1.92 + public:
1.93 + /// Default constructor
1.94 +
1.95 + /// @warning The default constructor sets the iterator
1.96 + /// to an undefined value.
1.97 + Node() { }
1.98 + /// Copy constructor.
1.99 +
1.100 + /// Copy constructor.
1.101 + ///
1.102 + Node(const Node&) { }
1.103 +
1.104 + /// Invalid constructor \& conversion.
1.105 +
1.106 + /// This constructor initializes the iterator to be invalid.
1.107 + /// \sa Invalid for more details.
1.108 + Node(Invalid) { }
1.109 + /// Equality operator
1.110 +
1.111 + /// Two iterators are equal if and only if they point to the
1.112 + /// same object or both are invalid.
1.113 + bool operator==(Node) const { return true; }
1.114 +
1.115 + /// Inequality operator
1.116 +
1.117 + /// \sa operator==(Node n)
1.118 + ///
1.119 + bool operator!=(Node) const { return true; }
1.120 +
1.121 + /// Artificial ordering operator.
1.122 +
1.123 + /// To allow the use of graph descriptors as key type in std::map or
1.124 + /// similar associative container we require this.
1.125 + ///
1.126 + /// \note This operator only have to define some strict ordering of
1.127 + /// the items; this order has nothing to do with the iteration
1.128 + /// ordering of the items.
1.129 + bool operator<(Node) const { return false; }
1.130 +
1.131 + };
1.132 +
1.133 + /// \brief Helper class for ANodes.
1.134 + ///
1.135 + /// This class is just a helper class for ANodes, it is not
1.136 + /// suggested to use it directly. It can be converted easily to
1.137 + /// node and vice versa. The usage of this class is limited
1.138 + /// to use just as template parameters for special map types.
1.139 + class ANode : public Node {
1.140 + public:
1.141 + /// Default constructor
1.142 +
1.143 + /// @warning The default constructor sets the iterator
1.144 + /// to an undefined value.
1.145 + ANode() : Node() { }
1.146 + /// Copy constructor.
1.147 +
1.148 + /// Copy constructor.
1.149 + ///
1.150 + ANode(const ANode&) : Node() { }
1.151 +
1.152 + /// Construct the same node as ANode.
1.153 +
1.154 + /// Construct the same node as ANode. It may throws assertion
1.155 + /// when the given node is from the BNode set.
1.156 + ANode(const Node&) : Node() { }
1.157 +
1.158 + /// Assign node to A-node.
1.159 +
1.160 + /// Besides the core graph item functionality each node should
1.161 + /// be convertible to the represented A-node if it is it possible.
1.162 + ANode& operator=(const Node&) { return *this; }
1.163 +
1.164 + /// Invalid constructor \& conversion.
1.165 +
1.166 + /// This constructor initializes the iterator to be invalid.
1.167 + /// \sa Invalid for more details.
1.168 + ANode(Invalid) { }
1.169 + /// Equality operator
1.170 +
1.171 + /// Two iterators are equal if and only if they point to the
1.172 + /// same object or both are invalid.
1.173 + bool operator==(ANode) const { return true; }
1.174 +
1.175 + /// Inequality operator
1.176 +
1.177 + /// \sa operator==(ANode n)
1.178 + ///
1.179 + bool operator!=(ANode) const { return true; }
1.180 +
1.181 + /// Artificial ordering operator.
1.182 +
1.183 + /// To allow the use of graph descriptors as key type in std::map or
1.184 + /// similar associative container we require this.
1.185 + ///
1.186 + /// \note This operator only have to define some strict ordering of
1.187 + /// the items; this order has nothing to do with the iteration
1.188 + /// ordering of the items.
1.189 + bool operator<(ANode) const { return false; }
1.190 +
1.191 + };
1.192 +
1.193 + /// \brief Helper class for BNodes.
1.194 + ///
1.195 + /// This class is just a helper class for BNodes, it is not
1.196 + /// suggested to use it directly. It can be converted easily to
1.197 + /// node and vice versa. The usage of this class is limited
1.198 + /// to use just as template parameters for special map types.
1.199 + class BNode : public Node {
1.200 + public:
1.201 + /// Default constructor
1.202 +
1.203 + /// @warning The default constructor sets the iterator
1.204 + /// to an undefined value.
1.205 + BNode() : Node() { }
1.206 + /// Copy constructor.
1.207 +
1.208 + /// Copy constructor.
1.209 + ///
1.210 + BNode(const BNode&) : Node() { }
1.211 +
1.212 + /// Construct the same node as BNode.
1.213 +
1.214 + /// Construct the same node as BNode. It may throws assertion
1.215 + /// when the given node is from the ANode set.
1.216 + BNode(const Node&) : Node() { }
1.217 +
1.218 + /// Assign node to B-node.
1.219 +
1.220 + /// Besides the core graph item functionality each node should
1.221 + /// be convertible to the represented B-node if it is it possible.
1.222 + BNode& operator=(const Node&) { return *this; }
1.223 +
1.224 + /// Invalid constructor \& conversion.
1.225 +
1.226 + /// This constructor initializes the iterator to be invalid.
1.227 + /// \sa Invalid for more details.
1.228 + BNode(Invalid) { }
1.229 + /// Equality operator
1.230 +
1.231 + /// Two iterators are equal if and only if they point to the
1.232 + /// same object or both are invalid.
1.233 + bool operator==(BNode) const { return true; }
1.234 +
1.235 + /// Inequality operator
1.236 +
1.237 + /// \sa operator==(BNode n)
1.238 + ///
1.239 + bool operator!=(BNode) const { return true; }
1.240 +
1.241 + /// Artificial ordering operator.
1.242 +
1.243 + /// To allow the use of graph descriptors as key type in std::map or
1.244 + /// similar associative container we require this.
1.245 + ///
1.246 + /// \note This operator only have to define some strict ordering of
1.247 + /// the items; this order has nothing to do with the iteration
1.248 + /// ordering of the items.
1.249 + bool operator<(BNode) const { return false; }
1.250 +
1.251 + };
1.252 +
1.253 + /// This iterator goes through each node.
1.254 +
1.255 + /// This iterator goes through each node.
1.256 + /// Its usage is quite simple, for example you can count the number
1.257 + /// of nodes in graph \c g of type \c Graph like this:
1.258 + ///\code
1.259 + /// int count=0;
1.260 + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.261 + ///\endcode
1.262 + class NodeIt : public Node {
1.263 + public:
1.264 + /// Default constructor
1.265 +
1.266 + /// @warning The default constructor sets the iterator
1.267 + /// to an undefined value.
1.268 + NodeIt() { }
1.269 + /// Copy constructor.
1.270 +
1.271 + /// Copy constructor.
1.272 + ///
1.273 + NodeIt(const NodeIt& n) : Node(n) { }
1.274 + /// Invalid constructor \& conversion.
1.275 +
1.276 + /// Initialize the iterator to be invalid.
1.277 + /// \sa Invalid for more details.
1.278 + NodeIt(Invalid) { }
1.279 + /// Sets the iterator to the first node.
1.280 +
1.281 + /// Sets the iterator to the first node of \c g.
1.282 + ///
1.283 + NodeIt(const BpUGraph&) { }
1.284 + /// Node -> NodeIt conversion.
1.285 +
1.286 + /// Sets the iterator to the node of \c the graph pointed by
1.287 + /// the trivial iterator.
1.288 + /// This feature necessitates that each time we
1.289 + /// iterate the edge-set, the iteration order is the same.
1.290 + NodeIt(const BpUGraph&, const Node&) { }
1.291 + /// Next node.
1.292 +
1.293 + /// Assign the iterator to the next node.
1.294 + ///
1.295 + NodeIt& operator++() { return *this; }
1.296 + };
1.297 +
1.298 + /// This iterator goes through each ANode.
1.299 +
1.300 + /// This iterator goes through each ANode.
1.301 + /// Its usage is quite simple, for example you can count the number
1.302 + /// of nodes in graph \c g of type \c Graph like this:
1.303 + ///\code
1.304 + /// int count=0;
1.305 + /// for (Graph::ANodeIt n(g); n!=INVALID; ++n) ++count;
1.306 + ///\endcode
1.307 + class ANodeIt : public Node {
1.308 + public:
1.309 + /// Default constructor
1.310 +
1.311 + /// @warning The default constructor sets the iterator
1.312 + /// to an undefined value.
1.313 + ANodeIt() { }
1.314 + /// Copy constructor.
1.315 +
1.316 + /// Copy constructor.
1.317 + ///
1.318 + ANodeIt(const ANodeIt& n) : Node(n) { }
1.319 + /// Invalid constructor \& conversion.
1.320 +
1.321 + /// Initialize the iterator to be invalid.
1.322 + /// \sa Invalid for more details.
1.323 + ANodeIt(Invalid) { }
1.324 + /// Sets the iterator to the first node.
1.325 +
1.326 + /// Sets the iterator to the first node of \c g.
1.327 + ///
1.328 + ANodeIt(const BpUGraph&) { }
1.329 + /// Node -> ANodeIt conversion.
1.330 +
1.331 + /// Sets the iterator to the node of \c the graph pointed by
1.332 + /// the trivial iterator.
1.333 + /// This feature necessitates that each time we
1.334 + /// iterate the edge-set, the iteration order is the same.
1.335 + ANodeIt(const BpUGraph&, const Node&) { }
1.336 + /// Next node.
1.337 +
1.338 + /// Assign the iterator to the next node.
1.339 + ///
1.340 + ANodeIt& operator++() { return *this; }
1.341 + };
1.342 +
1.343 + /// This iterator goes through each BNode.
1.344 +
1.345 + /// This iterator goes through each BNode.
1.346 + /// Its usage is quite simple, for example you can count the number
1.347 + /// of nodes in graph \c g of type \c Graph like this:
1.348 + ///\code
1.349 + /// int count=0;
1.350 + /// for (Graph::BNodeIt n(g); n!=INVALID; ++n) ++count;
1.351 + ///\endcode
1.352 + class BNodeIt : public Node {
1.353 + public:
1.354 + /// Default constructor
1.355 +
1.356 + /// @warning The default constructor sets the iterator
1.357 + /// to an undefined value.
1.358 + BNodeIt() { }
1.359 + /// Copy constructor.
1.360 +
1.361 + /// Copy constructor.
1.362 + ///
1.363 + BNodeIt(const BNodeIt& n) : Node(n) { }
1.364 + /// Invalid constructor \& conversion.
1.365 +
1.366 + /// Initialize the iterator to be invalid.
1.367 + /// \sa Invalid for more details.
1.368 + BNodeIt(Invalid) { }
1.369 + /// Sets the iterator to the first node.
1.370 +
1.371 + /// Sets the iterator to the first node of \c g.
1.372 + ///
1.373 + BNodeIt(const BpUGraph&) { }
1.374 + /// Node -> BNodeIt conversion.
1.375 +
1.376 + /// Sets the iterator to the node of \c the graph pointed by
1.377 + /// the trivial iterator.
1.378 + /// This feature necessitates that each time we
1.379 + /// iterate the edge-set, the iteration order is the same.
1.380 + BNodeIt(const BpUGraph&, const Node&) { }
1.381 + /// Next node.
1.382 +
1.383 + /// Assign the iterator to the next node.
1.384 + ///
1.385 + BNodeIt& operator++() { return *this; }
1.386 + };
1.387 +
1.388 +
1.389 + /// The base type of the undirected edge iterators.
1.390 +
1.391 + /// The base type of the undirected edge iterators.
1.392 + ///
1.393 + class UEdge {
1.394 + public:
1.395 + /// Default constructor
1.396 +
1.397 + /// @warning The default constructor sets the iterator
1.398 + /// to an undefined value.
1.399 + UEdge() { }
1.400 + /// Copy constructor.
1.401 +
1.402 + /// Copy constructor.
1.403 + ///
1.404 + UEdge(const UEdge&) { }
1.405 + /// Initialize the iterator to be invalid.
1.406 +
1.407 + /// Initialize the iterator to be invalid.
1.408 + ///
1.409 + UEdge(Invalid) { }
1.410 + /// Equality operator
1.411 +
1.412 + /// Two iterators are equal if and only if they point to the
1.413 + /// same object or both are invalid.
1.414 + bool operator==(UEdge) const { return true; }
1.415 + /// Inequality operator
1.416 +
1.417 + /// \sa operator==(UEdge n)
1.418 + ///
1.419 + bool operator!=(UEdge) const { return true; }
1.420 +
1.421 + /// Artificial ordering operator.
1.422 +
1.423 + /// To allow the use of graph descriptors as key type in std::map or
1.424 + /// similar associative container we require this.
1.425 + ///
1.426 + /// \note This operator only have to define some strict ordering of
1.427 + /// the items; this order has nothing to do with the iteration
1.428 + /// ordering of the items.
1.429 + bool operator<(UEdge) const { return false; }
1.430 + };
1.431 +
1.432 + /// This iterator goes through each undirected edge.
1.433 +
1.434 + /// This iterator goes through each undirected edge of a graph.
1.435 + /// Its usage is quite simple, for example you can count the number
1.436 + /// of undirected edges in a graph \c g of type \c Graph as follows:
1.437 + ///\code
1.438 + /// int count=0;
1.439 + /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count;
1.440 + ///\endcode
1.441 + class UEdgeIt : public UEdge {
1.442 + public:
1.443 + /// Default constructor
1.444 +
1.445 + /// @warning The default constructor sets the iterator
1.446 + /// to an undefined value.
1.447 + UEdgeIt() { }
1.448 + /// Copy constructor.
1.449 +
1.450 + /// Copy constructor.
1.451 + ///
1.452 + UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
1.453 + /// Initialize the iterator to be invalid.
1.454 +
1.455 + /// Initialize the iterator to be invalid.
1.456 + ///
1.457 + UEdgeIt(Invalid) { }
1.458 + /// This constructor sets the iterator to the first undirected edge.
1.459 +
1.460 + /// This constructor sets the iterator to the first undirected edge.
1.461 + UEdgeIt(const BpUGraph&) { }
1.462 + /// UEdge -> UEdgeIt conversion
1.463 +
1.464 + /// Sets the iterator to the value of the trivial iterator.
1.465 + /// This feature necessitates that each time we
1.466 + /// iterate the undirected edge-set, the iteration order is the
1.467 + /// same.
1.468 + UEdgeIt(const BpUGraph&, const UEdge&) { }
1.469 + /// Next undirected edge
1.470 +
1.471 + /// Assign the iterator to the next undirected edge.
1.472 + UEdgeIt& operator++() { return *this; }
1.473 + };
1.474 +
1.475 + /// \brief This iterator goes trough the incident undirected
1.476 + /// edges of a node.
1.477 + ///
1.478 + /// This iterator goes trough the incident undirected edges
1.479 + /// of a certain node
1.480 + /// of a graph.
1.481 + /// Its usage is quite simple, for example you can compute the
1.482 + /// degree (i.e. count the number
1.483 + /// of incident edges of a node \c n
1.484 + /// in graph \c g of type \c Graph as follows.
1.485 + ///\code
1.486 + /// int count=0;
1.487 + /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.488 + ///\endcode
1.489 + class IncEdgeIt : public UEdge {
1.490 + public:
1.491 + /// Default constructor
1.492 +
1.493 + /// @warning The default constructor sets the iterator
1.494 + /// to an undefined value.
1.495 + IncEdgeIt() { }
1.496 + /// Copy constructor.
1.497 +
1.498 + /// Copy constructor.
1.499 + ///
1.500 + IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { }
1.501 + /// Initialize the iterator to be invalid.
1.502 +
1.503 + /// Initialize the iterator to be invalid.
1.504 + ///
1.505 + IncEdgeIt(Invalid) { }
1.506 + /// This constructor sets the iterator to first incident edge.
1.507 +
1.508 + /// This constructor set the iterator to the first incident edge of
1.509 + /// the node.
1.510 + IncEdgeIt(const BpUGraph&, const Node&) { }
1.511 + /// UEdge -> IncEdgeIt conversion
1.512 +
1.513 + /// Sets the iterator to the value of the trivial iterator \c e.
1.514 + /// This feature necessitates that each time we
1.515 + /// iterate the edge-set, the iteration order is the same.
1.516 + IncEdgeIt(const BpUGraph&, const UEdge&) { }
1.517 + /// Next incident edge
1.518 +
1.519 + /// Assign the iterator to the next incident edge
1.520 + /// of the corresponding node.
1.521 + IncEdgeIt& operator++() { return *this; }
1.522 + };
1.523 +
1.524 + /// The directed edge type.
1.525 +
1.526 + /// The directed edge type. It can be converted to the
1.527 + /// undirected edge.
1.528 + class Edge : public UEdge {
1.529 + public:
1.530 + /// Default constructor
1.531 +
1.532 + /// @warning The default constructor sets the iterator
1.533 + /// to an undefined value.
1.534 + Edge() { }
1.535 + /// Copy constructor.
1.536 +
1.537 + /// Copy constructor.
1.538 + ///
1.539 + Edge(const Edge& e) : UEdge(e) { }
1.540 + /// Initialize the iterator to be invalid.
1.541 +
1.542 + /// Initialize the iterator to be invalid.
1.543 + ///
1.544 + Edge(Invalid) { }
1.545 + /// Equality operator
1.546 +
1.547 + /// Two iterators are equal if and only if they point to the
1.548 + /// same object or both are invalid.
1.549 + bool operator==(Edge) const { return true; }
1.550 + /// Inequality operator
1.551 +
1.552 + /// \sa operator==(Edge n)
1.553 + ///
1.554 + bool operator!=(Edge) const { return true; }
1.555 +
1.556 + /// Artificial ordering operator.
1.557 +
1.558 + /// To allow the use of graph descriptors as key type in std::map or
1.559 + /// similar associative container we require this.
1.560 + ///
1.561 + /// \note This operator only have to define some strict ordering of
1.562 + /// the items; this order has nothing to do with the iteration
1.563 + /// ordering of the items.
1.564 + bool operator<(Edge) const { return false; }
1.565 +
1.566 + };
1.567 + /// This iterator goes through each directed edge.
1.568 +
1.569 + /// This iterator goes through each edge of a graph.
1.570 + /// Its usage is quite simple, for example you can count the number
1.571 + /// of edges in a graph \c g of type \c Graph as follows:
1.572 + ///\code
1.573 + /// int count=0;
1.574 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.575 + ///\endcode
1.576 + class EdgeIt : public Edge {
1.577 + public:
1.578 + /// Default constructor
1.579 +
1.580 + /// @warning The default constructor sets the iterator
1.581 + /// to an undefined value.
1.582 + EdgeIt() { }
1.583 + /// Copy constructor.
1.584 +
1.585 + /// Copy constructor.
1.586 + ///
1.587 + EdgeIt(const EdgeIt& e) : Edge(e) { }
1.588 + /// Initialize the iterator to be invalid.
1.589 +
1.590 + /// Initialize the iterator to be invalid.
1.591 + ///
1.592 + EdgeIt(Invalid) { }
1.593 + /// This constructor sets the iterator to the first edge.
1.594 +
1.595 + /// This constructor sets the iterator to the first edge of \c g.
1.596 + ///@param g the graph
1.597 + EdgeIt(const BpUGraph &g) { ignore_unused_variable_warning(g); }
1.598 + /// Edge -> EdgeIt conversion
1.599 +
1.600 + /// Sets the iterator to the value of the trivial iterator \c e.
1.601 + /// This feature necessitates that each time we
1.602 + /// iterate the edge-set, the iteration order is the same.
1.603 + EdgeIt(const BpUGraph&, const Edge&) { }
1.604 + ///Next edge
1.605 +
1.606 + /// Assign the iterator to the next edge.
1.607 + EdgeIt& operator++() { return *this; }
1.608 + };
1.609 +
1.610 + /// This iterator goes trough the outgoing directed edges of a node.
1.611 +
1.612 + /// This iterator goes trough the \e outgoing edges of a certain node
1.613 + /// of a graph.
1.614 + /// Its usage is quite simple, for example you can count the number
1.615 + /// of outgoing edges of a node \c n
1.616 + /// in graph \c g of type \c Graph as follows.
1.617 + ///\code
1.618 + /// int count=0;
1.619 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.620 + ///\endcode
1.621 +
1.622 + class OutEdgeIt : public Edge {
1.623 + public:
1.624 + /// Default constructor
1.625 +
1.626 + /// @warning The default constructor sets the iterator
1.627 + /// to an undefined value.
1.628 + OutEdgeIt() { }
1.629 + /// Copy constructor.
1.630 +
1.631 + /// Copy constructor.
1.632 + ///
1.633 + OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
1.634 + /// Initialize the iterator to be invalid.
1.635 +
1.636 + /// Initialize the iterator to be invalid.
1.637 + ///
1.638 + OutEdgeIt(Invalid) { }
1.639 + /// This constructor sets the iterator to the first outgoing edge.
1.640 +
1.641 + /// This constructor sets the iterator to the first outgoing edge of
1.642 + /// the node.
1.643 + ///@param n the node
1.644 + ///@param g the graph
1.645 + OutEdgeIt(const BpUGraph& n, const Node& g) {
1.646 + ignore_unused_variable_warning(n);
1.647 + ignore_unused_variable_warning(g);
1.648 + }
1.649 + /// Edge -> OutEdgeIt conversion
1.650 +
1.651 + /// Sets the iterator to the value of the trivial iterator.
1.652 + /// This feature necessitates that each time we
1.653 + /// iterate the edge-set, the iteration order is the same.
1.654 + OutEdgeIt(const BpUGraph&, const Edge&) { }
1.655 + ///Next outgoing edge
1.656 +
1.657 + /// Assign the iterator to the next
1.658 + /// outgoing edge of the corresponding node.
1.659 + OutEdgeIt& operator++() { return *this; }
1.660 + };
1.661 +
1.662 + /// This iterator goes trough the incoming directed edges of a node.
1.663 +
1.664 + /// This iterator goes trough the \e incoming edges of a certain node
1.665 + /// of a graph.
1.666 + /// Its usage is quite simple, for example you can count the number
1.667 + /// of outgoing edges of a node \c n
1.668 + /// in graph \c g of type \c Graph as follows.
1.669 + ///\code
1.670 + /// int count=0;
1.671 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.672 + ///\endcode
1.673 +
1.674 + class InEdgeIt : public Edge {
1.675 + public:
1.676 + /// Default constructor
1.677 +
1.678 + /// @warning The default constructor sets the iterator
1.679 + /// to an undefined value.
1.680 + InEdgeIt() { }
1.681 + /// Copy constructor.
1.682 +
1.683 + /// Copy constructor.
1.684 + ///
1.685 + InEdgeIt(const InEdgeIt& e) : Edge(e) { }
1.686 + /// Initialize the iterator to be invalid.
1.687 +
1.688 + /// Initialize the iterator to be invalid.
1.689 + ///
1.690 + InEdgeIt(Invalid) { }
1.691 + /// This constructor sets the iterator to first incoming edge.
1.692 +
1.693 + /// This constructor set the iterator to the first incoming edge of
1.694 + /// the node.
1.695 + ///@param n the node
1.696 + ///@param g the graph
1.697 + InEdgeIt(const BpUGraph& g, const Node& n) {
1.698 + ignore_unused_variable_warning(n);
1.699 + ignore_unused_variable_warning(g);
1.700 + }
1.701 + /// Edge -> InEdgeIt conversion
1.702 +
1.703 + /// Sets the iterator to the value of the trivial iterator \c e.
1.704 + /// This feature necessitates that each time we
1.705 + /// iterate the edge-set, the iteration order is the same.
1.706 + InEdgeIt(const BpUGraph&, const Edge&) { }
1.707 + /// Next incoming edge
1.708 +
1.709 + /// Assign the iterator to the next inedge of the corresponding node.
1.710 + ///
1.711 + InEdgeIt& operator++() { return *this; }
1.712 + };
1.713 +
1.714 + /// \brief Read write map of the nodes to type \c T.
1.715 + ///
1.716 + /// ReadWrite map of the nodes to type \c T.
1.717 + /// \sa Reference
1.718 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.719 + /// needs some extra attention!
1.720 + /// \todo Wrong documentation
1.721 + template<class T>
1.722 + class NodeMap : public ReadWriteMap< Node, T >
1.723 + {
1.724 + public:
1.725 +
1.726 + ///\e
1.727 + NodeMap(const BpUGraph&) { }
1.728 + ///\e
1.729 + NodeMap(const BpUGraph&, T) { }
1.730 +
1.731 + ///Copy constructor
1.732 + NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.733 + ///Assignment operator
1.734 + NodeMap& operator=(const NodeMap&) { return *this; }
1.735 + ///Assignment operator
1.736 + template <typename CMap>
1.737 + NodeMap& operator=(const CMap&) {
1.738 + checkConcept<ReadMap<Node, T>, CMap>();
1.739 + return *this;
1.740 + }
1.741 + };
1.742 +
1.743 + /// \brief Read write map of the ANodes to type \c T.
1.744 + ///
1.745 + /// ReadWrite map of the ANodes to type \c T.
1.746 + /// \sa Reference
1.747 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.748 + /// needs some extra attention!
1.749 + /// \todo Wrong documentation
1.750 + template<class T>
1.751 + class ANodeMap : public ReadWriteMap< Node, T >
1.752 + {
1.753 + public:
1.754 +
1.755 + ///\e
1.756 + ANodeMap(const BpUGraph&) { }
1.757 + ///\e
1.758 + ANodeMap(const BpUGraph&, T) { }
1.759 +
1.760 + ///Copy constructor
1.761 + ANodeMap(const ANodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.762 + ///Assignment operator
1.763 + ANodeMap& operator=(const ANodeMap&) { return *this; }
1.764 + ///Assignment operator
1.765 + template <typename CMap>
1.766 + ANodeMap& operator=(const CMap&) {
1.767 + checkConcept<ReadMap<Node, T>, CMap>();
1.768 + return *this;
1.769 + }
1.770 + };
1.771 +
1.772 + /// \brief Read write map of the BNodes to type \c T.
1.773 + ///
1.774 + /// ReadWrite map of the BNodes to type \c T.
1.775 + /// \sa Reference
1.776 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.777 + /// needs some extra attention!
1.778 + /// \todo Wrong documentation
1.779 + template<class T>
1.780 + class BNodeMap : public ReadWriteMap< Node, T >
1.781 + {
1.782 + public:
1.783 +
1.784 + ///\e
1.785 + BNodeMap(const BpUGraph&) { }
1.786 + ///\e
1.787 + BNodeMap(const BpUGraph&, T) { }
1.788 +
1.789 + ///Copy constructor
1.790 + BNodeMap(const BNodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.791 + ///Assignment operator
1.792 + BNodeMap& operator=(const BNodeMap&) { return *this; }
1.793 + ///Assignment operator
1.794 + template <typename CMap>
1.795 + BNodeMap& operator=(const CMap&) {
1.796 + checkConcept<ReadMap<Node, T>, CMap>();
1.797 + return *this;
1.798 + }
1.799 + };
1.800 +
1.801 + /// \brief Read write map of the directed edges to type \c T.
1.802 + ///
1.803 + /// Reference map of the directed edges to type \c T.
1.804 + /// \sa Reference
1.805 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.806 + /// needs some extra attention!
1.807 + /// \todo Wrong documentation
1.808 + template<class T>
1.809 + class EdgeMap : public ReadWriteMap<Edge,T>
1.810 + {
1.811 + public:
1.812 +
1.813 + ///\e
1.814 + EdgeMap(const BpUGraph&) { }
1.815 + ///\e
1.816 + EdgeMap(const BpUGraph&, T) { }
1.817 + ///Copy constructor
1.818 + EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
1.819 + ///Assignment operator
1.820 + EdgeMap& operator=(const EdgeMap&) { return *this; }
1.821 + ///Assignment operator
1.822 + template <typename CMap>
1.823 + EdgeMap& operator=(const CMap&) {
1.824 + checkConcept<ReadMap<Edge, T>, CMap>();
1.825 + return *this;
1.826 + }
1.827 + };
1.828 +
1.829 + /// Read write map of the undirected edges to type \c T.
1.830 +
1.831 + /// Reference map of the edges to type \c T.
1.832 + /// \sa Reference
1.833 + /// \warning Making maps that can handle bool type (UEdgeMap<bool>)
1.834 + /// needs some extra attention!
1.835 + /// \todo Wrong documentation
1.836 + template<class T>
1.837 + class UEdgeMap : public ReadWriteMap<UEdge,T>
1.838 + {
1.839 + public:
1.840 +
1.841 + ///\e
1.842 + UEdgeMap(const BpUGraph&) { }
1.843 + ///\e
1.844 + UEdgeMap(const BpUGraph&, T) { }
1.845 + ///Copy constructor
1.846 + UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
1.847 + ///Assignment operator
1.848 + UEdgeMap &operator=(const UEdgeMap&) { return *this; }
1.849 + ///Assignment operator
1.850 + template <typename CMap>
1.851 + UEdgeMap& operator=(const CMap&) {
1.852 + checkConcept<ReadMap<UEdge, T>, CMap>();
1.853 + return *this;
1.854 + }
1.855 + };
1.856 +
1.857 + /// \brief Direct the given undirected edge.
1.858 + ///
1.859 + /// Direct the given undirected edge. The returned edge source
1.860 + /// will be the given node.
1.861 + Edge direct(const UEdge&, const Node&) const {
1.862 + return INVALID;
1.863 + }
1.864 +
1.865 + /// \brief Direct the given undirected edge.
1.866 + ///
1.867 + /// Direct the given undirected edge. The returned edge
1.868 + /// represents the given undireted edge and the direction comes
1.869 + /// from the given bool. The source of the undirected edge and
1.870 + /// the directed edge is the same when the given bool is true.
1.871 + Edge direct(const UEdge&, bool) const {
1.872 + return INVALID;
1.873 + }
1.874 +
1.875 + /// \brief Returns true when the given node is an ANode.
1.876 + ///
1.877 + /// Returns true when the given node is an ANode.
1.878 + bool aNode(Node) const { return true;}
1.879 +
1.880 + /// \brief Returns true when the given node is an BNode.
1.881 + ///
1.882 + /// Returns true when the given node is an BNode.
1.883 + bool bNode(Node) const { return true;}
1.884 +
1.885 + /// \brief Returns the edge's end node which is in the ANode set.
1.886 + ///
1.887 + /// Returns the edge's end node which is in the ANode set.
1.888 + Node aNode(UEdge) const { return INVALID;}
1.889 +
1.890 + /// \brief Returns the edge's end node which is in the BNode set.
1.891 + ///
1.892 + /// Returns the edge's end node which is in the BNode set.
1.893 + Node bNode(UEdge) const { return INVALID;}
1.894 +
1.895 + /// \brief Returns true if the edge has default orientation.
1.896 + ///
1.897 + /// Returns whether the given directed edge is same orientation as
1.898 + /// the corresponding undirected edge's default orientation.
1.899 + bool direction(Edge) const { return true; }
1.900 +
1.901 + /// \brief Returns the opposite directed edge.
1.902 + ///
1.903 + /// Returns the opposite directed edge.
1.904 + Edge oppositeEdge(Edge) const { return INVALID; }
1.905 +
1.906 + /// \brief Opposite node on an edge
1.907 + ///
1.908 + /// \return the opposite of the given Node on the given UEdge
1.909 + Node oppositeNode(Node, UEdge) const { return INVALID; }
1.910 +
1.911 + /// \brief First node of the undirected edge.
1.912 + ///
1.913 + /// \return the first node of the given UEdge.
1.914 + ///
1.915 + /// Naturally undirected edges don't have direction and thus
1.916 + /// don't have source and target node. But we use these two methods
1.917 + /// to query the two endnodes of the edge. The direction of the edge
1.918 + /// which arises this way is called the inherent direction of the
1.919 + /// undirected edge, and is used to define the "default" direction
1.920 + /// of the directed versions of the edges.
1.921 + /// \sa direction
1.922 + Node source(UEdge) const { return INVALID; }
1.923 +
1.924 + /// \brief Second node of the undirected edge.
1.925 + Node target(UEdge) const { return INVALID; }
1.926 +
1.927 + /// \brief Source node of the directed edge.
1.928 + Node source(Edge) const { return INVALID; }
1.929 +
1.930 + /// \brief Target node of the directed edge.
1.931 + Node target(Edge) const { return INVALID; }
1.932 +
1.933 + /// \brief Base node of the iterator
1.934 + ///
1.935 + /// Returns the base node (the source in this case) of the iterator
1.936 + Node baseNode(OutEdgeIt e) const {
1.937 + return source(e);
1.938 + }
1.939 +
1.940 + /// \brief Running node of the iterator
1.941 + ///
1.942 + /// Returns the running node (the target in this case) of the
1.943 + /// iterator
1.944 + Node runningNode(OutEdgeIt e) const {
1.945 + return target(e);
1.946 + }
1.947 +
1.948 + /// \brief Base node of the iterator
1.949 + ///
1.950 + /// Returns the base node (the target in this case) of the iterator
1.951 + Node baseNode(InEdgeIt e) const {
1.952 + return target(e);
1.953 + }
1.954 + /// \brief Running node of the iterator
1.955 + ///
1.956 + /// Returns the running node (the source in this case) of the
1.957 + /// iterator
1.958 + Node runningNode(InEdgeIt e) const {
1.959 + return source(e);
1.960 + }
1.961 +
1.962 + /// \brief Base node of the iterator
1.963 + ///
1.964 + /// Returns the base node of the iterator
1.965 + Node baseNode(IncEdgeIt) const {
1.966 + return INVALID;
1.967 + }
1.968 +
1.969 + /// \brief Running node of the iterator
1.970 + ///
1.971 + /// Returns the running node of the iterator
1.972 + Node runningNode(IncEdgeIt) const {
1.973 + return INVALID;
1.974 + }
1.975 +
1.976 + void first(Node&) const {}
1.977 + void next(Node&) const {}
1.978 +
1.979 + void first(Edge&) const {}
1.980 + void next(Edge&) const {}
1.981 +
1.982 + void first(UEdge&) const {}
1.983 + void next(UEdge&) const {}
1.984 +
1.985 + void firstANode(Node&) const {}
1.986 + void nextANode(Node&) const {}
1.987 +
1.988 + void firstBNode(Node&) const {}
1.989 + void nextBNode(Node&) const {}
1.990 +
1.991 + void firstIn(Edge&, const Node&) const {}
1.992 + void nextIn(Edge&) const {}
1.993 +
1.994 + void firstOut(Edge&, const Node&) const {}
1.995 + void nextOut(Edge&) const {}
1.996 +
1.997 + void firstInc(UEdge &, bool &, const Node &) const {}
1.998 + void nextInc(UEdge &, bool &) const {}
1.999 +
1.1000 + void firstFromANode(UEdge&, const Node&) const {}
1.1001 + void nextFromANode(UEdge&) const {}
1.1002 +
1.1003 + void firstFromBNode(UEdge&, const Node&) const {}
1.1004 + void nextFromBNode(UEdge&) const {}
1.1005 +
1.1006 + template <typename Graph>
1.1007 + struct Constraints {
1.1008 + void constraints() {
1.1009 + checkConcept<IterableBpUGraphComponent<>, Graph>();
1.1010 + checkConcept<MappableBpUGraphComponent<>, Graph>();
1.1011 + }
1.1012 + };
1.1013 +
1.1014 + };
1.1015 +
1.1016 +
1.1017 + /// @}
1.1018 +
1.1019 + }
1.1020 +
1.1021 +}
1.1022 +
1.1023 +#endif