I have a directed graph created in matlab. I am trying to print all paths from root to leaves. I used stack to implement my algorithm but it seems very slow when I have large number of nodes and edges.
Is it possible to solve this problem in O(nlogn) time ?
%This is my graph:
output =
edges: {[0 1] [0 2] [1 3] [1 4] [1 5] [2 6] [3 6] [2 7] [3 7] [4 7]}
vertices: [0 1 2 3 4 5 6 7]
%I am traversing with this code
maximal_sets = {};
stack=java.util.Stack();
stack.push(0);
CP = [];
Q = [];
labels = ones(1,size(output.vertices,2));
while ~stack.empty()
flag = 0;
x = stack.peek();
for e = 1:size(output.edges,2)
if output.edges{e}(1) == x && labels(output.edges{e}(2)+1) == 1
flag = 1;
w = output.edges{e}(2);
stack.push(w);
CP = union(CP,w);
break
end
end
if flag == 0
Q = [];
% PRECEDES are leaves of the graph
if any(PRECEDES{end}==x)
for v=1:size(CP,2)
Q = union(Q,CP(v));
end
end
if size(Q,2) > 0
maximal_sets{end+1} = Q;
end
for ed = 1:size(output.edges,2)
if output.edges{ed}(1) == x
labels(output.edges{ed}(2)+1) = 1;
end
end
labels(x+1) = 0;
stack.pop();
CP = CP(find(CP~=x));
end
end
for i = 1:size(maximal_sets,2)
disp(maximal_sets{i})
end
%The paths from root to leaves (not including root which is 0) are listed:
1 3 7
1 4 7
1 5
2 6
2 7
This works well with toy examples, but when I have 403 vertices, and 6717 edges. It does not stop. I think it is exponential.
The traversing code was taken from [http://drum.lib.umd.edu/bitstream/handle/1903/4638/TR_87-130.pdf?sequence=1&isAllowed=y] and modified.