1.1 --- a/lemon/adaptors.h Thu Jan 08 17:19:26 2009 +0000
1.2 +++ b/lemon/adaptors.h Sun Jan 11 15:09:53 2009 +0000
1.3 @@ -21,7 +21,7 @@
1.4
1.5 /// \ingroup graph_adaptors
1.6 /// \file
1.7 -/// \brief Several graph adaptors
1.8 +/// \brief Adaptor classes for digraphs and graphs
1.9 ///
1.10 /// This file contains several useful adaptors for digraphs and graphs.
1.11
1.12 @@ -70,21 +70,21 @@
1.13 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.14 int nodeNum() const { return _digraph->nodeNum(); }
1.15
1.16 - typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1.17 + typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1.18 int arcNum() const { return _digraph->arcNum(); }
1.19
1.20 - typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.21 - Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
1.22 + typedef FindArcTagIndicator<Digraph> FindArcTag;
1.23 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
1.24 return _digraph->findArc(u, v, prev);
1.25 }
1.26
1.27 Node addNode() { return _digraph->addNode(); }
1.28 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
1.29
1.30 - void erase(const Node& n) const { _digraph->erase(n); }
1.31 - void erase(const Arc& a) const { _digraph->erase(a); }
1.32 -
1.33 - void clear() const { _digraph->clear(); }
1.34 + void erase(const Node& n) { _digraph->erase(n); }
1.35 + void erase(const Arc& a) { _digraph->erase(a); }
1.36 +
1.37 + void clear() { _digraph->clear(); }
1.38
1.39 int id(const Node& n) const { return _digraph->id(n); }
1.40 int id(const Arc& a) const { return _digraph->id(a); }
1.41 @@ -198,15 +198,21 @@
1.42 typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.43 int nodeNum() const { return _graph->nodeNum(); }
1.44
1.45 + typedef ArcNumTagIndicator<Graph> ArcNumTag;
1.46 + int arcNum() const { return _graph->arcNum(); }
1.47 +
1.48 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.49 - int arcNum() const { return _graph->arcNum(); }
1.50 int edgeNum() const { return _graph->edgeNum(); }
1.51
1.52 - typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.53 - Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
1.54 + typedef FindArcTagIndicator<Graph> FindArcTag;
1.55 + Arc findArc(const Node& u, const Node& v,
1.56 + const Arc& prev = INVALID) const {
1.57 return _graph->findArc(u, v, prev);
1.58 }
1.59 - Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
1.60 +
1.61 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.62 + Edge findEdge(const Node& u, const Node& v,
1.63 + const Edge& prev = INVALID) const {
1.64 return _graph->findEdge(u, v, prev);
1.65 }
1.66
1.67 @@ -330,9 +336,9 @@
1.68
1.69 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
1.70
1.71 - typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.72 + typedef FindArcTagIndicator<Digraph> FindArcTag;
1.73 Arc findArc(const Node& u, const Node& v,
1.74 - const Arc& prev = INVALID) {
1.75 + const Arc& prev = INVALID) const {
1.76 return Parent::findArc(v, u, prev);
1.77 }
1.78
1.79 @@ -340,41 +346,56 @@
1.80
1.81 /// \ingroup graph_adaptors
1.82 ///
1.83 - /// \brief A digraph adaptor which reverses the orientation of the arcs.
1.84 + /// \brief Adaptor class for reversing the orientation of the arcs in
1.85 + /// a digraph.
1.86 ///
1.87 - /// ReverseDigraph reverses the arcs in the adapted digraph. The
1.88 - /// SubDigraph is conform to the \ref concepts::Digraph
1.89 - /// "Digraph concept".
1.90 + /// ReverseDigraph can be used for reversing the arcs in a digraph.
1.91 + /// It conforms to the \ref concepts::Digraph "Digraph" concept.
1.92 ///
1.93 - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.94 - /// "Digraph concept". The type can be specified to be const.
1.95 - template<typename _Digraph>
1.96 + /// The adapted digraph can also be modified through this adaptor
1.97 + /// by adding or removing nodes or arcs, unless the \c GR template
1.98 + /// parameter is set to be \c const.
1.99 + ///
1.100 + /// \tparam GR The type of the adapted digraph.
1.101 + /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.102 + /// It can also be specified to be \c const.
1.103 + ///
1.104 + /// \note The \c Node and \c Arc types of this adaptor and the adapted
1.105 + /// digraph are convertible to each other.
1.106 + template<typename GR>
1.107 +#ifdef DOXYGEN
1.108 + class ReverseDigraph {
1.109 +#else
1.110 class ReverseDigraph :
1.111 - public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
1.112 + public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
1.113 +#endif
1.114 public:
1.115 - typedef _Digraph Digraph;
1.116 - typedef DigraphAdaptorExtender<
1.117 - ReverseDigraphBase<_Digraph> > Parent;
1.118 + /// The type of the adapted digraph.
1.119 + typedef GR Digraph;
1.120 + typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
1.121 protected:
1.122 ReverseDigraph() { }
1.123 public:
1.124
1.125 /// \brief Constructor
1.126 ///
1.127 - /// Creates a reverse digraph adaptor for the given digraph
1.128 + /// Creates a reverse digraph adaptor for the given digraph.
1.129 explicit ReverseDigraph(Digraph& digraph) {
1.130 Parent::setDigraph(digraph);
1.131 }
1.132 };
1.133
1.134 - /// \brief Just gives back a reverse digraph adaptor
1.135 + /// \brief Returns a read-only ReverseDigraph adaptor
1.136 ///
1.137 - /// Just gives back a reverse digraph adaptor
1.138 - template<typename Digraph>
1.139 - ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
1.140 - return ReverseDigraph<const Digraph>(digraph);
1.141 + /// This function just returns a read-only \ref ReverseDigraph adaptor.
1.142 + /// \ingroup graph_adaptors
1.143 + /// \relates ReverseDigraph
1.144 + template<typename GR>
1.145 + ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
1.146 + return ReverseDigraph<const GR>(digraph);
1.147 }
1.148
1.149 +
1.150 template <typename _Digraph, typename _NodeFilterMap,
1.151 typename _ArcFilterMap, bool _checked = true>
1.152 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
1.153 @@ -457,21 +478,18 @@
1.154 Parent::nextOut(i);
1.155 }
1.156
1.157 - void hide(const Node& n) const { _node_filter->set(n, false); }
1.158 - void hide(const Arc& a) const { _arc_filter->set(a, false); }
1.159 -
1.160 - void unHide(const Node& n) const { _node_filter->set(n, true); }
1.161 - void unHide(const Arc& a) const { _arc_filter->set(a, true); }
1.162 -
1.163 - bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.164 - bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
1.165 + void status(const Node& n, bool v) const { _node_filter->set(n, v); }
1.166 + void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
1.167 +
1.168 + bool status(const Node& n) const { return (*_node_filter)[n]; }
1.169 + bool status(const Arc& a) const { return (*_arc_filter)[a]; }
1.170
1.171 typedef False NodeNumTag;
1.172 - typedef False EdgeNumTag;
1.173 -
1.174 - typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.175 + typedef False ArcNumTag;
1.176 +
1.177 + typedef FindArcTagIndicator<Digraph> FindArcTag;
1.178 Arc findArc(const Node& source, const Node& target,
1.179 - const Arc& prev = INVALID) {
1.180 + const Arc& prev = INVALID) const {
1.181 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.182 return INVALID;
1.183 }
1.184 @@ -600,21 +618,18 @@
1.185 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
1.186 }
1.187
1.188 - void hide(const Node& n) const { _node_filter->set(n, false); }
1.189 - void hide(const Arc& e) const { _arc_filter->set(e, false); }
1.190 -
1.191 - void unHide(const Node& n) const { _node_filter->set(n, true); }
1.192 - void unHide(const Arc& e) const { _arc_filter->set(e, true); }
1.193 -
1.194 - bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.195 - bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
1.196 + void status(const Node& n, bool v) const { _node_filter->set(n, v); }
1.197 + void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
1.198 +
1.199 + bool status(const Node& n) const { return (*_node_filter)[n]; }
1.200 + bool status(const Arc& a) const { return (*_arc_filter)[a]; }
1.201
1.202 typedef False NodeNumTag;
1.203 - typedef False EdgeNumTag;
1.204 -
1.205 - typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.206 + typedef False ArcNumTag;
1.207 +
1.208 + typedef FindArcTagIndicator<Digraph> FindArcTag;
1.209 Arc findArc(const Node& source, const Node& target,
1.210 - const Arc& prev = INVALID) {
1.211 + const Arc& prev = INVALID) const {
1.212 if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.213 return INVALID;
1.214 }
1.215 @@ -679,42 +694,57 @@
1.216
1.217 /// \ingroup graph_adaptors
1.218 ///
1.219 - /// \brief An adaptor for hiding nodes and arcs in a digraph
1.220 + /// \brief Adaptor class for hiding nodes and arcs in a digraph
1.221 ///
1.222 - /// SubDigraph hides nodes and arcs in a digraph. A bool node map
1.223 - /// and a bool arc map must be specified, which define the filters
1.224 - /// for nodes and arcs. Just the nodes and arcs with true value are
1.225 - /// shown in the subdigraph. The SubDigraph is conform to the \ref
1.226 - /// concepts::Digraph "Digraph concept". If the \c _checked parameter
1.227 - /// is true, then the arcs incident to filtered nodes are also
1.228 - /// filtered out.
1.229 + /// SubDigraph can be used for hiding nodes and arcs in a digraph.
1.230 + /// A \c bool node map and a \c bool arc map must be specified, which
1.231 + /// define the filters for nodes and arcs.
1.232 + /// Only the nodes and arcs with \c true filter value are
1.233 + /// shown in the subdigraph. The arcs that are incident to hidden
1.234 + /// nodes are also filtered out.
1.235 + /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
1.236 ///
1.237 - /// \tparam _Digraph It must be conform to the \ref
1.238 - /// concepts::Digraph "Digraph concept". The type can be specified
1.239 - /// to const.
1.240 - /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
1.241 - /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
1.242 - /// \tparam _checked If the parameter is false then the arc filtering
1.243 - /// is not checked with respect to node filter. Otherwise, each arc
1.244 - /// is automatically filtered, which is incident to a filtered node.
1.245 + /// The adapted digraph can also be modified through this adaptor
1.246 + /// by adding or removing nodes or arcs, unless the \c GR template
1.247 + /// parameter is set to be \c const.
1.248 + ///
1.249 + /// \tparam GR The type of the adapted digraph.
1.250 + /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.251 + /// It can also be specified to be \c const.
1.252 + /// \tparam NF The type of the node filter map.
1.253 + /// It must be a \c bool (or convertible) node map of the
1.254 + /// adapted digraph. The default type is
1.255 + /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>".
1.256 + /// \tparam AF The type of the arc filter map.
1.257 + /// It must be \c bool (or convertible) arc map of the
1.258 + /// adapted digraph. The default type is
1.259 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
1.260 + ///
1.261 + /// \note The \c Node and \c Arc types of this adaptor and the adapted
1.262 + /// digraph are convertible to each other.
1.263 ///
1.264 /// \see FilterNodes
1.265 /// \see FilterArcs
1.266 - template<typename _Digraph,
1.267 - typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.268 - typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
1.269 - bool _checked = true>
1.270 - class SubDigraph
1.271 - : public DigraphAdaptorExtender<
1.272 - SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
1.273 +#ifdef DOXYGEN
1.274 + template<typename GR, typename NF, typename AF>
1.275 + class SubDigraph {
1.276 +#else
1.277 + template<typename GR,
1.278 + typename NF = typename GR::template NodeMap<bool>,
1.279 + typename AF = typename GR::template ArcMap<bool> >
1.280 + class SubDigraph :
1.281 + public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
1.282 +#endif
1.283 public:
1.284 - typedef _Digraph Digraph;
1.285 - typedef _NodeFilterMap NodeFilterMap;
1.286 - typedef _ArcFilterMap ArcFilterMap;
1.287 -
1.288 - typedef DigraphAdaptorExtender<
1.289 - SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
1.290 - Parent;
1.291 + /// The type of the adapted digraph.
1.292 + typedef GR Digraph;
1.293 + /// The type of the node filter map.
1.294 + typedef NF NodeFilterMap;
1.295 + /// The type of the arc filter map.
1.296 + typedef AF ArcFilterMap;
1.297 +
1.298 + typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >
1.299 + Parent;
1.300
1.301 typedef typename Parent::Node Node;
1.302 typedef typename Parent::Arc Arc;
1.303 @@ -725,8 +755,8 @@
1.304
1.305 /// \brief Constructor
1.306 ///
1.307 - /// Creates a subdigraph for the given digraph with
1.308 - /// given node and arc map filters.
1.309 + /// Creates a subdigraph for the given digraph with the
1.310 + /// given node and arc filter maps.
1.311 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
1.312 ArcFilterMap& arc_filter) {
1.313 setDigraph(digraph);
1.314 @@ -734,88 +764,106 @@
1.315 setArcFilterMap(arc_filter);
1.316 }
1.317
1.318 - /// \brief Hides the node of the graph
1.319 + /// \brief Sets the status of the given node
1.320 ///
1.321 - /// This function hides \c n in the digraph, i.e. the iteration
1.322 - /// jumps over it. This is done by simply setting the value of \c n
1.323 - /// to be false in the corresponding node-map.
1.324 - void hide(const Node& n) const { Parent::hide(n); }
1.325 -
1.326 - /// \brief Hides the arc of the graph
1.327 + /// This function sets the status of the given node.
1.328 + /// It is done by simply setting the assigned value of \c n
1.329 + /// to \c v in the node filter map.
1.330 + void status(const Node& n, bool v) const { Parent::status(n, v); }
1.331 +
1.332 + /// \brief Sets the status of the given arc
1.333 ///
1.334 - /// This function hides \c a in the digraph, i.e. the iteration
1.335 - /// jumps over it. This is done by simply setting the value of \c a
1.336 - /// to be false in the corresponding arc-map.
1.337 - void hide(const Arc& a) const { Parent::hide(a); }
1.338 -
1.339 - /// \brief Unhides the node of the graph
1.340 + /// This function sets the status of the given arc.
1.341 + /// It is done by simply setting the assigned value of \c a
1.342 + /// to \c v in the arc filter map.
1.343 + void status(const Arc& a, bool v) const { Parent::status(a, v); }
1.344 +
1.345 + /// \brief Returns the status of the given node
1.346 ///
1.347 - /// The value of \c n is set to be true in the node-map which stores
1.348 - /// hide information. If \c n was hidden previuosly, then it is shown
1.349 - /// again
1.350 - void unHide(const Node& n) const { Parent::unHide(n); }
1.351 -
1.352 - /// \brief Unhides the arc of the graph
1.353 + /// This function returns the status of the given node.
1.354 + /// It is \c true if the given node is enabled (i.e. not hidden).
1.355 + bool status(const Node& n) const { return Parent::status(n); }
1.356 +
1.357 + /// \brief Returns the status of the given arc
1.358 ///
1.359 - /// The value of \c a is set to be true in the arc-map which stores
1.360 - /// hide information. If \c a was hidden previuosly, then it is shown
1.361 - /// again
1.362 - void unHide(const Arc& a) const { Parent::unHide(a); }
1.363 -
1.364 - /// \brief Returns true if \c n is hidden.
1.365 + /// This function returns the status of the given arc.
1.366 + /// It is \c true if the given arc is enabled (i.e. not hidden).
1.367 + bool status(const Arc& a) const { return Parent::status(a); }
1.368 +
1.369 + /// \brief Disables the given node
1.370 ///
1.371 - /// Returns true if \c n is hidden.
1.372 + /// This function disables the given node in the subdigraph,
1.373 + /// so the iteration jumps over it.
1.374 + /// It is the same as \ref status() "status(n, false)".
1.375 + void disable(const Node& n) const { Parent::status(n, false); }
1.376 +
1.377 + /// \brief Disables the given arc
1.378 ///
1.379 - bool hidden(const Node& n) const { return Parent::hidden(n); }
1.380 -
1.381 - /// \brief Returns true if \c a is hidden.
1.382 + /// This function disables the given arc in the subdigraph,
1.383 + /// so the iteration jumps over it.
1.384 + /// It is the same as \ref status() "status(a, false)".
1.385 + void disable(const Arc& a) const { Parent::status(a, false); }
1.386 +
1.387 + /// \brief Enables the given node
1.388 ///
1.389 - /// Returns true if \c a is hidden.
1.390 + /// This function enables the given node in the subdigraph.
1.391 + /// It is the same as \ref status() "status(n, true)".
1.392 + void enable(const Node& n) const { Parent::status(n, true); }
1.393 +
1.394 + /// \brief Enables the given arc
1.395 ///
1.396 - bool hidden(const Arc& a) const { return Parent::hidden(a); }
1.397 + /// This function enables the given arc in the subdigraph.
1.398 + /// It is the same as \ref status() "status(a, true)".
1.399 + void enable(const Arc& a) const { Parent::status(a, true); }
1.400
1.401 };
1.402
1.403 - /// \brief Just gives back a subdigraph
1.404 + /// \brief Returns a read-only SubDigraph adaptor
1.405 ///
1.406 - /// Just gives back a subdigraph
1.407 - template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.408 - SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
1.409 - subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
1.410 - return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
1.411 - (digraph, nfm, afm);
1.412 + /// This function just returns a read-only \ref SubDigraph adaptor.
1.413 + /// \ingroup graph_adaptors
1.414 + /// \relates SubDigraph
1.415 + template<typename GR, typename NF, typename AF>
1.416 + SubDigraph<const GR, NF, AF>
1.417 + subDigraph(const GR& digraph,
1.418 + NF& node_filter_map, AF& arc_filter_map) {
1.419 + return SubDigraph<const GR, NF, AF>
1.420 + (digraph, node_filter_map, arc_filter_map);
1.421 }
1.422
1.423 - template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.424 - SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
1.425 - subDigraph(const Digraph& digraph,
1.426 - const NodeFilterMap& nfm, ArcFilterMap& afm) {
1.427 - return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
1.428 - (digraph, nfm, afm);
1.429 + template<typename GR, typename NF, typename AF>
1.430 + SubDigraph<const GR, const NF, AF>
1.431 + subDigraph(const GR& digraph,
1.432 + const NF& node_filter_map, AF& arc_filter_map) {
1.433 + return SubDigraph<const GR, const NF, AF>
1.434 + (digraph, node_filter_map, arc_filter_map);
1.435 }
1.436
1.437 - template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.438 - SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
1.439 - subDigraph(const Digraph& digraph,
1.440 - NodeFilterMap& nfm, const ArcFilterMap& afm) {
1.441 - return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
1.442 - (digraph, nfm, afm);
1.443 + template<typename GR, typename NF, typename AF>
1.444 + SubDigraph<const GR, NF, const AF>
1.445 + subDigraph(const GR& digraph,
1.446 + NF& node_filter_map, const AF& arc_filter_map) {
1.447 + return SubDigraph<const GR, NF, const AF>
1.448 + (digraph, node_filter_map, arc_filter_map);
1.449 }
1.450
1.451 - template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.452 - SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
1.453 - subDigraph(const Digraph& digraph,
1.454 - const NodeFilterMap& nfm, const ArcFilterMap& afm) {
1.455 - return SubDigraph<const Digraph, const NodeFilterMap,
1.456 - const ArcFilterMap>(digraph, nfm, afm);
1.457 + template<typename GR, typename NF, typename AF>
1.458 + SubDigraph<const GR, const NF, const AF>
1.459 + subDigraph(const GR& digraph,
1.460 + const NF& node_filter_map, const AF& arc_filter_map) {
1.461 + return SubDigraph<const GR, const NF, const AF>
1.462 + (digraph, node_filter_map, arc_filter_map);
1.463 }
1.464
1.465
1.466 - template <typename _Graph, typename NodeFilterMap,
1.467 - typename EdgeFilterMap, bool _checked = true>
1.468 + template <typename _Graph, typename _NodeFilterMap,
1.469 + typename _EdgeFilterMap, bool _checked = true>
1.470 class SubGraphBase : public GraphAdaptorBase<_Graph> {
1.471 public:
1.472 typedef _Graph Graph;
1.473 + typedef _NodeFilterMap NodeFilterMap;
1.474 + typedef _EdgeFilterMap EdgeFilterMap;
1.475 +
1.476 typedef SubGraphBase Adaptor;
1.477 typedef GraphAdaptorBase<_Graph> Parent;
1.478 protected:
1.479 @@ -925,21 +973,19 @@
1.480 Parent::nextInc(i, d);
1.481 }
1.482
1.483 - void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.484 - void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.485 -
1.486 - void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.487 - void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.488 -
1.489 - bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.490 - bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.491 + void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
1.492 + void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
1.493 +
1.494 + bool status(const Node& n) const { return (*_node_filter_map)[n]; }
1.495 + bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
1.496
1.497 typedef False NodeNumTag;
1.498 + typedef False ArcNumTag;
1.499 typedef False EdgeNumTag;
1.500
1.501 - typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.502 + typedef FindArcTagIndicator<Graph> FindArcTag;
1.503 Arc findArc(const Node& u, const Node& v,
1.504 - const Arc& prev = INVALID) {
1.505 + const Arc& prev = INVALID) const {
1.506 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.507 return INVALID;
1.508 }
1.509 @@ -949,8 +995,10 @@
1.510 }
1.511 return arc;
1.512 }
1.513 +
1.514 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.515 Edge findEdge(const Node& u, const Node& v,
1.516 - const Edge& prev = INVALID) {
1.517 + const Edge& prev = INVALID) const {
1.518 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.519 return INVALID;
1.520 }
1.521 @@ -1039,11 +1087,14 @@
1.522
1.523 };
1.524
1.525 - template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.526 - class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1.527 + template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
1.528 + class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
1.529 : public GraphAdaptorBase<_Graph> {
1.530 public:
1.531 typedef _Graph Graph;
1.532 + typedef _NodeFilterMap NodeFilterMap;
1.533 + typedef _EdgeFilterMap EdgeFilterMap;
1.534 +
1.535 typedef SubGraphBase Adaptor;
1.536 typedef GraphAdaptorBase<_Graph> Parent;
1.537 protected:
1.538 @@ -1121,29 +1172,29 @@
1.539 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.540 }
1.541
1.542 - void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.543 - void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.544 -
1.545 - void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.546 - void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.547 -
1.548 - bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.549 - bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.550 + void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
1.551 + void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
1.552 +
1.553 + bool status(const Node& n) const { return (*_node_filter_map)[n]; }
1.554 + bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
1.555
1.556 typedef False NodeNumTag;
1.557 + typedef False ArcNumTag;
1.558 typedef False EdgeNumTag;
1.559
1.560 - typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.561 + typedef FindArcTagIndicator<Graph> FindArcTag;
1.562 Arc findArc(const Node& u, const Node& v,
1.563 - const Arc& prev = INVALID) {
1.564 + const Arc& prev = INVALID) const {
1.565 Arc arc = Parent::findArc(u, v, prev);
1.566 while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.567 arc = Parent::findArc(u, v, arc);
1.568 }
1.569 return arc;
1.570 }
1.571 +
1.572 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.573 Edge findEdge(const Node& u, const Node& v,
1.574 - const Edge& prev = INVALID) {
1.575 + const Edge& prev = INVALID) const {
1.576 Edge edge = Parent::findEdge(u, v, prev);
1.577 while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.578 edge = Parent::findEdge(u, v, edge);
1.579 @@ -1231,37 +1282,58 @@
1.580
1.581 /// \ingroup graph_adaptors
1.582 ///
1.583 - /// \brief A graph adaptor for hiding nodes and edges in an
1.584 - /// undirected graph.
1.585 + /// \brief Adaptor class for hiding nodes and edges in an undirected
1.586 + /// graph.
1.587 ///
1.588 - /// SubGraph hides nodes and edges in a graph. A bool node map and a
1.589 - /// bool edge map must be specified, which define the filters for
1.590 - /// nodes and edges. Just the nodes and edges with true value are
1.591 - /// shown in the subgraph. The SubGraph is conform to the \ref
1.592 - /// concepts::Graph "Graph concept". If the \c _checked parameter is
1.593 - /// true, then the edges incident to filtered nodes are also
1.594 - /// filtered out.
1.595 + /// SubGraph can be used for hiding nodes and edges in a graph.
1.596 + /// A \c bool node map and a \c bool edge map must be specified, which
1.597 + /// define the filters for nodes and edges.
1.598 + /// Only the nodes and edges with \c true filter value are
1.599 + /// shown in the subgraph. The edges that are incident to hidden
1.600 + /// nodes are also filtered out.
1.601 + /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
1.602 ///
1.603 - /// \tparam _Graph It must be conform to the \ref
1.604 - /// concepts::Graph "Graph concept". The type can be specified
1.605 - /// to const.
1.606 - /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1.607 - /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
1.608 - /// \tparam _checked If the parameter is false then the edge filtering
1.609 - /// is not checked with respect to node filter. Otherwise, each edge
1.610 - /// is automatically filtered, which is incident to a filtered node.
1.611 + /// The adapted graph can also be modified through this adaptor
1.612 + /// by adding or removing nodes or edges, unless the \c GR template
1.613 + /// parameter is set to be \c const.
1.614 + ///
1.615 + /// \tparam GR The type of the adapted graph.
1.616 + /// It must conform to the \ref concepts::Graph "Graph" concept.
1.617 + /// It can also be specified to be \c const.
1.618 + /// \tparam NF The type of the node filter map.
1.619 + /// It must be a \c bool (or convertible) node map of the
1.620 + /// adapted graph. The default type is
1.621 + /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1.622 + /// \tparam EF The type of the edge filter map.
1.623 + /// It must be a \c bool (or convertible) edge map of the
1.624 + /// adapted graph. The default type is
1.625 + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1.626 + ///
1.627 + /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1.628 + /// adapted graph are convertible to each other.
1.629 ///
1.630 /// \see FilterNodes
1.631 /// \see FilterEdges
1.632 - template<typename _Graph, typename NodeFilterMap,
1.633 - typename EdgeFilterMap, bool _checked = true>
1.634 - class SubGraph
1.635 - : public GraphAdaptorExtender<
1.636 - SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
1.637 +#ifdef DOXYGEN
1.638 + template<typename GR, typename NF, typename EF>
1.639 + class SubGraph {
1.640 +#else
1.641 + template<typename GR,
1.642 + typename NF = typename GR::template NodeMap<bool>,
1.643 + typename EF = typename GR::template EdgeMap<bool> >
1.644 + class SubGraph :
1.645 + public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {
1.646 +#endif
1.647 public:
1.648 - typedef _Graph Graph;
1.649 - typedef GraphAdaptorExtender<
1.650 - SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1.651 + /// The type of the adapted graph.
1.652 + typedef GR Graph;
1.653 + /// The type of the node filter map.
1.654 + typedef NF NodeFilterMap;
1.655 + /// The type of the edge filter map.
1.656 + typedef EF EdgeFilterMap;
1.657 +
1.658 + typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >
1.659 + Parent;
1.660
1.661 typedef typename Parent::Node Node;
1.662 typedef typename Parent::Edge Edge;
1.663 @@ -1272,132 +1344,153 @@
1.664
1.665 /// \brief Constructor
1.666 ///
1.667 - /// Creates a subgraph for the given graph with given node and
1.668 - /// edge map filters.
1.669 - SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
1.670 + /// Creates a subgraph for the given graph with the given node
1.671 + /// and edge filter maps.
1.672 + SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
1.673 EdgeFilterMap& edge_filter_map) {
1.674 - setGraph(_graph);
1.675 + setGraph(graph);
1.676 setNodeFilterMap(node_filter_map);
1.677 setEdgeFilterMap(edge_filter_map);
1.678 }
1.679
1.680 - /// \brief Hides the node of the graph
1.681 + /// \brief Sets the status of the given node
1.682 ///
1.683 - /// This function hides \c n in the graph, i.e. the iteration
1.684 - /// jumps over it. This is done by simply setting the value of \c n
1.685 - /// to be false in the corresponding node-map.
1.686 - void hide(const Node& n) const { Parent::hide(n); }
1.687 -
1.688 - /// \brief Hides the edge of the graph
1.689 + /// This function sets the status of the given node.
1.690 + /// It is done by simply setting the assigned value of \c n
1.691 + /// to \c v in the node filter map.
1.692 + void status(const Node& n, bool v) const { Parent::status(n, v); }
1.693 +
1.694 + /// \brief Sets the status of the given edge
1.695 ///
1.696 - /// This function hides \c e in the graph, i.e. the iteration
1.697 - /// jumps over it. This is done by simply setting the value of \c e
1.698 - /// to be false in the corresponding edge-map.
1.699 - void hide(const Edge& e) const { Parent::hide(e); }
1.700 -
1.701 - /// \brief Unhides the node of the graph
1.702 + /// This function sets the status of the given edge.
1.703 + /// It is done by simply setting the assigned value of \c e
1.704 + /// to \c v in the edge filter map.
1.705 + void status(const Edge& e, bool v) const { Parent::status(e, v); }
1.706 +
1.707 + /// \brief Returns the status of the given node
1.708 ///
1.709 - /// The value of \c n is set to be true in the node-map which stores
1.710 - /// hide information. If \c n was hidden previuosly, then it is shown
1.711 - /// again
1.712 - void unHide(const Node& n) const { Parent::unHide(n); }
1.713 -
1.714 - /// \brief Unhides the edge of the graph
1.715 + /// This function returns the status of the given node.
1.716 + /// It is \c true if the given node is enabled (i.e. not hidden).
1.717 + bool status(const Node& n) const { return Parent::status(n); }
1.718 +
1.719 + /// \brief Returns the status of the given edge
1.720 ///
1.721 - /// The value of \c e is set to be true in the edge-map which stores
1.722 - /// hide information. If \c e was hidden previuosly, then it is shown
1.723 - /// again
1.724 - void unHide(const Edge& e) const { Parent::unHide(e); }
1.725 -
1.726 - /// \brief Returns true if \c n is hidden.
1.727 + /// This function returns the status of the given edge.
1.728 + /// It is \c true if the given edge is enabled (i.e. not hidden).
1.729 + bool status(const Edge& e) const { return Parent::status(e); }
1.730 +
1.731 + /// \brief Disables the given node
1.732 ///
1.733 - /// Returns true if \c n is hidden.
1.734 + /// This function disables the given node in the subdigraph,
1.735 + /// so the iteration jumps over it.
1.736 + /// It is the same as \ref status() "status(n, false)".
1.737 + void disable(const Node& n) const { Parent::status(n, false); }
1.738 +
1.739 + /// \brief Disables the given edge
1.740 ///
1.741 - bool hidden(const Node& n) const { return Parent::hidden(n); }
1.742 -
1.743 - /// \brief Returns true if \c e is hidden.
1.744 + /// This function disables the given edge in the subgraph,
1.745 + /// so the iteration jumps over it.
1.746 + /// It is the same as \ref status() "status(e, false)".
1.747 + void disable(const Edge& e) const { Parent::status(e, false); }
1.748 +
1.749 + /// \brief Enables the given node
1.750 ///
1.751 - /// Returns true if \c e is hidden.
1.752 + /// This function enables the given node in the subdigraph.
1.753 + /// It is the same as \ref status() "status(n, true)".
1.754 + void enable(const Node& n) const { Parent::status(n, true); }
1.755 +
1.756 + /// \brief Enables the given edge
1.757 ///
1.758 - bool hidden(const Edge& e) const { return Parent::hidden(e); }
1.759 + /// This function enables the given edge in the subgraph.
1.760 + /// It is the same as \ref status() "status(e, true)".
1.761 + void enable(const Edge& e) const { Parent::status(e, true); }
1.762 +
1.763 };
1.764
1.765 - /// \brief Just gives back a subgraph
1.766 + /// \brief Returns a read-only SubGraph adaptor
1.767 ///
1.768 - /// Just gives back a subgraph
1.769 - template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.770 - SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1.771 - subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1.772 - return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1.773 + /// This function just returns a read-only \ref SubGraph adaptor.
1.774 + /// \ingroup graph_adaptors
1.775 + /// \relates SubGraph
1.776 + template<typename GR, typename NF, typename EF>
1.777 + SubGraph<const GR, NF, EF>
1.778 + subGraph(const GR& graph,
1.779 + NF& node_filter_map, EF& edge_filter_map) {
1.780 + return SubGraph<const GR, NF, EF>
1.781 + (graph, node_filter_map, edge_filter_map);
1.782 }
1.783
1.784 - template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.785 - SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1.786 - subGraph(const Graph& graph,
1.787 - const NodeFilterMap& nfm, ArcFilterMap& efm) {
1.788 - return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1.789 - (graph, nfm, efm);
1.790 + template<typename GR, typename NF, typename EF>
1.791 + SubGraph<const GR, const NF, EF>
1.792 + subGraph(const GR& graph,
1.793 + const NF& node_filter_map, EF& edge_filter_map) {
1.794 + return SubGraph<const GR, const NF, EF>
1.795 + (graph, node_filter_map, edge_filter_map);
1.796 }
1.797
1.798 - template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.799 - SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1.800 - subGraph(const Graph& graph,
1.801 - NodeFilterMap& nfm, const ArcFilterMap& efm) {
1.802 - return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1.803 - (graph, nfm, efm);
1.804 + template<typename GR, typename NF, typename EF>
1.805 + SubGraph<const GR, NF, const EF>
1.806 + subGraph(const GR& graph,
1.807 + NF& node_filter_map, const EF& edge_filter_map) {
1.808 + return SubGraph<const GR, NF, const EF>
1.809 + (graph, node_filter_map, edge_filter_map);
1.810 }
1.811
1.812 - template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.813 - SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1.814 - subGraph(const Graph& graph,
1.815 - const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1.816 - return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1.817 - (graph, nfm, efm);
1.818 + template<typename GR, typename NF, typename EF>
1.819 + SubGraph<const GR, const NF, const EF>
1.820 + subGraph(const GR& graph,
1.821 + const NF& node_filter_map, const EF& edge_filter_map) {
1.822 + return SubGraph<const GR, const NF, const EF>
1.823 + (graph, node_filter_map, edge_filter_map);
1.824 }
1.825
1.826 +
1.827 /// \ingroup graph_adaptors
1.828 ///
1.829 - /// \brief An adaptor for hiding nodes from a digraph or a graph.
1.830 + /// \brief Adaptor class for hiding nodes in a digraph or a graph.
1.831 ///
1.832 - /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
1.833 - /// node map must be specified, which defines the filters for
1.834 - /// nodes. Just the unfiltered nodes and the arcs or edges incident
1.835 - /// to unfiltered nodes are shown in the subdigraph or subgraph. The
1.836 - /// FilterNodes is conform to the \ref concepts::Digraph
1.837 - /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
1.838 - /// on the \c _Digraph template parameter. If the \c _checked
1.839 - /// parameter is true, then the arc or edges incident to filtered nodes
1.840 - /// are also filtered out.
1.841 + /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
1.842 + /// graph. A \c bool node map must be specified, which defines the filter
1.843 + /// for the nodes. Only the nodes with \c true filter value and the
1.844 + /// arcs/edges incident to nodes both with \c true filter value are shown
1.845 + /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
1.846 + /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
1.847 + /// depending on the \c GR template parameter.
1.848 ///
1.849 - /// \tparam _Digraph It must be conform to the \ref
1.850 - /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
1.851 - /// "Graph concept". The type can be specified to be const.
1.852 - /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1.853 - /// \tparam _checked If the parameter is false then the arc or edge
1.854 - /// filtering is not checked with respect to node filter. In this
1.855 - /// case just isolated nodes can be filtered out from the
1.856 - /// graph.
1.857 + /// The adapted (di)graph can also be modified through this adaptor
1.858 + /// by adding or removing nodes or arcs/edges, unless the \c GR template
1.859 + /// parameter is set to be \c const.
1.860 + ///
1.861 + /// \tparam GR The type of the adapted digraph or graph.
1.862 + /// It must conform to the \ref concepts::Digraph "Digraph" concept
1.863 + /// or the \ref concepts::Graph "Graph" concept.
1.864 + /// It can also be specified to be \c const.
1.865 + /// \tparam NF The type of the node filter map.
1.866 + /// It must be a \c bool (or convertible) node map of the
1.867 + /// adapted (di)graph. The default type is
1.868 + /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
1.869 + ///
1.870 + /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
1.871 + /// adapted (di)graph are convertible to each other.
1.872 #ifdef DOXYGEN
1.873 - template<typename _Digraph,
1.874 - typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.875 - bool _checked = true>
1.876 + template<typename GR, typename NF>
1.877 + class FilterNodes {
1.878 #else
1.879 - template<typename _Digraph,
1.880 - typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.881 - bool _checked = true,
1.882 + template<typename GR,
1.883 + typename NF = typename GR::template NodeMap<bool>,
1.884 typename Enable = void>
1.885 + class FilterNodes :
1.886 + public DigraphAdaptorExtender<
1.887 + SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
1.888 #endif
1.889 - class FilterNodes
1.890 - : public SubDigraph<_Digraph, _NodeFilterMap,
1.891 - ConstMap<typename _Digraph::Arc, bool>, _checked> {
1.892 public:
1.893
1.894 - typedef _Digraph Digraph;
1.895 - typedef _NodeFilterMap NodeFilterMap;
1.896 -
1.897 - typedef SubDigraph<Digraph, NodeFilterMap,
1.898 - ConstMap<typename Digraph::Arc, bool>, _checked>
1.899 - Parent;
1.900 + typedef GR Digraph;
1.901 + typedef NF NodeFilterMap;
1.902 +
1.903 + typedef DigraphAdaptorExtender<
1.904 + SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
1.905 + Parent;
1.906
1.907 typedef typename Parent::Node Node;
1.908
1.909 @@ -1412,47 +1505,56 @@
1.910
1.911 /// \brief Constructor
1.912 ///
1.913 - /// Creates an adaptor for the given digraph or graph with
1.914 + /// Creates a subgraph for the given digraph or graph with the
1.915 /// given node filter map.
1.916 - FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
1.917 - Parent(), const_true_map(true) {
1.918 - Parent::setDigraph(_digraph);
1.919 + FilterNodes(GR& graph, NodeFilterMap& node_filter) :
1.920 + Parent(), const_true_map(true)
1.921 + {
1.922 + Parent::setDigraph(graph);
1.923 Parent::setNodeFilterMap(node_filter);
1.924 Parent::setArcFilterMap(const_true_map);
1.925 }
1.926
1.927 - /// \brief Hides the node of the graph
1.928 + /// \brief Sets the status of the given node
1.929 ///
1.930 - /// This function hides \c n in the digraph or graph, i.e. the iteration
1.931 - /// jumps over it. This is done by simply setting the value of \c n
1.932 - /// to be false in the corresponding node map.
1.933 - void hide(const Node& n) const { Parent::hide(n); }
1.934 -
1.935 - /// \brief Unhides the node of the graph
1.936 + /// This function sets the status of the given node.
1.937 + /// It is done by simply setting the assigned value of \c n
1.938 + /// to \c v in the node filter map.
1.939 + void status(const Node& n, bool v) const { Parent::status(n, v); }
1.940 +
1.941 + /// \brief Returns the status of the given node
1.942 ///
1.943 - /// The value of \c n is set to be true in the node-map which stores
1.944 - /// hide information. If \c n was hidden previuosly, then it is shown
1.945 - /// again
1.946 - void unHide(const Node& n) const { Parent::unHide(n); }
1.947 -
1.948 - /// \brief Returns true if \c n is hidden.
1.949 + /// This function returns the status of the given node.
1.950 + /// It is \c true if the given node is enabled (i.e. not hidden).
1.951 + bool status(const Node& n) const { return Parent::status(n); }
1.952 +
1.953 + /// \brief Disables the given node
1.954 ///
1.955 - /// Returns true if \c n is hidden.
1.956 + /// This function disables the given node, so the iteration
1.957 + /// jumps over it.
1.958 + /// It is the same as \ref status() "status(n, false)".
1.959 + void disable(const Node& n) const { Parent::status(n, false); }
1.960 +
1.961 + /// \brief Enables the given node
1.962 ///
1.963 - bool hidden(const Node& n) const { return Parent::hidden(n); }
1.964 + /// This function enables the given node.
1.965 + /// It is the same as \ref status() "status(n, true)".
1.966 + void enable(const Node& n) const { Parent::status(n, true); }
1.967
1.968 };
1.969
1.970 - template<typename _Graph, typename _NodeFilterMap, bool _checked>
1.971 - class FilterNodes<_Graph, _NodeFilterMap, _checked,
1.972 - typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1.973 - : public SubGraph<_Graph, _NodeFilterMap,
1.974 - ConstMap<typename _Graph::Edge, bool>, _checked> {
1.975 + template<typename GR, typename NF>
1.976 + class FilterNodes<GR, NF,
1.977 + typename enable_if<UndirectedTagIndicator<GR> >::type> :
1.978 + public GraphAdaptorExtender<
1.979 + SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
1.980 +
1.981 public:
1.982 - typedef _Graph Graph;
1.983 - typedef _NodeFilterMap NodeFilterMap;
1.984 - typedef SubGraph<Graph, NodeFilterMap,
1.985 - ConstMap<typename Graph::Edge, bool> > Parent;
1.986 + typedef GR Graph;
1.987 + typedef NF NodeFilterMap;
1.988 + typedef GraphAdaptorExtender<
1.989 + SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
1.990 + Parent;
1.991
1.992 typedef typename Parent::Node Node;
1.993 protected:
1.994 @@ -1471,51 +1573,75 @@
1.995 Parent::setEdgeFilterMap(const_true_map);
1.996 }
1.997
1.998 - void hide(const Node& n) const { Parent::hide(n); }
1.999 - void unHide(const Node& n) const { Parent::unHide(n); }
1.1000 - bool hidden(const Node& n) const { return Parent::hidden(n); }
1.1001 + void status(const Node& n, bool v) const { Parent::status(n, v); }
1.1002 + bool status(const Node& n) const { return Parent::status(n); }
1.1003 + void disable(const Node& n) const { Parent::status(n, false); }
1.1004 + void enable(const Node& n) const { Parent::status(n, true); }
1.1005
1.1006 };
1.1007
1.1008
1.1009 - /// \brief Just gives back a FilterNodes adaptor
1.1010 + /// \brief Returns a read-only FilterNodes adaptor
1.1011 ///
1.1012 - /// Just gives back a FilterNodes adaptor
1.1013 - template<typename Digraph, typename NodeFilterMap>
1.1014 - FilterNodes<const Digraph, NodeFilterMap>
1.1015 - filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1.1016 - return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1.1017 + /// This function just returns a read-only \ref FilterNodes adaptor.
1.1018 + /// \ingroup graph_adaptors
1.1019 + /// \relates FilterNodes
1.1020 + template<typename GR, typename NF>
1.1021 + FilterNodes<const GR, NF>
1.1022 + filterNodes(const GR& graph, NF& node_filter_map) {
1.1023 + return FilterNodes<const GR, NF>(graph, node_filter_map);
1.1024 }
1.1025
1.1026 - template<typename Digraph, typename NodeFilterMap>
1.1027 - FilterNodes<const Digraph, const NodeFilterMap>
1.1028 - filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1.1029 - return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1.1030 + template<typename GR, typename NF>
1.1031 + FilterNodes<const GR, const NF>
1.1032 + filterNodes(const GR& graph, const NF& node_filter_map) {
1.1033 + return FilterNodes<const GR, const NF>(graph, node_filter_map);
1.1034 }
1.1035
1.1036 /// \ingroup graph_adaptors
1.1037 ///
1.1038 - /// \brief An adaptor for hiding arcs from a digraph.
1.1039 + /// \brief Adaptor class for hiding arcs in a digraph.
1.1040 ///
1.1041 - /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
1.1042 - /// be specified, which defines the filters for arcs. Just the
1.1043 - /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
1.1044 - /// conform to the \ref concepts::Digraph "Digraph concept".
1.1045 + /// FilterArcs adaptor can be used for hiding arcs in a digraph.
1.1046 + /// A \c bool arc map must be specified, which defines the filter for
1.1047 + /// the arcs. Only the arcs with \c true filter value are shown in the
1.1048 + /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
1.1049 + /// "Digraph" concept.
1.1050 ///
1.1051 - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.1052 - /// "Digraph concept". The type can be specified to be const.
1.1053 - /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
1.1054 - /// graph.
1.1055 - template<typename _Digraph, typename _ArcFilterMap>
1.1056 + /// The adapted digraph can also be modified through this adaptor
1.1057 + /// by adding or removing nodes or arcs, unless the \c GR template
1.1058 + /// parameter is set to be \c const.
1.1059 + ///
1.1060 + /// \tparam GR The type of the adapted digraph.
1.1061 + /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.1062 + /// It can also be specified to be \c const.
1.1063 + /// \tparam AF The type of the arc filter map.
1.1064 + /// It must be a \c bool (or convertible) arc map of the
1.1065 + /// adapted digraph. The default type is
1.1066 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>".
1.1067 + ///
1.1068 + /// \note The \c Node and \c Arc types of this adaptor and the adapted
1.1069 + /// digraph are convertible to each other.
1.1070 +#ifdef DOXYGEN
1.1071 + template<typename GR,
1.1072 + typename AF>
1.1073 + class FilterArcs {
1.1074 +#else
1.1075 + template<typename GR,
1.1076 + typename AF = typename GR::template ArcMap<bool> >
1.1077 class FilterArcs :
1.1078 - public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1.1079 - _ArcFilterMap, false> {
1.1080 + public DigraphAdaptorExtender<
1.1081 + SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
1.1082 +#endif
1.1083 public:
1.1084 - typedef _Digraph Digraph;
1.1085 - typedef _ArcFilterMap ArcFilterMap;
1.1086 -
1.1087 - typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1.1088 - ArcFilterMap, false> Parent;
1.1089 + /// The type of the adapted digraph.
1.1090 + typedef GR Digraph;
1.1091 + /// The type of the arc filter map.
1.1092 + typedef AF ArcFilterMap;
1.1093 +
1.1094 + typedef DigraphAdaptorExtender<
1.1095 + SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
1.1096 + Parent;
1.1097
1.1098 typedef typename Parent::Arc Arc;
1.1099
1.1100 @@ -1530,8 +1656,8 @@
1.1101
1.1102 /// \brief Constructor
1.1103 ///
1.1104 - /// Creates a FilterArcs adaptor for the given graph with
1.1105 - /// given arc map filter.
1.1106 + /// Creates a subdigraph for the given digraph with the given arc
1.1107 + /// filter map.
1.1108 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1.1109 : Parent(), const_true_map(true) {
1.1110 Parent::setDigraph(digraph);
1.1111 @@ -1539,66 +1665,98 @@
1.1112 Parent::setArcFilterMap(arc_filter);
1.1113 }
1.1114
1.1115 - /// \brief Hides the arc of the graph
1.1116 + /// \brief Sets the status of the given arc
1.1117 ///
1.1118 - /// This function hides \c a in the graph, i.e. the iteration
1.1119 - /// jumps over it. This is done by simply setting the value of \c a
1.1120 - /// to be false in the corresponding arc map.
1.1121 - void hide(const Arc& a) const { Parent::hide(a); }
1.1122 -
1.1123 - /// \brief Unhides the arc of the graph
1.1124 + /// This function sets the status of the given arc.
1.1125 + /// It is done by simply setting the assigned value of \c a
1.1126 + /// to \c v in the arc filter map.
1.1127 + void status(const Arc& a, bool v) const { Parent::status(a, v); }
1.1128 +
1.1129 + /// \brief Returns the status of the given arc
1.1130 ///
1.1131 - /// The value of \c a is set to be true in the arc-map which stores
1.1132 - /// hide information. If \c a was hidden previuosly, then it is shown
1.1133 - /// again
1.1134 - void unHide(const Arc& a) const { Parent::unHide(a); }
1.1135 -
1.1136 - /// \brief Returns true if \c a is hidden.
1.1137 + /// This function returns the status of the given arc.
1.1138 + /// It is \c true if the given arc is enabled (i.e. not hidden).
1.1139 + bool status(const Arc& a) const { return Parent::status(a); }
1.1140 +
1.1141 + /// \brief Disables the given arc
1.1142 ///
1.1143 - /// Returns true if \c a is hidden.
1.1144 + /// This function disables the given arc in the subdigraph,
1.1145 + /// so the iteration jumps over it.
1.1146 + /// It is the same as \ref status() "status(a, false)".
1.1147 + void disable(const Arc& a) const { Parent::status(a, false); }
1.1148 +
1.1149 + /// \brief Enables the given arc
1.1150 ///
1.1151 - bool hidden(const Arc& a) const { return Parent::hidden(a); }
1.1152 + /// This function enables the given arc in the subdigraph.
1.1153 + /// It is the same as \ref status() "status(a, true)".
1.1154 + void enable(const Arc& a) const { Parent::status(a, true); }
1.1155
1.1156 };
1.1157
1.1158 - /// \brief Just gives back an FilterArcs adaptor
1.1159 + /// \brief Returns a read-only FilterArcs adaptor
1.1160 ///
1.1161 - /// Just gives back an FilterArcs adaptor
1.1162 - template<typename Digraph, typename ArcFilterMap>
1.1163 - FilterArcs<const Digraph, ArcFilterMap>
1.1164 - filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1.1165 - return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1.1166 + /// This function just returns a read-only \ref FilterArcs adaptor.
1.1167 + /// \ingroup graph_adaptors
1.1168 + /// \relates FilterArcs
1.1169 + template<typename GR, typename AF>
1.1170 + FilterArcs<const GR, AF>
1.1171 + filterArcs(const GR& digraph, AF& arc_filter_map) {
1.1172 + return FilterArcs<const GR, AF>(digraph, arc_filter_map);
1.1173 }
1.1174
1.1175 - template<typename Digraph, typename ArcFilterMap>
1.1176 - FilterArcs<const Digraph, const ArcFilterMap>
1.1177 - filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1.1178 - return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1.1179 + template<typename GR, typename AF>
1.1180 + FilterArcs<const GR, const AF>
1.1181 + filterArcs(const GR& digraph, const AF& arc_filter_map) {
1.1182 + return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
1.1183 }
1.1184
1.1185 /// \ingroup graph_adaptors
1.1186 ///
1.1187 - /// \brief An adaptor for hiding edges from a graph.
1.1188 + /// \brief Adaptor class for hiding edges in a graph.
1.1189 ///
1.1190 - /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
1.1191 - /// be specified, which defines the filters for edges. Just the
1.1192 - /// unfiltered edges are shown in the subdigraph. The FilterEdges is
1.1193 - /// conform to the \ref concepts::Graph "Graph concept".
1.1194 + /// FilterEdges adaptor can be used for hiding edges in a graph.
1.1195 + /// A \c bool edge map must be specified, which defines the filter for
1.1196 + /// the edges. Only the edges with \c true filter value are shown in the
1.1197 + /// subgraph. This adaptor conforms to the \ref concepts::Graph
1.1198 + /// "Graph" concept.
1.1199 ///
1.1200 - /// \tparam _Graph It must be conform to the \ref concepts::Graph
1.1201 - /// "Graph concept". The type can be specified to be const.
1.1202 - /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
1.1203 - /// graph.
1.1204 - template<typename _Graph, typename _EdgeFilterMap>
1.1205 + /// The adapted graph can also be modified through this adaptor
1.1206 + /// by adding or removing nodes or edges, unless the \c GR template
1.1207 + /// parameter is set to be \c const.
1.1208 + ///
1.1209 + /// \tparam GR The type of the adapted graph.
1.1210 + /// It must conform to the \ref concepts::Graph "Graph" concept.
1.1211 + /// It can also be specified to be \c const.
1.1212 + /// \tparam EF The type of the edge filter map.
1.1213 + /// It must be a \c bool (or convertible) edge map of the
1.1214 + /// adapted graph. The default type is
1.1215 + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1.1216 + ///
1.1217 + /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
1.1218 + /// adapted graph are convertible to each other.
1.1219 +#ifdef DOXYGEN
1.1220 + template<typename GR,
1.1221 + typename EF>
1.1222 + class FilterEdges {
1.1223 +#else
1.1224 + template<typename GR,
1.1225 + typename EF = typename GR::template EdgeMap<bool> >
1.1226 class FilterEdges :
1.1227 - public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1.1228 - _EdgeFilterMap, false> {
1.1229 + public GraphAdaptorExtender<
1.1230 + SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
1.1231 +#endif
1.1232 public:
1.1233 - typedef _Graph Graph;
1.1234 - typedef _EdgeFilterMap EdgeFilterMap;
1.1235 - typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1.1236 - EdgeFilterMap, false> Parent;
1.1237 + /// The type of the adapted graph.
1.1238 + typedef GR Graph;
1.1239 + /// The type of the edge filter map.
1.1240 + typedef EF EdgeFilterMap;
1.1241 +
1.1242 + typedef GraphAdaptorExtender<
1.1243 + SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >
1.1244 + Parent;
1.1245 +
1.1246 typedef typename Parent::Edge Edge;
1.1247 +
1.1248 protected:
1.1249 ConstMap<typename Graph::Node, bool> const_true_map;
1.1250
1.1251 @@ -1610,52 +1768,61 @@
1.1252
1.1253 /// \brief Constructor
1.1254 ///
1.1255 - /// Creates a FilterEdges adaptor for the given graph with
1.1256 - /// given edge map filters.
1.1257 - FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1.1258 + /// Creates a subgraph for the given graph with the given edge
1.1259 + /// filter map.
1.1260 + FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
1.1261 Parent(), const_true_map(true) {
1.1262 - Parent::setGraph(_graph);
1.1263 + Parent::setGraph(graph);
1.1264 Parent::setNodeFilterMap(const_true_map);
1.1265 Parent::setEdgeFilterMap(edge_filter_map);
1.1266 }
1.1267
1.1268 - /// \brief Hides the edge of the graph
1.1269 + /// \brief Sets the status of the given edge
1.1270 ///
1.1271 - /// This function hides \c e in the graph, i.e. the iteration
1.1272 - /// jumps over it. This is done by simply setting the value of \c e
1.1273 - /// to be false in the corresponding edge-map.
1.1274 - void hide(const Edge& e) const { Parent::hide(e); }
1.1275 -
1.1276 - /// \brief Unhides the edge of the graph
1.1277 + /// This function sets the status of the given edge.
1.1278 + /// It is done by simply setting the assigned value of \c e
1.1279 + /// to \c v in the edge filter map.
1.1280 + void status(const Edge& e, bool v) const { Parent::status(e, v); }
1.1281 +
1.1282 + /// \brief Returns the status of the given edge
1.1283 ///
1.1284 - /// The value of \c e is set to be true in the edge-map which stores
1.1285 - /// hide information. If \c e was hidden previuosly, then it is shown
1.1286 - /// again
1.1287 - void unHide(const Edge& e) const { Parent::unHide(e); }
1.1288 -
1.1289 - /// \brief Returns true if \c e is hidden.
1.1290 + /// This function returns the status of the given edge.
1.1291 + /// It is \c true if the given edge is enabled (i.e. not hidden).
1.1292 + bool status(const Edge& e) const { return Parent::status(e); }
1.1293 +
1.1294 + /// \brief Disables the given edge
1.1295 ///
1.1296 - /// Returns true if \c e is hidden.
1.1297 + /// This function disables the given edge in the subgraph,
1.1298 + /// so the iteration jumps over it.
1.1299 + /// It is the same as \ref status() "status(e, false)".
1.1300 + void disable(const Edge& e) const { Parent::status(e, false); }
1.1301 +
1.1302 + /// \brief Enables the given edge
1.1303 ///
1.1304 - bool hidden(const Edge& e) const { return Parent::hidden(e); }
1.1305 + /// This function enables the given edge in the subgraph.
1.1306 + /// It is the same as \ref status() "status(e, true)".
1.1307 + void enable(const Edge& e) const { Parent::status(e, true); }
1.1308
1.1309 };
1.1310
1.1311 - /// \brief Just gives back a FilterEdges adaptor
1.1312 + /// \brief Returns a read-only FilterEdges adaptor
1.1313 ///
1.1314 - /// Just gives back a FilterEdges adaptor
1.1315 - template<typename Graph, typename EdgeFilterMap>
1.1316 - FilterEdges<const Graph, EdgeFilterMap>
1.1317 - filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1.1318 - return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1.1319 + /// This function just returns a read-only \ref FilterEdges adaptor.
1.1320 + /// \ingroup graph_adaptors
1.1321 + /// \relates FilterEdges
1.1322 + template<typename GR, typename EF>
1.1323 + FilterEdges<const GR, EF>
1.1324 + filterEdges(const GR& graph, EF& edge_filter_map) {
1.1325 + return FilterEdges<const GR, EF>(graph, edge_filter_map);
1.1326 }
1.1327
1.1328 - template<typename Graph, typename EdgeFilterMap>
1.1329 - FilterEdges<const Graph, const EdgeFilterMap>
1.1330 - filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1.1331 - return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1.1332 + template<typename GR, typename EF>
1.1333 + FilterEdges<const GR, const EF>
1.1334 + filterEdges(const GR& graph, const EF& edge_filter_map) {
1.1335 + return FilterEdges<const GR, const EF>(graph, edge_filter_map);
1.1336 }
1.1337
1.1338 +
1.1339 template <typename _Digraph>
1.1340 class UndirectorBase {
1.1341 public:
1.1342 @@ -1695,8 +1862,6 @@
1.1343 }
1.1344 };
1.1345
1.1346 -
1.1347 -
1.1348 void first(Node& n) const {
1.1349 _digraph->first(n);
1.1350 }
1.1351 @@ -1845,12 +2010,15 @@
1.1352 void clear() { _digraph->clear(); }
1.1353
1.1354 typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.1355 - int nodeNum() const { return 2 * _digraph->arcNum(); }
1.1356 - typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1.1357 + int nodeNum() const { return _digraph->nodeNum(); }
1.1358 +
1.1359 + typedef ArcNumTagIndicator<Digraph> ArcNumTag;
1.1360 int arcNum() const { return 2 * _digraph->arcNum(); }
1.1361 +
1.1362 + typedef ArcNumTag EdgeNumTag;
1.1363 int edgeNum() const { return _digraph->arcNum(); }
1.1364
1.1365 - typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.1366 + typedef FindArcTagIndicator<Digraph> FindArcTag;
1.1367 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1.1368 if (p == INVALID) {
1.1369 Edge arc = _digraph->findArc(s, t);
1.1370 @@ -1869,6 +2037,7 @@
1.1371 return INVALID;
1.1372 }
1.1373
1.1374 + typedef FindArcTag FindEdgeTag;
1.1375 Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1.1376 if (s != t) {
1.1377 if (p == INVALID) {
1.1378 @@ -1876,7 +2045,7 @@
1.1379 if (arc != INVALID) return arc;
1.1380 arc = _digraph->findArc(t, s);
1.1381 if (arc != INVALID) return arc;
1.1382 - } else if (_digraph->s(p) == s) {
1.1383 + } else if (_digraph->source(p) == s) {
1.1384 Edge arc = _digraph->findArc(s, t, p);
1.1385 if (arc != INVALID) return arc;
1.1386 arc = _digraph->findArc(t, s);
1.1387 @@ -1905,6 +2074,10 @@
1.1388
1.1389 typedef _Value Value;
1.1390 typedef Arc Key;
1.1391 + typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
1.1392 + typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
1.1393 + typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
1.1394 + typedef typename MapTraits<MapImpl>::ReturnValue Reference;
1.1395
1.1396 ArcMapBase(const Adaptor& adaptor) :
1.1397 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1.1398 @@ -1920,8 +2093,7 @@
1.1399 }
1.1400 }
1.1401
1.1402 - typename MapTraits<MapImpl>::ConstReturnValue
1.1403 - operator[](const Arc& a) const {
1.1404 + ConstReturnValue operator[](const Arc& a) const {
1.1405 if (direction(a)) {
1.1406 return _forward[a];
1.1407 } else {
1.1408 @@ -1929,8 +2101,7 @@
1.1409 }
1.1410 }
1.1411
1.1412 - typename MapTraits<MapImpl>::ReturnValue
1.1413 - operator[](const Arc& a) {
1.1414 + ReturnValue operator[](const Arc& a) {
1.1415 if (direction(a)) {
1.1416 return _forward[a];
1.1417 } else {
1.1418 @@ -1980,7 +2151,7 @@
1.1419 typedef _Value Value;
1.1420 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.1421
1.1422 - ArcMap(const Adaptor& adaptor)
1.1423 + explicit ArcMap(const Adaptor& adaptor)
1.1424 : Parent(adaptor) {}
1.1425
1.1426 ArcMap(const Adaptor& adaptor, const Value& value)
1.1427 @@ -2027,6 +2198,9 @@
1.1428 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.1429 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.1430
1.1431 + typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
1.1432 + EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
1.1433 +
1.1434 protected:
1.1435
1.1436 UndirectorBase() : _digraph(0) {}
1.1437 @@ -2041,59 +2215,76 @@
1.1438
1.1439 /// \ingroup graph_adaptors
1.1440 ///
1.1441 - /// \brief Undirect the graph
1.1442 + /// \brief Adaptor class for viewing a digraph as an undirected graph.
1.1443 ///
1.1444 - /// This adaptor makes an undirected graph from a directed
1.1445 - /// graph. All arcs of the underlying digraph will be showed in the
1.1446 - /// adaptor as an edge. The Orienter adaptor is conform to the \ref
1.1447 - /// concepts::Graph "Graph concept".
1.1448 + /// Undirector adaptor can be used for viewing a digraph as an undirected
1.1449 + /// graph. All arcs of the underlying digraph are showed in the
1.1450 + /// adaptor as an edge (and also as a pair of arcs, of course).
1.1451 + /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
1.1452 ///
1.1453 - /// \tparam _Digraph It must be conform to the \ref
1.1454 - /// concepts::Digraph "Digraph concept". The type can be specified
1.1455 - /// to const.
1.1456 - template<typename _Digraph>
1.1457 - class Undirector
1.1458 - : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
1.1459 + /// The adapted digraph can also be modified through this adaptor
1.1460 + /// by adding or removing nodes or edges, unless the \c GR template
1.1461 + /// parameter is set to be \c const.
1.1462 + ///
1.1463 + /// \tparam GR The type of the adapted digraph.
1.1464 + /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.1465 + /// It can also be specified to be \c const.
1.1466 + ///
1.1467 + /// \note The \c Node type of this adaptor and the adapted digraph are
1.1468 + /// convertible to each other, moreover the \c Edge type of the adaptor
1.1469 + /// and the \c Arc type of the adapted digraph are also convertible to
1.1470 + /// each other.
1.1471 + /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
1.1472 + /// of the adapted digraph.)
1.1473 + template<typename GR>
1.1474 +#ifdef DOXYGEN
1.1475 + class Undirector {
1.1476 +#else
1.1477 + class Undirector :
1.1478 + public GraphAdaptorExtender<UndirectorBase<GR> > {
1.1479 +#endif
1.1480 public:
1.1481 - typedef _Digraph Digraph;
1.1482 - typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
1.1483 + /// The type of the adapted digraph.
1.1484 + typedef GR Digraph;
1.1485 + typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent;
1.1486 protected:
1.1487 Undirector() { }
1.1488 public:
1.1489
1.1490 /// \brief Constructor
1.1491 ///
1.1492 - /// Creates a undirected graph from the given digraph
1.1493 - Undirector(_Digraph& digraph) {
1.1494 + /// Creates an undirected graph from the given digraph.
1.1495 + Undirector(Digraph& digraph) {
1.1496 setDigraph(digraph);
1.1497 }
1.1498
1.1499 - /// \brief ArcMap combined from two original ArcMap
1.1500 + /// \brief Arc map combined from two original arc maps
1.1501 ///
1.1502 - /// This class adapts two original digraph ArcMap to
1.1503 - /// get an arc map on the undirected graph.
1.1504 - template <typename _ForwardMap, typename _BackwardMap>
1.1505 + /// This map adaptor class adapts two arc maps of the underlying
1.1506 + /// digraph to get an arc map of the undirected graph.
1.1507 + /// Its value type is inherited from the first arc map type
1.1508 + /// (\c %ForwardMap).
1.1509 + template <typename ForwardMap, typename BackwardMap>
1.1510 class CombinedArcMap {
1.1511 public:
1.1512
1.1513 - typedef _ForwardMap ForwardMap;
1.1514 - typedef _BackwardMap BackwardMap;
1.1515 + /// The key type of the map
1.1516 + typedef typename Parent::Arc Key;
1.1517 + /// The value type of the map
1.1518 + typedef typename ForwardMap::Value Value;
1.1519
1.1520 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1.1521
1.1522 - typedef typename ForwardMap::Value Value;
1.1523 - typedef typename Parent::Arc Key;
1.1524 -
1.1525 - /// \brief Constructor
1.1526 - ///
1.1527 + typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
1.1528 + typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
1.1529 + typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
1.1530 + typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
1.1531 +
1.1532 /// Constructor
1.1533 CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
1.1534 : _forward(&forward), _backward(&backward) {}
1.1535
1.1536 -
1.1537 - /// \brief Sets the value associated with a key.
1.1538 - ///
1.1539 - /// Sets the value associated with a key.
1.1540 + /// Sets the value associated with the given key.
1.1541 void set(const Key& e, const Value& a) {
1.1542 if (Parent::direction(e)) {
1.1543 _forward->set(e, a);
1.1544 @@ -2102,11 +2293,8 @@
1.1545 }
1.1546 }
1.1547
1.1548 - /// \brief Returns the value associated with a key.
1.1549 - ///
1.1550 - /// Returns the value associated with a key.
1.1551 - typename MapTraits<ForwardMap>::ConstReturnValue
1.1552 - operator[](const Key& e) const {
1.1553 + /// Returns the value associated with the given key.
1.1554 + ConstReturnValue operator[](const Key& e) const {
1.1555 if (Parent::direction(e)) {
1.1556 return (*_forward)[e];
1.1557 } else {
1.1558 @@ -2114,11 +2302,8 @@
1.1559 }
1.1560 }
1.1561
1.1562 - /// \brief Returns the value associated with a key.
1.1563 - ///
1.1564 - /// Returns the value associated with a key.
1.1565 - typename MapTraits<ForwardMap>::ReturnValue
1.1566 - operator[](const Key& e) {
1.1567 + /// Returns a reference to the value associated with the given key.
1.1568 + ReturnValue operator[](const Key& e) {
1.1569 if (Parent::direction(e)) {
1.1570 return (*_forward)[e];
1.1571 } else {
1.1572 @@ -2133,9 +2318,9 @@
1.1573
1.1574 };
1.1575
1.1576 - /// \brief Just gives back a combined arc map
1.1577 + /// \brief Returns a combined arc map
1.1578 ///
1.1579 - /// Just gives back a combined arc map
1.1580 + /// This function just returns a combined arc map.
1.1581 template <typename ForwardMap, typename BackwardMap>
1.1582 static CombinedArcMap<ForwardMap, BackwardMap>
1.1583 combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
1.1584 @@ -2165,15 +2350,17 @@
1.1585
1.1586 };
1.1587
1.1588 - /// \brief Just gives back an undirected view of the given digraph
1.1589 + /// \brief Returns a read-only Undirector adaptor
1.1590 ///
1.1591 - /// Just gives back an undirected view of the given digraph
1.1592 - template<typename Digraph>
1.1593 - Undirector<const Digraph>
1.1594 - undirector(const Digraph& digraph) {
1.1595 - return Undirector<const Digraph>(digraph);
1.1596 + /// This function just returns a read-only \ref Undirector adaptor.
1.1597 + /// \ingroup graph_adaptors
1.1598 + /// \relates Undirector
1.1599 + template<typename GR>
1.1600 + Undirector<const GR> undirector(const GR& digraph) {
1.1601 + return Undirector<const GR>(digraph);
1.1602 }
1.1603
1.1604 +
1.1605 template <typename _Graph, typename _DirectionMap>
1.1606 class OrienterBase {
1.1607 public:
1.1608 @@ -2191,12 +2378,12 @@
1.1609 void first(Node& i) const { _graph->first(i); }
1.1610 void first(Arc& i) const { _graph->first(i); }
1.1611 void firstIn(Arc& i, const Node& n) const {
1.1612 - bool d;
1.1613 + bool d = true;
1.1614 _graph->firstInc(i, d, n);
1.1615 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
1.1616 }
1.1617 void firstOut(Arc& i, const Node& n ) const {
1.1618 - bool d;
1.1619 + bool d = true;
1.1620 _graph->firstInc(i, d, n);
1.1621 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
1.1622 }
1.1623 @@ -2224,24 +2411,15 @@
1.1624 typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.1625 int nodeNum() const { return _graph->nodeNum(); }
1.1626
1.1627 - typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.1628 + typedef EdgeNumTagIndicator<Graph> ArcNumTag;
1.1629 int arcNum() const { return _graph->edgeNum(); }
1.1630
1.1631 - typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.1632 + typedef FindEdgeTagIndicator<Graph> FindArcTag;
1.1633 Arc findArc(const Node& u, const Node& v,
1.1634 - const Arc& prev = INVALID) {
1.1635 - Arc arc = prev;
1.1636 - bool d = arc == INVALID ? true : (*_direction)[arc];
1.1637 - if (d) {
1.1638 + const Arc& prev = INVALID) const {
1.1639 + Arc arc = _graph->findEdge(u, v, prev);
1.1640 + while (arc != INVALID && source(arc) != u) {
1.1641 arc = _graph->findEdge(u, v, arc);
1.1642 - while (arc != INVALID && !(*_direction)[arc]) {
1.1643 - _graph->findEdge(u, v, arc);
1.1644 - }
1.1645 - if (arc != INVALID) return arc;
1.1646 - }
1.1647 - _graph->findEdge(v, u, arc);
1.1648 - while (arc != INVALID && (*_direction)[arc]) {
1.1649 - _graph->findEdge(u, v, arc);
1.1650 }
1.1651 return arc;
1.1652 }
1.1653 @@ -2251,8 +2429,8 @@
1.1654 }
1.1655
1.1656 Arc addArc(const Node& u, const Node& v) {
1.1657 - Arc arc = _graph->addArc(u, v);
1.1658 - _direction->set(arc, _graph->source(arc) == u);
1.1659 + Arc arc = _graph->addEdge(u, v);
1.1660 + _direction->set(arc, _graph->u(arc) == u);
1.1661 return arc;
1.1662 }
1.1663
1.1664 @@ -2343,78 +2521,98 @@
1.1665
1.1666 /// \ingroup graph_adaptors
1.1667 ///
1.1668 - /// \brief Orients the edges of the graph to get a digraph
1.1669 + /// \brief Adaptor class for orienting the edges of a graph to get a digraph
1.1670 ///
1.1671 - /// This adaptor orients each edge in the undirected graph. The
1.1672 - /// direction of the arcs stored in an edge node map. The arcs can
1.1673 - /// be easily reverted by the \c reverseArc() member function in the
1.1674 - /// adaptor. The Orienter adaptor is conform to the \ref
1.1675 - /// concepts::Digraph "Digraph concept".
1.1676 + /// Orienter adaptor can be used for orienting the edges of a graph to
1.1677 + /// get a digraph. A \c bool edge map of the underlying graph must be
1.1678 + /// specified, which define the direction of the arcs in the adaptor.
1.1679 + /// The arcs can be easily reversed by the \c reverseArc() member function
1.1680 + /// of the adaptor.
1.1681 + /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
1.1682 ///
1.1683 - /// \tparam _Graph It must be conform to the \ref concepts::Graph
1.1684 - /// "Graph concept". The type can be specified to be const.
1.1685 - /// \tparam _DirectionMap A bool valued edge map of the the adapted
1.1686 - /// graph.
1.1687 + /// The adapted graph can also be modified through this adaptor
1.1688 + /// by adding or removing nodes or arcs, unless the \c GR template
1.1689 + /// parameter is set to be \c const.
1.1690 ///
1.1691 - /// \sa orienter
1.1692 - template<typename _Graph,
1.1693 - typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1.1694 + /// \tparam GR The type of the adapted graph.
1.1695 + /// It must conform to the \ref concepts::Graph "Graph" concept.
1.1696 + /// It can also be specified to be \c const.
1.1697 + /// \tparam DM The type of the direction map.
1.1698 + /// It must be a \c bool (or convertible) edge map of the
1.1699 + /// adapted graph. The default type is
1.1700 + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
1.1701 + ///
1.1702 + /// \note The \c Node type of this adaptor and the adapted graph are
1.1703 + /// convertible to each other, moreover the \c Arc type of the adaptor
1.1704 + /// and the \c Edge type of the adapted graph are also convertible to
1.1705 + /// each other.
1.1706 +#ifdef DOXYGEN
1.1707 + template<typename GR,
1.1708 + typename DM>
1.1709 + class Orienter {
1.1710 +#else
1.1711 + template<typename GR,
1.1712 + typename DM = typename GR::template EdgeMap<bool> >
1.1713 class Orienter :
1.1714 - public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
1.1715 + public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
1.1716 +#endif
1.1717 public:
1.1718 - typedef _Graph Graph;
1.1719 - typedef DigraphAdaptorExtender<
1.1720 - OrienterBase<_Graph, DirectionMap> > Parent;
1.1721 +
1.1722 + /// The type of the adapted graph.
1.1723 + typedef GR Graph;
1.1724 + /// The type of the direction edge map.
1.1725 + typedef DM DirectionMap;
1.1726 +
1.1727 + typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
1.1728 typedef typename Parent::Arc Arc;
1.1729 protected:
1.1730 Orienter() { }
1.1731 public:
1.1732
1.1733 - /// \brief Constructor of the adaptor
1.1734 + /// \brief Constructor
1.1735 ///
1.1736 - /// Constructor of the adaptor
1.1737 + /// Constructor of the adaptor.
1.1738 Orienter(Graph& graph, DirectionMap& direction) {
1.1739 setGraph(graph);
1.1740 setDirectionMap(direction);
1.1741 }
1.1742
1.1743 - /// \brief Reverse arc
1.1744 + /// \brief Reverses the given arc
1.1745 ///
1.1746 - /// It reverse the given arc. It simply negate the direction in the map.
1.1747 + /// This function reverses the given arc.
1.1748 + /// It is done by simply negate the assigned value of \c a
1.1749 + /// in the direction map.
1.1750 void reverseArc(const Arc& a) {
1.1751 Parent::reverseArc(a);
1.1752 }
1.1753 };
1.1754
1.1755 - /// \brief Just gives back a Orienter
1.1756 + /// \brief Returns a read-only Orienter adaptor
1.1757 ///
1.1758 - /// Just gives back a Orienter
1.1759 - template<typename Graph, typename DirectionMap>
1.1760 - Orienter<const Graph, DirectionMap>
1.1761 - orienter(const Graph& graph, DirectionMap& dm) {
1.1762 - return Orienter<const Graph, DirectionMap>(graph, dm);
1.1763 + /// This function just returns a read-only \ref Orienter adaptor.
1.1764 + /// \ingroup graph_adaptors
1.1765 + /// \relates Orienter
1.1766 + template<typename GR, typename DM>
1.1767 + Orienter<const GR, DM>
1.1768 + orienter(const GR& graph, DM& direction_map) {
1.1769 + return Orienter<const GR, DM>(graph, direction_map);
1.1770 }
1.1771
1.1772 - template<typename Graph, typename DirectionMap>
1.1773 - Orienter<const Graph, const DirectionMap>
1.1774 - orienter(const Graph& graph, const DirectionMap& dm) {
1.1775 - return Orienter<const Graph, const DirectionMap>(graph, dm);
1.1776 + template<typename GR, typename DM>
1.1777 + Orienter<const GR, const DM>
1.1778 + orienter(const GR& graph, const DM& direction_map) {
1.1779 + return Orienter<const GR, const DM>(graph, direction_map);
1.1780 }
1.1781
1.1782 namespace _adaptor_bits {
1.1783
1.1784 - template<typename _Digraph,
1.1785 - typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.1786 - typename _FlowMap = _CapacityMap,
1.1787 - typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.1788 + template<typename Digraph,
1.1789 + typename CapacityMap,
1.1790 + typename FlowMap,
1.1791 + typename Tolerance>
1.1792 class ResForwardFilter {
1.1793 public:
1.1794
1.1795 - typedef _Digraph Digraph;
1.1796 - typedef _CapacityMap CapacityMap;
1.1797 - typedef _FlowMap FlowMap;
1.1798 - typedef _Tolerance Tolerance;
1.1799 -
1.1800 typedef typename Digraph::Arc Key;
1.1801 typedef bool Value;
1.1802
1.1803 @@ -2434,18 +2632,13 @@
1.1804 }
1.1805 };
1.1806
1.1807 - template<typename _Digraph,
1.1808 - typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.1809 - typename _FlowMap = _CapacityMap,
1.1810 - typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.1811 + template<typename Digraph,
1.1812 + typename CapacityMap,
1.1813 + typename FlowMap,
1.1814 + typename Tolerance>
1.1815 class ResBackwardFilter {
1.1816 public:
1.1817
1.1818 - typedef _Digraph Digraph;
1.1819 - typedef _CapacityMap CapacityMap;
1.1820 - typedef _FlowMap FlowMap;
1.1821 - typedef _Tolerance Tolerance;
1.1822 -
1.1823 typedef typename Digraph::Arc Key;
1.1824 typedef bool Value;
1.1825
1.1826 @@ -2470,50 +2663,71 @@
1.1827
1.1828 /// \ingroup graph_adaptors
1.1829 ///
1.1830 - /// \brief An adaptor for composing the residual graph for directed
1.1831 + /// \brief Adaptor class for composing the residual digraph for directed
1.1832 /// flow and circulation problems.
1.1833 ///
1.1834 - /// An adaptor for composing the residual graph for directed flow and
1.1835 - /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1.1836 - /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1.1837 - /// be functions on the arc-set.
1.1838 + /// Residual can be used for composing the \e residual digraph for directed
1.1839 + /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1.1840 + /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
1.1841 + /// functions on the arcs.
1.1842 + /// This adaptor implements a digraph structure with node set \f$ V \f$
1.1843 + /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
1.1844 + /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
1.1845 + /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
1.1846 + /// called residual digraph.
1.1847 + /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
1.1848 + /// multiplicities are counted, i.e. the adaptor has exactly
1.1849 + /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
1.1850 + /// arcs).
1.1851 + /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
1.1852 ///
1.1853 - /// Then Residual implements the digraph structure with
1.1854 - /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
1.1855 - /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1.1856 - /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
1.1857 - /// called residual graph. When we take the union
1.1858 - /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
1.1859 - /// i.e. if an arc is in both \f$ A_{forward} \f$ and
1.1860 - /// \f$ A_{backward} \f$, then in the adaptor it appears in both
1.1861 - /// orientation.
1.1862 + /// \tparam GR The type of the adapted digraph.
1.1863 + /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.1864 + /// It is implicitly \c const.
1.1865 + /// \tparam CM The type of the capacity map.
1.1866 + /// It must be an arc map of some numerical type, which defines
1.1867 + /// the capacities in the flow problem. It is implicitly \c const.
1.1868 + /// The default type is
1.1869 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.1870 + /// \tparam FM The type of the flow map.
1.1871 + /// It must be an arc map of some numerical type, which defines
1.1872 + /// the flow values in the flow problem. The default type is \c CM.
1.1873 + /// \tparam TL The tolerance type for handling inexact computation.
1.1874 + /// The default tolerance type depends on the value type of the
1.1875 + /// capacity map.
1.1876 ///
1.1877 - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.1878 - /// "Digraph concept". The type is implicitly const.
1.1879 - /// \tparam _CapacityMap An arc map of some numeric type, it defines
1.1880 - /// the capacities in the flow problem. The map is implicitly const.
1.1881 - /// \tparam _FlowMap An arc map of some numeric type, it defines
1.1882 - /// the capacities in the flow problem.
1.1883 - /// \tparam _Tolerance Handler for inexact computation.
1.1884 - template<typename _Digraph,
1.1885 - typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.1886 - typename _FlowMap = _CapacityMap,
1.1887 - typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.1888 + /// \note This adaptor is implemented using Undirector and FilterArcs
1.1889 + /// adaptors.
1.1890 + ///
1.1891 + /// \note The \c Node type of this adaptor and the adapted digraph are
1.1892 + /// convertible to each other, moreover the \c Arc type of the adaptor
1.1893 + /// is convertible to the \c Arc type of the adapted digraph.
1.1894 +#ifdef DOXYGEN
1.1895 + template<typename GR, typename CM, typename FM, typename TL>
1.1896 + class Residual
1.1897 +#else
1.1898 + template<typename GR,
1.1899 + typename CM = typename GR::template ArcMap<int>,
1.1900 + typename FM = CM,
1.1901 + typename TL = Tolerance<typename CM::Value> >
1.1902 class Residual :
1.1903 public FilterArcs<
1.1904 - Undirector<const _Digraph>,
1.1905 - typename Undirector<const _Digraph>::template CombinedArcMap<
1.1906 - _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
1.1907 - _FlowMap, _Tolerance>,
1.1908 - _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
1.1909 - _FlowMap, _Tolerance> > >
1.1910 + Undirector<const GR>,
1.1911 + typename Undirector<const GR>::template CombinedArcMap<
1.1912 + _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
1.1913 + _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
1.1914 +#endif
1.1915 {
1.1916 public:
1.1917
1.1918 - typedef _Digraph Digraph;
1.1919 - typedef _CapacityMap CapacityMap;
1.1920 - typedef _FlowMap FlowMap;
1.1921 - typedef _Tolerance Tolerance;
1.1922 + /// The type of the underlying digraph.
1.1923 + typedef GR Digraph;
1.1924 + /// The type of the capacity map.
1.1925 + typedef CM CapacityMap;
1.1926 + /// The type of the flow map.
1.1927 + typedef FM FlowMap;
1.1928 + /// The tolerance type.
1.1929 + typedef TL Tolerance;
1.1930
1.1931 typedef typename CapacityMap::Value Value;
1.1932 typedef Residual Adaptor;
1.1933 @@ -2529,7 +2743,7 @@
1.1934 FlowMap, Tolerance> BackwardFilter;
1.1935
1.1936 typedef typename Undirected::
1.1937 - template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1.1938 + template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1.1939
1.1940 typedef FilterArcs<Undirected, ArcFilter> Parent;
1.1941
1.1942 @@ -2543,10 +2757,10 @@
1.1943
1.1944 public:
1.1945
1.1946 - /// \brief Constructor of the residual digraph.
1.1947 + /// \brief Constructor
1.1948 ///
1.1949 - /// Constructor of the residual graph. The parameters are the digraph,
1.1950 - /// the flow map, the capacity map and a tolerance object.
1.1951 + /// Constructor of the residual digraph adaptor. The parameters are the
1.1952 + /// digraph, the capacity map, the flow map, and a tolerance object.
1.1953 Residual(const Digraph& digraph, const CapacityMap& capacity,
1.1954 FlowMap& flow, const Tolerance& tolerance = Tolerance())
1.1955 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1.1956 @@ -2560,9 +2774,9 @@
1.1957
1.1958 typedef typename Parent::Arc Arc;
1.1959
1.1960 - /// \brief Gives back the residual capacity of the arc.
1.1961 + /// \brief Returns the residual capacity of the given arc.
1.1962 ///
1.1963 - /// Gives back the residual capacity of the arc.
1.1964 + /// Returns the residual capacity of the given arc.
1.1965 Value residualCapacity(const Arc& a) const {
1.1966 if (Undirected::direction(a)) {
1.1967 return (*_capacity)[a] - (*_flow)[a];
1.1968 @@ -2571,11 +2785,11 @@
1.1969 }
1.1970 }
1.1971
1.1972 - /// \brief Augment on the given arc in the residual graph.
1.1973 + /// \brief Augments on the given arc in the residual digraph.
1.1974 ///
1.1975 - /// Augment on the given arc in the residual graph. It increase
1.1976 - /// or decrease the flow on the original arc depend on the direction
1.1977 - /// of the residual arc.
1.1978 + /// Augments on the given arc in the residual digraph. It increases
1.1979 + /// or decreases the flow value on the original arc according to the
1.1980 + /// direction of the residual arc.
1.1981 void augment(const Arc& a, const Value& v) const {
1.1982 if (Undirected::direction(a)) {
1.1983 _flow->set(a, (*_flow)[a] + v);
1.1984 @@ -2584,59 +2798,84 @@
1.1985 }
1.1986 }
1.1987
1.1988 - /// \brief Returns the direction of the arc.
1.1989 + /// \brief Returns \c true if the given residual arc is a forward arc.
1.1990 ///
1.1991 - /// Returns true when the arc is same oriented as the original arc.
1.1992 + /// Returns \c true if the given residual arc has the same orientation
1.1993 + /// as the original arc, i.e. it is a so called forward arc.
1.1994 static bool forward(const Arc& a) {
1.1995 return Undirected::direction(a);
1.1996 }
1.1997
1.1998 - /// \brief Returns the direction of the arc.
1.1999 + /// \brief Returns \c true if the given residual arc is a backward arc.
1.2000 ///
1.2001 - /// Returns true when the arc is opposite oriented as the original arc.
1.2002 + /// Returns \c true if the given residual arc has the opposite orientation
1.2003 + /// than the original arc, i.e. it is a so called backward arc.
1.2004 static bool backward(const Arc& a) {
1.2005 return !Undirected::direction(a);
1.2006 }
1.2007
1.2008 - /// \brief Gives back the forward oriented residual arc.
1.2009 + /// \brief Returns the forward oriented residual arc.
1.2010 ///
1.2011 - /// Gives back the forward oriented residual arc.
1.2012 + /// Returns the forward oriented residual arc related to the given
1.2013 + /// arc of the underlying digraph.
1.2014 static Arc forward(const typename Digraph::Arc& a) {
1.2015 return Undirected::direct(a, true);
1.2016 }
1.2017
1.2018 - /// \brief Gives back the backward oriented residual arc.
1.2019 + /// \brief Returns the backward oriented residual arc.
1.2020 ///
1.2021 - /// Gives back the backward oriented residual arc.
1.2022 + /// Returns the backward oriented residual arc related to the given
1.2023 + /// arc of the underlying digraph.
1.2024 static Arc backward(const typename Digraph::Arc& a) {
1.2025 return Undirected::direct(a, false);
1.2026 }
1.2027
1.2028 /// \brief Residual capacity map.
1.2029 ///
1.2030 - /// In generic residual graph the residual capacity can be obtained
1.2031 - /// as a map.
1.2032 + /// This map adaptor class can be used for obtaining the residual
1.2033 + /// capacities as an arc map of the residual digraph.
1.2034 + /// Its value type is inherited from the capacity map.
1.2035 class ResidualCapacity {
1.2036 protected:
1.2037 const Adaptor* _adaptor;
1.2038 public:
1.2039 - /// The Key type
1.2040 + /// The key type of the map
1.2041 typedef Arc Key;
1.2042 - /// The Value type
1.2043 - typedef typename _CapacityMap::Value Value;
1.2044 + /// The value type of the map
1.2045 + typedef typename CapacityMap::Value Value;
1.2046
1.2047 /// Constructor
1.2048 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
1.2049
1.2050 - /// \e
1.2051 + /// Returns the value associated with the given residual arc
1.2052 Value operator[](const Arc& a) const {
1.2053 return _adaptor->residualCapacity(a);
1.2054 }
1.2055
1.2056 };
1.2057
1.2058 + /// \brief Returns a residual capacity map
1.2059 + ///
1.2060 + /// This function just returns a residual capacity map.
1.2061 + ResidualCapacity residualCapacity() const {
1.2062 + return ResidualCapacity(*this);
1.2063 + }
1.2064 +
1.2065 };
1.2066
1.2067 + /// \brief Returns a (read-only) Residual adaptor
1.2068 + ///
1.2069 + /// This function just returns a (read-only) \ref Residual adaptor.
1.2070 + /// \ingroup graph_adaptors
1.2071 + /// \relates Residual
1.2072 + template<typename GR, typename CM, typename FM>
1.2073 + Residual<GR, CM, FM> residual(const GR& digraph,
1.2074 + const CM& capacity_map,
1.2075 + FM& flow_map) {
1.2076 + return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
1.2077 + }
1.2078 +
1.2079 +
1.2080 template <typename _Digraph>
1.2081 class SplitNodesBase {
1.2082 public:
1.2083 @@ -2884,30 +3123,26 @@
1.2084 }
1.2085
1.2086 typedef True NodeNumTag;
1.2087 -
1.2088 int nodeNum() const {
1.2089 return 2 * countNodes(*_digraph);
1.2090 }
1.2091
1.2092 - typedef True EdgeNumTag;
1.2093 + typedef True ArcNumTag;
1.2094 int arcNum() const {
1.2095 return countArcs(*_digraph) + countNodes(*_digraph);
1.2096 }
1.2097
1.2098 - typedef True FindEdgeTag;
1.2099 + typedef True FindArcTag;
1.2100 Arc findArc(const Node& u, const Node& v,
1.2101 const Arc& prev = INVALID) const {
1.2102 - if (inNode(u)) {
1.2103 - if (outNode(v)) {
1.2104 - if (static_cast<const DigraphNode&>(u) ==
1.2105 - static_cast<const DigraphNode&>(v) && prev == INVALID) {
1.2106 - return Arc(u);
1.2107 - }
1.2108 + if (inNode(u) && outNode(v)) {
1.2109 + if (static_cast<const DigraphNode&>(u) ==
1.2110 + static_cast<const DigraphNode&>(v) && prev == INVALID) {
1.2111 + return Arc(u);
1.2112 }
1.2113 - } else {
1.2114 - if (inNode(v)) {
1.2115 - return Arc(::lemon::findArc(*_digraph, u, v, prev));
1.2116 - }
1.2117 + }
1.2118 + else if (outNode(u) && inNode(v)) {
1.2119 + return Arc(::lemon::findArc(*_digraph, u, v, prev));
1.2120 }
1.2121 return INVALID;
1.2122 }
1.2123 @@ -2921,6 +3156,11 @@
1.2124 public:
1.2125 typedef Node Key;
1.2126 typedef _Value Value;
1.2127 + typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
1.2128 + typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
1.2129 + typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
1.2130 + typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
1.2131 + typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
1.2132
1.2133 NodeMapBase(const Adaptor& adaptor)
1.2134 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
1.2135 @@ -2933,14 +3173,12 @@
1.2136 else {_out_map.set(key, val); }
1.2137 }
1.2138
1.2139 - typename MapTraits<NodeImpl>::ReturnValue
1.2140 - operator[](const Node& key) {
1.2141 + ReturnValue operator[](const Node& key) {
1.2142 if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2143 else { return _out_map[key]; }
1.2144 }
1.2145
1.2146 - typename MapTraits<NodeImpl>::ConstReturnValue
1.2147 - operator[](const Node& key) const {
1.2148 + ConstReturnValue operator[](const Node& key) const {
1.2149 if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2150 else { return _out_map[key]; }
1.2151 }
1.2152 @@ -2957,6 +3195,11 @@
1.2153 public:
1.2154 typedef Arc Key;
1.2155 typedef _Value Value;
1.2156 + typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
1.2157 + typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
1.2158 + typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
1.2159 + typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
1.2160 + typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
1.2161
1.2162 ArcMapBase(const Adaptor& adaptor)
1.2163 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
1.2164 @@ -2972,8 +3215,7 @@
1.2165 }
1.2166 }
1.2167
1.2168 - typename MapTraits<ArcImpl>::ReturnValue
1.2169 - operator[](const Arc& key) {
1.2170 + ReturnValue operator[](const Arc& key) {
1.2171 if (Adaptor::origArc(key)) {
1.2172 return _arc_map[key._item.first()];
1.2173 } else {
1.2174 @@ -2981,8 +3223,7 @@
1.2175 }
1.2176 }
1.2177
1.2178 - typename MapTraits<ArcImpl>::ConstReturnValue
1.2179 - operator[](const Arc& key) const {
1.2180 + ConstReturnValue operator[](const Arc& key) const {
1.2181 if (Adaptor::origArc(key)) {
1.2182 return _arc_map[key._item.first()];
1.2183 } else {
1.2184 @@ -3063,31 +3304,41 @@
1.2185
1.2186 /// \ingroup graph_adaptors
1.2187 ///
1.2188 - /// \brief Split the nodes of a directed graph
1.2189 + /// \brief Adaptor class for splitting the nodes of a digraph.
1.2190 ///
1.2191 - /// The SplitNodes adaptor splits each node into an in-node and an
1.2192 - /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
1.2193 - /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
1.2194 - /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
1.2195 - /// original digraph the new target of the arc will be \f$ u_{in} \f$
1.2196 - /// and similarly the source of the original \f$ (u, v) \f$ arc
1.2197 - /// will be \f$ u_{out} \f$. The adaptor will add for each node in
1.2198 - /// the original digraph an additional arc which connects
1.2199 - /// \f$ (u_{in}, u_{out}) \f$.
1.2200 + /// SplitNodes adaptor can be used for splitting each node into an
1.2201 + /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
1.2202 + /// replaces each node \f$ u \f$ in the digraph with two nodes,
1.2203 + /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
1.2204 + /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
1.2205 + /// new target of the arc will be \f$ u_{in} \f$ and similarly the
1.2206 + /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
1.2207 + /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
1.2208 + /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
1.2209 ///
1.2210 - /// The aim of this class is to run algorithm with node costs if the
1.2211 - /// algorithm can use directly just arc costs. In this case we should use
1.2212 - /// a \c SplitNodes and set the node cost of the graph to the
1.2213 - /// bind arc in the adapted graph.
1.2214 + /// The aim of this class is running an algorithm with respect to node
1.2215 + /// costs or capacities if the algorithm considers only arc costs or
1.2216 + /// capacities directly.
1.2217 + /// In this case you can use \c SplitNodes adaptor, and set the node
1.2218 + /// costs/capacities of the original digraph to the \e bind \e arcs
1.2219 + /// in the adaptor.
1.2220 ///
1.2221 - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.2222 - /// "Digraph concept". The type can be specified to be const.
1.2223 - template <typename _Digraph>
1.2224 + /// \tparam GR The type of the adapted digraph.
1.2225 + /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.2226 + /// It is implicitly \c const.
1.2227 + ///
1.2228 + /// \note The \c Node type of this adaptor is converible to the \c Node
1.2229 + /// type of the adapted digraph.
1.2230 + template <typename GR>
1.2231 +#ifdef DOXYGEN
1.2232 + class SplitNodes {
1.2233 +#else
1.2234 class SplitNodes
1.2235 - : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
1.2236 + : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
1.2237 +#endif
1.2238 public:
1.2239 - typedef _Digraph Digraph;
1.2240 - typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
1.2241 + typedef GR Digraph;
1.2242 + typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
1.2243
1.2244 typedef typename Digraph::Node DigraphNode;
1.2245 typedef typename Digraph::Arc DigraphArc;
1.2246 @@ -3095,89 +3346,110 @@
1.2247 typedef typename Parent::Node Node;
1.2248 typedef typename Parent::Arc Arc;
1.2249
1.2250 - /// \brief Constructor of the adaptor.
1.2251 + /// \brief Constructor
1.2252 ///
1.2253 /// Constructor of the adaptor.
1.2254 - SplitNodes(Digraph& g) {
1.2255 + SplitNodes(const Digraph& g) {
1.2256 Parent::setDigraph(g);
1.2257 }
1.2258
1.2259 - /// \brief Returns true when the node is in-node.
1.2260 + /// \brief Returns \c true if the given node is an in-node.
1.2261 ///
1.2262 - /// Returns true when the node is in-node.
1.2263 + /// Returns \c true if the given node is an in-node.
1.2264 static bool inNode(const Node& n) {
1.2265 return Parent::inNode(n);
1.2266 }
1.2267
1.2268 - /// \brief Returns true when the node is out-node.
1.2269 + /// \brief Returns \c true if the given node is an out-node.
1.2270 ///
1.2271 - /// Returns true when the node is out-node.
1.2272 + /// Returns \c true if the given node is an out-node.
1.2273 static bool outNode(const Node& n) {
1.2274 return Parent::outNode(n);
1.2275 }
1.2276
1.2277 - /// \brief Returns true when the arc is arc in the original digraph.
1.2278 + /// \brief Returns \c true if the given arc is an original arc.
1.2279 ///
1.2280 - /// Returns true when the arc is arc in the original digraph.
1.2281 + /// Returns \c true if the given arc is one of the arcs in the
1.2282 + /// original digraph.
1.2283 static bool origArc(const Arc& a) {
1.2284 return Parent::origArc(a);
1.2285 }
1.2286
1.2287 - /// \brief Returns true when the arc binds an in-node and an out-node.
1.2288 + /// \brief Returns \c true if the given arc is a bind arc.
1.2289 ///
1.2290 - /// Returns true when the arc binds an in-node and an out-node.
1.2291 + /// Returns \c true if the given arc is a bind arc, i.e. it connects
1.2292 + /// an in-node and an out-node.
1.2293 static bool bindArc(const Arc& a) {
1.2294 return Parent::bindArc(a);
1.2295 }
1.2296
1.2297 - /// \brief Gives back the in-node created from the \c node.
1.2298 + /// \brief Returns the in-node created from the given original node.
1.2299 ///
1.2300 - /// Gives back the in-node created from the \c node.
1.2301 + /// Returns the in-node created from the given original node.
1.2302 static Node inNode(const DigraphNode& n) {
1.2303 return Parent::inNode(n);
1.2304 }
1.2305
1.2306 - /// \brief Gives back the out-node created from the \c node.
1.2307 + /// \brief Returns the out-node created from the given original node.
1.2308 ///
1.2309 - /// Gives back the out-node created from the \c node.
1.2310 + /// Returns the out-node created from the given original node.
1.2311 static Node outNode(const DigraphNode& n) {
1.2312 return Parent::outNode(n);
1.2313 }
1.2314
1.2315 - /// \brief Gives back the arc binds the two part of the node.
1.2316 + /// \brief Returns the bind arc that corresponds to the given
1.2317 + /// original node.
1.2318 ///
1.2319 - /// Gives back the arc binds the two part of the node.
1.2320 + /// Returns the bind arc in the adaptor that corresponds to the given
1.2321 + /// original node, i.e. the arc connecting the in-node and out-node
1.2322 + /// of \c n.
1.2323 static Arc arc(const DigraphNode& n) {
1.2324 return Parent::arc(n);
1.2325 }
1.2326
1.2327 - /// \brief Gives back the arc of the original arc.
1.2328 + /// \brief Returns the arc that corresponds to the given original arc.
1.2329 ///
1.2330 - /// Gives back the arc of the original arc.
1.2331 + /// Returns the arc in the adaptor that corresponds to the given
1.2332 + /// original arc.
1.2333 static Arc arc(const DigraphArc& a) {
1.2334 return Parent::arc(a);
1.2335 }
1.2336
1.2337 - /// \brief NodeMap combined from two original NodeMap
1.2338 + /// \brief Node map combined from two original node maps
1.2339 ///
1.2340 - /// This class adapt two of the original digraph NodeMap to
1.2341 - /// get a node map on the adapted digraph.
1.2342 + /// This map adaptor class adapts two node maps of the original digraph
1.2343 + /// to get a node map of the split digraph.
1.2344 + /// Its value type is inherited from the first node map type
1.2345 + /// (\c InNodeMap).
1.2346 template <typename InNodeMap, typename OutNodeMap>
1.2347 class CombinedNodeMap {
1.2348 public:
1.2349
1.2350 + /// The key type of the map
1.2351 typedef Node Key;
1.2352 + /// The value type of the map
1.2353 typedef typename InNodeMap::Value Value;
1.2354
1.2355 - /// \brief Constructor
1.2356 - ///
1.2357 - /// Constructor.
1.2358 + typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
1.2359 + typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
1.2360 + typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
1.2361 + typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
1.2362 + typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
1.2363 +
1.2364 + /// Constructor
1.2365 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
1.2366 : _in_map(in_map), _out_map(out_map) {}
1.2367
1.2368 - /// \brief The subscript operator.
1.2369 - ///
1.2370 - /// The subscript operator.
1.2371 + /// Returns the value associated with the given key.
1.2372 + Value operator[](const Key& key) const {
1.2373 + if (Parent::inNode(key)) {
1.2374 + return _in_map[key];
1.2375 + } else {
1.2376 + return _out_map[key];
1.2377 + }
1.2378 + }
1.2379 +
1.2380 + /// Returns a reference to the value associated with the given key.
1.2381 Value& operator[](const Key& key) {
1.2382 if (Parent::inNode(key)) {
1.2383 return _in_map[key];
1.2384 @@ -3186,20 +3458,7 @@
1.2385 }
1.2386 }
1.2387
1.2388 - /// \brief The const subscript operator.
1.2389 - ///
1.2390 - /// The const subscript operator.
1.2391 - Value operator[](const Key& key) const {
1.2392 - if (Parent::inNode(key)) {
1.2393 - return _in_map[key];
1.2394 - } else {
1.2395 - return _out_map[key];
1.2396 - }
1.2397 - }
1.2398 -
1.2399 - /// \brief The setter function of the map.
1.2400 - ///
1.2401 - /// The setter function of the map.
1.2402 + /// Sets the value associated with the given key.
1.2403 void set(const Key& key, const Value& value) {
1.2404 if (Parent::inNode(key)) {
1.2405 _in_map.set(key, value);
1.2406 @@ -3216,9 +3475,9 @@
1.2407 };
1.2408
1.2409
1.2410 - /// \brief Just gives back a combined node map
1.2411 + /// \brief Returns a combined node map
1.2412 ///
1.2413 - /// Just gives back a combined node map
1.2414 + /// This function just returns a combined node map.
1.2415 template <typename InNodeMap, typename OutNodeMap>
1.2416 static CombinedNodeMap<InNodeMap, OutNodeMap>
1.2417 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
1.2418 @@ -3244,26 +3503,51 @@
1.2419 const OutNodeMap>(in_map, out_map);
1.2420 }
1.2421
1.2422 - /// \brief ArcMap combined from an original ArcMap and a NodeMap
1.2423 + /// \brief Arc map combined from an arc map and a node map of the
1.2424 + /// original digraph.
1.2425 ///
1.2426 - /// This class adapt an original ArcMap and a NodeMap to get an
1.2427 - /// arc map on the adapted digraph
1.2428 - template <typename DigraphArcMap, typename DigraphNodeMap>
1.2429 + /// This map adaptor class adapts an arc map and a node map of the
1.2430 + /// original digraph to get an arc map of the split digraph.
1.2431 + /// Its value type is inherited from the original arc map type
1.2432 + /// (\c ArcMap).
1.2433 + template <typename ArcMap, typename NodeMap>
1.2434 class CombinedArcMap {
1.2435 public:
1.2436
1.2437 + /// The key type of the map
1.2438 typedef Arc Key;
1.2439 - typedef typename DigraphArcMap::Value Value;
1.2440 -
1.2441 - /// \brief Constructor
1.2442 - ///
1.2443 - /// Constructor.
1.2444 - CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
1.2445 + /// The value type of the map
1.2446 + typedef typename ArcMap::Value Value;
1.2447 +
1.2448 + typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
1.2449 + typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
1.2450 + typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
1.2451 + typedef typename MapTraits<ArcMap>::ReturnValue Reference;
1.2452 + typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
1.2453 +
1.2454 + /// Constructor
1.2455 + CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
1.2456 : _arc_map(arc_map), _node_map(node_map) {}
1.2457
1.2458 - /// \brief The subscript operator.
1.2459 - ///
1.2460 - /// The subscript operator.
1.2461 + /// Returns the value associated with the given key.
1.2462 + Value operator[](const Key& arc) const {
1.2463 + if (Parent::origArc(arc)) {
1.2464 + return _arc_map[arc];
1.2465 + } else {
1.2466 + return _node_map[arc];
1.2467 + }
1.2468 + }
1.2469 +
1.2470 + /// Returns a reference to the value associated with the given key.
1.2471 + Value& operator[](const Key& arc) {
1.2472 + if (Parent::origArc(arc)) {
1.2473 + return _arc_map[arc];
1.2474 + } else {
1.2475 + return _node_map[arc];
1.2476 + }
1.2477 + }
1.2478 +
1.2479 + /// Sets the value associated with the given key.
1.2480 void set(const Arc& arc, const Value& val) {
1.2481 if (Parent::origArc(arc)) {
1.2482 _arc_map.set(arc, val);
1.2483 @@ -3272,76 +3556,51 @@
1.2484 }
1.2485 }
1.2486
1.2487 - /// \brief The const subscript operator.
1.2488 - ///
1.2489 - /// The const subscript operator.
1.2490 - Value operator[](const Key& arc) const {
1.2491 - if (Parent::origArc(arc)) {
1.2492 - return _arc_map[arc];
1.2493 - } else {
1.2494 - return _node_map[arc];
1.2495 - }
1.2496 - }
1.2497 -
1.2498 - /// \brief The const subscript operator.
1.2499 - ///
1.2500 - /// The const subscript operator.
1.2501 - Value& operator[](const Key& arc) {
1.2502 - if (Parent::origArc(arc)) {
1.2503 - return _arc_map[arc];
1.2504 - } else {
1.2505 - return _node_map[arc];
1.2506 - }
1.2507 - }
1.2508 -
1.2509 private:
1.2510 - DigraphArcMap& _arc_map;
1.2511 - DigraphNodeMap& _node_map;
1.2512 + ArcMap& _arc_map;
1.2513 + NodeMap& _node_map;
1.2514 };
1.2515
1.2516 - /// \brief Just gives back a combined arc map
1.2517 + /// \brief Returns a combined arc map
1.2518 ///
1.2519 - /// Just gives back a combined arc map
1.2520 - template <typename DigraphArcMap, typename DigraphNodeMap>
1.2521 - static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
1.2522 - combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
1.2523 - return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
1.2524 + /// This function just returns a combined arc map.
1.2525 + template <typename ArcMap, typename NodeMap>
1.2526 + static CombinedArcMap<ArcMap, NodeMap>
1.2527 + combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
1.2528 + return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
1.2529 }
1.2530
1.2531 - template <typename DigraphArcMap, typename DigraphNodeMap>
1.2532 - static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
1.2533 - combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
1.2534 - return CombinedArcMap<const DigraphArcMap,
1.2535 - DigraphNodeMap>(arc_map, node_map);
1.2536 + template <typename ArcMap, typename NodeMap>
1.2537 + static CombinedArcMap<const ArcMap, NodeMap>
1.2538 + combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
1.2539 + return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
1.2540 }
1.2541
1.2542 - template <typename DigraphArcMap, typename DigraphNodeMap>
1.2543 - static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
1.2544 - combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
1.2545 - return CombinedArcMap<DigraphArcMap,
1.2546 - const DigraphNodeMap>(arc_map, node_map);
1.2547 + template <typename ArcMap, typename NodeMap>
1.2548 + static CombinedArcMap<ArcMap, const NodeMap>
1.2549 + combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
1.2550 + return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
1.2551 }
1.2552
1.2553 - template <typename DigraphArcMap, typename DigraphNodeMap>
1.2554 - static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
1.2555 - combinedArcMap(const DigraphArcMap& arc_map,
1.2556 - const DigraphNodeMap& node_map) {
1.2557 - return CombinedArcMap<const DigraphArcMap,
1.2558 - const DigraphNodeMap>(arc_map, node_map);
1.2559 + template <typename ArcMap, typename NodeMap>
1.2560 + static CombinedArcMap<const ArcMap, const NodeMap>
1.2561 + combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
1.2562 + return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
1.2563 }
1.2564
1.2565 };
1.2566
1.2567 - /// \brief Just gives back a node splitter
1.2568 + /// \brief Returns a (read-only) SplitNodes adaptor
1.2569 ///
1.2570 - /// Just gives back a node splitter
1.2571 - template<typename Digraph>
1.2572 - SplitNodes<Digraph>
1.2573 - splitNodes(const Digraph& digraph) {
1.2574 - return SplitNodes<Digraph>(digraph);
1.2575 + /// This function just returns a (read-only) \ref SplitNodes adaptor.
1.2576 + /// \ingroup graph_adaptors
1.2577 + /// \relates SplitNodes
1.2578 + template<typename GR>
1.2579 + SplitNodes<GR>
1.2580 + splitNodes(const GR& digraph) {
1.2581 + return SplitNodes<GR>(digraph);
1.2582 }
1.2583
1.2584 -
1.2585 } //namespace lemon
1.2586
1.2587 #endif //LEMON_ADAPTORS_H