How to implement all or nothing assignment in a graph / network ?

Hi,

I have a transport network of n nodes represented by a ( nxn ) matrix A . This matrix contains zeros for non existing links between nodes and positive numbers for existing links. These numbers reflect the weight/cost of the link. I have applied graphshortestpath to A , in a loop, in order to find the shortest paths, with corresponding node sequencies and predecessors, from each node to every other node.

I also have a transport Origin-Destination ( OD ) demand matrix which indicates how many people want o travel between two nodes i and j .

What I want to do now is to find the traffic flows on each edge, according to the shortest path between each OD pair, performing all-or-nothing assignment. This means that the total demand between two nodes i and j will be transferred only through the edges which belong to the shortest path between i and j .

As example I use the following A and OD matrices:

A=[0 3 5 0 0;
    0 0 2 6 0;
    0 1 0 4 6;
    0 0 0 0 4;
    3 0 0 7 0];

OD=[0 2 7 3 1;
    2 0 2 6 8;
    1 4 0 4 6;
    4 10 9 0 4;
    5 6 3 6 0];

and the following loop to produce the matrix with the Shortest Paths, node sequencies and predecessors

 for jj=1:size(A,1)
    [SP,path,pred] = graphshortestpath(sparse(A),jj);
    SPmat(jj,:)=SP;
    pathMat(jj,:)=path;
    predMat(jj,:)=pred;
 end

Can anyone suggest what is the easiest way to do implement the above with these inputs?

Thanks,

Iro

[Iro]

I have written the following code which seems to work.

sparse(A);
[i,j,s]=find(sparse(A));
SPRS_Mat=[i,j,s]; 
Links=SPRS_Mat(:,1:2);
link_sum_flow=[];

for ll=1:size(Links,1)
    this_link=Links(ll,:);
    Link_flow=[];
    linkFlow=[];
    for spr=1:size(pathMat,1)
        for spcol=1:size(pathMat,2)
            this_path=pathMat{spr,spcol}; % for every path of pathMat:
            path_or=this_path(1); % find the Origin
            path_dest=this_path(end); % find the Destination
            path_OD=OD(path_or,path_dest); % find the corresponding OD
            % Check if this link belongs to this path
            [tf,loc] = ismember(this_link,this_path); 
            if (tf(1)==1 && tf(2)==1 && abs(loc(1)-loc(2))==1)
                % Add the OD flow on this link
                linkFlow(spcol)=path_OD;
            else
                linkFlow(spcol)=0;
            end
        end
        Link_flow(spr,:)=linkFlow; % matrix with all flows of thislink     
    end
    Link_flow;
    link_sum_flow(ll)=sum(sum(Link_flow,1));
end
link_sum_flow; % The vector with the flows for each link
LinkFlowMat=[SPRS_Mat,link_sum_flow'];

But I would appreciate any tips for more efficient implementation since my real networks are much bigger than this example.

Thanks,

Iro

[Muhammad Tabish Bilal]

Well coded, simplified yet briliantly explained assignment code.