Set props.
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/bits/invalid.h>
28 #include <lemon/bits/utility.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/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,
52 ///\note If \c G it a template parameter, it should be used in this way.
54 /// GRAPH_TYPEDEFS(typename G)
57 ///\warning There are no typedefs for the graph maps because of the lack of
58 ///template typedefs in C++.
59 #define GRAPH_TYPEDEFS(Graph) \
60 typedef Graph:: Node Node; \
61 typedef Graph:: NodeIt NodeIt; \
62 typedef Graph:: Edge Edge; \
63 typedef Graph:: EdgeIt EdgeIt; \
64 typedef Graph:: InEdgeIt InEdgeIt; \
65 typedef Graph::OutEdgeIt OutEdgeIt;
67 ///Creates convenience typedefs for the undirected graph types and iterators
69 ///This \c \#define creates the same convenience typedefs as defined by
70 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
71 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
73 ///\note If \c G it a template parameter, it should be used in this way.
75 /// UGRAPH_TYPEDEFS(typename G)
78 ///\warning There are no typedefs for the graph maps because of the lack of
79 ///template typedefs in C++.
80 #define UGRAPH_TYPEDEFS(Graph) \
81 GRAPH_TYPEDEFS(Graph) \
82 typedef Graph:: UEdge UEdge; \
83 typedef Graph:: UEdgeIt UEdgeIt; \
84 typedef Graph:: IncEdgeIt IncEdgeIt;
85 // typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;
86 // typedef Graph::template UEdgeMap<int> IntUEdgeMap;
87 // typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
89 ///\brief Creates convenience typedefs for the bipartite undirected graph
90 ///types and iterators
92 ///This \c \#define creates the same convenience typedefs as defined by
93 ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates
94 ///\c ANodeIt, \c BNodeIt,
96 ///\note If \c G it a template parameter, it should be used in this way.
98 /// BPUGRAPH_TYPEDEFS(typename G)
101 ///\warning There are no typedefs for the graph maps because of the lack of
102 ///template typedefs in C++.
103 #define BPUGRAPH_TYPEDEFS(Graph) \
104 UGRAPH_TYPEDEFS(Graph) \
105 typedef Graph::ANodeIt ANodeIt; \
106 typedef Graph::BNodeIt BNodeIt;
108 /// \brief Function to count the items in the graph.
110 /// This function counts the items (nodes, edges etc) in the graph.
111 /// The complexity of the function is O(n) because
112 /// it iterates on all of the items.
114 template <typename Graph, typename Item>
115 inline int countItems(const Graph& g) {
116 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
118 for (ItemIt it(g); it != INVALID; ++it) {
126 namespace _graph_utils_bits {
128 template <typename Graph, typename Enable = void>
129 struct CountNodesSelector {
130 static int count(const Graph &g) {
131 return countItems<Graph, typename Graph::Node>(g);
135 template <typename Graph>
136 struct CountNodesSelector<
138 enable_if<typename Graph::NodeNumTag, void>::type>
140 static int count(const Graph &g) {
146 /// \brief Function to count the nodes in the graph.
148 /// This function counts the nodes in the graph.
149 /// The complexity of the function is O(n) but for some
150 /// graph structures it is specialized to run in O(1).
152 /// \todo refer how to specialize it
154 template <typename Graph>
155 inline int countNodes(const Graph& g) {
156 return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
159 namespace _graph_utils_bits {
161 template <typename Graph, typename Enable = void>
162 struct CountANodesSelector {
163 static int count(const Graph &g) {
164 return countItems<Graph, typename Graph::ANode>(g);
168 template <typename Graph>
169 struct CountANodesSelector<
171 enable_if<typename Graph::NodeNumTag, void>::type>
173 static int count(const Graph &g) {
179 /// \brief Function to count the anodes in the graph.
181 /// This function counts the anodes in the graph.
182 /// The complexity of the function is O(an) but for some
183 /// graph structures it is specialized to run in O(1).
185 /// \todo refer how to specialize it
187 template <typename Graph>
188 inline int countANodes(const Graph& g) {
189 return _graph_utils_bits::CountANodesSelector<Graph>::count(g);
192 namespace _graph_utils_bits {
194 template <typename Graph, typename Enable = void>
195 struct CountBNodesSelector {
196 static int count(const Graph &g) {
197 return countItems<Graph, typename Graph::BNode>(g);
201 template <typename Graph>
202 struct CountBNodesSelector<
204 enable_if<typename Graph::NodeNumTag, void>::type>
206 static int count(const Graph &g) {
212 /// \brief Function to count the bnodes in the graph.
214 /// This function counts the bnodes in the graph.
215 /// The complexity of the function is O(bn) but for some
216 /// graph structures it is specialized to run in O(1).
218 /// \todo refer how to specialize it
220 template <typename Graph>
221 inline int countBNodes(const Graph& g) {
222 return _graph_utils_bits::CountBNodesSelector<Graph>::count(g);
228 namespace _graph_utils_bits {
230 template <typename Graph, typename Enable = void>
231 struct CountEdgesSelector {
232 static int count(const Graph &g) {
233 return countItems<Graph, typename Graph::Edge>(g);
237 template <typename Graph>
238 struct CountEdgesSelector<
240 typename enable_if<typename Graph::EdgeNumTag, void>::type>
242 static int count(const Graph &g) {
248 /// \brief Function to count the edges in the graph.
250 /// This function counts the edges in the graph.
251 /// The complexity of the function is O(e) but for some
252 /// graph structures it is specialized to run in O(1).
254 template <typename Graph>
255 inline int countEdges(const Graph& g) {
256 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
259 // Undirected edge counting:
260 namespace _graph_utils_bits {
262 template <typename Graph, typename Enable = void>
263 struct CountUEdgesSelector {
264 static int count(const Graph &g) {
265 return countItems<Graph, typename Graph::UEdge>(g);
269 template <typename Graph>
270 struct CountUEdgesSelector<
272 typename enable_if<typename Graph::EdgeNumTag, void>::type>
274 static int count(const Graph &g) {
280 /// \brief Function to count the undirected edges in the graph.
282 /// This function counts the undirected edges in the graph.
283 /// The complexity of the function is O(e) but for some
284 /// graph structures it is specialized to run in O(1).
286 template <typename Graph>
287 inline int countUEdges(const Graph& g) {
288 return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
293 template <typename Graph, typename DegIt>
294 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
296 for (DegIt it(_g, _n); it != INVALID; ++it) {
302 /// \brief Function to count the number of the out-edges from node \c n.
304 /// This function counts the number of the out-edges from node \c n
306 template <typename Graph>
307 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
308 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
311 /// \brief Function to count the number of the in-edges to node \c n.
313 /// This function counts the number of the in-edges to node \c n
315 template <typename Graph>
316 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
317 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
320 /// \brief Function to count the number of the inc-edges to node \c n.
322 /// This function counts the number of the inc-edges to node \c n
324 template <typename Graph>
325 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
326 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
329 namespace _graph_utils_bits {
331 template <typename Graph, typename Enable = void>
332 struct FindEdgeSelector {
333 typedef typename Graph::Node Node;
334 typedef typename Graph::Edge Edge;
335 static Edge find(const Graph &g, Node u, Node v, Edge e) {
341 while (e != INVALID && g.target(e) != v) {
348 template <typename Graph>
349 struct FindEdgeSelector<
351 typename enable_if<typename Graph::FindEdgeTag, void>::type>
353 typedef typename Graph::Node Node;
354 typedef typename Graph::Edge Edge;
355 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
356 return g.findEdge(u, v, prev);
361 /// \brief Finds an edge between two nodes of a graph.
363 /// Finds an edge from node \c u to node \c v in graph \c g.
365 /// If \c prev is \ref INVALID (this is the default value), then
366 /// it finds the first edge from \c u to \c v. Otherwise it looks for
367 /// the next edge from \c u to \c v after \c prev.
368 /// \return The found edge or \ref INVALID if there is no such an edge.
370 /// Thus you can iterate through each edge from \c u to \c v as it follows.
372 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
376 template <typename Graph>
377 inline typename Graph::Edge findEdge(const Graph &g,
378 typename Graph::Node u,
379 typename Graph::Node v,
380 typename Graph::Edge prev = INVALID) {
381 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
384 /// \brief Iterator for iterating on edges connected the same nodes.
386 /// Iterator for iterating on edges connected the same nodes. It is
387 /// higher level interface for the findEdge() function. You can
388 /// use it the following way:
390 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
395 /// \author Balazs Dezso
396 template <typename _Graph>
397 class ConEdgeIt : public _Graph::Edge {
400 typedef _Graph Graph;
401 typedef typename Graph::Edge Parent;
403 typedef typename Graph::Edge Edge;
404 typedef typename Graph::Node Node;
406 /// \brief Constructor.
408 /// Construct a new ConEdgeIt iterating on the edges which
409 /// connects the \c u and \c v node.
410 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
411 Parent::operator=(findEdge(graph, u, v));
414 /// \brief Constructor.
416 /// Construct a new ConEdgeIt which continues the iterating from
418 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
420 /// \brief Increment operator.
422 /// It increments the iterator and gives back the next edge.
423 ConEdgeIt& operator++() {
424 Parent::operator=(findEdge(graph, graph.source(*this),
425 graph.target(*this), *this));
432 namespace _graph_utils_bits {
434 template <typename Graph, typename Enable = void>
435 struct FindUEdgeSelector {
436 typedef typename Graph::Node Node;
437 typedef typename Graph::UEdge UEdge;
438 static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
444 b = g.source(e) == u;
447 while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
457 while (e != INVALID && (!b || g.target(e) != v)) {
465 template <typename Graph>
466 struct FindUEdgeSelector<
468 typename enable_if<typename Graph::FindEdgeTag, void>::type>
470 typedef typename Graph::Node Node;
471 typedef typename Graph::UEdge UEdge;
472 static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
473 return g.findUEdge(u, v, prev);
478 /// \brief Finds an uedge between two nodes of a graph.
480 /// Finds an uedge from node \c u to node \c v in graph \c g.
481 /// If the node \c u and node \c v is equal then each loop edge
482 /// will be enumerated.
484 /// If \c prev is \ref INVALID (this is the default value), then
485 /// it finds the first edge from \c u to \c v. Otherwise it looks for
486 /// the next edge from \c u to \c v after \c prev.
487 /// \return The found edge or \ref INVALID if there is no such an edge.
489 /// Thus you can iterate through each edge from \c u to \c v as it follows.
491 /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
492 /// e = findUEdge(g,u,v,e)) {
496 template <typename Graph>
497 inline typename Graph::UEdge findUEdge(const Graph &g,
498 typename Graph::Node u,
499 typename Graph::Node v,
500 typename Graph::UEdge p = INVALID) {
501 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
504 /// \brief Iterator for iterating on uedges connected the same nodes.
506 /// Iterator for iterating on uedges connected the same nodes. It is
507 /// higher level interface for the findUEdge() function. You can
508 /// use it the following way:
510 /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
515 /// \author Balazs Dezso
516 template <typename _Graph>
517 class ConUEdgeIt : public _Graph::UEdge {
520 typedef _Graph Graph;
521 typedef typename Graph::UEdge Parent;
523 typedef typename Graph::UEdge UEdge;
524 typedef typename Graph::Node Node;
526 /// \brief Constructor.
528 /// Construct a new ConUEdgeIt iterating on the edges which
529 /// connects the \c u and \c v node.
530 ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
531 Parent::operator=(findUEdge(graph, u, v));
534 /// \brief Constructor.
536 /// Construct a new ConUEdgeIt which continues the iterating from
538 ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
540 /// \brief Increment operator.
542 /// It increments the iterator and gives back the next edge.
543 ConUEdgeIt& operator++() {
544 Parent::operator=(findUEdge(graph, graph.source(*this),
545 graph.target(*this), *this));
552 /// \brief Copy a map.
554 /// This function copies the \c source map to the \c target map. It uses the
555 /// given iterator to iterate on the data structure and it uses the \c ref
556 /// mapping to convert the source's keys to the target's keys.
557 template <typename Target, typename Source,
558 typename ItemIt, typename Ref>
559 void copyMap(Target& target, const Source& source,
560 ItemIt it, const Ref& ref) {
561 for (; it != INVALID; ++it) {
562 target[ref[it]] = source[it];
566 /// \brief Copy the source map to the target map.
568 /// Copy the \c source map to the \c target map. It uses the given iterator
569 /// to iterate on the data structure.
570 template <typename Target, typename Source, typename ItemIt>
571 void copyMap(Target& target, const Source& source, ItemIt it) {
572 for (; it != INVALID; ++it) {
573 target[it] = source[it];
577 /// \brief Class to copy a graph.
579 /// Class to copy a graph to another graph (duplicate a graph). The
580 /// simplest way of using it is through the \c copyGraph() function.
581 template <typename Target, typename Source>
584 typedef typename Source::Node Node;
585 typedef typename Source::NodeIt NodeIt;
586 typedef typename Source::Edge Edge;
587 typedef typename Source::EdgeIt EdgeIt;
589 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
590 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
592 /// \brief Constructor for the GraphCopy.
594 /// It copies the content of the \c _source graph into the
595 /// \c _target graph. It creates also two references, one beetween
596 /// the two nodeset and one beetween the two edgesets.
597 GraphCopy(Target& _target, const Source& _source)
598 : source(_source), target(_target),
599 nodeRefMap(_source), edgeRefMap(_source) {
600 for (NodeIt it(source); it != INVALID; ++it) {
601 nodeRefMap[it] = target.addNode();
603 for (EdgeIt it(source); it != INVALID; ++it) {
604 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
605 nodeRefMap[source.target(it)]);
609 /// \brief Copies the node references into the given map.
611 /// Copies the node references into the given map.
612 template <typename NodeRef>
613 const GraphCopy& nodeRef(NodeRef& map) const {
614 for (NodeIt it(source); it != INVALID; ++it) {
615 map.set(it, nodeRefMap[it]);
620 /// \brief Reverse and copies the node references into the given map.
622 /// Reverse and copies the node references into the given map.
623 template <typename NodeRef>
624 const GraphCopy& nodeCrossRef(NodeRef& map) const {
625 for (NodeIt it(source); it != INVALID; ++it) {
626 map.set(nodeRefMap[it], it);
631 /// \brief Copies the edge references into the given map.
633 /// Copies the edge references into the given map.
634 template <typename EdgeRef>
635 const GraphCopy& edgeRef(EdgeRef& map) const {
636 for (EdgeIt it(source); it != INVALID; ++it) {
637 map.set(it, edgeRefMap[it]);
642 /// \brief Reverse and copies the edge references into the given map.
644 /// Reverse and copies the edge references into the given map.
645 template <typename EdgeRef>
646 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
647 for (EdgeIt it(source); it != INVALID; ++it) {
648 map.set(edgeRefMap[it], it);
653 /// \brief Make copy of the given map.
655 /// Makes copy of the given map for the newly created graph.
656 /// The new map's key type is the target graph's node type,
657 /// and the copied map's key type is the source graph's node
659 template <typename TargetMap, typename SourceMap>
660 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
661 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
665 /// \brief Make copy of the given map.
667 /// Makes copy of the given map for the newly created graph.
668 /// The new map's key type is the target graph's edge type,
669 /// and the copied map's key type is the source graph's edge
671 template <typename TargetMap, typename SourceMap>
672 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
673 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
677 /// \brief Gives back the stored node references.
679 /// Gives back the stored node references.
680 const NodeRefMap& nodeRef() const {
684 /// \brief Gives back the stored edge references.
686 /// Gives back the stored edge references.
687 const EdgeRefMap& edgeRef() const {
695 const Source& source;
698 NodeRefMap nodeRefMap;
699 EdgeRefMap edgeRefMap;
702 /// \brief Copy a graph to another graph.
704 /// Copy a graph to another graph.
705 /// The usage of the function:
708 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
711 /// After the copy the \c nr map will contain the mapping from the
712 /// source graph's nodes to the target graph's nodes and the \c ecr will
713 /// contain the mapping from the target graph's edges to the source's
715 template <typename Target, typename Source>
716 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
717 return GraphCopy<Target, Source>(target, source);
720 /// \brief Class to copy an undirected graph.
722 /// Class to copy an undirected graph to another graph (duplicate a graph).
723 /// The simplest way of using it is through the \c copyUGraph() function.
724 template <typename Target, typename Source>
727 typedef typename Source::Node Node;
728 typedef typename Source::NodeIt NodeIt;
729 typedef typename Source::Edge Edge;
730 typedef typename Source::EdgeIt EdgeIt;
731 typedef typename Source::UEdge UEdge;
732 typedef typename Source::UEdgeIt UEdgeIt;
734 typedef typename Source::
735 template NodeMap<typename Target::Node> NodeRefMap;
737 typedef typename Source::
738 template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
743 EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
744 typedef typename Source::Edge Key;
745 typedef typename Target::Edge Value;
747 Value operator[](const Key& key) {
748 return gc.target.direct(gc.uEdgeRef[key],
749 gc.target.direction(key));
757 /// \brief Constructor for the UGraphCopy.
759 /// It copies the content of the \c _source graph into the
760 /// \c _target graph. It creates also two references, one beetween
761 /// the two nodeset and one beetween the two edgesets.
762 UGraphCopy(Target& _target, const Source& _source)
763 : source(_source), target(_target),
764 nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
765 for (NodeIt it(source); it != INVALID; ++it) {
766 nodeRefMap[it] = target.addNode();
768 for (UEdgeIt it(source); it != INVALID; ++it) {
769 uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
770 nodeRefMap[source.target(it)]);
774 /// \brief Copies the node references into the given map.
776 /// Copies the node references into the given map.
777 template <typename NodeRef>
778 const UGraphCopy& nodeRef(NodeRef& map) const {
779 for (NodeIt it(source); it != INVALID; ++it) {
780 map.set(it, nodeRefMap[it]);
785 /// \brief Reverse and copies the node references into the given map.
787 /// Reverse and copies the node references into the given map.
788 template <typename NodeRef>
789 const UGraphCopy& nodeCrossRef(NodeRef& map) const {
790 for (NodeIt it(source); it != INVALID; ++it) {
791 map.set(nodeRefMap[it], it);
796 /// \brief Copies the edge references into the given map.
798 /// Copies the edge references into the given map.
799 template <typename EdgeRef>
800 const UGraphCopy& edgeRef(EdgeRef& map) const {
801 for (EdgeIt it(source); it != INVALID; ++it) {
802 map.set(edgeRefMap[it], it);
807 /// \brief Reverse and copies the undirected edge references into the
810 /// Reverse and copies the undirected edge references into the given map.
811 template <typename EdgeRef>
812 const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
813 for (EdgeIt it(source); it != INVALID; ++it) {
814 map.set(it, edgeRefMap[it]);
819 /// \brief Copies the undirected edge references into the given map.
821 /// Copies the undirected edge references into the given map.
822 template <typename EdgeRef>
823 const UGraphCopy& uEdgeRef(EdgeRef& map) const {
824 for (UEdgeIt it(source); it != INVALID; ++it) {
825 map.set(it, uEdgeRefMap[it]);
830 /// \brief Reverse and copies the undirected edge references into the
833 /// Reverse and copies the undirected edge references into the given map.
834 template <typename EdgeRef>
835 const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
836 for (UEdgeIt it(source); it != INVALID; ++it) {
837 map.set(uEdgeRefMap[it], it);
842 /// \brief Make copy of the given map.
844 /// Makes copy of the given map for the newly created graph.
845 /// The new map's key type is the target graph's node type,
846 /// and the copied map's key type is the source graph's node
848 template <typename TargetMap, typename SourceMap>
849 const UGraphCopy& nodeMap(TargetMap& tMap,
850 const SourceMap& sMap) const {
851 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
855 /// \brief Make copy of the given map.
857 /// Makes copy of the given map for the newly created graph.
858 /// The new map's key type is the target graph's edge type,
859 /// and the copied map's key type is the source graph's edge
861 template <typename TargetMap, typename SourceMap>
862 const UGraphCopy& edgeMap(TargetMap& tMap,
863 const SourceMap& sMap) const {
864 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
868 /// \brief Make copy of the given map.
870 /// Makes copy of the given map for the newly created graph.
871 /// The new map's key type is the target graph's edge type,
872 /// and the copied map's key type is the source graph's edge
874 template <typename TargetMap, typename SourceMap>
875 const UGraphCopy& uEdgeMap(TargetMap& tMap,
876 const SourceMap& sMap) const {
877 copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
881 /// \brief Gives back the stored node references.
883 /// Gives back the stored node references.
884 const NodeRefMap& nodeRef() const {
888 /// \brief Gives back the stored edge references.
890 /// Gives back the stored edge references.
891 const EdgeRefMap& edgeRef() const {
895 /// \brief Gives back the stored uedge references.
897 /// Gives back the stored uedge references.
898 const UEdgeRefMap& uEdgeRef() const {
906 const Source& source;
909 NodeRefMap nodeRefMap;
910 EdgeRefMap edgeRefMap;
911 UEdgeRefMap uEdgeRefMap;
914 /// \brief Copy a graph to another graph.
916 /// Copy a graph to another graph.
917 /// The usage of the function:
920 /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
923 /// After the copy the \c nr map will contain the mapping from the
924 /// source graph's nodes to the target graph's nodes and the \c ecr will
925 /// contain the mapping from the target graph's edges to the source's
927 template <typename Target, typename Source>
928 UGraphCopy<Target, Source>
929 copyUGraph(Target& target, const Source& source) {
930 return UGraphCopy<Target, Source>(target, source);
936 /// \addtogroup graph_maps
939 /// Provides an immutable and unique id for each item in the graph.
941 /// The IdMap class provides a unique and immutable id for each item of the
942 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
943 /// different items (nodes) get different ids <li>\b immutable: the id of an
944 /// item (node) does not change (even if you delete other nodes). </ul>
945 /// Through this map you get access (i.e. can read) the inner id values of
946 /// the items stored in the graph. This map can be inverted with its member
947 /// class \c InverseMap.
949 template <typename _Graph, typename _Item>
952 typedef _Graph Graph;
957 /// \brief Constructor.
959 /// Constructor for creating id map.
960 IdMap(const Graph& _graph) : graph(&_graph) {}
962 /// \brief Gives back the \e id of the item.
964 /// Gives back the immutable and unique \e id of the map.
965 int operator[](const Item& item) const { return graph->id(item);}
973 /// \brief The class represents the inverse of its owner (IdMap).
975 /// The class represents the inverse of its owner (IdMap).
980 /// \brief Constructor.
982 /// Constructor for creating an id-to-item map.
983 InverseMap(const Graph& _graph) : graph(&_graph) {}
985 /// \brief Constructor.
987 /// Constructor for creating an id-to-item map.
988 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
990 /// \brief Gives back the given item from its id.
992 /// Gives back the given item from its id.
994 Item operator[](int id) const { return graph->fromId(id, Item());}
999 /// \brief Gives back the inverse of the map.
1001 /// Gives back the inverse of the IdMap.
1002 InverseMap inverse() const { return InverseMap(*graph);}
1007 /// \brief General invertable graph-map type.
1009 /// This type provides simple invertable graph-maps.
1010 /// The InvertableMap wraps an arbitrary ReadWriteMap
1011 /// and if a key is set to a new value then store it
1012 /// in the inverse map.
1014 /// The values of the map can be accessed
1015 /// with stl compatible forward iterator.
1017 /// \param _Graph The graph type.
1018 /// \param _Item The item type of the graph.
1019 /// \param _Value The value type of the map.
1021 /// \see IterableValueMap
1023 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1025 typename _Graph, typename _Item, typename _Value,
1026 typename _Map = DefaultMap<_Graph, _Item, _Value>
1029 template <typename _Graph, typename _Item, typename _Value>
1031 class InvertableMap : protected _Map {
1034 /// The key type of InvertableMap (Node, Edge, UEdge).
1035 typedef typename _Map::Key Key;
1036 /// The value type of the InvertableMap.
1037 typedef typename _Map::Value Value;
1042 typedef _Graph Graph;
1044 typedef std::map<Value, Key> Container;
1051 /// \brief Constructor.
1053 /// Construct a new InvertableMap for the graph.
1055 InvertableMap(const Graph& graph) : Map(graph) {}
1057 /// \brief Forward iterator for values.
1059 /// This iterator is an stl compatible forward
1060 /// iterator on the values of the map. The values can
1061 /// be accessed in the [beginValue, endValue) range.
1064 : public std::iterator<std::forward_iterator_tag, Value> {
1065 friend class InvertableMap;
1067 ValueIterator(typename Container::const_iterator _it)
1073 ValueIterator& operator++() { ++it; return *this; }
1074 ValueIterator operator++(int) {
1075 ValueIterator tmp(*this);
1080 const Value& operator*() const { return it->first; }
1081 const Value* operator->() const { return &(it->first); }
1083 bool operator==(ValueIterator jt) const { return it == jt.it; }
1084 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1087 typename Container::const_iterator it;
1090 /// \brief Returns an iterator to the first value.
1092 /// Returns an stl compatible iterator to the
1093 /// first value of the map. The values of the
1094 /// map can be accessed in the [beginValue, endValue)
1096 ValueIterator beginValue() const {
1097 return ValueIterator(invMap.begin());
1100 /// \brief Returns an iterator after the last value.
1102 /// Returns an stl compatible iterator after the
1103 /// last value of the map. The values of the
1104 /// map can be accessed in the [beginValue, endValue)
1106 ValueIterator endValue() const {
1107 return ValueIterator(invMap.end());
1110 /// \brief The setter function of the map.
1112 /// Sets the mapped value.
1113 void set(const Key& key, const Value& val) {
1114 Value oldval = Map::operator[](key);
1115 typename Container::iterator it = invMap.find(oldval);
1116 if (it != invMap.end() && it->second == key) {
1119 invMap.insert(make_pair(val, key));
1123 /// \brief The getter function of the map.
1125 /// It gives back the value associated with the key.
1126 typename MapTraits<Map>::ConstReturnValue
1127 operator[](const Key& key) const {
1128 return Map::operator[](key);
1133 /// \brief Erase the key from the map.
1135 /// Erase the key to the map. It is called by the
1136 /// \c AlterationNotifier.
1137 virtual void erase(const Key& key) {
1138 Value val = Map::operator[](key);
1139 typename Container::iterator it = invMap.find(val);
1140 if (it != invMap.end() && it->second == key) {
1146 /// \brief Erase more keys from the map.
1148 /// Erase more keys from the map. It is called by the
1149 /// \c AlterationNotifier.
1150 virtual void erase(const std::vector<Key>& keys) {
1151 for (int i = 0; i < (int)keys.size(); ++i) {
1152 Value val = Map::operator[](keys[i]);
1153 typename Container::iterator it = invMap.find(val);
1154 if (it != invMap.end() && it->second == keys[i]) {
1161 /// \brief Clear the keys from the map and inverse map.
1163 /// Clear the keys from the map and inverse map. It is called by the
1164 /// \c AlterationNotifier.
1165 virtual void clear() {
1172 /// \brief The inverse map type.
1174 /// The inverse of this map. The subscript operator of the map
1175 /// gives back always the item what was last assigned to the value.
1178 /// \brief Constructor of the InverseMap.
1180 /// Constructor of the InverseMap.
1181 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
1183 /// The value type of the InverseMap.
1184 typedef typename InvertableMap::Key Value;
1185 /// The key type of the InverseMap.
1186 typedef typename InvertableMap::Value Key;
1188 /// \brief Subscript operator.
1190 /// Subscript operator. It gives back always the item
1191 /// what was last assigned to the value.
1192 Value operator[](const Key& key) const {
1193 typename Container::const_iterator it = inverted.invMap.find(key);
1198 const InvertableMap& inverted;
1201 /// \brief It gives back the just readable inverse map.
1203 /// It gives back the just readable inverse map.
1204 InverseMap inverse() const {
1205 return InverseMap(*this);
1212 /// \brief Provides a mutable, continuous and unique descriptor for each
1213 /// item in the graph.
1215 /// The DescriptorMap class provides a unique and continuous (but mutable)
1216 /// descriptor (id) for each item of the same type (e.g. node) in the
1217 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1218 /// different ids <li>\b continuous: the range of the ids is the set of
1219 /// integers between 0 and \c n-1, where \c n is the number of the items of
1220 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1221 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1222 /// with its member class \c InverseMap.
1224 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1225 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1228 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1230 typename _Graph, typename _Item,
1231 typename _Map = DefaultMap<_Graph, _Item, int>
1234 template <typename _Graph, typename _Item>
1236 class DescriptorMap : protected _Map {
1242 /// The graph class of DescriptorMap.
1243 typedef _Graph Graph;
1245 /// The key type of DescriptorMap (Node, Edge, UEdge).
1246 typedef typename _Map::Key Key;
1247 /// The value type of DescriptorMap.
1248 typedef typename _Map::Value Value;
1250 /// \brief Constructor.
1252 /// Constructor for descriptor map.
1253 DescriptorMap(const Graph& _graph) : Map(_graph) {
1259 /// \brief Add a new key to the map.
1261 /// Add a new key to the map. It is called by the
1262 /// \c AlterationNotifier.
1263 virtual void add(const Item& item) {
1265 Map::set(item, invMap.size());
1266 invMap.push_back(item);
1269 /// \brief Add more new keys to the map.
1271 /// Add more new keys to the map. It is called by the
1272 /// \c AlterationNotifier.
1273 virtual void add(const std::vector<Item>& items) {
1275 for (int i = 0; i < (int)items.size(); ++i) {
1276 Map::set(items[i], invMap.size());
1277 invMap.push_back(items[i]);
1281 /// \brief Erase the key from the map.
1283 /// Erase the key from the map. It is called by the
1284 /// \c AlterationNotifier.
1285 virtual void erase(const Item& item) {
1286 Map::set(invMap.back(), Map::operator[](item));
1287 invMap[Map::operator[](item)] = invMap.back();
1292 /// \brief Erase more keys from the map.
1294 /// Erase more keys from the map. It is called by the
1295 /// \c AlterationNotifier.
1296 virtual void erase(const std::vector<Item>& items) {
1297 for (int i = 0; i < (int)items.size(); ++i) {
1298 Map::set(invMap.back(), Map::operator[](items[i]));
1299 invMap[Map::operator[](items[i])] = invMap.back();
1305 /// \brief Build the unique map.
1307 /// Build the unique map. It is called by the
1308 /// \c AlterationNotifier.
1309 virtual void build() {
1312 const typename Map::Notifier* notifier = Map::getNotifier();
1313 for (notifier->first(it); it != INVALID; notifier->next(it)) {
1314 Map::set(it, invMap.size());
1315 invMap.push_back(it);
1319 /// \brief Clear the keys from the map.
1321 /// Clear the keys from the map. It is called by the
1322 /// \c AlterationNotifier.
1323 virtual void clear() {
1330 /// \brief Returns the maximal value plus one.
1332 /// Returns the maximal value plus one in the map.
1333 unsigned int size() const {
1334 return invMap.size();
1337 /// \brief Swaps the position of the two items in the map.
1339 /// Swaps the position of the two items in the map.
1340 void swap(const Item& p, const Item& q) {
1341 int pi = Map::operator[](p);
1342 int qi = Map::operator[](q);
1349 /// \brief Gives back the \e descriptor of the item.
1351 /// Gives back the mutable and unique \e descriptor of the map.
1352 int operator[](const Item& item) const {
1353 return Map::operator[](item);
1358 typedef std::vector<Item> Container;
1362 /// \brief The inverse map type of DescriptorMap.
1364 /// The inverse map type of DescriptorMap.
1367 /// \brief Constructor of the InverseMap.
1369 /// Constructor of the InverseMap.
1370 InverseMap(const DescriptorMap& _inverted)
1371 : inverted(_inverted) {}
1374 /// The value type of the InverseMap.
1375 typedef typename DescriptorMap::Key Value;
1376 /// The key type of the InverseMap.
1377 typedef typename DescriptorMap::Value Key;
1379 /// \brief Subscript operator.
1381 /// Subscript operator. It gives back the item
1382 /// that the descriptor belongs to currently.
1383 Value operator[](const Key& key) const {
1384 return inverted.invMap[key];
1387 /// \brief Size of the map.
1389 /// Returns the size of the map.
1390 unsigned int size() const {
1391 return inverted.invMap.size();
1395 const DescriptorMap& inverted;
1398 /// \brief Gives back the inverse of the map.
1400 /// Gives back the inverse of the map.
1401 const InverseMap inverse() const {
1402 return InverseMap(*this);
1406 /// \brief Returns the source of the given edge.
1408 /// The SourceMap gives back the source Node of the given edge.
1409 /// \author Balazs Dezso
1410 template <typename Graph>
1414 typedef typename Graph::Node Value;
1415 typedef typename Graph::Edge Key;
1417 /// \brief Constructor
1420 /// \param _graph The graph that the map belongs to.
1421 SourceMap(const Graph& _graph) : graph(_graph) {}
1423 /// \brief The subscript operator.
1425 /// The subscript operator.
1426 /// \param edge The edge
1427 /// \return The source of the edge
1428 Value operator[](const Key& edge) const {
1429 return graph.source(edge);
1436 /// \brief Returns a \ref SourceMap class
1438 /// This function just returns an \ref SourceMap class.
1439 /// \relates SourceMap
1440 template <typename Graph>
1441 inline SourceMap<Graph> sourceMap(const Graph& graph) {
1442 return SourceMap<Graph>(graph);
1445 /// \brief Returns the target of the given edge.
1447 /// The TargetMap gives back the target Node of the given edge.
1448 /// \author Balazs Dezso
1449 template <typename Graph>
1453 typedef typename Graph::Node Value;
1454 typedef typename Graph::Edge Key;
1456 /// \brief Constructor
1459 /// \param _graph The graph that the map belongs to.
1460 TargetMap(const Graph& _graph) : graph(_graph) {}
1462 /// \brief The subscript operator.
1464 /// The subscript operator.
1465 /// \param e The edge
1466 /// \return The target of the edge
1467 Value operator[](const Key& e) const {
1468 return graph.target(e);
1475 /// \brief Returns a \ref TargetMap class
1477 /// This function just returns a \ref TargetMap class.
1478 /// \relates TargetMap
1479 template <typename Graph>
1480 inline TargetMap<Graph> targetMap(const Graph& graph) {
1481 return TargetMap<Graph>(graph);
1484 /// \brief Returns the "forward" directed edge view of an undirected edge.
1486 /// Returns the "forward" directed edge view of an undirected edge.
1487 /// \author Balazs Dezso
1488 template <typename Graph>
1492 typedef typename Graph::Edge Value;
1493 typedef typename Graph::UEdge Key;
1495 /// \brief Constructor
1498 /// \param _graph The graph that the map belongs to.
1499 ForwardMap(const Graph& _graph) : graph(_graph) {}
1501 /// \brief The subscript operator.
1503 /// The subscript operator.
1504 /// \param key An undirected edge
1505 /// \return The "forward" directed edge view of undirected edge
1506 Value operator[](const Key& key) const {
1507 return graph.direct(key, true);
1514 /// \brief Returns a \ref ForwardMap class
1516 /// This function just returns an \ref ForwardMap class.
1517 /// \relates ForwardMap
1518 template <typename Graph>
1519 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1520 return ForwardMap<Graph>(graph);
1523 /// \brief Returns the "backward" directed edge view of an undirected edge.
1525 /// Returns the "backward" directed edge view of an undirected edge.
1526 /// \author Balazs Dezso
1527 template <typename Graph>
1531 typedef typename Graph::Edge Value;
1532 typedef typename Graph::UEdge Key;
1534 /// \brief Constructor
1537 /// \param _graph The graph that the map belongs to.
1538 BackwardMap(const Graph& _graph) : graph(_graph) {}
1540 /// \brief The subscript operator.
1542 /// The subscript operator.
1543 /// \param key An undirected edge
1544 /// \return The "backward" directed edge view of undirected edge
1545 Value operator[](const Key& key) const {
1546 return graph.direct(key, false);
1553 /// \brief Returns a \ref BackwardMap class
1555 /// This function just returns a \ref BackwardMap class.
1556 /// \relates BackwardMap
1557 template <typename Graph>
1558 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1559 return BackwardMap<Graph>(graph);
1562 /// \brief Potential difference map
1564 /// If there is an potential map on the nodes then we
1565 /// can get an edge map as we get the substraction of the
1566 /// values of the target and source.
1567 template <typename Graph, typename NodeMap>
1568 class PotentialDifferenceMap {
1570 typedef typename Graph::Edge Key;
1571 typedef typename NodeMap::Value Value;
1573 /// \brief Constructor
1575 /// Contructor of the map
1576 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1577 : graph(_graph), potential(_potential) {}
1579 /// \brief Const subscription operator
1581 /// Const subscription operator
1582 Value operator[](const Key& edge) const {
1583 return potential[graph.target(edge)] - potential[graph.source(edge)];
1588 const NodeMap& potential;
1591 /// \brief Just returns a PotentialDifferenceMap
1593 /// Just returns a PotentialDifferenceMap
1594 /// \relates PotentialDifferenceMap
1595 template <typename Graph, typename NodeMap>
1596 PotentialDifferenceMap<Graph, NodeMap>
1597 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1598 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1601 /// \brief Map of the node in-degrees.
1603 /// This map returns the in-degree of a node. Once it is constructed,
1604 /// the degrees are stored in a standard NodeMap, so each query is done
1605 /// in constant time. On the other hand, the values are updated automatically
1606 /// whenever the graph changes.
1608 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1609 /// alternative ways to modify the graph. The correct behavior of InDegMap
1610 /// is not guarantied if these additional features are used. For example
1611 /// the functions \ref ListGraph::changeSource() "changeSource()",
1612 /// \ref ListGraph::changeTarget() "changeTarget()" and
1613 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1614 /// of \ref ListGraph will \e not update the degree values correctly.
1618 template <typename _Graph>
1620 : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1621 ::ItemNotifier::ObserverBase {
1625 typedef _Graph Graph;
1627 typedef typename Graph::Node Key;
1629 typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1630 ::ItemNotifier::ObserverBase Parent;
1634 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1637 typedef DefaultMap<_Graph, Key, int> Parent;
1638 typedef typename Parent::Graph Graph;
1640 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1642 virtual void add(const Key& key) {
1644 Parent::set(key, 0);
1647 virtual void add(const std::vector<Key>& keys) {
1649 for (int i = 0; i < (int)keys.size(); ++i) {
1650 Parent::set(keys[i], 0);
1657 /// \brief Constructor.
1659 /// Constructor for creating in-degree map.
1660 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1661 Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1663 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1664 deg[it] = countInEdges(graph, it);
1668 /// Gives back the in-degree of a Node.
1669 int operator[](const Key& key) const {
1675 typedef typename Graph::Edge Edge;
1677 virtual void add(const Edge& edge) {
1678 ++deg[graph.target(edge)];
1681 virtual void add(const std::vector<Edge>& edges) {
1682 for (int i = 0; i < (int)edges.size(); ++i) {
1683 ++deg[graph.target(edges[i])];
1687 virtual void erase(const Edge& edge) {
1688 --deg[graph.target(edge)];
1691 virtual void erase(const std::vector<Edge>& edges) {
1692 for (int i = 0; i < (int)edges.size(); ++i) {
1693 --deg[graph.target(edges[i])];
1697 virtual void build() {
1698 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1699 deg[it] = countInEdges(graph, it);
1703 virtual void clear() {
1704 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1710 const _Graph& graph;
1714 /// \brief Map of the node out-degrees.
1716 /// This map returns the out-degree of a node. Once it is constructed,
1717 /// the degrees are stored in a standard NodeMap, so each query is done
1718 /// in constant time. On the other hand, the values are updated automatically
1719 /// whenever the graph changes.
1721 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1722 /// alternative ways to modify the graph. The correct behavior of OutDegMap
1723 /// is not guarantied if these additional features are used. For example
1724 /// the functions \ref ListGraph::changeSource() "changeSource()",
1725 /// \ref ListGraph::changeTarget() "changeTarget()" and
1726 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1727 /// of \ref ListGraph will \e not update the degree values correctly.
1731 template <typename _Graph>
1733 : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1734 ::ItemNotifier::ObserverBase {
1738 typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1739 ::ItemNotifier::ObserverBase Parent;
1741 typedef _Graph Graph;
1743 typedef typename Graph::Node Key;
1747 class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1750 typedef DefaultMap<_Graph, Key, int> Parent;
1751 typedef typename Parent::Graph Graph;
1753 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1755 virtual void add(const Key& key) {
1757 Parent::set(key, 0);
1759 virtual void add(const std::vector<Key>& keys) {
1761 for (int i = 0; i < (int)keys.size(); ++i) {
1762 Parent::set(keys[i], 0);
1769 /// \brief Constructor.
1771 /// Constructor for creating out-degree map.
1772 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1773 Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1775 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1776 deg[it] = countOutEdges(graph, it);
1780 /// Gives back the out-degree of a Node.
1781 int operator[](const Key& key) const {
1787 typedef typename Graph::Edge Edge;
1789 virtual void add(const Edge& edge) {
1790 ++deg[graph.source(edge)];
1793 virtual void add(const std::vector<Edge>& edges) {
1794 for (int i = 0; i < (int)edges.size(); ++i) {
1795 ++deg[graph.source(edges[i])];
1799 virtual void erase(const Edge& edge) {
1800 --deg[graph.source(edge)];
1803 virtual void erase(const std::vector<Edge>& edges) {
1804 for (int i = 0; i < (int)edges.size(); ++i) {
1805 --deg[graph.source(edges[i])];
1809 virtual void build() {
1810 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1811 deg[it] = countOutEdges(graph, it);
1815 virtual void clear() {
1816 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1822 const _Graph& graph;
1829 } //END OF NAMESPACE LEMON