1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
25 #include <lemon/config.h>
26 #include <lemon/bits/enable_if.h>
27 #include <lemon/bits/traits.h>
28 #include <lemon/assert.h>
30 // Disable the following warnings when compiling with MSVC:
31 // C4250: 'class1' : inherits 'class2::member' via dominance
32 // C4267: conversion from 'size_t' to 'type', possible loss of data
33 // C4355: 'this' : used in base member initializer list
34 // C4503: 'function' : decorated name length exceeded, name was truncated
35 // C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
36 // C4996: 'function': was declared deprecated
38 #pragma warning( disable : 4250 4267 4355 4503 4800 4996 )
41 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
42 // Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
43 #pragma GCC diagnostic ignored "-Wunused-local-typedefs"
47 ///\brief LEMON core utilities.
49 ///This header file contains core utilities for LEMON.
50 ///It is automatically included by all graph types, therefore it usually
51 ///do not have to be included directly.
55 /// \brief Dummy type to make it easier to create invalid iterators.
57 /// Dummy type to make it easier to create invalid iterators.
58 /// See \ref INVALID for the usage.
61 bool operator==(Invalid) { return true; }
62 bool operator!=(Invalid) { return false; }
63 bool operator< (Invalid) { return false; }
66 /// \brief Invalid iterators.
68 /// \ref Invalid is a global type that converts to each iterator
69 /// in such a way that the value of the target iterator will be invalid.
70 #ifdef LEMON_ONLY_TEMPLATES
71 const Invalid INVALID = Invalid();
73 extern const Invalid INVALID;
76 /// \addtogroup gutils
79 ///Create convenience typedefs for the digraph types and iterators
81 ///This \c \#define creates convenient type definitions for the following
82 ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
83 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
84 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
86 ///\note If the graph type is a dependent type, ie. the graph type depend
87 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
89 #define DIGRAPH_TYPEDEFS(Digraph) \
90 typedef Digraph::Node Node; \
91 typedef Digraph::NodeIt NodeIt; \
92 typedef Digraph::Arc Arc; \
93 typedef Digraph::ArcIt ArcIt; \
94 typedef Digraph::InArcIt InArcIt; \
95 typedef Digraph::OutArcIt OutArcIt; \
96 typedef Digraph::NodeMap<bool> BoolNodeMap; \
97 typedef Digraph::NodeMap<int> IntNodeMap; \
98 typedef Digraph::NodeMap<double> DoubleNodeMap; \
99 typedef Digraph::ArcMap<bool> BoolArcMap; \
100 typedef Digraph::ArcMap<int> IntArcMap; \
101 typedef Digraph::ArcMap<double> DoubleArcMap
103 ///Create convenience typedefs for the digraph types and iterators
105 ///\see DIGRAPH_TYPEDEFS
107 ///\note Use this macro, if the graph type is a dependent type,
108 ///ie. the graph type depend on a template parameter.
109 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
110 typedef typename Digraph::Node Node; \
111 typedef typename Digraph::NodeIt NodeIt; \
112 typedef typename Digraph::Arc Arc; \
113 typedef typename Digraph::ArcIt ArcIt; \
114 typedef typename Digraph::InArcIt InArcIt; \
115 typedef typename Digraph::OutArcIt OutArcIt; \
116 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
117 typedef typename Digraph::template NodeMap<int> IntNodeMap; \
118 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
119 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
120 typedef typename Digraph::template ArcMap<int> IntArcMap; \
121 typedef typename Digraph::template ArcMap<double> DoubleArcMap
123 ///Create convenience typedefs for the graph types and iterators
125 ///This \c \#define creates the same convenient type definitions as defined
126 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
127 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
130 ///\note If the graph type is a dependent type, ie. the graph type depend
131 ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
133 #define GRAPH_TYPEDEFS(Graph) \
134 DIGRAPH_TYPEDEFS(Graph); \
135 typedef Graph::Edge Edge; \
136 typedef Graph::EdgeIt EdgeIt; \
137 typedef Graph::IncEdgeIt IncEdgeIt; \
138 typedef Graph::EdgeMap<bool> BoolEdgeMap; \
139 typedef Graph::EdgeMap<int> IntEdgeMap; \
140 typedef Graph::EdgeMap<double> DoubleEdgeMap
142 ///Create convenience typedefs for the graph types and iterators
144 ///\see GRAPH_TYPEDEFS
146 ///\note Use this macro, if the graph type is a dependent type,
147 ///ie. the graph type depend on a template parameter.
148 #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
149 TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
150 typedef typename Graph::Edge Edge; \
151 typedef typename Graph::EdgeIt EdgeIt; \
152 typedef typename Graph::IncEdgeIt IncEdgeIt; \
153 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
154 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
155 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
157 ///Create convenience typedefs for the bipartite graph types and iterators
159 ///This \c \#define creates the same convenient type definitions as
160 ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
161 ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
162 ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
163 ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
165 ///\note If the graph type is a dependent type, ie. the graph type depend
166 ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
168 #define BPGRAPH_TYPEDEFS(BpGraph) \
169 GRAPH_TYPEDEFS(BpGraph); \
170 typedef BpGraph::RedNode RedNode; \
171 typedef BpGraph::RedNodeIt RedNodeIt; \
172 typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap; \
173 typedef BpGraph::RedNodeMap<int> IntRedNodeMap; \
174 typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap; \
175 typedef BpGraph::BlueNode BlueNode; \
176 typedef BpGraph::BlueNodeIt BlueNodeIt; \
177 typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap; \
178 typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap; \
179 typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
181 ///Create convenience typedefs for the bipartite graph types and iterators
183 ///\see BPGRAPH_TYPEDEFS
185 ///\note Use this macro, if the graph type is a dependent type,
186 ///ie. the graph type depend on a template parameter.
187 #define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \
188 TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \
189 typedef typename BpGraph::RedNode RedNode; \
190 typedef typename BpGraph::RedNodeIt RedNodeIt; \
191 typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap; \
192 typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap; \
193 typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap; \
194 typedef typename BpGraph::BlueNode BlueNode; \
195 typedef typename BpGraph::BlueNodeIt BlueNodeIt; \
196 typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap; \
197 typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap; \
198 typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
200 /// \brief Function to count the items in a graph.
202 /// This function counts the items (nodes, arcs etc.) in a graph.
203 /// The complexity of the function is linear because
204 /// it iterates on all of the items.
205 template <typename Graph, typename Item>
206 inline int countItems(const Graph& g) {
207 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
209 for (ItemIt it(g); it != INVALID; ++it) {
217 namespace _core_bits {
219 template <typename Graph, typename Enable = void>
220 struct CountNodesSelector {
221 static int count(const Graph &g) {
222 return countItems<Graph, typename Graph::Node>(g);
226 template <typename Graph>
227 struct CountNodesSelector<
229 enable_if<typename Graph::NodeNumTag, void>::type>
231 static int count(const Graph &g) {
237 /// \brief Function to count the nodes in the graph.
239 /// This function counts the nodes in the graph.
240 /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
241 /// graph structures it is specialized to run in <em>O</em>(1).
243 /// \note If the graph contains a \c nodeNum() member function and a
244 /// \c NodeNumTag tag then this function calls directly the member
245 /// function to query the cardinality of the node set.
246 template <typename Graph>
247 inline int countNodes(const Graph& g) {
248 return _core_bits::CountNodesSelector<Graph>::count(g);
251 namespace _graph_utils_bits {
253 template <typename Graph, typename Enable = void>
254 struct CountRedNodesSelector {
255 static int count(const Graph &g) {
256 return countItems<Graph, typename Graph::RedNode>(g);
260 template <typename Graph>
261 struct CountRedNodesSelector<
263 enable_if<typename Graph::NodeNumTag, void>::type>
265 static int count(const Graph &g) {
271 /// \brief Function to count the red nodes in the graph.
273 /// This function counts the red nodes in the graph.
274 /// The complexity of the function is O(n) but for some
275 /// graph structures it is specialized to run in O(1).
277 /// If the graph contains a \e redNum() member function and a
278 /// \e NodeNumTag tag then this function calls directly the member
279 /// function to query the cardinality of the node set.
280 template <typename Graph>
281 inline int countRedNodes(const Graph& g) {
282 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
285 namespace _graph_utils_bits {
287 template <typename Graph, typename Enable = void>
288 struct CountBlueNodesSelector {
289 static int count(const Graph &g) {
290 return countItems<Graph, typename Graph::BlueNode>(g);
294 template <typename Graph>
295 struct CountBlueNodesSelector<
297 enable_if<typename Graph::NodeNumTag, void>::type>
299 static int count(const Graph &g) {
305 /// \brief Function to count the blue nodes in the graph.
307 /// This function counts the blue nodes in the graph.
308 /// The complexity of the function is O(n) but for some
309 /// graph structures it is specialized to run in O(1).
311 /// If the graph contains a \e blueNum() member function and a
312 /// \e NodeNumTag tag then this function calls directly the member
313 /// function to query the cardinality of the node set.
314 template <typename Graph>
315 inline int countBlueNodes(const Graph& g) {
316 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
321 namespace _core_bits {
323 template <typename Graph, typename Enable = void>
324 struct CountArcsSelector {
325 static int count(const Graph &g) {
326 return countItems<Graph, typename Graph::Arc>(g);
330 template <typename Graph>
331 struct CountArcsSelector<
333 typename enable_if<typename Graph::ArcNumTag, void>::type>
335 static int count(const Graph &g) {
341 /// \brief Function to count the arcs in the graph.
343 /// This function counts the arcs in the graph.
344 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
345 /// graph structures it is specialized to run in <em>O</em>(1).
347 /// \note If the graph contains a \c arcNum() member function and a
348 /// \c ArcNumTag tag then this function calls directly the member
349 /// function to query the cardinality of the arc set.
350 template <typename Graph>
351 inline int countArcs(const Graph& g) {
352 return _core_bits::CountArcsSelector<Graph>::count(g);
357 namespace _core_bits {
359 template <typename Graph, typename Enable = void>
360 struct CountEdgesSelector {
361 static int count(const Graph &g) {
362 return countItems<Graph, typename Graph::Edge>(g);
366 template <typename Graph>
367 struct CountEdgesSelector<
369 typename enable_if<typename Graph::EdgeNumTag, void>::type>
371 static int count(const Graph &g) {
377 /// \brief Function to count the edges in the graph.
379 /// This function counts the edges in the graph.
380 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
381 /// graph structures it is specialized to run in <em>O</em>(1).
383 /// \note If the graph contains a \c edgeNum() member function and a
384 /// \c EdgeNumTag tag then this function calls directly the member
385 /// function to query the cardinality of the edge set.
386 template <typename Graph>
387 inline int countEdges(const Graph& g) {
388 return _core_bits::CountEdgesSelector<Graph>::count(g);
393 template <typename Graph, typename DegIt>
394 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
396 for (DegIt it(_g, _n); it != INVALID; ++it) {
402 /// \brief Function to count the number of the out-arcs from node \c n.
404 /// This function counts the number of the out-arcs from node \c n
405 /// in the graph \c g.
406 template <typename Graph>
407 inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
408 return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
411 /// \brief Function to count the number of the in-arcs to node \c n.
413 /// This function counts the number of the in-arcs to node \c n
414 /// in the graph \c g.
415 template <typename Graph>
416 inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
417 return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
420 /// \brief Function to count the number of the inc-edges to node \c n.
422 /// This function counts the number of the inc-edges to node \c n
423 /// in the undirected graph \c g.
424 template <typename Graph>
425 inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
426 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
429 namespace _core_bits {
431 template <typename Digraph, typename Item, typename RefMap>
434 virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
436 virtual ~MapCopyBase() {}
439 template <typename Digraph, typename Item, typename RefMap,
440 typename FromMap, typename ToMap>
441 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
444 MapCopy(const FromMap& map, ToMap& tmap)
445 : _map(map), _tmap(tmap) {}
447 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
448 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
449 for (ItemIt it(digraph); it != INVALID; ++it) {
450 _tmap.set(refMap[it], _map[it]);
459 template <typename Digraph, typename Item, typename RefMap, typename It>
460 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
463 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
465 virtual void copy(const Digraph&, const RefMap& refMap) {
474 template <typename Digraph, typename Item, typename RefMap, typename Ref>
475 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
478 RefCopy(Ref& map) : _map(map) {}
480 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
481 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
482 for (ItemIt it(digraph); it != INVALID; ++it) {
483 _map.set(it, refMap[it]);
491 template <typename Digraph, typename Item, typename RefMap,
493 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
496 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
498 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
499 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
500 for (ItemIt it(digraph); it != INVALID; ++it) {
501 _cmap.set(refMap[it], it);
509 template <typename Digraph, typename Enable = void>
510 struct DigraphCopySelector {
511 template <typename From, typename NodeRefMap, typename ArcRefMap>
512 static void copy(const From& from, Digraph &to,
513 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
515 for (typename From::NodeIt it(from); it != INVALID; ++it) {
516 nodeRefMap[it] = to.addNode();
518 for (typename From::ArcIt it(from); it != INVALID; ++it) {
519 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
520 nodeRefMap[from.target(it)]);
525 template <typename Digraph>
526 struct DigraphCopySelector<
528 typename enable_if<typename Digraph::BuildTag, void>::type>
530 template <typename From, typename NodeRefMap, typename ArcRefMap>
531 static void copy(const From& from, Digraph &to,
532 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
533 to.build(from, nodeRefMap, arcRefMap);
537 template <typename Graph, typename Enable = void>
538 struct GraphCopySelector {
539 template <typename From, typename NodeRefMap, typename EdgeRefMap>
540 static void copy(const From& from, Graph &to,
541 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
543 for (typename From::NodeIt it(from); it != INVALID; ++it) {
544 nodeRefMap[it] = to.addNode();
546 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
547 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
548 nodeRefMap[from.v(it)]);
553 template <typename Graph>
554 struct GraphCopySelector<
556 typename enable_if<typename Graph::BuildTag, void>::type>
558 template <typename From, typename NodeRefMap, typename EdgeRefMap>
559 static void copy(const From& from, Graph &to,
560 NodeRefMap& nodeRefMap,
561 EdgeRefMap& edgeRefMap) {
562 to.build(from, nodeRefMap, edgeRefMap);
566 template <typename BpGraph, typename Enable = void>
567 struct BpGraphCopySelector {
568 template <typename From, typename RedNodeRefMap,
569 typename BlueNodeRefMap, typename EdgeRefMap>
570 static void copy(const From& from, BpGraph &to,
571 RedNodeRefMap& redNodeRefMap,
572 BlueNodeRefMap& blueNodeRefMap,
573 EdgeRefMap& edgeRefMap) {
575 for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
576 redNodeRefMap[it] = to.addRedNode();
578 for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
579 blueNodeRefMap[it] = to.addBlueNode();
581 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
582 edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
583 blueNodeRefMap[from.blueNode(it)]);
588 template <typename BpGraph>
589 struct BpGraphCopySelector<
591 typename enable_if<typename BpGraph::BuildTag, void>::type>
593 template <typename From, typename RedNodeRefMap,
594 typename BlueNodeRefMap, typename EdgeRefMap>
595 static void copy(const From& from, BpGraph &to,
596 RedNodeRefMap& redNodeRefMap,
597 BlueNodeRefMap& blueNodeRefMap,
598 EdgeRefMap& edgeRefMap) {
599 to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
605 /// \brief Check whether a graph is undirected.
607 /// This function returns \c true if the given graph is undirected.
609 template <typename GR>
610 bool undirected(const GR& g) { return false; }
612 template <typename GR>
613 typename enable_if<UndirectedTagIndicator<GR>, bool>::type
614 undirected(const GR&) {
617 template <typename GR>
618 typename disable_if<UndirectedTagIndicator<GR>, bool>::type
619 undirected(const GR&) {
624 /// \brief Class to copy a digraph.
626 /// Class to copy a digraph to another digraph (duplicate a digraph). The
627 /// simplest way of using it is through the \c digraphCopy() function.
629 /// This class not only make a copy of a digraph, but it can create
630 /// references and cross references between the nodes and arcs of
631 /// the two digraphs, and it can copy maps to use with the newly created
634 /// To make a copy from a digraph, first an instance of DigraphCopy
635 /// should be created, then the data belongs to the digraph should
636 /// assigned to copy. In the end, the \c run() member should be
639 /// The next code copies a digraph with several data:
641 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
642 /// // Create references for the nodes
643 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
645 /// // Create cross references (inverse) for the arcs
646 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
647 /// cg.arcCrossRef(acr);
648 /// // Copy an arc map
649 /// OrigGraph::ArcMap<double> oamap(orig_graph);
650 /// NewGraph::ArcMap<double> namap(new_graph);
651 /// cg.arcMap(oamap, namap);
653 /// OrigGraph::Node on;
654 /// NewGraph::Node nn;
656 /// // Execute copying
659 template <typename From, typename To>
663 typedef typename From::Node Node;
664 typedef typename From::NodeIt NodeIt;
665 typedef typename From::Arc Arc;
666 typedef typename From::ArcIt ArcIt;
668 typedef typename To::Node TNode;
669 typedef typename To::Arc TArc;
671 typedef typename From::template NodeMap<TNode> NodeRefMap;
672 typedef typename From::template ArcMap<TArc> ArcRefMap;
676 /// \brief Constructor of DigraphCopy.
678 /// Constructor of DigraphCopy for copying the content of the
679 /// \c from digraph into the \c to digraph.
680 DigraphCopy(const From& from, To& to)
681 : _from(from), _to(to) {}
683 /// \brief Destructor of DigraphCopy
685 /// Destructor of DigraphCopy.
687 for (int i = 0; i < int(_node_maps.size()); ++i) {
688 delete _node_maps[i];
690 for (int i = 0; i < int(_arc_maps.size()); ++i) {
696 /// \brief Copy the node references into the given map.
698 /// This function copies the node references into the given map.
699 /// The parameter should be a map, whose key type is the Node type of
700 /// the source digraph, while the value type is the Node type of the
701 /// destination digraph.
702 template <typename NodeRef>
703 DigraphCopy& nodeRef(NodeRef& map) {
704 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
705 NodeRefMap, NodeRef>(map));
709 /// \brief Copy the node cross references into the given map.
711 /// This function copies the node cross references (reverse references)
712 /// into the given map. The parameter should be a map, whose key type
713 /// is the Node type of the destination digraph, while the value type is
714 /// the Node type of the source digraph.
715 template <typename NodeCrossRef>
716 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
717 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
718 NodeRefMap, NodeCrossRef>(map));
722 /// \brief Make a copy of the given node map.
724 /// This function makes a copy of the given node map for the newly
726 /// The key type of the new map \c tmap should be the Node type of the
727 /// destination digraph, and the key type of the original map \c map
728 /// should be the Node type of the source digraph.
729 template <typename FromMap, typename ToMap>
730 DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
731 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
732 NodeRefMap, FromMap, ToMap>(map, tmap));
736 /// \brief Make a copy of the given node.
738 /// This function makes a copy of the given node.
739 DigraphCopy& node(const Node& node, TNode& tnode) {
740 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
741 NodeRefMap, TNode>(node, tnode));
745 /// \brief Copy the arc references into the given map.
747 /// This function copies the arc references into the given map.
748 /// The parameter should be a map, whose key type is the Arc type of
749 /// the source digraph, while the value type is the Arc type of the
750 /// destination digraph.
751 template <typename ArcRef>
752 DigraphCopy& arcRef(ArcRef& map) {
753 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
754 ArcRefMap, ArcRef>(map));
758 /// \brief Copy the arc cross references into the given map.
760 /// This function copies the arc cross references (reverse references)
761 /// into the given map. The parameter should be a map, whose key type
762 /// is the Arc type of the destination digraph, while the value type is
763 /// the Arc type of the source digraph.
764 template <typename ArcCrossRef>
765 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
766 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
767 ArcRefMap, ArcCrossRef>(map));
771 /// \brief Make a copy of the given arc map.
773 /// This function makes a copy of the given arc map for the newly
775 /// The key type of the new map \c tmap should be the Arc type of the
776 /// destination digraph, and the key type of the original map \c map
777 /// should be the Arc type of the source digraph.
778 template <typename FromMap, typename ToMap>
779 DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
780 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
781 ArcRefMap, FromMap, ToMap>(map, tmap));
785 /// \brief Make a copy of the given arc.
787 /// This function makes a copy of the given arc.
788 DigraphCopy& arc(const Arc& arc, TArc& tarc) {
789 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
790 ArcRefMap, TArc>(arc, tarc));
794 /// \brief Execute copying.
796 /// This function executes the copying of the digraph along with the
797 /// copying of the assigned data.
799 NodeRefMap nodeRefMap(_from);
800 ArcRefMap arcRefMap(_from);
801 _core_bits::DigraphCopySelector<To>::
802 copy(_from, _to, nodeRefMap, arcRefMap);
803 for (int i = 0; i < int(_node_maps.size()); ++i) {
804 _node_maps[i]->copy(_from, nodeRefMap);
806 for (int i = 0; i < int(_arc_maps.size()); ++i) {
807 _arc_maps[i]->copy(_from, arcRefMap);
816 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
819 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
824 /// \brief Copy a digraph to another digraph.
826 /// This function copies a digraph to another digraph.
827 /// The complete usage of it is detailed in the DigraphCopy class, but
828 /// a short example shows a basic work:
830 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
833 /// After the copy the \c nr map will contain the mapping from the
834 /// nodes of the \c from digraph to the nodes of the \c to digraph and
835 /// \c acr will contain the mapping from the arcs of the \c to digraph
836 /// to the arcs of the \c from digraph.
839 template <typename From, typename To>
840 DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
841 return DigraphCopy<From, To>(from, to);
844 /// \brief Class to copy a graph.
846 /// Class to copy a graph to another graph (duplicate a graph). The
847 /// simplest way of using it is through the \c graphCopy() function.
849 /// This class not only make a copy of a graph, but it can create
850 /// references and cross references between the nodes, edges and arcs of
851 /// the two graphs, and it can copy maps for using with the newly created
854 /// To make a copy from a graph, first an instance of GraphCopy
855 /// should be created, then the data belongs to the graph should
856 /// assigned to copy. In the end, the \c run() member should be
859 /// The next code copies a graph with several data:
861 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
862 /// // Create references for the nodes
863 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
865 /// // Create cross references (inverse) for the edges
866 /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
867 /// cg.edgeCrossRef(ecr);
868 /// // Copy an edge map
869 /// OrigGraph::EdgeMap<double> oemap(orig_graph);
870 /// NewGraph::EdgeMap<double> nemap(new_graph);
871 /// cg.edgeMap(oemap, nemap);
873 /// OrigGraph::Node on;
874 /// NewGraph::Node nn;
876 /// // Execute copying
879 template <typename From, typename To>
883 typedef typename From::Node Node;
884 typedef typename From::NodeIt NodeIt;
885 typedef typename From::Arc Arc;
886 typedef typename From::ArcIt ArcIt;
887 typedef typename From::Edge Edge;
888 typedef typename From::EdgeIt EdgeIt;
890 typedef typename To::Node TNode;
891 typedef typename To::Arc TArc;
892 typedef typename To::Edge TEdge;
894 typedef typename From::template NodeMap<TNode> NodeRefMap;
895 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
898 ArcRefMap(const From& from, const To& to,
899 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
900 : _from(from), _to(to),
901 _edge_ref(edge_ref), _node_ref(node_ref) {}
903 typedef typename From::Arc Key;
904 typedef typename To::Arc Value;
906 Value operator[](const Key& key) const {
907 bool forward = _from.u(key) != _from.v(key) ?
908 _node_ref[_from.source(key)] ==
909 _to.source(_to.direct(_edge_ref[key], true)) :
910 _from.direction(key);
911 return _to.direct(_edge_ref[key], forward);
916 const EdgeRefMap& _edge_ref;
917 const NodeRefMap& _node_ref;
922 /// \brief Constructor of GraphCopy.
924 /// Constructor of GraphCopy for copying the content of the
925 /// \c from graph into the \c to graph.
926 GraphCopy(const From& from, To& to)
927 : _from(from), _to(to) {}
929 /// \brief Destructor of GraphCopy
931 /// Destructor of GraphCopy.
933 for (int i = 0; i < int(_node_maps.size()); ++i) {
934 delete _node_maps[i];
936 for (int i = 0; i < int(_arc_maps.size()); ++i) {
939 for (int i = 0; i < int(_edge_maps.size()); ++i) {
940 delete _edge_maps[i];
944 /// \brief Copy the node references into the given map.
946 /// This function copies the node references into the given map.
947 /// The parameter should be a map, whose key type is the Node type of
948 /// the source graph, while the value type is the Node type of the
949 /// destination graph.
950 template <typename NodeRef>
951 GraphCopy& nodeRef(NodeRef& map) {
952 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
953 NodeRefMap, NodeRef>(map));
957 /// \brief Copy the node cross references into the given map.
959 /// This function copies the node cross references (reverse references)
960 /// into the given map. The parameter should be a map, whose key type
961 /// is the Node type of the destination graph, while the value type is
962 /// the Node type of the source graph.
963 template <typename NodeCrossRef>
964 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
965 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
966 NodeRefMap, NodeCrossRef>(map));
970 /// \brief Make a copy of the given node map.
972 /// This function makes a copy of the given node map for the newly
974 /// The key type of the new map \c tmap should be the Node type of the
975 /// destination graph, and the key type of the original map \c map
976 /// should be the Node type of the source graph.
977 template <typename FromMap, typename ToMap>
978 GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
979 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
980 NodeRefMap, FromMap, ToMap>(map, tmap));
984 /// \brief Make a copy of the given node.
986 /// This function makes a copy of the given node.
987 GraphCopy& node(const Node& node, TNode& tnode) {
988 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
989 NodeRefMap, TNode>(node, tnode));
993 /// \brief Copy the arc references into the given map.
995 /// This function copies the arc references into the given map.
996 /// The parameter should be a map, whose key type is the Arc type of
997 /// the source graph, while the value type is the Arc type of the
998 /// destination graph.
999 template <typename ArcRef>
1000 GraphCopy& arcRef(ArcRef& map) {
1001 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1002 ArcRefMap, ArcRef>(map));
1006 /// \brief Copy the arc cross references into the given map.
1008 /// This function copies the arc cross references (reverse references)
1009 /// into the given map. The parameter should be a map, whose key type
1010 /// is the Arc type of the destination graph, while the value type is
1011 /// the Arc type of the source graph.
1012 template <typename ArcCrossRef>
1013 GraphCopy& arcCrossRef(ArcCrossRef& map) {
1014 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1015 ArcRefMap, ArcCrossRef>(map));
1019 /// \brief Make a copy of the given arc map.
1021 /// This function makes a copy of the given arc map for the newly
1023 /// The key type of the new map \c tmap should be the Arc type of the
1024 /// destination graph, and the key type of the original map \c map
1025 /// should be the Arc type of the source graph.
1026 template <typename FromMap, typename ToMap>
1027 GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1028 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1029 ArcRefMap, FromMap, ToMap>(map, tmap));
1033 /// \brief Make a copy of the given arc.
1035 /// This function makes a copy of the given arc.
1036 GraphCopy& arc(const Arc& arc, TArc& tarc) {
1037 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1038 ArcRefMap, TArc>(arc, tarc));
1042 /// \brief Copy the edge references into the given map.
1044 /// This function copies the edge references into the given map.
1045 /// The parameter should be a map, whose key type is the Edge type of
1046 /// the source graph, while the value type is the Edge type of the
1047 /// destination graph.
1048 template <typename EdgeRef>
1049 GraphCopy& edgeRef(EdgeRef& map) {
1050 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1051 EdgeRefMap, EdgeRef>(map));
1055 /// \brief Copy the edge cross references into the given map.
1057 /// This function copies the edge cross references (reverse references)
1058 /// into the given map. The parameter should be a map, whose key type
1059 /// is the Edge type of the destination graph, while the value type is
1060 /// the Edge type of the source graph.
1061 template <typename EdgeCrossRef>
1062 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1063 _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1064 Edge, EdgeRefMap, EdgeCrossRef>(map));
1068 /// \brief Make a copy of the given edge map.
1070 /// This function makes a copy of the given edge map for the newly
1072 /// The key type of the new map \c tmap should be the Edge type of the
1073 /// destination graph, and the key type of the original map \c map
1074 /// should be the Edge type of the source graph.
1075 template <typename FromMap, typename ToMap>
1076 GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1077 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1078 EdgeRefMap, FromMap, ToMap>(map, tmap));
1082 /// \brief Make a copy of the given edge.
1084 /// This function makes a copy of the given edge.
1085 GraphCopy& edge(const Edge& edge, TEdge& tedge) {
1086 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1087 EdgeRefMap, TEdge>(edge, tedge));
1091 /// \brief Execute copying.
1093 /// This function executes the copying of the graph along with the
1094 /// copying of the assigned data.
1096 NodeRefMap nodeRefMap(_from);
1097 EdgeRefMap edgeRefMap(_from);
1098 ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
1099 _core_bits::GraphCopySelector<To>::
1100 copy(_from, _to, nodeRefMap, edgeRefMap);
1101 for (int i = 0; i < int(_node_maps.size()); ++i) {
1102 _node_maps[i]->copy(_from, nodeRefMap);
1104 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1105 _edge_maps[i]->copy(_from, edgeRefMap);
1107 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1108 _arc_maps[i]->copy(_from, arcRefMap);
1117 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1120 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1123 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1128 /// \brief Copy a graph to another graph.
1130 /// This function copies a graph to another graph.
1131 /// The complete usage of it is detailed in the GraphCopy class,
1132 /// but a short example shows a basic work:
1134 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1137 /// After the copy the \c nr map will contain the mapping from the
1138 /// nodes of the \c from graph to the nodes of the \c to graph and
1139 /// \c ecr will contain the mapping from the edges of the \c to graph
1140 /// to the edges of the \c from graph.
1143 template <typename From, typename To>
1145 graphCopy(const From& from, To& to) {
1146 return GraphCopy<From, To>(from, to);
1149 /// \brief Class to copy a bipartite graph.
1151 /// Class to copy a bipartite graph to another graph (duplicate a
1152 /// graph). The simplest way of using it is through the
1153 /// \c bpGraphCopy() function.
1155 /// This class not only make a copy of a bipartite graph, but it can
1156 /// create references and cross references between the nodes, edges
1157 /// and arcs of the two graphs, and it can copy maps for using with
1158 /// the newly created graph.
1160 /// To make a copy from a graph, first an instance of BpGraphCopy
1161 /// should be created, then the data belongs to the graph should
1162 /// assigned to copy. In the end, the \c run() member should be
1165 /// The next code copies a graph with several data:
1167 /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
1168 /// // Create references for the nodes
1169 /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
1171 /// // Create cross references (inverse) for the edges
1172 /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
1173 /// cg.edgeCrossRef(ecr);
1174 /// // Copy a red node map
1175 /// OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
1176 /// NewBpGraph::RedNodeMap<double> nrmap(new_graph);
1177 /// cg.redNodeMap(ormap, nrmap);
1179 /// OrigBpGraph::Node on;
1180 /// NewBpGraph::Node nn;
1181 /// cg.node(on, nn);
1182 /// // Execute copying
1185 template <typename From, typename To>
1189 typedef typename From::Node Node;
1190 typedef typename From::RedNode RedNode;
1191 typedef typename From::BlueNode BlueNode;
1192 typedef typename From::NodeIt NodeIt;
1193 typedef typename From::Arc Arc;
1194 typedef typename From::ArcIt ArcIt;
1195 typedef typename From::Edge Edge;
1196 typedef typename From::EdgeIt EdgeIt;
1198 typedef typename To::Node TNode;
1199 typedef typename To::RedNode TRedNode;
1200 typedef typename To::BlueNode TBlueNode;
1201 typedef typename To::Arc TArc;
1202 typedef typename To::Edge TEdge;
1204 typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
1205 typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
1206 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1209 NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
1210 const BlueNodeRefMap& blue_node_ref)
1211 : _from(from), _red_node_ref(red_node_ref),
1212 _blue_node_ref(blue_node_ref) {}
1214 typedef typename From::Node Key;
1215 typedef typename To::Node Value;
1217 Value operator[](const Key& key) const {
1218 if (_from.red(key)) {
1219 return _red_node_ref[_from.asRedNodeUnsafe(key)];
1221 return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
1226 const RedNodeRefMap& _red_node_ref;
1227 const BlueNodeRefMap& _blue_node_ref;
1231 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
1232 : _from(from), _to(to), _edge_ref(edge_ref) {}
1234 typedef typename From::Arc Key;
1235 typedef typename To::Arc Value;
1237 Value operator[](const Key& key) const {
1238 return _to.direct(_edge_ref[key], _from.direction(key));
1243 const EdgeRefMap& _edge_ref;
1248 /// \brief Constructor of BpGraphCopy.
1250 /// Constructor of BpGraphCopy for copying the content of the
1251 /// \c from graph into the \c to graph.
1252 BpGraphCopy(const From& from, To& to)
1253 : _from(from), _to(to) {}
1255 /// \brief Destructor of BpGraphCopy
1257 /// Destructor of BpGraphCopy.
1259 for (int i = 0; i < int(_node_maps.size()); ++i) {
1260 delete _node_maps[i];
1262 for (int i = 0; i < int(_red_maps.size()); ++i) {
1263 delete _red_maps[i];
1265 for (int i = 0; i < int(_blue_maps.size()); ++i) {
1266 delete _blue_maps[i];
1268 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1269 delete _arc_maps[i];
1271 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1272 delete _edge_maps[i];
1276 /// \brief Copy the node references into the given map.
1278 /// This function copies the node references into the given map.
1279 /// The parameter should be a map, whose key type is the Node type of
1280 /// the source graph, while the value type is the Node type of the
1281 /// destination graph.
1282 template <typename NodeRef>
1283 BpGraphCopy& nodeRef(NodeRef& map) {
1284 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1285 NodeRefMap, NodeRef>(map));
1289 /// \brief Copy the node cross references into the given map.
1291 /// This function copies the node cross references (reverse references)
1292 /// into the given map. The parameter should be a map, whose key type
1293 /// is the Node type of the destination graph, while the value type is
1294 /// the Node type of the source graph.
1295 template <typename NodeCrossRef>
1296 BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1297 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1298 NodeRefMap, NodeCrossRef>(map));
1302 /// \brief Make a copy of the given node map.
1304 /// This function makes a copy of the given node map for the newly
1306 /// The key type of the new map \c tmap should be the Node type of the
1307 /// destination graph, and the key type of the original map \c map
1308 /// should be the Node type of the source graph.
1309 template <typename FromMap, typename ToMap>
1310 BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
1311 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1312 NodeRefMap, FromMap, ToMap>(map, tmap));
1316 /// \brief Make a copy of the given node.
1318 /// This function makes a copy of the given node.
1319 BpGraphCopy& node(const Node& node, TNode& tnode) {
1320 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1321 NodeRefMap, TNode>(node, tnode));
1325 /// \brief Copy the red node references into the given map.
1327 /// This function copies the red node references into the given
1328 /// map. The parameter should be a map, whose key type is the
1329 /// Node type of the source graph with the red item set, while the
1330 /// value type is the Node type of the destination graph.
1331 template <typename RedRef>
1332 BpGraphCopy& redRef(RedRef& map) {
1333 _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
1334 RedNodeRefMap, RedRef>(map));
1338 /// \brief Copy the red node cross references into the given map.
1340 /// This function copies the red node cross references (reverse
1341 /// references) into the given map. The parameter should be a map,
1342 /// whose key type is the Node type of the destination graph with
1343 /// the red item set, while the value type is the Node type of the
1345 template <typename RedCrossRef>
1346 BpGraphCopy& redCrossRef(RedCrossRef& map) {
1347 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
1348 RedNodeRefMap, RedCrossRef>(map));
1352 /// \brief Make a copy of the given red node map.
1354 /// This function makes a copy of the given red node map for the newly
1356 /// The key type of the new map \c tmap should be the Node type of
1357 /// the destination graph with the red items, and the key type of
1358 /// the original map \c map should be the Node type of the source
1360 template <typename FromMap, typename ToMap>
1361 BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
1362 _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
1363 RedNodeRefMap, FromMap, ToMap>(map, tmap));
1367 /// \brief Make a copy of the given red node.
1369 /// This function makes a copy of the given red node.
1370 BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
1371 _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
1372 RedNodeRefMap, TRedNode>(node, tnode));
1376 /// \brief Copy the blue node references into the given map.
1378 /// This function copies the blue node references into the given
1379 /// map. The parameter should be a map, whose key type is the
1380 /// Node type of the source graph with the blue item set, while the
1381 /// value type is the Node type of the destination graph.
1382 template <typename BlueRef>
1383 BpGraphCopy& blueRef(BlueRef& map) {
1384 _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
1385 BlueNodeRefMap, BlueRef>(map));
1389 /// \brief Copy the blue node cross references into the given map.
1391 /// This function copies the blue node cross references (reverse
1392 /// references) into the given map. The parameter should be a map,
1393 /// whose key type is the Node type of the destination graph with
1394 /// the blue item set, while the value type is the Node type of the
1396 template <typename BlueCrossRef>
1397 BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1398 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
1399 BlueNodeRefMap, BlueCrossRef>(map));
1403 /// \brief Make a copy of the given blue node map.
1405 /// This function makes a copy of the given blue node map for the newly
1407 /// The key type of the new map \c tmap should be the Node type of
1408 /// the destination graph with the blue items, and the key type of
1409 /// the original map \c map should be the Node type of the source
1411 template <typename FromMap, typename ToMap>
1412 BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
1413 _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
1414 BlueNodeRefMap, FromMap, ToMap>(map, tmap));
1418 /// \brief Make a copy of the given blue node.
1420 /// This function makes a copy of the given blue node.
1421 BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
1422 _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
1423 BlueNodeRefMap, TBlueNode>(node, tnode));
1427 /// \brief Copy the arc references into the given map.
1429 /// This function copies the arc references into the given map.
1430 /// The parameter should be a map, whose key type is the Arc type of
1431 /// the source graph, while the value type is the Arc type of the
1432 /// destination graph.
1433 template <typename ArcRef>
1434 BpGraphCopy& arcRef(ArcRef& map) {
1435 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1436 ArcRefMap, ArcRef>(map));
1440 /// \brief Copy the arc cross references into the given map.
1442 /// This function copies the arc cross references (reverse references)
1443 /// into the given map. The parameter should be a map, whose key type
1444 /// is the Arc type of the destination graph, while the value type is
1445 /// the Arc type of the source graph.
1446 template <typename ArcCrossRef>
1447 BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
1448 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1449 ArcRefMap, ArcCrossRef>(map));
1453 /// \brief Make a copy of the given arc map.
1455 /// This function makes a copy of the given arc map for the newly
1457 /// The key type of the new map \c tmap should be the Arc type of the
1458 /// destination graph, and the key type of the original map \c map
1459 /// should be the Arc type of the source graph.
1460 template <typename FromMap, typename ToMap>
1461 BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1462 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1463 ArcRefMap, FromMap, ToMap>(map, tmap));
1467 /// \brief Make a copy of the given arc.
1469 /// This function makes a copy of the given arc.
1470 BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
1471 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1472 ArcRefMap, TArc>(arc, tarc));
1476 /// \brief Copy the edge references into the given map.
1478 /// This function copies the edge references into the given map.
1479 /// The parameter should be a map, whose key type is the Edge type of
1480 /// the source graph, while the value type is the Edge type of the
1481 /// destination graph.
1482 template <typename EdgeRef>
1483 BpGraphCopy& edgeRef(EdgeRef& map) {
1484 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1485 EdgeRefMap, EdgeRef>(map));
1489 /// \brief Copy the edge cross references into the given map.
1491 /// This function copies the edge cross references (reverse references)
1492 /// into the given map. The parameter should be a map, whose key type
1493 /// is the Edge type of the destination graph, while the value type is
1494 /// the Edge type of the source graph.
1495 template <typename EdgeCrossRef>
1496 BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1497 _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1498 Edge, EdgeRefMap, EdgeCrossRef>(map));
1502 /// \brief Make a copy of the given edge map.
1504 /// This function makes a copy of the given edge map for the newly
1506 /// The key type of the new map \c tmap should be the Edge type of the
1507 /// destination graph, and the key type of the original map \c map
1508 /// should be the Edge type of the source graph.
1509 template <typename FromMap, typename ToMap>
1510 BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1511 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1512 EdgeRefMap, FromMap, ToMap>(map, tmap));
1516 /// \brief Make a copy of the given edge.
1518 /// This function makes a copy of the given edge.
1519 BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
1520 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1521 EdgeRefMap, TEdge>(edge, tedge));
1525 /// \brief Execute copying.
1527 /// This function executes the copying of the graph along with the
1528 /// copying of the assigned data.
1530 RedNodeRefMap redNodeRefMap(_from);
1531 BlueNodeRefMap blueNodeRefMap(_from);
1532 NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
1533 EdgeRefMap edgeRefMap(_from);
1534 ArcRefMap arcRefMap(_from, _to, edgeRefMap);
1535 _core_bits::BpGraphCopySelector<To>::
1536 copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
1537 for (int i = 0; i < int(_node_maps.size()); ++i) {
1538 _node_maps[i]->copy(_from, nodeRefMap);
1540 for (int i = 0; i < int(_red_maps.size()); ++i) {
1541 _red_maps[i]->copy(_from, redNodeRefMap);
1543 for (int i = 0; i < int(_blue_maps.size()); ++i) {
1544 _blue_maps[i]->copy(_from, blueNodeRefMap);
1546 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1547 _edge_maps[i]->copy(_from, edgeRefMap);
1549 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1550 _arc_maps[i]->copy(_from, arcRefMap);
1559 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1562 std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
1565 std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
1568 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1571 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1576 /// \brief Copy a graph to another graph.
1578 /// This function copies a graph to another graph.
1579 /// The complete usage of it is detailed in the BpGraphCopy class,
1580 /// but a short example shows a basic work:
1582 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1585 /// After the copy the \c nr map will contain the mapping from the
1586 /// nodes of the \c from graph to the nodes of the \c to graph and
1587 /// \c ecr will contain the mapping from the edges of the \c to graph
1588 /// to the edges of the \c from graph.
1590 /// \see BpGraphCopy
1591 template <typename From, typename To>
1592 BpGraphCopy<From, To>
1593 bpGraphCopy(const From& from, To& to) {
1594 return BpGraphCopy<From, To>(from, to);
1597 namespace _core_bits {
1599 template <typename Graph, typename Enable = void>
1600 struct FindArcSelector {
1601 typedef typename Graph::Node Node;
1602 typedef typename Graph::Arc Arc;
1603 static Arc find(const Graph &g, Node u, Node v, Arc e) {
1609 while (e != INVALID && g.target(e) != v) {
1616 template <typename Graph>
1617 struct FindArcSelector<
1619 typename enable_if<typename Graph::FindArcTag, void>::type>
1621 typedef typename Graph::Node Node;
1622 typedef typename Graph::Arc Arc;
1623 static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1624 return g.findArc(u, v, prev);
1629 /// \brief Find an arc between two nodes of a digraph.
1631 /// This function finds an arc from node \c u to node \c v in the
1634 /// If \c prev is \ref INVALID (this is the default value), then
1635 /// it finds the first arc from \c u to \c v. Otherwise it looks for
1636 /// the next arc from \c u to \c v after \c prev.
1637 /// \return The found arc or \ref INVALID if there is no such an arc.
1639 /// Thus you can iterate through each arc from \c u to \c v as it follows.
1641 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1646 /// \note \ref ConArcIt provides iterator interface for the same
1650 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1651 template <typename Graph>
1652 inline typename Graph::Arc
1653 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1654 typename Graph::Arc prev = INVALID) {
1655 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1658 /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1660 /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1661 /// a higher level interface for the \ref findArc() function. You can
1662 /// use it the following way:
1664 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1670 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1671 template <typename GR>
1672 class ConArcIt : public GR::Arc {
1673 typedef typename GR::Arc Parent;
1677 typedef typename GR::Arc Arc;
1678 typedef typename GR::Node Node;
1680 /// \brief Constructor.
1682 /// Construct a new ConArcIt iterating on the arcs that
1683 /// connects nodes \c u and \c v.
1684 ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
1685 Parent::operator=(findArc(_graph, u, v));
1688 /// \brief Constructor.
1690 /// Construct a new ConArcIt that continues the iterating from arc \c a.
1691 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
1693 /// \brief Increment operator.
1695 /// It increments the iterator and gives back the next arc.
1696 ConArcIt& operator++() {
1697 Parent::operator=(findArc(_graph, _graph.source(*this),
1698 _graph.target(*this), *this));
1705 namespace _core_bits {
1707 template <typename Graph, typename Enable = void>
1708 struct FindEdgeSelector {
1709 typedef typename Graph::Node Node;
1710 typedef typename Graph::Edge Edge;
1711 static Edge find(const Graph &g, Node u, Node v, Edge e) {
1715 g.firstInc(e, b, u);
1720 while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1725 g.firstInc(e, b, u);
1730 while (e != INVALID && (!b || g.v(e) != v)) {
1738 template <typename Graph>
1739 struct FindEdgeSelector<
1741 typename enable_if<typename Graph::FindEdgeTag, void>::type>
1743 typedef typename Graph::Node Node;
1744 typedef typename Graph::Edge Edge;
1745 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1746 return g.findEdge(u, v, prev);
1751 /// \brief Find an edge between two nodes of a graph.
1753 /// This function finds an edge from node \c u to node \c v in graph \c g.
1754 /// If node \c u and node \c v is equal then each loop edge
1755 /// will be enumerated once.
1757 /// If \c prev is \ref INVALID (this is the default value), then
1758 /// it finds the first edge from \c u to \c v. Otherwise it looks for
1759 /// the next edge from \c u to \c v after \c prev.
1760 /// \return The found edge or \ref INVALID if there is no such an edge.
1762 /// Thus you can iterate through each edge between \c u and \c v
1765 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1770 /// \note \ref ConEdgeIt provides iterator interface for the same
1774 template <typename Graph>
1775 inline typename Graph::Edge
1776 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1777 typename Graph::Edge p = INVALID) {
1778 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1781 /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1783 /// Iterator for iterating on parallel edges connecting the same nodes.
1784 /// It is a higher level interface for the findEdge() function. You can
1785 /// use it the following way:
1787 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1793 template <typename GR>
1794 class ConEdgeIt : public GR::Edge {
1795 typedef typename GR::Edge Parent;
1799 typedef typename GR::Edge Edge;
1800 typedef typename GR::Node Node;
1802 /// \brief Constructor.
1804 /// Construct a new ConEdgeIt iterating on the edges that
1805 /// connects nodes \c u and \c v.
1806 ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1807 Parent::operator=(findEdge(_graph, _u, _v));
1810 /// \brief Constructor.
1812 /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1813 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
1815 /// \brief Increment operator.
1817 /// It increments the iterator and gives back the next edge.
1818 ConEdgeIt& operator++() {
1819 Parent::operator=(findEdge(_graph, _u, _v, *this));
1828 ///Dynamic arc look-up between given endpoints.
1830 ///Using this class, you can find an arc in a digraph from a given
1831 ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1832 ///where <em>d</em> is the out-degree of the source node.
1834 ///It is possible to find \e all parallel arcs between two nodes with
1835 ///the \c operator() member.
1837 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1838 ///\ref AllArcLookUp if your digraph is not changed so frequently.
1840 ///This class uses a self-adjusting binary search tree, the Splay tree
1841 ///of Sleator and Tarjan to guarantee the logarithmic amortized
1842 ///time bound for arc look-ups. This class also guarantees the
1843 ///optimal time bound in a constant factor for any distribution of
1846 ///\tparam GR The type of the underlying digraph.
1850 template <typename GR>
1852 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
1854 typedef typename ItemSetTraits<GR, typename GR::Arc>
1855 ::ItemNotifier::ObserverBase Parent;
1857 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1861 /// The Digraph type
1866 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
1868 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
1872 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
1874 virtual void add(const Node& node) {
1876 Parent::set(node, INVALID);
1879 virtual void add(const std::vector<Node>& nodes) {
1881 for (int i = 0; i < int(nodes.size()); ++i) {
1882 Parent::set(nodes[i], INVALID);
1886 virtual void build() {
1889 typename Parent::Notifier* nf = Parent::notifier();
1890 for (nf->first(it); it != INVALID; nf->next(it)) {
1891 Parent::set(it, INVALID);
1899 ArcLess(const Digraph &_g) : g(_g) {}
1900 bool operator()(Arc a,Arc b) const
1902 return g.target(a)<g.target(b);
1910 typename Digraph::template ArcMap<Arc> _parent;
1911 typename Digraph::template ArcMap<Arc> _left;
1912 typename Digraph::template ArcMap<Arc> _right;
1920 ///It builds up the search database.
1921 DynArcLookUp(const Digraph &g)
1922 : _g(g),_head(g),_parent(g),_left(g),_right(g)
1924 Parent::attach(_g.notifier(typename Digraph::Arc()));
1930 virtual void add(const Arc& arc) {
1934 virtual void add(const std::vector<Arc>& arcs) {
1935 for (int i = 0; i < int(arcs.size()); ++i) {
1940 virtual void erase(const Arc& arc) {
1944 virtual void erase(const std::vector<Arc>& arcs) {
1945 for (int i = 0; i < int(arcs.size()); ++i) {
1950 virtual void build() {
1954 virtual void clear() {
1955 for(NodeIt n(_g);n!=INVALID;++n) {
1960 void insert(Arc arc) {
1961 Node s = _g.source(arc);
1962 Node t = _g.target(arc);
1963 _left[arc] = INVALID;
1964 _right[arc] = INVALID;
1969 _parent[arc] = INVALID;
1973 if (t < _g.target(e)) {
1974 if (_left[e] == INVALID) {
1983 if (_right[e] == INVALID) {
1995 void remove(Arc arc) {
1996 if (_left[arc] == INVALID) {
1997 if (_right[arc] != INVALID) {
1998 _parent[_right[arc]] = _parent[arc];
2000 if (_parent[arc] != INVALID) {
2001 if (_left[_parent[arc]] == arc) {
2002 _left[_parent[arc]] = _right[arc];
2004 _right[_parent[arc]] = _right[arc];
2007 _head[_g.source(arc)] = _right[arc];
2009 } else if (_right[arc] == INVALID) {
2010 _parent[_left[arc]] = _parent[arc];
2011 if (_parent[arc] != INVALID) {
2012 if (_left[_parent[arc]] == arc) {
2013 _left[_parent[arc]] = _left[arc];
2015 _right[_parent[arc]] = _left[arc];
2018 _head[_g.source(arc)] = _left[arc];
2022 if (_right[e] != INVALID) {
2024 while (_right[e] != INVALID) {
2028 _right[_parent[e]] = _left[e];
2029 if (_left[e] != INVALID) {
2030 _parent[_left[e]] = _parent[e];
2033 _left[e] = _left[arc];
2034 _parent[_left[arc]] = e;
2035 _right[e] = _right[arc];
2036 _parent[_right[arc]] = e;
2038 _parent[e] = _parent[arc];
2039 if (_parent[arc] != INVALID) {
2040 if (_left[_parent[arc]] == arc) {
2041 _left[_parent[arc]] = e;
2043 _right[_parent[arc]] = e;
2048 _right[e] = _right[arc];
2049 _parent[_right[arc]] = e;
2050 _parent[e] = _parent[arc];
2052 if (_parent[arc] != INVALID) {
2053 if (_left[_parent[arc]] == arc) {
2054 _left[_parent[arc]] = e;
2056 _right[_parent[arc]] = e;
2059 _head[_g.source(arc)] = e;
2065 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2070 Arc left = refreshRec(v,a,m-1);
2074 _left[me] = INVALID;
2077 Arc right = refreshRec(v,m+1,b);
2079 _parent[right] = me;
2081 _right[me] = INVALID;
2087 for(NodeIt n(_g);n!=INVALID;++n) {
2089 for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
2091 std::sort(v.begin(),v.end(),ArcLess(_g));
2092 Arc head = refreshRec(v,0,v.size()-1);
2094 _parent[head] = INVALID;
2096 else _head[n] = INVALID;
2102 _parent[v] = _parent[w];
2104 _left[w] = _right[v];
2106 if (_parent[v] != INVALID) {
2107 if (_right[_parent[v]] == w) {
2108 _right[_parent[v]] = v;
2110 _left[_parent[v]] = v;
2113 if (_left[w] != INVALID){
2114 _parent[_left[w]] = w;
2120 _parent[v] = _parent[w];
2122 _right[w] = _left[v];
2124 if (_parent[v] != INVALID){
2125 if (_left[_parent[v]] == w) {
2126 _left[_parent[v]] = v;
2128 _right[_parent[v]] = v;
2131 if (_right[w] != INVALID){
2132 _parent[_right[w]] = w;
2137 while (_parent[v] != INVALID) {
2138 if (v == _left[_parent[v]]) {
2139 if (_parent[_parent[v]] == INVALID) {
2142 if (_parent[v] == _left[_parent[_parent[v]]]) {
2151 if (_parent[_parent[v]] == INVALID) {
2154 if (_parent[v] == _left[_parent[_parent[v]]]) {
2164 _head[_g.source(v)] = v;
2170 ///Find an arc between two nodes.
2172 ///Find an arc between two nodes.
2173 ///\param s The source node.
2174 ///\param t The target node.
2175 ///\param p The previous arc between \c s and \c t. It it is INVALID or
2176 ///not given, the operator finds the first appropriate arc.
2177 ///\return An arc from \c s to \c t after \c p or
2178 ///\ref INVALID if there is no more.
2180 ///For example, you can count the number of arcs from \c u to \c v in the
2183 ///DynArcLookUp<ListDigraph> ae(g);
2186 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
2189 ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
2190 ///amortized time, specifically, the time complexity of the lookups
2191 ///is equal to the optimal search tree implementation for the
2192 ///current query distribution in a constant factor.
2194 ///\note This is a dynamic data structure, therefore the data
2195 ///structure is updated after each graph alteration. Thus although
2196 ///this data structure is theoretically faster than \ref ArcLookUp
2197 ///and \ref AllArcLookUp, it often provides worse performance than
2199 Arc operator()(Node s, Node t, Arc p = INVALID) const {
2202 if (a == INVALID) return INVALID;
2205 if (_g.target(a) < t) {
2206 if (_right[a] == INVALID) {
2207 const_cast<DynArcLookUp&>(*this).splay(a);
2213 if (_g.target(a) == t) {
2216 if (_left[a] == INVALID) {
2217 const_cast<DynArcLookUp&>(*this).splay(a);
2226 if (_right[a] != INVALID) {
2228 while (_left[a] != INVALID) {
2231 const_cast<DynArcLookUp&>(*this).splay(a);
2233 while (_parent[a] != INVALID && _right[_parent[a]] == a) {
2236 if (_parent[a] == INVALID) {
2240 const_cast<DynArcLookUp&>(*this).splay(a);
2243 if (_g.target(a) == t) return a;
2244 else return INVALID;
2250 ///Fast arc look-up between given endpoints.
2252 ///Using this class, you can find an arc in a digraph from a given
2253 ///source to a given target in time <em>O</em>(log<em>d</em>),
2254 ///where <em>d</em> is the out-degree of the source node.
2256 ///It is not possible to find \e all parallel arcs between two nodes.
2257 ///Use \ref AllArcLookUp for this purpose.
2259 ///\warning This class is static, so you should call refresh() (or at
2260 ///least refresh(Node)) to refresh this data structure whenever the
2261 ///digraph changes. This is a time consuming (superlinearly proportional
2262 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
2264 ///\tparam GR The type of the underlying digraph.
2271 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2275 /// The Digraph type
2280 typename Digraph::template NodeMap<Arc> _head;
2281 typename Digraph::template ArcMap<Arc> _left;
2282 typename Digraph::template ArcMap<Arc> _right;
2287 ArcLess(const Digraph &_g) : g(_g) {}
2288 bool operator()(Arc a,Arc b) const
2290 return g.target(a)<g.target(b);
2300 ///It builds up the search database, which remains valid until the digraph
2302 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2305 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2309 _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2310 _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2314 ///Refresh the search data structure at a node.
2316 ///Build up the search database of node \c n.
2318 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
2319 ///is the number of the outgoing arcs of \c n.
2320 void refresh(Node n)
2323 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2325 std::sort(v.begin(),v.end(),ArcLess(_g));
2326 _head[n]=refreshRec(v,0,v.size()-1);
2328 else _head[n]=INVALID;
2330 ///Refresh the full data structure.
2332 ///Build up the full search database. In fact, it simply calls
2333 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2335 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
2336 ///the number of the arcs in the digraph and <em>D</em> is the maximum
2337 ///out-degree of the digraph.
2340 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2343 ///Find an arc between two nodes.
2345 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
2346 ///where <em>d</em> is the number of outgoing arcs of \c s.
2347 ///\param s The source node.
2348 ///\param t The target node.
2349 ///\return An arc from \c s to \c t if there exists,
2350 ///\ref INVALID otherwise.
2352 ///\warning If you change the digraph, refresh() must be called before using
2353 ///this operator. If you change the outgoing arcs of
2354 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
2355 Arc operator()(Node s, Node t) const
2359 e!=INVALID&&_g.target(e)!=t;
2360 e = t < _g.target(e)?_left[e]:_right[e]) ;
2366 ///Fast look-up of all arcs between given endpoints.
2368 ///This class is the same as \ref ArcLookUp, with the addition
2369 ///that it makes it possible to find all parallel arcs between given
2372 ///\warning This class is static, so you should call refresh() (or at
2373 ///least refresh(Node)) to refresh this data structure whenever the
2374 ///digraph changes. This is a time consuming (superlinearly proportional
2375 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
2377 ///\tparam GR The type of the underlying digraph.
2382 class AllArcLookUp : public ArcLookUp<GR>
2384 using ArcLookUp<GR>::_g;
2385 using ArcLookUp<GR>::_right;
2386 using ArcLookUp<GR>::_left;
2387 using ArcLookUp<GR>::_head;
2389 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2391 typename GR::template ArcMap<Arc> _next;
2393 Arc refreshNext(Arc head,Arc next=INVALID)
2395 if(head==INVALID) return next;
2397 next=refreshNext(_right[head],next);
2398 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2400 return refreshNext(_left[head],head);
2406 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2411 /// The Digraph type
2418 ///It builds up the search database, which remains valid until the digraph
2420 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
2422 ///Refresh the data structure at a node.
2424 ///Build up the search database of node \c n.
2426 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
2427 ///the number of the outgoing arcs of \c n.
2428 void refresh(Node n)
2430 ArcLookUp<GR>::refresh(n);
2431 refreshNext(_head[n]);
2434 ///Refresh the full data structure.
2436 ///Build up the full search database. In fact, it simply calls
2437 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2439 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
2440 ///the number of the arcs in the digraph and <em>D</em> is the maximum
2441 ///out-degree of the digraph.
2444 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2447 ///Find an arc between two nodes.
2449 ///Find an arc between two nodes.
2450 ///\param s The source node.
2451 ///\param t The target node.
2452 ///\param prev The previous arc between \c s and \c t. It it is INVALID or
2453 ///not given, the operator finds the first appropriate arc.
2454 ///\return An arc from \c s to \c t after \c prev or
2455 ///\ref INVALID if there is no more.
2457 ///For example, you can count the number of arcs from \c u to \c v in the
2460 ///AllArcLookUp<ListDigraph> ae(g);
2463 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
2466 ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
2467 ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
2468 ///consecutive arcs are found in constant time.
2470 ///\warning If you change the digraph, refresh() must be called before using
2471 ///this operator. If you change the outgoing arcs of
2472 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
2474 Arc operator()(Node s, Node t, Arc prev=INVALID) const
2481 e!=INVALID&&_g.target(e)!=t;
2482 e = t < _g.target(e)?_left[e]:_right[e]) ;
2492 else return _next[prev];