function xyOut = solver(a, xyIn, wts)
% Attempt to arrange points on circle so that at least 2 connections have
% no crossings. For now just use circle and round but should design so no
% flat sides using integer ratios. For N<320 need 40 different in [0,1]
% Solver06 tried forcing the next point to be adjacent to last, for a tiny
% net loss! Surprising; may indicate local minimum? Or bad circle?
% 10 start at a loose end 44047
% 12 prioritises points that only connect in 43240
% 13 removes singleton postprocess 43270  cleaner but not needed yet
% 14 attempts some polishing, of worst points, very marginal pickup 43059
% 15 focus on just points with 1 or 0 local links 4.2759
% 16 debugged backup circle code
% 17 iterative version, 42226.
% 18 3 second bounce gives 42099, is it legal to use cputime?
% 19 just == on first pass, 42103
% 20 new merit, 42098
% 21 reduced tail to 16, 40934 and use a16 at start, 40811
% 22 pick less connected given equal scores 39529
% 23 applies samelogic to the two conin picks. Does worse, 39627... hmmm.
% Does not seem to help for nonadjacent points so dropped.
% 24 minor merit tweak to close circle 39489
% 25 repositioning leaves 39487, so turned it back off.
% 0.5^2 merit improved to 39535
% Set up gradients that will draw smooth circles on integer grid
% Should move apart the closer ones to make adjustment safe?
g = repmat(1:11,11,1);
r = g ./ g';
g2 = g';
rm = [g(:),g2(:),r(:)];
rms = sortrows(rm,3);
keep = [true;rms(2:end,3)~=rms(1:end1,3)];
g11 = [ [0,1]; rms(keep,1:2) ];
g11 = [ g11; [g11(:,2),g11(:,1)] ];
g11 = [ g11; [g11(:,1),g11(:,2)] ];
g11 = cumsum(g11);
% Find a loosely connected point to start.
% better to use a^logn and start in middle?
% try using this to do whole largescale ordering job?
a2 = a * a;
a4 = a2 * a2;
a8 = a4 * a4;
a16 = a8 * a8;
[central,loose] = sort(diag(a16));
priority = diag(a16); % higher numbers are less well connected
% Set up initial loop through points
n = size(a,1);
done = false(n,1);
list = zeros(n,1);
p = loose(1); % start somewhere not well connected
done(p) = true;
list(1) = p;
for i = 2:n
% choose a point well connected to recent ones; among those
% prefer poorly connected outside
tail = max(1,i16); % tend to ignore points placed long ago
% setting tail = 1 worsens a lot
conin = sum(a(:,list(tail:i1)),2); % # connections to recent points
conin(done) = 0;
conout = sum(a(:,~done),2); % # connections to unplaced
justin = ~logical(conout); % if there are nodes with only internal
if any(conin(justin)) % connections then ignore others
conin(~justin) = 0;
end
cand = a(:,p); % points adjacent to p
aconin = conin;
aconin(~logical(cand)) = 0;
[score,p1] = max(aconin); % Try an adjacent one first
temp = priority;
temp(aconin~=score) = inf;
[~,p] = max(temp); % from equal scores take higher priority
if score == 0
[score,p] = max(conin); % Try best connected to last few
if score == 0
conin = sum(a(:,list(1:i1)),2); % Best connected to any past
conin(done) = 0;
[score,p] = max(conin);
if score == 0 % should mean disjoint graph?
central = diag(a8); % code not tested on visible set
central(done) = inf;
[score,p] = min(central); % pick another loose one
end
end
end
% update records
done(p) = true;
list(i) = p;
end
% Now have a list that indexes into a. I want to move the matrix closer to
% diagonal so that lines are short (and hence have less scope to knot)
% Symrcm could perhaps be adapted but needs different objective to use on
% whole matrix; even when result is better on length metric it worsens
% score. Better to polish subsets that are already wellbehaved?
%{
len = min( [0,0:n2], [n2:1:0,0] );
lenmat = toeplitz( len );
newa1 = a(list,list);
totlen1 = sum(sum(newa1 .* lenmat)); % overall merit for permutation
list2 = symrcm(a);
newa2 = a(list2,list2)
totlen2 = sum(sum(newa2 .* lenmat));
if totlen2 < totlen1
list = list2;
end
%}
len = min( [0,0:n2], [n2:1:0,0] );
lenmat = toeplitz( len );
tried = false(n,1);
newlist = list;
count = 10;
meritv = [0,1,0.5,0.3,0.2,0.1,0.05,0.025,0.01,zeros(1,n)];
meritv = (0.5 * ones(1,n)) .^ (1:n);
meritv = meritv(1:n); % guard n<6
meritv = max(meritv,fliplr(meritv));
meritv(1) = 0;
meritv(n) = 0;
meritm = toeplitz( meritv );
madechanges = true;
firstpass = true;
% time0 = cputime;
% while madechanges && (cputime  time0 < 3)
while madechanges
madechanges = false;
for j = n:1:2 % consider moving this point
a2 = a(newlist,newlist);
a2merit = sum(sum(a2 .* meritm));
if (j==n)  ~( a2(j,j1) && a2(j1,j) ) % not in chain
targets = find( a2(j,:) );
targets = unique([targets,targets+1]);
besti = NaN;
bestm = inf;
for i = targets % try to insert j at i
% p and j both point into a2, dereference later if used
if j~=i
if j<i
map = [1:j1,j+1:i1,j,i:n];
else
map = [1:i1,j,i:j1,j+1:n];
end
a3 = a2(map,map);
a3merit = sum(sum(a3 .* meritm));
if a3merit > bestm
besti = i;
bestm = a3merit;
bestmap = map;
end
end
end
if bestm > a2merit  (firstpass && bestm == a2merit)
newlist = newlist(bestmap);
madechanges = true;
end
end
end
list = newlist;
firstpass = false;
end
%{
a2 = a(newlist,newlist);
totlen = sum(a2 .* lenmat); % total incoming length
a2merit = sum(totlen);
totlen(tried) = 0;
[score,p] = max(totlen);
tried(p) = true;
%}
% Arrange points on circle
xyOut = zeros(size(xyIn));
if n < 337
for i = 1:n
xyOut(list(i),:) = g11(i,:);
end
else
for i = 1:n % Debugged from Solver16
ang = i * 2 * pi / n;
rad = 2*(n+1) / pi;
x = round(cos(ang) * rad);
y = round(sin(ang) * rad);
xyOut(list(i),:) = [x,y];
end
end
%{
% Now clean up singlyconnected nodes
% actually better to implement this during initial phase and put in next
% slots; can handle >1 and more regular makes further moves easier.
single = find(sum(a,2) == 1);
[linksto,~] = find(a(single,:)');
if size(linksto,1)>1 % For first attempt only handle one singleton per linksto
[linksto, id] = sort(linksto);
single = single(id);
keep = [true;linksto(2:end)~=linksto(1:end1)];
single = single(keep);
linksto = linksto(keep);
end
mid = [490,0]; % Check safe for n>336?
dir = bsxfun( @minus, xyOut(linksto,:), mid );
dir = sign(dir);
if all(sum(abs(dir),2)) % Should always be true...?
xyOut(single,:) = xyOut(linksto,:) + dir*10;
end
%}
% Centre circle; should reduce average move
wgtin = wts * xyIn ./ sum(wts);
wgtout = wts * xyOut ./ sum(wts);
xyOut = bsxfun( @plus, xyOut, round(wgtinwgtout));
end
