Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LG_check_kcoredecompose: deconstruct the graph into a k-core, given a
       3             : // decompostion vector (simple method)
       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             : // This method is for testing only, to check the result of other, faster methods.
      20             : // Do not benchmark this method; it is slow and simple by design.
      21             : 
      22             : #define LG_FREE_WORK                \
      23             : {                                   \
      24             :     GrB_free (&C) ;                 \
      25             :     GrB_free (&deg) ;               \
      26             : }
      27             : 
      28             : #define LG_FREE_ALL                 \
      29             : {                                   \
      30             :     LG_FREE_WORK                    \
      31             :     GrB_free (D) ;                  \
      32             : }
      33             : 
      34             : 
      35             : #include "LG_internal.h"
      36             : #include "LG_test.h"
      37             : #include "LG_Xtest.h"
      38             : 
      39           3 : int LG_check_kcore_decompose
      40             : (
      41             :     // outputs:
      42             :     GrB_Matrix *D,              // kcore decomposition
      43             :     // inputs:
      44             :     LAGraph_Graph G,            // input graph
      45             :     GrB_Vector decomp,
      46             :     uint64_t k,
      47             :     char *msg
      48             : )
      49             : {
      50           3 :     LG_CLEAR_MSG ;
      51             : 
      52             :     // declare items
      53           3 :     GrB_Matrix A = NULL, C = NULL;
      54           3 :     GrB_Vector deg = NULL;
      55             : 
      56           3 :     LG_ASSERT (D != NULL, GrB_NULL_POINTER) ;
      57           3 :     (*D) = NULL ;
      58             : 
      59           3 :     LG_TRY (LAGraph_CheckGraph (G, msg)) ;
      60             : 
      61           3 :     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           2 :         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           2 :     LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
      76             : 
      77             :     //create work scalars
      78             :     GrB_Index size_matrix, nvals_matrix, size_vector, nvals_vector;
      79           2 :     GRB_TRY (GrB_Matrix_nrows(&size_matrix, A)) ;
      80           2 :     GRB_TRY (GrB_Vector_size(&size_vector, decomp)) ;
      81             : 
      82           2 :     LG_ASSERT_MSG (size_matrix == size_vector, -1003, "Size of vector and of matrix must be same") ;
      83             : 
      84             :     //create D and nvals scalars
      85           2 :     GRB_TRY (GrB_Matrix_new(D, GrB_INT64, size_matrix, size_matrix)) ;
      86           2 :     GRB_TRY (GrB_Matrix_nvals(&nvals_matrix, A)) ;
      87           2 :     GRB_TRY (GrB_Vector_nvals(&nvals_vector, decomp));
      88             : 
      89             :     //extract out the values of the input graph
      90           2 :     GrB_Index *row = NULL, *col = NULL , *matrix_values = NULL, *vector = NULL, *vector_values = NULL;
      91           2 :     LG_TRY (LAGraph_Malloc ((void **) &row, nvals_matrix, sizeof (GrB_Index), msg));
      92           2 :     LG_TRY (LAGraph_Malloc ((void **) &col, nvals_matrix, sizeof (GrB_Index), msg));
      93           2 :     LG_TRY (LAGraph_Malloc ((void **) &matrix_values, nvals_matrix, sizeof (GrB_Index), msg));
      94             : 
      95           2 :     LG_TRY (LAGraph_Malloc ((void **) &vector, nvals_vector, sizeof (GrB_Index), msg));
      96           2 :     LG_TRY (LAGraph_Malloc ((void **) &vector_values, nvals_vector, sizeof (GrB_Index), msg));
      97             : 
      98           2 :     GRB_TRY(GrB_Matrix_extractTuples(row, col, (int64_t *) matrix_values, &nvals_matrix, A));
      99           2 :     GRB_TRY(GrB_Vector_extractTuples(vector, (int64_t *) vector_values, &size_vector, decomp));
     100             :     //take all values that have row and col indices
     101         732 :     for(uint64_t i = 0; i < nvals_matrix; i++){
     102         730 :         bool ok_row = false, ok_col = false;
     103       25952 :         for(uint64_t j = 0; (j < nvals_vector) && (!ok_row || !ok_col); j++){
     104       25222 :             if(row[i] == vector[j] && vector_values[j] >= k)
     105         651 :                 ok_row = true;
     106       25222 :             if(col[i] == vector[j] && vector_values[j] >= k)
     107         651 :                 ok_col = true;
     108             :         }
     109         730 :         if(ok_row && ok_col){
     110         604 :             GRB_TRY(GrB_Matrix_setElement(*D, matrix_values[i], row[i], col[i]));
     111             :         }
     112             :     }
     113           2 :     LG_FREE_WORK;
     114           2 :     GRB_TRY (GrB_Matrix_wait(*D, GrB_MATERIALIZE));
     115           2 :     return (GrB_SUCCESS);
     116             : }