1.1 --- a/lemon/digraph_adaptor.h Sun Nov 30 18:57:18 2008 +0100
1.2 +++ b/lemon/digraph_adaptor.h Sun Nov 30 19:00:30 2008 +0100
1.3 @@ -23,7 +23,7 @@
1.4 ///\file
1.5 ///\brief Several digraph adaptors.
1.6 ///
1.7 -///This file contains several useful digraph adaptor functions.
1.8 +///This file contains several useful digraph adaptor classes.
1.9
1.10 #include <lemon/core.h>
1.11 #include <lemon/maps.h>
1.12 @@ -38,17 +38,6 @@
1.13
1.14 namespace lemon {
1.15
1.16 - ///\brief Base type for the Digraph Adaptors
1.17 - ///
1.18 - ///Base type for the Digraph Adaptors
1.19 - ///
1.20 - ///This is the base type for most of LEMON digraph adaptors. This
1.21 - ///class implements a trivial digraph adaptor i.e. it only wraps the
1.22 - ///functions and types of the digraph. The purpose of this class is
1.23 - ///to make easier implementing digraph adaptors. E.g. if an adaptor
1.24 - ///is considered which differs from the wrapped digraph only in some
1.25 - ///of its functions or types, then it can be derived from
1.26 - ///DigraphAdaptor, and only the differences should be implemented.
1.27 template<typename _Digraph>
1.28 class DigraphAdaptorBase {
1.29 public:
1.30 @@ -166,35 +155,6 @@
1.31
1.32 };
1.33
1.34 - ///\ingroup graph_adaptors
1.35 - ///
1.36 - ///\brief Trivial Digraph Adaptor
1.37 - ///
1.38 - /// This class is an adaptor which does not change the adapted
1.39 - /// digraph. It can be used only to test the digraph adaptors.
1.40 - template <typename _Digraph>
1.41 - class DigraphAdaptor :
1.42 - public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
1.43 - public:
1.44 - typedef _Digraph Digraph;
1.45 - typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
1.46 - protected:
1.47 - DigraphAdaptor() : Parent() { }
1.48 -
1.49 - public:
1.50 - explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
1.51 - };
1.52 -
1.53 - /// \brief Just gives back a digraph adaptor
1.54 - ///
1.55 - /// Just gives back a digraph adaptor which
1.56 - /// should be provide original digraph
1.57 - template<typename Digraph>
1.58 - DigraphAdaptor<const Digraph>
1.59 - digraphAdaptor(const Digraph& digraph) {
1.60 - return DigraphAdaptor<const Digraph>(digraph);
1.61 - }
1.62 -
1.63
1.64 template <typename _Digraph>
1.65 class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
1.66 @@ -231,27 +191,25 @@
1.67 ///
1.68 /// If \c g is defined as
1.69 ///\code
1.70 - /// ListDigraph g;
1.71 + /// ListDigraph dg;
1.72 ///\endcode
1.73 /// then
1.74 ///\code
1.75 - /// RevDigraphAdaptor<ListDigraph> ga(g);
1.76 + /// RevDigraphAdaptor<ListDigraph> dga(dg);
1.77 ///\endcode
1.78 - /// implements the digraph obtained from \c g by
1.79 + /// implements the digraph obtained from \c dg by
1.80 /// reversing the orientation of its arcs.
1.81 ///
1.82 - /// A good example of using RevDigraphAdaptor is to decide that the
1.83 - /// directed graph is wheter strongly connected or not. If from one
1.84 - /// node each node is reachable and from each node is reachable this
1.85 - /// node then and just then the digraph is strongly
1.86 - /// connected. Instead of this condition we use a little bit
1.87 - /// different. From one node each node ahould be reachable in the
1.88 - /// digraph and in the reversed digraph. Now this condition can be
1.89 - /// checked with the Dfs algorithm class and the RevDigraphAdaptor
1.90 - /// algorithm class.
1.91 + /// A good example of using RevDigraphAdaptor is to decide whether
1.92 + /// the directed graph is strongly connected or not. The digraph is
1.93 + /// strongly connected iff each node is reachable from one node and
1.94 + /// this node is reachable from the others. Instead of this
1.95 + /// condition we use a slightly different, from one node each node
1.96 + /// is reachable both in the digraph and the reversed digraph. Now
1.97 + /// this condition can be checked with the Dfs algorithm and the
1.98 + /// RevDigraphAdaptor class.
1.99 ///
1.100 - /// And look at the code:
1.101 - ///
1.102 + /// The implementation:
1.103 ///\code
1.104 /// bool stronglyConnected(const Digraph& digraph) {
1.105 /// if (NodeIt(digraph) == INVALID) return true;
1.106 @@ -284,6 +242,10 @@
1.107 protected:
1.108 RevDigraphAdaptor() { }
1.109 public:
1.110 +
1.111 + /// \brief Constructor
1.112 + ///
1.113 + /// Creates a reverse graph adaptor for the given digraph
1.114 explicit RevDigraphAdaptor(Digraph& digraph) {
1.115 Parent::setDigraph(digraph);
1.116 }
1.117 @@ -374,44 +336,13 @@
1.118 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
1.119 }
1.120
1.121 - ///\e
1.122 -
1.123 - /// This function hides \c n in the digraph, i.e. the iteration
1.124 - /// jumps over it. This is done by simply setting the value of \c n
1.125 - /// to be false in the corresponding node-map.
1.126 void hide(const Node& n) const { _node_filter->set(n, false); }
1.127 -
1.128 - ///\e
1.129 -
1.130 - /// This function hides \c a in the digraph, i.e. the iteration
1.131 - /// jumps over it. This is done by simply setting the value of \c a
1.132 - /// to be false in the corresponding arc-map.
1.133 void hide(const Arc& a) const { _arc_filter->set(a, false); }
1.134
1.135 - ///\e
1.136 -
1.137 - /// The value of \c n is set to be true in the node-map which stores
1.138 - /// hide information. If \c n was hidden previuosly, then it is shown
1.139 - /// again
1.140 - void unHide(const Node& n) const { _node_filter->set(n, true); }
1.141 -
1.142 - ///\e
1.143 -
1.144 - /// The value of \c a is set to be true in the arc-map which stores
1.145 - /// hide information. If \c a was hidden previuosly, then it is shown
1.146 - /// again
1.147 + void unHide(const Node& n) const { _node_filter->set(n, true); }
1.148 void unHide(const Arc& a) const { _arc_filter->set(a, true); }
1.149
1.150 - /// Returns true if \c n is hidden.
1.151 -
1.152 - ///\e
1.153 - ///
1.154 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.155 -
1.156 - /// Returns true if \c a is hidden.
1.157 -
1.158 - ///\e
1.159 - ///
1.160 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
1.161
1.162 typedef False NodeNumTag;
1.163 @@ -548,44 +479,13 @@
1.164 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
1.165 }
1.166
1.167 - ///\e
1.168 -
1.169 - /// This function hides \c n in the digraph, i.e. the iteration
1.170 - /// jumps over it. This is done by simply setting the value of \c n
1.171 - /// to be false in the corresponding node-map.
1.172 void hide(const Node& n) const { _node_filter->set(n, false); }
1.173 -
1.174 - ///\e
1.175 -
1.176 - /// This function hides \c e in the digraph, i.e. the iteration
1.177 - /// jumps over it. This is done by simply setting the value of \c e
1.178 - /// to be false in the corresponding arc-map.
1.179 void hide(const Arc& e) const { _arc_filter->set(e, false); }
1.180
1.181 - ///\e
1.182 -
1.183 - /// The value of \c n is set to be true in the node-map which stores
1.184 - /// hide information. If \c n was hidden previuosly, then it is shown
1.185 - /// again
1.186 - void unHide(const Node& n) const { _node_filter->set(n, true); }
1.187 -
1.188 - ///\e
1.189 -
1.190 - /// The value of \c e is set to be true in the arc-map which stores
1.191 - /// hide information. If \c e was hidden previuosly, then it is shown
1.192 - /// again
1.193 + void unHide(const Node& n) const { _node_filter->set(n, true); }
1.194 void unHide(const Arc& e) const { _arc_filter->set(e, true); }
1.195
1.196 - /// Returns true if \c n is hidden.
1.197 -
1.198 - ///\e
1.199 - ///
1.200 bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.201 -
1.202 - /// Returns true if \c n is hidden.
1.203 -
1.204 - ///\e
1.205 - ///
1.206 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
1.207
1.208 typedef False NodeNumTag;
1.209 @@ -661,26 +561,14 @@
1.210 /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
1.211 ///
1.212 /// SubDigraphAdaptor shows the digraph with filtered node-set and
1.213 - /// arc-set. If the \c checked parameter is true then it filters the arcset
1.214 - /// to do not get invalid arcs without source or target.
1.215 - /// Let \f$ G=(V, A) \f$ be a directed digraph
1.216 - /// and suppose that the digraph instance \c g of type ListDigraph
1.217 - /// implements \f$ G \f$.
1.218 - /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
1.219 - /// on the node-set and arc-set.
1.220 - /// SubDigraphAdaptor<...>::NodeIt iterates
1.221 - /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
1.222 - /// SubDigraphAdaptor<...>::ArcIt iterates
1.223 - /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
1.224 - /// SubDigraphAdaptor<...>::OutArcIt and
1.225 - /// SubDigraphAdaptor<...>::InArcIt iterates
1.226 - /// only on arcs leaving and entering a specific node which have true value.
1.227 + /// arc-set. If the \c checked parameter is true then it filters the arc-set
1.228 + /// respect to the source and target.
1.229 ///
1.230 - /// If the \c checked template parameter is false then we have to
1.231 - /// note that the node-iterator cares only the filter on the
1.232 - /// node-set, and the arc-iterator cares only the filter on the
1.233 - /// arc-set. This way the arc-map should filter all arcs which's
1.234 - /// source or target is filtered by the node-filter.
1.235 + /// If the \c checked template parameter is false then the
1.236 + /// node-iterator cares only the filter on the node-set, and the
1.237 + /// arc-iterator cares only the filter on the arc-set. Therefore
1.238 + /// the arc-map have to filter all arcs which's source or target is
1.239 + /// filtered by the node-filter.
1.240 ///\code
1.241 /// typedef ListDigraph Digraph;
1.242 /// DIGRAPH_TYPEDEFS(Digraph);
1.243 @@ -693,21 +581,19 @@
1.244 /// nm.set(u, false);
1.245 /// BoolArcMap am(g, true);
1.246 /// am.set(a, false);
1.247 - /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;
1.248 - /// SubGA ga(g, nm, am);
1.249 - /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
1.250 + /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA;
1.251 + /// SubDGA ga(g, nm, am);
1.252 + /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n)
1.253 /// std::cout << g.id(n) << std::endl;
1.254 - /// std::cout << ":-)" << std::endl;
1.255 - /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
1.256 + /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a)
1.257 /// std::cout << g.id(a) << std::endl;
1.258 ///\endcode
1.259 /// The output of the above code is the following.
1.260 ///\code
1.261 /// 1
1.262 - /// :-)
1.263 /// 1
1.264 ///\endcode
1.265 - /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
1.266 + /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to
1.267 /// \c Digraph::Node that is why \c g.id(n) can be applied.
1.268 ///
1.269 /// For other examples see also the documentation of
1.270 @@ -728,10 +614,17 @@
1.271 SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
1.272 Parent;
1.273
1.274 + typedef typename Parent::Node Node;
1.275 + typedef typename Parent::Arc Arc;
1.276 +
1.277 protected:
1.278 SubDigraphAdaptor() { }
1.279 public:
1.280
1.281 + /// \brief Constructor
1.282 + ///
1.283 + /// Creates a sub-digraph-adaptor for the given digraph with
1.284 + /// given node and arc map filters.
1.285 SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
1.286 ArcFilterMap& arc_filter) {
1.287 setDigraph(digraph);
1.288 @@ -739,11 +632,51 @@
1.289 setArcFilterMap(arc_filter);
1.290 }
1.291
1.292 + /// \brief Hides the node of the graph
1.293 + ///
1.294 + /// This function hides \c n in the digraph, i.e. the iteration
1.295 + /// jumps over it. This is done by simply setting the value of \c n
1.296 + /// to be false in the corresponding node-map.
1.297 + void hide(const Node& n) const { Parent::hide(n); }
1.298 +
1.299 + /// \brief Hides the arc of the graph
1.300 + ///
1.301 + /// This function hides \c a in the digraph, i.e. the iteration
1.302 + /// jumps over it. This is done by simply setting the value of \c a
1.303 + /// to be false in the corresponding arc-map.
1.304 + void hide(const Arc& a) const { Parent::hide(a); }
1.305 +
1.306 + /// \brief Unhides the node of the graph
1.307 + ///
1.308 + /// The value of \c n is set to be true in the node-map which stores
1.309 + /// hide information. If \c n was hidden previuosly, then it is shown
1.310 + /// again
1.311 + void unHide(const Node& n) const { Parent::unHide(n); }
1.312 +
1.313 + /// \brief Unhides the arc of the graph
1.314 + ///
1.315 + /// The value of \c a is set to be true in the arc-map which stores
1.316 + /// hide information. If \c a was hidden previuosly, then it is shown
1.317 + /// again
1.318 + void unHide(const Arc& a) const { Parent::unHide(a); }
1.319 +
1.320 + /// \brief Returns true if \c n is hidden.
1.321 + ///
1.322 + /// Returns true if \c n is hidden.
1.323 + ///
1.324 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.325 +
1.326 + /// \brief Returns true if \c a is hidden.
1.327 + ///
1.328 + /// Returns true if \c a is hidden.
1.329 + ///
1.330 + bool hidden(const Arc& a) const { return Parent::hidden(a); }
1.331 +
1.332 };
1.333
1.334 - /// \brief Just gives back a sub digraph adaptor
1.335 + /// \brief Just gives back a sub-digraph-adaptor
1.336 ///
1.337 - /// Just gives back a sub digraph adaptor
1.338 + /// Just gives back a sub-digraph-adaptor
1.339 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.340 SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
1.341 subDigraphAdaptor(const Digraph& digraph,
1.342 @@ -774,6 +707,7 @@
1.343 NodeFilterMap& nfm, ArcFilterMap& afm) {
1.344 return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
1.345 const ArcFilterMap>(digraph, nfm, afm);
1.346 +
1.347 }
1.348
1.349
1.350 @@ -802,6 +736,8 @@
1.351 ConstMap<typename Digraph::Arc, bool>, checked>
1.352 Parent;
1.353
1.354 + typedef typename Parent::Node Node;
1.355 +
1.356 protected:
1.357 ConstMap<typename Digraph::Arc, bool> const_true_map;
1.358
1.359 @@ -811,6 +747,10 @@
1.360
1.361 public:
1.362
1.363 + /// \brief Constructor
1.364 + ///
1.365 + /// Creates a node-sub-digraph-adaptor for the given digraph with
1.366 + /// given node map filter.
1.367 NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
1.368 Parent(), const_true_map(true) {
1.369 Parent::setDigraph(_digraph);
1.370 @@ -818,12 +758,32 @@
1.371 Parent::setArcFilterMap(const_true_map);
1.372 }
1.373
1.374 + /// \brief Hides the node of the graph
1.375 + ///
1.376 + /// This function hides \c n in the digraph, i.e. the iteration
1.377 + /// jumps over it. This is done by simply setting the value of \c n
1.378 + /// to be false in the corresponding node-map.
1.379 + void hide(const Node& n) const { Parent::hide(n); }
1.380 +
1.381 + /// \brief Unhides the node of the graph
1.382 + ///
1.383 + /// The value of \c n is set to be true in the node-map which stores
1.384 + /// hide information. If \c n was hidden previuosly, then it is shown
1.385 + /// again
1.386 + void unHide(const Node& n) const { Parent::unHide(n); }
1.387 +
1.388 + /// \brief Returns true if \c n is hidden.
1.389 + ///
1.390 + /// Returns true if \c n is hidden.
1.391 + ///
1.392 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.393 +
1.394 };
1.395
1.396
1.397 - /// \brief Just gives back a \c NodeSubDigraphAdaptor
1.398 + /// \brief Just gives back a node-sub-digraph adaptor
1.399 ///
1.400 - /// Just gives back a \c NodeSubDigraphAdaptor
1.401 + /// Just gives back a node-sub-digraph adaptor
1.402 template<typename Digraph, typename NodeFilterMap>
1.403 NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
1.404 nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
1.405 @@ -846,9 +806,10 @@
1.406 ///can be filtered. The usefulness of this adaptor is demonstrated
1.407 ///in the problem of searching a maximum number of arc-disjoint
1.408 ///shortest paths between two nodes \c s and \c t. Shortest here
1.409 - ///means being shortest w.r.t. non-negative arc-lengths. Note that
1.410 - ///the comprehension of the presented solution need's some
1.411 - ///elementary knowlarc from combinatorial optimization.
1.412 + ///means being shortest with respect to non-negative
1.413 + ///arc-lengths. Note that the comprehension of the presented
1.414 + ///solution need's some elementary knowledge from combinatorial
1.415 + ///optimization.
1.416 ///
1.417 ///If a single shortest path is to be searched between \c s and \c
1.418 ///t, then this can be done easily by applying the Dijkstra
1.419 @@ -868,7 +829,7 @@
1.420 ///generated by the demo program \ref dim_to_dot.cc.
1.421 ///
1.422 ///\dot
1.423 - ///didigraph lemon_dot_example {
1.424 + ///digraph lemon_dot_example {
1.425 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.426 ///n0 [ label="0 (s)" ];
1.427 ///n1 [ label="1" ];
1.428 @@ -974,6 +935,9 @@
1.429
1.430 typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
1.431 ArcFilterMap, false> Parent;
1.432 +
1.433 + typedef typename Parent::Arc Arc;
1.434 +
1.435 protected:
1.436 ConstMap<typename Digraph::Node, bool> const_true_map;
1.437
1.438 @@ -983,6 +947,10 @@
1.439
1.440 public:
1.441
1.442 + /// \brief Constructor
1.443 + ///
1.444 + /// Creates a arc-sub-digraph-adaptor for the given digraph with
1.445 + /// given arc map filter.
1.446 ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
1.447 : Parent(), const_true_map(true) {
1.448 Parent::setDigraph(digraph);
1.449 @@ -990,11 +958,31 @@
1.450 Parent::setArcFilterMap(arc_filter);
1.451 }
1.452
1.453 + /// \brief Hides the arc of the graph
1.454 + ///
1.455 + /// This function hides \c a in the digraph, i.e. the iteration
1.456 + /// jumps over it. This is done by simply setting the value of \c a
1.457 + /// to be false in the corresponding arc-map.
1.458 + void hide(const Arc& a) const { Parent::hide(a); }
1.459 +
1.460 + /// \brief Unhides the arc of the graph
1.461 + ///
1.462 + /// The value of \c a is set to be true in the arc-map which stores
1.463 + /// hide information. If \c a was hidden previuosly, then it is shown
1.464 + /// again
1.465 + void unHide(const Arc& a) const { Parent::unHide(a); }
1.466 +
1.467 + /// \brief Returns true if \c a is hidden.
1.468 + ///
1.469 + /// Returns true if \c a is hidden.
1.470 + ///
1.471 + bool hidden(const Arc& a) const { return Parent::hidden(a); }
1.472 +
1.473 };
1.474
1.475 - /// \brief Just gives back an arc sub digraph adaptor
1.476 + /// \brief Just gives back an arc-sub-digraph adaptor
1.477 ///
1.478 - /// Just gives back an arc sub digraph adaptor
1.479 + /// Just gives back an arc-sub-digraph adaptor
1.480 template<typename Digraph, typename ArcFilterMap>
1.481 ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
1.482 arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
1.483 @@ -1393,12 +1381,12 @@
1.484
1.485 ///\ingroup graph_adaptors
1.486 ///
1.487 - /// \brief An graph is made from a directed digraph by an adaptor
1.488 + /// \brief A graph is made from a directed digraph by an adaptor
1.489 ///
1.490 /// This adaptor makes an undirected graph from a directed
1.491 - /// digraph. All arc of the underlying will be showed in the adaptor
1.492 - /// as an edge. Let's see an informal example about using
1.493 - /// this adaptor:
1.494 + /// graph. All arc of the underlying digraph will be showed in the
1.495 + /// adaptor as an edge. Let's see an informal example about using
1.496 + /// this adaptor.
1.497 ///
1.498 /// There is a network of the streets of a town. Of course there are
1.499 /// some one-way street in the town hence the network is a directed
1.500 @@ -1802,12 +1790,6 @@
1.501
1.502 };
1.503
1.504 - /// \brief Base class for split digraph adaptor
1.505 - ///
1.506 - /// Base class of split digraph adaptor. In most case you do not need to
1.507 - /// use it directly but the documented member functions of this class can
1.508 - /// be used with the SplitDigraphAdaptor class.
1.509 - /// \sa SplitDigraphAdaptor
1.510 template <typename _Digraph>
1.511 class SplitDigraphAdaptorBase {
1.512 public:
1.513 @@ -2022,58 +2004,34 @@
1.514 (_digraph->maxArcId() << 1) | 1);
1.515 }
1.516
1.517 - /// \brief Returns true when the node is in-node.
1.518 - ///
1.519 - /// Returns true when the node is in-node.
1.520 static bool inNode(const Node& n) {
1.521 return n._in;
1.522 }
1.523
1.524 - /// \brief Returns true when the node is out-node.
1.525 - ///
1.526 - /// Returns true when the node is out-node.
1.527 static bool outNode(const Node& n) {
1.528 return !n._in;
1.529 }
1.530
1.531 - /// \brief Returns true when the arc is arc in the original digraph.
1.532 - ///
1.533 - /// Returns true when the arc is arc in the original digraph.
1.534 static bool origArc(const Arc& e) {
1.535 return e._item.firstState();
1.536 }
1.537
1.538 - /// \brief Returns true when the arc binds an in-node and an out-node.
1.539 - ///
1.540 - /// Returns true when the arc binds an in-node and an out-node.
1.541 static bool bindArc(const Arc& e) {
1.542 return e._item.secondState();
1.543 }
1.544
1.545 - /// \brief Gives back the in-node created from the \c node.
1.546 - ///
1.547 - /// Gives back the in-node created from the \c node.
1.548 static Node inNode(const DigraphNode& n) {
1.549 return Node(n, true);
1.550 }
1.551
1.552 - /// \brief Gives back the out-node created from the \c node.
1.553 - ///
1.554 - /// Gives back the out-node created from the \c node.
1.555 static Node outNode(const DigraphNode& n) {
1.556 return Node(n, false);
1.557 }
1.558
1.559 - /// \brief Gives back the arc binds the two part of the node.
1.560 - ///
1.561 - /// Gives back the arc binds the two part of the node.
1.562 static Arc arc(const DigraphNode& n) {
1.563 return Arc(n);
1.564 }
1.565
1.566 - /// \brief Gives back the arc of the original arc.
1.567 - ///
1.568 - /// Gives back the arc of the original arc.
1.569 static Arc arc(const DigraphArc& e) {
1.570 return Arc(e);
1.571 }
1.572 @@ -2275,7 +2233,7 @@
1.573 /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
1.574 /// bind arc in the adapted digraph.
1.575 ///
1.576 - /// By example a maximum flow algoritm can compute how many arc
1.577 + /// For example a maximum flow algorithm can compute how many arc
1.578 /// disjoint paths are in the digraph. But we would like to know how
1.579 /// many node disjoint paths are in the digraph. First we have to
1.580 /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
1.581 @@ -2330,6 +2288,9 @@
1.582 typedef _Digraph Digraph;
1.583 typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
1.584
1.585 + typedef typename Digraph::Node DigraphNode;
1.586 + typedef typename Digraph::Arc DigraphArc;
1.587 +
1.588 typedef typename Parent::Node Node;
1.589 typedef typename Parent::Arc Arc;
1.590
1.591 @@ -2340,6 +2301,62 @@
1.592 Parent::setDigraph(g);
1.593 }
1.594
1.595 + /// \brief Returns true when the node is in-node.
1.596 + ///
1.597 + /// Returns true when the node is in-node.
1.598 + static bool inNode(const Node& n) {
1.599 + return Parent::inNode(n);
1.600 + }
1.601 +
1.602 + /// \brief Returns true when the node is out-node.
1.603 + ///
1.604 + /// Returns true when the node is out-node.
1.605 + static bool outNode(const Node& n) {
1.606 + return Parent::outNode(n);
1.607 + }
1.608 +
1.609 + /// \brief Returns true when the arc is arc in the original digraph.
1.610 + ///
1.611 + /// Returns true when the arc is arc in the original digraph.
1.612 + static bool origArc(const Arc& a) {
1.613 + return Parent::origArc(a);
1.614 + }
1.615 +
1.616 + /// \brief Returns true when the arc binds an in-node and an out-node.
1.617 + ///
1.618 + /// Returns true when the arc binds an in-node and an out-node.
1.619 + static bool bindArc(const Arc& a) {
1.620 + return Parent::bindArc(a);
1.621 + }
1.622 +
1.623 + /// \brief Gives back the in-node created from the \c node.
1.624 + ///
1.625 + /// Gives back the in-node created from the \c node.
1.626 + static Node inNode(const DigraphNode& n) {
1.627 + return Parent::inNode(n);
1.628 + }
1.629 +
1.630 + /// \brief Gives back the out-node created from the \c node.
1.631 + ///
1.632 + /// Gives back the out-node created from the \c node.
1.633 + static Node outNode(const DigraphNode& n) {
1.634 + return Parent::outNode(n);
1.635 + }
1.636 +
1.637 + /// \brief Gives back the arc binds the two part of the node.
1.638 + ///
1.639 + /// Gives back the arc binds the two part of the node.
1.640 + static Arc arc(const DigraphNode& n) {
1.641 + return Parent::arc(n);
1.642 + }
1.643 +
1.644 + /// \brief Gives back the arc of the original arc.
1.645 + ///
1.646 + /// Gives back the arc of the original arc.
1.647 + static Arc arc(const DigraphArc& a) {
1.648 + return Parent::arc(a);
1.649 + }
1.650 +
1.651 /// \brief NodeMap combined from two original NodeMap
1.652 ///
1.653 /// This class adapt two of the original digraph NodeMap to