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