Changeset 1459:2ee881cf30a8 in lemon-0.x for lemon/graph_utils.h
- Timestamp:
- 06/09/05 11:49:56 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1939
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_utils.h
r1454 r1459 25 25 #include <lemon/utility.h> 26 26 #include <lemon/maps.h> 27 #include <lemon/bits/alteration_notifier.h> 27 28 28 29 ///\ingroup gutils … … 856 857 857 858 858 /* ***************************************************************** */ 859 860 /// Provides O(1) time node-degree queries. 861 862 ///\todo Undocumented 863 /// 859 /// Map of the node in-degrees. 860 861 ///This map returns the in-degree of a node. Ones it is constructed, 862 ///the degrees are stored in a standard NodeMap, so each query is done 863 ///in constant time. On the other hand, the values updates automatically 864 ///whenever the graph changes. 865 /// 866 ///\sa OutDegMap 864 867 template <typename _Graph> 865 868 class InDegMap : 866 protected _Graph::template AlterationNotifier<typename _Graph::Node>:: 867 ObserverBase, 868 protected _Graph::template AlterationNotifier<typename _Graph::Edge>:: 869 ObserverBase 869 protected _Graph::template NodeMap<int>, 870 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase 870 871 { 871 typename _Graph::template NodeMap<int> deg; 872 const _Graph* graph; 872 const _Graph& graph; 873 873 public: 874 874 typedef int Value; … … 878 878 /// 879 879 /// Constructor for creating in-degree map. 880 InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0) 880 InDegMap(const _Graph& _graph) : 881 _Graph::NodeMap<int>(_graph,0), 882 graph(_graph) 881 883 { 882 typename _Graph::template AlterationNotifier<typename _Graph::Node> 883 ::ObserverBase::attach(graph->getNotifier(typename _Graph::Node())); 884 typename _Graph::template AlterationNotifier<typename _Graph::Edge> 885 ::ObserverBase::attach(graph->getNotifier(typename _Graph::Edge())); 884 AlterationNotifier<typename _Graph::Edge> 885 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); 886 886 887 887 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n) 888 888 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e) 889 deg[e]++;890 } 891 892 ~InDegMap()889 _Graph::template NodeMap<int>::operator[](graph.target(e))++; 890 } 891 892 virtual ~InDegMap() 893 893 { 894 typename _Graph::template AlterationNotifier<typename _Graph::Node>::894 AlterationNotifier<typename _Graph::Edge>:: 895 895 ObserverBase::detach(); 896 typename _Graph::template AlterationNotifier<typename _Graph::Edge>::897 ObserverBase::detach(); 898 }899 900 /// Gives back the in degree of a Node.901 int operator[](const Key& k) const { return deg[k];}896 } 897 898 /// Gives back the in-degree of a Node. 899 int operator[](const Key& k) const { 900 return _Graph::template NodeMap<int>::operator[](k); 901 } 902 902 903 903 protected: 904 904 virtual void add(const typename _Graph::Node& n) { 905 ///\bug Which 'add' comes before to other?906 deg[n]=0;907 } 908 virtual void erase(const typename _Graph::Node& )905 _Graph::template NodeMap<int>::add(n); 906 _Graph::template NodeMap<int>::operator[](n)=0; 907 } 908 virtual void erase(const typename _Graph::Node&n) 909 909 { 910 _Graph::template NodeMap<int>::erase(n); 910 911 } 911 912 virtual void add(const typename _Graph::Edge& e) { 912 deg[graph.target(e)]++;913 _Graph::template NodeMap<int>::operator[](graph.target(e))++; 913 914 } 914 915 virtual void erase(const typename _Graph::Edge& e) { 915 deg[graph.target(e)]--; 916 } 917 916 _Graph::template NodeMap<int>::operator[](graph.target(e))--; 917 } 918 919 virtual void build() {} 920 virtual void clear() {} 921 922 }; 923 924 925 /// Map of the node out-degrees. 926 927 ///This map returns the out-degree of a node. One it is constructed, 928 ///the degrees are stored in a standard NodeMap, so each query is done 929 ///in constant time. On the other hand, the values updates automatically 930 ///whenever the graph changes. 931 /// 932 ///\sa OutDegMap 933 template <typename _Graph> 934 class OutDegMap : 935 protected _Graph::template NodeMap<int>, 936 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase 937 { 938 const _Graph& graph; 939 public: 940 typedef int Value; 941 typedef typename _Graph::Node Key; 942 943 /// \brief Constructor. 944 /// 945 /// Constructor for creating out-degree map. 946 OutDegMap(const _Graph& _graph) : 947 _Graph::NodeMap<int>(_graph,0), 948 graph(_graph) 949 { 950 AlterationNotifier<typename _Graph::Edge> 951 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); 952 953 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n) 954 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e) 955 _Graph::template NodeMap<int>::operator[](graph.source(e))++; 956 } 957 958 ~OutDegMap() 959 { 960 AlterationNotifier<typename _Graph::Edge>:: 961 ObserverBase::detach(); 962 } 963 964 /// Gives back the in-degree of a Node. 965 int operator[](const Key& k) const { 966 return _Graph::template NodeMap<int>::operator[](k); 967 } 968 969 protected: 970 virtual void add(const typename _Graph::Node& n) { 971 _Graph::template NodeMap<int>::add(n); 972 _Graph::template NodeMap<int>::operator[](n)=0; 973 } 974 virtual void erase(const typename _Graph::Node&n) 975 { 976 _Graph::template NodeMap<int>::erase(n); 977 } 978 virtual void add(const typename _Graph::Edge& e) { 979 _Graph::template NodeMap<int>::operator[](graph.source(e))++; 980 } 981 virtual void erase(const typename _Graph::Edge& e) { 982 _Graph::template NodeMap<int>::operator[](graph.source(e))--; 983 } 984 985 virtual void build() {} 986 virtual void clear() {} 918 987 919 988 };
Note: See TracChangeset
for help on using the changeset viewer.