1function gbtest00 (doplots) 2%GBTEST00 test GrB.bfs and plot (graph (G)) 3 4% SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved. 5% SPDX-License-Identifier: GPL-3.0-or-later 6 7if (nargin < 1) 8 doplots = true ; 9end 10 11save_threads = GrB.threads ; 12save_chunk = GrB.chunk ; 13GrB.threads (4) ; 14GrB.chunk (2) ; 15 16%%MatrixMarket matrix coordinate pattern general 17%%GraphBLAS GrB_BOOL 18% Matrix from the cover of "Graph Algorithms in the Language of Linear 19% Algebra", Kepner and Gilbert. Note that cover shows A'. This is A. 20% 7 7 12 21ij = [ 224 1 231 2 244 3 256 3 267 3 271 4 287 4 292 5 307 5 313 6 325 6 332 7 ] ; 34 35source = 1 ; 36 37A = sparse (ij (:,1), ij (:,2), ones (12,1), 8, 8) ; 38 39formats = { 'by row', 'by col' } ; 40if (doplots) 41 figure (1) ; 42 clf ; 43end 44 45for k1 = 1:2 46 fmt = formats {k1} ; 47 48 A = GrB (A, fmt) ; 49 H = GrB (A, 'logical', fmt) ; 50 if (k1 == 1 && doplots) 51 subplot (1,2,1) ; 52 plot (digraph (A)) ; 53 end 54 55 v1 = GrB.bfs (H, source) ; 56 [v, pi] = GrB.bfs (H, source) ; 57 assert (isequal (v, v1)) ; 58 59 vok = [1 2 3 2 3 4 3 0] ; 60 assert (isequal (full (double (v)), vok)) ; 61 62 % there are 2 valid trees, and GrB.bfs can return either one 63 piok1 = [1 1 4 1 2 3 2 0] ; 64 piok2 = [1 1 4 1 2 5 2 0] ; 65 ok1 = isequal (full (double (pi)), piok1) ; 66 ok2 = isequal (full (double (pi)), piok2) ; 67 if (ok1) 68 % this tree is more commonly found 69 % fprintf ('.') ; 70 end 71 if (ok2) 72 % fprintf ('#') ; 73 end 74 assert (ok1 || ok2) ; 75 76 G = digraph (H) ; 77 v2 = bfsearch (G, source) ; 78 79 levels = full (double (v (v2))) ; 80 assert (isequal (levels, sort (levels))) ; 81 82 [v, pi] = GrB.bfs (H, source, 'directed') ; 83 assert (isequal (full (double (v)), vok)) ; 84 85 ok1 = isequal (full (double (pi)), piok1) ; 86 ok2 = isequal (full (double (pi)), piok2) ; 87 if (ok1) 88 % this tree is more commonly found 89 % fprintf ('+') ; 90 end 91 if (ok2) 92 % this is also valid 93 % fprintf ('-') ; 94 end 95 assert (ok1 || ok2) ; 96 97 [v, pi] = GrB.bfs (H, source, 'directed', 'check') ; 98 assert (isequal (full (double (v)), vok)) ; 99 100 ok1 = isequal (full (double (pi)), piok1) ; 101 ok2 = isequal (full (double (pi)), piok2) ; 102 if (ok1) 103 % this tree is more commonly found 104 % fprintf ('\\') ; 105 end 106 if (ok2) 107 % this is also valid 108 % fprintf ('/') ; 109 end 110 assert (ok1 || ok2) ; 111 112end 113 114A = A+A' ; 115[v, pi] = GrB.bfs (A, 2, 'undirected') ; 116if (doplots) 117 subplot (1,2,2) ; 118 plot (graph (A)) 119end 120vok = [2 1 3 3 2 3 2 0] ; 121assert (isequal (full (double (v)), vok)) ; 122% two valid trees: 123piok1 = [2 2 7 1 2 5 2 0] ; 124piok2 = [2 2 7 7 2 5 2 0] ; 125 126 ok1 = isequal (full (double (pi)), piok1) ; 127 ok2 = isequal (full (double (pi)), piok2) ; 128 if (ok1) 129 % this tree is more commonly found 130 % fprintf ('@') ; 131 end 132 if (ok2) 133 % fprintf ('_') ; 134 end 135 assert (ok1 || ok2) ; 136 137GrB.threads (save_threads) ; 138GrB.chunk (save_chunk) ; 139 140fprintf ('gbtest00: all tests passed\n') ; 141 142 143