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