Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGr_SampleDegree: sample the degree median and mean
       3             : //------------------------------------------------------------------------------
       4             : 
       5             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       6             : // SPDX-License-Identifier: BSD-2-Clause
       7             : //
       8             : // For additional details (including references to third party source code and
       9             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      10             : // Contributors.txt for a full list of contributors. Created, in part, with
      11             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      12             : // DM22-0790
      13             : 
      14             : // Contributed by Timothy A. Davis, Texas A&M University
      15             : 
      16             : //------------------------------------------------------------------------------
      17             : 
      18             : // LAGr_SampleDegree computes estimates of the mean and median of the
      19             : // row or column degree of a graph.
      20             : 
      21             : #define LG_FREE_ALL LAGraph_Free ((void **) &samples, NULL) ;
      22             : 
      23             : #include "LG_internal.h"
      24             : 
      25         551 : int LAGr_SampleDegree
      26             : (
      27             :     // output:
      28             :     double *sample_mean,    // sampled mean degree
      29             :     double *sample_median,  // sampled median degree
      30             :     // input:
      31             :     const LAGraph_Graph G,  // graph of n nodes
      32             :     bool byout,             // if true, sample G->out_degree, else G->in_degree
      33             :     int64_t nsamples,       // number of samples
      34             :     uint64_t seed,          // random number seed
      35             :     char *msg
      36             : )
      37             : {
      38             : 
      39             :     //--------------------------------------------------------------------------
      40             :     // check inputs
      41             :     //--------------------------------------------------------------------------
      42             : 
      43         551 :     LG_CLEAR_MSG ;
      44         551 :     int64_t *samples = NULL ;
      45         551 :     LG_ASSERT (sample_mean != NULL, GrB_NULL_POINTER) ;
      46         551 :     LG_ASSERT (sample_median != NULL, GrB_NULL_POINTER) ;
      47         551 :     nsamples = LAGRAPH_MAX (nsamples, 1) ;
      48         551 :     LG_TRY (LAGraph_CheckGraph (G, msg)) ;
      49             : 
      50             :     GrB_Vector Degree ;
      51             : 
      52         551 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
      53         482 :        (G->kind == LAGraph_ADJACENCY_DIRECTED &&
      54         482 :         G->is_symmetric_structure == LAGraph_TRUE))
      55             :     {
      56             :         // the structure of A is known to be symmetric
      57         479 :         Degree = G->out_degree ;
      58             :     }
      59             :     else
      60             :     {
      61             :         // A is not known to be symmetric
      62          72 :         Degree = (byout) ? G->out_degree : G->in_degree ;
      63             :     }
      64             : 
      65         551 :     LG_ASSERT_MSG (Degree != NULL, LAGRAPH_NOT_CACHED, "degree unknown") ;
      66             : 
      67             :     //--------------------------------------------------------------------------
      68             :     // allocate workspace
      69             :     //--------------------------------------------------------------------------
      70             : 
      71         533 :     LG_TRY (LAGraph_Malloc ((void **) &samples, nsamples, sizeof (int64_t),
      72             :         msg)) ;
      73             : 
      74             :     //--------------------------------------------------------------------------
      75             :     // pick nsamples nodes at random and determine their degree
      76             :     //--------------------------------------------------------------------------
      77             : 
      78             :     // See also the hashed sampling method in LG_CC_FastSV6, which computes a
      79             :     // fast estimate of the mode of an integer vector.  This method does not
      80             :     // require a hash table.  However, the mode estimator in LG_CC_FastSV6
      81             :     // would be a good candidate to add as an LAGraph_SampleMode utility
      82             :     // function.
      83             : 
      84             :     GrB_Index n ;
      85         503 :     GRB_TRY (GrB_Vector_size (&n, Degree)) ;
      86             : 
      87             :     // FUTURE: use LAGraph_Random_Seed instead
      88             : 
      89         503 :     if (seed == 0) seed = 1 ;   // a seed of zero will fail
      90             : 
      91         503 :     int64_t dsum = 0 ;
      92      934723 :     for (int k = 0 ; k < nsamples ; k++)
      93             :     {
      94      934220 :         uint64_t result = LG_Random64 (&seed) ;
      95      934220 :         int64_t i = result % n ;
      96             :         // d = Degree (i)
      97      934220 :         int64_t d = 0 ;
      98      934220 :         GRB_TRY (GrB_Vector_extractElement (&d, Degree, i)) ;
      99      934220 :         samples [k] = d ;
     100      934220 :         dsum += d ;
     101             :     }
     102             : 
     103             :     // find the mean degree
     104         503 :     (*sample_mean) = ((double) dsum) / nsamples ;
     105             : 
     106             :     // find the median degree
     107         503 :     LG_qsort_1a (samples, nsamples) ;
     108         503 :     (*sample_median) = (double) samples [nsamples/2] ;
     109             : 
     110             :     //--------------------------------------------------------------------------
     111             :     // free workspace and return result
     112             :     //--------------------------------------------------------------------------
     113             : 
     114         503 :     LG_FREE_ALL ;
     115         503 :     return (GrB_SUCCESS) ;
     116             : }