Ant=CheckAnt(MyGraph,MaxAnt)

function Ant=CheckAnt(MyGraph,MaxAnt)
%%%%%%%%%%
% Ant=CheckAnt(MyGraph,MaxAnt)
% 
% This function tests for the anticipation of the input graph (input:
% MyGraph). This is done by an exhaustive search of the paths in the power
% graphs. We start with the first power and check to see if there are any
% two paths originating at the same state and generating the same word but
% with a different initial edge. If there is none then the anticipation is
% 1. Otherwise we go on to the next power and so forth. This must terminate
% so optional input MaxAnt is used as a top value for the test. This is
% optional and by default the maximum anticipation tested is 10.

%
% 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.
%%%%%%%%%%%%%%%%%%%%%%%
% By Roee Lahav 2009  %
% [e-mail]    %
%%%%%%%%%%%%%%%%%%%%%%%

  

if(nargin<2)
    MaxAnt=10;
end;

NStates=length(MyGraph.A);
Ant=0;
NotFound=1;
while(NotFound)
    PathLength=Ant+1;
    TestGraph=FindPowerGraph(MyGraph,PathLength,1);
    for k=1:NStates
        WordList=[];
        InitialArc=[];
        InitialState=[];
        for m=1:NStates
            if(TestGraph.A(k,m)>0)
                WordList=[WordList ; TestGraph.EdgeLabels{k,m}];
                InitialArc=[InitialArc;TestGraph.ArcNumbers{k,m}(:,1)];
                InitialState=[InitialState; TestGraph.StateNumbers{k,m}(:,2)];
            end;
        end;
        NWords=size(WordList,1);
        NotFound=0;
        for w=1:NWords
            TestWord=WordList(w,:);
            TestInitialArc=InitialArc(w);
            TestInitialState=InitialState(w);
            Occurences=strmatch(TestWord,WordList,'exact');
            if(any(...
                ~((TestInitialArc==InitialArc(Occurences)) & ...
                  (TestInitialState==InitialState(Occurences)) )))
                NotFound=1;
                break;
            end;
        end;
        if(NotFound)
            break;
        end;
    end;
    
    
    if(NotFound)
        fprintf('Anticipation is not %d\n',Ant);
        fprintf('Initial state: %d\n',k);
        fprintf('Problematic word is %s\n',TestWord);
        fprintf('Possible Initial states: ');
        fprintf('%d ',InitialState(Occurences));
        fprintf('\nPossible Initial arcs: ');
        fprintf('%d ',InitialArc(Occurences));
        fprintf('\n');
        if(Ant>MaxAnt)
            fprintf('Reached maximum anticipation value\n');
            return;
        end;
        Ant=Ant+1;
    end;
end;