1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concepts/bpgraph.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,1029 @@
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-2013
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 RedNodeIt and BlueNodeIt in the
1.55 + /// two node sets. With RedNodeMap and BlueNodeMap values can be
1.56 + /// assigned to 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 + };
1.156 +
1.157 + /// Class to represent blue nodes.
1.158 +
1.159 + /// This class represents the blue nodes of the graph. It does
1.160 + /// not supposed to be used directly, because the nodes can be
1.161 + /// represented as Node instances. This class can be used as
1.162 + /// template parameter for special map classes.
1.163 + class BlueNode : public Node {
1.164 + public:
1.165 + /// Default constructor
1.166 +
1.167 + /// Default constructor.
1.168 + /// \warning It sets the object to an undefined value.
1.169 + BlueNode() { }
1.170 + /// Copy constructor.
1.171 +
1.172 + /// Copy constructor.
1.173 + ///
1.174 + BlueNode(const BlueNode&) : Node() { }
1.175 +
1.176 + /// %Invalid constructor \& conversion.
1.177 +
1.178 + /// Initializes the object to be invalid.
1.179 + /// \sa Invalid for more details.
1.180 + BlueNode(Invalid) { }
1.181 +
1.182 + };
1.183 +
1.184 + /// Iterator class for the red nodes.
1.185 +
1.186 + /// This iterator goes through each red node of the graph.
1.187 + /// Its usage is quite simple, for example, you can count the number
1.188 + /// of red nodes in a graph \c g of type \c %BpGraph like this:
1.189 + ///\code
1.190 + /// int count=0;
1.191 + /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
1.192 + ///\endcode
1.193 + class RedNodeIt : public RedNode {
1.194 + public:
1.195 + /// Default constructor
1.196 +
1.197 + /// Default constructor.
1.198 + /// \warning It sets the iterator to an undefined value.
1.199 + RedNodeIt() { }
1.200 + /// Copy constructor.
1.201 +
1.202 + /// Copy constructor.
1.203 + ///
1.204 + RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
1.205 + /// %Invalid constructor \& conversion.
1.206 +
1.207 + /// Initializes the iterator to be invalid.
1.208 + /// \sa Invalid for more details.
1.209 + RedNodeIt(Invalid) { }
1.210 + /// Sets the iterator to the first red node.
1.211 +
1.212 + /// Sets the iterator to the first red node of the given
1.213 + /// digraph.
1.214 + explicit RedNodeIt(const BpGraph&) { }
1.215 + /// Sets the iterator to the given red node.
1.216 +
1.217 + /// Sets the iterator to the given red node of the given
1.218 + /// digraph.
1.219 + RedNodeIt(const BpGraph&, const RedNode&) { }
1.220 + /// Next node.
1.221 +
1.222 + /// Assign the iterator to the next red node.
1.223 + ///
1.224 + RedNodeIt& operator++() { return *this; }
1.225 + };
1.226 +
1.227 + /// Iterator class for the blue nodes.
1.228 +
1.229 + /// This iterator goes through each blue node of the graph.
1.230 + /// Its usage is quite simple, for example, you can count the number
1.231 + /// of blue nodes in a graph \c g of type \c %BpGraph like this:
1.232 + ///\code
1.233 + /// int count=0;
1.234 + /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
1.235 + ///\endcode
1.236 + class BlueNodeIt : public BlueNode {
1.237 + public:
1.238 + /// Default constructor
1.239 +
1.240 + /// Default constructor.
1.241 + /// \warning It sets the iterator to an undefined value.
1.242 + BlueNodeIt() { }
1.243 + /// Copy constructor.
1.244 +
1.245 + /// Copy constructor.
1.246 + ///
1.247 + BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
1.248 + /// %Invalid constructor \& conversion.
1.249 +
1.250 + /// Initializes the iterator to be invalid.
1.251 + /// \sa Invalid for more details.
1.252 + BlueNodeIt(Invalid) { }
1.253 + /// Sets the iterator to the first blue node.
1.254 +
1.255 + /// Sets the iterator to the first blue node of the given
1.256 + /// digraph.
1.257 + explicit BlueNodeIt(const BpGraph&) { }
1.258 + /// Sets the iterator to the given blue node.
1.259 +
1.260 + /// Sets the iterator to the given blue node of the given
1.261 + /// digraph.
1.262 + BlueNodeIt(const BpGraph&, const BlueNode&) { }
1.263 + /// Next node.
1.264 +
1.265 + /// Assign the iterator to the next blue node.
1.266 + ///
1.267 + BlueNodeIt& operator++() { return *this; }
1.268 + };
1.269 +
1.270 + /// Iterator class for the nodes.
1.271 +
1.272 + /// This iterator goes through each node of the graph.
1.273 + /// Its usage is quite simple, for example, you can count the number
1.274 + /// of nodes in a graph \c g of type \c %BpGraph like this:
1.275 + ///\code
1.276 + /// int count=0;
1.277 + /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.278 + ///\endcode
1.279 + class NodeIt : public Node {
1.280 + public:
1.281 + /// Default constructor
1.282 +
1.283 + /// Default constructor.
1.284 + /// \warning It sets the iterator to an undefined value.
1.285 + NodeIt() { }
1.286 + /// Copy constructor.
1.287 +
1.288 + /// Copy constructor.
1.289 + ///
1.290 + NodeIt(const NodeIt& n) : Node(n) { }
1.291 + /// %Invalid constructor \& conversion.
1.292 +
1.293 + /// Initializes the iterator to be invalid.
1.294 + /// \sa Invalid for more details.
1.295 + NodeIt(Invalid) { }
1.296 + /// Sets the iterator to the first node.
1.297 +
1.298 + /// Sets the iterator to the first node of the given digraph.
1.299 + ///
1.300 + explicit NodeIt(const BpGraph&) { }
1.301 + /// Sets the iterator to the given node.
1.302 +
1.303 + /// Sets the iterator to the given node of the given digraph.
1.304 + ///
1.305 + NodeIt(const BpGraph&, const Node&) { }
1.306 + /// Next node.
1.307 +
1.308 + /// Assign the iterator to the next node.
1.309 + ///
1.310 + NodeIt& operator++() { return *this; }
1.311 + };
1.312 +
1.313 +
1.314 + /// The edge type of the graph
1.315 +
1.316 + /// This class identifies an edge of the graph. It also serves
1.317 + /// as a base class of the edge iterators,
1.318 + /// thus they will convert to this type.
1.319 + class Edge {
1.320 + public:
1.321 + /// Default constructor
1.322 +
1.323 + /// Default constructor.
1.324 + /// \warning It sets the object to an undefined value.
1.325 + Edge() { }
1.326 + /// Copy constructor.
1.327 +
1.328 + /// Copy constructor.
1.329 + ///
1.330 + Edge(const Edge&) { }
1.331 + /// %Invalid constructor \& conversion.
1.332 +
1.333 + /// Initializes the object to be invalid.
1.334 + /// \sa Invalid for more details.
1.335 + Edge(Invalid) { }
1.336 + /// Equality operator
1.337 +
1.338 + /// Equality operator.
1.339 + ///
1.340 + /// Two iterators are equal if and only if they point to the
1.341 + /// same object or both are \c INVALID.
1.342 + bool operator==(Edge) const { return true; }
1.343 + /// Inequality operator
1.344 +
1.345 + /// Inequality operator.
1.346 + bool operator!=(Edge) const { return true; }
1.347 +
1.348 + /// Artificial ordering operator.
1.349 +
1.350 + /// Artificial ordering operator.
1.351 + ///
1.352 + /// \note This operator only has to define some strict ordering of
1.353 + /// the edges; this order has nothing to do with the iteration
1.354 + /// ordering of the edges.
1.355 + bool operator<(Edge) const { return false; }
1.356 + };
1.357 +
1.358 + /// Iterator class for the edges.
1.359 +
1.360 + /// This iterator goes through each edge of the graph.
1.361 + /// Its usage is quite simple, for example, you can count the number
1.362 + /// of edges in a graph \c g of type \c %BpGraph as follows:
1.363 + ///\code
1.364 + /// int count=0;
1.365 + /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.366 + ///\endcode
1.367 + class EdgeIt : public Edge {
1.368 + public:
1.369 + /// Default constructor
1.370 +
1.371 + /// Default constructor.
1.372 + /// \warning It sets the iterator to an undefined value.
1.373 + EdgeIt() { }
1.374 + /// Copy constructor.
1.375 +
1.376 + /// Copy constructor.
1.377 + ///
1.378 + EdgeIt(const EdgeIt& e) : Edge(e) { }
1.379 + /// %Invalid constructor \& conversion.
1.380 +
1.381 + /// Initializes the iterator to be invalid.
1.382 + /// \sa Invalid for more details.
1.383 + EdgeIt(Invalid) { }
1.384 + /// Sets the iterator to the first edge.
1.385 +
1.386 + /// Sets the iterator to the first edge of the given graph.
1.387 + ///
1.388 + explicit EdgeIt(const BpGraph&) { }
1.389 + /// Sets the iterator to the given edge.
1.390 +
1.391 + /// Sets the iterator to the given edge of the given graph.
1.392 + ///
1.393 + EdgeIt(const BpGraph&, const Edge&) { }
1.394 + /// Next edge
1.395 +
1.396 + /// Assign the iterator to the next edge.
1.397 + ///
1.398 + EdgeIt& operator++() { return *this; }
1.399 + };
1.400 +
1.401 + /// Iterator class for the incident edges of a node.
1.402 +
1.403 + /// This iterator goes trough the incident undirected edges
1.404 + /// of a certain node of a graph.
1.405 + /// Its usage is quite simple, for example, you can compute the
1.406 + /// degree (i.e. the number of incident edges) of a node \c n
1.407 + /// in a graph \c g of type \c %BpGraph as follows.
1.408 + ///
1.409 + ///\code
1.410 + /// int count=0;
1.411 + /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.412 + ///\endcode
1.413 + ///
1.414 + /// \warning Loop edges will be iterated twice.
1.415 + class IncEdgeIt : public Edge {
1.416 + public:
1.417 + /// Default constructor
1.418 +
1.419 + /// Default constructor.
1.420 + /// \warning It sets the iterator to an undefined value.
1.421 + IncEdgeIt() { }
1.422 + /// Copy constructor.
1.423 +
1.424 + /// Copy constructor.
1.425 + ///
1.426 + IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
1.427 + /// %Invalid constructor \& conversion.
1.428 +
1.429 + /// Initializes the iterator to be invalid.
1.430 + /// \sa Invalid for more details.
1.431 + IncEdgeIt(Invalid) { }
1.432 + /// Sets the iterator to the first incident edge.
1.433 +
1.434 + /// Sets the iterator to the first incident edge of the given node.
1.435 + ///
1.436 + IncEdgeIt(const BpGraph&, const Node&) { }
1.437 + /// Sets the iterator to the given edge.
1.438 +
1.439 + /// Sets the iterator to the given edge of the given graph.
1.440 + ///
1.441 + IncEdgeIt(const BpGraph&, const Edge&) { }
1.442 + /// Next incident edge
1.443 +
1.444 + /// Assign the iterator to the next incident edge
1.445 + /// of the corresponding node.
1.446 + IncEdgeIt& operator++() { return *this; }
1.447 + };
1.448 +
1.449 + /// The arc type of the graph
1.450 +
1.451 + /// This class identifies a directed arc of the graph. It also serves
1.452 + /// as a base class of the arc iterators,
1.453 + /// thus they will convert to this type.
1.454 + class Arc {
1.455 + public:
1.456 + /// Default constructor
1.457 +
1.458 + /// Default constructor.
1.459 + /// \warning It sets the object to an undefined value.
1.460 + Arc() { }
1.461 + /// Copy constructor.
1.462 +
1.463 + /// Copy constructor.
1.464 + ///
1.465 + Arc(const Arc&) { }
1.466 + /// %Invalid constructor \& conversion.
1.467 +
1.468 + /// Initializes the object to be invalid.
1.469 + /// \sa Invalid for more details.
1.470 + Arc(Invalid) { }
1.471 + /// Equality operator
1.472 +
1.473 + /// Equality operator.
1.474 + ///
1.475 + /// Two iterators are equal if and only if they point to the
1.476 + /// same object or both are \c INVALID.
1.477 + bool operator==(Arc) const { return true; }
1.478 + /// Inequality operator
1.479 +
1.480 + /// Inequality operator.
1.481 + bool operator!=(Arc) const { return true; }
1.482 +
1.483 + /// Artificial ordering operator.
1.484 +
1.485 + /// Artificial ordering operator.
1.486 + ///
1.487 + /// \note This operator only has to define some strict ordering of
1.488 + /// the arcs; this order has nothing to do with the iteration
1.489 + /// ordering of the arcs.
1.490 + bool operator<(Arc) const { return false; }
1.491 +
1.492 + /// Converison to \c Edge
1.493 +
1.494 + /// Converison to \c Edge.
1.495 + ///
1.496 + operator Edge() const { return Edge(); }
1.497 + };
1.498 +
1.499 + /// Iterator class for the arcs.
1.500 +
1.501 + /// This iterator goes through each directed arc of the graph.
1.502 + /// Its usage is quite simple, for example, you can count the number
1.503 + /// of arcs in a graph \c g of type \c %BpGraph as follows:
1.504 + ///\code
1.505 + /// int count=0;
1.506 + /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
1.507 + ///\endcode
1.508 + class ArcIt : public Arc {
1.509 + public:
1.510 + /// Default constructor
1.511 +
1.512 + /// Default constructor.
1.513 + /// \warning It sets the iterator to an undefined value.
1.514 + ArcIt() { }
1.515 + /// Copy constructor.
1.516 +
1.517 + /// Copy constructor.
1.518 + ///
1.519 + ArcIt(const ArcIt& e) : Arc(e) { }
1.520 + /// %Invalid constructor \& conversion.
1.521 +
1.522 + /// Initializes the iterator to be invalid.
1.523 + /// \sa Invalid for more details.
1.524 + ArcIt(Invalid) { }
1.525 + /// Sets the iterator to the first arc.
1.526 +
1.527 + /// Sets the iterator to the first arc of the given graph.
1.528 + ///
1.529 + explicit ArcIt(const BpGraph &g)
1.530 + {
1.531 + ::lemon::ignore_unused_variable_warning(g);
1.532 + }
1.533 + /// Sets the iterator to the given arc.
1.534 +
1.535 + /// Sets the iterator to the given arc of the given graph.
1.536 + ///
1.537 + ArcIt(const BpGraph&, const Arc&) { }
1.538 + /// Next arc
1.539 +
1.540 + /// Assign the iterator to the next arc.
1.541 + ///
1.542 + ArcIt& operator++() { return *this; }
1.543 + };
1.544 +
1.545 + /// Iterator class for the outgoing arcs of a node.
1.546 +
1.547 + /// This iterator goes trough the \e outgoing directed arcs of a
1.548 + /// certain node of a graph.
1.549 + /// Its usage is quite simple, for example, you can count the number
1.550 + /// of outgoing arcs of a node \c n
1.551 + /// in a graph \c g of type \c %BpGraph as follows.
1.552 + ///\code
1.553 + /// int count=0;
1.554 + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
1.555 + ///\endcode
1.556 + class OutArcIt : public Arc {
1.557 + public:
1.558 + /// Default constructor
1.559 +
1.560 + /// Default constructor.
1.561 + /// \warning It sets the iterator to an undefined value.
1.562 + OutArcIt() { }
1.563 + /// Copy constructor.
1.564 +
1.565 + /// Copy constructor.
1.566 + ///
1.567 + OutArcIt(const OutArcIt& e) : Arc(e) { }
1.568 + /// %Invalid constructor \& conversion.
1.569 +
1.570 + /// Initializes the iterator to be invalid.
1.571 + /// \sa Invalid for more details.
1.572 + OutArcIt(Invalid) { }
1.573 + /// Sets the iterator to the first outgoing arc.
1.574 +
1.575 + /// Sets the iterator to the first outgoing arc of the given node.
1.576 + ///
1.577 + OutArcIt(const BpGraph& n, const Node& g) {
1.578 + ::lemon::ignore_unused_variable_warning(n);
1.579 + ::lemon::ignore_unused_variable_warning(g);
1.580 + }
1.581 + /// Sets the iterator to the given arc.
1.582 +
1.583 + /// Sets the iterator to the given arc of the given graph.
1.584 + ///
1.585 + OutArcIt(const BpGraph&, const Arc&) { }
1.586 + /// Next outgoing arc
1.587 +
1.588 + /// Assign the iterator to the next
1.589 + /// outgoing arc of the corresponding node.
1.590 + OutArcIt& operator++() { return *this; }
1.591 + };
1.592 +
1.593 + /// Iterator class for the incoming arcs of a node.
1.594 +
1.595 + /// This iterator goes trough the \e incoming directed arcs of a
1.596 + /// certain node of a graph.
1.597 + /// Its usage is quite simple, for example, you can count the number
1.598 + /// of incoming arcs of a node \c n
1.599 + /// in a graph \c g of type \c %BpGraph as follows.
1.600 + ///\code
1.601 + /// int count=0;
1.602 + /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
1.603 + ///\endcode
1.604 + class InArcIt : public Arc {
1.605 + public:
1.606 + /// Default constructor
1.607 +
1.608 + /// Default constructor.
1.609 + /// \warning It sets the iterator to an undefined value.
1.610 + InArcIt() { }
1.611 + /// Copy constructor.
1.612 +
1.613 + /// Copy constructor.
1.614 + ///
1.615 + InArcIt(const InArcIt& e) : Arc(e) { }
1.616 + /// %Invalid constructor \& conversion.
1.617 +
1.618 + /// Initializes the iterator to be invalid.
1.619 + /// \sa Invalid for more details.
1.620 + InArcIt(Invalid) { }
1.621 + /// Sets the iterator to the first incoming arc.
1.622 +
1.623 + /// Sets the iterator to the first incoming arc of the given node.
1.624 + ///
1.625 + InArcIt(const BpGraph& g, const Node& n) {
1.626 + ::lemon::ignore_unused_variable_warning(n);
1.627 + ::lemon::ignore_unused_variable_warning(g);
1.628 + }
1.629 + /// Sets the iterator to the given arc.
1.630 +
1.631 + /// Sets the iterator to the given arc of the given graph.
1.632 + ///
1.633 + InArcIt(const BpGraph&, const Arc&) { }
1.634 + /// Next incoming arc
1.635 +
1.636 + /// Assign the iterator to the next
1.637 + /// incoming arc of the corresponding node.
1.638 + InArcIt& operator++() { return *this; }
1.639 + };
1.640 +
1.641 + /// \brief Standard graph map type for the nodes.
1.642 + ///
1.643 + /// Standard graph map type for the nodes.
1.644 + /// It conforms to the ReferenceMap concept.
1.645 + template<class T>
1.646 + class NodeMap : public ReferenceMap<Node, T, T&, const T&>
1.647 + {
1.648 + public:
1.649 +
1.650 + /// Constructor
1.651 + explicit NodeMap(const BpGraph&) { }
1.652 + /// Constructor with given initial value
1.653 + NodeMap(const BpGraph&, T) { }
1.654 +
1.655 + private:
1.656 + ///Copy constructor
1.657 + NodeMap(const NodeMap& nm) :
1.658 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.659 + ///Assignment operator
1.660 + template <typename CMap>
1.661 + NodeMap& operator=(const CMap&) {
1.662 + checkConcept<ReadMap<Node, T>, CMap>();
1.663 + return *this;
1.664 + }
1.665 + };
1.666 +
1.667 + /// \brief Standard graph map type for the red nodes.
1.668 + ///
1.669 + /// Standard graph map type for the red nodes.
1.670 + /// It conforms to the ReferenceMap concept.
1.671 + template<class T>
1.672 + class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
1.673 + {
1.674 + public:
1.675 +
1.676 + /// Constructor
1.677 + explicit RedNodeMap(const BpGraph&) { }
1.678 + /// Constructor with given initial value
1.679 + RedNodeMap(const BpGraph&, T) { }
1.680 +
1.681 + private:
1.682 + ///Copy constructor
1.683 + RedNodeMap(const RedNodeMap& nm) :
1.684 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.685 + ///Assignment operator
1.686 + template <typename CMap>
1.687 + RedNodeMap& operator=(const CMap&) {
1.688 + checkConcept<ReadMap<Node, T>, CMap>();
1.689 + return *this;
1.690 + }
1.691 + };
1.692 +
1.693 + /// \brief Standard graph map type for the blue nodes.
1.694 + ///
1.695 + /// Standard graph map type for the blue nodes.
1.696 + /// It conforms to the ReferenceMap concept.
1.697 + template<class T>
1.698 + class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
1.699 + {
1.700 + public:
1.701 +
1.702 + /// Constructor
1.703 + explicit BlueNodeMap(const BpGraph&) { }
1.704 + /// Constructor with given initial value
1.705 + BlueNodeMap(const BpGraph&, T) { }
1.706 +
1.707 + private:
1.708 + ///Copy constructor
1.709 + BlueNodeMap(const BlueNodeMap& nm) :
1.710 + ReferenceMap<Node, T, T&, const T&>(nm) { }
1.711 + ///Assignment operator
1.712 + template <typename CMap>
1.713 + BlueNodeMap& operator=(const CMap&) {
1.714 + checkConcept<ReadMap<Node, T>, CMap>();
1.715 + return *this;
1.716 + }
1.717 + };
1.718 +
1.719 + /// \brief Standard graph map type for the arcs.
1.720 + ///
1.721 + /// Standard graph map type for the arcs.
1.722 + /// It conforms to the ReferenceMap concept.
1.723 + template<class T>
1.724 + class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
1.725 + {
1.726 + public:
1.727 +
1.728 + /// Constructor
1.729 + explicit ArcMap(const BpGraph&) { }
1.730 + /// Constructor with given initial value
1.731 + ArcMap(const BpGraph&, T) { }
1.732 +
1.733 + private:
1.734 + ///Copy constructor
1.735 + ArcMap(const ArcMap& em) :
1.736 + ReferenceMap<Arc, T, T&, const T&>(em) { }
1.737 + ///Assignment operator
1.738 + template <typename CMap>
1.739 + ArcMap& operator=(const CMap&) {
1.740 + checkConcept<ReadMap<Arc, T>, CMap>();
1.741 + return *this;
1.742 + }
1.743 + };
1.744 +
1.745 + /// \brief Standard graph map type for the edges.
1.746 + ///
1.747 + /// Standard graph map type for the edges.
1.748 + /// It conforms to the ReferenceMap concept.
1.749 + template<class T>
1.750 + class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
1.751 + {
1.752 + public:
1.753 +
1.754 + /// Constructor
1.755 + explicit EdgeMap(const BpGraph&) { }
1.756 + /// Constructor with given initial value
1.757 + EdgeMap(const BpGraph&, T) { }
1.758 +
1.759 + private:
1.760 + ///Copy constructor
1.761 + EdgeMap(const EdgeMap& em) :
1.762 + ReferenceMap<Edge, T, T&, const T&>(em) {}
1.763 + ///Assignment operator
1.764 + template <typename CMap>
1.765 + EdgeMap& operator=(const CMap&) {
1.766 + checkConcept<ReadMap<Edge, T>, CMap>();
1.767 + return *this;
1.768 + }
1.769 + };
1.770 +
1.771 + /// \brief Gives back %true for red nodes.
1.772 + ///
1.773 + /// Gives back %true for red nodes.
1.774 + bool red(const Node&) const { return true; }
1.775 +
1.776 + /// \brief Gives back %true for blue nodes.
1.777 + ///
1.778 + /// Gives back %true for blue nodes.
1.779 + bool blue(const Node&) const { return true; }
1.780 +
1.781 + /// \brief Converts the node to red node object.
1.782 + ///
1.783 + /// This function converts unsafely the node to red node
1.784 + /// object. It should be called only if the node is from the red
1.785 + /// partition or INVALID.
1.786 + RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
1.787 +
1.788 + /// \brief Converts the node to blue node object.
1.789 + ///
1.790 + /// This function converts unsafely the node to blue node
1.791 + /// object. It should be called only if the node is from the red
1.792 + /// partition or INVALID.
1.793 + BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
1.794 +
1.795 + /// \brief Converts the node to red node object.
1.796 + ///
1.797 + /// This function converts safely the node to red node
1.798 + /// object. If the node is not from the red partition, then it
1.799 + /// returns INVALID.
1.800 + RedNode asRedNode(const Node&) const { return RedNode(); }
1.801 +
1.802 + /// \brief Converts the node to blue node object.
1.803 + ///
1.804 + /// This function converts unsafely the node to blue node
1.805 + /// object. If the node is not from the blue partition, then it
1.806 + /// returns INVALID.
1.807 + BlueNode asBlueNode(const Node&) const { return BlueNode(); }
1.808 +
1.809 + /// \brief Gives back the red end node of the edge.
1.810 + ///
1.811 + /// Gives back the red end node of the edge.
1.812 + RedNode redNode(const Edge&) const { return RedNode(); }
1.813 +
1.814 + /// \brief Gives back the blue end node of the edge.
1.815 + ///
1.816 + /// Gives back the blue end node of the edge.
1.817 + BlueNode blueNode(const Edge&) const { return BlueNode(); }
1.818 +
1.819 + /// \brief The first node of the edge.
1.820 + ///
1.821 + /// It is a synonim for the \c redNode().
1.822 + Node u(Edge) const { return INVALID; }
1.823 +
1.824 + /// \brief The second node of the edge.
1.825 + ///
1.826 + /// It is a synonim for the \c blueNode().
1.827 + Node v(Edge) const { return INVALID; }
1.828 +
1.829 + /// \brief The source node of the arc.
1.830 + ///
1.831 + /// Returns the source node of the given arc.
1.832 + Node source(Arc) const { return INVALID; }
1.833 +
1.834 + /// \brief The target node of the arc.
1.835 + ///
1.836 + /// Returns the target node of the given arc.
1.837 + Node target(Arc) const { return INVALID; }
1.838 +
1.839 + /// \brief The ID of the node.
1.840 + ///
1.841 + /// Returns the ID of the given node.
1.842 + int id(Node) const { return -1; }
1.843 +
1.844 + /// \brief The red ID of the node.
1.845 + ///
1.846 + /// Returns the red ID of the given node.
1.847 + int id(RedNode) const { return -1; }
1.848 +
1.849 + /// \brief The blue ID of the node.
1.850 + ///
1.851 + /// Returns the blue ID of the given node.
1.852 + int id(BlueNode) const { return -1; }
1.853 +
1.854 + /// \brief The ID of the edge.
1.855 + ///
1.856 + /// Returns the ID of the given edge.
1.857 + int id(Edge) const { return -1; }
1.858 +
1.859 + /// \brief The ID of the arc.
1.860 + ///
1.861 + /// Returns the ID of the given arc.
1.862 + int id(Arc) const { return -1; }
1.863 +
1.864 + /// \brief The node with the given ID.
1.865 + ///
1.866 + /// Returns the node with the given ID.
1.867 + /// \pre The argument should be a valid node ID in the graph.
1.868 + Node nodeFromId(int) const { return INVALID; }
1.869 +
1.870 + /// \brief The edge with the given ID.
1.871 + ///
1.872 + /// Returns the edge with the given ID.
1.873 + /// \pre The argument should be a valid edge ID in the graph.
1.874 + Edge edgeFromId(int) const { return INVALID; }
1.875 +
1.876 + /// \brief The arc with the given ID.
1.877 + ///
1.878 + /// Returns the arc with the given ID.
1.879 + /// \pre The argument should be a valid arc ID in the graph.
1.880 + Arc arcFromId(int) const { return INVALID; }
1.881 +
1.882 + /// \brief An upper bound on the node IDs.
1.883 + ///
1.884 + /// Returns an upper bound on the node IDs.
1.885 + int maxNodeId() const { return -1; }
1.886 +
1.887 + /// \brief An upper bound on the red IDs.
1.888 + ///
1.889 + /// Returns an upper bound on the red IDs.
1.890 + int maxRedId() const { return -1; }
1.891 +
1.892 + /// \brief An upper bound on the blue IDs.
1.893 + ///
1.894 + /// Returns an upper bound on the blue IDs.
1.895 + int maxBlueId() const { return -1; }
1.896 +
1.897 + /// \brief An upper bound on the edge IDs.
1.898 + ///
1.899 + /// Returns an upper bound on the edge IDs.
1.900 + int maxEdgeId() const { return -1; }
1.901 +
1.902 + /// \brief An upper bound on the arc IDs.
1.903 + ///
1.904 + /// Returns an upper bound on the arc IDs.
1.905 + int maxArcId() const { return -1; }
1.906 +
1.907 + /// \brief The direction of the arc.
1.908 + ///
1.909 + /// Returns \c true if the given arc goes from a red node to a blue node.
1.910 + bool direction(Arc) const { return true; }
1.911 +
1.912 + /// \brief Direct the edge.
1.913 + ///
1.914 + /// Direct the given edge. The returned arc
1.915 + /// represents the given edge and its direction comes
1.916 + /// from the bool parameter. If it is \c true, then the source of the node
1.917 + /// will be a red node.
1.918 + Arc direct(Edge, bool) const {
1.919 + return INVALID;
1.920 + }
1.921 +
1.922 + /// \brief Direct the edge.
1.923 + ///
1.924 + /// Direct the given edge. The returned arc represents the given
1.925 + /// edge and its source node is the given node.
1.926 + Arc direct(Edge, Node) const {
1.927 + return INVALID;
1.928 + }
1.929 +
1.930 + /// \brief The oppositely directed arc.
1.931 + ///
1.932 + /// Returns the oppositely directed arc representing the same edge.
1.933 + Arc oppositeArc(Arc) const { return INVALID; }
1.934 +
1.935 + /// \brief The opposite node on the edge.
1.936 + ///
1.937 + /// Returns the opposite node on the given edge.
1.938 + Node oppositeNode(Node, Edge) const { return INVALID; }
1.939 +
1.940 + void first(Node&) const {}
1.941 + void next(Node&) const {}
1.942 +
1.943 + void firstRed(RedNode&) const {}
1.944 + void nextRed(RedNode&) const {}
1.945 +
1.946 + void firstBlue(BlueNode&) const {}
1.947 + void nextBlue(BlueNode&) const {}
1.948 +
1.949 + void first(Edge&) const {}
1.950 + void next(Edge&) const {}
1.951 +
1.952 + void first(Arc&) const {}
1.953 + void next(Arc&) const {}
1.954 +
1.955 + void firstOut(Arc&, Node) const {}
1.956 + void nextOut(Arc&) const {}
1.957 +
1.958 + void firstIn(Arc&, Node) const {}
1.959 + void nextIn(Arc&) const {}
1.960 +
1.961 + void firstInc(Edge &, bool &, const Node &) const {}
1.962 + void nextInc(Edge &, bool &) const {}
1.963 +
1.964 + // The second parameter is dummy.
1.965 + Node fromId(int, Node) const { return INVALID; }
1.966 + // The second parameter is dummy.
1.967 + Edge fromId(int, Edge) const { return INVALID; }
1.968 + // The second parameter is dummy.
1.969 + Arc fromId(int, Arc) const { return INVALID; }
1.970 +
1.971 + // Dummy parameter.
1.972 + int maxId(Node) const { return -1; }
1.973 + // Dummy parameter.
1.974 + int maxId(RedNode) const { return -1; }
1.975 + // Dummy parameter.
1.976 + int maxId(BlueNode) const { return -1; }
1.977 + // Dummy parameter.
1.978 + int maxId(Edge) const { return -1; }
1.979 + // Dummy parameter.
1.980 + int maxId(Arc) const { return -1; }
1.981 +
1.982 + /// \brief The base node of the iterator.
1.983 + ///
1.984 + /// Returns the base node of the given incident edge iterator.
1.985 + Node baseNode(IncEdgeIt) const { return INVALID; }
1.986 +
1.987 + /// \brief The running node of the iterator.
1.988 + ///
1.989 + /// Returns the running node of the given incident edge iterator.
1.990 + Node runningNode(IncEdgeIt) const { return INVALID; }
1.991 +
1.992 + /// \brief The base node of the iterator.
1.993 + ///
1.994 + /// Returns the base node of the given outgoing arc iterator
1.995 + /// (i.e. the source node of the corresponding arc).
1.996 + Node baseNode(OutArcIt) const { return INVALID; }
1.997 +
1.998 + /// \brief The running node of the iterator.
1.999 + ///
1.1000 + /// Returns the running node of the given outgoing arc iterator
1.1001 + /// (i.e. the target node of the corresponding arc).
1.1002 + Node runningNode(OutArcIt) const { return INVALID; }
1.1003 +
1.1004 + /// \brief The base node of the iterator.
1.1005 + ///
1.1006 + /// Returns the base node of the given incoming arc iterator
1.1007 + /// (i.e. the target node of the corresponding arc).
1.1008 + Node baseNode(InArcIt) const { return INVALID; }
1.1009 +
1.1010 + /// \brief The running node of the iterator.
1.1011 + ///
1.1012 + /// Returns the running node of the given incoming arc iterator
1.1013 + /// (i.e. the source node of the corresponding arc).
1.1014 + Node runningNode(InArcIt) const { return INVALID; }
1.1015 +
1.1016 + template <typename _BpGraph>
1.1017 + struct Constraints {
1.1018 + void constraints() {
1.1019 + checkConcept<BaseBpGraphComponent, _BpGraph>();
1.1020 + checkConcept<IterableBpGraphComponent<>, _BpGraph>();
1.1021 + checkConcept<IDableBpGraphComponent<>, _BpGraph>();
1.1022 + checkConcept<MappableBpGraphComponent<>, _BpGraph>();
1.1023 + }
1.1024 + };
1.1025 +
1.1026 + };
1.1027 +
1.1028 + }
1.1029 +
1.1030 +}
1.1031 +
1.1032 +#endif