Automatically connect nodes without overlapping other nodes or connections

In making a tree diagram with TikZ. Say that I've got the following nodes

\node(a) {$$A$$};
\node(b1) at ($(a)+(4,1)$){$$B_1$$};
\node(b2) at ($(b1)+(0,-1)$){$$B_2$$};
\node(c) at ($(b1)+(1,-0.9)$){$$C$$};
\node(d) at ($(c)+(2,0)$){$$D$$};
\node(e) at ($(d)+(1,0.5)$){$$E$$};


and that I want to draw the following connections

• (a) to (b1)
• (a) to (b2)
• (b1) to (d)
• (b2) to (e)

but I want no or as few connections as possible to overlap another node or another connection (without changing the placement of the nodes).

If I draw straight lines between the nodes

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{calc}

\begin{document}

\begin{tikzpicture}
\node(a) {$$A$$};
\node(b1) at ($(a)+(4,1)$){$$B_1$$};
\node(b2) at ($(b1)+(0,-1)$){$$B_2$$};
\node(c) at ($(b1)+(1,-0.9)$){$$C$$};
\node(d) at ($(c)+(2,0)$){$$D$$};
\node(e) at ($(d)+(1,0.5)$){$$E$$};
\draw[->] (a) to (b1);
\draw[->] (a) to (b2);
\draw[->] (b1) to (d);
\draw[->,red] (b2) to (e);

\end{tikzpicture}

\end{document}


I end up with an overlap of C and an overlap of the line B₁ and D (the red line):

Also, if I make the lines somewhat curved

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{calc}

\begin{document}

\begin{tikzpicture}
\node(a) {$$A$$};
\node(b1) at ($(a)+(4,1)$){$$B_1$$};
\node(b2) at ($(b1)+(0,-1)$){$$B_2$$};
\node(c) at ($(b1)+(1,-0.9)$){$$C$$};
\node(d) at ($(c)+(2,0)$){$$D$$};
\node(e) at ($(d)+(1,0.5)$){$$E$$};
\draw[->] (a) to[out=20,in=180] (b1);
\draw[->] (a) to[out=0,in=180] (b2);
\draw[->] (b1) to[out=0,in=160] (d);
\draw[->,red] (b2) to[out=0,in=180] (e);
\draw[->,red,dashed] (b2) to[out=-40,in=240] (e);

\end{tikzpicture}

\end{document}


I get the same kind of overlap:

What I'm after is a result like the dashed red line that don't overlap anything but without having to manually set what angles the lines should enter and exit nodes from.

In short, is there a way to avoid overlaps of nodes and other lines except for manually changing angles for lines, i.e. can I tell TikZ to avoid drawing over other nodes and lines and draw around them instead?

• this is beyond my tex ability to make a fool proof code but maybe using the intersection library, you can check if there is any cross-over and resort to bend option if there is any, then simply comparing the vertical coordinate of end-points decide over or under pass. – percusse Sep 8 '11 at 19:30
• Hmm, while your problem is yet quite simple, this is a highly non-trivial task. My guess would be that it is comparable to the "traveling salesman" problem, so the computation power required will probably rise with more than n², so doing this inside LaTex is probably not a good idea. – Tom Bombadil Sep 8 '11 at 20:48
• I'm guessing this would be an awesome feature that is going to be super-duper hard to automate. A bounty may initiate the willingness to overcome the super-duper-ness. Regardless, without sufficient general use for it (since the manual intervention might be minimal in many cases, or automation might yield sub-optimal results like pushing the dashed arrow between B_1 & C), super-duper-ness may reign supreme. – Werner Sep 9 '11 at 4:20
• Aha, I found it: graphs may be planar, but a graph with 5 vertices may well be not. So there is no general solution. But perhaps someone has the time and ability to check if planarity is possible (see the link) and then implement a solution? – Tom Bombadil Sep 9 '11 at 21:28

I have a very strong suspicion that the general problem is not really tractable by TeX/TikZ. This is based on the fact that there are programs like graphviz which have really complicated routines for solving this sort of problem. Moreover, I think that it's going to be impossible in general in that there will be configurations where there is no solution with no crossings.

So what I have to offer is the following code. This defines a to path which goes from its start to its end through a particular point. The intention being that you use it to avoid a node by saying that you want your path to go through a particular corner of the node you want to avoid; thus we use the node as the region to avoid.

To make the problem tractable, I've used a different family of curves than is used by the to[out=angle, in=angle] curves.

Here's the proof-of-concept code:

\documentclass{standalone}
%\url{http://tex.stackexchange.com/q/27899/86}
\usepackage{tikz}
\usetikzlibrary{calc}

\makeatletter
\tikzset{
through point/.style={
to path={%
\pgfextra{%
\tikz@scan@one@point\pgfutil@firstofone(\tikztostart)\relax
\pgfmathsetmacro{\pt@sx}{\pgf@x * 0.03514598035}%
\pgfmathsetmacro{\pt@sy}{\pgf@y * 0.03514598035}%
\tikz@scan@one@point\pgfutil@firstofone#1\relax
\pgfmathsetmacro{\pt@ax}{\pgf@x * 0.03514598035 - \pt@sx}%
\pgfmathsetmacro{\pt@ay}{\pgf@y * 0.03514598035 - \pt@sy}%
\tikz@scan@one@point\pgfutil@firstofone(\tikztotarget)\relax
\pgfmathsetmacro{\pt@ex}{\pgf@x * 0.03514598035 - \pt@sx}%
\pgfmathsetmacro{\pt@ey}{\pgf@y * 0.03514598035 - \pt@sy}%
\pgfmathsetmacro{\pt@len}{\pt@ex * \pt@ex + \pt@ey * \pt@ey}%
\pgfmathsetmacro{\pt@t}{(\pt@ax * \pt@ex + \pt@ay * \pt@ey)/\pt@len}%
\pgfmathsetmacro{\pt@t}{(\pt@t > .5 ? 1 - \pt@t : \pt@t)}%
\pgfmathsetmacro{\pt@h}{(\pt@ax * \pt@ey - \pt@ay * \pt@ex)/\pt@len}%
\pgfmathsetmacro{\pt@y}{\pt@h/(3 * \pt@t * (1 - \pt@t))}%
}
(\tikztostart) .. controls +(\pt@t * \pt@ex + \pt@y * \pt@ey, \pt@t * \pt@ey - \pt@y * \pt@ex) and +(-\pt@t * \pt@ex + \pt@y * \pt@ey, -\pt@t * \pt@ey - \pt@y * \pt@ex) .. (\tikztotarget)
}
}
}

\makeatother

\begin{document}
\begin{tikzpicture}
\draw
(0,0) to[through point={(2,1)}] (5,5);
\end{tikzpicture}
\end{document}


and the result:

If we put that in your code, we get the following, where the green line is that added by my code:

Here's the code:

\documentclass{standalone}
%\url{http://tex.stackexchange.com/q/27899/86}
\usepackage{tikz}
\usetikzlibrary{calc}

\makeatletter
\tikzset{
through point/.style={
to path={%
\pgfextra{%
\tikz@scan@one@point\pgfutil@firstofone(\tikztostart)\relax
\pgfmathsetmacro{\pt@sx}{\pgf@x * 0.03514598035}%
\pgfmathsetmacro{\pt@sy}{\pgf@y * 0.03514598035}%
\tikz@scan@one@point\pgfutil@firstofone#1\relax
\pgfmathsetmacro{\pt@ax}{\pgf@x * 0.03514598035 - \pt@sx}%
\pgfmathsetmacro{\pt@ay}{\pgf@y * 0.03514598035 - \pt@sy}%
\tikz@scan@one@point\pgfutil@firstofone(\tikztotarget)\relax
\pgfmathsetmacro{\pt@ex}{\pgf@x * 0.03514598035 - \pt@sx}%
\pgfmathsetmacro{\pt@ey}{\pgf@y * 0.03514598035 - \pt@sy}%
\pgfmathsetmacro{\pt@len}{\pt@ex * \pt@ex + \pt@ey * \pt@ey}%
\pgfmathsetmacro{\pt@t}{(\pt@ax * \pt@ex + \pt@ay *           \pt@ey)/\pt@len}%
\pgfmathsetmacro{\pt@t}{(\pt@t > .5 ? 1 - \pt@t : \pt@t)}%
\pgfmathsetmacro{\pt@h}{(\pt@ax * \pt@ey - \pt@ay *           \pt@ex)/\pt@len}%
\pgfmathsetmacro{\pt@y}{\pt@h/(3 * \pt@t * (1 - \pt@t))}%
}
(\tikztostart) .. controls +(\pt@t * \pt@ex + \pt@y * \pt@ey, \pt@t * \pt@ey - \pt@y * \pt@ex) and +(-\pt@t * \pt@ex + \pt@y * \pt@ey, -\pt@t * \pt@ey - \pt@y * \pt@ex) .. (\tikztotarget)
}
}
}

\makeatother

\begin{document}
\begin{tikzpicture}
\node(a) {$$A$$};
\node(b1) at ($(a)+(4,1)$){$$B_1$$};
\node(b2) at ($(b1)+(0,-1)$){$$B_2$$};
\node(c) at ($(b1)+(1,-0.9)$){$$C$$};
\node(d) at ($(c)+(2,0)$){$$D$$};
\node(e) at ($(d)+(1,0.5)$){$$E$$};
\draw[->] (a) to[out=20,in=180] (b1);
\draw[->] (a) to[out=0,in=180] (b2);
\draw[->] (b1) to[out=0,in=160] (d);
\draw[->,red] (b2) to[out=0,in=180] (e);
\draw[->,red,dashed] (b2) to[out=-40,in=240] (e);
\draw[->,green] (b2) to[through point={(d.south east)}] (e);
\end{tikzpicture}
\end{document}


As I said at the start, I think that the general problem will not be (easily) soluble (I'd be happy to be proved wrong ...). So to get around this, I require you, the user, to decide which paths have to move, and to decide which side to move it. The code then works out a nice (I hope!) path.

Explanation of the code: We want a bezier curve from the start to the finish through a particular point. In general, this would involve solving a cubic equation which, while possible, isn't pleasant. So we simplify the bezier. Let's take a bezier, a (1 - t)^3 + 3 b t (1 - t)^2 + 3 c t^2 (1 - t) + d t^3, and transform our coordinates so that a is at the origin and d is at (1,0). Then if we pick the x coordinates of b and c to be 1/3, the x-projection is linear. This means that it is easy to figure out the time at which the bezier goes through a particular vertical line.

So to make it go through a particular point, say (p,q) with p ∈ (0,1), we simply take t = p. Then we also assume that the y-coordinates of b and c are the same (say h), whence we get the formula h = q/(3 p (1 - p)).

The code above does this, only we have to work in a different coordinate system, so we have lots of orthogonal projections going on.

• Awesome solution. I assume the magic number 0.03514598035 is just a conversion from TeX points to cm? – Peter Grill Sep 10 '11 at 0:11
• @Peter: Yes (found it from some conversion website). I found that if the numbers were in pt then the computations got too large so scaling down to cm made the calculations work. – Loop Space Sep 10 '11 at 19:06
• I really appreciate your answer. I have to admit that I'm clueless of how the code works. As for compiling I don't have the package standalone installed so I changed the document class to article and tried to compile the second code block and got ! Illegal unit of measure (pt inserted). <to be read again> ? l.47 ...b2) to[through point={(d.south east)}] (e). Is it my old TikZ version (using Ubuntu 11.04's TeX Live 2009)? – N.N. Sep 12 '11 at 19:22
• @N.N.: Sorry, I shouldn't have left the standalone there. It's a class that Martin developed for creating documents the same size as their contents. It uses article internally so that should work. But I probably do use stuff from a more recent version of PGF. Ubuntu is really old. You can just install a more up-to-date version of PGF if you don't want to install the whole of TL2011 (but I do recommend a full upgrade if possible). There are questions here about how to do either (install TL2011 alongside Ubuntu, or just install PGF). – Loop Space Sep 12 '11 at 19:25
• @AndrewStacey Cheers! I grabbed PGF from CTAN and installed it locally and it compiles fine now. Is it possible to get it to pass multiple points? I tried to add another to as in \draw[->,green] (b2) to[through point={(c.south east)}] to[through point={(d.south east)}] (e); but I get the following error ! Package tikz Error: (, +, coordinate, or node expected.. – N.N. Sep 12 '11 at 19:46