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