COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 1194:699c7eac2c6d

Last change on this file since 1194:699c7eac2c6d was 1194:699c7eac2c6d, checked in by Balazs Dezso <deba@…>, 12 years ago

Renamings in BpGraphs? (#69)

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