Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_AllKTruss.c: find all k-trusses of a graph
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_AllKTruss: find all k-trusses of a graph via GraphBLAS.
19 :
20 : // Given a symmetric graph A with no-self edges, LAGraph_AllKTruss finds all
21 : // k-trusses of A.
22 :
23 : // The output matrices Cset [3..kmax-1] are the k-trusses of A. Their edges
24 : // are a subset of A. Each edge in C = Cset [k] is part of at least k-2
25 : // triangles in C. The structure of C is the adjacency matrix of the k-truss
26 : // subgraph of A. The edge weights of C are the support of each edge. That
27 : // is, C(i,j)=nt if the edge (i,j) is part of nt triangles in C. All edges in
28 : // C have support of at least k-2. The total number of triangles in C is
29 : // sum(C)/6. The number of edges in C is nnz(C)/2. C = Cset [k] is returned
30 : // as symmetric with a zero-free diagonal. Cset [kmax] is an empty matrix
31 : // since the kmax-truss is empty.
32 :
33 : // The arrays ntris, nedges, and nstepss hold the output statistics.
34 : // ntris [k] = # of triangles in the k-truss
35 : // nedges [k] = # of edges in the k-truss
36 : // nstepss [k] = # of steps required to compute the k-truss
37 :
38 : // Usage: constructs all k-trusses of A, for k = 3:kmax
39 :
40 : // int64_t kmax ;
41 : // GrB_Matrix_nrows (&n, A) ;
42 : // int64_t n4 = (n > 4) ? n : 4 ;
43 : // GrB_Matrix *Cset = LAGraph_malloc (n4, sizeof (GrB_Matrix)) ;
44 : // int64_t *ntris = LAGraph_malloc (n4, sizeof (int64_t)) ;
45 : // int64_t *nedges = LAGraph_malloc (n4, sizeof (int64_t)) ;
46 : // int64_t *nstepss = LAGraph_malloc (n4, sizeof (int64_t)) ;
47 : // int result = LAGraph_AllKTruss (&Cset, &kmax, ntris, nedges,
48 : // nstepss, G, msg) ;
49 :
50 : // todo: add experimental/benchmark/ktruss_demo.c to benchmark k-truss
51 : // and all-k-truss
52 :
53 : // todo: consider LAGraph_KTrussNext to compute the (k+1)-truss from the
54 : // k-truss
55 :
56 : #define LG_FREE_ALL \
57 : { \
58 : for (int64_t kk = 3 ; kk <= k ; kk++) \
59 : { \
60 : GrB_free (&(Cset [kk])) ; \
61 : } \
62 : }
63 :
64 : #include "LG_internal.h"
65 : #include "LAGraphX.h"
66 :
67 : //------------------------------------------------------------------------------
68 : // C = LAGraph_AllKTruss: find all k-trusses a graph
69 : //------------------------------------------------------------------------------
70 :
71 22 : int LAGraph_AllKTruss // compute all k-trusses of a graph
72 : (
73 : // outputs
74 : GrB_Matrix *Cset, // size n, output k-truss subgraphs
75 : int64_t *kmax, // smallest k where k-truss is empty
76 : int64_t *ntris, // size max(n,4), ntris [k] is #triangles in k-truss
77 : int64_t *nedges, // size max(n,4), nedges [k] is #edges in k-truss
78 : int64_t *nstepss, // size max(n,4), nstepss [k] is #steps for k-truss
79 : // input
80 : LAGraph_Graph G, // input graph
81 : char *msg
82 : )
83 : {
84 :
85 : //--------------------------------------------------------------------------
86 : // check inputs
87 : //--------------------------------------------------------------------------
88 :
89 22 : LG_CLEAR_MSG ;
90 22 : int64_t k = 0 ;
91 22 : LG_ASSERT (Cset != NULL && nstepss != NULL, GrB_NULL_POINTER) ;
92 22 : LG_ASSERT (kmax != NULL && ntris != NULL, GrB_NULL_POINTER) ;
93 21 : LG_ASSERT (nedges != NULL, GrB_NULL_POINTER) ;
94 21 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
95 :
96 20 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
97 10 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
98 10 : G->is_symmetric_structure == LAGraph_TRUE))
99 : {
100 : // the structure of A is known to be symmetric
101 : ;
102 : }
103 : else
104 : {
105 : // A is not known to be symmetric
106 1 : LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
107 : }
108 :
109 : // no self edges can be present
110 19 : LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
111 :
112 : //--------------------------------------------------------------------------
113 : // initializations
114 : //--------------------------------------------------------------------------
115 :
116 90 : for (k = 0 ; k <= 3 ; k++)
117 : {
118 72 : Cset [k] = NULL ;
119 72 : ntris [k] = 0 ;
120 72 : nedges [k] = 0 ;
121 72 : nstepss [k] = 0 ;
122 : }
123 18 : k = 3 ;
124 18 : (*kmax) = 0 ;
125 :
126 : //--------------------------------------------------------------------------
127 : // initialzations
128 : //--------------------------------------------------------------------------
129 :
130 : GrB_Index n ;
131 18 : GrB_Matrix S = G->A ;
132 18 : GRB_TRY (GrB_Matrix_nrows (&n, S)) ;
133 18 : GRB_TRY (GrB_Matrix_new (&(Cset [k]), GrB_UINT32, n, n)) ;
134 18 : GrB_Matrix C = Cset [k] ;
135 : GrB_Index nvals, nvals_last ;
136 18 : GRB_TRY (GrB_Matrix_nvals (&nvals_last, S)) ;
137 18 : int64_t nsteps = 0 ;
138 :
139 : //--------------------------------------------------------------------------
140 : // find all k-trusses
141 : //--------------------------------------------------------------------------
142 :
143 : while (true)
144 : {
145 : // C{S} = S*S'
146 434 : GRB_TRY (GrB_mxm (C, S, NULL, LAGraph_plus_one_uint32, S, S,
147 : GrB_DESC_RST1)) ;
148 : // keep entries in C that are >= k-2
149 434 : GRB_TRY (GrB_select (C, NULL, NULL, GrB_VALUEGE_UINT32, C, k-2, NULL)) ;
150 434 : nsteps++ ;
151 : // check if k-truss has been found
152 434 : GRB_TRY (GrB_Matrix_nvals (&nvals, C)) ;
153 434 : if (nvals == nvals_last)
154 : {
155 : // k-truss has been found
156 96 : int64_t nt = 0 ;
157 114 : GRB_TRY (GrB_reduce (&nt, NULL, GrB_PLUS_MONOID_INT64, C, NULL)) ;
158 96 : ntris [k] = nt / 6 ;
159 96 : nedges [k] = nvals / 2 ;
160 96 : nstepss [k] = nsteps ;
161 96 : nsteps = 0 ;
162 96 : if (nvals == 0)
163 : {
164 : // this is the last k-truss
165 18 : (*kmax) = k ;
166 18 : return (GrB_SUCCESS) ;
167 : }
168 78 : S = C ; // S = current k-truss for k+1 iteration
169 78 : k++ ; // advance to the next k-tryss
170 78 : GRB_TRY (GrB_Matrix_new (&(Cset [k]), GrB_UINT32, n, n)) ;
171 78 : C = Cset [k] ; // C = new matrix for next k-truss
172 : }
173 : else
174 : {
175 : // advance to the next step, still computing the current k-truss
176 338 : nvals_last = nvals ;
177 338 : S = C ;
178 : }
179 : }
180 : }
|
