NewGraph=FindPowerGraph(OldGraph,Power,RecordArcNumbers)

function NewGraph=FindPowerGraph(OldGraph,Power,RecordArcNumbers)
%%%%%%%%%%
% NewGraph=FindPowerGraph(OldGraph,Power,RecordArcNumbers)
% 
% This function generates a new graph (output: NewGraph) from an old graph
% (input: OldGraph) where the output graph is the n'th power (input: Power)
% graph 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 optional input RecordArcNumbers is by default 0. If it is 1 then the
% output graph contains two new fields called NewGraph.ArcNumbers and
% NewGraph.StateNumbers which are V by V cells that describe which sequence of 
% arc and state numbers in the original graph are represented by the 
% corresponding edge in the power graph (this option is used by the
% CheckAnt function)
%
% The n'th power graph G' of a graph G is a graph with the same vertices
% and there is an edge from v1 to v2 in G' if there is a length n path from
% v1 to v2 in G. The label of this edge will be the length n word generated
% by this path.
%
%%%%%%%%%%%%%%%%%%%%%%%
% By Roee Lahav 2009  %
% [e-mail]    %
%%%%%%%%%%%%%%%%%%%%%%%


NStates=length(OldGraph.A);

NewGraph=OldGraph;
NewGraph.A=OldGraph.A^Power;
NewGraph.EdgeLabels=cell(NStates);

if(nargin<3)
    RecordArcNumbers=0;
end;

AnyWord=find(OldGraph.A(:)>0,1,'first');
WordLength=size(OldGraph.EdgeLabels{AnyWord},2);
if(RecordArcNumbers)
    NewGraph.ArcNumbers=cell(NStates);
    NewGraph.StateNumbers=cell(NStates);
end;

for s=1:NStates
    CurrentPathArc=[];
    CurrentPathWord=[];
    CurrentPath=s;
    FindPaths(s,Power)
end;




    function FindPaths(StartState,Length)
        if(Length==0)
            s=CurrentPath(1);
            e=CurrentPath(end);
            NewGraph.EdgeLabels{s,e}=[NewGraph.EdgeLabels{s,e};CurrentPathWord];
            if(RecordArcNumbers)
                NewGraph.ArcNumbers{s,e}=[NewGraph.ArcNumbers{s,e};CurrentPathArc];
                NewGraph.StateNumbers{s,e}=[NewGraph.StateNumbers{s,e};CurrentPath];
            end;
            %             fprintf('Current Path: ');
            %             fprintf('%d ',CurrentPath);
            %             fprintf('\nCurrent Word: ');
            %             fprintf('%c ',CurrentPathWord);
            %             fprintf('\n\n');
        else
            for k=1:NStates

                if(OldGraph.A(StartState,k))
                    CurrentPath=[CurrentPath k];
                    for m=1:OldGraph.A(StartState,k)
                        % fprintf('S=%d\t k=%d \t m=%d\n',StartState,k,m);
                        CurrentPathWord=[CurrentPathWord OldGraph.EdgeLabels{StartState,k}(m,:)];
                        CurrentPathArc=[CurrentPathArc m];
                        FindPaths(k,Length-1);
                        CurrentPathWord=CurrentPathWord(1:(end-WordLength));
                        CurrentPathArc=CurrentPathArc(1:end-1);
                    end;
                    CurrentPath=CurrentPath(1:end-1);
                end;
            end;
        end;
    end
end