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