Enumerating all paths in a tree

Question

I've tried and tried; searched and searched, but could not really find an algorithm to solve my problem. I want to enumerate all paths in a tree, (not just simple paths) those which start and end with the leaf nodes (this is an easy constraint though).

For example, for a tree;

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

I want to be able to generate the following paths:

4
4-2-5
4-2-5-2-1-3-6
4-2-5-2-1-3-7
4-2-5-2-1-3-6-3-7
4-2-1-3-6
4-2-1-3-7
4-2-1-3-6-3-7
5
5-2-1-3-6
5-2-1-3-7
5-2-1-3-6-3-7
6
6-3-7
7

I guess that's all.

I have tried the following solution Complexity of finding all simple paths using depth first search? . However, that only finds the simple paths, therefore paths such as 4-2-5-2-1-3-6 could not be found.

Are there any ways that you can guide me, any algorithm perhaps ?

Since you're also allowing nodes to be visited more than once, then there are an infinite amount of paths: `4-2-1-2-1-2-1-2-1-2-1-2-5`, (you can keep repeating `2-1-2-1-...`). Perhaps I'm misinterpreting your question? — Bart Kiers, May 01 '11 at 09:50
What’s your criteria for visiting an edge more than once? At most two? In that case, wouldn’t it be a digraph? — , May 01 '11 at 09:52
My thought on that was; I could let each inner node be visited at most the leaves that are connected to it. So, for example, node 1 can be visited 4 times at each run; and node 2 can be visited once each run. — fizboz, May 01 '11 at 09:53
it seems you're not entirely clear what exactly do you want. Maybe it will help if you tell us why do you want to this. — svick, May 01 '11 at 14:29
Explaining the reason may be more complicated than explaining the problem. But what I want to do is, I want to have all subtrees, whose leaf nodes are the leaf nodes of the initial tree. Then these lists will be a part of my bigger problem, to the solution of which I hope I have the algorithm to =) — fizboz, May 01 '11 at 15:06

score 0 · Answer 1 · answered May 01 '11 at 15:32

Do paths like 4-2-1-2-5 count? If so, I think I have the answer:

It looks to me like you only want each edge to be visited "once" . So take the "dual" of your graph and look at paths as a sequence of edges rather than a sequence of vertices. This way, edges become your "vertices" and vertices become "edges".

This should reduce your problem to generating simple paths of a graph, a problem you already know how to do.

traverse(path, edg):
    mark edg as visited
    print path
    for each edge (e2) sharing a vertex with edg:
        traverse(e2, path+e2)

(with some sort of precaution to avoid duplicate paths being printed)

score 0 · Answer 2 · edited Dec 22 '13 at 22:43

IF your tree is a binary tree, here's a reasonably simple recursive algorithm. In Python:

def lchild(u):
    return 2 * u

def rchild(u):
    return 2 * u + 1

def paths(u, depth):
    if depth <= 0:
        yield ((), (u,), ())
    else:
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            yield ((u,) + ldown, lpath, lup + (u,))
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            for rdown, rpath, rup in paths(rchild(u), depth - 1):
                yield ((u,) + ldown, lpath + lup + (u,) + rdown + rpath, rup + (u,))
        for rdown, rpath, rup in paths(rchild(u), depth - 1):
            yield ((u,) + rdown, rpath, rup + (u,))

if __name__ == '__main__':
    for down, path, up in paths(1, 2):
        print path

Enumerating all paths in a tree

2 Answers2