COIN-OR::LEMON - Graph Library

Changeset 1453:08c8db58080e in lemon-0.x


Ignore:
Timestamp:
06/08/05 18:36:01 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1933
Message:

InDegMap? added

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1435 r1453  
    855855
    856856
     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
    857925  /// @}
    858926
Note: See TracChangeset for help on using the changeset viewer.