COIN-OR::LEMON - Graph Library

Changeset 1515:dd7616b51333 in lemon-0.x for lemon/graph_utils.h


Ignore:
Timestamp:
06/27/05 12:49:37 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2000
Message:

InDegMap? and OutDegMap? fixed

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1506 r1515  
    483483    }
    484484
     485  protected:
     486
    485487    /// \brief Add a new key to the map.
    486488    ///
     
    598600    }
    599601
     602  protected:
     603
    600604    /// \brief Add a new key to the map.
    601605    ///
     
    773777
    774778  /// \brief Returns a \ref TargetMap class
    775 
     779  ///
    776780  /// This function just returns an \ref TargetMap class.
    777781  /// \relates TargetMap
     
    814818
    815819  /// \brief Returns a \ref ForwardMap class
    816 
     820  ///
    817821  /// This function just returns an \ref ForwardMap class.
    818822  /// \relates ForwardMap
     
    862866  }
    863867
    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
    874868  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 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;
    881896    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:
    883918
    884919    /// \brief Constructor.
    885920    ///
    886921    /// Constructor for creating in-degree 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) {
    891923      AlterationNotifier<typename _Graph::Edge>
    892924        ::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() {
    901932      AlterationNotifier<typename _Graph::Edge>::
    902933        ObserverBase::detach();
     
    904935   
    905936    /// Gives back the in-degree 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];
    908939    }
    909940
    910941  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 out-degrees.
    941 
    942   ///This map returns the out-degree 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 out-degrees.
     973  ///
     974  /// This map returns the out-degree 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
    948981  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;
    955988    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:
    9571010
    9581011    /// \brief Constructor.
    9591012    ///
    9601013    /// Constructor for creating out-degree 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) {
    9651015      AlterationNotifier<typename _Graph::Edge>
    9661016        ::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() {
    9751024      AlterationNotifier<typename _Graph::Edge>::
    9761025        ObserverBase::detach();
     
    9781027   
    9791028    /// Gives back the in-degree 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];
    9821031    }
    9831032
    9841033  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  };
    10151062
    10161063  /// @}
Note: See TracChangeset for help on using the changeset viewer.