1.1 --- a/lemon/concept/bpugraph.h Tue Oct 24 16:49:41 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1020 +0,0 @@
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/concept/graph_components.h>
1.31 -
1.32 -#include <lemon/concept/graph.h>
1.33 -#include <lemon/concept/ugraph.h>
1.34 -
1.35 -#include <lemon/bits/utility.h>
1.36 -
1.37 -namespace lemon {
1.38 - namespace concept {
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::concept::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