COIN-OR::LEMON - Graph Library

Changeset 1459:2ee881cf30a8 in lemon-0.x


Ignore:
Timestamp:
06/09/05 11:49:56 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1939
Message:
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1454 r1459  
    2525#include <lemon/utility.h>
    2626#include <lemon/maps.h>
     27#include <lemon/bits/alteration_notifier.h>
    2728
    2829///\ingroup gutils
     
    856857
    857858
    858   /* ***************************************************************** */
    859 
    860   /// Provides O(1) time node-degree queries.
    861 
    862   ///\todo Undocumented
    863   ///
     859  /// Map of the node in-degrees.
     860
     861  ///This map returns the in-degree of a node. Ones it is constructed,
     862  ///the degrees are stored in a standard NodeMap, so each query is done
     863  ///in constant time. On the other hand, the values updates automatically
     864  ///whenever the graph changes.
     865  ///
     866  ///\sa OutDegMap
    864867  template <typename _Graph>
    865868  class InDegMap  :
    866     protected _Graph::template AlterationNotifier<typename _Graph::Node>::
    867     ObserverBase,
    868     protected _Graph::template AlterationNotifier<typename _Graph::Edge>::
    869     ObserverBase
     869    protected _Graph::template NodeMap<int>,
     870    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
    870871  {
    871     typename _Graph::template NodeMap<int> deg;
    872     const _Graph* graph;
     872    const _Graph& graph;
    873873  public:
    874874    typedef int Value;
     
    878878    ///
    879879    /// 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)
    881883    {
    882       typename _Graph::template AlterationNotifier<typename _Graph::Node>
    883         ::ObserverBase::attach(graph->getNotifier(typename _Graph::Node()));
    884       typename _Graph::template AlterationNotifier<typename _Graph::Edge>
    885         ::ObserverBase::attach(graph->getNotifier(typename _Graph::Edge()));
     884      AlterationNotifier<typename _Graph::Edge>
     885        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
    886886
    887887      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
    888888        for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
    889           deg[e]++;
    890     }
    891 
    892     ~InDegMap()
     889          _Graph::template NodeMap<int>::operator[](graph.target(e))++;
     890    }
     891
     892    virtual ~InDegMap()
    893893    {
    894       typename _Graph::template AlterationNotifier<typename _Graph::Node>::
     894      AlterationNotifier<typename _Graph::Edge>::
    895895        ObserverBase::detach();
    896       typename _Graph::template 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];}
     896    }
     897   
     898    /// Gives back the in-degree of a Node.
     899    int operator[](const Key& k) const {
     900      return _Graph::template NodeMap<int>::operator[](k);
     901    }
    902902
    903903  protected:
    904904    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&)
     905      _Graph::template NodeMap<int>::add(n);
     906       _Graph::template NodeMap<int>::operator[](n)=0;
     907    }
     908    virtual void erase(const typename _Graph::Node&n)
    909909    {
     910      _Graph::template NodeMap<int>::erase(n);
    910911    }
    911912    virtual void add(const typename _Graph::Edge& e) {
    912       deg[graph.target(e)]++;
     913      _Graph::template NodeMap<int>::operator[](graph.target(e))++;
    913914    }
    914915    virtual void erase(const typename _Graph::Edge& e) {
    915       deg[graph.target(e)]--;
    916     }
    917 
     916      _Graph::template NodeMap<int>::operator[](graph.target(e))--;
     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() {}
    918987
    919988  };
  • test/graph_utils_test.cc

    r1435 r1459  
    1616using namespace lemon;
    1717
     18template<class Graph>
     19void checkSnapDeg()
     20{
     21  Graph g;
     22  typename Graph::Node n1=g.addNode();
     23  typename Graph::Node n2=g.addNode();
     24   
     25  InDegMap<Graph> ind(g);
     26 
     27  g.addEdge(n1,n2);
     28 
     29  typename Graph::SnapShot snap(g);
     30 
     31  OutDegMap<Graph> outd(g);
     32 
     33  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
     34  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
     35
     36  g.addEdge(n1,n2);
     37  g.addEdge(n2,n1);
     38 
     39  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
     40  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
     41
     42  snap.restore();
     43
     44  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
     45  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
     46 
     47}
    1848
    1949int main() {
     
    3262  }
    3363
     64  //check In/OutDegMap (and SnapShot feature)
     65
     66  checkSnapDeg<ListGraph>();
     67  checkSnapDeg<SmartGraph>();
     68 
     69
     70  ///Everything is OK
    3471  std::cout << __FILE__ ": All tests passed.\n";
    3572
Note: See TracChangeset for help on using the changeset viewer.