removed the fit to window form the toolbar and the menu since its current implementation is broken
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
24 #include <lemon/invalid.h>
25 #include <lemon/utility.h>
26 #include <lemon/maps.h>
27 #include <lemon/bits/alteration_notifier.h>
31 ///\brief Graph utilities.
38 /// \addtogroup gutils
41 /// \brief Function to count the items in the graph.
43 /// This function counts the items (nodes, edges etc) in the graph.
44 /// The complexity of the function is O(n) because
45 /// it iterates on all of the items.
47 template <typename Graph, typename ItemIt>
48 inline int countItems(const Graph& g) {
50 for (ItemIt it(g); it != INVALID; ++it) {
58 template <typename Graph>
60 typename enable_if<typename Graph::NodeNumTag, int>::type
61 _countNodes(const Graph &g) {
65 template <typename Graph>
66 inline int _countNodes(Wrap<Graph> w) {
67 return countItems<Graph, typename Graph::NodeIt>(w.value);
70 /// \brief Function to count the nodes in the graph.
72 /// This function counts the nodes in the graph.
73 /// The complexity of the function is O(n) but for some
74 /// graph structures it is specialized to run in O(1).
76 /// \todo refer how to specialize it
78 template <typename Graph>
79 inline int countNodes(const Graph& g) {
80 return _countNodes<Graph>(g);
85 template <typename Graph>
87 typename enable_if<typename Graph::EdgeNumTag, int>::type
88 _countEdges(const Graph &g) {
92 template <typename Graph>
93 inline int _countEdges(Wrap<Graph> w) {
94 return countItems<Graph, typename Graph::EdgeIt>(w.value);
97 /// \brief Function to count the edges in the graph.
99 /// This function counts the edges in the graph.
100 /// The complexity of the function is O(e) but for some
101 /// graph structures it is specialized to run in O(1).
103 template <typename Graph>
104 inline int countEdges(const Graph& g) {
105 return _countEdges<Graph>(g);
108 // Undirected edge counting:
110 template <typename Graph>
112 typename enable_if<typename Graph::EdgeNumTag, int>::type
113 _countUndirEdges(const Graph &g) {
114 return g.undirEdgeNum();
117 template <typename Graph>
118 inline int _countUndirEdges(Wrap<Graph> w) {
119 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
122 /// \brief Function to count the undirected edges in the graph.
124 /// This function counts the undirected edges in the graph.
125 /// The complexity of the function is O(e) but for some
126 /// graph structures it is specialized to run in O(1).
128 template <typename Graph>
129 inline int countUndirEdges(const Graph& g) {
130 return _countUndirEdges<Graph>(g);
135 template <typename Graph, typename DegIt>
136 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
138 for (DegIt it(_g, _n); it != INVALID; ++it) {
144 /// \brief Function to count the number of the out-edges from node \c n.
146 /// This function counts the number of the out-edges from node \c n
148 template <typename Graph>
149 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
150 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
153 /// \brief Function to count the number of the in-edges to node \c n.
155 /// This function counts the number of the in-edges to node \c n
157 template <typename Graph>
158 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
159 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
163 template <typename Graph>
165 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
166 _findEdge(const Graph &g,
167 typename Graph::Node u, typename Graph::Node v,
168 typename Graph::Edge prev = INVALID) {
169 return g.findEdge(u, v, prev);
172 template <typename Graph>
173 inline typename Graph::Edge
174 _findEdge(Wrap<Graph> w,
175 typename Graph::Node u,
176 typename Graph::Node v,
177 typename Graph::Edge prev = INVALID) {
178 const Graph& g = w.value;
179 if (prev == INVALID) {
180 typename Graph::OutEdgeIt e(g, u);
181 while (e != INVALID && g.target(e) != v) ++e;
184 typename Graph::OutEdgeIt e(g, prev); ++e;
185 while (e != INVALID && g.target(e) != v) ++e;
190 /// \brief Finds an edge between two nodes of a graph.
192 /// Finds an edge from node \c u to node \c v in graph \c g.
194 /// If \c prev is \ref INVALID (this is the default value), then
195 /// it finds the first edge from \c u to \c v. Otherwise it looks for
196 /// the next edge from \c u to \c v after \c prev.
197 /// \return The found edge or \ref INVALID if there is no such an edge.
199 /// Thus you can iterate through each edge from \c u to \c v as it follows.
201 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
205 // /// \todo We may want to use the "GraphBase"
206 // /// interface here...
207 // /// It would not work with the undirected graphs.
208 template <typename Graph>
209 inline typename Graph::Edge findEdge(const Graph &g,
210 typename Graph::Node u,
211 typename Graph::Node v,
212 typename Graph::Edge prev = INVALID) {
213 return _findEdge<Graph>(g, u, v, prev);
216 /// \brief Iterator for iterating on edges connected the same nodes.
218 /// Iterator for iterating on edges connected the same nodes. It is
219 /// higher level interface for the findEdge() function. You can
220 /// use it the following way:
222 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
227 /// \author Balazs Dezso
228 template <typename _Graph>
229 class ConEdgeIt : public _Graph::Edge {
232 typedef _Graph Graph;
233 typedef typename Graph::Edge Parent;
235 typedef typename Graph::Edge Edge;
236 typedef typename Graph::Node Node;
238 /// \brief Constructor.
240 /// Construct a new ConEdgeIt iterating on the edges which
241 /// connects the \c u and \c v node.
242 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
243 Parent::operator=(findEdge(graph, u, v));
246 /// \brief Constructor.
248 /// Construct a new ConEdgeIt which continues the iterating from
250 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
252 /// \brief Increment operator.
254 /// It increments the iterator and gives back the next edge.
255 ConEdgeIt& operator++() {
256 Parent::operator=(findEdge(graph, graph.source(*this),
257 graph.target(*this), *this));
264 /// \brief Copy a map.
266 /// This function copies the \c source map to the \c target map. It uses the
267 /// given iterator to iterate on the data structure and it uses the \c ref
268 /// mapping to convert the source's keys to the target's keys.
269 template <typename Target, typename Source,
270 typename ItemIt, typename Ref>
271 void copyMap(Target& target, const Source& source,
272 ItemIt it, const Ref& ref) {
273 for (; it != INVALID; ++it) {
274 target[ref[it]] = source[it];
278 /// \brief Copy the source map to the target map.
280 /// Copy the \c source map to the \c target map. It uses the given iterator
281 /// to iterate on the data structure.
282 template <typename Target, typename Source,
284 void copyMap(Target& target, const Source& source, ItemIt it) {
285 for (; it != INVALID; ++it) {
286 target[it] = source[it];
291 /// \brief Class to copy a graph.
293 /// Class to copy a graph to an other graph (duplicate a graph). The
294 /// simplest way of using it is through the \c copyGraph() function.
295 template <typename Target, typename Source>
298 typedef typename Source::Node Node;
299 typedef typename Source::NodeIt NodeIt;
300 typedef typename Source::Edge Edge;
301 typedef typename Source::EdgeIt EdgeIt;
303 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
304 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
306 /// \brief Constructor for the GraphCopy.
308 /// It copies the content of the \c _source graph into the
309 /// \c _target graph. It creates also two references, one beetween
310 /// the two nodeset and one beetween the two edgesets.
311 GraphCopy(Target& _target, const Source& _source)
312 : source(_source), target(_target),
313 nodeRefMap(_source), edgeRefMap(_source) {
314 for (NodeIt it(source); it != INVALID; ++it) {
315 nodeRefMap[it] = target.addNode();
317 for (EdgeIt it(source); it != INVALID; ++it) {
318 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
319 nodeRefMap[source.target(it)]);
323 /// \brief Copies the node references into the given map.
325 /// Copies the node references into the given map.
326 template <typename NodeRef>
327 const GraphCopy& nodeRef(NodeRef& map) const {
328 for (NodeIt it(source); it != INVALID; ++it) {
329 map.set(it, nodeRefMap[it]);
334 /// \brief Reverse and copies the node references into the given map.
336 /// Reverse and copies the node references into the given map.
337 template <typename NodeRef>
338 const GraphCopy& nodeCrossRef(NodeRef& map) const {
339 for (NodeIt it(source); it != INVALID; ++it) {
340 map.set(nodeRefMap[it], it);
345 /// \brief Copies the edge references into the given map.
347 /// Copies the edge references into the given map.
348 template <typename EdgeRef>
349 const GraphCopy& edgeRef(EdgeRef& map) const {
350 for (EdgeIt it(source); it != INVALID; ++it) {
351 map.set(it, edgeRefMap[it]);
356 /// \brief Reverse and copies the edge references into the given map.
358 /// Reverse and copies the edge references into the given map.
359 template <typename EdgeRef>
360 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
361 for (EdgeIt it(source); it != INVALID; ++it) {
362 map.set(edgeRefMap[it], it);
367 /// \brief Make copy of the given map.
369 /// Makes copy of the given map for the newly created graph.
370 /// The new map's key type is the target graph's node type,
371 /// and the copied map's key type is the source graph's node
373 template <typename TargetMap, typename SourceMap>
374 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
375 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
379 /// \brief Make copy of the given map.
381 /// Makes copy of the given map for the newly created graph.
382 /// The new map's key type is the target graph's edge type,
383 /// and the copied map's key type is the source graph's edge
385 template <typename TargetMap, typename SourceMap>
386 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
387 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
391 /// \brief Gives back the stored node references.
393 /// Gives back the stored node references.
394 const NodeRefMap& nodeRef() const {
398 /// \brief Gives back the stored edge references.
400 /// Gives back the stored edge references.
401 const EdgeRefMap& edgeRef() const {
407 const Source& source;
410 NodeRefMap nodeRefMap;
411 EdgeRefMap edgeRefMap;
414 /// \brief Copy a graph to an other graph.
416 /// Copy a graph to an other graph.
417 /// The usage of the function:
420 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
423 /// After the copy the \c nr map will contain the mapping from the
424 /// source graph's nodes to the target graph's nodes and the \c ecr will
425 /// contain the mapping from the target graph's edges to the source's
427 template <typename Target, typename Source>
428 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
429 return GraphCopy<Target, Source>(target, source);
432 template <typename _Graph, typename _Item>
433 class ItemSetTraits {};
435 template <typename _Graph>
436 class ItemSetTraits<_Graph, typename _Graph::Node> {
439 typedef _Graph Graph;
441 typedef typename Graph::Node Item;
442 typedef typename Graph::NodeIt ItemIt;
444 template <typename _Value>
445 class Map : public Graph::template NodeMap<_Value> {
447 typedef typename Graph::template NodeMap<_Value> Parent;
448 typedef typename Parent::Value Value;
450 Map(const Graph& _graph) : Parent(_graph) {}
451 Map(const Graph& _graph, const Value& _value)
452 : Parent(_graph, _value) {}
457 template <typename _Graph>
458 class ItemSetTraits<_Graph, typename _Graph::Edge> {
461 typedef _Graph Graph;
463 typedef typename Graph::Edge Item;
464 typedef typename Graph::EdgeIt ItemIt;
466 template <typename _Value>
467 class Map : public Graph::template EdgeMap<_Value> {
469 typedef typename Graph::template EdgeMap<_Value> Parent;
470 typedef typename Parent::Value Value;
472 Map(const Graph& _graph) : Parent(_graph) {}
473 Map(const Graph& _graph, const Value& _value)
474 : Parent(_graph, _value) {}
479 template <typename _Graph>
480 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
483 typedef _Graph Graph;
485 typedef typename Graph::UndirEdge Item;
486 typedef typename Graph::UndirEdgeIt ItemIt;
488 template <typename _Value>
489 class Map : public Graph::template UndirEdgeMap<_Value> {
491 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
492 typedef typename Parent::Value Value;
494 Map(const Graph& _graph) : Parent(_graph) {}
495 Map(const Graph& _graph, const Value& _value)
496 : Parent(_graph, _value) {}
503 /// \addtogroup graph_maps
506 template <typename Map, typename Enable = void>
507 struct ReferenceMapTraits {
508 typedef typename Map::Value Value;
509 typedef typename Map::Value& Reference;
510 typedef const typename Map::Value& ConstReference;
511 typedef typename Map::Value* Pointer;
512 typedef const typename Map::Value* ConstPointer;
515 template <typename Map>
516 struct ReferenceMapTraits<
518 typename enable_if<typename Map::FullTypeTag, void>::type
520 typedef typename Map::Value Value;
521 typedef typename Map::Reference Reference;
522 typedef typename Map::ConstReference ConstReference;
523 typedef typename Map::Pointer Pointer;
524 typedef typename Map::ConstPointer ConstPointer;
527 /// Provides an immutable and unique id for each item in the graph.
529 /// The IdMap class provides a unique and immutable id for each item of the
530 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
531 /// different items (nodes) get different ids <li>\b immutable: the id of an
532 /// item (node) does not change (even if you delete other nodes). </ul>
533 /// Through this map you get access (i.e. can read) the inner id values of
534 /// the items stored in the graph. This map can be inverted with its member
535 /// class \c InverseMap.
537 template <typename _Graph, typename _Item>
540 typedef _Graph Graph;
545 typedef True NeedCopy;
547 /// \brief Constructor.
549 /// Constructor for creating id map.
550 IdMap(const Graph& _graph) : graph(&_graph) {}
552 /// \brief Gives back the \e id of the item.
554 /// Gives back the immutable and unique \e id of the map.
555 int operator[](const Item& item) const { return graph->id(item);}
563 /// \brief The class represents the inverse of its owner (IdMap).
565 /// The class represents the inverse of its owner (IdMap).
570 typedef True NeedCopy;
572 /// \brief Constructor.
574 /// Constructor for creating an id-to-item map.
575 InverseMap(const Graph& _graph) : graph(&_graph) {}
577 /// \brief Constructor.
579 /// Constructor for creating an id-to-item map.
580 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
582 /// \brief Gives back the given item from its id.
584 /// Gives back the given item from its id.
586 Item operator[](int id) const { return graph->fromId(id, Item());}
591 /// \brief Gives back the inverse of the map.
593 /// Gives back the inverse of the IdMap.
594 InverseMap inverse() const { return InverseMap(*graph);}
599 /// \brief General invertable graph-map type.
601 /// This type provides simple invertable graph-maps.
602 /// The InvertableMap wraps an arbitrary ReadWriteMap
603 /// and if a key is set to a new value then store it
604 /// in the inverse map.
605 /// \param _Graph The graph type.
606 /// \param _Map The map to extend with invertable functionality.
612 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
614 class InvertableMap : protected _Map {
619 typedef _Graph Graph;
621 /// The key type of InvertableMap (Node, Edge, UndirEdge).
622 typedef typename _Map::Key Key;
623 /// The value type of the InvertableMap.
624 typedef typename _Map::Value Value;
626 /// \brief Constructor.
628 /// Construct a new InvertableMap for the graph.
630 InvertableMap(const Graph& graph) : Map(graph) {}
632 /// \brief The setter function of the map.
634 /// Sets the mapped value.
635 void set(const Key& key, const Value& val) {
636 Value oldval = Map::operator[](key);
637 typename Container::iterator it = invMap.find(oldval);
638 if (it != invMap.end() && it->second == key) {
641 invMap.insert(make_pair(val, key));
645 /// \brief The getter function of the map.
647 /// It gives back the value associated with the key.
648 const Value operator[](const Key& key) const {
649 return Map::operator[](key);
654 /// \brief Add a new key to the map.
656 /// Add a new key to the map. It is called by the
657 /// \c AlterationNotifier.
658 virtual void add(const Key& key) {
662 /// \brief Erase the key from the map.
664 /// Erase the key to the map. It is called by the
665 /// \c AlterationNotifier.
666 virtual void erase(const Key& key) {
667 Value val = Map::operator[](key);
668 typename Container::iterator it = invMap.find(val);
669 if (it != invMap.end() && it->second == key) {
675 /// \brief Clear the keys from the map and inverse map.
677 /// Clear the keys from the map and inverse map. It is called by the
678 /// \c AlterationNotifier.
679 virtual void clear() {
686 typedef std::map<Value, Key> Container;
691 /// \brief The inverse map type.
693 /// The inverse of this map. The subscript operator of the map
694 /// gives back always the item what was last assigned to the value.
697 /// \brief Constructor of the InverseMap.
699 /// Constructor of the InverseMap.
700 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
702 /// The value type of the InverseMap.
703 typedef typename InvertableMap::Key Value;
704 /// The key type of the InverseMap.
705 typedef typename InvertableMap::Value Key;
707 /// \brief Subscript operator.
709 /// Subscript operator. It gives back always the item
710 /// what was last assigned to the value.
711 Value operator[](const Key& key) const {
712 typename Container::const_iterator it = inverted.invMap.find(key);
717 const InvertableMap& inverted;
720 /// \brief It gives back the just readeable inverse map.
722 /// It gives back the just readeable inverse map.
723 InverseMap inverse() const {
724 return InverseMap(*this);
731 /// \brief Provides a mutable, continuous and unique descriptor for each
732 /// item in the graph.
734 /// The DescriptorMap class provides a unique and continuous (but mutable)
735 /// descriptor (id) for each item of the same type (e.g. node) in the
736 /// graph. This id is <ul><li>\b unique: different items (nodes) get
737 /// different ids <li>\b continuous: the range of the ids is the set of
738 /// integers between 0 and \c n-1, where \c n is the number of the items of
739 /// this type (e.g. nodes) (so the id of a node can change if you delete an
740 /// other node, i.e. this id is mutable). </ul> This map can be inverted
741 /// with its member class \c InverseMap.
743 /// \param _Graph The graph class the \c DescriptorMap belongs to.
744 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
746 /// \param _Map A ReadWriteMap mapping from the item type to integer.
751 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
753 class DescriptorMap : protected _Map {
759 /// The graph class of DescriptorMap.
760 typedef _Graph Graph;
762 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
763 typedef typename _Map::Key Key;
764 /// The value type of DescriptorMap.
765 typedef typename _Map::Value Value;
767 /// \brief Constructor.
769 /// Constructor for descriptor map.
770 DescriptorMap(const Graph& _graph) : Map(_graph) {
776 /// \brief Add a new key to the map.
778 /// Add a new key to the map. It is called by the
779 /// \c AlterationNotifier.
780 virtual void add(const Item& item) {
782 Map::set(item, invMap.size());
783 invMap.push_back(item);
786 /// \brief Erase the key from the map.
788 /// Erase the key to the map. It is called by the
789 /// \c AlterationNotifier.
790 virtual void erase(const Item& item) {
791 Map::set(invMap.back(), Map::operator[](item));
792 invMap[Map::operator[](item)] = invMap.back();
797 /// \brief Build the unique map.
799 /// Build the unique map. It is called by the
800 /// \c AlterationNotifier.
801 virtual void build() {
804 const typename Map::Graph* graph = Map::getGraph();
805 for (graph->first(it); it != INVALID; graph->next(it)) {
806 Map::set(it, invMap.size());
807 invMap.push_back(it);
811 /// \brief Clear the keys from the map.
813 /// Clear the keys from the map. It is called by the
814 /// \c AlterationNotifier.
815 virtual void clear() {
822 /// \brief Swaps the position of the two items in the map.
824 /// Swaps the position of the two items in the map.
825 void swap(const Item& p, const Item& q) {
826 int pi = Map::operator[](p);
827 int qi = Map::operator[](q);
834 /// \brief Gives back the \e descriptor of the item.
836 /// Gives back the mutable and unique \e descriptor of the map.
837 int operator[](const Item& item) const {
838 return Map::operator[](item);
843 typedef std::vector<Item> Container;
847 /// \brief The inverse map type of DescriptorMap.
849 /// The inverse map type of DescriptorMap.
852 /// \brief Constructor of the InverseMap.
854 /// Constructor of the InverseMap.
855 InverseMap(const DescriptorMap& _inverted)
856 : inverted(_inverted) {}
859 /// The value type of the InverseMap.
860 typedef typename DescriptorMap::Key Value;
861 /// The key type of the InverseMap.
862 typedef typename DescriptorMap::Value Key;
864 /// \brief Subscript operator.
866 /// Subscript operator. It gives back the item
867 /// that the descriptor belongs to currently.
868 Value operator[](const Key& key) const {
869 return inverted.invMap[key];
872 /// \brief Size of the map.
874 /// Returns the size of the map.
876 return inverted.invMap.size();
880 const DescriptorMap& inverted;
883 /// \brief Gives back the inverse of the map.
885 /// Gives back the inverse of the map.
886 const InverseMap inverse() const {
887 return InverseMap(*this);
891 /// \brief Returns the source of the given edge.
893 /// The SourceMap gives back the source Node of the given edge.
894 /// \author Balazs Dezso
895 template <typename Graph>
899 typedef True NeedCopy;
901 typedef typename Graph::Node Value;
902 typedef typename Graph::Edge Key;
904 /// \brief Constructor
907 /// \param _graph The graph that the map belongs to.
908 SourceMap(const Graph& _graph) : graph(_graph) {}
910 /// \brief The subscript operator.
912 /// The subscript operator.
913 /// \param edge The edge
914 /// \return The source of the edge
915 Value operator[](const Key& edge) {
916 return graph.source(edge);
923 /// \brief Returns a \ref SourceMap class
925 /// This function just returns an \ref SourceMap class.
926 /// \relates SourceMap
927 template <typename Graph>
928 inline SourceMap<Graph> sourceMap(const Graph& graph) {
929 return SourceMap<Graph>(graph);
932 /// \brief Returns the target of the given edge.
934 /// The TargetMap gives back the target Node of the given edge.
935 /// \author Balazs Dezso
936 template <typename Graph>
940 typedef True NeedCopy;
942 typedef typename Graph::Node Value;
943 typedef typename Graph::Edge Key;
945 /// \brief Constructor
948 /// \param _graph The graph that the map belongs to.
949 TargetMap(const Graph& _graph) : graph(_graph) {}
951 /// \brief The subscript operator.
953 /// The subscript operator.
954 /// \param e The edge
955 /// \return The target of the edge
956 Value operator[](const Key& e) {
957 return graph.target(e);
964 /// \brief Returns a \ref TargetMap class
966 /// This function just returns a \ref TargetMap class.
967 /// \relates TargetMap
968 template <typename Graph>
969 inline TargetMap<Graph> targetMap(const Graph& graph) {
970 return TargetMap<Graph>(graph);
973 /// \brief Returns the "forward" directed edge view of an undirected edge.
975 /// Returns the "forward" directed edge view of an undirected edge.
976 /// \author Balazs Dezso
977 template <typename Graph>
981 typedef True NeedCopy;
983 typedef typename Graph::Edge Value;
984 typedef typename Graph::UndirEdge Key;
986 /// \brief Constructor
989 /// \param _graph The graph that the map belongs to.
990 ForwardMap(const Graph& _graph) : graph(_graph) {}
992 /// \brief The subscript operator.
994 /// The subscript operator.
995 /// \param key An undirected edge
996 /// \return The "forward" directed edge view of undirected edge
997 Value operator[](const Key& key) const {
998 return graph.direct(key, true);
1005 /// \brief Returns a \ref ForwardMap class
1007 /// This function just returns an \ref ForwardMap class.
1008 /// \relates ForwardMap
1009 template <typename Graph>
1010 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1011 return ForwardMap<Graph>(graph);
1014 /// \brief Returns the "backward" directed edge view of an undirected edge.
1016 /// Returns the "backward" directed edge view of an undirected edge.
1017 /// \author Balazs Dezso
1018 template <typename Graph>
1021 typedef True NeedCopy;
1023 typedef typename Graph::Edge Value;
1024 typedef typename Graph::UndirEdge Key;
1026 /// \brief Constructor
1029 /// \param _graph The graph that the map belongs to.
1030 BackwardMap(const Graph& _graph) : graph(_graph) {}
1032 /// \brief The subscript operator.
1034 /// The subscript operator.
1035 /// \param key An undirected edge
1036 /// \return The "backward" directed edge view of undirected edge
1037 Value operator[](const Key& key) const {
1038 return graph.direct(key, false);
1045 /// \brief Returns a \ref BackwardMap class
1047 /// This function just returns a \ref BackwardMap class.
1048 /// \relates BackwardMap
1049 template <typename Graph>
1050 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1051 return BackwardMap<Graph>(graph);
1054 template <typename _Graph>
1058 typedef _Graph Graph;
1062 typedef typename Graph::template NodeMap<int> IntNodeMap;
1066 /// \brief Map of the node in-degrees.
1068 /// This map returns the in-degree of a node. Once it is constructed,
1069 /// the degrees are stored in a standard NodeMap, so each query is done
1070 /// in constant time. On the other hand, the values are updated automatically
1071 /// whenever the graph changes.
1075 template <typename _Graph>
1077 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1081 typedef _Graph Graph;
1083 typedef typename Graph::Node Key;
1087 class AutoNodeMap : public Graph::template NodeMap<int> {
1090 typedef typename Graph::template NodeMap<int> Parent;
1092 typedef typename Parent::Key Key;
1093 typedef typename Parent::Value Value;
1095 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1097 void add(const Key& key) {
1099 Parent::set(key, 0);
1105 /// \brief Constructor.
1107 /// Constructor for creating in-degree map.
1108 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1109 AlterationNotifier<typename _Graph::Edge>
1110 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1112 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1113 deg[it] = countInEdges(graph, it);
1117 virtual ~InDegMap() {
1118 AlterationNotifier<typename _Graph::Edge>::
1119 ObserverBase::detach();
1122 /// Gives back the in-degree of a Node.
1123 int operator[](const Key& key) const {
1129 typedef typename Graph::Edge Edge;
1131 virtual void add(const Edge& edge) {
1132 ++deg[graph.target(edge)];
1135 virtual void erase(const Edge& edge) {
1136 --deg[graph.target(edge)];
1140 virtual void build() {
1141 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1142 deg[it] = countInEdges(graph, it);
1146 virtual void clear() {
1147 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1153 const _Graph& graph;
1158 /// \brief Map of the node out-degrees.
1160 /// This map returns the out-degree of a node. Once it is constructed,
1161 /// the degrees are stored in a standard NodeMap, so each query is done
1162 /// in constant time. On the other hand, the values are updated automatically
1163 /// whenever the graph changes.
1167 template <typename _Graph>
1169 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1173 typedef _Graph Graph;
1175 typedef typename Graph::Node Key;
1179 class AutoNodeMap : public Graph::template NodeMap<int> {
1182 typedef typename Graph::template NodeMap<int> Parent;
1184 typedef typename Parent::Key Key;
1185 typedef typename Parent::Value Value;
1187 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1189 void add(const Key& key) {
1191 Parent::set(key, 0);
1197 /// \brief Constructor.
1199 /// Constructor for creating out-degree map.
1200 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1201 AlterationNotifier<typename _Graph::Edge>
1202 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1204 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1205 deg[it] = countOutEdges(graph, it);
1209 virtual ~OutDegMap() {
1210 AlterationNotifier<typename _Graph::Edge>::
1211 ObserverBase::detach();
1214 /// Gives back the in-degree of a Node.
1215 int operator[](const Key& key) const {
1221 typedef typename Graph::Edge Edge;
1223 virtual void add(const Edge& edge) {
1224 ++deg[graph.source(edge)];
1227 virtual void erase(const Edge& edge) {
1228 --deg[graph.source(edge)];
1232 virtual void build() {
1233 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1234 deg[it] = countOutEdges(graph, it);
1238 virtual void clear() {
1239 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1245 const _Graph& graph;
1251 } //END OF NAMESPACE LEMON