allowing only horizontal edges (with labels) by using boxes of varying height for nodes

Question

I would like to take advantage of tikz-qtree's spacing algorithm to draw (horizontal) trees of the following form

 S  _     C
---| |---------
   | |    B
   |a|---------
   | | A  _  U
   |_|---| |---
         |b| V
         |_|---

where
* both nodes and edges can be labeled
* all edges are horizontal
* the nodes are made up of boxes of varying height.

Actually, I would also like to extend this to graphs that no longer are trees as in the following example

 S  _        C
---| |---------------
   | |    B     _
   |a|---------| | V
   | | A  _  U |c|---
   |_|---| |---|_|
         |b|
         |_|---------
                X

Any ideas how to extend tikz-qtree in this direction? Maybe other tikz-related packages are better suited for this purpose, if so, please let me know.

Answer 1

I would suggest using my tikz-based tree drawing package, forest. (Available at CTAN.)

I will admit, however, that drawing what you want is not trivial. First the code and the result, then the comments.

\documentclass{standalone}
\usepackage{forest}
\begin{document}
\forestset{
  horizontal/.style={
    edge node/.style={edge label={node[midway,above,font=\scriptsize]{##1}}},
    for tree={grow'=0,anchor=center,draw,s sep=3ex,align=center,
      if n children=0{tier=leaf}{},
      parent anchor=east,
      edge path={\noexpand\path[\forestoption{edge}](!u.parent anchor|-.child anchor)--(.child anchor)\forestoption{edge label};},
      before typesetting nodes={where content={}{coordinate}{}},
      fit=rectangle,
    }
  }
}
\begin{forest} horizontal
  [
    [a,minimum height=12ex
      [,edge node=C]
      [,edge node=B]
      [b,minimum height=7ex,edge node=A
        [,edge node=U]
        [,edge node=V]
      ]
    ]
  ]
\end{forest}
\quad
\begin{forest} horizontal,
  [
    [a,minimum height=12ex,s sep=1ex
      [,edge node=C]
      [\phantom{c},name=c1,tier=c,node options'={},edge node=B,s+=2ex
        [,edge node=V,before computing xy={s-=3ex}]
      ]
      [b,minimum height=7ex,edge node=A
        [\phantom{c},edge node=U,name=c2,tier=c,node options'={},
          [,phantom]
        ]
          {\node[fit=(c1)(c2),draw,inner sep=0]{c};}
        [,edge node=X]
      ]
    ]
  ]
\end{forest}
\end{document}

About the first picture. Style horizontal defined in the beginning will make it reasonably easy to draw the tree (it makes edges horizontal, defines style edge node for drawing labels, makes all the leaves align, and makes empty nodes into coordinated), but the minimum height of the nodes is not computed automatically. (This seems to be a common desire, so I'm thinking how this could be done.)

About the non-tree. The package was not really meant for these ... so this picture is necessarily done as a "hack": edges B and U end in "phantom" nodes c1 and c2; an extra node is fit over both; the position of edges V (which formally belongs to c1 node) and B adjusted manually.