create a threshold graph, or test if g is a threshold graph thresh(g,x) -- create a threshold graph g is the graph to be created x is a vector of values in [0,1] we have an edge between i and j in g iff x(i) + x(j) >= 1 thresh(g) -- determine if g is a threshold graph; return true if it is.
0001 function y = thresh(g,x) 0002 % create a threshold graph, or test if g is a threshold graph 0003 % 0004 % thresh(g,x) -- create a threshold graph 0005 % g is the graph to be created 0006 % x is a vector of values in [0,1] 0007 % we have an edge between i and j in g iff x(i) + x(j) >= 1 0008 % 0009 % thresh(g) -- determine if g is a threshold graph; return true if it is. 0010 0011 0012 % one argument case: check if the graph is a threshold graph 0013 if nargin==1 0014 ds = sort(deg(g)); 0015 y = dscheck(ds); 0016 return 0017 end 0018 0019 0020 0021 % make sure x is a row-vector 0022 x = x(:)'; 0023 0024 n = length(x); 0025 0026 % Here is a MATLAB trick. We want a matrix whose ij entry is x(i)+x(j). 0027 % To do this, we exponentiate x, multiple x'*x, and then logarithm. 0028 0029 ex = exp(x); 0030 M = log(ex'*ex); 0031 0032 A = M >= 1; 0033 for k=1:n 0034 A(k,k) = 0; 0035 end 0036 0037 set_matrix(g,A); 0038 0039 0040 function y = dscheck(ds) 0041 % check a degree sequence to see if it comes from a threshold graph 0042 % we assume ds is given to us sorted 0043 if isempty(ds) 0044 y = true; 0045 return 0046 end 0047 0048 if length(ds) == 1 0049 y = (ds == 0); 0050 return 0051 end 0052 0053 if ds(1) == 0 0054 y = dscheck(ds(2:end)); 0055 return 0056 end 0057 0058 n = length(ds); 0059 if (ds(n) == n-1) 0060 ds = ds(1:n-1)-1; 0061 y = dscheck(ds); 0062 return 0063 end 0064 y = false; 0065 0066 0067