# What's the most efficient way to print all paths from root to leaves in a directed graph?

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.

• Where do you get that runtime goal from? How do you expect to enumerate (super-)exponentially many paths in less time? – Raphael Aug 18 '17 at 6:08
• Welcome to Computer Science! Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. – Raphael Aug 18 '17 at 6:09
• If you want any helpful analysis or algorithm, you need to specify what kinds of graphs you are looking at. Can the worst case happen? Are there bounds on the number of edges or the out-degree? Do you know statistical properties of the class of graphs you are looking at, i.e. average number of edges or out-degree? – Raphael Aug 18 '17 at 6:34
• Root and leaves , do you have a tree data structure? If it's a tree then it's possible – Romantic Electron Aug 18 '17 at 7:42
• I'm voting to close this question because the request is impossible. – David Richerby Aug 18 '17 at 10:01

In a directed graph with $n$ vertices there may be $(n-2)!$ different simple paths (paths without cycles) between any two vertices. Just consider a complete directed graph. So its running time is $O(n!)$ and hence it is impossible to solve the problem in $O(n\log{n})$.
• Nitpick: You need $\Omega(_)$ to show that $O(n \log n)$ is impossible. – Raphael Aug 18 '17 at 6:09