Ask Your Question
1

How to draw special trees from a list consisting of tuples with Sage?

asked 2015-11-12 10:31:27 -0500

Bern gravatar image

updated 2015-11-12 14:10:41 -0500

I have the following problem:

Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list L.

To every tuple (i,j) I have associated a list L{ij}=[...]. The entries of L{ij} are special other tuples from L, which we call "compatible with the tuple (i,j)". So, in general, all the lists L{ij} are different from one another.

I would like the PC to draw trees in the following manner:

In the first level, there is one tuple T. This was manually chosen from the list L.

In the second level, there are all the tuples T1, ... , Tr, which are compatible with T. Each of them shall be connected with T by a single line.

In the third level, for each tuple Ts of the second line, there are drawn all the tuples that are compatible with Ts and at the same time already appeared one level higher (here: in level 2). Call the tuples of this level T11, ... , T1m, T21, ... T2p, .... Each of the T11, ... , T1m shall be connected with T1 by a single line. Each of the T21, ... , T2p shall be connected with T2 by a single line, and so on.

Iterate this, until the process stops (is finished) and you have drawn a tree.

The arrows of the tree are just edges and the points are the tuples, that should be numbered by (1,1), ... , (k,n). Note that not every entry of L has to appear in the resulting tree, since the lists L{ij} need not be a partition of L.

Here is a small example:

Let L=[(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)].

Let L_{11}=[(2,2), (2,3), (2,1)].
Let L_{12}=[(1,3), (2,1)].
Let L_{13}=[(1,2)].
Let L_{21}=[(1,1), (1,2),(2,2)].
Let L_{22}=[(1,1), (2,1)].
Let L_{23}=[(1,1)].

This gives the following tree for (1,1):

              (1,1)
  --------------|-------------- 
  |             |             |
(2,1)         (2,2)         (2,3)
  |             |                   
  |             |                   
(2,2)         (2,1)

Not only the tree, but also its "longest" branches (i.e. these, that can no more be extended by the procedure above...in the above example, these are (1,1)-(2,1)-(2,2) and (1,1)-(2,2)-(2,1) and (1,1)-(2,3)) should be returned (there are no repetitions allowed in the branches).

Now, my question is:

What's the best possibility to solve problems of this kind in a fast way with Sage?

Thanks for the help!

edit retag flag offensive close merge delete

Comments

According to your definition, i do not understand why there is no infinite branch in your example like (1,1)-(2,1)-(2,2)-(2,1)-(2,2)-(2,1)-(2,2)-(2,1)-(2,2)-(2,1)-(2,2)-....

tmonteil gravatar imagetmonteil ( 2015-11-12 13:57:28 -0500 )edit

Hi, thank you for your comment. I draw the tree in order to find longest branches of tuples that are compatible with one another...therefore, I would prefer to have no repetitions in the branches...this was not clear from my original question...I edited it now.

Bern gravatar imageBern ( 2015-11-12 14:10:00 -0500 )edit

Is the example still wrong or is there something missing? It seems like (2, 2) should not have any descendants since (1, 1) and (2, 1) have already appeared. Also, shouldn't (1, 2) be a child of (2, 1)?

fidbc gravatar imagefidbc ( 2015-11-12 14:44:36 -0500 )edit

Hi, thank you for your comment. $(1,1)$ and $(2,1)$ appeared in level 2. So, in level 3 we write down $(2,1)$ as a descendant of $(2,2)$, since it is compatible with $(2,2)$. This is true for $(1,1)$, too, but we didn't allow repetitions...$(1,1)$ would be a descendant and an ancestor.

$(1,2)$ is no descendant of $(2,1)$, because it did not appear in level 2.

Bern gravatar imageBern ( 2015-11-12 19:17:43 -0500 )edit

Since I did not explain it very well in the original question, I would like to add the following comment for clarification:

If we choose an arbitrary, but fixed, branch, then it is not allowed that a fixed tuple appears both as a predecessor and an ancestor (this is what I meant by repetitions). But, one fixed tuple can appear in two neighboring branches (this is what I forgot to mention).

Bern gravatar imageBern ( 2015-11-19 05:58:59 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2015-11-24 08:59:13 -0500

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)
edit flag offensive delete link more

Comments

Thank you very much for your answer.

Bern gravatar imageBern ( 2015-11-25 21:08:31 -0500 )edit

The code is not very documented, do not hesitate to ask more if you need. There are at least good pointers to the relevant Sage objects: Digraph and LabelledOrderedTree.

vdelecroix gravatar imagevdelecroix ( 2015-11-26 04:28:31 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-11-12 10:31:27 -0500

Seen: 2,973 times

Last updated: Nov 24 '15