2 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_GRAPH_UTILS_H
18 #define LEMON_GRAPH_UTILS_H
25 #include <lemon/invalid.h>
26 #include <lemon/utility.h>
27 #include <lemon/maps.h>
28 #include <lemon/traits.h>
29 #include <lemon/bits/alteration_notifier.h>
33 ///\brief Graph utilities.
40 /// \addtogroup gutils
43 ///Creates convenience typedefs for the graph types and iterators
45 ///This \c \#define creates convenience typedefs for the following types
46 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
47 ///\c OutEdgeIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
48 ///\c BoolEdgeMap, \c IntEdgeMap, \c DoubleEdgeMap.
49 ///\note If \c G it a template parameter, it should be used in this way.
51 /// GRAPH_TYPEDEFS(typename G)
54 ///\warning There are no typedefs for the graph maps because of the lack of
55 ///template typedefs in C++.
56 #define GRAPH_TYPEDEFS(Graph) \
57 typedef Graph:: Node Node; \
58 typedef Graph:: NodeIt NodeIt; \
59 typedef Graph:: Edge Edge; \
60 typedef Graph:: EdgeIt EdgeIt; \
61 typedef Graph:: InEdgeIt InEdgeIt; \
62 typedef Graph::OutEdgeIt OutEdgeIt;
63 // typedef Graph::template NodeMap<bool> BoolNodeMap;
64 // typedef Graph::template NodeMap<int> IntNodeMap;
65 // typedef Graph::template NodeMap<double> DoubleNodeMap;
66 // typedef Graph::template EdgeMap<bool> BoolEdgeMap;
67 // typedef Graph::template EdgeMap<int> IntEdgeMap;
68 // typedef Graph::template EdgeMap<double> DoubleEdgeMap;
70 ///Creates convenience typedefs for the undirected graph types and iterators
72 ///This \c \#define creates the same convenience typedefs as defined by
73 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
74 ///\c UndirEdge, \c UndirEdgeIt, \c IncEdgeIt,
75 ///\c BoolUndirEdgeMap, \c IntUndirEdgeMap, \c DoubleUndirEdgeMap.
77 ///\note If \c G it a template parameter, it should be used in this way.
79 /// UNDIRGRAPH_TYPEDEFS(typename G)
82 ///\warning There are no typedefs for the graph maps because of the lack of
83 ///template typedefs in C++.
84 #define UNDIRGRAPH_TYPEDEFS(Graph) \
85 GRAPH_TYPEDEFS(Graph) \
86 typedef Graph:: UndirEdge UndirEdge; \
87 typedef Graph:: UndirEdgeIt UndirEdgeIt; \
88 typedef Graph:: IncEdgeIt IncEdgeIt;
89 // typedef Graph::template UndirEdgeMap<bool> BoolUndirEdgeMap;
90 // typedef Graph::template UndirEdgeMap<int> IntUndirEdgeMap;
91 // typedef Graph::template UndirEdgeMap<double> DoubleUndirEdgeMap;
95 /// \brief Function to count the items in the graph.
97 /// This function counts the items (nodes, edges etc) in the graph.
98 /// The complexity of the function is O(n) because
99 /// it iterates on all of the items.
101 template <typename Graph, typename ItemIt>
102 inline int countItems(const Graph& g) {
104 for (ItemIt it(g); it != INVALID; ++it) {
112 template <typename Graph>
113 inline typename enable_if<typename Graph::NodeNumTag, int>::type
114 _countNodes(const Graph &g) {
118 template <typename Graph>
119 inline int _countNodes(Wrap<Graph> w) {
120 return countItems<Graph, typename Graph::NodeIt>(w.value);
123 /// \brief Function to count the nodes in the graph.
125 /// This function counts the nodes in the graph.
126 /// The complexity of the function is O(n) but for some
127 /// graph structures it is specialized to run in O(1).
129 /// \todo refer how to specialize it
131 template <typename Graph>
132 inline int countNodes(const Graph& g) {
133 return _countNodes<Graph>(g);
138 template <typename Graph>
139 inline typename enable_if<typename Graph::EdgeNumTag, int>::type
140 _countEdges(const Graph &g) {
144 template <typename Graph>
145 inline int _countEdges(Wrap<Graph> w) {
146 return countItems<Graph, typename Graph::EdgeIt>(w.value);
149 /// \brief Function to count the edges in the graph.
151 /// This function counts the edges in the graph.
152 /// The complexity of the function is O(e) but for some
153 /// graph structures it is specialized to run in O(1).
155 template <typename Graph>
156 inline int countEdges(const Graph& g) {
157 return _countEdges<Graph>(g);
160 // Undirected edge counting:
162 template <typename Graph>
164 typename enable_if<typename Graph::EdgeNumTag, int>::type
165 _countUndirEdges(const Graph &g) {
166 return g.undirEdgeNum();
169 template <typename Graph>
170 inline int _countUndirEdges(Wrap<Graph> w) {
171 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
174 /// \brief Function to count the undirected edges in the graph.
176 /// This function counts the undirected edges in the graph.
177 /// The complexity of the function is O(e) but for some
178 /// graph structures it is specialized to run in O(1).
180 template <typename Graph>
181 inline int countUndirEdges(const Graph& g) {
182 return _countUndirEdges<Graph>(g);
187 template <typename Graph, typename DegIt>
188 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
190 for (DegIt it(_g, _n); it != INVALID; ++it) {
196 /// \brief Function to count the number of the out-edges from node \c n.
198 /// This function counts the number of the out-edges from node \c n
200 template <typename Graph>
201 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
202 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
205 /// \brief Function to count the number of the in-edges to node \c n.
207 /// This function counts the number of the in-edges to node \c n
209 template <typename Graph>
210 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
211 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
214 /// \brief Function to count the number of the inc-edges to node \c n.
216 /// This function counts the number of the inc-edges to node \c n
218 template <typename Graph>
219 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
220 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
224 template <typename Graph>
226 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
227 _findEdge(const Graph &g,
228 typename Graph::Node u, typename Graph::Node v,
229 typename Graph::Edge prev = INVALID) {
230 return g.findEdge(u, v, prev);
233 template <typename Graph>
234 inline typename Graph::Edge
235 _findEdge(Wrap<Graph> w,
236 typename Graph::Node u,
237 typename Graph::Node v,
238 typename Graph::Edge prev = INVALID) {
239 const Graph& g = w.value;
240 if (prev == INVALID) {
241 typename Graph::OutEdgeIt e(g, u);
242 while (e != INVALID && g.target(e) != v) ++e;
245 typename Graph::OutEdgeIt e(g, prev); ++e;
246 while (e != INVALID && g.target(e) != v) ++e;
251 /// \brief Finds an edge between two nodes of a graph.
253 /// Finds an edge from node \c u to node \c v in graph \c g.
255 /// If \c prev is \ref INVALID (this is the default value), then
256 /// it finds the first edge from \c u to \c v. Otherwise it looks for
257 /// the next edge from \c u to \c v after \c prev.
258 /// \return The found edge or \ref INVALID if there is no such an edge.
260 /// Thus you can iterate through each edge from \c u to \c v as it follows.
262 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
266 // /// \todo We may want to use the "GraphBase"
267 // /// interface here...
268 template <typename Graph>
269 inline typename Graph::Edge findEdge(const Graph &g,
270 typename Graph::Node u,
271 typename Graph::Node v,
272 typename Graph::Edge prev = INVALID) {
273 return _findEdge<Graph>(g, u, v, prev);
276 /// \brief Iterator for iterating on edges connected the same nodes.
278 /// Iterator for iterating on edges connected the same nodes. It is
279 /// higher level interface for the findEdge() function. You can
280 /// use it the following way:
282 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
287 /// \author Balazs Dezso
288 template <typename _Graph>
289 class ConEdgeIt : public _Graph::Edge {
292 typedef _Graph Graph;
293 typedef typename Graph::Edge Parent;
295 typedef typename Graph::Edge Edge;
296 typedef typename Graph::Node Node;
298 /// \brief Constructor.
300 /// Construct a new ConEdgeIt iterating on the edges which
301 /// connects the \c u and \c v node.
302 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
303 Parent::operator=(findEdge(graph, u, v));
306 /// \brief Constructor.
308 /// Construct a new ConEdgeIt which continues the iterating from
310 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
312 /// \brief Increment operator.
314 /// It increments the iterator and gives back the next edge.
315 ConEdgeIt& operator++() {
316 Parent::operator=(findEdge(graph, graph.source(*this),
317 graph.target(*this), *this));
324 template <typename Graph>
327 typename Graph::FindEdgeTag,
328 typename Graph::UndirEdge>::type
329 _findUndirEdge(const Graph &g,
330 typename Graph::Node u, typename Graph::Node v,
331 typename Graph::UndirEdge prev = INVALID) {
332 return g.findUndirEdge(u, v, prev);
335 template <typename Graph>
336 inline typename Graph::UndirEdge
337 _findUndirEdge(Wrap<Graph> w,
338 typename Graph::Node u,
339 typename Graph::Node v,
340 typename Graph::UndirEdge prev = INVALID) {
341 const Graph& g = w.value;
342 if (prev == INVALID) {
343 typename Graph::OutEdgeIt e(g, u);
344 while (e != INVALID && g.target(e) != v) ++e;
347 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
348 while (e != INVALID && g.target(e) != v) ++e;
353 /// \brief Finds an undir edge between two nodes of a graph.
355 /// Finds an undir edge from node \c u to node \c v in graph \c g.
357 /// If \c prev is \ref INVALID (this is the default value), then
358 /// it finds the first edge from \c u to \c v. Otherwise it looks for
359 /// the next edge from \c u to \c v after \c prev.
360 /// \return The found edge or \ref INVALID if there is no such an edge.
362 /// Thus you can iterate through each edge from \c u to \c v as it follows.
364 /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
365 /// e = findUndirEdge(g,u,v,e)) {
369 // /// \todo We may want to use the "GraphBase"
370 // /// interface here...
371 template <typename Graph>
372 inline typename Graph::UndirEdge
373 findUndirEdge(const Graph &g,
374 typename Graph::Node u,
375 typename Graph::Node v,
376 typename Graph::UndirEdge prev = INVALID) {
377 return _findUndirEdge<Graph>(g, u, v, prev);
380 /// \brief Iterator for iterating on undir edges connected the same nodes.
382 /// Iterator for iterating on undir edges connected the same nodes. It is
383 /// higher level interface for the findUndirEdge() function. You can
384 /// use it the following way:
386 /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
391 /// \author Balazs Dezso
392 template <typename _Graph>
393 class ConUndirEdgeIt : public _Graph::UndirEdge {
396 typedef _Graph Graph;
397 typedef typename Graph::UndirEdge Parent;
399 typedef typename Graph::UndirEdge UndirEdge;
400 typedef typename Graph::Node Node;
402 /// \brief Constructor.
404 /// Construct a new ConUndirEdgeIt iterating on the edges which
405 /// connects the \c u and \c v node.
406 ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
407 Parent::operator=(findUndirEdge(graph, u, v));
410 /// \brief Constructor.
412 /// Construct a new ConUndirEdgeIt which continues the iterating from
414 ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
416 /// \brief Increment operator.
418 /// It increments the iterator and gives back the next edge.
419 ConUndirEdgeIt& operator++() {
420 Parent::operator=(findUndirEdge(graph, graph.source(*this),
421 graph.target(*this), *this));
428 /// \brief Copy a map.
430 /// This function copies the \c source map to the \c target map. It uses the
431 /// given iterator to iterate on the data structure and it uses the \c ref
432 /// mapping to convert the source's keys to the target's keys.
433 template <typename Target, typename Source,
434 typename ItemIt, typename Ref>
435 void copyMap(Target& target, const Source& source,
436 ItemIt it, const Ref& ref) {
437 for (; it != INVALID; ++it) {
438 target[ref[it]] = source[it];
442 /// \brief Copy the source map to the target map.
444 /// Copy the \c source map to the \c target map. It uses the given iterator
445 /// to iterate on the data structure.
446 template <typename Target, typename Source,
448 void copyMap(Target& target, const Source& source, ItemIt it) {
449 for (; it != INVALID; ++it) {
450 target[it] = source[it];
454 /// \brief Class to copy a graph.
456 /// Class to copy a graph to an other graph (duplicate a graph). The
457 /// simplest way of using it is through the \c copyGraph() function.
458 template <typename Target, typename Source>
461 typedef typename Source::Node Node;
462 typedef typename Source::NodeIt NodeIt;
463 typedef typename Source::Edge Edge;
464 typedef typename Source::EdgeIt EdgeIt;
466 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
467 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
469 /// \brief Constructor for the GraphCopy.
471 /// It copies the content of the \c _source graph into the
472 /// \c _target graph. It creates also two references, one beetween
473 /// the two nodeset and one beetween the two edgesets.
474 GraphCopy(Target& _target, const Source& _source)
475 : source(_source), target(_target),
476 nodeRefMap(_source), edgeRefMap(_source) {
477 for (NodeIt it(source); it != INVALID; ++it) {
478 nodeRefMap[it] = target.addNode();
480 for (EdgeIt it(source); it != INVALID; ++it) {
481 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
482 nodeRefMap[source.target(it)]);
486 /// \brief Copies the node references into the given map.
488 /// Copies the node references into the given map.
489 template <typename NodeRef>
490 const GraphCopy& nodeRef(NodeRef& map) const {
491 for (NodeIt it(source); it != INVALID; ++it) {
492 map.set(it, nodeRefMap[it]);
497 /// \brief Reverse and copies the node references into the given map.
499 /// Reverse and copies the node references into the given map.
500 template <typename NodeRef>
501 const GraphCopy& nodeCrossRef(NodeRef& map) const {
502 for (NodeIt it(source); it != INVALID; ++it) {
503 map.set(nodeRefMap[it], it);
508 /// \brief Copies the edge references into the given map.
510 /// Copies the edge references into the given map.
511 template <typename EdgeRef>
512 const GraphCopy& edgeRef(EdgeRef& map) const {
513 for (EdgeIt it(source); it != INVALID; ++it) {
514 map.set(it, edgeRefMap[it]);
519 /// \brief Reverse and copies the edge references into the given map.
521 /// Reverse and copies the edge references into the given map.
522 template <typename EdgeRef>
523 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
524 for (EdgeIt it(source); it != INVALID; ++it) {
525 map.set(edgeRefMap[it], it);
530 /// \brief Make copy of the given map.
532 /// Makes copy of the given map for the newly created graph.
533 /// The new map's key type is the target graph's node type,
534 /// and the copied map's key type is the source graph's node
536 template <typename TargetMap, typename SourceMap>
537 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
538 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
542 /// \brief Make copy of the given map.
544 /// Makes copy of the given map for the newly created graph.
545 /// The new map's key type is the target graph's edge type,
546 /// and the copied map's key type is the source graph's edge
548 template <typename TargetMap, typename SourceMap>
549 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
550 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
554 /// \brief Gives back the stored node references.
556 /// Gives back the stored node references.
557 const NodeRefMap& nodeRef() const {
561 /// \brief Gives back the stored edge references.
563 /// Gives back the stored edge references.
564 const EdgeRefMap& edgeRef() const {
572 const Source& source;
575 NodeRefMap nodeRefMap;
576 EdgeRefMap edgeRefMap;
579 /// \brief Copy a graph to an other graph.
581 /// Copy a graph to an other graph.
582 /// The usage of the function:
585 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
588 /// After the copy the \c nr map will contain the mapping from the
589 /// source graph's nodes to the target graph's nodes and the \c ecr will
590 /// contain the mapping from the target graph's edges to the source's
592 template <typename Target, typename Source>
593 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
594 return GraphCopy<Target, Source>(target, source);
597 /// \brief Class to copy an undirected graph.
599 /// Class to copy an undirected graph to an other graph (duplicate a graph).
600 /// The simplest way of using it is through the \c copyUndirGraph() function.
601 template <typename Target, typename Source>
602 class UndirGraphCopy {
604 typedef typename Source::Node Node;
605 typedef typename Source::NodeIt NodeIt;
606 typedef typename Source::Edge Edge;
607 typedef typename Source::EdgeIt EdgeIt;
608 typedef typename Source::UndirEdge UndirEdge;
609 typedef typename Source::UndirEdgeIt UndirEdgeIt;
611 typedef typename Source::
612 template NodeMap<typename Target::Node> NodeRefMap;
614 typedef typename Source::
615 template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
620 EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
621 typedef typename Source::Edge Key;
622 typedef typename Target::Edge Value;
624 Value operator[](const Key& key) {
625 return gc.target.direct(gc.undirEdgeRef[key],
626 gc.target.direction(key));
634 /// \brief Constructor for the UndirGraphCopy.
636 /// It copies the content of the \c _source graph into the
637 /// \c _target graph. It creates also two references, one beetween
638 /// the two nodeset and one beetween the two edgesets.
639 UndirGraphCopy(Target& _target, const Source& _source)
640 : source(_source), target(_target),
641 nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
642 for (NodeIt it(source); it != INVALID; ++it) {
643 nodeRefMap[it] = target.addNode();
645 for (UndirEdgeIt it(source); it != INVALID; ++it) {
646 undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
647 nodeRefMap[source.target(it)]);
651 /// \brief Copies the node references into the given map.
653 /// Copies the node references into the given map.
654 template <typename NodeRef>
655 const UndirGraphCopy& nodeRef(NodeRef& map) const {
656 for (NodeIt it(source); it != INVALID; ++it) {
657 map.set(it, nodeRefMap[it]);
662 /// \brief Reverse and copies the node references into the given map.
664 /// Reverse and copies the node references into the given map.
665 template <typename NodeRef>
666 const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
667 for (NodeIt it(source); it != INVALID; ++it) {
668 map.set(nodeRefMap[it], it);
673 /// \brief Copies the edge references into the given map.
675 /// Copies the edge references into the given map.
676 template <typename EdgeRef>
677 const UndirGraphCopy& edgeRef(EdgeRef& map) const {
678 for (EdgeIt it(source); it != INVALID; ++it) {
679 map.set(edgeRefMap[it], it);
684 /// \brief Reverse and copies the undirected edge references into the
687 /// Reverse and copies the undirected edge references into the given map.
688 template <typename EdgeRef>
689 const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
690 for (EdgeIt it(source); it != INVALID; ++it) {
691 map.set(it, edgeRefMap[it]);
696 /// \brief Copies the undirected edge references into the given map.
698 /// Copies the undirected edge references into the given map.
699 template <typename EdgeRef>
700 const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
701 for (UndirEdgeIt it(source); it != INVALID; ++it) {
702 map.set(it, undirEdgeRefMap[it]);
707 /// \brief Reverse and copies the undirected edge references into the
710 /// Reverse and copies the undirected edge references into the given map.
711 template <typename EdgeRef>
712 const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
713 for (UndirEdgeIt it(source); it != INVALID; ++it) {
714 map.set(undirEdgeRefMap[it], it);
719 /// \brief Make copy of the given map.
721 /// Makes copy of the given map for the newly created graph.
722 /// The new map's key type is the target graph's node type,
723 /// and the copied map's key type is the source graph's node
725 template <typename TargetMap, typename SourceMap>
726 const UndirGraphCopy& nodeMap(TargetMap& tMap,
727 const SourceMap& sMap) const {
728 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
732 /// \brief Make copy of the given map.
734 /// Makes copy of the given map for the newly created graph.
735 /// The new map's key type is the target graph's edge type,
736 /// and the copied map's key type is the source graph's edge
738 template <typename TargetMap, typename SourceMap>
739 const UndirGraphCopy& edgeMap(TargetMap& tMap,
740 const SourceMap& sMap) const {
741 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
745 /// \brief Make copy of the given map.
747 /// Makes copy of the given map for the newly created graph.
748 /// The new map's key type is the target graph's edge type,
749 /// and the copied map's key type is the source graph's edge
751 template <typename TargetMap, typename SourceMap>
752 const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
753 const SourceMap& sMap) const {
754 copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
758 /// \brief Gives back the stored node references.
760 /// Gives back the stored node references.
761 const NodeRefMap& nodeRef() const {
765 /// \brief Gives back the stored edge references.
767 /// Gives back the stored edge references.
768 const EdgeRefMap& edgeRef() const {
772 /// \brief Gives back the stored undir edge references.
774 /// Gives back the stored undir edge references.
775 const UndirEdgeRefMap& undirEdgeRef() const {
776 return undirEdgeRefMap;
783 const Source& source;
786 NodeRefMap nodeRefMap;
787 EdgeRefMap edgeRefMap;
788 UndirEdgeRefMap undirEdgeRefMap;
791 /// \brief Copy a graph to an other graph.
793 /// Copy a graph to an other graph.
794 /// The usage of the function:
797 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
800 /// After the copy the \c nr map will contain the mapping from the
801 /// source graph's nodes to the target graph's nodes and the \c ecr will
802 /// contain the mapping from the target graph's edges to the source's
804 template <typename Target, typename Source>
805 UndirGraphCopy<Target, Source>
806 copyUndirGraph(Target& target, const Source& source) {
807 return UndirGraphCopy<Target, Source>(target, source);
813 /// \addtogroup graph_maps
816 /// Provides an immutable and unique id for each item in the graph.
818 /// The IdMap class provides a unique and immutable id for each item of the
819 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
820 /// different items (nodes) get different ids <li>\b immutable: the id of an
821 /// item (node) does not change (even if you delete other nodes). </ul>
822 /// Through this map you get access (i.e. can read) the inner id values of
823 /// the items stored in the graph. This map can be inverted with its member
824 /// class \c InverseMap.
826 template <typename _Graph, typename _Item>
829 typedef _Graph Graph;
834 /// \brief Constructor.
836 /// Constructor for creating id map.
837 IdMap(const Graph& _graph) : graph(&_graph) {}
839 /// \brief Gives back the \e id of the item.
841 /// Gives back the immutable and unique \e id of the map.
842 int operator[](const Item& item) const { return graph->id(item);}
850 /// \brief The class represents the inverse of its owner (IdMap).
852 /// The class represents the inverse of its owner (IdMap).
857 /// \brief Constructor.
859 /// Constructor for creating an id-to-item map.
860 InverseMap(const Graph& _graph) : graph(&_graph) {}
862 /// \brief Constructor.
864 /// Constructor for creating an id-to-item map.
865 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
867 /// \brief Gives back the given item from its id.
869 /// Gives back the given item from its id.
871 Item operator[](int id) const { return graph->fromId(id, Item());}
876 /// \brief Gives back the inverse of the map.
878 /// Gives back the inverse of the IdMap.
879 InverseMap inverse() const { return InverseMap(*graph);}
884 /// \brief General invertable graph-map type.
886 /// This type provides simple invertable graph-maps.
887 /// The InvertableMap wraps an arbitrary ReadWriteMap
888 /// and if a key is set to a new value then store it
889 /// in the inverse map.
890 /// \param _Graph The graph type.
891 /// \param _Map The map to extend with invertable functionality.
897 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
899 class InvertableMap : protected _Map {
904 typedef _Graph Graph;
906 /// The key type of InvertableMap (Node, Edge, UndirEdge).
907 typedef typename _Map::Key Key;
908 /// The value type of the InvertableMap.
909 typedef typename _Map::Value Value;
911 /// \brief Constructor.
913 /// Construct a new InvertableMap for the graph.
915 InvertableMap(const Graph& graph) : Map(graph) {}
917 /// \brief The setter function of the map.
919 /// Sets the mapped value.
920 void set(const Key& key, const Value& val) {
921 Value oldval = Map::operator[](key);
922 typename Container::iterator it = invMap.find(oldval);
923 if (it != invMap.end() && it->second == key) {
926 invMap.insert(make_pair(val, key));
930 /// \brief The getter function of the map.
932 /// It gives back the value associated with the key.
933 Value operator[](const Key& key) const {
934 return Map::operator[](key);
939 /// \brief Erase the key from the map.
941 /// Erase the key to the map. It is called by the
942 /// \c AlterationNotifier.
943 virtual void erase(const Key& key) {
944 Value val = Map::operator[](key);
945 typename Container::iterator it = invMap.find(val);
946 if (it != invMap.end() && it->second == key) {
952 /// \brief Erase more keys from the map.
954 /// Erase more keys from the map. It is called by the
955 /// \c AlterationNotifier.
956 virtual void erase(const std::vector<Key>& keys) {
957 for (int i = 0; i < (int)keys.size(); ++i) {
958 Value val = Map::operator[](keys[i]);
959 typename Container::iterator it = invMap.find(val);
960 if (it != invMap.end() && it->second == keys[i]) {
967 /// \brief Clear the keys from the map and inverse map.
969 /// Clear the keys from the map and inverse map. It is called by the
970 /// \c AlterationNotifier.
971 virtual void clear() {
978 typedef std::map<Value, Key> Container;
983 /// \brief The inverse map type.
985 /// The inverse of this map. The subscript operator of the map
986 /// gives back always the item what was last assigned to the value.
989 /// \brief Constructor of the InverseMap.
991 /// Constructor of the InverseMap.
992 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
994 /// The value type of the InverseMap.
995 typedef typename InvertableMap::Key Value;
996 /// The key type of the InverseMap.
997 typedef typename InvertableMap::Value Key;
999 /// \brief Subscript operator.
1001 /// Subscript operator. It gives back always the item
1002 /// what was last assigned to the value.
1003 Value operator[](const Key& key) const {
1004 typename Container::const_iterator it = inverted.invMap.find(key);
1009 const InvertableMap& inverted;
1012 /// \brief It gives back the just readeable inverse map.
1014 /// It gives back the just readeable inverse map.
1015 InverseMap inverse() const {
1016 return InverseMap(*this);
1023 /// \brief Provides a mutable, continuous and unique descriptor for each
1024 /// item in the graph.
1026 /// The DescriptorMap class provides a unique and continuous (but mutable)
1027 /// descriptor (id) for each item of the same type (e.g. node) in the
1028 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1029 /// different ids <li>\b continuous: the range of the ids is the set of
1030 /// integers between 0 and \c n-1, where \c n is the number of the items of
1031 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1032 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1033 /// with its member class \c InverseMap.
1035 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1036 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1038 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1043 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
1045 class DescriptorMap : protected _Map {
1051 /// The graph class of DescriptorMap.
1052 typedef _Graph Graph;
1054 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1055 typedef typename _Map::Key Key;
1056 /// The value type of DescriptorMap.
1057 typedef typename _Map::Value Value;
1059 /// \brief Constructor.
1061 /// Constructor for descriptor map.
1062 DescriptorMap(const Graph& _graph) : Map(_graph) {
1068 /// \brief Add a new key to the map.
1070 /// Add a new key to the map. It is called by the
1071 /// \c AlterationNotifier.
1072 virtual void add(const Item& item) {
1074 Map::set(item, invMap.size());
1075 invMap.push_back(item);
1078 /// \brief Add more new keys to the map.
1080 /// Add more new keys to the map. It is called by the
1081 /// \c AlterationNotifier.
1082 virtual void add(const std::vector<Item>& items) {
1084 for (int i = 0; i < (int)items.size(); ++i) {
1085 Map::set(items[i], invMap.size());
1086 invMap.push_back(items[i]);
1090 /// \brief Erase the key from the map.
1092 /// Erase the key from the map. It is called by the
1093 /// \c AlterationNotifier.
1094 virtual void erase(const Item& item) {
1095 Map::set(invMap.back(), Map::operator[](item));
1096 invMap[Map::operator[](item)] = invMap.back();
1101 /// \brief Erase more keys from the map.
1103 /// Erase more keys from the map. It is called by the
1104 /// \c AlterationNotifier.
1105 virtual void erase(const std::vector<Item>& items) {
1106 for (int i = 0; i < (int)items.size(); ++i) {
1107 Map::set(invMap.back(), Map::operator[](items[i]));
1108 invMap[Map::operator[](items[i])] = invMap.back();
1114 /// \brief Build the unique map.
1116 /// Build the unique map. It is called by the
1117 /// \c AlterationNotifier.
1118 virtual void build() {
1121 const typename Map::Graph* graph = Map::getGraph();
1122 for (graph->first(it); it != INVALID; graph->next(it)) {
1123 Map::set(it, invMap.size());
1124 invMap.push_back(it);
1128 /// \brief Clear the keys from the map.
1130 /// Clear the keys from the map. It is called by the
1131 /// \c AlterationNotifier.
1132 virtual void clear() {
1139 /// \brief Swaps the position of the two items in the map.
1141 /// Swaps the position of the two items in the map.
1142 void swap(const Item& p, const Item& q) {
1143 int pi = Map::operator[](p);
1144 int qi = Map::operator[](q);
1151 /// \brief Gives back the \e descriptor of the item.
1153 /// Gives back the mutable and unique \e descriptor of the map.
1154 int operator[](const Item& item) const {
1155 return Map::operator[](item);
1160 typedef std::vector<Item> Container;
1164 /// \brief The inverse map type of DescriptorMap.
1166 /// The inverse map type of DescriptorMap.
1169 /// \brief Constructor of the InverseMap.
1171 /// Constructor of the InverseMap.
1172 InverseMap(const DescriptorMap& _inverted)
1173 : inverted(_inverted) {}
1176 /// The value type of the InverseMap.
1177 typedef typename DescriptorMap::Key Value;
1178 /// The key type of the InverseMap.
1179 typedef typename DescriptorMap::Value Key;
1181 /// \brief Subscript operator.
1183 /// Subscript operator. It gives back the item
1184 /// that the descriptor belongs to currently.
1185 Value operator[](const Key& key) const {
1186 return inverted.invMap[key];
1189 /// \brief Size of the map.
1191 /// Returns the size of the map.
1193 return inverted.invMap.size();
1197 const DescriptorMap& inverted;
1200 /// \brief Gives back the inverse of the map.
1202 /// Gives back the inverse of the map.
1203 const InverseMap inverse() const {
1204 return InverseMap(*this);
1208 /// \brief Returns the source of the given edge.
1210 /// The SourceMap gives back the source Node of the given edge.
1211 /// \author Balazs Dezso
1212 template <typename Graph>
1216 typedef typename Graph::Node Value;
1217 typedef typename Graph::Edge Key;
1219 /// \brief Constructor
1222 /// \param _graph The graph that the map belongs to.
1223 SourceMap(const Graph& _graph) : graph(_graph) {}
1225 /// \brief The subscript operator.
1227 /// The subscript operator.
1228 /// \param edge The edge
1229 /// \return The source of the edge
1230 Value operator[](const Key& edge) const {
1231 return graph.source(edge);
1238 /// \brief Returns a \ref SourceMap class
1240 /// This function just returns an \ref SourceMap class.
1241 /// \relates SourceMap
1242 template <typename Graph>
1243 inline SourceMap<Graph> sourceMap(const Graph& graph) {
1244 return SourceMap<Graph>(graph);
1247 /// \brief Returns the target of the given edge.
1249 /// The TargetMap gives back the target Node of the given edge.
1250 /// \author Balazs Dezso
1251 template <typename Graph>
1255 typedef typename Graph::Node Value;
1256 typedef typename Graph::Edge Key;
1258 /// \brief Constructor
1261 /// \param _graph The graph that the map belongs to.
1262 TargetMap(const Graph& _graph) : graph(_graph) {}
1264 /// \brief The subscript operator.
1266 /// The subscript operator.
1267 /// \param e The edge
1268 /// \return The target of the edge
1269 Value operator[](const Key& e) const {
1270 return graph.target(e);
1277 /// \brief Returns a \ref TargetMap class
1279 /// This function just returns a \ref TargetMap class.
1280 /// \relates TargetMap
1281 template <typename Graph>
1282 inline TargetMap<Graph> targetMap(const Graph& graph) {
1283 return TargetMap<Graph>(graph);
1286 /// \brief Returns the "forward" directed edge view of an undirected edge.
1288 /// Returns the "forward" directed edge view of an undirected edge.
1289 /// \author Balazs Dezso
1290 template <typename Graph>
1294 typedef typename Graph::Edge Value;
1295 typedef typename Graph::UndirEdge Key;
1297 /// \brief Constructor
1300 /// \param _graph The graph that the map belongs to.
1301 ForwardMap(const Graph& _graph) : graph(_graph) {}
1303 /// \brief The subscript operator.
1305 /// The subscript operator.
1306 /// \param key An undirected edge
1307 /// \return The "forward" directed edge view of undirected edge
1308 Value operator[](const Key& key) const {
1309 return graph.direct(key, true);
1316 /// \brief Returns a \ref ForwardMap class
1318 /// This function just returns an \ref ForwardMap class.
1319 /// \relates ForwardMap
1320 template <typename Graph>
1321 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1322 return ForwardMap<Graph>(graph);
1325 /// \brief Returns the "backward" directed edge view of an undirected edge.
1327 /// Returns the "backward" directed edge view of an undirected edge.
1328 /// \author Balazs Dezso
1329 template <typename Graph>
1333 typedef typename Graph::Edge Value;
1334 typedef typename Graph::UndirEdge Key;
1336 /// \brief Constructor
1339 /// \param _graph The graph that the map belongs to.
1340 BackwardMap(const Graph& _graph) : graph(_graph) {}
1342 /// \brief The subscript operator.
1344 /// The subscript operator.
1345 /// \param key An undirected edge
1346 /// \return The "backward" directed edge view of undirected edge
1347 Value operator[](const Key& key) const {
1348 return graph.direct(key, false);
1355 /// \brief Returns a \ref BackwardMap class
1357 /// This function just returns a \ref BackwardMap class.
1358 /// \relates BackwardMap
1359 template <typename Graph>
1360 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1361 return BackwardMap<Graph>(graph);
1364 /// \brief Potential difference map
1366 /// If there is an potential map on the nodes then we
1367 /// can get an edge map as we get the substraction of the
1368 /// values of the target and source.
1369 template <typename Graph, typename NodeMap>
1370 class PotentialDifferenceMap {
1372 typedef typename Graph::Edge Key;
1373 typedef typename NodeMap::Value Value;
1375 /// \brief Constructor
1377 /// Contructor of the map
1378 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1379 : graph(_graph), potential(_potential) {}
1381 /// \brief Const subscription operator
1383 /// Const subscription operator
1384 Value operator[](const Key& edge) const {
1385 return potential[graph.target(edge)] - potential[graph.source(edge)];
1390 const NodeMap& potential;
1393 /// \brief Just returns a PotentialDifferenceMap
1395 /// Just returns a PotentialDifferenceMap
1396 /// \relates PotentialDifferenceMap
1397 template <typename Graph, typename NodeMap>
1398 PotentialDifferenceMap<Graph, NodeMap>
1399 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1400 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1403 /// \brief Map of the node in-degrees.
1405 /// This map returns the in-degree of a node. Once it is constructed,
1406 /// the degrees are stored in a standard NodeMap, so each query is done
1407 /// in constant time. On the other hand, the values are updated automatically
1408 /// whenever the graph changes.
1410 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1411 /// alternative ways to modify the graph. The correct behavior of InDegMap
1412 /// is not guarantied if these additional features are used. For example
1413 /// the functions \ref ListGraph::changeSource() "changeSource()",
1414 /// \ref ListGraph::changeTarget() "changeTarget()" and
1415 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1416 /// of \ref ListGraph will \e not update the degree values correctly.
1420 template <typename _Graph>
1422 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1426 typedef _Graph Graph;
1428 typedef typename Graph::Node Key;
1432 class AutoNodeMap : public Graph::template NodeMap<int> {
1435 typedef typename Graph::template NodeMap<int> Parent;
1437 typedef typename Parent::Key Key;
1438 typedef typename Parent::Value Value;
1440 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1442 virtual void add(const Key& key) {
1444 Parent::set(key, 0);
1446 virtual void add(const std::vector<Key>& keys) {
1448 for (int i = 0; i < (int)keys.size(); ++i) {
1449 Parent::set(keys[i], 0);
1456 /// \brief Constructor.
1458 /// Constructor for creating in-degree map.
1459 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1460 AlterationNotifier<typename _Graph::Edge>
1461 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1463 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1464 deg[it] = countInEdges(graph, it);
1468 virtual ~InDegMap() {
1469 AlterationNotifier<typename _Graph::Edge>::
1470 ObserverBase::detach();
1473 /// Gives back the in-degree of a Node.
1474 int operator[](const Key& key) const {
1480 typedef typename Graph::Edge Edge;
1482 virtual void add(const Edge& edge) {
1483 ++deg[graph.target(edge)];
1486 virtual void erase(const Edge& edge) {
1487 --deg[graph.target(edge)];
1490 virtual void build() {
1491 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1492 deg[it] = countInEdges(graph, it);
1496 virtual void clear() {
1497 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1503 const _Graph& graph;
1507 /// \brief Map of the node out-degrees.
1509 /// This map returns the out-degree of a node. Once it is constructed,
1510 /// the degrees are stored in a standard NodeMap, so each query is done
1511 /// in constant time. On the other hand, the values are updated automatically
1512 /// whenever the graph changes.
1514 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1515 /// alternative ways to modify the graph. The correct behavior of OutDegMap
1516 /// is not guarantied if these additional features are used. For example
1517 /// the functions \ref ListGraph::changeSource() "changeSource()",
1518 /// \ref ListGraph::changeTarget() "changeTarget()" and
1519 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1520 /// of \ref ListGraph will \e not update the degree values correctly.
1524 template <typename _Graph>
1526 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1530 typedef _Graph Graph;
1532 typedef typename Graph::Node Key;
1536 class AutoNodeMap : public Graph::template NodeMap<int> {
1539 typedef typename Graph::template NodeMap<int> Parent;
1541 typedef typename Parent::Key Key;
1542 typedef typename Parent::Value Value;
1544 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1546 virtual void add(const Key& key) {
1548 Parent::set(key, 0);
1550 virtual void add(const std::vector<Key>& keys) {
1552 for (int i = 0; i < (int)keys.size(); ++i) {
1553 Parent::set(keys[i], 0);
1560 /// \brief Constructor.
1562 /// Constructor for creating out-degree map.
1563 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1564 AlterationNotifier<typename _Graph::Edge>
1565 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1567 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1568 deg[it] = countOutEdges(graph, it);
1572 virtual ~OutDegMap() {
1573 AlterationNotifier<typename _Graph::Edge>::
1574 ObserverBase::detach();
1577 /// Gives back the in-degree of a Node.
1578 int operator[](const Key& key) const {
1584 typedef typename Graph::Edge Edge;
1586 virtual void add(const Edge& edge) {
1587 ++deg[graph.source(edge)];
1590 virtual void erase(const Edge& edge) {
1591 --deg[graph.source(edge)];
1594 virtual void build() {
1595 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1596 deg[it] = countOutEdges(graph, it);
1600 virtual void clear() {
1601 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1607 const _Graph& graph;
1614 } //END OF NAMESPACE LEMON