%% Remove Cycles from Graph
% Make a directed graph acyclic by reversing some of its edges.
% Create and plot a directed graph.

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

%
% Perform a depth-first search on the graph, flagging the 'edgetodiscovered' event. This event corresponds to edges that complete a cycle.

[e,edge_indices] = dfsearch(g, 1, 'edgetodiscovered', 'Restart', true)

%
% Use flipedge to reverse the direction of the flagged edges, so that they no longer complete a cycle. This removes all cycles from the graph. Use isdag to confirm that the graph is acyclic.

gnew = flipedge(g, edge_indices);
isdag(gnew)

%
% Plot the new graph and highlight the edges that were flipped.

p = plot(gnew, 'Layout', 'force');
highlight(p,'Edges',findedge(gnew,e(:,2),e(:,1)),'EdgeColor','r')

% Copyright 2012 The MathWorks, Inc.