Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/GraphViz/make_layout.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 [x, y] = layout_dag(adj)
wolffd@0 2 % MAKE_LAYOUT Creates a layout from an adjacency matrix
wolffd@0 3 %
wolffd@0 4 % [X, Y] = MAKE_LAYOUT(ADJ)
wolffd@0 5 %
wolffd@0 6 % Inputs :
wolffd@0 7 % ADJ = adjacency matrix (source, sink)
wolffd@0 8 %
wolffd@0 9 % Outputs :
wolffd@0 10 % X, Y : Positions of nodes
wolffd@0 11 %
wolffd@0 12 % Usage Example : [X, Y] = make_layout(adj);
wolffd@0 13 %
wolffd@0 14 %
wolffd@0 15 % Note : Uses some very simple heuristics, so any other
wolffd@0 16 % algorithm would create a nicer layout
wolffd@0 17 %
wolffd@0 18 % See also
wolffd@0 19
wolffd@0 20 % Uses :
wolffd@0 21
wolffd@0 22 % Change History :
wolffd@0 23 % Date Time Prog Note
wolffd@0 24 % 13-Apr-2000 8:25 PM ATC Created under MATLAB 5.3.1.29215a (R11.1)
wolffd@0 25
wolffd@0 26 % ATC = Ali Taylan Cemgil,
wolffd@0 27 % SNN - University of Nijmegen, Department of Medical Physics and Biophysics
wolffd@0 28 % e-mail : cemgil@mbfys.kun.nl
wolffd@0 29
wolffd@0 30 N = size(adj,1);
wolffd@0 31 tps = toposort(adj);
wolffd@0 32
wolffd@0 33 if ~isempty(tps), % is directed ?
wolffd@0 34 level = zeros(1,N);
wolffd@0 35 for i=tps,
wolffd@0 36 idx = find(adj(:,i));
wolffd@0 37 if ~isempty(idx),
wolffd@0 38 l = max(level(idx));
wolffd@0 39 level(i)=l+1;
wolffd@0 40 end;
wolffd@0 41 end;
wolffd@0 42 else
wolffd@0 43 level = poset(adj,1)'-1;
wolffd@0 44 end;
wolffd@0 45
wolffd@0 46 y = (level+1)./(max(level)+2);
wolffd@0 47 y = 1-y;
wolffd@0 48 x = zeros(size(y));
wolffd@0 49 for i=0:max(level),
wolffd@0 50 idx = find(level==i);
wolffd@0 51 offset = (rem(i,2)-0.5)/10;
wolffd@0 52 x(idx) = (1:length(idx))./(length(idx)+1)+offset;
wolffd@0 53 end;
wolffd@0 54
wolffd@0 55 %%%%%%%
wolffd@0 56
wolffd@0 57 function [depth] = poset(adj, root)
wolffd@0 58 % POSET Identify a partial ordering among the nodes of a graph
wolffd@0 59 %
wolffd@0 60 % [DEPTH] = POSET(ADJ,ROOT)
wolffd@0 61 %
wolffd@0 62 % Inputs :
wolffd@0 63 % ADJ : Adjacency Matrix
wolffd@0 64 % ROOT : Node to start with
wolffd@0 65 %
wolffd@0 66 % Outputs :
wolffd@0 67 % DEPTH : Depth of the Node
wolffd@0 68 %
wolffd@0 69 % Usage Example : [depth] = poset(adj,12);
wolffd@0 70 %
wolffd@0 71 %
wolffd@0 72 % Note : All Nodes must be connected
wolffd@0 73 % See also
wolffd@0 74
wolffd@0 75 % Uses :
wolffd@0 76
wolffd@0 77 % Change History :
wolffd@0 78 % Date Time Prog Note
wolffd@0 79 % 17-Jun-1998 12:01 PM ATC Created under MATLAB 5.1.0.421
wolffd@0 80
wolffd@0 81 % ATC = Ali Taylan Cemgil,
wolffd@0 82 % SNN - University of Nijmegen, Department of Medical Physics and Biophysics
wolffd@0 83 % e-mail : cemgil@mbfys.kun.nl
wolffd@0 84
wolffd@0 85 adj = adj+adj';
wolffd@0 86
wolffd@0 87 N = size(adj,1);
wolffd@0 88 depth = zeros(N,1);
wolffd@0 89 depth(root) = 1;
wolffd@0 90 queue = root;
wolffd@0 91
wolffd@0 92 while 1,
wolffd@0 93 if isempty(queue),
wolffd@0 94 if all(depth), break;
wolffd@0 95 else
wolffd@0 96 root = find(depth==0);
wolffd@0 97 root = root(1);
wolffd@0 98 depth(root) = 1;
wolffd@0 99 queue = root;
wolffd@0 100 end;
wolffd@0 101 end;
wolffd@0 102 r = queue(1); queue(1) = [];
wolffd@0 103 idx = find(adj(r,:));
wolffd@0 104 idx2 = find(~depth(idx));
wolffd@0 105 idx = idx(idx2);
wolffd@0 106 queue = [queue idx];
wolffd@0 107 depth(idx) = depth(r)+1;
wolffd@0 108 end;
wolffd@0 109
wolffd@0 110 %%%%%%%%%
wolffd@0 111
wolffd@0 112 function [seq] = toposort(adj)
wolffd@0 113 % TOPOSORT A Topological ordering of nodes in a directed graph
wolffd@0 114 %
wolffd@0 115 % [SEQ] = TOPOSORT(ADJ)
wolffd@0 116 %
wolffd@0 117 % Inputs :
wolffd@0 118 % ADJ : Adjacency Matrix.
wolffd@0 119 % ADJ(i,j)==1 ==> there exists a directed edge
wolffd@0 120 % from i to j
wolffd@0 121 %
wolffd@0 122 % Outputs :
wolffd@0 123 % SEQ : A topological ordered sequence of nodes.
wolffd@0 124 % empty matrix if graph contains cycles.
wolffd@0 125 %
wolffd@0 126 % Usage Example :
wolffd@0 127 % N=5;
wolffd@0 128 % [l,u] = lu(rand(N));
wolffd@0 129 % adj = ~diag(ones(1,N)) & u>0.5;
wolffd@0 130 % seq = toposort(adj);
wolffd@0 131 %
wolffd@0 132 %
wolffd@0 133 % Note :
wolffd@0 134 % See also
wolffd@0 135
wolffd@0 136 % Uses :
wolffd@0 137
wolffd@0 138 % Change History :
wolffd@0 139 % Date Time Prog Note
wolffd@0 140 % 18-May-1998 4:44 PM ATC Created under MATLAB 5.1.0.421
wolffd@0 141
wolffd@0 142 % ATC = Ali Taylan Cemgil,
wolffd@0 143 % SNN - University of Nijmegen, Department of Medical Physics and Biophysics
wolffd@0 144 % e-mail : cemgil@mbfys.kun.nl
wolffd@0 145
wolffd@0 146 N = size(adj);
wolffd@0 147 indeg = sum(adj,1);
wolffd@0 148 outdeg = sum(adj,2);
wolffd@0 149 seq = [];
wolffd@0 150
wolffd@0 151 for i=1:N,
wolffd@0 152 % Find nodes with indegree 0
wolffd@0 153 idx = find(indeg==0);
wolffd@0 154 % If can't find than graph contains a cycle
wolffd@0 155 if isempty(idx),
wolffd@0 156 seq = [];
wolffd@0 157 break;
wolffd@0 158 end;
wolffd@0 159 % Remove the node with the max number of connections
wolffd@0 160 [dummy idx2] = max(outdeg(idx));
wolffd@0 161 indx = idx(idx2);
wolffd@0 162 seq = [seq, indx];
wolffd@0 163 indeg(indx)=-1;
wolffd@0 164 idx = find(adj(indx,:));
wolffd@0 165 indeg(idx) = indeg(idx)-1;
wolffd@0 166 end;
wolffd@0 167
wolffd@0 168
wolffd@0 169
wolffd@0 170