Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_Cached_IsSymmetricStructure: determine G->is_symmetric_structure
       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             : // Also computes G->AT if not already computed, if G is not an undirected
      19             : // graph and G->A is square.
      20             : 
      21             : #define LG_FREE_WORK        \
      22             : {                           \
      23             :     GrB_free (&S1) ;        \
      24             :     GrB_free (&S2) ;        \
      25             :     GrB_free (&C) ;         \
      26             : }
      27             : 
      28             : #include "LG_internal.h"
      29             : 
      30        1658 : int LAGraph_Cached_IsSymmetricStructure
      31             : (
      32             :     // input/output:
      33             :     LAGraph_Graph G,    // graph to determine the symmetry of structure of A
      34             :     char *msg
      35             : )
      36             : {
      37             : 
      38             :     //--------------------------------------------------------------------------
      39             :     // clear msg and check G
      40             :     //--------------------------------------------------------------------------
      41             : 
      42        1658 :     GrB_Matrix C = NULL, S1 = NULL, S2 = NULL ;
      43        1658 :     LG_CLEAR_MSG_AND_BASIC_ASSERT (G, msg) ;
      44             : 
      45        1657 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED)
      46             :     {
      47             :         // assume A is symmetric for an undirected graph
      48         349 :         G->is_symmetric_structure = LAGraph_TRUE ;
      49         349 :         return (GrB_SUCCESS) ;
      50             :     }
      51             : 
      52        1308 :     if (G->is_symmetric_structure != LAGRAPH_UNKNOWN)
      53             :     {
      54             :         // cached symmetric property is already known
      55         207 :         return (GrB_SUCCESS) ;
      56             :     }
      57             : 
      58             :     //--------------------------------------------------------------------------
      59             :     // determine the size of A
      60             :     //--------------------------------------------------------------------------
      61             : 
      62        1101 :     GrB_Matrix A = G->A ;
      63             :     GrB_Index n, ncols ;
      64        1101 :     GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
      65        1101 :     GRB_TRY (GrB_Matrix_ncols (&ncols, A)) ;
      66        1101 :     if (n != ncols)
      67             :     {
      68             :         // A is rectangular and thus cannot be symmetric
      69          16 :         G->is_symmetric_structure = LAGraph_FALSE ;
      70          16 :         return (GrB_SUCCESS) ;
      71             :     }
      72             : 
      73             :     //--------------------------------------------------------------------------
      74             :     // compute the transpose, if not already computed
      75             :     //--------------------------------------------------------------------------
      76             : 
      77        1085 :     if (G->AT == NULL)
      78             :     {
      79         578 :         LG_TRY (LAGraph_Cached_AT (G, msg)) ;
      80             :     }
      81             : 
      82             :     //--------------------------------------------------------------------------
      83             :     // check if the structure of A and AT are the same
      84             :     //--------------------------------------------------------------------------
      85             : 
      86         827 :     GRB_TRY (GrB_Matrix_new (&C, GrB_BOOL, n, n)) ;
      87             : 
      88             :     // C(i,j) = 1 if both A(i,j) and AT(i,j) exist
      89         625 :     GRB_TRY (GrB_eWiseMult (C, NULL, NULL, GrB_ONEB_BOOL, A, G->AT, NULL)) ;
      90             : 
      91             :     GrB_Index nvals1, nvals2 ;
      92         478 :     GRB_TRY (GrB_Matrix_nvals (&nvals1, C)) ;
      93         478 :     GRB_TRY (GrB_Matrix_nvals (&nvals2, A)) ;
      94         478 :     G->is_symmetric_structure =
      95         478 :         (nvals1 == nvals2) ? LAGraph_TRUE : LAGraph_FALSE ;
      96             : 
      97             :     //--------------------------------------------------------------------------
      98             :     // free workspace and return result
      99             :     //--------------------------------------------------------------------------
     100             : 
     101         478 :     LG_FREE_WORK ;
     102         478 :     return (GrB_SUCCESS) ;
     103             : }