function ival = r8mat_is_propa ( n, a )
%*****************************************************************************80
%
%% R8MAT_IS_PROPA checks whether an R8MAT has property A.
%
% Discussion:
%
% An R8MAT is a matrix of real values.
%
% A matrix has property A if the indices 1 through N can be divided
% into two sets, S1 and S2, in such a way that the only nonzero
% offdiagonal elements occur as "connections" between sets S1 and S2.
%
% In other words, if I /= J, then A(I,J) /= 0 implies that I is in
% S1 and J is in S2, or vice versa.
%
% In this case, A can be reordered to have the form:
%
% D1 B
% C D2
%
% where D1 and D2 are diagonal matrices.
%
% A matrix has property A is roughly the same as saying that the
% corresponding graph ( I is connected to J if and only if A(I,J)
% or A(J,I) is nonzero) is bipartite.
%
% Licensing:
%
% This code is distributed under the GNU LGPL license.
%
% Modified:
%
% 04 November 2007
%
% Author:
%
% John Burkardt
%
% Input:
%
% integer N, the order of the matrix.
%
% real A(N,N), the matrix.
%
% Output:
%
% integer IVAL:
% -1, the matrix does not have property A.
% 1, the matrix has property A.
%
set(1:n) = 0;
nset = 0;
nstack1 = 0;
nstack2 = 0;
nstack1 = nstack1 + 1;
stack1(nstack1) = 1;
set(1) = 1;
nset = nset + 1;
while ( true )
%
% Check all connections from the new candidates for set 1...
% ...to old nodes, for consistency, and
% ...to new nodes, to find candidates for the next sweep.
%
nset_old = nset;
while ( 0 < nstack1 )
i = stack1(nstack1);
for j = 1 : n
if ( j == i )
continue
end
if ( a(i,j) == 0.0 && a(j,i) == 0.0 )
continue
end
if ( set(j) == 2 )
continue
elseif ( set(j) == 1 )
ival = -1;
return
end
nstack2 = nstack2 + 1;
stack2(nstack2) = j;
set(j) = 2;
nset = nset + 1;
end
nstack1 = nstack1 - 1;
end
%
% If we didn't add any new neighbors...
%
if ( nset == nset_old )
%
% ...and the current candidates make up the rest of the set,
% then we've looked at everything and we're done.
%
if ( nset == n )
ival = 1;
break
end
%
% ...otherwise, grab an unused index as a new candidate, and continue.
%
for i = 1 : n
if ( set(i) == 0 )
nstack2 = nstack2 + 1;
stack2(nstack2) = i;
set(i) = 2;
nset = nset + 1;
break
end
end
end
%
% Check all connections from the new candidates for set 2...
% ...to old nodes, for consistency, and
% ...to new nodes, to find candidates for the next sweep.
%
nset_old = nset;
while ( 0 < nstack2 )
i = stack2(nstack2);
for j = 1 : n
if ( j == i )
continue
end
if ( a(i,j) == 0.0 && a(j,i) == 0.0 )
continue
end
if ( set(j) == 1 )
continue
elseif ( set(j) == 2 )
ival = -1;
return
end
nstack1 = nstack1 + 1;
stack1(nstack1) = j;
set(j) = 1;
nset = nset + 1;
end
nstack2 = nstack2 - 1;
end
%
% If we didn't add any new neighbors...
%
if ( nset == nset_old )
%
% ...and the current candidates make up the rest of the set,
% then we've looked at everything and we're done.
%
if ( nset == n )
ival = 1;
break
end
%
% ...otherwise, grab an unused index as a new candidate, and continue.
%
for i = 1 : n
if ( set(i) == 0 )
nstack1 = nstack1 + 1;
stack1(nstack1) = i;
set(i) = 1;
nset = nset + 1;
break
end
end
end
end
return
end