Changeset 1459:2ee881cf30a8 in lemon0.x
 Timestamp:
 06/09/05 11:49:56 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1939
 Files:

 2 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 nodedegree queries. 861 862 ///\todo Undocumented 863 /// 859 /// Map of the node indegrees. 860 861 ///This map returns the indegree 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 indegree 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 indegree 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 outdegrees. 926 927 ///This map returns the outdegree 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 outdegree 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 indegree 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 }; 
test/graph_utils_test.cc
r1435 r1459 16 16 using namespace lemon; 17 17 18 template<class Graph> 19 void checkSnapDeg() 20 { 21 Graph g; 22 typename Graph::Node n1=g.addNode(); 23 typename Graph::Node n2=g.addNode(); 24 25 InDegMap<Graph> ind(g); 26 27 g.addEdge(n1,n2); 28 29 typename Graph::SnapShot snap(g); 30 31 OutDegMap<Graph> outd(g); 32 33 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); 34 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); 35 36 g.addEdge(n1,n2); 37 g.addEdge(n2,n1); 38 39 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); 40 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); 41 42 snap.restore(); 43 44 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); 45 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); 46 47 } 18 48 19 49 int main() { … … 32 62 } 33 63 64 //check In/OutDegMap (and SnapShot feature) 65 66 checkSnapDeg<ListGraph>(); 67 checkSnapDeg<SmartGraph>(); 68 69 70 ///Everything is OK 34 71 std::cout << __FILE__ ": All tests passed.\n"; 35 72
Note: See TracChangeset
for help on using the changeset viewer.