Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph/src/test/test_edgeBetweennessCentrality.c: test cases for EBC
3 : // -----------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2025 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 Casey Pei and Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // NOTE: these tests require SuiteSparse:GraphBLAS
19 :
20 : #include <stdio.h>
21 : #include <acutest.h>
22 : #include "LAGraphX.h" // important
23 : #include "LAGraph_test.h"
24 : #include "LG_Xtest.h"
25 : #include "LG_internal.h"
26 :
27 : #define LEN 512
28 : char msg [LAGRAPH_MSG_LEN] ;
29 : char filename [LEN+1] ;
30 : LAGraph_Graph G = NULL ;
31 :
32 : //------------------------------------------------------------------------------
33 : // difference: compare the LAGraph and GAP results
34 : //------------------------------------------------------------------------------
35 :
36 : double difference(GrB_Matrix bc, double* reference_bc, GrB_Index rows, GrB_Index cols) ;
37 :
38 8 : double difference(GrB_Matrix bc, double* reference_bc, GrB_Index rows, GrB_Index cols)
39 : {
40 : // GrB_Matrix diff = NULL;
41 8 : GrB_Matrix diff = NULL, reference_bc_matrix = NULL ;
42 8 : OK(GrB_Matrix_new(&reference_bc_matrix, GrB_FP64, rows, cols)) ;
43 :
44 : // Populate gap_bc with values from gap_result
45 176 : for (GrB_Index i = 0; i < rows; i++) {
46 5048 : for (GrB_Index j = 0; j < cols; j++) {
47 4880 : OK(GrB_Matrix_setElement_FP64(reference_bc_matrix, *(reference_bc + i * cols + j), i, j)) ;
48 : }
49 : }
50 :
51 : // Compute diff = max(abs(reference_bc_matrix - bc))
52 8 : OK(GrB_Matrix_new(&diff, GrB_FP64, rows, cols)) ;
53 8 : OK(GrB_eWiseAdd(diff, NULL, NULL, GrB_MINUS_FP64, reference_bc_matrix, bc, NULL)) ;
54 8 : OK(GrB_apply(diff, NULL, NULL, GrB_ABS_FP64, diff, NULL)) ;
55 :
56 8 : double err = 0 ;
57 8 : OK(GrB_reduce(&err, NULL, GrB_MAX_MONOID_FP64, diff, NULL)) ;
58 :
59 8 : OK(GrB_free(&diff)) ;
60 8 : OK(GrB_free(&reference_bc_matrix)) ;
61 :
62 8 : return err ;
63 : }
64 :
65 : double matrix_difference(GrB_Matrix bc, GrB_Matrix reference_bc) ;
66 :
67 18 : double matrix_difference(GrB_Matrix bc, GrB_Matrix reference_bc)
68 : {
69 18 : GrB_Matrix diff = NULL ;
70 :
71 : uint64_t n ;
72 18 : GrB_Matrix_nrows (&n, bc) ;
73 :
74 : // Compute diff = max(abs(reference_bc - bc))
75 18 : GrB_Matrix_new(&diff, GrB_FP64, n, n) ;
76 18 : GrB_eWiseAdd(diff, NULL, NULL, GrB_MINUS_FP64, reference_bc, bc, NULL) ;
77 18 : GrB_apply(diff, NULL, NULL, GrB_ABS_FP64, diff, NULL) ;
78 :
79 18 : double err = 1 ;
80 18 : GrB_reduce(&err, NULL, GrB_MAX_MONOID_FP64, diff, NULL) ;
81 :
82 18 : GrB_free(&diff) ;
83 :
84 18 : return err ;
85 : }
86 :
87 : //------------------------------------------------------------------------------
88 : // results for book graph
89 : //------------------------------------------------------------------------------
90 :
91 : // Exact results from edge_betweenness_centrality from NetworkX of the graph
92 : // from the book
93 :
94 : double diamonds_ebc [8][8] =
95 : {
96 : {0.0, 2.333333333333333, 2.333333333333333, 2.333333333333333, 0.0, 0.0, 0.0, 0.0},
97 : {0.0, 0.0, 1.0, 0.0, 5.333333333333333, 0.0, 0.0, 0.0},
98 : {0.0, 0.0, 0.0, 0.0, 5.333333333333333, 0.0, 0.0, 0.0},
99 : {0.0, 0.0, 1.0, 0.0, 5.333333333333333, 0.0, 0.0, 0.0},
100 : {0.0, 0.0, 0.0, 0.0, 0.0, 7.5, 7.5, 0.0},
101 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.5},
102 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.5},
103 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
104 : } ;
105 :
106 : // Approximate results from edge_betweenness_centrality from NetworkX of the karate
107 : // graph
108 :
109 : int64_t diamonds_sources [4] = {1, 0, 5, 2};
110 :
111 : double diamonds_ebc_approx [8][8] =
112 : {
113 : {0.0, 2.333333333333333, 2.333333333333333, 2.333333333333333, 0.0, 0.0, 0.0, 0.0},
114 : {0.0, 0.0, 1.0, 0.0, 5.333333333333333, 0.0, 0.0, 0.0},
115 : {0.0, 0.0, 0.0, 0.0, 5.333333333333333, 0.0, 0.0, 0.0},
116 : {0.0, 0.0, 0.0, 0.0, 1.3333333333333333, 0.0, 0.0, 0.0},
117 : {0.0, 0.0, 0.0, 0.0, 0.0, 4.5, 4.5, 0.0},
118 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.5},
119 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.5},
120 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
121 : } ;
122 :
123 : //------------------------------------------------------------------------------
124 : // results for karate graph
125 : //------------------------------------------------------------------------------
126 :
127 : // Exact results from edge_betweenness_centrality from NetworkX of the karate
128 : // graph
129 :
130 : double karate_ebc [34][34] =
131 : {
132 : {0.0, 14.166666666666664, 43.638888888888886, 11.5, 29.333333333333332, 43.83333333333333, 43.833333333333336, 12.80238095238095, 41.64841269841271, 0.0, 29.333333333333332, 33.0, 26.099999999999994, 23.77063492063493, 0.0, 0.0, 0.0, 22.509523809523813, 0.0, 25.770634920634926, 0.0, 22.50952380952381, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 71.39285714285712, 0.0, 0.0},
133 : {14.166666666666664, 0.0, 13.033333333333335, 4.333333333333333, 0.0, 0.0, 0.0, 4.164285714285714, 0.0, 0.0, 0.0, 0.0, 0.0, 6.9595238095238106, 0.0, 0.0, 0.0, 10.490476190476187, 0.0, 8.209523809523809, 0.0, 10.490476190476187, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 18.10952380952381, 0.0, 0.0, 0.0},
134 : {43.638888888888886, 13.033333333333335, 0.0, 12.583333333333332, 0.0, 0.0, 0.0, 14.145238095238092, 5.147619047619047, 17.28095238095238, 0.0, 0.0, 0.0, 4.28095238095238, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 23.10873015873016, 12.780952380952376, 0.0, 0.0, 0.0, 38.70158730158729, 0.0},
135 : {11.5, 4.333333333333333, 12.583333333333332, 0.0, 0.0, 0.0, 0.0, 1.8880952380952383, 0.0, 0.0, 0.0, 0.0, 6.899999999999997, 8.37142857142857, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
136 : {29.333333333333332, 0.0, 0.0, 0.0, 0.0, 0.0, 2.6666666666666665, 0.0, 0.0, 0.0, 1.6666666666666665, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
137 : {43.83333333333333, 0.0, 0.0, 0.0, 0.0, 0.0, 1.6666666666666667, 0.0, 0.0, 0.0, 2.6666666666666665, 0.0, 0.0, 0.0, 0.0, 0.0, 16.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
138 : {43.833333333333336, 0.0, 0.0, 0.0, 2.6666666666666665, 1.6666666666666667, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 16.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
139 : {12.80238095238095, 4.164285714285714, 14.145238095238092, 1.8880952380952383, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
140 : {41.64841269841271, 0.0, 5.147619047619047, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 5.5, 0.0, 17.077777777777776, 22.684920634920633},
141 : {0.0, 0.0, 17.28095238095238, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 16.614285714285714},
142 : {29.333333333333332, 0.0, 0.0, 0.0, 1.6666666666666665, 2.6666666666666665, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
143 : {33.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
144 : {26.099999999999994, 0.0, 0.0, 6.899999999999997, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
145 : {23.77063492063493, 6.9595238095238106, 4.28095238095238, 8.37142857142857, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 38.04920634920634},
146 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 13.511111111111113, 19.488888888888887},
147 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 13.511111111111113, 19.488888888888887},
148 : {0.0, 0.0, 0.0, 0.0, 0.0, 16.5, 16.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
149 : {22.509523809523813, 10.490476190476187, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
150 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 13.511111111111111, 19.488888888888887},
151 : {25.770634920634926, 8.209523809523809, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 33.31349206349207},
152 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 13.511111111111113, 19.488888888888887},
153 : {22.50952380952381, 10.490476190476187, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
154 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 13.511111111111111, 19.488888888888887},
155 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 11.094444444444443, 0.0, 5.9111111111111105, 0.0, 3.7333333333333334, 0.0, 0.0, 12.533333333333331, 18.327777777777783},
156 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.3666666666666667, 0.0, 10.466666666666665, 0.0, 0.0, 0.0, 22.5, 0.0, 0.0},
157 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 11.094444444444443, 2.3666666666666667, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 23.59444444444445, 0.0, 0.0},
158 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.5428571428571427, 0.0, 0.0, 0.0, 30.457142857142856},
159 : {0.0, 0.0, 23.10873015873016, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 5.9111111111111105, 10.466666666666665, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 17.097619047619048},
160 : {0.0, 0.0, 12.780952380952376, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 8.333333333333332, 0.0, 13.78095238095238},
161 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.7333333333333334, 0.0, 0.0, 2.5428571428571427, 0.0, 0.0, 0.0, 0.0, 0.0, 13.087301587301585, 16.72222222222222},
162 : {0.0, 18.10952380952381, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 5.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 9.566666666666666, 15.042857142857141},
163 : {71.39285714285712, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 22.5, 23.59444444444445, 0.0, 0.0, 8.333333333333332, 0.0, 0.0, 0.0, 23.244444444444447, 29.95396825396826},
164 : {0.0, 0.0, 38.70158730158729, 0.0, 0.0, 0.0, 0.0, 0.0, 17.077777777777776, 0.0, 0.0, 0.0, 0.0, 0.0, 13.511111111111113, 13.511111111111113, 0.0, 0.0, 13.511111111111113, 0.0, 13.511111111111113, 0.0, 13.511111111111111, 12.533333333333331, 0.0, 0.0, 0.0, 0.0, 0.0, 13.087301587301585, 9.566666666666666, 23.244444444444447, 0.0, 4.614285714285714},
165 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 22.684920634920633, 16.614285714285714, 0.0, 0.0, 0.0, 38.04920634920634, 19.488888888888887, 19.488888888888887, 0.0, 0.0, 19.488888888888887, 33.31349206349207, 19.488888888888887, 0.0, 19.488888888888887, 18.327777777777783, 0.0, 0.0, 30.457142857142856, 17.097619047619048, 13.78095238095238, 16.72222222222222, 15.042857142857141, 29.95396825396826, 4.614285714285714, 0.0},
166 : } ;
167 :
168 :
169 : // Approximate results from edge_betweenness_centrality from NetworkX of the karate
170 : // graph
171 :
172 : int64_t karate_sources [4] = {7, 1, 17, 15};
173 :
174 : double karate_ebc_approx [34][34] =
175 : {
176 : {0.0, 5.166666666666666, 1.9722222222222223, 0.25, 2.0, 3.0, 3.0, 6.651190476190476, 3.0730158730158728, 0.0, 2.0, 2.0, 1.3888888888888888, 1.509126984126984, 0.0, 0.0, 0.0, 11.79642857142857, 0.0, 1.634126984126984, 0.0, 0.7916666666666666, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 6.356349206349205, 0.0, 0.0},
177 : {5.166666666666666, 0.0, 4.95, 1.0, 0.0, 0.0, 0.0, 2.8321428571428573, 0.0, 0.0, 0.0, 0.0, 0.0, 2.570238095238095, 0.0, 0.0, 0.0, 6.203571428571427, 0.0, 2.695238095238095, 0.0, 1.2083333333333333, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 4.8619047619047615, 0.0, 0.0, 0.0},
178 : {1.9722222222222223, 4.95, 0.0, 0.3055555555555556, 0.0, 0.0, 0.0, 7.572619047619047, 0.48571428571428565, 1.569047619047619, 0.0, 0.0, 0.0, 0.19404761904761905, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.469047619047619, 1.4023809523809523, 0.0, 0.0, 0.0, 7.68015873015873, 0.0},
179 : {0.25, 1.0, 0.3055555555555556, 0.0, 0.0, 0.0, 0.0, 0.944047619047619, 0.0, 0.0, 0.0, 0.0, 0.6111111111111112, 0.4996031746031746, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
180 : {2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
181 : {3.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
182 : {3.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
183 : {6.651190476190476, 2.8321428571428573, 7.572619047619047, 0.944047619047619, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
184 : {3.0730158730158728, 0.0, 0.48571428571428565, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.16666666666666666, 0.0, 1.2722222222222221, 1.4531746031746033},
185 : {0.0, 0.0, 1.569047619047619, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.569047619047619},
186 : {2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
187 : {2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
188 : {1.3888888888888888, 0.0, 0.0, 0.6111111111111112, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
189 : {1.509126984126984, 2.570238095238095, 0.19404761904761905, 0.4996031746031746, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.7730158730158725},
190 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1583333333333332, 0.8416666666666667},
191 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 7.66388888888889, 10.336111111111112},
192 : {0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
193 : {11.79642857142857, 6.203571428571427, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
194 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1583333333333332, 0.8416666666666667},
195 : {1.634126984126984, 2.695238095238095, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.3293650793650795},
196 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1583333333333332, 0.8416666666666667},
197 : {0.7916666666666666, 1.2083333333333333, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
198 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1583333333333332, 0.8416666666666667},
199 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2833333333333333, 0.0, 0.39999999999999997, 0.0, 0.0, 0.0, 0.0, 0.9583333333333333, 0.8583333333333334},
200 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.6666666666666666, 0.0, 0.0, 0.0, 1.3333333333333333, 0.0, 0.0},
201 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2833333333333333, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.7833333333333332, 0.0, 0.0},
202 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.03333333333333333, 0.0, 0.0, 0.0, 1.9666666666666668},
203 : {0.0, 0.0, 2.469047619047619, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.39999999999999997, 0.6666666666666666, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.7357142857142857},
204 : {0.0, 0.0, 1.4023809523809523, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.16666666666666666, 0.0, 0.569047619047619},
205 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.03333333333333333, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1916666666666667, 0.8416666666666667},
206 : {0.0, 4.8619047619047615, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.16666666666666666, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.75, 1.9452380952380952},
207 : {6.356349206349205, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.3333333333333333, 1.7833333333333332, 0.0, 0.0, 0.16666666666666666, 0.0, 0.0, 0.0, 1.5638888888888889, 1.6757936507936506},
208 : {0.0, 0.0, 7.68015873015873, 0.0, 0.0, 0.0, 0.0, 0.0, 1.2722222222222221, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1583333333333332, 7.66388888888889, 0.0, 0.0, 1.1583333333333332, 0.0, 1.1583333333333332, 0.0, 1.1583333333333332, 0.9583333333333333, 0.0, 0.0, 0.0, 0.0, 0.0, 1.1916666666666667, 1.75, 1.5638888888888889, 0.0, 0.06904761904761905},
209 : {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.4531746031746033, 0.569047619047619, 0.0, 0.0, 0.0, 3.7730158730158725, 0.8416666666666667, 10.336111111111112, 0.0, 0.0, 0.8416666666666667, 3.3293650793650795, 0.8416666666666667, 0.0, 0.8416666666666667, 0.8583333333333334, 0.0, 0.0, 1.9666666666666668, 0.7357142857142857, 0.569047619047619, 0.8416666666666667, 1.9452380952380952, 1.6757936507936506, 0.06904761904761905, 0.0},
210 : } ;
211 :
212 : // test many approx
213 : int64_t approx_sources [4] = {0, 1, 2, 3};
214 :
215 : //------------------------------------------------------------------------------
216 : // test_diamonds_ebc: Test diamonds graph on exact EBC against NetworkX and C
217 : //------------------------------------------------------------------------------
218 :
219 1 : void test_diamonds_ebc (void)
220 : {
221 : #if LAGRAPH_SUITESPARSE
222 1 : LAGraph_Init (msg) ;
223 1 : GrB_Matrix A = NULL ;
224 1 : GrB_Matrix AT = NULL ;
225 1 : GrB_Matrix centrality = NULL ;
226 1 : int niters = 0 ;
227 1 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
228 :
229 : // create the diamonds graph
230 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "diamonds.mtx") ;
231 1 : FILE *f = fopen (filename, "r") ;
232 1 : TEST_CHECK (f != NULL) ;
233 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
234 1 : OK (fclose (f)) ;
235 1 : OK (LAGraph_New (&G, &A, kind, msg)) ;
236 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
237 :
238 : // Print graph statistics
239 : uint64_t n, nedges ;
240 1 : OK (GrB_Matrix_nrows(&n, G->A)) ;
241 1 : OK (GrB_Matrix_nvals(&nedges, G->A)) ;
242 1 : printf ("\n\nDiamonds graph (%" PRIu64 " nodes, %" PRIu64 " edges):\n", n, nedges) ;
243 :
244 : // check that AT is cached
245 1 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
246 1 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
247 1 : int result = LAGraph_Cached_AT (G, msg) ;
248 1 : TEST_CHECK (result == ok_result) ;
249 :
250 : // compute its betweenness centrality with C version
251 1 : double t = LAGraph_WallClockTime() ;
252 1 : OK (LG_check_edgeBetweennessCentrality (¢rality, G, NULL, msg)) ;
253 1 : t = LAGraph_WallClockTime() - t ;
254 1 : double err = difference(centrality, &diamonds_ebc[0][0], 8, 8) ;
255 1 : printf ("Time for LG_check_edgeBetweennessCentrality: %g sec\n", t) ;
256 1 : printf (" diamonds: err: %e (C version)\n", err) ;
257 1 : TEST_CHECK (err < 1e-4) ;
258 1 : OK (GrB_free (¢rality)) ;
259 :
260 : // compute its betweenness centrality with GraphBLAS version
261 1 : t = LAGraph_WallClockTime() ;
262 1 : OK (LAGr_EdgeBetweennessCentrality (¢rality, G, NULL, msg)) ;
263 1 : t = LAGraph_WallClockTime() - t ;
264 1 : err = difference(centrality, &diamonds_ebc[0][0], 8, 8) ;
265 1 : printf ("Time for LAGr_EdgeBetweennessCentrality: %g sec\n", t) ;
266 1 : printf (" diamonds: err: %e (pure GraphBLAS)\n", err) ;
267 1 : TEST_CHECK (err < 1e-4) ;
268 1 : OK (GrB_free (¢rality)) ;
269 :
270 1 : OK (LAGraph_Delete (&G, msg)) ;
271 1 : LAGraph_Finalize (msg) ;
272 : #endif
273 1 : }
274 :
275 : //------------------------------------------------------------------------------
276 : // test_karate_ebc: Test karate graph on exact EBC against NetworkX and C
277 : //------------------------------------------------------------------------------
278 :
279 1 : void test_karate_ebc (void)
280 : {
281 : #if LAGRAPH_SUITESPARSE
282 1 : LAGraph_Init (msg) ;
283 1 : GrB_Matrix A = NULL ;
284 1 : GrB_Matrix centrality = NULL ;
285 1 : int niters = 0 ;
286 :
287 : // create the karate graph
288 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
289 1 : FILE *f = fopen (filename, "r") ;
290 1 : TEST_CHECK (f != NULL) ;
291 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
292 1 : OK (fclose (f)) ;
293 1 : OK (LAGraph_New (&G, &A, LAGraph_ADJACENCY_UNDIRECTED, msg)) ;
294 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
295 :
296 : // Print graph statistics
297 : uint64_t n, nedges ;
298 1 : OK (GrB_Matrix_nrows(&n, G->A)) ;
299 1 : OK (GrB_Matrix_nvals(&nedges, G->A)) ;
300 1 : printf ("\n\nKarate graph (%" PRIu64 " nodes, %" PRIu64 " edges):\n", n, nedges) ;
301 :
302 : // compute its betweenness centrality (C version)
303 1 : double t = LAGraph_WallClockTime() ;
304 1 : OK (LG_check_edgeBetweennessCentrality (¢rality, G, NULL, msg)) ;
305 1 : t = LAGraph_WallClockTime() - t ;
306 1 : double err = difference(centrality, &karate_ebc[0][0], 34, 34) ;
307 1 : printf (" Time for LG_check_edgeBetweennessCentrality: %g sec\n", t) ;
308 1 : printf (" karate: err: %e (C version)\n", err) ;
309 1 : TEST_CHECK (err < 1e-4) ;
310 1 : OK (GrB_free (¢rality)) ;
311 :
312 : // compute its betweenness centrality (GraphBLAS version)
313 1 : t = LAGraph_WallClockTime() ;
314 1 : OK (LAGr_EdgeBetweennessCentrality (¢rality, G, NULL, msg)) ;
315 1 : t = LAGraph_WallClockTime() - t ;
316 1 : err = difference(centrality, &karate_ebc[0][0], 34, 34) ;
317 1 : printf (" Time for LAGr_EdgeBetweennessCentrality: %g sec\n", t) ;
318 1 : printf (" karate: err: %e (GraphBLAS version)\n", err) ;
319 1 : TEST_CHECK (err < 1e-4) ;
320 1 : OK (GrB_free (¢rality)) ;
321 :
322 1 : OK (LAGraph_Delete (&G, msg)) ;
323 1 : LAGraph_Finalize (msg) ;
324 : #endif
325 1 : }
326 :
327 : //------------------------------------------------------------------------------
328 : // test_many: Test multiple matrix market files on exact EBC against C
329 : //------------------------------------------------------------------------------
330 :
331 1 : void test_many(void)
332 : {
333 : #if LAGRAPH_SUITESPARSE
334 1 : LAGraph_Init(msg);
335 :
336 1 : const char *files[] = {
337 : "random_unweighted_general1.mtx",
338 : "random_unweighted_general2.mtx",
339 : "random_unweighted_bipartite1.mtx",
340 : "random_unweighted_bipartite2.mtx",
341 : "jagmesh7.mtx",
342 : "dnn_data/n1024-l1.mtx",
343 : // "bcsstk13.mtx",
344 : // "pushpull.mtx",
345 : // "cryg2500.mtx",
346 : NULL
347 : };
348 :
349 7 : for (int i = 0; files[i] != NULL; i++)
350 : {
351 6 : GrB_Matrix A = NULL;
352 6 : GrB_Matrix centrality = NULL;
353 6 : GrB_Matrix reference_centrality = NULL;
354 :
355 6 : snprintf(filename, LEN, LG_DATA_DIR "%s", files[i]);
356 6 : FILE *f = fopen(filename, "r");
357 6 : TEST_CHECK(f != NULL);
358 6 : OK(LAGraph_MMRead(&A, f, msg));
359 6 : OK(fclose(f));
360 6 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_DIRECTED, msg));
361 6 : OK(LAGraph_DeleteSelfEdges (G, msg)) ;
362 6 : OK(LAGraph_Cached_AT (G, msg)) ;
363 6 : TEST_CHECK(A == NULL); // A has been moved into G->A
364 :
365 : // Print graph statistics
366 : uint64_t n, nedges ;
367 6 : OK (GrB_Matrix_nrows(&n, G->A)) ;
368 6 : OK (GrB_Matrix_nvals(&nedges, G->A)) ;
369 6 : printf ("\n\n%s (%" PRIu64 " nodes, %" PRIu64 " edges)\n", files[i], n, nedges) ;
370 :
371 : // compute its betweenness centrality (GraphBLAS version)
372 6 : double t = LAGraph_WallClockTime() ;
373 6 : OK(LAGr_EdgeBetweennessCentrality(¢rality, G, NULL, msg));
374 6 : t = LAGraph_WallClockTime() - t ;
375 6 : printf (" Time for LAGr_EdgeBetweennessCentrality: %g sec\n", t) ;
376 :
377 : // compute its betweenness centrality (C version)
378 6 : t = LAGraph_WallClockTime() ;
379 6 : OK(LG_check_edgeBetweennessCentrality(&reference_centrality, G, NULL, msg));
380 6 : t = LAGraph_WallClockTime() - t ;
381 6 : printf (" Time for LG_check_edgeBetweennessCentrality: %g sec\n", t) ;
382 :
383 : // Compare the results
384 6 : double err = matrix_difference(centrality, reference_centrality);
385 6 : printf(" %s: err: %e", files[i], err);
386 6 : TEST_CHECK(err < 1e-4);
387 :
388 6 : OK(GrB_free(¢rality));
389 6 : OK(GrB_free(&reference_centrality));
390 6 : OK(LAGraph_Delete(&G, msg));
391 : }
392 1 : printf("\n") ;
393 :
394 1 : LAGraph_Finalize(msg);
395 : #endif
396 1 : }
397 :
398 : //------------------------------------------------------------------------------
399 : // test_diamonds_ebc_approx: Test diamonds graph on approx EBC against NetworkX and C
400 : //------------------------------------------------------------------------------
401 :
402 1 : void test_diamonds_ebc_approx (void)
403 : {
404 : #if LAGRAPH_SUITESPARSE
405 1 : LAGraph_Init (msg) ;
406 1 : GrB_Matrix A = NULL ;
407 1 : GrB_Matrix AT = NULL ;
408 1 : GrB_Matrix centrality = NULL ;
409 1 : int niters = 0 ;
410 1 : LAGraph_Kind kind = LAGraph_ADJACENCY_DIRECTED ;
411 :
412 : // create the diamonds graph
413 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "diamonds.mtx") ;
414 1 : FILE *f = fopen (filename, "r") ;
415 1 : TEST_CHECK (f != NULL) ;
416 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
417 1 : OK (fclose (f)) ;
418 1 : OK (LAGraph_New (&G, &A, kind, msg)) ;
419 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
420 :
421 : // Print graph statistics
422 : uint64_t n, nedges ;
423 1 : OK (GrB_Matrix_nrows(&n, G->A)) ;
424 1 : OK (GrB_Matrix_nvals(&nedges, G->A)) ;
425 1 : printf ("\n\nDiamonds graph (%" PRIu64 " nodes, %" PRIu64 " edges):\n", n, nedges) ;
426 :
427 : // create sources vector
428 : GrB_Vector sources;
429 1 : GrB_Vector_new(&sources, GrB_INT64, 4);
430 5 : for (GrB_Index i = 0; i < 4; i++) {
431 4 : OK (GrB_Vector_setElement_INT64 (sources, diamonds_sources[i], i)) ;
432 : }
433 :
434 : // check that AT is cached
435 1 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
436 1 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
437 1 : int result = LAGraph_Cached_AT (G, msg) ;
438 1 : TEST_CHECK (result == ok_result) ;
439 :
440 : double t, err ;
441 :
442 : // compute its betweenness centrality with C version
443 1 : t = LAGraph_WallClockTime() ;
444 1 : OK (LG_check_edgeBetweennessCentrality (¢rality, G, sources, msg)) ;
445 1 : t = LAGraph_WallClockTime() - t ;
446 1 : err = difference(centrality, &diamonds_ebc_approx[0][0], 8, 8) ;
447 1 : printf ("Time for LG_check_edgeBetweennessCentrality: %g sec\n", t) ;
448 1 : printf (" diamonds: err: %e (C version)\n", err) ;
449 1 : TEST_CHECK (err < 1e-4) ;
450 1 : OK (GrB_free (¢rality)) ;
451 :
452 : // compute its betweenness centrality with GraphBLAS version
453 1 : t = LAGraph_WallClockTime() ;
454 1 : OK (LAGr_EdgeBetweennessCentrality (¢rality, G, sources, msg)) ;
455 1 : t = LAGraph_WallClockTime() - t ;
456 1 : err = difference(centrality, &diamonds_ebc_approx[0][0], 8, 8) ;
457 1 : printf ("Time for LAGr_EdgeBetweennessCentrality: %g sec\n", t) ;
458 1 : printf (" diamonds: err: %e (pure GraphBLAS)\n", err) ;
459 1 : TEST_CHECK (err < 1e-4) ;
460 1 : OK (GrB_free (¢rality)) ;
461 1 : OK (GrB_free (&sources)) ;
462 :
463 1 : OK (LAGraph_Delete (&G, msg)) ;
464 1 : LAGraph_Finalize (msg) ;
465 : #endif
466 1 : }
467 :
468 : //------------------------------------------------------------------------------
469 : // test_karate_ebc: Test karate graph on approx EBC against NetworkX and C
470 : //------------------------------------------------------------------------------
471 :
472 1 : void test_karate_ebc_approx (void)
473 : {
474 : #if LAGRAPH_SUITESPARSE
475 1 : LAGraph_Init (msg) ;
476 1 : GrB_Matrix A = NULL ;
477 1 : GrB_Matrix centrality = NULL ;
478 1 : int niters = 0 ;
479 1 : LAGraph_Kind kind = LAGraph_ADJACENCY_UNDIRECTED;
480 :
481 : // create the karate graph
482 1 : snprintf (filename, LEN, LG_DATA_DIR "%s", "karate.mtx") ;
483 1 : FILE *f = fopen (filename, "r") ;
484 1 : TEST_CHECK (f != NULL) ;
485 1 : OK (LAGraph_MMRead (&A, f, msg)) ;
486 1 : OK (fclose (f)) ;
487 1 : OK (LAGraph_New (&G, &A, kind, msg)) ;
488 1 : TEST_CHECK (A == NULL) ; // A has been moved into G->A
489 :
490 : // check that AT is cached
491 1 : int ok_result = (kind == LAGraph_ADJACENCY_UNDIRECTED) ?
492 1 : LAGRAPH_CACHE_NOT_NEEDED : GrB_SUCCESS ;
493 1 : int result = LAGraph_Cached_AT (G, msg) ;
494 1 : TEST_CHECK (result == ok_result) ;
495 :
496 : // Print graph statistics
497 : uint64_t n, nedges ;
498 1 : OK (GrB_Matrix_nrows(&n, G->A)) ;
499 1 : OK (GrB_Matrix_nvals(&nedges, G->A)) ;
500 1 : printf ("\n\nKarate graph (%" PRIu64 " nodes, %" PRIu64 " edges):\n", n, nedges) ;
501 :
502 : // create sources vector
503 : GrB_Vector sources;
504 1 : GrB_Vector_new(&sources, GrB_INT64, 4);
505 5 : for (GrB_Index i = 0; i < 4; i++) {
506 4 : OK (GrB_Vector_setElement_INT64 (sources, karate_sources[i], i)) ;
507 : }
508 :
509 : double t, err ;
510 : // compute its betweenness centrality (C version)
511 1 : t = LAGraph_WallClockTime() ;
512 1 : OK (LG_check_edgeBetweennessCentrality (¢rality, G, sources, msg)) ;
513 1 : t = LAGraph_WallClockTime() - t ;
514 1 : err = difference(centrality, &karate_ebc_approx[0][0], 34, 34) ;
515 1 : printf (" Time for LG_check_edgeBetweennessCentrality: %g sec\n", t) ;
516 1 : printf (" karate: err: %e (C version)\n", err) ;
517 1 : TEST_CHECK (err < 1e-4) ;
518 1 : OK (GrB_free (¢rality)) ;
519 :
520 : // compute its betweenness centrality (GraphBLAS version)
521 1 : t = LAGraph_WallClockTime() ;
522 1 : OK (LAGr_EdgeBetweennessCentrality (¢rality, G, sources, msg)) ;
523 1 : t = LAGraph_WallClockTime() - t ;
524 1 : err = difference(centrality, &karate_ebc_approx[0][0], 34, 34) ;
525 1 : printf (" Time for LAGr_EdgeBetweennessCentrality: %g sec\n", t) ;
526 1 : printf (" karate: err: %e (GraphBLAS version)\n", err) ;
527 1 : TEST_CHECK (err < 1e-4) ;
528 1 : OK (GrB_free (¢rality)) ;
529 1 : OK (GrB_free (&sources)) ;
530 :
531 1 : OK (LAGraph_Delete (&G, msg)) ;
532 1 : LAGraph_Finalize (msg) ;
533 : #endif
534 1 : }
535 :
536 : //------------------------------------------------------------------------------
537 : // test_many_approx: Test multiple matrix market files on exact EBC against C
538 : // using 8 random indices
539 : //------------------------------------------------------------------------------
540 :
541 1 : void test_many_approx(void)
542 : {
543 : #if LAGRAPH_SUITESPARSE
544 1 : LAGraph_Init(msg);
545 :
546 1 : const char *files[] = {
547 : "random_unweighted_general1.mtx",
548 : "random_unweighted_general2.mtx",
549 : "random_unweighted_bipartite1.mtx",
550 : "random_unweighted_bipartite2.mtx",
551 : "jagmesh7.mtx",
552 : "dnn_data/n1024-l1.mtx",
553 : // "bcsstk13.mtx",
554 : // "pushpull.mtx",
555 : // "cryg2500.mtx",
556 : NULL
557 : };
558 :
559 7 : for (int i = 0; files[i] != NULL; i++)
560 : {
561 6 : GrB_Matrix A = NULL;
562 6 : GrB_Matrix centrality = NULL;
563 6 : GrB_Matrix reference_centrality = NULL;
564 :
565 6 : snprintf(filename, LEN, LG_DATA_DIR "%s", files[i]);
566 6 : FILE *f = fopen(filename, "r");
567 6 : TEST_CHECK(f != NULL);
568 6 : OK(LAGraph_MMRead(&A, f, msg));
569 6 : OK(fclose(f));
570 6 : OK(LAGraph_New(&G, &A, LAGraph_ADJACENCY_DIRECTED, msg));
571 6 : OK(LAGraph_DeleteSelfEdges (G, msg)) ;
572 6 : OK(LAGraph_Cached_AT (G, msg)) ;
573 6 : TEST_CHECK(A == NULL); // A has been moved into G->A
574 :
575 : // Print graph statistics
576 : uint64_t n, nedges ;
577 6 : OK (GrB_Matrix_nrows(&n, G->A)) ;
578 6 : OK (GrB_Matrix_nvals(&nedges, G->A)) ;
579 6 : printf ("\n\n%s (%" PRIu64 " nodes, %" PRIu64 " edges)\n", files[i], n, nedges) ;
580 :
581 : GrB_Vector randomSources;
582 6 : GrB_Vector_new(&randomSources, GrB_UINT64, 8);
583 :
584 : // For ensuring unique indices
585 6 : bool *used = NULL ;
586 6 : OK (LAGraph_Calloc ((void **) &used, n, sizeof (bool), msg)) ;
587 :
588 6 : double t = LAGraph_WallClockTime() ;
589 : // srand((int) t);
590 6 : uint64_t seed = 42 ;
591 :
592 : // Generate 8 unique random indices between 0 and n-1
593 6 : int count = 0;
594 54 : while (count < 8 && count < n) {
595 48 : GrB_Index random_idx = LG_Random64 (&seed) % n;
596 48 : if (!used[random_idx]) {
597 48 : used[random_idx] = true;
598 48 : GrB_Vector_setElement(randomSources, random_idx, count);
599 48 : count++;
600 : }
601 : }
602 6 : OK (LAGraph_Free ((void **) &used, msg)) ;
603 :
604 : // compute its betweenness centrality (GraphBLAS version)
605 6 : t = LAGraph_WallClockTime() ;
606 6 : OK(LAGr_EdgeBetweennessCentrality(¢rality, G, randomSources, msg));
607 6 : t = LAGraph_WallClockTime() - t ;
608 6 : printf (" Time for LAGr_EdgeBetweennessCentrality: %g sec\n", t) ;
609 :
610 : // compute its betweenness centrality (C version)
611 6 : t = LAGraph_WallClockTime() ;
612 6 : OK(LG_check_edgeBetweennessCentrality(&reference_centrality, G, randomSources, msg));
613 6 : t = LAGraph_WallClockTime() - t ;
614 6 : printf (" Time for LG_check_edgeBetweennessCentrality: %g sec\n", t) ;
615 :
616 : // Compare the results
617 6 : double err = matrix_difference(centrality, reference_centrality);
618 6 : printf(" %s: err: %e\n", files[i], err);
619 6 : TEST_CHECK(err < 1e-4);
620 :
621 6 : OK(GrB_free(¢rality));
622 :
623 : // try without the JIT
624 : // LG_SET_BURBLE (true) ;
625 6 : OK (LG_SET_JIT (LG_JIT_PAUSE)) ;
626 6 : OK (LAGr_EdgeBetweennessCentrality(¢rality, G, randomSources, msg));
627 6 : err = matrix_difference (centrality, reference_centrality);
628 6 : printf(" %s: err: %e (JIT paused)\n", files[i], err);
629 6 : TEST_CHECK(err < 1e-4);
630 6 : OK (LG_SET_JIT (LG_JIT_ON)) ;
631 : // LG_SET_BURBLE (false) ;
632 :
633 6 : OK(GrB_free(¢rality));
634 6 : OK(GrB_free(&reference_centrality));
635 6 : OK(GrB_free(&randomSources));
636 6 : OK(LAGraph_Delete(&G, msg));
637 : }
638 1 : printf("\n") ;
639 :
640 1 : LAGraph_Finalize(msg);
641 : #endif
642 1 : }
643 :
644 : //------------------------------------------------------------------------------
645 :
646 1 : void test_no_sources (void)
647 : {
648 : #if LAGRAPH_SUITESPARSE
649 1 : LAGraph_Init(msg);
650 :
651 1 : GrB_Matrix A = NULL ;
652 1 : GrB_Matrix centrality = NULL ;
653 1 : GrB_Matrix reference_centrality = NULL ;
654 1 : GrB_Vector sources = NULL ;
655 1 : LAGraph_Graph G = NULL ;
656 :
657 1 : OK (GrB_Matrix_new (&A, GrB_FP64, 10, 10)) ;
658 1 : OK (GrB_Vector_new (&sources, GrB_INT64, 0)) ;
659 1 : OK (LAGraph_New(&G, &A, LAGraph_ADJACENCY_DIRECTED, msg)) ;
660 :
661 1 : int result = (LAGr_EdgeBetweennessCentrality (¢rality, G, sources, msg)) ;
662 1 : TEST_CHECK (result == GrB_INVALID_VALUE) ;
663 :
664 1 : OK (LG_check_edgeBetweennessCentrality(&reference_centrality, G, sources, msg));
665 :
666 1 : OK (GrB_free (¢rality)) ;
667 1 : OK (GrB_free (&reference_centrality)) ;
668 1 : OK (GrB_free (&sources)) ;
669 1 : OK (LAGraph_Delete (&G, msg)) ;
670 :
671 1 : LAGraph_Finalize(msg);
672 : #endif
673 1 : }
674 :
675 : //------------------------------------------------------------------------------
676 : // list of tests
677 : //------------------------------------------------------------------------------
678 :
679 : TEST_LIST = {
680 : {"test_diamonds_ebc", test_diamonds_ebc},
681 : {"test_karate_ebc", test_karate_ebc},
682 : {"test_many", test_many},
683 : {"test_diamonds_ebc_approx", test_diamonds_ebc_approx},
684 : {"test_karate_ebc_approx", test_karate_ebc_approx},
685 : {"test_many_approx", test_many_approx},
686 : {"test_no_sources", test_no_sources},
687 : {NULL, NULL}
688 : };
|
