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