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>
114 typename enable_if<typename Graph::NodeNumTag, int>::type
115 _countNodes(const Graph &g) {
119 template <typename Graph>
120 inline int _countNodes(Wrap<Graph> w) {
121 return countItems<Graph, typename Graph::NodeIt>(w.value);
124 /// \brief Function to count the nodes in the graph.
126 /// This function counts the nodes in the graph.
127 /// The complexity of the function is O(n) but for some
128 /// graph structures it is specialized to run in O(1).
130 /// \todo refer how to specialize it
132 template <typename Graph>
133 inline int countNodes(const Graph& g) {
134 return _countNodes<Graph>(g);
139 template <typename Graph>
141 typename enable_if<typename Graph::EdgeNumTag, int>::type
142 _countEdges(const Graph &g) {
146 template <typename Graph>
147 inline int _countEdges(Wrap<Graph> w) {
148 return countItems<Graph, typename Graph::EdgeIt>(w.value);
151 /// \brief Function to count the edges in the graph.
153 /// This function counts the edges in the graph.
154 /// The complexity of the function is O(e) but for some
155 /// graph structures it is specialized to run in O(1).
157 template <typename Graph>
158 inline int countEdges(const Graph& g) {
159 return _countEdges<Graph>(g);
162 // Undirected edge counting:
164 template <typename Graph>
166 typename enable_if<typename Graph::EdgeNumTag, int>::type
167 _countUndirEdges(const Graph &g) {
168 return g.undirEdgeNum();
171 template <typename Graph>
172 inline int _countUndirEdges(Wrap<Graph> w) {
173 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
176 /// \brief Function to count the undirected edges in the graph.
178 /// This function counts the undirected edges in the graph.
179 /// The complexity of the function is O(e) but for some
180 /// graph structures it is specialized to run in O(1).
182 template <typename Graph>
183 inline int countUndirEdges(const Graph& g) {
184 return _countUndirEdges<Graph>(g);
189 template <typename Graph, typename DegIt>
190 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
192 for (DegIt it(_g, _n); it != INVALID; ++it) {
198 /// \brief Function to count the number of the out-edges from node \c n.
200 /// This function counts the number of the out-edges from node \c n
202 template <typename Graph>
203 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
204 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
207 /// \brief Function to count the number of the in-edges to node \c n.
209 /// This function counts the number of the in-edges to node \c n
211 template <typename Graph>
212 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
213 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
216 /// \brief Function to count the number of the inc-edges to node \c n.
218 /// This function counts the number of the inc-edges to node \c n
220 template <typename Graph>
221 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
222 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
226 template <typename Graph>
228 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
229 _findEdge(const Graph &g,
230 typename Graph::Node u, typename Graph::Node v,
231 typename Graph::Edge prev = INVALID) {
232 return g.findEdge(u, v, prev);
235 template <typename Graph>
236 inline typename Graph::Edge
237 _findEdge(Wrap<Graph> w,
238 typename Graph::Node u,
239 typename Graph::Node v,
240 typename Graph::Edge prev = INVALID) {
241 const Graph& g = w.value;
242 if (prev == INVALID) {
243 typename Graph::OutEdgeIt e(g, u);
244 while (e != INVALID && g.target(e) != v) ++e;
247 typename Graph::OutEdgeIt e(g, prev); ++e;
248 while (e != INVALID && g.target(e) != v) ++e;
253 /// \brief Finds an edge between two nodes of a graph.
255 /// Finds an edge from node \c u to node \c v in graph \c g.
257 /// If \c prev is \ref INVALID (this is the default value), then
258 /// it finds the first edge from \c u to \c v. Otherwise it looks for
259 /// the next edge from \c u to \c v after \c prev.
260 /// \return The found edge or \ref INVALID if there is no such an edge.
262 /// Thus you can iterate through each edge from \c u to \c v as it follows.
264 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
268 // /// \todo We may want to use the "GraphBase"
269 // /// interface here...
270 template <typename Graph>
271 inline typename Graph::Edge findEdge(const Graph &g,
272 typename Graph::Node u,
273 typename Graph::Node v,
274 typename Graph::Edge prev = INVALID) {
275 return _findEdge<Graph>(g, u, v, prev);
278 /// \brief Iterator for iterating on edges connected the same nodes.
280 /// Iterator for iterating on edges connected the same nodes. It is
281 /// higher level interface for the findEdge() function. You can
282 /// use it the following way:
284 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
289 /// \author Balazs Dezso
290 template <typename _Graph>
291 class ConEdgeIt : public _Graph::Edge {
294 typedef _Graph Graph;
295 typedef typename Graph::Edge Parent;
297 typedef typename Graph::Edge Edge;
298 typedef typename Graph::Node Node;
300 /// \brief Constructor.
302 /// Construct a new ConEdgeIt iterating on the edges which
303 /// connects the \c u and \c v node.
304 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
305 Parent::operator=(findEdge(graph, u, v));
308 /// \brief Constructor.
310 /// Construct a new ConEdgeIt which continues the iterating from
312 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
314 /// \brief Increment operator.
316 /// It increments the iterator and gives back the next edge.
317 ConEdgeIt& operator++() {
318 Parent::operator=(findEdge(graph, graph.source(*this),
319 graph.target(*this), *this));
326 template <typename Graph>
329 typename Graph::FindEdgeTag,
330 typename Graph::UndirEdge>::type
331 _findUndirEdge(const Graph &g,
332 typename Graph::Node u, typename Graph::Node v,
333 typename Graph::UndirEdge prev = INVALID) {
334 return g.findUndirEdge(u, v, prev);
337 template <typename Graph>
338 inline typename Graph::UndirEdge
339 _findUndirEdge(Wrap<Graph> w,
340 typename Graph::Node u,
341 typename Graph::Node v,
342 typename Graph::UndirEdge prev = INVALID) {
343 const Graph& g = w.value;
344 if (prev == INVALID) {
345 typename Graph::OutEdgeIt e(g, u);
346 while (e != INVALID && g.target(e) != v) ++e;
349 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
350 while (e != INVALID && g.target(e) != v) ++e;
355 /// \brief Finds an undir edge between two nodes of a graph.
357 /// Finds an undir edge from node \c u to node \c v in graph \c g.
359 /// If \c prev is \ref INVALID (this is the default value), then
360 /// it finds the first edge from \c u to \c v. Otherwise it looks for
361 /// the next edge from \c u to \c v after \c prev.
362 /// \return The found edge or \ref INVALID if there is no such an edge.
364 /// Thus you can iterate through each edge from \c u to \c v as it follows.
366 /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
367 /// e = findUndirEdge(g,u,v,e)) {
371 // /// \todo We may want to use the "GraphBase"
372 // /// interface here...
373 template <typename Graph>
374 inline typename Graph::UndirEdge
375 findUndirEdge(const Graph &g,
376 typename Graph::Node u,
377 typename Graph::Node v,
378 typename Graph::UndirEdge prev = INVALID) {
379 return _findUndirEdge<Graph>(g, u, v, prev);
382 /// \brief Iterator for iterating on undir edges connected the same nodes.
384 /// Iterator for iterating on undir edges connected the same nodes. It is
385 /// higher level interface for the findUndirEdge() function. You can
386 /// use it the following way:
388 /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
393 /// \author Balazs Dezso
394 template <typename _Graph>
395 class ConUndirEdgeIt : public _Graph::UndirEdge {
398 typedef _Graph Graph;
399 typedef typename Graph::UndirEdge Parent;
401 typedef typename Graph::UndirEdge UndirEdge;
402 typedef typename Graph::Node Node;
404 /// \brief Constructor.
406 /// Construct a new ConUndirEdgeIt iterating on the edges which
407 /// connects the \c u and \c v node.
408 ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
409 Parent::operator=(findUndirEdge(graph, u, v));
412 /// \brief Constructor.
414 /// Construct a new ConUndirEdgeIt which continues the iterating from
416 ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
418 /// \brief Increment operator.
420 /// It increments the iterator and gives back the next edge.
421 ConUndirEdgeIt& operator++() {
422 Parent::operator=(findUndirEdge(graph, graph.source(*this),
423 graph.target(*this), *this));
430 /// \brief Copy a map.
432 /// This function copies the \c source map to the \c target map. It uses the
433 /// given iterator to iterate on the data structure and it uses the \c ref
434 /// mapping to convert the source's keys to the target's keys.
435 template <typename Target, typename Source,
436 typename ItemIt, typename Ref>
437 void copyMap(Target& target, const Source& source,
438 ItemIt it, const Ref& ref) {
439 for (; it != INVALID; ++it) {
440 target[ref[it]] = source[it];
444 /// \brief Copy the source map to the target map.
446 /// Copy the \c source map to the \c target map. It uses the given iterator
447 /// to iterate on the data structure.
448 template <typename Target, typename Source,
450 void copyMap(Target& target, const Source& source, ItemIt it) {
451 for (; it != INVALID; ++it) {
452 target[it] = source[it];
456 /// \brief Class to copy a graph.
458 /// Class to copy a graph to an other graph (duplicate a graph). The
459 /// simplest way of using it is through the \c copyGraph() function.
460 template <typename Target, typename Source>
463 typedef typename Source::Node Node;
464 typedef typename Source::NodeIt NodeIt;
465 typedef typename Source::Edge Edge;
466 typedef typename Source::EdgeIt EdgeIt;
468 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
469 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
471 /// \brief Constructor for the GraphCopy.
473 /// It copies the content of the \c _source graph into the
474 /// \c _target graph. It creates also two references, one beetween
475 /// the two nodeset and one beetween the two edgesets.
476 GraphCopy(Target& _target, const Source& _source)
477 : source(_source), target(_target),
478 nodeRefMap(_source), edgeRefMap(_source) {
479 for (NodeIt it(source); it != INVALID; ++it) {
480 nodeRefMap[it] = target.addNode();
482 for (EdgeIt it(source); it != INVALID; ++it) {
483 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
484 nodeRefMap[source.target(it)]);
488 /// \brief Copies the node references into the given map.
490 /// Copies the node references into the given map.
491 template <typename NodeRef>
492 const GraphCopy& nodeRef(NodeRef& map) const {
493 for (NodeIt it(source); it != INVALID; ++it) {
494 map.set(it, nodeRefMap[it]);
499 /// \brief Reverse and copies the node references into the given map.
501 /// Reverse and copies the node references into the given map.
502 template <typename NodeRef>
503 const GraphCopy& nodeCrossRef(NodeRef& map) const {
504 for (NodeIt it(source); it != INVALID; ++it) {
505 map.set(nodeRefMap[it], it);
510 /// \brief Copies the edge references into the given map.
512 /// Copies the edge references into the given map.
513 template <typename EdgeRef>
514 const GraphCopy& edgeRef(EdgeRef& map) const {
515 for (EdgeIt it(source); it != INVALID; ++it) {
516 map.set(it, edgeRefMap[it]);
521 /// \brief Reverse and copies the edge references into the given map.
523 /// Reverse and copies the edge references into the given map.
524 template <typename EdgeRef>
525 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
526 for (EdgeIt it(source); it != INVALID; ++it) {
527 map.set(edgeRefMap[it], it);
532 /// \brief Make copy of the given map.
534 /// Makes copy of the given map for the newly created graph.
535 /// The new map's key type is the target graph's node type,
536 /// and the copied map's key type is the source graph's node
538 template <typename TargetMap, typename SourceMap>
539 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
540 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
544 /// \brief Make copy of the given map.
546 /// Makes copy of the given map for the newly created graph.
547 /// The new map's key type is the target graph's edge type,
548 /// and the copied map's key type is the source graph's edge
550 template <typename TargetMap, typename SourceMap>
551 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
552 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
556 /// \brief Gives back the stored node references.
558 /// Gives back the stored node references.
559 const NodeRefMap& nodeRef() const {
563 /// \brief Gives back the stored edge references.
565 /// Gives back the stored edge references.
566 const EdgeRefMap& edgeRef() const {
574 const Source& source;
577 NodeRefMap nodeRefMap;
578 EdgeRefMap edgeRefMap;
581 /// \brief Copy a graph to an other graph.
583 /// Copy a graph to an other graph.
584 /// The usage of the function:
587 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
590 /// After the copy the \c nr map will contain the mapping from the
591 /// source graph's nodes to the target graph's nodes and the \c ecr will
592 /// contain the mapping from the target graph's edges to the source's
594 template <typename Target, typename Source>
595 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
596 return GraphCopy<Target, Source>(target, source);
599 /// \brief Class to copy an undirected graph.
601 /// Class to copy an undirected graph to an other graph (duplicate a graph).
602 /// The simplest way of using it is through the \c copyUndirGraph() function.
603 template <typename Target, typename Source>
604 class UndirGraphCopy {
606 typedef typename Source::Node Node;
607 typedef typename Source::NodeIt NodeIt;
608 typedef typename Source::Edge Edge;
609 typedef typename Source::EdgeIt EdgeIt;
610 typedef typename Source::UndirEdge UndirEdge;
611 typedef typename Source::UndirEdgeIt UndirEdgeIt;
613 typedef typename Source::
614 template NodeMap<typename Target::Node> NodeRefMap;
616 typedef typename Source::
617 template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
622 EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
623 typedef typename Source::Edge Key;
624 typedef typename Target::Edge Value;
626 Value operator[](const Key& key) {
627 return gc.target.direct(gc.undirEdgeRef[key],
628 gc.target.direction(key));
636 /// \brief Constructor for the UndirGraphCopy.
638 /// It copies the content of the \c _source graph into the
639 /// \c _target graph. It creates also two references, one beetween
640 /// the two nodeset and one beetween the two edgesets.
641 UndirGraphCopy(Target& _target, const Source& _source)
642 : source(_source), target(_target),
643 nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
644 for (NodeIt it(source); it != INVALID; ++it) {
645 nodeRefMap[it] = target.addNode();
647 for (UndirEdgeIt it(source); it != INVALID; ++it) {
648 undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
649 nodeRefMap[source.target(it)]);
653 /// \brief Copies the node references into the given map.
655 /// Copies the node references into the given map.
656 template <typename NodeRef>
657 const UndirGraphCopy& nodeRef(NodeRef& map) const {
658 for (NodeIt it(source); it != INVALID; ++it) {
659 map.set(it, nodeRefMap[it]);
664 /// \brief Reverse and copies the node references into the given map.
666 /// Reverse and copies the node references into the given map.
667 template <typename NodeRef>
668 const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
669 for (NodeIt it(source); it != INVALID; ++it) {
670 map.set(nodeRefMap[it], it);
675 /// \brief Copies the edge references into the given map.
677 /// Copies the edge references into the given map.
678 template <typename EdgeRef>
679 const UndirGraphCopy& edgeRef(EdgeRef& map) const {
680 for (EdgeIt it(source); it != INVALID; ++it) {
681 map.set(edgeRefMap[it], it);
686 /// \brief Reverse and copies the undirected edge references into the
689 /// Reverse and copies the undirected edge references into the given map.
690 template <typename EdgeRef>
691 const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
692 for (EdgeIt it(source); it != INVALID; ++it) {
693 map.set(it, edgeRefMap[it]);
698 /// \brief Copies the undirected edge references into the given map.
700 /// Copies the undirected edge references into the given map.
701 template <typename EdgeRef>
702 const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
703 for (UndirEdgeIt it(source); it != INVALID; ++it) {
704 map.set(it, undirEdgeRefMap[it]);
709 /// \brief Reverse and copies the undirected edge references into the
712 /// Reverse and copies the undirected edge references into the given map.
713 template <typename EdgeRef>
714 const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
715 for (UndirEdgeIt it(source); it != INVALID; ++it) {
716 map.set(undirEdgeRefMap[it], it);
721 /// \brief Make copy of the given map.
723 /// Makes copy of the given map for the newly created graph.
724 /// The new map's key type is the target graph's node type,
725 /// and the copied map's key type is the source graph's node
727 template <typename TargetMap, typename SourceMap>
728 const UndirGraphCopy& nodeMap(TargetMap& tMap,
729 const SourceMap& sMap) const {
730 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
734 /// \brief Make copy of the given map.
736 /// Makes copy of the given map for the newly created graph.
737 /// The new map's key type is the target graph's edge type,
738 /// and the copied map's key type is the source graph's edge
740 template <typename TargetMap, typename SourceMap>
741 const UndirGraphCopy& edgeMap(TargetMap& tMap,
742 const SourceMap& sMap) const {
743 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
747 /// \brief Make copy of the given map.
749 /// Makes copy of the given map for the newly created graph.
750 /// The new map's key type is the target graph's edge type,
751 /// and the copied map's key type is the source graph's edge
753 template <typename TargetMap, typename SourceMap>
754 const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
755 const SourceMap& sMap) const {
756 copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
760 /// \brief Gives back the stored node references.
762 /// Gives back the stored node references.
763 const NodeRefMap& nodeRef() const {
767 /// \brief Gives back the stored edge references.
769 /// Gives back the stored edge references.
770 const EdgeRefMap& edgeRef() const {
774 /// \brief Gives back the stored undir edge references.
776 /// Gives back the stored undir edge references.
777 const UndirEdgeRefMap& undirEdgeRef() const {
778 return undirEdgeRefMap;
785 const Source& source;
788 NodeRefMap nodeRefMap;
789 EdgeRefMap edgeRefMap;
790 UndirEdgeRefMap undirEdgeRefMap;
793 /// \brief Copy a graph to an other graph.
795 /// Copy a graph to an other graph.
796 /// The usage of the function:
799 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
802 /// After the copy the \c nr map will contain the mapping from the
803 /// source graph's nodes to the target graph's nodes and the \c ecr will
804 /// contain the mapping from the target graph's edges to the source's
806 template <typename Target, typename Source>
807 UndirGraphCopy<Target, Source>
808 copyUndirGraph(Target& target, const Source& source) {
809 return UndirGraphCopy<Target, Source>(target, source);
815 /// \addtogroup graph_maps
818 /// Provides an immutable and unique id for each item in the graph.
820 /// The IdMap class provides a unique and immutable id for each item of the
821 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
822 /// different items (nodes) get different ids <li>\b immutable: the id of an
823 /// item (node) does not change (even if you delete other nodes). </ul>
824 /// Through this map you get access (i.e. can read) the inner id values of
825 /// the items stored in the graph. This map can be inverted with its member
826 /// class \c InverseMap.
828 template <typename _Graph, typename _Item>
831 typedef _Graph Graph;
836 /// \brief Constructor.
838 /// Constructor for creating id map.
839 IdMap(const Graph& _graph) : graph(&_graph) {}
841 /// \brief Gives back the \e id of the item.
843 /// Gives back the immutable and unique \e id of the map.
844 int operator[](const Item& item) const { return graph->id(item);}
852 /// \brief The class represents the inverse of its owner (IdMap).
854 /// The class represents the inverse of its owner (IdMap).
859 /// \brief Constructor.
861 /// Constructor for creating an id-to-item map.
862 InverseMap(const Graph& _graph) : graph(&_graph) {}
864 /// \brief Constructor.
866 /// Constructor for creating an id-to-item map.
867 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
869 /// \brief Gives back the given item from its id.
871 /// Gives back the given item from its id.
873 Item operator[](int id) const { return graph->fromId(id, Item());}
878 /// \brief Gives back the inverse of the map.
880 /// Gives back the inverse of the IdMap.
881 InverseMap inverse() const { return InverseMap(*graph);}
886 /// \brief General invertable graph-map type.
888 /// This type provides simple invertable graph-maps.
889 /// The InvertableMap wraps an arbitrary ReadWriteMap
890 /// and if a key is set to a new value then store it
891 /// in the inverse map.
892 /// \param _Graph The graph type.
893 /// \param _Map The map to extend with invertable functionality.
899 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
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 Add a new key to the map.
943 /// Add a new key to the map. It is called by the
944 /// \c AlterationNotifier.
945 virtual void add(const Key& key) {
949 /// \brief Erase the key from the map.
951 /// Erase the key to the map. It is called by the
952 /// \c AlterationNotifier.
953 virtual void erase(const Key& key) {
954 Value val = Map::operator[](key);
955 typename Container::iterator it = invMap.find(val);
956 if (it != invMap.end() && it->second == key) {
962 /// \brief Clear the keys from the map and inverse map.
964 /// Clear the keys from the map and inverse map. It is called by the
965 /// \c AlterationNotifier.
966 virtual void clear() {
973 typedef std::map<Value, Key> Container;
978 /// \brief The inverse map type.
980 /// The inverse of this map. The subscript operator of the map
981 /// gives back always the item what was last assigned to the value.
984 /// \brief Constructor of the InverseMap.
986 /// Constructor of the InverseMap.
987 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
989 /// The value type of the InverseMap.
990 typedef typename InvertableMap::Key Value;
991 /// The key type of the InverseMap.
992 typedef typename InvertableMap::Value Key;
994 /// \brief Subscript operator.
996 /// Subscript operator. It gives back always the item
997 /// what was last assigned to the value.
998 Value operator[](const Key& key) const {
999 typename Container::const_iterator it = inverted.invMap.find(key);
1004 const InvertableMap& inverted;
1007 /// \brief It gives back the just readeable inverse map.
1009 /// It gives back the just readeable inverse map.
1010 InverseMap inverse() const {
1011 return InverseMap(*this);
1018 /// \brief Provides a mutable, continuous and unique descriptor for each
1019 /// item in the graph.
1021 /// The DescriptorMap class provides a unique and continuous (but mutable)
1022 /// descriptor (id) for each item of the same type (e.g. node) in the
1023 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1024 /// different ids <li>\b continuous: the range of the ids is the set of
1025 /// integers between 0 and \c n-1, where \c n is the number of the items of
1026 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1027 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1028 /// with its member class \c InverseMap.
1030 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1031 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1033 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1038 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
1040 class DescriptorMap : protected _Map {
1046 /// The graph class of DescriptorMap.
1047 typedef _Graph Graph;
1049 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
1050 typedef typename _Map::Key Key;
1051 /// The value type of DescriptorMap.
1052 typedef typename _Map::Value Value;
1054 /// \brief Constructor.
1056 /// Constructor for descriptor map.
1057 DescriptorMap(const Graph& _graph) : Map(_graph) {
1063 /// \brief Add a new key to the map.
1065 /// Add a new key to the map. It is called by the
1066 /// \c AlterationNotifier.
1067 virtual void add(const Item& item) {
1069 Map::set(item, invMap.size());
1070 invMap.push_back(item);
1073 /// \brief Erase the key from the map.
1075 /// Erase the key to the map. It is called by the
1076 /// \c AlterationNotifier.
1077 virtual void erase(const Item& item) {
1078 Map::set(invMap.back(), Map::operator[](item));
1079 invMap[Map::operator[](item)] = invMap.back();
1084 /// \brief Build the unique map.
1086 /// Build the unique map. It is called by the
1087 /// \c AlterationNotifier.
1088 virtual void build() {
1091 const typename Map::Graph* graph = Map::getGraph();
1092 for (graph->first(it); it != INVALID; graph->next(it)) {
1093 Map::set(it, invMap.size());
1094 invMap.push_back(it);
1098 /// \brief Clear the keys from the map.
1100 /// Clear the keys from the map. It is called by the
1101 /// \c AlterationNotifier.
1102 virtual void clear() {
1109 /// \brief Swaps the position of the two items in the map.
1111 /// Swaps the position of the two items in the map.
1112 void swap(const Item& p, const Item& q) {
1113 int pi = Map::operator[](p);
1114 int qi = Map::operator[](q);
1121 /// \brief Gives back the \e descriptor of the item.
1123 /// Gives back the mutable and unique \e descriptor of the map.
1124 int operator[](const Item& item) const {
1125 return Map::operator[](item);
1130 typedef std::vector<Item> Container;
1134 /// \brief The inverse map type of DescriptorMap.
1136 /// The inverse map type of DescriptorMap.
1139 /// \brief Constructor of the InverseMap.
1141 /// Constructor of the InverseMap.
1142 InverseMap(const DescriptorMap& _inverted)
1143 : inverted(_inverted) {}
1146 /// The value type of the InverseMap.
1147 typedef typename DescriptorMap::Key Value;
1148 /// The key type of the InverseMap.
1149 typedef typename DescriptorMap::Value Key;
1151 /// \brief Subscript operator.
1153 /// Subscript operator. It gives back the item
1154 /// that the descriptor belongs to currently.
1155 Value operator[](const Key& key) const {
1156 return inverted.invMap[key];
1159 /// \brief Size of the map.
1161 /// Returns the size of the map.
1163 return inverted.invMap.size();
1167 const DescriptorMap& inverted;
1170 /// \brief Gives back the inverse of the map.
1172 /// Gives back the inverse of the map.
1173 const InverseMap inverse() const {
1174 return InverseMap(*this);
1178 /// \brief Returns the source of the given edge.
1180 /// The SourceMap gives back the source Node of the given edge.
1181 /// \author Balazs Dezso
1182 template <typename Graph>
1186 typedef typename Graph::Node Value;
1187 typedef typename Graph::Edge Key;
1189 /// \brief Constructor
1192 /// \param _graph The graph that the map belongs to.
1193 SourceMap(const Graph& _graph) : graph(_graph) {}
1195 /// \brief The subscript operator.
1197 /// The subscript operator.
1198 /// \param edge The edge
1199 /// \return The source of the edge
1200 Value operator[](const Key& edge) const {
1201 return graph.source(edge);
1208 /// \brief Returns a \ref SourceMap class
1210 /// This function just returns an \ref SourceMap class.
1211 /// \relates SourceMap
1212 template <typename Graph>
1213 inline SourceMap<Graph> sourceMap(const Graph& graph) {
1214 return SourceMap<Graph>(graph);
1217 /// \brief Returns the target of the given edge.
1219 /// The TargetMap gives back the target Node of the given edge.
1220 /// \author Balazs Dezso
1221 template <typename Graph>
1225 typedef typename Graph::Node Value;
1226 typedef typename Graph::Edge Key;
1228 /// \brief Constructor
1231 /// \param _graph The graph that the map belongs to.
1232 TargetMap(const Graph& _graph) : graph(_graph) {}
1234 /// \brief The subscript operator.
1236 /// The subscript operator.
1237 /// \param e The edge
1238 /// \return The target of the edge
1239 Value operator[](const Key& e) const {
1240 return graph.target(e);
1247 /// \brief Returns a \ref TargetMap class
1249 /// This function just returns a \ref TargetMap class.
1250 /// \relates TargetMap
1251 template <typename Graph>
1252 inline TargetMap<Graph> targetMap(const Graph& graph) {
1253 return TargetMap<Graph>(graph);
1256 /// \brief Returns the "forward" directed edge view of an undirected edge.
1258 /// Returns the "forward" directed edge view of an undirected edge.
1259 /// \author Balazs Dezso
1260 template <typename Graph>
1264 typedef typename Graph::Edge Value;
1265 typedef typename Graph::UndirEdge Key;
1267 /// \brief Constructor
1270 /// \param _graph The graph that the map belongs to.
1271 ForwardMap(const Graph& _graph) : graph(_graph) {}
1273 /// \brief The subscript operator.
1275 /// The subscript operator.
1276 /// \param key An undirected edge
1277 /// \return The "forward" directed edge view of undirected edge
1278 Value operator[](const Key& key) const {
1279 return graph.direct(key, true);
1286 /// \brief Returns a \ref ForwardMap class
1288 /// This function just returns an \ref ForwardMap class.
1289 /// \relates ForwardMap
1290 template <typename Graph>
1291 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1292 return ForwardMap<Graph>(graph);
1295 /// \brief Returns the "backward" directed edge view of an undirected edge.
1297 /// Returns the "backward" directed edge view of an undirected edge.
1298 /// \author Balazs Dezso
1299 template <typename Graph>
1303 typedef typename Graph::Edge Value;
1304 typedef typename Graph::UndirEdge Key;
1306 /// \brief Constructor
1309 /// \param _graph The graph that the map belongs to.
1310 BackwardMap(const Graph& _graph) : graph(_graph) {}
1312 /// \brief The subscript operator.
1314 /// The subscript operator.
1315 /// \param key An undirected edge
1316 /// \return The "backward" directed edge view of undirected edge
1317 Value operator[](const Key& key) const {
1318 return graph.direct(key, false);
1325 /// \brief Returns a \ref BackwardMap class
1327 /// This function just returns a \ref BackwardMap class.
1328 /// \relates BackwardMap
1329 template <typename Graph>
1330 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1331 return BackwardMap<Graph>(graph);
1334 /// \brief Potential difference map
1336 /// If there is an potential map on the nodes then we
1337 /// can get an edge map as we get the substraction of the
1338 /// values of the target and source.
1339 template <typename Graph, typename NodeMap>
1340 class PotentialDifferenceMap {
1342 typedef typename Graph::Edge Key;
1343 typedef typename NodeMap::Value Value;
1345 /// \brief Constructor
1347 /// Contructor of the map
1348 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1349 : graph(_graph), potential(_potential) {}
1351 /// \brief Const subscription operator
1353 /// Const subscription operator
1354 Value operator[](const Key& edge) const {
1355 return potential[graph.target(edge)] - potential[graph.source(edge)];
1360 const NodeMap& potential;
1363 /// \brief Just returns a PotentialDifferenceMap
1365 /// Just returns a PotentialDifferenceMap
1366 /// \relates PotentialDifferenceMap
1367 template <typename Graph, typename NodeMap>
1368 PotentialDifferenceMap<Graph, NodeMap>
1369 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1370 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1373 /// \brief Map of the node in-degrees.
1375 /// This map returns the in-degree of a node. Once it is constructed,
1376 /// the degrees are stored in a standard NodeMap, so each query is done
1377 /// in constant time. On the other hand, the values are updated automatically
1378 /// whenever the graph changes.
1380 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1381 /// alternative ways to modify the graph. The correct behavior of InDegMap
1382 /// is not guarantied if these additional featureas are used. For example
1383 /// the funstions \ref ListGraph::changeSource() "changeSource()",
1384 /// \ref ListGraph::changeTarget() "changeTarget()" and
1385 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1386 /// of \ref ListGraph will \e not update the degree values correctly.
1390 template <typename _Graph>
1392 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1396 typedef _Graph Graph;
1398 typedef typename Graph::Node Key;
1402 class AutoNodeMap : public Graph::template NodeMap<int> {
1405 typedef typename Graph::template NodeMap<int> Parent;
1407 typedef typename Parent::Key Key;
1408 typedef typename Parent::Value Value;
1410 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1412 void add(const Key& key) {
1414 Parent::set(key, 0);
1420 /// \brief Constructor.
1422 /// Constructor for creating in-degree map.
1423 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1424 AlterationNotifier<typename _Graph::Edge>
1425 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1427 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1428 deg[it] = countInEdges(graph, it);
1432 virtual ~InDegMap() {
1433 AlterationNotifier<typename _Graph::Edge>::
1434 ObserverBase::detach();
1437 /// Gives back the in-degree of a Node.
1438 int operator[](const Key& key) const {
1444 typedef typename Graph::Edge Edge;
1446 virtual void add(const Edge& edge) {
1447 ++deg[graph.target(edge)];
1450 virtual void erase(const Edge& edge) {
1451 --deg[graph.target(edge)];
1454 virtual void signalChange(const Edge& edge) {
1458 virtual void commitChange(const Edge& edge) {
1462 virtual void build() {
1463 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1464 deg[it] = countInEdges(graph, it);
1468 virtual void clear() {
1469 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1475 const _Graph& graph;
1479 /// \brief Map of the node out-degrees.
1481 /// This map returns the out-degree of a node. Once it is constructed,
1482 /// the degrees are stored in a standard NodeMap, so each query is done
1483 /// in constant time. On the other hand, the values are updated automatically
1484 /// whenever the graph changes.
1486 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1487 /// alternative ways to modify the graph. The correct behavior of OutDegMap
1488 /// is not guarantied if these additional featureas are used. For example
1489 /// the funstions \ref ListGraph::changeSource() "changeSource()",
1490 /// \ref ListGraph::changeTarget() "changeTarget()" and
1491 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1492 /// of \ref ListGraph will \e not update the degree values correctly.
1496 template <typename _Graph>
1498 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1502 typedef _Graph Graph;
1504 typedef typename Graph::Node Key;
1508 class AutoNodeMap : public Graph::template NodeMap<int> {
1511 typedef typename Graph::template NodeMap<int> Parent;
1513 typedef typename Parent::Key Key;
1514 typedef typename Parent::Value Value;
1516 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1518 void add(const Key& key) {
1520 Parent::set(key, 0);
1526 /// \brief Constructor.
1528 /// Constructor for creating out-degree map.
1529 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1530 AlterationNotifier<typename _Graph::Edge>
1531 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1533 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1534 deg[it] = countOutEdges(graph, it);
1538 virtual ~OutDegMap() {
1539 AlterationNotifier<typename _Graph::Edge>::
1540 ObserverBase::detach();
1543 /// Gives back the in-degree of a Node.
1544 int operator[](const Key& key) const {
1550 typedef typename Graph::Edge Edge;
1552 virtual void add(const Edge& edge) {
1553 ++deg[graph.source(edge)];
1556 virtual void erase(const Edge& edge) {
1557 --deg[graph.source(edge)];
1560 virtual void signalChange(const Edge& edge) {
1564 virtual void commitChange(const Edge& edge) {
1569 virtual void build() {
1570 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1571 deg[it] = countOutEdges(graph, it);
1575 virtual void clear() {
1576 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1582 const _Graph& graph;
1589 } //END OF NAMESPACE LEMON