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.
42 /// \addtogroup gutils
45 ///Creates convenience typedefs for the graph types and iterators
47 ///This \c \#define creates convenience typedefs for the following types
48 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
50 ///\note If \c G it a template parameter, it should be used in this way.
52 /// GRAPH_TYPEDEFS(typename G);
55 ///\warning There are no typedefs for the graph maps because of the lack of
56 ///template typedefs in C++.
57 #define GRAPH_TYPEDEFS(Graph) \
58 typedef Graph:: Node Node; \
59 typedef Graph:: NodeIt NodeIt; \
60 typedef Graph:: Edge Edge; \
61 typedef Graph:: EdgeIt EdgeIt; \
62 typedef Graph:: InEdgeIt InEdgeIt; \
63 typedef Graph::OutEdgeIt OutEdgeIt
65 ///Creates convenience typedefs for the undirected graph types and iterators
67 ///This \c \#define creates the same convenience typedefs as defined by
68 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
69 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
71 ///\note If \c G it a template parameter, it should be used in this way.
73 /// UGRAPH_TYPEDEFS(typename G);
76 ///\warning There are no typedefs for the graph maps because of the lack of
77 ///template typedefs in C++.
78 #define UGRAPH_TYPEDEFS(Graph) \
79 GRAPH_TYPEDEFS(Graph); \
80 typedef Graph:: UEdge UEdge; \
81 typedef Graph:: UEdgeIt UEdgeIt; \
82 typedef Graph:: IncEdgeIt IncEdgeIt
84 ///\brief Creates convenience typedefs for the bipartite undirected graph
85 ///types and iterators
87 ///This \c \#define creates the same convenience typedefs as defined by
88 ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates
89 ///\c ANodeIt, \c BNodeIt,
91 ///\note If \c G it a template parameter, it should be used in this way.
93 /// BPUGRAPH_TYPEDEFS(typename G);
96 ///\warning There are no typedefs for the graph maps because of the lack of
97 ///template typedefs in C++.
98 #define BPUGRAPH_TYPEDEFS(Graph) \
99 UGRAPH_TYPEDEFS(Graph); \
100 typedef Graph::ANode ANode; \
101 typedef Graph::BNode BNode; \
102 typedef Graph::ANodeIt ANodeIt; \
103 typedef Graph::BNodeIt BNodeIt
105 /// \brief Function to count the items in the graph.
107 /// This function counts the items (nodes, edges etc) in the graph.
108 /// The complexity of the function is O(n) because
109 /// it iterates on all of the items.
111 template <typename Graph, typename Item>
112 inline int countItems(const Graph& g) {
113 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
115 for (ItemIt it(g); it != INVALID; ++it) {
123 namespace _graph_utils_bits {
125 template <typename Graph, typename Enable = void>
126 struct CountNodesSelector {
127 static int count(const Graph &g) {
128 return countItems<Graph, typename Graph::Node>(g);
132 template <typename Graph>
133 struct CountNodesSelector<
135 enable_if<typename Graph::NodeNumTag, void>::type>
137 static int count(const Graph &g) {
143 /// \brief Function to count the nodes in the graph.
145 /// This function counts the nodes in the graph.
146 /// The complexity of the function is O(n) but for some
147 /// graph structures it is specialized to run in O(1).
149 /// If the graph contains a \e nodeNum() member function and a
150 /// \e NodeNumTag tag then this function calls directly the member
151 /// function to query the cardinality of the node set.
152 template <typename Graph>
153 inline int countNodes(const Graph& g) {
154 return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
157 namespace _graph_utils_bits {
159 template <typename Graph, typename Enable = void>
160 struct CountANodesSelector {
161 static int count(const Graph &g) {
162 return countItems<Graph, typename Graph::ANode>(g);
166 template <typename Graph>
167 struct CountANodesSelector<
169 enable_if<typename Graph::NodeNumTag, void>::type>
171 static int count(const Graph &g) {
177 /// \brief Function to count the anodes in the graph.
179 /// This function counts the anodes in the graph.
180 /// The complexity of the function is O(an) but for some
181 /// graph structures it is specialized to run in O(1).
183 /// If the graph contains an \e aNodeNum() member function and a
184 /// \e NodeNumTag tag then this function calls directly the member
185 /// function to query the cardinality of the A-node set.
186 template <typename Graph>
187 inline int countANodes(const Graph& g) {
188 return _graph_utils_bits::CountANodesSelector<Graph>::count(g);
191 namespace _graph_utils_bits {
193 template <typename Graph, typename Enable = void>
194 struct CountBNodesSelector {
195 static int count(const Graph &g) {
196 return countItems<Graph, typename Graph::BNode>(g);
200 template <typename Graph>
201 struct CountBNodesSelector<
203 enable_if<typename Graph::NodeNumTag, void>::type>
205 static int count(const Graph &g) {
211 /// \brief Function to count the bnodes in the graph.
213 /// This function counts the bnodes in the graph.
214 /// The complexity of the function is O(bn) but for some
215 /// graph structures it is specialized to run in O(1).
217 /// If the graph contains a \e bNodeNum() member function and a
218 /// \e NodeNumTag tag then this function calls directly the member
219 /// function to query the cardinality of the B-node set.
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 /// If the graph contains a \e edgeNum() member function and a
255 /// \e EdgeNumTag tag then this function calls directly the member
256 /// function to query the cardinality of the edge set.
257 template <typename Graph>
258 inline int countEdges(const Graph& g) {
259 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
262 // Undirected edge counting:
263 namespace _graph_utils_bits {
265 template <typename Graph, typename Enable = void>
266 struct CountUEdgesSelector {
267 static int count(const Graph &g) {
268 return countItems<Graph, typename Graph::UEdge>(g);
272 template <typename Graph>
273 struct CountUEdgesSelector<
275 typename enable_if<typename Graph::EdgeNumTag, void>::type>
277 static int count(const Graph &g) {
283 /// \brief Function to count the undirected edges in the graph.
285 /// This function counts the undirected edges in the graph.
286 /// The complexity of the function is O(e) but for some
287 /// graph structures it is specialized to run in O(1).
289 /// If the graph contains a \e uEdgeNum() member function and a
290 /// \e EdgeNumTag tag then this function calls directly the member
291 /// function to query the cardinality of the undirected edge set.
292 template <typename Graph>
293 inline int countUEdges(const Graph& g) {
294 return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
299 template <typename Graph, typename DegIt>
300 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
302 for (DegIt it(_g, _n); it != INVALID; ++it) {
308 /// \brief Function to count the number of the out-edges from node \c n.
310 /// This function counts the number of the out-edges from node \c n
312 template <typename Graph>
313 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
314 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
317 /// \brief Function to count the number of the in-edges to node \c n.
319 /// This function counts the number of the in-edges to node \c n
321 template <typename Graph>
322 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
323 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
326 /// \brief Function to count the number of the inc-edges to node \c n.
328 /// This function counts the number of the inc-edges to node \c n
330 template <typename Graph>
331 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
332 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
335 namespace _graph_utils_bits {
337 template <typename Graph, typename Enable = void>
338 struct FindEdgeSelector {
339 typedef typename Graph::Node Node;
340 typedef typename Graph::Edge Edge;
341 static Edge find(const Graph &g, Node u, Node v, Edge e) {
347 while (e != INVALID && g.target(e) != v) {
354 template <typename Graph>
355 struct FindEdgeSelector<
357 typename enable_if<typename Graph::FindEdgeTag, void>::type>
359 typedef typename Graph::Node Node;
360 typedef typename Graph::Edge Edge;
361 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
362 return g.findEdge(u, v, prev);
367 /// \brief Finds an edge between two nodes of a graph.
369 /// Finds an edge from node \c u to node \c v in graph \c g.
371 /// If \c prev is \ref INVALID (this is the default value), then
372 /// it finds the first edge from \c u to \c v. Otherwise it looks for
373 /// the next edge from \c u to \c v after \c prev.
374 /// \return The found edge or \ref INVALID if there is no such an edge.
376 /// Thus you can iterate through each edge from \c u to \c v as it follows.
378 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
386 template <typename Graph>
387 inline typename Graph::Edge
388 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
389 typename Graph::Edge prev = INVALID) {
390 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
393 /// \brief Iterator for iterating on edges connected the same nodes.
395 /// Iterator for iterating on edges connected the same nodes. It is
396 /// higher level interface for the findEdge() function. You can
397 /// use it the following way:
399 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
408 /// \author Balazs Dezso
409 template <typename _Graph>
410 class ConEdgeIt : public _Graph::Edge {
413 typedef _Graph Graph;
414 typedef typename Graph::Edge Parent;
416 typedef typename Graph::Edge Edge;
417 typedef typename Graph::Node Node;
419 /// \brief Constructor.
421 /// Construct a new ConEdgeIt iterating on the edges which
422 /// connects the \c u and \c v node.
423 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
424 Parent::operator=(findEdge(graph, u, v));
427 /// \brief Constructor.
429 /// Construct a new ConEdgeIt which continues the iterating from
431 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
433 /// \brief Increment operator.
435 /// It increments the iterator and gives back the next edge.
436 ConEdgeIt& operator++() {
437 Parent::operator=(findEdge(graph, graph.source(*this),
438 graph.target(*this), *this));
445 namespace _graph_utils_bits {
447 template <typename Graph, typename Enable = void>
448 struct FindUEdgeSelector {
449 typedef typename Graph::Node Node;
450 typedef typename Graph::UEdge UEdge;
451 static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
457 b = g.source(e) == u;
460 while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
470 while (e != INVALID && (!b || g.target(e) != v)) {
478 template <typename Graph>
479 struct FindUEdgeSelector<
481 typename enable_if<typename Graph::FindEdgeTag, void>::type>
483 typedef typename Graph::Node Node;
484 typedef typename Graph::UEdge UEdge;
485 static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
486 return g.findUEdge(u, v, prev);
491 /// \brief Finds an uedge between two nodes of a graph.
493 /// Finds an uedge from node \c u to node \c v in graph \c g.
494 /// If the node \c u and node \c v is equal then each loop edge
495 /// will be enumerated.
497 /// If \c prev is \ref INVALID (this is the default value), then
498 /// it finds the first edge from \c u to \c v. Otherwise it looks for
499 /// the next edge from \c u to \c v after \c prev.
500 /// \return The found edge or \ref INVALID if there is no such an edge.
502 /// Thus you can iterate through each edge from \c u to \c v as it follows.
504 /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
505 /// e = findUEdge(g,u,v,e)) {
512 template <typename Graph>
513 inline typename Graph::UEdge
514 findUEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
515 typename Graph::UEdge p = INVALID) {
516 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
519 /// \brief Iterator for iterating on uedges connected the same nodes.
521 /// Iterator for iterating on uedges connected the same nodes. It is
522 /// higher level interface for the findUEdge() function. You can
523 /// use it the following way:
525 /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
532 /// \author Balazs Dezso
533 template <typename _Graph>
534 class ConUEdgeIt : public _Graph::UEdge {
537 typedef _Graph Graph;
538 typedef typename Graph::UEdge Parent;
540 typedef typename Graph::UEdge UEdge;
541 typedef typename Graph::Node Node;
543 /// \brief Constructor.
545 /// Construct a new ConUEdgeIt iterating on the edges which
546 /// connects the \c u and \c v node.
547 ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
548 Parent::operator=(findUEdge(graph, u, v));
551 /// \brief Constructor.
553 /// Construct a new ConUEdgeIt which continues the iterating from
555 ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
557 /// \brief Increment operator.
559 /// It increments the iterator and gives back the next edge.
560 ConUEdgeIt& operator++() {
561 Parent::operator=(findUEdge(graph, graph.source(*this),
562 graph.target(*this), *this));
569 /// \brief Copy a map.
571 /// This function copies the \c from map to the \c to map. It uses the
572 /// given iterator to iterate on the data structure and it uses the \c ref
573 /// mapping to convert the from's keys to the to's keys.
574 template <typename To, typename From,
575 typename ItemIt, typename Ref>
576 void copyMap(To& to, const From& from,
577 ItemIt it, const Ref& ref) {
578 for (; it != INVALID; ++it) {
579 to[ref[it]] = from[it];
583 /// \brief Copy the from map to the to map.
585 /// Copy the \c from map to the \c to map. It uses the given iterator
586 /// to iterate on the data structure.
587 template <typename To, typename From, typename ItemIt>
588 void copyMap(To& to, const From& from, ItemIt it) {
589 for (; it != INVALID; ++it) {
594 namespace _graph_utils_bits {
596 template <typename Graph, typename Item, typename RefMap>
599 virtual void copy(const Graph& from, const RefMap& refMap) = 0;
601 virtual ~MapCopyBase() {}
604 template <typename Graph, typename Item, typename RefMap,
605 typename ToMap, typename FromMap>
606 class MapCopy : public MapCopyBase<Graph, Item, RefMap> {
609 MapCopy(ToMap& tmap, const FromMap& map)
610 : _tmap(tmap), _map(map) {}
612 virtual void copy(const Graph& graph, const RefMap& refMap) {
613 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
614 for (ItemIt it(graph); it != INVALID; ++it) {
615 _tmap.set(refMap[it], _map[it]);
624 template <typename Graph, typename Item, typename RefMap, typename It>
625 class ItemCopy : public MapCopyBase<Graph, Item, RefMap> {
628 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
630 virtual void copy(const Graph&, const RefMap& refMap) {
639 template <typename Graph, typename Item, typename RefMap, typename Ref>
640 class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
643 RefCopy(Ref& map) : _map(map) {}
645 virtual void copy(const Graph& graph, const RefMap& refMap) {
646 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
647 for (ItemIt it(graph); it != INVALID; ++it) {
648 _map.set(it, refMap[it]);
656 template <typename Graph, typename Item, typename RefMap,
658 class CrossRefCopy : public MapCopyBase<Graph, Item, RefMap> {
661 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
663 virtual void copy(const Graph& graph, const RefMap& refMap) {
664 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
665 for (ItemIt it(graph); it != INVALID; ++it) {
666 _cmap.set(refMap[it], it);
674 template <typename Graph, typename Enable = void>
675 struct GraphCopySelector {
676 template <typename From, typename NodeRefMap, typename EdgeRefMap>
677 static void copy(Graph &to, const From& from,
678 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
679 for (typename From::NodeIt it(from); it != INVALID; ++it) {
680 nodeRefMap[it] = to.addNode();
682 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
683 edgeRefMap[it] = to.addEdge(nodeRefMap[from.source(it)],
684 nodeRefMap[from.target(it)]);
689 template <typename Graph>
690 struct GraphCopySelector<
692 typename enable_if<typename Graph::BuildTag, void>::type>
694 template <typename From, typename NodeRefMap, typename EdgeRefMap>
695 static void copy(Graph &to, const From& from,
696 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
697 to.build(from, nodeRefMap, edgeRefMap);
701 template <typename UGraph, typename Enable = void>
702 struct UGraphCopySelector {
703 template <typename From, typename NodeRefMap, typename UEdgeRefMap>
704 static void copy(UGraph &to, const From& from,
705 NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
706 for (typename From::NodeIt it(from); it != INVALID; ++it) {
707 nodeRefMap[it] = to.addNode();
709 for (typename From::UEdgeIt it(from); it != INVALID; ++it) {
710 uEdgeRefMap[it] = to.addEdge(nodeRefMap[from.source(it)],
711 nodeRefMap[from.target(it)]);
716 template <typename UGraph>
717 struct UGraphCopySelector<
719 typename enable_if<typename UGraph::BuildTag, void>::type>
721 template <typename From, typename NodeRefMap, typename UEdgeRefMap>
722 static void copy(UGraph &to, const From& from,
723 NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
724 to.build(from, nodeRefMap, uEdgeRefMap);
728 template <typename BpUGraph, typename Enable = void>
729 struct BpUGraphCopySelector {
730 template <typename From, typename ANodeRefMap,
731 typename BNodeRefMap, typename UEdgeRefMap>
732 static void copy(BpUGraph &to, const From& from,
733 ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
734 UEdgeRefMap& uEdgeRefMap) {
735 for (typename From::ANodeIt it(from); it != INVALID; ++it) {
736 aNodeRefMap[it] = to.addANode();
738 for (typename From::BNodeIt it(from); it != INVALID; ++it) {
739 bNodeRefMap[it] = to.addBNode();
741 for (typename From::UEdgeIt it(from); it != INVALID; ++it) {
742 uEdgeRefMap[it] = to.addEdge(aNodeRefMap[from.aNode(it)],
743 bNodeRefMap[from.bNode(it)]);
748 template <typename BpUGraph>
749 struct BpUGraphCopySelector<
751 typename enable_if<typename BpUGraph::BuildTag, void>::type>
753 template <typename From, typename ANodeRefMap,
754 typename BNodeRefMap, typename UEdgeRefMap>
755 static void copy(BpUGraph &to, const From& from,
756 ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
757 UEdgeRefMap& uEdgeRefMap) {
758 to.build(from, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
765 /// \brief Class to copy a graph.
767 /// Class to copy a graph to another graph (duplicate a graph). The
768 /// simplest way of using it is through the \c copyGraph() function.
769 template <typename To, typename From>
773 typedef typename From::Node Node;
774 typedef typename From::NodeIt NodeIt;
775 typedef typename From::Edge Edge;
776 typedef typename From::EdgeIt EdgeIt;
778 typedef typename To::Node TNode;
779 typedef typename To::Edge TEdge;
781 typedef typename From::template NodeMap<TNode> NodeRefMap;
782 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
788 /// \brief Constructor for the GraphCopy.
790 /// It copies the content of the \c _from graph into the
792 GraphCopy(To& _to, const From& _from)
793 : from(_from), to(_to) {}
795 /// \brief Destructor of the GraphCopy
797 /// Destructor of the GraphCopy
799 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
800 delete nodeMapCopies[i];
802 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
803 delete edgeMapCopies[i];
808 /// \brief Copies the node references into the given map.
810 /// Copies the node references into the given map.
811 template <typename NodeRef>
812 GraphCopy& nodeRef(NodeRef& map) {
813 nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Node,
814 NodeRefMap, NodeRef>(map));
818 /// \brief Copies the node cross references into the given map.
820 /// Copies the node cross references (reverse references) into
822 template <typename NodeCrossRef>
823 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
824 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
825 NodeRefMap, NodeCrossRef>(map));
829 /// \brief Make copy of the given map.
831 /// Makes copy of the given map for the newly created graph.
832 /// The new map's key type is the to graph's node type,
833 /// and the copied map's key type is the from graph's node
835 template <typename ToMap, typename FromMap>
836 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
837 nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, Node,
838 NodeRefMap, ToMap, FromMap>(tmap, map));
842 /// \brief Make a copy of the given node.
844 /// Make a copy of the given node.
845 GraphCopy& node(TNode& tnode, const Node& snode) {
846 nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Node,
847 NodeRefMap, TNode>(tnode, snode));
851 /// \brief Copies the edge references into the given map.
853 /// Copies the edge references into the given map.
854 template <typename EdgeRef>
855 GraphCopy& edgeRef(EdgeRef& map) {
856 edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Edge,
857 EdgeRefMap, EdgeRef>(map));
861 /// \brief Copies the edge cross references into the given map.
863 /// Copies the edge cross references (reverse references) into
865 template <typename EdgeCrossRef>
866 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
867 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Edge,
868 EdgeRefMap, EdgeCrossRef>(map));
872 /// \brief Make copy of the given map.
874 /// Makes copy of the given map for the newly created graph.
875 /// The new map's key type is the to graph's edge type,
876 /// and the copied map's key type is the from graph's edge
878 template <typename ToMap, typename FromMap>
879 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
880 edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, Edge,
881 EdgeRefMap, ToMap, FromMap>(tmap, map));
885 /// \brief Make a copy of the given edge.
887 /// Make a copy of the given edge.
888 GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
889 edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
890 EdgeRefMap, TEdge>(tedge, sedge));
894 /// \brief Executes the copies.
896 /// Executes the copies.
898 NodeRefMap nodeRefMap(from);
899 EdgeRefMap edgeRefMap(from);
900 _graph_utils_bits::GraphCopySelector<To>::
901 copy(to, from, nodeRefMap, edgeRefMap);
902 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
903 nodeMapCopies[i]->copy(from, nodeRefMap);
905 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
906 edgeMapCopies[i]->copy(from, edgeRefMap);
916 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
919 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
924 /// \brief Copy a graph to another graph.
926 /// Copy a graph to another graph.
927 /// The usage of the function:
930 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
933 /// After the copy the \c nr map will contain the mapping from the
934 /// from graph's nodes to the to graph's nodes and the \c ecr will
935 /// contain the mapping from the to graph's edges to the from's
939 template <typename To, typename From>
940 GraphCopy<To, From> copyGraph(To& to, const From& from) {
941 return GraphCopy<To, From>(to, from);
944 /// \brief Class to copy an undirected graph.
946 /// Class to copy an undirected graph to another graph (duplicate a graph).
947 /// The simplest way of using it is through the \c copyUGraph() function.
948 template <typename To, typename From>
952 typedef typename From::Node Node;
953 typedef typename From::NodeIt NodeIt;
954 typedef typename From::Edge Edge;
955 typedef typename From::EdgeIt EdgeIt;
956 typedef typename From::UEdge UEdge;
957 typedef typename From::UEdgeIt UEdgeIt;
959 typedef typename To::Node TNode;
960 typedef typename To::Edge TEdge;
961 typedef typename To::UEdge TUEdge;
963 typedef typename From::template NodeMap<TNode> NodeRefMap;
964 typedef typename From::template UEdgeMap<TUEdge> UEdgeRefMap;
967 EdgeRefMap(const To& _to, const From& _from,
968 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
969 : to(_to), from(_from),
970 uedge_ref(_uedge_ref), node_ref(_node_ref) {}
972 typedef typename From::Edge Key;
973 typedef typename To::Edge Value;
975 Value operator[](const Key& key) const {
977 (from.direction(key) ==
978 (node_ref[from.source(static_cast<const UEdge&>(key))] ==
979 to.source(uedge_ref[static_cast<const UEdge&>(key)])));
980 return to.direct(uedge_ref[key], forward);
985 const UEdgeRefMap& uedge_ref;
986 const NodeRefMap& node_ref;
993 /// \brief Constructor for the GraphCopy.
995 /// It copies the content of the \c _from graph into the
997 UGraphCopy(To& _to, const From& _from)
998 : from(_from), to(_to) {}
1000 /// \brief Destructor of the GraphCopy
1002 /// Destructor of the GraphCopy
1004 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1005 delete nodeMapCopies[i];
1007 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1008 delete edgeMapCopies[i];
1010 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1011 delete uEdgeMapCopies[i];
1016 /// \brief Copies the node references into the given map.
1018 /// Copies the node references into the given map.
1019 template <typename NodeRef>
1020 UGraphCopy& nodeRef(NodeRef& map) {
1021 nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Node,
1022 NodeRefMap, NodeRef>(map));
1026 /// \brief Copies the node cross references into the given map.
1028 /// Copies the node cross references (reverse references) into
1030 template <typename NodeCrossRef>
1031 UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1032 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1033 NodeRefMap, NodeCrossRef>(map));
1037 /// \brief Make copy of the given map.
1039 /// Makes copy of the given map for the newly created graph.
1040 /// The new map's key type is the to graph's node type,
1041 /// and the copied map's key type is the from graph's node
1043 template <typename ToMap, typename FromMap>
1044 UGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1045 nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, Node,
1046 NodeRefMap, ToMap, FromMap>(tmap, map));
1050 /// \brief Make a copy of the given node.
1052 /// Make a copy of the given node.
1053 UGraphCopy& node(TNode& tnode, const Node& snode) {
1054 nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1055 NodeRefMap, TNode>(tnode, snode));
1059 /// \brief Copies the edge references into the given map.
1061 /// Copies the edge references into the given map.
1062 template <typename EdgeRef>
1063 UGraphCopy& edgeRef(EdgeRef& map) {
1064 edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1065 EdgeRefMap, EdgeRef>(map));
1069 /// \brief Copies the edge cross references into the given map.
1071 /// Copies the edge cross references (reverse references) into
1073 template <typename EdgeCrossRef>
1074 UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1075 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Edge,
1076 EdgeRefMap, EdgeCrossRef>(map));
1080 /// \brief Make copy of the given map.
1082 /// Makes copy of the given map for the newly created graph.
1083 /// The new map's key type is the to graph's edge type,
1084 /// and the copied map's key type is the from graph's edge
1086 template <typename ToMap, typename FromMap>
1087 UGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1088 edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1089 EdgeRefMap, ToMap, FromMap>(tmap, map));
1093 /// \brief Make a copy of the given edge.
1095 /// Make a copy of the given edge.
1096 UGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1097 edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1098 EdgeRefMap, TEdge>(tedge, sedge));
1102 /// \brief Copies the undirected edge references into the given map.
1104 /// Copies the undirected edge references into the given map.
1105 template <typename UEdgeRef>
1106 UGraphCopy& uEdgeRef(UEdgeRef& map) {
1107 uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, UEdge,
1108 UEdgeRefMap, UEdgeRef>(map));
1112 /// \brief Copies the undirected edge cross references into the given map.
1114 /// Copies the undirected edge cross references (reverse
1115 /// references) into the given map.
1116 template <typename UEdgeCrossRef>
1117 UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1118 uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
1119 UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
1123 /// \brief Make copy of the given map.
1125 /// Makes copy of the given map for the newly created graph.
1126 /// The new map's key type is the to graph's undirected edge type,
1127 /// and the copied map's key type is the from graph's undirected edge
1129 template <typename ToMap, typename FromMap>
1130 UGraphCopy& uEdgeMap(ToMap& tmap, const FromMap& map) {
1131 uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, UEdge,
1132 UEdgeRefMap, ToMap, FromMap>(tmap, map));
1136 /// \brief Make a copy of the given undirected edge.
1138 /// Make a copy of the given undirected edge.
1139 UGraphCopy& uEdge(TUEdge& tuedge, const UEdge& suedge) {
1140 uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, UEdge,
1141 UEdgeRefMap, TUEdge>(tuedge, suedge));
1145 /// \brief Executes the copies.
1147 /// Executes the copies.
1149 NodeRefMap nodeRefMap(from);
1150 UEdgeRefMap uEdgeRefMap(from);
1151 EdgeRefMap edgeRefMap(to, from, uEdgeRefMap, nodeRefMap);
1152 _graph_utils_bits::UGraphCopySelector<To>::
1153 copy(to, from, nodeRefMap, uEdgeRefMap);
1154 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1155 nodeMapCopies[i]->copy(from, nodeRefMap);
1157 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1158 uEdgeMapCopies[i]->copy(from, uEdgeRefMap);
1160 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1161 edgeMapCopies[i]->copy(from, edgeRefMap);
1170 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1173 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1176 std::vector<_graph_utils_bits::MapCopyBase<From, UEdge, UEdgeRefMap>* >
1181 /// \brief Copy an undirected graph to another graph.
1183 /// Copy an undirected graph to another graph.
1184 /// The usage of the function:
1187 /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
1190 /// After the copy the \c nr map will contain the mapping from the
1191 /// from graph's nodes to the to graph's nodes and the \c ecr will
1192 /// contain the mapping from the to graph's edges to the from's
1196 template <typename To, typename From>
1197 UGraphCopy<To, From>
1198 copyUGraph(To& to, const From& from) {
1199 return UGraphCopy<To, From>(to, from);
1202 /// \brief Class to copy a bipartite undirected graph.
1204 /// Class to copy a bipartite undirected graph to another graph
1205 /// (duplicate a graph). The simplest way of using it is through
1206 /// the \c copyBpUGraph() function.
1207 template <typename To, typename From>
1208 class BpUGraphCopy {
1211 typedef typename From::Node Node;
1212 typedef typename From::ANode ANode;
1213 typedef typename From::BNode BNode;
1214 typedef typename From::NodeIt NodeIt;
1215 typedef typename From::Edge Edge;
1216 typedef typename From::EdgeIt EdgeIt;
1217 typedef typename From::UEdge UEdge;
1218 typedef typename From::UEdgeIt UEdgeIt;
1220 typedef typename To::Node TNode;
1221 typedef typename To::Edge TEdge;
1222 typedef typename To::UEdge TUEdge;
1224 typedef typename From::template ANodeMap<TNode> ANodeRefMap;
1225 typedef typename From::template BNodeMap<TNode> BNodeRefMap;
1226 typedef typename From::template UEdgeMap<TUEdge> UEdgeRefMap;
1229 NodeRefMap(const From& _from, const ANodeRefMap& _anode_ref,
1230 const BNodeRefMap& _bnode_ref)
1231 : from(_from), anode_ref(_anode_ref), bnode_ref(_bnode_ref) {}
1233 typedef typename From::Node Key;
1234 typedef typename To::Node Value;
1236 Value operator[](const Key& key) const {
1237 return from.aNode(key) ? anode_ref[key] : bnode_ref[key];
1241 const ANodeRefMap& anode_ref;
1242 const BNodeRefMap& bnode_ref;
1246 EdgeRefMap(const To& _to, const From& _from,
1247 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
1248 : to(_to), from(_from),
1249 uedge_ref(_uedge_ref), node_ref(_node_ref) {}
1251 typedef typename From::Edge Key;
1252 typedef typename To::Edge Value;
1254 Value operator[](const Key& key) const {
1256 (from.direction(key) ==
1257 (node_ref[from.source(static_cast<const UEdge&>(key))] ==
1258 to.source(uedge_ref[static_cast<const UEdge&>(key)])));
1259 return to.direct(uedge_ref[key], forward);
1264 const UEdgeRefMap& uedge_ref;
1265 const NodeRefMap& node_ref;
1271 /// \brief Constructor for the GraphCopy.
1273 /// It copies the content of the \c _from graph into the
1275 BpUGraphCopy(To& _to, const From& _from)
1276 : from(_from), to(_to) {}
1278 /// \brief Destructor of the GraphCopy
1280 /// Destructor of the GraphCopy
1282 for (int i = 0; i < int(aNodeMapCopies.size()); ++i) {
1283 delete aNodeMapCopies[i];
1285 for (int i = 0; i < int(bNodeMapCopies.size()); ++i) {
1286 delete bNodeMapCopies[i];
1288 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1289 delete nodeMapCopies[i];
1291 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1292 delete edgeMapCopies[i];
1294 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1295 delete uEdgeMapCopies[i];
1300 /// \brief Copies the A-node references into the given map.
1302 /// Copies the A-node references into the given map.
1303 template <typename ANodeRef>
1304 BpUGraphCopy& aNodeRef(ANodeRef& map) {
1305 aNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, ANode,
1306 ANodeRefMap, ANodeRef>(map));
1310 /// \brief Copies the A-node cross references into the given map.
1312 /// Copies the A-node cross references (reverse references) into
1314 template <typename ANodeCrossRef>
1315 BpUGraphCopy& aNodeCrossRef(ANodeCrossRef& map) {
1316 aNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
1317 ANode, ANodeRefMap, ANodeCrossRef>(map));
1321 /// \brief Make copy of the given A-node map.
1323 /// Makes copy of the given map for the newly created graph.
1324 /// The new map's key type is the to graph's node type,
1325 /// and the copied map's key type is the from graph's node
1327 template <typename ToMap, typename FromMap>
1328 BpUGraphCopy& aNodeMap(ToMap& tmap, const FromMap& map) {
1329 aNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, ANode,
1330 ANodeRefMap, ToMap, FromMap>(tmap, map));
1334 /// \brief Copies the B-node references into the given map.
1336 /// Copies the B-node references into the given map.
1337 template <typename BNodeRef>
1338 BpUGraphCopy& bNodeRef(BNodeRef& map) {
1339 bNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, BNode,
1340 BNodeRefMap, BNodeRef>(map));
1344 /// \brief Copies the B-node cross references into the given map.
1346 /// Copies the B-node cross references (reverse references) into
1348 template <typename BNodeCrossRef>
1349 BpUGraphCopy& bNodeCrossRef(BNodeCrossRef& map) {
1350 bNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
1351 BNode, BNodeRefMap, BNodeCrossRef>(map));
1355 /// \brief Make copy of the given B-node map.
1357 /// Makes copy of the given map for the newly created graph.
1358 /// The new map's key type is the to graph's node type,
1359 /// and the copied map's key type is the from graph's node
1361 template <typename ToMap, typename FromMap>
1362 BpUGraphCopy& bNodeMap(ToMap& tmap, const FromMap& map) {
1363 bNodeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, BNode,
1364 BNodeRefMap, ToMap, FromMap>(tmap, map));
1367 /// \brief Copies the node references into the given map.
1369 /// Copies the node references into the given map.
1370 template <typename NodeRef>
1371 BpUGraphCopy& nodeRef(NodeRef& map) {
1372 nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Node,
1373 NodeRefMap, NodeRef>(map));
1377 /// \brief Copies the node cross references into the given map.
1379 /// Copies the node cross references (reverse references) into
1381 template <typename NodeCrossRef>
1382 BpUGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1383 nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1384 NodeRefMap, NodeCrossRef>(map));
1388 /// \brief Make copy of the given map.
1390 /// Makes copy of the given map for the newly created graph.
1391 /// The new map's key type is the to graph's node type,
1392 /// and the copied map's key type is the from graph's node
1394 template <typename ToMap, typename FromMap>
1395 BpUGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1396 nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, Node,
1397 NodeRefMap, ToMap, FromMap>(tmap, map));
1401 /// \brief Make a copy of the given node.
1403 /// Make a copy of the given node.
1404 BpUGraphCopy& node(TNode& tnode, const Node& snode) {
1405 nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1406 NodeRefMap, TNode>(tnode, snode));
1410 /// \brief Copies the edge references into the given map.
1412 /// Copies the edge references into the given map.
1413 template <typename EdgeRef>
1414 BpUGraphCopy& edgeRef(EdgeRef& map) {
1415 edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1416 EdgeRefMap, EdgeRef>(map));
1420 /// \brief Copies the edge cross references into the given map.
1422 /// Copies the edge cross references (reverse references) into
1424 template <typename EdgeCrossRef>
1425 BpUGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1426 edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Edge,
1427 EdgeRefMap, EdgeCrossRef>(map));
1431 /// \brief Make copy of the given map.
1433 /// Makes copy of the given map for the newly created graph.
1434 /// The new map's key type is the to graph's edge type,
1435 /// and the copied map's key type is the from graph's edge
1437 template <typename ToMap, typename FromMap>
1438 BpUGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1439 edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1440 EdgeRefMap, ToMap, FromMap>(tmap, map));
1444 /// \brief Make a copy of the given edge.
1446 /// Make a copy of the given edge.
1447 BpUGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1448 edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1449 EdgeRefMap, TEdge>(tedge, sedge));
1453 /// \brief Copies the undirected edge references into the given map.
1455 /// Copies the undirected edge references into the given map.
1456 template <typename UEdgeRef>
1457 BpUGraphCopy& uEdgeRef(UEdgeRef& map) {
1458 uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, UEdge,
1459 UEdgeRefMap, UEdgeRef>(map));
1463 /// \brief Copies the undirected edge cross references into the given map.
1465 /// Copies the undirected edge cross references (reverse
1466 /// references) into the given map.
1467 template <typename UEdgeCrossRef>
1468 BpUGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1469 uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
1470 UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
1474 /// \brief Make copy of the given map.
1476 /// Makes copy of the given map for the newly created graph.
1477 /// The new map's key type is the to graph's undirected edge type,
1478 /// and the copied map's key type is the from graph's undirected edge
1480 template <typename ToMap, typename FromMap>
1481 BpUGraphCopy& uEdgeMap(ToMap& tmap, const FromMap& map) {
1482 uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<From, UEdge,
1483 UEdgeRefMap, ToMap, FromMap>(tmap, map));
1487 /// \brief Make a copy of the given undirected edge.
1489 /// Make a copy of the given undirected edge.
1490 BpUGraphCopy& uEdge(TUEdge& tuedge, const UEdge& suedge) {
1491 uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, UEdge,
1492 UEdgeRefMap, TUEdge>(tuedge, suedge));
1496 /// \brief Executes the copies.
1498 /// Executes the copies.
1500 ANodeRefMap aNodeRefMap(from);
1501 BNodeRefMap bNodeRefMap(from);
1502 NodeRefMap nodeRefMap(from, aNodeRefMap, bNodeRefMap);
1503 UEdgeRefMap uEdgeRefMap(from);
1504 EdgeRefMap edgeRefMap(to, from, uEdgeRefMap, nodeRefMap);
1505 _graph_utils_bits::BpUGraphCopySelector<To>::
1506 copy(to, from, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
1507 for (int i = 0; i < int(aNodeMapCopies.size()); ++i) {
1508 aNodeMapCopies[i]->copy(from, aNodeRefMap);
1510 for (int i = 0; i < int(bNodeMapCopies.size()); ++i) {
1511 bNodeMapCopies[i]->copy(from, bNodeRefMap);
1513 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1514 nodeMapCopies[i]->copy(from, nodeRefMap);
1516 for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
1517 uEdgeMapCopies[i]->copy(from, uEdgeRefMap);
1519 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1520 edgeMapCopies[i]->copy(from, edgeRefMap);
1529 std::vector<_graph_utils_bits::MapCopyBase<From, ANode, ANodeRefMap>* >
1532 std::vector<_graph_utils_bits::MapCopyBase<From, BNode, BNodeRefMap>* >
1535 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1538 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1541 std::vector<_graph_utils_bits::MapCopyBase<From, UEdge, UEdgeRefMap>* >
1546 /// \brief Copy a bipartite undirected graph to another graph.
1548 /// Copy a bipartite undirected graph to another graph.
1549 /// The usage of the function:
1552 /// copyBpUGraph(trg, src).aNodeRef(anr).edgeCrossRef(ecr).run();
1555 /// After the copy the \c nr map will contain the mapping from the
1556 /// from graph's nodes to the to graph's nodes and the \c ecr will
1557 /// contain the mapping from the to graph's edges to the from's
1560 /// \see BpUGraphCopy
1561 template <typename To, typename From>
1562 BpUGraphCopy<To, From>
1563 copyBpUGraph(To& to, const From& from) {
1564 return BpUGraphCopy<To, From>(to, from);
1570 /// \addtogroup graph_maps
1573 /// Provides an immutable and unique id for each item in the graph.
1575 /// The IdMap class provides a unique and immutable id for each item of the
1576 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1577 /// different items (nodes) get different ids <li>\b immutable: the id of an
1578 /// item (node) does not change (even if you delete other nodes). </ul>
1579 /// Through this map you get access (i.e. can read) the inner id values of
1580 /// the items stored in the graph. This map can be inverted with its member
1581 /// class \c InverseMap.
1583 template <typename _Graph, typename _Item>
1586 typedef _Graph Graph;
1591 /// \brief Constructor.
1593 /// Constructor of the map.
1594 explicit IdMap(const Graph& _graph) : graph(&_graph) {}
1596 /// \brief Gives back the \e id of the item.
1598 /// Gives back the immutable and unique \e id of the item.
1599 int operator[](const Item& item) const { return graph->id(item);}
1601 /// \brief Gives back the item by its id.
1603 /// Gives back the item by its id.
1604 Item operator()(int id) { return graph->fromId(id, Item()); }
1611 /// \brief The class represents the inverse of its owner (IdMap).
1613 /// The class represents the inverse of its owner (IdMap).
1618 /// \brief Constructor.
1620 /// Constructor for creating an id-to-item map.
1621 explicit InverseMap(const Graph& _graph) : graph(&_graph) {}
1623 /// \brief Constructor.
1625 /// Constructor for creating an id-to-item map.
1626 explicit InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1628 /// \brief Gives back the given item from its id.
1630 /// Gives back the given item from its id.
1632 Item operator[](int id) const { return graph->fromId(id, Item());}
1638 /// \brief Gives back the inverse of the map.
1640 /// Gives back the inverse of the IdMap.
1641 InverseMap inverse() const { return InverseMap(*graph);}
1646 /// \brief General invertable graph-map type.
1648 /// This type provides simple invertable graph-maps.
1649 /// The InvertableMap wraps an arbitrary ReadWriteMap
1650 /// and if a key is set to a new value then store it
1651 /// in the inverse map.
1653 /// The values of the map can be accessed
1654 /// with stl compatible forward iterator.
1656 /// \param _Graph The graph type.
1657 /// \param _Item The item type of the graph.
1658 /// \param _Value The value type of the map.
1660 /// \see IterableValueMap
1661 template <typename _Graph, typename _Item, typename _Value>
1662 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1665 typedef DefaultMap<_Graph, _Item, _Value> Map;
1666 typedef _Graph Graph;
1668 typedef std::map<_Value, _Item> Container;
1673 /// The key type of InvertableMap (Node, Edge, UEdge).
1674 typedef typename Map::Key Key;
1675 /// The value type of the InvertableMap.
1676 typedef typename Map::Value Value;
1680 /// \brief Constructor.
1682 /// Construct a new InvertableMap for the graph.
1684 explicit InvertableMap(const Graph& graph) : Map(graph) {}
1686 /// \brief Forward iterator for values.
1688 /// This iterator is an stl compatible forward
1689 /// iterator on the values of the map. The values can
1690 /// be accessed in the [beginValue, endValue) range.
1693 : public std::iterator<std::forward_iterator_tag, Value> {
1694 friend class InvertableMap;
1696 ValueIterator(typename Container::const_iterator _it)
1702 ValueIterator& operator++() { ++it; return *this; }
1703 ValueIterator operator++(int) {
1704 ValueIterator tmp(*this);
1709 const Value& operator*() const { return it->first; }
1710 const Value* operator->() const { return &(it->first); }
1712 bool operator==(ValueIterator jt) const { return it == jt.it; }
1713 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1716 typename Container::const_iterator it;
1719 /// \brief Returns an iterator to the first value.
1721 /// Returns an stl compatible iterator to the
1722 /// first value of the map. The values of the
1723 /// map can be accessed in the [beginValue, endValue)
1725 ValueIterator beginValue() const {
1726 return ValueIterator(invMap.begin());
1729 /// \brief Returns an iterator after the last value.
1731 /// Returns an stl compatible iterator after the
1732 /// last value of the map. The values of the
1733 /// map can be accessed in the [beginValue, endValue)
1735 ValueIterator endValue() const {
1736 return ValueIterator(invMap.end());
1739 /// \brief The setter function of the map.
1741 /// Sets the mapped value.
1742 void set(const Key& key, const Value& val) {
1743 Value oldval = Map::operator[](key);
1744 typename Container::iterator it = invMap.find(oldval);
1745 if (it != invMap.end() && it->second == key) {
1748 invMap.insert(make_pair(val, key));
1752 /// \brief The getter function of the map.
1754 /// It gives back the value associated with the key.
1755 typename MapTraits<Map>::ConstReturnValue
1756 operator[](const Key& key) const {
1757 return Map::operator[](key);
1760 /// \brief Gives back the item by its value.
1762 /// Gives back the item by its value.
1763 Key operator()(const Value& key) const {
1764 typename Container::const_iterator it = invMap.find(key);
1765 return it != invMap.end() ? it->second : INVALID;
1770 /// \brief Erase the key from the map.
1772 /// Erase the key to the map. It is called by the
1773 /// \c AlterationNotifier.
1774 virtual void erase(const Key& key) {
1775 Value val = Map::operator[](key);
1776 typename Container::iterator it = invMap.find(val);
1777 if (it != invMap.end() && it->second == key) {
1783 /// \brief Erase more keys from the map.
1785 /// Erase more keys from the map. It is called by the
1786 /// \c AlterationNotifier.
1787 virtual void erase(const std::vector<Key>& keys) {
1788 for (int i = 0; i < int(keys.size()); ++i) {
1789 Value val = Map::operator[](keys[i]);
1790 typename Container::iterator it = invMap.find(val);
1791 if (it != invMap.end() && it->second == keys[i]) {
1798 /// \brief Clear the keys from the map and inverse map.
1800 /// Clear the keys from the map and inverse map. It is called by the
1801 /// \c AlterationNotifier.
1802 virtual void clear() {
1809 /// \brief The inverse map type.
1811 /// The inverse of this map. The subscript operator of the map
1812 /// gives back always the item what was last assigned to the value.
1815 /// \brief Constructor of the InverseMap.
1817 /// Constructor of the InverseMap.
1818 explicit InverseMap(const InvertableMap& _inverted)
1819 : inverted(_inverted) {}
1821 /// The value type of the InverseMap.
1822 typedef typename InvertableMap::Key Value;
1823 /// The key type of the InverseMap.
1824 typedef typename InvertableMap::Value Key;
1826 /// \brief Subscript operator.
1828 /// Subscript operator. It gives back always the item
1829 /// what was last assigned to the value.
1830 Value operator[](const Key& key) const {
1831 return inverted(key);
1835 const InvertableMap& inverted;
1838 /// \brief It gives back the just readable inverse map.
1840 /// It gives back the just readable inverse map.
1841 InverseMap inverse() const {
1842 return InverseMap(*this);
1849 /// \brief Provides a mutable, continuous and unique descriptor for each
1850 /// item in the graph.
1852 /// The DescriptorMap class provides a unique and continuous (but mutable)
1853 /// descriptor (id) for each item of the same type (e.g. node) in the
1854 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1855 /// different ids <li>\b continuous: the range of the ids is the set of
1856 /// integers between 0 and \c n-1, where \c n is the number of the items of
1857 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1858 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1859 /// with its member class \c InverseMap.
1861 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1862 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1864 template <typename _Graph, typename _Item>
1865 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1868 typedef DefaultMap<_Graph, _Item, int> Map;
1871 /// The graph class of DescriptorMap.
1872 typedef _Graph Graph;
1874 /// The key type of DescriptorMap (Node, Edge, UEdge).
1875 typedef typename Map::Key Key;
1876 /// The value type of DescriptorMap.
1877 typedef typename Map::Value Value;
1879 /// \brief Constructor.
1881 /// Constructor for descriptor map.
1882 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1884 const typename Map::Notifier* nf = Map::notifier();
1885 for (nf->first(it); it != INVALID; nf->next(it)) {
1886 Map::set(it, invMap.size());
1887 invMap.push_back(it);
1893 /// \brief Add a new key to the map.
1895 /// Add a new key to the map. It is called by the
1896 /// \c AlterationNotifier.
1897 virtual void add(const Item& item) {
1899 Map::set(item, invMap.size());
1900 invMap.push_back(item);
1903 /// \brief Add more new keys to the map.
1905 /// Add more new keys to the map. It is called by the
1906 /// \c AlterationNotifier.
1907 virtual void add(const std::vector<Item>& items) {
1909 for (int i = 0; i < int(items.size()); ++i) {
1910 Map::set(items[i], invMap.size());
1911 invMap.push_back(items[i]);
1915 /// \brief Erase the key from the map.
1917 /// Erase the key from the map. It is called by the
1918 /// \c AlterationNotifier.
1919 virtual void erase(const Item& item) {
1920 Map::set(invMap.back(), Map::operator[](item));
1921 invMap[Map::operator[](item)] = invMap.back();
1926 /// \brief Erase more keys from the map.
1928 /// Erase more keys from the map. It is called by the
1929 /// \c AlterationNotifier.
1930 virtual void erase(const std::vector<Item>& items) {
1931 for (int i = 0; i < int(items.size()); ++i) {
1932 Map::set(invMap.back(), Map::operator[](items[i]));
1933 invMap[Map::operator[](items[i])] = invMap.back();
1939 /// \brief Build the unique map.
1941 /// Build the unique map. It is called by the
1942 /// \c AlterationNotifier.
1943 virtual void build() {
1946 const typename Map::Notifier* nf = Map::notifier();
1947 for (nf->first(it); it != INVALID; nf->next(it)) {
1948 Map::set(it, invMap.size());
1949 invMap.push_back(it);
1953 /// \brief Clear the keys from the map.
1955 /// Clear the keys from the map. It is called by the
1956 /// \c AlterationNotifier.
1957 virtual void clear() {
1964 /// \brief Returns the maximal value plus one.
1966 /// Returns the maximal value plus one in the map.
1967 unsigned int size() const {
1968 return invMap.size();
1971 /// \brief Swaps the position of the two items in the map.
1973 /// Swaps the position of the two items in the map.
1974 void swap(const Item& p, const Item& q) {
1975 int pi = Map::operator[](p);
1976 int qi = Map::operator[](q);
1983 /// \brief Gives back the \e descriptor of the item.
1985 /// Gives back the mutable and unique \e descriptor of the map.
1986 int operator[](const Item& item) const {
1987 return Map::operator[](item);
1990 /// \brief Gives back the item by its descriptor.
1992 /// Gives back th item by its descriptor.
1993 Item operator()(int id) const {
1999 typedef std::vector<Item> Container;
2003 /// \brief The inverse map type of DescriptorMap.
2005 /// The inverse map type of DescriptorMap.
2008 /// \brief Constructor of the InverseMap.
2010 /// Constructor of the InverseMap.
2011 explicit InverseMap(const DescriptorMap& _inverted)
2012 : inverted(_inverted) {}
2015 /// The value type of the InverseMap.
2016 typedef typename DescriptorMap::Key Value;
2017 /// The key type of the InverseMap.
2018 typedef typename DescriptorMap::Value Key;
2020 /// \brief Subscript operator.
2022 /// Subscript operator. It gives back the item
2023 /// that the descriptor belongs to currently.
2024 Value operator[](const Key& key) const {
2025 return inverted(key);
2028 /// \brief Size of the map.
2030 /// Returns the size of the map.
2031 unsigned int size() const {
2032 return inverted.size();
2036 const DescriptorMap& inverted;
2039 /// \brief Gives back the inverse of the map.
2041 /// Gives back the inverse of the map.
2042 const InverseMap inverse() const {
2043 return InverseMap(*this);
2047 /// \brief Returns the source of the given edge.
2049 /// The SourceMap gives back the source Node of the given edge.
2051 /// \author Balazs Dezso
2052 template <typename Graph>
2056 typedef typename Graph::Node Value;
2057 typedef typename Graph::Edge Key;
2059 /// \brief Constructor
2062 /// \param _graph The graph that the map belongs to.
2063 explicit SourceMap(const Graph& _graph) : graph(_graph) {}
2065 /// \brief The subscript operator.
2067 /// The subscript operator.
2068 /// \param edge The edge
2069 /// \return The source of the edge
2070 Value operator[](const Key& edge) const {
2071 return graph.source(edge);
2078 /// \brief Returns a \ref SourceMap class.
2080 /// This function just returns an \ref SourceMap class.
2081 /// \relates SourceMap
2082 template <typename Graph>
2083 inline SourceMap<Graph> sourceMap(const Graph& graph) {
2084 return SourceMap<Graph>(graph);
2087 /// \brief Returns the target of the given edge.
2089 /// The TargetMap gives back the target Node of the given edge.
2091 /// \author Balazs Dezso
2092 template <typename Graph>
2096 typedef typename Graph::Node Value;
2097 typedef typename Graph::Edge Key;
2099 /// \brief Constructor
2102 /// \param _graph The graph that the map belongs to.
2103 explicit TargetMap(const Graph& _graph) : graph(_graph) {}
2105 /// \brief The subscript operator.
2107 /// The subscript operator.
2108 /// \param e The edge
2109 /// \return The target of the edge
2110 Value operator[](const Key& e) const {
2111 return graph.target(e);
2118 /// \brief Returns a \ref TargetMap class.
2120 /// This function just returns a \ref TargetMap class.
2121 /// \relates TargetMap
2122 template <typename Graph>
2123 inline TargetMap<Graph> targetMap(const Graph& graph) {
2124 return TargetMap<Graph>(graph);
2127 /// \brief Returns the "forward" directed edge view of an undirected edge.
2129 /// Returns the "forward" directed edge view of an undirected edge.
2130 /// \see BackwardMap
2131 /// \author Balazs Dezso
2132 template <typename Graph>
2136 typedef typename Graph::Edge Value;
2137 typedef typename Graph::UEdge Key;
2139 /// \brief Constructor
2142 /// \param _graph The graph that the map belongs to.
2143 explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
2145 /// \brief The subscript operator.
2147 /// The subscript operator.
2148 /// \param key An undirected edge
2149 /// \return The "forward" directed edge view of undirected edge
2150 Value operator[](const Key& key) const {
2151 return graph.direct(key, true);
2158 /// \brief Returns a \ref ForwardMap class.
2160 /// This function just returns an \ref ForwardMap class.
2161 /// \relates ForwardMap
2162 template <typename Graph>
2163 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2164 return ForwardMap<Graph>(graph);
2167 /// \brief Returns the "backward" directed edge view of an undirected edge.
2169 /// Returns the "backward" directed edge view of an undirected edge.
2171 /// \author Balazs Dezso
2172 template <typename Graph>
2176 typedef typename Graph::Edge Value;
2177 typedef typename Graph::UEdge Key;
2179 /// \brief Constructor
2182 /// \param _graph The graph that the map belongs to.
2183 explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
2185 /// \brief The subscript operator.
2187 /// The subscript operator.
2188 /// \param key An undirected edge
2189 /// \return The "backward" directed edge view of undirected edge
2190 Value operator[](const Key& key) const {
2191 return graph.direct(key, false);
2198 /// \brief Returns a \ref BackwardMap class
2200 /// This function just returns a \ref BackwardMap class.
2201 /// \relates BackwardMap
2202 template <typename Graph>
2203 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2204 return BackwardMap<Graph>(graph);
2207 /// \brief Potential difference map
2209 /// If there is an potential map on the nodes then we
2210 /// can get an edge map as we get the substraction of the
2211 /// values of the target and source.
2212 template <typename Graph, typename NodeMap>
2213 class PotentialDifferenceMap {
2215 typedef typename Graph::Edge Key;
2216 typedef typename NodeMap::Value Value;
2218 /// \brief Constructor
2220 /// Contructor of the map
2221 explicit PotentialDifferenceMap(const Graph& _graph,
2222 const NodeMap& _potential)
2223 : graph(_graph), potential(_potential) {}
2225 /// \brief Const subscription operator
2227 /// Const subscription operator
2228 Value operator[](const Key& edge) const {
2229 return potential[graph.target(edge)] - potential[graph.source(edge)];
2234 const NodeMap& potential;
2237 /// \brief Returns a PotentialDifferenceMap.
2239 /// This function just returns a PotentialDifferenceMap.
2240 /// \relates PotentialDifferenceMap
2241 template <typename Graph, typename NodeMap>
2242 PotentialDifferenceMap<Graph, NodeMap>
2243 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
2244 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
2247 /// \brief Map of the node in-degrees.
2249 /// This map returns the in-degree of a node. Once it is constructed,
2250 /// the degrees are stored in a standard NodeMap, so each query is done
2251 /// in constant time. On the other hand, the values are updated automatically
2252 /// whenever the graph changes.
2254 /// \warning Besides addNode() and addEdge(), a graph structure may provide
2255 /// alternative ways to modify the graph. The correct behavior of InDegMap
2256 /// is not guarantied if these additional features are used. For example
2257 /// the functions \ref ListGraph::changeSource() "changeSource()",
2258 /// \ref ListGraph::changeTarget() "changeTarget()" and
2259 /// \ref ListGraph::reverseEdge() "reverseEdge()"
2260 /// of \ref ListGraph will \e not update the degree values correctly.
2264 template <typename _Graph>
2266 : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2267 ::ItemNotifier::ObserverBase {
2271 typedef _Graph Graph;
2273 typedef typename Graph::Node Key;
2275 typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2276 ::ItemNotifier::ObserverBase Parent;
2280 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
2283 typedef DefaultMap<_Graph, Key, int> Parent;
2284 typedef typename Parent::Graph Graph;
2286 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2288 virtual void add(const Key& key) {
2290 Parent::set(key, 0);
2293 virtual void add(const std::vector<Key>& keys) {
2295 for (int i = 0; i < int(keys.size()); ++i) {
2296 Parent::set(keys[i], 0);
2303 /// \brief Constructor.
2305 /// Constructor for creating in-degree map.
2306 explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
2307 Parent::attach(graph.notifier(typename _Graph::Edge()));
2309 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2310 deg[it] = countInEdges(graph, it);
2314 /// Gives back the in-degree of a Node.
2315 int operator[](const Key& key) const {
2321 typedef typename Graph::Edge Edge;
2323 virtual void add(const Edge& edge) {
2324 ++deg[graph.target(edge)];
2327 virtual void add(const std::vector<Edge>& edges) {
2328 for (int i = 0; i < int(edges.size()); ++i) {
2329 ++deg[graph.target(edges[i])];
2333 virtual void erase(const Edge& edge) {
2334 --deg[graph.target(edge)];
2337 virtual void erase(const std::vector<Edge>& edges) {
2338 for (int i = 0; i < int(edges.size()); ++i) {
2339 --deg[graph.target(edges[i])];
2343 virtual void build() {
2344 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2345 deg[it] = countInEdges(graph, it);
2349 virtual void clear() {
2350 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2356 const _Graph& graph;
2360 /// \brief Map of the node out-degrees.
2362 /// This map returns the out-degree of a node. Once it is constructed,
2363 /// the degrees are stored in a standard NodeMap, so each query is done
2364 /// in constant time. On the other hand, the values are updated automatically
2365 /// whenever the graph changes.
2367 /// \warning Besides addNode() and addEdge(), a graph structure may provide
2368 /// alternative ways to modify the graph. The correct behavior of OutDegMap
2369 /// is not guarantied if these additional features are used. For example
2370 /// the functions \ref ListGraph::changeSource() "changeSource()",
2371 /// \ref ListGraph::changeTarget() "changeTarget()" and
2372 /// \ref ListGraph::reverseEdge() "reverseEdge()"
2373 /// of \ref ListGraph will \e not update the degree values correctly.
2377 template <typename _Graph>
2379 : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2380 ::ItemNotifier::ObserverBase {
2384 typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2385 ::ItemNotifier::ObserverBase Parent;
2387 typedef _Graph Graph;
2389 typedef typename Graph::Node Key;
2393 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
2396 typedef DefaultMap<_Graph, Key, int> Parent;
2397 typedef typename Parent::Graph Graph;
2399 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2401 virtual void add(const Key& key) {
2403 Parent::set(key, 0);
2405 virtual void add(const std::vector<Key>& keys) {
2407 for (int i = 0; i < int(keys.size()); ++i) {
2408 Parent::set(keys[i], 0);
2415 /// \brief Constructor.
2417 /// Constructor for creating out-degree map.
2418 explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
2419 Parent::attach(graph.notifier(typename _Graph::Edge()));
2421 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2422 deg[it] = countOutEdges(graph, it);
2426 /// Gives back the out-degree of a Node.
2427 int operator[](const Key& key) const {
2433 typedef typename Graph::Edge Edge;
2435 virtual void add(const Edge& edge) {
2436 ++deg[graph.source(edge)];
2439 virtual void add(const std::vector<Edge>& edges) {
2440 for (int i = 0; i < int(edges.size()); ++i) {
2441 ++deg[graph.source(edges[i])];
2445 virtual void erase(const Edge& edge) {
2446 --deg[graph.source(edge)];
2449 virtual void erase(const std::vector<Edge>& edges) {
2450 for (int i = 0; i < int(edges.size()); ++i) {
2451 --deg[graph.source(edges[i])];
2455 virtual void build() {
2456 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2457 deg[it] = countOutEdges(graph, it);
2461 virtual void clear() {
2462 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2468 const _Graph& graph;
2473 ///Fast edge look up between given endpoints.
2476 ///Using this class, you can find an edge in a graph from a given
2477 ///source to a given target in time <em>O(log d)</em>,
2478 ///where <em>d</em> is the out-degree of the source node.
2480 ///It is not possible to find \e all parallel edges between two nodes.
2481 ///Use \ref AllEdgeLookUp for this purpose.
2483 ///\warning This class is static, so you should refresh() (or at least
2484 ///refresh(Node)) this data structure
2485 ///whenever the graph changes. This is a time consuming (superlinearly
2486 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2488 ///\param G The type of the underlying graph.
2490 ///\sa AllEdgeLookUp
2495 GRAPH_TYPEDEFS(typename G);
2500 typename Graph::template NodeMap<Edge> _head;
2501 typename Graph::template EdgeMap<Edge> _left;
2502 typename Graph::template EdgeMap<Edge> _right;
2507 EdgeLess(const Graph &_g) : g(_g) {}
2508 bool operator()(Edge a,Edge b) const
2510 return g.target(a)<g.target(b);
2520 ///It builds up the search database, which remains valid until the graph
2522 EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2525 Edge refresh_rec(std::vector<Edge> &v,int a,int b)
2529 _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
2530 _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
2534 ///Refresh the data structure at a node.
2536 ///Build up the search database of node \c n.
2538 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2539 ///the number of the outgoing edges of \c n.
2540 void refresh(Node n)
2542 std::vector<Edge> v;
2543 for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2545 std::sort(v.begin(),v.end(),EdgeLess(_g));
2546 _head[n]=refresh_rec(v,0,v.size()-1);
2548 else _head[n]=INVALID;
2550 ///Refresh the full data structure.
2552 ///Build up the full search database. In fact, it simply calls
2553 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2555 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2556 ///the number of the edges of \c n and <em>D</em> is the maximum
2557 ///out-degree of the graph.
2561 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2564 ///Find an edge between two nodes.
2566 ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2567 /// <em>d</em> is the number of outgoing edges of \c s.
2568 ///\param s The source node
2569 ///\param t The target node
2570 ///\return An edge from \c s to \c t if there exists,
2571 ///\ref INVALID otherwise.
2573 ///\warning If you change the graph, refresh() must be called before using
2574 ///this operator. If you change the outgoing edges of
2575 ///a single node \c n, then
2576 ///\ref refresh(Node) "refresh(n)" is enough.
2578 Edge operator()(Node s, Node t) const
2582 e!=INVALID&&_g.target(e)!=t;
2583 e = t < _g.target(e)?_left[e]:_right[e]) ;
2589 ///Fast look up of all edges between given endpoints.
2592 ///This class is the same as \ref EdgeLookUp, with the addition
2593 ///that it makes it possible to find all edges between given endpoints.
2595 ///\warning This class is static, so you should refresh() (or at least
2596 ///refresh(Node)) this data structure
2597 ///whenever the graph changes. This is a time consuming (superlinearly
2598 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2600 ///\param G The type of the underlying graph.
2604 class AllEdgeLookUp : public EdgeLookUp<G>
2606 using EdgeLookUp<G>::_g;
2607 using EdgeLookUp<G>::_right;
2608 using EdgeLookUp<G>::_left;
2609 using EdgeLookUp<G>::_head;
2611 GRAPH_TYPEDEFS(typename G);
2614 typename Graph::template EdgeMap<Edge> _next;
2616 Edge refreshNext(Edge head,Edge next=INVALID)
2618 if(head==INVALID) return next;
2620 next=refreshNext(_right[head],next);
2621 // _next[head]=next;
2622 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2624 return refreshNext(_left[head],head);
2630 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2638 ///It builds up the search database, which remains valid until the graph
2640 AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
2642 ///Refresh the data structure at a node.
2644 ///Build up the search database of node \c n.
2646 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2647 ///the number of the outgoing edges of \c n.
2649 void refresh(Node n)
2651 EdgeLookUp<G>::refresh(n);
2652 refreshNext(_head[n]);
2655 ///Refresh the full data structure.
2657 ///Build up the full search database. In fact, it simply calls
2658 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2660 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2661 ///the number of the edges of \c n and <em>D</em> is the maximum
2662 ///out-degree of the graph.
2666 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2669 ///Find an edge between two nodes.
2671 ///Find an edge between two nodes.
2672 ///\param s The source node
2673 ///\param t The target node
2674 ///\param prev The previous edge between \c s and \c t. It it is INVALID or
2675 ///not given, the operator finds the first appropriate edge.
2676 ///\return An edge from \c s to \c t after \c prev or
2677 ///\ref INVALID if there is no more.
2679 ///For example, you can count the number of edges from \c u to \c v in the
2682 ///AllEdgeLookUp<ListGraph> ae(g);
2685 ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2688 ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
2689 /// <em>d</em> is the number of outgoing edges of \c s. Then, the
2690 ///consecutive edges are found in constant time.
2692 ///\warning If you change the graph, refresh() must be called before using
2693 ///this operator. If you change the outgoing edges of
2694 ///a single node \c n, then
2695 ///\ref refresh(Node) "refresh(n)" is enough.
2698 Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
2700 using EdgeLookUp<G>::operator() ;
2701 Edge operator()(Node s, Node t, Edge prev) const
2703 return prev==INVALID?(*this)(s,t):_next[prev];
2711 } //END OF NAMESPACE LEMON