3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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
28 #include <lemon/bits/invalid.h>
29 #include <lemon/bits/utility.h>
30 #include <lemon/maps.h>
31 #include <lemon/bits/traits.h>
33 #include <lemon/bits/alteration_notifier.h>
34 #include <lemon/bits/default_map.h>
38 ///\brief Graph utilities.
42 /// \addtogroup gutils
45 ///Creates convenience typedefs for the digraph types and iterators
47 ///This \c \#define creates convenience typedefs for the following types
48 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
49 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
50 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
51 #define DIGRAPH_TYPEDEFS(Digraph) \
52 typedef Digraph::Node Node; \
53 typedef Digraph::NodeIt NodeIt; \
54 typedef Digraph::Arc Arc; \
55 typedef Digraph::ArcIt ArcIt; \
56 typedef Digraph::InArcIt InArcIt; \
57 typedef Digraph::OutArcIt OutArcIt
59 ///Creates convenience typedefs for the graph types and iterators
61 ///This \c \#define creates the same convenience typedefs as defined
62 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
63 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
65 #define GRAPH_TYPEDEFS(Graph) \
66 DIGRAPH_TYPEDEFS(Graph); \
67 typedef Graph::Edge Edge; \
68 typedef Graph::EdgeIt EdgeIt; \
69 typedef Graph::IncEdgeIt IncEdgeIt
71 /// \brief Function to count the items in the graph.
73 /// This function counts the items (nodes, arcs etc) in the graph.
74 /// The complexity of the function is O(n) because
75 /// it iterates on all of the items.
76 template <typename Graph, typename Item>
77 inline int countItems(const Graph& g) {
78 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
80 for (ItemIt it(g); it != INVALID; ++it) {
88 namespace _graph_utils_bits {
90 template <typename Graph, typename Enable = void>
91 struct CountNodesSelector {
92 static int count(const Graph &g) {
93 return countItems<Graph, typename Graph::Node>(g);
97 template <typename Graph>
98 struct CountNodesSelector<
100 enable_if<typename Graph::NodeNumTag, void>::type>
102 static int count(const Graph &g) {
108 /// \brief Function to count the nodes in the graph.
110 /// This function counts the nodes in the graph.
111 /// The complexity of the function is O(n) but for some
112 /// graph structures it is specialized to run in O(1).
114 /// If the graph contains a \e nodeNum() member function and a
115 /// \e NodeNumTag tag then this function calls directly the member
116 /// function to query the cardinality of the node set.
117 template <typename Graph>
118 inline int countNodes(const Graph& g) {
119 return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
124 namespace _graph_utils_bits {
126 template <typename Graph, typename Enable = void>
127 struct CountArcsSelector {
128 static int count(const Graph &g) {
129 return countItems<Graph, typename Graph::Arc>(g);
133 template <typename Graph>
134 struct CountArcsSelector<
136 typename enable_if<typename Graph::ArcNumTag, void>::type>
138 static int count(const Graph &g) {
144 /// \brief Function to count the arcs in the graph.
146 /// This function counts the arcs in the graph.
147 /// The complexity of the function is O(e) but for some
148 /// graph structures it is specialized to run in O(1).
150 /// If the graph contains a \e arcNum() member function and a
151 /// \e EdgeNumTag tag then this function calls directly the member
152 /// function to query the cardinality of the arc set.
153 template <typename Graph>
154 inline int countArcs(const Graph& g) {
155 return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
159 namespace _graph_utils_bits {
161 template <typename Graph, typename Enable = void>
162 struct CountEdgesSelector {
163 static int count(const Graph &g) {
164 return countItems<Graph, typename Graph::Edge>(g);
168 template <typename Graph>
169 struct CountEdgesSelector<
171 typename enable_if<typename Graph::EdgeNumTag, void>::type>
173 static int count(const Graph &g) {
179 /// \brief Function to count the edges in the graph.
181 /// This function counts the edges in the graph.
182 /// The complexity of the function is O(m) but for some
183 /// graph structures it is specialized to run in O(1).
185 /// If the graph contains a \e edgeNum() member function and a
186 /// \e EdgeNumTag tag then this function calls directly the member
187 /// function to query the cardinality of the edge set.
188 template <typename Graph>
189 inline int countEdges(const Graph& g) {
190 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
195 template <typename Graph, typename DegIt>
196 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
198 for (DegIt it(_g, _n); it != INVALID; ++it) {
204 /// \brief Function to count the number of the out-arcs from node \c n.
206 /// This function counts the number of the out-arcs from node \c n
208 template <typename Graph>
209 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
210 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
213 /// \brief Function to count the number of the in-arcs to node \c n.
215 /// This function counts the number of the in-arcs to node \c n
217 template <typename Graph>
218 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
219 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
222 /// \brief Function to count the number of the inc-edges to node \c n.
224 /// This function counts the number of the inc-edges to node \c n
226 template <typename Graph>
227 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
228 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
231 namespace _graph_utils_bits {
233 template <typename Graph, typename Enable = void>
234 struct FindArcSelector {
235 typedef typename Graph::Node Node;
236 typedef typename Graph::Arc Arc;
237 static Arc find(const Graph &g, Node u, Node v, Arc e) {
243 while (e != INVALID && g.target(e) != v) {
250 template <typename Graph>
251 struct FindArcSelector<
253 typename enable_if<typename Graph::FindEdgeTag, void>::type>
255 typedef typename Graph::Node Node;
256 typedef typename Graph::Arc Arc;
257 static Arc find(const Graph &g, Node u, Node v, Arc prev) {
258 return g.findArc(u, v, prev);
263 /// \brief Finds an arc between two nodes of a graph.
265 /// Finds an arc from node \c u to node \c v in graph \c g.
267 /// If \c prev is \ref INVALID (this is the default value), then
268 /// it finds the first arc from \c u to \c v. Otherwise it looks for
269 /// the next arc from \c u to \c v after \c prev.
270 /// \return The found arc or \ref INVALID if there is no such an arc.
272 /// Thus you can iterate through each arc from \c u to \c v as it follows.
274 /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
283 template <typename Graph>
284 inline typename Graph::Arc
285 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
286 typename Graph::Arc prev = INVALID) {
287 return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
290 /// \brief Iterator for iterating on arcs connected the same nodes.
292 /// Iterator for iterating on arcs connected the same nodes. It is
293 /// higher level interface for the findArc() function. You can
294 /// use it the following way:
296 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
306 /// \author Balazs Dezso
307 template <typename _Graph>
308 class ConArcIt : public _Graph::Arc {
311 typedef _Graph Graph;
312 typedef typename Graph::Arc Parent;
314 typedef typename Graph::Arc Arc;
315 typedef typename Graph::Node Node;
317 /// \brief Constructor.
319 /// Construct a new ConArcIt iterating on the arcs which
320 /// connects the \c u and \c v node.
321 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
322 Parent::operator=(findArc(_graph, u, v));
325 /// \brief Constructor.
327 /// Construct a new ConArcIt which continues the iterating from
329 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
331 /// \brief Increment operator.
333 /// It increments the iterator and gives back the next arc.
334 ConArcIt& operator++() {
335 Parent::operator=(findArc(_graph, _graph.source(*this),
336 _graph.target(*this), *this));
343 namespace _graph_utils_bits {
345 template <typename Graph, typename Enable = void>
346 struct FindEdgeSelector {
347 typedef typename Graph::Node Node;
348 typedef typename Graph::Edge Edge;
349 static Edge find(const Graph &g, Node u, Node v, Edge e) {
355 b = g.source(e) == u;
358 while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
368 while (e != INVALID && (!b || g.target(e) != v)) {
376 template <typename Graph>
377 struct FindEdgeSelector<
379 typename enable_if<typename Graph::FindEdgeTag, void>::type>
381 typedef typename Graph::Node Node;
382 typedef typename Graph::Edge Edge;
383 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
384 return g.findEdge(u, v, prev);
389 /// \brief Finds an edge between two nodes of a graph.
391 /// Finds an edge from node \c u to node \c v in graph \c g.
392 /// If the node \c u and node \c v is equal then each loop edge
393 /// will be enumerated once.
395 /// If \c prev is \ref INVALID (this is the default value), then
396 /// it finds the first arc from \c u to \c v. Otherwise it looks for
397 /// the next arc from \c u to \c v after \c prev.
398 /// \return The found arc or \ref INVALID if there is no such an arc.
400 /// Thus you can iterate through each arc from \c u to \c v as it follows.
402 /// for(Edge e = findEdge(g,u,v); e != INVALID;
403 /// e = findEdge(g,u,v,e)) {
410 template <typename Graph>
411 inline typename Graph::Edge
412 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
413 typename Graph::Edge p = INVALID) {
414 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
417 /// \brief Iterator for iterating on edges connected the same nodes.
419 /// Iterator for iterating on edges connected the same nodes. It is
420 /// higher level interface for the findEdge() function. You can
421 /// use it the following way:
423 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
430 /// \author Balazs Dezso
431 template <typename _Graph>
432 class ConEdgeIt : public _Graph::Edge {
435 typedef _Graph Graph;
436 typedef typename Graph::Edge Parent;
438 typedef typename Graph::Edge Edge;
439 typedef typename Graph::Node Node;
441 /// \brief Constructor.
443 /// Construct a new ConEdgeIt iterating on the edges which
444 /// connects the \c u and \c v node.
445 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
446 Parent::operator=(findEdge(_graph, u, v));
449 /// \brief Constructor.
451 /// Construct a new ConEdgeIt which continues the iterating from
453 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
455 /// \brief Increment operator.
457 /// It increments the iterator and gives back the next edge.
458 ConEdgeIt& operator++() {
459 Parent::operator=(findEdge(_graph, _graph.source(*this),
460 _graph.target(*this), *this));
467 namespace _graph_utils_bits {
469 template <typename Digraph, typename Item, typename RefMap>
472 virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
474 virtual ~MapCopyBase() {}
477 template <typename Digraph, typename Item, typename RefMap,
478 typename ToMap, typename FromMap>
479 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
482 MapCopy(ToMap& tmap, const FromMap& map)
483 : _tmap(tmap), _map(map) {}
485 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
486 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
487 for (ItemIt it(digraph); it != INVALID; ++it) {
488 _tmap.set(refMap[it], _map[it]);
497 template <typename Digraph, typename Item, typename RefMap, typename It>
498 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
501 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
503 virtual void copy(const Digraph&, const RefMap& refMap) {
512 template <typename Digraph, typename Item, typename RefMap, typename Ref>
513 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
516 RefCopy(Ref& map) : _map(map) {}
518 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
519 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
520 for (ItemIt it(digraph); it != INVALID; ++it) {
521 _map.set(it, refMap[it]);
529 template <typename Digraph, typename Item, typename RefMap,
531 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
534 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
536 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
537 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
538 for (ItemIt it(digraph); it != INVALID; ++it) {
539 _cmap.set(refMap[it], it);
547 template <typename Digraph, typename Enable = void>
548 struct DigraphCopySelector {
549 template <typename From, typename NodeRefMap, typename ArcRefMap>
550 static void copy(Digraph &to, const From& from,
551 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
552 for (typename From::NodeIt it(from); it != INVALID; ++it) {
553 nodeRefMap[it] = to.addNode();
555 for (typename From::ArcIt it(from); it != INVALID; ++it) {
556 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
557 nodeRefMap[from.target(it)]);
562 template <typename Digraph>
563 struct DigraphCopySelector<
565 typename enable_if<typename Digraph::BuildTag, void>::type>
567 template <typename From, typename NodeRefMap, typename ArcRefMap>
568 static void copy(Digraph &to, const From& from,
569 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
570 to.build(from, nodeRefMap, arcRefMap);
574 template <typename Graph, typename Enable = void>
575 struct GraphCopySelector {
576 template <typename From, typename NodeRefMap, typename EdgeRefMap>
577 static void copy(Graph &to, const From& from,
578 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
579 for (typename From::NodeIt it(from); it != INVALID; ++it) {
580 nodeRefMap[it] = to.addNode();
582 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
583 edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
584 nodeRefMap[from.target(it)]);
589 template <typename Graph>
590 struct GraphCopySelector<
592 typename enable_if<typename Graph::BuildTag, void>::type>
594 template <typename From, typename NodeRefMap, typename EdgeRefMap>
595 static void copy(Graph &to, const From& from,
596 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
597 to.build(from, nodeRefMap, edgeRefMap);
603 /// \brief Class to copy a digraph.
605 /// Class to copy a digraph to another digraph (duplicate a digraph). The
606 /// simplest way of using it is through the \c copyDigraph() function.
608 /// This class not just make a copy of a graph, but it can create
609 /// references and cross references between the nodes and arcs of
610 /// the two graphs, it can copy maps for use with the newly created
611 /// graph and copy nodes and arcs.
613 /// To make a copy from a graph, first an instance of DigraphCopy
614 /// should be created, then the data belongs to the graph should
615 /// assigned to copy. In the end, the \c run() member should be
618 /// The next code copies a graph with several data:
620 /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
621 /// // create a reference for the nodes
622 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
624 /// // create a cross reference (inverse) for the arcs
625 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
626 /// dc.arcCrossRef(acr);
627 /// // copy an arc map
628 /// OrigGraph::ArcMap<double> oamap(orig_graph);
629 /// NewGraph::ArcMap<double> namap(new_graph);
630 /// dc.arcMap(namap, oamap);
632 /// OrigGraph::Node on;
633 /// NewGraph::Node nn;
635 /// // Executions of copy
638 template <typename To, typename From>
642 typedef typename From::Node Node;
643 typedef typename From::NodeIt NodeIt;
644 typedef typename From::Arc Arc;
645 typedef typename From::ArcIt ArcIt;
647 typedef typename To::Node TNode;
648 typedef typename To::Arc TArc;
650 typedef typename From::template NodeMap<TNode> NodeRefMap;
651 typedef typename From::template ArcMap<TArc> ArcRefMap;
657 /// \brief Constructor for the DigraphCopy.
659 /// It copies the content of the \c _from digraph into the
661 DigraphCopy(To& to, const From& from)
662 : _from(from), _to(to) {}
664 /// \brief Destructor of the DigraphCopy
666 /// Destructor of the DigraphCopy
668 for (int i = 0; i < int(_node_maps.size()); ++i) {
669 delete _node_maps[i];
671 for (int i = 0; i < int(_arc_maps.size()); ++i) {
677 /// \brief Copies the node references into the given map.
679 /// Copies the node references into the given map. The parameter
680 /// should be a map, which key type is the Node type of the source
681 /// graph, while the value type is the Node type of the
682 /// destination graph.
683 template <typename NodeRef>
684 DigraphCopy& nodeRef(NodeRef& map) {
685 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
686 NodeRefMap, NodeRef>(map));
690 /// \brief Copies the node cross references into the given map.
692 /// Copies the node cross references (reverse references) into
693 /// the given map. The parameter should be a map, which key type
694 /// is the Node type of the destination graph, while the value type is
695 /// the Node type of the source graph.
696 template <typename NodeCrossRef>
697 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
698 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
699 NodeRefMap, NodeCrossRef>(map));
703 /// \brief Make copy of the given map.
705 /// Makes copy of the given map for the newly created digraph.
706 /// The new map's key type is the destination graph's node type,
707 /// and the copied map's key type is the source graph's node type.
708 template <typename ToMap, typename FromMap>
709 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
710 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
711 NodeRefMap, ToMap, FromMap>(tmap, map));
715 /// \brief Make a copy of the given node.
717 /// Make a copy of the given node.
718 DigraphCopy& node(TNode& tnode, const Node& snode) {
719 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
720 NodeRefMap, TNode>(tnode, snode));
724 /// \brief Copies the arc references into the given map.
726 /// Copies the arc references into the given map.
727 template <typename ArcRef>
728 DigraphCopy& arcRef(ArcRef& map) {
729 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
730 ArcRefMap, ArcRef>(map));
734 /// \brief Copies the arc cross references into the given map.
736 /// Copies the arc cross references (reverse references) into
738 template <typename ArcCrossRef>
739 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
740 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
741 ArcRefMap, ArcCrossRef>(map));
745 /// \brief Make copy of the given map.
747 /// Makes copy of the given map for the newly created digraph.
748 /// The new map's key type is the to digraph's arc type,
749 /// and the copied map's key type is the from digraph's arc
751 template <typename ToMap, typename FromMap>
752 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
753 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
754 ArcRefMap, ToMap, FromMap>(tmap, map));
758 /// \brief Make a copy of the given arc.
760 /// Make a copy of the given arc.
761 DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
762 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
763 ArcRefMap, TArc>(tarc, sarc));
767 /// \brief Executes the copies.
769 /// Executes the copies.
771 NodeRefMap nodeRefMap(_from);
772 ArcRefMap arcRefMap(_from);
773 _graph_utils_bits::DigraphCopySelector<To>::
774 copy(_to, _from, nodeRefMap, arcRefMap);
775 for (int i = 0; i < int(_node_maps.size()); ++i) {
776 _node_maps[i]->copy(_from, nodeRefMap);
778 for (int i = 0; i < int(_arc_maps.size()); ++i) {
779 _arc_maps[i]->copy(_from, arcRefMap);
789 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
792 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
797 /// \brief Copy a digraph to another digraph.
799 /// Copy a digraph to another digraph. The complete usage of the
800 /// function is detailed in the DigraphCopy class, but a short
801 /// example shows a basic work:
803 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
806 /// After the copy the \c nr map will contain the mapping from the
807 /// nodes of the \c from digraph to the nodes of the \c to digraph and
808 /// \c ecr will contain the mapping from the arcs of the \c to digraph
809 /// to the arcs of the \c from digraph.
812 template <typename To, typename From>
813 DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
814 return DigraphCopy<To, From>(to, from);
817 /// \brief Class to copy a graph.
819 /// Class to copy a graph to another graph (duplicate a graph). The
820 /// simplest way of using it is through the \c copyGraph() function.
822 /// This class not just make a copy of a graph, but it can create
823 /// references and cross references between the nodes, edges and arcs of
824 /// the two graphs, it can copy maps for use with the newly created
825 /// graph and copy nodes, edges and arcs.
827 /// To make a copy from a graph, first an instance of GraphCopy
828 /// should be created, then the data belongs to the graph should
829 /// assigned to copy. In the end, the \c run() member should be
832 /// The next code copies a graph with several data:
834 /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
835 /// // create a reference for the nodes
836 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
838 /// // create a cross reference (inverse) for the edges
839 /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
840 /// dc.edgeCrossRef(ecr);
841 /// // copy an arc map
842 /// OrigGraph::ArcMap<double> oamap(orig_graph);
843 /// NewGraph::ArcMap<double> namap(new_graph);
844 /// dc.arcMap(namap, oamap);
846 /// OrigGraph::Node on;
847 /// NewGraph::Node nn;
849 /// // Executions of copy
852 template <typename To, typename From>
856 typedef typename From::Node Node;
857 typedef typename From::NodeIt NodeIt;
858 typedef typename From::Arc Arc;
859 typedef typename From::ArcIt ArcIt;
860 typedef typename From::Edge Edge;
861 typedef typename From::EdgeIt EdgeIt;
863 typedef typename To::Node TNode;
864 typedef typename To::Arc TArc;
865 typedef typename To::Edge TEdge;
867 typedef typename From::template NodeMap<TNode> NodeRefMap;
868 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
871 ArcRefMap(const To& to, const From& from,
872 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
873 : _to(to), _from(from),
874 _edge_ref(edge_ref), _node_ref(node_ref) {}
876 typedef typename From::Arc Key;
877 typedef typename To::Arc Value;
879 Value operator[](const Key& key) const {
881 (_from.direction(key) ==
882 (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
883 return _to.direct(_edge_ref[key], forward);
888 const EdgeRefMap& _edge_ref;
889 const NodeRefMap& _node_ref;
896 /// \brief Constructor for the GraphCopy.
898 /// It copies the content of the \c _from graph into the
900 GraphCopy(To& to, const From& from)
901 : _from(from), _to(to) {}
903 /// \brief Destructor of the GraphCopy
905 /// Destructor of the GraphCopy
907 for (int i = 0; i < int(_node_maps.size()); ++i) {
908 delete _node_maps[i];
910 for (int i = 0; i < int(_arc_maps.size()); ++i) {
913 for (int i = 0; i < int(_edge_maps.size()); ++i) {
914 delete _edge_maps[i];
919 /// \brief Copies the node references into the given map.
921 /// Copies the node references into the given map.
922 template <typename NodeRef>
923 GraphCopy& nodeRef(NodeRef& map) {
924 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
925 NodeRefMap, NodeRef>(map));
929 /// \brief Copies the node cross references into the given map.
931 /// Copies the node cross references (reverse references) into
933 template <typename NodeCrossRef>
934 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
935 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
936 NodeRefMap, NodeCrossRef>(map));
940 /// \brief Make copy of the given map.
942 /// Makes copy of the given map for the newly created graph.
943 /// The new map's key type is the to graph's node type,
944 /// and the copied map's key type is the from graph's node
946 template <typename ToMap, typename FromMap>
947 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
948 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
949 NodeRefMap, ToMap, FromMap>(tmap, map));
953 /// \brief Make a copy of the given node.
955 /// Make a copy of the given node.
956 GraphCopy& node(TNode& tnode, const Node& snode) {
957 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
958 NodeRefMap, TNode>(tnode, snode));
962 /// \brief Copies the arc references into the given map.
964 /// Copies the arc references into the given map.
965 template <typename ArcRef>
966 GraphCopy& arcRef(ArcRef& map) {
967 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
968 ArcRefMap, ArcRef>(map));
972 /// \brief Copies the arc cross references into the given map.
974 /// Copies the arc cross references (reverse references) into
976 template <typename ArcCrossRef>
977 GraphCopy& arcCrossRef(ArcCrossRef& map) {
978 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
979 ArcRefMap, ArcCrossRef>(map));
983 /// \brief Make copy of the given map.
985 /// Makes copy of the given map for the newly created graph.
986 /// The new map's key type is the to graph's arc type,
987 /// and the copied map's key type is the from graph's arc
989 template <typename ToMap, typename FromMap>
990 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
991 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
992 ArcRefMap, ToMap, FromMap>(tmap, map));
996 /// \brief Make a copy of the given arc.
998 /// Make a copy of the given arc.
999 GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1000 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1001 ArcRefMap, TArc>(tarc, sarc));
1005 /// \brief Copies the edge references into the given map.
1007 /// Copies the edge references into the given map.
1008 template <typename EdgeRef>
1009 GraphCopy& edgeRef(EdgeRef& map) {
1010 _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1011 EdgeRefMap, EdgeRef>(map));
1015 /// \brief Copies the edge cross references into the given map.
1017 /// Copies the edge cross references (reverse
1018 /// references) into the given map.
1019 template <typename EdgeCrossRef>
1020 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1021 _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1022 Edge, EdgeRefMap, EdgeCrossRef>(map));
1026 /// \brief Make copy of the given map.
1028 /// Makes copy of the given map for the newly created graph.
1029 /// The new map's key type is the to graph's edge type,
1030 /// and the copied map's key type is the from graph's edge
1032 template <typename ToMap, typename FromMap>
1033 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1034 _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1035 EdgeRefMap, ToMap, FromMap>(tmap, map));
1039 /// \brief Make a copy of the given edge.
1041 /// Make a copy of the given edge.
1042 GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1043 _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1044 EdgeRefMap, TEdge>(tedge, sedge));
1048 /// \brief Executes the copies.
1050 /// Executes the copies.
1052 NodeRefMap nodeRefMap(_from);
1053 EdgeRefMap edgeRefMap(_from);
1054 ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
1055 _graph_utils_bits::GraphCopySelector<To>::
1056 copy(_to, _from, nodeRefMap, edgeRefMap);
1057 for (int i = 0; i < int(_node_maps.size()); ++i) {
1058 _node_maps[i]->copy(_from, nodeRefMap);
1060 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1061 _edge_maps[i]->copy(_from, edgeRefMap);
1063 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1064 _arc_maps[i]->copy(_from, arcRefMap);
1073 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1076 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1079 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1084 /// \brief Copy a graph to another graph.
1086 /// Copy a graph to another graph. The complete usage of the
1087 /// function is detailed in the GraphCopy class, but a short
1088 /// example shows a basic work:
1090 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1093 /// After the copy the \c nr map will contain the mapping from the
1094 /// nodes of the \c from graph to the nodes of the \c to graph and
1095 /// \c ecr will contain the mapping from the arcs of the \c to graph
1096 /// to the arcs of the \c from graph.
1099 template <typename To, typename From>
1101 copyGraph(To& to, const From& from) {
1102 return GraphCopy<To, From>(to, from);
1107 /// \addtogroup graph_maps
1110 /// Provides an immutable and unique id for each item in the graph.
1112 /// The IdMap class provides a unique and immutable id for each item of the
1113 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1114 /// different items (nodes) get different ids <li>\b immutable: the id of an
1115 /// item (node) does not change (even if you delete other nodes). </ul>
1116 /// Through this map you get access (i.e. can read) the inner id values of
1117 /// the items stored in the graph. This map can be inverted with its member
1118 /// class \c InverseMap or with the \c operator() member.
1120 template <typename _Graph, typename _Item>
1123 typedef _Graph Graph;
1128 /// \brief Constructor.
1130 /// Constructor of the map.
1131 explicit IdMap(const Graph& graph) : _graph(&graph) {}
1133 /// \brief Gives back the \e id of the item.
1135 /// Gives back the immutable and unique \e id of the item.
1136 int operator[](const Item& item) const { return _graph->id(item);}
1138 /// \brief Gives back the item by its id.
1140 /// Gives back the item by its id.
1141 Item operator()(int id) { return _graph->fromId(id, Item()); }
1144 const Graph* _graph;
1148 /// \brief The class represents the inverse of its owner (IdMap).
1150 /// The class represents the inverse of its owner (IdMap).
1155 /// \brief Constructor.
1157 /// Constructor for creating an id-to-item map.
1158 explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1160 /// \brief Constructor.
1162 /// Constructor for creating an id-to-item map.
1163 explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1165 /// \brief Gives back the given item from its id.
1167 /// Gives back the given item from its id.
1169 Item operator[](int id) const { return _graph->fromId(id, Item());}
1172 const Graph* _graph;
1175 /// \brief Gives back the inverse of the map.
1177 /// Gives back the inverse of the IdMap.
1178 InverseMap inverse() const { return InverseMap(*_graph);}
1183 /// \brief General invertable graph-map type.
1185 /// This type provides simple invertable graph-maps.
1186 /// The InvertableMap wraps an arbitrary ReadWriteMap
1187 /// and if a key is set to a new value then store it
1188 /// in the inverse map.
1190 /// The values of the map can be accessed
1191 /// with stl compatible forward iterator.
1193 /// \param _Graph The graph type.
1194 /// \param _Item The item type of the graph.
1195 /// \param _Value The value type of the map.
1197 /// \see IterableValueMap
1198 template <typename _Graph, typename _Item, typename _Value>
1199 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1202 typedef DefaultMap<_Graph, _Item, _Value> Map;
1203 typedef _Graph Graph;
1205 typedef std::map<_Value, _Item> Container;
1210 /// The key type of InvertableMap (Node, Arc, Edge).
1211 typedef typename Map::Key Key;
1212 /// The value type of the InvertableMap.
1213 typedef typename Map::Value Value;
1217 /// \brief Constructor.
1219 /// Construct a new InvertableMap for the graph.
1221 explicit InvertableMap(const Graph& graph) : Map(graph) {}
1223 /// \brief Forward iterator for values.
1225 /// This iterator is an stl compatible forward
1226 /// iterator on the values of the map. The values can
1227 /// be accessed in the [beginValue, endValue) range.
1230 : public std::iterator<std::forward_iterator_tag, Value> {
1231 friend class InvertableMap;
1233 ValueIterator(typename Container::const_iterator _it)
1239 ValueIterator& operator++() { ++it; return *this; }
1240 ValueIterator operator++(int) {
1241 ValueIterator tmp(*this);
1246 const Value& operator*() const { return it->first; }
1247 const Value* operator->() const { return &(it->first); }
1249 bool operator==(ValueIterator jt) const { return it == jt.it; }
1250 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1253 typename Container::const_iterator it;
1256 /// \brief Returns an iterator to the first value.
1258 /// Returns an stl compatible iterator to the
1259 /// first value of the map. The values of the
1260 /// map can be accessed in the [beginValue, endValue)
1262 ValueIterator beginValue() const {
1263 return ValueIterator(_inv_map.begin());
1266 /// \brief Returns an iterator after the last value.
1268 /// Returns an stl compatible iterator after the
1269 /// last value of the map. The values of the
1270 /// map can be accessed in the [beginValue, endValue)
1272 ValueIterator endValue() const {
1273 return ValueIterator(_inv_map.end());
1276 /// \brief The setter function of the map.
1278 /// Sets the mapped value.
1279 void set(const Key& key, const Value& val) {
1280 Value oldval = Map::operator[](key);
1281 typename Container::iterator it = _inv_map.find(oldval);
1282 if (it != _inv_map.end() && it->second == key) {
1285 _inv_map.insert(make_pair(val, key));
1289 /// \brief The getter function of the map.
1291 /// It gives back the value associated with the key.
1292 typename MapTraits<Map>::ConstReturnValue
1293 operator[](const Key& key) const {
1294 return Map::operator[](key);
1297 /// \brief Gives back the item by its value.
1299 /// Gives back the item by its value.
1300 Key operator()(const Value& key) const {
1301 typename Container::const_iterator it = _inv_map.find(key);
1302 return it != _inv_map.end() ? it->second : INVALID;
1307 /// \brief Erase the key from the map.
1309 /// Erase the key to the map. It is called by the
1310 /// \c AlterationNotifier.
1311 virtual void erase(const Key& key) {
1312 Value val = Map::operator[](key);
1313 typename Container::iterator it = _inv_map.find(val);
1314 if (it != _inv_map.end() && it->second == key) {
1320 /// \brief Erase more keys from the map.
1322 /// Erase more keys from the map. It is called by the
1323 /// \c AlterationNotifier.
1324 virtual void erase(const std::vector<Key>& keys) {
1325 for (int i = 0; i < int(keys.size()); ++i) {
1326 Value val = Map::operator[](keys[i]);
1327 typename Container::iterator it = _inv_map.find(val);
1328 if (it != _inv_map.end() && it->second == keys[i]) {
1335 /// \brief Clear the keys from the map and inverse map.
1337 /// Clear the keys from the map and inverse map. It is called by the
1338 /// \c AlterationNotifier.
1339 virtual void clear() {
1346 /// \brief The inverse map type.
1348 /// The inverse of this map. The subscript operator of the map
1349 /// gives back always the item what was last assigned to the value.
1352 /// \brief Constructor of the InverseMap.
1354 /// Constructor of the InverseMap.
1355 explicit InverseMap(const InvertableMap& inverted)
1356 : _inverted(inverted) {}
1358 /// The value type of the InverseMap.
1359 typedef typename InvertableMap::Key Value;
1360 /// The key type of the InverseMap.
1361 typedef typename InvertableMap::Value Key;
1363 /// \brief Subscript operator.
1365 /// Subscript operator. It gives back always the item
1366 /// what was last assigned to the value.
1367 Value operator[](const Key& key) const {
1368 return _inverted(key);
1372 const InvertableMap& _inverted;
1375 /// \brief It gives back the just readable inverse map.
1377 /// It gives back the just readable inverse map.
1378 InverseMap inverse() const {
1379 return InverseMap(*this);
1386 /// \brief Provides a mutable, continuous and unique descriptor for each
1387 /// item in the graph.
1389 /// The DescriptorMap class provides a unique and continuous (but mutable)
1390 /// descriptor (id) for each item of the same type (e.g. node) in the
1391 /// graph. This id is <ul><li>\b unique: different items (nodes) get
1392 /// different ids <li>\b continuous: the range of the ids is the set of
1393 /// integers between 0 and \c n-1, where \c n is the number of the items of
1394 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1395 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1396 /// with its member class \c InverseMap, or with the \c operator() member.
1398 /// \param _Graph The graph class the \c DescriptorMap belongs to.
1399 /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
1401 template <typename _Graph, typename _Item>
1402 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1405 typedef DefaultMap<_Graph, _Item, int> Map;
1408 /// The graph class of DescriptorMap.
1409 typedef _Graph Graph;
1411 /// The key type of DescriptorMap (Node, Arc, Edge).
1412 typedef typename Map::Key Key;
1413 /// The value type of DescriptorMap.
1414 typedef typename Map::Value Value;
1416 /// \brief Constructor.
1418 /// Constructor for descriptor map.
1419 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1421 const typename Map::Notifier* nf = Map::notifier();
1422 for (nf->first(it); it != INVALID; nf->next(it)) {
1423 Map::set(it, _inv_map.size());
1424 _inv_map.push_back(it);
1430 /// \brief Add a new key to the map.
1432 /// Add a new key to the map. It is called by the
1433 /// \c AlterationNotifier.
1434 virtual void add(const Item& item) {
1436 Map::set(item, _inv_map.size());
1437 _inv_map.push_back(item);
1440 /// \brief Add more new keys to the map.
1442 /// Add more new keys to the map. It is called by the
1443 /// \c AlterationNotifier.
1444 virtual void add(const std::vector<Item>& items) {
1446 for (int i = 0; i < int(items.size()); ++i) {
1447 Map::set(items[i], _inv_map.size());
1448 _inv_map.push_back(items[i]);
1452 /// \brief Erase the key from the map.
1454 /// Erase the key from the map. It is called by the
1455 /// \c AlterationNotifier.
1456 virtual void erase(const Item& item) {
1457 Map::set(_inv_map.back(), Map::operator[](item));
1458 _inv_map[Map::operator[](item)] = _inv_map.back();
1459 _inv_map.pop_back();
1463 /// \brief Erase more keys from the map.
1465 /// Erase more keys from the map. It is called by the
1466 /// \c AlterationNotifier.
1467 virtual void erase(const std::vector<Item>& items) {
1468 for (int i = 0; i < int(items.size()); ++i) {
1469 Map::set(_inv_map.back(), Map::operator[](items[i]));
1470 _inv_map[Map::operator[](items[i])] = _inv_map.back();
1471 _inv_map.pop_back();
1476 /// \brief Build the unique map.
1478 /// Build the unique map. It is called by the
1479 /// \c AlterationNotifier.
1480 virtual void build() {
1483 const typename Map::Notifier* nf = Map::notifier();
1484 for (nf->first(it); it != INVALID; nf->next(it)) {
1485 Map::set(it, _inv_map.size());
1486 _inv_map.push_back(it);
1490 /// \brief Clear the keys from the map.
1492 /// Clear the keys from the map. It is called by the
1493 /// \c AlterationNotifier.
1494 virtual void clear() {
1501 /// \brief Returns the maximal value plus one.
1503 /// Returns the maximal value plus one in the map.
1504 unsigned int size() const {
1505 return _inv_map.size();
1508 /// \brief Swaps the position of the two items in the map.
1510 /// Swaps the position of the two items in the map.
1511 void swap(const Item& p, const Item& q) {
1512 int pi = Map::operator[](p);
1513 int qi = Map::operator[](q);
1520 /// \brief Gives back the \e descriptor of the item.
1522 /// Gives back the mutable and unique \e descriptor of the map.
1523 int operator[](const Item& item) const {
1524 return Map::operator[](item);
1527 /// \brief Gives back the item by its descriptor.
1529 /// Gives back th item by its descriptor.
1530 Item operator()(int id) const {
1531 return _inv_map[id];
1536 typedef std::vector<Item> Container;
1540 /// \brief The inverse map type of DescriptorMap.
1542 /// The inverse map type of DescriptorMap.
1545 /// \brief Constructor of the InverseMap.
1547 /// Constructor of the InverseMap.
1548 explicit InverseMap(const DescriptorMap& inverted)
1549 : _inverted(inverted) {}
1552 /// The value type of the InverseMap.
1553 typedef typename DescriptorMap::Key Value;
1554 /// The key type of the InverseMap.
1555 typedef typename DescriptorMap::Value Key;
1557 /// \brief Subscript operator.
1559 /// Subscript operator. It gives back the item
1560 /// that the descriptor belongs to currently.
1561 Value operator[](const Key& key) const {
1562 return _inverted(key);
1565 /// \brief Size of the map.
1567 /// Returns the size of the map.
1568 unsigned int size() const {
1569 return _inverted.size();
1573 const DescriptorMap& _inverted;
1576 /// \brief Gives back the inverse of the map.
1578 /// Gives back the inverse of the map.
1579 const InverseMap inverse() const {
1580 return InverseMap(*this);
1584 /// \brief Returns the source of the given arc.
1586 /// The SourceMap gives back the source Node of the given arc.
1588 /// \author Balazs Dezso
1589 template <typename Digraph>
1593 typedef typename Digraph::Node Value;
1594 typedef typename Digraph::Arc Key;
1596 /// \brief Constructor
1599 /// \param _digraph The digraph that the map belongs to.
1600 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
1602 /// \brief The subscript operator.
1604 /// The subscript operator.
1605 /// \param arc The arc
1606 /// \return The source of the arc
1607 Value operator[](const Key& arc) const {
1608 return _digraph.source(arc);
1612 const Digraph& _digraph;
1615 /// \brief Returns a \ref SourceMap class.
1617 /// This function just returns an \ref SourceMap class.
1618 /// \relates SourceMap
1619 template <typename Digraph>
1620 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
1621 return SourceMap<Digraph>(digraph);
1624 /// \brief Returns the target of the given arc.
1626 /// The TargetMap gives back the target Node of the given arc.
1628 /// \author Balazs Dezso
1629 template <typename Digraph>
1633 typedef typename Digraph::Node Value;
1634 typedef typename Digraph::Arc Key;
1636 /// \brief Constructor
1639 /// \param _digraph The digraph that the map belongs to.
1640 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
1642 /// \brief The subscript operator.
1644 /// The subscript operator.
1645 /// \param e The arc
1646 /// \return The target of the arc
1647 Value operator[](const Key& e) const {
1648 return _digraph.target(e);
1652 const Digraph& _digraph;
1655 /// \brief Returns a \ref TargetMap class.
1657 /// This function just returns a \ref TargetMap class.
1658 /// \relates TargetMap
1659 template <typename Digraph>
1660 inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
1661 return TargetMap<Digraph>(digraph);
1664 /// \brief Returns the "forward" directed arc view of an edge.
1666 /// Returns the "forward" directed arc view of an edge.
1667 /// \see BackwardMap
1668 /// \author Balazs Dezso
1669 template <typename Graph>
1673 typedef typename Graph::Arc Value;
1674 typedef typename Graph::Edge Key;
1676 /// \brief Constructor
1679 /// \param _graph The graph that the map belongs to.
1680 explicit ForwardMap(const Graph& graph) : _graph(graph) {}
1682 /// \brief The subscript operator.
1684 /// The subscript operator.
1685 /// \param key An edge
1686 /// \return The "forward" directed arc view of edge
1687 Value operator[](const Key& key) const {
1688 return _graph.direct(key, true);
1692 const Graph& _graph;
1695 /// \brief Returns a \ref ForwardMap class.
1697 /// This function just returns an \ref ForwardMap class.
1698 /// \relates ForwardMap
1699 template <typename Graph>
1700 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1701 return ForwardMap<Graph>(graph);
1704 /// \brief Returns the "backward" directed arc view of an edge.
1706 /// Returns the "backward" directed arc view of an edge.
1708 /// \author Balazs Dezso
1709 template <typename Graph>
1713 typedef typename Graph::Arc Value;
1714 typedef typename Graph::Edge Key;
1716 /// \brief Constructor
1719 /// \param _graph The graph that the map belongs to.
1720 explicit BackwardMap(const Graph& graph) : _graph(graph) {}
1722 /// \brief The subscript operator.
1724 /// The subscript operator.
1725 /// \param key An edge
1726 /// \return The "backward" directed arc view of edge
1727 Value operator[](const Key& key) const {
1728 return _graph.direct(key, false);
1732 const Graph& _graph;
1735 /// \brief Returns a \ref BackwardMap class
1737 /// This function just returns a \ref BackwardMap class.
1738 /// \relates BackwardMap
1739 template <typename Graph>
1740 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1741 return BackwardMap<Graph>(graph);
1744 /// \brief Potential difference map
1746 /// If there is an potential map on the nodes then we
1747 /// can get an arc map as we get the substraction of the
1748 /// values of the target and source.
1749 template <typename Digraph, typename NodeMap>
1750 class PotentialDifferenceMap {
1752 typedef typename Digraph::Arc Key;
1753 typedef typename NodeMap::Value Value;
1755 /// \brief Constructor
1757 /// Contructor of the map
1758 explicit PotentialDifferenceMap(const Digraph& digraph,
1759 const NodeMap& potential)
1760 : _digraph(digraph), _potential(potential) {}
1762 /// \brief Const subscription operator
1764 /// Const subscription operator
1765 Value operator[](const Key& arc) const {
1766 return _potential[_digraph.target(arc)] -
1767 _potential[_digraph.source(arc)];
1771 const Digraph& _digraph;
1772 const NodeMap& _potential;
1775 /// \brief Returns a PotentialDifferenceMap.
1777 /// This function just returns a PotentialDifferenceMap.
1778 /// \relates PotentialDifferenceMap
1779 template <typename Digraph, typename NodeMap>
1780 PotentialDifferenceMap<Digraph, NodeMap>
1781 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
1782 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
1785 /// \brief Map of the node in-degrees.
1787 /// This map returns the in-degree of a node. Once it is constructed,
1788 /// the degrees are stored in a standard NodeMap, so each query is done
1789 /// in constant time. On the other hand, the values are updated automatically
1790 /// whenever the digraph changes.
1792 /// \warning Besides addNode() and addArc(), a digraph structure may provide
1793 /// alternative ways to modify the digraph. The correct behavior of InDegMap
1794 /// is not guarantied if these additional features are used. For example
1795 /// the functions \ref ListDigraph::changeSource() "changeSource()",
1796 /// \ref ListDigraph::changeTarget() "changeTarget()" and
1797 /// \ref ListDigraph::reverseArc() "reverseArc()"
1798 /// of \ref ListDigraph will \e not update the degree values correctly.
1802 template <typename _Digraph>
1804 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1805 ::ItemNotifier::ObserverBase {
1809 typedef _Digraph Digraph;
1811 typedef typename Digraph::Node Key;
1813 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1814 ::ItemNotifier::ObserverBase Parent;
1818 class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1821 typedef DefaultMap<Digraph, Key, int> Parent;
1823 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1825 virtual void add(const Key& key) {
1827 Parent::set(key, 0);
1830 virtual void add(const std::vector<Key>& keys) {
1832 for (int i = 0; i < int(keys.size()); ++i) {
1833 Parent::set(keys[i], 0);
1837 virtual void build() {
1840 typename Parent::Notifier* nf = Parent::notifier();
1841 for (nf->first(it); it != INVALID; nf->next(it)) {
1849 /// \brief Constructor.
1851 /// Constructor for creating in-degree map.
1852 explicit InDegMap(const Digraph& digraph)
1853 : _digraph(digraph), _deg(digraph) {
1854 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1856 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1857 _deg[it] = countInArcs(_digraph, it);
1861 /// Gives back the in-degree of a Node.
1862 int operator[](const Key& key) const {
1868 typedef typename Digraph::Arc Arc;
1870 virtual void add(const Arc& arc) {
1871 ++_deg[_digraph.target(arc)];
1874 virtual void add(const std::vector<Arc>& arcs) {
1875 for (int i = 0; i < int(arcs.size()); ++i) {
1876 ++_deg[_digraph.target(arcs[i])];
1880 virtual void erase(const Arc& arc) {
1881 --_deg[_digraph.target(arc)];
1884 virtual void erase(const std::vector<Arc>& arcs) {
1885 for (int i = 0; i < int(arcs.size()); ++i) {
1886 --_deg[_digraph.target(arcs[i])];
1890 virtual void build() {
1891 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1892 _deg[it] = countInArcs(_digraph, it);
1896 virtual void clear() {
1897 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1903 const Digraph& _digraph;
1907 /// \brief Map of the node out-degrees.
1909 /// This map returns the out-degree of a node. Once it is constructed,
1910 /// the degrees are stored in a standard NodeMap, so each query is done
1911 /// in constant time. On the other hand, the values are updated automatically
1912 /// whenever the digraph changes.
1914 /// \warning Besides addNode() and addArc(), a digraph structure may provide
1915 /// alternative ways to modify the digraph. The correct behavior of OutDegMap
1916 /// is not guarantied if these additional features are used. For example
1917 /// the functions \ref ListDigraph::changeSource() "changeSource()",
1918 /// \ref ListDigraph::changeTarget() "changeTarget()" and
1919 /// \ref ListDigraph::reverseArc() "reverseArc()"
1920 /// of \ref ListDigraph will \e not update the degree values correctly.
1924 template <typename _Digraph>
1926 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1927 ::ItemNotifier::ObserverBase {
1931 typedef _Digraph Digraph;
1933 typedef typename Digraph::Node Key;
1935 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1936 ::ItemNotifier::ObserverBase Parent;
1940 class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1943 typedef DefaultMap<Digraph, Key, int> Parent;
1945 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1947 virtual void add(const Key& key) {
1949 Parent::set(key, 0);
1951 virtual void add(const std::vector<Key>& keys) {
1953 for (int i = 0; i < int(keys.size()); ++i) {
1954 Parent::set(keys[i], 0);
1957 virtual void build() {
1960 typename Parent::Notifier* nf = Parent::notifier();
1961 for (nf->first(it); it != INVALID; nf->next(it)) {
1969 /// \brief Constructor.
1971 /// Constructor for creating out-degree map.
1972 explicit OutDegMap(const Digraph& digraph)
1973 : _digraph(digraph), _deg(digraph) {
1974 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1976 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1977 _deg[it] = countOutArcs(_digraph, it);
1981 /// Gives back the out-degree of a Node.
1982 int operator[](const Key& key) const {
1988 typedef typename Digraph::Arc Arc;
1990 virtual void add(const Arc& arc) {
1991 ++_deg[_digraph.source(arc)];
1994 virtual void add(const std::vector<Arc>& arcs) {
1995 for (int i = 0; i < int(arcs.size()); ++i) {
1996 ++_deg[_digraph.source(arcs[i])];
2000 virtual void erase(const Arc& arc) {
2001 --_deg[_digraph.source(arc)];
2004 virtual void erase(const std::vector<Arc>& arcs) {
2005 for (int i = 0; i < int(arcs.size()); ++i) {
2006 --_deg[_digraph.source(arcs[i])];
2010 virtual void build() {
2011 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2012 _deg[it] = countOutArcs(_digraph, it);
2016 virtual void clear() {
2017 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2023 const Digraph& _digraph;
2028 ///Dynamic arc look up between given endpoints.
2031 ///Using this class, you can find an arc in a digraph from a given
2032 ///source to a given target in amortized time <em>O(log d)</em>,
2033 ///where <em>d</em> is the out-degree of the source node.
2035 ///It is possible to find \e all parallel arcs between two nodes with
2036 ///the \c findFirst() and \c findNext() members.
2038 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
2039 ///digraph is not changed so frequently.
2041 ///This class uses a self-adjusting binary search tree, Sleator's
2042 ///and Tarjan's Splay tree for guarantee the logarithmic amortized
2043 ///time bound for arc lookups. This class also guarantees the
2044 ///optimal time bound in a constant factor for any distribution of
2047 ///\param G The type of the underlying digraph.
2053 : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
2056 typedef typename ItemSetTraits<G, typename G::Arc>
2057 ::ItemNotifier::ObserverBase Parent;
2059 DIGRAPH_TYPEDEFS(typename G);
2064 class AutoNodeMap : public DefaultMap<G, Node, Arc> {
2067 typedef DefaultMap<G, Node, Arc> Parent;
2069 AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
2071 virtual void add(const Node& node) {
2073 Parent::set(node, INVALID);
2076 virtual void add(const std::vector<Node>& nodes) {
2078 for (int i = 0; i < int(nodes.size()); ++i) {
2079 Parent::set(nodes[i], INVALID);
2083 virtual void build() {
2086 typename Parent::Notifier* nf = Parent::notifier();
2087 for (nf->first(it); it != INVALID; nf->next(it)) {
2088 Parent::set(it, INVALID);
2095 typename Digraph::template ArcMap<Arc> _parent;
2096 typename Digraph::template ArcMap<Arc> _left;
2097 typename Digraph::template ArcMap<Arc> _right;
2102 ArcLess(const Digraph &_g) : g(_g) {}
2103 bool operator()(Arc a,Arc b) const
2105 return g.target(a)<g.target(b);
2115 ///It builds up the search database.
2116 DynArcLookUp(const Digraph &g)
2117 : _g(g),_head(g),_parent(g),_left(g),_right(g)
2119 Parent::attach(_g.notifier(typename Digraph::Arc()));
2125 virtual void add(const Arc& arc) {
2129 virtual void add(const std::vector<Arc>& arcs) {
2130 for (int i = 0; i < int(arcs.size()); ++i) {
2135 virtual void erase(const Arc& arc) {
2139 virtual void erase(const std::vector<Arc>& arcs) {
2140 for (int i = 0; i < int(arcs.size()); ++i) {
2145 virtual void build() {
2149 virtual void clear() {
2150 for(NodeIt n(_g);n!=INVALID;++n) {
2151 _head.set(n, INVALID);
2155 void insert(Arc arc) {
2156 Node s = _g.source(arc);
2157 Node t = _g.target(arc);
2158 _left.set(arc, INVALID);
2159 _right.set(arc, INVALID);
2164 _parent.set(arc, INVALID);
2168 if (t < _g.target(e)) {
2169 if (_left[e] == INVALID) {
2171 _parent.set(arc, e);
2178 if (_right[e] == INVALID) {
2180 _parent.set(arc, e);
2190 void remove(Arc arc) {
2191 if (_left[arc] == INVALID) {
2192 if (_right[arc] != INVALID) {
2193 _parent.set(_right[arc], _parent[arc]);
2195 if (_parent[arc] != INVALID) {
2196 if (_left[_parent[arc]] == arc) {
2197 _left.set(_parent[arc], _right[arc]);
2199 _right.set(_parent[arc], _right[arc]);
2202 _head.set(_g.source(arc), _right[arc]);
2204 } else if (_right[arc] == INVALID) {
2205 _parent.set(_left[arc], _parent[arc]);
2206 if (_parent[arc] != INVALID) {
2207 if (_left[_parent[arc]] == arc) {
2208 _left.set(_parent[arc], _left[arc]);
2210 _right.set(_parent[arc], _left[arc]);
2213 _head.set(_g.source(arc), _left[arc]);
2217 if (_right[e] != INVALID) {
2219 while (_right[e] != INVALID) {
2223 _right.set(_parent[e], _left[e]);
2224 if (_left[e] != INVALID) {
2225 _parent.set(_left[e], _parent[e]);
2228 _left.set(e, _left[arc]);
2229 _parent.set(_left[arc], e);
2230 _right.set(e, _right[arc]);
2231 _parent.set(_right[arc], e);
2233 _parent.set(e, _parent[arc]);
2234 if (_parent[arc] != INVALID) {
2235 if (_left[_parent[arc]] == arc) {
2236 _left.set(_parent[arc], e);
2238 _right.set(_parent[arc], e);
2243 _right.set(e, _right[arc]);
2244 _parent.set(_right[arc], e);
2246 if (_parent[arc] != INVALID) {
2247 if (_left[_parent[arc]] == arc) {
2248 _left.set(_parent[arc], e);
2250 _right.set(_parent[arc], e);
2253 _head.set(_g.source(arc), e);
2259 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2264 Arc left = refreshRec(v,a,m-1);
2265 _left.set(me, left);
2266 _parent.set(left, me);
2268 _left.set(me, INVALID);
2271 Arc right = refreshRec(v,m+1,b);
2272 _right.set(me, right);
2273 _parent.set(right, me);
2275 _right.set(me, INVALID);
2281 for(NodeIt n(_g);n!=INVALID;++n) {
2283 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2285 std::sort(v.begin(),v.end(),ArcLess(_g));
2286 Arc head = refreshRec(v,0,v.size()-1);
2288 _parent.set(head, INVALID);
2290 else _head.set(n, INVALID);
2296 _parent.set(v, _parent[w]);
2298 _left.set(w, _right[v]);
2300 if (_parent[v] != INVALID) {
2301 if (_right[_parent[v]] == w) {
2302 _right.set(_parent[v], v);
2304 _left.set(_parent[v], v);
2307 if (_left[w] != INVALID){
2308 _parent.set(_left[w], w);
2314 _parent.set(v, _parent[w]);
2316 _right.set(w, _left[v]);
2318 if (_parent[v] != INVALID){
2319 if (_left[_parent[v]] == w) {
2320 _left.set(_parent[v], v);
2322 _right.set(_parent[v], v);
2325 if (_right[w] != INVALID){
2326 _parent.set(_right[w], w);
2331 while (_parent[v] != INVALID) {
2332 if (v == _left[_parent[v]]) {
2333 if (_parent[_parent[v]] == INVALID) {
2336 if (_parent[v] == _left[_parent[_parent[v]]]) {
2345 if (_parent[_parent[v]] == INVALID) {
2348 if (_parent[v] == _left[_parent[_parent[v]]]) {
2358 _head[_g.source(v)] = v;
2364 ///Find an arc between two nodes.
2366 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
2367 /// <em>d</em> is the number of outgoing arcs of \c s.
2368 ///\param s The source node
2369 ///\param t The target node
2370 ///\return An arc from \c s to \c t if there exists,
2371 ///\ref INVALID otherwise.
2372 Arc operator()(Node s, Node t) const
2376 if (_g.target(a) == t) {
2377 const_cast<DynArcLookUp&>(*this).splay(a);
2379 } else if (t < _g.target(a)) {
2380 if (_left[a] == INVALID) {
2381 const_cast<DynArcLookUp&>(*this).splay(a);
2387 if (_right[a] == INVALID) {
2388 const_cast<DynArcLookUp&>(*this).splay(a);
2397 ///Find the first arc between two nodes.
2399 ///Find the first arc between two nodes in time
2400 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2401 /// outgoing arcs of \c s.
2402 ///\param s The source node
2403 ///\param t The target node
2404 ///\return An arc from \c s to \c t if there exists, \ref INVALID
2406 Arc findFirst(Node s, Node t) const
2411 if (_g.target(a) < t) {
2412 if (_right[a] == INVALID) {
2413 const_cast<DynArcLookUp&>(*this).splay(a);
2419 if (_g.target(a) == t) {
2422 if (_left[a] == INVALID) {
2423 const_cast<DynArcLookUp&>(*this).splay(a);
2432 ///Find the next arc between two nodes.
2434 ///Find the next arc between two nodes in time
2435 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2436 /// outgoing arcs of \c s.
2437 ///\param s The source node
2438 ///\param t The target node
2439 ///\return An arc from \c s to \c t if there exists, \ref INVALID
2442 ///\note If \c e is not the result of the previous \c findFirst()
2443 ///operation then the amorized time bound can not be guaranteed.
2445 Arc findNext(Node s, Node t, Arc a) const
2447 Arc findNext(Node, Node t, Arc a) const
2450 if (_right[a] != INVALID) {
2452 while (_left[a] != INVALID) {
2455 const_cast<DynArcLookUp&>(*this).splay(a);
2457 while (_parent[a] != INVALID && _right[_parent[a]] == a) {
2460 if (_parent[a] == INVALID) {
2464 const_cast<DynArcLookUp&>(*this).splay(a);
2467 if (_g.target(a) == t) return a;
2468 else return INVALID;
2473 ///Fast arc look up between given endpoints.
2476 ///Using this class, you can find an arc in a digraph from a given
2477 ///source to a given target in time <em>O(log d)</em>,
2478 ///where <em>d</em> is the out-degree of the source node.
2480 ///It is not possible to find \e all parallel arcs between two nodes.
2481 ///Use \ref AllArcLookUp for this purpose.
2483 ///\warning This class is static, so you should refresh() (or at least
2484 ///refresh(Node)) this data structure
2485 ///whenever the digraph changes. This is a time consuming (superlinearly
2486 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
2488 ///\param G The type of the underlying digraph.
2496 DIGRAPH_TYPEDEFS(typename G);
2501 typename Digraph::template NodeMap<Arc> _head;
2502 typename Digraph::template ArcMap<Arc> _left;
2503 typename Digraph::template ArcMap<Arc> _right;
2508 ArcLess(const Digraph &_g) : g(_g) {}
2509 bool operator()(Arc a,Arc b) const
2511 return g.target(a)<g.target(b);
2521 ///It builds up the search database, which remains valid until the digraph
2523 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2526 Arc refreshRec(std::vector<Arc> &v,int a,int b)
2530 _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2531 _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2535 ///Refresh the data structure at a node.
2537 ///Build up the search database of node \c n.
2539 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2540 ///the number of the outgoing arcs of \c n.
2541 void refresh(Node n)
2544 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2546 std::sort(v.begin(),v.end(),ArcLess(_g));
2547 _head[n]=refreshRec(v,0,v.size()-1);
2549 else _head[n]=INVALID;
2551 ///Refresh the full data structure.
2553 ///Build up the full search database. In fact, it simply calls
2554 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2556 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2557 ///the number of the arcs of \c n and <em>D</em> is the maximum
2558 ///out-degree of the digraph.
2562 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2565 ///Find an arc between two nodes.
2567 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
2568 /// <em>d</em> is the number of outgoing arcs of \c s.
2569 ///\param s The source node
2570 ///\param t The target node
2571 ///\return An arc from \c s to \c t if there exists,
2572 ///\ref INVALID otherwise.
2574 ///\warning If you change the digraph, refresh() must be called before using
2575 ///this operator. If you change the outgoing arcs of
2576 ///a single node \c n, then
2577 ///\ref refresh(Node) "refresh(n)" is enough.
2579 Arc operator()(Node s, Node t) const
2583 e!=INVALID&&_g.target(e)!=t;
2584 e = t < _g.target(e)?_left[e]:_right[e]) ;
2590 ///Fast look up of all arcs between given endpoints.
2593 ///This class is the same as \ref ArcLookUp, with the addition
2594 ///that it makes it possible to find all arcs between given endpoints.
2596 ///\warning This class is static, so you should refresh() (or at least
2597 ///refresh(Node)) this data structure
2598 ///whenever the digraph changes. This is a time consuming (superlinearly
2599 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
2601 ///\param G The type of the underlying digraph.
2606 class AllArcLookUp : public ArcLookUp<G>
2608 using ArcLookUp<G>::_g;
2609 using ArcLookUp<G>::_right;
2610 using ArcLookUp<G>::_left;
2611 using ArcLookUp<G>::_head;
2613 DIGRAPH_TYPEDEFS(typename G);
2616 typename Digraph::template ArcMap<Arc> _next;
2618 Arc refreshNext(Arc head,Arc next=INVALID)
2620 if(head==INVALID) return next;
2622 next=refreshNext(_right[head],next);
2623 // _next[head]=next;
2624 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2626 return refreshNext(_left[head],head);
2632 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2640 ///It builds up the search database, which remains valid until the digraph
2642 AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
2644 ///Refresh the data structure at a node.
2646 ///Build up the search database of node \c n.
2648 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2649 ///the number of the outgoing arcs of \c n.
2651 void refresh(Node n)
2653 ArcLookUp<G>::refresh(n);
2654 refreshNext(_head[n]);
2657 ///Refresh the full data structure.
2659 ///Build up the full search database. In fact, it simply calls
2660 ///\ref refresh(Node) "refresh(n)" for each node \c n.
2662 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2663 ///the number of the arcs of \c n and <em>D</em> is the maximum
2664 ///out-degree of the digraph.
2668 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2671 ///Find an arc between two nodes.
2673 ///Find an arc between two nodes.
2674 ///\param s The source node
2675 ///\param t The target node
2676 ///\param prev The previous arc between \c s and \c t. It it is INVALID or
2677 ///not given, the operator finds the first appropriate arc.
2678 ///\return An arc from \c s to \c t after \c prev or
2679 ///\ref INVALID if there is no more.
2681 ///For example, you can count the number of arcs from \c u to \c v in the
2684 ///AllArcLookUp<ListDigraph> ae(g);
2687 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2690 ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
2691 /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
2692 ///consecutive arcs are found in constant time.
2694 ///\warning If you change the digraph, refresh() must be called before using
2695 ///this operator. If you change the outgoing arcs of
2696 ///a single node \c n, then
2697 ///\ref refresh(Node) "refresh(n)" is enough.
2700 Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
2702 using ArcLookUp<G>::operator() ;
2703 Arc operator()(Node s, Node t, Arc prev) const
2705 return prev==INVALID?(*this)(s,t):_next[prev];
2713 } //END OF NAMESPACE LEMON