7

I'd like to draw trees like the following:

desired tree display http://quicklatex.com/cache3/ql_c0f6b5397c19caf09ce70d6e47841eb7_l3.png

That is, I have edges which are crossing. The tree should be drawn like a regular tree (without crossings) except at the last level where the leaves can be in any horizontal order. The number of nodes etc. is arbitrary, the image is just an example.

The only thing I know about the tree is (a) its structure, that is, nodes and their children, and (b) an ordering number (=x position) for each leaf which determines where the leaves should be displayed horizontally to form the crossings. In the example above, I would know a1 is at position 0, b1 at 1, a2 at 2, and b2 at 3. I can use these numbers when I draw a specific leaf.

The code must represent the structure of the tree, like that:

\documentclass[a4paper]{scrartcl}
\usepackage{tikz}
\usepackage{tikz-qtree}
\begin{document}
\begin{tikzpicture}
\tikzset{frontier/.style={distance from root=70pt}}
  \Tree [.Z [.\node{A};
                \node{a1};
                \node{a2}; ]
              [.\node{B};
                \node{b1};
                \node{b2}; ] ]
\end{tikzpicture}
\end{document}

which produces:

non-crossing tree display http://quicklatex.com/cache3/ql_4217cf1d35018cf2016b55ac580d6085_l3.png

Ideally, now I'd like to reorder the leaves based on their ordering numbers that I know:

  \Tree [.Z [.\node{A};
                \node at (0,0) {a1};
                \node at (2,0) {a2}; ]
              [.\node{B};
                \node at (1,0) {b1};
                \node at (3,0) {b2}; ] ]

The problem is that this becomes:

wrong tree http://quicklatex.com/cache3/ql_8b543330e2e251476b91100f13dcca4a_l3.png

Question: How can the repositioning of the leaves be achieved without loosing the automatic tree layout functionality of tikz-qtree?

Some background: These are derivation trees generated recursively by so-called multiple context-free grammars which can model languages like a^i b^j a^i b^j. I appended numbers to the terminals to make it more explicit where they end up when reordered.

  • What should it look like? If the nodes are automatically laid out, you get the first result. If you specify them, they go where you say. I don't understand how they can be both repositioned and automatically laid out. – cfr Jan 29 '15 at 16:18
  • I only want to specify where the leaf nodes should be after positioning the tree like usual, you could think of it like a post-processing step where the leaf nodes are moved somewhere in the horizontal line where they are. Edit: The problem is that I don't want to use the standard tikz left-of etc. positioning as it will overlap in most cases. – letmaik Jan 29 '15 at 16:21
  • See my edited answer for a way to automate the count of the total number of leaves. I can't guarantee this won't break but it works for your example, so it should at least give you some potentially useful ideas. – cfr Jan 30 '15 at 22:07
  • Just tested it for a bigger one, seems to work just fine! i.imgur.com/UUfWDAw.jpg – letmaik Jan 31 '15 at 11:39
7

Do you want something like this?

Note that I'm not at all sure I understand what you are trying to do.

In your comments on Gonzalo Medina's answer, you say you know that 'a' must end up in position 0 and 2, and 'b' in position 1 and 3, say. But it isn't clear how you expect this to be automated. (How can TeX tell the difference between 1 'a' and another? There is no input word 'abab' in your example code, so this information doesn't seem to be provided in any form.)

forest allows you to create 'dynamic' trees i.e. you can move stuff around at various stages. Here, I shift the nodes after the layout of the tree is computed but before it is drawn:

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}

\begin{document}
  \begin{forest}
    for tree={
      parent anchor=south,
      child anchor=north,
      where n children=0{
        s sep=1.5em,
        inner xsep=0pt
      }{},
    }
    [Z
      [A
        [a1
        ]
        [a2, before drawing tree={x+=1.5em}
        ]
      ]
      [B
        [b1, before drawing tree={x-=1.5em}
        ]
        [b2
        ]
      ]
    ]
  \end{forest}
\end{document}

shifting nodes after layout is computed

EDIT

The OP edited the question to demonstrate a solution based on my answer above and discussion in comments. However, that solution required manually specifying the total number of leaf nodes. I think that the following should avoid this requirement. The idea is to increment a LaTeX counter for each leaf node and then use the final value of this counter to adjust the position of the node before the tree is drawn. A new style, leaf position is defined which takes one argument which should be the position of the node in the ordered sequence i.e. leaf position=2 if the leaf should end up in the third (number 2) slot.

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}
\usepackage{calc}

\begin{document}

\begingroup

\newcounter{leafnodes}
\setcounter{leafnodes}{0}
\forestset{
  leaf position/.style={
    before drawing tree={
      where n children=0{
        x/.pgfmath={(#1-(.5*\theleafnodes)+.5)*1.5em}
      }{},
    }
  },
}
\begin{forest}
  for tree={
    parent anchor=south,
    child anchor=north,
    where n children=0{
      s sep=1.5em,
      inner xsep=0pt,
      delay={TeX={\stepcounter{leafnodes}}},
    }{},
  },
  [Z
    [A
      [a1, leaf position=0
      ]
      [a2, leaf position=2
      ]
    ]
    [B
      [b1, leaf position=1
      ]
      [b2, leaf position=3
      ]
    ]
  ]
\end{forest}
\endgroup

\end{document}

automate calculation of total number of leaf nodes

EDIT EDIT

In response to the discussion in comments, here's an example which puts all of the leaf nodes on the same level, using tier=leaves, and which sets the height of these nodes to a standard size so that the edges drawn from the parents do not terminate at different heights. I've also moved the leftmost node a bit left since it looked a bit odd with a larger tree. Obviously this could be adjusted further if desired.

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}
\usepackage{calc}

\begin{document}

\begingroup

\newcounter{leafnodes}
\setcounter{leafnodes}{0}
\forestset{
  leaf position/.style={
    before drawing tree={
      where n children=0{
        x/.pgfmath={(#1-(.5*\theleafnodes))*1.5em}
      }{},
    }
  },
}
\begin{forest}
  for tree={
    parent anchor=south,
    child anchor=north,
    where n children=0{
      s sep=1.5em,
      inner xsep=0pt,
      tier=leaves,
      text height=5pt,
      delay={TeX={\stepcounter{leafnodes}}},
    }{},
  },
  [Z
    [A
      [A
        [A
          [T, leaf position=6
          ]
          [y, leaf position=1
          ]
          [e, leaf position=0
          ]
        ]
        [a, leaf position=5
        ]
        [a, leaf position=4
        ]
      ]
      [a1, leaf position=8
      ]
      [a2, leaf position=2
      ]
    ]
    [B
      [b1, leaf position=7
      ]
      [b2, leaf position=3
      ]
    ]
  ]
\end{forest}
\endgroup

\end{document}

levelled leaves

  • This is getting closer. Sorry for the confusion... to make it absolutely clear (I hope): forget about the double 'a's etc. What I know is: I know in which order each leaf node should be at the bottom, that is, a1 at position 0, b1 at 1, a2 at 2, and b2 at 3. I have these numbers and can use them in the code for the respective nodes, that is, in [a2, before drawing tree={x+=1.5em} I can use the number 2 somehow, which is more or less equivalent to an absolute position. Your solution is based on relative positions, and I don't know how to infer the relative ones from the absolute ones. – letmaik Jan 30 '15 at 8:49
  • @neo Well, xy is the absolute coordinate system as opposed to ls which is relative to the tree. You could say e.g. x=... and then multiply the distance by the number i.e. it doesn't have to be x+= or x-=. It can just be x=. – cfr Jan 30 '15 at 12:31
  • @GonzaloMedina Well, you used forest first. But I already gave you (+1), so I can't reciprocate further ;). The dynamic tree stuff is weirdly cool. Have you heard anything further about testing the new beta? – cfr Jan 30 '15 at 21:11
  • 1
    @cfr I just tested your code but it shows differently then your image: oi62.tinypic.com/24fhhm9.jpg Did you forget anything? – letmaik Jan 30 '15 at 23:37
  • @neo I just copied the code back from my answer above, compiled it and got the same result I posted earlier. You didn't by any chance omit the delay did you? I can reproduce the result you posted if I take that out. – cfr Jan 31 '15 at 0:13
5

If you're willing to switch to the powerful forest package, this can be easily done:

\documentclass[a4paper]{scrartcl}
\usepackage{forest}

\begin{document}

\begin{forest}
for tree={
  parent anchor=south,
  child anchor=north,
  l sep=0.75cm
}
[Z,s sep=-40pt
  [A,calign=fixed edge angles,calign primary angle=-30,calign secondary angle=60
    [a1]
    [a2]
  ]
  [B,calign=fixed edge angles,calign primary angle=-60,calign secondary angle=30
    [b1]
    [b2]
  ]
]
\end{forest}

\end{document}

enter image description here

  • Interesting, how would I calculate the angles (or use something else?) if I only have the x coordinates of the leaves? – letmaik Jan 29 '15 at 16:31
  • @neo I am not sure I understand your question. Can you please give a real example of the situation mentioned? – Gonzalo Medina Jan 29 '15 at 16:57
  • Sure, let's say the leaves are "a", "a", "b", "b" in normal tree alignment. My input word was "abab", and I know which character belongs to which position in the input word. That is, "a"->0, "a"->2, "b"->1, "b"->3 when starting to count at zero. And this is the only information I got for aligning the leaf nodes. I want to align them like the input word. – letmaik Jan 29 '15 at 17:01
  • I added an explanation in the question to make it more clear hopefully, sorry about the confusion. – letmaik Jan 30 '15 at 8:56
1

Derived from cfr's original answer and comments:

\documentclass[tikz,border=5pt]{standalone}
\usepackage{forest}
\usepackage{calc}

\begin{document}

\begingroup

\def\f{1.5em} % scale
\def\n{4} % number of leaves

\def\xleaf#1{\f*(#1-\n/2+0.5)} % calculates x of a leaf
\begin{forest}
  for tree={
    parent anchor=south,
    child anchor=north,
    where n children=0{
      s sep=1.5em,
      inner xsep=0pt
    }{},
  }
  [Z
    [A
      [a1, before drawing tree={x=\xleaf{0}}
      ]
      [a2, before drawing tree={x=\xleaf{2}}
      ]
    ]
    [B
      [b1, before drawing tree={x=\xleaf{1}}
      ]
      [b2, before drawing tree={x=\xleaf{3}}
      ]
    ]
  ]
\end{forest}
\endgroup

\end{document}

I guess this is as far as it gets. A shame that it needs the total number of leaves though but I guess it's too complicated to derive that automatically from the tree and then use it inside the before drawing tree expressions.

Note: cfr's updated answer can count leaves now!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.