Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_ExactDiameter: Graph Diameter Computation
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2021 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : // See additional acknowledgments in the LICENSE file,
8 : // or contact permission@sei.cmu.edu for the full terms.
9 :
10 : // Contributed by Alexandra Goff
11 :
12 : //------------------------------------------------------------------------------
13 :
14 : // TODO: almost ready for src; says it's not vanilla but should be OK
15 :
16 : // Takes in a graph and finds the diameter
17 : // and optionally also the peripheral nodes of the graph
18 :
19 : // Outputs:
20 : // Diameter returns the diameter of the graph
21 : // If not set to NULL, peripheral will be a vector with n elements
22 : // index i of peripheral is the diameter if it's a peripheral node or nothing if not
23 : // If not set to NULL, eccentricity will be a vector with the eccentricity of each
24 : // node in the graph
25 :
26 : // Inputs:
27 : // G is the graph to be analyzed
28 : // k is the number of nodes in each batch of the BFS,
29 : // higher k value allows for more parallelization at the cost of more space used
30 : // msg is a buffer for error messages
31 :
32 : #define LG_FREE_WORK \
33 : { \
34 : GrB_free (&srcEcc) ; \
35 : GrB_free (&ecc) ; \
36 : GrB_free (&level) ; \
37 : GrB_free (&srcs) ; \
38 : LAGraph_Free((void**) &sources, NULL); \
39 : }
40 :
41 : #define LG_FREE_ALL \
42 : { \
43 : LG_FREE_WORK ; \
44 : GrB_free (eccentricity) ; \
45 : GrB_free (&peri) ; \
46 : }
47 :
48 : #include "LG_internal.h"
49 : #include "LAGraphX.h"
50 :
51 10 : int LAGraph_ExactDiameter
52 : (
53 : // outputs:
54 : GrB_Index *diameter,
55 : GrB_Vector *peripheral,
56 : GrB_Vector *eccentricity,
57 : // inputs:
58 : const LAGraph_Graph G,
59 : GrB_Index k,
60 : char *msg
61 : )
62 : {
63 : #if LAGRAPH_SUITESPARSE
64 :
65 : //--------------------------------------------------------------------------
66 : // check inputs
67 : //--------------------------------------------------------------------------
68 :
69 10 : LG_CLEAR_MSG ;
70 10 : GrB_Vector ecc = NULL ; // the eccentricity of the nodes
71 10 : GrB_Vector peri = NULL ; // vector to store peripheral node status in
72 10 : GrB_Vector srcEcc = NULL ; // work vector to store each iteration's eccentricity in temporarily
73 10 : GrB_Matrix level = NULL; // work matrix for storing msbfs level info
74 : GrB_Index d ; // diameter
75 10 : GrB_Vector srcs = NULL ;
76 10 : GrB_Index *sources = NULL ;
77 :
78 10 : bool compute_periphery = (peripheral != NULL) ;
79 10 : if (compute_periphery ) (*peripheral) = NULL ;
80 10 : bool compute_eccentricity = (eccentricity != NULL) ;
81 10 : if (compute_eccentricity ) (*eccentricity) = NULL ;
82 10 : bool compute_diameter = (diameter != NULL) ;
83 10 : LG_ASSERT_MSG (compute_diameter, GrB_NULL_POINTER,
84 : "Diameter destination must be non-NULL") ;
85 :
86 10 : LG_TRY (LAGraph_CheckGraph (G, msg)) ;
87 :
88 : //--------------------------------------------------------------------------
89 : // get the problem size and cached properties
90 : //--------------------------------------------------------------------------
91 :
92 10 : GrB_Matrix A = G->A ;
93 :
94 : GrB_Index n; // number of nodes in the graph
95 10 : GRB_TRY (GrB_Matrix_nrows (&n, A)) ;
96 :
97 10 : GrB_Type int_type = (n > INT32_MAX) ? GrB_INT64 : GrB_INT32 ;
98 10 : GRB_TRY (GrB_Vector_new (&ecc, int_type, n)) ;
99 :
100 : //--------------------------------------------------------------------------
101 : // get eccentricity, k nodes at a time
102 : //--------------------------------------------------------------------------
103 :
104 10 : int64_t setStart = 0;
105 20 : GrB_Monoid max = (n > INT32_MAX) ?
106 10 : GrB_MAX_MONOID_INT64 : GrB_MAX_MONOID_INT32 ;
107 428 : while (setStart < n){
108 : // set up the sources for this iteration
109 : int64_t nsrcs;
110 418 : if ((setStart + k) <= n){
111 409 : nsrcs = k;
112 : } else {
113 9 : nsrcs = n - setStart;
114 : }
115 418 : GRB_TRY (GrB_Vector_new (&srcs, int_type, nsrcs)) ;
116 418 : GRB_TRY (LAGraph_Calloc((void **) &sources, nsrcs, sizeof(GrB_Index), msg)) ;
117 3712 : for (int64_t i = 0; i < nsrcs; i++){
118 3294 : GRB_TRY (GrB_Vector_setElement (srcs, setStart+i, i)) ;
119 3294 : sources[i] = setStart+i;
120 : }
121 :
122 : // run bfs to get level matrix for the sources
123 418 : GrB_free (&level) ;
124 418 : LAGRAPH_TRY (LAGraph_MultiSourceBFS (&level, NULL, G, srcs, msg)) ;
125 418 : GrB_free (&srcs) ;
126 :
127 : // populate setStart to setStart+nsrcs of ecc with the max level for each src
128 418 : GRB_TRY (GrB_Vector_new (&srcEcc, int_type, nsrcs)) ;
129 418 : GRB_TRY (GrB_reduce(srcEcc, NULL, NULL, max, level, GrB_NULL)) ;
130 418 : LAGRAPH_TRY (GrB_assign(ecc, NULL, NULL, srcEcc, sources, nsrcs, GrB_NULL)) ;
131 418 : GrB_free (&level) ;
132 418 : GrB_free (&srcEcc) ;
133 :
134 418 : LAGraph_Free((void**) &sources, NULL);
135 :
136 : // adjust setStart for next iteration
137 418 : setStart = setStart + nsrcs;
138 : }
139 :
140 :
141 : //--------------------------------------------------------------------------
142 : // determine diameter from eccentricity list
143 : //--------------------------------------------------------------------------
144 :
145 10 : GRB_TRY (GrB_reduce(&d, NULL, max, ecc, GrB_NULL)) ;
146 :
147 : //--------------------------------------------------------------------------
148 : // get peripheral nodes, if applicable
149 : //--------------------------------------------------------------------------
150 :
151 10 : if (compute_periphery){
152 20 : GrB_IndexUnaryOp eqOp = (n > INT32_MAX) ?
153 10 : GrB_VALUEEQ_INT64 : GrB_VALUEEQ_INT32 ;
154 10 : GRB_TRY (GrB_Vector_new (&peri, int_type, n)) ;
155 10 : GRB_TRY (GrB_select(peri, NULL, NULL, eqOp, ecc, d, NULL)) ;
156 : }
157 :
158 : //--------------------------------------------------------------------------
159 : // free workspace and return result
160 : //--------------------------------------------------------------------------
161 :
162 10 : if (compute_periphery)
163 : {
164 10 : (*peripheral) = peri ;
165 10 : peri = NULL ;
166 : }
167 10 : if (compute_eccentricity)
168 : {
169 10 : (*eccentricity) = ecc ;
170 10 : ecc = NULL; // makes sure eccentricity vector doesn't get freed if the user wants it
171 : }
172 10 : (*diameter) = d;
173 10 : LG_FREE_WORK ;
174 10 : return (GrB_SUCCESS) ;
175 : #else
176 : return (GrB_NOT_IMPLEMENTED) ;
177 : #endif
178 : }
|
