COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 1192:b84e68af8248

Last change on this file since 1192:b84e68af8248 was 1190:523e45e37e52, checked in by Balazs Dezso <deba@…>, 13 years ago

Implementation of BpGraphCopy? (#69)

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