libraryGraph_capacityShortestPath (linkTable , ingressNode , egressNode , minimumCapacityInEachLink)

% libraryGraph_capacityShortestPath
%
% Usage: [sequenceOfSPFLinkIds, sequenceOfSPFNodeIds , totalCost] =
% libraryGraph_capacityShortestPath (linkTable , ingressNode , egressNode , minimumCapacityInEachLink)
%
% Abstract: This function computes the shortest path between a pair of
% nodes (ingress node, egress node) with links with enough free capacity. 
% 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. 
% Only the links with enough free capacity (capacity upper than the
% "minimumCapacityInEachLink") are considered to find the shortest path.
% If it 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.
% If a path is found, the free link capacity of each link is not
% modified by substracting it the "minimumCapacityInEachLink".
%
% Arguments:
% o	In: 
%    linkTable(L,4): Matrix of L physical links by 4. 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'.
%     And the fourth column is the free capacity of the link 'l' in Gbps.
%
%    ingressNode: Origin Node of the path.
%
%   . egressNode: Destination Node of the path.
%
%   . minimumCapacityInEachLink: Minimum capacity (Gbps) in each link. It
%     must be lower than the free link capacity to consider the link in the
%     shortest path computation. Therefore, none of the links can have less
%     free capacity than this value.
%   
% 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.
%
%
%                                  Technical University of Cartagena, 2007 

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

numberNetNodes = max (max (linkTable(:,1:2)));
numberNetNodes = max ([numberNetNodes ingressNode egressNode]);
numberlinkTable = size (linkTable , 1);

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;
    
    for cont=1:length(weightTagsPerNode)
        
    end

    % 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)) && (linkTable(outLinkId,4) >= minimumCapacityInEachLink)
                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 = [];

% si el destino no esta en intree es que no habia camino 
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');