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-2008 |
|
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_GRAPH_UTILS_H |
|
20 #define LEMON_GRAPH_UTILS_H |
|
21 |
|
22 #include <iterator> |
|
23 #include <vector> |
|
24 #include <map> |
|
25 #include <cmath> |
|
26 #include <algorithm> |
|
27 |
|
28 #include <lemon/bits/invalid.h> |
|
29 #include <lemon/bits/utility.h> |
|
30 #include <lemon/maps.h> |
|
31 #include <lemon/bits/traits.h> |
|
32 |
|
33 #include <lemon/bits/alteration_notifier.h> |
|
34 #include <lemon/bits/default_map.h> |
|
35 |
|
36 ///\ingroup gutils |
|
37 ///\file |
|
38 ///\brief Graph utilities. |
|
39 |
|
40 namespace lemon { |
|
41 |
|
42 /// \addtogroup gutils |
|
43 /// @{ |
|
44 |
|
45 ///Creates convenience typedefs for the digraph types and iterators |
|
46 |
|
47 ///This \c \#define creates convenience typedefs for the following types |
|
48 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, |
|
49 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, |
|
50 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. |
|
51 /// |
|
52 ///\note If the graph type is a dependent type, ie. the graph type depend |
|
53 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
|
54 ///macro. |
|
55 #define DIGRAPH_TYPEDEFS(Digraph) \ |
|
56 typedef Digraph::Node Node; \ |
|
57 typedef Digraph::NodeIt NodeIt; \ |
|
58 typedef Digraph::Arc Arc; \ |
|
59 typedef Digraph::ArcIt ArcIt; \ |
|
60 typedef Digraph::InArcIt InArcIt; \ |
|
61 typedef Digraph::OutArcIt OutArcIt; \ |
|
62 typedef Digraph::NodeMap<bool> BoolNodeMap; \ |
|
63 typedef Digraph::NodeMap<int> IntNodeMap; \ |
|
64 typedef Digraph::NodeMap<double> DoubleNodeMap; \ |
|
65 typedef Digraph::ArcMap<bool> BoolArcMap; \ |
|
66 typedef Digraph::ArcMap<int> IntArcMap; \ |
|
67 typedef Digraph::ArcMap<double> DoubleArcMap |
|
68 |
|
69 ///Creates convenience typedefs for the digraph types and iterators |
|
70 |
|
71 ///\see DIGRAPH_TYPEDEFS |
|
72 /// |
|
73 ///\note Use this macro, if the graph type is a dependent type, |
|
74 ///ie. the graph type depend on a template parameter. |
|
75 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ |
|
76 typedef typename Digraph::Node Node; \ |
|
77 typedef typename Digraph::NodeIt NodeIt; \ |
|
78 typedef typename Digraph::Arc Arc; \ |
|
79 typedef typename Digraph::ArcIt ArcIt; \ |
|
80 typedef typename Digraph::InArcIt InArcIt; \ |
|
81 typedef typename Digraph::OutArcIt OutArcIt; \ |
|
82 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ |
|
83 typedef typename Digraph::template NodeMap<int> IntNodeMap; \ |
|
84 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ |
|
85 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ |
|
86 typedef typename Digraph::template ArcMap<int> IntArcMap; \ |
|
87 typedef typename Digraph::template ArcMap<double> DoubleArcMap |
|
88 |
|
89 ///Creates convenience typedefs for the graph types and iterators |
|
90 |
|
91 ///This \c \#define creates the same convenience typedefs as defined |
|
92 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates |
|
93 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, |
|
94 ///\c DoubleEdgeMap. |
|
95 /// |
|
96 ///\note If the graph type is a dependent type, ie. the graph type depend |
|
97 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
|
98 ///macro. |
|
99 #define GRAPH_TYPEDEFS(Graph) \ |
|
100 DIGRAPH_TYPEDEFS(Graph); \ |
|
101 typedef Graph::Edge Edge; \ |
|
102 typedef Graph::EdgeIt EdgeIt; \ |
|
103 typedef Graph::IncEdgeIt IncEdgeIt; \ |
|
104 typedef Graph::EdgeMap<bool> BoolEdgeMap; \ |
|
105 typedef Graph::EdgeMap<int> IntEdgeMap; \ |
|
106 typedef Graph::EdgeMap<double> DoubleEdgeMap |
|
107 |
|
108 ///Creates convenience typedefs for the graph types and iterators |
|
109 |
|
110 ///\see GRAPH_TYPEDEFS |
|
111 /// |
|
112 ///\note Use this macro, if the graph type is a dependent type, |
|
113 ///ie. the graph type depend on a template parameter. |
|
114 #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ |
|
115 TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ |
|
116 typedef typename Graph::Edge Edge; \ |
|
117 typedef typename Graph::EdgeIt EdgeIt; \ |
|
118 typedef typename Graph::IncEdgeIt IncEdgeIt; \ |
|
119 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ |
|
120 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ |
|
121 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap |
|
122 |
|
123 /// \brief Function to count the items in the graph. |
|
124 /// |
|
125 /// This function counts the items (nodes, arcs etc) in the graph. |
|
126 /// The complexity of the function is O(n) because |
|
127 /// it iterates on all of the items. |
|
128 template <typename Graph, typename Item> |
|
129 inline int countItems(const Graph& g) { |
|
130 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
|
131 int num = 0; |
|
132 for (ItemIt it(g); it != INVALID; ++it) { |
|
133 ++num; |
|
134 } |
|
135 return num; |
|
136 } |
|
137 |
|
138 // Node counting: |
|
139 |
|
140 namespace _graph_utils_bits { |
|
141 |
|
142 template <typename Graph, typename Enable = void> |
|
143 struct CountNodesSelector { |
|
144 static int count(const Graph &g) { |
|
145 return countItems<Graph, typename Graph::Node>(g); |
|
146 } |
|
147 }; |
|
148 |
|
149 template <typename Graph> |
|
150 struct CountNodesSelector< |
|
151 Graph, typename |
|
152 enable_if<typename Graph::NodeNumTag, void>::type> |
|
153 { |
|
154 static int count(const Graph &g) { |
|
155 return g.nodeNum(); |
|
156 } |
|
157 }; |
|
158 } |
|
159 |
|
160 /// \brief Function to count the nodes in the graph. |
|
161 /// |
|
162 /// This function counts the nodes in the graph. |
|
163 /// The complexity of the function is O(n) but for some |
|
164 /// graph structures it is specialized to run in O(1). |
|
165 /// |
|
166 /// If the graph contains a \e nodeNum() member function and a |
|
167 /// \e NodeNumTag tag then this function calls directly the member |
|
168 /// function to query the cardinality of the node set. |
|
169 template <typename Graph> |
|
170 inline int countNodes(const Graph& g) { |
|
171 return _graph_utils_bits::CountNodesSelector<Graph>::count(g); |
|
172 } |
|
173 |
|
174 // Arc counting: |
|
175 |
|
176 namespace _graph_utils_bits { |
|
177 |
|
178 template <typename Graph, typename Enable = void> |
|
179 struct CountArcsSelector { |
|
180 static int count(const Graph &g) { |
|
181 return countItems<Graph, typename Graph::Arc>(g); |
|
182 } |
|
183 }; |
|
184 |
|
185 template <typename Graph> |
|
186 struct CountArcsSelector< |
|
187 Graph, |
|
188 typename enable_if<typename Graph::ArcNumTag, void>::type> |
|
189 { |
|
190 static int count(const Graph &g) { |
|
191 return g.arcNum(); |
|
192 } |
|
193 }; |
|
194 } |
|
195 |
|
196 /// \brief Function to count the arcs in the graph. |
|
197 /// |
|
198 /// This function counts the arcs in the graph. |
|
199 /// The complexity of the function is O(e) but for some |
|
200 /// graph structures it is specialized to run in O(1). |
|
201 /// |
|
202 /// If the graph contains a \e arcNum() member function and a |
|
203 /// \e EdgeNumTag tag then this function calls directly the member |
|
204 /// function to query the cardinality of the arc set. |
|
205 template <typename Graph> |
|
206 inline int countArcs(const Graph& g) { |
|
207 return _graph_utils_bits::CountArcsSelector<Graph>::count(g); |
|
208 } |
|
209 |
|
210 // Edge counting: |
|
211 namespace _graph_utils_bits { |
|
212 |
|
213 template <typename Graph, typename Enable = void> |
|
214 struct CountEdgesSelector { |
|
215 static int count(const Graph &g) { |
|
216 return countItems<Graph, typename Graph::Edge>(g); |
|
217 } |
|
218 }; |
|
219 |
|
220 template <typename Graph> |
|
221 struct CountEdgesSelector< |
|
222 Graph, |
|
223 typename enable_if<typename Graph::EdgeNumTag, void>::type> |
|
224 { |
|
225 static int count(const Graph &g) { |
|
226 return g.edgeNum(); |
|
227 } |
|
228 }; |
|
229 } |
|
230 |
|
231 /// \brief Function to count the edges in the graph. |
|
232 /// |
|
233 /// This function counts the edges in the graph. |
|
234 /// The complexity of the function is O(m) but for some |
|
235 /// graph structures it is specialized to run in O(1). |
|
236 /// |
|
237 /// If the graph contains a \e edgeNum() member function and a |
|
238 /// \e EdgeNumTag tag then this function calls directly the member |
|
239 /// function to query the cardinality of the edge set. |
|
240 template <typename Graph> |
|
241 inline int countEdges(const Graph& g) { |
|
242 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g); |
|
243 |
|
244 } |
|
245 |
|
246 |
|
247 template <typename Graph, typename DegIt> |
|
248 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { |
|
249 int num = 0; |
|
250 for (DegIt it(_g, _n); it != INVALID; ++it) { |
|
251 ++num; |
|
252 } |
|
253 return num; |
|
254 } |
|
255 |
|
256 /// \brief Function to count the number of the out-arcs from node \c n. |
|
257 /// |
|
258 /// This function counts the number of the out-arcs from node \c n |
|
259 /// in the graph. |
|
260 template <typename Graph> |
|
261 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { |
|
262 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n); |
|
263 } |
|
264 |
|
265 /// \brief Function to count the number of the in-arcs to node \c n. |
|
266 /// |
|
267 /// This function counts the number of the in-arcs to node \c n |
|
268 /// in the graph. |
|
269 template <typename Graph> |
|
270 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { |
|
271 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n); |
|
272 } |
|
273 |
|
274 /// \brief Function to count the number of the inc-edges to node \c n. |
|
275 /// |
|
276 /// This function counts the number of the inc-edges to node \c n |
|
277 /// in the graph. |
|
278 template <typename Graph> |
|
279 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { |
|
280 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); |
|
281 } |
|
282 |
|
283 namespace _graph_utils_bits { |
|
284 |
|
285 template <typename Graph, typename Enable = void> |
|
286 struct FindArcSelector { |
|
287 typedef typename Graph::Node Node; |
|
288 typedef typename Graph::Arc Arc; |
|
289 static Arc find(const Graph &g, Node u, Node v, Arc e) { |
|
290 if (e == INVALID) { |
|
291 g.firstOut(e, u); |
|
292 } else { |
|
293 g.nextOut(e); |
|
294 } |
|
295 while (e != INVALID && g.target(e) != v) { |
|
296 g.nextOut(e); |
|
297 } |
|
298 return e; |
|
299 } |
|
300 }; |
|
301 |
|
302 template <typename Graph> |
|
303 struct FindArcSelector< |
|
304 Graph, |
|
305 typename enable_if<typename Graph::FindEdgeTag, void>::type> |
|
306 { |
|
307 typedef typename Graph::Node Node; |
|
308 typedef typename Graph::Arc Arc; |
|
309 static Arc find(const Graph &g, Node u, Node v, Arc prev) { |
|
310 return g.findArc(u, v, prev); |
|
311 } |
|
312 }; |
|
313 } |
|
314 |
|
315 /// \brief Finds an arc between two nodes of a graph. |
|
316 /// |
|
317 /// Finds an arc from node \c u to node \c v in graph \c g. |
|
318 /// |
|
319 /// If \c prev is \ref INVALID (this is the default value), then |
|
320 /// it finds the first arc from \c u to \c v. Otherwise it looks for |
|
321 /// the next arc from \c u to \c v after \c prev. |
|
322 /// \return The found arc or \ref INVALID if there is no such an arc. |
|
323 /// |
|
324 /// Thus you can iterate through each arc from \c u to \c v as it follows. |
|
325 ///\code |
|
326 /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) { |
|
327 /// ... |
|
328 /// } |
|
329 ///\endcode |
|
330 /// |
|
331 ///\sa ArcLookUp |
|
332 ///\sa AllArcLookUp |
|
333 ///\sa DynArcLookUp |
|
334 ///\sa ConArcIt |
|
335 template <typename Graph> |
|
336 inline typename Graph::Arc |
|
337 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, |
|
338 typename Graph::Arc prev = INVALID) { |
|
339 return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev); |
|
340 } |
|
341 |
|
342 /// \brief Iterator for iterating on arcs connected the same nodes. |
|
343 /// |
|
344 /// Iterator for iterating on arcs connected the same nodes. It is |
|
345 /// higher level interface for the findArc() function. You can |
|
346 /// use it the following way: |
|
347 ///\code |
|
348 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
|
349 /// ... |
|
350 /// } |
|
351 ///\endcode |
|
352 /// |
|
353 ///\sa findArc() |
|
354 ///\sa ArcLookUp |
|
355 ///\sa AllArcLookUp |
|
356 ///\sa DynArcLookUp |
|
357 template <typename _Graph> |
|
358 class ConArcIt : public _Graph::Arc { |
|
359 public: |
|
360 |
|
361 typedef _Graph Graph; |
|
362 typedef typename Graph::Arc Parent; |
|
363 |
|
364 typedef typename Graph::Arc Arc; |
|
365 typedef typename Graph::Node Node; |
|
366 |
|
367 /// \brief Constructor. |
|
368 /// |
|
369 /// Construct a new ConArcIt iterating on the arcs which |
|
370 /// connects the \c u and \c v node. |
|
371 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { |
|
372 Parent::operator=(findArc(_graph, u, v)); |
|
373 } |
|
374 |
|
375 /// \brief Constructor. |
|
376 /// |
|
377 /// Construct a new ConArcIt which continues the iterating from |
|
378 /// the \c e arc. |
|
379 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} |
|
380 |
|
381 /// \brief Increment operator. |
|
382 /// |
|
383 /// It increments the iterator and gives back the next arc. |
|
384 ConArcIt& operator++() { |
|
385 Parent::operator=(findArc(_graph, _graph.source(*this), |
|
386 _graph.target(*this), *this)); |
|
387 return *this; |
|
388 } |
|
389 private: |
|
390 const Graph& _graph; |
|
391 }; |
|
392 |
|
393 namespace _graph_utils_bits { |
|
394 |
|
395 template <typename Graph, typename Enable = void> |
|
396 struct FindEdgeSelector { |
|
397 typedef typename Graph::Node Node; |
|
398 typedef typename Graph::Edge Edge; |
|
399 static Edge find(const Graph &g, Node u, Node v, Edge e) { |
|
400 bool b; |
|
401 if (u != v) { |
|
402 if (e == INVALID) { |
|
403 g.firstInc(e, b, u); |
|
404 } else { |
|
405 b = g.u(e) == u; |
|
406 g.nextInc(e, b); |
|
407 } |
|
408 while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) { |
|
409 g.nextInc(e, b); |
|
410 } |
|
411 } else { |
|
412 if (e == INVALID) { |
|
413 g.firstInc(e, b, u); |
|
414 } else { |
|
415 b = true; |
|
416 g.nextInc(e, b); |
|
417 } |
|
418 while (e != INVALID && (!b || g.v(e) != v)) { |
|
419 g.nextInc(e, b); |
|
420 } |
|
421 } |
|
422 return e; |
|
423 } |
|
424 }; |
|
425 |
|
426 template <typename Graph> |
|
427 struct FindEdgeSelector< |
|
428 Graph, |
|
429 typename enable_if<typename Graph::FindEdgeTag, void>::type> |
|
430 { |
|
431 typedef typename Graph::Node Node; |
|
432 typedef typename Graph::Edge Edge; |
|
433 static Edge find(const Graph &g, Node u, Node v, Edge prev) { |
|
434 return g.findEdge(u, v, prev); |
|
435 } |
|
436 }; |
|
437 } |
|
438 |
|
439 /// \brief Finds an edge between two nodes of a graph. |
|
440 /// |
|
441 /// Finds an edge from node \c u to node \c v in graph \c g. |
|
442 /// If the node \c u and node \c v is equal then each loop edge |
|
443 /// will be enumerated once. |
|
444 /// |
|
445 /// If \c prev is \ref INVALID (this is the default value), then |
|
446 /// it finds the first arc from \c u to \c v. Otherwise it looks for |
|
447 /// the next arc from \c u to \c v after \c prev. |
|
448 /// \return The found arc or \ref INVALID if there is no such an arc. |
|
449 /// |
|
450 /// Thus you can iterate through each arc from \c u to \c v as it follows. |
|
451 ///\code |
|
452 /// for(Edge e = findEdge(g,u,v); e != INVALID; |
|
453 /// e = findEdge(g,u,v,e)) { |
|
454 /// ... |
|
455 /// } |
|
456 ///\endcode |
|
457 /// |
|
458 ///\sa ConEdgeIt |
|
459 |
|
460 template <typename Graph> |
|
461 inline typename Graph::Edge |
|
462 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, |
|
463 typename Graph::Edge p = INVALID) { |
|
464 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p); |
|
465 } |
|
466 |
|
467 /// \brief Iterator for iterating on edges connected the same nodes. |
|
468 /// |
|
469 /// Iterator for iterating on edges connected the same nodes. It is |
|
470 /// higher level interface for the findEdge() function. You can |
|
471 /// use it the following way: |
|
472 ///\code |
|
473 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
|
474 /// ... |
|
475 /// } |
|
476 ///\endcode |
|
477 /// |
|
478 ///\sa findEdge() |
|
479 template <typename _Graph> |
|
480 class ConEdgeIt : public _Graph::Edge { |
|
481 public: |
|
482 |
|
483 typedef _Graph Graph; |
|
484 typedef typename Graph::Edge Parent; |
|
485 |
|
486 typedef typename Graph::Edge Edge; |
|
487 typedef typename Graph::Node Node; |
|
488 |
|
489 /// \brief Constructor. |
|
490 /// |
|
491 /// Construct a new ConEdgeIt iterating on the edges which |
|
492 /// connects the \c u and \c v node. |
|
493 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { |
|
494 Parent::operator=(findEdge(_graph, u, v)); |
|
495 } |
|
496 |
|
497 /// \brief Constructor. |
|
498 /// |
|
499 /// Construct a new ConEdgeIt which continues the iterating from |
|
500 /// the \c e edge. |
|
501 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} |
|
502 |
|
503 /// \brief Increment operator. |
|
504 /// |
|
505 /// It increments the iterator and gives back the next edge. |
|
506 ConEdgeIt& operator++() { |
|
507 Parent::operator=(findEdge(_graph, _graph.u(*this), |
|
508 _graph.v(*this), *this)); |
|
509 return *this; |
|
510 } |
|
511 private: |
|
512 const Graph& _graph; |
|
513 }; |
|
514 |
|
515 namespace _graph_utils_bits { |
|
516 |
|
517 template <typename Digraph, typename Item, typename RefMap> |
|
518 class MapCopyBase { |
|
519 public: |
|
520 virtual void copy(const Digraph& from, const RefMap& refMap) = 0; |
|
521 |
|
522 virtual ~MapCopyBase() {} |
|
523 }; |
|
524 |
|
525 template <typename Digraph, typename Item, typename RefMap, |
|
526 typename ToMap, typename FromMap> |
|
527 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { |
|
528 public: |
|
529 |
|
530 MapCopy(ToMap& tmap, const FromMap& map) |
|
531 : _tmap(tmap), _map(map) {} |
|
532 |
|
533 virtual void copy(const Digraph& digraph, const RefMap& refMap) { |
|
534 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; |
|
535 for (ItemIt it(digraph); it != INVALID; ++it) { |
|
536 _tmap.set(refMap[it], _map[it]); |
|
537 } |
|
538 } |
|
539 |
|
540 private: |
|
541 ToMap& _tmap; |
|
542 const FromMap& _map; |
|
543 }; |
|
544 |
|
545 template <typename Digraph, typename Item, typename RefMap, typename It> |
|
546 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> { |
|
547 public: |
|
548 |
|
549 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} |
|
550 |
|
551 virtual void copy(const Digraph&, const RefMap& refMap) { |
|
552 _it = refMap[_item]; |
|
553 } |
|
554 |
|
555 private: |
|
556 It& _it; |
|
557 Item _item; |
|
558 }; |
|
559 |
|
560 template <typename Digraph, typename Item, typename RefMap, typename Ref> |
|
561 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> { |
|
562 public: |
|
563 |
|
564 RefCopy(Ref& map) : _map(map) {} |
|
565 |
|
566 virtual void copy(const Digraph& digraph, const RefMap& refMap) { |
|
567 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; |
|
568 for (ItemIt it(digraph); it != INVALID; ++it) { |
|
569 _map.set(it, refMap[it]); |
|
570 } |
|
571 } |
|
572 |
|
573 private: |
|
574 Ref& _map; |
|
575 }; |
|
576 |
|
577 template <typename Digraph, typename Item, typename RefMap, |
|
578 typename CrossRef> |
|
579 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> { |
|
580 public: |
|
581 |
|
582 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {} |
|
583 |
|
584 virtual void copy(const Digraph& digraph, const RefMap& refMap) { |
|
585 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; |
|
586 for (ItemIt it(digraph); it != INVALID; ++it) { |
|
587 _cmap.set(refMap[it], it); |
|
588 } |
|
589 } |
|
590 |
|
591 private: |
|
592 CrossRef& _cmap; |
|
593 }; |
|
594 |
|
595 template <typename Digraph, typename Enable = void> |
|
596 struct DigraphCopySelector { |
|
597 template <typename From, typename NodeRefMap, typename ArcRefMap> |
|
598 static void copy(Digraph &to, const From& from, |
|
599 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { |
|
600 for (typename From::NodeIt it(from); it != INVALID; ++it) { |
|
601 nodeRefMap[it] = to.addNode(); |
|
602 } |
|
603 for (typename From::ArcIt it(from); it != INVALID; ++it) { |
|
604 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], |
|
605 nodeRefMap[from.target(it)]); |
|
606 } |
|
607 } |
|
608 }; |
|
609 |
|
610 template <typename Digraph> |
|
611 struct DigraphCopySelector< |
|
612 Digraph, |
|
613 typename enable_if<typename Digraph::BuildTag, void>::type> |
|
614 { |
|
615 template <typename From, typename NodeRefMap, typename ArcRefMap> |
|
616 static void copy(Digraph &to, const From& from, |
|
617 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { |
|
618 to.build(from, nodeRefMap, arcRefMap); |
|
619 } |
|
620 }; |
|
621 |
|
622 template <typename Graph, typename Enable = void> |
|
623 struct GraphCopySelector { |
|
624 template <typename From, typename NodeRefMap, typename EdgeRefMap> |
|
625 static void copy(Graph &to, const From& from, |
|
626 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { |
|
627 for (typename From::NodeIt it(from); it != INVALID; ++it) { |
|
628 nodeRefMap[it] = to.addNode(); |
|
629 } |
|
630 for (typename From::EdgeIt it(from); it != INVALID; ++it) { |
|
631 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], |
|
632 nodeRefMap[from.v(it)]); |
|
633 } |
|
634 } |
|
635 }; |
|
636 |
|
637 template <typename Graph> |
|
638 struct GraphCopySelector< |
|
639 Graph, |
|
640 typename enable_if<typename Graph::BuildTag, void>::type> |
|
641 { |
|
642 template <typename From, typename NodeRefMap, typename EdgeRefMap> |
|
643 static void copy(Graph &to, const From& from, |
|
644 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { |
|
645 to.build(from, nodeRefMap, edgeRefMap); |
|
646 } |
|
647 }; |
|
648 |
|
649 } |
|
650 |
|
651 /// \brief Class to copy a digraph. |
|
652 /// |
|
653 /// Class to copy a digraph to another digraph (duplicate a digraph). The |
|
654 /// simplest way of using it is through the \c copyDigraph() function. |
|
655 /// |
|
656 /// This class not just make a copy of a graph, but it can create |
|
657 /// references and cross references between the nodes and arcs of |
|
658 /// the two graphs, it can copy maps for use with the newly created |
|
659 /// graph and copy nodes and arcs. |
|
660 /// |
|
661 /// To make a copy from a graph, first an instance of DigraphCopy |
|
662 /// should be created, then the data belongs to the graph should |
|
663 /// assigned to copy. In the end, the \c run() member should be |
|
664 /// called. |
|
665 /// |
|
666 /// The next code copies a graph with several data: |
|
667 ///\code |
|
668 /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); |
|
669 /// // create a reference for the nodes |
|
670 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); |
|
671 /// dc.nodeRef(nr); |
|
672 /// // create a cross reference (inverse) for the arcs |
|
673 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); |
|
674 /// dc.arcCrossRef(acr); |
|
675 /// // copy an arc map |
|
676 /// OrigGraph::ArcMap<double> oamap(orig_graph); |
|
677 /// NewGraph::ArcMap<double> namap(new_graph); |
|
678 /// dc.arcMap(namap, oamap); |
|
679 /// // copy a node |
|
680 /// OrigGraph::Node on; |
|
681 /// NewGraph::Node nn; |
|
682 /// dc.node(nn, on); |
|
683 /// // Executions of copy |
|
684 /// dc.run(); |
|
685 ///\endcode |
|
686 template <typename To, typename From> |
|
687 class DigraphCopy { |
|
688 private: |
|
689 |
|
690 typedef typename From::Node Node; |
|
691 typedef typename From::NodeIt NodeIt; |
|
692 typedef typename From::Arc Arc; |
|
693 typedef typename From::ArcIt ArcIt; |
|
694 |
|
695 typedef typename To::Node TNode; |
|
696 typedef typename To::Arc TArc; |
|
697 |
|
698 typedef typename From::template NodeMap<TNode> NodeRefMap; |
|
699 typedef typename From::template ArcMap<TArc> ArcRefMap; |
|
700 |
|
701 |
|
702 public: |
|
703 |
|
704 |
|
705 /// \brief Constructor for the DigraphCopy. |
|
706 /// |
|
707 /// It copies the content of the \c _from digraph into the |
|
708 /// \c _to digraph. |
|
709 DigraphCopy(To& to, const From& from) |
|
710 : _from(from), _to(to) {} |
|
711 |
|
712 /// \brief Destructor of the DigraphCopy |
|
713 /// |
|
714 /// Destructor of the DigraphCopy |
|
715 ~DigraphCopy() { |
|
716 for (int i = 0; i < int(_node_maps.size()); ++i) { |
|
717 delete _node_maps[i]; |
|
718 } |
|
719 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
|
720 delete _arc_maps[i]; |
|
721 } |
|
722 |
|
723 } |
|
724 |
|
725 /// \brief Copies the node references into the given map. |
|
726 /// |
|
727 /// Copies the node references into the given map. The parameter |
|
728 /// should be a map, which key type is the Node type of the source |
|
729 /// graph, while the value type is the Node type of the |
|
730 /// destination graph. |
|
731 template <typename NodeRef> |
|
732 DigraphCopy& nodeRef(NodeRef& map) { |
|
733 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, |
|
734 NodeRefMap, NodeRef>(map)); |
|
735 return *this; |
|
736 } |
|
737 |
|
738 /// \brief Copies the node cross references into the given map. |
|
739 /// |
|
740 /// Copies the node cross references (reverse references) into |
|
741 /// the given map. The parameter should be a map, which key type |
|
742 /// is the Node type of the destination graph, while the value type is |
|
743 /// the Node type of the source graph. |
|
744 template <typename NodeCrossRef> |
|
745 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { |
|
746 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, |
|
747 NodeRefMap, NodeCrossRef>(map)); |
|
748 return *this; |
|
749 } |
|
750 |
|
751 /// \brief Make copy of the given map. |
|
752 /// |
|
753 /// Makes copy of the given map for the newly created digraph. |
|
754 /// The new map's key type is the destination graph's node type, |
|
755 /// and the copied map's key type is the source graph's node type. |
|
756 template <typename ToMap, typename FromMap> |
|
757 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { |
|
758 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, |
|
759 NodeRefMap, ToMap, FromMap>(tmap, map)); |
|
760 return *this; |
|
761 } |
|
762 |
|
763 /// \brief Make a copy of the given node. |
|
764 /// |
|
765 /// Make a copy of the given node. |
|
766 DigraphCopy& node(TNode& tnode, const Node& snode) { |
|
767 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, |
|
768 NodeRefMap, TNode>(tnode, snode)); |
|
769 return *this; |
|
770 } |
|
771 |
|
772 /// \brief Copies the arc references into the given map. |
|
773 /// |
|
774 /// Copies the arc references into the given map. |
|
775 template <typename ArcRef> |
|
776 DigraphCopy& arcRef(ArcRef& map) { |
|
777 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, |
|
778 ArcRefMap, ArcRef>(map)); |
|
779 return *this; |
|
780 } |
|
781 |
|
782 /// \brief Copies the arc cross references into the given map. |
|
783 /// |
|
784 /// Copies the arc cross references (reverse references) into |
|
785 /// the given map. |
|
786 template <typename ArcCrossRef> |
|
787 DigraphCopy& arcCrossRef(ArcCrossRef& map) { |
|
788 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, |
|
789 ArcRefMap, ArcCrossRef>(map)); |
|
790 return *this; |
|
791 } |
|
792 |
|
793 /// \brief Make copy of the given map. |
|
794 /// |
|
795 /// Makes copy of the given map for the newly created digraph. |
|
796 /// The new map's key type is the to digraph's arc type, |
|
797 /// and the copied map's key type is the from digraph's arc |
|
798 /// type. |
|
799 template <typename ToMap, typename FromMap> |
|
800 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { |
|
801 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, |
|
802 ArcRefMap, ToMap, FromMap>(tmap, map)); |
|
803 return *this; |
|
804 } |
|
805 |
|
806 /// \brief Make a copy of the given arc. |
|
807 /// |
|
808 /// Make a copy of the given arc. |
|
809 DigraphCopy& arc(TArc& tarc, const Arc& sarc) { |
|
810 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, |
|
811 ArcRefMap, TArc>(tarc, sarc)); |
|
812 return *this; |
|
813 } |
|
814 |
|
815 /// \brief Executes the copies. |
|
816 /// |
|
817 /// Executes the copies. |
|
818 void run() { |
|
819 NodeRefMap nodeRefMap(_from); |
|
820 ArcRefMap arcRefMap(_from); |
|
821 _graph_utils_bits::DigraphCopySelector<To>:: |
|
822 copy(_to, _from, nodeRefMap, arcRefMap); |
|
823 for (int i = 0; i < int(_node_maps.size()); ++i) { |
|
824 _node_maps[i]->copy(_from, nodeRefMap); |
|
825 } |
|
826 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
|
827 _arc_maps[i]->copy(_from, arcRefMap); |
|
828 } |
|
829 } |
|
830 |
|
831 protected: |
|
832 |
|
833 |
|
834 const From& _from; |
|
835 To& _to; |
|
836 |
|
837 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > |
|
838 _node_maps; |
|
839 |
|
840 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > |
|
841 _arc_maps; |
|
842 |
|
843 }; |
|
844 |
|
845 /// \brief Copy a digraph to another digraph. |
|
846 /// |
|
847 /// Copy a digraph to another digraph. The complete usage of the |
|
848 /// function is detailed in the DigraphCopy class, but a short |
|
849 /// example shows a basic work: |
|
850 ///\code |
|
851 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); |
|
852 ///\endcode |
|
853 /// |
|
854 /// After the copy the \c nr map will contain the mapping from the |
|
855 /// nodes of the \c from digraph to the nodes of the \c to digraph and |
|
856 /// \c ecr will contain the mapping from the arcs of the \c to digraph |
|
857 /// to the arcs of the \c from digraph. |
|
858 /// |
|
859 /// \see DigraphCopy |
|
860 template <typename To, typename From> |
|
861 DigraphCopy<To, From> copyDigraph(To& to, const From& from) { |
|
862 return DigraphCopy<To, From>(to, from); |
|
863 } |
|
864 |
|
865 /// \brief Class to copy a graph. |
|
866 /// |
|
867 /// Class to copy a graph to another graph (duplicate a graph). The |
|
868 /// simplest way of using it is through the \c copyGraph() function. |
|
869 /// |
|
870 /// This class not just make a copy of a graph, but it can create |
|
871 /// references and cross references between the nodes, edges and arcs of |
|
872 /// the two graphs, it can copy maps for use with the newly created |
|
873 /// graph and copy nodes, edges and arcs. |
|
874 /// |
|
875 /// To make a copy from a graph, first an instance of GraphCopy |
|
876 /// should be created, then the data belongs to the graph should |
|
877 /// assigned to copy. In the end, the \c run() member should be |
|
878 /// called. |
|
879 /// |
|
880 /// The next code copies a graph with several data: |
|
881 ///\code |
|
882 /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); |
|
883 /// // create a reference for the nodes |
|
884 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); |
|
885 /// dc.nodeRef(nr); |
|
886 /// // create a cross reference (inverse) for the edges |
|
887 /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph); |
|
888 /// dc.edgeCrossRef(ecr); |
|
889 /// // copy an arc map |
|
890 /// OrigGraph::ArcMap<double> oamap(orig_graph); |
|
891 /// NewGraph::ArcMap<double> namap(new_graph); |
|
892 /// dc.arcMap(namap, oamap); |
|
893 /// // copy a node |
|
894 /// OrigGraph::Node on; |
|
895 /// NewGraph::Node nn; |
|
896 /// dc.node(nn, on); |
|
897 /// // Executions of copy |
|
898 /// dc.run(); |
|
899 ///\endcode |
|
900 template <typename To, typename From> |
|
901 class GraphCopy { |
|
902 private: |
|
903 |
|
904 typedef typename From::Node Node; |
|
905 typedef typename From::NodeIt NodeIt; |
|
906 typedef typename From::Arc Arc; |
|
907 typedef typename From::ArcIt ArcIt; |
|
908 typedef typename From::Edge Edge; |
|
909 typedef typename From::EdgeIt EdgeIt; |
|
910 |
|
911 typedef typename To::Node TNode; |
|
912 typedef typename To::Arc TArc; |
|
913 typedef typename To::Edge TEdge; |
|
914 |
|
915 typedef typename From::template NodeMap<TNode> NodeRefMap; |
|
916 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; |
|
917 |
|
918 struct ArcRefMap { |
|
919 ArcRefMap(const To& to, const From& from, |
|
920 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) |
|
921 : _to(to), _from(from), |
|
922 _edge_ref(edge_ref), _node_ref(node_ref) {} |
|
923 |
|
924 typedef typename From::Arc Key; |
|
925 typedef typename To::Arc Value; |
|
926 |
|
927 Value operator[](const Key& key) const { |
|
928 bool forward = _from.u(key) != _from.v(key) ? |
|
929 _node_ref[_from.source(key)] == |
|
930 _to.source(_to.direct(_edge_ref[key], true)) : |
|
931 _from.direction(key); |
|
932 return _to.direct(_edge_ref[key], forward); |
|
933 } |
|
934 |
|
935 const To& _to; |
|
936 const From& _from; |
|
937 const EdgeRefMap& _edge_ref; |
|
938 const NodeRefMap& _node_ref; |
|
939 }; |
|
940 |
|
941 |
|
942 public: |
|
943 |
|
944 |
|
945 /// \brief Constructor for the GraphCopy. |
|
946 /// |
|
947 /// It copies the content of the \c _from graph into the |
|
948 /// \c _to graph. |
|
949 GraphCopy(To& to, const From& from) |
|
950 : _from(from), _to(to) {} |
|
951 |
|
952 /// \brief Destructor of the GraphCopy |
|
953 /// |
|
954 /// Destructor of the GraphCopy |
|
955 ~GraphCopy() { |
|
956 for (int i = 0; i < int(_node_maps.size()); ++i) { |
|
957 delete _node_maps[i]; |
|
958 } |
|
959 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
|
960 delete _arc_maps[i]; |
|
961 } |
|
962 for (int i = 0; i < int(_edge_maps.size()); ++i) { |
|
963 delete _edge_maps[i]; |
|
964 } |
|
965 |
|
966 } |
|
967 |
|
968 /// \brief Copies the node references into the given map. |
|
969 /// |
|
970 /// Copies the node references into the given map. |
|
971 template <typename NodeRef> |
|
972 GraphCopy& nodeRef(NodeRef& map) { |
|
973 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, |
|
974 NodeRefMap, NodeRef>(map)); |
|
975 return *this; |
|
976 } |
|
977 |
|
978 /// \brief Copies the node cross references into the given map. |
|
979 /// |
|
980 /// Copies the node cross references (reverse references) into |
|
981 /// the given map. |
|
982 template <typename NodeCrossRef> |
|
983 GraphCopy& nodeCrossRef(NodeCrossRef& map) { |
|
984 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, |
|
985 NodeRefMap, NodeCrossRef>(map)); |
|
986 return *this; |
|
987 } |
|
988 |
|
989 /// \brief Make copy of the given map. |
|
990 /// |
|
991 /// Makes copy of the given map for the newly created graph. |
|
992 /// The new map's key type is the to graph's node type, |
|
993 /// and the copied map's key type is the from graph's node |
|
994 /// type. |
|
995 template <typename ToMap, typename FromMap> |
|
996 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { |
|
997 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, |
|
998 NodeRefMap, ToMap, FromMap>(tmap, map)); |
|
999 return *this; |
|
1000 } |
|
1001 |
|
1002 /// \brief Make a copy of the given node. |
|
1003 /// |
|
1004 /// Make a copy of the given node. |
|
1005 GraphCopy& node(TNode& tnode, const Node& snode) { |
|
1006 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, |
|
1007 NodeRefMap, TNode>(tnode, snode)); |
|
1008 return *this; |
|
1009 } |
|
1010 |
|
1011 /// \brief Copies the arc references into the given map. |
|
1012 /// |
|
1013 /// Copies the arc references into the given map. |
|
1014 template <typename ArcRef> |
|
1015 GraphCopy& arcRef(ArcRef& map) { |
|
1016 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, |
|
1017 ArcRefMap, ArcRef>(map)); |
|
1018 return *this; |
|
1019 } |
|
1020 |
|
1021 /// \brief Copies the arc cross references into the given map. |
|
1022 /// |
|
1023 /// Copies the arc cross references (reverse references) into |
|
1024 /// the given map. |
|
1025 template <typename ArcCrossRef> |
|
1026 GraphCopy& arcCrossRef(ArcCrossRef& map) { |
|
1027 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, |
|
1028 ArcRefMap, ArcCrossRef>(map)); |
|
1029 return *this; |
|
1030 } |
|
1031 |
|
1032 /// \brief Make copy of the given map. |
|
1033 /// |
|
1034 /// Makes copy of the given map for the newly created graph. |
|
1035 /// The new map's key type is the to graph's arc type, |
|
1036 /// and the copied map's key type is the from graph's arc |
|
1037 /// type. |
|
1038 template <typename ToMap, typename FromMap> |
|
1039 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { |
|
1040 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, |
|
1041 ArcRefMap, ToMap, FromMap>(tmap, map)); |
|
1042 return *this; |
|
1043 } |
|
1044 |
|
1045 /// \brief Make a copy of the given arc. |
|
1046 /// |
|
1047 /// Make a copy of the given arc. |
|
1048 GraphCopy& arc(TArc& tarc, const Arc& sarc) { |
|
1049 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, |
|
1050 ArcRefMap, TArc>(tarc, sarc)); |
|
1051 return *this; |
|
1052 } |
|
1053 |
|
1054 /// \brief Copies the edge references into the given map. |
|
1055 /// |
|
1056 /// Copies the edge references into the given map. |
|
1057 template <typename EdgeRef> |
|
1058 GraphCopy& edgeRef(EdgeRef& map) { |
|
1059 _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, |
|
1060 EdgeRefMap, EdgeRef>(map)); |
|
1061 return *this; |
|
1062 } |
|
1063 |
|
1064 /// \brief Copies the edge cross references into the given map. |
|
1065 /// |
|
1066 /// Copies the edge cross references (reverse |
|
1067 /// references) into the given map. |
|
1068 template <typename EdgeCrossRef> |
|
1069 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { |
|
1070 _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, |
|
1071 Edge, EdgeRefMap, EdgeCrossRef>(map)); |
|
1072 return *this; |
|
1073 } |
|
1074 |
|
1075 /// \brief Make copy of the given map. |
|
1076 /// |
|
1077 /// Makes copy of the given map for the newly created graph. |
|
1078 /// The new map's key type is the to graph's edge type, |
|
1079 /// and the copied map's key type is the from graph's edge |
|
1080 /// type. |
|
1081 template <typename ToMap, typename FromMap> |
|
1082 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { |
|
1083 _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, |
|
1084 EdgeRefMap, ToMap, FromMap>(tmap, map)); |
|
1085 return *this; |
|
1086 } |
|
1087 |
|
1088 /// \brief Make a copy of the given edge. |
|
1089 /// |
|
1090 /// Make a copy of the given edge. |
|
1091 GraphCopy& edge(TEdge& tedge, const Edge& sedge) { |
|
1092 _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, |
|
1093 EdgeRefMap, TEdge>(tedge, sedge)); |
|
1094 return *this; |
|
1095 } |
|
1096 |
|
1097 /// \brief Executes the copies. |
|
1098 /// |
|
1099 /// Executes the copies. |
|
1100 void run() { |
|
1101 NodeRefMap nodeRefMap(_from); |
|
1102 EdgeRefMap edgeRefMap(_from); |
|
1103 ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); |
|
1104 _graph_utils_bits::GraphCopySelector<To>:: |
|
1105 copy(_to, _from, nodeRefMap, edgeRefMap); |
|
1106 for (int i = 0; i < int(_node_maps.size()); ++i) { |
|
1107 _node_maps[i]->copy(_from, nodeRefMap); |
|
1108 } |
|
1109 for (int i = 0; i < int(_edge_maps.size()); ++i) { |
|
1110 _edge_maps[i]->copy(_from, edgeRefMap); |
|
1111 } |
|
1112 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
|
1113 _arc_maps[i]->copy(_from, arcRefMap); |
|
1114 } |
|
1115 } |
|
1116 |
|
1117 private: |
|
1118 |
|
1119 const From& _from; |
|
1120 To& _to; |
|
1121 |
|
1122 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > |
|
1123 _node_maps; |
|
1124 |
|
1125 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > |
|
1126 _arc_maps; |
|
1127 |
|
1128 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > |
|
1129 _edge_maps; |
|
1130 |
|
1131 }; |
|
1132 |
|
1133 /// \brief Copy a graph to another graph. |
|
1134 /// |
|
1135 /// Copy a graph to another graph. The complete usage of the |
|
1136 /// function is detailed in the GraphCopy class, but a short |
|
1137 /// example shows a basic work: |
|
1138 ///\code |
|
1139 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); |
|
1140 ///\endcode |
|
1141 /// |
|
1142 /// After the copy the \c nr map will contain the mapping from the |
|
1143 /// nodes of the \c from graph to the nodes of the \c to graph and |
|
1144 /// \c ecr will contain the mapping from the arcs of the \c to graph |
|
1145 /// to the arcs of the \c from graph. |
|
1146 /// |
|
1147 /// \see GraphCopy |
|
1148 template <typename To, typename From> |
|
1149 GraphCopy<To, From> |
|
1150 copyGraph(To& to, const From& from) { |
|
1151 return GraphCopy<To, From>(to, from); |
|
1152 } |
|
1153 |
|
1154 /// @} |
|
1155 |
|
1156 /// \addtogroup graph_maps |
|
1157 /// @{ |
|
1158 |
|
1159 /// Provides an immutable and unique id for each item in the graph. |
|
1160 |
|
1161 /// The IdMap class provides a unique and immutable id for each item of the |
|
1162 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: |
|
1163 /// different items (nodes) get different ids <li>\b immutable: the id of an |
|
1164 /// item (node) does not change (even if you delete other nodes). </ul> |
|
1165 /// Through this map you get access (i.e. can read) the inner id values of |
|
1166 /// the items stored in the graph. This map can be inverted with its member |
|
1167 /// class \c InverseMap or with the \c operator() member. |
|
1168 /// |
|
1169 template <typename _Graph, typename _Item> |
|
1170 class IdMap { |
|
1171 public: |
|
1172 typedef _Graph Graph; |
|
1173 typedef int Value; |
|
1174 typedef _Item Item; |
|
1175 typedef _Item Key; |
|
1176 |
|
1177 /// \brief Constructor. |
|
1178 /// |
|
1179 /// Constructor of the map. |
|
1180 explicit IdMap(const Graph& graph) : _graph(&graph) {} |
|
1181 |
|
1182 /// \brief Gives back the \e id of the item. |
|
1183 /// |
|
1184 /// Gives back the immutable and unique \e id of the item. |
|
1185 int operator[](const Item& item) const { return _graph->id(item);} |
|
1186 |
|
1187 /// \brief Gives back the item by its id. |
|
1188 /// |
|
1189 /// Gives back the item by its id. |
|
1190 Item operator()(int id) { return _graph->fromId(id, Item()); } |
|
1191 |
|
1192 private: |
|
1193 const Graph* _graph; |
|
1194 |
|
1195 public: |
|
1196 |
|
1197 /// \brief The class represents the inverse of its owner (IdMap). |
|
1198 /// |
|
1199 /// The class represents the inverse of its owner (IdMap). |
|
1200 /// \see inverse() |
|
1201 class InverseMap { |
|
1202 public: |
|
1203 |
|
1204 /// \brief Constructor. |
|
1205 /// |
|
1206 /// Constructor for creating an id-to-item map. |
|
1207 explicit InverseMap(const Graph& graph) : _graph(&graph) {} |
|
1208 |
|
1209 /// \brief Constructor. |
|
1210 /// |
|
1211 /// Constructor for creating an id-to-item map. |
|
1212 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} |
|
1213 |
|
1214 /// \brief Gives back the given item from its id. |
|
1215 /// |
|
1216 /// Gives back the given item from its id. |
|
1217 /// |
|
1218 Item operator[](int id) const { return _graph->fromId(id, Item());} |
|
1219 |
|
1220 private: |
|
1221 const Graph* _graph; |
|
1222 }; |
|
1223 |
|
1224 /// \brief Gives back the inverse of the map. |
|
1225 /// |
|
1226 /// Gives back the inverse of the IdMap. |
|
1227 InverseMap inverse() const { return InverseMap(*_graph);} |
|
1228 |
|
1229 }; |
|
1230 |
|
1231 |
|
1232 /// \brief General invertable graph-map type. |
|
1233 |
|
1234 /// This type provides simple invertable graph-maps. |
|
1235 /// The InvertableMap wraps an arbitrary ReadWriteMap |
|
1236 /// and if a key is set to a new value then store it |
|
1237 /// in the inverse map. |
|
1238 /// |
|
1239 /// The values of the map can be accessed |
|
1240 /// with stl compatible forward iterator. |
|
1241 /// |
|
1242 /// \tparam _Graph The graph type. |
|
1243 /// \tparam _Item The item type of the graph. |
|
1244 /// \tparam _Value The value type of the map. |
|
1245 /// |
|
1246 /// \see IterableValueMap |
|
1247 template <typename _Graph, typename _Item, typename _Value> |
|
1248 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { |
|
1249 private: |
|
1250 |
|
1251 typedef DefaultMap<_Graph, _Item, _Value> Map; |
|
1252 typedef _Graph Graph; |
|
1253 |
|
1254 typedef std::map<_Value, _Item> Container; |
|
1255 Container _inv_map; |
|
1256 |
|
1257 public: |
|
1258 |
|
1259 /// The key type of InvertableMap (Node, Arc, Edge). |
|
1260 typedef typename Map::Key Key; |
|
1261 /// The value type of the InvertableMap. |
|
1262 typedef typename Map::Value Value; |
|
1263 |
|
1264 |
|
1265 |
|
1266 /// \brief Constructor. |
|
1267 /// |
|
1268 /// Construct a new InvertableMap for the graph. |
|
1269 /// |
|
1270 explicit InvertableMap(const Graph& graph) : Map(graph) {} |
|
1271 |
|
1272 /// \brief Forward iterator for values. |
|
1273 /// |
|
1274 /// This iterator is an stl compatible forward |
|
1275 /// iterator on the values of the map. The values can |
|
1276 /// be accessed in the [beginValue, endValue) range. |
|
1277 /// |
|
1278 class ValueIterator |
|
1279 : public std::iterator<std::forward_iterator_tag, Value> { |
|
1280 friend class InvertableMap; |
|
1281 private: |
|
1282 ValueIterator(typename Container::const_iterator _it) |
|
1283 : it(_it) {} |
|
1284 public: |
|
1285 |
|
1286 ValueIterator() {} |
|
1287 |
|
1288 ValueIterator& operator++() { ++it; return *this; } |
|
1289 ValueIterator operator++(int) { |
|
1290 ValueIterator tmp(*this); |
|
1291 operator++(); |
|
1292 return tmp; |
|
1293 } |
|
1294 |
|
1295 const Value& operator*() const { return it->first; } |
|
1296 const Value* operator->() const { return &(it->first); } |
|
1297 |
|
1298 bool operator==(ValueIterator jt) const { return it == jt.it; } |
|
1299 bool operator!=(ValueIterator jt) const { return it != jt.it; } |
|
1300 |
|
1301 private: |
|
1302 typename Container::const_iterator it; |
|
1303 }; |
|
1304 |
|
1305 /// \brief Returns an iterator to the first value. |
|
1306 /// |
|
1307 /// Returns an stl compatible iterator to the |
|
1308 /// first value of the map. The values of the |
|
1309 /// map can be accessed in the [beginValue, endValue) |
|
1310 /// range. |
|
1311 ValueIterator beginValue() const { |
|
1312 return ValueIterator(_inv_map.begin()); |
|
1313 } |
|
1314 |
|
1315 /// \brief Returns an iterator after the last value. |
|
1316 /// |
|
1317 /// Returns an stl compatible iterator after the |
|
1318 /// last value of the map. The values of the |
|
1319 /// map can be accessed in the [beginValue, endValue) |
|
1320 /// range. |
|
1321 ValueIterator endValue() const { |
|
1322 return ValueIterator(_inv_map.end()); |
|
1323 } |
|
1324 |
|
1325 /// \brief The setter function of the map. |
|
1326 /// |
|
1327 /// Sets the mapped value. |
|
1328 void set(const Key& key, const Value& val) { |
|
1329 Value oldval = Map::operator[](key); |
|
1330 typename Container::iterator it = _inv_map.find(oldval); |
|
1331 if (it != _inv_map.end() && it->second == key) { |
|
1332 _inv_map.erase(it); |
|
1333 } |
|
1334 _inv_map.insert(make_pair(val, key)); |
|
1335 Map::set(key, val); |
|
1336 } |
|
1337 |
|
1338 /// \brief The getter function of the map. |
|
1339 /// |
|
1340 /// It gives back the value associated with the key. |
|
1341 typename MapTraits<Map>::ConstReturnValue |
|
1342 operator[](const Key& key) const { |
|
1343 return Map::operator[](key); |
|
1344 } |
|
1345 |
|
1346 /// \brief Gives back the item by its value. |
|
1347 /// |
|
1348 /// Gives back the item by its value. |
|
1349 Key operator()(const Value& key) const { |
|
1350 typename Container::const_iterator it = _inv_map.find(key); |
|
1351 return it != _inv_map.end() ? it->second : INVALID; |
|
1352 } |
|
1353 |
|
1354 protected: |
|
1355 |
|
1356 /// \brief Erase the key from the map. |
|
1357 /// |
|
1358 /// Erase the key to the map. It is called by the |
|
1359 /// \c AlterationNotifier. |
|
1360 virtual void erase(const Key& key) { |
|
1361 Value val = Map::operator[](key); |
|
1362 typename Container::iterator it = _inv_map.find(val); |
|
1363 if (it != _inv_map.end() && it->second == key) { |
|
1364 _inv_map.erase(it); |
|
1365 } |
|
1366 Map::erase(key); |
|
1367 } |
|
1368 |
|
1369 /// \brief Erase more keys from the map. |
|
1370 /// |
|
1371 /// Erase more keys from the map. It is called by the |
|
1372 /// \c AlterationNotifier. |
|
1373 virtual void erase(const std::vector<Key>& keys) { |
|
1374 for (int i = 0; i < int(keys.size()); ++i) { |
|
1375 Value val = Map::operator[](keys[i]); |
|
1376 typename Container::iterator it = _inv_map.find(val); |
|
1377 if (it != _inv_map.end() && it->second == keys[i]) { |
|
1378 _inv_map.erase(it); |
|
1379 } |
|
1380 } |
|
1381 Map::erase(keys); |
|
1382 } |
|
1383 |
|
1384 /// \brief Clear the keys from the map and inverse map. |
|
1385 /// |
|
1386 /// Clear the keys from the map and inverse map. It is called by the |
|
1387 /// \c AlterationNotifier. |
|
1388 virtual void clear() { |
|
1389 _inv_map.clear(); |
|
1390 Map::clear(); |
|
1391 } |
|
1392 |
|
1393 public: |
|
1394 |
|
1395 /// \brief The inverse map type. |
|
1396 /// |
|
1397 /// The inverse of this map. The subscript operator of the map |
|
1398 /// gives back always the item what was last assigned to the value. |
|
1399 class InverseMap { |
|
1400 public: |
|
1401 /// \brief Constructor of the InverseMap. |
|
1402 /// |
|
1403 /// Constructor of the InverseMap. |
|
1404 explicit InverseMap(const InvertableMap& inverted) |
|
1405 : _inverted(inverted) {} |
|
1406 |
|
1407 /// The value type of the InverseMap. |
|
1408 typedef typename InvertableMap::Key Value; |
|
1409 /// The key type of the InverseMap. |
|
1410 typedef typename InvertableMap::Value Key; |
|
1411 |
|
1412 /// \brief Subscript operator. |
|
1413 /// |
|
1414 /// Subscript operator. It gives back always the item |
|
1415 /// what was last assigned to the value. |
|
1416 Value operator[](const Key& key) const { |
|
1417 return _inverted(key); |
|
1418 } |
|
1419 |
|
1420 private: |
|
1421 const InvertableMap& _inverted; |
|
1422 }; |
|
1423 |
|
1424 /// \brief It gives back the just readable inverse map. |
|
1425 /// |
|
1426 /// It gives back the just readable inverse map. |
|
1427 InverseMap inverse() const { |
|
1428 return InverseMap(*this); |
|
1429 } |
|
1430 |
|
1431 |
|
1432 |
|
1433 }; |
|
1434 |
|
1435 /// \brief Provides a mutable, continuous and unique descriptor for each |
|
1436 /// item in the graph. |
|
1437 /// |
|
1438 /// The DescriptorMap class provides a unique and continuous (but mutable) |
|
1439 /// descriptor (id) for each item of the same type (e.g. node) in the |
|
1440 /// graph. This id is <ul><li>\b unique: different items (nodes) get |
|
1441 /// different ids <li>\b continuous: the range of the ids is the set of |
|
1442 /// integers between 0 and \c n-1, where \c n is the number of the items of |
|
1443 /// this type (e.g. nodes) (so the id of a node can change if you delete an |
|
1444 /// other node, i.e. this id is mutable). </ul> This map can be inverted |
|
1445 /// with its member class \c InverseMap, or with the \c operator() member. |
|
1446 /// |
|
1447 /// \tparam _Graph The graph class the \c DescriptorMap belongs to. |
|
1448 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or |
|
1449 /// Edge. |
|
1450 template <typename _Graph, typename _Item> |
|
1451 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> { |
|
1452 |
|
1453 typedef _Item Item; |
|
1454 typedef DefaultMap<_Graph, _Item, int> Map; |
|
1455 |
|
1456 public: |
|
1457 /// The graph class of DescriptorMap. |
|
1458 typedef _Graph Graph; |
|
1459 |
|
1460 /// The key type of DescriptorMap (Node, Arc, Edge). |
|
1461 typedef typename Map::Key Key; |
|
1462 /// The value type of DescriptorMap. |
|
1463 typedef typename Map::Value Value; |
|
1464 |
|
1465 /// \brief Constructor. |
|
1466 /// |
|
1467 /// Constructor for descriptor map. |
|
1468 explicit DescriptorMap(const Graph& _graph) : Map(_graph) { |
|
1469 Item it; |
|
1470 const typename Map::Notifier* nf = Map::notifier(); |
|
1471 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
1472 Map::set(it, _inv_map.size()); |
|
1473 _inv_map.push_back(it); |
|
1474 } |
|
1475 } |
|
1476 |
|
1477 protected: |
|
1478 |
|
1479 /// \brief Add a new key to the map. |
|
1480 /// |
|
1481 /// Add a new key to the map. It is called by the |
|
1482 /// \c AlterationNotifier. |
|
1483 virtual void add(const Item& item) { |
|
1484 Map::add(item); |
|
1485 Map::set(item, _inv_map.size()); |
|
1486 _inv_map.push_back(item); |
|
1487 } |
|
1488 |
|
1489 /// \brief Add more new keys to the map. |
|
1490 /// |
|
1491 /// Add more new keys to the map. It is called by the |
|
1492 /// \c AlterationNotifier. |
|
1493 virtual void add(const std::vector<Item>& items) { |
|
1494 Map::add(items); |
|
1495 for (int i = 0; i < int(items.size()); ++i) { |
|
1496 Map::set(items[i], _inv_map.size()); |
|
1497 _inv_map.push_back(items[i]); |
|
1498 } |
|
1499 } |
|
1500 |
|
1501 /// \brief Erase the key from the map. |
|
1502 /// |
|
1503 /// Erase the key from the map. It is called by the |
|
1504 /// \c AlterationNotifier. |
|
1505 virtual void erase(const Item& item) { |
|
1506 Map::set(_inv_map.back(), Map::operator[](item)); |
|
1507 _inv_map[Map::operator[](item)] = _inv_map.back(); |
|
1508 _inv_map.pop_back(); |
|
1509 Map::erase(item); |
|
1510 } |
|
1511 |
|
1512 /// \brief Erase more keys from the map. |
|
1513 /// |
|
1514 /// Erase more keys from the map. It is called by the |
|
1515 /// \c AlterationNotifier. |
|
1516 virtual void erase(const std::vector<Item>& items) { |
|
1517 for (int i = 0; i < int(items.size()); ++i) { |
|
1518 Map::set(_inv_map.back(), Map::operator[](items[i])); |
|
1519 _inv_map[Map::operator[](items[i])] = _inv_map.back(); |
|
1520 _inv_map.pop_back(); |
|
1521 } |
|
1522 Map::erase(items); |
|
1523 } |
|
1524 |
|
1525 /// \brief Build the unique map. |
|
1526 /// |
|
1527 /// Build the unique map. It is called by the |
|
1528 /// \c AlterationNotifier. |
|
1529 virtual void build() { |
|
1530 Map::build(); |
|
1531 Item it; |
|
1532 const typename Map::Notifier* nf = Map::notifier(); |
|
1533 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
1534 Map::set(it, _inv_map.size()); |
|
1535 _inv_map.push_back(it); |
|
1536 } |
|
1537 } |
|
1538 |
|
1539 /// \brief Clear the keys from the map. |
|
1540 /// |
|
1541 /// Clear the keys from the map. It is called by the |
|
1542 /// \c AlterationNotifier. |
|
1543 virtual void clear() { |
|
1544 _inv_map.clear(); |
|
1545 Map::clear(); |
|
1546 } |
|
1547 |
|
1548 public: |
|
1549 |
|
1550 /// \brief Returns the maximal value plus one. |
|
1551 /// |
|
1552 /// Returns the maximal value plus one in the map. |
|
1553 unsigned int size() const { |
|
1554 return _inv_map.size(); |
|
1555 } |
|
1556 |
|
1557 /// \brief Swaps the position of the two items in the map. |
|
1558 /// |
|
1559 /// Swaps the position of the two items in the map. |
|
1560 void swap(const Item& p, const Item& q) { |
|
1561 int pi = Map::operator[](p); |
|
1562 int qi = Map::operator[](q); |
|
1563 Map::set(p, qi); |
|
1564 _inv_map[qi] = p; |
|
1565 Map::set(q, pi); |
|
1566 _inv_map[pi] = q; |
|
1567 } |
|
1568 |
|
1569 /// \brief Gives back the \e descriptor of the item. |
|
1570 /// |
|
1571 /// Gives back the mutable and unique \e descriptor of the map. |
|
1572 int operator[](const Item& item) const { |
|
1573 return Map::operator[](item); |
|
1574 } |
|
1575 |
|
1576 /// \brief Gives back the item by its descriptor. |
|
1577 /// |
|
1578 /// Gives back th item by its descriptor. |
|
1579 Item operator()(int id) const { |
|
1580 return _inv_map[id]; |
|
1581 } |
|
1582 |
|
1583 private: |
|
1584 |
|
1585 typedef std::vector<Item> Container; |
|
1586 Container _inv_map; |
|
1587 |
|
1588 public: |
|
1589 /// \brief The inverse map type of DescriptorMap. |
|
1590 /// |
|
1591 /// The inverse map type of DescriptorMap. |
|
1592 class InverseMap { |
|
1593 public: |
|
1594 /// \brief Constructor of the InverseMap. |
|
1595 /// |
|
1596 /// Constructor of the InverseMap. |
|
1597 explicit InverseMap(const DescriptorMap& inverted) |
|
1598 : _inverted(inverted) {} |
|
1599 |
|
1600 |
|
1601 /// The value type of the InverseMap. |
|
1602 typedef typename DescriptorMap::Key Value; |
|
1603 /// The key type of the InverseMap. |
|
1604 typedef typename DescriptorMap::Value Key; |
|
1605 |
|
1606 /// \brief Subscript operator. |
|
1607 /// |
|
1608 /// Subscript operator. It gives back the item |
|
1609 /// that the descriptor belongs to currently. |
|
1610 Value operator[](const Key& key) const { |
|
1611 return _inverted(key); |
|
1612 } |
|
1613 |
|
1614 /// \brief Size of the map. |
|
1615 /// |
|
1616 /// Returns the size of the map. |
|
1617 unsigned int size() const { |
|
1618 return _inverted.size(); |
|
1619 } |
|
1620 |
|
1621 private: |
|
1622 const DescriptorMap& _inverted; |
|
1623 }; |
|
1624 |
|
1625 /// \brief Gives back the inverse of the map. |
|
1626 /// |
|
1627 /// Gives back the inverse of the map. |
|
1628 const InverseMap inverse() const { |
|
1629 return InverseMap(*this); |
|
1630 } |
|
1631 }; |
|
1632 |
|
1633 /// \brief Returns the source of the given arc. |
|
1634 /// |
|
1635 /// The SourceMap gives back the source Node of the given arc. |
|
1636 /// \see TargetMap |
|
1637 template <typename Digraph> |
|
1638 class SourceMap { |
|
1639 public: |
|
1640 |
|
1641 typedef typename Digraph::Node Value; |
|
1642 typedef typename Digraph::Arc Key; |
|
1643 |
|
1644 /// \brief Constructor |
|
1645 /// |
|
1646 /// Constructor |
|
1647 /// \param _digraph The digraph that the map belongs to. |
|
1648 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} |
|
1649 |
|
1650 /// \brief The subscript operator. |
|
1651 /// |
|
1652 /// The subscript operator. |
|
1653 /// \param arc The arc |
|
1654 /// \return The source of the arc |
|
1655 Value operator[](const Key& arc) const { |
|
1656 return _digraph.source(arc); |
|
1657 } |
|
1658 |
|
1659 private: |
|
1660 const Digraph& _digraph; |
|
1661 }; |
|
1662 |
|
1663 /// \brief Returns a \ref SourceMap class. |
|
1664 /// |
|
1665 /// This function just returns an \ref SourceMap class. |
|
1666 /// \relates SourceMap |
|
1667 template <typename Digraph> |
|
1668 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) { |
|
1669 return SourceMap<Digraph>(digraph); |
|
1670 } |
|
1671 |
|
1672 /// \brief Returns the target of the given arc. |
|
1673 /// |
|
1674 /// The TargetMap gives back the target Node of the given arc. |
|
1675 /// \see SourceMap |
|
1676 template <typename Digraph> |
|
1677 class TargetMap { |
|
1678 public: |
|
1679 |
|
1680 typedef typename Digraph::Node Value; |
|
1681 typedef typename Digraph::Arc Key; |
|
1682 |
|
1683 /// \brief Constructor |
|
1684 /// |
|
1685 /// Constructor |
|
1686 /// \param _digraph The digraph that the map belongs to. |
|
1687 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} |
|
1688 |
|
1689 /// \brief The subscript operator. |
|
1690 /// |
|
1691 /// The subscript operator. |
|
1692 /// \param e The arc |
|
1693 /// \return The target of the arc |
|
1694 Value operator[](const Key& e) const { |
|
1695 return _digraph.target(e); |
|
1696 } |
|
1697 |
|
1698 private: |
|
1699 const Digraph& _digraph; |
|
1700 }; |
|
1701 |
|
1702 /// \brief Returns a \ref TargetMap class. |
|
1703 /// |
|
1704 /// This function just returns a \ref TargetMap class. |
|
1705 /// \relates TargetMap |
|
1706 template <typename Digraph> |
|
1707 inline TargetMap<Digraph> targetMap(const Digraph& digraph) { |
|
1708 return TargetMap<Digraph>(digraph); |
|
1709 } |
|
1710 |
|
1711 /// \brief Returns the "forward" directed arc view of an edge. |
|
1712 /// |
|
1713 /// Returns the "forward" directed arc view of an edge. |
|
1714 /// \see BackwardMap |
|
1715 template <typename Graph> |
|
1716 class ForwardMap { |
|
1717 public: |
|
1718 |
|
1719 typedef typename Graph::Arc Value; |
|
1720 typedef typename Graph::Edge Key; |
|
1721 |
|
1722 /// \brief Constructor |
|
1723 /// |
|
1724 /// Constructor |
|
1725 /// \param _graph The graph that the map belongs to. |
|
1726 explicit ForwardMap(const Graph& graph) : _graph(graph) {} |
|
1727 |
|
1728 /// \brief The subscript operator. |
|
1729 /// |
|
1730 /// The subscript operator. |
|
1731 /// \param key An edge |
|
1732 /// \return The "forward" directed arc view of edge |
|
1733 Value operator[](const Key& key) const { |
|
1734 return _graph.direct(key, true); |
|
1735 } |
|
1736 |
|
1737 private: |
|
1738 const Graph& _graph; |
|
1739 }; |
|
1740 |
|
1741 /// \brief Returns a \ref ForwardMap class. |
|
1742 /// |
|
1743 /// This function just returns an \ref ForwardMap class. |
|
1744 /// \relates ForwardMap |
|
1745 template <typename Graph> |
|
1746 inline ForwardMap<Graph> forwardMap(const Graph& graph) { |
|
1747 return ForwardMap<Graph>(graph); |
|
1748 } |
|
1749 |
|
1750 /// \brief Returns the "backward" directed arc view of an edge. |
|
1751 /// |
|
1752 /// Returns the "backward" directed arc view of an edge. |
|
1753 /// \see ForwardMap |
|
1754 template <typename Graph> |
|
1755 class BackwardMap { |
|
1756 public: |
|
1757 |
|
1758 typedef typename Graph::Arc Value; |
|
1759 typedef typename Graph::Edge Key; |
|
1760 |
|
1761 /// \brief Constructor |
|
1762 /// |
|
1763 /// Constructor |
|
1764 /// \param _graph The graph that the map belongs to. |
|
1765 explicit BackwardMap(const Graph& graph) : _graph(graph) {} |
|
1766 |
|
1767 /// \brief The subscript operator. |
|
1768 /// |
|
1769 /// The subscript operator. |
|
1770 /// \param key An edge |
|
1771 /// \return The "backward" directed arc view of edge |
|
1772 Value operator[](const Key& key) const { |
|
1773 return _graph.direct(key, false); |
|
1774 } |
|
1775 |
|
1776 private: |
|
1777 const Graph& _graph; |
|
1778 }; |
|
1779 |
|
1780 /// \brief Returns a \ref BackwardMap class |
|
1781 |
|
1782 /// This function just returns a \ref BackwardMap class. |
|
1783 /// \relates BackwardMap |
|
1784 template <typename Graph> |
|
1785 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
|
1786 return BackwardMap<Graph>(graph); |
|
1787 } |
|
1788 |
|
1789 /// \brief Potential difference map |
|
1790 /// |
|
1791 /// If there is an potential map on the nodes then we |
|
1792 /// can get an arc map as we get the substraction of the |
|
1793 /// values of the target and source. |
|
1794 template <typename Digraph, typename NodeMap> |
|
1795 class PotentialDifferenceMap { |
|
1796 public: |
|
1797 typedef typename Digraph::Arc Key; |
|
1798 typedef typename NodeMap::Value Value; |
|
1799 |
|
1800 /// \brief Constructor |
|
1801 /// |
|
1802 /// Contructor of the map |
|
1803 explicit PotentialDifferenceMap(const Digraph& digraph, |
|
1804 const NodeMap& potential) |
|
1805 : _digraph(digraph), _potential(potential) {} |
|
1806 |
|
1807 /// \brief Const subscription operator |
|
1808 /// |
|
1809 /// Const subscription operator |
|
1810 Value operator[](const Key& arc) const { |
|
1811 return _potential[_digraph.target(arc)] - |
|
1812 _potential[_digraph.source(arc)]; |
|
1813 } |
|
1814 |
|
1815 private: |
|
1816 const Digraph& _digraph; |
|
1817 const NodeMap& _potential; |
|
1818 }; |
|
1819 |
|
1820 /// \brief Returns a PotentialDifferenceMap. |
|
1821 /// |
|
1822 /// This function just returns a PotentialDifferenceMap. |
|
1823 /// \relates PotentialDifferenceMap |
|
1824 template <typename Digraph, typename NodeMap> |
|
1825 PotentialDifferenceMap<Digraph, NodeMap> |
|
1826 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { |
|
1827 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential); |
|
1828 } |
|
1829 |
|
1830 /// \brief Map of the node in-degrees. |
|
1831 /// |
|
1832 /// This map returns the in-degree of a node. Once it is constructed, |
|
1833 /// the degrees are stored in a standard NodeMap, so each query is done |
|
1834 /// in constant time. On the other hand, the values are updated automatically |
|
1835 /// whenever the digraph changes. |
|
1836 /// |
|
1837 /// \warning Besides addNode() and addArc(), a digraph structure may provide |
|
1838 /// alternative ways to modify the digraph. The correct behavior of InDegMap |
|
1839 /// is not guarantied if these additional features are used. For example |
|
1840 /// the functions \ref ListDigraph::changeSource() "changeSource()", |
|
1841 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
|
1842 /// \ref ListDigraph::reverseArc() "reverseArc()" |
|
1843 /// of \ref ListDigraph will \e not update the degree values correctly. |
|
1844 /// |
|
1845 /// \sa OutDegMap |
|
1846 |
|
1847 template <typename _Digraph> |
|
1848 class InDegMap |
|
1849 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> |
|
1850 ::ItemNotifier::ObserverBase { |
|
1851 |
|
1852 public: |
|
1853 |
|
1854 typedef _Digraph Digraph; |
|
1855 typedef int Value; |
|
1856 typedef typename Digraph::Node Key; |
|
1857 |
|
1858 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> |
|
1859 ::ItemNotifier::ObserverBase Parent; |
|
1860 |
|
1861 private: |
|
1862 |
|
1863 class AutoNodeMap : public DefaultMap<Digraph, Key, int> { |
|
1864 public: |
|
1865 |
|
1866 typedef DefaultMap<Digraph, Key, int> Parent; |
|
1867 |
|
1868 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} |
|
1869 |
|
1870 virtual void add(const Key& key) { |
|
1871 Parent::add(key); |
|
1872 Parent::set(key, 0); |
|
1873 } |
|
1874 |
|
1875 virtual void add(const std::vector<Key>& keys) { |
|
1876 Parent::add(keys); |
|
1877 for (int i = 0; i < int(keys.size()); ++i) { |
|
1878 Parent::set(keys[i], 0); |
|
1879 } |
|
1880 } |
|
1881 |
|
1882 virtual void build() { |
|
1883 Parent::build(); |
|
1884 Key it; |
|
1885 typename Parent::Notifier* nf = Parent::notifier(); |
|
1886 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
1887 Parent::set(it, 0); |
|
1888 } |
|
1889 } |
|
1890 }; |
|
1891 |
|
1892 public: |
|
1893 |
|
1894 /// \brief Constructor. |
|
1895 /// |
|
1896 /// Constructor for creating in-degree map. |
|
1897 explicit InDegMap(const Digraph& digraph) |
|
1898 : _digraph(digraph), _deg(digraph) { |
|
1899 Parent::attach(_digraph.notifier(typename Digraph::Arc())); |
|
1900 |
|
1901 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
|
1902 _deg[it] = countInArcs(_digraph, it); |
|
1903 } |
|
1904 } |
|
1905 |
|
1906 /// Gives back the in-degree of a Node. |
|
1907 int operator[](const Key& key) const { |
|
1908 return _deg[key]; |
|
1909 } |
|
1910 |
|
1911 protected: |
|
1912 |
|
1913 typedef typename Digraph::Arc Arc; |
|
1914 |
|
1915 virtual void add(const Arc& arc) { |
|
1916 ++_deg[_digraph.target(arc)]; |
|
1917 } |
|
1918 |
|
1919 virtual void add(const std::vector<Arc>& arcs) { |
|
1920 for (int i = 0; i < int(arcs.size()); ++i) { |
|
1921 ++_deg[_digraph.target(arcs[i])]; |
|
1922 } |
|
1923 } |
|
1924 |
|
1925 virtual void erase(const Arc& arc) { |
|
1926 --_deg[_digraph.target(arc)]; |
|
1927 } |
|
1928 |
|
1929 virtual void erase(const std::vector<Arc>& arcs) { |
|
1930 for (int i = 0; i < int(arcs.size()); ++i) { |
|
1931 --_deg[_digraph.target(arcs[i])]; |
|
1932 } |
|
1933 } |
|
1934 |
|
1935 virtual void build() { |
|
1936 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
|
1937 _deg[it] = countInArcs(_digraph, it); |
|
1938 } |
|
1939 } |
|
1940 |
|
1941 virtual void clear() { |
|
1942 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
|
1943 _deg[it] = 0; |
|
1944 } |
|
1945 } |
|
1946 private: |
|
1947 |
|
1948 const Digraph& _digraph; |
|
1949 AutoNodeMap _deg; |
|
1950 }; |
|
1951 |
|
1952 /// \brief Map of the node out-degrees. |
|
1953 /// |
|
1954 /// This map returns the out-degree of a node. Once it is constructed, |
|
1955 /// the degrees are stored in a standard NodeMap, so each query is done |
|
1956 /// in constant time. On the other hand, the values are updated automatically |
|
1957 /// whenever the digraph changes. |
|
1958 /// |
|
1959 /// \warning Besides addNode() and addArc(), a digraph structure may provide |
|
1960 /// alternative ways to modify the digraph. The correct behavior of OutDegMap |
|
1961 /// is not guarantied if these additional features are used. For example |
|
1962 /// the functions \ref ListDigraph::changeSource() "changeSource()", |
|
1963 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
|
1964 /// \ref ListDigraph::reverseArc() "reverseArc()" |
|
1965 /// of \ref ListDigraph will \e not update the degree values correctly. |
|
1966 /// |
|
1967 /// \sa InDegMap |
|
1968 |
|
1969 template <typename _Digraph> |
|
1970 class OutDegMap |
|
1971 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> |
|
1972 ::ItemNotifier::ObserverBase { |
|
1973 |
|
1974 public: |
|
1975 |
|
1976 typedef _Digraph Digraph; |
|
1977 typedef int Value; |
|
1978 typedef typename Digraph::Node Key; |
|
1979 |
|
1980 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> |
|
1981 ::ItemNotifier::ObserverBase Parent; |
|
1982 |
|
1983 private: |
|
1984 |
|
1985 class AutoNodeMap : public DefaultMap<Digraph, Key, int> { |
|
1986 public: |
|
1987 |
|
1988 typedef DefaultMap<Digraph, Key, int> Parent; |
|
1989 |
|
1990 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} |
|
1991 |
|
1992 virtual void add(const Key& key) { |
|
1993 Parent::add(key); |
|
1994 Parent::set(key, 0); |
|
1995 } |
|
1996 virtual void add(const std::vector<Key>& keys) { |
|
1997 Parent::add(keys); |
|
1998 for (int i = 0; i < int(keys.size()); ++i) { |
|
1999 Parent::set(keys[i], 0); |
|
2000 } |
|
2001 } |
|
2002 virtual void build() { |
|
2003 Parent::build(); |
|
2004 Key it; |
|
2005 typename Parent::Notifier* nf = Parent::notifier(); |
|
2006 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
2007 Parent::set(it, 0); |
|
2008 } |
|
2009 } |
|
2010 }; |
|
2011 |
|
2012 public: |
|
2013 |
|
2014 /// \brief Constructor. |
|
2015 /// |
|
2016 /// Constructor for creating out-degree map. |
|
2017 explicit OutDegMap(const Digraph& digraph) |
|
2018 : _digraph(digraph), _deg(digraph) { |
|
2019 Parent::attach(_digraph.notifier(typename Digraph::Arc())); |
|
2020 |
|
2021 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
|
2022 _deg[it] = countOutArcs(_digraph, it); |
|
2023 } |
|
2024 } |
|
2025 |
|
2026 /// Gives back the out-degree of a Node. |
|
2027 int operator[](const Key& key) const { |
|
2028 return _deg[key]; |
|
2029 } |
|
2030 |
|
2031 protected: |
|
2032 |
|
2033 typedef typename Digraph::Arc Arc; |
|
2034 |
|
2035 virtual void add(const Arc& arc) { |
|
2036 ++_deg[_digraph.source(arc)]; |
|
2037 } |
|
2038 |
|
2039 virtual void add(const std::vector<Arc>& arcs) { |
|
2040 for (int i = 0; i < int(arcs.size()); ++i) { |
|
2041 ++_deg[_digraph.source(arcs[i])]; |
|
2042 } |
|
2043 } |
|
2044 |
|
2045 virtual void erase(const Arc& arc) { |
|
2046 --_deg[_digraph.source(arc)]; |
|
2047 } |
|
2048 |
|
2049 virtual void erase(const std::vector<Arc>& arcs) { |
|
2050 for (int i = 0; i < int(arcs.size()); ++i) { |
|
2051 --_deg[_digraph.source(arcs[i])]; |
|
2052 } |
|
2053 } |
|
2054 |
|
2055 virtual void build() { |
|
2056 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
|
2057 _deg[it] = countOutArcs(_digraph, it); |
|
2058 } |
|
2059 } |
|
2060 |
|
2061 virtual void clear() { |
|
2062 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { |
|
2063 _deg[it] = 0; |
|
2064 } |
|
2065 } |
|
2066 private: |
|
2067 |
|
2068 const Digraph& _digraph; |
|
2069 AutoNodeMap _deg; |
|
2070 }; |
|
2071 |
|
2072 |
|
2073 ///Dynamic arc look up between given endpoints. |
|
2074 |
|
2075 ///\ingroup gutils |
|
2076 ///Using this class, you can find an arc in a digraph from a given |
|
2077 ///source to a given target in amortized time <em>O(log d)</em>, |
|
2078 ///where <em>d</em> is the out-degree of the source node. |
|
2079 /// |
|
2080 ///It is possible to find \e all parallel arcs between two nodes with |
|
2081 ///the \c findFirst() and \c findNext() members. |
|
2082 /// |
|
2083 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your |
|
2084 ///digraph is not changed so frequently. |
|
2085 /// |
|
2086 ///This class uses a self-adjusting binary search tree, Sleator's |
|
2087 ///and Tarjan's Splay tree for guarantee the logarithmic amortized |
|
2088 ///time bound for arc lookups. This class also guarantees the |
|
2089 ///optimal time bound in a constant factor for any distribution of |
|
2090 ///queries. |
|
2091 /// |
|
2092 ///\tparam G The type of the underlying digraph. |
|
2093 /// |
|
2094 ///\sa ArcLookUp |
|
2095 ///\sa AllArcLookUp |
|
2096 template<class G> |
|
2097 class DynArcLookUp |
|
2098 : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase |
|
2099 { |
|
2100 public: |
|
2101 typedef typename ItemSetTraits<G, typename G::Arc> |
|
2102 ::ItemNotifier::ObserverBase Parent; |
|
2103 |
|
2104 TEMPLATE_DIGRAPH_TYPEDEFS(G); |
|
2105 typedef G Digraph; |
|
2106 |
|
2107 protected: |
|
2108 |
|
2109 class AutoNodeMap : public DefaultMap<G, Node, Arc> { |
|
2110 public: |
|
2111 |
|
2112 typedef DefaultMap<G, Node, Arc> Parent; |
|
2113 |
|
2114 AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {} |
|
2115 |
|
2116 virtual void add(const Node& node) { |
|
2117 Parent::add(node); |
|
2118 Parent::set(node, INVALID); |
|
2119 } |
|
2120 |
|
2121 virtual void add(const std::vector<Node>& nodes) { |
|
2122 Parent::add(nodes); |
|
2123 for (int i = 0; i < int(nodes.size()); ++i) { |
|
2124 Parent::set(nodes[i], INVALID); |
|
2125 } |
|
2126 } |
|
2127 |
|
2128 virtual void build() { |
|
2129 Parent::build(); |
|
2130 Node it; |
|
2131 typename Parent::Notifier* nf = Parent::notifier(); |
|
2132 for (nf->first(it); it != INVALID; nf->next(it)) { |
|
2133 Parent::set(it, INVALID); |
|
2134 } |
|
2135 } |
|
2136 }; |
|
2137 |
|
2138 const Digraph &_g; |
|
2139 AutoNodeMap _head; |
|
2140 typename Digraph::template ArcMap<Arc> _parent; |
|
2141 typename Digraph::template ArcMap<Arc> _left; |
|
2142 typename Digraph::template ArcMap<Arc> _right; |
|
2143 |
|
2144 class ArcLess { |
|
2145 const Digraph &g; |
|
2146 public: |
|
2147 ArcLess(const Digraph &_g) : g(_g) {} |
|
2148 bool operator()(Arc a,Arc b) const |
|
2149 { |
|
2150 return g.target(a)<g.target(b); |
|
2151 } |
|
2152 }; |
|
2153 |
|
2154 public: |
|
2155 |
|
2156 ///Constructor |
|
2157 |
|
2158 ///Constructor. |
|
2159 /// |
|
2160 ///It builds up the search database. |
|
2161 DynArcLookUp(const Digraph &g) |
|
2162 : _g(g),_head(g),_parent(g),_left(g),_right(g) |
|
2163 { |
|
2164 Parent::attach(_g.notifier(typename Digraph::Arc())); |
|
2165 refresh(); |
|
2166 } |
|
2167 |
|
2168 protected: |
|
2169 |
|
2170 virtual void add(const Arc& arc) { |
|
2171 insert(arc); |
|
2172 } |
|
2173 |
|
2174 virtual void add(const std::vector<Arc>& arcs) { |
|
2175 for (int i = 0; i < int(arcs.size()); ++i) { |
|
2176 insert(arcs[i]); |
|
2177 } |
|
2178 } |
|
2179 |
|
2180 virtual void erase(const Arc& arc) { |
|
2181 remove(arc); |
|
2182 } |
|
2183 |
|
2184 virtual void erase(const std::vector<Arc>& arcs) { |
|
2185 for (int i = 0; i < int(arcs.size()); ++i) { |
|
2186 remove(arcs[i]); |
|
2187 } |
|
2188 } |
|
2189 |
|
2190 virtual void build() { |
|
2191 refresh(); |
|
2192 } |
|
2193 |
|
2194 virtual void clear() { |
|
2195 for(NodeIt n(_g);n!=INVALID;++n) { |
|
2196 _head.set(n, INVALID); |
|
2197 } |
|
2198 } |
|
2199 |
|
2200 void insert(Arc arc) { |
|
2201 Node s = _g.source(arc); |
|
2202 Node t = _g.target(arc); |
|
2203 _left.set(arc, INVALID); |
|
2204 _right.set(arc, INVALID); |
|
2205 |
|
2206 Arc e = _head[s]; |
|
2207 if (e == INVALID) { |
|
2208 _head.set(s, arc); |
|
2209 _parent.set(arc, INVALID); |
|
2210 return; |
|
2211 } |
|
2212 while (true) { |
|
2213 if (t < _g.target(e)) { |
|
2214 if (_left[e] == INVALID) { |
|
2215 _left.set(e, arc); |
|
2216 _parent.set(arc, e); |
|
2217 splay(arc); |
|
2218 return; |
|
2219 } else { |
|
2220 e = _left[e]; |
|
2221 } |
|
2222 } else { |
|
2223 if (_right[e] == INVALID) { |
|
2224 _right.set(e, arc); |
|
2225 _parent.set(arc, e); |
|
2226 splay(arc); |
|
2227 return; |
|
2228 } else { |
|
2229 e = _right[e]; |
|
2230 } |
|
2231 } |
|
2232 } |
|
2233 } |
|
2234 |
|
2235 void remove(Arc arc) { |
|
2236 if (_left[arc] == INVALID) { |
|
2237 if (_right[arc] != INVALID) { |
|
2238 _parent.set(_right[arc], _parent[arc]); |
|
2239 } |
|
2240 if (_parent[arc] != INVALID) { |
|
2241 if (_left[_parent[arc]] == arc) { |
|
2242 _left.set(_parent[arc], _right[arc]); |
|
2243 } else { |
|
2244 _right.set(_parent[arc], _right[arc]); |
|
2245 } |
|
2246 } else { |
|
2247 _head.set(_g.source(arc), _right[arc]); |
|
2248 } |
|
2249 } else if (_right[arc] == INVALID) { |
|
2250 _parent.set(_left[arc], _parent[arc]); |
|
2251 if (_parent[arc] != INVALID) { |
|
2252 if (_left[_parent[arc]] == arc) { |
|
2253 _left.set(_parent[arc], _left[arc]); |
|
2254 } else { |
|
2255 _right.set(_parent[arc], _left[arc]); |
|
2256 } |
|
2257 } else { |
|
2258 _head.set(_g.source(arc), _left[arc]); |
|
2259 } |
|
2260 } else { |
|
2261 Arc e = _left[arc]; |
|
2262 if (_right[e] != INVALID) { |
|
2263 e = _right[e]; |
|
2264 while (_right[e] != INVALID) { |
|
2265 e = _right[e]; |
|
2266 } |
|
2267 Arc s = _parent[e]; |
|
2268 _right.set(_parent[e], _left[e]); |
|
2269 if (_left[e] != INVALID) { |
|
2270 _parent.set(_left[e], _parent[e]); |
|
2271 } |
|
2272 |
|
2273 _left.set(e, _left[arc]); |
|
2274 _parent.set(_left[arc], e); |
|
2275 _right.set(e, _right[arc]); |
|
2276 _parent.set(_right[arc], e); |
|
2277 |
|
2278 _parent.set(e, _parent[arc]); |
|
2279 if (_parent[arc] != INVALID) { |
|
2280 if (_left[_parent[arc]] == arc) { |
|
2281 _left.set(_parent[arc], e); |
|
2282 } else { |
|
2283 _right.set(_parent[arc], e); |
|
2284 } |
|
2285 } |
|
2286 splay(s); |
|
2287 } else { |
|
2288 _right.set(e, _right[arc]); |
|
2289 _parent.set(_right[arc], e); |
|
2290 |
|
2291 if (_parent[arc] != INVALID) { |
|
2292 if (_left[_parent[arc]] == arc) { |
|
2293 _left.set(_parent[arc], e); |
|
2294 } else { |
|
2295 _right.set(_parent[arc], e); |
|
2296 } |
|
2297 } else { |
|
2298 _head.set(_g.source(arc), e); |
|
2299 } |
|
2300 } |
|
2301 } |
|
2302 } |
|
2303 |
|
2304 Arc refreshRec(std::vector<Arc> &v,int a,int b) |
|
2305 { |
|
2306 int m=(a+b)/2; |
|
2307 Arc me=v[m]; |
|
2308 if (a < m) { |
|
2309 Arc left = refreshRec(v,a,m-1); |
|
2310 _left.set(me, left); |
|
2311 _parent.set(left, me); |
|
2312 } else { |
|
2313 _left.set(me, INVALID); |
|
2314 } |
|
2315 if (m < b) { |
|
2316 Arc right = refreshRec(v,m+1,b); |
|
2317 _right.set(me, right); |
|
2318 _parent.set(right, me); |
|
2319 } else { |
|
2320 _right.set(me, INVALID); |
|
2321 } |
|
2322 return me; |
|
2323 } |
|
2324 |
|
2325 void refresh() { |
|
2326 for(NodeIt n(_g);n!=INVALID;++n) { |
|
2327 std::vector<Arc> v; |
|
2328 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); |
|
2329 if(v.size()) { |
|
2330 std::sort(v.begin(),v.end(),ArcLess(_g)); |
|
2331 Arc head = refreshRec(v,0,v.size()-1); |
|
2332 _head.set(n, head); |
|
2333 _parent.set(head, INVALID); |
|
2334 } |
|
2335 else _head.set(n, INVALID); |
|
2336 } |
|
2337 } |
|
2338 |
|
2339 void zig(Arc v) { |
|
2340 Arc w = _parent[v]; |
|
2341 _parent.set(v, _parent[w]); |
|
2342 _parent.set(w, v); |
|
2343 _left.set(w, _right[v]); |
|
2344 _right.set(v, w); |
|
2345 if (_parent[v] != INVALID) { |
|
2346 if (_right[_parent[v]] == w) { |
|
2347 _right.set(_parent[v], v); |
|
2348 } else { |
|
2349 _left.set(_parent[v], v); |
|
2350 } |
|
2351 } |
|
2352 if (_left[w] != INVALID){ |
|
2353 _parent.set(_left[w], w); |
|
2354 } |
|
2355 } |
|
2356 |
|
2357 void zag(Arc v) { |
|
2358 Arc w = _parent[v]; |
|
2359 _parent.set(v, _parent[w]); |
|
2360 _parent.set(w, v); |
|
2361 _right.set(w, _left[v]); |
|
2362 _left.set(v, w); |
|
2363 if (_parent[v] != INVALID){ |
|
2364 if (_left[_parent[v]] == w) { |
|
2365 _left.set(_parent[v], v); |
|
2366 } else { |
|
2367 _right.set(_parent[v], v); |
|
2368 } |
|
2369 } |
|
2370 if (_right[w] != INVALID){ |
|
2371 _parent.set(_right[w], w); |
|
2372 } |
|
2373 } |
|
2374 |
|
2375 void splay(Arc v) { |
|
2376 while (_parent[v] != INVALID) { |
|
2377 if (v == _left[_parent[v]]) { |
|
2378 if (_parent[_parent[v]] == INVALID) { |
|
2379 zig(v); |
|
2380 } else { |
|
2381 if (_parent[v] == _left[_parent[_parent[v]]]) { |
|
2382 zig(_parent[v]); |
|
2383 zig(v); |
|
2384 } else { |
|
2385 zig(v); |
|
2386 zag(v); |
|
2387 } |
|
2388 } |
|
2389 } else { |
|
2390 if (_parent[_parent[v]] == INVALID) { |
|
2391 zag(v); |
|
2392 } else { |
|
2393 if (_parent[v] == _left[_parent[_parent[v]]]) { |
|
2394 zag(v); |
|
2395 zig(v); |
|
2396 } else { |
|
2397 zag(_parent[v]); |
|
2398 zag(v); |
|
2399 } |
|
2400 } |
|
2401 } |
|
2402 } |
|
2403 _head[_g.source(v)] = v; |
|
2404 } |
|
2405 |
|
2406 |
|
2407 public: |
|
2408 |
|
2409 ///Find an arc between two nodes. |
|
2410 |
|
2411 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where |
|
2412 /// <em>d</em> is the number of outgoing arcs of \c s. |
|
2413 ///\param s The source node |
|
2414 ///\param t The target node |
|
2415 ///\return An arc from \c s to \c t if there exists, |
|
2416 ///\ref INVALID otherwise. |
|
2417 Arc operator()(Node s, Node t) const |
|
2418 { |
|
2419 Arc a = _head[s]; |
|
2420 while (true) { |
|
2421 if (_g.target(a) == t) { |
|
2422 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2423 return a; |
|
2424 } else if (t < _g.target(a)) { |
|
2425 if (_left[a] == INVALID) { |
|
2426 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2427 return INVALID; |
|
2428 } else { |
|
2429 a = _left[a]; |
|
2430 } |
|
2431 } else { |
|
2432 if (_right[a] == INVALID) { |
|
2433 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2434 return INVALID; |
|
2435 } else { |
|
2436 a = _right[a]; |
|
2437 } |
|
2438 } |
|
2439 } |
|
2440 } |
|
2441 |
|
2442 ///Find the first arc between two nodes. |
|
2443 |
|
2444 ///Find the first arc between two nodes in time |
|
2445 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of |
|
2446 /// outgoing arcs of \c s. |
|
2447 ///\param s The source node |
|
2448 ///\param t The target node |
|
2449 ///\return An arc from \c s to \c t if there exists, \ref INVALID |
|
2450 /// otherwise. |
|
2451 Arc findFirst(Node s, Node t) const |
|
2452 { |
|
2453 Arc a = _head[s]; |
|
2454 Arc r = INVALID; |
|
2455 while (true) { |
|
2456 if (_g.target(a) < t) { |
|
2457 if (_right[a] == INVALID) { |
|
2458 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2459 return r; |
|
2460 } else { |
|
2461 a = _right[a]; |
|
2462 } |
|
2463 } else { |
|
2464 if (_g.target(a) == t) { |
|
2465 r = a; |
|
2466 } |
|
2467 if (_left[a] == INVALID) { |
|
2468 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2469 return r; |
|
2470 } else { |
|
2471 a = _left[a]; |
|
2472 } |
|
2473 } |
|
2474 } |
|
2475 } |
|
2476 |
|
2477 ///Find the next arc between two nodes. |
|
2478 |
|
2479 ///Find the next arc between two nodes in time |
|
2480 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of |
|
2481 /// outgoing arcs of \c s. |
|
2482 ///\param s The source node |
|
2483 ///\param t The target node |
|
2484 ///\return An arc from \c s to \c t if there exists, \ref INVALID |
|
2485 /// otherwise. |
|
2486 |
|
2487 ///\note If \c e is not the result of the previous \c findFirst() |
|
2488 ///operation then the amorized time bound can not be guaranteed. |
|
2489 #ifdef DOXYGEN |
|
2490 Arc findNext(Node s, Node t, Arc a) const |
|
2491 #else |
|
2492 Arc findNext(Node, Node t, Arc a) const |
|
2493 #endif |
|
2494 { |
|
2495 if (_right[a] != INVALID) { |
|
2496 a = _right[a]; |
|
2497 while (_left[a] != INVALID) { |
|
2498 a = _left[a]; |
|
2499 } |
|
2500 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2501 } else { |
|
2502 while (_parent[a] != INVALID && _right[_parent[a]] == a) { |
|
2503 a = _parent[a]; |
|
2504 } |
|
2505 if (_parent[a] == INVALID) { |
|
2506 return INVALID; |
|
2507 } else { |
|
2508 a = _parent[a]; |
|
2509 const_cast<DynArcLookUp&>(*this).splay(a); |
|
2510 } |
|
2511 } |
|
2512 if (_g.target(a) == t) return a; |
|
2513 else return INVALID; |
|
2514 } |
|
2515 |
|
2516 }; |
|
2517 |
|
2518 ///Fast arc look up between given endpoints. |
|
2519 |
|
2520 ///\ingroup gutils |
|
2521 ///Using this class, you can find an arc in a digraph from a given |
|
2522 ///source to a given target in time <em>O(log d)</em>, |
|
2523 ///where <em>d</em> is the out-degree of the source node. |
|
2524 /// |
|
2525 ///It is not possible to find \e all parallel arcs between two nodes. |
|
2526 ///Use \ref AllArcLookUp for this purpose. |
|
2527 /// |
|
2528 ///\warning This class is static, so you should refresh() (or at least |
|
2529 ///refresh(Node)) this data structure |
|
2530 ///whenever the digraph changes. This is a time consuming (superlinearly |
|
2531 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
|
2532 /// |
|
2533 ///\tparam G The type of the underlying digraph. |
|
2534 /// |
|
2535 ///\sa DynArcLookUp |
|
2536 ///\sa AllArcLookUp |
|
2537 template<class G> |
|
2538 class ArcLookUp |
|
2539 { |
|
2540 public: |
|
2541 TEMPLATE_DIGRAPH_TYPEDEFS(G); |
|
2542 typedef G Digraph; |
|
2543 |
|
2544 protected: |
|
2545 const Digraph &_g; |
|
2546 typename Digraph::template NodeMap<Arc> _head; |
|
2547 typename Digraph::template ArcMap<Arc> _left; |
|
2548 typename Digraph::template ArcMap<Arc> _right; |
|
2549 |
|
2550 class ArcLess { |
|
2551 const Digraph &g; |
|
2552 public: |
|
2553 ArcLess(const Digraph &_g) : g(_g) {} |
|
2554 bool operator()(Arc a,Arc b) const |
|
2555 { |
|
2556 return g.target(a)<g.target(b); |
|
2557 } |
|
2558 }; |
|
2559 |
|
2560 public: |
|
2561 |
|
2562 ///Constructor |
|
2563 |
|
2564 ///Constructor. |
|
2565 /// |
|
2566 ///It builds up the search database, which remains valid until the digraph |
|
2567 ///changes. |
|
2568 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();} |
|
2569 |
|
2570 private: |
|
2571 Arc refreshRec(std::vector<Arc> &v,int a,int b) |
|
2572 { |
|
2573 int m=(a+b)/2; |
|
2574 Arc me=v[m]; |
|
2575 _left[me] = a<m?refreshRec(v,a,m-1):INVALID; |
|
2576 _right[me] = m<b?refreshRec(v,m+1,b):INVALID; |
|
2577 return me; |
|
2578 } |
|
2579 public: |
|
2580 ///Refresh the data structure at a node. |
|
2581 |
|
2582 ///Build up the search database of node \c n. |
|
2583 /// |
|
2584 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is |
|
2585 ///the number of the outgoing arcs of \c n. |
|
2586 void refresh(Node n) |
|
2587 { |
|
2588 std::vector<Arc> v; |
|
2589 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); |
|
2590 if(v.size()) { |
|
2591 std::sort(v.begin(),v.end(),ArcLess(_g)); |
|
2592 _head[n]=refreshRec(v,0,v.size()-1); |
|
2593 } |
|
2594 else _head[n]=INVALID; |
|
2595 } |
|
2596 ///Refresh the full data structure. |
|
2597 |
|
2598 ///Build up the full search database. In fact, it simply calls |
|
2599 ///\ref refresh(Node) "refresh(n)" for each node \c n. |
|
2600 /// |
|
2601 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is |
|
2602 ///the number of the arcs of \c n and <em>D</em> is the maximum |
|
2603 ///out-degree of the digraph. |
|
2604 |
|
2605 void refresh() |
|
2606 { |
|
2607 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); |
|
2608 } |
|
2609 |
|
2610 ///Find an arc between two nodes. |
|
2611 |
|
2612 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where |
|
2613 /// <em>d</em> is the number of outgoing arcs of \c s. |
|
2614 ///\param s The source node |
|
2615 ///\param t The target node |
|
2616 ///\return An arc from \c s to \c t if there exists, |
|
2617 ///\ref INVALID otherwise. |
|
2618 /// |
|
2619 ///\warning If you change the digraph, refresh() must be called before using |
|
2620 ///this operator. If you change the outgoing arcs of |
|
2621 ///a single node \c n, then |
|
2622 ///\ref refresh(Node) "refresh(n)" is enough. |
|
2623 /// |
|
2624 Arc operator()(Node s, Node t) const |
|
2625 { |
|
2626 Arc e; |
|
2627 for(e=_head[s]; |
|
2628 e!=INVALID&&_g.target(e)!=t; |
|
2629 e = t < _g.target(e)?_left[e]:_right[e]) ; |
|
2630 return e; |
|
2631 } |
|
2632 |
|
2633 }; |
|
2634 |
|
2635 ///Fast look up of all arcs between given endpoints. |
|
2636 |
|
2637 ///\ingroup gutils |
|
2638 ///This class is the same as \ref ArcLookUp, with the addition |
|
2639 ///that it makes it possible to find all arcs between given endpoints. |
|
2640 /// |
|
2641 ///\warning This class is static, so you should refresh() (or at least |
|
2642 ///refresh(Node)) this data structure |
|
2643 ///whenever the digraph changes. This is a time consuming (superlinearly |
|
2644 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
|
2645 /// |
|
2646 ///\tparam G The type of the underlying digraph. |
|
2647 /// |
|
2648 ///\sa DynArcLookUp |
|
2649 ///\sa ArcLookUp |
|
2650 template<class G> |
|
2651 class AllArcLookUp : public ArcLookUp<G> |
|
2652 { |
|
2653 using ArcLookUp<G>::_g; |
|
2654 using ArcLookUp<G>::_right; |
|
2655 using ArcLookUp<G>::_left; |
|
2656 using ArcLookUp<G>::_head; |
|
2657 |
|
2658 TEMPLATE_DIGRAPH_TYPEDEFS(G); |
|
2659 typedef G Digraph; |
|
2660 |
|
2661 typename Digraph::template ArcMap<Arc> _next; |
|
2662 |
|
2663 Arc refreshNext(Arc head,Arc next=INVALID) |
|
2664 { |
|
2665 if(head==INVALID) return next; |
|
2666 else { |
|
2667 next=refreshNext(_right[head],next); |
|
2668 // _next[head]=next; |
|
2669 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) |
|
2670 ? next : INVALID; |
|
2671 return refreshNext(_left[head],head); |
|
2672 } |
|
2673 } |
|
2674 |
|
2675 void refreshNext() |
|
2676 { |
|
2677 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]); |
|
2678 } |
|
2679 |
|
2680 public: |
|
2681 ///Constructor |
|
2682 |
|
2683 ///Constructor. |
|
2684 /// |
|
2685 ///It builds up the search database, which remains valid until the digraph |
|
2686 ///changes. |
|
2687 AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();} |
|
2688 |
|
2689 ///Refresh the data structure at a node. |
|
2690 |
|
2691 ///Build up the search database of node \c n. |
|
2692 /// |
|
2693 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is |
|
2694 ///the number of the outgoing arcs of \c n. |
|
2695 |
|
2696 void refresh(Node n) |
|
2697 { |
|
2698 ArcLookUp<G>::refresh(n); |
|
2699 refreshNext(_head[n]); |
|
2700 } |
|
2701 |
|
2702 ///Refresh the full data structure. |
|
2703 |
|
2704 ///Build up the full search database. In fact, it simply calls |
|
2705 ///\ref refresh(Node) "refresh(n)" for each node \c n. |
|
2706 /// |
|
2707 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is |
|
2708 ///the number of the arcs of \c n and <em>D</em> is the maximum |
|
2709 ///out-degree of the digraph. |
|
2710 |
|
2711 void refresh() |
|
2712 { |
|
2713 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); |
|
2714 } |
|
2715 |
|
2716 ///Find an arc between two nodes. |
|
2717 |
|
2718 ///Find an arc between two nodes. |
|
2719 ///\param s The source node |
|
2720 ///\param t The target node |
|
2721 ///\param prev The previous arc between \c s and \c t. It it is INVALID or |
|
2722 ///not given, the operator finds the first appropriate arc. |
|
2723 ///\return An arc from \c s to \c t after \c prev or |
|
2724 ///\ref INVALID if there is no more. |
|
2725 /// |
|
2726 ///For example, you can count the number of arcs from \c u to \c v in the |
|
2727 ///following way. |
|
2728 ///\code |
|
2729 ///AllArcLookUp<ListDigraph> ae(g); |
|
2730 ///... |
|
2731 ///int n=0; |
|
2732 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; |
|
2733 ///\endcode |
|
2734 /// |
|
2735 ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where |
|
2736 /// <em>d</em> is the number of outgoing arcs of \c s. Then, the |
|
2737 ///consecutive arcs are found in constant time. |
|
2738 /// |
|
2739 ///\warning If you change the digraph, refresh() must be called before using |
|
2740 ///this operator. If you change the outgoing arcs of |
|
2741 ///a single node \c n, then |
|
2742 ///\ref refresh(Node) "refresh(n)" is enough. |
|
2743 /// |
|
2744 #ifdef DOXYGEN |
|
2745 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} |
|
2746 #else |
|
2747 using ArcLookUp<G>::operator() ; |
|
2748 Arc operator()(Node s, Node t, Arc prev) const |
|
2749 { |
|
2750 return prev==INVALID?(*this)(s,t):_next[prev]; |
|
2751 } |
|
2752 #endif |
|
2753 |
|
2754 }; |
|
2755 |
|
2756 /// @} |
|
2757 |
|
2758 } //END OF NAMESPACE LEMON |
|
2759 |
|
2760 #endif |
|