NewGraph=StateSplitRound(OldGraph,Partition)

function NewGraph=StateSplitRound(OldGraph,Partition)
%%%%%%%%%%
% NewGraph=StateSplitRound(OldGraph,Partition)
% 
% This function generates a new graph (output: NewGraph) from an old graph
% (input: OldGraph) created by running a single complex round of state
% out-splitting, whose partitions are specified (input: Parition)
%
% A graph is a structure with the following compulsory fields
%   A - a V by V adjacency matrix where V is the number of states
%   (vertices) in the graph. An adjacency matrix row i column j entry
%   contains the number of edges directed from state i to state j
%
%   EdgeLabels - a V by V cell. An entry in the cell is empty if the
%   corresponding entry in A is 0. Otherwise it is a character array in
%   which each row is the label of the corresponding edge. The labels are
%   arranged in rows. Note that this means that all the edges from state i
%   to state j must have names of the same length (or padded by spaces so
%   that they will be so).
%
%   StateLabels - a V by 1 cell. Each entry contains the string which is
%   the state name.
%  
%
%  The input variable Partition is a V by V cell whose row i column j entry
%  can either be -
%   - empty if there are no edges from state i to state j
%   - an array which is of size OldGraph.A(i,j) in which each entry
%   contains a number which signifies to which partition the edges will
%   belong in the new graph.
%   The set of partition numbers in the same row of "Partition" must constitute 
%   a list of integers from 1 to M (the number of target partitions for the 
%   relevant state) without skipping any integer. If this is not so results are
%   unpredictable (most probably the result will be an error).
%
%%%%%%%%%%%%%%%%%%%%%%%
% By Roee Lahav 2009  %
% [e-mail]    %
%%%%%%%%%%%%%%%%%%%%%%%



NewGraph=OldGraph;

NOldStates=size(Partition,1);
NNewStates=0;
NPartitions=zeros(NOldStates,1);
StateNewIndex=cell(NOldStates);

% find number of target partitions for each state and create an old state -
% new state map.

for k=1:NOldStates
    NPartitions(k)=1;
    for t=1:NOldStates
        NPartitions(k)=max([NPartitions(k);Partition{k,t}]);
    end;
    StateNewIndex{k}=(1:NPartitions(k))+NNewStates;
    NNewStates=NNewStates+NPartitions(k);
    for t=1:NPartitions(k)
        if(NPartitions(k)>1)
            NewGraph.StateLabels{StateNewIndex{k}(t)}=[OldGraph.StateLabels{k} '_' 'a'+(t-1)];
        else
            NewGraph.StateLabels{StateNewIndex{k}(t)}=OldGraph.StateLabels{k};
        end;
    end;
end;


NewGraph.EdgeLabels=cell(NNewStates);
NewGraph.A=zeros(NNewStates);

% run the complex out-splitting round.

for SourceStateOldIndex=1:NOldStates
    for TargetStateOldIndex=1:NOldStates
        NTargetPartitions=NPartitions(TargetStateOldIndex);
        NEdges=OldGraph.A(SourceStateOldIndex,TargetStateOldIndex);
        for Edge=1:NEdges
            SourcePartition=Partition{SourceStateOldIndex,TargetStateOldIndex}(Edge);
            SourceStateNewIndex=StateNewIndex{SourceStateOldIndex}(SourcePartition);
            for TargetPartition=1:NTargetPartitions
                TargetStateNewIndex=StateNewIndex{TargetStateOldIndex}(TargetPartition);
                % update number of edges
                NewGraph.A(SourceStateNewIndex,TargetStateNewIndex)=...
                    NewGraph.A(SourceStateNewIndex,TargetStateNewIndex)+1;
                temp=NewGraph.A(SourceStateNewIndex,TargetStateNewIndex);
                % update edge labels
                NewGraph.EdgeLabels{SourceStateNewIndex,TargetStateNewIndex}(temp,:)=...
                    OldGraph.EdgeLabels{SourceStateOldIndex,TargetStateOldIndex}(Edge,:);
            end;
        end;
    end;
end;