Can stress majorization in GraphViz's neato generate 3D layouts

Question

I am looking at GraphViz's neato graph layout utility. It uses stress majorization, on which I found a paper. I can't say that I followed all the math, but it does seem formulated for laying out a graph in an arbitrarily high dimensional space. I am interested in generating node coordinates in 3D space, but I see no indication that this is supported in neato. Does neato's stress majorization generate 3D layouts?

score 2 · Answer 1 · answered Jul 14 '22 at 19:45

2

Not really, only if you provide the Z coordinate as input! See https://www.graphviz.org/faq/#Faq3D for more detail.
p.s. The VRML generator needs work.

answered Jul 14 '22 at 19:45

sroush

121
2

Thanks. Unfortunately, coming up with coordinates isn't trivial. It is much of the purpose of stress majorization (and Kamada-Kawai layout) to find coordinates that respect the node distances (i.e., the input data) as closely as possible. So the z-coordinate cannot be determined separately from z and y coordinates. I tried `neato -Gdim=3 Input.dot >| Output.dog` as described on the paragraph that you linked, but the output is still only 2D. – user2153235 Jul 14 '22 at 21:34
The paragraph also says that one can get higher dimension output if neato is invoked as a library, but there isn't much detail about what API it is referring to. The same page links to a [Graphviz library manual](https://www.graphviz.org/pdf/libguide.pdf), but it can't be read by Firefox, PhantomPDF, or `ps2pdf`. Googling `invoke-neato-as-a-library` yields "Using Graphviz as a Library (cgraph version)" with the same URL above, but somehow I managed to download it once (but failed in successive attempts). It looks like a C interface, and Googling `what-is-cgraph` seems to corroborate this. – user2153235 Jul 14 '22 at 21:59
Unfortunately, the actual [PDF download](https://www.graphviz.org/pdf/cgraph.pdf) for `cgraph` can't be opened either. The `cgraph` search also turned up manpage webpages, again indicating a C API. From web searching, my impression is that there are many APIs to many languages at various levels (scripting and compiled); it is unclear which interfaces provide the access that supports 3D graph layout. – user2153235 Jul 14 '22 at 22:10
Apart from finding the right API, getting 3D coordinates also requires that the stress majorization implementation supports 3D. The use of `-Gdim=3` from the command line doesn't provide indication of this, so satisfaction of the two requirements in the preceding sentence are unknowns. – user2153235 Jul 14 '22 at 22:15
Today, I am able to download *and* open the PDFs cited above. Again, it looks like a C interface, so not much more information than yesterday. It seems that accessing the 3D generation capability of the stress majorization implementation (if it exists) requires (i) that one is using an API and (ii) determining whether the API supports 3D generation, using what documentation is available for the API and some experimentation. – user2153235 Jul 15 '22 at 17:08
Still doubtful, but 1) ask here https://forum.graphviz.org/ and 2) find documentation here: https://www.graphviz.org/documentation/#users-guides – sroush Jul 15 '22 at 18:19
I believe that the body of documentation that you cited is the same as those which I cite in my link. I will try the GraphViz forum. Thanks! **Afternote:** Posted [here](https://forum.graphviz.org/t/can-stress-majorization-in-graphvizs-neato-generate-3d-layouts/1254) – user2153235 Jul 15 '22 at 18:57

user2153235 · Accepted Answer · 2022-07-20T23:30:56.647

According to the GraphViz forum answer, neato can be supplied with command line option -Gdimen=3 to generate nodes with 3D coordinates. I confirmed this in Bash:

# Extract 3D node coordinates from the laying out of test distances
neato -Gdimen=3 <<EndInputDistances | grep '\bpos=".*",$'
   graph G {
         node [label="" xlabel="\N" shape=point]; //optional
      A -- B [len=0.235775]
      A -- C [len=0.652547]
      A -- D [len=0.55973]
      A -- E [len=0.818456]
      A -- F [len=1.15465]
      A -- G [len=0.854722]
      A -- H [len=5.5227]
      A -- I [len=1.34589]
      A -- J [len=3.54823]
      A -- K [len=3.76446]
      B -- C [len=0.705402]
      B -- D [len=0.612585]
      B -- E [len=0.871248]
      B -- F [len=0.92202]
      B -- G [len=0.619055]
      B -- H [len=5.30155]
      B -- I [len=1.1126]
      B -- J [len=3.32248]
      B -- K [len=3.53941]
      C -- D [len=0.093438]
      C -- E [len=1.04822]
      C -- F [len=1.12001]
      C -- G [len=1.15562]
      C -- H [len=5.55643]
      C -- I [len=1.2144]
      C -- J [len=3.83315]
      C -- K [len=4.04868]
      D -- E [len=0.955712]
      D -- F [len=1.03057]
      D -- G [len=1.06578]
      D -- H [len=5.46601]
      D -- I [len=1.12436]
      D -- J [len=3.74375]
      D -- K [len=3.95929]
      E -- F [len=1.52546]
      E -- G [len=1.30344]
      E -- H [len=5.66555]
      E -- I [len=1.71811]
      E -- J [len=4.07063]
      E -- K [len=4.21716]
      F -- G [len=0.247014]
      F -- H [len=5.4171]
      F -- I [len=0.400343]
      F -- J [len=3.00052]
      F -- K [len=3.10713]
      G -- H [len=5.42413]
      G -- I [len=0.649788]
      G -- J [len=2.96942]
      G -- K [len=3.07688]
      H -- I [len=5.49541]
      H -- J [len=5.97982]
      H -- K [len=6.09039]
      I -- J [len=3.33034]
      I -- K [len=3.43739]
      J -- K [len=0.671053]
   }
EndInputDistances

# The above generates these 3D coordinates:
 pos="65.646,358.56,-27.811",
 pos="80.526,353.04,-21.496",
 pos="72.666,403.22,-15.719",
 pos="74.3,396.72,-16.502",
 pos="34.696,353.3,20.593",
 pos="139.7,356.2,-14.918",
 pos="125.7,344.67,-14.841",
 pos="12.8,1.8,-131.09",
 pos="154.5,379.75,-23.846",
 pos="253.25,259.03,137.45",
 pos="274,226.91,108.17",

The z-positions average to 0, within a tolerance of $10^{-3}$.

Can stress majorization in GraphViz's neato generate 3D layouts

2 Answers2