Changeset 1515:dd7616b51333 in lemon0.x
 Timestamp:
 06/27/05 12:49:37 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2000
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r1506 r1515 483 483 } 484 484 485 protected: 486 485 487 /// \brief Add a new key to the map. 486 488 /// … … 598 600 } 599 601 602 protected: 603 600 604 /// \brief Add a new key to the map. 601 605 /// … … 773 777 774 778 /// \brief Returns a \ref TargetMap class 775 779 /// 776 780 /// This function just returns an \ref TargetMap class. 777 781 /// \relates TargetMap … … 814 818 815 819 /// \brief Returns a \ref ForwardMap class 816 820 /// 817 821 /// This function just returns an \ref ForwardMap class. 818 822 /// \relates ForwardMap … … 862 866 } 863 867 864 865 866 /// Map of the node indegrees.867 868 ///This map returns the indegree of a node. Ones it is constructed,869 ///the degrees are stored in a standard NodeMap, so each query is done870 ///in constant time. On the other hand, the values updates automatically871 ///whenever the graph changes.872 ///873 ///\sa OutDegMap874 868 template <typename _Graph> 875 class InDegMap : 876 protected _Graph::template NodeMap<int>, 877 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase 878 { 879 const _Graph& graph; 880 public: 869 class DegMapBase { 870 public: 871 872 typedef _Graph Graph; 873 874 protected: 875 876 typedef typename Graph::template NodeMap<int> IntNodeMap; 877 878 }; 879 880 /// \brief Map of the node indegrees. 881 /// 882 /// This map returns the indegree 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. 886 /// 887 /// \sa OutDegMap 888 889 template <typename _Graph> 890 class InDegMap 891 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase { 892 893 public: 894 895 typedef _Graph Graph; 881 896 typedef int Value; 882 typedef typename _Graph::Node Key; 897 typedef typename Graph::Node Key; 898 899 private: 900 901 class AutoNodeMap : public Graph::template NodeMap<int> { 902 public: 903 904 typedef typename Graph::template NodeMap<int> Parent; 905 906 typedef typename Parent::Key Key; 907 typedef typename Parent::Value Value; 908 909 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} 910 911 void add(const Key& key) { 912 Parent::add(key); 913 Parent::set(key, 0); 914 } 915 }; 916 917 public: 883 918 884 919 /// \brief Constructor. 885 920 /// 886 921 /// Constructor for creating indegree map. 887 InDegMap(const _Graph& _graph) : 888 _Graph::template NodeMap<int>(_graph,0), 889 graph(_graph) 890 { 922 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) { 891 923 AlterationNotifier<typename _Graph::Edge> 892 924 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); 893 894 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n) 895 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e) 896 _Graph::template NodeMap<int>::operator[](graph.target(e))++; 897 } 898 899 virtual ~InDegMap() 900 { 925 926 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { 927 deg[it] = countInEdges(graph, it); 928 } 929 } 930 931 virtual ~InDegMap() { 901 932 AlterationNotifier<typename _Graph::Edge>:: 902 933 ObserverBase::detach(); … … 904 935 905 936 /// Gives back the indegree of a Node. 906 int operator[](const Key& k ) const {907 return _Graph::template NodeMap<int>::operator[](k);937 int operator[](const Key& key) const { 938 return deg[key]; 908 939 } 909 940 910 941 protected: 911 virtual void add(const typename _Graph::Node& n) { 912 _Graph::template NodeMap<int>::add(n); 913 _Graph::template NodeMap<int>::operator[](n)=0; 914 } 915 virtual void erase(const typename _Graph::Node&n) 916 { 917 _Graph::template NodeMap<int>::erase(n); 918 } 919 virtual void add(const typename _Graph::Edge& e) { 920 _Graph::template NodeMap<int>::operator[](graph.target(e))++; 921 } 922 virtual void erase(const typename _Graph::Edge& e) { 923 _Graph::template NodeMap<int>::operator[](graph.target(e)); 924 } 925 926 ///\e 927 928 ///\bug Unimplemented 929 /// 930 virtual void build() {} 931 ///\e 932 933 ///\bug Unimplemented 934 /// 935 virtual void clear() {} 936 937 }; 938 939 940 /// Map of the node outdegrees. 941 942 ///This map returns the outdegree of a node. One it is constructed, 943 ///the degrees are stored in a standard NodeMap, so each query is done 944 ///in constant time. On the other hand, the values updates automatically 945 ///whenever the graph changes. 946 /// 947 ///\sa OutDegMap 942 943 typedef typename Graph::Edge Edge; 944 945 virtual void add(const Edge& edge) { 946 ++deg[graph.target(edge)]; 947 } 948 949 virtual void erase(const Edge& edge) { 950 deg[graph.target(edge)]; 951 } 952 953 954 virtual void build() { 955 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { 956 deg[it] = countInEdges(graph, it); 957 } 958 } 959 960 virtual void clear() { 961 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { 962 deg[it] = 0; 963 } 964 } 965 private: 966 967 const _Graph& graph; 968 AutoNodeMap deg; 969 }; 970 971 972 /// \brief Map of the node outdegrees. 973 /// 974 /// This map returns the outdegree 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. 978 /// 979 /// \sa OutDegMap 980 948 981 template <typename _Graph> 949 class OutDegMap :950 protected _Graph::template NodeMap<int>,951 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase 952 {953 const _Graph& graph;954 public:982 class OutDegMap 983 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase { 984 985 public: 986 987 typedef _Graph Graph; 955 988 typedef int Value; 956 typedef typename _Graph::Node Key; 989 typedef typename Graph::Node Key; 990 991 private: 992 993 class AutoNodeMap : public Graph::template NodeMap<int> { 994 public: 995 996 typedef typename Graph::template NodeMap<int> Parent; 997 998 typedef typename Parent::Key Key; 999 typedef typename Parent::Value Value; 1000 1001 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} 1002 1003 void add(const Key& key) { 1004 Parent::add(key); 1005 Parent::set(key, 0); 1006 } 1007 }; 1008 1009 public: 957 1010 958 1011 /// \brief Constructor. 959 1012 /// 960 1013 /// Constructor for creating outdegree map. 961 OutDegMap(const _Graph& _graph) : 962 _Graph::template NodeMap<int>(_graph,0), 963 graph(_graph) 964 { 1014 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) { 965 1015 AlterationNotifier<typename _Graph::Edge> 966 1016 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); 967 968 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n) 969 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e) 970 _Graph::template NodeMap<int>::operator[](graph.source(e))++; 971 } 972 973 ~OutDegMap() 974 { 1017 1018 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { 1019 deg[it] = countOutEdges(graph, it); 1020 } 1021 } 1022 1023 virtual ~OutDegMap() { 975 1024 AlterationNotifier<typename _Graph::Edge>:: 976 1025 ObserverBase::detach(); … … 978 1027 979 1028 /// Gives back the indegree of a Node. 980 int operator[](const Key& k ) const {981 return _Graph::template NodeMap<int>::operator[](k);1029 int operator[](const Key& key) const { 1030 return deg[key]; 982 1031 } 983 1032 984 1033 protected: 985 virtual void add(const typename _Graph::Node& n) { 986 _Graph::template NodeMap<int>::add(n); 987 _Graph::template NodeMap<int>::operator[](n)=0; 988 } 989 virtual void erase(const typename _Graph::Node&n) 990 { 991 _Graph::template NodeMap<int>::erase(n); 992 } 993 virtual void add(const typename _Graph::Edge& e) { 994 _Graph::template NodeMap<int>::operator[](graph.source(e))++; 995 } 996 virtual void erase(const typename _Graph::Edge& e) { 997 _Graph::template NodeMap<int>::operator[](graph.source(e)); 998 } 999 1000 ///\e 1001 1002 ///\bug Unimplemented 1003 /// 1004 virtual void build() {} 1005 ///\e 1006 1007 ///\bug Unimplemented 1008 /// 1009 virtual void clear() {} 1010 1011 }; 1012 1013 1014 1034 1035 typedef typename Graph::Edge Edge; 1036 1037 virtual void add(const Edge& edge) { 1038 ++deg[graph.source(edge)]; 1039 } 1040 1041 virtual void erase(const Edge& edge) { 1042 deg[graph.source(edge)]; 1043 } 1044 1045 1046 virtual void build() { 1047 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { 1048 deg[it] = countOutEdges(graph, it); 1049 } 1050 } 1051 1052 virtual void clear() { 1053 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { 1054 deg[it] = 0; 1055 } 1056 } 1057 private: 1058 1059 const _Graph& graph; 1060 AutoNodeMap deg; 1061 }; 1015 1062 1016 1063 /// @}
Note: See TracChangeset
for help on using the changeset viewer.