853 return BackwardMap<Graph>(graph); |
854 return BackwardMap<Graph>(graph); |
854 } |
855 } |
855 |
856 |
856 |
857 |
857 |
858 |
858 /* ***************************************************************** */ |
859 /// Map of the node in-degrees. |
859 |
860 |
860 /// Provides O(1) time node-degree queries. |
861 ///This map returns the in-degree of a node. Ones it is constructed, |
861 |
862 ///the degrees are stored in a standard NodeMap, so each query is done |
862 ///\todo Undocumented |
863 ///in constant time. On the other hand, the values updates automatically |
863 /// |
864 ///whenever the graph changes. |
|
865 /// |
|
866 ///\sa OutDegMap |
864 template <typename _Graph> |
867 template <typename _Graph> |
865 class InDegMap : |
868 class InDegMap : |
866 protected _Graph::template AlterationNotifier<typename _Graph::Node>:: |
869 protected _Graph::template NodeMap<int>, |
867 ObserverBase, |
870 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase |
868 protected _Graph::template AlterationNotifier<typename _Graph::Edge>:: |
|
869 ObserverBase |
|
870 { |
871 { |
871 typename _Graph::template NodeMap<int> deg; |
872 const _Graph& graph; |
872 const _Graph* graph; |
|
873 public: |
873 public: |
874 typedef int Value; |
874 typedef int Value; |
875 typedef typename _Graph::Node Key; |
875 typedef typename _Graph::Node Key; |
876 |
876 |
877 /// \brief Constructor. |
877 /// \brief Constructor. |
878 /// |
878 /// |
879 /// Constructor for creating in-degree map. |
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> |
884 AlterationNotifier<typename _Graph::Edge> |
883 ::ObserverBase::attach(graph->getNotifier(typename _Graph::Node())); |
885 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); |
884 typename _Graph::template AlterationNotifier<typename _Graph::Edge> |
|
885 ::ObserverBase::attach(graph->getNotifier(typename _Graph::Edge())); |
|
886 |
886 |
887 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n) |
887 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n) |
888 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e) |
888 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e) |
889 deg[e]++; |
889 _Graph::template NodeMap<int>::operator[](graph.target(e))++; |
890 } |
890 } |
891 |
891 |
892 ~InDegMap() |
892 virtual ~InDegMap() |
893 { |
893 { |
894 typename _Graph::template AlterationNotifier<typename _Graph::Node>:: |
894 AlterationNotifier<typename _Graph::Edge>:: |
895 ObserverBase::detach(); |
895 ObserverBase::detach(); |
896 typename _Graph::template AlterationNotifier<typename _Graph::Edge>:: |
896 } |
897 ObserverBase::detach(); |
897 |
898 } |
898 /// Gives back the in-degree of a Node. |
899 |
899 int operator[](const Key& k) const { |
900 /// Gives back the in degree of a Node. |
900 return _Graph::template NodeMap<int>::operator[](k); |
901 int operator[](const Key& k) const { return deg[k];} |
901 } |
902 |
902 |
903 protected: |
903 protected: |
904 virtual void add(const typename _Graph::Node& n) { |
904 virtual void add(const typename _Graph::Node& n) { |
905 ///\bug Which 'add' comes before to other? |
905 _Graph::template NodeMap<int>::add(n); |
906 deg[n]=0; |
906 _Graph::template NodeMap<int>::operator[](n)=0; |
907 } |
907 } |
908 virtual void erase(const typename _Graph::Node&) |
908 virtual void erase(const typename _Graph::Node&n) |
909 { |
909 { |
|
910 _Graph::template NodeMap<int>::erase(n); |
910 } |
911 } |
911 virtual void add(const typename _Graph::Edge& e) { |
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 virtual void erase(const typename _Graph::Edge& e) { |
915 virtual void erase(const typename _Graph::Edge& e) { |
915 deg[graph.target(e)]--; |
916 _Graph::template NodeMap<int>::operator[](graph.target(e))--; |
916 } |
917 } |
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 }; |
920 |
989 |
921 |
990 |
922 |
991 |