lemon/concepts/bpgraph.h
changeset 1018 2e959a5a0c2d
child 1025 c8fa41fcc4a7
     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