Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LG_check_mis: test if iset is a maximal independent set
       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             : #define LG_FREE_WORK                    \
      19             : {                                       \
      20             :     GrB_free (&C) ;                     \
      21             :     LAGraph_Free ((void **) &I, NULL) ; \
      22             :     LAGraph_Free ((void **) &X, NULL) ; \
      23             : }
      24             : 
      25             : #define LG_FREE_ALL                     \
      26             : {                                       \
      27             :     LG_FREE_WORK ;                      \
      28             : }
      29             : 
      30             : #include "LG_internal.h"
      31             : #include "LG_test.h"
      32             : 
      33         339 : int LG_check_mis        // check if iset is a valid MIS of A
      34             : (
      35             :     GrB_Matrix A,
      36             :     GrB_Vector iset,
      37             :     GrB_Vector ignore_node,     // if NULL, no nodes are ignored.  otherwise,
      38             :                         // ignore_node(i)=true if node i is to be ignored, and
      39             :                         // not added to the independent set.
      40             :     char *msg
      41             : )
      42             : {
      43             : 
      44             :     //--------------------------------------------------------------------------
      45             :     // check and report the results
      46             :     //--------------------------------------------------------------------------
      47             : 
      48         339 :     LG_CLEAR_MSG ;
      49         339 :     GrB_Matrix C = NULL ;
      50         339 :     GrB_Index *I = NULL ;
      51         339 :     bool *X = NULL ;
      52             : 
      53             :     GrB_Index n ;
      54         339 :     GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
      55             : 
      56             :     int64_t isize ;
      57         339 :     GRB_TRY (GrB_Vector_reduce_INT64 (&isize, NULL, GrB_PLUS_MONOID_INT64,
      58             :         iset, NULL)) ;
      59             : 
      60             :     GrB_Index nvals ;
      61         339 :     GRB_TRY (GrB_Vector_nvals (&nvals, iset)) ;
      62         339 :     LAGRAPH_TRY (LAGraph_Malloc ((void **) &I, nvals, sizeof (GrB_Index), msg));
      63         339 :     LAGRAPH_TRY (LAGraph_Malloc ((void **) &X, nvals, sizeof (bool), msg)) ;
      64             : 
      65         339 :     GRB_TRY (GrB_Vector_extractTuples_BOOL (I, X, &nvals, iset)) ;
      66             : 
      67             :     // I [0..isize-1] is the independent set
      68         339 :     isize = 0 ;
      69       46320 :     for (int64_t k = 0 ; k < nvals ; k++)
      70             :     {
      71       45981 :         if (X [k])
      72             :         {
      73       45981 :             I [isize++] = I [k] ;
      74             :         }
      75             :     }
      76             : 
      77         339 :     LAGraph_Free ((void **) &X, NULL) ;
      78             : 
      79             :     // printf ("independent set found: %.16g of %.16g nodes\n",
      80             :     // (double) isize, (double) n) ;
      81             : 
      82             :     //--------------------------------------------------------------------------
      83             :     // verify the result
      84             :     //--------------------------------------------------------------------------
      85             : 
      86             :     // C = A(I,I) must be empty, except for diagonal entries
      87         339 :     GRB_TRY (GrB_Matrix_new (&C, GrB_BOOL, isize, isize)) ;
      88         339 :     GRB_TRY (GrB_Matrix_extract (C, NULL, NULL, A, I, isize, I, isize, NULL)) ;
      89         339 :     GRB_TRY (GrB_select (C, NULL, NULL, GrB_OFFDIAG, C, 0, NULL)) ;
      90         339 :     GRB_TRY (GrB_Matrix_nvals (&nvals, C)) ;
      91         339 :     LG_ASSERT_MSG (nvals == 0, -1, "error!  A(I,I) has an edge!\n") ;
      92         339 :     GrB_Matrix_free (&C) ;
      93             : 
      94             :     // now check if all other nodes are adjacent to the iset
      95             : 
      96             :     // e = iset
      97         339 :     GrB_Vector e = NULL ;
      98         339 :     GRB_TRY (GrB_Vector_dup (&e, iset)) ;
      99             : 
     100             :     // e = e || ignore_node
     101         339 :     int64_t ignored = 0 ;
     102         339 :     if (ignore_node != NULL)
     103             :     {
     104         160 :         GRB_TRY (GrB_eWiseAdd (e, NULL, NULL, GrB_LOR, e, ignore_node, NULL)) ;
     105         160 :         GRB_TRY (GrB_reduce (&ignored, NULL, GrB_PLUS_MONOID_INT64,
     106             :             ignore_node, NULL)) ;
     107             :     }
     108             : 
     109             :     // e = (e || A*iset), using the structural semiring
     110         339 :     GRB_TRY (GrB_vxm (e, NULL, GrB_LOR, LAGraph_any_one_bool, iset, A, NULL)) ;
     111             : 
     112             :     // drop explicit zeros from e
     113             :     // e<e.replace> = e
     114         339 :     GRB_TRY (GrB_assign (e, e, NULL, e, GrB_ALL, n, GrB_DESC_R)) ;
     115             : 
     116         339 :     GRB_TRY (GrB_Vector_nvals (&nvals, e)) ;
     117         339 :     GrB_Vector_free (&e) ;
     118         339 :     LG_ASSERT_MSG (nvals == n, -1, "error! A (I,I is not maximal!\n") ;
     119             : 
     120         339 :     LAGraph_Free ((void **) &I, NULL) ;
     121             : 
     122         339 :     printf ("maximal independent set OK %.16g of %.16g nodes",
     123             :         (double) isize, (double) n) ;
     124         339 :     if (ignored > 0) printf (" (%g nodes ignored)\n", (double) ignored) ;
     125         339 :     printf ("\n") ;
     126         339 :     return (GrB_SUCCESS) ;
     127             : }