# 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, 2017 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, 2017 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, 2017 at 6:34
• Root and leaves , do you have a tree data structure? If it's a tree then it's possible Aug 18, 2017 at 7:42
• I'm voting to close this question because the request is impossible. Aug 18, 2017 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, 2017 at 6:09
• @Raphael the best case is when there is no edges, the worst case is when the graph is complete. So I the best thing is to consider the average case, though it would better if asker clarified how he/she is going to generate graphs, how dense, how sparse graphs are. Agree? Aug 18, 2017 at 6:21
• Sure -- an analysis that better matches the usage scenario is always better. Average-case on graphs is not as clear cut as one would like, though; there are many models for random graphs. Maybe a worst-case analysis in terms of number of nodes and edges together with upper bounds on the number of edges or average/maximum out-degree are enough here. There's not enough in the question to tell.
– Raphael
Aug 18, 2017 at 6:33