algorithm - List of all edge disjoint paths in a tree -

in generic tree represented common node structure having parent , child pointers, how can 1 find list of paths have no overlapping edges each other , terminate leaf node.

for example, given tree this:

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

the desired output list of paths 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 path lists , order can vary based on order of processing of tree branches. example, following possible solution if process left branches first:

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

for sake of question, no specific order required.

you can use recursive dfs algorithm modifications.
didn't language use, so, hope c# ok you.

let's define class our tree node:

public class node {     public int id;     public bool usedonce = false;     public bool visited = false;     public node[] children; } 

take @ usedonce variable - can pretty ambigious.
usedonce equals true if node has been used once in output. since have tree, means an edge node parent has been used once in output (in tree, every node has 1 parent edge edge parent). read not become confused in future.

here have simple, basic depth-first search algorithm implementation.
magic covered in output method.

list<node> currentpath = new list<node>(); // list of visited nodes  public void dfs(node node) {     if (node.children.length == 0) // if leaf (no children) - output     {         outputandmarkasusedonce(); // here goes magic...         return;     }      foreach (var child in node.children)     {         if (!child.visited) // every not visited children call dfs         {             child.visited = true;             currentpath.add(child);             dfs(child);              currentpath.remove(child);             child.visited = false;         }     } } 

if outputandmarkedasusedonce outputed currentpath contents, have plain dfs output this:

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

now, need use our usedonce. let's find last used-once-node (which has been in output) in current path , output path node inclusively. guaranteed such node exists because, @ least last node in path has never been met before , couldn't marked used once.

for instance, if current path "1 2 3 4 5" , 1, 2, 3 marked used once - output "3 4 5".

in example:

1. we @ "1 2 5". of them unused, output "1 2 5" , mark 1, 2, 5 used once
2. now, @ "1 2 6". 1, 2 used - 2 last one. output 2 inclusively, "2 6", mark 2 , 6 used.
3. now @ "1 3 7", 1 used, , last. output 1 inclusively, "1 3 7". mark 1, 3, 7 used.
4. now @ "1 4 8". 1 used, , last. output "1 4 8".
5. now @ "1 4 9". 1, 4 used. output 4 - "4 9".

it works because in tree "used node" means "used (the parent) edge between , parent". so, mark used edges , not output them again.

for example, when mark 2, 5 used - means mark edges 1-2 , 2-5. then, when go "1 2 6" - don't output edges "1-2" because used, output "2-6".
marking root node (node 1) used once doesn't affect output because value never checked. has physical explanation - root node has no parent edge.

sorry poor explanation. pretty difficult explain algorithm on trees without drawing :) feel free ask questions concerning algorithms or c#.

here working ideone demo.

p.s. code is, probably, not , proper c# code (avoided auto-properties, avoided linq) in order make understandable other coders.

of course, algorithm not perfect - can remove currentpath because in tree path recoverable; can improve output; can encapsulate algorithm in class. have tried show common solution.