libraryFR_CSPF(traff_trafficMatrix, linkTable, linkCapacities, varargin)

% libraryFR_CSPF

% Usage: [exitFlag flowTable flowRoutingMatrix] =
% libraryFR_CSPF(traff_trafficMatrix, linkTable, linkCapacities, linkCostPerGbps)
%
% Abstract: This function solves the Traffic Flow Routing over a network
% topology (physical or virtual) by means of the Capacitated Shortest Path
% First (CSPF)Algorithm. 
%
% Arguments:
% o	In: 
%   traff_trafficMatrix(NxN): Average traffic flow offered between node
%    pairs. The Traffic Matrix is a two-dimensional matrix with N (N:
%    number of nodes) rows and N columns. An entry(s,d) means the average
%    traffic flow from node 's' to node 'd', expressed in Gbps. The main
%    diagonal is full of 0s.
%
% .  linkTable(M,2): M-by-2 integer matrix. Each row is an edge (physical link 
%    or lightpath) 'm', where the first and second columns of each row are the 
%    origin node 'x' and destination node 'y' of this edge 'm' respectively and
%    M is the number of physical links or lightpaths if the network topology
%    is physical or virtual respectively.
%
% .  linkCapacities(M,1): Capacity in Gbps of each link. This is the
%    maximum traffic that the link can carry.
%
%   
% o	Out:
%  . exitFlag: 
%           0, if it is possible to route all the traffic flows
%           1, if some traffic flow was not routed
%           2, if the traffic flow routing is not FEASIBLE.
%
%  . flowTable(F,3): F-by-3 matrix. First column de ingress node, second
%    the egress node, third the traffic offered in Gbps.
%
%  . flowRoutingMatrix (F,L): F-by-L integer matrix where F is the number of 
%    flows and L is the number of lightpaths. Each row is a flow 'f' and each 
%    column is a lightpath 'l'. If a flow 'f' uses a lightpath 'l', the
%    entry (f,l) is equal to the value of the flow 'f' carried by the
%    lightpath 'f'. If no lightpath is used by the flow 'f', the entry is
%    equal to '0'. If a row is a row of zeros, the the traffic flows was
%    not routed
%
function [exitFlag flowTable flowRoutingMatrix] = libraryFR_CSPF(traff_trafficMatrix, linkTable, linkCapacities, varargin)
%CSFP Routing Algorithm so as to route each flow (ingress node, egress
%node) over the network topology considering if there are enough capacity
%in each link. 
numberOfFlows = nnz(traff_trafficMatrix);
flowTable=zeros(numberOfFlows,3);
flowRoutingMatrix=zeros(numberOfFlows, size(linkTable,1));
minimumCapacityInEachLink=0;
exitFlag = 0;
 
k=0;
for i=1:size(traff_trafficMatrix,2),
    for j=1:size(traff_trafficMatrix,1),
        if traff_trafficMatrix(i,j)~=0,
            k=k+1;
            demandedCapacity=traff_trafficMatrix(i,j);    
            freeLinkCapacities=linkCapacities-(sum(flowRoutingMatrix,1))'-demandedCapacity*ones(size(linkTable,1),1);
            
            [sequenceOfSPFLinkIds,sequenceOfSPFNodeIds , totalCost] = libraryGraph_capacityShortestPath ...
                 ([linkTable ones(size(linkTable,1),1) freeLinkCapacities] , i , j , minimumCapacityInEachLink);
             
             if isempty(sequenceOfSPFLinkIds),
                 exitFlag = 1; %some traffic flow was not routed
                 flowTable(k,:)=[i j traff_trafficMatrix(i,j)];
             else %if there is shortest route, we add a new flow to the routing matrix
                 newFlowRoutingEntry=zeros(1,size(linkTable,1));
                 for l=1:length(sequenceOfSPFLinkIds),
                     newFlowRoutingEntry(sequenceOfSPFLinkIds(l))=traff_trafficMatrix(i,j);
                 end   
                 flowTable(k,:)=[i j traff_trafficMatrix(i,j)];
                 flowRoutingMatrix(k,:) = newFlowRoutingEntry ;
             end         
        end
    end
end

if isempty(flowTable) || isempty(flowRoutingMatrix), exitFlag = 2; end %Flow routing not feasible