Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGr_SortByDegree: sort a graph by its row or column degree
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 : // LAGr_SortByDegree computes a permutation vector P that sorts a graph
19 : // by degree (either row or column degree of its adjacency matrix A).
20 : // If G is undirected, or if G is directed but is known to have a symmetric
21 : // adjacency matrix, then G->out_degree is used (and byout is ignored).
22 : // Otherwise, if G->out_degree is used if byout is true, and G->in_degree is
23 : // used if byout is false.
24 :
25 : // G->out_degree or G->in_degree must first be computed. An error is returned
26 : // if the required degree vector has not yet been computed. See
27 : // LAGraph_Cached_OutDegree and LAGraph_Cached_InDegree.
28 :
29 : // The permutation is in ascending order of degree if ascending is true, and
30 : // in descending order otherwise.
31 :
32 : // Ties are broken by the node id, so the sort is always predicable. Lower
33 : // numbered rows/columns always appear before higher ones, if they have the
34 : // same degree.
35 :
36 : // The output is a permutation P where P [k] = i if row i is the kth row in
37 : // the permutation (or P [k] = j if column j is the kth column in the
38 : // permutation, with byout false).
39 :
40 : #define LG_FREE_WORK \
41 : { \
42 : LAGraph_Free ((void **) &W, NULL) ; \
43 : LAGraph_Free ((void **) &D, NULL) ; \
44 : }
45 :
46 : #define LG_FREE_ALL \
47 : { \
48 : LG_FREE_WORK ; \
49 : LAGraph_Free ((void **) &P, NULL) ; \
50 : }
51 :
52 : #include "LG_internal.h"
53 :
54 2179 : int LAGr_SortByDegree
55 : (
56 : // output:
57 : int64_t **P_handle, // permutation vector of size n
58 : // input:
59 : const LAGraph_Graph G, // graph of n nodes
60 : bool byout, // if true, sort G->out_degree, else G->in_degree
61 : bool ascending, // sort in ascending or descending order
62 : char *msg
63 : )
64 : {
65 :
66 : //--------------------------------------------------------------------------
67 : // check inputs
68 : //--------------------------------------------------------------------------
69 :
70 2179 : LG_CLEAR_MSG ;
71 2179 : int64_t *P = NULL ;
72 2179 : int64_t *W = NULL ;
73 2179 : int64_t *D = NULL ;
74 2179 : LG_ASSERT_MSG (P_handle != NULL, GrB_NULL_POINTER, "&P != NULL") ;
75 2178 : (*P_handle) = NULL ;
76 2178 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
77 :
78 : GrB_Vector Degree ;
79 :
80 2177 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
81 2048 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
82 2048 : G->is_symmetric_structure == LAGraph_TRUE))
83 : {
84 : // the structure of A is known to be symmetric
85 2081 : Degree = G->out_degree ;
86 : }
87 : else
88 : {
89 : // A is not known to be symmetric
90 96 : Degree = (byout) ? G->out_degree : G->in_degree ;
91 : }
92 :
93 2177 : LG_ASSERT_MSG (Degree != NULL, LAGRAPH_NOT_CACHED, "degree unknown") ;
94 :
95 : //--------------------------------------------------------------------------
96 : // decide how many threads to use
97 : //--------------------------------------------------------------------------
98 :
99 : GrB_Index n ;
100 2176 : GRB_TRY (GrB_Vector_size (&n, Degree)) ;
101 :
102 : #define CHUNK (64*1024)
103 2176 : int nthreads = LG_nthreads_outer * LG_nthreads_inner ;
104 2176 : nthreads = LAGRAPH_MIN (nthreads, n/CHUNK) ;
105 2176 : nthreads = LAGRAPH_MAX (nthreads, 1) ;
106 :
107 : //--------------------------------------------------------------------------
108 : // allocate result and workspace
109 : //--------------------------------------------------------------------------
110 :
111 2176 : LG_TRY (LAGraph_Malloc ((void **) &P, n, sizeof (int64_t), msg)) ;
112 2120 : LG_TRY (LAGraph_Malloc ((void **) &D, n, sizeof (int64_t), msg)) ;
113 2064 : LG_TRY (LAGraph_Malloc ((void **) &W, 2*n, sizeof (int64_t), msg)) ;
114 2008 : int64_t *W0 = W ;
115 2008 : int64_t *W1 = W + n ;
116 :
117 : //--------------------------------------------------------------------------
118 : // construct the pair [D,P] to sort
119 : //--------------------------------------------------------------------------
120 :
121 : int64_t k;
122 : #pragma omp parallel for num_threads(nthreads) schedule(static)
123 1495576 : for (k = 0 ; k < n ; k++)
124 : {
125 1493568 : D [k] = 0 ;
126 1493568 : P [k] = k ;
127 : }
128 :
129 : // extract the degrees
130 2008 : GrB_Index nvals = n ;
131 2008 : GRB_TRY (GrB_Vector_extractTuples ((GrB_Index *) W0, W1, &nvals, Degree)) ;
132 :
133 1997 : if (ascending)
134 : {
135 : // sort [D,P] in ascending order of degree, tie-breaking on P
136 : #pragma omp parallel for num_threads(nthreads) schedule(static)
137 755741 : for (k = 0 ; k < nvals ; k++)
138 : {
139 753960 : D [W0 [k]] = W1 [k] ;
140 : }
141 : }
142 : else
143 : {
144 : // sort [D,P] in descending order of degree, tie-breaking on P
145 : #pragma omp parallel for num_threads(nthreads) schedule(static)
146 37756 : for (k = 0 ; k < nvals ; k++)
147 : {
148 37540 : D [W0 [k]] = -W1 [k] ;
149 : }
150 : }
151 :
152 1997 : LG_TRY (LAGraph_Free ((void **) &W, NULL)) ;
153 :
154 : //--------------------------------------------------------------------------
155 : // sort by degrees, with ties by node id
156 : //--------------------------------------------------------------------------
157 :
158 1997 : LG_TRY (LG_msort2 (D, P, n, msg)) ;
159 :
160 : //--------------------------------------------------------------------------
161 : // free workspace and return result
162 : //--------------------------------------------------------------------------
163 :
164 1997 : LG_FREE_WORK ;
165 1997 : (*P_handle) = P ;
166 1997 : return (GrB_SUCCESS) ;
167 : }
|
