Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_KCoreDecompose: Helper method to LAGraph_KCore and LAGraph_AllKCore
       3             : // that performs graph decomposition given a specified value k.
       4             : //------------------------------------------------------------------------------
       5             : 
       6             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       7             : // SPDX-License-Identifier: BSD-2-Clause
       8             : //
       9             : // For additional details (including references to third party source code and
      10             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      11             : // Contributors.txt for a full list of contributors. Created, in part, with
      12             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      13             : // DM22-0790
      14             : 
      15             : // Contributed by Pranav Konduri, Texas A&M University
      16             : 
      17             : //------------------------------------------------------------------------------
      18             : 
      19             : #define LG_FREE_WORK                \
      20             : {                                   \
      21             :     GrB_free (&C) ;                 \
      22             :     GrB_free (&deg) ;               \
      23             : }
      24             : 
      25             : #define LG_FREE_ALL                 \
      26             : {                                   \
      27             :     LG_FREE_WORK                    \
      28             :     GrB_free (D) ;                  \
      29             : }
      30             : 
      31             : #include "LG_internal.h"
      32             : 
      33             : 
      34           6 : int LAGraph_KCore_Decompose
      35             : (
      36             :     // outputs:
      37             :     GrB_Matrix *D,              // kcore decomposition
      38             :     // inputs:
      39             :     LAGraph_Graph G,            // input graph
      40             :     GrB_Vector decomp,         // input decomposition matrix
      41             :     uint64_t k,
      42             :     char *msg
      43             : )
      44             : {
      45           6 :     LG_CLEAR_MSG ;
      46             : 
      47             :     // declare items
      48           6 :     GrB_Matrix A = NULL, C = NULL;
      49           6 :     GrB_Vector deg = NULL;
      50             : 
      51             : 
      52           6 :     LG_ASSERT (D != NULL, GrB_NULL_POINTER) ;
      53           6 :     (*D) = NULL ;
      54             : 
      55             : #if !LAGRAPH_SUITESPARSE
      56             :     LG_ASSERT (false, GrB_NOT_IMPLEMENTED) ;
      57             : #else
      58             : 
      59           6 :     LG_TRY (LAGraph_CheckGraph (G, msg)) ;
      60             : 
      61           5 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
      62           2 :        (G->kind == LAGraph_ADJACENCY_DIRECTED &&
      63           2 :         G->is_symmetric_structure == LAGraph_TRUE))
      64             :     {
      65             :          // the structure of A is known to be symmetric
      66           4 :         A = G->A ;
      67             :     }
      68             :     else
      69             :     {
      70             :         // A is not known to be symmetric
      71           1 :         LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
      72             :     }
      73             : 
      74             :     // no self edges can be present
      75             :     // todo: what would happen if there are self edges?
      76           4 :     LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
      77             : 
      78             :     //create work scalars
      79             :     GrB_Index nrows, n;
      80           3 :     GRB_TRY (GrB_Matrix_nrows(&nrows, A)) ;
      81           3 :     GRB_TRY (GrB_Vector_size(&n, decomp)) ;
      82           2 :     LG_ASSERT_MSG (nrows == n, -1003, "Size of vector and rows of matrix must be same") ;
      83             : 
      84             :     //Create Vectors and Matrices
      85           2 :     GRB_TRY (GrB_Vector_new(&deg, GrB_INT64, n)) ;
      86           2 :     GRB_TRY (GrB_Matrix_new(D, GrB_INT64, n, n)) ;
      87             : 
      88             :     //create deg vector using select
      89           2 :     GRB_TRY (GrB_select (deg, GrB_NULL, GrB_NULL, GrB_VALUEGE_INT64, decomp, k, GrB_NULL)) ;
      90             : 
      91             :     //create decomposition matrix (C * A * C)
      92             : 
      93             :     #if LAGRAPH_SUITESPARSE
      94             :         #if GxB_IMPLEMENTATION >= GxB_VERSION (7,0,0)
      95             :         // SuiteSparse 7.x and later:
      96           2 :         GRB_TRY (GrB_Matrix_diag(&C, deg, 0)) ;
      97             :         #else
      98             :         // SuiteSparse 6.x and earlier, which had the incorrect signature:
      99             :         GRB_TRY (GrB_Matrix_new(&C, GrB_INT64, n, n)) ;
     100             :         GRB_TRY (GrB_Matrix_diag(C, deg, 0)) ;
     101             :         #endif
     102             :     #else
     103             :     // standard GrB:
     104             :     GRB_TRY (GrB_Matrix_diag(&C, deg, 0)) ;
     105             :     #endif
     106             : 
     107           2 :     GRB_TRY (GrB_mxm (*D, NULL, NULL, GxB_ANY_SECONDI_INT64, C, A, GrB_NULL)) ;
     108           2 :     GRB_TRY (GrB_mxm (*D, NULL, NULL, GxB_MIN_SECONDI_INT64, *D, C, GrB_NULL)) ;
     109             : 
     110             :     //Assigns all values as 1 (todo: change to something cleaner)
     111           2 :     GRB_TRY (GrB_assign (*D, *D, NULL, (int64_t) 1, GrB_ALL, n, GrB_ALL, n, GrB_DESC_S)) ;
     112             : 
     113           2 :     LG_FREE_WORK ;
     114           2 :     return (GrB_SUCCESS) ;
     115             : #endif
     116             : }