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 : // GrB_Matrix *Cset = array of size max(n,4)
43 : // int64_t *ntris = array of size max(n,4)
44 : // int64_t *nedges = array of size max(n,4)
45 : // int64_t *nstepss = array of size max(n,4)
46 : // int result = LAGraph_AllKTruss (&Cset, &kmax, ntris, nedges,
47 : // nstepss, G, msg) ;
48 :
49 : // todo: add experimental/benchmark/ktruss_demo.c to benchmark k-truss
50 : // and all-k-truss
51 :
52 : // todo: consider LAGraph_KTrussNext to compute the (k+1)-truss from the
53 : // k-truss
54 :
55 : // TODO: ready for src
56 :
57 : #define LG_FREE_ALL \
58 : { \
59 : for (int64_t kk = 3 ; kk <= k ; kk++) \
60 : { \
61 : GrB_free (&(Cset [kk])) ; \
62 : } \
63 : }
64 :
65 : #include "LG_internal.h"
66 : #include "LAGraphX.h"
67 :
68 : //------------------------------------------------------------------------------
69 : // C = LAGraph_AllKTruss: find all k-trusses a graph
70 : //------------------------------------------------------------------------------
71 :
72 22 : int LAGraph_AllKTruss // compute all k-trusses of a graph
73 : (
74 : // outputs
75 : GrB_Matrix *Cset, // size n, output k-truss subgraphs
76 : int64_t *kmax, // smallest k where k-truss is empty
77 : int64_t *ntris, // size max(n,4), ntris [k] is #triangles in k-truss
78 : int64_t *nedges, // size max(n,4), nedges [k] is #edges in k-truss
79 : int64_t *nstepss, // size max(n,4), nstepss [k] is #steps for k-truss
80 : // input
81 : LAGraph_Graph G, // input graph
82 : char *msg
83 : )
84 : {
85 :
86 : //--------------------------------------------------------------------------
87 : // check inputs
88 : //--------------------------------------------------------------------------
89 :
90 22 : LG_CLEAR_MSG ;
91 22 : int64_t k = 0 ;
92 22 : LG_ASSERT (Cset != NULL && nstepss != NULL, GrB_NULL_POINTER) ;
93 22 : LG_ASSERT (kmax != NULL && ntris != NULL, GrB_NULL_POINTER) ;
94 21 : LG_ASSERT (nedges != NULL, GrB_NULL_POINTER) ;
95 21 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
96 :
97 20 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
98 10 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
99 10 : G->is_symmetric_structure == LAGraph_TRUE))
100 : {
101 : // the structure of A is known to be symmetric
102 : ;
103 : }
104 : else
105 : {
106 : // A is not known to be symmetric
107 1 : LG_ASSERT_MSG (false, -1005, "G->A must be symmetric") ;
108 : }
109 :
110 : // no self edges can be present
111 19 : LG_ASSERT_MSG (G->nself_edges == 0, -1004, "G->nself_edges must be zero") ;
112 :
113 : //--------------------------------------------------------------------------
114 : // initializations
115 : //--------------------------------------------------------------------------
116 :
117 90 : for (k = 0 ; k <= 3 ; k++)
118 : {
119 72 : Cset [k] = NULL ;
120 72 : ntris [k] = 0 ;
121 72 : nedges [k] = 0 ;
122 72 : nstepss [k] = 0 ;
123 : }
124 18 : k = 3 ;
125 18 : (*kmax) = 0 ;
126 :
127 : //--------------------------------------------------------------------------
128 : // initialzations
129 : //--------------------------------------------------------------------------
130 :
131 : GrB_Index n ;
132 18 : GrB_Matrix S = G->A ;
133 18 : GRB_TRY (GrB_Matrix_nrows (&n, S)) ;
134 18 : GRB_TRY (GrB_Matrix_new (&(Cset [k]), GrB_UINT32, n, n)) ;
135 18 : GrB_Matrix C = Cset [k] ;
136 : GrB_Index nvals, nvals_last ;
137 18 : GRB_TRY (GrB_Matrix_nvals (&nvals_last, S)) ;
138 18 : int64_t nsteps = 0 ;
139 :
140 : //--------------------------------------------------------------------------
141 : // find all k-trusses
142 : //--------------------------------------------------------------------------
143 :
144 : #if 0
145 : int mtx = 0 ;
146 : #endif
147 :
148 : while (true)
149 : {
150 : #if 0
151 : // dump the matrix S to a file
152 : uint64_t snvals ;
153 : GRB_TRY (GrB_Matrix_nvals (&snvals, S)) ;
154 : char filename [2000] ;
155 : sprintf (filename, "mtx_%04d.mtx", mtx) ;
156 : FILE *f = fopen (filename, "w") ;
157 : printf ("%s: with %" PRId64 " values\n", filename, snvals) ;
158 : LAGraph_MMWrite (S, f, NULL, msg) ;
159 : fclose (f) ;
160 : mtx++ ;
161 : #endif
162 :
163 : // C{S} = S*S'
164 434 : GRB_TRY (GrB_mxm (C, S, NULL, LAGraph_plus_one_uint32, S, S,
165 : GrB_DESC_RST1)) ;
166 : // keep entries in C that are >= k-2
167 434 : GRB_TRY (GrB_select (C, NULL, NULL, GrB_VALUEGE_UINT32, C, k-2, NULL)) ;
168 434 : nsteps++ ;
169 : // check if k-truss has been found
170 434 : GRB_TRY (GrB_Matrix_nvals (&nvals, C)) ;
171 434 : if (nvals == nvals_last)
172 : {
173 : // k-truss has been found
174 96 : int64_t nt = 0 ;
175 114 : GRB_TRY (GrB_reduce (&nt, NULL, GrB_PLUS_MONOID_INT64, C, NULL)) ;
176 96 : ntris [k] = nt / 6 ;
177 96 : nedges [k] = nvals / 2 ;
178 96 : nstepss [k] = nsteps ;
179 96 : nsteps = 0 ;
180 96 : if (nvals == 0)
181 : {
182 : // this is the last k-truss
183 18 : (*kmax) = k ;
184 18 : return (GrB_SUCCESS) ;
185 : }
186 78 : S = C ; // S = current k-truss for k+1 iteration
187 78 : k++ ; // advance to the next k-tryss
188 78 : GRB_TRY (GrB_Matrix_new (&(Cset [k]), GrB_UINT32, n, n)) ;
189 78 : C = Cset [k] ; // C = new matrix for next k-truss
190 : }
191 : else
192 : {
193 : // advance to the next step, still computing the current k-truss
194 338 : nvals_last = nvals ;
195 338 : S = C ;
196 : }
197 : }
198 : }
|
