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
154 ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
155 ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
156 ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
157 ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
159 ///\note If the graph type is a dependent type, ie. the graph type depend
160 ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
162 #define BPGRAPH_TYPEDEFS(BpGraph) \
163 GRAPH_TYPEDEFS(BpGraph); \
164 typedef BpGraph::RedNode RedNode; \
165 typedef BpGraph::RedNodeIt RedNodeIt; \
166 typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap; \
167 typedef BpGraph::RedNodeMap<int> IntRedNodeMap; \
168 typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap; \
169 typedef BpGraph::BlueNode BlueNode; \
170 typedef BpGraph::BlueNodeIt BlueNodeIt; \
171 typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap; \
172 typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap; \
173 typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
175 ///Create convenience typedefs for the bipartite graph types and iterators
177 ///\see BPGRAPH_TYPEDEFS
179 ///\note Use this macro, if the graph type is a dependent type,
180 ///ie. the graph type depend on a template parameter.
181 #define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \
182 TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \
183 typedef typename BpGraph::RedNode RedNode; \
184 typedef typename BpGraph::RedNodeIt RedNodeIt; \
185 typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap; \
186 typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap; \
187 typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap; \
188 typedef typename BpGraph::BlueNode BlueNode; \
189 typedef typename BpGraph::BlueNodeIt BlueNodeIt; \
190 typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap; \
191 typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap; \
192 typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
194 /// \brief Function to count the items in a graph.
196 /// This function counts the items (nodes, arcs etc.) in a graph.
197 /// The complexity of the function is linear because
198 /// it iterates on all of the items.
199 template <typename Graph, typename Item>
200 inline int countItems(const Graph& g) {
201 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
203 for (ItemIt it(g); it != INVALID; ++it) {
211 namespace _core_bits {
213 template <typename Graph, typename Enable = void>
214 struct CountNodesSelector {
215 static int count(const Graph &g) {
216 return countItems<Graph, typename Graph::Node>(g);
220 template <typename Graph>
221 struct CountNodesSelector<
223 enable_if<typename Graph::NodeNumTag, void>::type>
225 static int count(const Graph &g) {
231 /// \brief Function to count the nodes in the graph.
233 /// This function counts the nodes in the graph.
234 /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
235 /// graph structures it is specialized to run in <em>O</em>(1).
237 /// \note If the graph contains a \c nodeNum() member function and a
238 /// \c NodeNumTag tag then this function calls directly the member
239 /// function to query the cardinality of the node set.
240 template <typename Graph>
241 inline int countNodes(const Graph& g) {
242 return _core_bits::CountNodesSelector<Graph>::count(g);
245 namespace _graph_utils_bits {
247 template <typename Graph, typename Enable = void>
248 struct CountRedNodesSelector {
249 static int count(const Graph &g) {
250 return countItems<Graph, typename Graph::RedNode>(g);
254 template <typename Graph>
255 struct CountRedNodesSelector<
257 enable_if<typename Graph::NodeNumTag, void>::type>
259 static int count(const Graph &g) {
265 /// \brief Function to count the red nodes in the graph.
267 /// This function counts the red nodes in the graph.
268 /// The complexity of the function is O(n) but for some
269 /// graph structures it is specialized to run in O(1).
271 /// If the graph contains a \e redNum() member function and a
272 /// \e NodeNumTag tag then this function calls directly the member
273 /// function to query the cardinality of the node set.
274 template <typename Graph>
275 inline int countRedNodes(const Graph& g) {
276 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
279 namespace _graph_utils_bits {
281 template <typename Graph, typename Enable = void>
282 struct CountBlueNodesSelector {
283 static int count(const Graph &g) {
284 return countItems<Graph, typename Graph::BlueNode>(g);
288 template <typename Graph>
289 struct CountBlueNodesSelector<
291 enable_if<typename Graph::NodeNumTag, void>::type>
293 static int count(const Graph &g) {
299 /// \brief Function to count the blue nodes in the graph.
301 /// This function counts the blue nodes in the graph.
302 /// The complexity of the function is O(n) but for some
303 /// graph structures it is specialized to run in O(1).
305 /// If the graph contains a \e blueNum() member function and a
306 /// \e NodeNumTag tag then this function calls directly the member
307 /// function to query the cardinality of the node set.
308 template <typename Graph>
309 inline int countBlueNodes(const Graph& g) {
310 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
315 namespace _core_bits {
317 template <typename Graph, typename Enable = void>
318 struct CountArcsSelector {
319 static int count(const Graph &g) {
320 return countItems<Graph, typename Graph::Arc>(g);
324 template <typename Graph>
325 struct CountArcsSelector<
327 typename enable_if<typename Graph::ArcNumTag, void>::type>
329 static int count(const Graph &g) {
335 /// \brief Function to count the arcs in the graph.
337 /// This function counts the arcs in the graph.
338 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
339 /// graph structures it is specialized to run in <em>O</em>(1).
341 /// \note If the graph contains a \c arcNum() member function and a
342 /// \c ArcNumTag tag then this function calls directly the member
343 /// function to query the cardinality of the arc set.
344 template <typename Graph>
345 inline int countArcs(const Graph& g) {
346 return _core_bits::CountArcsSelector<Graph>::count(g);
351 namespace _core_bits {
353 template <typename Graph, typename Enable = void>
354 struct CountEdgesSelector {
355 static int count(const Graph &g) {
356 return countItems<Graph, typename Graph::Edge>(g);
360 template <typename Graph>
361 struct CountEdgesSelector<
363 typename enable_if<typename Graph::EdgeNumTag, void>::type>
365 static int count(const Graph &g) {
371 /// \brief Function to count the edges in the graph.
373 /// This function counts the edges in the graph.
374 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
375 /// graph structures it is specialized to run in <em>O</em>(1).
377 /// \note If the graph contains a \c edgeNum() member function and a
378 /// \c EdgeNumTag tag then this function calls directly the member
379 /// function to query the cardinality of the edge set.
380 template <typename Graph>
381 inline int countEdges(const Graph& g) {
382 return _core_bits::CountEdgesSelector<Graph>::count(g);
387 template <typename Graph, typename DegIt>
388 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
390 for (DegIt it(_g, _n); it != INVALID; ++it) {
396 /// \brief Function to count the number of the out-arcs from node \c n.
398 /// This function counts the number of the out-arcs from node \c n
399 /// in the graph \c g.
400 template <typename Graph>
401 inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
402 return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
405 /// \brief Function to count the number of the in-arcs to node \c n.
407 /// This function counts the number of the in-arcs to node \c n
408 /// in the graph \c g.
409 template <typename Graph>
410 inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
411 return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
414 /// \brief Function to count the number of the inc-edges to node \c n.
416 /// This function counts the number of the inc-edges to node \c n
417 /// in the undirected graph \c g.
418 template <typename Graph>
419 inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
420 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
423 namespace _core_bits {
425 template <typename Digraph, typename Item, typename RefMap>
428 virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
430 virtual ~MapCopyBase() {}
433 template <typename Digraph, typename Item, typename RefMap,
434 typename FromMap, typename ToMap>
435 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
438 MapCopy(const FromMap& map, ToMap& tmap)
439 : _map(map), _tmap(tmap) {}
441 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
442 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
443 for (ItemIt it(digraph); it != INVALID; ++it) {
444 _tmap.set(refMap[it], _map[it]);
453 template <typename Digraph, typename Item, typename RefMap, typename It>
454 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
457 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
459 virtual void copy(const Digraph&, const RefMap& refMap) {
468 template <typename Digraph, typename Item, typename RefMap, typename Ref>
469 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
472 RefCopy(Ref& map) : _map(map) {}
474 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
475 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
476 for (ItemIt it(digraph); it != INVALID; ++it) {
477 _map.set(it, refMap[it]);
485 template <typename Digraph, typename Item, typename RefMap,
487 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
490 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
492 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
493 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
494 for (ItemIt it(digraph); it != INVALID; ++it) {
495 _cmap.set(refMap[it], it);
503 template <typename Digraph, typename Enable = void>
504 struct DigraphCopySelector {
505 template <typename From, typename NodeRefMap, typename ArcRefMap>
506 static void copy(const From& from, Digraph &to,
507 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
509 for (typename From::NodeIt it(from); it != INVALID; ++it) {
510 nodeRefMap[it] = to.addNode();
512 for (typename From::ArcIt it(from); it != INVALID; ++it) {
513 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
514 nodeRefMap[from.target(it)]);
519 template <typename Digraph>
520 struct DigraphCopySelector<
522 typename enable_if<typename Digraph::BuildTag, void>::type>
524 template <typename From, typename NodeRefMap, typename ArcRefMap>
525 static void copy(const From& from, Digraph &to,
526 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
527 to.build(from, nodeRefMap, arcRefMap);
531 template <typename Graph, typename Enable = void>
532 struct GraphCopySelector {
533 template <typename From, typename NodeRefMap, typename EdgeRefMap>
534 static void copy(const From& from, Graph &to,
535 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
537 for (typename From::NodeIt it(from); it != INVALID; ++it) {
538 nodeRefMap[it] = to.addNode();
540 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
541 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
542 nodeRefMap[from.v(it)]);
547 template <typename Graph>
548 struct GraphCopySelector<
550 typename enable_if<typename Graph::BuildTag, void>::type>
552 template <typename From, typename NodeRefMap, typename EdgeRefMap>
553 static void copy(const From& from, Graph &to,
554 NodeRefMap& nodeRefMap,
555 EdgeRefMap& edgeRefMap) {
556 to.build(from, nodeRefMap, edgeRefMap);
560 template <typename BpGraph, typename Enable = void>
561 struct BpGraphCopySelector {
562 template <typename From, typename RedNodeRefMap,
563 typename BlueNodeRefMap, typename EdgeRefMap>
564 static void copy(const From& from, BpGraph &to,
565 RedNodeRefMap& redNodeRefMap,
566 BlueNodeRefMap& blueNodeRefMap,
567 EdgeRefMap& edgeRefMap) {
569 for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
570 redNodeRefMap[it] = to.addRedNode();
572 for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
573 blueNodeRefMap[it] = to.addBlueNode();
575 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
576 edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
577 blueNodeRefMap[from.blueNode(it)]);
582 template <typename BpGraph>
583 struct BpGraphCopySelector<
585 typename enable_if<typename BpGraph::BuildTag, void>::type>
587 template <typename From, typename RedNodeRefMap,
588 typename BlueNodeRefMap, typename EdgeRefMap>
589 static void copy(const From& from, BpGraph &to,
590 RedNodeRefMap& redNodeRefMap,
591 BlueNodeRefMap& blueNodeRefMap,
592 EdgeRefMap& edgeRefMap) {
593 to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
599 /// \brief Check whether a graph is undirected.
601 /// This function returns \c true if the given graph is undirected.
603 template <typename GR>
604 bool undirected(const GR& g) { return false; }
606 template <typename GR>
607 typename enable_if<UndirectedTagIndicator<GR>, bool>::type
608 undirected(const GR&) {
611 template <typename GR>
612 typename disable_if<UndirectedTagIndicator<GR>, bool>::type
613 undirected(const GR&) {
618 /// \brief Class to copy a digraph.
620 /// Class to copy a digraph to another digraph (duplicate a digraph). The
621 /// simplest way of using it is through the \c digraphCopy() function.
623 /// This class not only make a copy of a digraph, but it can create
624 /// references and cross references between the nodes and arcs of
625 /// the two digraphs, and it can copy maps to use with the newly created
628 /// To make a copy from a digraph, first an instance of DigraphCopy
629 /// should be created, then the data belongs to the digraph should
630 /// assigned to copy. In the end, the \c run() member should be
633 /// The next code copies a digraph with several data:
635 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
636 /// // Create references for the nodes
637 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
639 /// // Create cross references (inverse) for the arcs
640 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
641 /// cg.arcCrossRef(acr);
642 /// // Copy an arc map
643 /// OrigGraph::ArcMap<double> oamap(orig_graph);
644 /// NewGraph::ArcMap<double> namap(new_graph);
645 /// cg.arcMap(oamap, namap);
647 /// OrigGraph::Node on;
648 /// NewGraph::Node nn;
650 /// // Execute copying
653 template <typename From, typename To>
657 typedef typename From::Node Node;
658 typedef typename From::NodeIt NodeIt;
659 typedef typename From::Arc Arc;
660 typedef typename From::ArcIt ArcIt;
662 typedef typename To::Node TNode;
663 typedef typename To::Arc TArc;
665 typedef typename From::template NodeMap<TNode> NodeRefMap;
666 typedef typename From::template ArcMap<TArc> ArcRefMap;
670 /// \brief Constructor of DigraphCopy.
672 /// Constructor of DigraphCopy for copying the content of the
673 /// \c from digraph into the \c to digraph.
674 DigraphCopy(const From& from, To& to)
675 : _from(from), _to(to) {}
677 /// \brief Destructor of DigraphCopy
679 /// Destructor of DigraphCopy.
681 for (int i = 0; i < int(_node_maps.size()); ++i) {
682 delete _node_maps[i];
684 for (int i = 0; i < int(_arc_maps.size()); ++i) {
690 /// \brief Copy the node references into the given map.
692 /// This function copies the node references into the given map.
693 /// The parameter should be a map, whose key type is the Node type of
694 /// the source digraph, while the value type is the Node type of the
695 /// destination digraph.
696 template <typename NodeRef>
697 DigraphCopy& nodeRef(NodeRef& map) {
698 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
699 NodeRefMap, NodeRef>(map));
703 /// \brief Copy the node cross references into the given map.
705 /// This function copies the node cross references (reverse references)
706 /// into the given map. The parameter should be a map, whose key type
707 /// is the Node type of the destination digraph, while the value type is
708 /// the Node type of the source digraph.
709 template <typename NodeCrossRef>
710 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
711 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
712 NodeRefMap, NodeCrossRef>(map));
716 /// \brief Make a copy of the given node map.
718 /// This function makes a copy of the given node map for the newly
720 /// The key type of the new map \c tmap should be the Node type of the
721 /// destination digraph, and the key type of the original map \c map
722 /// should be the Node type of the source digraph.
723 template <typename FromMap, typename ToMap>
724 DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
725 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
726 NodeRefMap, FromMap, ToMap>(map, tmap));
730 /// \brief Make a copy of the given node.
732 /// This function makes a copy of the given node.
733 DigraphCopy& node(const Node& node, TNode& tnode) {
734 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
735 NodeRefMap, TNode>(node, tnode));
739 /// \brief Copy the arc references into the given map.
741 /// This function copies the arc references into the given map.
742 /// The parameter should be a map, whose key type is the Arc type of
743 /// the source digraph, while the value type is the Arc type of the
744 /// destination digraph.
745 template <typename ArcRef>
746 DigraphCopy& arcRef(ArcRef& map) {
747 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
748 ArcRefMap, ArcRef>(map));
752 /// \brief Copy the arc cross references into the given map.
754 /// This function copies the arc cross references (reverse references)
755 /// into the given map. The parameter should be a map, whose key type
756 /// is the Arc type of the destination digraph, while the value type is
757 /// the Arc type of the source digraph.
758 template <typename ArcCrossRef>
759 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
760 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
761 ArcRefMap, ArcCrossRef>(map));
765 /// \brief Make a copy of the given arc map.
767 /// This function makes a copy of the given arc map for the newly
769 /// The key type of the new map \c tmap should be the Arc type of the
770 /// destination digraph, and the key type of the original map \c map
771 /// should be the Arc type of the source digraph.
772 template <typename FromMap, typename ToMap>
773 DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
774 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
775 ArcRefMap, FromMap, ToMap>(map, tmap));
779 /// \brief Make a copy of the given arc.
781 /// This function makes a copy of the given arc.
782 DigraphCopy& arc(const Arc& arc, TArc& tarc) {
783 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
784 ArcRefMap, TArc>(arc, tarc));
788 /// \brief Execute copying.
790 /// This function executes the copying of the digraph along with the
791 /// copying of the assigned data.
793 NodeRefMap nodeRefMap(_from);
794 ArcRefMap arcRefMap(_from);
795 _core_bits::DigraphCopySelector<To>::
796 copy(_from, _to, nodeRefMap, arcRefMap);
797 for (int i = 0; i < int(_node_maps.size()); ++i) {
798 _node_maps[i]->copy(_from, nodeRefMap);
800 for (int i = 0; i < int(_arc_maps.size()); ++i) {
801 _arc_maps[i]->copy(_from, arcRefMap);
810 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
813 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
818 /// \brief Copy a digraph to another digraph.
820 /// This function copies a digraph to another digraph.
821 /// The complete usage of it is detailed in the DigraphCopy class, but
822 /// a short example shows a basic work:
824 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
827 /// After the copy the \c nr map will contain the mapping from the
828 /// nodes of the \c from digraph to the nodes of the \c to digraph and
829 /// \c acr will contain the mapping from the arcs of the \c to digraph
830 /// to the arcs of the \c from digraph.
833 template <typename From, typename To>
834 DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
835 return DigraphCopy<From, To>(from, to);
838 /// \brief Class to copy a graph.
840 /// Class to copy a graph to another graph (duplicate a graph). The
841 /// simplest way of using it is through the \c graphCopy() function.
843 /// This class not only make a copy of a graph, but it can create
844 /// references and cross references between the nodes, edges and arcs of
845 /// the two graphs, and it can copy maps for using with the newly created
848 /// To make a copy from a graph, first an instance of GraphCopy
849 /// should be created, then the data belongs to the graph should
850 /// assigned to copy. In the end, the \c run() member should be
853 /// The next code copies a graph with several data:
855 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
856 /// // Create references for the nodes
857 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
859 /// // Create cross references (inverse) for the edges
860 /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
861 /// cg.edgeCrossRef(ecr);
862 /// // Copy an edge map
863 /// OrigGraph::EdgeMap<double> oemap(orig_graph);
864 /// NewGraph::EdgeMap<double> nemap(new_graph);
865 /// cg.edgeMap(oemap, nemap);
867 /// OrigGraph::Node on;
868 /// NewGraph::Node nn;
870 /// // Execute copying
873 template <typename From, typename To>
877 typedef typename From::Node Node;
878 typedef typename From::NodeIt NodeIt;
879 typedef typename From::Arc Arc;
880 typedef typename From::ArcIt ArcIt;
881 typedef typename From::Edge Edge;
882 typedef typename From::EdgeIt EdgeIt;
884 typedef typename To::Node TNode;
885 typedef typename To::Arc TArc;
886 typedef typename To::Edge TEdge;
888 typedef typename From::template NodeMap<TNode> NodeRefMap;
889 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
892 ArcRefMap(const From& from, const To& to,
893 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
894 : _from(from), _to(to),
895 _edge_ref(edge_ref), _node_ref(node_ref) {}
897 typedef typename From::Arc Key;
898 typedef typename To::Arc Value;
900 Value operator[](const Key& key) const {
901 bool forward = _from.u(key) != _from.v(key) ?
902 _node_ref[_from.source(key)] ==
903 _to.source(_to.direct(_edge_ref[key], true)) :
904 _from.direction(key);
905 return _to.direct(_edge_ref[key], forward);
910 const EdgeRefMap& _edge_ref;
911 const NodeRefMap& _node_ref;
916 /// \brief Constructor of GraphCopy.
918 /// Constructor of GraphCopy for copying the content of the
919 /// \c from graph into the \c to graph.
920 GraphCopy(const From& from, To& to)
921 : _from(from), _to(to) {}
923 /// \brief Destructor of GraphCopy
925 /// Destructor of GraphCopy.
927 for (int i = 0; i < int(_node_maps.size()); ++i) {
928 delete _node_maps[i];
930 for (int i = 0; i < int(_arc_maps.size()); ++i) {
933 for (int i = 0; i < int(_edge_maps.size()); ++i) {
934 delete _edge_maps[i];
938 /// \brief Copy the node references into the given map.
940 /// This function copies the node references into the given map.
941 /// The parameter should be a map, whose key type is the Node type of
942 /// the source graph, while the value type is the Node type of the
943 /// destination graph.
944 template <typename NodeRef>
945 GraphCopy& nodeRef(NodeRef& map) {
946 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
947 NodeRefMap, NodeRef>(map));
951 /// \brief Copy the node cross references into the given map.
953 /// This function copies the node cross references (reverse references)
954 /// into the given map. The parameter should be a map, whose key type
955 /// is the Node type of the destination graph, while the value type is
956 /// the Node type of the source graph.
957 template <typename NodeCrossRef>
958 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
959 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
960 NodeRefMap, NodeCrossRef>(map));
964 /// \brief Make a copy of the given node map.
966 /// This function makes a copy of the given node map for the newly
968 /// The key type of the new map \c tmap should be the Node type of the
969 /// destination graph, and the key type of the original map \c map
970 /// should be the Node type of the source graph.
971 template <typename FromMap, typename ToMap>
972 GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
973 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
974 NodeRefMap, FromMap, ToMap>(map, tmap));
978 /// \brief Make a copy of the given node.
980 /// This function makes a copy of the given node.
981 GraphCopy& node(const Node& node, TNode& tnode) {
982 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
983 NodeRefMap, TNode>(node, tnode));
987 /// \brief Copy the arc references into the given map.
989 /// This function copies the arc references into the given map.
990 /// The parameter should be a map, whose key type is the Arc type of
991 /// the source graph, while the value type is the Arc type of the
992 /// destination graph.
993 template <typename ArcRef>
994 GraphCopy& arcRef(ArcRef& map) {
995 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
996 ArcRefMap, ArcRef>(map));
1000 /// \brief Copy the arc cross references into the given map.
1002 /// This function copies the arc cross references (reverse references)
1003 /// into the given map. The parameter should be a map, whose key type
1004 /// is the Arc type of the destination graph, while the value type is
1005 /// the Arc type of the source graph.
1006 template <typename ArcCrossRef>
1007 GraphCopy& arcCrossRef(ArcCrossRef& map) {
1008 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1009 ArcRefMap, ArcCrossRef>(map));
1013 /// \brief Make a copy of the given arc map.
1015 /// This function makes a copy of the given arc map for the newly
1017 /// The key type of the new map \c tmap should be the Arc type of the
1018 /// destination graph, and the key type of the original map \c map
1019 /// should be the Arc type of the source graph.
1020 template <typename FromMap, typename ToMap>
1021 GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1022 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1023 ArcRefMap, FromMap, ToMap>(map, tmap));
1027 /// \brief Make a copy of the given arc.
1029 /// This function makes a copy of the given arc.
1030 GraphCopy& arc(const Arc& arc, TArc& tarc) {
1031 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1032 ArcRefMap, TArc>(arc, tarc));
1036 /// \brief Copy the edge references into the given map.
1038 /// This function copies the edge references into the given map.
1039 /// The parameter should be a map, whose key type is the Edge type of
1040 /// the source graph, while the value type is the Edge type of the
1041 /// destination graph.
1042 template <typename EdgeRef>
1043 GraphCopy& edgeRef(EdgeRef& map) {
1044 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1045 EdgeRefMap, EdgeRef>(map));
1049 /// \brief Copy the edge cross references into the given map.
1051 /// This function copies the edge cross references (reverse references)
1052 /// into the given map. The parameter should be a map, whose key type
1053 /// is the Edge type of the destination graph, while the value type is
1054 /// the Edge type of the source graph.
1055 template <typename EdgeCrossRef>
1056 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1057 _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1058 Edge, EdgeRefMap, EdgeCrossRef>(map));
1062 /// \brief Make a copy of the given edge map.
1064 /// This function makes a copy of the given edge map for the newly
1066 /// The key type of the new map \c tmap should be the Edge type of the
1067 /// destination graph, and the key type of the original map \c map
1068 /// should be the Edge type of the source graph.
1069 template <typename FromMap, typename ToMap>
1070 GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1071 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1072 EdgeRefMap, FromMap, ToMap>(map, tmap));
1076 /// \brief Make a copy of the given edge.
1078 /// This function makes a copy of the given edge.
1079 GraphCopy& edge(const Edge& edge, TEdge& tedge) {
1080 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1081 EdgeRefMap, TEdge>(edge, tedge));
1085 /// \brief Execute copying.
1087 /// This function executes the copying of the graph along with the
1088 /// copying of the assigned data.
1090 NodeRefMap nodeRefMap(_from);
1091 EdgeRefMap edgeRefMap(_from);
1092 ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
1093 _core_bits::GraphCopySelector<To>::
1094 copy(_from, _to, nodeRefMap, edgeRefMap);
1095 for (int i = 0; i < int(_node_maps.size()); ++i) {
1096 _node_maps[i]->copy(_from, nodeRefMap);
1098 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1099 _edge_maps[i]->copy(_from, edgeRefMap);
1101 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1102 _arc_maps[i]->copy(_from, arcRefMap);
1111 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1114 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1117 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1122 /// \brief Copy a graph to another graph.
1124 /// This function copies a graph to another graph.
1125 /// The complete usage of it is detailed in the GraphCopy class,
1126 /// but a short example shows a basic work:
1128 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1131 /// After the copy the \c nr map will contain the mapping from the
1132 /// nodes of the \c from graph to the nodes of the \c to graph and
1133 /// \c ecr will contain the mapping from the edges of the \c to graph
1134 /// to the edges of the \c from graph.
1137 template <typename From, typename To>
1139 graphCopy(const From& from, To& to) {
1140 return GraphCopy<From, To>(from, to);
1143 /// \brief Class to copy a bipartite graph.
1145 /// Class to copy a bipartite graph to another graph (duplicate a
1146 /// graph). The simplest way of using it is through the
1147 /// \c bpGraphCopy() function.
1149 /// This class not only make a copy of a bipartite graph, but it can
1150 /// create references and cross references between the nodes, edges
1151 /// and arcs of the two graphs, and it can copy maps for using with
1152 /// the newly created graph.
1154 /// To make a copy from a graph, first an instance of BpGraphCopy
1155 /// should be created, then the data belongs to the graph should
1156 /// assigned to copy. In the end, the \c run() member should be
1159 /// The next code copies a graph with several data:
1161 /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
1162 /// // Create references for the nodes
1163 /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
1165 /// // Create cross references (inverse) for the edges
1166 /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
1167 /// cg.edgeCrossRef(ecr);
1168 /// // Copy a red node map
1169 /// OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
1170 /// NewBpGraph::RedNodeMap<double> nrmap(new_graph);
1171 /// cg.redNodeMap(ormap, nrmap);
1173 /// OrigBpGraph::Node on;
1174 /// NewBpGraph::Node nn;
1175 /// cg.node(on, nn);
1176 /// // Execute copying
1179 template <typename From, typename To>
1183 typedef typename From::Node Node;
1184 typedef typename From::RedNode RedNode;
1185 typedef typename From::BlueNode BlueNode;
1186 typedef typename From::NodeIt NodeIt;
1187 typedef typename From::Arc Arc;
1188 typedef typename From::ArcIt ArcIt;
1189 typedef typename From::Edge Edge;
1190 typedef typename From::EdgeIt EdgeIt;
1192 typedef typename To::Node TNode;
1193 typedef typename To::RedNode TRedNode;
1194 typedef typename To::BlueNode TBlueNode;
1195 typedef typename To::Arc TArc;
1196 typedef typename To::Edge TEdge;
1198 typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
1199 typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
1200 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1203 NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
1204 const BlueNodeRefMap& blue_node_ref)
1205 : _from(from), _red_node_ref(red_node_ref),
1206 _blue_node_ref(blue_node_ref) {}
1208 typedef typename From::Node Key;
1209 typedef typename To::Node Value;
1211 Value operator[](const Key& key) const {
1212 std::pair<RedNode, BlueNode> red_blue_pair = _from.asRedBlueNode(key);
1213 if (red_blue_pair.first != INVALID) {
1214 return _red_node_ref[red_blue_pair.first];
1216 return _blue_node_ref[red_blue_pair.second];
1221 const RedNodeRefMap& _red_node_ref;
1222 const BlueNodeRefMap& _blue_node_ref;
1226 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
1227 : _from(from), _to(to), _edge_ref(edge_ref) {}
1229 typedef typename From::Arc Key;
1230 typedef typename To::Arc Value;
1232 Value operator[](const Key& key) const {
1233 return _to.direct(_edge_ref[key], _from.direction(key));
1238 const EdgeRefMap& _edge_ref;
1243 /// \brief Constructor of BpGraphCopy.
1245 /// Constructor of BpGraphCopy for copying the content of the
1246 /// \c from graph into the \c to graph.
1247 BpGraphCopy(const From& from, To& to)
1248 : _from(from), _to(to) {}
1250 /// \brief Destructor of BpGraphCopy
1252 /// Destructor of BpGraphCopy.
1254 for (int i = 0; i < int(_node_maps.size()); ++i) {
1255 delete _node_maps[i];
1257 for (int i = 0; i < int(_red_maps.size()); ++i) {
1258 delete _red_maps[i];
1260 for (int i = 0; i < int(_blue_maps.size()); ++i) {
1261 delete _blue_maps[i];
1263 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1264 delete _arc_maps[i];
1266 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1267 delete _edge_maps[i];
1271 /// \brief Copy the node references into the given map.
1273 /// This function copies the node references into the given map.
1274 /// The parameter should be a map, whose key type is the Node type of
1275 /// the source graph, while the value type is the Node type of the
1276 /// destination graph.
1277 template <typename NodeRef>
1278 BpGraphCopy& nodeRef(NodeRef& map) {
1279 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1280 NodeRefMap, NodeRef>(map));
1284 /// \brief Copy the node cross references into the given map.
1286 /// This function copies the node cross references (reverse references)
1287 /// into the given map. The parameter should be a map, whose key type
1288 /// is the Node type of the destination graph, while the value type is
1289 /// the Node type of the source graph.
1290 template <typename NodeCrossRef>
1291 BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1292 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1293 NodeRefMap, NodeCrossRef>(map));
1297 /// \brief Make a copy of the given node map.
1299 /// This function makes a copy of the given node map for the newly
1301 /// The key type of the new map \c tmap should be the Node type of the
1302 /// destination graph, and the key type of the original map \c map
1303 /// should be the Node type of the source graph.
1304 template <typename FromMap, typename ToMap>
1305 BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
1306 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1307 NodeRefMap, FromMap, ToMap>(map, tmap));
1311 /// \brief Make a copy of the given node.
1313 /// This function makes a copy of the given node.
1314 BpGraphCopy& node(const Node& node, TNode& tnode) {
1315 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1316 NodeRefMap, TNode>(node, tnode));
1320 /// \brief Copy the red node references into the given map.
1322 /// This function copies the red node references into the given
1323 /// map. The parameter should be a map, whose key type is the
1324 /// Node type of the source graph with the red item set, while the
1325 /// value type is the Node type of the destination graph.
1326 template <typename RedRef>
1327 BpGraphCopy& redRef(RedRef& map) {
1328 _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
1329 RedNodeRefMap, RedRef>(map));
1333 /// \brief Copy the red node cross references into the given map.
1335 /// This function copies the red node cross references (reverse
1336 /// references) into the given map. The parameter should be a map,
1337 /// whose key type is the Node type of the destination graph with
1338 /// the red item set, while the value type is the Node type of the
1340 template <typename RedCrossRef>
1341 BpGraphCopy& redCrossRef(RedCrossRef& map) {
1342 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
1343 RedNodeRefMap, RedCrossRef>(map));
1347 /// \brief Make a copy of the given red node map.
1349 /// This function makes a copy of the given red node map for the newly
1351 /// The key type of the new map \c tmap should be the Node type of
1352 /// the destination graph with the red items, and the key type of
1353 /// the original map \c map should be the Node type of the source
1355 template <typename FromMap, typename ToMap>
1356 BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
1357 _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
1358 RedNodeRefMap, FromMap, ToMap>(map, tmap));
1362 /// \brief Make a copy of the given red node.
1364 /// This function makes a copy of the given red node.
1365 BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
1366 _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
1367 RedNodeRefMap, TRedNode>(node, tnode));
1371 /// \brief Copy the blue node references into the given map.
1373 /// This function copies the blue node references into the given
1374 /// map. The parameter should be a map, whose key type is the
1375 /// Node type of the source graph with the blue item set, while the
1376 /// value type is the Node type of the destination graph.
1377 template <typename BlueRef>
1378 BpGraphCopy& blueRef(BlueRef& map) {
1379 _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
1380 BlueNodeRefMap, BlueRef>(map));
1384 /// \brief Copy the blue node cross references into the given map.
1386 /// This function copies the blue node cross references (reverse
1387 /// references) into the given map. The parameter should be a map,
1388 /// whose key type is the Node type of the destination graph with
1389 /// the blue item set, while the value type is the Node type of the
1391 template <typename BlueCrossRef>
1392 BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1393 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
1394 BlueNodeRefMap, BlueCrossRef>(map));
1398 /// \brief Make a copy of the given blue node map.
1400 /// This function makes a copy of the given blue node map for the newly
1402 /// The key type of the new map \c tmap should be the Node type of
1403 /// the destination graph with the blue items, and the key type of
1404 /// the original map \c map should be the Node type of the source
1406 template <typename FromMap, typename ToMap>
1407 BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
1408 _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
1409 BlueNodeRefMap, FromMap, ToMap>(map, tmap));
1413 /// \brief Make a copy of the given blue node.
1415 /// This function makes a copy of the given blue node.
1416 BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
1417 _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
1418 BlueNodeRefMap, TBlueNode>(node, tnode));
1422 /// \brief Copy the arc references into the given map.
1424 /// This function copies the arc references into the given map.
1425 /// The parameter should be a map, whose key type is the Arc type of
1426 /// the source graph, while the value type is the Arc type of the
1427 /// destination graph.
1428 template <typename ArcRef>
1429 BpGraphCopy& arcRef(ArcRef& map) {
1430 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1431 ArcRefMap, ArcRef>(map));
1435 /// \brief Copy the arc cross references into the given map.
1437 /// This function copies the arc cross references (reverse references)
1438 /// into the given map. The parameter should be a map, whose key type
1439 /// is the Arc type of the destination graph, while the value type is
1440 /// the Arc type of the source graph.
1441 template <typename ArcCrossRef>
1442 BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
1443 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1444 ArcRefMap, ArcCrossRef>(map));
1448 /// \brief Make a copy of the given arc map.
1450 /// This function makes a copy of the given arc map for the newly
1452 /// The key type of the new map \c tmap should be the Arc type of the
1453 /// destination graph, and the key type of the original map \c map
1454 /// should be the Arc type of the source graph.
1455 template <typename FromMap, typename ToMap>
1456 BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1457 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1458 ArcRefMap, FromMap, ToMap>(map, tmap));
1462 /// \brief Make a copy of the given arc.
1464 /// This function makes a copy of the given arc.
1465 BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
1466 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1467 ArcRefMap, TArc>(arc, tarc));
1471 /// \brief Copy the edge references into the given map.
1473 /// This function copies the edge references into the given map.
1474 /// The parameter should be a map, whose key type is the Edge type of
1475 /// the source graph, while the value type is the Edge type of the
1476 /// destination graph.
1477 template <typename EdgeRef>
1478 BpGraphCopy& edgeRef(EdgeRef& map) {
1479 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1480 EdgeRefMap, EdgeRef>(map));
1484 /// \brief Copy the edge cross references into the given map.
1486 /// This function copies the edge cross references (reverse references)
1487 /// into the given map. The parameter should be a map, whose key type
1488 /// is the Edge type of the destination graph, while the value type is
1489 /// the Edge type of the source graph.
1490 template <typename EdgeCrossRef>
1491 BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1492 _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1493 Edge, EdgeRefMap, EdgeCrossRef>(map));
1497 /// \brief Make a copy of the given edge map.
1499 /// This function makes a copy of the given edge map for the newly
1501 /// The key type of the new map \c tmap should be the Edge type of the
1502 /// destination graph, and the key type of the original map \c map
1503 /// should be the Edge type of the source graph.
1504 template <typename FromMap, typename ToMap>
1505 BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1506 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1507 EdgeRefMap, FromMap, ToMap>(map, tmap));
1511 /// \brief Make a copy of the given edge.
1513 /// This function makes a copy of the given edge.
1514 BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
1515 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1516 EdgeRefMap, TEdge>(edge, tedge));
1520 /// \brief Execute copying.
1522 /// This function executes the copying of the graph along with the
1523 /// copying of the assigned data.
1525 RedNodeRefMap redNodeRefMap(_from);
1526 BlueNodeRefMap blueNodeRefMap(_from);
1527 NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
1528 EdgeRefMap edgeRefMap(_from);
1529 ArcRefMap arcRefMap(_from, _to, edgeRefMap);
1530 _core_bits::BpGraphCopySelector<To>::
1531 copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
1532 for (int i = 0; i < int(_node_maps.size()); ++i) {
1533 _node_maps[i]->copy(_from, nodeRefMap);
1535 for (int i = 0; i < int(_red_maps.size()); ++i) {
1536 _red_maps[i]->copy(_from, redNodeRefMap);
1538 for (int i = 0; i < int(_blue_maps.size()); ++i) {
1539 _blue_maps[i]->copy(_from, blueNodeRefMap);
1541 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1542 _edge_maps[i]->copy(_from, edgeRefMap);
1544 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1545 _arc_maps[i]->copy(_from, arcRefMap);
1554 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1557 std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
1560 std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
1563 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1566 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1571 /// \brief Copy a graph to another graph.
1573 /// This function copies a graph to another graph.
1574 /// The complete usage of it is detailed in the BpGraphCopy class,
1575 /// but a short example shows a basic work:
1577 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1580 /// After the copy the \c nr map will contain the mapping from the
1581 /// nodes of the \c from graph to the nodes of the \c to graph and
1582 /// \c ecr will contain the mapping from the edges of the \c to graph
1583 /// to the edges of the \c from graph.
1585 /// \see BpGraphCopy
1586 template <typename From, typename To>
1587 BpGraphCopy<From, To>
1588 bpGraphCopy(const From& from, To& to) {
1589 return BpGraphCopy<From, To>(from, to);
1592 namespace _core_bits {
1594 template <typename Graph, typename Enable = void>
1595 struct FindArcSelector {
1596 typedef typename Graph::Node Node;
1597 typedef typename Graph::Arc Arc;
1598 static Arc find(const Graph &g, Node u, Node v, Arc e) {
1604 while (e != INVALID && g.target(e) != v) {
1611 template <typename Graph>
1612 struct FindArcSelector<
1614 typename enable_if<typename Graph::FindArcTag, void>::type>
1616 typedef typename Graph::Node Node;
1617 typedef typename Graph::Arc Arc;
1618 static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1619 return g.findArc(u, v, prev);
1624 /// \brief Find an arc between two nodes of a digraph.
1626 /// This function finds an arc from node \c u to node \c v in the
1629 /// If \c prev is \ref INVALID (this is the default value), then
1630 /// it finds the first arc from \c u to \c v. Otherwise it looks for
1631 /// the next arc from \c u to \c v after \c prev.
1632 /// \return The found arc or \ref INVALID if there is no such an arc.
1634 /// Thus you can iterate through each arc from \c u to \c v as it follows.
1636 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1641 /// \note \ref ConArcIt provides iterator interface for the same
1645 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1646 template <typename Graph>
1647 inline typename Graph::Arc
1648 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1649 typename Graph::Arc prev = INVALID) {
1650 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1653 /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1655 /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1656 /// a higher level interface for the \ref findArc() function. You can
1657 /// use it the following way:
1659 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1665 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1666 template <typename GR>
1667 class ConArcIt : public GR::Arc {
1668 typedef typename GR::Arc Parent;
1672 typedef typename GR::Arc Arc;
1673 typedef typename GR::Node Node;
1675 /// \brief Constructor.
1677 /// Construct a new ConArcIt iterating on the arcs that
1678 /// connects nodes \c u and \c v.
1679 ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
1680 Parent::operator=(findArc(_graph, u, v));
1683 /// \brief Constructor.
1685 /// Construct a new ConArcIt that continues the iterating from arc \c a.
1686 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
1688 /// \brief Increment operator.
1690 /// It increments the iterator and gives back the next arc.
1691 ConArcIt& operator++() {
1692 Parent::operator=(findArc(_graph, _graph.source(*this),
1693 _graph.target(*this), *this));
1700 namespace _core_bits {
1702 template <typename Graph, typename Enable = void>
1703 struct FindEdgeSelector {
1704 typedef typename Graph::Node Node;
1705 typedef typename Graph::Edge Edge;
1706 static Edge find(const Graph &g, Node u, Node v, Edge e) {
1710 g.firstInc(e, b, u);
1715 while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1720 g.firstInc(e, b, u);
1725 while (e != INVALID && (!b || g.v(e) != v)) {
1733 template <typename Graph>
1734 struct FindEdgeSelector<
1736 typename enable_if<typename Graph::FindEdgeTag, void>::type>
1738 typedef typename Graph::Node Node;
1739 typedef typename Graph::Edge Edge;
1740 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1741 return g.findEdge(u, v, prev);
1746 /// \brief Find an edge between two nodes of a graph.
1748 /// This function finds an edge from node \c u to node \c v in graph \c g.
1749 /// If node \c u and node \c v is equal then each loop edge
1750 /// will be enumerated once.
1752 /// If \c prev is \ref INVALID (this is the default value), then
1753 /// it finds the first edge from \c u to \c v. Otherwise it looks for
1754 /// the next edge from \c u to \c v after \c prev.
1755 /// \return The found edge or \ref INVALID if there is no such an edge.
1757 /// Thus you can iterate through each edge between \c u and \c v
1760 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1765 /// \note \ref ConEdgeIt provides iterator interface for the same
1769 template <typename Graph>
1770 inline typename Graph::Edge
1771 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1772 typename Graph::Edge p = INVALID) {
1773 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1776 /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1778 /// Iterator for iterating on parallel edges connecting the same nodes.
1779 /// It is a higher level interface for the findEdge() function. You can
1780 /// use it the following way:
1782 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1788 template <typename GR>
1789 class ConEdgeIt : public GR::Edge {
1790 typedef typename GR::Edge Parent;
1794 typedef typename GR::Edge Edge;
1795 typedef typename GR::Node Node;
1797 /// \brief Constructor.
1799 /// Construct a new ConEdgeIt iterating on the edges that
1800 /// connects nodes \c u and \c v.
1801 ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1802 Parent::operator=(findEdge(_graph, _u, _v));
1805 /// \brief Constructor.
1807 /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1808 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
1810 /// \brief Increment operator.
1812 /// It increments the iterator and gives back the next edge.
1813 ConEdgeIt& operator++() {
1814 Parent::operator=(findEdge(_graph, _u, _v, *this));
1823 ///Dynamic arc look-up between given endpoints.
1825 ///Using this class, you can find an arc in a digraph from a given
1826 ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1827 ///where <em>d</em> is the out-degree of the source node.
1829 ///It is possible to find \e all parallel arcs between two nodes with
1830 ///the \c operator() member.
1832 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1833 ///\ref AllArcLookUp if your digraph is not changed so frequently.
1835 ///This class uses a self-adjusting binary search tree, the Splay tree
1836 ///of Sleator and Tarjan to guarantee the logarithmic amortized
1837 ///time bound for arc look-ups. This class also guarantees the
1838 ///optimal time bound in a constant factor for any distribution of
1841 ///\tparam GR The type of the underlying digraph.
1845 template <typename GR>
1847 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
1849 typedef typename ItemSetTraits<GR, typename GR::Arc>
1850 ::ItemNotifier::ObserverBase Parent;
1852 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1856 /// The Digraph type
1861 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
1863 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
1867 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
1869 virtual void add(const Node& node) {
1871 Parent::set(node, INVALID);
1874 virtual void add(const std::vector<Node>& nodes) {
1876 for (int i = 0; i < int(nodes.size()); ++i) {
1877 Parent::set(nodes[i], INVALID);
1881 virtual void build() {
1884 typename Parent::Notifier* nf = Parent::notifier();
1885 for (nf->first(it); it != INVALID; nf->next(it)) {
1886 Parent::set(it, INVALID);
1894 ArcLess(const Digraph &_g) : g(_g) {}
1895 bool operator()(Arc a,Arc b) const
1897 return g.target(a)<g.target(b);
1905 typename Digraph::template ArcMap<Arc> _parent;
1906 typename Digraph::template ArcMap<Arc> _left;
1907 typename Digraph::template ArcMap<Arc> _right;
1915 ///It builds up the search database.
1916 DynArcLookUp(const Digraph &g)
1917 : _g(g),_head(g),_parent(g),_left(g),_right(g)
1919 Parent::attach(_g.notifier(typename Digraph::Arc()));
1925 virtual void add(const Arc& arc) {
1929 virtual void add(const std::vector<Arc>& arcs) {
1930 for (int i = 0; i < int(arcs.size()); ++i) {
1935 virtual void erase(const Arc& arc) {
1939 virtual void erase(const std::vector<Arc>& arcs) {
1940 for (int i = 0; i < int(arcs.size()); ++i) {
1945 virtual void build() {
1949 virtual void clear() {
1950 for(NodeIt n(_g);n!=INVALID;++n) {
1955 void insert(Arc arc) {
1956 Node s = _g.source(arc);
1957 Node t = _g.target(arc);
1958 _left[arc] = INVALID;
1959 _right[arc] = INVALID;
1964 _parent[arc] = INVALID;
1968 if (t < _g.target(e)) {
1969 if (_left[e] == INVALID) {
1978 if (_right[e] == INVALID) {
1990 void remove(Arc arc) {
1991 if (_left[arc] == INVALID) {
1992 if (_right[arc] != INVALID) {
1993 _parent[_right[arc]] = _parent[arc];
1995 if (_parent[arc] != INVALID) {
1996 if (_left[_parent[arc]] == arc) {
1997 _left[_parent[arc]] = _right[arc];
1999 _right[_parent[arc]] = _right[arc];
2002 _head[_g.source(arc)] = _right[arc];
2004 } else if (_right[arc] == INVALID) {
2005 _parent[_left[arc]] = _parent[arc];
2006 if (_parent[arc] != INVALID) {
2007 if (_left[_parent[arc]] == arc) {
2008 _left[_parent[arc]] = _left[arc];
2010 _right[_parent[arc]] = _left[arc];
2013 _head[_g.source(arc)] = _left[arc];
2017 if (_right[e] != INVALID) {
2019 while (_right[e] != INVALID) {
2023 _right[_parent[e]] = _left[e];
2024 if (_left[e] != INVALID) {
2025 _parent[_left[e]] = _parent[e];
2028 _left[e] = _left[arc];
2029 _parent[_left[arc]] = e;
2030 _right[e] = _right[arc];
2031 _parent[_right[arc]] = e;
2033 _parent[e] = _parent[arc];
2034 if (_parent[arc] != INVALID) {
2035 if (_left[_parent[arc]] == arc) {
2036 _left[_parent[arc]] = e;
2038 _right[_parent[arc]] = e;
2043 _right[e] = _right[arc];
2044 _parent[_right[arc]] = e;
2045 _parent[e] = _parent[arc];
2047 if (_parent[arc] != INVALID) {
2048 if (_left[_parent[arc]] == arc) {
2049 _left[_parent[arc]] = e;
2051 _right[_parent[arc]] = e;
2054 _head[_g.source(arc)] = e;
2060 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2065 Arc left = refreshRec(v,a,m-1);
2069 _left[me] = INVALID;
2072 Arc right = refreshRec(v,m+1,b);
2074 _parent[right] = me;
2076 _right[me] = INVALID;
2082 for(NodeIt n(_g);n!=INVALID;++n) {
2084 for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
2086 std::sort(v.begin(),v.end(),ArcLess(_g));
2087 Arc head = refreshRec(v,0,v.size()-1);
2089 _parent[head] = INVALID;
2091 else _head[n] = INVALID;
2097 _parent[v] = _parent[w];
2099 _left[w] = _right[v];
2101 if (_parent[v] != INVALID) {
2102 if (_right[_parent[v]] == w) {
2103 _right[_parent[v]] = v;
2105 _left[_parent[v]] = v;
2108 if (_left[w] != INVALID){
2109 _parent[_left[w]] = w;
2115 _parent[v] = _parent[w];
2117 _right[w] = _left[v];
2119 if (_parent[v] != INVALID){
2120 if (_left[_parent[v]] == w) {
2121 _left[_parent[v]] = v;
2123 _right[_parent[v]] = v;
2126 if (_right[w] != INVALID){
2127 _parent[_right[w]] = w;
2132 while (_parent[v] != INVALID) {
2133 if (v == _left[_parent[v]]) {
2134 if (_parent[_parent[v]] == INVALID) {
2137 if (_parent[v] == _left[_parent[_parent[v]]]) {
2146 if (_parent[_parent[v]] == INVALID) {
2149 if (_parent[v] == _left[_parent[_parent[v]]]) {
2159 _head[_g.source(v)] = v;
2165 ///Find an arc between two nodes.
2167 ///Find an arc between two nodes.
2168 ///\param s The source node.
2169 ///\param t The target node.
2170 ///\param p The previous arc between \c s and \c t. It it is INVALID or
2171 ///not given, the operator finds the first appropriate arc.
2172 ///\return An arc from \c s to \c t after \c p or
2173 ///\ref INVALID if there is no more.
2175 ///For example, you can count the number of arcs from \c u to \c v in the
2178 ///DynArcLookUp<ListDigraph> ae(g);
2181 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
2184 ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
2185 ///amortized time, specifically, the time complexity of the lookups
2186 ///is equal to the optimal search tree implementation for the
2187 ///current query distribution in a constant factor.
2189 ///\note This is a dynamic data structure, therefore the data
2190 ///structure is updated after each graph alteration. Thus although
2191 ///this data structure is theoretically faster than \ref ArcLookUp
2192 ///and \ref AllArcLookUp, it often provides worse performance than
2194 Arc operator()(Node s, Node t, Arc p = INVALID) const {
2197 if (a == INVALID) return INVALID;
2200 if (_g.target(a) < t) {
2201 if (_right[a] == INVALID) {
2202 const_cast<DynArcLookUp&>(*this).splay(a);
2208 if (_g.target(a) == t) {
2211 if (_left[a] == INVALID) {
2212 const_cast<DynArcLookUp&>(*this).splay(a);
2221 if (_right[a] != INVALID) {
2223 while (_left[a] != INVALID) {
2226 const_cast<DynArcLookUp&>(*this).splay(a);
2228 while (_parent[a] != INVALID && _right[_parent[a]] == a) {
2231 if (_parent[a] == INVALID) {
2235 const_cast<DynArcLookUp&>(*this).splay(a);
2238 if (_g.target(a) == t) return a;
2239 else return INVALID;
2245 ///Fast arc look-up between given endpoints.
2247 ///Using this class, you can find an arc in a digraph from a given
2248 ///source to a given target in time <em>O</em>(log<em>d</em>),
2249 ///where <em>d</em> is the out-degree of the source node.
2251 ///It is not possible to find \e all parallel arcs between two nodes.
2252 ///Use \ref AllArcLookUp for this purpose.
2254 ///\warning This class is static, so you should call refresh() (or at
2255 ///least refresh(Node)) to refresh this data structure whenever the
2256 ///digraph changes. This is a time consuming (superlinearly proportional
2257 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
2259 ///\tparam GR The type of the underlying digraph.
2266 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2270 /// The Digraph type
2275 typename Digraph::template NodeMap<Arc> _head;
2276 typename Digraph::template ArcMap<Arc> _left;
2277 typename Digraph::template ArcMap<Arc> _right;
2282 ArcLess(const Digraph &_g) : g(_g) {}
2283 bool operator()(Arc a,Arc b) const
2285 return g.target(a)<g.target(b);
2295 ///It builds up the search database, which remains valid until the digraph
2297 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2300 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2304 _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2305 _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2309 ///Refresh the search data structure at a node.
2311 ///Build up the search database of node \c n.
2313 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
2314 ///is the number of the outgoing arcs of \c n.
2315 void refresh(Node n)
2318 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2320 std::sort(v.begin(),v.end(),ArcLess(_g));
2321 _head[n]=refreshRec(v,0,v.size()-1);
2323 else _head[n]=INVALID;
2325 ///Refresh the full data structure.
2327 ///Build up the full search database. In fact, it simply calls
2328 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2330 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
2331 ///the number of the arcs in the digraph and <em>D</em> is the maximum
2332 ///out-degree of the digraph.
2335 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2338 ///Find an arc between two nodes.
2340 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
2341 ///where <em>d</em> is the number of outgoing arcs of \c s.
2342 ///\param s The source node.
2343 ///\param t The target node.
2344 ///\return An arc from \c s to \c t if there exists,
2345 ///\ref INVALID otherwise.
2347 ///\warning If you change the digraph, refresh() must be called before using
2348 ///this operator. If you change the outgoing arcs of
2349 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
2350 Arc operator()(Node s, Node t) const
2354 e!=INVALID&&_g.target(e)!=t;
2355 e = t < _g.target(e)?_left[e]:_right[e]) ;
2361 ///Fast look-up of all arcs between given endpoints.
2363 ///This class is the same as \ref ArcLookUp, with the addition
2364 ///that it makes it possible to find all parallel arcs between given
2367 ///\warning This class is static, so you should call refresh() (or at
2368 ///least refresh(Node)) to refresh this data structure whenever the
2369 ///digraph changes. This is a time consuming (superlinearly proportional
2370 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
2372 ///\tparam GR The type of the underlying digraph.
2377 class AllArcLookUp : public ArcLookUp<GR>
2379 using ArcLookUp<GR>::_g;
2380 using ArcLookUp<GR>::_right;
2381 using ArcLookUp<GR>::_left;
2382 using ArcLookUp<GR>::_head;
2384 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2386 typename GR::template ArcMap<Arc> _next;
2388 Arc refreshNext(Arc head,Arc next=INVALID)
2390 if(head==INVALID) return next;
2392 next=refreshNext(_right[head],next);
2393 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2395 return refreshNext(_left[head],head);
2401 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2406 /// The Digraph type
2413 ///It builds up the search database, which remains valid until the digraph
2415 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
2417 ///Refresh the data structure at a node.
2419 ///Build up the search database of node \c n.
2421 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
2422 ///the number of the outgoing arcs of \c n.
2423 void refresh(Node n)
2425 ArcLookUp<GR>::refresh(n);
2426 refreshNext(_head[n]);
2429 ///Refresh the full data structure.
2431 ///Build up the full search database. In fact, it simply calls
2432 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2434 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
2435 ///the number of the arcs in the digraph and <em>D</em> is the maximum
2436 ///out-degree of the digraph.
2439 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2442 ///Find an arc between two nodes.
2444 ///Find an arc between two nodes.
2445 ///\param s The source node.
2446 ///\param t The target node.
2447 ///\param prev The previous arc between \c s and \c t. It it is INVALID or
2448 ///not given, the operator finds the first appropriate arc.
2449 ///\return An arc from \c s to \c t after \c prev or
2450 ///\ref INVALID if there is no more.
2452 ///For example, you can count the number of arcs from \c u to \c v in the
2455 ///AllArcLookUp<ListDigraph> ae(g);
2458 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
2461 ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
2462 ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
2463 ///consecutive arcs are found in constant time.
2465 ///\warning If you change the digraph, refresh() must be called before using
2466 ///this operator. If you change the outgoing arcs of
2467 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
2469 Arc operator()(Node s, Node t, Arc prev=INVALID) const
2476 e!=INVALID&&_g.target(e)!=t;
2477 e = t < _g.target(e)?_left[e]:_right[e]) ;
2487 else return _next[prev];