%% Red-Black Ordering with MatlabBGL
% In this example, we will use the MatlabBGL library to compute the
% red-black ordering of a matrix. For certain matrices, the red-black
% ordering does not exist, but if a red-black ordering exists, then this
% algorithm will find it.
%
% A matrix has a red-black ordering if the directed graph of the matrix
% elements is bipartite. To find a bipartite ordering of the matrix, we
% will use the MatlabBGL |bfs| command.
%% Generating a Matrix
% If you already have a matrix you want to use, you can skip this step.
% First, we generate a second order finite difference approximation to the
% Laplacian operator on a rectangular domain. This matrix does have a
% red-black ordering.
%%
% n is the number of points used to discretize each dimension.
% N is the total number rows and columns in the matrix/graph.
n = 55;
N = n*n;
%%
% This set of commands creates a pentadiagonal matrix.
A = delsq(numgrid('S',n+2));
%%
% Now we visualize the matrix.
spy(A)
%%
% The matrix A we just created is block tridiagonal, although this is
% (perhaps) not obvious from the plot.
%
% We know, analytically, that this matrix has a red black ordering given
% by the odd points and then the even points, when indexed in the current
% order.
p = [1:2:N 2:2:N];
spy(A(p,p));
%%
% Usually, it's a little easier to see a red-black ordering using the
% following command.
spy(A(p,p) - diag(diag(A(p,p))));
hold on;
plot([size(A,2)/2 size(A,2)/2],[0 size(A,1)], 'k-');
plot([0 size(A,2)],[size(A,1)/2 size(A,1)/2], 'k-');
hold off;
%%
% Now we can see that a matrix with a red-black ordering only has non-zero
% dots in the upper right and lower left boxes.
%% Finding the Red-Black ordering
% To find the red-black ordering for an arbitrary matrix (if we do not know
% it analytically) is easy using MatlabBGL.
%
% The key idea is to realize that a red-black ordering is equivalent with
% the partition of vertices in a bipartite graph. Once we see the problem
% in this light, we can quickly come up with an algorithm that yields a
% potential red-black ordering.
%
% We begin by picking an arbitrary vertex and look at how far a breadth
% first search goes at every step. To find the bipartition, we look at all
% vertices which are an even distance from the root and all the vertices
% which are an odd distance from the root. If the matrix has a red-black
% ordering or is a bipartite graph, this algorithm will find it.
%
% Implementing this algorithm is trivial using the MatlabBGL library.
% First, we compute a breadth first search on the graph and store the
% distance each vertex is from the root. Because we really do not care,
% we'll choose vertex 1 (row 1) of the matrix as the root vertex.
d = bfs(A,1);
%%
% Now we find the even and odd partitions
d_even = find(mod(d,2) == 0);
d_odd = find(mod(d,2) == 1);
%%
% Getting the actual permutation of the matrix is simple, we list the odd
% vertices and then the even vertices
p = [d_odd' d_even'];
%%
% Computing the same plot shows we found the red-black ordering!
spy(A(p,p) - diag(diag(A(p,p))));
hold on;
plot([size(A,2)/2 size(A,2)/2],[0 size(A,1)], 'k-');
plot([0 size(A,2)],[size(A,1)/2 size(A,1)/2], 'k-');
hold off;
%%
% and that's it! MatlabBGL and the |bfs| command made this problem simple!