Hmmm...
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.
34 ///revise the documentation.
40 /// \addtogroup gutils
43 /// \brief Function to count the items in the graph.
45 /// This function counts the items in the graph.
46 /// The complexity of the function is O(n) because
47 /// it iterates on all of the items.
49 template <typename Graph, typename ItemIt>
50 inline int countItems(const Graph& g) {
52 for (ItemIt it(g); it != INVALID; ++it) {
60 template <typename Graph>
62 typename enable_if<typename Graph::NodeNumTag, int>::type
63 _countNodes(const Graph &g) {
67 template <typename Graph>
68 inline int _countNodes(Wrap<Graph> w) {
69 return countItems<Graph, typename Graph::NodeIt>(w.value);
72 /// \brief Function to count the nodes in the graph.
74 /// This function counts the nodes in the graph.
75 /// The complexity of the function is O(n) but for some
76 /// graph structure it is specialized to run in O(1).
78 /// \todo refer how to specialize it
80 template <typename Graph>
81 inline int countNodes(const Graph& g) {
82 return _countNodes<Graph>(g);
87 template <typename Graph>
89 typename enable_if<typename Graph::EdgeNumTag, int>::type
90 _countEdges(const Graph &g) {
94 template <typename Graph>
95 inline int _countEdges(Wrap<Graph> w) {
96 return countItems<Graph, typename Graph::EdgeIt>(w.value);
99 /// \brief Function to count the edges in the graph.
101 /// This function counts the edges in the graph.
102 /// The complexity of the function is O(e) but for some
103 /// graph structure it is specialized to run in O(1).
105 template <typename Graph>
106 inline int countEdges(const Graph& g) {
107 return _countEdges<Graph>(g);
110 // Undirected edge counting:
112 template <typename Graph>
114 typename enable_if<typename Graph::EdgeNumTag, int>::type
115 _countUndirEdges(const Graph &g) {
116 return g.undirEdgeNum();
119 template <typename Graph>
120 inline int _countUndirEdges(Wrap<Graph> w) {
121 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
124 /// \brief Function to count the edges in the graph.
126 /// This function counts the edges in the graph.
127 /// The complexity of the function is O(e) but for some
128 /// graph structure it is specialized to run in O(1).
130 template <typename Graph>
131 inline int countUndirEdges(const Graph& g) {
132 return _countUndirEdges<Graph>(g);
137 template <typename Graph, typename DegIt>
138 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
140 for (DegIt it(_g, _n); it != INVALID; ++it) {
146 /// Finds an edge between two nodes of a graph.
148 /// Finds an edge from node \c u to node \c v in graph \c g.
150 /// If \c prev is \ref INVALID (this is the default value), then
151 /// it finds the first edge from \c u to \c v. Otherwise it looks for
152 /// the next edge from \c u to \c v after \c prev.
153 /// \return The found edge or \ref INVALID if there is no such an edge.
155 /// Thus you can iterate through each edge from \c u to \c v as it follows.
157 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
161 /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
162 /// interface here...
163 /// \bug Untested ...
164 template <typename Graph>
165 typename Graph::Edge findEdge(const Graph &g,
166 typename Graph::Node u, typename Graph::Node v,
167 typename Graph::Edge prev = INVALID)
169 typename Graph::OutEdgeIt e(g,prev);
170 // if(prev==INVALID) g.first(e,u);
171 if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
173 while(e!=INVALID && g.target(e)!=v) ++e;
179 ///\todo Please document.
181 template <typename Graph>
182 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
183 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
188 ///\todo Please document.
190 template <typename Graph>
191 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
192 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
198 typename DestinationGraph,
199 typename SourceGraph,
200 typename NodeBijection>
201 void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
202 NodeBijection& _nb) {
203 for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
204 _nb[it] = _d.addNode();
209 typename DestinationGraph,
210 typename SourceGraph,
211 typename NodeBijection,
212 typename EdgeBijection>
213 void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
214 const NodeBijection& _nb, EdgeBijection& _eb) {
215 for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
216 _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
221 typename DestinationGraph,
222 typename SourceGraph,
223 typename NodeBijection,
224 typename EdgeBijection>
225 void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
226 NodeBijection& _nb, EdgeBijection& _eb) {
227 nodeCopy(_d, _s, _nb);
228 edgeCopy(_d, _s, _nb, _eb);
232 typename _DestinationGraph,
233 typename _SourceGraph,
234 typename _NodeBijection
235 =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
236 typename _EdgeBijection
237 = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
242 typedef _DestinationGraph DestinationGraph;
243 typedef _SourceGraph SourceGraph;
245 typedef _NodeBijection NodeBijection;
246 typedef _EdgeBijection EdgeBijection;
250 NodeBijection node_bijection;
251 EdgeBijection edge_bijection;
255 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
256 copyGraph(_d, _s, node_bijection, edge_bijection);
259 const NodeBijection& getNodeBijection() const {
260 return node_bijection;
263 const EdgeBijection& getEdgeBijection() const {
264 return edge_bijection;
270 template <typename _Graph, typename _Item>
271 class ItemSetTraits {};
273 template <typename _Graph>
274 class ItemSetTraits<_Graph, typename _Graph::Node> {
277 typedef _Graph Graph;
279 typedef typename Graph::Node Item;
280 typedef typename Graph::NodeIt ItemIt;
282 template <typename _Value>
283 class Map : public Graph::template NodeMap<_Value> {
285 typedef typename Graph::template NodeMap<_Value> Parent;
286 typedef typename Parent::Value Value;
288 Map(const Graph& _graph) : Parent(_graph) {}
289 Map(const Graph& _graph, const Value& _value)
290 : Parent(_graph, _value) {}
295 template <typename _Graph>
296 class ItemSetTraits<_Graph, typename _Graph::Edge> {
299 typedef _Graph Graph;
301 typedef typename Graph::Edge Item;
302 typedef typename Graph::EdgeIt ItemIt;
304 template <typename _Value>
305 class Map : public Graph::template EdgeMap<_Value> {
307 typedef typename Graph::template EdgeMap<_Value> Parent;
308 typedef typename Parent::Value Value;
310 Map(const Graph& _graph) : Parent(_graph) {}
311 Map(const Graph& _graph, const Value& _value)
312 : Parent(_graph, _value) {}
317 template <typename _Graph>
318 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
321 typedef _Graph Graph;
323 typedef typename Graph::UndirEdge Item;
324 typedef typename Graph::UndirEdgeIt ItemIt;
326 template <typename _Value>
327 class Map : public Graph::template UndirEdgeMap<_Value> {
329 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
330 typedef typename Parent::Value Value;
332 Map(const Graph& _graph) : Parent(_graph) {}
333 Map(const Graph& _graph, const Value& _value)
334 : Parent(_graph, _value) {}
341 /// \addtogroup graph_maps
344 template <typename Map, typename Enable = void>
345 struct ReferenceMapTraits {
346 typedef typename Map::Value Value;
347 typedef typename Map::Value& Reference;
348 typedef const typename Map::Value& ConstReference;
349 typedef typename Map::Value* Pointer;
350 typedef const typename Map::Value* ConstPointer;
353 template <typename Map>
354 struct ReferenceMapTraits<
356 typename enable_if<typename Map::FullTypeTag, void>::type
358 typedef typename Map::Value Value;
359 typedef typename Map::Reference Reference;
360 typedef typename Map::ConstReference ConstReference;
361 typedef typename Map::Pointer Pointer;
362 typedef typename Map::ConstPointer ConstPointer;
365 /// Provides an immutable and unique id for each item in the graph.
367 /// The IdMap class provides an unique and immutable mapping for each item
370 template <typename _Graph, typename _Item>
373 typedef _Graph Graph;
378 typedef True NeedCopy;
380 /// \brief Constructor.
382 /// Constructor for creating id map.
383 IdMap(const Graph& _graph) : graph(&_graph) {}
385 /// \brief Gives back the \e id of the item.
387 /// Gives back the immutable and unique \e id of the map.
388 int operator[](const Item& item) const { return graph->id(item);}
396 /// \brief The class represents the inverse of the map.
398 /// The class represents the inverse of the map.
403 typedef True NeedCopy;
405 /// \brief Constructor.
407 /// Constructor for creating an id-to-item map.
408 InverseMap(const Graph& _graph) : graph(&_graph) {}
410 /// \brief Constructor.
412 /// Constructor for creating an id-to-item map.
413 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
415 /// \brief Gives back the given item from its id.
417 /// Gives back the given item from its id.
419 Item operator[](int id) const { return graph->fromId(id, Item());}
424 /// \brief Gives back the inverse of the map.
426 /// Gives back the inverse of the map.
427 InverseMap inverse() const { return InverseMap(*graph);}
432 /// \brief General inversable graph-map type.
434 /// This type provides simple inversable map functions.
435 /// The InversableMap wraps an arbitrary ReadWriteMap
436 /// and if a key is setted to a new value then store it
437 /// in the inverse map.
438 /// \param _Graph The graph type.
439 /// \param _Map The map to extend with inversable functionality.
445 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
447 class InvertableMap : protected _Map {
452 typedef _Graph Graph;
454 /// The key type of InvertableMap (Node, Edge, UndirEdge).
455 typedef typename _Map::Key Key;
456 /// The value type of the InvertableMap.
457 typedef typename _Map::Value Value;
459 /// \brief Constructor.
461 /// Construct a new InvertableMap for the graph.
463 InvertableMap(const Graph& graph) : Map(graph) {}
465 /// \brief The setter function of the map.
467 /// Sets the mapped value.
468 void set(const Key& key, const Value& val) {
469 Value oldval = Map::operator[](key);
470 typename Container::iterator it = invMap.find(oldval);
471 if (it != invMap.end() && it->second == key) {
474 invMap.insert(make_pair(val, key));
478 /// \brief The getter function of the map.
480 /// It gives back the value associated with the key.
481 const Value operator[](const Key& key) const {
482 return Map::operator[](key);
487 /// \brief Add a new key to the map.
489 /// Add a new key to the map. It is called by the
490 /// \c AlterationNotifier.
491 virtual void add(const Key& key) {
495 /// \brief Erase the key from the map.
497 /// Erase the key to the map. It is called by the
498 /// \c AlterationNotifier.
499 virtual void erase(const Key& key) {
500 Value val = Map::operator[](key);
501 typename Container::iterator it = invMap.find(val);
502 if (it != invMap.end() && it->second == key) {
508 /// \brief Clear the keys from the map and inverse map.
510 /// Clear the keys from the map and inverse map. It is called by the
511 /// \c AlterationNotifier.
512 virtual void clear() {
519 typedef std::map<Value, Key> Container;
524 /// \brief The inverse map type.
526 /// The inverse of this map. The subscript operator of the map
527 /// gives back always the item what was last assigned to the value.
530 /// \brief Constructor of the InverseMap.
532 /// Constructor of the InverseMap.
533 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
535 /// The value type of the InverseMap.
536 typedef typename InvertableMap::Key Value;
537 /// The key type of the InverseMap.
538 typedef typename InvertableMap::Value Key;
540 /// \brief Subscript operator.
542 /// Subscript operator. It gives back always the item
543 /// what was last assigned to the value.
544 Value operator[](const Key& key) const {
545 typename Container::const_iterator it = inverted.invMap.find(key);
550 const InvertableMap& inverted;
553 /// \brief It gives back the just readeable inverse map.
555 /// It gives back the just readeable inverse map.
556 InverseMap inverse() const {
557 return InverseMap(*this);
564 /// \brief Provides a mutable, continuous and unique descriptor for each
565 /// item in the graph.
567 /// The DescriptorMap class provides a mutable, continuous and immutable
568 /// mapping for each item in the graph. The value for an item may mutated
569 /// on each operation when the an item erased or added to graph.
571 /// \param _Graph The graph class the \c DescriptorMap belongs to.
572 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
574 /// \param _Map A ReadWriteMap mapping from the item type to integer.
579 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
581 class DescriptorMap : protected _Map {
587 /// The graph class of DescriptorMap.
588 typedef _Graph Graph;
590 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
591 typedef typename _Map::Key Key;
592 /// The value type of DescriptorMap.
593 typedef typename _Map::Value Value;
595 /// \brief Constructor.
597 /// Constructor for descriptor map.
598 DescriptorMap(const Graph& _graph) : Map(_graph) {
604 /// \brief Add a new key to the map.
606 /// Add a new key to the map. It is called by the
607 /// \c AlterationNotifier.
608 virtual void add(const Item& item) {
610 Map::set(item, invMap.size());
611 invMap.push_back(item);
614 /// \brief Erase the key from the map.
616 /// Erase the key to the map. It is called by the
617 /// \c AlterationNotifier.
618 virtual void erase(const Item& item) {
619 Map::set(invMap.back(), Map::operator[](item));
620 invMap[Map::operator[](item)] = invMap.back();
625 /// \brief Build the unique map.
627 /// Build the unique map. It is called by the
628 /// \c AlterationNotifier.
629 virtual void build() {
632 const typename Map::Graph* graph = Map::getGraph();
633 for (graph->first(it); it != INVALID; graph->next(it)) {
634 Map::set(it, invMap.size());
635 invMap.push_back(it);
639 /// \brief Clear the keys from the map.
641 /// Clear the keys from the map. It is called by the
642 /// \c AlterationNotifier.
643 virtual void clear() {
648 /// \brief Gives back the \e descriptor of the item.
650 /// Gives back the mutable and unique \e descriptor of the map.
651 int operator[](const Item& item) const {
652 return Map::operator[](item);
657 typedef std::vector<Item> Container;
661 /// \brief The inverse map type.
663 /// The inverse map type.
666 /// \brief Constructor of the InverseMap.
668 /// Constructor of the InverseMap.
669 InverseMap(const DescriptorMap& _inverted)
670 : inverted(_inverted) {}
673 /// The value type of the InverseMap.
674 typedef typename DescriptorMap::Key Value;
675 /// The key type of the InverseMap.
676 typedef typename DescriptorMap::Value Key;
678 /// \brief Subscript operator.
680 /// Subscript operator. It gives back the item
681 /// that the descriptor belongs to currently.
682 Value operator[](const Key& key) const {
683 return inverted.invMap[key];
686 /// \brief Size of the map.
688 /// Returns the size of the map.
689 unsigned size() const {
690 return inverted.invMap.size();
694 const DescriptorMap& inverted;
697 /// \brief Gives back the inverse of the map.
699 /// Gives back the inverse of the map.
700 const InverseMap inverse() const {
701 return InverseMap(*this);
705 /// \brief Returns the source of the given edge.
707 /// The SourceMap gives back the source Node of the given edge.
708 /// \author Balazs Dezso
709 template <typename Graph>
713 typedef True NeedCopy;
715 typedef typename Graph::Node Value;
716 typedef typename Graph::Edge Key;
718 /// \brief Constructor
721 /// \param _graph The graph that the map belongs to.
722 SourceMap(const Graph& _graph) : graph(_graph) {}
724 /// \brief The subscript operator.
726 /// The subscript operator.
727 /// \param edge The edge
728 /// \return The source of the edge
729 Value operator[](const Key& edge) {
730 return graph.source(edge);
737 /// \brief Returns a \ref SourceMap class
739 /// This function just returns an \ref SourceMap class.
740 /// \relates SourceMap
741 template <typename Graph>
742 inline SourceMap<Graph> sourceMap(const Graph& graph) {
743 return SourceMap<Graph>(graph);
746 /// \brief Returns the target of the given edge.
748 /// The TargetMap gives back the target Node of the given edge.
749 /// \author Balazs Dezso
750 template <typename Graph>
754 typedef True NeedCopy;
756 typedef typename Graph::Node Value;
757 typedef typename Graph::Edge Key;
759 /// \brief Constructor
762 /// \param _graph The graph that the map belongs to.
763 TargetMap(const Graph& _graph) : graph(_graph) {}
765 /// \brief The subscript operator.
767 /// The subscript operator.
768 /// \param edge The edge
769 /// \return The target of the edge
770 Value operator[](const Key& key) {
771 return graph.target(key);
778 /// \brief Returns a \ref TargetMap class
780 /// This function just returns an \ref TargetMap class.
781 /// \relates TargetMap
782 template <typename Graph>
783 inline TargetMap<Graph> targetMap(const Graph& graph) {
784 return TargetMap<Graph>(graph);
787 /// \brief Returns the "forward" directed edge view of undirected edge.
789 /// Returns the "forward" directed edge view of undirected edge.
790 /// \author Balazs Dezso
791 template <typename Graph>
795 typedef True NeedCopy;
797 typedef typename Graph::Edge Value;
798 typedef typename Graph::UndirEdge Key;
800 /// \brief Constructor
803 /// \param _graph The graph that the map belongs to.
804 ForwardMap(const Graph& _graph) : graph(_graph) {}
806 /// \brief The subscript operator.
808 /// The subscript operator.
809 /// \param key An undirected edge
810 /// \return The "forward" directed edge view of undirected edge
811 Value operator[](const Key& key) const {
812 return graph.edgeWithSource(key, graph.source(key));
819 /// \brief Returns a \ref ForwardMap class
821 /// This function just returns an \ref ForwardMap class.
822 /// \relates ForwardMap
823 template <typename Graph>
824 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
825 return ForwardMap<Graph>(graph);
828 /// \brief Returns the "backward" directed edge view of undirected edge.
830 /// Returns the "backward" directed edge view of undirected edge.
831 /// \author Balazs Dezso
832 template <typename Graph>
835 typedef True NeedCopy;
837 typedef typename Graph::Edge Value;
838 typedef typename Graph::UndirEdge Key;
840 /// \brief Constructor
843 /// \param _graph The graph that the map belongs to.
844 BackwardMap(const Graph& _graph) : graph(_graph) {}
846 /// \brief The subscript operator.
848 /// The subscript operator.
849 /// \param key An undirected edge
850 /// \return The "backward" directed edge view of undirected edge
851 Value operator[](const Key& key) const {
852 return graph.edgeWithSource(key, graph.target(key));
859 /// \brief Returns a \ref BackwardMap class
861 /// This function just returns an \ref BackwardMap class.
862 /// \relates BackwardMap
863 template <typename Graph>
864 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
865 return BackwardMap<Graph>(graph);
868 template <typename _Graph>
872 typedef _Graph Graph;
876 typedef typename Graph::template NodeMap<int> IntNodeMap;
880 /// \brief Map of the node in-degrees.
882 /// This map returns the in-degree of a node. Ones it is constructed,
883 /// the degrees are stored in a standard NodeMap, so each query is done
884 /// in constant time. On the other hand, the values updates automatically
885 /// whenever the graph changes.
889 template <typename _Graph>
891 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
895 typedef _Graph Graph;
897 typedef typename Graph::Node Key;
901 class AutoNodeMap : public Graph::template NodeMap<int> {
904 typedef typename Graph::template NodeMap<int> Parent;
906 typedef typename Parent::Key Key;
907 typedef typename Parent::Value Value;
909 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
911 void add(const Key& key) {
919 /// \brief Constructor.
921 /// Constructor for creating in-degree map.
922 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
923 AlterationNotifier<typename _Graph::Edge>
924 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
926 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
927 deg[it] = countInEdges(graph, it);
931 virtual ~InDegMap() {
932 AlterationNotifier<typename _Graph::Edge>::
933 ObserverBase::detach();
936 /// Gives back the in-degree of a Node.
937 int operator[](const Key& key) const {
943 typedef typename Graph::Edge Edge;
945 virtual void add(const Edge& edge) {
946 ++deg[graph.target(edge)];
949 virtual void erase(const Edge& edge) {
950 --deg[graph.target(edge)];
954 virtual void build() {
955 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
956 deg[it] = countInEdges(graph, it);
960 virtual void clear() {
961 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
972 /// \brief Map of the node out-degrees.
974 /// This map returns the out-degree of a node. One it is constructed,
975 /// the degrees are stored in a standard NodeMap, so each query is done
976 /// in constant time. On the other hand, the values updates automatically
977 /// whenever the graph changes.
981 template <typename _Graph>
983 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
987 typedef _Graph Graph;
989 typedef typename Graph::Node Key;
993 class AutoNodeMap : public Graph::template NodeMap<int> {
996 typedef typename Graph::template NodeMap<int> Parent;
998 typedef typename Parent::Key Key;
999 typedef typename Parent::Value Value;
1001 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1003 void add(const Key& key) {
1005 Parent::set(key, 0);
1011 /// \brief Constructor.
1013 /// Constructor for creating out-degree map.
1014 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1015 AlterationNotifier<typename _Graph::Edge>
1016 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1018 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1019 deg[it] = countOutEdges(graph, it);
1023 virtual ~OutDegMap() {
1024 AlterationNotifier<typename _Graph::Edge>::
1025 ObserverBase::detach();
1028 /// Gives back the in-degree of a Node.
1029 int operator[](const Key& key) const {
1035 typedef typename Graph::Edge Edge;
1037 virtual void add(const Edge& edge) {
1038 ++deg[graph.source(edge)];
1041 virtual void erase(const Edge& edge) {
1042 --deg[graph.source(edge)];
1046 virtual void build() {
1047 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1048 deg[it] = countOutEdges(graph, it);
1052 virtual void clear() {
1053 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1059 const _Graph& graph;
1065 } //END OF NAMESPACE LEMON