Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_KTruss: k-truss subgraph
       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             : // LAGraph_KTruss: k-truss subgraph.
      19             : 
      20             : // Given a symmetric graph A with no-self edges, LAGraph_KTruss finds the
      21             : // k-truss subgraph of A.
      22             : 
      23             : // The graph G must be undirected, or have an adjacency matrix with symmetric
      24             : // structure.  Only the structure of G->A is considered.  Its values are
      25             : // ignored.  G must not have any self-edges.
      26             : 
      27             : // The output matrix C is the k-truss subgraph of A.  Its edges are a subset of
      28             : // G->A.  Each edge in C is part of at least k-2 triangles in C.  The structure
      29             : // of C is the adjacency matrix of the k-truss subgraph of A.  The edge weights
      30             : // of C are the support of each edge.  That is, C(i,j)=nt if the edge (i,j) is
      31             : // part of nt triangles in C.  All edges in C have support of at least k-2.
      32             : // The total number of triangles in C is sum(C)/6.  C is returned as symmetric
      33             : // with a zero-free diagonal.
      34             : 
      35             : #define LG_FREE_ALL GrB_free (&C) ;
      36             : #include "LG_internal.h"
      37             : #include "LAGraphX.h"
      38             : 
      39             : //------------------------------------------------------------------------------
      40             : // LAGraph_KTruss: find the k-truss subgraph of a graph
      41             : //------------------------------------------------------------------------------
      42             : 
      43          84 : int LAGraph_KTruss              // compute the k-truss of a graph
      44             : (
      45             :     // outputs:
      46             :     GrB_Matrix *C_handle,       // output k-truss subgraph, C
      47             :     // inputs:
      48             :     LAGraph_Graph G,            // input graph
      49             :     uint32_t k,                 // find the k-truss, where k >= 3
      50             :     char *msg
      51             : )
      52             : {
      53             : 
      54             :     //--------------------------------------------------------------------------
      55             :     // check inputs
      56             :     //--------------------------------------------------------------------------
      57             : 
      58          84 :     LG_CLEAR_MSG ;
      59          84 :     GrB_Matrix C = NULL ;
      60          84 :     LG_ASSERT (C_handle != NULL, GrB_NULL_POINTER) ;
      61          83 :     (*C_handle) = NULL ;
      62          83 :     LG_ASSERT_MSG (k >= 3, GrB_INVALID_VALUE, "k invalid") ;
      63          82 :     LG_TRY (LAGraph_CheckGraph (G, msg)) ;
      64             : 
      65          81 :     if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
      66           9 :        (G->kind == LAGraph_ADJACENCY_DIRECTED &&
      67           9 :         G->is_symmetric_structure == LAGraph_TRUE))
      68             :     {
      69             :         // the structure of A is known to be symmetric
      70             :         ;
      71             :     }
      72             :     else
      73             :     {
      74             :         // A is not known to be symmetric
      75           1 :         LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
      76             :     }
      77             : 
      78             :     // no self edges can be present
      79          80 :     LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
      80             : 
      81             :     //--------------------------------------------------------------------------
      82             :     // initializations
      83             :     //--------------------------------------------------------------------------
      84             : 
      85             :     GrB_Index n ;
      86          79 :     GrB_Matrix S = G->A ;
      87          79 :     GRB_TRY (GrB_Matrix_nrows (&n, S)) ;
      88          79 :     GRB_TRY (GrB_Matrix_new (&C, GrB_UINT32, n, n)) ;
      89             :     GrB_Index nvals, nvals_last ;
      90          79 :     GRB_TRY (GrB_Matrix_nvals (&nvals_last, S)) ;
      91             : 
      92             :     //--------------------------------------------------------------------------
      93             :     // find the k-truss of G->A
      94             :     //--------------------------------------------------------------------------
      95             : 
      96             :     while (true)
      97             :     {
      98             :         // C{S} = S*S'
      99         327 :         GRB_TRY (GrB_mxm (C, S, NULL, LAGraph_plus_one_uint32, S, S,
     100             :             GrB_DESC_RST1)) ;
     101             :         // keep entries in C that are >= k-2
     102         327 :         GRB_TRY (GrB_select (C, NULL, NULL, GrB_VALUEGE_UINT32, C, k-2, NULL)) ;
     103             :         // return if the k-truss has been found
     104         327 :         GRB_TRY (GrB_Matrix_nvals (&nvals, C)) ;
     105         327 :         if (nvals == nvals_last)
     106             :         {
     107          79 :             (*C_handle) = C ;
     108          79 :             return (GrB_SUCCESS) ;
     109             :         }
     110             :         // advance to the next step
     111         248 :         nvals_last = nvals ;
     112         248 :         S = C ;
     113             :     }
     114             : }