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             : // The input is a graph G and its k-core vector, decomp.
      20             : // The output is the k-core adjacency matrix D itself, with the same number of
      21             : // nodes as the input graph G, but with edges not in the k-core deleted.
      22             : 
      23             : #define LG_FREE_WORK                \
      24             : {                                   \
      25             :     GrB_free (&C) ;                 \
      26             :     GrB_free (&deg) ;               \
      27             : }
      28             : 
      29             : #define LG_FREE_ALL                 \
      30             : {                                   \
      31             :     LG_FREE_WORK                    \
      32             :     GrB_free (D) ;                  \
      33             : }
      34             : 
      35             : #include "LG_internal.h"
      36             : 
      37             : // TODO: need both basic and expert; this is advanced
      38             : // TODO: this should return D as an LAGraph_Graph, not as a GrB_Matrix
      39             : 
      40           6 : int LAGraph_KCore_Decompose
      41             : (
      42             :     // outputs:
      43             :     GrB_Matrix *D,              // kcore decomposition
      44             :     // inputs:
      45             :     LAGraph_Graph G,            // input graph
      46             :     GrB_Vector decomp,          // input decomposition vector
      47             :     uint64_t k,
      48             :     char *msg
      49             : )
      50             : {
      51             : #if LAGRAPH_SUITESPARSE
      52           6 :     LG_CLEAR_MSG ;
      53             : 
      54             :     // declare items
      55           6 :     GrB_Matrix A = NULL, C = NULL;
      56           6 :     GrB_Vector deg = NULL;
      57             : 
      58             : 
      59           6 :     LG_ASSERT (D != NULL, GrB_NULL_POINTER) ;
      60           6 :     (*D) = NULL ;
      61             : 
      62           6 :     LG_TRY (LAGraph_CheckGraph (G, msg)) ;
      63             : 
      64           5 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
      65           2 :        (G->kind == LAGraph_ADJACENCY_DIRECTED &&
      66           2 :         G->is_symmetric_structure == LAGraph_TRUE))
      67             :     {
      68             :          // the structure of A is known to be symmetric
      69           4 :         A = G->A ;
      70             :     }
      71             :     else
      72             :     {
      73             :         // A is not known to be symmetric
      74           1 :         LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
      75             :     }
      76             : 
      77             :     // no self edges can be present
      78             :     // todo: what would happen if there are self edges?
      79           4 :     LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
      80             : 
      81             :     //create work scalars
      82             :     GrB_Index nrows, n;
      83           3 :     GRB_TRY (GrB_Matrix_nrows(&nrows, A)) ;
      84           3 :     GRB_TRY (GrB_Vector_size(&n, decomp)) ;
      85           2 :     LG_ASSERT_MSG (nrows == n, -1003, "Size of vector and rows of matrix must be same") ;
      86             : 
      87             :     //Create Vectors and Matrices
      88           2 :     GRB_TRY (GrB_Vector_new(&deg, GrB_INT64, n)) ;
      89           2 :     GRB_TRY (GrB_Matrix_new(D, GrB_INT64, n, n)) ;
      90             : 
      91             :     //create deg vector using select
      92           2 :     GRB_TRY (GrB_select (deg, GrB_NULL, GrB_NULL, GrB_VALUEGE_INT64, decomp, k, GrB_NULL)) ;
      93             : 
      94             :     //create decomposition matrix (C * A * C)
      95             : 
      96           2 :     GRB_TRY (GrB_Matrix_diag(&C, deg, 0)) ;
      97             : 
      98           2 :     GRB_TRY (GrB_mxm (*D, NULL, NULL, GxB_ANY_SECONDI_INT64, C, A, GrB_NULL)) ;
      99           2 :     GRB_TRY (GrB_mxm (*D, NULL, NULL, GxB_MIN_SECONDI_INT64, *D, C, GrB_NULL)) ;
     100             : 
     101             :     //Assigns all values as 1 (todo: change to something cleaner)
     102           2 :     GRB_TRY (GrB_assign (*D, *D, NULL, (int64_t) 1, GrB_ALL, n, GrB_ALL, n, GrB_DESC_S)) ;
     103             : 
     104           2 :     LG_FREE_WORK ;
     105           2 :     return (GrB_SUCCESS) ;
     106             : #else
     107             :     return (GrB_NOT_IMPLEMENTED) ;
     108             : #endif
     109             : }