Homec4science
Diffusion number_routes_multipath (master) Browse

R6360/code/matlab-code/paths_from_links.m
8f12ec2dec8emaster

Last Change
Raw File

paths_from_links.m
View Options

function [final_paths, thr_opt, thr_K] = paths_from_links(all_links,src,dst,K)
precision = 0.01;
% compute paths from set of used links
paths = {};
all_paths_done = false;
%all_links_rate = all_links;
while ~all_paths_done
if isempty(paths) % first link
next_links = find(all_links(:,1) == src);
for i=1:length(next_links)
paths{i} = all_links(next_links(i),:)';
end
if length(next_links) == length(all_links(:,1)) % only 1-hop paths
all_paths_done = true;
end
else
all_paths_done = true;
new_paths = {};
count = 1;
for i=1:length(paths)
path = paths{i};
if path(2,end) == dst % add the paths that are already finished
new_paths{count} = path;
count = count + 1;
else % continue the walk
% select next links based on rate
next_links = find(all_links(:,1) == path(2,end));
for j=1:length(next_links)
next_node = all_links(next_links(j),2);
if any(path(1,:) == next_node) % loop
continue
end
new_paths{count} = [path,all_links(next_links(j),:)'];
count = count + 1;
if all_links(next_links(j),2) ~= dst
all_paths_done = false;
end
end
end
end
paths = new_paths;
end
end
% check paths are between src and dst
end_paths = {};
count = 1;
for i=1:length(paths)
path = paths{i};
if path(2,end) == dst
end_paths{count} = path;
count = count + 1;
end
end
final_paths = {};
% if isempty(end_paths)
% thr_opt = 0;
% thr_K = 0;
% return
% end
% extract smallest set of paths compatible with link use
bottlenecks = cellfun(@(x) min(x(4,:)),end_paths);
% sort by bottleneck
[~,inds] = sort(bottlenecks, 'descend');
end_paths = end_paths(inds);
bottlenecks = bottlenecks(inds);
remaining_resources = all_links;
count = 1;
thr_K = 0;
thr_opt = 0;
bottlenecks_fin = [];
while ~isempty(bottlenecks) && bottlenecks(1) > precision
path = end_paths{1};
bottleneck = bottlenecks(1);
bottlenecks_fin(count) = bottleneck;
final_paths{count} = path;
count = count+1;
% update resources
for j=1:size(path,2)
link = path(:,j);
[~,indx]=ismember(link(1:3)',remaining_resources(:,1:3),'rows');
remaining_resources(indx,4) = remaining_resources(indx,4)-bottleneck;
end
end_paths = end_paths(2:end);
bottlenecks = bottlenecks(2:end);
% update bottlenecks with remaining resources
for i=1:length(end_paths)
path = end_paths{i};
for j=1:size(path,2)
link = path(:,j);
[~,indx]=ismember(link(1:3)',remaining_resources(:,1:3),'rows');
if remaining_resources(indx,4) < bottlenecks(i)
bottlenecks(i) = remaining_resources(indx,4);
end
if bottlenecks(i) < precision
break
end
end
end
[~,inds] = sort(bottlenecks, 'descend');
end_paths = end_paths(inds);
bottlenecks = bottlenecks(inds);
end
if ~isempty(bottlenecks_fin)
bottlenecks_fin = sort(bottlenecks_fin, 'descend');
thr_opt = sum(bottlenecks_fin);
ind = min(K,length(bottlenecks_fin));
thr_K = sum(bottlenecks_fin(1:ind));
end
end
c4science · Help