Changeset 1453:08c8db58080e in lemon-0.x for lemon
- Timestamp:
- 06/08/05 18:36:01 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1933
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_utils.h
r1435 r1453 855 855 856 856 857 858 /* ***************************************************************** */ 859 860 /// Provides O(1) time node-degree queries. 861 862 ///\todo Undocumented 863 /// 864 template <typename _Graph> 865 class InDegMap : 866 protected _Graph::AlterationNotifier<typename _Graph::Node>:: 867 ObserverBase, 868 protected _Graph::AlterationNotifier<typename _Graph::Edge>:: 869 ObserverBase 870 { 871 typename _Graph::template NodeMap<int> deg; 872 const _Graph* graph; 873 public: 874 typedef int Value; 875 typedef typename _Graph::Node Key; 876 877 /// \brief Constructor. 878 /// 879 /// Constructor for creating in-degree map. 880 InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0) 881 { 882 typename _Graph::AlterationNotifier<typename _Graph::Node>::ObserverBase:: 883 attach(graph->getNotifier(typename _Graph::Node())); 884 typename _Graph::AlterationNotifier<typename _Graph::Edge>::ObserverBase:: 885 attach(graph->getNotifier(typename _Graph::Edge())); 886 887 for(typename _Graph::NodeIt n(g);n!=INVALID;++n) 888 for(typename _Graph::InEdgeIt e(g,n);e!=INVALID;++e) 889 deg[e]++; 890 } 891 892 ~InDegMap() 893 { 894 typename _Graph::AlterationNotifier<typename _Graph::Node>:: 895 ObserverBase::detach(); 896 typename _Graph::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];} 902 903 protected: 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&) 909 { 910 } 911 virtual void add(const typename _Graph::Edge& n) { 912 deg[graph.target(e)]++; 913 }; 914 virtual void erase(const typename _Graph::Edge&) 915 { 916 deg[graph.target(e)]--; 917 } 918 919 920 }; 921 922 923 924 857 925 /// @} 858 926
Note: See TracChangeset
for help on using the changeset viewer.