Revision history [back]

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
new_leaves.append((n,v,b.union([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)