Small bug fixes.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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
19 #ifndef LEMON_GRAPH_UTILS_H
20 #define LEMON_GRAPH_UTILS_H
28 #include <lemon/bits/invalid.h>
29 #include <lemon/bits/utility.h>
30 #include <lemon/maps.h>
31 #include <lemon/bits/traits.h>
33 #include <lemon/bits/alteration_notifier.h>
34 #include <lemon/bits/default_map.h>
38 ///\brief Graph utilities.
45 /// \addtogroup gutils
48 ///Creates convenience typedefs for the graph types and iterators
50 ///This \c \#define creates convenience typedefs for the following types
51 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
53 ///\note If \c G it a template parameter, it should be used in this way.
55 /// GRAPH_TYPEDEFS(typename G)
58 ///\warning There are no typedefs for the graph maps because of the lack of
59 ///template typedefs in C++.
60 #define GRAPH_TYPEDEFS(Graph) \
61 typedef Graph:: Node Node; \
62 typedef Graph:: NodeIt NodeIt; \
63 typedef Graph:: Edge Edge; \
64 typedef Graph:: EdgeIt EdgeIt; \
65 typedef Graph:: InEdgeIt InEdgeIt; \
66 typedef Graph::OutEdgeIt OutEdgeIt;
68 ///Creates convenience typedefs for the undirected graph types and iterators
70 ///This \c \#define creates the same convenience typedefs as defined by
71 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
72 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
74 ///\note If \c G it a template parameter, it should be used in this way.
76 /// UGRAPH_TYPEDEFS(typename G)
79 ///\warning There are no typedefs for the graph maps because of the lack of
80 ///template typedefs in C++.
81 #define UGRAPH_TYPEDEFS(Graph) \
82 GRAPH_TYPEDEFS(Graph) \
83 typedef Graph:: UEdge UEdge; \
84 typedef Graph:: UEdgeIt UEdgeIt; \
85 typedef Graph:: IncEdgeIt IncEdgeIt;
87 ///\brief Creates convenience typedefs for the bipartite undirected graph
88 ///types and iterators
90 ///This \c \#define creates the same convenience typedefs as defined by
91 ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates
92 ///\c ANodeIt, \c BNodeIt,
94 ///\note If \c G it a template parameter, it should be used in this way.
96 /// BPUGRAPH_TYPEDEFS(typename G)
99 ///\warning There are no typedefs for the graph maps because of the lack of
100 ///template typedefs in C++.
101 #define BPUGRAPH_TYPEDEFS(Graph) \
102 UGRAPH_TYPEDEFS(Graph) \
103 typedef Graph::ANode ANode; \
104 typedef Graph::BNode BNode; \
105 typedef Graph::ANodeIt ANodeIt; \
106 typedef Graph::BNodeIt BNodeIt;
108 /// \brief Function to count the items in the graph.
110 /// This function counts the items (nodes, edges etc) in the graph.
111 /// The complexity of the function is O(n) because
112 /// it iterates on all of the items.
114 template <typename Graph, typename Item>
115 inline int countItems(const Graph& g) {
116 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
118 for (ItemIt it(g); it != INVALID; ++it) {
126 namespace _graph_utils_bits {
128 template <typename Graph, typename Enable = void>
129 struct CountNodesSelector {
130 static int count(const Graph &g) {
131 return countItems<Graph, typename Graph::Node>(g);
135 template <typename Graph>
136 struct CountNodesSelector<
138 enable_if<typename Graph::NodeNumTag, void>::type>
140 static int count(const Graph &g) {
146 /// \brief Function to count the nodes in the graph.
148 /// This function counts the nodes in the graph.
149 /// The complexity of the function is O(n) but for some
150 /// graph structures it is specialized to run in O(1).
152 /// \todo refer how to specialize it
154 template <typename Graph>
155 inline int countNodes(const Graph& g) {
156 return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
159 namespace _graph_utils_bits {
161 template <typename Graph, typename Enable = void>
162 struct CountANodesSelector {
163 static int count(const Graph &g) {
164 return countItems<Graph, typename Graph::ANode>(g);
168 template <typename Graph>
169 struct CountANodesSelector<
171 enable_if<typename Graph::NodeNumTag, void>::type>
173 static int count(const Graph &g) {
179 /// \brief Function to count the anodes in the graph.
181 /// This function counts the anodes in the graph.
182 /// The complexity of the function is O(an) but for some
183 /// graph structures it is specialized to run in O(1).
185 /// \todo refer how to specialize it
187 template <typename Graph>
188 inline int countANodes(const Graph& g) {
189 return _graph_utils_bits::CountANodesSelector<Graph>::count(g);
192 namespace _graph_utils_bits {
194 template <typename Graph, typename Enable = void>
195 struct CountBNodesSelector {
196 static int count(const Graph &g) {
197 return countItems<Graph, typename Graph::BNode>(g);
201 template <typename Graph>
202 struct CountBNodesSelector<
204 enable_if<typename Graph::NodeNumTag, void>::type>
206 static int count(const Graph &g) {
212 /// \brief Function to count the bnodes in the graph.
214 /// This function counts the bnodes in the graph.
215 /// The complexity of the function is O(bn) but for some
216 /// graph structures it is specialized to run in O(1).
218 /// \todo refer how to specialize it
220 template <typename Graph>
221 inline int countBNodes(const Graph& g) {
222 return _graph_utils_bits::CountBNodesSelector<Graph>::count(g);
228 namespace _graph_utils_bits {
230 template <typename Graph, typename Enable = void>
231 struct CountEdgesSelector {
232 static int count(const Graph &g) {
233 return countItems<Graph, typename Graph::Edge>(g);
237 template <typename Graph>
238 struct CountEdgesSelector<
240 typename enable_if<typename Graph::EdgeNumTag, void>::type>
242 static int count(const Graph &g) {
248 /// \brief Function to count the edges in the graph.
250 /// This function counts the edges in the graph.
251 /// The complexity of the function is O(e) but for some
252 /// graph structures it is specialized to run in O(1).
254 template <typename Graph>
255 inline int countEdges(const Graph& g) {
256 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
259 // Undirected edge counting:
260 namespace _graph_utils_bits {
262 template <typename Graph, typename Enable = void>
263 struct CountUEdgesSelector {
264 static int count(const Graph &g) {
265 return countItems<Graph, typename Graph::UEdge>(g);
269 template <typename Graph>
270 struct CountUEdgesSelector<
272 typename enable_if<typename Graph::EdgeNumTag, void>::type>
274 static int count(const Graph &g) {
280 /// \brief Function to count the undirected edges in the graph.
282 /// This function counts the undirected edges in the graph.
283 /// The complexity of the function is O(e) but for some
284 /// graph structures it is specialized to run in O(1).
286 template <typename Graph>
287 inline int countUEdges(const Graph& g) {
288 return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
293 template <typename Graph, typename DegIt>
294 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
296 for (DegIt it(_g, _n); it != INVALID; ++it) {
302 /// \brief Function to count the number of the out-edges from node \c n.
304 /// This function counts the number of the out-edges from node \c n
306 template <typename Graph>
307 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
308 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
311 /// \brief Function to count the number of the in-edges to node \c n.
313 /// This function counts the number of the in-edges to node \c n
315 template <typename Graph>
316 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
317 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
320 /// \brief Function to count the number of the inc-edges to node \c n.
322 /// This function counts the number of the inc-edges to node \c n
324 template <typename Graph>
325 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
326 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
329 namespace _graph_utils_bits {
331 template <typename Graph, typename Enable = void>
332 struct FindEdgeSelector {
333 typedef typename Graph::Node Node;
334 typedef typename Graph::Edge Edge;
335 static Edge find(const Graph &g, Node u, Node v, Edge e) {
341 while (e != INVALID && g.target(e) != v) {
348 template <typename Graph>
349 struct FindEdgeSelector<
351 typename enable_if<typename Graph::FindEdgeTag, void>::type>
353 typedef typename Graph::Node Node;
354 typedef typename Graph::Edge Edge;
355 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
356 return g.findEdge(u, v, prev);
361 /// \brief Finds an edge between two nodes of a graph.
363 /// Finds an edge from node \c u to node \c v in graph \c g.
365 /// If \c prev is \ref INVALID (this is the default value), then
366 /// it finds the first edge from \c u to \c v. Otherwise it looks for
367 /// the next edge from \c u to \c v after \c prev.
368 /// \return The found edge or \ref INVALID if there is no such an edge.
370 /// Thus you can iterate through each edge from \c u to \c v as it follows.
372 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
380 template <typename Graph>
381 inline typename Graph::Edge
382 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
383 typename Graph::Edge prev = INVALID) {
384 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
387 /// \brief Iterator for iterating on edges connected the same nodes.
389 /// Iterator for iterating on edges connected the same nodes. It is
390 /// higher level interface for the findEdge() function. You can
391 /// use it the following way:
393 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
402 /// \author Balazs Dezso
403 template <typename _Graph>
404 class ConEdgeIt : public _Graph::Edge {
407 typedef _Graph Graph;
408 typedef typename Graph::Edge Parent;
410 typedef typename Graph::Edge Edge;
411 typedef typename Graph::Node Node;
413 /// \brief Constructor.
415 /// Construct a new ConEdgeIt iterating on the edges which
416 /// connects the \c u and \c v node.
417 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
418 Parent::operator=(findEdge(graph, u, v));
421 /// \brief Constructor.
423 /// Construct a new ConEdgeIt which continues the iterating from
425 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
427 /// \brief Increment operator.
429 /// It increments the iterator and gives back the next edge.
430 ConEdgeIt& operator++() {
431 Parent::operator=(findEdge(graph, graph.source(*this),
432 graph.target(*this), *this));
439 namespace _graph_utils_bits {
441 template <typename Graph, typename Enable = void>
442 struct FindUEdgeSelector {
443 typedef typename Graph::Node Node;
444 typedef typename Graph::UEdge UEdge;
445 static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
451 b = g.source(e) == u;
454 while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
464 while (e != INVALID && (!b || g.target(e) != v)) {
472 template <typename Graph>
473 struct FindUEdgeSelector<
475 typename enable_if<typename Graph::FindEdgeTag, void>::type>
477 typedef typename Graph::Node Node;
478 typedef typename Graph::UEdge UEdge;
479 static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
480 return g.findUEdge(u, v, prev);
485 /// \brief Finds an uedge between two nodes of a graph.
487 /// Finds an uedge from node \c u to node \c v in graph \c g.
488 /// If the node \c u and node \c v is equal then each loop edge
489 /// will be enumerated.
491 /// If \c prev is \ref INVALID (this is the default value), then
492 /// it finds the first edge from \c u to \c v. Otherwise it looks for
493 /// the next edge from \c u to \c v after \c prev.
494 /// \return The found edge or \ref INVALID if there is no such an edge.
496 /// Thus you can iterate through each edge from \c u to \c v as it follows.
498 /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
499 /// e = findUEdge(g,u,v,e)) {
506 template <typename Graph>
507 inline typename Graph::UEdge
508 findUEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
509 typename Graph::UEdge p = INVALID) {
510 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
513 /// \brief Iterator for iterating on uedges connected the same nodes.
515 /// Iterator for iterating on uedges connected the same nodes. It is
516 /// higher level interface for the findUEdge() function. You can
517 /// use it the following way:
519 /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
526 /// \author Balazs Dezso
527 template <typename _Graph>
528 class ConUEdgeIt : public _Graph::UEdge {
531 typedef _Graph Graph;
532 typedef typename Graph::UEdge Parent;
534 typedef typename Graph::UEdge UEdge;
535 typedef typename Graph::Node Node;
537 /// \brief Constructor.
539 /// Construct a new ConUEdgeIt iterating on the edges which
540 /// connects the \c u and \c v node.
541 ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
542 Parent::operator=(findUEdge(graph, u, v));
545 /// \brief Constructor.
547 /// Construct a new ConUEdgeIt which continues the iterating from
549 ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
551 /// \brief Increment operator.
553 /// It increments the iterator and gives back the next edge.
554 ConUEdgeIt& operator++() {
555 Parent::operator=(findUEdge(graph, graph.source(*this),
556 graph.target(*this), *this));
563 /// \brief Copy a map.
565 /// This function copies the \c source map to the \c target map. It uses the
566 /// given iterator to iterate on the data structure and it uses the \c ref
567 /// mapping to convert the source's keys to the target's keys.
568 template <typename Target, typename Source,
569 typename ItemIt, typename Ref>
570 void copyMap(Target& target, const Source& source,
571 ItemIt it, const Ref& ref) {
572 for (; it != INVALID; ++it) {
573 target[ref[it]] = source[it];
577 /// \brief Copy the source map to the target map.
579 /// Copy the \c source map to the \c target map. It uses the given iterator
580 /// to iterate on the data structure.
581 template <typename Target, typename Source, typename ItemIt>
582 void copyMap(Target& target, const Source& source, ItemIt it) {
583 for (; it != INVALID; ++it) {
584 target[it] = source[it];
588 namespace _graph_utils_bits {
590 template <typename Graph, typename Item, typename RefMap>
593 virtual void copy(const Graph& source, const RefMap& refMap) = 0;
595 virtual ~MapCopyBase() {}
598 template <typename Graph, typename Item, typename RefMap,
599 typename TargetMap, typename SourceMap>
600 class MapCopy : public MapCopyBase<Graph, Item, RefMap> {
603 MapCopy(TargetMap& tmap, const SourceMap& map)
604 : _tmap(tmap), _map(map) {}
606 virtual void copy(const Graph& graph, const RefMap& refMap) {
607 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
608 for (ItemIt it(graph); it != INVALID; ++it) {
609 _tmap.set(refMap[it], _map[it]);
615 const SourceMap& _map;
618 template <typename Graph, typename Item, typename RefMap, typename It>
619 class ItemCopy : public MapCopyBase<Graph, Item, RefMap> {
622 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
624 virtual void copy(const Graph&, const RefMap& refMap) {
633 template <typename Graph, typename Item, typename RefMap, typename Ref>
634 class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
637 RefCopy(Ref& map) : _map(map) {}
639 virtual void copy(const Graph& graph, const RefMap& refMap) {
640 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
641 for (ItemIt it(graph); it != INVALID; ++it) {
642 _map.set(it, refMap[it]);
650 template <typename Graph, typename Item, typename RefMap,
652 class CrossRefCopy : public MapCopyBase<Graph, Item, RefMap> {
655 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
657 virtual void copy(const Graph& graph, const RefMap& refMap) {
658 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
659 for (ItemIt it(graph); it != INVALID; ++it) {
660 _cmap.set(refMap[it], it);
668 template <typename Graph, typename Enable = void>
669 struct GraphCopySelector {
670 template <typename Source, typename NodeRefMap, typename EdgeRefMap>
671 static void copy(Graph &target, const Source& source,
672 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
673 for (typename Source::NodeIt it(source); it != INVALID; ++it) {
674 nodeRefMap[it] = target.addNode();
676 for (typename Source::EdgeIt it(source); it != INVALID; ++it) {
677 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
678 nodeRefMap[source.target(it)]);
683 template <typename Graph>
684 struct GraphCopySelector<
686 typename enable_if<typename Graph::BuildTag, void>::type>
688 template <typename Source, typename NodeRefMap, typename EdgeRefMap>
689 static void copy(Graph &target, const Source& source,
690 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
691 target.build(source, nodeRefMap, edgeRefMap);
695 template <typename UGraph, typename Enable = void>
696 struct UGraphCopySelector {
697 template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
698 static void copy(UGraph &target, const Source& source,
699 NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
700 for (typename Source::NodeIt it(source); it != INVALID; ++it) {
701 nodeRefMap[it] = target.addNode();
703 for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
704 uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
705 nodeRefMap[source.target(it)]);
710 template <typename UGraph>
711 struct UGraphCopySelector<
713 typename enable_if<typename UGraph::BuildTag, void>::type>
715 template <typename Source, typename NodeRefMap, typename UEdgeRefMap>
716 static void copy(UGraph &target, const Source& source,
717 NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
718 target.build(source, nodeRefMap, uEdgeRefMap);
722 template <typename BpUGraph, typename Enable = void>
723 struct BpUGraphCopySelector {
724 template <typename Source, typename ANodeRefMap,
725 typename BNodeRefMap, typename UEdgeRefMap>
726 static void copy(BpUGraph &target, const Source& source,
727 ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
728 UEdgeRefMap& uEdgeRefMap) {
729 for (typename Source::ANodeIt it(source); it != INVALID; ++it) {
730 aNodeRefMap[it] = target.addANode();
732 for (typename Source::BNodeIt it(source); it != INVALID; ++it) {
733 bNodeRefMap[it] = target.addBNode();
735 for (typename Source::UEdgeIt it(source); it != INVALID; ++it) {
736 uEdgeRefMap[it] = target.addEdge(aNodeRefMap[source.aNode(it)],
737 bNodeRefMap[source.bNode(it)]);
742 template <typename BpUGraph>
743 struct BpUGraphCopySelector<
745 typename enable_if<typename BpUGraph::BuildTag, void>::type>
747 template <typename Source, typename ANodeRefMap,
748 typename BNodeRefMap, typename UEdgeRefMap>
749 static void copy(BpUGraph &target, const Source& source,
750 ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
751 UEdgeRefMap& uEdgeRefMap) {
752 target.build(source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
759 /// \brief Class to copy a graph.
761 /// Class to copy a graph to another graph (duplicate a graph). The
762 /// simplest way of using it is through the \c copyGraph() function.
763 template <typename Target, typename Source>
767 typedef typename Source::Node Node;
768 typedef typename Source::NodeIt NodeIt;
769 typedef typename Source::Edge Edge;
770 typedef typename Source::EdgeIt EdgeIt;
772 typedef typename Target::Node TNode;
773 typedef typename Target::Edge TEdge;
775 typedef typename Source::template NodeMap<TNode> NodeRefMap;
776 typedef typename Source::template EdgeMap<TEdge> EdgeRefMap;
782 /// \brief Constructor for the GraphCopy.
784 /// It copies the content of the \c _source graph into the
785 /// \c _target graph.
786 GraphCopy(Target& _target, const Source& _source)
787 : source(_source), target(_target) {}
789 /// \brief Destructor of the GraphCopy
791 /// Destructor of the GraphCopy
793 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
794 delete nodeMapCopies[i];
796 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
797 delete edgeMapCopies[i];
802 /// \brief Copies the node references into the given map.
804 /// Copies the node references into the given map.
805 template <typename NodeRef>
806 GraphCopy& nodeRef(NodeRef& map) {
807 nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
808 NodeRefMap, NodeRef>(map));
812 /// \brief Copies the node cross references into the given map.
814 /// Copies the node cross references (reverse references) into
816 template <typename NodeCrossRef>
817 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
818 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
819 NodeRefMap, NodeCrossRef>(map));
823 /// \brief Make copy of the given map.
825 /// Makes copy of the given map for the newly created graph.
826 /// The new map's key type is the target graph's node type,
827 /// and the copied map's key type is the source graph's node
829 template <typename TargetMap, typename SourceMap>
830 GraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
831 nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
832 NodeRefMap, TargetMap, SourceMap>(tmap, map));
836 /// \brief Make a copy of the given node.
838 /// Make a copy of the given node.
839 GraphCopy& node(TNode& tnode, const Node& snode) {
840 nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
841 NodeRefMap, TNode>(tnode, snode));
845 /// \brief Copies the edge references into the given map.
847 /// Copies the edge references into the given map.
848 template <typename EdgeRef>
849 GraphCopy& edgeRef(EdgeRef& map) {
850 edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
851 EdgeRefMap, EdgeRef>(map));
855 /// \brief Copies the edge cross references into the given map.
857 /// Copies the edge cross references (reverse references) into
859 template <typename EdgeCrossRef>
860 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
861 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
862 EdgeRefMap, EdgeCrossRef>(map));
866 /// \brief Make copy of the given map.
868 /// Makes copy of the given map for the newly created graph.
869 /// The new map's key type is the target graph's edge type,
870 /// and the copied map's key type is the source graph's edge
872 template <typename TargetMap, typename SourceMap>
873 GraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
874 edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
875 EdgeRefMap, TargetMap, SourceMap>(tmap, map));
879 /// \brief Make a copy of the given edge.
881 /// Make a copy of the given edge.
882 GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
883 edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
884 EdgeRefMap, TEdge>(tedge, sedge));
888 /// \brief Executes the copies.
890 /// Executes the copies.
892 NodeRefMap nodeRefMap(source);
893 EdgeRefMap edgeRefMap(source);
894 _graph_utils_bits::GraphCopySelector<Target>::
895 copy(target, source, nodeRefMap, edgeRefMap);
896 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
897 nodeMapCopies[i]->copy(source, nodeRefMap);
899 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
900 edgeMapCopies[i]->copy(source, edgeRefMap);
907 const Source& source;
910 std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
913 std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
918 /// \brief Copy a graph to another graph.
920 /// Copy a graph to another graph.
921 /// The usage of the function:
924 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
927 /// After the copy the \c nr map will contain the mapping from the
928 /// source graph's nodes to the target graph's nodes and the \c ecr will
929 /// contain the mapping from the target graph's edges to the source's
933 template <typename Target, typename Source>
934 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
935 return GraphCopy<Target, Source>(target, source);
938 /// \brief Class to copy an undirected graph.
940 /// Class to copy an undirected graph to another graph (duplicate a graph).
941 /// The simplest way of using it is through the \c copyUGraph() function.
942 template <typename Target, typename Source>
946 typedef typename Source::Node Node;
947 typedef typename Source::NodeIt NodeIt;
948 typedef typename Source::Edge Edge;
949 typedef typename Source::EdgeIt EdgeIt;
950 typedef typename Source::UEdge UEdge;
951 typedef typename Source::UEdgeIt UEdgeIt;
953 typedef typename Target::Node TNode;
954 typedef typename Target::Edge TEdge;
955 typedef typename Target::UEdge TUEdge;
957 typedef typename Source::template NodeMap<TNode> NodeRefMap;
958 typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
961 EdgeRefMap(const Target& _target, const Source& _source,
962 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
963 : target(_target), source(_source),
964 uedge_ref(_uedge_ref), node_ref(_node_ref) {}
966 typedef typename Source::Edge Key;
967 typedef typename Target::Edge Value;
969 Value operator[](const Key& key) const {
971 (source.direction(key) ==
972 (node_ref[source.source(static_cast<const UEdge&>(key))] ==
973 target.source(uedge_ref[static_cast<const UEdge&>(key)])));
974 return target.direct(uedge_ref[key], forward);
977 const Target& target;
978 const Source& source;
979 const UEdgeRefMap& uedge_ref;
980 const NodeRefMap& node_ref;
987 /// \brief Constructor for the GraphCopy.
989 /// It copies the content of the \c _source graph into the
990 /// \c _target graph.
991 UGraphCopy(Target& _target, const Source& _source)
992 : source(_source), target(_target) {}
994 /// \brief Destructor of the GraphCopy
996 /// Destructor of the GraphCopy
998 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
999 delete nodeMapCopies[i];
1001 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1002 delete edgeMapCopies[i];
1004 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1005 delete uEdgeMapCopies[i];
1010 /// \brief Copies the node references into the given map.
1012 /// Copies the node references into the given map.
1013 template <typename NodeRef>
1014 UGraphCopy& nodeRef(NodeRef& map) {
1015 nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
1016 NodeRefMap, NodeRef>(map));
1020 /// \brief Copies the node cross references into the given map.
1022 /// Copies the node cross references (reverse references) into
1024 template <typename NodeCrossRef>
1025 UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1026 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1027 NodeRefMap, NodeCrossRef>(map));
1031 /// \brief Make copy of the given map.
1033 /// Makes copy of the given map for the newly created graph.
1034 /// The new map's key type is the target graph's node type,
1035 /// and the copied map's key type is the source graph's node
1037 template <typename TargetMap, typename SourceMap>
1038 UGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
1039 nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
1040 NodeRefMap, TargetMap, SourceMap>(tmap, map));
1044 /// \brief Make a copy of the given node.
1046 /// Make a copy of the given node.
1047 UGraphCopy& node(TNode& tnode, const Node& snode) {
1048 nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
1049 NodeRefMap, TNode>(tnode, snode));
1053 /// \brief Copies the edge references into the given map.
1055 /// Copies the edge references into the given map.
1056 template <typename EdgeRef>
1057 UGraphCopy& edgeRef(EdgeRef& map) {
1058 edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
1059 EdgeRefMap, EdgeRef>(map));
1063 /// \brief Copies the edge cross references into the given map.
1065 /// Copies the edge cross references (reverse references) into
1067 template <typename EdgeCrossRef>
1068 UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1069 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1070 EdgeRefMap, EdgeCrossRef>(map));
1074 /// \brief Make copy of the given map.
1076 /// Makes copy of the given map for the newly created graph.
1077 /// The new map's key type is the target graph's edge type,
1078 /// and the copied map's key type is the source graph's edge
1080 template <typename TargetMap, typename SourceMap>
1081 UGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
1082 edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
1083 EdgeRefMap, TargetMap, SourceMap>(tmap, map));
1087 /// \brief Make a copy of the given edge.
1089 /// Make a copy of the given edge.
1090 UGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1091 edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
1092 EdgeRefMap, TEdge>(tedge, sedge));
1096 /// \brief Copies the undirected edge references into the given map.
1098 /// Copies the undirected edge references into the given map.
1099 template <typename UEdgeRef>
1100 UGraphCopy& uEdgeRef(UEdgeRef& map) {
1101 uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
1102 UEdgeRefMap, UEdgeRef>(map));
1106 /// \brief Copies the undirected edge cross references into the given map.
1108 /// Copies the undirected edge cross references (reverse
1109 /// references) into the given map.
1110 template <typename UEdgeCrossRef>
1111 UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1112 uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1113 UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
1117 /// \brief Make copy of the given map.
1119 /// Makes copy of the given map for the newly created graph.
1120 /// The new map's key type is the target graph's undirected edge type,
1121 /// and the copied map's key type is the source graph's undirected edge
1123 template <typename TargetMap, typename SourceMap>
1124 UGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
1125 uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge,
1126 UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
1130 /// \brief Make a copy of the given undirected edge.
1132 /// Make a copy of the given undirected edge.
1133 UGraphCopy& uEdge(TUEdge& tuedge, const UEdge& suedge) {
1134 uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge,
1135 UEdgeRefMap, TUEdge>(tuedge, suedge));
1139 /// \brief Executes the copies.
1141 /// Executes the copies.
1143 NodeRefMap nodeRefMap(source);
1144 UEdgeRefMap uEdgeRefMap(source);
1145 EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
1146 _graph_utils_bits::UGraphCopySelector<Target>::
1147 copy(target, source, nodeRefMap, uEdgeRefMap);
1148 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1149 nodeMapCopies[i]->copy(source, nodeRefMap);
1151 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1152 uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
1154 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1155 edgeMapCopies[i]->copy(source, edgeRefMap);
1161 const Source& source;
1164 std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
1167 std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
1170 std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* >
1175 /// \brief Copy an undirected graph to another graph.
1177 /// Copy an undirected graph to another graph.
1178 /// The usage of the function:
1181 /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
1184 /// After the copy the \c nr map will contain the mapping from the
1185 /// source graph's nodes to the target graph's nodes and the \c ecr will
1186 /// contain the mapping from the target graph's edges to the source's
1190 template <typename Target, typename Source>
1191 UGraphCopy<Target, Source>
1192 copyUGraph(Target& target, const Source& source) {
1193 return UGraphCopy<Target, Source>(target, source);
1196 /// \brief Class to copy a bipartite undirected graph.
1198 /// Class to copy a bipartite undirected graph to another graph
1199 /// (duplicate a graph). The simplest way of using it is through
1200 /// the \c copyBpUGraph() function.
1201 template <typename Target, typename Source>
1202 class BpUGraphCopy {
1205 typedef typename Source::Node Node;
1206 typedef typename Source::ANode ANode;
1207 typedef typename Source::BNode BNode;
1208 typedef typename Source::NodeIt NodeIt;
1209 typedef typename Source::Edge Edge;
1210 typedef typename Source::EdgeIt EdgeIt;
1211 typedef typename Source::UEdge UEdge;
1212 typedef typename Source::UEdgeIt UEdgeIt;
1214 typedef typename Target::Node TNode;
1215 typedef typename Target::Edge TEdge;
1216 typedef typename Target::UEdge TUEdge;
1218 typedef typename Source::template ANodeMap<TNode> ANodeRefMap;
1219 typedef typename Source::template BNodeMap<TNode> BNodeRefMap;
1220 typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
1223 NodeRefMap(const Source& _source, const ANodeRefMap& _anode_ref,
1224 const BNodeRefMap& _bnode_ref)
1225 : source(_source), anode_ref(_anode_ref), bnode_ref(_bnode_ref) {}
1227 typedef typename Source::Node Key;
1228 typedef typename Target::Node Value;
1230 Value operator[](const Key& key) const {
1231 return source.aNode(key) ? anode_ref[key] : bnode_ref[key];
1234 const Source& source;
1235 const ANodeRefMap& anode_ref;
1236 const BNodeRefMap& bnode_ref;
1240 EdgeRefMap(const Target& _target, const Source& _source,
1241 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
1242 : target(_target), source(_source),
1243 uedge_ref(_uedge_ref), node_ref(_node_ref) {}
1245 typedef typename Source::Edge Key;
1246 typedef typename Target::Edge Value;
1248 Value operator[](const Key& key) const {
1250 (source.direction(key) ==
1251 (node_ref[source.source(static_cast<const UEdge&>(key))] ==
1252 target.source(uedge_ref[static_cast<const UEdge&>(key)])));
1253 return target.direct(uedge_ref[key], forward);
1256 const Target& target;
1257 const Source& source;
1258 const UEdgeRefMap& uedge_ref;
1259 const NodeRefMap& node_ref;
1265 /// \brief Constructor for the GraphCopy.
1267 /// It copies the content of the \c _source graph into the
1268 /// \c _target graph.
1269 BpUGraphCopy(Target& _target, const Source& _source)
1270 : source(_source), target(_target) {}
1272 /// \brief Destructor of the GraphCopy
1274 /// Destructor of the GraphCopy
1276 for (int i = 0; i < int(aNodeMapCopies.size()); ++i) {
1277 delete aNodeMapCopies[i];
1279 for (int i = 0; i < int(bNodeMapCopies.size()); ++i) {
1280 delete bNodeMapCopies[i];
1282 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1283 delete nodeMapCopies[i];
1285 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1286 delete edgeMapCopies[i];
1288 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1289 delete uEdgeMapCopies[i];
1294 /// \brief Copies the A-node references into the given map.
1296 /// Copies the A-node references into the given map.
1297 template <typename ANodeRef>
1298 BpUGraphCopy& aNodeRef(ANodeRef& map) {
1299 aNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, ANode,
1300 ANodeRefMap, ANodeRef>(map));
1304 /// \brief Copies the A-node cross references into the given map.
1306 /// Copies the A-node cross references (reverse references) into
1308 template <typename ANodeCrossRef>
1309 BpUGraphCopy& aNodeCrossRef(ANodeCrossRef& map) {
1310 aNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1311 ANode, ANodeRefMap, ANodeCrossRef>(map));
1315 /// \brief Make copy of the given A-node map.
1317 /// Makes copy of the given map for the newly created graph.
1318 /// The new map's key type is the target graph's node type,
1319 /// and the copied map's key type is the source graph's node
1321 template <typename TargetMap, typename SourceMap>
1322 BpUGraphCopy& aNodeMap(TargetMap& tmap, const SourceMap& map) {
1323 aNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, ANode,
1324 ANodeRefMap, TargetMap, SourceMap>(tmap, map));
1328 /// \brief Copies the B-node references into the given map.
1330 /// Copies the B-node references into the given map.
1331 template <typename BNodeRef>
1332 BpUGraphCopy& bNodeRef(BNodeRef& map) {
1333 bNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, BNode,
1334 BNodeRefMap, BNodeRef>(map));
1338 /// \brief Copies the B-node cross references into the given map.
1340 /// Copies the B-node cross references (reverse references) into
1342 template <typename BNodeCrossRef>
1343 BpUGraphCopy& bNodeCrossRef(BNodeCrossRef& map) {
1344 bNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1345 BNode, BNodeRefMap, BNodeCrossRef>(map));
1349 /// \brief Make copy of the given B-node map.
1351 /// Makes copy of the given map for the newly created graph.
1352 /// The new map's key type is the target graph's node type,
1353 /// and the copied map's key type is the source graph's node
1355 template <typename TargetMap, typename SourceMap>
1356 BpUGraphCopy& bNodeMap(TargetMap& tmap, const SourceMap& map) {
1357 bNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, BNode,
1358 BNodeRefMap, TargetMap, SourceMap>(tmap, map));
1361 /// \brief Copies the node references into the given map.
1363 /// Copies the node references into the given map.
1364 template <typename NodeRef>
1365 BpUGraphCopy& nodeRef(NodeRef& map) {
1366 nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
1367 NodeRefMap, NodeRef>(map));
1371 /// \brief Copies the node cross references into the given map.
1373 /// Copies the node cross references (reverse references) into
1375 template <typename NodeCrossRef>
1376 BpUGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1377 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1378 NodeRefMap, NodeCrossRef>(map));
1382 /// \brief Make copy of the given map.
1384 /// Makes copy of the given map for the newly created graph.
1385 /// The new map's key type is the target graph's node type,
1386 /// and the copied map's key type is the source graph's node
1388 template <typename TargetMap, typename SourceMap>
1389 BpUGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
1390 nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
1391 NodeRefMap, TargetMap, SourceMap>(tmap, map));
1395 /// \brief Make a copy of the given node.
1397 /// Make a copy of the given node.
1398 BpUGraphCopy& node(TNode& tnode, const Node& snode) {
1399 nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Node,
1400 NodeRefMap, TNode>(tnode, snode));
1404 /// \brief Copies the edge references into the given map.
1406 /// Copies the edge references into the given map.
1407 template <typename EdgeRef>
1408 BpUGraphCopy& edgeRef(EdgeRef& map) {
1409 edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
1410 EdgeRefMap, EdgeRef>(map));
1414 /// \brief Copies the edge cross references into the given map.
1416 /// Copies the edge cross references (reverse references) into
1418 template <typename EdgeCrossRef>
1419 BpUGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1420 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1421 EdgeRefMap, EdgeCrossRef>(map));
1425 /// \brief Make copy of the given map.
1427 /// Makes copy of the given map for the newly created graph.
1428 /// The new map's key type is the target graph's edge type,
1429 /// and the copied map's key type is the source graph's edge
1431 template <typename TargetMap, typename SourceMap>
1432 BpUGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
1433 edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
1434 EdgeRefMap, TargetMap, SourceMap>(tmap, map));
1438 /// \brief Make a copy of the given edge.
1440 /// Make a copy of the given edge.
1441 BpUGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1442 edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, Edge,
1443 EdgeRefMap, TEdge>(tedge, sedge));
1447 /// \brief Copies the undirected edge references into the given map.
1449 /// Copies the undirected edge references into the given map.
1450 template <typename UEdgeRef>
1451 BpUGraphCopy& uEdgeRef(UEdgeRef& map) {
1452 uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
1453 UEdgeRefMap, UEdgeRef>(map));
1457 /// \brief Copies the undirected edge cross references into the given map.
1459 /// Copies the undirected edge cross references (reverse
1460 /// references) into the given map.
1461 template <typename UEdgeCrossRef>
1462 BpUGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1463 uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1464 UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
1468 /// \brief Make copy of the given map.
1470 /// Makes copy of the given map for the newly created graph.
1471 /// The new map's key type is the target graph's undirected edge type,
1472 /// and the copied map's key type is the source graph's undirected edge
1474 template <typename TargetMap, typename SourceMap>
1475 BpUGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
1476 uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge,
1477 UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
1481 /// \brief Make a copy of the given undirected edge.
1483 /// Make a copy of the given undirected edge.
1484 BpUGraphCopy& uEdge(TUEdge& tuedge, const UEdge& suedge) {
1485 uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<Source, UEdge,
1486 UEdgeRefMap, TUEdge>(tuedge, suedge));
1490 /// \brief Executes the copies.
1492 /// Executes the copies.
1494 ANodeRefMap aNodeRefMap(source);
1495 BNodeRefMap bNodeRefMap(source);
1496 NodeRefMap nodeRefMap(source, aNodeRefMap, bNodeRefMap);
1497 UEdgeRefMap uEdgeRefMap(source);
1498 EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
1499 _graph_utils_bits::BpUGraphCopySelector<Target>::
1500 copy(target, source, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
1501 for (int i = 0; i < int(aNodeMapCopies.size()); ++i) {
1502 aNodeMapCopies[i]->copy(source, aNodeRefMap);
1504 for (int i = 0; i < int(bNodeMapCopies.size()); ++i) {
1505 bNodeMapCopies[i]->copy(source, bNodeRefMap);
1507 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1508 nodeMapCopies[i]->copy(source, nodeRefMap);
1510 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1511 uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
1513 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1514 edgeMapCopies[i]->copy(source, edgeRefMap);
1520 const Source& source;
1523 std::vector<_graph_utils_bits::MapCopyBase<Source, ANode, ANodeRefMap>* >
1526 std::vector<_graph_utils_bits::MapCopyBase<Source, BNode, BNodeRefMap>* >
1529 std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
1532 std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
1535 std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* >
1540 /// \brief Copy a bipartite undirected graph to another graph.
1542 /// Copy a bipartite undirected graph to another graph.
1543 /// The usage of the function:
1546 /// copyBpUGraph(trg, src).aNodeRef(anr).edgeCrossRef(ecr).run();
1549 /// After the copy the \c nr map will contain the mapping from the
1550 /// source graph's nodes to the target graph's nodes and the \c ecr will
1551 /// contain the mapping from the target graph's edges to the source's
1554 /// \see BpUGraphCopy
1555 template <typename Target, typename Source>
1556 BpUGraphCopy<Target, Source>
1557 copyBpUGraph(Target& target, const Source& source) {
1558 return BpUGraphCopy<Target, Source>(target, source);
1564 /// \addtogroup graph_maps
1567 /// Provides an immutable and unique id for each item in the graph.
1569 /// The IdMap class provides a unique and immutable id for each item of the
1570 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1571 /// different items (nodes) get different ids <li>\b immutable: the id of an
1572 /// item (node) does not change (even if you delete other nodes). </ul>
1573 /// Through this map you get access (i.e. can read) the inner id values of
1574 /// the items stored in the graph. This map can be inverted with its member
1575 /// class \c InverseMap.
1577 template <typename _Graph, typename _Item>
1580 typedef _Graph Graph;
1585 /// \brief Constructor.
1587 /// Constructor of the map.
1588 explicit IdMap(const Graph& _graph) : graph(&_graph) {}
1590 /// \brief Gives back the \e id of the item.
1592 /// Gives back the immutable and unique \e id of the item.
1593 int operator[](const Item& item) const { return graph->id(item);}
1595 /// \brief Gives back the item by its id.
1597 /// Gives back the item by its id.
1598 Item operator()(int id) { return graph->fromId(id, Item()); }
1605 /// \brief The class represents the inverse of its owner (IdMap).
1607 /// The class represents the inverse of its owner (IdMap).
1612 /// \brief Constructor.
1614 /// Constructor for creating an id-to-item map.
1615 explicit InverseMap(const Graph& _graph) : graph(&_graph) {}
1617 /// \brief Constructor.
1619 /// Constructor for creating an id-to-item map.
1620 explicit InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1622 /// \brief Gives back the given item from its id.
1624 /// Gives back the given item from its id.
1626 Item operator[](int id) const { return graph->fromId(id, Item());}
1632 /// \brief Gives back the inverse of the map.
1634 /// Gives back the inverse of the IdMap.
1635 InverseMap inverse() const { return InverseMap(*graph);}
1640 /// \brief General invertable graph-map type.
1642 /// This type provides simple invertable graph-maps.
1643 /// The InvertableMap wraps an arbitrary ReadWriteMap
1644 /// and if a key is set to a new value then store it
1645 /// in the inverse map.
1647 /// The values of the map can be accessed
1648 /// with stl compatible forward iterator.
1650 /// \param _Graph The graph type.
1651 /// \param _Item The item type of the graph.
1652 /// \param _Value The value type of the map.
1654 /// \see IterableValueMap
1655 template <typename _Graph, typename _Item, typename _Value>
1656 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1659 typedef DefaultMap<_Graph, _Item, _Value> Map;
1660 typedef _Graph Graph;
1662 typedef std::map<_Value, _Item> Container;
1667 /// The key type of InvertableMap (Node, Edge, UEdge).
1668 typedef typename Map::Key Key;
1669 /// The value type of the InvertableMap.
1670 typedef typename Map::Value Value;
1674 /// \brief Constructor.
1676 /// Construct a new InvertableMap for the graph.
1678 explicit InvertableMap(const Graph& graph) : Map(graph) {}
1680 /// \brief Forward iterator for values.
1682 /// This iterator is an stl compatible forward
1683 /// iterator on the values of the map. The values can
1684 /// be accessed in the [beginValue, endValue) range.
1687 : public std::iterator<std::forward_iterator_tag, Value> {
1688 friend class InvertableMap;
1690 ValueIterator(typename Container::const_iterator _it)
1696 ValueIterator& operator++() { ++it; return *this; }
1697 ValueIterator operator++(int) {
1698 ValueIterator tmp(*this);
1703 const Value& operator*() const { return it->first; }
1704 const Value* operator->() const { return &(it->first); }
1706 bool operator==(ValueIterator jt) const { return it == jt.it; }
1707 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1710 typename Container::const_iterator it;
1713 /// \brief Returns an iterator to the first value.
1715 /// Returns an stl compatible iterator to the
1716 /// first value of the map. The values of the
1717 /// map can be accessed in the [beginValue, endValue)
1719 ValueIterator beginValue() const {
1720 return ValueIterator(invMap.begin());
1723 /// \brief Returns an iterator after the last value.
1725 /// Returns an stl compatible iterator after the
1726 /// last value of the map. The values of the
1727 /// map can be accessed in the [beginValue, endValue)
1729 ValueIterator endValue() const {
1730 return ValueIterator(invMap.end());
1733 /// \brief The setter function of the map.
1735 /// Sets the mapped value.
1736 void set(const Key& key, const Value& val) {
1737 Value oldval = Map::operator[](key);
1738 typename Container::iterator it = invMap.find(oldval);
1739 if (it != invMap.end() && it->second == key) {
1742 invMap.insert(make_pair(val, key));
1746 /// \brief The getter function of the map.
1748 /// It gives back the value associated with the key.
1749 typename MapTraits<Map>::ConstReturnValue
1750 operator[](const Key& key) const {
1751 return Map::operator[](key);
1754 /// \brief Gives back the item by its value.
1756 /// Gives back the item by its value.
1757 Key operator()(const Value& key) const {
1758 typename Container::const_iterator it = invMap.find(key);
1759 return it != invMap.end() ? it->second : INVALID;
1764 /// \brief Erase the key from the map.
1766 /// Erase the key to the map. It is called by the
1767 /// \c AlterationNotifier.
1768 virtual void erase(const Key& key) {
1769 Value val = Map::operator[](key);
1770 typename Container::iterator it = invMap.find(val);
1771 if (it != invMap.end() && it->second == key) {
1777 /// \brief Erase more keys from the map.
1779 /// Erase more keys from the map. It is called by the
1780 /// \c AlterationNotifier.
1781 virtual void erase(const std::vector<Key>& keys) {
1782 for (int i = 0; i < int(keys.size()); ++i) {
1783 Value val = Map::operator[](keys[i]);
1784 typename Container::iterator it = invMap.find(val);
1785 if (it != invMap.end() && it->second == keys[i]) {
1792 /// \brief Clear the keys from the map and inverse map.
1794 /// Clear the keys from the map and inverse map. It is called by the
1795 /// \c AlterationNotifier.
1796 virtual void clear() {
1803 /// \brief The inverse map type.
1805 /// The inverse of this map. The subscript operator of the map
1806 /// gives back always the item what was last assigned to the value.
1809 /// \brief Constructor of the InverseMap.
1811 /// Constructor of the InverseMap.
1812 explicit InverseMap(const InvertableMap& _inverted)
1813 : inverted(_inverted) {}
1815 /// The value type of the InverseMap.
1816 typedef typename InvertableMap::Key Value;
1817 /// The key type of the InverseMap.
1818 typedef typename InvertableMap::Value Key;
1820 /// \brief Subscript operator.
1822 /// Subscript operator. It gives back always the item
1823 /// what was last assigned to the value.
1824 Value operator[](const Key& key) const {
1825 return inverted(key);
1829 const InvertableMap& inverted;
1832 /// \brief It gives back the just readable inverse map.
1834 /// It gives back the just readable inverse map.
1835 InverseMap inverse() const {
1836 return InverseMap(*this);
1843 /// \brief Provides a mutable, continuous and unique descriptor for each
1844 /// item in the graph.
1846 /// The DescriptorMap class provides a unique and continuous (but mutable)
1847 /// descriptor (id) for each item of the same type (e.g. node) in the
1848 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1849 /// different ids <li>\b continuous: the range of the ids is the set of
1850 /// integers between 0 and \c n-1, where \c n is the number of the items of
1851 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1852 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1853 /// with its member class \c InverseMap.
1855 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1856 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1858 template <typename _Graph, typename _Item>
1859 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1862 typedef DefaultMap<_Graph, _Item, int> Map;
1865 /// The graph class of DescriptorMap.
1866 typedef _Graph Graph;
1868 /// The key type of DescriptorMap (Node, Edge, UEdge).
1869 typedef typename Map::Key Key;
1870 /// The value type of DescriptorMap.
1871 typedef typename Map::Value Value;
1873 /// \brief Constructor.
1875 /// Constructor for descriptor map.
1876 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1878 const typename Map::Notifier* nf = Map::notifier();
1879 for (nf->first(it); it != INVALID; nf->next(it)) {
1880 Map::set(it, invMap.size());
1881 invMap.push_back(it);
1887 /// \brief Add a new key to the map.
1889 /// Add a new key to the map. It is called by the
1890 /// \c AlterationNotifier.
1891 virtual void add(const Item& item) {
1893 Map::set(item, invMap.size());
1894 invMap.push_back(item);
1897 /// \brief Add more new keys to the map.
1899 /// Add more new keys to the map. It is called by the
1900 /// \c AlterationNotifier.
1901 virtual void add(const std::vector<Item>& items) {
1903 for (int i = 0; i < int(items.size()); ++i) {
1904 Map::set(items[i], invMap.size());
1905 invMap.push_back(items[i]);
1909 /// \brief Erase the key from the map.
1911 /// Erase the key from the map. It is called by the
1912 /// \c AlterationNotifier.
1913 virtual void erase(const Item& item) {
1914 Map::set(invMap.back(), Map::operator[](item));
1915 invMap[Map::operator[](item)] = invMap.back();
1920 /// \brief Erase more keys from the map.
1922 /// Erase more keys from the map. It is called by the
1923 /// \c AlterationNotifier.
1924 virtual void erase(const std::vector<Item>& items) {
1925 for (int i = 0; i < int(items.size()); ++i) {
1926 Map::set(invMap.back(), Map::operator[](items[i]));
1927 invMap[Map::operator[](items[i])] = invMap.back();
1933 /// \brief Build the unique map.
1935 /// Build the unique map. It is called by the
1936 /// \c AlterationNotifier.
1937 virtual void build() {
1940 const typename Map::Notifier* nf = Map::notifier();
1941 for (nf->first(it); it != INVALID; nf->next(it)) {
1942 Map::set(it, invMap.size());
1943 invMap.push_back(it);
1947 /// \brief Clear the keys from the map.
1949 /// Clear the keys from the map. It is called by the
1950 /// \c AlterationNotifier.
1951 virtual void clear() {
1958 /// \brief Returns the maximal value plus one.
1960 /// Returns the maximal value plus one in the map.
1961 unsigned int size() const {
1962 return invMap.size();
1965 /// \brief Swaps the position of the two items in the map.
1967 /// Swaps the position of the two items in the map.
1968 void swap(const Item& p, const Item& q) {
1969 int pi = Map::operator[](p);
1970 int qi = Map::operator[](q);
1977 /// \brief Gives back the \e descriptor of the item.
1979 /// Gives back the mutable and unique \e descriptor of the map.
1980 int operator[](const Item& item) const {
1981 return Map::operator[](item);
1984 /// \brief Gives back the item by its descriptor.
1986 /// Gives back th item by its descriptor.
1987 Item operator()(int id) const {
1993 typedef std::vector<Item> Container;
1997 /// \brief The inverse map type of DescriptorMap.
1999 /// The inverse map type of DescriptorMap.
2002 /// \brief Constructor of the InverseMap.
2004 /// Constructor of the InverseMap.
2005 explicit InverseMap(const DescriptorMap& _inverted)
2006 : inverted(_inverted) {}
2009 /// The value type of the InverseMap.
2010 typedef typename DescriptorMap::Key Value;
2011 /// The key type of the InverseMap.
2012 typedef typename DescriptorMap::Value Key;
2014 /// \brief Subscript operator.
2016 /// Subscript operator. It gives back the item
2017 /// that the descriptor belongs to currently.
2018 Value operator[](const Key& key) const {
2019 return inverted(key);
2022 /// \brief Size of the map.
2024 /// Returns the size of the map.
2025 unsigned int size() const {
2026 return inverted.size();
2030 const DescriptorMap& inverted;
2033 /// \brief Gives back the inverse of the map.
2035 /// Gives back the inverse of the map.
2036 const InverseMap inverse() const {
2037 return InverseMap(*this);
2041 /// \brief Returns the source of the given edge.
2043 /// The SourceMap gives back the source Node of the given edge.
2044 /// \author Balazs Dezso
2045 template <typename Graph>
2049 typedef typename Graph::Node Value;
2050 typedef typename Graph::Edge Key;
2052 /// \brief Constructor
2055 /// \param _graph The graph that the map belongs to.
2056 explicit SourceMap(const Graph& _graph) : graph(_graph) {}
2058 /// \brief The subscript operator.
2060 /// The subscript operator.
2061 /// \param edge The edge
2062 /// \return The source of the edge
2063 Value operator[](const Key& edge) const {
2064 return graph.source(edge);
2071 /// \brief Returns a \ref SourceMap class
2073 /// This function just returns an \ref SourceMap class.
2074 /// \relates SourceMap
2075 template <typename Graph>
2076 inline SourceMap<Graph> sourceMap(const Graph& graph) {
2077 return SourceMap<Graph>(graph);
2080 /// \brief Returns the target of the given edge.
2082 /// The TargetMap gives back the target Node of the given edge.
2083 /// \author Balazs Dezso
2084 template <typename Graph>
2088 typedef typename Graph::Node Value;
2089 typedef typename Graph::Edge Key;
2091 /// \brief Constructor
2094 /// \param _graph The graph that the map belongs to.
2095 explicit TargetMap(const Graph& _graph) : graph(_graph) {}
2097 /// \brief The subscript operator.
2099 /// The subscript operator.
2100 /// \param e The edge
2101 /// \return The target of the edge
2102 Value operator[](const Key& e) const {
2103 return graph.target(e);
2110 /// \brief Returns a \ref TargetMap class
2112 /// This function just returns a \ref TargetMap class.
2113 /// \relates TargetMap
2114 template <typename Graph>
2115 inline TargetMap<Graph> targetMap(const Graph& graph) {
2116 return TargetMap<Graph>(graph);
2119 /// \brief Returns the "forward" directed edge view of an undirected edge.
2121 /// Returns the "forward" directed edge view of an undirected edge.
2122 /// \author Balazs Dezso
2123 template <typename Graph>
2127 typedef typename Graph::Edge Value;
2128 typedef typename Graph::UEdge Key;
2130 /// \brief Constructor
2133 /// \param _graph The graph that the map belongs to.
2134 explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
2136 /// \brief The subscript operator.
2138 /// The subscript operator.
2139 /// \param key An undirected edge
2140 /// \return The "forward" directed edge view of undirected edge
2141 Value operator[](const Key& key) const {
2142 return graph.direct(key, true);
2149 /// \brief Returns a \ref ForwardMap class
2151 /// This function just returns an \ref ForwardMap class.
2152 /// \relates ForwardMap
2153 template <typename Graph>
2154 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2155 return ForwardMap<Graph>(graph);
2158 /// \brief Returns the "backward" directed edge view of an undirected edge.
2160 /// Returns the "backward" directed edge view of an undirected edge.
2161 /// \author Balazs Dezso
2162 template <typename Graph>
2166 typedef typename Graph::Edge Value;
2167 typedef typename Graph::UEdge Key;
2169 /// \brief Constructor
2172 /// \param _graph The graph that the map belongs to.
2173 explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
2175 /// \brief The subscript operator.
2177 /// The subscript operator.
2178 /// \param key An undirected edge
2179 /// \return The "backward" directed edge view of undirected edge
2180 Value operator[](const Key& key) const {
2181 return graph.direct(key, false);
2188 /// \brief Returns a \ref BackwardMap class
2190 /// This function just returns a \ref BackwardMap class.
2191 /// \relates BackwardMap
2192 template <typename Graph>
2193 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2194 return BackwardMap<Graph>(graph);
2197 /// \brief Potential difference map
2199 /// If there is an potential map on the nodes then we
2200 /// can get an edge map as we get the substraction of the
2201 /// values of the target and source.
2202 template <typename Graph, typename NodeMap>
2203 class PotentialDifferenceMap {
2205 typedef typename Graph::Edge Key;
2206 typedef typename NodeMap::Value Value;
2208 /// \brief Constructor
2210 /// Contructor of the map
2211 explicit PotentialDifferenceMap(const Graph& _graph,
2212 const NodeMap& _potential)
2213 : graph(_graph), potential(_potential) {}
2215 /// \brief Const subscription operator
2217 /// Const subscription operator
2218 Value operator[](const Key& edge) const {
2219 return potential[graph.target(edge)] - potential[graph.source(edge)];
2224 const NodeMap& potential;
2227 /// \brief Just returns a PotentialDifferenceMap
2229 /// Just returns a PotentialDifferenceMap
2230 /// \relates PotentialDifferenceMap
2231 template <typename Graph, typename NodeMap>
2232 PotentialDifferenceMap<Graph, NodeMap>
2233 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
2234 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
2237 /// \brief Map of the node in-degrees.
2239 /// This map returns the in-degree of a node. Once it is constructed,
2240 /// the degrees are stored in a standard NodeMap, so each query is done
2241 /// in constant time. On the other hand, the values are updated automatically
2242 /// whenever the graph changes.
2244 /// \warning Besides addNode() and addEdge(), a graph structure may provide
2245 /// alternative ways to modify the graph. The correct behavior of InDegMap
2246 /// is not guarantied if these additional features are used. For example
2247 /// the functions \ref ListGraph::changeSource() "changeSource()",
2248 /// \ref ListGraph::changeTarget() "changeTarget()" and
2249 /// \ref ListGraph::reverseEdge() "reverseEdge()"
2250 /// of \ref ListGraph will \e not update the degree values correctly.
2254 template <typename _Graph>
2256 : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2257 ::ItemNotifier::ObserverBase {
2261 typedef _Graph Graph;
2263 typedef typename Graph::Node Key;
2265 typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2266 ::ItemNotifier::ObserverBase Parent;
2270 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
2273 typedef DefaultMap<_Graph, Key, int> Parent;
2274 typedef typename Parent::Graph Graph;
2276 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2278 virtual void add(const Key& key) {
2280 Parent::set(key, 0);
2283 virtual void add(const std::vector<Key>& keys) {
2285 for (int i = 0; i < int(keys.size()); ++i) {
2286 Parent::set(keys[i], 0);
2293 /// \brief Constructor.
2295 /// Constructor for creating in-degree map.
2296 explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
2297 Parent::attach(graph.notifier(typename _Graph::Edge()));
2299 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2300 deg[it] = countInEdges(graph, it);
2304 /// Gives back the in-degree of a Node.
2305 int operator[](const Key& key) const {
2311 typedef typename Graph::Edge Edge;
2313 virtual void add(const Edge& edge) {
2314 ++deg[graph.target(edge)];
2317 virtual void add(const std::vector<Edge>& edges) {
2318 for (int i = 0; i < int(edges.size()); ++i) {
2319 ++deg[graph.target(edges[i])];
2323 virtual void erase(const Edge& edge) {
2324 --deg[graph.target(edge)];
2327 virtual void erase(const std::vector<Edge>& edges) {
2328 for (int i = 0; i < int(edges.size()); ++i) {
2329 --deg[graph.target(edges[i])];
2333 virtual void build() {
2334 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2335 deg[it] = countInEdges(graph, it);
2339 virtual void clear() {
2340 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2346 const _Graph& graph;
2350 /// \brief Map of the node out-degrees.
2352 /// This map returns the out-degree of a node. Once it is constructed,
2353 /// the degrees are stored in a standard NodeMap, so each query is done
2354 /// in constant time. On the other hand, the values are updated automatically
2355 /// whenever the graph changes.
2357 /// \warning Besides addNode() and addEdge(), a graph structure may provide
2358 /// alternative ways to modify the graph. The correct behavior of OutDegMap
2359 /// is not guarantied if these additional features are used. For example
2360 /// the functions \ref ListGraph::changeSource() "changeSource()",
2361 /// \ref ListGraph::changeTarget() "changeTarget()" and
2362 /// \ref ListGraph::reverseEdge() "reverseEdge()"
2363 /// of \ref ListGraph will \e not update the degree values correctly.
2367 template <typename _Graph>
2369 : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2370 ::ItemNotifier::ObserverBase {
2374 typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2375 ::ItemNotifier::ObserverBase Parent;
2377 typedef _Graph Graph;
2379 typedef typename Graph::Node Key;
2383 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
2386 typedef DefaultMap<_Graph, Key, int> Parent;
2387 typedef typename Parent::Graph Graph;
2389 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2391 virtual void add(const Key& key) {
2393 Parent::set(key, 0);
2395 virtual void add(const std::vector<Key>& keys) {
2397 for (int i = 0; i < int(keys.size()); ++i) {
2398 Parent::set(keys[i], 0);
2405 /// \brief Constructor.
2407 /// Constructor for creating out-degree map.
2408 explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
2409 Parent::attach(graph.notifier(typename _Graph::Edge()));
2411 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2412 deg[it] = countOutEdges(graph, it);
2416 /// Gives back the out-degree of a Node.
2417 int operator[](const Key& key) const {
2423 typedef typename Graph::Edge Edge;
2425 virtual void add(const Edge& edge) {
2426 ++deg[graph.source(edge)];
2429 virtual void add(const std::vector<Edge>& edges) {
2430 for (int i = 0; i < int(edges.size()); ++i) {
2431 ++deg[graph.source(edges[i])];
2435 virtual void erase(const Edge& edge) {
2436 --deg[graph.source(edge)];
2439 virtual void erase(const std::vector<Edge>& edges) {
2440 for (int i = 0; i < int(edges.size()); ++i) {
2441 --deg[graph.source(edges[i])];
2445 virtual void build() {
2446 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2447 deg[it] = countOutEdges(graph, it);
2451 virtual void clear() {
2452 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2458 const _Graph& graph;
2463 ///Fast edge look up between given endpoints.
2466 ///Using this class, you can find an edge in a graph from a given
2467 ///source to a given target in time <em>O(log d)</em>,
2468 ///where <em>d</em> is the out-degree of the source node.
2470 ///It is not possible to find \e all parallel edges between two nodes.
2471 ///Use \ref AllEdgeLookUp for this purpose.
2473 ///\warning This class is static, so you should refresh() (or at least
2474 ///refresh(Node)) this data structure
2475 ///whenever the graph changes. This is a time consuming (superlinearly
2476 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2478 ///\param G The type of the underlying graph.
2480 ///\sa AllEdgeLookUp
2485 GRAPH_TYPEDEFS(typename G)
2490 typename Graph::template NodeMap<Edge> _head;
2491 typename Graph::template EdgeMap<Edge> _left;
2492 typename Graph::template EdgeMap<Edge> _right;
2497 EdgeLess(const Graph &_g) : g(_g) {}
2498 bool operator()(Edge a,Edge b) const
2500 return g.target(a)<g.target(b);
2510 ///It builds up the search database, which remains valid until the graph
2512 EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2515 Edge refresh_rec(std::vector<Edge> &v,int a,int b)
2519 _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
2520 _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
2524 ///Refresh the data structure at a node.
2526 ///Build up the search database of node \c n.
2528 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2529 ///the number of the outgoing edges of \c n.
2530 void refresh(Node n)
2532 std::vector<Edge> v;
2533 for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2535 std::sort(v.begin(),v.end(),EdgeLess(_g));
2536 _head[n]=refresh_rec(v,0,v.size()-1);
2538 else _head[n]=INVALID;
2540 ///Refresh the full data structure.
2542 ///Build up the full search database. In fact, it simply calls
2543 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2545 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2546 ///the number of the edges of \c n and <em>D</em> is the maximum
2547 ///out-degree of the graph.
2551 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2554 ///Find an edge between two nodes.
2556 ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2557 /// <em>d</em> is the number of outgoing edges of \c s.
2558 ///\param s The source node
2559 ///\param t The target node
2560 ///\return An edge from \c s to \c t if there exists,
2561 ///\ref INVALID otherwise.
2563 ///\warning If you change the graph, refresh() must be called before using
2564 ///this operator. If you change the outgoing edges of
2565 ///a single node \c n, then
2566 ///\ref refresh(Node) "refresh(n)" is enough.
2568 Edge operator()(Node s, Node t) const
2572 e!=INVALID&&_g.target(e)!=t;
2573 e = t < _g.target(e)?_left[e]:_right[e]) ;
2579 ///Fast look up of all edges between given endpoints.
2582 ///This class is the same as \ref EdgeLookUp, with the addition
2583 ///that it makes it possible to find all edges between given endpoints.
2585 ///\warning This class is static, so you should refresh() (or at least
2586 ///refresh(Node)) this data structure
2587 ///whenever the graph changes. This is a time consuming (superlinearly
2588 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2590 ///\param G The type of the underlying graph.
2594 class AllEdgeLookUp : public EdgeLookUp<G>
2596 using EdgeLookUp<G>::_g;
2597 using EdgeLookUp<G>::_right;
2598 using EdgeLookUp<G>::_left;
2599 using EdgeLookUp<G>::_head;
2601 GRAPH_TYPEDEFS(typename G)
2604 typename Graph::template EdgeMap<Edge> _next;
2606 Edge refreshNext(Edge head,Edge next=INVALID)
2608 if(head==INVALID) return next;
2610 next=refreshNext(_right[head],next);
2611 // _next[head]=next;
2612 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2614 return refreshNext(_left[head],head);
2620 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2628 ///It builds up the search database, which remains valid until the graph
2630 AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
2632 ///Refresh the data structure at a node.
2634 ///Build up the search database of node \c n.
2636 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2637 ///the number of the outgoing edges of \c n.
2639 void refresh(Node n)
2641 EdgeLookUp<G>::refresh(n);
2642 refreshNext(_head[n]);
2645 ///Refresh the full data structure.
2647 ///Build up the full search database. In fact, it simply calls
2648 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2650 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2651 ///the number of the edges of \c n and <em>D</em> is the maximum
2652 ///out-degree of the graph.
2656 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2659 ///Find an edge between two nodes.
2661 ///Find an edge between two nodes.
2662 ///\param s The source node
2663 ///\param t The target node
2664 ///\param prev The previous edge between \c s and \c t. It it is INVALID or
2665 ///not given, the operator finds the first appropriate edge.
2666 ///\return An edge from \c s to \c t after \c prev or
2667 ///\ref INVALID if there is no more.
2669 ///For example, you can count the number of edges from \c u to \c v in the
2672 ///AllEdgeLookUp<ListGraph> ae(g);
2675 ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2678 ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
2679 /// <em>d</em> is the number of outgoing edges of \c s. Then, the
2680 ///consecutive edges are found in constant time.
2682 ///\warning If you change the graph, refresh() must be called before using
2683 ///this operator. If you change the outgoing edges of
2684 ///a single node \c n, then
2685 ///\ref refresh(Node) "refresh(n)" is enough.
2688 Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
2690 using EdgeLookUp<G>::operator() ;
2691 Edge operator()(Node s, Node t, Edge prev) const
2693 return prev==INVALID?(*this)(s,t):_next[prev];
2701 } //END OF NAMESPACE LEMON