The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_GRAPH_UTILS_H
20 #define LEMON_GRAPH_UTILS_H
27 #include <lemon/invalid.h>
28 #include <lemon/utility.h>
29 #include <lemon/maps.h>
30 #include <lemon/traits.h>
32 #include <lemon/bits/alteration_notifier.h>
33 #include <lemon/bits/default_map.h>
37 ///\brief Graph utilities.
44 /// \addtogroup gutils
47 ///Creates convenience typedefs for the graph types and iterators
49 ///This \c \#define creates convenience typedefs for the following types
50 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
51 ///\c OutEdgeIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
52 ///\c BoolEdgeMap, \c IntEdgeMap, \c DoubleEdgeMap.
53 ///\note If \c G it a template parameter, it should be used in this way.
55 /// GRAPH_TYPEDEFS(typename G)
58 ///\warning There are no typedefs for the graph maps because of the lack of
59 ///template typedefs in C++.
60 #define GRAPH_TYPEDEFS(Graph) \
61 typedef Graph:: Node Node; \
62 typedef Graph:: NodeIt NodeIt; \
63 typedef Graph:: Edge Edge; \
64 typedef Graph:: EdgeIt EdgeIt; \
65 typedef Graph:: InEdgeIt InEdgeIt; \
66 typedef Graph::OutEdgeIt OutEdgeIt;
67 // typedef Graph::template NodeMap<bool> BoolNodeMap;
68 // typedef Graph::template NodeMap<int> IntNodeMap;
69 // typedef Graph::template NodeMap<double> DoubleNodeMap;
70 // typedef Graph::template EdgeMap<bool> BoolEdgeMap;
71 // typedef Graph::template EdgeMap<int> IntEdgeMap;
72 // typedef Graph::template EdgeMap<double> DoubleEdgeMap;
74 ///Creates convenience typedefs for the undirected graph types and iterators
76 ///This \c \#define creates the same convenience typedefs as defined by
77 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
78 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
79 ///\c BoolUEdgeMap, \c IntUEdgeMap, \c DoubleUEdgeMap.
81 ///\note If \c G it a template parameter, it should be used in this way.
83 /// UNDIRGRAPH_TYPEDEFS(typename G)
86 ///\warning There are no typedefs for the graph maps because of the lack of
87 ///template typedefs in C++.
88 #define UNDIRGRAPH_TYPEDEFS(Graph) \
89 GRAPH_TYPEDEFS(Graph) \
90 typedef Graph:: UEdge UEdge; \
91 typedef Graph:: UEdgeIt UEdgeIt; \
92 typedef Graph:: IncEdgeIt IncEdgeIt;
93 // typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;
94 // typedef Graph::template UEdgeMap<int> IntUEdgeMap;
95 // typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
99 /// \brief Function to count the items in the graph.
101 /// This function counts the items (nodes, edges etc) in the graph.
102 /// The complexity of the function is O(n) because
103 /// it iterates on all of the items.
105 template <typename Graph, typename ItemIt>
106 inline int countItems(const Graph& g) {
108 for (ItemIt it(g); it != INVALID; ++it) {
116 template <typename Graph>
117 inline typename enable_if<typename Graph::NodeNumTag, int>::type
118 _countNodes(const Graph &g) {
122 template <typename Graph>
123 inline int _countNodes(Wrap<Graph> w) {
124 return countItems<Graph, typename Graph::NodeIt>(w.value);
127 /// \brief Function to count the nodes in the graph.
129 /// This function counts the nodes in the graph.
130 /// The complexity of the function is O(n) but for some
131 /// graph structures it is specialized to run in O(1).
133 /// \todo refer how to specialize it
135 template <typename Graph>
136 inline int countNodes(const Graph& g) {
137 return _countNodes<Graph>(g);
142 template <typename Graph>
143 inline typename enable_if<typename Graph::EdgeNumTag, int>::type
144 _countEdges(const Graph &g) {
148 template <typename Graph>
149 inline int _countEdges(Wrap<Graph> w) {
150 return countItems<Graph, typename Graph::EdgeIt>(w.value);
153 /// \brief Function to count the edges in the graph.
155 /// This function counts the edges in the graph.
156 /// The complexity of the function is O(e) but for some
157 /// graph structures it is specialized to run in O(1).
159 template <typename Graph>
160 inline int countEdges(const Graph& g) {
161 return _countEdges<Graph>(g);
164 // Undirected edge counting:
166 template <typename Graph>
168 typename enable_if<typename Graph::EdgeNumTag, int>::type
169 _countUEdges(const Graph &g) {
173 template <typename Graph>
174 inline int _countUEdges(Wrap<Graph> w) {
175 return countItems<Graph, typename Graph::UEdgeIt>(w.value);
178 /// \brief Function to count the undirected edges in the graph.
180 /// This function counts the undirected edges in the graph.
181 /// The complexity of the function is O(e) but for some
182 /// graph structures it is specialized to run in O(1).
184 template <typename Graph>
185 inline int countUEdges(const Graph& g) {
186 return _countUEdges<Graph>(g);
191 template <typename Graph, typename DegIt>
192 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
194 for (DegIt it(_g, _n); it != INVALID; ++it) {
200 /// \brief Function to count the number of the out-edges from node \c n.
202 /// This function counts the number of the out-edges from node \c n
204 template <typename Graph>
205 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
206 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
209 /// \brief Function to count the number of the in-edges to node \c n.
211 /// This function counts the number of the in-edges to node \c n
213 template <typename Graph>
214 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
215 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
218 /// \brief Function to count the number of the inc-edges to node \c n.
220 /// This function counts the number of the inc-edges to node \c n
222 template <typename Graph>
223 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
224 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
228 template <typename Graph>
230 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
231 _findEdge(const Graph &g,
232 typename Graph::Node u, typename Graph::Node v,
233 typename Graph::Edge prev = INVALID) {
234 return g.findEdge(u, v, prev);
237 template <typename Graph>
238 inline typename Graph::Edge
239 _findEdge(Wrap<Graph> w,
240 typename Graph::Node u,
241 typename Graph::Node v,
242 typename Graph::Edge prev = INVALID) {
243 const Graph& g = w.value;
244 if (prev == INVALID) {
245 typename Graph::OutEdgeIt e(g, u);
246 while (e != INVALID && g.target(e) != v) ++e;
249 typename Graph::OutEdgeIt e(g, prev); ++e;
250 while (e != INVALID && g.target(e) != v) ++e;
255 /// \brief Finds an edge between two nodes of a graph.
257 /// Finds an edge from node \c u to node \c v in graph \c g.
259 /// If \c prev is \ref INVALID (this is the default value), then
260 /// it finds the first edge from \c u to \c v. Otherwise it looks for
261 /// the next edge from \c u to \c v after \c prev.
262 /// \return The found edge or \ref INVALID if there is no such an edge.
264 /// Thus you can iterate through each edge from \c u to \c v as it follows.
266 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
270 // /// \todo We may want to use the "GraphBase"
271 // /// interface here...
272 template <typename Graph>
273 inline typename Graph::Edge findEdge(const Graph &g,
274 typename Graph::Node u,
275 typename Graph::Node v,
276 typename Graph::Edge prev = INVALID) {
277 return _findEdge<Graph>(g, u, v, prev);
280 /// \brief Iterator for iterating on edges connected the same nodes.
282 /// Iterator for iterating on edges connected the same nodes. It is
283 /// higher level interface for the findEdge() function. You can
284 /// use it the following way:
286 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
291 /// \author Balazs Dezso
292 template <typename _Graph>
293 class ConEdgeIt : public _Graph::Edge {
296 typedef _Graph Graph;
297 typedef typename Graph::Edge Parent;
299 typedef typename Graph::Edge Edge;
300 typedef typename Graph::Node Node;
302 /// \brief Constructor.
304 /// Construct a new ConEdgeIt iterating on the edges which
305 /// connects the \c u and \c v node.
306 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
307 Parent::operator=(findEdge(graph, u, v));
310 /// \brief Constructor.
312 /// Construct a new ConEdgeIt which continues the iterating from
314 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
316 /// \brief Increment operator.
318 /// It increments the iterator and gives back the next edge.
319 ConEdgeIt& operator++() {
320 Parent::operator=(findEdge(graph, graph.source(*this),
321 graph.target(*this), *this));
328 template <typename Graph>
331 typename Graph::FindEdgeTag,
332 typename Graph::UEdge>::type
333 _findUEdge(const Graph &g,
334 typename Graph::Node u, typename Graph::Node v,
335 typename Graph::UEdge prev = INVALID) {
336 return g.findUEdge(u, v, prev);
339 template <typename Graph>
340 inline typename Graph::UEdge
341 _findUEdge(Wrap<Graph> w,
342 typename Graph::Node u,
343 typename Graph::Node v,
344 typename Graph::UEdge prev = INVALID) {
345 const Graph& g = w.value;
346 if (prev == INVALID) {
347 typename Graph::OutEdgeIt e(g, u);
348 while (e != INVALID && g.target(e) != v) ++e;
351 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
352 while (e != INVALID && g.target(e) != v) ++e;
357 /// \brief Finds an uedge between two nodes of a graph.
359 /// Finds an uedge from node \c u to node \c v in graph \c g.
361 /// If \c prev is \ref INVALID (this is the default value), then
362 /// it finds the first edge from \c u to \c v. Otherwise it looks for
363 /// the next edge from \c u to \c v after \c prev.
364 /// \return The found edge or \ref INVALID if there is no such an edge.
366 /// Thus you can iterate through each edge from \c u to \c v as it follows.
368 /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
369 /// e = findUEdge(g,u,v,e)) {
373 // /// \todo We may want to use the "GraphBase"
374 // /// interface here...
375 template <typename Graph>
376 inline typename Graph::UEdge
377 findUEdge(const Graph &g,
378 typename Graph::Node u,
379 typename Graph::Node v,
380 typename Graph::UEdge prev = INVALID) {
381 return _findUEdge<Graph>(g, u, v, prev);
384 /// \brief Iterator for iterating on uedges connected the same nodes.
386 /// Iterator for iterating on uedges connected the same nodes. It is
387 /// higher level interface for the findUEdge() function. You can
388 /// use it the following way:
390 /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
395 /// \author Balazs Dezso
396 template <typename _Graph>
397 class ConUEdgeIt : public _Graph::UEdge {
400 typedef _Graph Graph;
401 typedef typename Graph::UEdge Parent;
403 typedef typename Graph::UEdge UEdge;
404 typedef typename Graph::Node Node;
406 /// \brief Constructor.
408 /// Construct a new ConUEdgeIt iterating on the edges which
409 /// connects the \c u and \c v node.
410 ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
411 Parent::operator=(findUEdge(graph, u, v));
414 /// \brief Constructor.
416 /// Construct a new ConUEdgeIt which continues the iterating from
418 ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
420 /// \brief Increment operator.
422 /// It increments the iterator and gives back the next edge.
423 ConUEdgeIt& operator++() {
424 Parent::operator=(findUEdge(graph, graph.source(*this),
425 graph.target(*this), *this));
432 /// \brief Copy a map.
434 /// This function copies the \c source map to the \c target map. It uses the
435 /// given iterator to iterate on the data structure and it uses the \c ref
436 /// mapping to convert the source's keys to the target's keys.
437 template <typename Target, typename Source,
438 typename ItemIt, typename Ref>
439 void copyMap(Target& target, const Source& source,
440 ItemIt it, const Ref& ref) {
441 for (; it != INVALID; ++it) {
442 target[ref[it]] = source[it];
446 /// \brief Copy the source map to the target map.
448 /// Copy the \c source map to the \c target map. It uses the given iterator
449 /// to iterate on the data structure.
450 template <typename Target, typename Source, typename ItemIt>
451 void copyMap(Target& target, const Source& source, ItemIt it) {
452 for (; it != INVALID; ++it) {
453 target[it] = source[it];
457 /// \brief Class to copy a graph.
459 /// Class to copy a graph to an other graph (duplicate a graph). The
460 /// simplest way of using it is through the \c copyGraph() function.
461 template <typename Target, typename Source>
464 typedef typename Source::Node Node;
465 typedef typename Source::NodeIt NodeIt;
466 typedef typename Source::Edge Edge;
467 typedef typename Source::EdgeIt EdgeIt;
469 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
470 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
472 /// \brief Constructor for the GraphCopy.
474 /// It copies the content of the \c _source graph into the
475 /// \c _target graph. It creates also two references, one beetween
476 /// the two nodeset and one beetween the two edgesets.
477 GraphCopy(Target& _target, const Source& _source)
478 : source(_source), target(_target),
479 nodeRefMap(_source), edgeRefMap(_source) {
480 for (NodeIt it(source); it != INVALID; ++it) {
481 nodeRefMap[it] = target.addNode();
483 for (EdgeIt it(source); it != INVALID; ++it) {
484 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
485 nodeRefMap[source.target(it)]);
489 /// \brief Copies the node references into the given map.
491 /// Copies the node references into the given map.
492 template <typename NodeRef>
493 const GraphCopy& nodeRef(NodeRef& map) const {
494 for (NodeIt it(source); it != INVALID; ++it) {
495 map.set(it, nodeRefMap[it]);
500 /// \brief Reverse and copies the node references into the given map.
502 /// Reverse and copies the node references into the given map.
503 template <typename NodeRef>
504 const GraphCopy& nodeCrossRef(NodeRef& map) const {
505 for (NodeIt it(source); it != INVALID; ++it) {
506 map.set(nodeRefMap[it], it);
511 /// \brief Copies the edge references into the given map.
513 /// Copies the edge references into the given map.
514 template <typename EdgeRef>
515 const GraphCopy& edgeRef(EdgeRef& map) const {
516 for (EdgeIt it(source); it != INVALID; ++it) {
517 map.set(it, edgeRefMap[it]);
522 /// \brief Reverse and copies the edge references into the given map.
524 /// Reverse and copies the edge references into the given map.
525 template <typename EdgeRef>
526 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
527 for (EdgeIt it(source); it != INVALID; ++it) {
528 map.set(edgeRefMap[it], it);
533 /// \brief Make copy of the given map.
535 /// Makes copy of the given map for the newly created graph.
536 /// The new map's key type is the target graph's node type,
537 /// and the copied map's key type is the source graph's node
539 template <typename TargetMap, typename SourceMap>
540 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
541 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
545 /// \brief Make copy of the given map.
547 /// Makes copy of the given map for the newly created graph.
548 /// The new map's key type is the target graph's edge type,
549 /// and the copied map's key type is the source graph's edge
551 template <typename TargetMap, typename SourceMap>
552 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
553 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
557 /// \brief Gives back the stored node references.
559 /// Gives back the stored node references.
560 const NodeRefMap& nodeRef() const {
564 /// \brief Gives back the stored edge references.
566 /// Gives back the stored edge references.
567 const EdgeRefMap& edgeRef() const {
575 const Source& source;
578 NodeRefMap nodeRefMap;
579 EdgeRefMap edgeRefMap;
582 /// \brief Copy a graph to an other graph.
584 /// Copy a graph to an other graph.
585 /// The usage of the function:
588 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
591 /// After the copy the \c nr map will contain the mapping from the
592 /// source graph's nodes to the target graph's nodes and the \c ecr will
593 /// contain the mapping from the target graph's edges to the source's
595 template <typename Target, typename Source>
596 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
597 return GraphCopy<Target, Source>(target, source);
600 /// \brief Class to copy an undirected graph.
602 /// Class to copy an undirected graph to an other graph (duplicate a graph).
603 /// The simplest way of using it is through the \c copyUGraph() function.
604 template <typename Target, typename Source>
607 typedef typename Source::Node Node;
608 typedef typename Source::NodeIt NodeIt;
609 typedef typename Source::Edge Edge;
610 typedef typename Source::EdgeIt EdgeIt;
611 typedef typename Source::UEdge UEdge;
612 typedef typename Source::UEdgeIt UEdgeIt;
614 typedef typename Source::
615 template NodeMap<typename Target::Node> NodeRefMap;
617 typedef typename Source::
618 template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
623 EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
624 typedef typename Source::Edge Key;
625 typedef typename Target::Edge Value;
627 Value operator[](const Key& key) {
628 return gc.target.direct(gc.uEdgeRef[key],
629 gc.target.direction(key));
637 /// \brief Constructor for the UGraphCopy.
639 /// It copies the content of the \c _source graph into the
640 /// \c _target graph. It creates also two references, one beetween
641 /// the two nodeset and one beetween the two edgesets.
642 UGraphCopy(Target& _target, const Source& _source)
643 : source(_source), target(_target),
644 nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
645 for (NodeIt it(source); it != INVALID; ++it) {
646 nodeRefMap[it] = target.addNode();
648 for (UEdgeIt it(source); it != INVALID; ++it) {
649 uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
650 nodeRefMap[source.target(it)]);
654 /// \brief Copies the node references into the given map.
656 /// Copies the node references into the given map.
657 template <typename NodeRef>
658 const UGraphCopy& nodeRef(NodeRef& map) const {
659 for (NodeIt it(source); it != INVALID; ++it) {
660 map.set(it, nodeRefMap[it]);
665 /// \brief Reverse and copies the node references into the given map.
667 /// Reverse and copies the node references into the given map.
668 template <typename NodeRef>
669 const UGraphCopy& nodeCrossRef(NodeRef& map) const {
670 for (NodeIt it(source); it != INVALID; ++it) {
671 map.set(nodeRefMap[it], it);
676 /// \brief Copies the edge references into the given map.
678 /// Copies the edge references into the given map.
679 template <typename EdgeRef>
680 const UGraphCopy& edgeRef(EdgeRef& map) const {
681 for (EdgeIt it(source); it != INVALID; ++it) {
682 map.set(edgeRefMap[it], it);
687 /// \brief Reverse and copies the undirected edge references into the
690 /// Reverse and copies the undirected edge references into the given map.
691 template <typename EdgeRef>
692 const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
693 for (EdgeIt it(source); it != INVALID; ++it) {
694 map.set(it, edgeRefMap[it]);
699 /// \brief Copies the undirected edge references into the given map.
701 /// Copies the undirected edge references into the given map.
702 template <typename EdgeRef>
703 const UGraphCopy& uEdgeRef(EdgeRef& map) const {
704 for (UEdgeIt it(source); it != INVALID; ++it) {
705 map.set(it, uEdgeRefMap[it]);
710 /// \brief Reverse and copies the undirected edge references into the
713 /// Reverse and copies the undirected edge references into the given map.
714 template <typename EdgeRef>
715 const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
716 for (UEdgeIt it(source); it != INVALID; ++it) {
717 map.set(uEdgeRefMap[it], it);
722 /// \brief Make copy of the given map.
724 /// Makes copy of the given map for the newly created graph.
725 /// The new map's key type is the target graph's node type,
726 /// and the copied map's key type is the source graph's node
728 template <typename TargetMap, typename SourceMap>
729 const UGraphCopy& nodeMap(TargetMap& tMap,
730 const SourceMap& sMap) const {
731 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
735 /// \brief Make copy of the given map.
737 /// Makes copy of the given map for the newly created graph.
738 /// The new map's key type is the target graph's edge type,
739 /// and the copied map's key type is the source graph's edge
741 template <typename TargetMap, typename SourceMap>
742 const UGraphCopy& edgeMap(TargetMap& tMap,
743 const SourceMap& sMap) const {
744 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
748 /// \brief Make copy of the given map.
750 /// Makes copy of the given map for the newly created graph.
751 /// The new map's key type is the target graph's edge type,
752 /// and the copied map's key type is the source graph's edge
754 template <typename TargetMap, typename SourceMap>
755 const UGraphCopy& uEdgeMap(TargetMap& tMap,
756 const SourceMap& sMap) const {
757 copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
761 /// \brief Gives back the stored node references.
763 /// Gives back the stored node references.
764 const NodeRefMap& nodeRef() const {
768 /// \brief Gives back the stored edge references.
770 /// Gives back the stored edge references.
771 const EdgeRefMap& edgeRef() const {
775 /// \brief Gives back the stored uedge references.
777 /// Gives back the stored uedge references.
778 const UEdgeRefMap& uEdgeRef() const {
786 const Source& source;
789 NodeRefMap nodeRefMap;
790 EdgeRefMap edgeRefMap;
791 UEdgeRefMap uEdgeRefMap;
794 /// \brief Copy a graph to an other graph.
796 /// Copy a graph to an other graph.
797 /// The usage of the function:
800 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
803 /// After the copy the \c nr map will contain the mapping from the
804 /// source graph's nodes to the target graph's nodes and the \c ecr will
805 /// contain the mapping from the target graph's edges to the source's
807 template <typename Target, typename Source>
808 UGraphCopy<Target, Source>
809 copyUGraph(Target& target, const Source& source) {
810 return UGraphCopy<Target, Source>(target, source);
816 /// \addtogroup graph_maps
819 /// Provides an immutable and unique id for each item in the graph.
821 /// The IdMap class provides a unique and immutable id for each item of the
822 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
823 /// different items (nodes) get different ids <li>\b immutable: the id of an
824 /// item (node) does not change (even if you delete other nodes). </ul>
825 /// Through this map you get access (i.e. can read) the inner id values of
826 /// the items stored in the graph. This map can be inverted with its member
827 /// class \c InverseMap.
829 template <typename _Graph, typename _Item>
832 typedef _Graph Graph;
837 /// \brief Constructor.
839 /// Constructor for creating id map.
840 IdMap(const Graph& _graph) : graph(&_graph) {}
842 /// \brief Gives back the \e id of the item.
844 /// Gives back the immutable and unique \e id of the map.
845 int operator[](const Item& item) const { return graph->id(item);}
853 /// \brief The class represents the inverse of its owner (IdMap).
855 /// The class represents the inverse of its owner (IdMap).
860 /// \brief Constructor.
862 /// Constructor for creating an id-to-item map.
863 InverseMap(const Graph& _graph) : graph(&_graph) {}
865 /// \brief Constructor.
867 /// Constructor for creating an id-to-item map.
868 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
870 /// \brief Gives back the given item from its id.
872 /// Gives back the given item from its id.
874 Item operator[](int id) const { return graph->fromId(id, Item());}
879 /// \brief Gives back the inverse of the map.
881 /// Gives back the inverse of the IdMap.
882 InverseMap inverse() const { return InverseMap(*graph);}
887 /// \brief General invertable graph-map type.
889 /// This type provides simple invertable graph-maps.
890 /// The InvertableMap wraps an arbitrary ReadWriteMap
891 /// and if a key is set to a new value then store it
892 /// in the inverse map.
894 /// The values of the map can be accessed
895 /// with stl compatible forward iterator.
897 /// \param _Graph The graph type.
898 /// \param _Item The item type of the graph.
899 /// \param _Value The value type of the map.
901 /// \see IterableValueMap
903 /// \param _Map A ReadWriteMap mapping from the item type to integer.
905 typename _Graph, typename _Item, typename _Value,
906 typename _Map = DefaultMap<_Graph, _Item, _Value>
909 template <typename _Graph, typename _Item, typename _Value>
911 class InvertableMap : protected _Map {
914 /// The key type of InvertableMap (Node, Edge, UEdge).
915 typedef typename _Map::Key Key;
916 /// The value type of the InvertableMap.
917 typedef typename _Map::Value Value;
922 typedef _Graph Graph;
924 typedef std::map<Value, Key> Container;
931 /// \brief Constructor.
933 /// Construct a new InvertableMap for the graph.
935 InvertableMap(const Graph& graph) : Map(graph) {}
937 /// \brief Forward iterator for values.
939 /// This iterator is an stl compatible forward
940 /// iterator on the values of the map. The values can
941 /// be accessed in the [beginValue, endValue) range.
944 : public std::iterator<std::forward_iterator_tag, Value> {
945 friend class InvertableMap;
947 ValueIterator(typename Container::const_iterator _it)
953 ValueIterator& operator++() { ++it; return *this; }
954 ValueIterator operator++(int) {
955 ValueIterator tmp(*this);
960 const Value& operator*() const { return it->first; }
961 const Value* operator->() const { return &(it->first); }
963 bool operator==(ValueIterator jt) const { return it == jt.it; }
964 bool operator!=(ValueIterator jt) const { return it != jt.it; }
967 typename Container::const_iterator it;
970 /// \brief Returns an iterator to the first value.
972 /// Returns an stl compatible iterator to the
973 /// first value of the map. The values of the
974 /// map can be accessed in the [beginValue, endValue)
976 ValueIterator beginValue() const {
977 return ValueIterator(invMap.begin());
980 /// \brief Returns an iterator after the last value.
982 /// Returns an stl compatible iterator after the
983 /// last value of the map. The values of the
984 /// map can be accessed in the [beginValue, endValue)
986 ValueIterator endValue() const {
987 return ValueIterator(invMap.end());
990 /// \brief The setter function of the map.
992 /// Sets the mapped value.
993 void set(const Key& key, const Value& val) {
994 Value oldval = Map::operator[](key);
995 typename Container::iterator it = invMap.find(oldval);
996 if (it != invMap.end() && it->second == key) {
999 invMap.insert(make_pair(val, key));
1003 /// \brief The getter function of the map.
1005 /// It gives back the value associated with the key.
1006 typename MapTraits<Map>::ConstReturnValue
1007 operator[](const Key& key) const {
1008 return Map::operator[](key);
1013 /// \brief Erase the key from the map.
1015 /// Erase the key to the map. It is called by the
1016 /// \c AlterationNotifier.
1017 virtual void erase(const Key& key) {
1018 Value val = Map::operator[](key);
1019 typename Container::iterator it = invMap.find(val);
1020 if (it != invMap.end() && it->second == key) {
1026 /// \brief Erase more keys from the map.
1028 /// Erase more keys from the map. It is called by the
1029 /// \c AlterationNotifier.
1030 virtual void erase(const std::vector<Key>& keys) {
1031 for (int i = 0; i < (int)keys.size(); ++i) {
1032 Value val = Map::operator[](keys[i]);
1033 typename Container::iterator it = invMap.find(val);
1034 if (it != invMap.end() && it->second == keys[i]) {
1041 /// \brief Clear the keys from the map and inverse map.
1043 /// Clear the keys from the map and inverse map. It is called by the
1044 /// \c AlterationNotifier.
1045 virtual void clear() {
1052 /// \brief The inverse map type.
1054 /// The inverse of this map. The subscript operator of the map
1055 /// gives back always the item what was last assigned to the value.
1058 /// \brief Constructor of the InverseMap.
1060 /// Constructor of the InverseMap.
1061 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
1063 /// The value type of the InverseMap.
1064 typedef typename InvertableMap::Key Value;
1065 /// The key type of the InverseMap.
1066 typedef typename InvertableMap::Value Key;
1068 /// \brief Subscript operator.
1070 /// Subscript operator. It gives back always the item
1071 /// what was last assigned to the value.
1072 Value operator[](const Key& key) const {
1073 typename Container::const_iterator it = inverted.invMap.find(key);
1078 const InvertableMap& inverted;
1081 /// \brief It gives back the just readeable inverse map.
1083 /// It gives back the just readeable inverse map.
1084 InverseMap inverse() const {
1085 return InverseMap(*this);
1092 /// \brief Provides a mutable, continuous and unique descriptor for each
1093 /// item in the graph.
1095 /// The DescriptorMap class provides a unique and continuous (but mutable)
1096 /// descriptor (id) for each item of the same type (e.g. node) in the
1097 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1098 /// different ids <li>\b continuous: the range of the ids is the set of
1099 /// integers between 0 and \c n-1, where \c n is the number of the items of
1100 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1101 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1102 /// with its member class \c InverseMap.
1104 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1105 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1108 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1110 typename _Graph, typename _Item,
1111 typename _Map = DefaultMap<_Graph, _Item, int>
1114 template <typename _Graph, typename _Item>
1116 class DescriptorMap : protected _Map {
1122 /// The graph class of DescriptorMap.
1123 typedef _Graph Graph;
1125 /// The key type of DescriptorMap (Node, Edge, UEdge).
1126 typedef typename _Map::Key Key;
1127 /// The value type of DescriptorMap.
1128 typedef typename _Map::Value Value;
1130 /// \brief Constructor.
1132 /// Constructor for descriptor map.
1133 DescriptorMap(const Graph& _graph) : Map(_graph) {
1139 /// \brief Add a new key to the map.
1141 /// Add a new key to the map. It is called by the
1142 /// \c AlterationNotifier.
1143 virtual void add(const Item& item) {
1145 Map::set(item, invMap.size());
1146 invMap.push_back(item);
1149 /// \brief Add more new keys to the map.
1151 /// Add more new keys to the map. It is called by the
1152 /// \c AlterationNotifier.
1153 virtual void add(const std::vector<Item>& items) {
1155 for (int i = 0; i < (int)items.size(); ++i) {
1156 Map::set(items[i], invMap.size());
1157 invMap.push_back(items[i]);
1161 /// \brief Erase the key from the map.
1163 /// Erase the key from the map. It is called by the
1164 /// \c AlterationNotifier.
1165 virtual void erase(const Item& item) {
1166 Map::set(invMap.back(), Map::operator[](item));
1167 invMap[Map::operator[](item)] = invMap.back();
1172 /// \brief Erase more keys from the map.
1174 /// Erase more keys from the map. It is called by the
1175 /// \c AlterationNotifier.
1176 virtual void erase(const std::vector<Item>& items) {
1177 for (int i = 0; i < (int)items.size(); ++i) {
1178 Map::set(invMap.back(), Map::operator[](items[i]));
1179 invMap[Map::operator[](items[i])] = invMap.back();
1185 /// \brief Build the unique map.
1187 /// Build the unique map. It is called by the
1188 /// \c AlterationNotifier.
1189 virtual void build() {
1192 const typename Map::Graph* graph = Map::getGraph();
1193 for (graph->first(it); it != INVALID; graph->next(it)) {
1194 Map::set(it, invMap.size());
1195 invMap.push_back(it);
1199 /// \brief Clear the keys from the map.
1201 /// Clear the keys from the map. It is called by the
1202 /// \c AlterationNotifier.
1203 virtual void clear() {
1210 /// \brief Returns the maximal value plus one.
1212 /// Returns the maximal value plus one in the map.
1213 unsigned int size() const {
1214 return invMap.size();
1217 /// \brief Swaps the position of the two items in the map.
1219 /// Swaps the position of the two items in the map.
1220 void swap(const Item& p, const Item& q) {
1221 int pi = Map::operator[](p);
1222 int qi = Map::operator[](q);
1229 /// \brief Gives back the \e descriptor of the item.
1231 /// Gives back the mutable and unique \e descriptor of the map.
1232 int operator[](const Item& item) const {
1233 return Map::operator[](item);
1238 typedef std::vector<Item> Container;
1242 /// \brief The inverse map type of DescriptorMap.
1244 /// The inverse map type of DescriptorMap.
1247 /// \brief Constructor of the InverseMap.
1249 /// Constructor of the InverseMap.
1250 InverseMap(const DescriptorMap& _inverted)
1251 : inverted(_inverted) {}
1254 /// The value type of the InverseMap.
1255 typedef typename DescriptorMap::Key Value;
1256 /// The key type of the InverseMap.
1257 typedef typename DescriptorMap::Value Key;
1259 /// \brief Subscript operator.
1261 /// Subscript operator. It gives back the item
1262 /// that the descriptor belongs to currently.
1263 Value operator[](const Key& key) const {
1264 return inverted.invMap[key];
1267 /// \brief Size of the map.
1269 /// Returns the size of the map.
1270 unsigned int size() const {
1271 return inverted.invMap.size();
1275 const DescriptorMap& inverted;
1278 /// \brief Gives back the inverse of the map.
1280 /// Gives back the inverse of the map.
1281 const InverseMap inverse() const {
1282 return InverseMap(*this);
1286 /// \brief Returns the source of the given edge.
1288 /// The SourceMap gives back the source Node of the given edge.
1289 /// \author Balazs Dezso
1290 template <typename Graph>
1294 typedef typename Graph::Node Value;
1295 typedef typename Graph::Edge Key;
1297 /// \brief Constructor
1300 /// \param _graph The graph that the map belongs to.
1301 SourceMap(const Graph& _graph) : graph(_graph) {}
1303 /// \brief The subscript operator.
1305 /// The subscript operator.
1306 /// \param edge The edge
1307 /// \return The source of the edge
1308 Value operator[](const Key& edge) const {
1309 return graph.source(edge);
1316 /// \brief Returns a \ref SourceMap class
1318 /// This function just returns an \ref SourceMap class.
1319 /// \relates SourceMap
1320 template <typename Graph>
1321 inline SourceMap<Graph> sourceMap(const Graph& graph) {
1322 return SourceMap<Graph>(graph);
1325 /// \brief Returns the target of the given edge.
1327 /// The TargetMap gives back the target Node of the given edge.
1328 /// \author Balazs Dezso
1329 template <typename Graph>
1333 typedef typename Graph::Node Value;
1334 typedef typename Graph::Edge Key;
1336 /// \brief Constructor
1339 /// \param _graph The graph that the map belongs to.
1340 TargetMap(const Graph& _graph) : graph(_graph) {}
1342 /// \brief The subscript operator.
1344 /// The subscript operator.
1345 /// \param e The edge
1346 /// \return The target of the edge
1347 Value operator[](const Key& e) const {
1348 return graph.target(e);
1355 /// \brief Returns a \ref TargetMap class
1357 /// This function just returns a \ref TargetMap class.
1358 /// \relates TargetMap
1359 template <typename Graph>
1360 inline TargetMap<Graph> targetMap(const Graph& graph) {
1361 return TargetMap<Graph>(graph);
1364 /// \brief Returns the "forward" directed edge view of an undirected edge.
1366 /// Returns the "forward" directed edge view of an undirected edge.
1367 /// \author Balazs Dezso
1368 template <typename Graph>
1372 typedef typename Graph::Edge Value;
1373 typedef typename Graph::UEdge Key;
1375 /// \brief Constructor
1378 /// \param _graph The graph that the map belongs to.
1379 ForwardMap(const Graph& _graph) : graph(_graph) {}
1381 /// \brief The subscript operator.
1383 /// The subscript operator.
1384 /// \param key An undirected edge
1385 /// \return The "forward" directed edge view of undirected edge
1386 Value operator[](const Key& key) const {
1387 return graph.direct(key, true);
1394 /// \brief Returns a \ref ForwardMap class
1396 /// This function just returns an \ref ForwardMap class.
1397 /// \relates ForwardMap
1398 template <typename Graph>
1399 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1400 return ForwardMap<Graph>(graph);
1403 /// \brief Returns the "backward" directed edge view of an undirected edge.
1405 /// Returns the "backward" directed edge view of an undirected edge.
1406 /// \author Balazs Dezso
1407 template <typename Graph>
1411 typedef typename Graph::Edge Value;
1412 typedef typename Graph::UEdge Key;
1414 /// \brief Constructor
1417 /// \param _graph The graph that the map belongs to.
1418 BackwardMap(const Graph& _graph) : graph(_graph) {}
1420 /// \brief The subscript operator.
1422 /// The subscript operator.
1423 /// \param key An undirected edge
1424 /// \return The "backward" directed edge view of undirected edge
1425 Value operator[](const Key& key) const {
1426 return graph.direct(key, false);
1433 /// \brief Returns a \ref BackwardMap class
1435 /// This function just returns a \ref BackwardMap class.
1436 /// \relates BackwardMap
1437 template <typename Graph>
1438 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1439 return BackwardMap<Graph>(graph);
1442 /// \brief Potential difference map
1444 /// If there is an potential map on the nodes then we
1445 /// can get an edge map as we get the substraction of the
1446 /// values of the target and source.
1447 template <typename Graph, typename NodeMap>
1448 class PotentialDifferenceMap {
1450 typedef typename Graph::Edge Key;
1451 typedef typename NodeMap::Value Value;
1453 /// \brief Constructor
1455 /// Contructor of the map
1456 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1457 : graph(_graph), potential(_potential) {}
1459 /// \brief Const subscription operator
1461 /// Const subscription operator
1462 Value operator[](const Key& edge) const {
1463 return potential[graph.target(edge)] - potential[graph.source(edge)];
1468 const NodeMap& potential;
1471 /// \brief Just returns a PotentialDifferenceMap
1473 /// Just returns a PotentialDifferenceMap
1474 /// \relates PotentialDifferenceMap
1475 template <typename Graph, typename NodeMap>
1476 PotentialDifferenceMap<Graph, NodeMap>
1477 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1478 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1481 /// \brief Map of the node in-degrees.
1483 /// This map returns the in-degree of a node. Once it is constructed,
1484 /// the degrees are stored in a standard NodeMap, so each query is done
1485 /// in constant time. On the other hand, the values are updated automatically
1486 /// whenever the graph changes.
1488 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1489 /// alternative ways to modify the graph. The correct behavior of InDegMap
1490 /// is not guarantied if these additional features are used. For example
1491 /// the functions \ref ListGraph::changeSource() "changeSource()",
1492 /// \ref ListGraph::changeTarget() "changeTarget()" and
1493 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1494 /// of \ref ListGraph will \e not update the degree values correctly.
1498 template <typename _Graph>
1500 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1504 typedef _Graph Graph;
1506 typedef typename Graph::Node Key;
1510 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1513 typedef DefaultMap<_Graph, Key, int> Parent;
1515 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1517 virtual void add(const Key& key) {
1519 Parent::set(key, 0);
1522 virtual void add(const std::vector<Key>& keys) {
1524 for (int i = 0; i < (int)keys.size(); ++i) {
1525 Parent::set(keys[i], 0);
1532 /// \brief Constructor.
1534 /// Constructor for creating in-degree map.
1535 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1536 AlterationNotifier<typename _Graph::Edge>
1537 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1539 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1540 deg[it] = countInEdges(graph, it);
1544 virtual ~InDegMap() {
1545 AlterationNotifier<typename _Graph::Edge>::
1546 ObserverBase::detach();
1549 /// Gives back the in-degree of a Node.
1550 int operator[](const Key& key) const {
1556 typedef typename Graph::Edge Edge;
1558 virtual void add(const Edge& edge) {
1559 ++deg[graph.target(edge)];
1562 virtual void add(const std::vector<Edge>& edges) {
1563 for (int i = 0; i < (int)edges.size(); ++i) {
1564 ++deg[graph.target(edges[i])];
1568 virtual void erase(const Edge& edge) {
1569 --deg[graph.target(edge)];
1572 virtual void erase(const std::vector<Edge>& edges) {
1573 for (int i = 0; i < (int)edges.size(); ++i) {
1574 --deg[graph.target(edges[i])];
1578 virtual void build() {
1579 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1580 deg[it] = countInEdges(graph, it);
1584 virtual void clear() {
1585 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1591 const _Graph& graph;
1595 /// \brief Map of the node out-degrees.
1597 /// This map returns the out-degree of a node. Once it is constructed,
1598 /// the degrees are stored in a standard NodeMap, so each query is done
1599 /// in constant time. On the other hand, the values are updated automatically
1600 /// whenever the graph changes.
1602 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1603 /// alternative ways to modify the graph. The correct behavior of OutDegMap
1604 /// is not guarantied if these additional features are used. For example
1605 /// the functions \ref ListGraph::changeSource() "changeSource()",
1606 /// \ref ListGraph::changeTarget() "changeTarget()" and
1607 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1608 /// of \ref ListGraph will \e not update the degree values correctly.
1612 template <typename _Graph>
1614 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1618 typedef _Graph Graph;
1620 typedef typename Graph::Node Key;
1624 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1627 typedef DefaultMap<_Graph, Key, int> Parent;
1629 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1631 virtual void add(const Key& key) {
1633 Parent::set(key, 0);
1635 virtual void add(const std::vector<Key>& keys) {
1637 for (int i = 0; i < (int)keys.size(); ++i) {
1638 Parent::set(keys[i], 0);
1645 /// \brief Constructor.
1647 /// Constructor for creating out-degree map.
1648 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1649 AlterationNotifier<typename _Graph::Edge>
1650 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1652 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1653 deg[it] = countOutEdges(graph, it);
1657 virtual ~OutDegMap() {
1658 AlterationNotifier<typename _Graph::Edge>::
1659 ObserverBase::detach();
1662 /// Gives back the out-degree of a Node.
1663 int operator[](const Key& key) const {
1669 typedef typename Graph::Edge Edge;
1671 virtual void add(const Edge& edge) {
1672 ++deg[graph.source(edge)];
1675 virtual void add(const std::vector<Edge>& edges) {
1676 for (int i = 0; i < (int)edges.size(); ++i) {
1677 ++deg[graph.source(edges[i])];
1681 virtual void erase(const Edge& edge) {
1682 --deg[graph.source(edge)];
1685 virtual void erase(const std::vector<Edge>& edges) {
1686 for (int i = 0; i < (int)edges.size(); ++i) {
1687 --deg[graph.source(edges[i])];
1691 virtual void build() {
1692 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1693 deg[it] = countOutEdges(graph, it);
1697 virtual void clear() {
1698 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1704 const _Graph& graph;
1711 } //END OF NAMESPACE LEMON