1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
function [x, y] = make_layout(adj)
%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 : cemgil@mbfys.kun.nl
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 : cemgil@mbfys.kun.nl
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 : cemgil@mbfys.kun.nl
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;
|
