comparison toolboxes/FullBNT-1.0.7/GraphViz/make_layout.m @ 0:e9a9cd732c1e tip

first hg version after svn

+function [x, y] = layout_dag(adj)
+% MAKE_LAYOUT		Creates a layout from an adjacency matrix
+%
+%  [X, Y] = MAKE_LAYOUT(ADJ)
+%
+% Inputs :
+%	ADJ = adjacency matrix (source, sink)
+%
+% Outputs :
+%	X, Y : Positions of nodes
+%
+% Usage Example : [X, Y] = make_layout(adj);
+%
+%
+% Note	: Uses some very simple heuristics, so any other
+%         algorithm would create a nicer layout 
+%
+% See also 
+
+% Uses :
+
+% Change History :
+% Date		Time		Prog	Note
+% 13-Apr-2000	 8:25 PM	ATC	Created under MATLAB 5.3.1.29215a (R11.1)
+
+% ATC = Ali Taylan Cemgil,
+% SNN - University of Nijmegen, Department of Medical Physics and Biophysics
+% e-mail : [e-mail] 
+
+N = size(adj,1);
+tps = toposort(adj);
+
+if ~isempty(tps), % is directed ?
+  level = zeros(1,N);
+  for i=tps,
+    idx = find(adj(:,i));
+    if ~isempty(idx),
+      l = max(level(idx));
+      level(i)=l+1;
+    end;
+  end;
+else
+  level = poset(adj,1)'-1;  
+end;
+
+y = (level+1)./(max(level)+2);
+y = 1-y;
+x = zeros(size(y));
+for i=0:max(level),
+  idx = find(level==i);
+  offset = (rem(i,2)-0.5)/10;
+  x(idx) = (1:length(idx))./(length(idx)+1)+offset;
+end;
+
+%%%%%%%
+
+function [depth] = poset(adj, root)
+% POSET		Identify a partial ordering among the nodes of a graph
+% 
+%  [DEPTH] = POSET(ADJ,ROOT)
+% 
+% Inputs :
+%    ADJ : Adjacency Matrix
+%    ROOT : Node to start with
+% 
+% Outputs :
+%    DEPTH : Depth of the Node
+% 
+% Usage Example : [depth] = poset(adj,12);
+% 
+% 
+% Note     : All Nodes must be connected
+% See also 
+
+% Uses :
+
+% Change History :
+% Date		Time		Prog	Note
+% 17-Jun-1998	12:01 PM	ATC	Created under MATLAB 5.1.0.421
+
+% ATC = Ali Taylan Cemgil,
+% SNN - University of Nijmegen, Department of Medical Physics and Biophysics
+% e-mail : [e-mail] 
+
+adj = adj+adj';
+
+N = size(adj,1);
+depth = zeros(N,1);
+depth(root) = 1;
+queue = root;
+
+while 1,
+  if isempty(queue),
+    if all(depth), break; 
+    else
+      root = find(depth==0); 
+      root = root(1);
+      depth(root) = 1;
+      queue = root;
+    end;
+  end;
+  r = queue(1); queue(1) = [];
+  idx = find(adj(r,:));
+  idx2 = find(~depth(idx));
+  idx = idx(idx2);
+  queue = [queue idx];
+  depth(idx) = depth(r)+1;
+end;
+
+%%%%%%%%%
+
+function [seq] = toposort(adj)
+% TOPOSORT		A Topological ordering of nodes in a directed graph
+% 
+%  [SEQ] = TOPOSORT(ADJ)
+% 
+% Inputs :
+%    ADJ : Adjacency Matrix. 
+%	   ADJ(i,j)==1 ==> there exists a directed edge
+%	   from i to j
+% 
+% Outputs :
+%    SEQ : A topological ordered sequence of nodes.
+%          empty matrix if graph contains cycles.
+%
+% Usage Example : 
+%		N=5;
+%		[l,u] = lu(rand(N));
+%		adj = ~diag(ones(1,N)) & u>0.5;		
+%		seq = toposort(adj);
+% 
+% 
+% Note     :
+% See also 
+
+% Uses :
+
+% Change History :
+% Date		Time		Prog	Note
+% 18-May-1998	 4:44 PM	ATC	Created under MATLAB 5.1.0.421
+
+% ATC = Ali Taylan Cemgil,
+% SNN - University of Nijmegen, Department of Medical Physics and Biophysics
+% e-mail : [e-mail] 
+ 
+N = size(adj);
+indeg = sum(adj,1);
+outdeg = sum(adj,2);
+seq = [];
+
+for i=1:N,
+  % Find nodes with indegree 0
+  idx = find(indeg==0);
+  % If can't find than graph contains a cycle
+  if isempty(idx), 
+    seq = [];
+    break;
+  end;
+  % Remove the node with the max number of connections
+  [dummy idx2] = max(outdeg(idx));
+  indx = idx(idx2);
+  seq = [seq, indx];
+  indeg(indx)=-1;
+  idx = find(adj(indx,:));
+  indeg(idx) = indeg(idx)-1;
+end;
+
+
+
+