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