Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/GraphViz/Old/dot_to_graph.m @ 0:e9a9cd732c1e tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
rev   line source
wolffd@0 1 function [Adj, labels, x, y] = dot_to_graph(filename)
wolffd@0 2
wolffd@0 3 % [Adj, labels, x, y] = dot_to_graph(filename)
wolffd@0 4 % Extract a matrix representation, node labels, and node position coordinates
wolffd@0 5 % from a file in GraphViz format http://www.research.att.com/sw/tools/graphviz
wolffd@0 6 %
wolffd@0 7 % INPUTS:
wolffd@0 8 % 'filename' - the file in DOT format containing the graph layout.
wolffd@0 9 % OUTPUT:
wolffd@0 10 % 'Adj' - an adjacency matrix representation of the graph in 'filename';
wolffd@0 11 % 'labels' - a character array with the names of the nodes of the graph;
wolffd@0 12 % 'x' - a row vector with the x-coordinates of the nodes in 'filename';
wolffd@0 13 % 'y' - a row vector with the y-coordinates of the nodes in 'filename'.
wolffd@0 14 %
wolffd@0 15 % WARNINGS: not guaranted to parse ANY GraphViz file. Debugged on undirected
wolffd@0 16 % sample graphs from GraphViz(Heawood, Petersen, ER, ngk10_4, process).
wolffd@0 17 % Complaines about RecursionLimit set only to 500 on huge graphs.
wolffd@0 18 % Ignores singletons (disjoint nodes).
wolffd@0 19 % Sample DOT code "ABC.dot", read by [Adj, labels, x, y] = dot_to_graph('ABC.dot')
wolffd@0 20 % digraph G {
wolffd@0 21 % A [pos="28,31"];
wolffd@0 22 % B [pos="74,87"];
wolffd@0 23 % A -- B [pos="e,61,71 41,47 46,53 50,58 55,64"];
wolffd@0 24 % }
wolffd@0 25 % last modified: Jan 2004
wolffd@0 26 % by Alexi Savov: asavov @wustl.edu | http://artsci.wustl.edu/~azsavov
wolffd@0 27 % Leon Peshkin: pesha @ai.mit.edu | http://www.ai.mit.edu/~pesha
wolffd@0 28
wolffd@0 29 if ~exist(filename) % Checks whether the specified file exists.
wolffd@0 30 error('* * * File does not exist or could not be found. * * *'); return;
wolffd@0 31 end;
wolffd@0 32
wolffd@0 33 lines = textread(filename,'%s','delimiter','\n','commentstyle','c'); % Read file into cell array
wolffd@0 34 dot_lines = strvcat(lines); % of lines, ignoring C-style comments
wolffd@0 35
wolffd@0 36 if findstr(dot_lines(1,:), 'graph ') == [] % Is this a DOT file ?
wolffd@0 37 error('* * * File does not appear to be in valid DOT format. * * *'); return;
wolffd@0 38 end;
wolffd@0 39
wolffd@0 40 Nlns = size(dot_lines,1); % The number of lines;
wolffd@0 41 labels = {};
wolffd@0 42 unread = 1:Nlns; % 'unread' list of lines which has not been examined yet
wolffd@0 43 edge_id = 1;
wolffd@0 44 for line_ndx = 1:Nlns % This section sets the adjacency matrix A(Lnode,Rnode) = edge_id.
wolffd@0 45 line = dot_lines(line_ndx,:);
wolffd@0 46 Ddash_pos = strfind(line, ' -- ') + 1; % double dash positions
wolffd@0 47 arrow_pos = strfind(line, ' -> ') + 1; % arrow dash positions
wolffd@0 48 tokens = strread(line,'%s','delimiter',' "');
wolffd@0 49 left_bound = 1;
wolffd@0 50 for dash_pos = [Ddash_pos arrow_pos]; % if empty - not a POS line
wolffd@0 51 Lnode = sscanf(line(left_bound:dash_pos -2), '%s');
wolffd@0 52 Rnode = sscanf(line(dash_pos +3 : length(line)-1),'%s',1);
wolffd@0 53 Lndx = strmatch(Lnode, labels, 'exact');
wolffd@0 54 Rndx = strmatch(Rnode, labels, 'exact');
wolffd@0 55 if isempty(Lndx) % extend our list of labels
wolffd@0 56 labels{end+1} = Lnode;
wolffd@0 57 Lndx = length(labels);
wolffd@0 58 end
wolffd@0 59 if isempty(Rndx)
wolffd@0 60 labels{end+1} = Rnode;
wolffd@0 61 Rndx = length(labels);
wolffd@0 62 end
wolffd@0 63 Adj(Lndx, Rndx) = edge_id;;
wolffd@0 64 if ismember(dash_pos, Ddash_pos) % The edge is undirected, A(Rndx,LndxL) is also set to 1;
wolffd@0 65 Adj(Rndx, Lndx) = edge_id;
wolffd@0 66 end
wolffd@0 67 edge_id = edge_id + 1;
wolffd@0 68 left_bound = dash_pos + 3;
wolffd@0 69 unread = setdiff(unread, line_ndx);
wolffd@0 70 end
wolffd@0 71 end
wolffd@0 72 Nvrt = length(labels); % number of vertices we found [Do we ever have singleton vertices ???]
wolffd@0 73 % labels = strvcat(labels); % convert to the searchable array
wolffd@0 74 x = zeros(1, Nvrt);
wolffd@0 75 y = zeros(1, Nvrt);
wolffd@0 76 lst_node = 0;
wolffd@0 77 % Find node's position coordinates if they are contained in 'filename'.
wolffd@0 78 for line_ndx = unread % Look for node's coordiantes among the 'unread' lines.
wolffd@0 79 line = dot_lines(line_ndx,:);
wolffd@0 80 bra_pos = strfind(line, '['); % has to have "[" if it has the lable
wolffd@0 81 pos_pos = strfind(line, 'pos'); % position of the "pos"
wolffd@0 82 for node = 1:Nvrt % look through the list of labels
wolffd@0 83 % THE NEXT STATEMENT we assume no label is substring of any other label
wolffd@0 84 lbl_pos = strfind(line, labels{node});
wolffd@0 85 if (~isempty(lbl_pos) & ~isempty(bra_pos) & (x(node) == 0)) % make sure we have not seen it
wolffd@0 86 if (lbl_pos(1) < bra_pos(1)) % label has to be to the left of braket
wolffd@0 87 lst_node = node;
wolffd@0 88 end
wolffd@0 89 end
wolffd@0 90 end
wolffd@0 91 if (~isempty(pos_pos) & lst_node) % this line contains SOME position
wolffd@0 92 [node_pos] = sscanf(line(pos_pos:length(line)), ' pos = "%d,%d"')';
wolffd@0 93 x(lst_node) = node_pos(1);
wolffd@0 94 y(lst_node) = node_pos(2);
wolffd@0 95 lst_node = 0; % not to assign position several times
wolffd@0 96 end
wolffd@0 97 end
wolffd@0 98
wolffd@0 99 if (isempty(find(x)) & (nargout > 2)) % If coordinates were requested, but not found in 'filename'.
wolffd@0 100 warning('File does not contain node coordinates.');
wolffd@0 101 end;
wolffd@0 102 if ~(size(Adj,1)==size(Adj,2)) % Make sure Adj is a square matrix. ?
wolffd@0 103 Adj = eye(max(size(Adj)),size(Adj,1))*Adj*eye(size(Adj,2),max(size(Adj)));
wolffd@0 104 end;
wolffd@0 105 x = .9*(x-min(x))/range(x)+.05; % normalise and push off margins
wolffd@0 106 y = .9*(y-min(y))/range(y)+.05;
wolffd@0 107