Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_Cached_InDegree: determine G->in_degree
       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             : // LAGraph_Cached_InDegree computes G->in_degree, where G->in_degree(j) is
      19             : // the number of entries in G->A (:,j).  If there are no entries in G->A (:,j),
      20             : // G->coldgree(j) is not present in the structure of G->in_degree.  That is,
      21             : // G->in_degree contains no explicit zero entries.
      22             : 
      23             : // G->in_degree is not computed if the graph is undirected.  Use G->out_degree
      24             : // instead, and LAGraph_Cached_OutDegree.
      25             : 
      26             : #define LG_FREE_WORK            \
      27             : {                               \
      28             :     GrB_free (&S) ;             \
      29             :     GrB_free (&x) ;             \
      30             : }
      31             : 
      32             : #define LG_FREE_ALL             \
      33             : {                               \
      34             :     LG_FREE_WORK ;              \
      35             :     GrB_free (&in_degree) ;    \
      36             : }
      37             : 
      38             : #include "LG_internal.h"
      39             : 
      40        1419 : int LAGraph_Cached_InDegree
      41             : (
      42             :     // input/output:
      43             :     LAGraph_Graph G,    // graph to determine G->in_degree
      44             :     char *msg
      45             : )
      46             : {
      47             : 
      48             :     //--------------------------------------------------------------------------
      49             :     // clear msg and check G
      50             :     //--------------------------------------------------------------------------
      51             : 
      52        1419 :     GrB_Matrix S = NULL ;
      53        1419 :     GrB_Vector in_degree = NULL, x = NULL ;
      54        1419 :     LG_CLEAR_MSG_AND_BASIC_ASSERT (G, msg) ;
      55             : 
      56        1418 :     if (G->in_degree != NULL)
      57             :     {
      58             :         // G->in_degree already computed
      59         110 :         return (GrB_SUCCESS) ;
      60             :     }
      61             : 
      62        1308 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED)
      63             :     {
      64             :         // G->in_degree is not computed since A is symmetric (warning only)
      65         152 :         return (LAGRAPH_CACHE_NOT_NEEDED) ;
      66             :     }
      67             : 
      68             :     //--------------------------------------------------------------------------
      69             :     // determine the size of A
      70             :     //--------------------------------------------------------------------------
      71             : 
      72        1156 :     GrB_Matrix A = G->A ;
      73        1156 :     GrB_Matrix AT = G->AT ;
      74             :     GrB_Index nrows, ncols ;
      75        1156 :     GRB_TRY (GrB_Matrix_nrows (&nrows, A)) ;
      76        1156 :     GRB_TRY (GrB_Matrix_ncols (&ncols, A)) ;
      77             : 
      78             :     //--------------------------------------------------------------------------
      79             :     // compute the in_degree
      80             :     //--------------------------------------------------------------------------
      81             : 
      82        1156 :     GRB_TRY (GrB_Vector_new (&in_degree, GrB_INT64, ncols)) ;
      83             :     // x = zeros (nrows,1)
      84         962 :     GRB_TRY (GrB_Vector_new (&x, GrB_INT64, nrows)) ;
      85         768 :     GRB_TRY (GrB_assign (x, NULL, NULL, 0, GrB_ALL, nrows, NULL)) ;
      86             : 
      87         671 :     if (AT != NULL)
      88             :     {
      89             :         // G->in_degree = row degree of AT; this will be faster assuming
      90             :         // AT is held in a row-oriented format.
      91         243 :         GRB_TRY (GrB_mxv (in_degree, NULL, NULL, LAGraph_plus_one_int64,
      92             :             AT, x, NULL)) ;
      93             :     }
      94             :     else
      95             :     {
      96             :         // G->in_degree = column degree of A
      97         428 :         GRB_TRY (GrB_mxv (in_degree, NULL, NULL, LAGraph_plus_one_int64,
      98             :             A, x, GrB_DESC_T0)) ;
      99             :     }
     100             : 
     101         470 :     G->in_degree = in_degree ;
     102             : 
     103         470 :     LG_FREE_WORK ;
     104         470 :     return (GrB_SUCCESS) ;
     105             : }