varargout=shortest_path_bfs(varargin)

function varargout=shortest_path_bfs(varargin)
%SHORTEST_PATH_BFS Compute shortest path between two edges in a
%directed/undirected graph without wages.
%   PATH=SHORTEST_PATH_BFS(BEGIN,END,NAME,STRUC_DIM) uses BFS
%   algorithm [1] for computing shortest path between BEGIN and END node
%   for a NAME.mat network (ie. help CREATE_NETWORK). STRUC_DIM is the
%   structure number saved in NAME.mat file.
%
%   See also CREATE_NETWORK, CREATE_RAND_NETWORK, SHORTEST_PATH_DIJKSTRA.
%
%   References:
%      [1]  T. E. Cormen et al., "Introduction to Algorithms", 
%      WNT, Warsaw 2000, page 530.

%   Copyright 2003-2004 Przemyslaw Pawelczak
%   E-mail: [e-mail]
%   Wroclaw University of Technology, Poland
%   $Revision: 1.0 $  $Date: 2004/02/12 01:34:13 $

%If no NUMBER specified then it will be first
if nargin==3
    varargin{4}=1;
end

%Exeption handling
message=nargchk(3,4,nargin);
testing_int=[varargin{1},varargin{2},varargin{4}];
if ~isempty(message)
    error('MATLAB:SHORTEST_PATH_BFS:NumberOfInputArguments',...
        message);
end 
if find(isnan(testing_int))
    error('MATLAB:SHORTEST_PATH_BFS:ArgumentType',...
        'Arguments must be numbers.');
end
%Check if VARARGIN are positive integers
if sum([testing_int<0,fix(testing_int)~=testing_int])~=0
    error('MATLAB:SHORTEST_PATH_BFS:ArgumentType',...
        'Arguments must be positive integers.');
end
if ~isstr(varargin{3})
    error('MATLAB:SHORTEST_PATH_BFS:ArgumentType',...
        'Argument must be string.');
end

%Change string into number (for all number of arguments)
for k=[1,2,4]
    if isstr(varargin{k})==1
        varargin{k}=str2num(varargin{k});
    end
end

%List all '*.mat' files in current working directory
%Change directory to MATLABROOT\networks - catalog must exist
cd([matlabroot,['\work\networks']]);
directory=what;
directory=struct2cell(directory);
directory=cellstr(directory{3});

%Check if specified '*.mat' file already exist
if find(strcmp(directory,[varargin{3},'.mat'])==1)
    load(varargin{3});
    fields_vector=[exist('description'),exist('structure')];
    if length(find(fields_vector))~=2
        error('MATLAB:SHORTEST_PATH_BFS:BadFieldNames',...
            'Bad field names.'); 
    else
        varargout{1}=bfs(varargin{1},varargin{2},structure,varargin{4});
    end
else
    error('MATLAB:SHORTEST_PATH_BFS:BadFileName',...
        'Bad file name.'); 
end

function [road]=bfs(begin_node,end_node,structure,number)

%Check how many nodes are in the graph
%Initialize flag - checking if graph has wages
has_wages=0;
structure_dimension=cellfun('ndims',structure);
structure_length=length(structure_dimension(:,1,1));
node_number=0;
for k=1:structure_length
    if ~isempty(structure{k,1,number})
        %Check if graph has no wages
        if ~isequal(ones(1,length(structure{k,2,number})),structure{k,2,number})
            %If yes then change flag to 1
            has_wages=1;
        end
        node_number=node_number+1;
    end
end

%Print warning
if has_wages==1
    warning('MATLAB:SHORTEST_PATH_BFS:WrongWages',...
        'Graph has wages. Changing all wages to 1.');
end

%Initialize variables
distance=zeros(1,node_number);
previous=zeros(1,node_number);
colour=zeros(1,node_number);
queue(1)=begin_node;

%BFS algorithm (taken form [1])

%Change colour of begin node to 1 (grey)
colour(queue(1))=1;
i=1;
while ~isempty(queue)
    node_incidence_vector=structure{queue(1),1,number};
    for k=1:length(node_incidence_vector)
        if colour(node_incidence_vector(k))==0
            %Change colour of node to 1 (grey)
            colour(node_incidence_vector(k))=1;
            %Change distance
            distance(node_incidence_vector(k))=distance(node_incidence_vector(k))+1;
            previous(node_incidence_vector(k))=queue(1);
            i=i+1;
            queue(i)=node_incidence_vector(k);
        end
    end
    %Change node colour to 2 (black)
    colour(queue(1))=2;
    %Remove element from queue
    queue(1)=[];
    i=length(queue);
end

%Show path
road=[];
position=end_node;
while position~=begin_node
    road=[road,previous(position)];
    position=previous(position);
end

road=fliplr([end_node,road]);