1function graph_demo (n) 2%GRAPH_DEMO graph partitioning demo 3% graph_demo(n) constructs an set of n-by-n 2D grids, partitions them, and 4% plots them in one-second intervals. n is optional; it defaults to 60. 5% 6% Example: 7% graph_demo 8% 9% See also DELSQ, NUMGRID, GPLOT, TREEPLOT 10 11% Copyright 2006-2007, Timothy A. Davis, http://www.suitesparse.com 12 13if (nargin < 1) 14 % construct a 60-by-60 grid 15 n = 60 ; 16end 17 18clf 19 20for regions = {'Square', 'C' 'Disc', 'Annulus', 'Heart', 'Butterfly', 'L'} 21 22 % construct the grid 23 region = regions {1} ; 24 g = numgrid (region (1), n) ; 25 x = repmat (0:n-1, n, 1) ; 26 y = repmat (((n-1):-1:0)', 1, n) ; 27 A = delsq (g) ; 28 x = x (find (g)) ; %#ok 29 y = y (find (g)) ; %#ok 30 31 % plot the original grid 32 clf 33 subplot (2,2,1) 34 my_gplot (A, x, y) 35 title (sprintf ('%s-shaped 2D grid', region)) ; 36 axis equal 37 axis off 38 39 % bisect the graph 40 s = bisect (A) ; 41 [i j] = find (A) ; 42 subplot (2,2,2) 43 my_gplot (sparse (i, j, s(i) == s(j)), x, y) ; 44 title ('node bisection') ; 45 axis equal 46 axis off 47 48 % nested dissection 49 nsmall = floor (size (A,1) / 2) ; 50 defaults = 0 ; 51 while (1) 52 if (defaults) 53 % use defaults 54 [p cp cmember] = nesdis (A) ; 55 else 56 [p cp cmember] = nesdis (A, 'sym', nsmall) ; 57 end 58 59 % plot the components 60 subplot (2,2,3) 61 my_gplot (sparse (i, j, cmember(i) == cmember (j)), x, y) ; 62 if (defaults) 63 title ('nested dissection (defaults)') ; 64 else 65 title (sprintf ('nested dissection, nsmall %d', nsmall)) ; 66 end 67 axis equal 68 axis off 69 70 % plot the separator tree 71 subplot (2,2,4) 72 treeplot (cp, 'ko') 73 title ('separator tree') ; 74 axis equal 75 axis off 76 77 drawnow 78 pause (0.1) 79 80 if (defaults) 81 break ; 82 end 83 84 nsmall = floor (nsmall / 2) ; 85 if (nsmall < 20) 86 defaults = 1 ; 87 pause (0.2) 88 end 89 end 90end 91 92function my_gplot (A, x, y) 93 % my_gplot : like gplot, just a lot faster 94[i, j] = find (A) ; 95[ignore, p] = sort (max(i, j)) ; 96i = i (p) ; 97j = j (p) ; 98nans = repmat (NaN, size (i)) ; 99x = [ x(i) x(j) nans ]' ; 100y = [ y(i) y(j) nans ]' ; 101plot (x (:), y (:)) ; 102