Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph/src/test/test_TriangleCentrality.c: test cases for triangle
       3             : // centrality
       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 Timothy A. Davis, Texas A&M University
      16             : 
      17             : //------------------------------------------------------------------------------
      18             : 
      19             : #include <stdio.h>
      20             : #include <acutest.h>
      21             : 
      22             : #include <LAGraphX.h>
      23             : #include <LAGraph_test.h>
      24             : 
      25             : char msg [LAGRAPH_MSG_LEN] ;
      26             : LAGraph_Graph G = NULL ;
      27             : GrB_Matrix A = NULL ;
      28             : GrB_Matrix C = NULL ;
      29             : #define LEN 512
      30             : char filename [LEN+1] ;
      31             : 
      32             : typedef struct
      33             : {
      34             :     uint64_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_TriangleCentrality (void)
      55             : {
      56           1 :     LAGraph_Init (msg) ;
      57             : 
      58           1 :     for (int k = 0 ; ; k++)
      59           9 :     {
      60             : 
      61             :         // load the matrix as A
      62          10 :         const char *aname = files [k].name ;
      63          10 :         uint64_t ntriangles = files [k].ntriangles ;
      64          10 :         if (strlen (aname) == 0) break;
      65           9 :         printf ("\n================================== %s:\n", aname) ;
      66           9 :         TEST_CASE (aname) ;
      67           9 :         snprintf (filename, LEN, LG_DATA_DIR "%s", aname) ;
      68           9 :         FILE *f = fopen (filename, "r") ;
      69           9 :         TEST_CHECK (f != NULL) ;
      70           9 :         OK (LAGraph_MMRead (&A, f, msg)) ;
      71             : 
      72             :         // C = spones (A), in FP64, required for methods 1 and 1.5
      73             :         GrB_Index n ;
      74           9 :         OK (GrB_Matrix_nrows (&n, A)) ;
      75           9 :         OK (GrB_Matrix_new (&C, GrB_FP64, n, n)) ;
      76           9 :         OK (GrB_assign (C, A, NULL, (double) 1, GrB_ALL, n, GrB_ALL, n,
      77             :             GrB_DESC_S)) ;
      78           9 :         OK (GrB_free (&A)) ;
      79           9 :         TEST_CHECK (A == NULL) ;
      80           9 :         OK (fclose (f)) ;
      81           9 :         TEST_MSG ("Loading of adjacency matrix failed") ;
      82             : 
      83             :         // construct an undirected graph G with adjacency matrix C
      84           9 :         OK (LAGraph_New (&G, &C, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
      85           9 :         TEST_CHECK (C == NULL) ;
      86             : 
      87             :         // check for self-edges
      88           9 :         OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
      89           9 :         if (G->nself_edges != 0)
      90             :         {
      91             :             // remove self-edges
      92           2 :             printf ("graph has %g self edges\n", (double) G->nself_edges) ;
      93           2 :             OK (LAGraph_DeleteSelfEdges (G, msg)) ;
      94           2 :             printf ("now has %g self edges\n", (double) G->nself_edges) ;
      95           2 :             TEST_CHECK (G->nself_edges == 0) ;
      96             :         }
      97             : 
      98             :         uint64_t ntri ;
      99           9 :         GrB_Vector c = NULL ;
     100          45 :         for (int method = 0 ; method <= 3 ; method++)
     101             :         {
     102          36 :             printf ("\nMethod: %d\n", method) ;
     103             : 
     104             :             // compute the triangle centrality
     105          36 :             OK (LAGraph_VertexCentrality_Triangle (&c, &ntri, method, G, msg)) ;
     106          36 :             printf ("# of triangles: %g\n", (double) ntri) ;
     107          36 :             TEST_CHECK (ntri == ntriangles) ;
     108             : 
     109             :             LAGraph_PrintLevel
     110          36 :                 pr = (n <= 100) ? LAGraph_COMPLETE : LAGraph_SHORT ;
     111          36 :             printf ("\ncentrality:\n") ;
     112          36 :             OK (LAGraph_Vector_Print (c, pr, stdout, msg)) ;
     113          36 :             OK (GrB_free (&c)) ;
     114             :         }
     115             : 
     116             :         // convert to directed with symmetric structure and recompute
     117           9 :         G->kind = LAGraph_ADJACENCY_DIRECTED ;
     118           9 :         OK (LAGraph_VertexCentrality_Triangle (&c, &ntri, 0, G, msg)) ;
     119           9 :         TEST_CHECK (ntri == ntriangles) ;
     120           9 :         GrB_free (&c) ;
     121             : 
     122           9 :         OK (LAGraph_Delete (&G, msg)) ;
     123             :     }
     124             : 
     125           1 :     LAGraph_Finalize (msg) ;
     126           1 : }
     127             : 
     128             : //------------------------------------------------------------------------------
     129             : // test_errors
     130             : //------------------------------------------------------------------------------
     131             : 
     132           1 : void test_errors (void)
     133             : {
     134           1 :     LAGraph_Init (msg) ;
     135             : 
     136           1 :     snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
     137           1 :     FILE *f = fopen (filename, "r") ;
     138           1 :     TEST_CHECK (f != NULL) ;
     139           1 :     OK (LAGraph_MMRead (&A, f, msg)) ;
     140           1 :     TEST_MSG ("Loading of adjacency matrix failed") ;
     141             : 
     142             :     // construct an undirected graph G with adjacency matrix A
     143           1 :     OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
     144           1 :     TEST_CHECK (A == NULL) ;
     145             : 
     146           1 :     OK (LAGraph_Cached_NSelfEdges (G, msg)) ;
     147             : 
     148             :     uint64_t ntri ;
     149           1 :     GrB_Vector c = NULL ;
     150             : 
     151             :     // c is NULL
     152           1 :     int result = LAGraph_VertexCentrality_Triangle (NULL, &ntri, 3, G, msg) ;
     153           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     154           1 :     TEST_CHECK (result == GrB_NULL_POINTER) ;
     155             : 
     156             :     // G is invalid
     157           1 :     result = LAGraph_VertexCentrality_Triangle (&c, &ntri, 3, NULL, msg) ;
     158           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     159           1 :     TEST_CHECK (result == GrB_NULL_POINTER) ;
     160           1 :     TEST_CHECK (c == NULL) ;
     161             : 
     162             :     // G may have self edges
     163           1 :     G->nself_edges = LAGRAPH_UNKNOWN ;
     164           1 :     result = LAGraph_VertexCentrality_Triangle (&c, &ntri, 3, G, msg) ;
     165           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     166           1 :     TEST_CHECK (result == -1004) ;
     167           1 :     TEST_CHECK (c == NULL) ;
     168             : 
     169             :     // G is undirected
     170           1 :     G->nself_edges = 0 ;
     171           1 :     G->kind = LAGraph_ADJACENCY_DIRECTED ;
     172           1 :     G->is_symmetric_structure = LAGraph_FALSE ;
     173           1 :     result = LAGraph_VertexCentrality_Triangle (&c, &ntri, 3, G, msg) ;
     174           1 :     printf ("\nresult: %d %s\n", result, msg) ;
     175           1 :     TEST_CHECK (result == -1005) ;
     176           1 :     TEST_CHECK (c == NULL) ;
     177             : 
     178           1 :     OK (LAGraph_Delete (&G, msg)) ;
     179           1 :     LAGraph_Finalize (msg) ;
     180           1 : }
     181             : 
     182             : 
     183             : //****************************************************************************
     184             : 
     185             : TEST_LIST = {
     186             :     {"TriangleCentrality", test_TriangleCentrality},
     187             :     {"TriangleCentrality_errors", test_errors},
     188             :     {NULL, NULL}
     189             : };