Exporting from MATLAB
From SpatoWiki
Calculating shortest-path trees in MATLAB
MatlabBGL is a package that provides various network-related algorithms, including Dijkstra's algorithm for finding shortest-paths. If your network is a structure with a field w that contains the weight matrix and a field N specifying the number of nodes, then the following code will compute all shortest-path trees and store the predecessor vectors in the field pred and the shortest-path distances in the field D:
[i j a] = find(g.w); if (useInverseWeights); a = 1./a; end A = sparse(i, j, a); [g.D, g.Dtop, g.pred] = all_shortest_path_trees(g.A, calcDtop); g.D = zeros(N); g.pred = zeros(N); for i=1:g.N [g.D(i,:) g.pred(i,:)] = dijkstra_sp(sparse(A), i); end
save_spato.m
The following function will create a SPaTo document from a network represented by a MATLAB structure (for details about the MATLAB structure, read the function documentation; for details about the SPaTo document format, see How to prepare data files). Note that Windows users might have to adapt some of the system(...) calls that create and compress the .spato directory.
function save_spato(g, filename, title, proj) % SAVE_SPATO(G, FILENAME, TITLE, PROJ) saves the network G as a SPaTo Document % % Example usage: % save_spato(g, '/path/to/file.spato', 'My Network'); % % The network structure must be in the format returned by load_wg_network % or load_aviation_network, with G.N being the number of nodes in the network % and G.w the N-by-N weight matrix. % % To provide a meaningful map view in SPaTo, G.nodes.poslong and G.nodes.poslat % should each be an N-by-1 vector containing the longitude/X- and % latitude/Y-coordinate, respectively. % % Node names (displayed in the lower right corner of SPaTo) will be saved % if G.nodes.name is an N-by-1 cell array of strings. % % Node labels (displayed next to the node in SPaTo) will be "Node %d" by default. % If G.nodes.lid is an N-by-1 cell array of strings or if G.nodes.id is an N-by-1 % vector, its values are used instead. % % If G.pred exists, the shortest-path trees encoded by it will be saved. % Otherwise, SPaTo will compute shortest-path trees. G.pred(i,j) is the % predecessor of node j in the shortest path from i to j. % % If G.D and/or G.SPTD exist, they will be saved as shortest-path distance % and shortest-path-tree dissimilarity matrices, respectively. % % Various quantities in G.nodes might be saved as node property vectors. % % The TITLE parameter is the name of the network displayed in the network % detail panel in SPaTo. % % The (optional) PROJ parameter specifies the geographic projection to use % (use 'Albers' for the continents, 'LonLat Roll' for full-world maps, and % 'LonLat' for intermediate (large parts of the world) or small-scale % maps, e.g. cities). If omitted, 'LonLat' is used. if (nargin < 4); proj = 'LonLat'; end useBlobs = false; compress = false; fprintf(['### Writing SPaTo document to ' filename ' (blobs=' num2str(useBlobs) ', compress=' num2str(compress) ') ...\n']); if ((length(filename) < 6) || ~strcmp(filename(end-5:end), '.spato')); filename = [filename '.spato']; end dir = filename; if (compress); dir = [dir '_tmp']; end system(['rm -rf "' dir '"']); if (compress); system(['rm -rf "' filename '"']); end system(['mkdir -p "' dir '"']); if (useBlobs); system(['mkdir -p "' dir '/blobs"']); end % write document.xml f = fopen([dir '/document.xml'], 'w'); fprintf(f, '<?xml version="1.0" ?>\n'); fprintf(f, '<document>\n'); fprintf(f, ' <title>%s</title>\n', title); if (isfield(g, 'meta')) fprintf(f, ' <description>\n'); for i=1:length(g.meta); fprintf(f, ' %s\n', char(g.meta{i})); end; clear i fprintf(f, ' </description>\n'); end fprintf(f, ' <nodes src="nodes.xml" />\n'); srcattr = ''; if (~useBlobs); srcattr = ' src="links.xml"'; end blobattr = ''; if (useBlobs); blobattr = ' blob="links"'; end fprintf(f, ' <links%s%s />\n', srcattr, blobattr); if (isfield(g, 'pred')); srcattr = ''; if (~useBlobs); srcattr = ' src="spt.xml"'; end blobattr = ''; if (useBlobs); blobattr = ' blob="spt"'; end fprintf(f, ' <slices name="SPT"%s%s />\n', srcattr, blobattr); end if (isfield(g, 'nodes') && any(isfield(g.nodes, { 'k', 'w', 'bc', 'c' }))) fprintf(f, ' <dataset src="nodeprops.xml" selected="true" />\n'); end if (isfield(g, 'D') || isfield(g, 'SPTD')); fprintf(f, ' <dataset src="dist.xml" />\n'); end fprintf(f, '</document>\n'); fclose(f); % write nodes.xml f = fopen([dir '/nodes.xml'], 'w'); fprintf(f, '<?xml version="1.0" ?>\n'); fprintf(f, '<nodes>\n'); fprintf(f, ' <projection name="%s" />\n', proj); for i=1:g.N id = num2str(i); name = ['Node ' id]; location = sprintf('%g,%g', rand(1), rand(1)); strength = full(sum(g.w(i,:))); if (isfield(g, 'nodes')) if (isfield(g.nodes, 'name')); name = g.nodes.name{i}; end if (isfield(g.nodes, 'lid')); id = g.nodes.lid{i}; elseif (isfield(g.nodes, 'id')); id = g.nodes.id(i); if (isnumeric(id)); id = num2str(id); end; end if (isfield(g.nodes, 'poslong') && isfield(g.nodes, 'poslat')) location = sprintf('%g,%g', g.nodes.poslong(i), g.nodes.poslat(i)); end end fprintf(f, ' <node id="%s" name="%s" location="%s" strength="%g" />\n', ... xmlencode(id, true), xmlencode(name, true), location, strength); end; clear i fprintf(f, '</nodes>\n'); fclose(f); % write links.xml if (useBlobs) writeSparseMatrixBlob('links', g.w); else f = fopen([dir '/links.xml'], 'w'); fprintf(f, '<?xml version="1.0" ?>\n'); fprintf(f, '<links>\n'); for i=1:g.N fprintf(f, ' <source index="%d">\n', i); I = find(g.w(i,:)); for j=I fprintf(f, ' <target index="%d" weight="%g" />\n', j, full(g.w(i,j))); end; clear j I fprintf(f, ' </source>\n'); end; clear i fprintf(f, '</links>\n'); fclose(f); end % write spt.xml if (isfield(g, 'pred')) fprintf('SPT: '); tic if (useBlobs) writeMatrixBlob('spt', 'int', g.pred - 1); else f = fopen([dir '/spt.xml'], 'w'); fprintf(f, '<?xml version="1.0" ?>\n'); fprintf(f, '<slices name="SPT">\n'); writeMatrixXML(f, 'slice', g.pred); fprintf(f, '</slices>\n'); fclose(f); end fprintf(' - %.3f secs\n', toc); end % write nodeprops.xml if (isfield(g, 'nodes') && any(isfield(g.nodes, { 'k', 'w', 'bc', 'wbc', 'c', 'wc', 'd', 'o', 'kk', 'kkw', 'ww', 'www' }))) f = fopen([dir '/nodeprops.xml'], 'w'); fprintf(f, '<?xml version="1.0" ?>\n'); fprintf(f, '<dataset name="Node Properties">\n'); if (isfield(g.nodes, 'k')); writeData(f, 'Node Degree', g.nodes.k, '', 'true'); end if (isfield(g.nodes, 'w')); writeData(f, 'Node Strength', g.nodes.w, ' selected="true"', 'true'); end if (isfield(g.nodes, 'bc')); writeData(f, 'Betweenness Centrality (topology)', g.nodes.bc, '', 'true'); end if (isfield(g.nodes, 'wbc')); writeData(f, 'Betweenness Centrality (weighted)', g.nodes.wbc, '', 'true'); end if (isfield(g.nodes, 'c')); writeData(f, 'Clustering coefficient (unweighted)', g.nodes.c, '', 'false'); end if (isfield(g.nodes, 'wc')); writeData(f, 'Clustering coefficient (weighted)', g.nodes.wc, '', 'true'); end if (isfield(g.nodes, 'd')); writeData(f, 'Distance strength', g.nodes.d, '', 'true'); end if (isfield(g.nodes, 'o')); writeData(f, 'Outreach', g.nodes.o, '', 'true'); end if (isfield(g.nodes, 'kk')); writeData(f, 'Next-neighbor degree (unweighted)', g.nodes.kk, '', 'true'); end if (isfield(g.nodes, 'kkw')); writeData(f, 'Next-neighbor degree (weighted)', g.nodes.kkw, '', 'true'); end if (isfield(g.nodes, 'ww')); writeData(f, 'Next-neighbor strength (unweighted)', g.nodes.ww, '', 'true'); end if (isfield(g.nodes, 'www')); writeData(f, 'Next-neighbor strength (weighted)', g.nodes.www, '', 'true'); end fprintf(f, '</dataset>\n'); fclose(f); end % write dist.xml if (isfield(g, 'D') || isfield(g, 'SPTD')) f = fopen([dir '/dist.xml'], 'w'); fprintf(f, '<?xml version="1.0" ?>\n'); fprintf(f, '<dataset name="Distance Measures">\n'); if (isfield(g, 'D')) fprintf('SPD: '); tic blobattr = ''; if (useBlobs); blobattr = ' blob="dist_spd"'; end fprintf(f, ' <data name="SPD"%s distmat="true">\n', blobattr); fprintf(f, ' <colormap log="true" minval="%g" maxval="%g" />\n', min(nonzeros(g.D)), max(nonzeros(g.D))); if (useBlobs); writeMatrixBlob('dist_spd', 'float', g.D); else writeMatrixXML(f, 'values', g.D); end fprintf(f, ' </data>\n'); fprintf(' - %.3f secs\n', toc); end if (isfield(g, 'SPTD')) fprintf('SPTD: '); tic blobattr = ''; if (useBlobs); blobattr = ' blob="dist_sptd"'; end fprintf(f, ' <data name="SPTD"%s>\n', blobattr); fprintf(f, ' <colormap minval="%g" maxval="%g" />\n', min(nonzeros(g.SPTD)), max(nonzeros(g.SPTD))); if (useBlobs); writeMatrixBlob('dist_sptd', 'float', g.SPTD); else writeMatrixXML(f, 'values', g.D); end fprintf(f, ' </data>\n'); fprintf(' - %.3f secs\n', toc); end fprintf(f, '</dataset>\n'); fclose(f); fprintf('\n'); end % compress if (compress) system(['cd "' dir '"; zip -9 -r ___compressed___.zip *; cd ../']); system(['mv "' dir '/___compressed___.zip" "' filename '"']); system(['rm -r "' dir '"']); end function str = xmlencode(str, escapeQuotes) str = strrep(str, '<', '<'); str = strrep(str, '>', '>'); str = strrep(str, '&', '&'); if (escapeQuotes); str = strrep(str, '"', '\"'); end end function writeData(ff, dataname, data, addattr, log) fprintf(ff, ' <data name="%s"%s>\n', dataname, addattr); fprintf(ff, ' <colormap log="%s" />\n', log); fprintf(ff, ' <values>%s</values>\n', implode('', ' ', data, '')); fprintf(ff, ' </data>\n'); end function writeMatrixXML(ff, tagname, data) for i=1:g.N fprintf(' %d', i); fprintf(ff, ' <%s root="%d">', tagname, i); for j=1:g.N if (mod(j, 100) == 1); fprintf(ff, '\n '); end fprintf(ff, ' %g', data(i,j)); end fprintf(ff, '\n </%s>\n', tagname); end end function writeMatrixBlob(blobname, type, data) fb = fopen([dir '/blobs/' blobname], 'w', 'b'); % Java is Big-Endian typeID = 1; % float if (strcmp(type, 'int')); typeID = 0; end fwrite(fb, [typeID g.N g.N -1], 'int'); % blob type (0=int, 1=float) and size (g.N x g.N) for i=1:g.N; fwrite(fb, data(i,:), type); end fclose(fb); clear fb end function writeSparseMatrixBlob(blobname, data) fb = fopen([dir '/blobs/' blobname], 'w', 'b'); fwrite(fb, [2 size(data,1)], 'int'); % blob type (2=SparseMatrix) and size (g.N) for i=1:size(data,1) [~, J, w] = find(data(i,:)); fwrite(fb, length(J), 'int'); % number of links from node i fwrite(fb, J-1, 'int'); % indices of end nodes fwrite(fb, w, 'float'); % corresponding link weights end end end
