COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 1241:879fcb781086

Last change on this file since 1241:879fcb781086 was 1239:d1a48668ddb4, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge fix #470

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