Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph/expirimental/test/test_SquareClustering.c: test cases for
       3             : // square clustering
       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 Erik Welch, NVIDIA
      16             : 
      17             : //------------------------------------------------------------------------------
      18             : 
      19             : #include <stdio.h>
      20             : #include <acutest.h>
      21             : 
      22             : #include <LAGraphX.h>
      23             : #include <LAGraph_test.h>
      24             : #include "LG_Xtest.h"
      25             : 
      26             : char msg [LAGRAPH_MSG_LEN] ;
      27             : 
      28             : // Data from NetworkX, test_lind_square_clustering: https://github.com/networkx\
      29             : //      /networkx/blob/main/networkx/algorithms/tests/test_cluster.py
      30             : GrB_Index rows[19] = {1, 1, 1, 1, 2, 2, 3, 3, 6, 7, 6, 7, 7, 6, 6, 2, 2, 3, 3} ;
      31             : GrB_Index cols[19] = {2, 3, 6, 7, 4, 5, 4, 5, 7, 8, 8, 9, 10, 11, 12, 13, 14,
      32             :     15, 16} ;
      33             : int64_t vals[19] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} ;
      34             : 
      35             : GrB_Index soln_indices[8] = {1, 2, 3, 4, 5, 6, 7, 8} ;
      36             : double soln_values[8] = {
      37             :     3.0 / 43.0,
      38             :     3.0 / 17.0,
      39             :     3.0 / 17.0,
      40             :     1.0 / 3.0,
      41             :     1.0 / 3.0,
      42             :     1.0 / 27.0,
      43             :     1.0 / 27.0,
      44             :     1.0 / 5.0
      45             : };
      46             : 
      47             : //------------------------------------------------------------------------------
      48             : // is_close: check whether two floats are close
      49             : //------------------------------------------------------------------------------
      50             : 
      51           8 : bool is_close (double a, double b)
      52             : {
      53           8 :     double abs_diff = fabs(a - b) ;
      54           8 :     return abs_diff < 1e-6 ;
      55             : }
      56             : 
      57           1 : void test_SquareClustering (void)
      58             : {
      59           1 :     LAGraph_Init (msg) ;
      60             : 
      61           1 :     GrB_Matrix A = NULL ;
      62           1 :     LAGraph_Graph G = NULL ;
      63             : 
      64           1 :     GrB_Index n = 17;
      65           1 :     OK (GrB_Matrix_new (&A, GrB_INT64, n, n)) ;
      66           1 :     OK (GrB_Matrix_build_INT64 (A, rows, cols, vals, 19, GrB_PLUS_INT64)) ;
      67             :     // Symmetrize A
      68           1 :     OK (GrB_Matrix_eWiseAdd_BinaryOp(A, NULL, NULL, GrB_FIRST_INT64, A, A,
      69             :         GrB_DESC_T1));
      70           1 :     OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
      71           1 :     TEST_CHECK (A == NULL) ;
      72             : 
      73             :     // check for self-edges
      74           1 :     OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
      75           1 :     bool sanitize = (G->nself_edges != 0) ;
      76             : 
      77           1 :     OK (LAGraph_Cached_OutDegree (G, msg)) ;
      78             : 
      79           1 :     GrB_Vector c = NULL ;
      80           1 :     OK (LAGraph_SquareClustering (&c, G, msg)) ;
      81             : 
      82             :     GrB_Index nvals;
      83           1 :     OK (GrB_Vector_nvals(&nvals, c)) ;
      84           1 :     TEST_CHECK (nvals == 8) ;
      85             : 
      86             :     // OK (GrB_Vector_new(&soln, GrB_FP64, n)) ;
      87             :     // OK (GrB_Vector_build_FP64(soln, soln_indices, soln_values, 8,
      88             :     //     GrB_PLUS_FP64)) ;
      89             :     double val;
      90           9 :     for (GrB_Index i = 0 ; i < 8 ; ++i)
      91             :     {
      92           8 :         GrB_Vector_extractElement_FP64(&val, c, soln_indices[i]) ;
      93           8 :         TEST_CHECK (is_close(val, soln_values[i])) ;
      94             :     }
      95             :     // OK (GrB_free (&soln)) ;
      96             : 
      97           1 :     OK (GrB_free (&c)) ;
      98           1 :     OK (LAGraph_Delete (&G, msg)) ;
      99             : 
     100           1 :     LAGraph_Finalize (msg) ;
     101           1 : };
     102             : 
     103             : TEST_LIST = {
     104             :     {"SquareClustering", test_SquareClustering},
     105             :     // {"SquareClustering_errors", test_errors},
     106             :     {NULL, NULL}
     107             : };