MGraph=FindMooreCoForm(Graph)

function MGraph=FindMooreCoForm(Graph)
%%%%%%%%%%
% MGraph=FindMooreCoForm(Graph)
% 
% This function generates a new graph (output: MGraph) from an old graph
% (input: Graph) where the output graph is the Moore co-form of the input
% graph.
%
% 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 moore co-form G' of a graph G is the following
%   1. The vertices of G' are the edges of G
%   2. In G' there is an edge from e1 to e2 only if the source of edge e1
%   in G is the target of edge e1 in G. Also, in G' the label of this edge
%   will be the label of the edge e1 in G.
%%%%%%%%%%%%%%%%%%%%%%%
% By Roee Lahav 2009  %
% [e-mail]    %
%%%%%%%%%%%%%%%%%%%%%%%


NStatesOldGraph=size(Graph.A,2);

CurrentEdge=1;

EdgeIndex=cell(NStatesOldGraph);

% give edges indexes
for k=1:NStatesOldGraph
    for m=1:NStatesOldGraph
        if(Graph.A(k,m)>0)
            for e=1:Graph.A(k,m)
                EdgeIndex{k,m}(e)=CurrentEdge;
                MGraph.StateLabels{CurrentEdge}=sprintf('%s-%s-%s',...
                    Graph.StateLabels{k},Graph.StateLabels{m},...
                    Graph.EdgeLabels{k,m}(e,:));
                CurrentEdge=CurrentEdge+1;
            end;
        end;
    end;
end;
NEdges=CurrentEdge-1;

MGraph.A=zeros(NEdges);

% create adjacency matrix and edge label matrix
for k=1:NStatesOldGraph
    for m=1:NStatesOldGraph
        if(Graph.A(k,m)>0)
            for e=1:Graph.A(k,m)
                SourceIndex=EdgeIndex{k,m}(e);
                for t=1:NStatesOldGraph
                    if(Graph.A(m,t)>0)
                        for p=1:Graph.A(m,t)
                            TargetIndex=EdgeIndex{m,t}(p);
                            MGraph.A(SourceIndex,TargetIndex)=1;
                            MGraph.EdgeLabels{SourceIndex,TargetIndex}=...
                                Graph.EdgeLabels{k,m}(e,:);
                        end;
                    end;
                end;
            end;
        end;
    end;
end;