0001 function output = prufer(g, code)
0002
0003
0004
0005
0006
0007
0008
0009 if nargin==1
0010 n = nv(g);
0011 m = ne(g);
0012 if (m ~= n-1)
0013 error('Input graph is not a tree')
0014 end
0015 if (~isconnected(g))
0016 error('Input graph is not a tree')
0017 end
0018
0019 if (n < 2)
0020 error('Algorithm applies only to trees with 2 or more vertices')
0021 end
0022
0023 if (n==2)
0024 output=[];
0025 return
0026 end
0027
0028 t = graph;
0029 copy(t,g);
0030
0031 names = 1:n;
0032 output = zeros(1,n-2);
0033
0034 for i=1:n-2
0035
0036 d = deg(t);
0037 v = min(find(d==1));
0038
0039
0040 w = neighbors(t,v);
0041
0042 output(i) = names(w);
0043
0044
0045 delete(t,v);
0046 names = [names(1:v-1),names(v+1:end)];
0047 end
0048
0049 free(t)
0050 return
0051 end
0052
0053 if ~prufer_check(code)
0054 error('Input is not a valid Prufer code')
0055 end
0056
0057 n = length(code) + 2;
0058
0059 resize(g,0);
0060 resize(g,n);
0061
0062 verts = 1:n;
0063 edges = zeros(n-1,2);
0064
0065 for k=1:n-2
0066 u = min(setdiff(verts,code));
0067 v = code(1);
0068 e = [u,v];
0069 edges(k,:) = e;
0070 code = code(2:end);
0071 i = find(verts == u);
0072 verts = [verts(1:i-1),verts(i+1:end)];
0073 end
0074
0075
0076 edges(n-1,:) = verts;
0077 add(g,edges);
0078
0079
0080
0081
0082 function ok = prufer_check(list)
0083 ok = false;
0084 n = length(list)+2;
0085
0086 if (any(list > n)) || (any(list < 1)) || (any(list ~= round(list)))
0087 return
0088 end
0089
0090 ok = true;
0091
0092