Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/GraphViz/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 % [Adj, labels, x, y] = dot_to_graph(filename)
wolffd@0 3 % Extract a matrix representation, node labels, and node position coordinates
wolffd@0 4 % from a file in GraphViz format http://www.research.att.com/sw/tools/graphviz
wolffd@0 5 %
wolffd@0 6 % INPUTS:
wolffd@0 7 % 'filename' - the file in DOT format containing the graph layout.
wolffd@0 8 % OUTPUT:
wolffd@0 9 % 'Adj' - an adjacency matrix representation of the graph in 'filename';
wolffd@0 10 % 'labels' - a character array with the names of the nodes of the graph;
wolffd@0 11 % 'x' - a row vector with the x-coordinates of the nodes in 'filename';
wolffd@0 12 % 'y' - a row vector with the y-coordinates of the nodes in 'filename'.
wolffd@0 13 %
wolffd@0 14 % WARNINGS: not guaranted to parse ANY GraphViz file. Debugged on undirected
wolffd@0 15 % sample graphs from GraphViz(Heawood, Petersen, ER, ngk10_4, process).
wolffd@0 16 % Complaines about RecursionLimit set only to 500 on huge graphs.
wolffd@0 17 % Ignores singletons (disjoint nodes).
wolffd@0 18 % Sample DOT code "ABC.dot", read by [Adj, labels, x, y] = dot_to_graph('ABC.dot')
wolffd@0 19 % digraph G {
wolffd@0 20 % A [pos="28,31"];
wolffd@0 21 % B [pos="74,87"];
wolffd@0 22 % A -- B [pos="e,61,71 41,47 46,53 50,58 55,64"];
wolffd@0 23 % }
wolffd@0 24 % last modified: Jan 2004
wolffd@0 25 % by Alexi Savov: asavov @wustl.edu | http://artsci.wustl.edu/~azsavov
wolffd@0 26 % Leon Peshkin: pesha @ai.mit.edu | http://www.ai.mit.edu/~pesha
wolffd@0 27 % Tom Minka
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. * * *');
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. * * *');
wolffd@0 38 end;
wolffd@0 39
wolffd@0 40 Nlns = size(dot_lines,1); % The number of lines;
wolffd@0 41 nodes = {};
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 Adj = [];
wolffd@0 45 for line_ndx = 1:Nlns % This section sets the adjacency matrix A(Lnode,Rnode) = edge_id.
wolffd@0 46 line = dot_lines(line_ndx,:);
wolffd@0 47 Ddash_pos = strfind(line, ' -- ') + 1; % double dash positions
wolffd@0 48 arrow_pos = strfind(line, ' -> ') + 1; % arrow dash positions
wolffd@0 49 tokens = strread(line,'%s','delimiter',' "');
wolffd@0 50 left_bound = 1;
wolffd@0 51 for dash_pos = [Ddash_pos arrow_pos]; % if empty - not a POS line
wolffd@0 52 Lnode = sscanf(line(left_bound:dash_pos -2), '%s');
wolffd@0 53 Rnode = sscanf(line(dash_pos +3 : length(line)-1),'%s',1);
wolffd@0 54 Lndx = strmatch(Lnode, nodes, 'exact');
wolffd@0 55 Rndx = strmatch(Rnode, nodes, 'exact');
wolffd@0 56 if isempty(Lndx) % extend our list of nodes
wolffd@0 57 nodes{end+1} = Lnode;
wolffd@0 58 Lndx = length(nodes);
wolffd@0 59 end
wolffd@0 60 if isempty(Rndx)
wolffd@0 61 nodes{end+1} = Rnode;
wolffd@0 62 Rndx = length(nodes);
wolffd@0 63 end
wolffd@0 64 Adj(Lndx, Rndx) = edge_id;
wolffd@0 65 if ismember(dash_pos, Ddash_pos) % The edge is undirected, A(Rndx,LndxL) is also set to 1;
wolffd@0 66 Adj(Rndx, Lndx) = edge_id;
wolffd@0 67 end
wolffd@0 68 edge_id = edge_id + 1;
wolffd@0 69 left_bound = dash_pos + 3;
wolffd@0 70 unread = setdiff(unread, line_ndx);
wolffd@0 71 end
wolffd@0 72 end
wolffd@0 73 Nvrt = length(nodes); % number of vertices we found [Do we ever have singleton vertices ???]
wolffd@0 74 % nodes = strvcat(nodes); % convert to the searchable array
wolffd@0 75 x = zeros(1, Nvrt);
wolffd@0 76 y = zeros(1, Nvrt);
wolffd@0 77 labels = nodes;
wolffd@0 78 % Find node's position coordinates if they are contained in 'filename'.
wolffd@0 79 for line_ndx = unread % Look for node's coordinates among the 'unread' lines.
wolffd@0 80 line = dot_lines(line_ndx,:);
wolffd@0 81 bra_pos = strfind(line, '['); % has to have "[" if it has the label
wolffd@0 82 lst_node = 0;
wolffd@0 83 for node = 1:Nvrt % look through the list of nodes
wolffd@0 84 % THE NEXT STATEMENT we assume no node is substring of any other node
wolffd@0 85 lbl_pos = strfind(line, nodes{node});
wolffd@0 86 if (~isempty(lbl_pos) & ~isempty(bra_pos) & (x(node) == 0)) % make sure we have not seen it
wolffd@0 87 if (lbl_pos(1) < bra_pos(1)) % label has to be to the left of bracket
wolffd@0 88 lst_node = node;
wolffd@0 89 end
wolffd@0 90 end
wolffd@0 91 end
wolffd@0 92 if lst_node
wolffd@0 93 pos_pos = strfind(line, 'pos'); % position of the "pos"
wolffd@0 94 if ~isempty(pos_pos) % this line contains SOME position
wolffd@0 95 [node_pos] = sscanf(line(pos_pos:end), ' pos = "%d,%d"')';
wolffd@0 96 x(lst_node) = node_pos(1);
wolffd@0 97 y(lst_node) = node_pos(2);
wolffd@0 98 end
wolffd@0 99 % minka
wolffd@0 100 label_pos = strfind(line, 'label'); % position of the "label"
wolffd@0 101 if ~isempty(label_pos)
wolffd@0 102 label_end = strfind(line(label_pos:end),',');
wolffd@0 103 labels{lst_node} = unquote(line(label_pos+(6:label_end(1)-2)));
wolffd@0 104 end
wolffd@0 105 end
wolffd@0 106 end
wolffd@0 107
wolffd@0 108 if (isempty(find(x)) & (nargout > 2)) % If coordinates were requested, but not found in 'filename'.
wolffd@0 109 warning('File does not contain node coordinates.');
wolffd@0 110 end;
wolffd@0 111 if ~(size(Adj,1)==size(Adj,2)) % Make sure Adj is a square matrix. ?
wolffd@0 112 Adj = eye(max(size(Adj)),size(Adj,1))*Adj*eye(size(Adj,2),max(size(Adj)));
wolffd@0 113 end;
wolffd@0 114 x = .9*(x-min(x))/range(x)+.05; % normalise and push off margins
wolffd@0 115 y = .9*(y-min(y))/range(y)+.05;
wolffd@0 116
wolffd@0 117
wolffd@0 118
wolffd@0 119 function s = unquote(s)
wolffd@0 120
wolffd@0 121 s = strrep(s,'"','');