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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
function find_components_example(example, dopause)
%FIND_COMPONENTS_EXAMPLE gives an example usage of find_components.
%
% Example:
% find_components_example(0) % a small example, with lots of printing
% find_components_example(1) % Doug's example, with lots of printing
% find_components_example(2) % a large example, just plotting
% find_components_example(A) % use the matrix A for the example
%
% See http://blogs.mathworks.com/pick/2008/08/18 for Doug Hull's description of
% the problem this m-file solves. With no inputs, Doug's example is used.
%
% See also FIND_COMPONENTS, LARGEST_COMPONENT, DMPERM, GPLOT
% find_components, Copyright (c) 2008, Timothy A Davis. All Rights Reserved.
% SPDX-License-Identifier: BSD-3-clause
%-------------------------------------------------------------------------------
% construct an image
%-------------------------------------------------------------------------------
if (nargin < 1)
example = 1 ;
end
if (example == 0)
A = [ 1 2 2 3
1 1 2 3
0 0 1 2
0 1 3 3 ] ;
elseif (example == 1)
A = [ 2 2 1 1 2
3 0 1 0 1
3 2 2 2 1
1 2 2 1 2
0 3 2 0 1 ] ;
elseif (example == 2)
A = round (rand (30) * 2) ;
else
A = example ;
end
[m n] = size (A) ;
%-------------------------------------------------------------------------------
% find all of its components
%-------------------------------------------------------------------------------
tic
[p r nc G xy] = find_components (A,1) ;
t = toc ;
fprintf ('Image size: %d-by-%d, time taken: %g seconds\n', m, n, t) ;
%-------------------------------------------------------------------------------
% walk through the components, plotting and printing them.
%-------------------------------------------------------------------------------
prompt = 'hit enter to single-step, ''a'' to show all, ''q'' to quit: ' ;
small = (max (m,n) <= 10) ;
if (nargin < 2)
dopause = 1 ;
end
for k = 1:nc
% get the nodes of the kth component
nodes = p (r (k) : r (k+1)-1) ;
% for large graphs, do not show components of size 1
if (~small && length (nodes) == 1)
continue
end
% plot the graph with the kth component highlighted
hold off
gplot (G, xy, '-') ;
hold on
[X,Y] = gplot (G * sparse (nodes, nodes, 1, m*n, m*n), xy, 'r-') ;
plot (X, Y, 'r-', 'LineWidth', 3) ;
axis ([0 n+1 0 m+1]) ;
a = A (p (r (k))) ;
siz = length (nodes) ;
Title = sprintf ('Graph component %d, size %d, value %g', k, siz, a) ;
title (Title, 'FontSize', 20) ;
label_nodes (xy, A, small, nodes) ;
drawnow
% print the image and the kth component, if the image is small
if (small)
fprintf ('\n%s\n', Title) ;
C = nan (m,n) ;
C (nodes) = a ;
fprintf ('A = \n') ; disp (A) ;
fprintf ('the component = \n') ; disp (C) ;
end
% pause, or prompt the user
if (dopause && (k < nc))
s = input (prompt, 's') ;
dopause = isempty (s) ;
if (~dopause && s (1) == 'q')
break ;
end
else
pause (0.5)
end
end
%-------------------------------------------------------------------------------
% plot the whole graph, no components highlighted
%-------------------------------------------------------------------------------
hold off
gplot (G, xy, '-') ;
title (sprintf ('%d connected components', nc), 'FontSize', 20) ;
axis ([0 n+1 0 m+1]) ;
label_nodes (xy, A, small)
%-------------------------------------------------------------------------------
function label_nodes (xy, A, small, nodes)
%LABEL_NODES label all the nodes in the plot
if (small)
[m n] = size (A) ;
for i = 1:m*n
text (xy (i,1), xy (i,2), sprintf ('%g', A (i)), 'FontSize', 20) ;
end
if (nargin == 4)
for i = nodes
text (xy (i,1), xy (i,2), sprintf ('%g', A (i)), ...
'FontSize', 20, 'Color', 'r') ;
end
end
end
|
