NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
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