1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/core.h Tue Jul 15 13:15:39 2008 +0200
1.3 @@ -0,0 +1,1851 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_CORE_H
1.23 +#define LEMON_CORE_H
1.24 +
1.25 +#include <vector>
1.26 +#include <algorithm>
1.27 +
1.28 +#include <lemon/bits/enable_if.h>
1.29 +#include <lemon/bits/traits.h>
1.30 +
1.31 +///\file
1.32 +///\brief LEMON core utilities.
1.33 +
1.34 +namespace lemon {
1.35 +
1.36 + /// \brief Dummy type to make it easier to create invalid iterators.
1.37 + ///
1.38 + /// Dummy type to make it easier to create invalid iterators.
1.39 + /// See \ref INVALID for the usage.
1.40 + struct Invalid {
1.41 + public:
1.42 + bool operator==(Invalid) { return true; }
1.43 + bool operator!=(Invalid) { return false; }
1.44 + bool operator< (Invalid) { return false; }
1.45 + };
1.46 +
1.47 + /// \brief Invalid iterators.
1.48 + ///
1.49 + /// \ref Invalid is a global type that converts to each iterator
1.50 + /// in such a way that the value of the target iterator will be invalid.
1.51 +#ifdef LEMON_ONLY_TEMPLATES
1.52 + const Invalid INVALID = Invalid();
1.53 +#else
1.54 + extern const Invalid INVALID;
1.55 +#endif
1.56 +
1.57 + /// \addtogroup gutils
1.58 + /// @{
1.59 +
1.60 + ///Creates convenience typedefs for the digraph types and iterators
1.61 +
1.62 + ///This \c \#define creates convenience typedefs for the following types
1.63 + ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
1.64 + ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
1.65 + ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
1.66 + ///
1.67 + ///\note If the graph type is a dependent type, ie. the graph type depend
1.68 + ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.69 + ///macro.
1.70 +#define DIGRAPH_TYPEDEFS(Digraph) \
1.71 + typedef Digraph::Node Node; \
1.72 + typedef Digraph::NodeIt NodeIt; \
1.73 + typedef Digraph::Arc Arc; \
1.74 + typedef Digraph::ArcIt ArcIt; \
1.75 + typedef Digraph::InArcIt InArcIt; \
1.76 + typedef Digraph::OutArcIt OutArcIt; \
1.77 + typedef Digraph::NodeMap<bool> BoolNodeMap; \
1.78 + typedef Digraph::NodeMap<int> IntNodeMap; \
1.79 + typedef Digraph::NodeMap<double> DoubleNodeMap; \
1.80 + typedef Digraph::ArcMap<bool> BoolArcMap; \
1.81 + typedef Digraph::ArcMap<int> IntArcMap; \
1.82 + typedef Digraph::ArcMap<double> DoubleArcMap
1.83 +
1.84 + ///Creates convenience typedefs for the digraph types and iterators
1.85 +
1.86 + ///\see DIGRAPH_TYPEDEFS
1.87 + ///
1.88 + ///\note Use this macro, if the graph type is a dependent type,
1.89 + ///ie. the graph type depend on a template parameter.
1.90 +#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
1.91 + typedef typename Digraph::Node Node; \
1.92 + typedef typename Digraph::NodeIt NodeIt; \
1.93 + typedef typename Digraph::Arc Arc; \
1.94 + typedef typename Digraph::ArcIt ArcIt; \
1.95 + typedef typename Digraph::InArcIt InArcIt; \
1.96 + typedef typename Digraph::OutArcIt OutArcIt; \
1.97 + typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
1.98 + typedef typename Digraph::template NodeMap<int> IntNodeMap; \
1.99 + typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
1.100 + typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
1.101 + typedef typename Digraph::template ArcMap<int> IntArcMap; \
1.102 + typedef typename Digraph::template ArcMap<double> DoubleArcMap
1.103 +
1.104 + ///Creates convenience typedefs for the graph types and iterators
1.105 +
1.106 + ///This \c \#define creates the same convenience typedefs as defined
1.107 + ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
1.108 + ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
1.109 + ///\c DoubleEdgeMap.
1.110 + ///
1.111 + ///\note If the graph type is a dependent type, ie. the graph type depend
1.112 + ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.113 + ///macro.
1.114 +#define GRAPH_TYPEDEFS(Graph) \
1.115 + DIGRAPH_TYPEDEFS(Graph); \
1.116 + typedef Graph::Edge Edge; \
1.117 + typedef Graph::EdgeIt EdgeIt; \
1.118 + typedef Graph::IncEdgeIt IncEdgeIt; \
1.119 + typedef Graph::EdgeMap<bool> BoolEdgeMap; \
1.120 + typedef Graph::EdgeMap<int> IntEdgeMap; \
1.121 + typedef Graph::EdgeMap<double> DoubleEdgeMap
1.122 +
1.123 + ///Creates convenience typedefs for the graph types and iterators
1.124 +
1.125 + ///\see GRAPH_TYPEDEFS
1.126 + ///
1.127 + ///\note Use this macro, if the graph type is a dependent type,
1.128 + ///ie. the graph type depend on a template parameter.
1.129 +#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
1.130 + TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
1.131 + typedef typename Graph::Edge Edge; \
1.132 + typedef typename Graph::EdgeIt EdgeIt; \
1.133 + typedef typename Graph::IncEdgeIt IncEdgeIt; \
1.134 + typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
1.135 + typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
1.136 + typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
1.137 +
1.138 + /// \brief Function to count the items in the graph.
1.139 + ///
1.140 + /// This function counts the items (nodes, arcs etc) in the graph.
1.141 + /// The complexity of the function is O(n) because
1.142 + /// it iterates on all of the items.
1.143 + template <typename Graph, typename Item>
1.144 + inline int countItems(const Graph& g) {
1.145 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.146 + int num = 0;
1.147 + for (ItemIt it(g); it != INVALID; ++it) {
1.148 + ++num;
1.149 + }
1.150 + return num;
1.151 + }
1.152 +
1.153 + // Node counting:
1.154 +
1.155 + namespace _core_bits {
1.156 +
1.157 + template <typename Graph, typename Enable = void>
1.158 + struct CountNodesSelector {
1.159 + static int count(const Graph &g) {
1.160 + return countItems<Graph, typename Graph::Node>(g);
1.161 + }
1.162 + };
1.163 +
1.164 + template <typename Graph>
1.165 + struct CountNodesSelector<
1.166 + Graph, typename
1.167 + enable_if<typename Graph::NodeNumTag, void>::type>
1.168 + {
1.169 + static int count(const Graph &g) {
1.170 + return g.nodeNum();
1.171 + }
1.172 + };
1.173 + }
1.174 +
1.175 + /// \brief Function to count the nodes in the graph.
1.176 + ///
1.177 + /// This function counts the nodes in the graph.
1.178 + /// The complexity of the function is O(n) but for some
1.179 + /// graph structures it is specialized to run in O(1).
1.180 + ///
1.181 + /// If the graph contains a \e nodeNum() member function and a
1.182 + /// \e NodeNumTag tag then this function calls directly the member
1.183 + /// function to query the cardinality of the node set.
1.184 + template <typename Graph>
1.185 + inline int countNodes(const Graph& g) {
1.186 + return _core_bits::CountNodesSelector<Graph>::count(g);
1.187 + }
1.188 +
1.189 + // Arc counting:
1.190 +
1.191 + namespace _core_bits {
1.192 +
1.193 + template <typename Graph, typename Enable = void>
1.194 + struct CountArcsSelector {
1.195 + static int count(const Graph &g) {
1.196 + return countItems<Graph, typename Graph::Arc>(g);
1.197 + }
1.198 + };
1.199 +
1.200 + template <typename Graph>
1.201 + struct CountArcsSelector<
1.202 + Graph,
1.203 + typename enable_if<typename Graph::ArcNumTag, void>::type>
1.204 + {
1.205 + static int count(const Graph &g) {
1.206 + return g.arcNum();
1.207 + }
1.208 + };
1.209 + }
1.210 +
1.211 + /// \brief Function to count the arcs in the graph.
1.212 + ///
1.213 + /// This function counts the arcs in the graph.
1.214 + /// The complexity of the function is O(e) but for some
1.215 + /// graph structures it is specialized to run in O(1).
1.216 + ///
1.217 + /// If the graph contains a \e arcNum() member function and a
1.218 + /// \e EdgeNumTag tag then this function calls directly the member
1.219 + /// function to query the cardinality of the arc set.
1.220 + template <typename Graph>
1.221 + inline int countArcs(const Graph& g) {
1.222 + return _core_bits::CountArcsSelector<Graph>::count(g);
1.223 + }
1.224 +
1.225 + // Edge counting:
1.226 + namespace _core_bits {
1.227 +
1.228 + template <typename Graph, typename Enable = void>
1.229 + struct CountEdgesSelector {
1.230 + static int count(const Graph &g) {
1.231 + return countItems<Graph, typename Graph::Edge>(g);
1.232 + }
1.233 + };
1.234 +
1.235 + template <typename Graph>
1.236 + struct CountEdgesSelector<
1.237 + Graph,
1.238 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.239 + {
1.240 + static int count(const Graph &g) {
1.241 + return g.edgeNum();
1.242 + }
1.243 + };
1.244 + }
1.245 +
1.246 + /// \brief Function to count the edges in the graph.
1.247 + ///
1.248 + /// This function counts the edges in the graph.
1.249 + /// The complexity of the function is O(m) but for some
1.250 + /// graph structures it is specialized to run in O(1).
1.251 + ///
1.252 + /// If the graph contains a \e edgeNum() member function and a
1.253 + /// \e EdgeNumTag tag then this function calls directly the member
1.254 + /// function to query the cardinality of the edge set.
1.255 + template <typename Graph>
1.256 + inline int countEdges(const Graph& g) {
1.257 + return _core_bits::CountEdgesSelector<Graph>::count(g);
1.258 +
1.259 + }
1.260 +
1.261 +
1.262 + template <typename Graph, typename DegIt>
1.263 + inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
1.264 + int num = 0;
1.265 + for (DegIt it(_g, _n); it != INVALID; ++it) {
1.266 + ++num;
1.267 + }
1.268 + return num;
1.269 + }
1.270 +
1.271 + /// \brief Function to count the number of the out-arcs from node \c n.
1.272 + ///
1.273 + /// This function counts the number of the out-arcs from node \c n
1.274 + /// in the graph.
1.275 + template <typename Graph>
1.276 + inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
1.277 + return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
1.278 + }
1.279 +
1.280 + /// \brief Function to count the number of the in-arcs to node \c n.
1.281 + ///
1.282 + /// This function counts the number of the in-arcs to node \c n
1.283 + /// in the graph.
1.284 + template <typename Graph>
1.285 + inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
1.286 + return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
1.287 + }
1.288 +
1.289 + /// \brief Function to count the number of the inc-edges to node \c n.
1.290 + ///
1.291 + /// This function counts the number of the inc-edges to node \c n
1.292 + /// in the graph.
1.293 + template <typename Graph>
1.294 + inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
1.295 + return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
1.296 + }
1.297 +
1.298 + namespace _core_bits {
1.299 +
1.300 + template <typename Digraph, typename Item, typename RefMap>
1.301 + class MapCopyBase {
1.302 + public:
1.303 + virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
1.304 +
1.305 + virtual ~MapCopyBase() {}
1.306 + };
1.307 +
1.308 + template <typename Digraph, typename Item, typename RefMap,
1.309 + typename ToMap, typename FromMap>
1.310 + class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.311 + public:
1.312 +
1.313 + MapCopy(ToMap& tmap, const FromMap& map)
1.314 + : _tmap(tmap), _map(map) {}
1.315 +
1.316 + virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.317 + typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.318 + for (ItemIt it(digraph); it != INVALID; ++it) {
1.319 + _tmap.set(refMap[it], _map[it]);
1.320 + }
1.321 + }
1.322 +
1.323 + private:
1.324 + ToMap& _tmap;
1.325 + const FromMap& _map;
1.326 + };
1.327 +
1.328 + template <typename Digraph, typename Item, typename RefMap, typename It>
1.329 + class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.330 + public:
1.331 +
1.332 + ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
1.333 +
1.334 + virtual void copy(const Digraph&, const RefMap& refMap) {
1.335 + _it = refMap[_item];
1.336 + }
1.337 +
1.338 + private:
1.339 + It& _it;
1.340 + Item _item;
1.341 + };
1.342 +
1.343 + template <typename Digraph, typename Item, typename RefMap, typename Ref>
1.344 + class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.345 + public:
1.346 +
1.347 + RefCopy(Ref& map) : _map(map) {}
1.348 +
1.349 + virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.350 + typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.351 + for (ItemIt it(digraph); it != INVALID; ++it) {
1.352 + _map.set(it, refMap[it]);
1.353 + }
1.354 + }
1.355 +
1.356 + private:
1.357 + Ref& _map;
1.358 + };
1.359 +
1.360 + template <typename Digraph, typename Item, typename RefMap,
1.361 + typename CrossRef>
1.362 + class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.363 + public:
1.364 +
1.365 + CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
1.366 +
1.367 + virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.368 + typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.369 + for (ItemIt it(digraph); it != INVALID; ++it) {
1.370 + _cmap.set(refMap[it], it);
1.371 + }
1.372 + }
1.373 +
1.374 + private:
1.375 + CrossRef& _cmap;
1.376 + };
1.377 +
1.378 + template <typename Digraph, typename Enable = void>
1.379 + struct DigraphCopySelector {
1.380 + template <typename From, typename NodeRefMap, typename ArcRefMap>
1.381 + static void copy(Digraph &to, const From& from,
1.382 + NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
1.383 + for (typename From::NodeIt it(from); it != INVALID; ++it) {
1.384 + nodeRefMap[it] = to.addNode();
1.385 + }
1.386 + for (typename From::ArcIt it(from); it != INVALID; ++it) {
1.387 + arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
1.388 + nodeRefMap[from.target(it)]);
1.389 + }
1.390 + }
1.391 + };
1.392 +
1.393 + template <typename Digraph>
1.394 + struct DigraphCopySelector<
1.395 + Digraph,
1.396 + typename enable_if<typename Digraph::BuildTag, void>::type>
1.397 + {
1.398 + template <typename From, typename NodeRefMap, typename ArcRefMap>
1.399 + static void copy(Digraph &to, const From& from,
1.400 + NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
1.401 + to.build(from, nodeRefMap, arcRefMap);
1.402 + }
1.403 + };
1.404 +
1.405 + template <typename Graph, typename Enable = void>
1.406 + struct GraphCopySelector {
1.407 + template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.408 + static void copy(Graph &to, const From& from,
1.409 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.410 + for (typename From::NodeIt it(from); it != INVALID; ++it) {
1.411 + nodeRefMap[it] = to.addNode();
1.412 + }
1.413 + for (typename From::EdgeIt it(from); it != INVALID; ++it) {
1.414 + edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
1.415 + nodeRefMap[from.v(it)]);
1.416 + }
1.417 + }
1.418 + };
1.419 +
1.420 + template <typename Graph>
1.421 + struct GraphCopySelector<
1.422 + Graph,
1.423 + typename enable_if<typename Graph::BuildTag, void>::type>
1.424 + {
1.425 + template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.426 + static void copy(Graph &to, const From& from,
1.427 + NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.428 + to.build(from, nodeRefMap, edgeRefMap);
1.429 + }
1.430 + };
1.431 +
1.432 + }
1.433 +
1.434 + /// \brief Class to copy a digraph.
1.435 + ///
1.436 + /// Class to copy a digraph to another digraph (duplicate a digraph). The
1.437 + /// simplest way of using it is through the \c copyDigraph() function.
1.438 + ///
1.439 + /// This class not just make a copy of a graph, but it can create
1.440 + /// references and cross references between the nodes and arcs of
1.441 + /// the two graphs, it can copy maps for use with the newly created
1.442 + /// graph and copy nodes and arcs.
1.443 + ///
1.444 + /// To make a copy from a graph, first an instance of DigraphCopy
1.445 + /// should be created, then the data belongs to the graph should
1.446 + /// assigned to copy. In the end, the \c run() member should be
1.447 + /// called.
1.448 + ///
1.449 + /// The next code copies a graph with several data:
1.450 + ///\code
1.451 + /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.452 + /// // create a reference for the nodes
1.453 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.454 + /// dc.nodeRef(nr);
1.455 + /// // create a cross reference (inverse) for the arcs
1.456 + /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
1.457 + /// dc.arcCrossRef(acr);
1.458 + /// // copy an arc map
1.459 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.460 + /// NewGraph::ArcMap<double> namap(new_graph);
1.461 + /// dc.arcMap(namap, oamap);
1.462 + /// // copy a node
1.463 + /// OrigGraph::Node on;
1.464 + /// NewGraph::Node nn;
1.465 + /// dc.node(nn, on);
1.466 + /// // Executions of copy
1.467 + /// dc.run();
1.468 + ///\endcode
1.469 + template <typename To, typename From>
1.470 + class DigraphCopy {
1.471 + private:
1.472 +
1.473 + typedef typename From::Node Node;
1.474 + typedef typename From::NodeIt NodeIt;
1.475 + typedef typename From::Arc Arc;
1.476 + typedef typename From::ArcIt ArcIt;
1.477 +
1.478 + typedef typename To::Node TNode;
1.479 + typedef typename To::Arc TArc;
1.480 +
1.481 + typedef typename From::template NodeMap<TNode> NodeRefMap;
1.482 + typedef typename From::template ArcMap<TArc> ArcRefMap;
1.483 +
1.484 +
1.485 + public:
1.486 +
1.487 +
1.488 + /// \brief Constructor for the DigraphCopy.
1.489 + ///
1.490 + /// It copies the content of the \c _from digraph into the
1.491 + /// \c _to digraph.
1.492 + DigraphCopy(To& to, const From& from)
1.493 + : _from(from), _to(to) {}
1.494 +
1.495 + /// \brief Destructor of the DigraphCopy
1.496 + ///
1.497 + /// Destructor of the DigraphCopy
1.498 + ~DigraphCopy() {
1.499 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.500 + delete _node_maps[i];
1.501 + }
1.502 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.503 + delete _arc_maps[i];
1.504 + }
1.505 +
1.506 + }
1.507 +
1.508 + /// \brief Copies the node references into the given map.
1.509 + ///
1.510 + /// Copies the node references into the given map. The parameter
1.511 + /// should be a map, which key type is the Node type of the source
1.512 + /// graph, while the value type is the Node type of the
1.513 + /// destination graph.
1.514 + template <typename NodeRef>
1.515 + DigraphCopy& nodeRef(NodeRef& map) {
1.516 + _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1.517 + NodeRefMap, NodeRef>(map));
1.518 + return *this;
1.519 + }
1.520 +
1.521 + /// \brief Copies the node cross references into the given map.
1.522 + ///
1.523 + /// Copies the node cross references (reverse references) into
1.524 + /// the given map. The parameter should be a map, which key type
1.525 + /// is the Node type of the destination graph, while the value type is
1.526 + /// the Node type of the source graph.
1.527 + template <typename NodeCrossRef>
1.528 + DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.529 + _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1.530 + NodeRefMap, NodeCrossRef>(map));
1.531 + return *this;
1.532 + }
1.533 +
1.534 + /// \brief Make copy of the given map.
1.535 + ///
1.536 + /// Makes copy of the given map for the newly created digraph.
1.537 + /// The new map's key type is the destination graph's node type,
1.538 + /// and the copied map's key type is the source graph's node type.
1.539 + template <typename ToMap, typename FromMap>
1.540 + DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.541 + _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1.542 + NodeRefMap, ToMap, FromMap>(tmap, map));
1.543 + return *this;
1.544 + }
1.545 +
1.546 + /// \brief Make a copy of the given node.
1.547 + ///
1.548 + /// Make a copy of the given node.
1.549 + DigraphCopy& node(TNode& tnode, const Node& snode) {
1.550 + _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1.551 + NodeRefMap, TNode>(tnode, snode));
1.552 + return *this;
1.553 + }
1.554 +
1.555 + /// \brief Copies the arc references into the given map.
1.556 + ///
1.557 + /// Copies the arc references into the given map.
1.558 + template <typename ArcRef>
1.559 + DigraphCopy& arcRef(ArcRef& map) {
1.560 + _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1.561 + ArcRefMap, ArcRef>(map));
1.562 + return *this;
1.563 + }
1.564 +
1.565 + /// \brief Copies the arc cross references into the given map.
1.566 + ///
1.567 + /// Copies the arc cross references (reverse references) into
1.568 + /// the given map.
1.569 + template <typename ArcCrossRef>
1.570 + DigraphCopy& arcCrossRef(ArcCrossRef& map) {
1.571 + _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1.572 + ArcRefMap, ArcCrossRef>(map));
1.573 + return *this;
1.574 + }
1.575 +
1.576 + /// \brief Make copy of the given map.
1.577 + ///
1.578 + /// Makes copy of the given map for the newly created digraph.
1.579 + /// The new map's key type is the to digraph's arc type,
1.580 + /// and the copied map's key type is the from digraph's arc
1.581 + /// type.
1.582 + template <typename ToMap, typename FromMap>
1.583 + DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.584 + _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1.585 + ArcRefMap, ToMap, FromMap>(tmap, map));
1.586 + return *this;
1.587 + }
1.588 +
1.589 + /// \brief Make a copy of the given arc.
1.590 + ///
1.591 + /// Make a copy of the given arc.
1.592 + DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.593 + _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1.594 + ArcRefMap, TArc>(tarc, sarc));
1.595 + return *this;
1.596 + }
1.597 +
1.598 + /// \brief Executes the copies.
1.599 + ///
1.600 + /// Executes the copies.
1.601 + void run() {
1.602 + NodeRefMap nodeRefMap(_from);
1.603 + ArcRefMap arcRefMap(_from);
1.604 + _core_bits::DigraphCopySelector<To>::
1.605 + copy(_to, _from, nodeRefMap, arcRefMap);
1.606 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.607 + _node_maps[i]->copy(_from, nodeRefMap);
1.608 + }
1.609 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.610 + _arc_maps[i]->copy(_from, arcRefMap);
1.611 + }
1.612 + }
1.613 +
1.614 + protected:
1.615 +
1.616 +
1.617 + const From& _from;
1.618 + To& _to;
1.619 +
1.620 + std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.621 + _node_maps;
1.622 +
1.623 + std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.624 + _arc_maps;
1.625 +
1.626 + };
1.627 +
1.628 + /// \brief Copy a digraph to another digraph.
1.629 + ///
1.630 + /// Copy a digraph to another digraph. The complete usage of the
1.631 + /// function is detailed in the DigraphCopy class, but a short
1.632 + /// example shows a basic work:
1.633 + ///\code
1.634 + /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.635 + ///\endcode
1.636 + ///
1.637 + /// After the copy the \c nr map will contain the mapping from the
1.638 + /// nodes of the \c from digraph to the nodes of the \c to digraph and
1.639 + /// \c ecr will contain the mapping from the arcs of the \c to digraph
1.640 + /// to the arcs of the \c from digraph.
1.641 + ///
1.642 + /// \see DigraphCopy
1.643 + template <typename To, typename From>
1.644 + DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
1.645 + return DigraphCopy<To, From>(to, from);
1.646 + }
1.647 +
1.648 + /// \brief Class to copy a graph.
1.649 + ///
1.650 + /// Class to copy a graph to another graph (duplicate a graph). The
1.651 + /// simplest way of using it is through the \c copyGraph() function.
1.652 + ///
1.653 + /// This class not just make a copy of a graph, but it can create
1.654 + /// references and cross references between the nodes, edges and arcs of
1.655 + /// the two graphs, it can copy maps for use with the newly created
1.656 + /// graph and copy nodes, edges and arcs.
1.657 + ///
1.658 + /// To make a copy from a graph, first an instance of GraphCopy
1.659 + /// should be created, then the data belongs to the graph should
1.660 + /// assigned to copy. In the end, the \c run() member should be
1.661 + /// called.
1.662 + ///
1.663 + /// The next code copies a graph with several data:
1.664 + ///\code
1.665 + /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.666 + /// // create a reference for the nodes
1.667 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.668 + /// dc.nodeRef(nr);
1.669 + /// // create a cross reference (inverse) for the edges
1.670 + /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
1.671 + /// dc.edgeCrossRef(ecr);
1.672 + /// // copy an arc map
1.673 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.674 + /// NewGraph::ArcMap<double> namap(new_graph);
1.675 + /// dc.arcMap(namap, oamap);
1.676 + /// // copy a node
1.677 + /// OrigGraph::Node on;
1.678 + /// NewGraph::Node nn;
1.679 + /// dc.node(nn, on);
1.680 + /// // Executions of copy
1.681 + /// dc.run();
1.682 + ///\endcode
1.683 + template <typename To, typename From>
1.684 + class GraphCopy {
1.685 + private:
1.686 +
1.687 + typedef typename From::Node Node;
1.688 + typedef typename From::NodeIt NodeIt;
1.689 + typedef typename From::Arc Arc;
1.690 + typedef typename From::ArcIt ArcIt;
1.691 + typedef typename From::Edge Edge;
1.692 + typedef typename From::EdgeIt EdgeIt;
1.693 +
1.694 + typedef typename To::Node TNode;
1.695 + typedef typename To::Arc TArc;
1.696 + typedef typename To::Edge TEdge;
1.697 +
1.698 + typedef typename From::template NodeMap<TNode> NodeRefMap;
1.699 + typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.700 +
1.701 + struct ArcRefMap {
1.702 + ArcRefMap(const To& to, const From& from,
1.703 + const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
1.704 + : _to(to), _from(from),
1.705 + _edge_ref(edge_ref), _node_ref(node_ref) {}
1.706 +
1.707 + typedef typename From::Arc Key;
1.708 + typedef typename To::Arc Value;
1.709 +
1.710 + Value operator[](const Key& key) const {
1.711 + bool forward = _from.u(key) != _from.v(key) ?
1.712 + _node_ref[_from.source(key)] ==
1.713 + _to.source(_to.direct(_edge_ref[key], true)) :
1.714 + _from.direction(key);
1.715 + return _to.direct(_edge_ref[key], forward);
1.716 + }
1.717 +
1.718 + const To& _to;
1.719 + const From& _from;
1.720 + const EdgeRefMap& _edge_ref;
1.721 + const NodeRefMap& _node_ref;
1.722 + };
1.723 +
1.724 +
1.725 + public:
1.726 +
1.727 +
1.728 + /// \brief Constructor for the GraphCopy.
1.729 + ///
1.730 + /// It copies the content of the \c _from graph into the
1.731 + /// \c _to graph.
1.732 + GraphCopy(To& to, const From& from)
1.733 + : _from(from), _to(to) {}
1.734 +
1.735 + /// \brief Destructor of the GraphCopy
1.736 + ///
1.737 + /// Destructor of the GraphCopy
1.738 + ~GraphCopy() {
1.739 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.740 + delete _node_maps[i];
1.741 + }
1.742 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.743 + delete _arc_maps[i];
1.744 + }
1.745 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.746 + delete _edge_maps[i];
1.747 + }
1.748 +
1.749 + }
1.750 +
1.751 + /// \brief Copies the node references into the given map.
1.752 + ///
1.753 + /// Copies the node references into the given map.
1.754 + template <typename NodeRef>
1.755 + GraphCopy& nodeRef(NodeRef& map) {
1.756 + _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1.757 + NodeRefMap, NodeRef>(map));
1.758 + return *this;
1.759 + }
1.760 +
1.761 + /// \brief Copies the node cross references into the given map.
1.762 + ///
1.763 + /// Copies the node cross references (reverse references) into
1.764 + /// the given map.
1.765 + template <typename NodeCrossRef>
1.766 + GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.767 + _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1.768 + NodeRefMap, NodeCrossRef>(map));
1.769 + return *this;
1.770 + }
1.771 +
1.772 + /// \brief Make copy of the given map.
1.773 + ///
1.774 + /// Makes copy of the given map for the newly created graph.
1.775 + /// The new map's key type is the to graph's node type,
1.776 + /// and the copied map's key type is the from graph's node
1.777 + /// type.
1.778 + template <typename ToMap, typename FromMap>
1.779 + GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.780 + _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1.781 + NodeRefMap, ToMap, FromMap>(tmap, map));
1.782 + return *this;
1.783 + }
1.784 +
1.785 + /// \brief Make a copy of the given node.
1.786 + ///
1.787 + /// Make a copy of the given node.
1.788 + GraphCopy& node(TNode& tnode, const Node& snode) {
1.789 + _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1.790 + NodeRefMap, TNode>(tnode, snode));
1.791 + return *this;
1.792 + }
1.793 +
1.794 + /// \brief Copies the arc references into the given map.
1.795 + ///
1.796 + /// Copies the arc references into the given map.
1.797 + template <typename ArcRef>
1.798 + GraphCopy& arcRef(ArcRef& map) {
1.799 + _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1.800 + ArcRefMap, ArcRef>(map));
1.801 + return *this;
1.802 + }
1.803 +
1.804 + /// \brief Copies the arc cross references into the given map.
1.805 + ///
1.806 + /// Copies the arc cross references (reverse references) into
1.807 + /// the given map.
1.808 + template <typename ArcCrossRef>
1.809 + GraphCopy& arcCrossRef(ArcCrossRef& map) {
1.810 + _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1.811 + ArcRefMap, ArcCrossRef>(map));
1.812 + return *this;
1.813 + }
1.814 +
1.815 + /// \brief Make copy of the given map.
1.816 + ///
1.817 + /// Makes copy of the given map for the newly created graph.
1.818 + /// The new map's key type is the to graph's arc type,
1.819 + /// and the copied map's key type is the from graph's arc
1.820 + /// type.
1.821 + template <typename ToMap, typename FromMap>
1.822 + GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.823 + _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1.824 + ArcRefMap, ToMap, FromMap>(tmap, map));
1.825 + return *this;
1.826 + }
1.827 +
1.828 + /// \brief Make a copy of the given arc.
1.829 + ///
1.830 + /// Make a copy of the given arc.
1.831 + GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.832 + _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1.833 + ArcRefMap, TArc>(tarc, sarc));
1.834 + return *this;
1.835 + }
1.836 +
1.837 + /// \brief Copies the edge references into the given map.
1.838 + ///
1.839 + /// Copies the edge references into the given map.
1.840 + template <typename EdgeRef>
1.841 + GraphCopy& edgeRef(EdgeRef& map) {
1.842 + _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1.843 + EdgeRefMap, EdgeRef>(map));
1.844 + return *this;
1.845 + }
1.846 +
1.847 + /// \brief Copies the edge cross references into the given map.
1.848 + ///
1.849 + /// Copies the edge cross references (reverse
1.850 + /// references) into the given map.
1.851 + template <typename EdgeCrossRef>
1.852 + GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.853 + _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1.854 + Edge, EdgeRefMap, EdgeCrossRef>(map));
1.855 + return *this;
1.856 + }
1.857 +
1.858 + /// \brief Make copy of the given map.
1.859 + ///
1.860 + /// Makes copy of the given map for the newly created graph.
1.861 + /// The new map's key type is the to graph's edge type,
1.862 + /// and the copied map's key type is the from graph's edge
1.863 + /// type.
1.864 + template <typename ToMap, typename FromMap>
1.865 + GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1.866 + _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1.867 + EdgeRefMap, ToMap, FromMap>(tmap, map));
1.868 + return *this;
1.869 + }
1.870 +
1.871 + /// \brief Make a copy of the given edge.
1.872 + ///
1.873 + /// Make a copy of the given edge.
1.874 + GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1.875 + _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1.876 + EdgeRefMap, TEdge>(tedge, sedge));
1.877 + return *this;
1.878 + }
1.879 +
1.880 + /// \brief Executes the copies.
1.881 + ///
1.882 + /// Executes the copies.
1.883 + void run() {
1.884 + NodeRefMap nodeRefMap(_from);
1.885 + EdgeRefMap edgeRefMap(_from);
1.886 + ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
1.887 + _core_bits::GraphCopySelector<To>::
1.888 + copy(_to, _from, nodeRefMap, edgeRefMap);
1.889 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.890 + _node_maps[i]->copy(_from, nodeRefMap);
1.891 + }
1.892 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.893 + _edge_maps[i]->copy(_from, edgeRefMap);
1.894 + }
1.895 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.896 + _arc_maps[i]->copy(_from, arcRefMap);
1.897 + }
1.898 + }
1.899 +
1.900 + private:
1.901 +
1.902 + const From& _from;
1.903 + To& _to;
1.904 +
1.905 + std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.906 + _node_maps;
1.907 +
1.908 + std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.909 + _arc_maps;
1.910 +
1.911 + std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.912 + _edge_maps;
1.913 +
1.914 + };
1.915 +
1.916 + /// \brief Copy a graph to another graph.
1.917 + ///
1.918 + /// Copy a graph to another graph. The complete usage of the
1.919 + /// function is detailed in the GraphCopy class, but a short
1.920 + /// example shows a basic work:
1.921 + ///\code
1.922 + /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.923 + ///\endcode
1.924 + ///
1.925 + /// After the copy the \c nr map will contain the mapping from the
1.926 + /// nodes of the \c from graph to the nodes of the \c to graph and
1.927 + /// \c ecr will contain the mapping from the arcs of the \c to graph
1.928 + /// to the arcs of the \c from graph.
1.929 + ///
1.930 + /// \see GraphCopy
1.931 + template <typename To, typename From>
1.932 + GraphCopy<To, From>
1.933 + copyGraph(To& to, const From& from) {
1.934 + return GraphCopy<To, From>(to, from);
1.935 + }
1.936 +
1.937 + namespace _core_bits {
1.938 +
1.939 + template <typename Graph, typename Enable = void>
1.940 + struct FindArcSelector {
1.941 + typedef typename Graph::Node Node;
1.942 + typedef typename Graph::Arc Arc;
1.943 + static Arc find(const Graph &g, Node u, Node v, Arc e) {
1.944 + if (e == INVALID) {
1.945 + g.firstOut(e, u);
1.946 + } else {
1.947 + g.nextOut(e);
1.948 + }
1.949 + while (e != INVALID && g.target(e) != v) {
1.950 + g.nextOut(e);
1.951 + }
1.952 + return e;
1.953 + }
1.954 + };
1.955 +
1.956 + template <typename Graph>
1.957 + struct FindArcSelector<
1.958 + Graph,
1.959 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.960 + {
1.961 + typedef typename Graph::Node Node;
1.962 + typedef typename Graph::Arc Arc;
1.963 + static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1.964 + return g.findArc(u, v, prev);
1.965 + }
1.966 + };
1.967 + }
1.968 +
1.969 + /// \brief Finds an arc between two nodes of a graph.
1.970 + ///
1.971 + /// Finds an arc from node \c u to node \c v in graph \c g.
1.972 + ///
1.973 + /// If \c prev is \ref INVALID (this is the default value), then
1.974 + /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.975 + /// the next arc from \c u to \c v after \c prev.
1.976 + /// \return The found arc or \ref INVALID if there is no such an arc.
1.977 + ///
1.978 + /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.979 + ///\code
1.980 + /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
1.981 + /// ...
1.982 + /// }
1.983 + ///\endcode
1.984 + ///
1.985 + ///\sa ArcLookUp
1.986 + ///\sa AllArcLookUp
1.987 + ///\sa DynArcLookUp
1.988 + ///\sa ConArcIt
1.989 + template <typename Graph>
1.990 + inline typename Graph::Arc
1.991 + findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.992 + typename Graph::Arc prev = INVALID) {
1.993 + return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1.994 + }
1.995 +
1.996 + /// \brief Iterator for iterating on arcs connected the same nodes.
1.997 + ///
1.998 + /// Iterator for iterating on arcs connected the same nodes. It is
1.999 + /// higher level interface for the findArc() function. You can
1.1000 + /// use it the following way:
1.1001 + ///\code
1.1002 + /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.1003 + /// ...
1.1004 + /// }
1.1005 + ///\endcode
1.1006 + ///
1.1007 + ///\sa findArc()
1.1008 + ///\sa ArcLookUp
1.1009 + ///\sa AllArcLookUp
1.1010 + ///\sa DynArcLookUp
1.1011 + template <typename _Graph>
1.1012 + class ConArcIt : public _Graph::Arc {
1.1013 + public:
1.1014 +
1.1015 + typedef _Graph Graph;
1.1016 + typedef typename Graph::Arc Parent;
1.1017 +
1.1018 + typedef typename Graph::Arc Arc;
1.1019 + typedef typename Graph::Node Node;
1.1020 +
1.1021 + /// \brief Constructor.
1.1022 + ///
1.1023 + /// Construct a new ConArcIt iterating on the arcs which
1.1024 + /// connects the \c u and \c v node.
1.1025 + ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1.1026 + Parent::operator=(findArc(_graph, u, v));
1.1027 + }
1.1028 +
1.1029 + /// \brief Constructor.
1.1030 + ///
1.1031 + /// Construct a new ConArcIt which continues the iterating from
1.1032 + /// the \c e arc.
1.1033 + ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1.1034 +
1.1035 + /// \brief Increment operator.
1.1036 + ///
1.1037 + /// It increments the iterator and gives back the next arc.
1.1038 + ConArcIt& operator++() {
1.1039 + Parent::operator=(findArc(_graph, _graph.source(*this),
1.1040 + _graph.target(*this), *this));
1.1041 + return *this;
1.1042 + }
1.1043 + private:
1.1044 + const Graph& _graph;
1.1045 + };
1.1046 +
1.1047 + namespace _core_bits {
1.1048 +
1.1049 + template <typename Graph, typename Enable = void>
1.1050 + struct FindEdgeSelector {
1.1051 + typedef typename Graph::Node Node;
1.1052 + typedef typename Graph::Edge Edge;
1.1053 + static Edge find(const Graph &g, Node u, Node v, Edge e) {
1.1054 + bool b;
1.1055 + if (u != v) {
1.1056 + if (e == INVALID) {
1.1057 + g.firstInc(e, b, u);
1.1058 + } else {
1.1059 + b = g.u(e) == u;
1.1060 + g.nextInc(e, b);
1.1061 + }
1.1062 + while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1.1063 + g.nextInc(e, b);
1.1064 + }
1.1065 + } else {
1.1066 + if (e == INVALID) {
1.1067 + g.firstInc(e, b, u);
1.1068 + } else {
1.1069 + b = true;
1.1070 + g.nextInc(e, b);
1.1071 + }
1.1072 + while (e != INVALID && (!b || g.v(e) != v)) {
1.1073 + g.nextInc(e, b);
1.1074 + }
1.1075 + }
1.1076 + return e;
1.1077 + }
1.1078 + };
1.1079 +
1.1080 + template <typename Graph>
1.1081 + struct FindEdgeSelector<
1.1082 + Graph,
1.1083 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.1084 + {
1.1085 + typedef typename Graph::Node Node;
1.1086 + typedef typename Graph::Edge Edge;
1.1087 + static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1.1088 + return g.findEdge(u, v, prev);
1.1089 + }
1.1090 + };
1.1091 + }
1.1092 +
1.1093 + /// \brief Finds an edge between two nodes of a graph.
1.1094 + ///
1.1095 + /// Finds an edge from node \c u to node \c v in graph \c g.
1.1096 + /// If the node \c u and node \c v is equal then each loop edge
1.1097 + /// will be enumerated once.
1.1098 + ///
1.1099 + /// If \c prev is \ref INVALID (this is the default value), then
1.1100 + /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.1101 + /// the next arc from \c u to \c v after \c prev.
1.1102 + /// \return The found arc or \ref INVALID if there is no such an arc.
1.1103 + ///
1.1104 + /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.1105 + ///\code
1.1106 + /// for(Edge e = findEdge(g,u,v); e != INVALID;
1.1107 + /// e = findEdge(g,u,v,e)) {
1.1108 + /// ...
1.1109 + /// }
1.1110 + ///\endcode
1.1111 + ///
1.1112 + ///\sa ConEdgeIt
1.1113 +
1.1114 + template <typename Graph>
1.1115 + inline typename Graph::Edge
1.1116 + findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.1117 + typename Graph::Edge p = INVALID) {
1.1118 + return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1.1119 + }
1.1120 +
1.1121 + /// \brief Iterator for iterating on edges connected the same nodes.
1.1122 + ///
1.1123 + /// Iterator for iterating on edges connected the same nodes. It is
1.1124 + /// higher level interface for the findEdge() function. You can
1.1125 + /// use it the following way:
1.1126 + ///\code
1.1127 + /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.1128 + /// ...
1.1129 + /// }
1.1130 + ///\endcode
1.1131 + ///
1.1132 + ///\sa findEdge()
1.1133 + template <typename _Graph>
1.1134 + class ConEdgeIt : public _Graph::Edge {
1.1135 + public:
1.1136 +
1.1137 + typedef _Graph Graph;
1.1138 + typedef typename Graph::Edge Parent;
1.1139 +
1.1140 + typedef typename Graph::Edge Edge;
1.1141 + typedef typename Graph::Node Node;
1.1142 +
1.1143 + /// \brief Constructor.
1.1144 + ///
1.1145 + /// Construct a new ConEdgeIt iterating on the edges which
1.1146 + /// connects the \c u and \c v node.
1.1147 + ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
1.1148 + Parent::operator=(findEdge(_graph, u, v));
1.1149 + }
1.1150 +
1.1151 + /// \brief Constructor.
1.1152 + ///
1.1153 + /// Construct a new ConEdgeIt which continues the iterating from
1.1154 + /// the \c e edge.
1.1155 + ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1.1156 +
1.1157 + /// \brief Increment operator.
1.1158 + ///
1.1159 + /// It increments the iterator and gives back the next edge.
1.1160 + ConEdgeIt& operator++() {
1.1161 + Parent::operator=(findEdge(_graph, _graph.u(*this),
1.1162 + _graph.v(*this), *this));
1.1163 + return *this;
1.1164 + }
1.1165 + private:
1.1166 + const Graph& _graph;
1.1167 + };
1.1168 +
1.1169 +
1.1170 + ///Dynamic arc look up between given endpoints.
1.1171 +
1.1172 + ///Using this class, you can find an arc in a digraph from a given
1.1173 + ///source to a given target in amortized time <em>O(log d)</em>,
1.1174 + ///where <em>d</em> is the out-degree of the source node.
1.1175 + ///
1.1176 + ///It is possible to find \e all parallel arcs between two nodes with
1.1177 + ///the \c findFirst() and \c findNext() members.
1.1178 + ///
1.1179 + ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
1.1180 + ///digraph is not changed so frequently.
1.1181 + ///
1.1182 + ///This class uses a self-adjusting binary search tree, Sleator's
1.1183 + ///and Tarjan's Splay tree for guarantee the logarithmic amortized
1.1184 + ///time bound for arc lookups. This class also guarantees the
1.1185 + ///optimal time bound in a constant factor for any distribution of
1.1186 + ///queries.
1.1187 + ///
1.1188 + ///\tparam G The type of the underlying digraph.
1.1189 + ///
1.1190 + ///\sa ArcLookUp
1.1191 + ///\sa AllArcLookUp
1.1192 + template<class G>
1.1193 + class DynArcLookUp
1.1194 + : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1.1195 + {
1.1196 + public:
1.1197 + typedef typename ItemSetTraits<G, typename G::Arc>
1.1198 + ::ItemNotifier::ObserverBase Parent;
1.1199 +
1.1200 + TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.1201 + typedef G Digraph;
1.1202 +
1.1203 + protected:
1.1204 +
1.1205 + class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
1.1206 + public:
1.1207 +
1.1208 + typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
1.1209 +
1.1210 + AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1.1211 +
1.1212 + virtual void add(const Node& node) {
1.1213 + Parent::add(node);
1.1214 + Parent::set(node, INVALID);
1.1215 + }
1.1216 +
1.1217 + virtual void add(const std::vector<Node>& nodes) {
1.1218 + Parent::add(nodes);
1.1219 + for (int i = 0; i < int(nodes.size()); ++i) {
1.1220 + Parent::set(nodes[i], INVALID);
1.1221 + }
1.1222 + }
1.1223 +
1.1224 + virtual void build() {
1.1225 + Parent::build();
1.1226 + Node it;
1.1227 + typename Parent::Notifier* nf = Parent::notifier();
1.1228 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.1229 + Parent::set(it, INVALID);
1.1230 + }
1.1231 + }
1.1232 + };
1.1233 +
1.1234 + const Digraph &_g;
1.1235 + AutoNodeMap _head;
1.1236 + typename Digraph::template ArcMap<Arc> _parent;
1.1237 + typename Digraph::template ArcMap<Arc> _left;
1.1238 + typename Digraph::template ArcMap<Arc> _right;
1.1239 +
1.1240 + class ArcLess {
1.1241 + const Digraph &g;
1.1242 + public:
1.1243 + ArcLess(const Digraph &_g) : g(_g) {}
1.1244 + bool operator()(Arc a,Arc b) const
1.1245 + {
1.1246 + return g.target(a)<g.target(b);
1.1247 + }
1.1248 + };
1.1249 +
1.1250 + public:
1.1251 +
1.1252 + ///Constructor
1.1253 +
1.1254 + ///Constructor.
1.1255 + ///
1.1256 + ///It builds up the search database.
1.1257 + DynArcLookUp(const Digraph &g)
1.1258 + : _g(g),_head(g),_parent(g),_left(g),_right(g)
1.1259 + {
1.1260 + Parent::attach(_g.notifier(typename Digraph::Arc()));
1.1261 + refresh();
1.1262 + }
1.1263 +
1.1264 + protected:
1.1265 +
1.1266 + virtual void add(const Arc& arc) {
1.1267 + insert(arc);
1.1268 + }
1.1269 +
1.1270 + virtual void add(const std::vector<Arc>& arcs) {
1.1271 + for (int i = 0; i < int(arcs.size()); ++i) {
1.1272 + insert(arcs[i]);
1.1273 + }
1.1274 + }
1.1275 +
1.1276 + virtual void erase(const Arc& arc) {
1.1277 + remove(arc);
1.1278 + }
1.1279 +
1.1280 + virtual void erase(const std::vector<Arc>& arcs) {
1.1281 + for (int i = 0; i < int(arcs.size()); ++i) {
1.1282 + remove(arcs[i]);
1.1283 + }
1.1284 + }
1.1285 +
1.1286 + virtual void build() {
1.1287 + refresh();
1.1288 + }
1.1289 +
1.1290 + virtual void clear() {
1.1291 + for(NodeIt n(_g);n!=INVALID;++n) {
1.1292 + _head.set(n, INVALID);
1.1293 + }
1.1294 + }
1.1295 +
1.1296 + void insert(Arc arc) {
1.1297 + Node s = _g.source(arc);
1.1298 + Node t = _g.target(arc);
1.1299 + _left.set(arc, INVALID);
1.1300 + _right.set(arc, INVALID);
1.1301 +
1.1302 + Arc e = _head[s];
1.1303 + if (e == INVALID) {
1.1304 + _head.set(s, arc);
1.1305 + _parent.set(arc, INVALID);
1.1306 + return;
1.1307 + }
1.1308 + while (true) {
1.1309 + if (t < _g.target(e)) {
1.1310 + if (_left[e] == INVALID) {
1.1311 + _left.set(e, arc);
1.1312 + _parent.set(arc, e);
1.1313 + splay(arc);
1.1314 + return;
1.1315 + } else {
1.1316 + e = _left[e];
1.1317 + }
1.1318 + } else {
1.1319 + if (_right[e] == INVALID) {
1.1320 + _right.set(e, arc);
1.1321 + _parent.set(arc, e);
1.1322 + splay(arc);
1.1323 + return;
1.1324 + } else {
1.1325 + e = _right[e];
1.1326 + }
1.1327 + }
1.1328 + }
1.1329 + }
1.1330 +
1.1331 + void remove(Arc arc) {
1.1332 + if (_left[arc] == INVALID) {
1.1333 + if (_right[arc] != INVALID) {
1.1334 + _parent.set(_right[arc], _parent[arc]);
1.1335 + }
1.1336 + if (_parent[arc] != INVALID) {
1.1337 + if (_left[_parent[arc]] == arc) {
1.1338 + _left.set(_parent[arc], _right[arc]);
1.1339 + } else {
1.1340 + _right.set(_parent[arc], _right[arc]);
1.1341 + }
1.1342 + } else {
1.1343 + _head.set(_g.source(arc), _right[arc]);
1.1344 + }
1.1345 + } else if (_right[arc] == INVALID) {
1.1346 + _parent.set(_left[arc], _parent[arc]);
1.1347 + if (_parent[arc] != INVALID) {
1.1348 + if (_left[_parent[arc]] == arc) {
1.1349 + _left.set(_parent[arc], _left[arc]);
1.1350 + } else {
1.1351 + _right.set(_parent[arc], _left[arc]);
1.1352 + }
1.1353 + } else {
1.1354 + _head.set(_g.source(arc), _left[arc]);
1.1355 + }
1.1356 + } else {
1.1357 + Arc e = _left[arc];
1.1358 + if (_right[e] != INVALID) {
1.1359 + e = _right[e];
1.1360 + while (_right[e] != INVALID) {
1.1361 + e = _right[e];
1.1362 + }
1.1363 + Arc s = _parent[e];
1.1364 + _right.set(_parent[e], _left[e]);
1.1365 + if (_left[e] != INVALID) {
1.1366 + _parent.set(_left[e], _parent[e]);
1.1367 + }
1.1368 +
1.1369 + _left.set(e, _left[arc]);
1.1370 + _parent.set(_left[arc], e);
1.1371 + _right.set(e, _right[arc]);
1.1372 + _parent.set(_right[arc], e);
1.1373 +
1.1374 + _parent.set(e, _parent[arc]);
1.1375 + if (_parent[arc] != INVALID) {
1.1376 + if (_left[_parent[arc]] == arc) {
1.1377 + _left.set(_parent[arc], e);
1.1378 + } else {
1.1379 + _right.set(_parent[arc], e);
1.1380 + }
1.1381 + }
1.1382 + splay(s);
1.1383 + } else {
1.1384 + _right.set(e, _right[arc]);
1.1385 + _parent.set(_right[arc], e);
1.1386 +
1.1387 + if (_parent[arc] != INVALID) {
1.1388 + if (_left[_parent[arc]] == arc) {
1.1389 + _left.set(_parent[arc], e);
1.1390 + } else {
1.1391 + _right.set(_parent[arc], e);
1.1392 + }
1.1393 + } else {
1.1394 + _head.set(_g.source(arc), e);
1.1395 + }
1.1396 + }
1.1397 + }
1.1398 + }
1.1399 +
1.1400 + Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.1401 + {
1.1402 + int m=(a+b)/2;
1.1403 + Arc me=v[m];
1.1404 + if (a < m) {
1.1405 + Arc left = refreshRec(v,a,m-1);
1.1406 + _left.set(me, left);
1.1407 + _parent.set(left, me);
1.1408 + } else {
1.1409 + _left.set(me, INVALID);
1.1410 + }
1.1411 + if (m < b) {
1.1412 + Arc right = refreshRec(v,m+1,b);
1.1413 + _right.set(me, right);
1.1414 + _parent.set(right, me);
1.1415 + } else {
1.1416 + _right.set(me, INVALID);
1.1417 + }
1.1418 + return me;
1.1419 + }
1.1420 +
1.1421 + void refresh() {
1.1422 + for(NodeIt n(_g);n!=INVALID;++n) {
1.1423 + std::vector<Arc> v;
1.1424 + for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.1425 + if(v.size()) {
1.1426 + std::sort(v.begin(),v.end(),ArcLess(_g));
1.1427 + Arc head = refreshRec(v,0,v.size()-1);
1.1428 + _head.set(n, head);
1.1429 + _parent.set(head, INVALID);
1.1430 + }
1.1431 + else _head.set(n, INVALID);
1.1432 + }
1.1433 + }
1.1434 +
1.1435 + void zig(Arc v) {
1.1436 + Arc w = _parent[v];
1.1437 + _parent.set(v, _parent[w]);
1.1438 + _parent.set(w, v);
1.1439 + _left.set(w, _right[v]);
1.1440 + _right.set(v, w);
1.1441 + if (_parent[v] != INVALID) {
1.1442 + if (_right[_parent[v]] == w) {
1.1443 + _right.set(_parent[v], v);
1.1444 + } else {
1.1445 + _left.set(_parent[v], v);
1.1446 + }
1.1447 + }
1.1448 + if (_left[w] != INVALID){
1.1449 + _parent.set(_left[w], w);
1.1450 + }
1.1451 + }
1.1452 +
1.1453 + void zag(Arc v) {
1.1454 + Arc w = _parent[v];
1.1455 + _parent.set(v, _parent[w]);
1.1456 + _parent.set(w, v);
1.1457 + _right.set(w, _left[v]);
1.1458 + _left.set(v, w);
1.1459 + if (_parent[v] != INVALID){
1.1460 + if (_left[_parent[v]] == w) {
1.1461 + _left.set(_parent[v], v);
1.1462 + } else {
1.1463 + _right.set(_parent[v], v);
1.1464 + }
1.1465 + }
1.1466 + if (_right[w] != INVALID){
1.1467 + _parent.set(_right[w], w);
1.1468 + }
1.1469 + }
1.1470 +
1.1471 + void splay(Arc v) {
1.1472 + while (_parent[v] != INVALID) {
1.1473 + if (v == _left[_parent[v]]) {
1.1474 + if (_parent[_parent[v]] == INVALID) {
1.1475 + zig(v);
1.1476 + } else {
1.1477 + if (_parent[v] == _left[_parent[_parent[v]]]) {
1.1478 + zig(_parent[v]);
1.1479 + zig(v);
1.1480 + } else {
1.1481 + zig(v);
1.1482 + zag(v);
1.1483 + }
1.1484 + }
1.1485 + } else {
1.1486 + if (_parent[_parent[v]] == INVALID) {
1.1487 + zag(v);
1.1488 + } else {
1.1489 + if (_parent[v] == _left[_parent[_parent[v]]]) {
1.1490 + zag(v);
1.1491 + zig(v);
1.1492 + } else {
1.1493 + zag(_parent[v]);
1.1494 + zag(v);
1.1495 + }
1.1496 + }
1.1497 + }
1.1498 + }
1.1499 + _head[_g.source(v)] = v;
1.1500 + }
1.1501 +
1.1502 +
1.1503 + public:
1.1504 +
1.1505 + ///Find an arc between two nodes.
1.1506 +
1.1507 + ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.1508 + /// <em>d</em> is the number of outgoing arcs of \c s.
1.1509 + ///\param s The source node
1.1510 + ///\param t The target node
1.1511 + ///\return An arc from \c s to \c t if there exists,
1.1512 + ///\ref INVALID otherwise.
1.1513 + Arc operator()(Node s, Node t) const
1.1514 + {
1.1515 + Arc a = _head[s];
1.1516 + while (true) {
1.1517 + if (_g.target(a) == t) {
1.1518 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1519 + return a;
1.1520 + } else if (t < _g.target(a)) {
1.1521 + if (_left[a] == INVALID) {
1.1522 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1523 + return INVALID;
1.1524 + } else {
1.1525 + a = _left[a];
1.1526 + }
1.1527 + } else {
1.1528 + if (_right[a] == INVALID) {
1.1529 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1530 + return INVALID;
1.1531 + } else {
1.1532 + a = _right[a];
1.1533 + }
1.1534 + }
1.1535 + }
1.1536 + }
1.1537 +
1.1538 + ///Find the first arc between two nodes.
1.1539 +
1.1540 + ///Find the first arc between two nodes in time
1.1541 + /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.1542 + /// outgoing arcs of \c s.
1.1543 + ///\param s The source node
1.1544 + ///\param t The target node
1.1545 + ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.1546 + /// otherwise.
1.1547 + Arc findFirst(Node s, Node t) const
1.1548 + {
1.1549 + Arc a = _head[s];
1.1550 + Arc r = INVALID;
1.1551 + while (true) {
1.1552 + if (_g.target(a) < t) {
1.1553 + if (_right[a] == INVALID) {
1.1554 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1555 + return r;
1.1556 + } else {
1.1557 + a = _right[a];
1.1558 + }
1.1559 + } else {
1.1560 + if (_g.target(a) == t) {
1.1561 + r = a;
1.1562 + }
1.1563 + if (_left[a] == INVALID) {
1.1564 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1565 + return r;
1.1566 + } else {
1.1567 + a = _left[a];
1.1568 + }
1.1569 + }
1.1570 + }
1.1571 + }
1.1572 +
1.1573 + ///Find the next arc between two nodes.
1.1574 +
1.1575 + ///Find the next arc between two nodes in time
1.1576 + /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.1577 + /// outgoing arcs of \c s.
1.1578 + ///\param s The source node
1.1579 + ///\param t The target node
1.1580 + ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.1581 + /// otherwise.
1.1582 +
1.1583 + ///\note If \c e is not the result of the previous \c findFirst()
1.1584 + ///operation then the amorized time bound can not be guaranteed.
1.1585 +#ifdef DOXYGEN
1.1586 + Arc findNext(Node s, Node t, Arc a) const
1.1587 +#else
1.1588 + Arc findNext(Node, Node t, Arc a) const
1.1589 +#endif
1.1590 + {
1.1591 + if (_right[a] != INVALID) {
1.1592 + a = _right[a];
1.1593 + while (_left[a] != INVALID) {
1.1594 + a = _left[a];
1.1595 + }
1.1596 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1597 + } else {
1.1598 + while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.1599 + a = _parent[a];
1.1600 + }
1.1601 + if (_parent[a] == INVALID) {
1.1602 + return INVALID;
1.1603 + } else {
1.1604 + a = _parent[a];
1.1605 + const_cast<DynArcLookUp&>(*this).splay(a);
1.1606 + }
1.1607 + }
1.1608 + if (_g.target(a) == t) return a;
1.1609 + else return INVALID;
1.1610 + }
1.1611 +
1.1612 + };
1.1613 +
1.1614 + ///Fast arc look up between given endpoints.
1.1615 +
1.1616 + ///Using this class, you can find an arc in a digraph from a given
1.1617 + ///source to a given target in time <em>O(log d)</em>,
1.1618 + ///where <em>d</em> is the out-degree of the source node.
1.1619 + ///
1.1620 + ///It is not possible to find \e all parallel arcs between two nodes.
1.1621 + ///Use \ref AllArcLookUp for this purpose.
1.1622 + ///
1.1623 + ///\warning This class is static, so you should refresh() (or at least
1.1624 + ///refresh(Node)) this data structure
1.1625 + ///whenever the digraph changes. This is a time consuming (superlinearly
1.1626 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
1.1627 + ///
1.1628 + ///\tparam G The type of the underlying digraph.
1.1629 + ///
1.1630 + ///\sa DynArcLookUp
1.1631 + ///\sa AllArcLookUp
1.1632 + template<class G>
1.1633 + class ArcLookUp
1.1634 + {
1.1635 + public:
1.1636 + TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.1637 + typedef G Digraph;
1.1638 +
1.1639 + protected:
1.1640 + const Digraph &_g;
1.1641 + typename Digraph::template NodeMap<Arc> _head;
1.1642 + typename Digraph::template ArcMap<Arc> _left;
1.1643 + typename Digraph::template ArcMap<Arc> _right;
1.1644 +
1.1645 + class ArcLess {
1.1646 + const Digraph &g;
1.1647 + public:
1.1648 + ArcLess(const Digraph &_g) : g(_g) {}
1.1649 + bool operator()(Arc a,Arc b) const
1.1650 + {
1.1651 + return g.target(a)<g.target(b);
1.1652 + }
1.1653 + };
1.1654 +
1.1655 + public:
1.1656 +
1.1657 + ///Constructor
1.1658 +
1.1659 + ///Constructor.
1.1660 + ///
1.1661 + ///It builds up the search database, which remains valid until the digraph
1.1662 + ///changes.
1.1663 + ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1.1664 +
1.1665 + private:
1.1666 + Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.1667 + {
1.1668 + int m=(a+b)/2;
1.1669 + Arc me=v[m];
1.1670 + _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1.1671 + _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1.1672 + return me;
1.1673 + }
1.1674 + public:
1.1675 + ///Refresh the data structure at a node.
1.1676 +
1.1677 + ///Build up the search database of node \c n.
1.1678 + ///
1.1679 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.1680 + ///the number of the outgoing arcs of \c n.
1.1681 + void refresh(Node n)
1.1682 + {
1.1683 + std::vector<Arc> v;
1.1684 + for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.1685 + if(v.size()) {
1.1686 + std::sort(v.begin(),v.end(),ArcLess(_g));
1.1687 + _head[n]=refreshRec(v,0,v.size()-1);
1.1688 + }
1.1689 + else _head[n]=INVALID;
1.1690 + }
1.1691 + ///Refresh the full data structure.
1.1692 +
1.1693 + ///Build up the full search database. In fact, it simply calls
1.1694 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.1695 + ///
1.1696 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.1697 + ///the number of the arcs of \c n and <em>D</em> is the maximum
1.1698 + ///out-degree of the digraph.
1.1699 +
1.1700 + void refresh()
1.1701 + {
1.1702 + for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.1703 + }
1.1704 +
1.1705 + ///Find an arc between two nodes.
1.1706 +
1.1707 + ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.1708 + /// <em>d</em> is the number of outgoing arcs of \c s.
1.1709 + ///\param s The source node
1.1710 + ///\param t The target node
1.1711 + ///\return An arc from \c s to \c t if there exists,
1.1712 + ///\ref INVALID otherwise.
1.1713 + ///
1.1714 + ///\warning If you change the digraph, refresh() must be called before using
1.1715 + ///this operator. If you change the outgoing arcs of
1.1716 + ///a single node \c n, then
1.1717 + ///\ref refresh(Node) "refresh(n)" is enough.
1.1718 + ///
1.1719 + Arc operator()(Node s, Node t) const
1.1720 + {
1.1721 + Arc e;
1.1722 + for(e=_head[s];
1.1723 + e!=INVALID&&_g.target(e)!=t;
1.1724 + e = t < _g.target(e)?_left[e]:_right[e]) ;
1.1725 + return e;
1.1726 + }
1.1727 +
1.1728 + };
1.1729 +
1.1730 + ///Fast look up of all arcs between given endpoints.
1.1731 +
1.1732 + ///This class is the same as \ref ArcLookUp, with the addition
1.1733 + ///that it makes it possible to find all arcs between given endpoints.
1.1734 + ///
1.1735 + ///\warning This class is static, so you should refresh() (or at least
1.1736 + ///refresh(Node)) this data structure
1.1737 + ///whenever the digraph changes. This is a time consuming (superlinearly
1.1738 + ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
1.1739 + ///
1.1740 + ///\tparam G The type of the underlying digraph.
1.1741 + ///
1.1742 + ///\sa DynArcLookUp
1.1743 + ///\sa ArcLookUp
1.1744 + template<class G>
1.1745 + class AllArcLookUp : public ArcLookUp<G>
1.1746 + {
1.1747 + using ArcLookUp<G>::_g;
1.1748 + using ArcLookUp<G>::_right;
1.1749 + using ArcLookUp<G>::_left;
1.1750 + using ArcLookUp<G>::_head;
1.1751 +
1.1752 + TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.1753 + typedef G Digraph;
1.1754 +
1.1755 + typename Digraph::template ArcMap<Arc> _next;
1.1756 +
1.1757 + Arc refreshNext(Arc head,Arc next=INVALID)
1.1758 + {
1.1759 + if(head==INVALID) return next;
1.1760 + else {
1.1761 + next=refreshNext(_right[head],next);
1.1762 +// _next[head]=next;
1.1763 + _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1.1764 + ? next : INVALID;
1.1765 + return refreshNext(_left[head],head);
1.1766 + }
1.1767 + }
1.1768 +
1.1769 + void refreshNext()
1.1770 + {
1.1771 + for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1.1772 + }
1.1773 +
1.1774 + public:
1.1775 + ///Constructor
1.1776 +
1.1777 + ///Constructor.
1.1778 + ///
1.1779 + ///It builds up the search database, which remains valid until the digraph
1.1780 + ///changes.
1.1781 + AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
1.1782 +
1.1783 + ///Refresh the data structure at a node.
1.1784 +
1.1785 + ///Build up the search database of node \c n.
1.1786 + ///
1.1787 + ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.1788 + ///the number of the outgoing arcs of \c n.
1.1789 +
1.1790 + void refresh(Node n)
1.1791 + {
1.1792 + ArcLookUp<G>::refresh(n);
1.1793 + refreshNext(_head[n]);
1.1794 + }
1.1795 +
1.1796 + ///Refresh the full data structure.
1.1797 +
1.1798 + ///Build up the full search database. In fact, it simply calls
1.1799 + ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.1800 + ///
1.1801 + ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.1802 + ///the number of the arcs of \c n and <em>D</em> is the maximum
1.1803 + ///out-degree of the digraph.
1.1804 +
1.1805 + void refresh()
1.1806 + {
1.1807 + for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1.1808 + }
1.1809 +
1.1810 + ///Find an arc between two nodes.
1.1811 +
1.1812 + ///Find an arc between two nodes.
1.1813 + ///\param s The source node
1.1814 + ///\param t The target node
1.1815 + ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1.1816 + ///not given, the operator finds the first appropriate arc.
1.1817 + ///\return An arc from \c s to \c t after \c prev or
1.1818 + ///\ref INVALID if there is no more.
1.1819 + ///
1.1820 + ///For example, you can count the number of arcs from \c u to \c v in the
1.1821 + ///following way.
1.1822 + ///\code
1.1823 + ///AllArcLookUp<ListDigraph> ae(g);
1.1824 + ///...
1.1825 + ///int n=0;
1.1826 + ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
1.1827 + ///\endcode
1.1828 + ///
1.1829 + ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
1.1830 + /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
1.1831 + ///consecutive arcs are found in constant time.
1.1832 + ///
1.1833 + ///\warning If you change the digraph, refresh() must be called before using
1.1834 + ///this operator. If you change the outgoing arcs of
1.1835 + ///a single node \c n, then
1.1836 + ///\ref refresh(Node) "refresh(n)" is enough.
1.1837 + ///
1.1838 +#ifdef DOXYGEN
1.1839 + Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1.1840 +#else
1.1841 + using ArcLookUp<G>::operator() ;
1.1842 + Arc operator()(Node s, Node t, Arc prev) const
1.1843 + {
1.1844 + return prev==INVALID?(*this)(s,t):_next[prev];
1.1845 + }
1.1846 +#endif
1.1847 +
1.1848 + };
1.1849 +
1.1850 + /// @}
1.1851 +
1.1852 +} //namespace lemon
1.1853 +
1.1854 +#endif