Wednesday, 30 March 2011

Serialisation of trees in Matlab

I have written a small but handy Matlab function to serialise tree structures from an adjacency matrix. I use the string then to process the trees in Python, but one can come up with some other reasons to do that.

The function has some constraints, i.e. since there is no separators between node indices it will only work for trees with small number of nodes, but it was sufficient for me and it is easy to extend.

function str = adjmatrix2string( adjmatrix, node, parent )
%ADJMATRIX2STRING converts an adjacency matrix of a tree to 
string
%   Converts an adjacency matrix of a tree to its 
%   string representation of 
%   the form 1(2(34)5(67))
%   adjmatrix - adjacency matrix
%   node - index of the current node
%   parent - index of parrent node, 0 for root
%   call example: adjmatrix2string(adjmatrix, 1, 0)

str = int2str(node);
childnodes = find(adjmatrix(node, :));
% only one node in a tree
if isempty(childnodes)
str = strcat(str, node);
elseif length(childnodes) == 1
% node is a root
if parent == 0
str = strcat(str, '(', adjmatrix2string(adjmatrix, 
             childnodes(1), node), ')');
end
else
str = strcat(str, '(');
for childnode = childnodes
if childnode ~= parent
str = strcat(str, adjmatrix2string(adjmatrix, 
      childnode, node));
end
end
str = strcat(str, ')');
end
end

It will convert an adjacency matrix
$\begin{pmatrix}0&1&1&0&1&0&0\\1&0&1&1&0&0&0\\0&1&0&0&0&0&0\\0&1&0&0&0&0&0\\1&0&0&0&0&1&1\\0&0&0&0&1&0&0\\0&0&0&0&1&0&0\\\end{pmatrix}$
to the string '1(2(34)5(67))'.

No comments:

Post a Comment