%% Determine if Graph is Bipartite
% Use breadth-first search to determine that a graph is bipartite, and return the relevant partitions. A bipartite graph is a graph that has nodes you can divide into two sets, A and B, with each edge in the graph connecting a node in A to a node in B.
% Create and plot a directed graph.

s = [1 1 1 1 2 2 4 5 6 7 8];
t = [2 3 6 8 5 10 6 6 10 3 10];
g = digraph(s,t);
plot(g);

%
% Use a breadth-first search on the graph to determine if it is bipartite, and if so, return the relevant partitions.

events = {'edgetonew', 'edgetodiscovered', 'edgetofinished'};
T = bfsearch(g, 1, events, 'Restart', true);
partitions = false(1, numnodes(g));
is_bipart = true;
is_edgetonew = T.Event == 'edgetonew';
ed = T.Edge;

for ii=1:size(T, 1)   
    if is_edgetonew(ii)
        partitions(ed(ii, 2)) = ~partitions(ed(ii, 1));
    else
        if partitions(ed(ii, 1)) == partitions(ed(ii, 2))
            is_bipart = false;
            break;
        end
    end
end

%

is_bipart

%
% Since g is bipartite, the partitions variable contains the information about which partition each node belongs to.
% Plot the bipartite graph with the 'layered' layout, using the partitions variable to specify the source nodes that appear in the first layer.

partitions

%

plot(g, 'Layout', 'layered', 'Source', find(partitions));

% Copyright 2015 The MathWorks, Inc.