Use “layered layout” with user-specified node ordering (i.e., without crossing minimization)

If and when someone answers this question in a way that demonstrates lua programming for TikZ graph algorithms, I will guarantee a 500-point bounty to that person.

According to the PGF 3.0 manual, Chapter 30, one of the key steps in the layered layout graph-drawing routine is to re-order the nodes within each layer so as to minimize edge crossing. I find that the order in which I specify the nodes is better, for my purposes, than the order created by the default algorithm.

How can I force TikZ not to employ this algorithm but instead do the "stupid" thing, just using the nodes in the same order I give them? I'm aware that this is likely to require some amount of Lua programming, but given the simplicity of the algorithm I'm asking for, it might be feasible to do as an answer to a stack-exchange question.

Note that this question differs from Why does PGF/TikZ 3.0 draw my simple layered graph as non-planar by default? primarily in that I am requesting a specific solution (implement the alternate, naive algorithm).

A "minimal" working example:

% !TEX TS-program = lualatex
\documentclass[tikz,convert,margin=10pt]{standalone}
\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{layered}
\begin{document}
\tikz[rounded corners] \graph [layered layout]
{
{[same layer] \foreach \i in {1, 2, ..., 16} {
pt\i/$P^0_{\i}$,
}};
{[same layer] \foreach \i in {1, 2, ..., 17} {
l\i/$P^1_{\i}$,
}};
\foreach \i [evaluate=\i as \j using int(\i+1)] in {1,2,...,16} {
pt\i -- l\i,
pt\i -- l\j,
};

Q/$P^1 \times P^1$ [gray];

\foreach \i [evaluate=\i using int(2*\i)] in {1,2,...,7} {
l\i -- [gray, edge node = {node [fill=white] {h}}] Q,
};

pt1 -- [gray] Q;
};
\end{document}


The result:

I would like the nodes in each layer to be numbered in order, regardless of what TikZ thinks would minimize crossings. Note that making the first two layers into a subgraph is not an acceptable solution here, because then the edge from the first layer to the third layer will not avoid the nodes in between.

• It seems like a Lua solution to this question would also be a satisfactory answer to my question. – hftf Apr 26 '14 at 9:11
• Something that would be really useful would be to be able to specify the coordinates of some nodes in the graphs and have TikZ leave them alone while taking their position in account when optimizing. That would be a (or yet another) killer feature to ditch graphviz! – Bordaigorl May 28 '14 at 20:40

Coding a new layout algorithm for tikz's graph library is a daunting task, even in Lua, even as "simple" as the one you want. The reason is the great amount of "boilerplate code" needed.

Instead, it is very easy to "cheat" and use one of the already provided algorithms, but changing one of its parts. In this case, we can take the layered layout and remove the part which does the node reordering in each layer.

But even this is not so simple, because we don't want to modify any of the lua "system files". We want all our changes to be confined to the document folder.

I've found a way to do it. I do not claim it is the cleanest way (nor even the easiest way perhaps some phases of the algorithm can be changed via pgf keys). But it works (see update 1 for a cleaner and nicer way).

What follows shows how it can be done.

The LaTeX document

\documentclass[tikz,convert,margin=10pt]{standalone}
\usetikzlibrary{graphs,graphdrawing}
%\usegdlibrary{layered}   % <--- This line removed
\usegdlibrary{layered-no-reorder}  % <--- This one added
\begin{document}
\tikz[rounded corners] \graph [layered layout]
{
{[same layer] \foreach \i in {1, 2, ..., 16} {
pt\i/$P^0_{\i}$,
}};
{[same layer] \foreach \i in {1, 2, ..., 17} {
l\i/$P^1_{\i}$,
}};
\foreach \i [evaluate=\i as \j using int(\i+1)] in {1,2,...,16} {
pt\i -- l\i,
pt\i -- l\j,
};

Q/$P^1 \times P^1$ [gray];

\foreach \i [evaluate=\i using int(2*\i)] in {1,2,...,7} {
l\i -- [gray, edge node = {node [fill=white] {h}}] Q,
};

pt1 -- [gray] Q;
};
\end{document}


layered-no-reorder.lua

This one is based in texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/library.lua. Only comments were removed, and one line changed (marked below):

local layered

require "pgf.gd.layered"

require "pgf.gd.layered.Sugiyama"
require "pgf.gd.layered.cycle_removal"
require "pgf.gd.layered.node_ranking"
require "no_crossing_minimization"      --  <-- This one changed
require "pgf.gd.layered.node_positioning"
require "pgf.gd.layered.edge_routing"


no_crossing_minimization.lua

This one is based on texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/crossing_minimization.lua. All comments were stripped out for brevity. The only interesting change is the marked line, which originally was require "pgf.gd.layered.CrossingMinimizationGansnerKNV1993".

local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
declare {
key = "no crossing minimization",
algorithm = require "noCrossing",  -- <--- This one changed
phase = "crossing minimization",
phase_default = true,

summary = [["
Fake phase. Does nothing.
"]],
documentation = [["
http://tex.stackexchange.com/questions/173540/use-layered-layout-with-user-specified-node-ordering-i-e-with
out-crossing-m
"]]
}


noCrossing.lua

This one is based on texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/CrossingMinimizationGansnerKNV1993.lua, but heavily stripped down. Only the run() function remains, and basically does nothing.

local CrossingMinimizationNone = {}

function CrossingMinimizationNone:run()
return self.ranking
end

return CrossingMinimizationNone


Update 1

There is a cleaner way to integrate the new "no reorder" algorithm into the general layered layout, without replacing the library. This way the author still has control to decide if he wants some graphs using the standard sweep crossing minimization (which is the default in Tikz) while others use the new no crossing minimization.

This is how:

• Remove the file layered-no-reorder.lua used in previous solution. It is no longer required, since standard layered library will be used instead.
• Remove the file no_crossing_minimization.lua. We will rewrite it (with a different name) in a better way.
• Keep the file noCrossing.lua as in the previous solution. This is the file which implements the new "algorigthm" for the reordering phase.

Now, write the following in a file called more-crossing-algorightms.lua:

local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
---

declare {
key = "no crossing minimization",
algorithm = require "noCrossing",
phase = "crossing minimization",
phase_default = false,

summary = [["
Fake phase. Does nothing.
"]],
documentation = [["
For more details, please see http://tex.stackexchange.com/questions/173540/use-layered-layout-with-user-specified-node-ordering-i-e-without-crossing-m
"]]
}


Note the key property. It is the name of a key which can be used later in the TikZ diagram to select this algorithm. In principle, we could declare more crossing algorithms in this same file, giving a different key to each one. This will allow to select one or other from tikz, using the appropiate key. Note also the phase_default property, which is set to false. This means that this algorithm will not be used by default, but only when it is explicitly selected with the key no crossing algorithm.

Now the main file is:

\documentclass[tikz,convert,margin=10pt]{standalone}
\usetikzlibrary{graphs,graphdrawing}

\usegdlibrary{layered}                 % <-- Now we do not replace this one

\begin{document}
\tikz[rounded corners] \graph [layered layout, no crossing minimization]
{
{[same layer] \foreach \i in {1, 2, ..., 16} {
pt\i/$P^0_{\i}$,
}};
{[same layer] \foreach \i in {1, 2, ..., 17} {
l\i/$P^1_{\i}$,
}};
\foreach \i [evaluate=\i as \j using int(\i+1)] in {1,2,...,16} {
pt\i -- l\i,
pt\i -- l\j,
};

Q/$P^1 \times P^1$ [gray];

\foreach \i [evaluate=\i using int(2*\i)] in {1,2,...,7} {
l\i -- [gray, edge node = {node [fill=white] {h}}] Q,
};

pt1 -- [gray] Q;
};
\end{document}


Note the \tikz line. It has the option no crossing minimization, which selects the new algorithm. If we omit that option, then the default sweep crossing algorithm will be selected (because it is marked as the default algorithm in TikZ libraries).

To sum up, all the files required in this new solution are test.tex (main document), more-crossing-algorithms.lua and noCrossing.lua. Standard TikZ libraries are not replaced, but extended.

• How hard would it be to change the name of the function from CrossingMinimizationGasnerKNV1993 to something less deceptive like CrossingMinimizationNone? – Charles Staats May 23 '14 at 21:16
• (I tried to award you the bounty and start a new one for 450, but it won't let me award the bounty for another hour.) – Charles Staats May 23 '14 at 21:18
• @CharlesStaats Good idea. I changed the name as you suggested. – JLDiaz May 23 '14 at 21:42
• Great! It would be cool if you can put everything on github or some other down-loadable place? – Dilawar Jul 16 '17 at 6:05

I think the solution here might be to use the no placement option and place the nodes manually. It sounds like a real pain but it turns out it is surprisingly little work given the use of \foreach.

NB the positioning of the nodes may actually be wrong for the OP's requirements, but it is simple to change using the x an y keys.

\documentclass[tikz,convert,margin=10pt]{standalone}
\usetikzlibrary{graphs,graphdrawing}
\begin{document}
\tikz[rounded corners] \graph [no placement]
{

\foreach \i in {1, 2, ..., 16} {
pt\i/$P^0_{\i}$ [x=\i, y=0],
};

\foreach \i in {1, 2, ..., 17} {
l\i/$P^1_{\i}$ [x=\i-1, y=-1],
};
\foreach \i [evaluate=\i as \j using int(\i+1)] in {1,2,...,16} {
pt\i -- l\i,
pt\i -- l\j,
};

Q/$P^1 \times P^1$ [gray, x=4,y=-3];

\foreach \i [evaluate=\i using int(2*\i)] in {1,2,...,7} {
l\i -- [gray, edge node = {node [fill=white] {h}}] Q,
};

pt1 -- [gray] Q;
};
\end{document}


• A nice thought, but I need edge rerouting (see the edge pt1 -- Q). Also, I think an answer to the question is potentially useful beyond the scope of my particular application. – Charles Staats Apr 26 '14 at 14:18