COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h

Last change on this file was 1416:f179aa1045a4, checked in by Peter Kovacs <kpeter@…>, 5 years ago

Suppress unused typdef warnings (#615)

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