1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2011
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>
31 ///\brief LEMON core utilities.
33 ///This header file contains core utilities for LEMON.
34 ///It is automatically included by all graph types, therefore it usually
35 ///do not have to be included directly.
39 /// \brief Dummy type to make it easier to create invalid iterators.
41 /// Dummy type to make it easier to create invalid iterators.
42 /// See \ref INVALID for the usage.
45 bool operator==(Invalid) { return true; }
46 bool operator!=(Invalid) { return false; }
47 bool operator< (Invalid) { return false; }
50 /// \brief Invalid iterators.
52 /// \ref Invalid is a global type that converts to each iterator
53 /// in such a way that the value of the target iterator will be invalid.
54 #ifdef LEMON_ONLY_TEMPLATES
55 const Invalid INVALID = Invalid();
57 extern const Invalid INVALID;
60 /// \addtogroup gutils
63 ///Create convenience typedefs for the digraph types and iterators
65 ///This \c \#define creates convenient type definitions for the following
66 ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
67 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
68 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
70 ///\note If the graph type is a dependent type, ie. the graph type depend
71 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
73 #define DIGRAPH_TYPEDEFS(Digraph) \
74 typedef Digraph::Node Node; \
75 typedef Digraph::NodeIt NodeIt; \
76 typedef Digraph::Arc Arc; \
77 typedef Digraph::ArcIt ArcIt; \
78 typedef Digraph::InArcIt InArcIt; \
79 typedef Digraph::OutArcIt OutArcIt; \
80 typedef Digraph::NodeMap<bool> BoolNodeMap; \
81 typedef Digraph::NodeMap<int> IntNodeMap; \
82 typedef Digraph::NodeMap<double> DoubleNodeMap; \
83 typedef Digraph::ArcMap<bool> BoolArcMap; \
84 typedef Digraph::ArcMap<int> IntArcMap; \
85 typedef Digraph::ArcMap<double> DoubleArcMap
87 ///Create convenience typedefs for the digraph types and iterators
89 ///\see DIGRAPH_TYPEDEFS
91 ///\note Use this macro, if the graph type is a dependent type,
92 ///ie. the graph type depend on a template parameter.
93 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
94 typedef typename Digraph::Node Node; \
95 typedef typename Digraph::NodeIt NodeIt; \
96 typedef typename Digraph::Arc Arc; \
97 typedef typename Digraph::ArcIt ArcIt; \
98 typedef typename Digraph::InArcIt InArcIt; \
99 typedef typename Digraph::OutArcIt OutArcIt; \
100 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
101 typedef typename Digraph::template NodeMap<int> IntNodeMap; \
102 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
103 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
104 typedef typename Digraph::template ArcMap<int> IntArcMap; \
105 typedef typename Digraph::template ArcMap<double> DoubleArcMap
107 ///Create convenience typedefs for the graph types and iterators
109 ///This \c \#define creates the same convenient type definitions as defined
110 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
111 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
114 ///\note If the graph type is a dependent type, ie. the graph type depend
115 ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
117 #define GRAPH_TYPEDEFS(Graph) \
118 DIGRAPH_TYPEDEFS(Graph); \
119 typedef Graph::Edge Edge; \
120 typedef Graph::EdgeIt EdgeIt; \
121 typedef Graph::IncEdgeIt IncEdgeIt; \
122 typedef Graph::EdgeMap<bool> BoolEdgeMap; \
123 typedef Graph::EdgeMap<int> IntEdgeMap; \
124 typedef Graph::EdgeMap<double> DoubleEdgeMap
126 ///Create convenience typedefs for the graph types and iterators
128 ///\see GRAPH_TYPEDEFS
130 ///\note Use this macro, if the graph type is a dependent type,
131 ///ie. the graph type depend on a template parameter.
132 #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
133 TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
134 typedef typename Graph::Edge Edge; \
135 typedef typename Graph::EdgeIt EdgeIt; \
136 typedef typename Graph::IncEdgeIt IncEdgeIt; \
137 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
138 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
139 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
141 /// \brief Function to count the items in a graph.
143 /// This function counts the items (nodes, arcs etc.) in a graph.
144 /// The complexity of the function is linear because
145 /// it iterates on all of the items.
146 template <typename Graph, typename Item>
147 inline int countItems(const Graph& g) {
148 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
150 for (ItemIt it(g); it != INVALID; ++it) {
158 namespace _core_bits {
160 template <typename Graph, typename Enable = void>
161 struct CountNodesSelector {
162 static int count(const Graph &g) {
163 return countItems<Graph, typename Graph::Node>(g);
167 template <typename Graph>
168 struct CountNodesSelector<
170 enable_if<typename Graph::NodeNumTag, void>::type>
172 static int count(const Graph &g) {
178 /// \brief Function to count the nodes in the graph.
180 /// This function counts the nodes in the graph.
181 /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
182 /// graph structures it is specialized to run in <em>O</em>(1).
184 /// \note If the graph contains a \c nodeNum() member function and a
185 /// \c NodeNumTag tag then this function calls directly the member
186 /// function to query the cardinality of the node set.
187 template <typename Graph>
188 inline int countNodes(const Graph& g) {
189 return _core_bits::CountNodesSelector<Graph>::count(g);
194 namespace _core_bits {
196 template <typename Graph, typename Enable = void>
197 struct CountArcsSelector {
198 static int count(const Graph &g) {
199 return countItems<Graph, typename Graph::Arc>(g);
203 template <typename Graph>
204 struct CountArcsSelector<
206 typename enable_if<typename Graph::ArcNumTag, void>::type>
208 static int count(const Graph &g) {
214 /// \brief Function to count the arcs in the graph.
216 /// This function counts the arcs in the graph.
217 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
218 /// graph structures it is specialized to run in <em>O</em>(1).
220 /// \note If the graph contains a \c arcNum() member function and a
221 /// \c ArcNumTag tag then this function calls directly the member
222 /// function to query the cardinality of the arc set.
223 template <typename Graph>
224 inline int countArcs(const Graph& g) {
225 return _core_bits::CountArcsSelector<Graph>::count(g);
230 namespace _core_bits {
232 template <typename Graph, typename Enable = void>
233 struct CountEdgesSelector {
234 static int count(const Graph &g) {
235 return countItems<Graph, typename Graph::Edge>(g);
239 template <typename Graph>
240 struct CountEdgesSelector<
242 typename enable_if<typename Graph::EdgeNumTag, void>::type>
244 static int count(const Graph &g) {
250 /// \brief Function to count the edges in the graph.
252 /// This function counts the edges in the graph.
253 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
254 /// graph structures it is specialized to run in <em>O</em>(1).
256 /// \note If the graph contains a \c edgeNum() member function and a
257 /// \c EdgeNumTag tag then this function calls directly the member
258 /// function to query the cardinality of the edge set.
259 template <typename Graph>
260 inline int countEdges(const Graph& g) {
261 return _core_bits::CountEdgesSelector<Graph>::count(g);
266 template <typename Graph, typename DegIt>
267 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
269 for (DegIt it(_g, _n); it != INVALID; ++it) {
275 /// \brief Function to count the number of the out-arcs from node \c n.
277 /// This function counts the number of the out-arcs from node \c n
278 /// in the graph \c g.
279 template <typename Graph>
280 inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
281 return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
284 /// \brief Function to count the number of the in-arcs to node \c n.
286 /// This function counts the number of the in-arcs to node \c n
287 /// in the graph \c g.
288 template <typename Graph>
289 inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
290 return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
293 /// \brief Function to count the number of the inc-edges to node \c n.
295 /// This function counts the number of the inc-edges to node \c n
296 /// in the undirected graph \c g.
297 template <typename Graph>
298 inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
299 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
302 namespace _core_bits {
304 template <typename Digraph, typename Item, typename RefMap>
307 virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
309 virtual ~MapCopyBase() {}
312 template <typename Digraph, typename Item, typename RefMap,
313 typename FromMap, typename ToMap>
314 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
317 MapCopy(const FromMap& map, ToMap& tmap)
318 : _map(map), _tmap(tmap) {}
320 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
321 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
322 for (ItemIt it(digraph); it != INVALID; ++it) {
323 _tmap.set(refMap[it], _map[it]);
332 template <typename Digraph, typename Item, typename RefMap, typename It>
333 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
336 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
338 virtual void copy(const Digraph&, const RefMap& refMap) {
347 template <typename Digraph, typename Item, typename RefMap, typename Ref>
348 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
351 RefCopy(Ref& map) : _map(map) {}
353 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
354 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
355 for (ItemIt it(digraph); it != INVALID; ++it) {
356 _map.set(it, refMap[it]);
364 template <typename Digraph, typename Item, typename RefMap,
366 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
369 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
371 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
372 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
373 for (ItemIt it(digraph); it != INVALID; ++it) {
374 _cmap.set(refMap[it], it);
382 template <typename Digraph, typename Enable = void>
383 struct DigraphCopySelector {
384 template <typename From, typename NodeRefMap, typename ArcRefMap>
385 static void copy(const From& from, Digraph &to,
386 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
388 for (typename From::NodeIt it(from); it != INVALID; ++it) {
389 nodeRefMap[it] = to.addNode();
391 for (typename From::ArcIt it(from); it != INVALID; ++it) {
392 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
393 nodeRefMap[from.target(it)]);
398 template <typename Digraph>
399 struct DigraphCopySelector<
401 typename enable_if<typename Digraph::BuildTag, void>::type>
403 template <typename From, typename NodeRefMap, typename ArcRefMap>
404 static void copy(const From& from, Digraph &to,
405 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
406 to.build(from, nodeRefMap, arcRefMap);
410 template <typename Graph, typename Enable = void>
411 struct GraphCopySelector {
412 template <typename From, typename NodeRefMap, typename EdgeRefMap>
413 static void copy(const From& from, Graph &to,
414 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
416 for (typename From::NodeIt it(from); it != INVALID; ++it) {
417 nodeRefMap[it] = to.addNode();
419 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
420 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
421 nodeRefMap[from.v(it)]);
426 template <typename Graph>
427 struct GraphCopySelector<
429 typename enable_if<typename Graph::BuildTag, void>::type>
431 template <typename From, typename NodeRefMap, typename EdgeRefMap>
432 static void copy(const From& from, Graph &to,
433 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
434 to.build(from, nodeRefMap, edgeRefMap);
440 /// \brief Class to copy a digraph.
442 /// Class to copy a digraph to another digraph (duplicate a digraph). The
443 /// simplest way of using it is through the \c digraphCopy() function.
445 /// This class not only make a copy of a digraph, but it can create
446 /// references and cross references between the nodes and arcs of
447 /// the two digraphs, and it can copy maps to use with the newly created
450 /// To make a copy from a digraph, first an instance of DigraphCopy
451 /// should be created, then the data belongs to the digraph should
452 /// assigned to copy. In the end, the \c run() member should be
455 /// The next code copies a digraph with several data:
457 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
458 /// // Create references for the nodes
459 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
461 /// // Create cross references (inverse) for the arcs
462 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
463 /// cg.arcCrossRef(acr);
464 /// // Copy an arc map
465 /// OrigGraph::ArcMap<double> oamap(orig_graph);
466 /// NewGraph::ArcMap<double> namap(new_graph);
467 /// cg.arcMap(oamap, namap);
469 /// OrigGraph::Node on;
470 /// NewGraph::Node nn;
472 /// // Execute copying
475 template <typename From, typename To>
479 typedef typename From::Node Node;
480 typedef typename From::NodeIt NodeIt;
481 typedef typename From::Arc Arc;
482 typedef typename From::ArcIt ArcIt;
484 typedef typename To::Node TNode;
485 typedef typename To::Arc TArc;
487 typedef typename From::template NodeMap<TNode> NodeRefMap;
488 typedef typename From::template ArcMap<TArc> ArcRefMap;
492 /// \brief Constructor of DigraphCopy.
494 /// Constructor of DigraphCopy for copying the content of the
495 /// \c from digraph into the \c to digraph.
496 DigraphCopy(const From& from, To& to)
497 : _from(from), _to(to) {}
499 /// \brief Destructor of DigraphCopy
501 /// Destructor of DigraphCopy.
503 for (int i = 0; i < int(_node_maps.size()); ++i) {
504 delete _node_maps[i];
506 for (int i = 0; i < int(_arc_maps.size()); ++i) {
512 /// \brief Copy the node references into the given map.
514 /// This function copies the node references into the given map.
515 /// The parameter should be a map, whose key type is the Node type of
516 /// the source digraph, while the value type is the Node type of the
517 /// destination digraph.
518 template <typename NodeRef>
519 DigraphCopy& nodeRef(NodeRef& map) {
520 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
521 NodeRefMap, NodeRef>(map));
525 /// \brief Copy the node cross references into the given map.
527 /// This function copies the node cross references (reverse references)
528 /// into the given map. The parameter should be a map, whose key type
529 /// is the Node type of the destination digraph, while the value type is
530 /// the Node type of the source digraph.
531 template <typename NodeCrossRef>
532 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
533 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
534 NodeRefMap, NodeCrossRef>(map));
538 /// \brief Make a copy of the given node map.
540 /// This function makes a copy of the given node map for the newly
542 /// The key type of the new map \c tmap should be the Node type of the
543 /// destination digraph, and the key type of the original map \c map
544 /// should be the Node type of the source digraph.
545 template <typename FromMap, typename ToMap>
546 DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
547 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
548 NodeRefMap, FromMap, ToMap>(map, tmap));
552 /// \brief Make a copy of the given node.
554 /// This function makes a copy of the given node.
555 DigraphCopy& node(const Node& node, TNode& tnode) {
556 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
557 NodeRefMap, TNode>(node, tnode));
561 /// \brief Copy the arc references into the given map.
563 /// This function copies the arc references into the given map.
564 /// The parameter should be a map, whose key type is the Arc type of
565 /// the source digraph, while the value type is the Arc type of the
566 /// destination digraph.
567 template <typename ArcRef>
568 DigraphCopy& arcRef(ArcRef& map) {
569 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
570 ArcRefMap, ArcRef>(map));
574 /// \brief Copy the arc cross references into the given map.
576 /// This function copies the arc cross references (reverse references)
577 /// into the given map. The parameter should be a map, whose key type
578 /// is the Arc type of the destination digraph, while the value type is
579 /// the Arc type of the source digraph.
580 template <typename ArcCrossRef>
581 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
582 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
583 ArcRefMap, ArcCrossRef>(map));
587 /// \brief Make a copy of the given arc map.
589 /// This function makes a copy of the given arc map for the newly
591 /// The key type of the new map \c tmap should be the Arc type of the
592 /// destination digraph, and the key type of the original map \c map
593 /// should be the Arc type of the source digraph.
594 template <typename FromMap, typename ToMap>
595 DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
596 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
597 ArcRefMap, FromMap, ToMap>(map, tmap));
601 /// \brief Make a copy of the given arc.
603 /// This function makes a copy of the given arc.
604 DigraphCopy& arc(const Arc& arc, TArc& tarc) {
605 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
606 ArcRefMap, TArc>(arc, tarc));
610 /// \brief Execute copying.
612 /// This function executes the copying of the digraph along with the
613 /// copying of the assigned data.
615 NodeRefMap nodeRefMap(_from);
616 ArcRefMap arcRefMap(_from);
617 _core_bits::DigraphCopySelector<To>::
618 copy(_from, _to, nodeRefMap, arcRefMap);
619 for (int i = 0; i < int(_node_maps.size()); ++i) {
620 _node_maps[i]->copy(_from, nodeRefMap);
622 for (int i = 0; i < int(_arc_maps.size()); ++i) {
623 _arc_maps[i]->copy(_from, arcRefMap);
632 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
635 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
640 /// \brief Copy a digraph to another digraph.
642 /// This function copies a digraph to another digraph.
643 /// The complete usage of it is detailed in the DigraphCopy class, but
644 /// a short example shows a basic work:
646 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
649 /// After the copy the \c nr map will contain the mapping from the
650 /// nodes of the \c from digraph to the nodes of the \c to digraph and
651 /// \c acr will contain the mapping from the arcs of the \c to digraph
652 /// to the arcs of the \c from digraph.
655 template <typename From, typename To>
656 DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
657 return DigraphCopy<From, To>(from, to);
660 /// \brief Class to copy a graph.
662 /// Class to copy a graph to another graph (duplicate a graph). The
663 /// simplest way of using it is through the \c graphCopy() function.
665 /// This class not only make a copy of a graph, but it can create
666 /// references and cross references between the nodes, edges and arcs of
667 /// the two graphs, and it can copy maps for using with the newly created
670 /// To make a copy from a graph, first an instance of GraphCopy
671 /// should be created, then the data belongs to the graph should
672 /// assigned to copy. In the end, the \c run() member should be
675 /// The next code copies a graph with several data:
677 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
678 /// // Create references for the nodes
679 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
681 /// // Create cross references (inverse) for the edges
682 /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
683 /// cg.edgeCrossRef(ecr);
684 /// // Copy an edge map
685 /// OrigGraph::EdgeMap<double> oemap(orig_graph);
686 /// NewGraph::EdgeMap<double> nemap(new_graph);
687 /// cg.edgeMap(oemap, nemap);
689 /// OrigGraph::Node on;
690 /// NewGraph::Node nn;
692 /// // Execute copying
695 template <typename From, typename To>
699 typedef typename From::Node Node;
700 typedef typename From::NodeIt NodeIt;
701 typedef typename From::Arc Arc;
702 typedef typename From::ArcIt ArcIt;
703 typedef typename From::Edge Edge;
704 typedef typename From::EdgeIt EdgeIt;
706 typedef typename To::Node TNode;
707 typedef typename To::Arc TArc;
708 typedef typename To::Edge TEdge;
710 typedef typename From::template NodeMap<TNode> NodeRefMap;
711 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
714 ArcRefMap(const From& from, const To& to,
715 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
716 : _from(from), _to(to),
717 _edge_ref(edge_ref), _node_ref(node_ref) {}
719 typedef typename From::Arc Key;
720 typedef typename To::Arc Value;
722 Value operator[](const Key& key) const {
723 bool forward = _from.u(key) != _from.v(key) ?
724 _node_ref[_from.source(key)] ==
725 _to.source(_to.direct(_edge_ref[key], true)) :
726 _from.direction(key);
727 return _to.direct(_edge_ref[key], forward);
732 const EdgeRefMap& _edge_ref;
733 const NodeRefMap& _node_ref;
738 /// \brief Constructor of GraphCopy.
740 /// Constructor of GraphCopy for copying the content of the
741 /// \c from graph into the \c to graph.
742 GraphCopy(const From& from, To& to)
743 : _from(from), _to(to) {}
745 /// \brief Destructor of GraphCopy
747 /// Destructor of GraphCopy.
749 for (int i = 0; i < int(_node_maps.size()); ++i) {
750 delete _node_maps[i];
752 for (int i = 0; i < int(_arc_maps.size()); ++i) {
755 for (int i = 0; i < int(_edge_maps.size()); ++i) {
756 delete _edge_maps[i];
760 /// \brief Copy the node references into the given map.
762 /// This function copies the node references into the given map.
763 /// The parameter should be a map, whose key type is the Node type of
764 /// the source graph, while the value type is the Node type of the
765 /// destination graph.
766 template <typename NodeRef>
767 GraphCopy& nodeRef(NodeRef& map) {
768 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
769 NodeRefMap, NodeRef>(map));
773 /// \brief Copy the node cross references into the given map.
775 /// This function copies the node cross references (reverse references)
776 /// into the given map. The parameter should be a map, whose key type
777 /// is the Node type of the destination graph, while the value type is
778 /// the Node type of the source graph.
779 template <typename NodeCrossRef>
780 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
781 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
782 NodeRefMap, NodeCrossRef>(map));
786 /// \brief Make a copy of the given node map.
788 /// This function makes a copy of the given node map for the newly
790 /// The key type of the new map \c tmap should be the Node type of the
791 /// destination graph, and the key type of the original map \c map
792 /// should be the Node type of the source graph.
793 template <typename FromMap, typename ToMap>
794 GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
795 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
796 NodeRefMap, FromMap, ToMap>(map, tmap));
800 /// \brief Make a copy of the given node.
802 /// This function makes a copy of the given node.
803 GraphCopy& node(const Node& node, TNode& tnode) {
804 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
805 NodeRefMap, TNode>(node, tnode));
809 /// \brief Copy the arc references into the given map.
811 /// This function copies the arc references into the given map.
812 /// The parameter should be a map, whose key type is the Arc type of
813 /// the source graph, while the value type is the Arc type of the
814 /// destination graph.
815 template <typename ArcRef>
816 GraphCopy& arcRef(ArcRef& map) {
817 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
818 ArcRefMap, ArcRef>(map));
822 /// \brief Copy the arc cross references into the given map.
824 /// This function copies the arc cross references (reverse references)
825 /// into the given map. The parameter should be a map, whose key type
826 /// is the Arc type of the destination graph, while the value type is
827 /// the Arc type of the source graph.
828 template <typename ArcCrossRef>
829 GraphCopy& arcCrossRef(ArcCrossRef& map) {
830 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
831 ArcRefMap, ArcCrossRef>(map));
835 /// \brief Make a copy of the given arc map.
837 /// This function makes a copy of the given arc map for the newly
839 /// The key type of the new map \c tmap should be the Arc type of the
840 /// destination graph, and the key type of the original map \c map
841 /// should be the Arc type of the source graph.
842 template <typename FromMap, typename ToMap>
843 GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
844 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
845 ArcRefMap, FromMap, ToMap>(map, tmap));
849 /// \brief Make a copy of the given arc.
851 /// This function makes a copy of the given arc.
852 GraphCopy& arc(const Arc& arc, TArc& tarc) {
853 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
854 ArcRefMap, TArc>(arc, tarc));
858 /// \brief Copy the edge references into the given map.
860 /// This function copies the edge references into the given map.
861 /// The parameter should be a map, whose key type is the Edge type of
862 /// the source graph, while the value type is the Edge type of the
863 /// destination graph.
864 template <typename EdgeRef>
865 GraphCopy& edgeRef(EdgeRef& map) {
866 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
867 EdgeRefMap, EdgeRef>(map));
871 /// \brief Copy the edge cross references into the given map.
873 /// This function copies the edge cross references (reverse references)
874 /// into the given map. The parameter should be a map, whose key type
875 /// is the Edge type of the destination graph, while the value type is
876 /// the Edge type of the source graph.
877 template <typename EdgeCrossRef>
878 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
879 _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
880 Edge, EdgeRefMap, EdgeCrossRef>(map));
884 /// \brief Make a copy of the given edge map.
886 /// This function makes a copy of the given edge map for the newly
888 /// The key type of the new map \c tmap should be the Edge type of the
889 /// destination graph, and the key type of the original map \c map
890 /// should be the Edge type of the source graph.
891 template <typename FromMap, typename ToMap>
892 GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
893 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
894 EdgeRefMap, FromMap, ToMap>(map, tmap));
898 /// \brief Make a copy of the given edge.
900 /// This function makes a copy of the given edge.
901 GraphCopy& edge(const Edge& edge, TEdge& tedge) {
902 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
903 EdgeRefMap, TEdge>(edge, tedge));
907 /// \brief Execute copying.
909 /// This function executes the copying of the graph along with the
910 /// copying of the assigned data.
912 NodeRefMap nodeRefMap(_from);
913 EdgeRefMap edgeRefMap(_from);
914 ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
915 _core_bits::GraphCopySelector<To>::
916 copy(_from, _to, nodeRefMap, edgeRefMap);
917 for (int i = 0; i < int(_node_maps.size()); ++i) {
918 _node_maps[i]->copy(_from, nodeRefMap);
920 for (int i = 0; i < int(_edge_maps.size()); ++i) {
921 _edge_maps[i]->copy(_from, edgeRefMap);
923 for (int i = 0; i < int(_arc_maps.size()); ++i) {
924 _arc_maps[i]->copy(_from, arcRefMap);
933 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
936 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
939 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
944 /// \brief Copy a graph to another graph.
946 /// This function copies a graph to another graph.
947 /// The complete usage of it is detailed in the GraphCopy class,
948 /// but a short example shows a basic work:
950 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
953 /// After the copy the \c nr map will contain the mapping from the
954 /// nodes of the \c from graph to the nodes of the \c to graph and
955 /// \c ecr will contain the mapping from the edges of the \c to graph
956 /// to the edges of the \c from graph.
959 template <typename From, typename To>
961 graphCopy(const From& from, To& to) {
962 return GraphCopy<From, To>(from, to);
965 namespace _core_bits {
967 template <typename Graph, typename Enable = void>
968 struct FindArcSelector {
969 typedef typename Graph::Node Node;
970 typedef typename Graph::Arc Arc;
971 static Arc find(const Graph &g, Node u, Node v, Arc e) {
977 while (e != INVALID && g.target(e) != v) {
984 template <typename Graph>
985 struct FindArcSelector<
987 typename enable_if<typename Graph::FindArcTag, void>::type>
989 typedef typename Graph::Node Node;
990 typedef typename Graph::Arc Arc;
991 static Arc find(const Graph &g, Node u, Node v, Arc prev) {
992 return g.findArc(u, v, prev);
997 /// \brief Find an arc between two nodes of a digraph.
999 /// This function finds an arc from node \c u to node \c v in the
1002 /// If \c prev is \ref INVALID (this is the default value), then
1003 /// it finds the first arc from \c u to \c v. Otherwise it looks for
1004 /// the next arc from \c u to \c v after \c prev.
1005 /// \return The found arc or \ref INVALID if there is no such an arc.
1007 /// Thus you can iterate through each arc from \c u to \c v as it follows.
1009 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1014 /// \note \ref ConArcIt provides iterator interface for the same
1018 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1019 template <typename Graph>
1020 inline typename Graph::Arc
1021 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1022 typename Graph::Arc prev = INVALID) {
1023 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1026 /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1028 /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1029 /// a higher level interface for the \ref findArc() function. You can
1030 /// use it the following way:
1032 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1038 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1039 template <typename _Graph>
1040 class ConArcIt : public _Graph::Arc {
1043 typedef _Graph Graph;
1044 typedef typename Graph::Arc Parent;
1046 typedef typename Graph::Arc Arc;
1047 typedef typename Graph::Node Node;
1049 /// \brief Constructor.
1051 /// Construct a new ConArcIt iterating on the arcs that
1052 /// connects nodes \c u and \c v.
1053 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1054 Parent::operator=(findArc(_graph, u, v));
1057 /// \brief Constructor.
1059 /// Construct a new ConArcIt that continues the iterating from arc \c a.
1060 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1062 /// \brief Increment operator.
1064 /// It increments the iterator and gives back the next arc.
1065 ConArcIt& operator++() {
1066 Parent::operator=(findArc(_graph, _graph.source(*this),
1067 _graph.target(*this), *this));
1071 const Graph& _graph;
1074 namespace _core_bits {
1076 template <typename Graph, typename Enable = void>
1077 struct FindEdgeSelector {
1078 typedef typename Graph::Node Node;
1079 typedef typename Graph::Edge Edge;
1080 static Edge find(const Graph &g, Node u, Node v, Edge e) {
1084 g.firstInc(e, b, u);
1089 while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1094 g.firstInc(e, b, u);
1099 while (e != INVALID && (!b || g.v(e) != v)) {
1107 template <typename Graph>
1108 struct FindEdgeSelector<
1110 typename enable_if<typename Graph::FindEdgeTag, void>::type>
1112 typedef typename Graph::Node Node;
1113 typedef typename Graph::Edge Edge;
1114 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1115 return g.findEdge(u, v, prev);
1120 /// \brief Find an edge between two nodes of a graph.
1122 /// This function finds an edge from node \c u to node \c v in graph \c g.
1123 /// If node \c u and node \c v is equal then each loop edge
1124 /// will be enumerated once.
1126 /// If \c prev is \ref INVALID (this is the default value), then
1127 /// it finds the first edge from \c u to \c v. Otherwise it looks for
1128 /// the next edge from \c u to \c v after \c prev.
1129 /// \return The found edge or \ref INVALID if there is no such an edge.
1131 /// Thus you can iterate through each edge between \c u and \c v
1134 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1139 /// \note \ref ConEdgeIt provides iterator interface for the same
1143 template <typename Graph>
1144 inline typename Graph::Edge
1145 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1146 typename Graph::Edge p = INVALID) {
1147 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1150 /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1152 /// Iterator for iterating on parallel edges connecting the same nodes.
1153 /// It is a higher level interface for the findEdge() function. You can
1154 /// use it the following way:
1156 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1162 template <typename _Graph>
1163 class ConEdgeIt : public _Graph::Edge {
1166 typedef _Graph Graph;
1167 typedef typename Graph::Edge Parent;
1169 typedef typename Graph::Edge Edge;
1170 typedef typename Graph::Node Node;
1172 /// \brief Constructor.
1174 /// Construct a new ConEdgeIt iterating on the edges that
1175 /// connects nodes \c u and \c v.
1176 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1177 Parent::operator=(findEdge(_graph, _u, _v));
1180 /// \brief Constructor.
1182 /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1183 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1185 /// \brief Increment operator.
1187 /// It increments the iterator and gives back the next edge.
1188 ConEdgeIt& operator++() {
1189 Parent::operator=(findEdge(_graph, _u, _v, *this));
1193 const Graph& _graph;
1198 ///Dynamic arc look-up between given endpoints.
1200 ///Using this class, you can find an arc in a digraph from a given
1201 ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1202 ///where <em>d</em> is the out-degree of the source node.
1204 ///It is possible to find \e all parallel arcs between two nodes with
1205 ///the \c operator() member.
1207 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1208 ///\ref AllArcLookUp if your digraph is not changed so frequently.
1210 ///This class uses a self-adjusting binary search tree, the Splay tree
1211 ///of Sleator and Tarjan to guarantee the logarithmic amortized
1212 ///time bound for arc look-ups. This class also guarantees the
1213 ///optimal time bound in a constant factor for any distribution of
1216 ///\tparam G The type of the underlying digraph.
1222 : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1225 typedef typename ItemSetTraits<G, typename G::Arc>
1226 ::ItemNotifier::ObserverBase Parent;
1228 TEMPLATE_DIGRAPH_TYPEDEFS(G);
1233 class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
1236 typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
1238 AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1240 virtual void add(const Node& node) {
1242 Parent::set(node, INVALID);
1245 virtual void add(const std::vector<Node>& nodes) {
1247 for (int i = 0; i < int(nodes.size()); ++i) {
1248 Parent::set(nodes[i], INVALID);
1252 virtual void build() {
1255 typename Parent::Notifier* nf = Parent::notifier();
1256 for (nf->first(it); it != INVALID; nf->next(it)) {
1257 Parent::set(it, INVALID);
1264 typename Digraph::template ArcMap<Arc> _parent;
1265 typename Digraph::template ArcMap<Arc> _left;
1266 typename Digraph::template ArcMap<Arc> _right;
1271 ArcLess(const Digraph &_g) : g(_g) {}
1272 bool operator()(Arc a,Arc b) const
1274 return g.target(a)<g.target(b);
1284 ///It builds up the search database.
1285 DynArcLookUp(const Digraph &g)
1286 : _g(g),_head(g),_parent(g),_left(g),_right(g)
1288 Parent::attach(_g.notifier(typename Digraph::Arc()));
1294 virtual void add(const Arc& arc) {
1298 virtual void add(const std::vector<Arc>& arcs) {
1299 for (int i = 0; i < int(arcs.size()); ++i) {
1304 virtual void erase(const Arc& arc) {
1308 virtual void erase(const std::vector<Arc>& arcs) {
1309 for (int i = 0; i < int(arcs.size()); ++i) {
1314 virtual void build() {
1318 virtual void clear() {
1319 for(NodeIt n(_g);n!=INVALID;++n) {
1320 _head.set(n, INVALID);
1324 void insert(Arc arc) {
1325 Node s = _g.source(arc);
1326 Node t = _g.target(arc);
1327 _left.set(arc, INVALID);
1328 _right.set(arc, INVALID);
1333 _parent.set(arc, INVALID);
1337 if (t < _g.target(e)) {
1338 if (_left[e] == INVALID) {
1340 _parent.set(arc, e);
1347 if (_right[e] == INVALID) {
1349 _parent.set(arc, e);
1359 void remove(Arc arc) {
1360 if (_left[arc] == INVALID) {
1361 if (_right[arc] != INVALID) {
1362 _parent.set(_right[arc], _parent[arc]);
1364 if (_parent[arc] != INVALID) {
1365 if (_left[_parent[arc]] == arc) {
1366 _left.set(_parent[arc], _right[arc]);
1368 _right.set(_parent[arc], _right[arc]);
1371 _head.set(_g.source(arc), _right[arc]);
1373 } else if (_right[arc] == INVALID) {
1374 _parent.set(_left[arc], _parent[arc]);
1375 if (_parent[arc] != INVALID) {
1376 if (_left[_parent[arc]] == arc) {
1377 _left.set(_parent[arc], _left[arc]);
1379 _right.set(_parent[arc], _left[arc]);
1382 _head.set(_g.source(arc), _left[arc]);
1386 if (_right[e] != INVALID) {
1388 while (_right[e] != INVALID) {
1392 _right.set(_parent[e], _left[e]);
1393 if (_left[e] != INVALID) {
1394 _parent.set(_left[e], _parent[e]);
1397 _left.set(e, _left[arc]);
1398 _parent.set(_left[arc], e);
1399 _right.set(e, _right[arc]);
1400 _parent.set(_right[arc], e);
1402 _parent.set(e, _parent[arc]);
1403 if (_parent[arc] != INVALID) {
1404 if (_left[_parent[arc]] == arc) {
1405 _left.set(_parent[arc], e);
1407 _right.set(_parent[arc], e);
1412 _right.set(e, _right[arc]);
1413 _parent.set(_right[arc], e);
1414 _parent.set(e, _parent[arc]);
1416 if (_parent[arc] != INVALID) {
1417 if (_left[_parent[arc]] == arc) {
1418 _left.set(_parent[arc], e);
1420 _right.set(_parent[arc], e);
1423 _head.set(_g.source(arc), e);
1429 Arc refreshRec(std::vector<Arc> &v,int a,int b)
1434 Arc left = refreshRec(v,a,m-1);
1435 _left.set(me, left);
1436 _parent.set(left, me);
1438 _left.set(me, INVALID);
1441 Arc right = refreshRec(v,m+1,b);
1442 _right.set(me, right);
1443 _parent.set(right, me);
1445 _right.set(me, INVALID);
1451 for(NodeIt n(_g);n!=INVALID;++n) {
1453 for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
1455 std::sort(v.begin(),v.end(),ArcLess(_g));
1456 Arc head = refreshRec(v,0,v.size()-1);
1458 _parent.set(head, INVALID);
1460 else _head.set(n, INVALID);
1466 _parent.set(v, _parent[w]);
1468 _left.set(w, _right[v]);
1470 if (_parent[v] != INVALID) {
1471 if (_right[_parent[v]] == w) {
1472 _right.set(_parent[v], v);
1474 _left.set(_parent[v], v);
1477 if (_left[w] != INVALID){
1478 _parent.set(_left[w], w);
1484 _parent.set(v, _parent[w]);
1486 _right.set(w, _left[v]);
1488 if (_parent[v] != INVALID){
1489 if (_left[_parent[v]] == w) {
1490 _left.set(_parent[v], v);
1492 _right.set(_parent[v], v);
1495 if (_right[w] != INVALID){
1496 _parent.set(_right[w], w);
1501 while (_parent[v] != INVALID) {
1502 if (v == _left[_parent[v]]) {
1503 if (_parent[_parent[v]] == INVALID) {
1506 if (_parent[v] == _left[_parent[_parent[v]]]) {
1515 if (_parent[_parent[v]] == INVALID) {
1518 if (_parent[v] == _left[_parent[_parent[v]]]) {
1528 _head[_g.source(v)] = v;
1534 ///Find an arc between two nodes.
1536 ///Find an arc between two nodes.
1537 ///\param s The source node.
1538 ///\param t The target node.
1539 ///\param p The previous arc between \c s and \c t. It it is INVALID or
1540 ///not given, the operator finds the first appropriate arc.
1541 ///\return An arc from \c s to \c t after \c p or
1542 ///\ref INVALID if there is no more.
1544 ///For example, you can count the number of arcs from \c u to \c v in the
1547 ///DynArcLookUp<ListDigraph> ae(g);
1550 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
1553 ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
1554 ///amortized time, specifically, the time complexity of the lookups
1555 ///is equal to the optimal search tree implementation for the
1556 ///current query distribution in a constant factor.
1558 ///\note This is a dynamic data structure, therefore the data
1559 ///structure is updated after each graph alteration. Thus although
1560 ///this data structure is theoretically faster than \ref ArcLookUp
1561 ///and \ref AllArcLookUp, it often provides worse performance than
1563 Arc operator()(Node s, Node t, Arc p = INVALID) const {
1566 if (a == INVALID) return INVALID;
1569 if (_g.target(a) < t) {
1570 if (_right[a] == INVALID) {
1571 const_cast<DynArcLookUp&>(*this).splay(a);
1577 if (_g.target(a) == t) {
1580 if (_left[a] == INVALID) {
1581 const_cast<DynArcLookUp&>(*this).splay(a);
1590 if (_right[a] != INVALID) {
1592 while (_left[a] != INVALID) {
1595 const_cast<DynArcLookUp&>(*this).splay(a);
1597 while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1600 if (_parent[a] == INVALID) {
1604 const_cast<DynArcLookUp&>(*this).splay(a);
1607 if (_g.target(a) == t) return a;
1608 else return INVALID;
1614 ///Fast arc look-up between given endpoints.
1616 ///Using this class, you can find an arc in a digraph from a given
1617 ///source to a given target in time <em>O</em>(log<em>d</em>),
1618 ///where <em>d</em> is the out-degree of the source node.
1620 ///It is not possible to find \e all parallel arcs between two nodes.
1621 ///Use \ref AllArcLookUp for this purpose.
1623 ///\warning This class is static, so you should call refresh() (or at
1624 ///least refresh(Node)) to refresh this data structure whenever the
1625 ///digraph changes. This is a time consuming (superlinearly proportional
1626 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1628 ///\tparam G The type of the underlying digraph.
1636 TEMPLATE_DIGRAPH_TYPEDEFS(G);
1641 typename Digraph::template NodeMap<Arc> _head;
1642 typename Digraph::template ArcMap<Arc> _left;
1643 typename Digraph::template ArcMap<Arc> _right;
1648 ArcLess(const Digraph &_g) : g(_g) {}
1649 bool operator()(Arc a,Arc b) const
1651 return g.target(a)<g.target(b);
1661 ///It builds up the search database, which remains valid until the digraph
1663 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1666 Arc refreshRec(std::vector<Arc> &v,int a,int b)
1670 _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1671 _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1675 ///Refresh the search data structure at a node.
1677 ///Build up the search database of node \c n.
1679 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
1680 ///is the number of the outgoing arcs of \c n.
1681 void refresh(Node n)
1684 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1686 std::sort(v.begin(),v.end(),ArcLess(_g));
1687 _head[n]=refreshRec(v,0,v.size()-1);
1689 else _head[n]=INVALID;
1691 ///Refresh the full data structure.
1693 ///Build up the full search database. In fact, it simply calls
1694 ///\ref refresh(Node) "refresh(n)" for each node \c n.
1696 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1697 ///the number of the arcs in the digraph and <em>D</em> is the maximum
1698 ///out-degree of the digraph.
1701 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1704 ///Find an arc between two nodes.
1706 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
1707 ///where <em>d</em> is the number of outgoing arcs of \c s.
1708 ///\param s The source node.
1709 ///\param t The target node.
1710 ///\return An arc from \c s to \c t if there exists,
1711 ///\ref INVALID otherwise.
1713 ///\warning If you change the digraph, refresh() must be called before using
1714 ///this operator. If you change the outgoing arcs of
1715 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1716 Arc operator()(Node s, Node t) const
1720 e!=INVALID&&_g.target(e)!=t;
1721 e = t < _g.target(e)?_left[e]:_right[e]) ;
1727 ///Fast look-up of all arcs between given endpoints.
1729 ///This class is the same as \ref ArcLookUp, with the addition
1730 ///that it makes it possible to find all parallel arcs between given
1733 ///\warning This class is static, so you should call refresh() (or at
1734 ///least refresh(Node)) to refresh this data structure whenever the
1735 ///digraph changes. This is a time consuming (superlinearly proportional
1736 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1738 ///\tparam G The type of the underlying digraph.
1743 class AllArcLookUp : public ArcLookUp<G>
1745 using ArcLookUp<G>::_g;
1746 using ArcLookUp<G>::_right;
1747 using ArcLookUp<G>::_left;
1748 using ArcLookUp<G>::_head;
1750 TEMPLATE_DIGRAPH_TYPEDEFS(G);
1753 typename Digraph::template ArcMap<Arc> _next;
1755 Arc refreshNext(Arc head,Arc next=INVALID)
1757 if(head==INVALID) return next;
1759 next=refreshNext(_right[head],next);
1760 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1762 return refreshNext(_left[head],head);
1768 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1776 ///It builds up the search database, which remains valid until the digraph
1778 AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
1780 ///Refresh the data structure at a node.
1782 ///Build up the search database of node \c n.
1784 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
1785 ///the number of the outgoing arcs of \c n.
1786 void refresh(Node n)
1788 ArcLookUp<G>::refresh(n);
1789 refreshNext(_head[n]);
1792 ///Refresh the full data structure.
1794 ///Build up the full search database. In fact, it simply calls
1795 ///\ref refresh(Node) "refresh(n)" for each node \c n.
1797 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1798 ///the number of the arcs in the digraph and <em>D</em> is the maximum
1799 ///out-degree of the digraph.
1802 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1805 ///Find an arc between two nodes.
1807 ///Find an arc between two nodes.
1808 ///\param s The source node.
1809 ///\param t The target node.
1810 ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1811 ///not given, the operator finds the first appropriate arc.
1812 ///\return An arc from \c s to \c t after \c prev or
1813 ///\ref INVALID if there is no more.
1815 ///For example, you can count the number of arcs from \c u to \c v in the
1818 ///AllArcLookUp<ListDigraph> ae(g);
1821 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
1824 ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
1825 ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
1826 ///consecutive arcs are found in constant time.
1828 ///\warning If you change the digraph, refresh() must be called before using
1829 ///this operator. If you change the outgoing arcs of
1830 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1833 Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1835 using ArcLookUp<G>::operator() ;
1836 Arc operator()(Node s, Node t, Arc prev) const
1838 return prev==INVALID?(*this)(s,t):_next[prev];