% 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".
% 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;
% 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)))
intree (newNodeIdInTree) = 1;
outgoingLinksFromNewNodeInTree = find (linkTable(:,1)==newNodeIdInTree);
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;
% 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];
warning ('on' , 'MATLAB:divideByZero');