| Code: | function w = islands_and_bridges(B)
%{
Expanding to posiblity for multiple bridges per value
I think this does just one bridge per value :)
%}
[nr,nc] = size(B);
wm = false(nr,nc,4); % wire matrix
w = [];
bridges = [];
remaining_values = get_values(B);
wts = get_weights(B,remaining_values);
% To save LOTS of time, create lookup tables and nested functions
sub2ind_mat = reshape(1:nr*nc,nr,nc);
ind2sub_r = repmat((1:nr)',1,nc);
ind2sub_c = repmat(1:nc,nr,1);
function ind = fastsub2ind(r,c)
ind = sub2ind_mat(r,c);
end
function [r,c] = fastind2sub(ind)
r = ind2sub_r(ind);
c = ind2sub_c(ind);
end
% build neighbor lut
blank_nb = zeros(1,4);
nb_lut = cell(1,nr*nc);
nb_lut_full = nb_lut;
for i = 1:length(B(:))
nb_full = get_neighbors(i);
nb_lut_full{i} = nb_full;
nb = nb_full(nb_full ~= 0);
nb_lut{i} = nb;
end
blank_dist_map = repmat(-1,nr,nc);
blank_region = zeros(nr,nc);
%% %%%%%%% Loop over values %%%%%%
while ~isempty(remaining_values)
%% Choose value for this pass
val = choose_val(B,remaining_values,wts);
wts(remaining_values==val) = []; % drop matching wt
remaining_values(remaining_values==val) = []; % drop chosen value from list
%% Construct obstacle matrix for chosen value
om = obstacle_matrix(val, B, wm);
%% Initialize variables for loop
start_nodes = find(B==val); % starting points
nodes = start_nodes; % keep initial list for reference
if length(nodes) == 1
% no one to link to
break
end
r = struct;
r.wirings = [];
for i = 1:length(nodes)
r(i).nodes = nodes(i);
r(i).dist_counter = 0;
r(i).dist_map = blank_dist_map;
r(i).wpoints = nodes(i);
r(i).dist_map(r(i).wpoints) = 0;
r(i).points_to_change = [];
r(i).changed_points = nodes(i);
r(i).bridges = [];
end
%% Start building regions and generating wirings
finished = false;
while length(r)>1 && ~finished
for i = 1:length(r)
r(i).points_to_change = [];
%dist_map_i_lut = isnan(r(i).dist_map);
% Grow the distance map for each layer
for j = 1:length(r(i).changed_points)
nb = nb_lut{r(i).changed_points(j)};
for k = 1:length(nb)
%if ~om(nb(k)) && dist_map_i_lut(nb(k))
if ~om(nb(k)) && r(i).dist_map(nb(k))==-1
r(i).points_to_change(end+1) = nb(k);
end
end
end
r(i).points_to_change = unique(r(i).points_to_change);
r(i).changed_points = r(i).points_to_change;
r(i).dist_counter = r(i).dist_counter+1;
r(i).dist_map(r(i).points_to_change) = r(i).dist_counter;
end
% Check for overlaps
dist_array = cat(3,r.dist_map);
region_array = dist_array~=-1;
overlap_inds = find(sum(region_array,3)>1);
if ~isempty(overlap_inds)
% there are overlaps, sort them out
% find sum of distance maps at each overlap point, then merge
% and wire the regions which have the minimum distance per
% region joined
len = length(overlap_inds);
avg_d = zeros(1,len);
layers = cell(1,len);
for i = 1:len
% determine which layers are involved
[or,oc] = fastind2sub(overlap_inds(i));
layers{i} = find(region_array(or,oc,:));
avg_d(i) = sum(dist_array(or,oc,layers{i}))/length(layers{i});
end
% Choose minimum avg dist
[dum,ind] = min(avg_d);
% Link wire to this point from all regions
wpoints_add = cell(length(layers{ind}),1);
for i = 1:length(layers{ind})
wpoints_add{i} = wire_me(overlap_inds(ind),r(layers{ind}(i)).dist_map,nb_lut);
end
% Merge layers
% add merged layer to the end of r, then drop the current
% layers
r(end+1).dist_counter = 0;
r(end).nodes = [r(layers{ind}).nodes];
r(end).dist_map = blank_dist_map;
% combine wired points from each layer and the ones to add
r(end).wpoints = unique(cat(2,[r(layers{ind}).wpoints],wpoints_add{:}));
r(end).dist_map(r(end).wpoints) = 0;
r(end).changed_points = r(end).wpoints;
r(layers{ind}) = [];
end
changes = cat(2,r.changed_points);
if isempty(changes)
finished = true;
end
end % building regions and generating wirings
%% Looking for Bridges
look_for_more_bridges = true;
wpoints_add = [];
region = blank_region;
if length(r)==1
wpoints_add = r.wpoints;
rscore = ones(size(r));
for i = 1:length(r)
rscore(i) = score_wpoints(r(i).wpoints,B);
end
look_for_more_bridges = false; %don't enter bridge loop if there's only one region
else
% set up for loop
label_mat = blank_region;%repmat(length(r)+1,nr,nc); %label matrix
flat_dist_map = blank_dist_map;
rscore = ones(length(r),1);
for i = 1:length(r)
label_mat(r(i).dist_map~=-1) = i;
flat_dist_map(r(i).dist_map~=-1) = r(i).dist_map(r(i).dist_map~=-1);
rscore(i) = score_wpoints(r(i).wpoints,B);
end
% Find possible bridge points
[br_orig,n1_orig,n2_orig] = bridges_and_neighbors(wm,B,nb_lut_full);
br = br_orig; n1 = n1_orig; n2 = n2_orig;
end
% This loop should add a bridge each time through, I think
while look_for_more_bridges
% determine bridge point linkages
c1 = label_mat(n1);
c2 = label_mat(n2);
% drop linkages to non-value-regions or self linkages
bad_inds = c1==0 | c2==0 | c1==c2;
br(bad_inds) = [];
n1(bad_inds) = [];
n2(bad_inds) = [];
c1(bad_inds) = [];
c2(bad_inds) = [];
dm1 = flat_dist_map(n1);
dm2 = flat_dist_map(n2);
% bridge point br(i) links region c1(i) to region c2(i) by being
% adjacent to points n1(i) and n2(i).
% score for any particular bridge br(i) is
% 25+dm1(i)+dm2(i)-min([rscore(c1(i)),rscore(c2(i)])
br_score = 25+dm1+dm2+max(rscore(c1),rscore(c2));
min_br_score = min(br_score);
if min_br_score<0
% Add the bridge
best_br_inds = find(br_score==min_br_score);
br_ind = best_br_inds(ceil(rand*length(best_br_inds)));
br_chosen = br(br_ind);
% Wire to the bridge from each region
r1_ind = c1(br_ind);
r2_ind = c2(br_ind);
wpoints_add1 = wire_me(n1(br_ind),r(r1_ind).dist_map,nb_lut); %
wpoints_add2 = wire_me(n2(br_ind),r(r2_ind).dist_map,nb_lut); %
wpoints = [wpoints_add,br_chosen,r(r1_ind).wpoints, r(r2_ind).wpoints,wpoints_add1,wpoints_add2];
% make new merged region
merged_map = blank_dist_map;
merged_map(r(r1_ind).dist_map~=-1) = r(r1_ind).dist_map(r(r1_ind).dist_map~=-1);
merged_map(r(r2_ind).dist_map~=-1) = r(r2_ind).dist_map(r(r2_ind).dist_map~=-1);
r(end+1).dist_map = merged_map;
r(end).wpoints = wpoints;
r(end).bridges = [r(r1_ind).bridges;r(r2_ind).bridges;br_chosen];
% Update label_mat, flat_dist_map, rscore, and br,n1,and n2
% Just rebuild them, it's easier :)
label_mat = blank_region;%repmat(length(r)+1,nr,nc); %label matrix
flat_dist_map = blank_dist_map;
rscore = ones(length(r),1);
for i = 1:length(r)
label_mat(r(i).dist_map~=-1) = i;
flat_dist_map(r(i).dist_map~=-1) = r(i).dist_map(r(i).dist_map~=-1);
rscore(i) = score_wpoints(r(i).wpoints,B);
end
% Reload possible bridge points
br = br_orig; n1 = n1_orig; n2 = n2_orig;
else
% No further improvement by adding a bridge
look_for_more_bridges = false;
end
end % done looking for bridges
% Wire the best region you have
for i = 1:length(r)
if length(r(i).wpoints)==1
rscore(i) = Inf;
end
end
[minscore,ind] = min(rscore);
if minscore>0
w_add = [];
wm_add = false(nr,nc,4);
br_add = [];
else
region(r(ind).wpoints) = true;
[w_add,wm_add] = wires_from_region(region);
br_add = r(ind).bridges;
end
% record final wires and bridges for this value
w = [w;w_add];
wm = wm | wm_add;
bridges = [bridges; br_add];
end % loop over values
%% Add bridges to wiring list
[bridge_r,bridge_c] = fastind2sub(bridges);
br_w = [bridge_r,bridge_c,bridge_r,bridge_c];
w = [w; br_w];
%% %%%%%%%%%%%%%%% NESTED FUNCTIONS %%%%%%%%%%%%%%%
%% get_neighbors
function nb = get_neighbors(point)
[r,c] = fastind2sub(point);
nb = blank_nb;
if r>1
nb(1) = fastsub2ind(r-1,c);
end
if r<nr
nb(2) = fastsub2ind(r+1,c);
end
if c>1
nb(3) = fastsub2ind(r,c-1);
end
if c<nc
nb(4) = fastsub2ind(r,c+1);
end
%nb(nb==0) = [];
% order is N, S, W, E
end
%%%%%%%%%%% END of NESTED FUNCTIONS %%%%%%%%%
end %end of main function
%% %%%%%%%%%%%%%%%% SUBFUNCTIONS %%%%%%%%%%%%%%%%%
%% get_values
function vals = get_values(B)
% list values in board
vals = unique(B(:));
vals(vals==0) = []; %drop zero
end
%% get_weights
function wts = get_weights(B,vals)
wts = zeros(size(vals));
for i = 1:length(vals)
wts(i) = vals(i)*sum(B(:)==vals(i));
end
end
%% choose_val
function val = choose_val(B,remaining_values,wts)
% one way to choose would be to pick a values to maximize
% value*num_occurences
% Choose starting value
[dum,ind] = max(wts);
val = remaining_values(ind);
end
%% obstacle_matrix (val,B)
function om = obstacle_matrix(val,B,wm)
% The obstacle matrix is just the union of non-goal numbers and other
% wires
B(B==val) = 0;
om = B~=0; % Covers non-goal numbers
om = om | sum(wm,3); % adds wired nodes
end
%% wire_me
function w_points = wire_me(gp,dist_map,nb_lut)
% Constructs a wire path from a goal point and a distance map
% Start from goal point
cur_dist = dist_map(gp);
if cur_dist==0
w_points = []; %adjacent points, already connected
return
end
w_points(cur_dist) = gp;
while cur_dist > 1
% Find neighbors with one less distance
nb = nb_lut{w_points(cur_dist)};
cur_dist = cur_dist-1; %decrement current distance
inds = find(dist_map(nb)==cur_dist);
% Choose a neighbor (randomly for now)
ind = ceil(rand*length(inds));
% Add point
w_points(cur_dist) = nb(inds(ind));
end
end
%% wires_from_region
function [w,wm] = wires_from_region(region)
% makes a list of wire connections from a binary matrix which has a
% connected set of ones
% Horizontal connections
east = region & shiftnD(region,-2);
west = shiftnD(east,2);
% vertical
south = region & shiftnD(region,-1);
north = shiftnD(south,1);
[r,c] = find(east);
w = [r,c,r,c+1];
[r,c] = find(south);
w = [w; r,c,r+1,c];
wm = cat(3,east,south,west,north);
end
%% score_wpoints
function score = score_wpoints(wpoints,B)
score = length(wpoints)-sum(B(wpoints));
end
%% bridges_and_neighbors
function [br,n1,n2] = bridges_and_neighbors(wm,B,nb_lut_full)
% returns potential bridge point indices, and the indices of the
% corresponding neigboring regions
east = wm(:,:,1);
west = wm(:,:,3);
south = wm(:,:,2);
north = wm(:,:,4);
h_bridge = find(east & west & ~(north | south) & B==0);
if isempty(h_bridge)
h_n1 = [];
h_n2 = [];
else
nb_h_full = cat(1,nb_lut_full{h_bridge}); % all neighbors of h bridge points
h_n1 = nb_h_full(:,1); % north
h_n2 = nb_h_full(:,2); % south
end
v_bridge = find(north & south & ~(east | west) & B==0);
if isempty(v_bridge)
v_n1 = [];
v_n2 = [];
else
nb_v_full = cat(1,nb_lut_full{v_bridge});
v_n1 = nb_v_full(:,4); % east
v_n2 = nb_v_full(:,3); % west
end
br = [h_bridge; v_bridge];
n1 = [h_n1;v_n1];
n2 = [h_n2;v_n2];
% only return bridges with valid neigbors on both sides
bad_inds = n1==0 | n2==0;
br(bad_inds) = [];
n1(bad_inds) = [];
n2(bad_inds) = [];
end
%% get_bridge_points
function [br_add] = get_bridge_points(r,wm,B)
% How? Use old wiring matrix to identify potiential bridge points
% Then, identify regions on either side of bridge points and value in
% crossing
end
%% shiftnD
function shifted_array = shiftnD(array, direction)
% shifted_array = shiftnD(array, direction,repetitions)
% This function should take the given array and shift it in the direction
% given. The direction should be the number of the dimension in which to
% shift, positive if shifting in the direction of increasing indices,
% negative if shifting in the direction of decreasing indices.
if direction ==0 %don't shift
shifted_array = array;
return
end
dims = size(array);
shiftdim = abs(direction); % this is the dimension to shift in
shiftdir = sign(direction); % this is the direction to shift in that dimension
if abs(direction)>length(dims)
%error('Direction chosen is inappropriate')
end
% construct extended matrix
for i = 1:length(dims)
c{i} = 1:dims(i);
end
c2 = c;
if shiftdir>0
c{shiftdim} = 2:dims(shiftdim);
c2{shiftdim} = 1:dims(shiftdim)-1;
elseif shiftdir<0
c{shiftdim} = 1:dims(shiftdim)-1;
c2{shiftdim} = 2:dims(shiftdim);
end
shifted_array = zeros(dims);
shifted_array(c{:}) = array(c2{:});
end
|