1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
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 // 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
37 #pragma warning( disable : 4250 4355 4503 4800 4996 )
41 ///\brief LEMON core utilities.
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.
49 /// \brief Dummy type to make it easier to create invalid iterators.
51 /// Dummy type to make it easier to create invalid iterators.
52 /// See \ref INVALID for the usage.
55 bool operator==(Invalid) { return true; }
56 bool operator!=(Invalid) { return false; }
57 bool operator< (Invalid) { return false; }
60 /// \brief Invalid iterators.
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();
67 extern const Invalid INVALID;
70 /// \addtogroup gutils
73 ///Create convenience typedefs for the digraph types and iterators
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.
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()
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
97 ///Create convenience typedefs for the digraph types and iterators
99 ///\see DIGRAPH_TYPEDEFS
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
117 ///Create convenience typedefs for the graph types and iterators
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,
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()
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
136 ///Create convenience typedefs for the graph types and iterators
138 ///\see GRAPH_TYPEDEFS
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
151 ///Create convenience typedefs for the bipartite graph types and iterators
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.
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()
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
174 ///Create convenience typedefs for the bipartite graph types and iterators
176 ///\see BPGRAPH_TYPEDEFS
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
193 /// \brief Function to count the items in a graph.
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;
202 for (ItemIt it(g); it != INVALID; ++it) {
210 namespace _core_bits {
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);
219 template <typename Graph>
220 struct CountNodesSelector<
222 enable_if<typename Graph::NodeNumTag, void>::type>
224 static int count(const Graph &g) {
230 /// \brief Function to count the nodes in the graph.
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).
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);
244 namespace _graph_utils_bits {
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);
253 template <typename Graph>
254 struct CountRedNodesSelector<
256 enable_if<typename Graph::NodeNumTag, void>::type>
258 static int count(const Graph &g) {
264 /// \brief Function to count the red nodes in the graph.
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).
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);
278 namespace _graph_utils_bits {
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);
287 template <typename Graph>
288 struct CountBlueNodesSelector<
290 enable_if<typename Graph::NodeNumTag, void>::type>
292 static int count(const Graph &g) {
298 /// \brief Function to count the blue nodes in the graph.
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).
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);
314 namespace _core_bits {
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);
323 template <typename Graph>
324 struct CountArcsSelector<
326 typename enable_if<typename Graph::ArcNumTag, void>::type>
328 static int count(const Graph &g) {
334 /// \brief Function to count the arcs in the graph.
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).
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);
350 namespace _core_bits {
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);
359 template <typename Graph>
360 struct CountEdgesSelector<
362 typename enable_if<typename Graph::EdgeNumTag, void>::type>
364 static int count(const Graph &g) {
370 /// \brief Function to count the edges in the graph.
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).
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);
386 template <typename Graph, typename DegIt>
387 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
389 for (DegIt it(_g, _n); it != INVALID; ++it) {
395 /// \brief Function to count the number of the out-arcs from node \c n.
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);
404 /// \brief Function to count the number of the in-arcs to node \c n.
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);
413 /// \brief Function to count the number of the inc-edges to node \c n.
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);
422 namespace _core_bits {
424 template <typename Digraph, typename Item, typename RefMap>
427 virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
429 virtual ~MapCopyBase() {}
432 template <typename Digraph, typename Item, typename RefMap,
433 typename FromMap, typename ToMap>
434 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
437 MapCopy(const FromMap& map, ToMap& tmap)
438 : _map(map), _tmap(tmap) {}
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]);
452 template <typename Digraph, typename Item, typename RefMap, typename It>
453 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
456 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
458 virtual void copy(const Digraph&, const RefMap& refMap) {
467 template <typename Digraph, typename Item, typename RefMap, typename Ref>
468 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
471 RefCopy(Ref& map) : _map(map) {}
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]);
484 template <typename Digraph, typename Item, typename RefMap,
486 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
489 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
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);
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) {
508 for (typename From::NodeIt it(from); it != INVALID; ++it) {
509 nodeRefMap[it] = to.addNode();
511 for (typename From::ArcIt it(from); it != INVALID; ++it) {
512 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
513 nodeRefMap[from.target(it)]);
518 template <typename Digraph>
519 struct DigraphCopySelector<
521 typename enable_if<typename Digraph::BuildTag, void>::type>
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);
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) {
536 for (typename From::NodeIt it(from); it != INVALID; ++it) {
537 nodeRefMap[it] = to.addNode();
539 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
540 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
541 nodeRefMap[from.v(it)]);
546 template <typename Graph>
547 struct GraphCopySelector<
549 typename enable_if<typename Graph::BuildTag, void>::type>
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);
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) {
568 for (typename From::RedIt it(from); it != INVALID; ++it) {
569 redNodeRefMap[it] = to.addRedNode();
571 for (typename From::BlueIt it(from); it != INVALID; ++it) {
572 blueNodeRefMap[it] = to.addBlueNode();
574 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
575 edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
576 blueNodeRefMap[from.blueNode(it)]);
581 template <typename BpGraph>
582 struct BpGraphCopySelector<
584 typename enable_if<typename BpGraph::BuildTag, void>::type>
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);
598 /// \brief Check whether a graph is undirected.
600 /// This function returns \c true if the given graph is undirected.
602 template <typename GR>
603 bool undirected(const GR& g) { return false; }
605 template <typename GR>
606 typename enable_if<UndirectedTagIndicator<GR>, bool>::type
607 undirected(const GR&) {
610 template <typename GR>
611 typename disable_if<UndirectedTagIndicator<GR>, bool>::type
612 undirected(const GR&) {
617 /// \brief Class to copy a digraph.
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.
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
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
632 /// The next code copies a digraph with several data:
634 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
635 /// // Create references for the nodes
636 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
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);
646 /// OrigGraph::Node on;
647 /// NewGraph::Node nn;
649 /// // Execute copying
652 template <typename From, typename To>
656 typedef typename From::Node Node;
657 typedef typename From::NodeIt NodeIt;
658 typedef typename From::Arc Arc;
659 typedef typename From::ArcIt ArcIt;
661 typedef typename To::Node TNode;
662 typedef typename To::Arc TArc;
664 typedef typename From::template NodeMap<TNode> NodeRefMap;
665 typedef typename From::template ArcMap<TArc> ArcRefMap;
669 /// \brief Constructor of DigraphCopy.
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) {}
676 /// \brief Destructor of DigraphCopy
678 /// Destructor of DigraphCopy.
680 for (int i = 0; i < int(_node_maps.size()); ++i) {
681 delete _node_maps[i];
683 for (int i = 0; i < int(_arc_maps.size()); ++i) {
689 /// \brief Copy the node references into the given map.
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));
702 /// \brief Copy the node cross references into the given map.
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));
715 /// \brief Make a copy of the given node map.
717 /// This function makes a copy of the given node map for the newly
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));
729 /// \brief Make a copy of the given node.
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));
738 /// \brief Copy the arc references into the given map.
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));
751 /// \brief Copy the arc cross references into the given map.
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));
764 /// \brief Make a copy of the given arc map.
766 /// This function makes a copy of the given arc map for the newly
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));
778 /// \brief Make a copy of the given arc.
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));
787 /// \brief Execute copying.
789 /// This function executes the copying of the digraph along with the
790 /// copying of the assigned data.
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);
799 for (int i = 0; i < int(_arc_maps.size()); ++i) {
800 _arc_maps[i]->copy(_from, arcRefMap);
809 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
812 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
817 /// \brief Copy a digraph to another digraph.
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:
823 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
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.
832 template <typename From, typename To>
833 DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
834 return DigraphCopy<From, To>(from, to);
837 /// \brief Class to copy a graph.
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.
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
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
852 /// The next code copies a graph with several data:
854 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
855 /// // Create references for the nodes
856 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
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);
866 /// OrigGraph::Node on;
867 /// NewGraph::Node nn;
869 /// // Execute copying
872 template <typename From, typename To>
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;
883 typedef typename To::Node TNode;
884 typedef typename To::Arc TArc;
885 typedef typename To::Edge TEdge;
887 typedef typename From::template NodeMap<TNode> NodeRefMap;
888 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
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) {}
896 typedef typename From::Arc Key;
897 typedef typename To::Arc Value;
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);
909 const EdgeRefMap& _edge_ref;
910 const NodeRefMap& _node_ref;
915 /// \brief Constructor of GraphCopy.
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) {}
922 /// \brief Destructor of GraphCopy
924 /// Destructor of GraphCopy.
926 for (int i = 0; i < int(_node_maps.size()); ++i) {
927 delete _node_maps[i];
929 for (int i = 0; i < int(_arc_maps.size()); ++i) {
932 for (int i = 0; i < int(_edge_maps.size()); ++i) {
933 delete _edge_maps[i];
937 /// \brief Copy the node references into the given map.
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));
950 /// \brief Copy the node cross references into the given map.
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));
963 /// \brief Make a copy of the given node map.
965 /// This function makes a copy of the given node map for the newly
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));
977 /// \brief Make a copy of the given node.
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));
986 /// \brief Copy the arc references into the given map.
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));
999 /// \brief Copy the arc cross references into the given map.
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));
1012 /// \brief Make a copy of the given arc map.
1014 /// This function makes a copy of the given arc map for the newly
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));
1026 /// \brief Make a copy of the given arc.
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));
1035 /// \brief Copy the edge references into the given map.
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));
1048 /// \brief Copy the edge cross references into the given map.
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));
1061 /// \brief Make a copy of the given edge map.
1063 /// This function makes a copy of the given edge map for the newly
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));
1075 /// \brief Make a copy of the given edge.
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));
1084 /// \brief Execute copying.
1086 /// This function executes the copying of the graph along with the
1087 /// copying of the assigned data.
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);
1097 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1098 _edge_maps[i]->copy(_from, edgeRefMap);
1100 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1101 _arc_maps[i]->copy(_from, arcRefMap);
1110 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1113 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1116 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1121 /// \brief Copy a graph to another graph.
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:
1127 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
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.
1136 template <typename From, typename To>
1138 graphCopy(const From& from, To& to) {
1139 return GraphCopy<From, To>(from, to);
1142 /// \brief Class to copy a bipartite graph.
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.
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.
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
1158 /// The next code copies a graph with several data:
1160 /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
1161 /// // Create references for the nodes
1162 /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
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);
1172 /// OrigBpGraph::Node on;
1173 /// NewBpGraph::Node nn;
1174 /// cg.node(on, nn);
1175 /// // Execute copying
1178 template <typename From, typename To>
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;
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;
1197 typedef typename From::template RedMap<TRedNode> RedNodeRefMap;
1198 typedef typename From::template BlueMap<TBlueNode> BlueNodeRefMap;
1199 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
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) {}
1207 typedef typename From::Node Key;
1208 typedef typename To::Node Value;
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];
1215 return _blue_node_ref[red_blue_pair.second];
1220 const RedNodeRefMap& _red_node_ref;
1221 const BlueNodeRefMap& _blue_node_ref;
1225 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
1226 : _from(from), _to(to), _edge_ref(edge_ref) {}
1228 typedef typename From::Arc Key;
1229 typedef typename To::Arc Value;
1231 Value operator[](const Key& key) const {
1232 return _to.direct(_edge_ref[key], _from.direction(key));
1237 const EdgeRefMap& _edge_ref;
1242 /// \brief Constructor of BpGraphCopy.
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) {}
1249 /// \brief Destructor of BpGraphCopy
1251 /// Destructor of BpGraphCopy.
1253 for (int i = 0; i < int(_node_maps.size()); ++i) {
1254 delete _node_maps[i];
1256 for (int i = 0; i < int(_red_maps.size()); ++i) {
1257 delete _red_maps[i];
1259 for (int i = 0; i < int(_blue_maps.size()); ++i) {
1260 delete _blue_maps[i];
1262 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1263 delete _arc_maps[i];
1265 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1266 delete _edge_maps[i];
1270 /// \brief Copy the node references into the given map.
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));
1283 /// \brief Copy the node cross references into the given map.
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));
1296 /// \brief Make a copy of the given node map.
1298 /// This function makes a copy of the given node map for the newly
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));
1310 /// \brief Make a copy of the given node.
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));
1319 /// \brief Copy the red node references into the given map.
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));
1332 /// \brief Copy the red node cross references into the given map.
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
1339 template <typename RedCrossRef>
1340 BpGraphCopy& redCrossRef(RedCrossRef& map) {
1341 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
1342 RedNodeRefMap, RedCrossRef>(map));
1346 /// \brief Make a copy of the given red node map.
1348 /// This function makes a copy of the given red node map for the newly
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
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));
1361 /// \brief Make a copy of the given red node.
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));
1370 /// \brief Copy the blue node references into the given map.
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));
1383 /// \brief Copy the blue node cross references into the given map.
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
1390 template <typename BlueCrossRef>
1391 BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1392 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
1393 BlueNodeRefMap, BlueCrossRef>(map));
1397 /// \brief Make a copy of the given blue node map.
1399 /// This function makes a copy of the given blue node map for the newly
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
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));
1412 /// \brief Make a copy of the given blue node.
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));
1421 /// \brief Copy the arc references into the given map.
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));
1434 /// \brief Copy the arc cross references into the given map.
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));
1447 /// \brief Make a copy of the given arc map.
1449 /// This function makes a copy of the given arc map for the newly
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));
1461 /// \brief Make a copy of the given arc.
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));
1470 /// \brief Copy the edge references into the given map.
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));
1483 /// \brief Copy the edge cross references into the given map.
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));
1496 /// \brief Make a copy of the given edge map.
1498 /// This function makes a copy of the given edge map for the newly
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));
1510 /// \brief Make a copy of the given edge.
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));
1519 /// \brief Execute copying.
1521 /// This function executes the copying of the graph along with the
1522 /// copying of the assigned data.
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);
1534 for (int i = 0; i < int(_red_maps.size()); ++i) {
1535 _red_maps[i]->copy(_from, redNodeRefMap);
1537 for (int i = 0; i < int(_blue_maps.size()); ++i) {
1538 _blue_maps[i]->copy(_from, blueNodeRefMap);
1540 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1541 _edge_maps[i]->copy(_from, edgeRefMap);
1543 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1544 _arc_maps[i]->copy(_from, arcRefMap);
1553 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1556 std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
1559 std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
1562 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1565 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1570 /// \brief Copy a graph to another graph.
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:
1576 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
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.
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);
1591 namespace _core_bits {
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) {
1603 while (e != INVALID && g.target(e) != v) {
1610 template <typename Graph>
1611 struct FindArcSelector<
1613 typename enable_if<typename Graph::FindArcTag, void>::type>
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);
1623 /// \brief Find an arc between two nodes of a digraph.
1625 /// This function finds an arc from node \c u to node \c v in the
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.
1633 /// Thus you can iterate through each arc from \c u to \c v as it follows.
1635 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1640 /// \note \ref ConArcIt provides iterator interface for the same
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);
1652 /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
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:
1658 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1664 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1665 template <typename GR>
1666 class ConArcIt : public GR::Arc {
1667 typedef typename GR::Arc Parent;
1671 typedef typename GR::Arc Arc;
1672 typedef typename GR::Node Node;
1674 /// \brief Constructor.
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));
1682 /// \brief Constructor.
1684 /// Construct a new ConArcIt that continues the iterating from arc \c a.
1685 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
1687 /// \brief Increment operator.
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));
1699 namespace _core_bits {
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) {
1709 g.firstInc(e, b, u);
1714 while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1719 g.firstInc(e, b, u);
1724 while (e != INVALID && (!b || g.v(e) != v)) {
1732 template <typename Graph>
1733 struct FindEdgeSelector<
1735 typename enable_if<typename Graph::FindEdgeTag, void>::type>
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);
1745 /// \brief Find an edge between two nodes of a graph.
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.
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.
1756 /// Thus you can iterate through each edge between \c u and \c v
1759 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1764 /// \note \ref ConEdgeIt provides iterator interface for the same
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);
1775 /// \brief Iterator for iterating on parallel edges connecting the same nodes.
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:
1781 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1787 template <typename GR>
1788 class ConEdgeIt : public GR::Edge {
1789 typedef typename GR::Edge Parent;
1793 typedef typename GR::Edge Edge;
1794 typedef typename GR::Node Node;
1796 /// \brief Constructor.
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));
1804 /// \brief Constructor.
1806 /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1807 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
1809 /// \brief Increment operator.
1811 /// It increments the iterator and gives back the next edge.
1812 ConEdgeIt& operator++() {
1813 Parent::operator=(findEdge(_graph, _u, _v, *this));
1822 ///Dynamic arc look-up between given endpoints.
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.
1828 ///It is possible to find \e all parallel arcs between two nodes with
1829 ///the \c operator() member.
1831 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1832 ///\ref AllArcLookUp if your digraph is not changed so frequently.
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
1840 ///\tparam GR The type of the underlying digraph.
1844 template <typename GR>
1846 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
1848 typedef typename ItemSetTraits<GR, typename GR::Arc>
1849 ::ItemNotifier::ObserverBase Parent;
1851 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1855 /// The Digraph type
1860 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
1862 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
1866 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
1868 virtual void add(const Node& node) {
1870 Parent::set(node, INVALID);
1873 virtual void add(const std::vector<Node>& nodes) {
1875 for (int i = 0; i < int(nodes.size()); ++i) {
1876 Parent::set(nodes[i], INVALID);
1880 virtual void build() {
1883 typename Parent::Notifier* nf = Parent::notifier();
1884 for (nf->first(it); it != INVALID; nf->next(it)) {
1885 Parent::set(it, INVALID);
1893 ArcLess(const Digraph &_g) : g(_g) {}
1894 bool operator()(Arc a,Arc b) const
1896 return g.target(a)<g.target(b);
1904 typename Digraph::template ArcMap<Arc> _parent;
1905 typename Digraph::template ArcMap<Arc> _left;
1906 typename Digraph::template ArcMap<Arc> _right;
1914 ///It builds up the search database.
1915 DynArcLookUp(const Digraph &g)
1916 : _g(g),_head(g),_parent(g),_left(g),_right(g)
1918 Parent::attach(_g.notifier(typename Digraph::Arc()));
1924 virtual void add(const Arc& arc) {
1928 virtual void add(const std::vector<Arc>& arcs) {
1929 for (int i = 0; i < int(arcs.size()); ++i) {
1934 virtual void erase(const Arc& arc) {
1938 virtual void erase(const std::vector<Arc>& arcs) {
1939 for (int i = 0; i < int(arcs.size()); ++i) {
1944 virtual void build() {
1948 virtual void clear() {
1949 for(NodeIt n(_g);n!=INVALID;++n) {
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;
1963 _parent[arc] = INVALID;
1967 if (t < _g.target(e)) {
1968 if (_left[e] == INVALID) {
1977 if (_right[e] == INVALID) {
1989 void remove(Arc arc) {
1990 if (_left[arc] == INVALID) {
1991 if (_right[arc] != INVALID) {
1992 _parent[_right[arc]] = _parent[arc];
1994 if (_parent[arc] != INVALID) {
1995 if (_left[_parent[arc]] == arc) {
1996 _left[_parent[arc]] = _right[arc];
1998 _right[_parent[arc]] = _right[arc];
2001 _head[_g.source(arc)] = _right[arc];
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];
2009 _right[_parent[arc]] = _left[arc];
2012 _head[_g.source(arc)] = _left[arc];
2016 if (_right[e] != INVALID) {
2018 while (_right[e] != INVALID) {
2022 _right[_parent[e]] = _left[e];
2023 if (_left[e] != INVALID) {
2024 _parent[_left[e]] = _parent[e];
2027 _left[e] = _left[arc];
2028 _parent[_left[arc]] = e;
2029 _right[e] = _right[arc];
2030 _parent[_right[arc]] = e;
2032 _parent[e] = _parent[arc];
2033 if (_parent[arc] != INVALID) {
2034 if (_left[_parent[arc]] == arc) {
2035 _left[_parent[arc]] = e;
2037 _right[_parent[arc]] = e;
2042 _right[e] = _right[arc];
2043 _parent[_right[arc]] = e;
2044 _parent[e] = _parent[arc];
2046 if (_parent[arc] != INVALID) {
2047 if (_left[_parent[arc]] == arc) {
2048 _left[_parent[arc]] = e;
2050 _right[_parent[arc]] = e;
2053 _head[_g.source(arc)] = e;
2059 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2064 Arc left = refreshRec(v,a,m-1);
2068 _left[me] = INVALID;
2071 Arc right = refreshRec(v,m+1,b);
2073 _parent[right] = me;
2075 _right[me] = INVALID;
2081 for(NodeIt n(_g);n!=INVALID;++n) {
2083 for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
2085 std::sort(v.begin(),v.end(),ArcLess(_g));
2086 Arc head = refreshRec(v,0,v.size()-1);
2088 _parent[head] = INVALID;
2090 else _head[n] = INVALID;
2096 _parent[v] = _parent[w];
2098 _left[w] = _right[v];
2100 if (_parent[v] != INVALID) {
2101 if (_right[_parent[v]] == w) {
2102 _right[_parent[v]] = v;
2104 _left[_parent[v]] = v;
2107 if (_left[w] != INVALID){
2108 _parent[_left[w]] = w;
2114 _parent[v] = _parent[w];
2116 _right[w] = _left[v];
2118 if (_parent[v] != INVALID){
2119 if (_left[_parent[v]] == w) {
2120 _left[_parent[v]] = v;
2122 _right[_parent[v]] = v;
2125 if (_right[w] != INVALID){
2126 _parent[_right[w]] = w;
2131 while (_parent[v] != INVALID) {
2132 if (v == _left[_parent[v]]) {
2133 if (_parent[_parent[v]] == INVALID) {
2136 if (_parent[v] == _left[_parent[_parent[v]]]) {
2145 if (_parent[_parent[v]] == INVALID) {
2148 if (_parent[v] == _left[_parent[_parent[v]]]) {
2158 _head[_g.source(v)] = v;
2164 ///Find an arc between two nodes.
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.
2174 ///For example, you can count the number of arcs from \c u to \c v in the
2177 ///DynArcLookUp<ListDigraph> ae(g);
2180 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
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.
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
2193 Arc operator()(Node s, Node t, Arc p = INVALID) const {
2196 if (a == INVALID) return INVALID;
2199 if (_g.target(a) < t) {
2200 if (_right[a] == INVALID) {
2201 const_cast<DynArcLookUp&>(*this).splay(a);
2207 if (_g.target(a) == t) {
2210 if (_left[a] == INVALID) {
2211 const_cast<DynArcLookUp&>(*this).splay(a);
2220 if (_right[a] != INVALID) {
2222 while (_left[a] != INVALID) {
2225 const_cast<DynArcLookUp&>(*this).splay(a);
2227 while (_parent[a] != INVALID && _right[_parent[a]] == a) {
2230 if (_parent[a] == INVALID) {
2234 const_cast<DynArcLookUp&>(*this).splay(a);
2237 if (_g.target(a) == t) return a;
2238 else return INVALID;
2244 ///Fast arc look-up between given endpoints.
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.
2250 ///It is not possible to find \e all parallel arcs between two nodes.
2251 ///Use \ref AllArcLookUp for this purpose.
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).
2258 ///\tparam GR The type of the underlying digraph.
2265 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2269 /// The Digraph type
2274 typename Digraph::template NodeMap<Arc> _head;
2275 typename Digraph::template ArcMap<Arc> _left;
2276 typename Digraph::template ArcMap<Arc> _right;
2281 ArcLess(const Digraph &_g) : g(_g) {}
2282 bool operator()(Arc a,Arc b) const
2284 return g.target(a)<g.target(b);
2294 ///It builds up the search database, which remains valid until the digraph
2296 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2299 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2303 _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2304 _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2308 ///Refresh the search data structure at a node.
2310 ///Build up the search database of node \c n.
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)
2317 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2319 std::sort(v.begin(),v.end(),ArcLess(_g));
2320 _head[n]=refreshRec(v,0,v.size()-1);
2322 else _head[n]=INVALID;
2324 ///Refresh the full data structure.
2326 ///Build up the full search database. In fact, it simply calls
2327 ///\ref refresh(Node) "refresh(n)" for each node \c n.
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.
2334 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2337 ///Find an arc between two nodes.
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.
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
2353 e!=INVALID&&_g.target(e)!=t;
2354 e = t < _g.target(e)?_left[e]:_right[e]) ;
2360 ///Fast look-up of all arcs between given endpoints.
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
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).
2371 ///\tparam GR The type of the underlying digraph.
2376 class AllArcLookUp : public ArcLookUp<GR>
2378 using ArcLookUp<GR>::_g;
2379 using ArcLookUp<GR>::_right;
2380 using ArcLookUp<GR>::_left;
2381 using ArcLookUp<GR>::_head;
2383 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2385 typename GR::template ArcMap<Arc> _next;
2387 Arc refreshNext(Arc head,Arc next=INVALID)
2389 if(head==INVALID) return next;
2391 next=refreshNext(_right[head],next);
2392 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2394 return refreshNext(_left[head],head);
2400 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2405 /// The Digraph type
2412 ///It builds up the search database, which remains valid until the digraph
2414 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
2416 ///Refresh the data structure at a node.
2418 ///Build up the search database of node \c n.
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)
2424 ArcLookUp<GR>::refresh(n);
2425 refreshNext(_head[n]);
2428 ///Refresh the full data structure.
2430 ///Build up the full search database. In fact, it simply calls
2431 ///\ref refresh(Node) "refresh(n)" for each node \c n.
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.
2438 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2441 ///Find an arc between two nodes.
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.
2451 ///For example, you can count the number of arcs from \c u to \c v in the
2454 ///AllArcLookUp<ListDigraph> ae(g);
2457 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
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.
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.
2468 Arc operator()(Node s, Node t, Arc prev=INVALID) const
2475 e!=INVALID&&_g.target(e)!=t;
2476 e = t < _g.target(e)?_left[e]:_right[e]) ;
2486 else return _next[prev];