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

Question

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.

Answer 1

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 result

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}

The remaining files in the document folder

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

-- Load declarations from:
require "pgf.gd.layered"

-- Load algorithms from:
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 = [["
       For more details, please see 
       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
\usegdlibrary{more-crossing-algorithms}% <-- but extend it, loading more algorithms

\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.

Answer 2

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}