Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/graph_utils.h
changeset 1515 dd7616b51333
parent 1506 e8f1ad6cc8dd
child 1526 8c14aa8f27a2
equal deleted inserted replaced
6:e0f5f6f7d519 7:604c12c2c39f 
   480     /// It gives back the value associated with the key.
 
   480     /// It gives back the value associated with the key.
 
   481     const Value operator[](const Key& key) const {
 
   481     const Value operator[](const Key& key) const {
 
   482       return Map::operator[](key);
 
   482       return Map::operator[](key);
 
   483     }
 
   483     }
 
   484 
   484 
       
   485   protected:
 
       
   486 
   485     /// \brief Add a new key to the map.
 
   487     /// \brief Add a new key to the map.
 
   486     ///
 
   488     ///
 
   487     /// Add a new key to the map. It is called by the
 
   489     /// Add a new key to the map. It is called by the
 
   488     /// \c AlterationNotifier.
 
   490     /// \c AlterationNotifier.
 
   489     virtual void add(const Key& key) {
 
   491     virtual void add(const Key& key) {
 
   595     /// Constructor for descriptor map.
 
   597     /// Constructor for descriptor map.
 
   596     DescriptorMap(const Graph& _graph) : Map(_graph) {
 
   598     DescriptorMap(const Graph& _graph) : Map(_graph) {
 
   597       build();
 
   599       build();
 
   598     }
 
   600     }
 
   599 
   601 
       
   602   protected:
 
       
   603 
   600     /// \brief Add a new key to the map.
 
   604     /// \brief Add a new key to the map.
 
   601     ///
 
   605     ///
 
   602     /// Add a new key to the map. It is called by the
 
   606     /// Add a new key to the map. It is called by the
 
   603     /// \c AlterationNotifier.
 
   607     /// \c AlterationNotifier.
 
   604     virtual void add(const Item& item) {
 
   608     virtual void add(const Item& item) {
 
   770   private:
 
   774   private:
 
   771     const Graph& graph;
 
   775     const Graph& graph;
 
   772   };
 
   776   };
 
   773 
   777 
   774   /// \brief Returns a \ref TargetMap class
 
   778   /// \brief Returns a \ref TargetMap class
 
   775 
   779   ///
 
   776   /// This function just returns an \ref TargetMap class.
 
   780   /// This function just returns an \ref TargetMap class.
 
   777   /// \relates TargetMap
 
   781   /// \relates TargetMap
 
   778   template <typename Graph>
 
   782   template <typename Graph>
 
   779   inline TargetMap<Graph> targetMap(const Graph& graph) {
 
   783   inline TargetMap<Graph> targetMap(const Graph& graph) {
 
   780     return TargetMap<Graph>(graph);
 
   784     return TargetMap<Graph>(graph);
 
   811   private:
 
   815   private:
 
   812     const Graph& graph;
 
   816     const Graph& graph;
 
   813   };
 
   817   };
 
   814 
   818 
   815   /// \brief Returns a \ref ForwardMap class
 
   819   /// \brief Returns a \ref ForwardMap class
 
   816 
   820   ///
 
   817   /// This function just returns an \ref ForwardMap class.
 
   821   /// This function just returns an \ref ForwardMap class.
 
   818   /// \relates ForwardMap
 
   822   /// \relates ForwardMap
 
   819   template <typename Graph>
 
   823   template <typename Graph>
 
   820   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
 
   824   inline ForwardMap<Graph> forwardMap(const Graph& graph) {
 
   821     return ForwardMap<Graph>(graph);
 
   825     return ForwardMap<Graph>(graph);
 
   859   template <typename Graph>
 
   863   template <typename Graph>
 
   860   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
 
   864   inline BackwardMap<Graph> backwardMap(const Graph& graph) {
 
   861     return BackwardMap<Graph>(graph);
 
   865     return BackwardMap<Graph>(graph);
 
   862   }
 
   866   }
 
   863 
   867 
   864 
       
   865 
       
   866   /// Map of the node in-degrees.
 
       
   867 
       
   868   ///This map returns the in-degree of a node. Ones it is constructed,
 
       
   869   ///the degrees are stored in a standard NodeMap, so each query is done
 
       
   870   ///in constant time. On the other hand, the values updates automatically
 
       
   871   ///whenever the graph changes.
 
       
   872   ///
 
       
   873   ///\sa OutDegMap
 
       
   874   template <typename _Graph>
 
   868   template <typename _Graph>
 
   875   class InDegMap  :
 
   869   class DegMapBase {
 
   876     protected _Graph::template NodeMap<int>,
 
   870   public:
 
   877     protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
 
   871     
   878   {
 
   872     typedef _Graph Graph;
 
   879     const _Graph& graph;
 
   873 
   880   public:
 
   874   protected:
 
       
   875 
       
   876     typedef typename Graph::template NodeMap<int> IntNodeMap;
 
       
   877     
       
   878   };
 
       
   879 
       
   880   /// \brief Map of the node in-degrees.
 
       
   881   ///
 
       
   882   /// This map returns the in-degree 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     typedef int Value;
 
   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     /// \brief Constructor.
 
   919     /// \brief Constructor.
 
   885     ///
 
   920     ///
 
   886     /// Constructor for creating in-degree map.
 
   921     /// Constructor for creating in-degree map.
 
   887     InDegMap(const _Graph& _graph) :
 
   922     InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
 
   888       _Graph::template NodeMap<int>(_graph,0),
 
       
   889       graph(_graph)
 
       
   890     {
 
       
   891       AlterationNotifier<typename _Graph::Edge>
 
   923       AlterationNotifier<typename _Graph::Edge>
 
   892 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
 
   924 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
 
   893 
   925       
   894       for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
 
   926       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 
   895 	for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
 
   927 	deg[it] = countInEdges(graph, it);
 
   896 	  _Graph::template NodeMap<int>::operator[](graph.target(e))++;
 
   928       }
 
   897     }
 
   929     }
 
   898 
   930 
   899     virtual ~InDegMap() 
   931     virtual ~InDegMap() {
 
   900     {
 
       
   901       AlterationNotifier<typename _Graph::Edge>::
 
   932       AlterationNotifier<typename _Graph::Edge>::
 
   902 	ObserverBase::detach();
 
   933 	ObserverBase::detach();
 
   903     }
 
   934     }
 
   904     
   935     
   905     /// Gives back the in-degree of a Node.
 
   936     /// Gives back the in-degree of a Node.
 
   906     int operator[](const Key& k) const {
 
   937     int operator[](const Key& key) const {
 
   907       return _Graph::template NodeMap<int>::operator[](k);
 
   938       return deg[key];
 
   908     }
 
   939     }
 
   909 
   940 
   910   protected:
 
   941   protected:
 
   911     virtual void add(const typename _Graph::Node& n) {
 
   942     
   912       _Graph::template NodeMap<int>::add(n);
 
   943     typedef typename Graph::Edge Edge;
 
   913        _Graph::template NodeMap<int>::operator[](n)=0;
 
   944 
   914     }
 
   945     virtual void add(const Edge& edge) {
 
   915     virtual void erase(const typename _Graph::Node&n) 
   946       ++deg[graph.target(edge)];
 
   916     {
 
   947     }
 
   917       _Graph::template NodeMap<int>::erase(n);
 
   948 
   918     }
 
   949     virtual void erase(const Edge& edge) {
 
   919     virtual void add(const typename _Graph::Edge& e) {
 
   950       --deg[graph.target(edge)];
 
   920       _Graph::template NodeMap<int>::operator[](graph.target(e))++;
 
   951     }
 
   921     }
 
   952 
   922     virtual void erase(const typename _Graph::Edge& e) {
 
   953 
   923       _Graph::template NodeMap<int>::operator[](graph.target(e))--;
 
   954     virtual void build() {
 
   924     }
 
   955       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 
   925 
   956 	deg[it] = countInEdges(graph, it);
 
   926     ///\e
 
   957       }      
   927     
   958     }
 
   928     ///\bug Unimplemented
 
   959 
   929     ///
 
   960     virtual void clear() {
 
   930     virtual void build() {}
 
   961       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 
   931     ///\e
 
   962 	deg[it] = 0;
 
   932     
   963       }
 
   933     ///\bug Unimplemented
 
   964     }
 
   934     ///
 
   965   private:
 
   935     virtual void clear() {}
 
   966     
   936 
   967     const _Graph& graph;
 
   937   };
 
   968     AutoNodeMap deg;
 
   938 
   969   };
 
   939 
   970 
   940   /// Map of the node out-degrees.
 
   971 
   941 
   972   /// \brief Map of the node out-degrees.
 
   942   ///This map returns the out-degree of a node. One it is constructed,
 
   973   ///
 
   943   ///the degrees are stored in a standard NodeMap, so each query is done
 
   974   /// This map returns the out-degree of a node. One it is constructed,
 
   944   ///in constant time. On the other hand, the values updates automatically
 
   975   /// the degrees are stored in a standard NodeMap, so each query is done
 
   945   ///whenever the graph changes.
 
   976   /// in constant time. On the other hand, the values updates automatically
 
   946   ///
 
   977   /// whenever the graph changes.
 
   947   ///\sa OutDegMap
 
   978   ///
 
       
   979   /// \sa OutDegMap
 
       
   980 
   948   template <typename _Graph>
 
   981   template <typename _Graph>
 
   949   class OutDegMap  :
 
   982   class OutDegMap  
   950     protected _Graph::template NodeMap<int>,
 
   983     : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
 
   951     protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
 
   984 
   952   {
 
   985   public:
 
   953     const _Graph& graph;
 
   986     
   954   public:
 
   987     typedef _Graph Graph;
 
   955     typedef int Value;
 
   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     /// \brief Constructor.
 
  1011     /// \brief Constructor.
 
   959     ///
 
  1012     ///
 
   960     /// Constructor for creating out-degree map.
 
  1013     /// Constructor for creating out-degree map.
 
   961     OutDegMap(const _Graph& _graph) :
 
  1014     OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
 
   962       _Graph::template NodeMap<int>(_graph,0),
 
       
   963       graph(_graph)
 
       
   964     {
 
       
   965       AlterationNotifier<typename _Graph::Edge>
 
  1015       AlterationNotifier<typename _Graph::Edge>
 
   966 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
 
  1016 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
 
   967 
  1017       
   968       for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
 
  1018       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 
   969 	for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
 
  1019 	deg[it] = countOutEdges(graph, it);
 
   970 	  _Graph::template NodeMap<int>::operator[](graph.source(e))++;
 
  1020       }
 
   971     }
 
  1021     }
 
   972 
  1022 
   973     ~OutDegMap() 
  1023     virtual ~OutDegMap() {
 
   974     {
 
       
   975       AlterationNotifier<typename _Graph::Edge>::
 
  1024       AlterationNotifier<typename _Graph::Edge>::
 
   976 	ObserverBase::detach();
 
  1025 	ObserverBase::detach();
 
   977     }
 
  1026     }
 
   978     
  1027     
   979     /// Gives back the in-degree of a Node.
 
  1028     /// Gives back the in-degree of a Node.
 
   980     int operator[](const Key& k) const {
 
  1029     int operator[](const Key& key) const {
 
   981       return _Graph::template NodeMap<int>::operator[](k);
 
  1030       return deg[key];
 
   982     }
 
  1031     }
 
   983 
  1032 
   984   protected:
 
  1033   protected:
 
   985     virtual void add(const typename _Graph::Node& n) {
 
  1034     
   986       _Graph::template NodeMap<int>::add(n);
 
  1035     typedef typename Graph::Edge Edge;
 
   987        _Graph::template NodeMap<int>::operator[](n)=0;
 
  1036 
   988     }
 
  1037     virtual void add(const Edge& edge) {
 
   989     virtual void erase(const typename _Graph::Node&n) 
  1038       ++deg[graph.source(edge)];
 
   990     {
 
  1039     }
 
   991       _Graph::template NodeMap<int>::erase(n);
 
  1040 
   992     }
 
  1041     virtual void erase(const Edge& edge) {
 
   993     virtual void add(const typename _Graph::Edge& e) {
 
  1042       --deg[graph.source(edge)];
 
   994       _Graph::template NodeMap<int>::operator[](graph.source(e))++;
 
  1043     }
 
   995     }
 
  1044 
   996     virtual void erase(const typename _Graph::Edge& e) {
 
  1045 
   997       _Graph::template NodeMap<int>::operator[](graph.source(e))--;
 
  1046     virtual void build() {
 
   998     }
 
  1047       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 
   999 
  1048 	deg[it] = countOutEdges(graph, it);
 
  1000     ///\e
 
  1049       }      
  1001     
  1050     }
 
  1002     ///\bug Unimplemented
 
  1051 
  1003     ///
 
  1052     virtual void clear() {
 
  1004     virtual void build() {}
 
  1053       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 
  1005     ///\e
 
  1054 	deg[it] = 0;
 
  1006     
  1055       }
 
  1007     ///\bug Unimplemented
 
  1056     }
 
  1008     ///
 
  1057   private:
 
  1009     virtual void clear() {}
 
  1058     
  1010 
  1059     const _Graph& graph;
 
  1011   };
 
  1060     AutoNodeMap deg;
 
  1012 
  1061   };
 
  1013 
       
  1014 
       
  1015 
  1062 
  1016   /// @}
 
  1063   /// @}
 
  1017 
  1064 
  1018 } //END OF NAMESPACE LEMON
 
  1065 } //END OF NAMESPACE LEMON
 
  1019 
  1066
lemon-0.x