Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_CheckGraph: check if a graph is valid
       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 "LG_internal.h"
      19             : 
      20       33187 : int LAGraph_CheckGraph
      21             : (
      22             :     // input/output:
      23             :     LAGraph_Graph G,    // graph to check
      24             :     char *msg
      25             : )
      26             : {
      27             : 
      28             :     //--------------------------------------------------------------------------
      29             :     // clear the msg and check basic components
      30             :     //--------------------------------------------------------------------------
      31             : 
      32       33187 :     LG_CLEAR_MSG_AND_BASIC_ASSERT (G, msg) ;
      33       33172 :     GrB_Matrix A = G->A ;
      34       33172 :     LAGraph_Kind kind = G->kind ;
      35             : 
      36             :     //--------------------------------------------------------------------------
      37             :     // ensure the matrix is square for directed or undirected graphs
      38             :     //--------------------------------------------------------------------------
      39             : 
      40             :     GrB_Index nrows, ncols ;
      41       33172 :     if (kind == LAGraph_ADJACENCY_UNDIRECTED ||
      42             :         kind == LAGraph_ADJACENCY_DIRECTED)
      43             :     {
      44       33172 :         GRB_TRY (GrB_Matrix_nrows (&nrows, A)) ;
      45       33172 :         GRB_TRY (GrB_Matrix_ncols (&ncols, A)) ;
      46       33172 :         LG_ASSERT_MSG (nrows == ncols, LAGRAPH_INVALID_GRAPH,
      47             :             "adjacency matrix must be square") ;
      48             :     }
      49             : 
      50             :     #if LAGRAPH_SUITESPARSE
      51             :         // only by-row format is supported when using SuiteSparse
      52             :         GxB_Format_Value fmt ;
      53       33171 :         GRB_TRY (GxB_get (A, GxB_FORMAT, &fmt)) ;
      54       33171 :         LG_ASSERT_MSG (fmt == GxB_BY_ROW, LAGRAPH_INVALID_GRAPH,
      55             :             "only by-row format supported") ;
      56             :     #endif
      57             : 
      58             :     //--------------------------------------------------------------------------
      59             :     // check the cached properties
      60             :     //--------------------------------------------------------------------------
      61             : 
      62       33170 :     GrB_Matrix AT = G->AT ;
      63       33170 :     if (AT != NULL)
      64             :     {
      65             :         GrB_Index nrows2, ncols2;
      66        6464 :         GRB_TRY (GrB_Matrix_nrows (&nrows2, AT)) ;
      67        6458 :         GRB_TRY (GrB_Matrix_ncols (&ncols2, AT)) ;
      68        6458 :         LG_ASSERT_MSG (nrows == ncols2 && ncols == nrows2,
      69             :             LAGRAPH_INVALID_GRAPH, "G->AT matrix has the wrong dimensions") ;
      70             : 
      71             :         #if LAGRAPH_SUITESPARSE
      72             :             // only by-row format is supported when using SuiteSparse
      73             :             GxB_Format_Value fmt ;
      74        6456 :             GRB_TRY (GxB_get (AT, GxB_FORMAT, &fmt)) ;
      75        6456 :             LG_ASSERT_MSG (fmt == GxB_BY_ROW,
      76             :                 LAGRAPH_INVALID_GRAPH, "only by-row format supported") ;
      77             :         #endif
      78             : 
      79             :         // ensure the types of A and AT are the same
      80             :         char atype [LAGRAPH_MAX_NAME_LEN] ;
      81             :         char ttype [LAGRAPH_MAX_NAME_LEN] ;
      82        6454 :         LG_TRY (LAGraph_Matrix_TypeName (atype, A, msg)) ;
      83        6454 :         LG_TRY (LAGraph_Matrix_TypeName (ttype, AT, msg)) ;
      84        6454 :         LG_ASSERT_MSG (MATCHNAME (atype, ttype),
      85             :             LAGRAPH_INVALID_GRAPH, "A and AT must have the same type") ;
      86             :     }
      87             : 
      88       33164 :     GrB_Vector out_degree = G->out_degree ;
      89       33164 :     if (out_degree != NULL)
      90             :     {
      91             :         GrB_Index m ;
      92       17444 :         GRB_TRY (GrB_Vector_size (&m, out_degree)) ;
      93       17442 :         LG_ASSERT_MSG (m == nrows, LAGRAPH_INVALID_GRAPH,
      94             :             "out_degree invalid size") ;
      95             :         char rtype [LAGRAPH_MAX_NAME_LEN] ;
      96       17441 :         LG_TRY (LAGraph_Vector_TypeName (rtype, out_degree, msg)) ;
      97       17441 :         LG_ASSERT_MSG (MATCHNAME (rtype, "int64_t"),
      98             :             LAGRAPH_INVALID_GRAPH,
      99             :             "out_degree has wrong type; must be GrB_INT64") ;
     100             :     }
     101             : 
     102       33162 :     GrB_Vector in_degree = G->in_degree ;
     103       33162 :     if (in_degree != NULL)
     104             :     {
     105             :         GrB_Index n ;
     106        6274 :         GRB_TRY (GrB_Vector_size (&n, in_degree)) ;
     107        6272 :         LG_ASSERT_MSG (n == ncols, LAGRAPH_INVALID_GRAPH,
     108             :             "in_degree invalid size") ;
     109             :         char ctype [LAGRAPH_MAX_NAME_LEN] ;
     110        6271 :         LG_TRY (LAGraph_Vector_TypeName (ctype, in_degree, msg)) ;
     111        6271 :         LG_ASSERT_MSG (MATCHNAME (ctype, "int64_t"),
     112             :             LAGRAPH_INVALID_GRAPH,
     113             :             "in_degree has wrong type; must be GrB_INT64") ;
     114             :     }
     115             : 
     116       33160 :     return (GrB_SUCCESS) ;
     117             : }