852 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
852 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
853 return BackwardMap<Graph>(graph); |
853 return BackwardMap<Graph>(graph); |
854 } |
854 } |
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 |
859 } //END OF NAMESPACE LEMON |
927 } //END OF NAMESPACE LEMON |
860 |
928 |
861 #endif |
929 #endif |