1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Where do you get that runtime goal from? How do you expect to enumerate (super-)exponentially many paths in less time? $\endgroup$ – Raphael♦ Aug 18 '17 at 6:08
  • $\begingroup$ 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. $\endgroup$ – Raphael♦ Aug 18 '17 at 6:09
  • $\begingroup$ 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? $\endgroup$ – Raphael♦ Aug 18 '17 at 6:34
  • $\begingroup$ Root and leaves , do you have a tree data structure? If it's a tree then it's possible $\endgroup$ – Romantic Electron Aug 18 '17 at 7:42
  • 1
    $\begingroup$ I'm voting to close this question because the request is impossible. $\endgroup$ – David Richerby Aug 18 '17 at 10:01
1
$\begingroup$

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})$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nitpick: You need $\Omega(_)$ to show that $O(n \log n)$ is impossible. $\endgroup$ – Raphael♦ Aug 18 '17 at 6:09
  • $\begingroup$ @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? $\endgroup$ – fade2black Aug 18 '17 at 6:21
  • $\begingroup$ 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. $\endgroup$ – Raphael♦ Aug 18 '17 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.