Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.
Some bugfix in the adaptors
New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.
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 && g.target(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 readeable inverse map.
1203 /// It gives back the just readeable 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