1

I'm trying to use layered graph layouts to generate Directed Acyclic Graphs where all nodes are partitioned into layers. The following code produces a near-perfect result.

\RequirePackage{luatex85}
\documentclass{article}

\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{a4wide}

\usepackage{tikz}
\usetikzlibrary{graphs,graphdrawing,quotes}
\usegdlibrary{layered}

\begin{document}
\begin{figure}
\centering
\begin{subfigure}[]{0.3\textwidth}
\centering
\begin{tikzpicture}[rounded corners]
\graph [layered layout,
edge quotes={fill=white,inner sep=1pt,font=\scriptsize},
nodes={circle,draw,inner sep=.2,outer sep=0, minimum size=.45cm},
level sep=1.5cm, %vertical distance between layers
sibling distance=2cm, %distance between nodes of the same connected component in the same layer
component sep=0cm %distance between connected components
]
{
{
[nodes={draw=none,text opacity=0}, edge={draw=none}]
l0 ->["$v0$"] l1 ->["$v1$"] l2 ->["$v2$"] l3 ->["$v4$"] l4 ->["$v5$"] l5;
},
{[edge={pos=.45}]
r/"$r$";
t/"$t$";
2/"$u_{2}$";
3/"$u_{3}$";
4/"$u_{4}$";
5/"$u_{5}$";
6/"$u_{6}$";
7/"$u_{7}$";
8/"$u_{8}$";
9/"$u_{9}$";
10/"$u_{10}$";
11/"$u_{11}$";
12/"$u_{12}$";
r ->["$0$",bend left=0] 2,
r ->["$1$",bend left=0] 3,
2 ->["$0$",bend left=0] 4,
2 ->["$1$",bend left=0] 5,
3 ->["$0$",bend left=0] 6,
3 ->["$1$",bend left=0] 4,
4 ->["$0$",bend left=0] 7,
4 ->["$1$",bend left=0] 8,
5 ->["$0$",bend left=0] 9,
5 ->["$1$",bend left=0] 7,
6 ->["$0$",bend left=0] 8,
6 ->["$1$",bend left=0] 9,
7 ->["$0$",bend left=0] 10,
7 ->["$1$",bend left=0] 11,
8 ->["$0$",bend left=0] 12,
8 ->["$1$",bend left=0] 10,
9 ->["$0$",bend left=0] 11,
9 ->["$1$",bend left=0] 12,
10 ->["$1$",bend left=-80] t,
10 ->["$4$",bend left=-60] t,
10 ->["$7$",bend left=-40] t,
10 ->["$10$",bend left=-20] t,
10 ->["$13$",bend left=0] t,
10 ->["$16$",bend left=20] t,
10 ->["$19$",bend left=40] t,
10 ->["$22$",bend left=60] t,
10 ->["$25$",bend left=80] t,
11 ->["$0$",bend left=-80] t,
11 ->["$3$",bend left=-60] t,
11 ->["$6$",bend left=-40] t,
11 ->["$9$",bend left=-20] t,
11 ->["$12$",bend left=0] t,
11 ->["$15$",bend left=20] t,
11 ->["$18$",bend left=40] t,
11 ->["$21$",bend left=60] t,
11 ->["$24$",bend left=80] t,
12 ->["$2$",bend left=-80] t,
12 ->["$5$",bend left=-60] t,
12 ->["$8$",bend left=-40] t,
12 ->["$11$",bend left=-20] t,
12 ->["$14$",bend left=0] t,
12 ->["$17$",bend left=20] t,
12 ->["$20$",bend left=40] t,
12 ->["$23$",bend left=60] t,
}
};
\begin{scope}[node distance=.4cm,font=\scriptsize]
\node[right of=r]{$0$};
\node[right of=t]{$1$};
\node[right of=2]{$0$};
\node[right of=3]{$2$};
\node[right of=4]{$0$};
\node[right of=5]{$1$};
\node[right of=6]{$2$};
\node[right of=7]{$0$};
\node[right of=8]{$2$};
\node[right of=9]{$1$};
\node[right of=10]{$0$};
\node[right of=11]{$1$};
\node[right of=12]{$2$};
\end{scope}
\end{tikzpicture}
\caption{c0(mod5)}
\end{subfigure}
\caption{test 0}
\end{figure}
\end{document}

enter image description here

Notice that for some weird reason, vertex t is placed in the same layer as u7, u8, u9, resulting in a lot of edge overlap. Vertex t should have been placed in a new layer, below the layer containing vertices u10, u11, u12. Is there a way I can force this?

According to the Tikz manual chapter 31st, the layered layout algorithm performs the following steps:

  1. Cycle removal.
  2. Layer assignment (sometimes called node ranking).
  3. Crossing minimization (also referred to as node ordering).
  4. Node positioning (or coordinate assignment).
  5. Edge routing.

Technically I don't need steps 1,2,5 because I already know the layers for each node, and my graph is guaranteed not to contain cycles. I do however need step 3 to determine the ordering of nodes in each layer to minimize crossings, as well as step 4 to determine coordinates.

  • This is at best a workaround but if you replace 10 ->["$1$",bend left=-80] t, by 10 ->["$1$",bend left=-80] t[nudge=(down:4.5cm)], you can "nudge" t down. – marmot Mar 31 at 4:00
  • The issue is caused by bugs in layered layout. (1) an easy fix would be to set the node ranking algorithm to minimum height layer assignment as opposed to the default linear optimization layer assignment. However, the minimum height layer assignment is bugged because NodeRankingMinimumHeight.lua line 31 should be for _,edge in ipairs(edges) do as opposed to for _,edge in ipairs(edge) do. (2) even after fixing this, there's another bug. Somehow the number of incoming edges into vertex t appears to be 0 in NodeRankingMinimumHeight.lua! Need to figure out how to file bug report. – Joris Kinable Mar 31 at 11:37
  • The 2nd issue is caused by a bug in node:getIncomingEdges() which is invoked in NodeRankingMinimumHeight.lua. For vertex t, the set of incoming edges is empty. This seems to be caused by the lines r/"$r$"; t/"$t$"; .... Removing those lines fixes the issue. Clearly you loose the node labels. Any workarounds? Bug reported: sourceforge.net/p/pgf/bugs/525 – Joris Kinable Mar 31 at 12:38

Your Answer

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

Browse other questions tagged or ask your own question.