Home > matgraph > @graph > prufer.m

prufer

PURPOSE ^

prufer --- convert a tree to/from its Prufer code

SYNOPSIS ^

function output = prufer(g, code)

DESCRIPTION ^

 prufer --- convert a tree to/from its Prufer code
 output = prufer(g) returns the Prufer code for g (assuming g is a tree)
 prufer(g,code) overwrites g with a tree based on the code 

 The Prufer code is a way to map bijectively trees on n vertices 
 into n-2 long sequences of integers drawn from [n].

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function output = prufer(g, code)
0002 % prufer --- convert a tree to/from its Prufer code
0003 % output = prufer(g) returns the Prufer code for g (assuming g is a tree)
0004 % prufer(g,code) overwrites g with a tree based on the code
0005 %
0006 % The Prufer code is a way to map bijectively trees on n vertices
0007 % into n-2 long sequences of integers drawn from [n].
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;  % temporary copy of g
0029     copy(t,g);
0030     
0031     names = 1:n;  % names of the vertices
0032     output = zeros(1,n-2);
0033     
0034     for i=1:n-2
0035         % find least leaf
0036         d = deg(t);
0037         v = min(find(d==1));
0038         
0039         % find neighbor of the least leaf
0040         w = neighbors(t,v);
0041         
0042         output(i) = names(w); % add this vertex to the output
0043         
0044         % delete v and its name
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)  % check if list is a valid Prufer code
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

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003