2 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_GRAPH_UTILS_H
18 #define LEMON_GRAPH_UTILS_H
25 #include <lemon/invalid.h>
26 #include <lemon/utility.h>
27 #include <lemon/maps.h>
28 #include <lemon/bits/alteration_notifier.h>
32 ///\brief Graph utilities.
39 /// \addtogroup gutils
42 /// \brief Function to count the items in the graph.
44 /// This function counts the items (nodes, edges etc) in the graph.
45 /// The complexity of the function is O(n) because
46 /// it iterates on all of the items.
48 template <typename Graph, typename ItemIt>
49 inline int countItems(const Graph& g) {
51 for (ItemIt it(g); it != INVALID; ++it) {
59 template <typename Graph>
61 typename enable_if<typename Graph::NodeNumTag, int>::type
62 _countNodes(const Graph &g) {
66 template <typename Graph>
67 inline int _countNodes(Wrap<Graph> w) {
68 return countItems<Graph, typename Graph::NodeIt>(w.value);
71 /// \brief Function to count the nodes in the graph.
73 /// This function counts the nodes in the graph.
74 /// The complexity of the function is O(n) but for some
75 /// graph structures it is specialized to run in O(1).
77 /// \todo refer how to specialize it
79 template <typename Graph>
80 inline int countNodes(const Graph& g) {
81 return _countNodes<Graph>(g);
86 template <typename Graph>
88 typename enable_if<typename Graph::EdgeNumTag, int>::type
89 _countEdges(const Graph &g) {
93 template <typename Graph>
94 inline int _countEdges(Wrap<Graph> w) {
95 return countItems<Graph, typename Graph::EdgeIt>(w.value);
98 /// \brief Function to count the edges in the graph.
100 /// This function counts the edges in the graph.
101 /// The complexity of the function is O(e) but for some
102 /// graph structures it is specialized to run in O(1).
104 template <typename Graph>
105 inline int countEdges(const Graph& g) {
106 return _countEdges<Graph>(g);
109 // Undirected edge counting:
111 template <typename Graph>
113 typename enable_if<typename Graph::EdgeNumTag, int>::type
114 _countUndirEdges(const Graph &g) {
115 return g.undirEdgeNum();
118 template <typename Graph>
119 inline int _countUndirEdges(Wrap<Graph> w) {
120 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
123 /// \brief Function to count the undirected edges in the graph.
125 /// This function counts the undirected edges in the graph.
126 /// The complexity of the function is O(e) but for some
127 /// graph structures it is specialized to run in O(1).
129 template <typename Graph>
130 inline int countUndirEdges(const Graph& g) {
131 return _countUndirEdges<Graph>(g);
136 template <typename Graph, typename DegIt>
137 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
139 for (DegIt it(_g, _n); it != INVALID; ++it) {
145 /// \brief Function to count the number of the out-edges from node \c n.
147 /// This function counts the number of the out-edges from node \c n
149 template <typename Graph>
150 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
151 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
154 /// \brief Function to count the number of the in-edges to node \c n.
156 /// This function counts the number of the in-edges to node \c n
158 template <typename Graph>
159 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
160 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
163 /// \brief Function to count the number of the in-edges to node \c n.
165 /// This function counts the number of the in-edges to node \c n
167 template <typename Graph>
168 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
169 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
173 template <typename Graph>
175 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
176 _findEdge(const Graph &g,
177 typename Graph::Node u, typename Graph::Node v,
178 typename Graph::Edge prev = INVALID) {
179 return g.findEdge(u, v, prev);
182 template <typename Graph>
183 inline typename Graph::Edge
184 _findEdge(Wrap<Graph> w,
185 typename Graph::Node u,
186 typename Graph::Node v,
187 typename Graph::Edge prev = INVALID) {
188 const Graph& g = w.value;
189 if (prev == INVALID) {
190 typename Graph::OutEdgeIt e(g, u);
191 while (e != INVALID && g.target(e) != v) ++e;
194 typename Graph::OutEdgeIt e(g, prev); ++e;
195 while (e != INVALID && g.target(e) != v) ++e;
200 /// \brief Finds an edge between two nodes of a graph.
202 /// Finds an edge from node \c u to node \c v in graph \c g.
204 /// If \c prev is \ref INVALID (this is the default value), then
205 /// it finds the first edge from \c u to \c v. Otherwise it looks for
206 /// the next edge from \c u to \c v after \c prev.
207 /// \return The found edge or \ref INVALID if there is no such an edge.
209 /// Thus you can iterate through each edge from \c u to \c v as it follows.
211 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
215 // /// \todo We may want to use the "GraphBase"
216 // /// interface here...
217 // /// It would not work with the undirected graphs.
218 template <typename Graph>
219 inline typename Graph::Edge findEdge(const Graph &g,
220 typename Graph::Node u,
221 typename Graph::Node v,
222 typename Graph::Edge prev = INVALID) {
223 return _findEdge<Graph>(g, u, v, prev);
226 /// \brief Iterator for iterating on edges connected the same nodes.
228 /// Iterator for iterating on edges connected the same nodes. It is
229 /// higher level interface for the findEdge() function. You can
230 /// use it the following way:
232 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
237 /// \author Balazs Dezso
238 template <typename _Graph>
239 class ConEdgeIt : public _Graph::Edge {
242 typedef _Graph Graph;
243 typedef typename Graph::Edge Parent;
245 typedef typename Graph::Edge Edge;
246 typedef typename Graph::Node Node;
248 /// \brief Constructor.
250 /// Construct a new ConEdgeIt iterating on the edges which
251 /// connects the \c u and \c v node.
252 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
253 Parent::operator=(findEdge(graph, u, v));
256 /// \brief Constructor.
258 /// Construct a new ConEdgeIt which continues the iterating from
260 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
262 /// \brief Increment operator.
264 /// It increments the iterator and gives back the next edge.
265 ConEdgeIt& operator++() {
266 Parent::operator=(findEdge(graph, graph.source(*this),
267 graph.target(*this), *this));
274 /// \brief Copy a map.
276 /// This function copies the \c source map to the \c target map. It uses the
277 /// given iterator to iterate on the data structure and it uses the \c ref
278 /// mapping to convert the source's keys to the target's keys.
279 template <typename Target, typename Source,
280 typename ItemIt, typename Ref>
281 void copyMap(Target& target, const Source& source,
282 ItemIt it, const Ref& ref) {
283 for (; it != INVALID; ++it) {
284 target[ref[it]] = source[it];
288 /// \brief Copy the source map to the target map.
290 /// Copy the \c source map to the \c target map. It uses the given iterator
291 /// to iterate on the data structure.
292 template <typename Target, typename Source,
294 void copyMap(Target& target, const Source& source, ItemIt it) {
295 for (; it != INVALID; ++it) {
296 target[it] = source[it];
301 /// \brief Class to copy a graph.
303 /// Class to copy a graph to an other graph (duplicate a graph). The
304 /// simplest way of using it is through the \c copyGraph() function.
305 template <typename Target, typename Source>
308 typedef typename Source::Node Node;
309 typedef typename Source::NodeIt NodeIt;
310 typedef typename Source::Edge Edge;
311 typedef typename Source::EdgeIt EdgeIt;
313 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
314 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
316 /// \brief Constructor for the GraphCopy.
318 /// It copies the content of the \c _source graph into the
319 /// \c _target graph. It creates also two references, one beetween
320 /// the two nodeset and one beetween the two edgesets.
321 GraphCopy(Target& _target, const Source& _source)
322 : source(_source), target(_target),
323 nodeRefMap(_source), edgeRefMap(_source) {
324 for (NodeIt it(source); it != INVALID; ++it) {
325 nodeRefMap[it] = target.addNode();
327 for (EdgeIt it(source); it != INVALID; ++it) {
328 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
329 nodeRefMap[source.target(it)]);
333 /// \brief Copies the node references into the given map.
335 /// Copies the node references into the given map.
336 template <typename NodeRef>
337 const GraphCopy& nodeRef(NodeRef& map) const {
338 for (NodeIt it(source); it != INVALID; ++it) {
339 map.set(it, nodeRefMap[it]);
344 /// \brief Reverse and copies the node references into the given map.
346 /// Reverse and copies the node references into the given map.
347 template <typename NodeRef>
348 const GraphCopy& nodeCrossRef(NodeRef& map) const {
349 for (NodeIt it(source); it != INVALID; ++it) {
350 map.set(nodeRefMap[it], it);
355 /// \brief Copies the edge references into the given map.
357 /// Copies the edge references into the given map.
358 template <typename EdgeRef>
359 const GraphCopy& edgeRef(EdgeRef& map) const {
360 for (EdgeIt it(source); it != INVALID; ++it) {
361 map.set(it, edgeRefMap[it]);
366 /// \brief Reverse and copies the edge references into the given map.
368 /// Reverse and copies the edge references into the given map.
369 template <typename EdgeRef>
370 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
371 for (EdgeIt it(source); it != INVALID; ++it) {
372 map.set(edgeRefMap[it], it);
377 /// \brief Make copy of the given map.
379 /// Makes copy of the given map for the newly created graph.
380 /// The new map's key type is the target graph's node type,
381 /// and the copied map's key type is the source graph's node
383 template <typename TargetMap, typename SourceMap>
384 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
385 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
389 /// \brief Make copy of the given map.
391 /// Makes copy of the given map for the newly created graph.
392 /// The new map's key type is the target graph's edge type,
393 /// and the copied map's key type is the source graph's edge
395 template <typename TargetMap, typename SourceMap>
396 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
397 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
401 /// \brief Gives back the stored node references.
403 /// Gives back the stored node references.
404 const NodeRefMap& nodeRef() const {
408 /// \brief Gives back the stored edge references.
410 /// Gives back the stored edge references.
411 const EdgeRefMap& edgeRef() const {
417 const Source& source;
420 NodeRefMap nodeRefMap;
421 EdgeRefMap edgeRefMap;
424 /// \brief Copy a graph to an other graph.
426 /// Copy a graph to an other graph.
427 /// The usage of the function:
430 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
433 /// After the copy the \c nr map will contain the mapping from the
434 /// source graph's nodes to the target graph's nodes and the \c ecr will
435 /// contain the mapping from the target graph's edges to the source's
437 template <typename Target, typename Source>
438 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
439 return GraphCopy<Target, Source>(target, source);
442 template <typename _Graph, typename _Item>
443 class ItemSetTraits {};
445 template <typename _Graph>
446 class ItemSetTraits<_Graph, typename _Graph::Node> {
449 typedef _Graph Graph;
451 typedef typename Graph::Node Item;
452 typedef typename Graph::NodeIt ItemIt;
454 template <typename _Value>
455 class Map : public Graph::template NodeMap<_Value> {
457 typedef typename Graph::template NodeMap<_Value> Parent;
458 typedef typename Parent::Value Value;
460 Map(const Graph& _graph) : Parent(_graph) {}
461 Map(const Graph& _graph, const Value& _value)
462 : Parent(_graph, _value) {}
467 template <typename _Graph>
468 class ItemSetTraits<_Graph, typename _Graph::Edge> {
471 typedef _Graph Graph;
473 typedef typename Graph::Edge Item;
474 typedef typename Graph::EdgeIt ItemIt;
476 template <typename _Value>
477 class Map : public Graph::template EdgeMap<_Value> {
479 typedef typename Graph::template EdgeMap<_Value> Parent;
480 typedef typename Parent::Value Value;
482 Map(const Graph& _graph) : Parent(_graph) {}
483 Map(const Graph& _graph, const Value& _value)
484 : Parent(_graph, _value) {}
489 template <typename _Graph>
490 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
493 typedef _Graph Graph;
495 typedef typename Graph::UndirEdge Item;
496 typedef typename Graph::UndirEdgeIt ItemIt;
498 template <typename _Value>
499 class Map : public Graph::template UndirEdgeMap<_Value> {
501 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
502 typedef typename Parent::Value Value;
504 Map(const Graph& _graph) : Parent(_graph) {}
505 Map(const Graph& _graph, const Value& _value)
506 : Parent(_graph, _value) {}
513 /// \addtogroup graph_maps
516 template <typename Map, typename Enable = void>
517 struct ReferenceMapTraits {
518 typedef typename Map::Value Value;
519 typedef typename Map::Value& Reference;
520 typedef const typename Map::Value& ConstReference;
521 typedef typename Map::Value* Pointer;
522 typedef const typename Map::Value* ConstPointer;
525 template <typename Map>
526 struct ReferenceMapTraits<
528 typename enable_if<typename Map::FullTypeTag, void>::type
530 typedef typename Map::Value Value;
531 typedef typename Map::Reference Reference;
532 typedef typename Map::ConstReference ConstReference;
533 typedef typename Map::Pointer Pointer;
534 typedef typename Map::ConstPointer ConstPointer;
537 /// Provides an immutable and unique id for each item in the graph.
539 /// The IdMap class provides a unique and immutable id for each item of the
540 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
541 /// different items (nodes) get different ids <li>\b immutable: the id of an
542 /// item (node) does not change (even if you delete other nodes). </ul>
543 /// Through this map you get access (i.e. can read) the inner id values of
544 /// the items stored in the graph. This map can be inverted with its member
545 /// class \c InverseMap.
547 template <typename _Graph, typename _Item>
550 typedef _Graph Graph;
555 typedef True NeedCopy;
557 /// \brief Constructor.
559 /// Constructor for creating id map.
560 IdMap(const Graph& _graph) : graph(&_graph) {}
562 /// \brief Gives back the \e id of the item.
564 /// Gives back the immutable and unique \e id of the map.
565 int operator[](const Item& item) const { return graph->id(item);}
573 /// \brief The class represents the inverse of its owner (IdMap).
575 /// The class represents the inverse of its owner (IdMap).
580 typedef True NeedCopy;
582 /// \brief Constructor.
584 /// Constructor for creating an id-to-item map.
585 InverseMap(const Graph& _graph) : graph(&_graph) {}
587 /// \brief Constructor.
589 /// Constructor for creating an id-to-item map.
590 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
592 /// \brief Gives back the given item from its id.
594 /// Gives back the given item from its id.
596 Item operator[](int id) const { return graph->fromId(id, Item());}
601 /// \brief Gives back the inverse of the map.
603 /// Gives back the inverse of the IdMap.
604 InverseMap inverse() const { return InverseMap(*graph);}
609 /// \brief General invertable graph-map type.
611 /// This type provides simple invertable graph-maps.
612 /// The InvertableMap wraps an arbitrary ReadWriteMap
613 /// and if a key is set to a new value then store it
614 /// in the inverse map.
615 /// \param _Graph The graph type.
616 /// \param _Map The map to extend with invertable functionality.
622 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
624 class InvertableMap : protected _Map {
629 typedef _Graph Graph;
631 /// The key type of InvertableMap (Node, Edge, UndirEdge).
632 typedef typename _Map::Key Key;
633 /// The value type of the InvertableMap.
634 typedef typename _Map::Value Value;
636 /// \brief Constructor.
638 /// Construct a new InvertableMap for the graph.
640 InvertableMap(const Graph& graph) : Map(graph) {}
642 /// \brief The setter function of the map.
644 /// Sets the mapped value.
645 void set(const Key& key, const Value& val) {
646 Value oldval = Map::operator[](key);
647 typename Container::iterator it = invMap.find(oldval);
648 if (it != invMap.end() && it->second == key) {
651 invMap.insert(make_pair(val, key));
655 /// \brief The getter function of the map.
657 /// It gives back the value associated with the key.
658 const Value operator[](const Key& key) const {
659 return Map::operator[](key);
664 /// \brief Add a new key to the map.
666 /// Add a new key to the map. It is called by the
667 /// \c AlterationNotifier.
668 virtual void add(const Key& key) {
672 /// \brief Erase the key from the map.
674 /// Erase the key to the map. It is called by the
675 /// \c AlterationNotifier.
676 virtual void erase(const Key& key) {
677 Value val = Map::operator[](key);
678 typename Container::iterator it = invMap.find(val);
679 if (it != invMap.end() && it->second == key) {
685 /// \brief Clear the keys from the map and inverse map.
687 /// Clear the keys from the map and inverse map. It is called by the
688 /// \c AlterationNotifier.
689 virtual void clear() {
696 typedef std::map<Value, Key> Container;
701 /// \brief The inverse map type.
703 /// The inverse of this map. The subscript operator of the map
704 /// gives back always the item what was last assigned to the value.
707 /// \brief Constructor of the InverseMap.
709 /// Constructor of the InverseMap.
710 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
712 /// The value type of the InverseMap.
713 typedef typename InvertableMap::Key Value;
714 /// The key type of the InverseMap.
715 typedef typename InvertableMap::Value Key;
717 /// \brief Subscript operator.
719 /// Subscript operator. It gives back always the item
720 /// what was last assigned to the value.
721 Value operator[](const Key& key) const {
722 typename Container::const_iterator it = inverted.invMap.find(key);
727 const InvertableMap& inverted;
730 /// \brief It gives back the just readeable inverse map.
732 /// It gives back the just readeable inverse map.
733 InverseMap inverse() const {
734 return InverseMap(*this);
741 /// \brief Provides a mutable, continuous and unique descriptor for each
742 /// item in the graph.
744 /// The DescriptorMap class provides a unique and continuous (but mutable)
745 /// descriptor (id) for each item of the same type (e.g. node) in the
746 /// graph. This id is <ul><li>\b unique: different items (nodes) get
747 /// different ids <li>\b continuous: the range of the ids is the set of
748 /// integers between 0 and \c n-1, where \c n is the number of the items of
749 /// this type (e.g. nodes) (so the id of a node can change if you delete an
750 /// other node, i.e. this id is mutable). </ul> This map can be inverted
751 /// with its member class \c InverseMap.
753 /// \param _Graph The graph class the \c DescriptorMap belongs to.
754 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
756 /// \param _Map A ReadWriteMap mapping from the item type to integer.
761 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
763 class DescriptorMap : protected _Map {
769 /// The graph class of DescriptorMap.
770 typedef _Graph Graph;
772 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
773 typedef typename _Map::Key Key;
774 /// The value type of DescriptorMap.
775 typedef typename _Map::Value Value;
777 /// \brief Constructor.
779 /// Constructor for descriptor map.
780 DescriptorMap(const Graph& _graph) : Map(_graph) {
786 /// \brief Add a new key to the map.
788 /// Add a new key to the map. It is called by the
789 /// \c AlterationNotifier.
790 virtual void add(const Item& item) {
792 Map::set(item, invMap.size());
793 invMap.push_back(item);
796 /// \brief Erase the key from the map.
798 /// Erase the key to the map. It is called by the
799 /// \c AlterationNotifier.
800 virtual void erase(const Item& item) {
801 Map::set(invMap.back(), Map::operator[](item));
802 invMap[Map::operator[](item)] = invMap.back();
807 /// \brief Build the unique map.
809 /// Build the unique map. It is called by the
810 /// \c AlterationNotifier.
811 virtual void build() {
814 const typename Map::Graph* graph = Map::getGraph();
815 for (graph->first(it); it != INVALID; graph->next(it)) {
816 Map::set(it, invMap.size());
817 invMap.push_back(it);
821 /// \brief Clear the keys from the map.
823 /// Clear the keys from the map. It is called by the
824 /// \c AlterationNotifier.
825 virtual void clear() {
832 /// \brief Swaps the position of the two items in the map.
834 /// Swaps the position of the two items in the map.
835 void swap(const Item& p, const Item& q) {
836 int pi = Map::operator[](p);
837 int qi = Map::operator[](q);
844 /// \brief Gives back the \e descriptor of the item.
846 /// Gives back the mutable and unique \e descriptor of the map.
847 int operator[](const Item& item) const {
848 return Map::operator[](item);
853 typedef std::vector<Item> Container;
857 /// \brief The inverse map type of DescriptorMap.
859 /// The inverse map type of DescriptorMap.
862 /// \brief Constructor of the InverseMap.
864 /// Constructor of the InverseMap.
865 InverseMap(const DescriptorMap& _inverted)
866 : inverted(_inverted) {}
869 /// The value type of the InverseMap.
870 typedef typename DescriptorMap::Key Value;
871 /// The key type of the InverseMap.
872 typedef typename DescriptorMap::Value Key;
874 /// \brief Subscript operator.
876 /// Subscript operator. It gives back the item
877 /// that the descriptor belongs to currently.
878 Value operator[](const Key& key) const {
879 return inverted.invMap[key];
882 /// \brief Size of the map.
884 /// Returns the size of the map.
886 return inverted.invMap.size();
890 const DescriptorMap& inverted;
893 /// \brief Gives back the inverse of the map.
895 /// Gives back the inverse of the map.
896 const InverseMap inverse() const {
897 return InverseMap(*this);
901 /// \brief Returns the source of the given edge.
903 /// The SourceMap gives back the source Node of the given edge.
904 /// \author Balazs Dezso
905 template <typename Graph>
909 typedef True NeedCopy;
911 typedef typename Graph::Node Value;
912 typedef typename Graph::Edge Key;
914 /// \brief Constructor
917 /// \param _graph The graph that the map belongs to.
918 SourceMap(const Graph& _graph) : graph(_graph) {}
920 /// \brief The subscript operator.
922 /// The subscript operator.
923 /// \param edge The edge
924 /// \return The source of the edge
925 Value operator[](const Key& edge) const {
926 return graph.source(edge);
933 /// \brief Returns a \ref SourceMap class
935 /// This function just returns an \ref SourceMap class.
936 /// \relates SourceMap
937 template <typename Graph>
938 inline SourceMap<Graph> sourceMap(const Graph& graph) {
939 return SourceMap<Graph>(graph);
942 /// \brief Returns the target of the given edge.
944 /// The TargetMap gives back the target Node of the given edge.
945 /// \author Balazs Dezso
946 template <typename Graph>
950 typedef True NeedCopy;
952 typedef typename Graph::Node Value;
953 typedef typename Graph::Edge Key;
955 /// \brief Constructor
958 /// \param _graph The graph that the map belongs to.
959 TargetMap(const Graph& _graph) : graph(_graph) {}
961 /// \brief The subscript operator.
963 /// The subscript operator.
964 /// \param e The edge
965 /// \return The target of the edge
966 Value operator[](const Key& e) const {
967 return graph.target(e);
974 /// \brief Returns a \ref TargetMap class
976 /// This function just returns a \ref TargetMap class.
977 /// \relates TargetMap
978 template <typename Graph>
979 inline TargetMap<Graph> targetMap(const Graph& graph) {
980 return TargetMap<Graph>(graph);
983 /// \brief Returns the "forward" directed edge view of an undirected edge.
985 /// Returns the "forward" directed edge view of an undirected edge.
986 /// \author Balazs Dezso
987 template <typename Graph>
991 typedef True NeedCopy;
993 typedef typename Graph::Edge Value;
994 typedef typename Graph::UndirEdge Key;
996 /// \brief Constructor
999 /// \param _graph The graph that the map belongs to.
1000 ForwardMap(const Graph& _graph) : graph(_graph) {}
1002 /// \brief The subscript operator.
1004 /// The subscript operator.
1005 /// \param key An undirected edge
1006 /// \return The "forward" directed edge view of undirected edge
1007 Value operator[](const Key& key) const {
1008 return graph.direct(key, true);
1015 /// \brief Returns a \ref ForwardMap class
1017 /// This function just returns an \ref ForwardMap class.
1018 /// \relates ForwardMap
1019 template <typename Graph>
1020 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1021 return ForwardMap<Graph>(graph);
1024 /// \brief Returns the "backward" directed edge view of an undirected edge.
1026 /// Returns the "backward" directed edge view of an undirected edge.
1027 /// \author Balazs Dezso
1028 template <typename Graph>
1031 typedef True NeedCopy;
1033 typedef typename Graph::Edge Value;
1034 typedef typename Graph::UndirEdge Key;
1036 /// \brief Constructor
1039 /// \param _graph The graph that the map belongs to.
1040 BackwardMap(const Graph& _graph) : graph(_graph) {}
1042 /// \brief The subscript operator.
1044 /// The subscript operator.
1045 /// \param key An undirected edge
1046 /// \return The "backward" directed edge view of undirected edge
1047 Value operator[](const Key& key) const {
1048 return graph.direct(key, false);
1055 /// \brief Returns a \ref BackwardMap class
1057 /// This function just returns a \ref BackwardMap class.
1058 /// \relates BackwardMap
1059 template <typename Graph>
1060 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1061 return BackwardMap<Graph>(graph);
1064 /// \brief Potential difference map
1066 /// If there is an potential map on the nodes then we
1067 /// can get an edge map as we get the substraction of the
1068 /// values of the target and source.
1069 template <typename Graph, typename NodeMap>
1070 class PotentialDifferenceMap {
1072 typedef typename Graph::Edge Key;
1073 typedef typename NodeMap::Value Value;
1075 /// \brief Constructor
1077 /// Contructor of the map
1078 PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1079 : graph(_graph), potential(_potential) {}
1081 /// \brief Const subscription operator
1083 /// Const subscription operator
1084 Value operator[](const Key& edge) const {
1085 return potential[graph.target(edge)] - potential[graph.source(edge)];
1090 const NodeMap& potential;
1093 /// \brief Just returns a PotentialDifferenceMap
1095 /// Just returns a PotentialDifferenceMap
1096 /// \relates PotentialDifferenceMap
1097 template <typename Graph, typename NodeMap>
1098 PotentialDifferenceMap<Graph, NodeMap>
1099 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1100 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1103 /// \brief Container for store values for each ordered pair of nodes
1105 /// Container for store values for each ordered pair of nodes.
1106 template <typename _Graph, typename _Value>
1108 : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
1110 typedef _Graph Graph;
1111 typedef typename Graph::Node Node;
1113 typedef _Value Value;
1115 /// \brief Creates a node matrix for the given graph
1117 /// Creates a node matrix for the given graph.
1118 NodeMatrixMap(const Graph& _graph)
1119 : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
1121 /// \brief Creates a node matrix for the given graph
1123 /// Creates a node matrix for the given graph and assigns each
1124 /// initial value to the given parameter.
1125 NodeMatrixMap(const Graph& _graph, const Value& _val)
1126 : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
1128 /// \brief Gives back the value assigned to the \c left - \c right
1131 /// Gives back the value assigned to the \c left - \c right ordered pair.
1132 const Value& operator()(const Node& left, const Node& right) const {
1133 return values[index(graph.id(left), graph.id(right))];
1136 /// \brief Gives back the value assigned to the \c left - \c right
1139 /// Gives back the value assigned to the \c left - \c right ordered pair.
1140 Value& operator()(const Node& left, const Node& right) {
1141 return values[index(graph.id(left), graph.id(right))];
1144 /// \brief Setter function for the matrix map.
1146 /// Setter function for the matrix map.
1147 void set(const Node& left, const Node& right, const Value& val) {
1148 values[index(graph.id(left), graph.id(right))] = val;
1151 /// \brief Map for the coloumn view of the matrix
1153 /// Map for the coloumn view of the matrix.
1154 class ColMap : public MapBase<Node, Value> {
1155 friend class NodeMatrixMap;
1157 ColMap(NodeMatrixMap& _matrix, Node _col)
1158 : matrix(_matrix), col(_col) {}
1161 /// \brief Subscription operator
1163 /// Subscription operator.
1164 Value& operator[](Node row) {
1165 return matrix(col, row);
1168 /// \brief Setter function
1170 /// Setter function.
1171 void set(Node row, const Value& val) {
1172 matrix.set(col, row, val);
1175 /// \brief Subscription operator
1177 /// Subscription operator.
1178 const Value& operator[](Node row) const {
1179 return matrix(col, row);
1183 NodeMatrixMap& matrix;
1187 /// \brief Map for the const coloumn view of the matrix
1189 /// Map for the const coloumn view of the matrix.
1190 class ConstColMap : public MapBase<Node, Value> {
1191 friend class NodeMatrixMap;
1193 ConstColMap(const NodeMatrixMap& _matrix, Node _col)
1194 : matrix(_matrix), col(_col) {}
1197 /// \brief Subscription operator
1199 /// Subscription operator.
1200 const Value& operator[](Node row) const {
1201 return matrix(col, row);
1205 const NodeMatrixMap& matrix;
1209 /// \brief Map for the row view of the matrix
1211 /// Map for the row view of the matrix.
1212 class RowMap : public MapBase<Node, Value> {
1214 friend class NodeMatrixMap;
1216 RowMap(NodeMatrixMap& _matrix, Node _row)
1217 : matrix(_matrix), row(_row) {}
1220 /// \brief Subscription operator
1222 /// Subscription operator.
1223 Value& operator[](Node col) {
1224 return matrix(col, row);
1227 /// \brief Setter function
1229 /// Setter function.
1230 void set(Node col, const Value& val) {
1231 matrix.set(col, row, val);
1234 /// \brief Subscription operator
1236 /// Subscription operator.
1237 const Value& operator[](Node col) const {
1238 return matrix(col, row);
1242 NodeMatrixMap& matrix;
1246 /// \brief Map for the const row view of the matrix
1248 /// Map for the row const view of the matrix.
1249 class ConstRowMap : public MapBase<Node, Value> {
1251 friend class NodeMatrixMap;
1253 ConstRowMap(const NodeMatrixMap& _matrix, Node _row)
1254 : matrix(_matrix), row(_row) {}
1257 /// \brief Subscription operator
1259 /// Subscription operator.
1260 const Value& operator[](Node col) const {
1261 return matrix(col, row);
1265 const NodeMatrixMap& matrix;
1269 /// \brief Gives back the column view for the given node
1271 /// Gives back the column view for the given node
1272 ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
1273 /// \brief Gives back the column view for the given node
1275 /// Gives back the column view for the given node
1276 ColMap operator[](Node col) { return ColMap(*this, col); }
1278 /// \brief Gives back the column view for the given node
1280 /// Gives back the column view for the given node
1281 ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
1282 /// \brief Gives back the column view for the given node
1284 /// Gives back the column view for the given node
1285 ColMap colMap(Node col) { return ColMap(*this, col); }
1287 /// \brief Gives back the row view for the given node
1289 /// Gives back the row view for the given node
1290 ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
1291 /// \brief Gives back the row view for the given node
1293 /// Gives back the row view for the given node
1294 RowMap rowMap(Node row) { return RowMap(*this, row); }
1298 static int index(int i, int j) {
1299 int m = i > j ? i : j;
1303 return m * m + m + j;
1307 static int size(int s) {
1311 void add(const Node& node) {
1312 if (size(graph.id(node) + 1) > values.size()) {
1313 values.resize(size(graph.id(node) + 1));
1317 void erase(const Node&) {}
1320 values.resize(size(graph.maxId(Node()) + 1));
1329 std::vector<Value> values;
1332 /// \brief Map of the node in-degrees.
1334 /// This map returns the in-degree of a node. Once it is constructed,
1335 /// the degrees are stored in a standard NodeMap, so each query is done
1336 /// in constant time. On the other hand, the values are updated automatically
1337 /// whenever the graph changes.
1339 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1340 /// alternative ways to mogify the graph. The correct behavior of InDegMap
1341 /// is not guarantied if these additional featureas are used. For example
1342 /// the funstions \ref ListGraph::changeSource() "changeSource()",
1343 /// \ref ListGraph::changeTarget() "changeTarget()" and
1344 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1345 /// of \ref ListGraph will \e not update the degree values correctly.
1349 template <typename _Graph>
1351 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1355 typedef _Graph Graph;
1357 typedef typename Graph::Node Key;
1361 class AutoNodeMap : public Graph::template NodeMap<int> {
1364 typedef typename Graph::template NodeMap<int> Parent;
1366 typedef typename Parent::Key Key;
1367 typedef typename Parent::Value Value;
1369 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1371 void add(const Key& key) {
1373 Parent::set(key, 0);
1379 /// \brief Constructor.
1381 /// Constructor for creating in-degree map.
1382 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1383 AlterationNotifier<typename _Graph::Edge>
1384 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1386 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1387 deg[it] = countInEdges(graph, it);
1391 virtual ~InDegMap() {
1392 AlterationNotifier<typename _Graph::Edge>::
1393 ObserverBase::detach();
1396 /// Gives back the in-degree of a Node.
1397 int operator[](const Key& key) const {
1403 typedef typename Graph::Edge Edge;
1405 virtual void add(const Edge& edge) {
1406 ++deg[graph.target(edge)];
1409 virtual void erase(const Edge& edge) {
1410 --deg[graph.target(edge)];
1414 virtual void build() {
1415 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1416 deg[it] = countInEdges(graph, it);
1420 virtual void clear() {
1421 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1427 const _Graph& graph;
1431 /// \brief Map of the node out-degrees.
1433 /// This map returns the out-degree of a node. Once it is constructed,
1434 /// the degrees are stored in a standard NodeMap, so each query is done
1435 /// in constant time. On the other hand, the values are updated automatically
1436 /// whenever the graph changes.
1438 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1439 /// alternative ways to mogify the graph. The correct behavior of OutDegMap
1440 /// is not guarantied if these additional featureas are used. For example
1441 /// the funstions \ref ListGraph::changeSource() "changeSource()",
1442 /// \ref ListGraph::changeTarget() "changeTarget()" and
1443 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1444 /// of \ref ListGraph will \e not update the degree values correctly.
1448 template <typename _Graph>
1450 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1454 typedef _Graph Graph;
1456 typedef typename Graph::Node Key;
1460 class AutoNodeMap : public Graph::template NodeMap<int> {
1463 typedef typename Graph::template NodeMap<int> Parent;
1465 typedef typename Parent::Key Key;
1466 typedef typename Parent::Value Value;
1468 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1470 void add(const Key& key) {
1472 Parent::set(key, 0);
1478 /// \brief Constructor.
1480 /// Constructor for creating out-degree map.
1481 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1482 AlterationNotifier<typename _Graph::Edge>
1483 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1485 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1486 deg[it] = countOutEdges(graph, it);
1490 virtual ~OutDegMap() {
1491 AlterationNotifier<typename _Graph::Edge>::
1492 ObserverBase::detach();
1495 /// Gives back the in-degree of a Node.
1496 int operator[](const Key& key) const {
1502 typedef typename Graph::Edge Edge;
1504 virtual void add(const Edge& edge) {
1505 ++deg[graph.source(edge)];
1508 virtual void erase(const Edge& edge) {
1509 --deg[graph.source(edge)];
1513 virtual void build() {
1514 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1515 deg[it] = countOutEdges(graph, it);
1519 virtual void clear() {
1520 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1526 const _Graph& graph;
1530 // Indicators for the tags
1532 template <typename Graph, typename Enable = void>
1533 struct NodeNumTagIndicator {
1534 static const bool value = false;
1537 template <typename Graph>
1538 struct NodeNumTagIndicator<
1540 typename enable_if<typename Graph::NodeNumTag, void>::type
1542 static const bool value = true;
1545 template <typename Graph, typename Enable = void>
1546 struct EdgeNumTagIndicator {
1547 static const bool value = false;
1550 template <typename Graph>
1551 struct EdgeNumTagIndicator<
1553 typename enable_if<typename Graph::EdgeNumTag, void>::type
1555 static const bool value = true;
1558 template <typename Graph, typename Enable = void>
1559 struct FindEdgeTagIndicator {
1560 static const bool value = false;
1563 template <typename Graph>
1564 struct FindEdgeTagIndicator<
1566 typename enable_if<typename Graph::FindEdgeTag, void>::type
1568 static const bool value = true;
1574 } //END OF NAMESPACE LEMON