LCOV - code coverage report
Current view: top level - experimental/test - LG_check_kcoredecompose.c (source / functions) Hit Total Coverage
Test: LAGraph code coverage report. Commit id: 7b9d2ee. Current time (UTC): 2025-06-03T21:57:17Z Lines: 39 39 100.0 %
Date: 2025-06-03 22:02:40 Functions: 1 1 100.0 %

          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             :     LAGraph_Free ((void **) &row, msg) ;                \
      27             :     LAGraph_Free ((void **) &col, msg) ;                \
      28             :     LAGraph_Free ((void **) &matrix_values, msg) ;      \
      29             :     LAGraph_Free ((void **) &vector, msg) ;             \
      30             :     LAGraph_Free ((void **) &vector_values, msg) ;      \
      31             : }
      32             : 
      33             : #define LG_FREE_ALL                 \
      34             : {                                   \
      35             :     LG_FREE_WORK                    \
      36             :     GrB_free (D) ;                  \
      37             : }
      38             : 
      39             : 
      40             : #include "LG_internal.h"
      41             : #include "LG_test.h"
      42             : #include "LG_Xtest.h"
      43             : 
      44           3 : int LG_check_kcore_decompose
      45             : (
      46             :     // outputs:
      47             :     GrB_Matrix *D,              // kcore decomposition
      48             :     // inputs:
      49             :     LAGraph_Graph G,            // input graph
      50             :     GrB_Vector decomp,
      51             :     uint64_t k,
      52             :     char *msg
      53             : )
      54             : {
      55           3 :     LG_CLEAR_MSG ;
      56             : 
      57             :     // declare items
      58           3 :     GrB_Matrix A = NULL, C = NULL;
      59           3 :     GrB_Vector deg = NULL;
      60           3 :     GrB_Index *row = NULL, *col = NULL , *matrix_values = NULL, *vector = NULL, *vector_values = NULL;
      61             : 
      62           3 :     LG_ASSERT (D != NULL, GrB_NULL_POINTER) ;
      63           3 :     (*D) = NULL ;
      64             : 
      65           3 :     LG_TRY (LAGraph_CheckGraph (G, msg)) ;
      66             : 
      67           3 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
      68           2 :        (G->kind == LAGraph_ADJACENCY_DIRECTED &&
      69           2 :         G->is_symmetric_structure == LAGraph_TRUE))
      70             :     {
      71             :          // the structure of A is known to be symmetric
      72           2 :         A = G->A ;
      73             :     }
      74             :     else
      75             :     {
      76             :         // A is not known to be symmetric
      77           1 :         LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
      78             :     }
      79             : 
      80             :     // no self edges can be present
      81           2 :     LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
      82             : 
      83             :     //create work scalars
      84             :     GrB_Index size_matrix, nvals_matrix, size_vector, nvals_vector;
      85           2 :     GRB_TRY (GrB_Matrix_nrows(&size_matrix, A)) ;
      86           2 :     GRB_TRY (GrB_Vector_size(&size_vector, decomp)) ;
      87             : 
      88           2 :     LG_ASSERT_MSG (size_matrix == size_vector, -1003, "Size of vector and of matrix must be same") ;
      89             : 
      90             :     //create D and nvals scalars
      91           2 :     GRB_TRY (GrB_Matrix_new(D, GrB_INT64, size_matrix, size_matrix)) ;
      92           2 :     GRB_TRY (GrB_Matrix_nvals(&nvals_matrix, A)) ;
      93           2 :     GRB_TRY (GrB_Vector_nvals(&nvals_vector, decomp));
      94             : 
      95             :     //extract out the values of the input graph
      96           2 :     LG_TRY (LAGraph_Malloc ((void **) &row, nvals_matrix, sizeof (GrB_Index), msg));
      97           2 :     LG_TRY (LAGraph_Malloc ((void **) &col, nvals_matrix, sizeof (GrB_Index), msg));
      98           2 :     LG_TRY (LAGraph_Malloc ((void **) &matrix_values, nvals_matrix, sizeof (GrB_Index), msg));
      99             : 
     100           2 :     LG_TRY (LAGraph_Malloc ((void **) &vector, nvals_vector, sizeof (GrB_Index), msg));
     101           2 :     LG_TRY (LAGraph_Malloc ((void **) &vector_values, nvals_vector, sizeof (GrB_Index), msg));
     102             : 
     103           2 :     GRB_TRY(GrB_Matrix_extractTuples(row, col, (int64_t *) matrix_values, &nvals_matrix, A));
     104           2 :     GRB_TRY(GrB_Vector_extractTuples(vector, (int64_t *) vector_values, &size_vector, decomp));
     105             :     //take all values that have row and col indices
     106         732 :     for(uint64_t i = 0; i < nvals_matrix; i++){
     107         730 :         bool ok_row = false, ok_col = false;
     108       25952 :         for(uint64_t j = 0; (j < nvals_vector) && (!ok_row || !ok_col); j++){
     109       25222 :             if(row[i] == vector[j] && vector_values[j] >= k)
     110         651 :                 ok_row = true;
     111       25222 :             if(col[i] == vector[j] && vector_values[j] >= k)
     112         651 :                 ok_col = true;
     113             :         }
     114         730 :         if(ok_row && ok_col){
     115         604 :             GRB_TRY(GrB_Matrix_setElement(*D, matrix_values[i], row[i], col[i]));
     116             :         }
     117             :     }
     118           2 :     LG_FREE_WORK;
     119           2 :     GRB_TRY (GrB_Matrix_wait(*D, GrB_MATERIALIZE));
     120           2 :     return (GrB_SUCCESS);
     121             : }
     122             : 

Generated by: LCOV version 1.14