1 | initial version |

From what I understood or your vague description, this is one possibility

```
def make_tree(G, root):
r"""
This function output a pair ``(tree, labels)`` where the tree is on the
nodes `{0, 1, 2, ..., n-1}` and the labels is a list of tuples of length
``n`` that correspond to the label of the vertices.
"""
T = DiGraph()
labels = [root]
n = 0
leaves = [(0,root,set([root]))]
current = set(G)
while leaves:
new_leaves = []
new_current = set()
for i,u,b in leaves:
for _,v,_ in G.outgoing_edges(u):
if v in current and v not in b:
labels.append(v)
n += 1
T.add_edge(i,n)
new_leaves.append((n,v,b.union([v])))
new_current.add(v)
leaves = new_leaves
current = new_current
return T,labels
def tree_from_graph(T, i, labels):
r"""
This function makes a labelled tree out of a graph in a recursive way.
"""
children = [tree_from_graph(T, j, labels) for _,j,_ in sorted(T.outgoing_edges(i), key=lambda x: labels[x[1]])]
return LabelledOrderedTree(children, label=labels[i])
```

Then if you load this file in Sage (e.g. with %runfile) you can do

```
sage: compatibility = {
....: (1,1): [(2,2), (2,3), (2,1)],
....: (1,2): [(1,3), (2,1)],
....: (1,3): [(1,2)],
....: (2,1): [(1,1), (1,2),(2,2)],
....: (2,2): [(1,1), (2,1)],
....: (2,3): [(1,1)] }
sage: G = DiGraph(compatibility)
sage: T, labels = make_tree(G, (1,1))
sage: tree_from_graph(T, 0, labels)._ascii_art_()
______(1, 1)__
/ / /
(2, 1) (2, 2) (2, 3)
| |
(2, 2) (2, 1)
```

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.