Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2010
6 : : * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 : : * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 : : *
9 : : * Permission to use, modify and distribute this software is granted
10 : : * provided that this copyright notice appears in all copies. For
11 : : * precise terms see the accompanying LICENSE file.
12 : : *
13 : : * This software is provided "AS IS" with no warranty of any kind,
14 : : * express or implied, and with no claim as to its suitability for any
15 : : * purpose.
16 : : *
17 : : */
18 : :
19 : : #ifndef LEMON_CORE_H
20 : : #define LEMON_CORE_H
21 : :
22 : : #include <vector>
23 : : #include <algorithm>
24 : :
25 : : #include <lemon/config.h>
26 : : #include <lemon/bits/enable_if.h>
27 : : #include <lemon/bits/traits.h>
28 : : #include <lemon/assert.h>
29 : :
30 : : // Disable the following warnings when compiling with MSVC:
31 : : // C4250: 'class1' : inherits 'class2::member' via dominance
32 : : // C4355: 'this' : used in base member initializer list
33 : : // C4503: 'function' : decorated name length exceeded, name was truncated
34 : : // C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
35 : : // C4996: 'function': was declared deprecated
36 : : #ifdef _MSC_VER
37 : : #pragma warning( disable : 4250 4355 4503 4800 4996 )
38 : : #endif
39 : :
40 : : ///\file
41 : : ///\brief LEMON core utilities.
42 : : ///
43 : : ///This header file contains core utilities for LEMON.
44 : : ///It is automatically included by all graph types, therefore it usually
45 : : ///do not have to be included directly.
46 : :
47 : : namespace lemon {
48 : :
49 : : /// \brief Dummy type to make it easier to create invalid iterators.
50 : : ///
51 : : /// Dummy type to make it easier to create invalid iterators.
52 : : /// See \ref INVALID for the usage.
53 : : struct Invalid {
54 : : public:
55 : : bool operator==(Invalid) { return true; }
56 : : bool operator!=(Invalid) { return false; }
57 : : bool operator< (Invalid) { return false; }
58 : : };
59 : :
60 : : /// \brief Invalid iterators.
61 : : ///
62 : : /// \ref Invalid is a global type that converts to each iterator
63 : : /// in such a way that the value of the target iterator will be invalid.
64 : : #ifdef LEMON_ONLY_TEMPLATES
65 : : const Invalid INVALID = Invalid();
66 : : #else
67 : : extern const Invalid INVALID;
68 : : #endif
69 : :
70 : : /// \addtogroup gutils
71 : : /// @{
72 : :
73 : : ///Create convenience typedefs for the digraph types and iterators
74 : :
75 : : ///This \c \#define creates convenient type definitions for the following
76 : : ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
77 : : ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
78 : : ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
79 : : ///
80 : : ///\note If the graph type is a dependent type, ie. the graph type depend
81 : : ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
82 : : ///macro.
83 : : #define DIGRAPH_TYPEDEFS(Digraph) \
84 : : typedef Digraph::Node Node; \
85 : : typedef Digraph::NodeIt NodeIt; \
86 : : typedef Digraph::Arc Arc; \
87 : : typedef Digraph::ArcIt ArcIt; \
88 : : typedef Digraph::InArcIt InArcIt; \
89 : : typedef Digraph::OutArcIt OutArcIt; \
90 : : typedef Digraph::NodeMap<bool> BoolNodeMap; \
91 : : typedef Digraph::NodeMap<int> IntNodeMap; \
92 : : typedef Digraph::NodeMap<double> DoubleNodeMap; \
93 : : typedef Digraph::ArcMap<bool> BoolArcMap; \
94 : : typedef Digraph::ArcMap<int> IntArcMap; \
95 : : typedef Digraph::ArcMap<double> DoubleArcMap
96 : :
97 : : ///Create convenience typedefs for the digraph types and iterators
98 : :
99 : : ///\see DIGRAPH_TYPEDEFS
100 : : ///
101 : : ///\note Use this macro, if the graph type is a dependent type,
102 : : ///ie. the graph type depend on a template parameter.
103 : : #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
104 : : typedef typename Digraph::Node Node; \
105 : : typedef typename Digraph::NodeIt NodeIt; \
106 : : typedef typename Digraph::Arc Arc; \
107 : : typedef typename Digraph::ArcIt ArcIt; \
108 : : typedef typename Digraph::InArcIt InArcIt; \
109 : : typedef typename Digraph::OutArcIt OutArcIt; \
110 : : typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
111 : : typedef typename Digraph::template NodeMap<int> IntNodeMap; \
112 : : typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
113 : : typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
114 : : typedef typename Digraph::template ArcMap<int> IntArcMap; \
115 : : typedef typename Digraph::template ArcMap<double> DoubleArcMap
116 : :
117 : : ///Create convenience typedefs for the graph types and iterators
118 : :
119 : : ///This \c \#define creates the same convenient type definitions as defined
120 : : ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
121 : : ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
122 : : ///\c DoubleEdgeMap.
123 : : ///
124 : : ///\note If the graph type is a dependent type, ie. the graph type depend
125 : : ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
126 : : ///macro.
127 : : #define GRAPH_TYPEDEFS(Graph) \
128 : : DIGRAPH_TYPEDEFS(Graph); \
129 : : typedef Graph::Edge Edge; \
130 : : typedef Graph::EdgeIt EdgeIt; \
131 : : typedef Graph::IncEdgeIt IncEdgeIt; \
132 : : typedef Graph::EdgeMap<bool> BoolEdgeMap; \
133 : : typedef Graph::EdgeMap<int> IntEdgeMap; \
134 : : typedef Graph::EdgeMap<double> DoubleEdgeMap
135 : :
136 : : ///Create convenience typedefs for the graph types and iterators
137 : :
138 : : ///\see GRAPH_TYPEDEFS
139 : : ///
140 : : ///\note Use this macro, if the graph type is a dependent type,
141 : : ///ie. the graph type depend on a template parameter.
142 : : #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
143 : : TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
144 : : typedef typename Graph::Edge Edge; \
145 : : typedef typename Graph::EdgeIt EdgeIt; \
146 : : typedef typename Graph::IncEdgeIt IncEdgeIt; \
147 : : typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
148 : : typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
149 : : typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
150 : :
151 : : /// \brief Function to count the items in a graph.
152 : : ///
153 : : /// This function counts the items (nodes, arcs etc.) in a graph.
154 : : /// The complexity of the function is linear because
155 : : /// it iterates on all of the items.
156 : : template <typename Graph, typename Item>
157 : 371 : inline int countItems(const Graph& g) {
158 : : typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
159 : 371 : int num = 0;
160 [ + - ][ + - ]: 2412 : for (ItemIt it(g); it != INVALID; ++it) {
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
161 : 2041 : ++num;
162 : : }
163 : 371 : return num;
164 : : }
165 : :
166 : : // Node counting:
167 : :
168 : : namespace _core_bits {
169 : :
170 : : template <typename Graph, typename Enable = void>
171 : : struct CountNodesSelector {
172 : 371 : static int count(const Graph &g) {
173 : 371 : return countItems<Graph, typename Graph::Node>(g);
174 : : }
175 : : };
176 : :
177 : : template <typename Graph>
178 : : struct CountNodesSelector<
179 : : Graph, typename
180 : : enable_if<typename Graph::NodeNumTag, void>::type>
181 : : {
182 : : static int count(const Graph &g) {
183 : : return g.nodeNum();
184 : : }
185 : : };
186 : : }
187 : :
188 : : /// \brief Function to count the nodes in the graph.
189 : : ///
190 : : /// This function counts the nodes in the graph.
191 : : /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
192 : : /// graph structures it is specialized to run in <em>O</em>(1).
193 : : ///
194 : : /// \note If the graph contains a \c nodeNum() member function and a
195 : : /// \c NodeNumTag tag then this function calls directly the member
196 : : /// function to query the cardinality of the node set.
197 : : template <typename Graph>
198 : 371 : inline int countNodes(const Graph& g) {
199 : 371 : return _core_bits::CountNodesSelector<Graph>::count(g);
200 : : }
201 : :
202 : : // Arc counting:
203 : :
204 : : namespace _core_bits {
205 : :
206 : : template <typename Graph, typename Enable = void>
207 : : struct CountArcsSelector {
208 : : static int count(const Graph &g) {
209 : : return countItems<Graph, typename Graph::Arc>(g);
210 : : }
211 : : };
212 : :
213 : : template <typename Graph>
214 : : struct CountArcsSelector<
215 : : Graph,
216 : : typename enable_if<typename Graph::ArcNumTag, void>::type>
217 : : {
218 : : static int count(const Graph &g) {
219 : : return g.arcNum();
220 : : }
221 : : };
222 : : }
223 : :
224 : : /// \brief Function to count the arcs in the graph.
225 : : ///
226 : : /// This function counts the arcs in the graph.
227 : : /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
228 : : /// graph structures it is specialized to run in <em>O</em>(1).
229 : : ///
230 : : /// \note If the graph contains a \c arcNum() member function and a
231 : : /// \c ArcNumTag tag then this function calls directly the member
232 : : /// function to query the cardinality of the arc set.
233 : : template <typename Graph>
234 : : inline int countArcs(const Graph& g) {
235 : : return _core_bits::CountArcsSelector<Graph>::count(g);
236 : : }
237 : :
238 : : // Edge counting:
239 : :
240 : : namespace _core_bits {
241 : :
242 : : template <typename Graph, typename Enable = void>
243 : : struct CountEdgesSelector {
244 : : static int count(const Graph &g) {
245 : : return countItems<Graph, typename Graph::Edge>(g);
246 : : }
247 : : };
248 : :
249 : : template <typename Graph>
250 : : struct CountEdgesSelector<
251 : : Graph,
252 : : typename enable_if<typename Graph::EdgeNumTag, void>::type>
253 : : {
254 : : static int count(const Graph &g) {
255 : : return g.edgeNum();
256 : : }
257 : : };
258 : : }
259 : :
260 : : /// \brief Function to count the edges in the graph.
261 : : ///
262 : : /// This function counts the edges in the graph.
263 : : /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
264 : : /// graph structures it is specialized to run in <em>O</em>(1).
265 : : ///
266 : : /// \note If the graph contains a \c edgeNum() member function and a
267 : : /// \c EdgeNumTag tag then this function calls directly the member
268 : : /// function to query the cardinality of the edge set.
269 : : template <typename Graph>
270 : : inline int countEdges(const Graph& g) {
271 : : return _core_bits::CountEdgesSelector<Graph>::count(g);
272 : :
273 : : }
274 : :
275 : :
276 : : template <typename Graph, typename DegIt>
277 : : inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
278 : : int num = 0;
279 : : for (DegIt it(_g, _n); it != INVALID; ++it) {
280 : : ++num;
281 : : }
282 : : return num;
283 : : }
284 : :
285 : : /// \brief Function to count the number of the out-arcs from node \c n.
286 : : ///
287 : : /// This function counts the number of the out-arcs from node \c n
288 : : /// in the graph \c g.
289 : : template <typename Graph>
290 : : inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
291 : : return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
292 : : }
293 : :
294 : : /// \brief Function to count the number of the in-arcs to node \c n.
295 : : ///
296 : : /// This function counts the number of the in-arcs to node \c n
297 : : /// in the graph \c g.
298 : : template <typename Graph>
299 : : inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
300 : : return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
301 : : }
302 : :
303 : : /// \brief Function to count the number of the inc-edges to node \c n.
304 : : ///
305 : : /// This function counts the number of the inc-edges to node \c n
306 : : /// in the undirected graph \c g.
307 : : template <typename Graph>
308 : : inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
309 : : return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
310 : : }
311 : :
312 : : namespace _core_bits {
313 : :
314 : : template <typename Digraph, typename Item, typename RefMap>
315 : : class MapCopyBase {
316 : : public:
317 : : virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
318 : :
319 : : virtual ~MapCopyBase() {}
320 : : };
321 : :
322 : : template <typename Digraph, typename Item, typename RefMap,
323 : : typename FromMap, typename ToMap>
324 : : class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
325 : : public:
326 : :
327 : : MapCopy(const FromMap& map, ToMap& tmap)
328 : : : _map(map), _tmap(tmap) {}
329 : :
330 : : virtual void copy(const Digraph& digraph, const RefMap& refMap) {
331 : : typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
332 : : for (ItemIt it(digraph); it != INVALID; ++it) {
333 : : _tmap.set(refMap[it], _map[it]);
334 : : }
335 : : }
336 : :
337 : : private:
338 : : const FromMap& _map;
339 : : ToMap& _tmap;
340 : : };
341 : :
342 : : template <typename Digraph, typename Item, typename RefMap, typename It>
343 : : class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
344 : : public:
345 : :
346 : : ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
347 : :
348 : : virtual void copy(const Digraph&, const RefMap& refMap) {
349 : : _it = refMap[_item];
350 : : }
351 : :
352 : : private:
353 : : Item _item;
354 : : It& _it;
355 : : };
356 : :
357 : : template <typename Digraph, typename Item, typename RefMap, typename Ref>
358 : : class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
359 : : public:
360 : :
361 : : RefCopy(Ref& map) : _map(map) {}
362 : :
363 : : virtual void copy(const Digraph& digraph, const RefMap& refMap) {
364 : : typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
365 : : for (ItemIt it(digraph); it != INVALID; ++it) {
366 : : _map.set(it, refMap[it]);
367 : : }
368 : : }
369 : :
370 : : private:
371 : : Ref& _map;
372 : : };
373 : :
374 : : template <typename Digraph, typename Item, typename RefMap,
375 : : typename CrossRef>
376 : : class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
377 : : public:
378 : :
379 : : CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
380 : :
381 : : virtual void copy(const Digraph& digraph, const RefMap& refMap) {
382 : : typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
383 : : for (ItemIt it(digraph); it != INVALID; ++it) {
384 : : _cmap.set(refMap[it], it);
385 : : }
386 : : }
387 : :
388 : : private:
389 : : CrossRef& _cmap;
390 : : };
391 : :
392 : : template <typename Digraph, typename Enable = void>
393 : : struct DigraphCopySelector {
394 : : template <typename From, typename NodeRefMap, typename ArcRefMap>
395 : : static void copy(const From& from, Digraph &to,
396 : : NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
397 : : to.clear();
398 : : for (typename From::NodeIt it(from); it != INVALID; ++it) {
399 : : nodeRefMap[it] = to.addNode();
400 : : }
401 : : for (typename From::ArcIt it(from); it != INVALID; ++it) {
402 : : arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
403 : : nodeRefMap[from.target(it)]);
404 : : }
405 : : }
406 : : };
407 : :
408 : : template <typename Digraph>
409 : : struct DigraphCopySelector<
410 : : Digraph,
411 : : typename enable_if<typename Digraph::BuildTag, void>::type>
412 : : {
413 : : template <typename From, typename NodeRefMap, typename ArcRefMap>
414 : : static void copy(const From& from, Digraph &to,
415 : : NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
416 : : to.build(from, nodeRefMap, arcRefMap);
417 : : }
418 : : };
419 : :
420 : : template <typename Graph, typename Enable = void>
421 : : struct GraphCopySelector {
422 : : template <typename From, typename NodeRefMap, typename EdgeRefMap>
423 : : static void copy(const From& from, Graph &to,
424 : : NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
425 : : to.clear();
426 : : for (typename From::NodeIt it(from); it != INVALID; ++it) {
427 : : nodeRefMap[it] = to.addNode();
428 : : }
429 : : for (typename From::EdgeIt it(from); it != INVALID; ++it) {
430 : : edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
431 : : nodeRefMap[from.v(it)]);
432 : : }
433 : : }
434 : : };
435 : :
436 : : template <typename Graph>
437 : : struct GraphCopySelector<
438 : : Graph,
439 : : typename enable_if<typename Graph::BuildTag, void>::type>
440 : : {
441 : : template <typename From, typename NodeRefMap, typename EdgeRefMap>
442 : : static void copy(const From& from, Graph &to,
443 : : NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
444 : : to.build(from, nodeRefMap, edgeRefMap);
445 : : }
446 : : };
447 : :
448 : : }
449 : :
450 : : /// \brief Class to copy a digraph.
451 : : ///
452 : : /// Class to copy a digraph to another digraph (duplicate a digraph). The
453 : : /// simplest way of using it is through the \c digraphCopy() function.
454 : : ///
455 : : /// This class not only make a copy of a digraph, but it can create
456 : : /// references and cross references between the nodes and arcs of
457 : : /// the two digraphs, and it can copy maps to use with the newly created
458 : : /// digraph.
459 : : ///
460 : : /// To make a copy from a digraph, first an instance of DigraphCopy
461 : : /// should be created, then the data belongs to the digraph should
462 : : /// assigned to copy. In the end, the \c run() member should be
463 : : /// called.
464 : : ///
465 : : /// The next code copies a digraph with several data:
466 : : ///\code
467 : : /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
468 : : /// // Create references for the nodes
469 : : /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
470 : : /// cg.nodeRef(nr);
471 : : /// // Create cross references (inverse) for the arcs
472 : : /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
473 : : /// cg.arcCrossRef(acr);
474 : : /// // Copy an arc map
475 : : /// OrigGraph::ArcMap<double> oamap(orig_graph);
476 : : /// NewGraph::ArcMap<double> namap(new_graph);
477 : : /// cg.arcMap(oamap, namap);
478 : : /// // Copy a node
479 : : /// OrigGraph::Node on;
480 : : /// NewGraph::Node nn;
481 : : /// cg.node(on, nn);
482 : : /// // Execute copying
483 : : /// cg.run();
484 : : ///\endcode
485 : : template <typename From, typename To>
486 : : class DigraphCopy {
487 : : private:
488 : :
489 : : typedef typename From::Node Node;
490 : : typedef typename From::NodeIt NodeIt;
491 : : typedef typename From::Arc Arc;
492 : : typedef typename From::ArcIt ArcIt;
493 : :
494 : : typedef typename To::Node TNode;
495 : : typedef typename To::Arc TArc;
496 : :
497 : : typedef typename From::template NodeMap<TNode> NodeRefMap;
498 : : typedef typename From::template ArcMap<TArc> ArcRefMap;
499 : :
500 : : public:
501 : :
502 : : /// \brief Constructor of DigraphCopy.
503 : : ///
504 : : /// Constructor of DigraphCopy for copying the content of the
505 : : /// \c from digraph into the \c to digraph.
506 : : DigraphCopy(const From& from, To& to)
507 : : : _from(from), _to(to) {}
508 : :
509 : : /// \brief Destructor of DigraphCopy
510 : : ///
511 : : /// Destructor of DigraphCopy.
512 : : ~DigraphCopy() {
513 : : for (int i = 0; i < int(_node_maps.size()); ++i) {
514 : : delete _node_maps[i];
515 : : }
516 : : for (int i = 0; i < int(_arc_maps.size()); ++i) {
517 : : delete _arc_maps[i];
518 : : }
519 : :
520 : : }
521 : :
522 : : /// \brief Copy the node references into the given map.
523 : : ///
524 : : /// This function copies the node references into the given map.
525 : : /// The parameter should be a map, whose key type is the Node type of
526 : : /// the source digraph, while the value type is the Node type of the
527 : : /// destination digraph.
528 : : template <typename NodeRef>
529 : : DigraphCopy& nodeRef(NodeRef& map) {
530 : : _node_maps.push_back(new _core_bits::RefCopy<From, Node,
531 : : NodeRefMap, NodeRef>(map));
532 : : return *this;
533 : : }
534 : :
535 : : /// \brief Copy the node cross references into the given map.
536 : : ///
537 : : /// This function copies the node cross references (reverse references)
538 : : /// into the given map. The parameter should be a map, whose key type
539 : : /// is the Node type of the destination digraph, while the value type is
540 : : /// the Node type of the source digraph.
541 : : template <typename NodeCrossRef>
542 : : DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
543 : : _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
544 : : NodeRefMap, NodeCrossRef>(map));
545 : : return *this;
546 : : }
547 : :
548 : : /// \brief Make a copy of the given node map.
549 : : ///
550 : : /// This function makes a copy of the given node map for the newly
551 : : /// created digraph.
552 : : /// The key type of the new map \c tmap should be the Node type of the
553 : : /// destination digraph, and the key type of the original map \c map
554 : : /// should be the Node type of the source digraph.
555 : : template <typename FromMap, typename ToMap>
556 : : DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
557 : : _node_maps.push_back(new _core_bits::MapCopy<From, Node,
558 : : NodeRefMap, FromMap, ToMap>(map, tmap));
559 : : return *this;
560 : : }
561 : :
562 : : /// \brief Make a copy of the given node.
563 : : ///
564 : : /// This function makes a copy of the given node.
565 : : DigraphCopy& node(const Node& node, TNode& tnode) {
566 : : _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
567 : : NodeRefMap, TNode>(node, tnode));
568 : : return *this;
569 : : }
570 : :
571 : : /// \brief Copy the arc references into the given map.
572 : : ///
573 : : /// This function copies the arc references into the given map.
574 : : /// The parameter should be a map, whose key type is the Arc type of
575 : : /// the source digraph, while the value type is the Arc type of the
576 : : /// destination digraph.
577 : : template <typename ArcRef>
578 : : DigraphCopy& arcRef(ArcRef& map) {
579 : : _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
580 : : ArcRefMap, ArcRef>(map));
581 : : return *this;
582 : : }
583 : :
584 : : /// \brief Copy the arc cross references into the given map.
585 : : ///
586 : : /// This function copies the arc cross references (reverse references)
587 : : /// into the given map. The parameter should be a map, whose key type
588 : : /// is the Arc type of the destination digraph, while the value type is
589 : : /// the Arc type of the source digraph.
590 : : template <typename ArcCrossRef>
591 : : DigraphCopy& arcCrossRef(ArcCrossRef& map) {
592 : : _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
593 : : ArcRefMap, ArcCrossRef>(map));
594 : : return *this;
595 : : }
596 : :
597 : : /// \brief Make a copy of the given arc map.
598 : : ///
599 : : /// This function makes a copy of the given arc map for the newly
600 : : /// created digraph.
601 : : /// The key type of the new map \c tmap should be the Arc type of the
602 : : /// destination digraph, and the key type of the original map \c map
603 : : /// should be the Arc type of the source digraph.
604 : : template <typename FromMap, typename ToMap>
605 : : DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
606 : : _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
607 : : ArcRefMap, FromMap, ToMap>(map, tmap));
608 : : return *this;
609 : : }
610 : :
611 : : /// \brief Make a copy of the given arc.
612 : : ///
613 : : /// This function makes a copy of the given arc.
614 : : DigraphCopy& arc(const Arc& arc, TArc& tarc) {
615 : : _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
616 : : ArcRefMap, TArc>(arc, tarc));
617 : : return *this;
618 : : }
619 : :
620 : : /// \brief Execute copying.
621 : : ///
622 : : /// This function executes the copying of the digraph along with the
623 : : /// copying of the assigned data.
624 : : void run() {
625 : : NodeRefMap nodeRefMap(_from);
626 : : ArcRefMap arcRefMap(_from);
627 : : _core_bits::DigraphCopySelector<To>::
628 : : copy(_from, _to, nodeRefMap, arcRefMap);
629 : : for (int i = 0; i < int(_node_maps.size()); ++i) {
630 : : _node_maps[i]->copy(_from, nodeRefMap);
631 : : }
632 : : for (int i = 0; i < int(_arc_maps.size()); ++i) {
633 : : _arc_maps[i]->copy(_from, arcRefMap);
634 : : }
635 : : }
636 : :
637 : : protected:
638 : :
639 : : const From& _from;
640 : : To& _to;
641 : :
642 : : std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
643 : : _node_maps;
644 : :
645 : : std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
646 : : _arc_maps;
647 : :
648 : : };
649 : :
650 : : /// \brief Copy a digraph to another digraph.
651 : : ///
652 : : /// This function copies a digraph to another digraph.
653 : : /// The complete usage of it is detailed in the DigraphCopy class, but
654 : : /// a short example shows a basic work:
655 : : ///\code
656 : : /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
657 : : ///\endcode
658 : : ///
659 : : /// After the copy the \c nr map will contain the mapping from the
660 : : /// nodes of the \c from digraph to the nodes of the \c to digraph and
661 : : /// \c acr will contain the mapping from the arcs of the \c to digraph
662 : : /// to the arcs of the \c from digraph.
663 : : ///
664 : : /// \see DigraphCopy
665 : : template <typename From, typename To>
666 : : DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
667 : : return DigraphCopy<From, To>(from, to);
668 : : }
669 : :
670 : : /// \brief Class to copy a graph.
671 : : ///
672 : : /// Class to copy a graph to another graph (duplicate a graph). The
673 : : /// simplest way of using it is through the \c graphCopy() function.
674 : : ///
675 : : /// This class not only make a copy of a graph, but it can create
676 : : /// references and cross references between the nodes, edges and arcs of
677 : : /// the two graphs, and it can copy maps for using with the newly created
678 : : /// graph.
679 : : ///
680 : : /// To make a copy from a graph, first an instance of GraphCopy
681 : : /// should be created, then the data belongs to the graph should
682 : : /// assigned to copy. In the end, the \c run() member should be
683 : : /// called.
684 : : ///
685 : : /// The next code copies a graph with several data:
686 : : ///\code
687 : : /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
688 : : /// // Create references for the nodes
689 : : /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
690 : : /// cg.nodeRef(nr);
691 : : /// // Create cross references (inverse) for the edges
692 : : /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
693 : : /// cg.edgeCrossRef(ecr);
694 : : /// // Copy an edge map
695 : : /// OrigGraph::EdgeMap<double> oemap(orig_graph);
696 : : /// NewGraph::EdgeMap<double> nemap(new_graph);
697 : : /// cg.edgeMap(oemap, nemap);
698 : : /// // Copy a node
699 : : /// OrigGraph::Node on;
700 : : /// NewGraph::Node nn;
701 : : /// cg.node(on, nn);
702 : : /// // Execute copying
703 : : /// cg.run();
704 : : ///\endcode
705 : : template <typename From, typename To>
706 : : class GraphCopy {
707 : : private:
708 : :
709 : : typedef typename From::Node Node;
710 : : typedef typename From::NodeIt NodeIt;
711 : : typedef typename From::Arc Arc;
712 : : typedef typename From::ArcIt ArcIt;
713 : : typedef typename From::Edge Edge;
714 : : typedef typename From::EdgeIt EdgeIt;
715 : :
716 : : typedef typename To::Node TNode;
717 : : typedef typename To::Arc TArc;
718 : : typedef typename To::Edge TEdge;
719 : :
720 : : typedef typename From::template NodeMap<TNode> NodeRefMap;
721 : : typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
722 : :
723 : : struct ArcRefMap {
724 : : ArcRefMap(const From& from, const To& to,
725 : : const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
726 : : : _from(from), _to(to),
727 : : _edge_ref(edge_ref), _node_ref(node_ref) {}
728 : :
729 : : typedef typename From::Arc Key;
730 : : typedef typename To::Arc Value;
731 : :
732 : : Value operator[](const Key& key) const {
733 : : bool forward = _from.u(key) != _from.v(key) ?
734 : : _node_ref[_from.source(key)] ==
735 : : _to.source(_to.direct(_edge_ref[key], true)) :
736 : : _from.direction(key);
737 : : return _to.direct(_edge_ref[key], forward);
738 : : }
739 : :
740 : : const From& _from;
741 : : const To& _to;
742 : : const EdgeRefMap& _edge_ref;
743 : : const NodeRefMap& _node_ref;
744 : : };
745 : :
746 : : public:
747 : :
748 : : /// \brief Constructor of GraphCopy.
749 : : ///
750 : : /// Constructor of GraphCopy for copying the content of the
751 : : /// \c from graph into the \c to graph.
752 : : GraphCopy(const From& from, To& to)
753 : : : _from(from), _to(to) {}
754 : :
755 : : /// \brief Destructor of GraphCopy
756 : : ///
757 : : /// Destructor of GraphCopy.
758 : : ~GraphCopy() {
759 : : for (int i = 0; i < int(_node_maps.size()); ++i) {
760 : : delete _node_maps[i];
761 : : }
762 : : for (int i = 0; i < int(_arc_maps.size()); ++i) {
763 : : delete _arc_maps[i];
764 : : }
765 : : for (int i = 0; i < int(_edge_maps.size()); ++i) {
766 : : delete _edge_maps[i];
767 : : }
768 : : }
769 : :
770 : : /// \brief Copy the node references into the given map.
771 : : ///
772 : : /// This function copies the node references into the given map.
773 : : /// The parameter should be a map, whose key type is the Node type of
774 : : /// the source graph, while the value type is the Node type of the
775 : : /// destination graph.
776 : : template <typename NodeRef>
777 : : GraphCopy& nodeRef(NodeRef& map) {
778 : : _node_maps.push_back(new _core_bits::RefCopy<From, Node,
779 : : NodeRefMap, NodeRef>(map));
780 : : return *this;
781 : : }
782 : :
783 : : /// \brief Copy the node cross references into the given map.
784 : : ///
785 : : /// This function copies the node cross references (reverse references)
786 : : /// into the given map. The parameter should be a map, whose key type
787 : : /// is the Node type of the destination graph, while the value type is
788 : : /// the Node type of the source graph.
789 : : template <typename NodeCrossRef>
790 : : GraphCopy& nodeCrossRef(NodeCrossRef& map) {
791 : : _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
792 : : NodeRefMap, NodeCrossRef>(map));
793 : : return *this;
794 : : }
795 : :
796 : : /// \brief Make a copy of the given node map.
797 : : ///
798 : : /// This function makes a copy of the given node map for the newly
799 : : /// created graph.
800 : : /// The key type of the new map \c tmap should be the Node type of the
801 : : /// destination graph, and the key type of the original map \c map
802 : : /// should be the Node type of the source graph.
803 : : template <typename FromMap, typename ToMap>
804 : : GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
805 : : _node_maps.push_back(new _core_bits::MapCopy<From, Node,
806 : : NodeRefMap, FromMap, ToMap>(map, tmap));
807 : : return *this;
808 : : }
809 : :
810 : : /// \brief Make a copy of the given node.
811 : : ///
812 : : /// This function makes a copy of the given node.
813 : : GraphCopy& node(const Node& node, TNode& tnode) {
814 : : _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
815 : : NodeRefMap, TNode>(node, tnode));
816 : : return *this;
817 : : }
818 : :
819 : : /// \brief Copy the arc references into the given map.
820 : : ///
821 : : /// This function copies the arc references into the given map.
822 : : /// The parameter should be a map, whose key type is the Arc type of
823 : : /// the source graph, while the value type is the Arc type of the
824 : : /// destination graph.
825 : : template <typename ArcRef>
826 : : GraphCopy& arcRef(ArcRef& map) {
827 : : _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
828 : : ArcRefMap, ArcRef>(map));
829 : : return *this;
830 : : }
831 : :
832 : : /// \brief Copy the arc cross references into the given map.
833 : : ///
834 : : /// This function copies the arc cross references (reverse references)
835 : : /// into the given map. The parameter should be a map, whose key type
836 : : /// is the Arc type of the destination graph, while the value type is
837 : : /// the Arc type of the source graph.
838 : : template <typename ArcCrossRef>
839 : : GraphCopy& arcCrossRef(ArcCrossRef& map) {
840 : : _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
841 : : ArcRefMap, ArcCrossRef>(map));
842 : : return *this;
843 : : }
844 : :
845 : : /// \brief Make a copy of the given arc map.
846 : : ///
847 : : /// This function makes a copy of the given arc map for the newly
848 : : /// created graph.
849 : : /// The key type of the new map \c tmap should be the Arc type of the
850 : : /// destination graph, and the key type of the original map \c map
851 : : /// should be the Arc type of the source graph.
852 : : template <typename FromMap, typename ToMap>
853 : : GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
854 : : _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
855 : : ArcRefMap, FromMap, ToMap>(map, tmap));
856 : : return *this;
857 : : }
858 : :
859 : : /// \brief Make a copy of the given arc.
860 : : ///
861 : : /// This function makes a copy of the given arc.
862 : : GraphCopy& arc(const Arc& arc, TArc& tarc) {
863 : : _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
864 : : ArcRefMap, TArc>(arc, tarc));
865 : : return *this;
866 : : }
867 : :
868 : : /// \brief Copy the edge references into the given map.
869 : : ///
870 : : /// This function copies the edge references into the given map.
871 : : /// The parameter should be a map, whose key type is the Edge type of
872 : : /// the source graph, while the value type is the Edge type of the
873 : : /// destination graph.
874 : : template <typename EdgeRef>
875 : : GraphCopy& edgeRef(EdgeRef& map) {
876 : : _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
877 : : EdgeRefMap, EdgeRef>(map));
878 : : return *this;
879 : : }
880 : :
881 : : /// \brief Copy the edge cross references into the given map.
882 : : ///
883 : : /// This function copies the edge cross references (reverse references)
884 : : /// into the given map. The parameter should be a map, whose key type
885 : : /// is the Edge type of the destination graph, while the value type is
886 : : /// the Edge type of the source graph.
887 : : template <typename EdgeCrossRef>
888 : : GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
889 : : _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
890 : : Edge, EdgeRefMap, EdgeCrossRef>(map));
891 : : return *this;
892 : : }
893 : :
894 : : /// \brief Make a copy of the given edge map.
895 : : ///
896 : : /// This function makes a copy of the given edge map for the newly
897 : : /// created graph.
898 : : /// The key type of the new map \c tmap should be the Edge type of the
899 : : /// destination graph, and the key type of the original map \c map
900 : : /// should be the Edge type of the source graph.
901 : : template <typename FromMap, typename ToMap>
902 : : GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
903 : : _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
904 : : EdgeRefMap, FromMap, ToMap>(map, tmap));
905 : : return *this;
906 : : }
907 : :
908 : : /// \brief Make a copy of the given edge.
909 : : ///
910 : : /// This function makes a copy of the given edge.
911 : : GraphCopy& edge(const Edge& edge, TEdge& tedge) {
912 : : _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
913 : : EdgeRefMap, TEdge>(edge, tedge));
914 : : return *this;
915 : : }
916 : :
917 : : /// \brief Execute copying.
918 : : ///
919 : : /// This function executes the copying of the graph along with the
920 : : /// copying of the assigned data.
921 : : void run() {
922 : : NodeRefMap nodeRefMap(_from);
923 : : EdgeRefMap edgeRefMap(_from);
924 : : ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
925 : : _core_bits::GraphCopySelector<To>::
926 : : copy(_from, _to, nodeRefMap, edgeRefMap);
927 : : for (int i = 0; i < int(_node_maps.size()); ++i) {
928 : : _node_maps[i]->copy(_from, nodeRefMap);
929 : : }
930 : : for (int i = 0; i < int(_edge_maps.size()); ++i) {
931 : : _edge_maps[i]->copy(_from, edgeRefMap);
932 : : }
933 : : for (int i = 0; i < int(_arc_maps.size()); ++i) {
934 : : _arc_maps[i]->copy(_from, arcRefMap);
935 : : }
936 : : }
937 : :
938 : : private:
939 : :
940 : : const From& _from;
941 : : To& _to;
942 : :
943 : : std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
944 : : _node_maps;
945 : :
946 : : std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
947 : : _arc_maps;
948 : :
949 : : std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
950 : : _edge_maps;
951 : :
952 : : };
953 : :
954 : : /// \brief Copy a graph to another graph.
955 : : ///
956 : : /// This function copies a graph to another graph.
957 : : /// The complete usage of it is detailed in the GraphCopy class,
958 : : /// but a short example shows a basic work:
959 : : ///\code
960 : : /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
961 : : ///\endcode
962 : : ///
963 : : /// After the copy the \c nr map will contain the mapping from the
964 : : /// nodes of the \c from graph to the nodes of the \c to graph and
965 : : /// \c ecr will contain the mapping from the edges of the \c to graph
966 : : /// to the edges of the \c from graph.
967 : : ///
968 : : /// \see GraphCopy
969 : : template <typename From, typename To>
970 : : GraphCopy<From, To>
971 : : graphCopy(const From& from, To& to) {
972 : : return GraphCopy<From, To>(from, to);
973 : : }
974 : :
975 : : namespace _core_bits {
976 : :
977 : : template <typename Graph, typename Enable = void>
978 : : struct FindArcSelector {
979 : : typedef typename Graph::Node Node;
980 : : typedef typename Graph::Arc Arc;
981 : : static Arc find(const Graph &g, Node u, Node v, Arc e) {
982 : : if (e == INVALID) {
983 : : g.firstOut(e, u);
984 : : } else {
985 : : g.nextOut(e);
986 : : }
987 : : while (e != INVALID && g.target(e) != v) {
988 : : g.nextOut(e);
989 : : }
990 : : return e;
991 : : }
992 : : };
993 : :
994 : : template <typename Graph>
995 : : struct FindArcSelector<
996 : : Graph,
997 : : typename enable_if<typename Graph::FindArcTag, void>::type>
998 : : {
999 : : typedef typename Graph::Node Node;
1000 : : typedef typename Graph::Arc Arc;
1001 : : static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1002 : : return g.findArc(u, v, prev);
1003 : : }
1004 : : };
1005 : : }
1006 : :
1007 : : /// \brief Find an arc between two nodes of a digraph.
1008 : : ///
1009 : : /// This function finds an arc from node \c u to node \c v in the
1010 : : /// digraph \c g.
1011 : : ///
1012 : : /// If \c prev is \ref INVALID (this is the default value), then
1013 : : /// it finds the first arc from \c u to \c v. Otherwise it looks for
1014 : : /// the next arc from \c u to \c v after \c prev.
1015 : : /// \return The found arc or \ref INVALID if there is no such an arc.
1016 : : ///
1017 : : /// Thus you can iterate through each arc from \c u to \c v as it follows.
1018 : : ///\code
1019 : : /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1020 : : /// ...
1021 : : /// }
1022 : : ///\endcode
1023 : : ///
1024 : : /// \note \ref ConArcIt provides iterator interface for the same
1025 : : /// functionality.
1026 : : ///
1027 : : ///\sa ConArcIt
1028 : : ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1029 : : template <typename Graph>
1030 : : inline typename Graph::Arc
1031 : : findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1032 : : typename Graph::Arc prev = INVALID) {
1033 : : return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1034 : : }
1035 : :
1036 : : /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1037 : : ///
1038 : : /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1039 : : /// a higher level interface for the \ref findArc() function. You can
1040 : : /// use it the following way:
1041 : : ///\code
1042 : : /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1043 : : /// ...
1044 : : /// }
1045 : : ///\endcode
1046 : : ///
1047 : : ///\sa findArc()
1048 : : ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1049 : : template <typename GR>
1050 : : class ConArcIt : public GR::Arc {
1051 : : typedef typename GR::Arc Parent;
1052 : :
1053 : : public:
1054 : :
1055 : : typedef typename GR::Arc Arc;
1056 : : typedef typename GR::Node Node;
1057 : :
1058 : : /// \brief Constructor.
1059 : : ///
1060 : : /// Construct a new ConArcIt iterating on the arcs that
1061 : : /// connects nodes \c u and \c v.
1062 : : ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
1063 : : Parent::operator=(findArc(_graph, u, v));
1064 : : }
1065 : :
1066 : : /// \brief Constructor.
1067 : : ///
1068 : : /// Construct a new ConArcIt that continues the iterating from arc \c a.
1069 : : ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
1070 : :
1071 : : /// \brief Increment operator.
1072 : : ///
1073 : : /// It increments the iterator and gives back the next arc.
1074 : : ConArcIt& operator++() {
1075 : : Parent::operator=(findArc(_graph, _graph.source(*this),
1076 : : _graph.target(*this), *this));
1077 : : return *this;
1078 : : }
1079 : : private:
1080 : : const GR& _graph;
1081 : : };
1082 : :
1083 : : namespace _core_bits {
1084 : :
1085 : : template <typename Graph, typename Enable = void>
1086 : : struct FindEdgeSelector {
1087 : : typedef typename Graph::Node Node;
1088 : : typedef typename Graph::Edge Edge;
1089 : : static Edge find(const Graph &g, Node u, Node v, Edge e) {
1090 : : bool b;
1091 : : if (u != v) {
1092 : : if (e == INVALID) {
1093 : : g.firstInc(e, b, u);
1094 : : } else {
1095 : : b = g.u(e) == u;
1096 : : g.nextInc(e, b);
1097 : : }
1098 : : while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1099 : : g.nextInc(e, b);
1100 : : }
1101 : : } else {
1102 : : if (e == INVALID) {
1103 : : g.firstInc(e, b, u);
1104 : : } else {
1105 : : b = true;
1106 : : g.nextInc(e, b);
1107 : : }
1108 : : while (e != INVALID && (!b || g.v(e) != v)) {
1109 : : g.nextInc(e, b);
1110 : : }
1111 : : }
1112 : : return e;
1113 : : }
1114 : : };
1115 : :
1116 : : template <typename Graph>
1117 : : struct FindEdgeSelector<
1118 : : Graph,
1119 : : typename enable_if<typename Graph::FindEdgeTag, void>::type>
1120 : : {
1121 : : typedef typename Graph::Node Node;
1122 : : typedef typename Graph::Edge Edge;
1123 : : static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1124 : : return g.findEdge(u, v, prev);
1125 : : }
1126 : : };
1127 : : }
1128 : :
1129 : : /// \brief Find an edge between two nodes of a graph.
1130 : : ///
1131 : : /// This function finds an edge from node \c u to node \c v in graph \c g.
1132 : : /// If node \c u and node \c v is equal then each loop edge
1133 : : /// will be enumerated once.
1134 : : ///
1135 : : /// If \c prev is \ref INVALID (this is the default value), then
1136 : : /// it finds the first edge from \c u to \c v. Otherwise it looks for
1137 : : /// the next edge from \c u to \c v after \c prev.
1138 : : /// \return The found edge or \ref INVALID if there is no such an edge.
1139 : : ///
1140 : : /// Thus you can iterate through each edge between \c u and \c v
1141 : : /// as it follows.
1142 : : ///\code
1143 : : /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1144 : : /// ...
1145 : : /// }
1146 : : ///\endcode
1147 : : ///
1148 : : /// \note \ref ConEdgeIt provides iterator interface for the same
1149 : : /// functionality.
1150 : : ///
1151 : : ///\sa ConEdgeIt
1152 : : template <typename Graph>
1153 : : inline typename Graph::Edge
1154 : : findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1155 : : typename Graph::Edge p = INVALID) {
1156 : : return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1157 : : }
1158 : :
1159 : : /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1160 : : ///
1161 : : /// Iterator for iterating on parallel edges connecting the same nodes.
1162 : : /// It is a higher level interface for the findEdge() function. You can
1163 : : /// use it the following way:
1164 : : ///\code
1165 : : /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1166 : : /// ...
1167 : : /// }
1168 : : ///\endcode
1169 : : ///
1170 : : ///\sa findEdge()
1171 : : template <typename GR>
1172 : : class ConEdgeIt : public GR::Edge {
1173 : : typedef typename GR::Edge Parent;
1174 : :
1175 : : public:
1176 : :
1177 : : typedef typename GR::Edge Edge;
1178 : : typedef typename GR::Node Node;
1179 : :
1180 : : /// \brief Constructor.
1181 : : ///
1182 : : /// Construct a new ConEdgeIt iterating on the edges that
1183 : : /// connects nodes \c u and \c v.
1184 : : ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1185 : : Parent::operator=(findEdge(_graph, _u, _v));
1186 : : }
1187 : :
1188 : : /// \brief Constructor.
1189 : : ///
1190 : : /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1191 : : ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
1192 : :
1193 : : /// \brief Increment operator.
1194 : : ///
1195 : : /// It increments the iterator and gives back the next edge.
1196 : : ConEdgeIt& operator++() {
1197 : : Parent::operator=(findEdge(_graph, _u, _v, *this));
1198 : : return *this;
1199 : : }
1200 : : private:
1201 : : const GR& _graph;
1202 : : Node _u, _v;
1203 : : };
1204 : :
1205 : :
1206 : : ///Dynamic arc look-up between given endpoints.
1207 : :
1208 : : ///Using this class, you can find an arc in a digraph from a given
1209 : : ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1210 : : ///where <em>d</em> is the out-degree of the source node.
1211 : : ///
1212 : : ///It is possible to find \e all parallel arcs between two nodes with
1213 : : ///the \c operator() member.
1214 : : ///
1215 : : ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1216 : : ///\ref AllArcLookUp if your digraph is not changed so frequently.
1217 : : ///
1218 : : ///This class uses a self-adjusting binary search tree, the Splay tree
1219 : : ///of Sleator and Tarjan to guarantee the logarithmic amortized
1220 : : ///time bound for arc look-ups. This class also guarantees the
1221 : : ///optimal time bound in a constant factor for any distribution of
1222 : : ///queries.
1223 : : ///
1224 : : ///\tparam GR The type of the underlying digraph.
1225 : : ///
1226 : : ///\sa ArcLookUp
1227 : : ///\sa AllArcLookUp
1228 : : template <typename GR>
1229 : : class DynArcLookUp
1230 : : : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
1231 : : {
1232 : : typedef typename ItemSetTraits<GR, typename GR::Arc>
1233 : : ::ItemNotifier::ObserverBase Parent;
1234 : :
1235 : : TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1236 : :
1237 : : public:
1238 : :
1239 : : /// The Digraph type
1240 : : typedef GR Digraph;
1241 : :
1242 : : protected:
1243 : :
1244 : : class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
1245 : : {
1246 : : typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
1247 : :
1248 : : public:
1249 : :
1250 : : AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
1251 : :
1252 : : virtual void add(const Node& node) {
1253 : : Parent::add(node);
1254 : : Parent::set(node, INVALID);
1255 : : }
1256 : :
1257 : : virtual void add(const std::vector<Node>& nodes) {
1258 : : Parent::add(nodes);
1259 : : for (int i = 0; i < int(nodes.size()); ++i) {
1260 : : Parent::set(nodes[i], INVALID);
1261 : : }
1262 : : }
1263 : :
1264 : : virtual void build() {
1265 : : Parent::build();
1266 : : Node it;
1267 : : typename Parent::Notifier* nf = Parent::notifier();
1268 : : for (nf->first(it); it != INVALID; nf->next(it)) {
1269 : : Parent::set(it, INVALID);
1270 : : }
1271 : : }
1272 : : };
1273 : :
1274 : : class ArcLess {
1275 : : const Digraph &g;
1276 : : public:
1277 : : ArcLess(const Digraph &_g) : g(_g) {}
1278 : : bool operator()(Arc a,Arc b) const
1279 : : {
1280 : : return g.target(a)<g.target(b);
1281 : : }
1282 : : };
1283 : :
1284 : : protected:
1285 : :
1286 : : const Digraph &_g;
1287 : : AutoNodeMap _head;
1288 : : typename Digraph::template ArcMap<Arc> _parent;
1289 : : typename Digraph::template ArcMap<Arc> _left;
1290 : : typename Digraph::template ArcMap<Arc> _right;
1291 : :
1292 : : public:
1293 : :
1294 : : ///Constructor
1295 : :
1296 : : ///Constructor.
1297 : : ///
1298 : : ///It builds up the search database.
1299 : : DynArcLookUp(const Digraph &g)
1300 : : : _g(g),_head(g),_parent(g),_left(g),_right(g)
1301 : : {
1302 : : Parent::attach(_g.notifier(typename Digraph::Arc()));
1303 : : refresh();
1304 : : }
1305 : :
1306 : : protected:
1307 : :
1308 : : virtual void add(const Arc& arc) {
1309 : : insert(arc);
1310 : : }
1311 : :
1312 : : virtual void add(const std::vector<Arc>& arcs) {
1313 : : for (int i = 0; i < int(arcs.size()); ++i) {
1314 : : insert(arcs[i]);
1315 : : }
1316 : : }
1317 : :
1318 : : virtual void erase(const Arc& arc) {
1319 : : remove(arc);
1320 : : }
1321 : :
1322 : : virtual void erase(const std::vector<Arc>& arcs) {
1323 : : for (int i = 0; i < int(arcs.size()); ++i) {
1324 : : remove(arcs[i]);
1325 : : }
1326 : : }
1327 : :
1328 : : virtual void build() {
1329 : : refresh();
1330 : : }
1331 : :
1332 : : virtual void clear() {
1333 : : for(NodeIt n(_g);n!=INVALID;++n) {
1334 : : _head[n] = INVALID;
1335 : : }
1336 : : }
1337 : :
1338 : : void insert(Arc arc) {
1339 : : Node s = _g.source(arc);
1340 : : Node t = _g.target(arc);
1341 : : _left[arc] = INVALID;
1342 : : _right[arc] = INVALID;
1343 : :
1344 : : Arc e = _head[s];
1345 : : if (e == INVALID) {
1346 : : _head[s] = arc;
1347 : : _parent[arc] = INVALID;
1348 : : return;
1349 : : }
1350 : : while (true) {
1351 : : if (t < _g.target(e)) {
1352 : : if (_left[e] == INVALID) {
1353 : : _left[e] = arc;
1354 : : _parent[arc] = e;
1355 : : splay(arc);
1356 : : return;
1357 : : } else {
1358 : : e = _left[e];
1359 : : }
1360 : : } else {
1361 : : if (_right[e] == INVALID) {
1362 : : _right[e] = arc;
1363 : : _parent[arc] = e;
1364 : : splay(arc);
1365 : : return;
1366 : : } else {
1367 : : e = _right[e];
1368 : : }
1369 : : }
1370 : : }
1371 : : }
1372 : :
1373 : : void remove(Arc arc) {
1374 : : if (_left[arc] == INVALID) {
1375 : : if (_right[arc] != INVALID) {
1376 : : _parent[_right[arc]] = _parent[arc];
1377 : : }
1378 : : if (_parent[arc] != INVALID) {
1379 : : if (_left[_parent[arc]] == arc) {
1380 : : _left[_parent[arc]] = _right[arc];
1381 : : } else {
1382 : : _right[_parent[arc]] = _right[arc];
1383 : : }
1384 : : } else {
1385 : : _head[_g.source(arc)] = _right[arc];
1386 : : }
1387 : : } else if (_right[arc] == INVALID) {
1388 : : _parent[_left[arc]] = _parent[arc];
1389 : : if (_parent[arc] != INVALID) {
1390 : : if (_left[_parent[arc]] == arc) {
1391 : : _left[_parent[arc]] = _left[arc];
1392 : : } else {
1393 : : _right[_parent[arc]] = _left[arc];
1394 : : }
1395 : : } else {
1396 : : _head[_g.source(arc)] = _left[arc];
1397 : : }
1398 : : } else {
1399 : : Arc e = _left[arc];
1400 : : if (_right[e] != INVALID) {
1401 : : e = _right[e];
1402 : : while (_right[e] != INVALID) {
1403 : : e = _right[e];
1404 : : }
1405 : : Arc s = _parent[e];
1406 : : _right[_parent[e]] = _left[e];
1407 : : if (_left[e] != INVALID) {
1408 : : _parent[_left[e]] = _parent[e];
1409 : : }
1410 : :
1411 : : _left[e] = _left[arc];
1412 : : _parent[_left[arc]] = e;
1413 : : _right[e] = _right[arc];
1414 : : _parent[_right[arc]] = e;
1415 : :
1416 : : _parent[e] = _parent[arc];
1417 : : if (_parent[arc] != INVALID) {
1418 : : if (_left[_parent[arc]] == arc) {
1419 : : _left[_parent[arc]] = e;
1420 : : } else {
1421 : : _right[_parent[arc]] = e;
1422 : : }
1423 : : }
1424 : : splay(s);
1425 : : } else {
1426 : : _right[e] = _right[arc];
1427 : : _parent[_right[arc]] = e;
1428 : : _parent[e] = _parent[arc];
1429 : :
1430 : : if (_parent[arc] != INVALID) {
1431 : : if (_left[_parent[arc]] == arc) {
1432 : : _left[_parent[arc]] = e;
1433 : : } else {
1434 : : _right[_parent[arc]] = e;
1435 : : }
1436 : : } else {
1437 : : _head[_g.source(arc)] = e;
1438 : : }
1439 : : }
1440 : : }
1441 : : }
1442 : :
1443 : : Arc refreshRec(std::vector<Arc> &v,int a,int b)
1444 : : {
1445 : : int m=(a+b)/2;
1446 : : Arc me=v[m];
1447 : : if (a < m) {
1448 : : Arc left = refreshRec(v,a,m-1);
1449 : : _left[me] = left;
1450 : : _parent[left] = me;
1451 : : } else {
1452 : : _left[me] = INVALID;
1453 : : }
1454 : : if (m < b) {
1455 : : Arc right = refreshRec(v,m+1,b);
1456 : : _right[me] = right;
1457 : : _parent[right] = me;
1458 : : } else {
1459 : : _right[me] = INVALID;
1460 : : }
1461 : : return me;
1462 : : }
1463 : :
1464 : : void refresh() {
1465 : : for(NodeIt n(_g);n!=INVALID;++n) {
1466 : : std::vector<Arc> v;
1467 : : for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
1468 : : if (!v.empty()) {
1469 : : std::sort(v.begin(),v.end(),ArcLess(_g));
1470 : : Arc head = refreshRec(v,0,v.size()-1);
1471 : : _head[n] = head;
1472 : : _parent[head] = INVALID;
1473 : : }
1474 : : else _head[n] = INVALID;
1475 : : }
1476 : : }
1477 : :
1478 : : void zig(Arc v) {
1479 : : Arc w = _parent[v];
1480 : : _parent[v] = _parent[w];
1481 : : _parent[w] = v;
1482 : : _left[w] = _right[v];
1483 : : _right[v] = w;
1484 : : if (_parent[v] != INVALID) {
1485 : : if (_right[_parent[v]] == w) {
1486 : : _right[_parent[v]] = v;
1487 : : } else {
1488 : : _left[_parent[v]] = v;
1489 : : }
1490 : : }
1491 : : if (_left[w] != INVALID){
1492 : : _parent[_left[w]] = w;
1493 : : }
1494 : : }
1495 : :
1496 : : void zag(Arc v) {
1497 : : Arc w = _parent[v];
1498 : : _parent[v] = _parent[w];
1499 : : _parent[w] = v;
1500 : : _right[w] = _left[v];
1501 : : _left[v] = w;
1502 : : if (_parent[v] != INVALID){
1503 : : if (_left[_parent[v]] == w) {
1504 : : _left[_parent[v]] = v;
1505 : : } else {
1506 : : _right[_parent[v]] = v;
1507 : : }
1508 : : }
1509 : : if (_right[w] != INVALID){
1510 : : _parent[_right[w]] = w;
1511 : : }
1512 : : }
1513 : :
1514 : : void splay(Arc v) {
1515 : : while (_parent[v] != INVALID) {
1516 : : if (v == _left[_parent[v]]) {
1517 : : if (_parent[_parent[v]] == INVALID) {
1518 : : zig(v);
1519 : : } else {
1520 : : if (_parent[v] == _left[_parent[_parent[v]]]) {
1521 : : zig(_parent[v]);
1522 : : zig(v);
1523 : : } else {
1524 : : zig(v);
1525 : : zag(v);
1526 : : }
1527 : : }
1528 : : } else {
1529 : : if (_parent[_parent[v]] == INVALID) {
1530 : : zag(v);
1531 : : } else {
1532 : : if (_parent[v] == _left[_parent[_parent[v]]]) {
1533 : : zag(v);
1534 : : zig(v);
1535 : : } else {
1536 : : zag(_parent[v]);
1537 : : zag(v);
1538 : : }
1539 : : }
1540 : : }
1541 : : }
1542 : : _head[_g.source(v)] = v;
1543 : : }
1544 : :
1545 : :
1546 : : public:
1547 : :
1548 : : ///Find an arc between two nodes.
1549 : :
1550 : : ///Find an arc between two nodes.
1551 : : ///\param s The source node.
1552 : : ///\param t The target node.
1553 : : ///\param p The previous arc between \c s and \c t. It it is INVALID or
1554 : : ///not given, the operator finds the first appropriate arc.
1555 : : ///\return An arc from \c s to \c t after \c p or
1556 : : ///\ref INVALID if there is no more.
1557 : : ///
1558 : : ///For example, you can count the number of arcs from \c u to \c v in the
1559 : : ///following way.
1560 : : ///\code
1561 : : ///DynArcLookUp<ListDigraph> ae(g);
1562 : : ///...
1563 : : ///int n = 0;
1564 : : ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
1565 : : ///\endcode
1566 : : ///
1567 : : ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
1568 : : ///amortized time, specifically, the time complexity of the lookups
1569 : : ///is equal to the optimal search tree implementation for the
1570 : : ///current query distribution in a constant factor.
1571 : : ///
1572 : : ///\note This is a dynamic data structure, therefore the data
1573 : : ///structure is updated after each graph alteration. Thus although
1574 : : ///this data structure is theoretically faster than \ref ArcLookUp
1575 : : ///and \ref AllArcLookUp, it often provides worse performance than
1576 : : ///them.
1577 : : Arc operator()(Node s, Node t, Arc p = INVALID) const {
1578 : : if (p == INVALID) {
1579 : : Arc a = _head[s];
1580 : : if (a == INVALID) return INVALID;
1581 : : Arc r = INVALID;
1582 : : while (true) {
1583 : : if (_g.target(a) < t) {
1584 : : if (_right[a] == INVALID) {
1585 : : const_cast<DynArcLookUp&>(*this).splay(a);
1586 : : return r;
1587 : : } else {
1588 : : a = _right[a];
1589 : : }
1590 : : } else {
1591 : : if (_g.target(a) == t) {
1592 : : r = a;
1593 : : }
1594 : : if (_left[a] == INVALID) {
1595 : : const_cast<DynArcLookUp&>(*this).splay(a);
1596 : : return r;
1597 : : } else {
1598 : : a = _left[a];
1599 : : }
1600 : : }
1601 : : }
1602 : : } else {
1603 : : Arc a = p;
1604 : : if (_right[a] != INVALID) {
1605 : : a = _right[a];
1606 : : while (_left[a] != INVALID) {
1607 : : a = _left[a];
1608 : : }
1609 : : const_cast<DynArcLookUp&>(*this).splay(a);
1610 : : } else {
1611 : : while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1612 : : a = _parent[a];
1613 : : }
1614 : : if (_parent[a] == INVALID) {
1615 : : return INVALID;
1616 : : } else {
1617 : : a = _parent[a];
1618 : : const_cast<DynArcLookUp&>(*this).splay(a);
1619 : : }
1620 : : }
1621 : : if (_g.target(a) == t) return a;
1622 : : else return INVALID;
1623 : : }
1624 : : }
1625 : :
1626 : : };
1627 : :
1628 : : ///Fast arc look-up between given endpoints.
1629 : :
1630 : : ///Using this class, you can find an arc in a digraph from a given
1631 : : ///source to a given target in time <em>O</em>(log<em>d</em>),
1632 : : ///where <em>d</em> is the out-degree of the source node.
1633 : : ///
1634 : : ///It is not possible to find \e all parallel arcs between two nodes.
1635 : : ///Use \ref AllArcLookUp for this purpose.
1636 : : ///
1637 : : ///\warning This class is static, so you should call refresh() (or at
1638 : : ///least refresh(Node)) to refresh this data structure whenever the
1639 : : ///digraph changes. This is a time consuming (superlinearly proportional
1640 : : ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1641 : : ///
1642 : : ///\tparam GR The type of the underlying digraph.
1643 : : ///
1644 : : ///\sa DynArcLookUp
1645 : : ///\sa AllArcLookUp
1646 : : template<class GR>
1647 : : class ArcLookUp
1648 : : {
1649 : : TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1650 : :
1651 : : public:
1652 : :
1653 : : /// The Digraph type
1654 : : typedef GR Digraph;
1655 : :
1656 : : protected:
1657 : : const Digraph &_g;
1658 : : typename Digraph::template NodeMap<Arc> _head;
1659 : : typename Digraph::template ArcMap<Arc> _left;
1660 : : typename Digraph::template ArcMap<Arc> _right;
1661 : :
1662 : : class ArcLess {
1663 : : const Digraph &g;
1664 : : public:
1665 : : ArcLess(const Digraph &_g) : g(_g) {}
1666 : : bool operator()(Arc a,Arc b) const
1667 : : {
1668 : : return g.target(a)<g.target(b);
1669 : : }
1670 : : };
1671 : :
1672 : : public:
1673 : :
1674 : : ///Constructor
1675 : :
1676 : : ///Constructor.
1677 : : ///
1678 : : ///It builds up the search database, which remains valid until the digraph
1679 : : ///changes.
1680 : : ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1681 : :
1682 : : private:
1683 : : Arc refreshRec(std::vector<Arc> &v,int a,int b)
1684 : : {
1685 : : int m=(a+b)/2;
1686 : : Arc me=v[m];
1687 : : _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1688 : : _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1689 : : return me;
1690 : : }
1691 : : public:
1692 : : ///Refresh the search data structure at a node.
1693 : :
1694 : : ///Build up the search database of node \c n.
1695 : : ///
1696 : : ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
1697 : : ///is the number of the outgoing arcs of \c n.
1698 : : void refresh(Node n)
1699 : : {
1700 : : std::vector<Arc> v;
1701 : : for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1702 : : if(v.size()) {
1703 : : std::sort(v.begin(),v.end(),ArcLess(_g));
1704 : : _head[n]=refreshRec(v,0,v.size()-1);
1705 : : }
1706 : : else _head[n]=INVALID;
1707 : : }
1708 : : ///Refresh the full data structure.
1709 : :
1710 : : ///Build up the full search database. In fact, it simply calls
1711 : : ///\ref refresh(Node) "refresh(n)" for each node \c n.
1712 : : ///
1713 : : ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1714 : : ///the number of the arcs in the digraph and <em>D</em> is the maximum
1715 : : ///out-degree of the digraph.
1716 : : void refresh()
1717 : : {
1718 : : for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1719 : : }
1720 : :
1721 : : ///Find an arc between two nodes.
1722 : :
1723 : : ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
1724 : : ///where <em>d</em> is the number of outgoing arcs of \c s.
1725 : : ///\param s The source node.
1726 : : ///\param t The target node.
1727 : : ///\return An arc from \c s to \c t if there exists,
1728 : : ///\ref INVALID otherwise.
1729 : : ///
1730 : : ///\warning If you change the digraph, refresh() must be called before using
1731 : : ///this operator. If you change the outgoing arcs of
1732 : : ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1733 : : Arc operator()(Node s, Node t) const
1734 : : {
1735 : : Arc e;
1736 : : for(e=_head[s];
1737 : : e!=INVALID&&_g.target(e)!=t;
1738 : : e = t < _g.target(e)?_left[e]:_right[e]) ;
1739 : : return e;
1740 : : }
1741 : :
1742 : : };
1743 : :
1744 : : ///Fast look-up of all arcs between given endpoints.
1745 : :
1746 : : ///This class is the same as \ref ArcLookUp, with the addition
1747 : : ///that it makes it possible to find all parallel arcs between given
1748 : : ///endpoints.
1749 : : ///
1750 : : ///\warning This class is static, so you should call refresh() (or at
1751 : : ///least refresh(Node)) to refresh this data structure whenever the
1752 : : ///digraph changes. This is a time consuming (superlinearly proportional
1753 : : ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1754 : : ///
1755 : : ///\tparam GR The type of the underlying digraph.
1756 : : ///
1757 : : ///\sa DynArcLookUp
1758 : : ///\sa ArcLookUp
1759 : : template<class GR>
1760 : : class AllArcLookUp : public ArcLookUp<GR>
1761 : : {
1762 : : using ArcLookUp<GR>::_g;
1763 : : using ArcLookUp<GR>::_right;
1764 : : using ArcLookUp<GR>::_left;
1765 : : using ArcLookUp<GR>::_head;
1766 : :
1767 : : TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1768 : :
1769 : : typename GR::template ArcMap<Arc> _next;
1770 : :
1771 : : Arc refreshNext(Arc head,Arc next=INVALID)
1772 : : {
1773 : : if(head==INVALID) return next;
1774 : : else {
1775 : : next=refreshNext(_right[head],next);
1776 : : _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1777 : : ? next : INVALID;
1778 : : return refreshNext(_left[head],head);
1779 : : }
1780 : : }
1781 : :
1782 : : void refreshNext()
1783 : : {
1784 : : for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1785 : : }
1786 : :
1787 : : public:
1788 : :
1789 : : /// The Digraph type
1790 : : typedef GR Digraph;
1791 : :
1792 : : ///Constructor
1793 : :
1794 : : ///Constructor.
1795 : : ///
1796 : : ///It builds up the search database, which remains valid until the digraph
1797 : : ///changes.
1798 : : AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
1799 : :
1800 : : ///Refresh the data structure at a node.
1801 : :
1802 : : ///Build up the search database of node \c n.
1803 : : ///
1804 : : ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
1805 : : ///the number of the outgoing arcs of \c n.
1806 : : void refresh(Node n)
1807 : : {
1808 : : ArcLookUp<GR>::refresh(n);
1809 : : refreshNext(_head[n]);
1810 : : }
1811 : :
1812 : : ///Refresh the full data structure.
1813 : :
1814 : : ///Build up the full search database. In fact, it simply calls
1815 : : ///\ref refresh(Node) "refresh(n)" for each node \c n.
1816 : : ///
1817 : : ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1818 : : ///the number of the arcs in the digraph and <em>D</em> is the maximum
1819 : : ///out-degree of the digraph.
1820 : : void refresh()
1821 : : {
1822 : : for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1823 : : }
1824 : :
1825 : : ///Find an arc between two nodes.
1826 : :
1827 : : ///Find an arc between two nodes.
1828 : : ///\param s The source node.
1829 : : ///\param t The target node.
1830 : : ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1831 : : ///not given, the operator finds the first appropriate arc.
1832 : : ///\return An arc from \c s to \c t after \c prev or
1833 : : ///\ref INVALID if there is no more.
1834 : : ///
1835 : : ///For example, you can count the number of arcs from \c u to \c v in the
1836 : : ///following way.
1837 : : ///\code
1838 : : ///AllArcLookUp<ListDigraph> ae(g);
1839 : : ///...
1840 : : ///int n = 0;
1841 : : ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
1842 : : ///\endcode
1843 : : ///
1844 : : ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
1845 : : ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
1846 : : ///consecutive arcs are found in constant time.
1847 : : ///
1848 : : ///\warning If you change the digraph, refresh() must be called before using
1849 : : ///this operator. If you change the outgoing arcs of
1850 : : ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1851 : : ///
1852 : : #ifdef DOXYGEN
1853 : : Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1854 : : #else
1855 : : using ArcLookUp<GR>::operator() ;
1856 : : Arc operator()(Node s, Node t, Arc prev) const
1857 : : {
1858 : : return prev==INVALID?(*this)(s,t):_next[prev];
1859 : : }
1860 : : #endif
1861 : :
1862 : : };
1863 : :
1864 : : /// @}
1865 : :
1866 : : } //namespace lemon
1867 : :
1868 : : #endif
|
