Newton finite differences with Tikz

I am trying to picture Newton's finite differences method with a Tikz tree. Unfortunately, a few nodes are doubled. Is the approach wrong or is there a solution?

\documentclass{article}
\usepackage{tikz}
\usepackage[active,tightpage]{preview}
\PreviewEnvironment{tikzpicture}
\setlength\PreviewBorder{0pt}%

\tikzset{root/.style={align=center,draw=none},level 2/.style={align=center,left=1.5cm}}

\begin{document}
\begin{tikzpicture}[grow=left,
level 1/.style={sibling distance=15mm},edge from parent/.style={<-,draw},>=latex]

\node[root] {$\delta_{[x_0,x_1,x_2,x_3]}$}
child {node[level 2] (c1) {$\delta_{[x_0,x_1,x_2]}$}
child {node[level 2] (c11) {$\delta_{[x_0,x_1]}$}
child {node[level 2] (c111) {$\delta_{[x_0]}$}}
child {node[level 2] (c112) {$\delta_{[x_1]}$}}
}
child {node[level 2] (c12) {$\delta_{[x_1,x_2]}$}
}
}
child {node[level 2] (c2) {$\delta_{[x_1,x_2,x_3]}$}
child {node[level 2] (c21) {$\delta_{[x_1,x_2]}$}}
child {node[level 2] (c22) {$\delta_{[x_2,x_3]}$}
child {node[level 2] (c221) {$\delta_{[x_2]}$}}
child {node[level 2] (c222) {$\delta_{[x_3]}$}}
}
};
\end{tikzpicture}
\end{document}


For instance, nodes c12 and c21 are identical. I want to keep them both without drawing one of them.

• Are there arrows from middle two on the left to the x1,x2 node? – percusse Jun 8 '13 at 10:12
• Potentially ignorant comment: what you're trying to draw isn't technically a tree (since x1,x2 has two different parents), so it might be inappropriate to use the TikZ tree syntax for this job. – John Wickerson Jun 8 '13 at 13:02
• @percusse nodes [x1] and [x2] should be connected to [x1x2]. Not done here because the explained difficulty is repeated. – pluton Jun 8 '13 at 13:58
• @pluton Can you show more examples of these drawings or give some general rules about these drawings? Certainly, you could kust hide one of the nodes (e.g. text opacity=0) or use the [missing] syntax and draw the edge extra. But maybe there is a better approach with other tree packages (using TikZ), or maybe the chains library is more helpful, or one can use some intelligent styles/keys/macros that makes this better. Or, of you want to get adventurous, and use the Graph drawing facilities of the current CVS version of TikZ? – Qrrbrbirlbel Jun 9 '13 at 22:35
• Reading yours and percusse’s comments, this resembles Pascal’s triangle. Maybe this is better done in a recursive loop? By the way, you can give one node two (or more) names with the alias option: node [name=c21, alias=c22] (name=c21 is the same as the (c21) syntax). – Qrrbrbirlbel Jun 9 '13 at 22:41

What follows are two solutions that uses chains.

The second solution builds the diagram column for column and uses four chains for it (the last chain consists only of one node). All chains go down (“below”). The edges are drawn manually.

The first solution (which I find a little bit smoother) uses eight chains. Four of them go left-down (“below left”), the other four left-up (“above left”). The edges are joins and are drawn automatically. As all nodes belong to two chains, the \chainin macro is used.
There is one annoyance: The first node of the left-down (“below left”) chains needs it chain on on the left-up chains, all other nodes the other way around. (Or I’m too dizzy to see a solution that is straight-forward.)

As the solutions use different placement options the node distances are different (firstly because one solution uses only-vertical placements and the other uses vertical and horizontal placement, and secondly because of my xshift* approach in the second solution). This could be solved, though … somehow.

I added tiny, blue labels to highlight the names of the nodes.

Code

\documentclass[tikz,convert=false]{standalone}
\usetikzlibrary{positioning,chains,backgrounds}
\newcommand*{\toplevel}{3}
\newcommand*{\base}{\delta}
\newcommand*{\bbase}{x}
\newcommand*{\nodeOnTwoChains}[2]{% shortcut to clean up the loop and to deal better with two chains
\node[on chain=#1,
label={[font=\tiny,blue,label distance=-2mm]below:c-\level-\llevel}
] (c-\level-\llevel)
{$\base_{[\foreach \bbbase in {\llevel,...,\lastlevel} {\ifnum\bbbase=\llevel\else,\fi\bbase_{\bbbase}}]}$};
\chainin (c-\level-\llevel) [on chain=#2];
}
\begin{document}
\begin{tikzpicture}[gridded,
node distance=0cm and 1.5cm,
start chain/.list/.expanded={0 going below left,... going below left,\toplevel\space going below left},
start chain/.list/.expanded={0' going above left,...' going above left,\toplevel' going above left},
every join/.append style={latex-},
every on chain/.style={join},
]
\foreach \level[evaluate={\lastlevel=int(\toplevel-\level)}] in {0,...,\toplevel} {
\foreach \llevel in {0,...,\lastlevel} {
\ifnum\llevel=0
\nodeOnTwoChains{\llevel'}{\level}
\else
\nodeOnTwoChains{\level}{\llevel'}
\fi
}
}
\end{tikzpicture}
\end{document}


Output

This is not what I was expecting when I started to answer this question.

There are certainly many ways to solve this. The Graph Drawing library of the CVS version comes to mind (which can a) draw graphs where children have more than one parent and b) place the nodes much better), but as even the subscript has some rule to them, I wrapped this inside two \foreach loops.

The nodes in each column are placed with the chains library (which is more or less the same as using below=of \tikzchainprevious repeatedly while updating \tikzchainprevious). The positioning-plus library makes it easy to use the already specified node distance (or one part of it) without storing it in some macro. It is only used for the xshift* option to mimic the below right option for half the vertical and one time the horizontal distance.

There are maybe better ways with another kind of chains arrangement. Especially as it makes it possible to use the join options but one has probably to do a lot of \chainins because the chains split up at every node in every direction. It seemed easier to do this manual with two edges.

Code

\documentclass[tikz,convert=false]{standalone}
\usetikzlibrary{positioning-plus,chains,backgrounds}
\newcommand*{\toplevel}{3}
\newcommand*{\base}{\delta}
\newcommand*{\bbase}{x}
\begin{document}
\begin{tikzpicture}[gridded,
node distance=.5cm and 1.5cm,
start chain/.list/.expanded={0 going below,... going below,\toplevel\space going below},
every edge/.append style={latex-}
]

\coordinate (@aux) at (0,0);
\foreach \level in {0,...,\toplevel} {
\ifnum\level>0
\path (c-\number\numexpr\level-1\relax-\number\numexpr\level-1\relax.south east) -- coordinate[pos=.5] (@aux) (c-\number\numexpr\level-1\relax-\level.north east);
\tikzset{shift={([xshift*]@aux)}}
\fi
\foreach \llevel[evaluate={\lllevel=int(\llevel-\level)}] in {\level,...,\toplevel} {
\node[on chain=\level,
label={[font=\tiny,label distance=-2mm,blue]below:c-\level-\llevel}
] (c-\level-\llevel) {$\base_{[\foreach \bbbase in {\lllevel,...,\llevel} {\ifnum\bbbase=\lllevel\else,\fi\bbase_{\bbbase}}]}$};
\ifnum\level>0
\path (c-\level-\llevel) edge (c-\number\numexpr\level-1\relax-\number\numexpr\llevel-1\relax)
edge (c-\number\numexpr\level-1\relax-\llevel);
\fi
}
}
\end{tikzpicture}
\end{document}


More

Oh my!