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 1538 : 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 1538 : LG_CLEAR_MSG ;
71 1538 : int64_t *P = NULL ;
72 1538 : int64_t *W = NULL ;
73 1538 : int64_t *D = NULL ;
74 1538 : LG_ASSERT_MSG (P_handle != NULL, GrB_NULL_POINTER, "&P != NULL") ;
75 1537 : (*P_handle) = NULL ;
76 1537 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
77 :
78 : GrB_Vector Degree ;
79 :
80 1536 : if (G->kind == LAGraph_ADJACENCY_UNDIRECTED ||
81 1441 : (G->kind == LAGraph_ADJACENCY_DIRECTED &&
82 1441 : G->is_symmetric_structure == LAGraph_TRUE))
83 : {
84 : // the structure of A is known to be symmetric
85 1440 : 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 1536 : 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 1535 : GRB_TRY (GrB_Vector_size (&n, Degree)) ;
101 :
102 : #define CHUNK (64*1024)
103 1535 : int nthreads = LG_nthreads_outer * LG_nthreads_inner ;
104 1535 : nthreads = LAGRAPH_MIN (nthreads, n/CHUNK) ;
105 1535 : nthreads = LAGRAPH_MAX (nthreads, 1) ;
106 :
107 : //--------------------------------------------------------------------------
108 : // allocate result and workspace
109 : //--------------------------------------------------------------------------
110 :
111 1535 : LG_TRY (LAGraph_Malloc ((void **) &P, n, sizeof (int64_t), msg)) ;
112 1490 : LG_TRY (LAGraph_Malloc ((void **) &D, n, sizeof (int64_t), msg)) ;
113 1445 : LG_TRY (LAGraph_Malloc ((void **) &W, 2*n, sizeof (int64_t), msg)) ;
114 1400 : int64_t *W0 = W ;
115 1400 : 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 808490 : for (k = 0 ; k < n ; k++)
124 : {
125 807090 : D [k] = 0 ;
126 807090 : P [k] = k ;
127 : }
128 :
129 : // extract the degrees
130 1400 : GrB_Index nvals = n ;
131 1400 : GRB_TRY (GrB_Vector_extractTuples ((GrB_Index *) W0, W1, &nvals, Degree)) ;
132 :
133 1400 : 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 706700 : for (k = 0 ; k < nvals ; k++)
138 : {
139 705446 : 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 101686 : for (k = 0 ; k < nvals ; k++)
147 : {
148 101540 : D [W0 [k]] = -W1 [k] ;
149 : }
150 : }
151 :
152 1400 : LG_TRY (LAGraph_Free ((void **) &W, NULL)) ;
153 :
154 : //--------------------------------------------------------------------------
155 : // sort by degrees, with ties by node id
156 : //--------------------------------------------------------------------------
157 :
158 1400 : LG_TRY (LG_msort2 (D, P, n, msg)) ;
159 :
160 : //--------------------------------------------------------------------------
161 : // free workspace and return result
162 : //--------------------------------------------------------------------------
163 :
164 1400 : LG_FREE_WORK ;
165 1400 : (*P_handle) = P ;
166 1400 : return (GrB_SUCCESS) ;
167 : }
|
