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
                    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)