List of all edge disjoint paths in a tree

Question

In a generic tree represented by the common node structure having parent and child pointers, how can one find a list of all paths that have no overlapping edges with each other and terminate with a leaf node.

For example, given a tree like this:

          1
      /   |   \               
     2    3    4
    / \   |   / \
   5   6  7  8   9 

The desired output would be a list of paths as follows:

1    2    1    1    4
|    |    |    |    |
2    6    3    4    9
|         |    | 
5         7    8

Or in list form:

[[1, 2, 5], [2, 6], [1, 3, 7], [1, 4, 8], [4, 9]]

Obviously the path lists themselves and their order can vary based on the order of processing of tree branches. For example, the following is another possible solution if we process left branches first:

[[1, 4, 9], [4, 8], [1, 3, 7], [1, 2, 6], [2, 5]]

For the sake of this question, no specific order is required.

Answer 1

You can use a recursive DFS algorithm with some modifications.
You didn't say what language you use, so, I hope that C# is OK for you.

Let's define a class for our tree node:

public class Node
{
    public int Id;
    public bool UsedOnce = false;
    public bool Visited = false;
    public Node[] Children;
}

Take a look at UsedOnce variable - it can look pretty ambigious.
UsedOnce equals to true if this node has been used once in an output. Since we have a tree, it also means that an edge from this node to its parent has been used once in an output (in a tree, every node has only one parent edge which is the edge to its parent). Read this carefully to not become confused in future.

Here we have a simple, basic depth-first search algorithm implementation.
All the magic will be covered in an output method.

List<Node> currentPath = new List<Node>(); // list of visited nodes

public void DFS(Node node)
{
    if (node.Children.Length == 0) // if it is a leaf (no children) - output
    {
        OutputAndMarkAsUsedOnce(); // Here goes the magic...
        return;
    }

    foreach (var child in node.Children)
    {
        if (!child.Visited) // for every not visited children call DFS
        {
            child.Visited = true;
            currentPath.Add(child);
            DFS(child); 
            currentPath.Remove(child);
            child.Visited = false;
        }
    }
}

If OutputAndMarkedAsUsedOnce just outputed a currentPath contents, then we would have a plain DFS output like this:

1 2 5
1 2 6
1 3 7
1 4 8
1 4 9

Now, we need to use our UsedOnce. Let's find the last used-once-node (which has already been in an output) in current path and output all the path from this node inclusively. It is guaranteed that such node exists because, at least the last node in a path has never been met before and couldn't be marked as used once.

For instance, if the current path is "1 2 3 4 5" and 1, 2, 3 are marked as used once - then output "3 4 5".

In your example:

1. We are at "1 2 5". All of them are unused, output "1 2 5" and mark 1, 2, 5 as used once
2. Now, we are at "1 2 6". 1, 2 are used - 2 is the last one. Output from 2 inclusively, "2 6", mark 2 and 6 as used.
3. Now we are at "1 3 7", 1 is used, the only and the last. Output from 1 inclusively, "1 3 7". Mark 1, 3, 7 as used.
4. Now we are at "1 4 8". 1 is used, the only and the last. Output "1 4 8".
5. Now we are at "1 4 9". 1, 4 are used. Output from 4 - "4 9".

It works because in a tree "used node" means "used (the only parent) edge between it and its parent". So, we actually mark used edges and do not output them again.

For example, when we mark 2, 5 as used - it means that we mark edges 1-2 and 2-5. Then, when we go for "1 2 6" - we don't output edges "1-2" because it is used, but output "2-6".
Marking root node (node 1) as used once doesn't affect the output because its value is never checked. It has a physical explanation - root node has no parent edge.

Sorry for a poor explanation. It is pretty difficult to explain an algorithm on trees without drawing :) Feel free to ask any questions concerning algorithms or C#.

Here is the working IDEOne demo.

P.S. This code is, probably, not a good and proper C# code (avoided auto-properties, avoided LINQ) in order to make it understandable to other coders.

Of course, this algorithm is not perfect - we can remove currentPath because in a tree the path is easily recoverable; we can improve output; we can encapsulate this algorithm in a class. I just have tried to show the common solution.

Answer 2

This is a tree. The other solutions probably work but are unnecessarily complicated. Represent a tree structure in Python.

class Node:
    def __init__(self, label, children):
        self.label = label
        self.children = children

Then the tree

  1
 / \
2   3
   / \
  4   5

is Node(1, [Node(2, []), Node(3, [Node(4, []), Node(5, [])])]). Make a recursive procedure as follows. We guarantee that the root appears in the first path.

def disjointpaths(node):
    if node.children:
        paths = []
        for child in node.children:
            childpaths = disjointpaths(child)
            childpaths[0].insert(0, node.label)
            paths.extend(childpaths)
        return paths
    else:
        return [[node.label]]

This can be optimized (first target: stop inserting at the front of a list).