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