1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concepts/bpgraph.h Sun Nov 14 16:35:31 2010 +0100
1.3 @@ -0,0 +1,1020 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
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 The concept of undirected graphs.
1.25 +
1.26 +#ifndef LEMON_CONCEPTS_BPGRAPH_H
1.27 +#define LEMON_CONCEPTS_BPGRAPH_H
1.28 +
1.29 +#include <lemon/concepts/graph_components.h>
1.30 +#include <lemon/concepts/maps.h>
1.31 +#include <lemon/concept_check.h>
1.32 +#include <lemon/core.h>
1.33 +
1.34 +namespace lemon {
1.35 + namespace concepts {
1.36 +
1.37 + /// \ingroup graph_concepts
1.38 + ///
1.39 + /// \brief Class describing the concept of undirected bipartite graphs.
1.40 + ///
1.41 + /// This class describes the common interface of all undirected
1.42 + /// bipartite graphs.
1.43 + ///
1.44 + /// Like all concept classes, it only provides an interface
1.45 + /// without any sensible implementation. So any general algorithm for
1.46 + /// undirected bipartite graphs should compile with this class,
1.47 + /// but it will not run properly, of course.
1.48 + /// An actual graph implementation like \ref ListBpGraph or
1.49 + /// \ref SmartBpGraph may have additional functionality.
1.50 + ///
1.51 + /// The bipartite graphs also fulfill the concept of \ref Graph
1.52 + /// "undirected graphs". Bipartite graphs provide a bipartition of
1.53 + /// the node set, namely a red and blue set of the nodes. The
1.54 + /// nodes can be iterated with the RedIt and BlueIt in the two
1.55 + /// node sets. With RedMap and BlueMap values can be assigned to
1.56 + /// the nodes in the two sets.
1.57 + ///
1.58 + /// The edges of the graph cannot connect two nodes of the same
1.59 + /// set. The edges inherent orientation is from the red nodes to
1.60 + /// the blue nodes.
1.61 + ///
1.62 + /// \sa Graph
1.63 + class BpGraph {
1.64 + private:
1.65 + /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
1.66 + BpGraph(const BpGraph&) {}
1.67 + /// \brief Assignment of a graph to another one is \e not allowed.
1.68 + /// Use bpGraphCopy instead.
1.69 + void operator=(const BpGraph&) {}
1.70 +
1.71 + public:
1.72 + /// Default constructor.
1.73 + BpGraph() {}
1.74 +
1.75 + /// \brief Undirected graphs should be tagged with \c UndirectedTag.
1.76 + ///
1.77 + /// Undirected graphs should be tagged with \c UndirectedTag.
1.78 + ///
1.79 + /// This tag helps the \c enable_if technics to make compile time
1.80 + /// specializations for undirected graphs.
1.81 + typedef True UndirectedTag;
1.82 +
1.83 + /// The node type of the graph
1.84 +
1.85 + /// This class identifies a node of the graph. It also serves
1.86 + /// as a base class of the node iterators,
1.87 + /// thus they convert to this type.
1.88 + class Node {
1.89 + public:
1.90 + /// Default constructor
1.91 +
1.92 + /// Default constructor.
1.93 + /// \warning It sets the object to an undefined value.
1.94 + Node() { }
1.95 + /// Copy constructor.
1.96 +
1.97 + /// Copy constructor.
1.98 + ///
1.99 + Node(const Node&) { }
1.100 +
1.101 + /// %Invalid constructor \& conversion.
1.102 +
1.103 + /// Initializes the object to be invalid.
1.104 + /// \sa Invalid for more details.
1.105 + Node(Invalid) { }
1.106 + /// Equality operator
1.107 +
1.108 + /// Equality operator.
1.109 + ///
1.110 + /// Two iterators are equal if and only if they point to the
1.111 + /// same object or both are \c INVALID.
1.112 + bool operator==(Node) const { return true; }
1.113 +
1.114 + /// Inequality operator
1.115 +
1.116 + /// Inequality operator.
1.117 + bool operator!=(Node) const { return true; }
1.118 +
1.119 + /// Artificial ordering operator.
1.120 +
1.121 + /// Artificial ordering operator.
1.122 + ///
1.123 + /// \note This operator only has to define some strict ordering of
1.124 + /// the items; this order has nothing to do with the iteration
1.125 + /// ordering of the items.
1.126 + bool operator<(Node) const { return false; }
1.127 +
1.128 + };
1.129 +
1.130 + /// Class to represent red nodes.
1.131 +
1.132 + /// This class represents the red nodes of the graph. It does
1.133 + /// not supposed to be used directly, because the nodes can be
1.134 + /// represented as Node instances. This class can be used as
1.135 + /// template parameter for special map classes.
1.136 + class RedNode : public Node {
1.137 + public:
1.138 + /// Default constructor
1.139 +
1.140 + /// Default constructor.
1.141 + /// \warning It sets the object to an undefined value.
1.142 + RedNode() { }
1.143 + /// Copy constructor.
1.144 +
1.145 + /// Copy constructor.
1.146 + ///
1.147 + RedNode(const RedNode&) : Node() { }
1.148 +
1.149 + /// %Invalid constructor \& conversion.
1.150 +
1.151 + /// Initializes the object to be invalid.
1.152 + /// \sa Invalid for more details.
1.153 + RedNode(Invalid) { }
1.154 +
1.155 + /// Constructor for conversion from a node.
1.156 +
1.157 + /// Constructor for conversion from a node. The conversion can
1.158 + /// be invalid, since the Node can be member of the blue
1.159 + /// set.
1.160 + RedNode(const Node&) {}
1.161 + };
1.162 +
1.163 + /// Class to represent blue nodes.
1.164 +
1.165 + /// This class represents the blue nodes of the graph. It does
1.166 + /// not supposed to be used directly, because the nodes can be
1.167 + /// represented as Node instances. This class can be used as
1.168 + /// template parameter for special map classes.
1.169 + class BlueNode : public Node {
1.170 + public:
1.171 + /// Default constructor
1.172 +
1.173 + /// Default constructor.
1.174 + /// \warning It sets the object to an undefined value.
1.175 + BlueNode() { }
1.176 + /// Copy constructor.
1.177 +
1.178 + /// Copy constructor.
1.179 + ///
1.180 + BlueNode(const BlueNode&) : Node() { }
1.181 +
1.182 + /// %Invalid constructor \& conversion.
1.183 +
1.184 + /// Initializes the object to be invalid.
1.185 + /// \sa Invalid for more details.
1.186 + BlueNode(Invalid) { }
1.187 +
1.188 + /// Constructor for conversion from a node.
1.189 +
1.190 + /// Constructor for conversion from a node. The conversion can
1.191 + /// be invalid, since the Node can be member of the red
1.192 + /// set.
1.193 + BlueNode(const Node&) {}
1.194 + };
1.195 +
1.196 + /// Iterator class for the red nodes.
1.197 +
1.198 + /// This iterator goes through each red node of the graph.
1.199 + /// Its usage is quite simple, for example, you can count the number
1.200 + /// of red nodes in a graph \c g of type \c %BpGraph like this:
1.201 + ///\code
1.202 + /// int count=0;
1.203 + /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
1.204 + ///\endcode
1.205 + class RedIt : public Node {
1.206 + public:
1.207 + /// Default constructor
1.208 +
1.209 + /// Default constructor.
1.210 + /// \warning It sets the iterator to an undefined value.
1.211 + RedIt() { }
1.212 + /// Copy constructor.
1.213 +
1.214 + /// Copy constructor.
1.215 + ///
1.216 + RedIt(const RedIt& n) : Node(n) { }
1.217 + /// %Invalid constructor \& conversion.
1.218 +
1.219 + /// Initializes the iterator to be invalid.
1.220 + /// \sa Invalid for more details.
1.221 + RedIt(Invalid) { }
1.222 + /// Sets the iterator to the first red node.
1.223 +
1.224 + /// Sets the iterator to the first red node of the given
1.225 + /// digraph.
1.226 + explicit RedIt(const BpGraph&) { }
1.227 + /// Sets the iterator to the given red node.
1.228 +
1.229 + /// Sets the iterator to the given red node of the given
1.230 + /// digraph.
1.231 + RedIt(const BpGraph&, const Node&) { }
1.232 + /// Next node.
1.233 +
1.234 + /// Assign the iterator to the next red node.
1.235 + ///
1.236 + RedIt& operator++() { return *this; }
1.237 + };
1.238 +
1.239 + /// Iterator class for the blue nodes.
1.240 +
1.241 + /// This iterator goes through each blue node of the graph.
1.242 + /// Its usage is quite simple, for example, you can count the number
1.243 + /// of blue nodes in a graph \c g of type \c %BpGraph like this:
1.244 + ///\code
1.245 + /// int count=0;
1.246 + /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
1.247 + ///\endcode
1.248 + class BlueIt : public Node {
1.249 + public:
1.250 + /// Default constructor
1.251 +
1.252 + /// Default constructor.
1.253 + /// \warning It sets the iterator to an undefined value.
1.254 + BlueIt() { }
1.255 + /// Copy constructor.
1.256 +
1.257 + /// Copy constructor.
1.258 + ///
1.259 + BlueIt(const BlueIt& n) : Node(n) { }
1.260 + /// %Invalid constructor \& conversion.
1.261 +
1.262 + /// Initializes the iterator to be invalid.
1.263 + /// \sa Invalid for more details.
1.264 + BlueIt(Invalid) { }
1.265 + /// Sets the iterator to the first blue node.
1.266 +
1.267 + /// Sets the iterator to the first blue node of the given
1.268 + /// digraph.
1.269 + explicit BlueIt(const BpGraph&) { }
1.270 + /// Sets the iterator to the given blue node.
1.271 +
1.272 + /// Sets the iterator to the given blue node of the given
1.273 + /// digraph.
1.274 + BlueIt(const BpGraph&, const Node&) { }
1.275 + /// Next node.
1.276 +
1.277 + /// Assign the iterator to the next blue node.
1.278 + ///
1.279 + BlueIt& operator++() { return *this; }
1.280 + };
1.281 +
1.282 + /// Iterator class for the nodes.
1.283 +
1.284 + /// This iterator goes through each node of the graph.
1.285 + /// Its usage is quite simple, for example, you can count the number
1.286 + /// of nodes in a graph \c g of type \c %BpGraph like this:
1.287 + ///\code
1.288 + /// int count=0;
1.289 + /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.290 + ///\endcode
1.291 + class NodeIt : public Node {
1.292 + public:
1.293 + /// Default constructor
1.294 +
1.295 + /// Default constructor.
1.296 + /// \warning It sets the iterator to an undefined value.
1.297 + NodeIt() { }
1.298 + /// Copy constructor.
1.299 +
1.300 + /// Copy constructor.
1.301 + ///
1.302 + NodeIt(const NodeIt& n) : Node(n) { }
1.303 + /// %Invalid constructor \& conversion.
1.304 +
1.305 + /// Initializes the iterator to be invalid.
1.306 + /// \sa Invalid for more details.
1.307 + NodeIt(Invalid) { }
1.308 + /// Sets the iterator to the first node.
1.309 +
1.310 + /// Sets the iterator to the first node of the given digraph.
1.311 + ///
1.312 + explicit NodeIt(const BpGraph&) { }
1.313 + /// Sets the iterator to the given node.
1.314 +
1.315 + /// Sets the iterator to the given node of the given digraph.
1.316 + ///
1.317 + NodeIt(const BpGraph&, const Node&) { }
1.318 + /// Next node.
1.319 +
1.320 + /// Assign the iterator to the next node.
1.321 + ///
1.322 + NodeIt& operator++() { return *this; }
1.323 + };
1.324 +
1.325 +
1.326 + /// The edge type of the graph
1.327 +
1.328 + /// This class identifies an edge of the graph. It also serves
1.329 + /// as a base class of the edge iterators,
1.330 + /// thus they will convert to this type.
1.331 + class Edge {
1.332 + public:
1.333 + /// Default constructor
1.334 +
1.335 + /// Default constructor.
1.336 + /// \warning It sets the object to an undefined value.
1.337 + Edge() { }
1.338 + /// Copy constructor.
1.339 +
1.340 + /// Copy constructor.
1.341 + ///
1.342 + Edge(const Edge&) { }
1.343 + /// %Invalid constructor \& conversion.
1.344 +
1.345 + /// Initializes the object to be invalid.
1.346 + /// \sa Invalid for more details.
1.347 + Edge(Invalid) { }
1.348 + /// Equality operator
1.349 +
1.350 + /// Equality operator.
1.351 + ///
1.352 + /// Two iterators are equal if and only if they point to the
1.353 + /// same object or both are \c INVALID.
1.354 + bool operator==(Edge) const { return true; }
1.355 + /// Inequality operator
1.356 +
1.357 + /// Inequality operator.
1.358 + bool operator!=(Edge) const { return true; }
1.359 +
1.360 + /// Artificial ordering operator.
1.361 +
1.362 + /// Artificial ordering operator.
1.363 + ///
1.364 + /// \note This operator only has to define some strict ordering of
1.365 + /// the edges; this order has nothing to do with the iteration
1.366 + /// ordering of the edges.
1.367 + bool operator<(Edge) const { return false; }
1.368 + };
1.369 +
1.370 + /// Iterator class for the edges.
1.371 +
1.372 + /// This iterator goes through each edge of the graph.
1.373 + /// Its usage is quite simple, for example, you can count the number
1.374 + /// of edges in a graph \c g of type \c %BpGraph as follows:
1.375 + ///\code
1.376 + /// int count=0;
1.377 + /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.378 + ///\endcode
1.379 + class EdgeIt : public Edge {
1.380 + public:
1.381 + /// Default constructor
1.382 +
1.383 + /// Default constructor.
1.384 + /// \warning It sets the iterator to an undefined value.
1.385 + EdgeIt() { }
1.386 + /// Copy constructor.
1.387 +
1.388 + /// Copy constructor.
1.389 + ///
1.390 + EdgeIt(const EdgeIt& e) : Edge(e) { }
1.391 + /// %Invalid constructor \& conversion.
1.392 +
1.393 + /// Initializes the iterator to be invalid.
1.394 + /// \sa Invalid for more details.
1.395 + EdgeIt(Invalid) { }
1.396 + /// Sets the iterator to the first edge.
1.397 +
1.398 + /// Sets the iterator to the first edge of the given graph.
1.399 + ///
1.400 + explicit EdgeIt(const BpGraph&) { }
1.401 + /// Sets the iterator to the given edge.
1.402 +
1.403 + /// Sets the iterator to the given edge of the given graph.
1.404 + ///
1.405 + EdgeIt(const BpGraph&, const Edge&) { }
1.406 + /// Next edge
1.407 +
1.408 + /// Assign the iterator to the next edge.
1.409 + ///
1.410 + EdgeIt& operator++() { return *this; }
1.411 + };
1.412 +
1.413 + /// Iterator class for the incident edges of a node.
1.414 +
1.415 + /// This iterator goes trough the incident undirected edges
1.416 + /// of a certain node of a graph.
1.417 + /// Its usage is quite simple, for example, you can compute the
1.418 + /// degree (i.e. the number of incident edges) of a node \c n
1.419 + /// in a graph \c g of type \c %BpGraph as follows.
1.420 + ///
1.421 + ///\code
1.422 + /// int count=0;
1.423 + /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.424 + ///\endcode
1.425 + ///
1.426 + /// \warning Loop edges will be iterated twice.
1.427 + class IncEdgeIt : public Edge {
1.428 + public:
1.429 + /// Default constructor
1.430 +
1.431 + /// Default constructor.
1.432 + /// \warning It sets the iterator to an undefined value.
1.433 + IncEdgeIt() { }
1.434 + /// Copy constructor.
1.435 +
1.436 + /// Copy constructor.
1.437 + ///
1.438 + IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
1.439 + /// %Invalid constructor \& conversion.
1.440 +
1.441 + /// Initializes the iterator to be invalid.
1.442 + /// \sa Invalid for more details.
1.443 + IncEdgeIt(Invalid) { }
1.444 + /// Sets the iterator to the first incident edge.
1.445 +
1.446 + /// Sets the iterator to the first incident edge of the given node.
1.447 + ///
1.448 + IncEdgeIt(const BpGraph&, const Node&) { }
1.449 + /// Sets the iterator to the given edge.
1.450 +
1.451 + /// Sets the iterator to the given edge of the given graph.
1.452 + ///
1.453 + IncEdgeIt(const BpGraph&, const Edge&) { }
1.454 + /// Next incident edge
1.455 +
1.456 + /// Assign the iterator to the next incident edge
1.457 + /// of the corresponding node.
1.458 + IncEdgeIt& operator++() { return *this; }
1.459 + };
1.460 +
1.461 + /// The arc type of the graph
1.462 +
1.463 + /// This class identifies a directed arc of the graph. It also serves
1.464 + /// as a base class of the arc iterators,
1.465 + /// thus they will convert to this type.
1.466 + class Arc {
1.467 + public:
1.468 + /// Default constructor
1.469 +
1.470 + /// Default constructor.
1.471 + /// \warning It sets the object to an undefined value.
1.472 + Arc() { }
1.473 + /// Copy constructor.
1.474 +
1.475 + /// Copy constructor.
1.476 + ///
1.477 + Arc(const Arc&) { }
1.478 + /// %Invalid constructor \& conversion.
1.479 +
1.480 + /// Initializes the object to be invalid.
1.481 + /// \sa Invalid for more details.
1.482 + Arc(Invalid) { }
1.483 + /// Equality operator
1.484 +
1.485 + /// Equality operator.
1.486 + ///
1.487 + /// Two iterators are equal if and only if they point to the
1.488 + /// same object or both are \c INVALID.
1.489 + bool operator==(Arc) const { return true; }
1.490 + /// Inequality operator
1.491 +
1.492 + /// Inequality operator.
1.493 + bool operator!=(Arc) const { return true; }
1.494 +
1.495 + /// Artificial ordering operator.
1.496 +
1.497 + /// Artificial ordering operator.
1.498 + ///
1.499 + /// \note This operator only has to define some strict ordering of
1.500 + /// the arcs; this order has nothing to do with the iteration
1.501 + /// ordering of the arcs.
1.502 + bool operator<(Arc) const { return false; }
1.503 +
1.504 + /// Converison to \c Edge
1.505 +
1.506 + /// Converison to \c Edge.
1.507 + ///
1.508 + operator Edge() const { return Edge(); }
1.509 + };
1.510 +
1.511 + /// Iterator class for the arcs.
1.512 +
1.513 + /// This iterator goes through each directed arc of the graph.
1.514 + /// Its usage is quite simple, for example, you can count the number
1.515 + /// of arcs in a graph \c g of type \c %BpGraph as follows:
1.516 + ///\code
1.517 + /// int count=0;
1.518 + /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
1.519 + ///\endcode
1.520 + class ArcIt : public Arc {
1.521 + public:
1.522 + /// Default constructor
1.523 +
1.524 + /// Default constructor.
1.525 + /// \warning It sets the iterator to an undefined value.
1.526 + ArcIt() { }
1.527 + /// Copy constructor.
1.528 +
1.529 + /// Copy constructor.
1.530 + ///
1.531 + ArcIt(const ArcIt& e) : Arc(e) { }
1.532 + /// %Invalid constructor \& conversion.
1.533 +
1.534 + /// Initializes the iterator to be invalid.
1.535 + /// \sa Invalid for more details.
1.536 + ArcIt(Invalid) { }
1.537 + /// Sets the iterator to the first arc.
1.538 +
1.539 + /// Sets the iterator to the first arc of the given graph.
1.540 + ///
1.541 + explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
1.542 + /// Sets the iterator to the given arc.
1.543 +
1.544 + /// Sets the iterator to the given arc of the given graph.
1.545 + ///
1.546 + ArcIt(const BpGraph&, const Arc&) { }
1.547 + /// Next arc
1.548 +
1.549 + /// Assign the iterator to the next arc.
1.550 + ///
1.551 + ArcIt& operator++() { return *this; }
1.552 + };
1.553 +
1.554 + /// Iterator class for the outgoing arcs of a node.
1.555 +
1.556 + /// This iterator goes trough the \e outgoing directed arcs of a
1.557 + /// certain node of a graph.
1.558 + /// Its usage is quite simple, for example, you can count the number
1.559 + /// of outgoing arcs of a node \c n
1.560 + /// in a graph \c g of type \c %BpGraph as follows.
1.561 + ///\code
1.562 + /// int count=0;
1.563 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
1.564 + ///\endcode
1.565 + class OutArcIt : public Arc {
1.566 + public:
1.567 + /// Default constructor
1.568 +
1.569 + /// Default constructor.
1.570 + /// \warning It sets the iterator to an undefined value.
1.571 + OutArcIt() { }
1.572 + /// Copy constructor.
1.573 +
1.574 + /// Copy constructor.
1.575 + ///
1.576 + OutArcIt(const OutArcIt& e) : Arc(e) { }
1.577 + /// %Invalid constructor \& conversion.
1.578 +
1.579 + /// Initializes the iterator to be invalid.
1.580 + /// \sa Invalid for more details.
1.581 + OutArcIt(Invalid) { }
1.582 + /// Sets the iterator to the first outgoing arc.
1.583 +
1.584 + /// Sets the iterator to the first outgoing arc of the given node.
1.585 + ///
1.586 + OutArcIt(const BpGraph& n, const Node& g) {
1.587 + ignore_unused_variable_warning(n);
1.588 + ignore_unused_variable_warning(g);
1.589 + }
1.590 + /// Sets the iterator to the given arc.
1.591 +
1.592 + /// Sets the iterator to the given arc of the given graph.
1.593 + ///
1.594 + OutArcIt(const BpGraph&, const Arc&) { }
1.595 + /// Next outgoing arc
1.596 +
1.597 + /// Assign the iterator to the next
1.598 + /// outgoing arc of the corresponding node.
1.599 + OutArcIt& operator++() { return *this; }
1.600 + };
1.601 +
1.602 + /// Iterator class for the incoming arcs of a node.
1.603 +
1.604 + /// This iterator goes trough the \e incoming directed arcs of a
1.605 + /// certain node of a graph.
1.606 + /// Its usage is quite simple, for example, you can count the number
1.607 + /// of incoming arcs of a node \c n
1.608 + /// in a graph \c g of type \c %BpGraph as follows.
1.609 + ///\code
1.610 + /// int count=0;
1.611 + /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
1.612 + ///\endcode
1.613 + class InArcIt : public Arc {
1.614 + public:
1.615 + /// Default constructor
1.616 +
1.617 + /// Default constructor.
1.618 + /// \warning It sets the iterator to an undefined value.
1.619 + InArcIt() { }
1.620 + /// Copy constructor.
1.621 +
1.622 + /// Copy constructor.
1.623 + ///
1.624 + InArcIt(const InArcIt& e) : Arc(e) { }
1.625 + /// %Invalid constructor \& conversion.
1.626 +
1.627 + /// Initializes the iterator to be invalid.
1.628 + /// \sa Invalid for more details.
1.629 + InArcIt(Invalid) { }
1.630 + /// Sets the iterator to the first incoming arc.
1.631 +
1.632 + /// Sets the iterator to the first incoming arc of the given node.
1.633 + ///
1.634 + InArcIt(const BpGraph& g, const Node& n) {
1.635 + ignore_unused_variable_warning(n);
1.636 + ignore_unused_variable_warning(g);
1.637 + }
1.638 + /// Sets the iterator to the given arc.
1.639 +
1.640 + /// Sets the iterator to the given arc of the given graph.
1.641 + ///
1.642 + InArcIt(const BpGraph&, const Arc&) { }
1.643 + /// Next incoming arc
1.644 +
1.645 + /// Assign the iterator to the next
1.646 + /// incoming arc of the corresponding node.
1.647 + InArcIt& operator++() { return *this; }
1.648 + };
1.649 +
1.650 + /// \brief Standard graph map type for the nodes.
1.651 + ///
1.652 + /// Standard graph map type for the nodes.
1.653 + /// It conforms to the ReferenceMap concept.
1.654 + template<class T>
1.655 + class NodeMap : public ReferenceMap<Node, T, T&, const T&>
1.656 + {
1.657 + public:
1.658 +
1.659 + /// Constructor
1.660 + explicit NodeMap(const BpGraph&) { }
1.661 + /// Constructor with given initial value
1.662 + NodeMap(const BpGraph&, T) { }
1.663 +
1.664 + private:
1.665 + ///Copy constructor
1.666 + NodeMap(const NodeMap& nm) :
1.667 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.668 + ///Assignment operator
1.669 + template <typename CMap>
1.670 + NodeMap& operator=(const CMap&) {
1.671 + checkConcept<ReadMap<Node, T>, CMap>();
1.672 + return *this;
1.673 + }
1.674 + };
1.675 +
1.676 + /// \brief Standard graph map type for the red nodes.
1.677 + ///
1.678 + /// Standard graph map type for the red nodes.
1.679 + /// It conforms to the ReferenceMap concept.
1.680 + template<class T>
1.681 + class RedMap : public ReferenceMap<Node, T, T&, const T&>
1.682 + {
1.683 + public:
1.684 +
1.685 + /// Constructor
1.686 + explicit RedMap(const BpGraph&) { }
1.687 + /// Constructor with given initial value
1.688 + RedMap(const BpGraph&, T) { }
1.689 +
1.690 + private:
1.691 + ///Copy constructor
1.692 + RedMap(const RedMap& nm) :
1.693 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.694 + ///Assignment operator
1.695 + template <typename CMap>
1.696 + RedMap& operator=(const CMap&) {
1.697 + checkConcept<ReadMap<Node, T>, CMap>();
1.698 + return *this;
1.699 + }
1.700 + };
1.701 +
1.702 + /// \brief Standard graph map type for the blue nodes.
1.703 + ///
1.704 + /// Standard graph map type for the blue nodes.
1.705 + /// It conforms to the ReferenceMap concept.
1.706 + template<class T>
1.707 + class BlueMap : public ReferenceMap<Node, T, T&, const T&>
1.708 + {
1.709 + public:
1.710 +
1.711 + /// Constructor
1.712 + explicit BlueMap(const BpGraph&) { }
1.713 + /// Constructor with given initial value
1.714 + BlueMap(const BpGraph&, T) { }
1.715 +
1.716 + private:
1.717 + ///Copy constructor
1.718 + BlueMap(const BlueMap& nm) :
1.719 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.720 + ///Assignment operator
1.721 + template <typename CMap>
1.722 + BlueMap& operator=(const CMap&) {
1.723 + checkConcept<ReadMap<Node, T>, CMap>();
1.724 + return *this;
1.725 + }
1.726 + };
1.727 +
1.728 + /// \brief Standard graph map type for the arcs.
1.729 + ///
1.730 + /// Standard graph map type for the arcs.
1.731 + /// It conforms to the ReferenceMap concept.
1.732 + template<class T>
1.733 + class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
1.734 + {
1.735 + public:
1.736 +
1.737 + /// Constructor
1.738 + explicit ArcMap(const BpGraph&) { }
1.739 + /// Constructor with given initial value
1.740 + ArcMap(const BpGraph&, T) { }
1.741 +
1.742 + private:
1.743 + ///Copy constructor
1.744 + ArcMap(const ArcMap& em) :
1.745 + ReferenceMap<Arc, T, T&, const T&>(em) { }
1.746 + ///Assignment operator
1.747 + template <typename CMap>
1.748 + ArcMap& operator=(const CMap&) {
1.749 + checkConcept<ReadMap<Arc, T>, CMap>();
1.750 + return *this;
1.751 + }
1.752 + };
1.753 +
1.754 + /// \brief Standard graph map type for the edges.
1.755 + ///
1.756 + /// Standard graph map type for the edges.
1.757 + /// It conforms to the ReferenceMap concept.
1.758 + template<class T>
1.759 + class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
1.760 + {
1.761 + public:
1.762 +
1.763 + /// Constructor
1.764 + explicit EdgeMap(const BpGraph&) { }
1.765 + /// Constructor with given initial value
1.766 + EdgeMap(const BpGraph&, T) { }
1.767 +
1.768 + private:
1.769 + ///Copy constructor
1.770 + EdgeMap(const EdgeMap& em) :
1.771 + ReferenceMap<Edge, T, T&, const T&>(em) {}
1.772 + ///Assignment operator
1.773 + template <typename CMap>
1.774 + EdgeMap& operator=(const CMap&) {
1.775 + checkConcept<ReadMap<Edge, T>, CMap>();
1.776 + return *this;
1.777 + }
1.778 + };
1.779 +
1.780 + /// \brief Gives back %true for red nodes.
1.781 + ///
1.782 + /// Gives back %true for red nodes.
1.783 + bool red(const Node&) const { return true; }
1.784 +
1.785 + /// \brief Gives back %true for blue nodes.
1.786 + ///
1.787 + /// Gives back %true for blue nodes.
1.788 + bool blue(const Node&) const { return true; }
1.789 +
1.790 + /// \brief Gives back the red end node of the edge.
1.791 + ///
1.792 + /// Gives back the red end node of the edge.
1.793 + Node redNode(const Edge&) const { return Node(); }
1.794 +
1.795 + /// \brief Gives back the blue end node of the edge.
1.796 + ///
1.797 + /// Gives back the blue end node of the edge.
1.798 + Node blueNode(const Edge&) const { return Node(); }
1.799 +
1.800 + /// \brief The first node of the edge.
1.801 + ///
1.802 + /// It is a synonim for the \c redNode().
1.803 + Node u(Edge) const { return INVALID; }
1.804 +
1.805 + /// \brief The second node of the edge.
1.806 + ///
1.807 + /// It is a synonim for the \c blueNode().
1.808 + Node v(Edge) const { return INVALID; }
1.809 +
1.810 + /// \brief The source node of the arc.
1.811 + ///
1.812 + /// Returns the source node of the given arc.
1.813 + Node source(Arc) const { return INVALID; }
1.814 +
1.815 + /// \brief The target node of the arc.
1.816 + ///
1.817 + /// Returns the target node of the given arc.
1.818 + Node target(Arc) const { return INVALID; }
1.819 +
1.820 + /// \brief The ID of the node.
1.821 + ///
1.822 + /// Returns the ID of the given node.
1.823 + int id(Node) const { return -1; }
1.824 +
1.825 + /// \brief The red ID of the node.
1.826 + ///
1.827 + /// Returns the red ID of the given node.
1.828 + int redId(Node) const { return -1; }
1.829 +
1.830 + /// \brief The red ID of the node.
1.831 + ///
1.832 + /// Returns the red ID of the given node.
1.833 + int id(RedNode) const { return -1; }
1.834 +
1.835 + /// \brief The blue ID of the node.
1.836 + ///
1.837 + /// Returns the blue ID of the given node.
1.838 + int blueId(Node) const { return -1; }
1.839 +
1.840 + /// \brief The blue ID of the node.
1.841 + ///
1.842 + /// Returns the blue ID of the given node.
1.843 + int id(BlueNode) const { return -1; }
1.844 +
1.845 + /// \brief The ID of the edge.
1.846 + ///
1.847 + /// Returns the ID of the given edge.
1.848 + int id(Edge) const { return -1; }
1.849 +
1.850 + /// \brief The ID of the arc.
1.851 + ///
1.852 + /// Returns the ID of the given arc.
1.853 + int id(Arc) const { return -1; }
1.854 +
1.855 + /// \brief The node with the given ID.
1.856 + ///
1.857 + /// Returns the node with the given ID.
1.858 + /// \pre The argument should be a valid node ID in the graph.
1.859 + Node nodeFromId(int) const { return INVALID; }
1.860 +
1.861 + /// \brief The edge with the given ID.
1.862 + ///
1.863 + /// Returns the edge with the given ID.
1.864 + /// \pre The argument should be a valid edge ID in the graph.
1.865 + Edge edgeFromId(int) const { return INVALID; }
1.866 +
1.867 + /// \brief The arc with the given ID.
1.868 + ///
1.869 + /// Returns the arc with the given ID.
1.870 + /// \pre The argument should be a valid arc ID in the graph.
1.871 + Arc arcFromId(int) const { return INVALID; }
1.872 +
1.873 + /// \brief An upper bound on the node IDs.
1.874 + ///
1.875 + /// Returns an upper bound on the node IDs.
1.876 + int maxNodeId() const { return -1; }
1.877 +
1.878 + /// \brief An upper bound on the red IDs.
1.879 + ///
1.880 + /// Returns an upper bound on the red IDs.
1.881 + int maxRedId() const { return -1; }
1.882 +
1.883 + /// \brief An upper bound on the blue IDs.
1.884 + ///
1.885 + /// Returns an upper bound on the blue IDs.
1.886 + int maxBlueId() const { return -1; }
1.887 +
1.888 + /// \brief An upper bound on the edge IDs.
1.889 + ///
1.890 + /// Returns an upper bound on the edge IDs.
1.891 + int maxEdgeId() const { return -1; }
1.892 +
1.893 + /// \brief An upper bound on the arc IDs.
1.894 + ///
1.895 + /// Returns an upper bound on the arc IDs.
1.896 + int maxArcId() const { return -1; }
1.897 +
1.898 + /// \brief The direction of the arc.
1.899 + ///
1.900 + /// Returns \c true if the given arc goes from a red node to a blue node.
1.901 + bool direction(Arc) const { return true; }
1.902 +
1.903 + /// \brief Direct the edge.
1.904 + ///
1.905 + /// Direct the given edge. The returned arc
1.906 + /// represents the given edge and its direction comes
1.907 + /// from the bool parameter. If it is \c true, then the source of the node
1.908 + /// will be a red node.
1.909 + Arc direct(Edge, bool) const {
1.910 + return INVALID;
1.911 + }
1.912 +
1.913 + /// \brief Direct the edge.
1.914 + ///
1.915 + /// Direct the given edge. The returned arc represents the given
1.916 + /// edge and its source node is the given node.
1.917 + Arc direct(Edge, Node) const {
1.918 + return INVALID;
1.919 + }
1.920 +
1.921 + /// \brief The oppositely directed arc.
1.922 + ///
1.923 + /// Returns the oppositely directed arc representing the same edge.
1.924 + Arc oppositeArc(Arc) const { return INVALID; }
1.925 +
1.926 + /// \brief The opposite node on the edge.
1.927 + ///
1.928 + /// Returns the opposite node on the given edge.
1.929 + Node oppositeNode(Node, Edge) const { return INVALID; }
1.930 +
1.931 + void first(Node&) const {}
1.932 + void next(Node&) const {}
1.933 +
1.934 + void firstRed(Node&) const {}
1.935 + void nextRed(Node&) const {}
1.936 +
1.937 + void firstBlue(Node&) const {}
1.938 + void nextBlue(Node&) const {}
1.939 +
1.940 + void first(Edge&) const {}
1.941 + void next(Edge&) const {}
1.942 +
1.943 + void first(Arc&) const {}
1.944 + void next(Arc&) const {}
1.945 +
1.946 + void firstOut(Arc&, Node) const {}
1.947 + void nextOut(Arc&) const {}
1.948 +
1.949 + void firstIn(Arc&, Node) const {}
1.950 + void nextIn(Arc&) const {}
1.951 +
1.952 + void firstInc(Edge &, bool &, const Node &) const {}
1.953 + void nextInc(Edge &, bool &) const {}
1.954 +
1.955 + // The second parameter is dummy.
1.956 + Node fromId(int, Node) const { return INVALID; }
1.957 + // The second parameter is dummy.
1.958 + Edge fromId(int, Edge) const { return INVALID; }
1.959 + // The second parameter is dummy.
1.960 + Arc fromId(int, Arc) const { return INVALID; }
1.961 +
1.962 + // Dummy parameter.
1.963 + int maxId(Node) const { return -1; }
1.964 + // Dummy parameter.
1.965 + int maxId(RedNode) const { return -1; }
1.966 + // Dummy parameter.
1.967 + int maxId(BlueNode) const { return -1; }
1.968 + // Dummy parameter.
1.969 + int maxId(Edge) const { return -1; }
1.970 + // Dummy parameter.
1.971 + int maxId(Arc) const { return -1; }
1.972 +
1.973 + /// \brief The base node of the iterator.
1.974 + ///
1.975 + /// Returns the base node of the given incident edge iterator.
1.976 + Node baseNode(IncEdgeIt) const { return INVALID; }
1.977 +
1.978 + /// \brief The running node of the iterator.
1.979 + ///
1.980 + /// Returns the running node of the given incident edge iterator.
1.981 + Node runningNode(IncEdgeIt) const { return INVALID; }
1.982 +
1.983 + /// \brief The base node of the iterator.
1.984 + ///
1.985 + /// Returns the base node of the given outgoing arc iterator
1.986 + /// (i.e. the source node of the corresponding arc).
1.987 + Node baseNode(OutArcIt) const { return INVALID; }
1.988 +
1.989 + /// \brief The running node of the iterator.
1.990 + ///
1.991 + /// Returns the running node of the given outgoing arc iterator
1.992 + /// (i.e. the target node of the corresponding arc).
1.993 + Node runningNode(OutArcIt) const { return INVALID; }
1.994 +
1.995 + /// \brief The base node of the iterator.
1.996 + ///
1.997 + /// Returns the base node of the given incomming arc iterator
1.998 + /// (i.e. the target node of the corresponding arc).
1.999 + Node baseNode(InArcIt) const { return INVALID; }
1.1000 +
1.1001 + /// \brief The running node of the iterator.
1.1002 + ///
1.1003 + /// Returns the running node of the given incomming arc iterator
1.1004 + /// (i.e. the source node of the corresponding arc).
1.1005 + Node runningNode(InArcIt) const { return INVALID; }
1.1006 +
1.1007 + template <typename _BpGraph>
1.1008 + struct Constraints {
1.1009 + void constraints() {
1.1010 + checkConcept<BaseBpGraphComponent, _BpGraph>();
1.1011 + checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1.1012 + checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1.1013 + checkConcept<MappableBpGraphComponent<>, _BpGraph>();
1.1014 + }
1.1015 + };
1.1016 +
1.1017 + };
1.1018 +
1.1019 + }
1.1020 +
1.1021 +}
1.1022 +
1.1023 +#endif
2.1 --- a/lemon/concepts/graph.h Sun Feb 24 19:44:14 2013 +0100
2.2 +++ b/lemon/concepts/graph.h Sun Nov 14 16:35:31 2010 +0100
2.3 @@ -72,10 +72,10 @@
2.4 /// \sa Digraph
2.5 class Graph {
2.6 private:
2.7 - /// Graphs are \e not copy constructible. Use DigraphCopy instead.
2.8 + /// Graphs are \e not copy constructible. Use GraphCopy instead.
2.9 Graph(const Graph&) {}
2.10 /// \brief Assignment of a graph to another one is \e not allowed.
2.11 - /// Use DigraphCopy instead.
2.12 + /// Use GraphCopy instead.
2.13 void operator=(const Graph&) {}
2.14
2.15 public:
3.1 --- a/lemon/concepts/graph_components.h Sun Feb 24 19:44:14 2013 +0100
3.2 +++ b/lemon/concepts/graph_components.h Sun Nov 14 16:35:31 2010 +0100
3.3 @@ -299,6 +299,151 @@
3.4
3.5 };
3.6
3.7 + /// \brief Base skeleton class for undirected bipartite graphs.
3.8 + ///
3.9 + /// This class describes the base interface of undirected
3.10 + /// bipartite graph types. All bipartite graph %concepts have to
3.11 + /// conform to this class. It extends the interface of \ref
3.12 + /// BaseGraphComponent with an \c Edge type and functions to get
3.13 + /// the end nodes of edges, to convert from arcs to edges and to
3.14 + /// get both direction of edges.
3.15 + class BaseBpGraphComponent : public BaseGraphComponent {
3.16 + public:
3.17 +
3.18 + typedef BaseBpGraphComponent BpGraph;
3.19 +
3.20 + typedef BaseDigraphComponent::Node Node;
3.21 + typedef BaseDigraphComponent::Arc Arc;
3.22 +
3.23 + /// \brief Class to represent red nodes.
3.24 + ///
3.25 + /// This class represents the red nodes of the graph. It does
3.26 + /// not supposed to be used directly, because the nodes can be
3.27 + /// represented as Node instances. This class can be used as
3.28 + /// template parameter for special map classes.
3.29 + class RedNode : public Node {
3.30 + typedef Node Parent;
3.31 +
3.32 + public:
3.33 + /// \brief Default constructor.
3.34 + ///
3.35 + /// Default constructor.
3.36 + /// \warning The default constructor is not required to set
3.37 + /// the item to some well-defined value. So you should consider it
3.38 + /// as uninitialized.
3.39 + RedNode() {}
3.40 +
3.41 + /// \brief Copy constructor.
3.42 + ///
3.43 + /// Copy constructor.
3.44 + RedNode(const RedNode &) : Parent() {}
3.45 +
3.46 + /// \brief Constructor for conversion from \c INVALID.
3.47 + ///
3.48 + /// Constructor for conversion from \c INVALID.
3.49 + /// It initializes the item to be invalid.
3.50 + /// \sa Invalid for more details.
3.51 + RedNode(Invalid) {}
3.52 +
3.53 + /// \brief Constructor for conversion from a node.
3.54 + ///
3.55 + /// Constructor for conversion from a node. The conversion can
3.56 + /// be invalid, since the Node can be member of the blue
3.57 + /// set.
3.58 + RedNode(const Node&) {}
3.59 + };
3.60 +
3.61 + /// \brief Class to represent blue nodes.
3.62 + ///
3.63 + /// This class represents the blue nodes of the graph. It does
3.64 + /// not supposed to be used directly, because the nodes can be
3.65 + /// represented as Node instances. This class can be used as
3.66 + /// template parameter for special map classes.
3.67 + class BlueNode : public Node {
3.68 + typedef Node Parent;
3.69 +
3.70 + public:
3.71 + /// \brief Default constructor.
3.72 + ///
3.73 + /// Default constructor.
3.74 + /// \warning The default constructor is not required to set
3.75 + /// the item to some well-defined value. So you should consider it
3.76 + /// as uninitialized.
3.77 + BlueNode() {}
3.78 +
3.79 + /// \brief Copy constructor.
3.80 + ///
3.81 + /// Copy constructor.
3.82 + BlueNode(const BlueNode &) : Parent() {}
3.83 +
3.84 + /// \brief Constructor for conversion from \c INVALID.
3.85 + ///
3.86 + /// Constructor for conversion from \c INVALID.
3.87 + /// It initializes the item to be invalid.
3.88 + /// \sa Invalid for more details.
3.89 + BlueNode(Invalid) {}
3.90 +
3.91 + /// \brief Constructor for conversion from a node.
3.92 + ///
3.93 + /// Constructor for conversion from a node. The conversion can
3.94 + /// be invalid, since the Node can be member of the red
3.95 + /// set.
3.96 + BlueNode(const Node&) {}
3.97 + };
3.98 +
3.99 + /// \brief Gives back %true for red nodes.
3.100 + ///
3.101 + /// Gives back %true for red nodes.
3.102 + bool red(const Node&) const { return true; }
3.103 +
3.104 + /// \brief Gives back %true for blue nodes.
3.105 + ///
3.106 + /// Gives back %true for blue nodes.
3.107 + bool blue(const Node&) const { return true; }
3.108 +
3.109 + /// \brief Gives back the red end node of the edge.
3.110 + ///
3.111 + /// Gives back the red end node of the edge.
3.112 + Node redNode(const Edge&) const { return Node(); }
3.113 +
3.114 + /// \brief Gives back the blue end node of the edge.
3.115 + ///
3.116 + /// Gives back the blue end node of the edge.
3.117 + Node blueNode(const Edge&) const { return Node(); }
3.118 +
3.119 + template <typename _BpGraph>
3.120 + struct Constraints {
3.121 + typedef typename _BpGraph::Node Node;
3.122 + typedef typename _BpGraph::RedNode RedNode;
3.123 + typedef typename _BpGraph::BlueNode BlueNode;
3.124 + typedef typename _BpGraph::Arc Arc;
3.125 + typedef typename _BpGraph::Edge Edge;
3.126 +
3.127 + void constraints() {
3.128 + checkConcept<BaseGraphComponent, _BpGraph>();
3.129 + checkConcept<GraphItem<'n'>, RedNode>();
3.130 + checkConcept<GraphItem<'n'>, BlueNode>();
3.131 + {
3.132 + Node n;
3.133 + RedNode rn = n;
3.134 + BlueNode bn = bn;
3.135 + Edge e;
3.136 + bool b;
3.137 + b = bpgraph.red(n);
3.138 + b = bpgraph.blue(n);
3.139 + ignore_unused_variable_warning(b);
3.140 + n = bpgraph.redNode(e);
3.141 + n = bpgraph.blueNode(e);
3.142 + rn = n;
3.143 + bn = n;
3.144 + }
3.145 + }
3.146 +
3.147 + const _BpGraph& bpgraph;
3.148 + };
3.149 +
3.150 + };
3.151 +
3.152 /// \brief Skeleton class for \e idable directed graphs.
3.153 ///
3.154 /// This class describes the interface of \e idable directed graphs.
3.155 @@ -431,6 +576,82 @@
3.156 };
3.157 };
3.158
3.159 + /// \brief Skeleton class for \e idable undirected bipartite graphs.
3.160 + ///
3.161 + /// This class describes the interface of \e idable undirected
3.162 + /// bipartite graphs. It extends \ref IDableGraphComponent with
3.163 + /// the core ID functions of undirected bipartite graphs. Beside
3.164 + /// the regular node ids, this class also provides ids within the
3.165 + /// the red and blue sets of the nodes. This concept is part of
3.166 + /// the BpGraph concept.
3.167 + template <typename BAS = BaseBpGraphComponent>
3.168 + class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
3.169 + public:
3.170 +
3.171 + typedef BAS Base;
3.172 + typedef IDableGraphComponent<BAS> Parent;
3.173 + typedef typename Base::Node Node;
3.174 + typedef typename Base::RedNode RedNode;
3.175 + typedef typename Base::BlueNode BlueNode;
3.176 +
3.177 + using Parent::id;
3.178 +
3.179 + /// \brief Return a unique integer id for the given node in the red set.
3.180 + ///
3.181 + /// Return a unique integer id for the given node in the red set.
3.182 + int redId(const Node&) const { return -1; }
3.183 +
3.184 + /// \brief Return the same value as redId().
3.185 + ///
3.186 + /// Return the same value as redId().
3.187 + int id(const RedNode&) const { return -1; }
3.188 +
3.189 + /// \brief Return a unique integer id for the given node in the blue set.
3.190 + ///
3.191 + /// Return a unique integer id for the given node in the blue set.
3.192 + int blueId(const Node&) const { return -1; }
3.193 +
3.194 + /// \brief Return the same value as blueId().
3.195 + ///
3.196 + /// Return the same value as blueId().
3.197 + int id(const BlueNode&) const { return -1; }
3.198 +
3.199 + /// \brief Return an integer greater or equal to the maximum
3.200 + /// node id in the red set.
3.201 + ///
3.202 + /// Return an integer greater or equal to the maximum
3.203 + /// node id in the red set.
3.204 + int maxRedId() const { return -1; }
3.205 +
3.206 + /// \brief Return an integer greater or equal to the maximum
3.207 + /// node id in the blue set.
3.208 + ///
3.209 + /// Return an integer greater or equal to the maximum
3.210 + /// node id in the blue set.
3.211 + int maxBlueId() const { return -1; }
3.212 +
3.213 + template <typename _BpGraph>
3.214 + struct Constraints {
3.215 +
3.216 + void constraints() {
3.217 + checkConcept<IDableGraphComponent<Base>, _BpGraph>();
3.218 + typename _BpGraph::Node node;
3.219 + typename _BpGraph::RedNode red;
3.220 + typename _BpGraph::BlueNode blue;
3.221 + int rid = bpgraph.redId(node);
3.222 + int bid = bpgraph.blueId(node);
3.223 + rid = bpgraph.id(red);
3.224 + bid = bpgraph.id(blue);
3.225 + rid = bpgraph.maxRedId();
3.226 + bid = bpgraph.maxBlueId();
3.227 + ignore_unused_variable_warning(rid);
3.228 + ignore_unused_variable_warning(bid);
3.229 + }
3.230 +
3.231 + const _BpGraph& bpgraph;
3.232 + };
3.233 + };
3.234 +
3.235 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
3.236 ///
3.237 /// This class describes the concept of \c NodeIt, \c ArcIt and
3.238 @@ -904,6 +1125,92 @@
3.239 };
3.240 };
3.241
3.242 + /// \brief Skeleton class for iterable undirected bipartite graphs.
3.243 + ///
3.244 + /// This class describes the interface of iterable undirected
3.245 + /// bipartite graphs. It extends \ref IterableGraphComponent with
3.246 + /// the core iterable interface of undirected bipartite graphs.
3.247 + /// This concept is part of the BpGraph concept.
3.248 + template <typename BAS = BaseBpGraphComponent>
3.249 + class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
3.250 + public:
3.251 +
3.252 + typedef BAS Base;
3.253 + typedef typename Base::Node Node;
3.254 + typedef typename Base::Arc Arc;
3.255 + typedef typename Base::Edge Edge;
3.256 +
3.257 +
3.258 + typedef IterableBpGraphComponent BpGraph;
3.259 +
3.260 + /// \name Base Iteration
3.261 + ///
3.262 + /// This interface provides functions for iteration on red and blue nodes.
3.263 + ///
3.264 + /// @{
3.265 +
3.266 + /// \brief Return the first red node.
3.267 + ///
3.268 + /// This function gives back the first red node in the iteration order.
3.269 + void firstRed(Node&) const {}
3.270 +
3.271 + /// \brief Return the next red node.
3.272 + ///
3.273 + /// This function gives back the next red node in the iteration order.
3.274 + void nextRed(Node&) const {}
3.275 +
3.276 + /// \brief Return the first blue node.
3.277 + ///
3.278 + /// This function gives back the first blue node in the iteration order.
3.279 + void firstBlue(Node&) const {}
3.280 +
3.281 + /// \brief Return the next blue node.
3.282 + ///
3.283 + /// This function gives back the next blue node in the iteration order.
3.284 + void nextBlue(Node&) const {}
3.285 +
3.286 +
3.287 + /// @}
3.288 +
3.289 + /// \name Class Based Iteration
3.290 + ///
3.291 + /// This interface provides iterator classes for red and blue nodes.
3.292 + ///
3.293 + /// @{
3.294 +
3.295 + /// \brief This iterator goes through each red node.
3.296 + ///
3.297 + /// This iterator goes through each red node.
3.298 + typedef GraphItemIt<BpGraph, Node> RedIt;
3.299 +
3.300 + /// \brief This iterator goes through each blue node.
3.301 + ///
3.302 + /// This iterator goes through each blue node.
3.303 + typedef GraphItemIt<BpGraph, Node> BlueIt;
3.304 +
3.305 + /// @}
3.306 +
3.307 + template <typename _BpGraph>
3.308 + struct Constraints {
3.309 + void constraints() {
3.310 + checkConcept<IterableGraphComponent<Base>, _BpGraph>();
3.311 +
3.312 + typename _BpGraph::Node node(INVALID);
3.313 + bpgraph.firstRed(node);
3.314 + bpgraph.nextRed(node);
3.315 + bpgraph.firstBlue(node);
3.316 + bpgraph.nextBlue(node);
3.317 +
3.318 + checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
3.319 + typename _BpGraph::RedIt>();
3.320 + checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
3.321 + typename _BpGraph::BlueIt>();
3.322 + }
3.323 +
3.324 + const _BpGraph& bpgraph;
3.325 + };
3.326 + };
3.327 +
3.328 /// \brief Skeleton class for alterable directed graphs.
3.329 ///
3.330 /// This class describes the interface of alterable directed
3.331 @@ -929,18 +1236,21 @@
3.332 typedef AlterationNotifier<AlterableDigraphComponent, Arc>
3.333 ArcNotifier;
3.334
3.335 + mutable NodeNotifier node_notifier;
3.336 + mutable ArcNotifier arc_notifier;
3.337 +
3.338 /// \brief Return the node alteration notifier.
3.339 ///
3.340 /// This function gives back the node alteration notifier.
3.341 NodeNotifier& notifier(Node) const {
3.342 - return NodeNotifier();
3.343 + return node_notifier;
3.344 }
3.345
3.346 /// \brief Return the arc alteration notifier.
3.347 ///
3.348 /// This function gives back the arc alteration notifier.
3.349 ArcNotifier& notifier(Arc) const {
3.350 - return ArcNotifier();
3.351 + return arc_notifier;
3.352 }
3.353
3.354 template <typename _Digraph>
3.355 @@ -976,6 +1286,7 @@
3.356 public:
3.357
3.358 typedef BAS Base;
3.359 + typedef AlterableDigraphComponent<Base> Parent;
3.360 typedef typename Base::Edge Edge;
3.361
3.362
3.363 @@ -983,11 +1294,15 @@
3.364 typedef AlterationNotifier<AlterableGraphComponent, Edge>
3.365 EdgeNotifier;
3.366
3.367 + mutable EdgeNotifier edge_notifier;
3.368 +
3.369 + using Parent::notifier;
3.370 +
3.371 /// \brief Return the edge alteration notifier.
3.372 ///
3.373 /// This function gives back the edge alteration notifier.
3.374 EdgeNotifier& notifier(Edge) const {
3.375 - return EdgeNotifier();
3.376 + return edge_notifier;
3.377 }
3.378
3.379 template <typename _Graph>
3.380 @@ -1004,6 +1319,68 @@
3.381 };
3.382 };
3.383
3.384 + /// \brief Skeleton class for alterable undirected bipartite graphs.
3.385 + ///
3.386 + /// This class describes the interface of alterable undirected
3.387 + /// bipartite graphs. It extends \ref AlterableGraphComponent with
3.388 + /// the alteration notifier interface of bipartite graphs. It
3.389 + /// implements an observer-notifier pattern for the red and blue
3.390 + /// nodes. More obsevers can be registered into the notifier and
3.391 + /// whenever an alteration occured in the graph all the observers
3.392 + /// will be notified about it.
3.393 + template <typename BAS = BaseBpGraphComponent>
3.394 + class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
3.395 + public:
3.396 +
3.397 + typedef BAS Base;
3.398 + typedef AlterableGraphComponent<Base> Parent;
3.399 + typedef typename Base::RedNode RedNode;
3.400 + typedef typename Base::BlueNode BlueNode;
3.401 +
3.402 +
3.403 + /// Red node alteration notifier class.
3.404 + typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
3.405 + RedNodeNotifier;
3.406 +
3.407 + /// Blue node alteration notifier class.
3.408 + typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
3.409 + BlueNodeNotifier;
3.410 +
3.411 + mutable RedNodeNotifier red_node_notifier;
3.412 + mutable BlueNodeNotifier blue_node_notifier;
3.413 +
3.414 + using Parent::notifier;
3.415 +
3.416 + /// \brief Return the red node alteration notifier.
3.417 + ///
3.418 + /// This function gives back the red node alteration notifier.
3.419 + RedNodeNotifier& notifier(RedNode) const {
3.420 + return red_node_notifier;
3.421 + }
3.422 +
3.423 + /// \brief Return the blue node alteration notifier.
3.424 + ///
3.425 + /// This function gives back the blue node alteration notifier.
3.426 + BlueNodeNotifier& notifier(BlueNode) const {
3.427 + return blue_node_notifier;
3.428 + }
3.429 +
3.430 + template <typename _BpGraph>
3.431 + struct Constraints {
3.432 + void constraints() {
3.433 + checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
3.434 + typename _BpGraph::RedNodeNotifier& rnn
3.435 + = bpgraph.notifier(typename _BpGraph::RedNode());
3.436 + typename _BpGraph::BlueNodeNotifier& bnn
3.437 + = bpgraph.notifier(typename _BpGraph::BlueNode());
3.438 + ignore_unused_variable_warning(rnn);
3.439 + ignore_unused_variable_warning(bnn);
3.440 + }
3.441 +
3.442 + const _BpGraph& bpgraph;
3.443 + };
3.444 + };
3.445 +
3.446 /// \brief Concept class for standard graph maps.
3.447 ///
3.448 /// This class describes the concept of standard graph maps, i.e.
3.449 @@ -1307,6 +1684,143 @@
3.450 };
3.451 };
3.452
3.453 + /// \brief Skeleton class for mappable undirected bipartite graphs.
3.454 + ///
3.455 + /// This class describes the interface of mappable undirected
3.456 + /// bipartite graphs. It extends \ref MappableGraphComponent with
3.457 + /// the standard graph map class for red and blue nodes (\c
3.458 + /// RedMap and BlueMap). This concept is part of the BpGraph concept.
3.459 + template <typename BAS = BaseBpGraphComponent>
3.460 + class MappableBpGraphComponent : public MappableGraphComponent<BAS> {
3.461 + public:
3.462 +
3.463 + typedef BAS Base;
3.464 + typedef typename Base::Node Node;
3.465 +
3.466 + typedef MappableBpGraphComponent BpGraph;
3.467 +
3.468 + /// \brief Standard graph map for the red nodes.
3.469 + ///
3.470 + /// Standard graph map for the red nodes.
3.471 + /// It conforms to the ReferenceMap concept.
3.472 + template <typename V>
3.473 + class RedMap : public GraphMap<MappableBpGraphComponent, Node, V> {
3.474 + typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
3.475 +
3.476 + public:
3.477 + /// \brief Construct a new map.
3.478 + ///
3.479 + /// Construct a new map for the graph.
3.480 + explicit RedMap(const MappableBpGraphComponent& graph)
3.481 + : Parent(graph) {}
3.482 +
3.483 + /// \brief Construct a new map with default value.
3.484 + ///
3.485 + /// Construct a new map for the graph and initalize the values.
3.486 + RedMap(const MappableBpGraphComponent& graph, const V& value)
3.487 + : Parent(graph, value) {}
3.488 +
3.489 + private:
3.490 + /// \brief Copy constructor.
3.491 + ///
3.492 + /// Copy Constructor.
3.493 + RedMap(const RedMap& nm) : Parent(nm) {}
3.494 +
3.495 + /// \brief Assignment operator.
3.496 + ///
3.497 + /// Assignment operator.
3.498 + template <typename CMap>
3.499 + RedMap& operator=(const CMap&) {
3.500 + checkConcept<ReadMap<Node, V>, CMap>();
3.501 + return *this;
3.502 + }
3.503 +
3.504 + };
3.505 +
3.506 + /// \brief Standard graph map for the blue nodes.
3.507 + ///
3.508 + /// Standard graph map for the blue nodes.
3.509 + /// It conforms to the ReferenceMap concept.
3.510 + template <typename V>
3.511 + class BlueMap : public GraphMap<MappableBpGraphComponent, Node, V> {
3.512 + typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
3.513 +
3.514 + public:
3.515 + /// \brief Construct a new map.
3.516 + ///
3.517 + /// Construct a new map for the graph.
3.518 + explicit BlueMap(const MappableBpGraphComponent& graph)
3.519 + : Parent(graph) {}
3.520 +
3.521 + /// \brief Construct a new map with default value.
3.522 + ///
3.523 + /// Construct a new map for the graph and initalize the values.
3.524 + BlueMap(const MappableBpGraphComponent& graph, const V& value)
3.525 + : Parent(graph, value) {}
3.526 +
3.527 + private:
3.528 + /// \brief Copy constructor.
3.529 + ///
3.530 + /// Copy Constructor.
3.531 + BlueMap(const BlueMap& nm) : Parent(nm) {}
3.532 +
3.533 + /// \brief Assignment operator.
3.534 + ///
3.535 + /// Assignment operator.
3.536 + template <typename CMap>
3.537 + BlueMap& operator=(const CMap&) {
3.538 + checkConcept<ReadMap<Node, V>, CMap>();
3.539 + return *this;
3.540 + }
3.541 +
3.542 + };
3.543 +
3.544 +
3.545 + template <typename _BpGraph>
3.546 + struct Constraints {
3.547 +
3.548 + struct Dummy {
3.549 + int value;
3.550 + Dummy() : value(0) {}
3.551 + Dummy(int _v) : value(_v) {}
3.552 + };
3.553 +
3.554 + void constraints() {
3.555 + checkConcept<MappableGraphComponent<Base>, _BpGraph>();
3.556 +
3.557 + { // int map test
3.558 + typedef typename _BpGraph::template RedMap<int> IntRedMap;
3.559 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
3.560 + IntRedMap >();
3.561 + } { // bool map test
3.562 + typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
3.563 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
3.564 + BoolRedMap >();
3.565 + } { // Dummy map test
3.566 + typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
3.567 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
3.568 + DummyRedMap >();
3.569 + }
3.570 +
3.571 + { // int map test
3.572 + typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
3.573 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
3.574 + IntBlueMap >();
3.575 + } { // bool map test
3.576 + typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
3.577 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
3.578 + BoolBlueMap >();
3.579 + } { // Dummy map test
3.580 + typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
3.581 + checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
3.582 + DummyBlueMap >();
3.583 + }
3.584 + }
3.585 +
3.586 + const _BpGraph& bpgraph;
3.587 + };
3.588 + };
3.589 +
3.590 /// \brief Skeleton class for extendable directed graphs.
3.591 ///
3.592 /// This class describes the interface of extendable directed graphs.
3.593 @@ -1397,6 +1911,58 @@
3.594 };
3.595 };
3.596
3.597 + /// \brief Skeleton class for extendable undirected bipartite graphs.
3.598 + ///
3.599 + /// This class describes the interface of extendable undirected
3.600 + /// bipartite graphs. It extends \ref BaseGraphComponent with
3.601 + /// functions for adding nodes and edges to the graph. This
3.602 + /// concept requires \ref AlterableBpGraphComponent.
3.603 + template <typename BAS = BaseBpGraphComponent>
3.604 + class ExtendableBpGraphComponent : public BAS {
3.605 + public:
3.606 +
3.607 + typedef BAS Base;
3.608 + typedef typename Base::Node Node;
3.609 + typedef typename Base::Edge Edge;
3.610 +
3.611 + /// \brief Add a new red node to the digraph.
3.612 + ///
3.613 + /// This function adds a red new node to the digraph.
3.614 + Node addRedNode() {
3.615 + return INVALID;
3.616 + }
3.617 +
3.618 + /// \brief Add a new blue node to the digraph.
3.619 + ///
3.620 + /// This function adds a blue new node to the digraph.
3.621 + Node addBlueNode() {
3.622 + return INVALID;
3.623 + }
3.624 +
3.625 + /// \brief Add a new edge connecting the given two nodes.
3.626 + ///
3.627 + /// This function adds a new edge connecting the given two nodes
3.628 + /// of the graph. The first node has to be a red node, and the
3.629 + /// second one a blue node.
3.630 + Edge addEdge(const Node&, const Node&) {
3.631 + return INVALID;
3.632 + }
3.633 +
3.634 + template <typename _BpGraph>
3.635 + struct Constraints {
3.636 + void constraints() {
3.637 + checkConcept<Base, _BpGraph>();
3.638 + typename _BpGraph::Node red_node, blue_node;
3.639 + red_node = bpgraph.addRedNode();
3.640 + blue_node = bpgraph.addBlueNode();
3.641 + typename _BpGraph::Edge edge;
3.642 + edge = bpgraph.addEdge(red_node, blue_node);
3.643 + }
3.644 +
3.645 + _BpGraph& bpgraph;
3.646 + };
3.647 + };
3.648 +
3.649 /// \brief Skeleton class for erasable directed graphs.
3.650 ///
3.651 /// This class describes the interface of erasable directed graphs.
3.652 @@ -1477,6 +2043,15 @@
3.653 };
3.654 };
3.655
3.656 + /// \brief Skeleton class for erasable undirected graphs.
3.657 + ///
3.658 + /// This class describes the interface of erasable undirected
3.659 + /// bipartite graphs. It extends \ref BaseBpGraphComponent with
3.660 + /// functions for removing nodes and edges from the graph. This
3.661 + /// concept requires \ref AlterableBpGraphComponent.
3.662 + template <typename BAS = BaseBpGraphComponent>
3.663 + class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
3.664 +
3.665 /// \brief Skeleton class for clearable directed graphs.
3.666 ///
3.667 /// This class describes the interface of clearable directed graphs.
3.668 @@ -1513,27 +2088,16 @@
3.669 /// the graph.
3.670 /// This concept requires \ref AlterableGraphComponent.
3.671 template <typename BAS = BaseGraphComponent>
3.672 - class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
3.673 - public:
3.674 + class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
3.675
3.676 - typedef BAS Base;
3.677 -
3.678 - /// \brief Erase all nodes and edges from the graph.
3.679 - ///
3.680 - /// This function erases all nodes and edges from the graph.
3.681 - void clear() {}
3.682 -
3.683 - template <typename _Graph>
3.684 - struct Constraints {
3.685 - void constraints() {
3.686 - checkConcept<Base, _Graph>();
3.687 - graph.clear();
3.688 - }
3.689 -
3.690 - _Graph& graph;
3.691 - Constraints() {}
3.692 - };
3.693 - };
3.694 + /// \brief Skeleton class for clearable undirected biparite graphs.
3.695 + ///
3.696 + /// This class describes the interface of clearable undirected
3.697 + /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
3.698 + /// function for clearing the graph. This concept requires \ref
3.699 + /// AlterableBpGraphComponent.
3.700 + template <typename BAS = BaseBpGraphComponent>
3.701 + class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
3.702
3.703 }
3.704
4.1 --- a/test/CMakeLists.txt Sun Feb 24 19:44:14 2013 +0100
4.2 +++ b/test/CMakeLists.txt Sun Nov 14 16:35:31 2010 +0100
4.3 @@ -16,6 +16,7 @@
4.4 arc_look_up_test
4.5 bellman_ford_test
4.6 bfs_test
4.7 + bpgraph_test
4.8 circulation_test
4.9 connectivity_test
4.10 counter_test
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/bpgraph_test.cc Sun Nov 14 16:35:31 2010 +0100
5.3 @@ -0,0 +1,70 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2010
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#include <lemon/concepts/bpgraph.h>
5.23 +//#include <lemon/list_graph.h>
5.24 +//#include <lemon/smart_graph.h>
5.25 +//#include <lemon/full_graph.h>
5.26 +//#include <lemon/grid_graph.h>
5.27 +//#include <lemon/hypercube_graph.h>
5.28 +
5.29 +#include "test_tools.h"
5.30 +#include "graph_test.h"
5.31 +
5.32 +using namespace lemon;
5.33 +using namespace lemon::concepts;
5.34 +
5.35 +void checkConcepts() {
5.36 + { // Checking graph components
5.37 + checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
5.38 +
5.39 + checkConcept<IDableBpGraphComponent<>,
5.40 + IDableBpGraphComponent<> >();
5.41 +
5.42 + checkConcept<IterableBpGraphComponent<>,
5.43 + IterableBpGraphComponent<> >();
5.44 +
5.45 + checkConcept<AlterableBpGraphComponent<>,
5.46 + AlterableBpGraphComponent<> >();
5.47 +
5.48 + checkConcept<MappableBpGraphComponent<>,
5.49 + MappableBpGraphComponent<> >();
5.50 +
5.51 + checkConcept<ExtendableBpGraphComponent<>,
5.52 + ExtendableBpGraphComponent<> >();
5.53 +
5.54 + checkConcept<ErasableBpGraphComponent<>,
5.55 + ErasableBpGraphComponent<> >();
5.56 +
5.57 + checkConcept<ClearableGraphComponent<>,
5.58 + ClearableGraphComponent<> >();
5.59 +
5.60 + }
5.61 + { // Checking skeleton graph
5.62 + checkConcept<BpGraph, BpGraph>();
5.63 + }
5.64 +}
5.65 +
5.66 +void checkGraphs() {
5.67 +}
5.68 +
5.69 +int main() {
5.70 + checkConcepts();
5.71 + checkGraphs();
5.72 + return 0;
5.73 +}