COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 1193:c8fa41fcc4a7

Last change on this file since 1193:c8fa41fcc4a7 was 1193:c8fa41fcc4a7, checked in by Balazs Dezso <deba@…>, 9 years ago

Type safe red and blue node set (#69)

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