Line data    Source code

       1             : //----------------------------------------------------------------------------
       2             : // LAGraph/experimental/test/test_KTruss.c: test cases for k-truss
       3             : // ----------------------------------------------------------------------------
       4             : 
       5             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       6             : // SPDX-License-Identifier: BSD-2-Clause
       7             : //
       8             : // For additional details (including references to third party source code and
       9             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      10             : // Contributors.txt for a full list of contributors. Created, in part, with
      11             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      12             : // DM22-0790
      13             : 
      14             : // Contributed by Timothy A. Davis, Texas A&M University
      15             : 
      16             : //-----------------------------------------------------------------------------
      17             : 
      18             : #include <stdio.h>
      19             : #include <acutest.h>
      20             : 
      21             : #include "LAGraphX.h"
      22             : #include "LAGraph_test.h"
      23             : #include "LG_Xtest.h"
      24             : 
      25             : char msg [LAGRAPH_MSG_LEN] ;
      26             : LAGraph_Graph G = NULL ;
      27             : GrB_Matrix A = NULL ;
      28             : GrB_Matrix C1 = NULL, C2 = NULL ;
      29             : #define LEN 512
      30             : char filename [LEN+1] ;
      31             : 
      32             : typedef struct
      33             : {
      34             :     uint32_t ntriangles ;
      35             :     const char *name ;
      36             : }
      37             : matrix_info ;
      38             : 
      39             : const matrix_info files [ ] =
      40             : {
      41             :     {     11, "A.mtx" },
      42             :     {   2016, "jagmesh7.mtx" },
      43             : //  { 342300, "bcsstk13.mtx" },
      44             :     {     45, "karate.mtx" },
      45             :     {      6, "ldbc-cdlp-undirected-example.mtx" },
      46             :     {      4, "ldbc-undirected-example-bool.mtx" },
      47             :     {      4, "ldbc-undirected-example-unweighted.mtx" },
      48             :     {      4, "ldbc-undirected-example.mtx" },
      49             :     {      5, "ldbc-wcc-example.mtx" },
      50             :     { 0, "" },
      51             : } ;
      52             : 
      53             : //****************************************************************************
      54           1 : void test_ktruss (void)
      55             : {
      56           1 :     LAGraph_Init (msg) ;
      57             : 
      58           1 :     for (int id = 0 ; ; id++)
      59           8 :     {
      60             : 
      61             :         // load the matrix as A
      62           9 :         const char *aname = files [id].name ;
      63           9 :         uint32_t ntriangles = files [id].ntriangles ;
      64           9 :         if (strlen (aname) == 0) break;
      65           8 :         printf ("\n================================== %s:\n", aname) ;
      66           8 :         TEST_CASE (aname) ;
      67           8 :         snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
      68           8 :         FILE *f = fopen (filename, "r") ;
      69           8 :         TEST_CHECK (f != NULL) ;
      70           8 :         OK (LAGraph_MMRead (&A, f, msg)) ;
      71           8 :         TEST_MSG ("Loading of adjacency matrix failed") ;
      72           8 :         fclose (f) ;
      73             : 
      74             :         // construct an undirected graph G with adjacency matrix A
      75           8 :         OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
      76           8 :         TEST_CHECK (A == NULL) ;
      77             : 
      78             :         // check for self-edges
      79           8 :         OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
      80           8 :         if (G->nself_edges != 0)
      81             :         {
      82             :             // remove self-edges
      83           1 :             printf ("graph has %g self edges\n", (double) G->nself_edges) ;
      84           1 :             OK (LAGraph_DeleteSelfEdges (G, msg)) ;
      85           1 :             printf ("now has %g self edges\n", (double) G->nself_edges) ;
      86           1 :             TEST_CHECK (G->nself_edges == 0) ;
      87             :         }
      88             : 
      89             :         // compute each k-truss until the result is empty
      90             :         bool ok ;
      91             :         GrB_Index n ;
      92           8 :         OK (GrB_Matrix_nrows (&n, G->A)) ;
      93          21 :         for (int k = 3 ; k < n ; k++)
      94             :         {
      95             :             // compute the k-truss
      96          21 :             printf ("\n%d-truss:\n", k) ;
      97          21 :             OK (LAGraph_KTruss (&C1, G, k, msg)) ;
      98             : 
      99             :             // compute it again to check the result
     100          21 :             OK (LG_check_ktruss (&C2, G, k, msg)) ;
     101          21 :             OK (LAGraph_Matrix_IsEqual (&ok, C1, C2, msg)) ;
     102          21 :             TEST_CHECK (ok) ;
     103             : 
     104             :             // count the triangles in the 3-truss
     105          21 :             if (k == 3)
     106             :             {
     107           8 :                 uint32_t nt = 0 ;
     108           8 :                 OK (GrB_reduce (&nt, NULL, GrB_PLUS_MONOID_UINT32, C1, NULL)) ;
     109           8 :                 nt = nt / 6 ;
     110           8 :                 TEST_CHECK (nt == ntriangles) ;
     111             :             }
     112             : 
     113             :             // free C1 and C2, and break if C1 is empty
     114             :             GrB_Index nvals ;
     115          21 :             OK (GrB_Matrix_nvals (&nvals, C1)) ;
     116          21 :             OK (GrB_free (&C1)) ;
     117          21 :             OK (GrB_free (&C2)) ;
     118          21 :             if (nvals == 0) break ;
     119             :         }
     120             : 
     121             :         // convert to directed with symmetric structure and recompute
     122           8 :         G->kind = LAGraph_ADJACENCY_DIRECTED ;
     123           8 :         G->is_symmetric_structure = LAGraph_TRUE ;
     124           8 :         OK (LAGraph_KTruss (&C1, G, 3, msg)) ;
     125           8 :         OK (LG_check_ktruss (&C2, G, 3, msg)) ;
     126           8 :         OK (LAGraph_Matrix_IsEqual (&ok, C1, C2, msg)) ;
     127           8 :         TEST_CHECK (ok) ;
     128           8 :         OK (GrB_free (&C1)) ;
     129           8 :         OK (GrB_free (&C2)) ;
     130             : 
     131           8 :         OK (LAGraph_Delete (&G, msg)) ;
     132             :     }
     133             : 
     134           1 :     LAGraph_Finalize (msg) ;
     135           1 : }
     136             : 
     137             : //------------------------------------------------------------------------------
     138             : // test_ktruss_error
     139             : //------------------------------------------------------------------------------
     140             : 
     141           1 : void test_ktruss_errors (void)
     142             : {
     143           1 :     LAGraph_Init (msg) ;
     144             : 
     145           1 :     snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
     146           1 :     FILE *f = fopen (filename, "r") ;
     147           1 :     TEST_CHECK (f != NULL) ;
     148           1 :     OK (LAGraph_MMRead (&A, f, msg)) ;
     149           1 :     TEST_MSG ("Loading of adjacency matrix failed") ;
     150           1 :     fclose (f) ;
     151             : 
     152             :     // construct an undirected graph G with adjacency matrix A
     153           1 :     OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
     154           1 :     TEST_CHECK (A == NULL) ;
     155             : 
     156           1 :     OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
     157             : 
     158             :     // C is NULL
     159           1 :     int result = LAGraph_KTruss (NULL, G, 3, msg) ;
     160           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     161           1 :     TEST_CHECK (result == GrB_NULL_POINTER) ;
     162             : 
     163             :     // k is invalid
     164           1 :     result = LAGraph_KTruss (&C1, G, 2, msg) ;
     165           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     166           1 :     TEST_CHECK (result == GrB_INVALID_VALUE) ;
     167           1 :     TEST_CHECK (C1 == NULL) ;
     168             : 
     169             :     // G is invalid
     170           1 :     result = LAGraph_KTruss (&C1, NULL, 3, msg) ;
     171           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     172           1 :     TEST_CHECK (result == GrB_NULL_POINTER) ;
     173           1 :     TEST_CHECK (C1 == NULL) ;
     174             : 
     175             :     // G may have self edges
     176           1 :     G->nself_edges = LAGRAPH_UNKNOWN ;
     177           1 :     result = LAGraph_KTruss (&C1, G, 3, msg) ;
     178           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     179           1 :     TEST_CHECK (result == -1004) ;
     180           1 :     TEST_CHECK (C1 == NULL) ;
     181             : 
     182             :     // G is undirected
     183           1 :     G->nself_edges = 0 ;
     184           1 :     G->kind = LAGraph_ADJACENCY_DIRECTED ;
     185           1 :     G->is_symmetric_structure = LAGraph_FALSE ;
     186           1 :     result = LAGraph_KTruss (&C1, G, 3, msg) ;
     187           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     188           1 :     TEST_CHECK (result == -1005) ;
     189           1 :     TEST_CHECK (C1 == NULL) ;
     190             : 
     191           1 :     result = LG_check_ktruss (&C1, G, 3, msg) ;
     192           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     193           1 :     TEST_CHECK (result == -1005) ;
     194           1 :     TEST_CHECK (C1 == NULL) ;
     195             : 
     196           1 :     OK (LAGraph_Delete (&G, msg)) ;
     197           1 :     LAGraph_Finalize (msg) ;
     198           1 : }
     199             : 
     200             : //****************************************************************************
     201             : 
     202             : TEST_LIST = {
     203             :     {"ktruss", test_ktruss},
     204             :     {"ktruss_errors", test_ktruss_errors},
     205             :     {NULL, NULL}
     206             : };