Line data    Source code

       1             : //----------------------------------------------------------------------------
       2             : // LAGraph/src/test/test_mcl.c: test cases for Markov Clustering
       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 Cameron Quilici, Texas A&M University
      15             : 
      16             : //-----------------------------------------------------------------------------
      17             : 
      18             : #include <acutest.h>
      19             : #include <stdio.h>
      20             : 
      21             : #include "LG_Xtest.h"
      22             : #include <LAGraphX.h>
      23             : #include <LAGraph_test.h>
      24             : 
      25             : char msg[LAGRAPH_MSG_LEN];
      26             : 
      27             : LAGraph_Graph G = NULL;
      28             : GrB_Matrix A = NULL;
      29             : #define LEN 512
      30             : char filename[LEN + 1];
      31             : 
      32             : typedef struct
      33             : {
      34             :     const char *name;
      35             : } matrix_info;
      36             : 
      37             : const matrix_info files[] = {
      38             :     {"A.mtx"},        {"jagmesh7.mtx"}, {"west0067.mtx"}, // unsymmetric
      39             :     {"bcsstk13.mtx"}, {"karate.mtx"},   {"mcl.mtx"},      {""},
      40             : };
      41             : 
      42             : const int nfiles = 6;
      43             : 
      44             : const double coverage[] = {1.000000, 0.635932, 0.784247,
      45             :                            0.089424, 0.871795, 0.888889};
      46             : 
      47             : const double performance[] = {0.714286, 0.990614, 0.282678,
      48             :                               0.975945, 0.611408, 0.622222};
      49             : 
      50             : const double modularity[] = {0.000000, 0.624182, 0.033355,
      51             :                              0.083733, 0.359961, 0.339506};
      52             : 
      53             : //****************************************************************************
      54           1 : void test_mcl(void)
      55             : {
      56             : #if LAGRAPH_SUITESPARSE
      57           1 :     LAGraph_Init(msg);
      58             : 
      59           1 :     for (int k = 0;; k++)
      60           6 :     {
      61             :         // load the matrix as A
      62           7 :         const char *aname = files[k].name;
      63           7 :         if (strlen(aname) == 0)
      64           1 :             break;
      65           6 :         printf("\n================================== %s:\n", aname);
      66           6 :         TEST_CASE(aname);
      67           6 :         snprintf(filename, LEN, LG_DATA_DIR "%s", aname);
      68           6 :         FILE *f = fopen(filename, "r");
      69           6 :         TEST_CHECK(f != NULL);
      70           6 :         OK(LAGraph_MMRead(&A, f, msg));
      71           6 :         fclose (f) ;
      72             : 
      73             :         // construct a directed graph G with adjacency matrix A
      74           6 :         OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_DIRECTED, msg));
      75           6 :         TEST_CHECK(A == NULL);
      76             : 
      77             :         // compute AT
      78           6 :         OK(LAGraph_Cached_AT(G, msg));
      79             :         // Needed to compute quality metrics
      80           6 :         OK(LAGraph_Cached_IsSymmetricStructure(G, msg));
      81             : 
      82           6 :         GrB_Vector c = NULL;
      83             : 
      84             :         // compute clustering
      85             :         double cov, perf, mod;
      86           6 :         OK(LAGr_MarkovClustering(&c, 2, 2, 0.0001, 1e-8, 100, G, msg));
      87           6 :         OK(LAGr_PartitionQuality(&cov, &perf, c, G, msg));
      88           6 :         OK(LAGr_Modularity(&mod, (double)1, c, G, msg));
      89             : 
      90           6 :         bool ok_cov = false, ok_perf = false, ok_mod = false;
      91           6 :         printf("coverage:   %g %g\n", cov, coverage[k]);
      92           6 :         printf("perf:       %g %g\n", perf, performance[k]);
      93           6 :         printf("modularity: %g %g\n", mod, modularity[k]);
      94           6 :         ok_cov = (fabs(cov - coverage[k]) < 1e-4) ? true : ok_cov;
      95           6 :         ok_perf = (fabs(perf - performance[k]) < 1e-4) ? true : ok_perf;
      96           6 :         ok_mod = (fabs(mod - modularity[k]) < 1e-4) ? true : ok_mod;
      97             : 
      98           6 :         TEST_CHECK(ok_cov);
      99           6 :         TEST_CHECK(ok_perf);
     100           6 :         TEST_CHECK(ok_mod);
     101           6 :         OK(GrB_free(&c));
     102             : 
     103           6 :         if (k != 3)
     104             :         {
     105             :             // compute clustering with higher e parameter (expansion coef)
     106           5 :             printf ("\nWith e=4:\n") ;
     107           5 :             OK(LAGr_MarkovClustering(&c, 4, 2, 0.0001, 1e-8, 100, G, msg));
     108           5 :             OK(LAGr_PartitionQuality(&cov, &perf, c, G, msg));
     109           5 :             OK(LAGr_Modularity(&mod, (double)1, c, G, msg));
     110           5 :             printf("coverage:   %g\n", cov);
     111           5 :             printf("perf:       %g\n", perf);
     112           5 :             printf("modularity: %g\n", mod);
     113           5 :             OK(GrB_free(&c));
     114             : 
     115             :             // compute clustering with high pruning threshold
     116           5 :             printf ("\nWith high pruning threshold:\n") ;
     117           5 :             OK (LAGr_MarkovClustering(&c, 4, 2, 0.005, 1e-8, 100, G, msg));
     118           5 :             OK (LAGr_PartitionQuality(&cov, &perf, c, G, msg));
     119           5 :             OK (LAGr_Modularity(&mod, (double)1, c, G, msg));
     120           5 :             printf("coverage:   %g\n", cov);
     121           5 :             printf("perf:       %g\n", perf);
     122           5 :             printf("modularity: %g\n", mod);
     123           5 :             OK(GrB_free(&c));
     124             :         }
     125             : 
     126           6 :         OK(LAGraph_Delete(&G, msg));
     127             :     }
     128             : 
     129           1 :     LAGraph_Finalize(msg);
     130             : #endif
     131           1 : }
     132             : 
     133             : //------------------------------------------------------------------------------
     134             : // test_errors
     135             : //------------------------------------------------------------------------------
     136             : 
     137           1 : void test_errors(void)
     138             : {
     139             : #if LAGRAPH_SUITESPARSE
     140           1 :     LAGraph_Init(msg);
     141             : 
     142           1 :     snprintf(filename, LEN, LG_DATA_DIR "%s", "karate.mtx");
     143           1 :     FILE *f = fopen(filename, "r");
     144           1 :     TEST_CHECK(f != NULL);
     145           1 :     OK(LAGraph_MMRead(&A, f, msg));
     146           1 :     TEST_MSG("Loading of adjacency matrix failed");
     147           1 :     fclose (f) ;
     148             : 
     149             :     // construct an undirected graph G with adjacency matrix A
     150           1 :     OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg));
     151           1 :     TEST_CHECK(A == NULL);
     152             : 
     153           1 :     GrB_Vector c = NULL;
     154           1 :     int e = 2, i = 2, max_iter = 50;
     155           1 :     double prune_thresh = 0.0001, conv_thresh = 1e-8;
     156             : 
     157             :     // c is NULL
     158           1 :     GrB_Info result = LAGr_MarkovClustering(NULL, e, i, prune_thresh,
     159             :                                             conv_thresh, max_iter, G, msg);
     160           1 :     printf("\nresult: %d %s\n", result, msg);
     161           1 :     TEST_CHECK(result == GrB_NULL_POINTER);
     162             : 
     163             :     // e is less than 2
     164           1 :     e = -100;
     165           1 :     result = LAGr_MarkovClustering(&c, e, i, prune_thresh, conv_thresh,
     166             :                                    max_iter, G, msg);
     167           1 :     printf("\nresult: %d %s\n", result, msg);
     168           1 :     TEST_CHECK(result == GrB_INVALID_VALUE);
     169             : 
     170           1 :     OK(LAGraph_Delete(&G, msg));
     171           1 :     TEST_CHECK(G == NULL);
     172             : 
     173             :     // bad graph, G->A is null
     174           1 :     OK(LAGraph_New(&G, NULL, LAGraph_ADJACENCY_UNDIRECTED, msg));
     175           1 :     result = LAGr_MarkovClustering(&c, e, i, prune_thresh, conv_thresh,
     176             :                                    max_iter, G, msg);
     177           1 :     printf("\nresult: %d %s\n", result, msg);
     178           1 :     TEST_CHECK(result == LAGRAPH_INVALID_GRAPH);
     179             : 
     180           1 :     OK(LAGraph_Delete(&G, msg));
     181           1 :     TEST_CHECK(G == NULL);
     182             : 
     183           1 :     LAGraph_Finalize(msg);
     184             : #endif
     185           1 : }
     186             : 
     187             : //****************************************************************************
     188             : 
     189             : TEST_LIST = {{"mcl", test_mcl},
     190             :              {"mcl_errors", test_errors},
     191             :              {NULL, NULL}};