Do not append -Wall -W to CXXFLAGS when it is set on the commandline.
2 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 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, typename ItemIt>
447 void copyMap(Target& target, const Source& source, ItemIt it) {
448 for (; it != INVALID; ++it) {
449 target[it] = source[it];
453 /// \brief Class to copy a graph.
455 /// Class to copy a graph to an other graph (duplicate a graph). The
456 /// simplest way of using it is through the \c copyGraph() function.
457 template <typename Target, typename Source>
460 typedef typename Source::Node Node;
461 typedef typename Source::NodeIt NodeIt;
462 typedef typename Source::Edge Edge;
463 typedef typename Source::EdgeIt EdgeIt;
465 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
466 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
468 /// \brief Constructor for the GraphCopy.
470 /// It copies the content of the \c _source graph into the
471 /// \c _target graph. It creates also two references, one beetween
472 /// the two nodeset and one beetween the two edgesets.
473 GraphCopy(Target& _target, const Source& _source)
474 : source(_source), target(_target),
475 nodeRefMap(_source), edgeRefMap(_source) {
476 for (NodeIt it(source); it != INVALID; ++it) {
477 nodeRefMap[it] = target.addNode();
479 for (EdgeIt it(source); it != INVALID; ++it) {
480 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
481 nodeRefMap[source.target(it)]);
485 /// \brief Copies the node references into the given map.
487 /// Copies the node references into the given map.
488 template <typename NodeRef>
489 const GraphCopy& nodeRef(NodeRef& map) const {
490 for (NodeIt it(source); it != INVALID; ++it) {
491 map.set(it, nodeRefMap[it]);
496 /// \brief Reverse and copies the node references into the given map.
498 /// Reverse and copies the node references into the given map.
499 template <typename NodeRef>
500 const GraphCopy& nodeCrossRef(NodeRef& map) const {
501 for (NodeIt it(source); it != INVALID; ++it) {
502 map.set(nodeRefMap[it], it);
507 /// \brief Copies the edge references into the given map.
509 /// Copies the edge references into the given map.
510 template <typename EdgeRef>
511 const GraphCopy& edgeRef(EdgeRef& map) const {
512 for (EdgeIt it(source); it != INVALID; ++it) {
513 map.set(it, edgeRefMap[it]);
518 /// \brief Reverse and copies the edge references into the given map.
520 /// Reverse and copies the edge references into the given map.
521 template <typename EdgeRef>
522 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
523 for (EdgeIt it(source); it != INVALID; ++it) {
524 map.set(edgeRefMap[it], it);
529 /// \brief Make copy of the given map.
531 /// Makes copy of the given map for the newly created graph.
532 /// The new map's key type is the target graph's node type,
533 /// and the copied map's key type is the source graph's node
535 template <typename TargetMap, typename SourceMap>
536 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
537 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
541 /// \brief Make copy of the given map.
543 /// Makes copy of the given map for the newly created graph.
544 /// The new map's key type is the target graph's edge type,
545 /// and the copied map's key type is the source graph's edge
547 template <typename TargetMap, typename SourceMap>
548 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
549 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
553 /// \brief Gives back the stored node references.
555 /// Gives back the stored node references.
556 const NodeRefMap& nodeRef() const {
560 /// \brief Gives back the stored edge references.
562 /// Gives back the stored edge references.
563 const EdgeRefMap& edgeRef() const {
571 const Source& source;
574 NodeRefMap nodeRefMap;
575 EdgeRefMap edgeRefMap;
578 /// \brief Copy a graph to an other graph.
580 /// Copy a graph to an other graph.
581 /// The usage of the function:
584 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
587 /// After the copy the \c nr map will contain the mapping from the
588 /// source graph's nodes to the target graph's nodes and the \c ecr will
589 /// contain the mapping from the target graph's edges to the source's
591 template <typename Target, typename Source>
592 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
593 return GraphCopy<Target, Source>(target, source);
596 /// \brief Class to copy an undirected graph.
598 /// Class to copy an undirected graph to an other graph (duplicate a graph).
599 /// The simplest way of using it is through the \c copyUndirGraph() function.
600 template <typename Target, typename Source>
601 class UndirGraphCopy {
603 typedef typename Source::Node Node;
604 typedef typename Source::NodeIt NodeIt;
605 typedef typename Source::Edge Edge;
606 typedef typename Source::EdgeIt EdgeIt;
607 typedef typename Source::UndirEdge UndirEdge;
608 typedef typename Source::UndirEdgeIt UndirEdgeIt;
610 typedef typename Source::
611 template NodeMap<typename Target::Node> NodeRefMap;
613 typedef typename Source::
614 template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
619 EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
620 typedef typename Source::Edge Key;
621 typedef typename Target::Edge Value;
623 Value operator[](const Key& key) {
624 return gc.target.direct(gc.undirEdgeRef[key],
625 gc.target.direction(key));
633 /// \brief Constructor for the UndirGraphCopy.
635 /// It copies the content of the \c _source graph into the
636 /// \c _target graph. It creates also two references, one beetween
637 /// the two nodeset and one beetween the two edgesets.
638 UndirGraphCopy(Target& _target, const Source& _source)
639 : source(_source), target(_target),
640 nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
641 for (NodeIt it(source); it != INVALID; ++it) {
642 nodeRefMap[it] = target.addNode();
644 for (UndirEdgeIt it(source); it != INVALID; ++it) {
645 undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
646 nodeRefMap[source.target(it)]);
650 /// \brief Copies the node references into the given map.
652 /// Copies the node references into the given map.
653 template <typename NodeRef>
654 const UndirGraphCopy& nodeRef(NodeRef& map) const {
655 for (NodeIt it(source); it != INVALID; ++it) {
656 map.set(it, nodeRefMap[it]);
661 /// \brief Reverse and copies the node references into the given map.
663 /// Reverse and copies the node references into the given map.
664 template <typename NodeRef>
665 const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
666 for (NodeIt it(source); it != INVALID; ++it) {
667 map.set(nodeRefMap[it], it);
672 /// \brief Copies the edge references into the given map.
674 /// Copies the edge references into the given map.
675 template <typename EdgeRef>
676 const UndirGraphCopy& edgeRef(EdgeRef& map) const {
677 for (EdgeIt it(source); it != INVALID; ++it) {
678 map.set(edgeRefMap[it], it);
683 /// \brief Reverse and copies the undirected edge references into the
686 /// Reverse and copies the undirected edge references into the given map.
687 template <typename EdgeRef>
688 const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
689 for (EdgeIt it(source); it != INVALID; ++it) {
690 map.set(it, edgeRefMap[it]);
695 /// \brief Copies the undirected edge references into the given map.
697 /// Copies the undirected edge references into the given map.
698 template <typename EdgeRef>
699 const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
700 for (UndirEdgeIt it(source); it != INVALID; ++it) {
701 map.set(it, undirEdgeRefMap[it]);
706 /// \brief Reverse and copies the undirected edge references into the
709 /// Reverse and copies the undirected edge references into the given map.
710 template <typename EdgeRef>
711 const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
712 for (UndirEdgeIt it(source); it != INVALID; ++it) {
713 map.set(undirEdgeRefMap[it], it);
718 /// \brief Make copy of the given map.
720 /// Makes copy of the given map for the newly created graph.
721 /// The new map's key type is the target graph's node type,
722 /// and the copied map's key type is the source graph's node
724 template <typename TargetMap, typename SourceMap>
725 const UndirGraphCopy& nodeMap(TargetMap& tMap,
726 const SourceMap& sMap) const {
727 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
731 /// \brief Make copy of the given map.
733 /// Makes copy of the given map for the newly created graph.
734 /// The new map's key type is the target graph's edge type,
735 /// and the copied map's key type is the source graph's edge
737 template <typename TargetMap, typename SourceMap>
738 const UndirGraphCopy& edgeMap(TargetMap& tMap,
739 const SourceMap& sMap) const {
740 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
744 /// \brief Make copy of the given map.
746 /// Makes copy of the given map for the newly created graph.
747 /// The new map's key type is the target graph's edge type,
748 /// and the copied map's key type is the source graph's edge
750 template <typename TargetMap, typename SourceMap>
751 const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
752 const SourceMap& sMap) const {
753 copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
757 /// \brief Gives back the stored node references.
759 /// Gives back the stored node references.
760 const NodeRefMap& nodeRef() const {
764 /// \brief Gives back the stored edge references.
766 /// Gives back the stored edge references.
767 const EdgeRefMap& edgeRef() const {
771 /// \brief Gives back the stored undir edge references.
773 /// Gives back the stored undir edge references.
774 const UndirEdgeRefMap& undirEdgeRef() const {
775 return undirEdgeRefMap;
782 const Source& source;
785 NodeRefMap nodeRefMap;
786 EdgeRefMap edgeRefMap;
787 UndirEdgeRefMap undirEdgeRefMap;
790 /// \brief Copy a graph to an other graph.
792 /// Copy a graph to an other graph.
793 /// The usage of the function:
796 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
799 /// After the copy the \c nr map will contain the mapping from the
800 /// source graph's nodes to the target graph's nodes and the \c ecr will
801 /// contain the mapping from the target graph's edges to the source's
803 template <typename Target, typename Source>
804 UndirGraphCopy<Target, Source>
805 copyUndirGraph(Target& target, const Source& source) {
806 return UndirGraphCopy<Target, Source>(target, source);
812 /// \addtogroup graph_maps
815 /// Provides an immutable and unique id for each item in the graph.
817 /// The IdMap class provides a unique and immutable id for each item of the
818 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
819 /// different items (nodes) get different ids <li>\b immutable: the id of an
820 /// item (node) does not change (even if you delete other nodes). </ul>
821 /// Through this map you get access (i.e. can read) the inner id values of
822 /// the items stored in the graph. This map can be inverted with its member
823 /// class \c InverseMap.
825 template <typename _Graph, typename _Item>
828 typedef _Graph Graph;
833 /// \brief Constructor.
835 /// Constructor for creating id map.
836 IdMap(const Graph& _graph) : graph(&_graph) {}
838 /// \brief Gives back the \e id of the item.
840 /// Gives back the immutable and unique \e id of the map.
841 int operator[](const Item& item) const { return graph->id(item);}
849 /// \brief The class represents the inverse of its owner (IdMap).
851 /// The class represents the inverse of its owner (IdMap).
856 /// \brief Constructor.
858 /// Constructor for creating an id-to-item map.
859 InverseMap(const Graph& _graph) : graph(&_graph) {}
861 /// \brief Constructor.
863 /// Constructor for creating an id-to-item map.
864 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
866 /// \brief Gives back the given item from its id.
868 /// Gives back the given item from its id.
870 Item operator[](int id) const { return graph->fromId(id, Item());}
875 /// \brief Gives back the inverse of the map.
877 /// Gives back the inverse of the IdMap.
878 InverseMap inverse() const { return InverseMap(*graph);}
883 /// \brief General invertable graph-map type.
885 /// This type provides simple invertable graph-maps.
886 /// The InvertableMap wraps an arbitrary ReadWriteMap
887 /// and if a key is set to a new value then store it
888 /// in the inverse map.
889 /// \param _Graph The graph type.
890 /// \param _Item The item type of the graph.
891 /// \param _Value The value type of the map.
893 /// \param _Map A ReadWriteMap mapping from the item type to integer.
895 typename _Graph, typename _Item, typename _Value, typename _Map
896 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
899 template <typename _Graph, typename _Item, typename _Value>
901 class InvertableMap : protected _Map {
906 typedef _Graph Graph;
908 /// The key type of InvertableMap (Node, Edge, UndirEdge).
909 typedef typename _Map::Key Key;
910 /// The value type of the InvertableMap.
911 typedef typename _Map::Value Value;
913 /// \brief Constructor.
915 /// Construct a new InvertableMap for the graph.
917 InvertableMap(const Graph& graph) : Map(graph) {}
919 /// \brief The setter function of the map.
921 /// Sets the mapped value.
922 void set(const Key& key, const Value& val) {
923 Value oldval = Map::operator[](key);
924 typename Container::iterator it = invMap.find(oldval);
925 if (it != invMap.end() && it->second == key) {
928 invMap.insert(make_pair(val, key));
932 /// \brief The getter function of the map.
934 /// It gives back the value associated with the key.
935 Value operator[](const Key& key) const {
936 return Map::operator[](key);
941 /// \brief Erase the key from the map.
943 /// Erase the key to the map. It is called by the
944 /// \c AlterationNotifier.
945 virtual void erase(const Key& key) {
946 Value val = Map::operator[](key);
947 typename Container::iterator it = invMap.find(val);
948 if (it != invMap.end() && it->second == key) {
954 /// \brief Erase more keys from the map.
956 /// Erase more keys from the map. It is called by the
957 /// \c AlterationNotifier.
958 virtual void erase(const std::vector<Key>& keys) {
959 for (int i = 0; i < (int)keys.size(); ++i) {
960 Value val = Map::operator[](keys[i]);
961 typename Container::iterator it = invMap.find(val);
962 if (it != invMap.end() && it->second == keys[i]) {
969 /// \brief Clear the keys from the map and inverse map.
971 /// Clear the keys from the map and inverse map. It is called by the
972 /// \c AlterationNotifier.
973 virtual void clear() {
980 typedef std::map<Value, Key> Container;
985 /// \brief The inverse map type.
987 /// The inverse of this map. The subscript operator of the map
988 /// gives back always the item what was last assigned to the value.
991 /// \brief Constructor of the InverseMap.
993 /// Constructor of the InverseMap.
994 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
996 /// The value type of the InverseMap.
997 typedef typename InvertableMap::Key Value;
998 /// The key type of the InverseMap.
999 typedef typename InvertableMap::Value Key;
1001 /// \brief Subscript operator.
1003 /// Subscript operator. It gives back always the item
1004 /// what was last assigned to the value.
1005 Value operator[](const Key& key) const {
1006 typename Container::const_iterator it = inverted.invMap.find(key);
1011 const InvertableMap& inverted;
1014 /// \brief It gives back the just readeable inverse map.
1016 /// It gives back the just readeable inverse map.
1017 InverseMap inverse() const {
1018 return InverseMap(*this);
1025 /// \brief Provides a mutable, continuous and unique descriptor for each
1026 /// item in the graph.
1028 /// The DescriptorMap class provides a unique and continuous (but mutable)
1029 /// descriptor (id) for each item of the same type (e.g. node) in the
1030 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1031 /// different ids <li>\b continuous: the range of the ids is the set of
1032 /// integers between 0 and \c n-1, where \c n is the number of the items of
1033 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1034 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1035 /// with its member class \c InverseMap.
1037 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1038 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1041 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1043 typename _Graph, typename _Item, typename _Map
1044 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
1047 template <typename _Graph, typename _Item>
1049 class DescriptorMap : protected _Map {
1055 /// The graph class of DescriptorMap.
1056 typedef _Graph Graph;
1058 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1059 typedef typename _Map::Key Key;
1060 /// The value type of DescriptorMap.
1061 typedef typename _Map::Value Value;
1063 /// \brief Constructor.
1065 /// Constructor for descriptor map.
1066 DescriptorMap(const Graph& _graph) : Map(_graph) {
1072 /// \brief Add a new key to the map.
1074 /// Add a new key to the map. It is called by the
1075 /// \c AlterationNotifier.
1076 virtual void add(const Item& item) {
1078 Map::set(item, invMap.size());
1079 invMap.push_back(item);
1082 /// \brief Add more new keys to the map.
1084 /// Add more new keys to the map. It is called by the
1085 /// \c AlterationNotifier.
1086 virtual void add(const std::vector<Item>& items) {
1088 for (int i = 0; i < (int)items.size(); ++i) {
1089 Map::set(items[i], invMap.size());
1090 invMap.push_back(items[i]);
1094 /// \brief Erase the key from the map.
1096 /// Erase the key from the map. It is called by the
1097 /// \c AlterationNotifier.
1098 virtual void erase(const Item& item) {
1099 Map::set(invMap.back(), Map::operator[](item));
1100 invMap[Map::operator[](item)] = invMap.back();
1105 /// \brief Erase more keys from the map.
1107 /// Erase more keys from the map. It is called by the
1108 /// \c AlterationNotifier.
1109 virtual void erase(const std::vector<Item>& items) {
1110 for (int i = 0; i < (int)items.size(); ++i) {
1111 Map::set(invMap.back(), Map::operator[](items[i]));
1112 invMap[Map::operator[](items[i])] = invMap.back();
1118 /// \brief Build the unique map.
1120 /// Build the unique map. It is called by the
1121 /// \c AlterationNotifier.
1122 virtual void build() {
1125 const typename Map::Graph* graph = Map::getGraph();
1126 for (graph->first(it); it != INVALID; graph->next(it)) {
1127 Map::set(it, invMap.size());
1128 invMap.push_back(it);
1132 /// \brief Clear the keys from the map.
1134 /// Clear the keys from the map. It is called by the
1135 /// \c AlterationNotifier.
1136 virtual void clear() {
1143 /// \brief Swaps the position of the two items in the map.
1145 /// Swaps the position of the two items in the map.
1146 void swap(const Item& p, const Item& q) {
1147 int pi = Map::operator[](p);
1148 int qi = Map::operator[](q);
1155 /// \brief Gives back the \e descriptor of the item.
1157 /// Gives back the mutable and unique \e descriptor of the map.
1158 int operator[](const Item& item) const {
1159 return Map::operator[](item);
1164 typedef std::vector<Item> Container;
1168 /// \brief The inverse map type of DescriptorMap.
1170 /// The inverse map type of DescriptorMap.
1173 /// \brief Constructor of the InverseMap.
1175 /// Constructor of the InverseMap.
1176 InverseMap(const DescriptorMap& _inverted)
1177 : inverted(_inverted) {}
1180 /// The value type of the InverseMap.
1181 typedef typename DescriptorMap::Key Value;
1182 /// The key type of the InverseMap.
1183 typedef typename DescriptorMap::Value Key;
1185 /// \brief Subscript operator.
1187 /// Subscript operator. It gives back the item
1188 /// that the descriptor belongs to currently.
1189 Value operator[](const Key& key) const {
1190 return inverted.invMap[key];
1193 /// \brief Size of the map.
1195 /// Returns the size of the map.
1197 return inverted.invMap.size();
1201 const DescriptorMap& inverted;
1204 /// \brief Gives back the inverse of the map.
1206 /// Gives back the inverse of the map.
1207 const InverseMap inverse() const {
1208 return InverseMap(*this);
1212 /// \brief Returns the source of the given edge.
1214 /// The SourceMap gives back the source Node of the given edge.
1215 /// \author Balazs Dezso
1216 template <typename Graph>
1220 typedef typename Graph::Node Value;
1221 typedef typename Graph::Edge Key;
1223 /// \brief Constructor
1226 /// \param _graph The graph that the map belongs to.
1227 SourceMap(const Graph& _graph) : graph(_graph) {}
1229 /// \brief The subscript operator.
1231 /// The subscript operator.
1232 /// \param edge The edge
1233 /// \return The source of the edge
1234 Value operator[](const Key& edge) const {
1235 return graph.source(edge);
1242 /// \brief Returns a \ref SourceMap class
1244 /// This function just returns an \ref SourceMap class.
1245 /// \relates SourceMap
1246 template <typename Graph>
1247 inline SourceMap<Graph> sourceMap(const Graph& graph) {
1248 return SourceMap<Graph>(graph);
1251 /// \brief Returns the target of the given edge.
1253 /// The TargetMap gives back the target Node of the given edge.
1254 /// \author Balazs Dezso
1255 template <typename Graph>
1259 typedef typename Graph::Node Value;
1260 typedef typename Graph::Edge Key;
1262 /// \brief Constructor
1265 /// \param _graph The graph that the map belongs to.
1266 TargetMap(const Graph& _graph) : graph(_graph) {}
1268 /// \brief The subscript operator.
1270 /// The subscript operator.
1271 /// \param e The edge
1272 /// \return The target of the edge
1273 Value operator[](const Key& e) const {
1274 return graph.target(e);
1281 /// \brief Returns a \ref TargetMap class
1283 /// This function just returns a \ref TargetMap class.
1284 /// \relates TargetMap
1285 template <typename Graph>
1286 inline TargetMap<Graph> targetMap(const Graph& graph) {
1287 return TargetMap<Graph>(graph);
1290 /// \brief Returns the "forward" directed edge view of an undirected edge.
1292 /// Returns the "forward" directed edge view of an undirected edge.
1293 /// \author Balazs Dezso
1294 template <typename Graph>
1298 typedef typename Graph::Edge Value;
1299 typedef typename Graph::UndirEdge Key;
1301 /// \brief Constructor
1304 /// \param _graph The graph that the map belongs to.
1305 ForwardMap(const Graph& _graph) : graph(_graph) {}
1307 /// \brief The subscript operator.
1309 /// The subscript operator.
1310 /// \param key An undirected edge
1311 /// \return The "forward" directed edge view of undirected edge
1312 Value operator[](const Key& key) const {
1313 return graph.direct(key, true);
1320 /// \brief Returns a \ref ForwardMap class
1322 /// This function just returns an \ref ForwardMap class.
1323 /// \relates ForwardMap
1324 template <typename Graph>
1325 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1326 return ForwardMap<Graph>(graph);
1329 /// \brief Returns the "backward" directed edge view of an undirected edge.
1331 /// Returns the "backward" directed edge view of an undirected edge.
1332 /// \author Balazs Dezso
1333 template <typename Graph>
1337 typedef typename Graph::Edge Value;
1338 typedef typename Graph::UndirEdge Key;
1340 /// \brief Constructor
1343 /// \param _graph The graph that the map belongs to.
1344 BackwardMap(const Graph& _graph) : graph(_graph) {}
1346 /// \brief The subscript operator.
1348 /// The subscript operator.
1349 /// \param key An undirected edge
1350 /// \return The "backward" directed edge view of undirected edge
1351 Value operator[](const Key& key) const {
1352 return graph.direct(key, false);
1359 /// \brief Returns a \ref BackwardMap class
1361 /// This function just returns a \ref BackwardMap class.
1362 /// \relates BackwardMap
1363 template <typename Graph>
1364 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1365 return BackwardMap<Graph>(graph);
1368 /// \brief Potential difference map
1370 /// If there is an potential map on the nodes then we
1371 /// can get an edge map as we get the substraction of the
1372 /// values of the target and source.
1373 template <typename Graph, typename NodeMap>
1374 class PotentialDifferenceMap {
1376 typedef typename Graph::Edge Key;
1377 typedef typename NodeMap::Value Value;
1379 /// \brief Constructor
1381 /// Contructor of the map
1382 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1383 : graph(_graph), potential(_potential) {}
1385 /// \brief Const subscription operator
1387 /// Const subscription operator
1388 Value operator[](const Key& edge) const {
1389 return potential[graph.target(edge)] - potential[graph.source(edge)];
1394 const NodeMap& potential;
1397 /// \brief Just returns a PotentialDifferenceMap
1399 /// Just returns a PotentialDifferenceMap
1400 /// \relates PotentialDifferenceMap
1401 template <typename Graph, typename NodeMap>
1402 PotentialDifferenceMap<Graph, NodeMap>
1403 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1404 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1407 /// \brief Map of the node in-degrees.
1409 /// This map returns the in-degree of a node. Once it is constructed,
1410 /// the degrees are stored in a standard NodeMap, so each query is done
1411 /// in constant time. On the other hand, the values are updated automatically
1412 /// whenever the graph changes.
1414 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1415 /// alternative ways to modify the graph. The correct behavior of InDegMap
1416 /// is not guarantied if these additional features are used. For example
1417 /// the functions \ref ListGraph::changeSource() "changeSource()",
1418 /// \ref ListGraph::changeTarget() "changeTarget()" and
1419 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1420 /// of \ref ListGraph will \e not update the degree values correctly.
1424 template <typename _Graph>
1426 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1430 typedef _Graph Graph;
1432 typedef typename Graph::Node Key;
1436 class AutoNodeMap : public Graph::template NodeMap<int> {
1439 typedef typename Graph::template NodeMap<int> Parent;
1441 typedef typename Parent::Key Key;
1442 typedef typename Parent::Value Value;
1444 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1446 virtual void add(const Key& key) {
1448 Parent::set(key, 0);
1450 virtual void add(const std::vector<Key>& keys) {
1452 for (int i = 0; i < (int)keys.size(); ++i) {
1453 Parent::set(keys[i], 0);
1460 /// \brief Constructor.
1462 /// Constructor for creating in-degree map.
1463 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1464 AlterationNotifier<typename _Graph::Edge>
1465 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1467 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1468 deg[it] = countInEdges(graph, it);
1472 virtual ~InDegMap() {
1473 AlterationNotifier<typename _Graph::Edge>::
1474 ObserverBase::detach();
1477 /// Gives back the in-degree of a Node.
1478 int operator[](const Key& key) const {
1484 typedef typename Graph::Edge Edge;
1486 virtual void add(const Edge& edge) {
1487 ++deg[graph.target(edge)];
1490 virtual void erase(const Edge& edge) {
1491 --deg[graph.target(edge)];
1494 virtual void build() {
1495 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1496 deg[it] = countInEdges(graph, it);
1500 virtual void clear() {
1501 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1507 const _Graph& graph;
1511 /// \brief Map of the node out-degrees.
1513 /// This map returns the out-degree of a node. Once it is constructed,
1514 /// the degrees are stored in a standard NodeMap, so each query is done
1515 /// in constant time. On the other hand, the values are updated automatically
1516 /// whenever the graph changes.
1518 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1519 /// alternative ways to modify the graph. The correct behavior of OutDegMap
1520 /// is not guarantied if these additional features are used. For example
1521 /// the functions \ref ListGraph::changeSource() "changeSource()",
1522 /// \ref ListGraph::changeTarget() "changeTarget()" and
1523 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1524 /// of \ref ListGraph will \e not update the degree values correctly.
1528 template <typename _Graph>
1530 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1534 typedef _Graph Graph;
1536 typedef typename Graph::Node Key;
1540 class AutoNodeMap : public Graph::template NodeMap<int> {
1543 typedef typename Graph::template NodeMap<int> Parent;
1545 typedef typename Parent::Key Key;
1546 typedef typename Parent::Value Value;
1548 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1550 virtual void add(const Key& key) {
1552 Parent::set(key, 0);
1554 virtual void add(const std::vector<Key>& keys) {
1556 for (int i = 0; i < (int)keys.size(); ++i) {
1557 Parent::set(keys[i], 0);
1564 /// \brief Constructor.
1566 /// Constructor for creating out-degree map.
1567 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1568 AlterationNotifier<typename _Graph::Edge>
1569 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1571 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1572 deg[it] = countOutEdges(graph, it);
1576 virtual ~OutDegMap() {
1577 AlterationNotifier<typename _Graph::Edge>::
1578 ObserverBase::detach();
1581 /// Gives back the in-degree of a Node.
1582 int operator[](const Key& key) const {
1588 typedef typename Graph::Edge Edge;
1590 virtual void add(const Edge& edge) {
1591 ++deg[graph.source(edge)];
1594 virtual void erase(const Edge& edge) {
1595 --deg[graph.source(edge)];
1598 virtual void build() {
1599 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1600 deg[it] = countOutEdges(graph, it);
1604 virtual void clear() {
1605 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1611 const _Graph& graph;
1618 } //END OF NAMESPACE LEMON