libraryGraph_shortestPath.m

% libraryGraph_shortestPath
%
% Usage: [sequenceOfSPFLinkIds,sequenceOfSPFNodeIds , totalCost] =
% libraryGraph_shortestPath (linkTable , ingressNode , egressNode)
%
% Abstract: This function computes the shortest path between a pair of
% nodes (ingress node, egress node). The shortest path is defined as the
% path with the minimum total weight (or cost), where the total weight is
% the sum of the weights of the links which the path consist of. If is not
% possible to find a path between ingress node and egress node, the
% function returns empty matrices. If there are several solutions with the
% minumum weight (or cost) between the pair ingress-egress, the function
% only returns one of them.
%
% Arguments:
% o	In: 
%    linkTable(L,3): Matrix of L physical links by 3. Each row is a
%     physical link 'l', where the first and second columns of each row are
%     the nodeID (integer number) of the origin node 'x' and the nodeID
%     (integer number) of the destination node 'y' of this link 'l'
%     respectively. The third column is the link weight of the link 'l'.
%
%    ingressNode: Origin Node of the path.
%
%   . egressNode: Destination Node of the path.
%   
% o	Out:
%    sequenceOfSPFLinkIds: Row vector with the sorted sequence of  IDs
%     of the links which the shortest path between ingress and egress
%     consist of. The links IDs are sorted from the ingress node to the
%     egress node.
%
%   . sequenceOfSPFNodeIds: Row vector with the sorted sequence of  IDs
%     of the nodes which the shortest path  between ingress and egress
%     consist of. The nodes IDs are sorted from the ingress node to the
%     egress node.
%
%   . totalCost: It is the total weight of the shortest path found  between
%     ingress and egress. It is computed as the sum of the weights of the
%     links which the shortest path consist of.
%
%



function [sequenceOfSPFLinkIds,sequenceOfSPFNodeIds , totalCost] = libraryGraph_shortestPath (linkTable , ingressNode , egressNode)

if isempty (linkTable)
    sequenceOfSPFLinkIds = [];
    sequenceOfSPFNodeIds = [];
    totalCost = -1;
    return
end
    
numberNetNodes = max (max (linkTable(:,1:2)));
numberNetNodes = max([numberNetNodes ingressNode egressNode]); % por si el egress o el ingress no estan en el linkTable


%%%%%%%%%%%%%%%%%ATTENTION!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
%%%%%%%%%%%%%%%%%!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
%numberNetNodes = max([numberNetNodes ingressNode egressNode]);
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

intree = zeros (1,numberNetNodes);
predLinkIds = -1 * ones (1,numberNetNodes); % the link which takes me to the ingress
weightTagsPerNode = inf * ones (1,numberNetNodes);
weightTagsPerNode (ingressNode) = 0;    

counterOfSteps = 0;

warning ('off' , 'MATLAB:divideByZero');
while (intree (egressNode) ~= 1) && (counterOfSteps <= numberNetNodes)
    counterOfSteps = counterOfSteps + 1;
    
    % to calculate the node id with lowest tag, only among the ones in the tree
    [auxiliar,newNodeIdInTree] = min (weightTagsPerNode  ./ (1-intree));

    % If the node with lowest tag has an infinite value => nodes not in
    % the tree are not connected to the component of the ingress node, and we should stop
    if (isinf (weightTagsPerNode(newNodeIdInTree)))
        break;
    end

    intree (newNodeIdInTree) = 1;
    
    outgoingLinksFromNewNodeInTree = find (linkTable(:,1)==newNodeIdInTree);
    for outLinkId=outgoingLinksFromNewNodeInTree'
        neighbour = linkTable(outLinkId,2);
        if (intree (neighbour) == 0)
            if (weightTagsPerNode (neighbour) > weightTagsPerNode (newNodeIdInTree) + linkTable (outLinkId,3))
                weightTagsPerNode (neighbour) = weightTagsPerNode (newNodeIdInTree) + linkTable (outLinkId,3);
                predLinkIds (neighbour) = outLinkId;
            end
        end
    end
end


% convert the pred structure into a sequence of links
sequenceOfLinkIds = [];
sequenceOfSPFLinkIds = [];
sequenceOfSPFNodeIds = [];

%if the destination node is not in "intree", there was not path 
totalCost = 0;
if (intree (egressNode) == 1)
    node = egressNode;
    sequenceOfSPFNodeIds = [egressNode];
    while (node ~= ingressNode)
        linkToAdd = linkTable (predLinkIds(node),:);
        totalCost =  totalCost + linkToAdd(3);
        sequenceOfSPFLinkIds = [predLinkIds(node) sequenceOfSPFLinkIds];
        node = linkToAdd (1); % source of the link added
        sequenceOfSPFNodeIds = [node sequenceOfSPFNodeIds];
    end
end

warning ('on' , 'MATLAB:divideByZero');