Layout algorithms

[frankliu]

I was looking up other algorithms used for layout. I am trying to figure out whether some of these algorithms would provide a ‘better’ layout for de bruijn graphs. Something that approaches the ones shown in

De Bruijn graph

I am listing some of the libraries I found in igraph and tulip, not sure if any of these would do a better job (not knowing much about their difference and their relation to the ones used in graphviz). I was wondering if someone with more experience with layout algorithms might provide some insight, and whether there are better algorithms that might be worth trying out.

igraph:

Method name	Short name	Algorithm description
layout_circle	circle , circular	Deterministic layout that places the vertices on a circle
layout_drl	drl	The Distributed Recursive Layout algorithm for large graphs
layout_fruchterman_reingold	fr	Fruchterman-Reingold force-directed algorithm
layout_fruchterman_reingold_3d	fr3d , fr_3d	Fruchterman-Reingold force-directed algorithm in three dimensions
layout_grid_fruchterman_reingold	grid_fr	Fruchterman-Reingold force-directed algorithm with grid heuristics for large graphs
layout_kamada_kawai	kk	Kamada-Kawai force-directed algorithm
layout_kamada_kawai_3d	kk3d , kk_3d	Kamada-Kawai force-directed algorithm in three dimensions
layout_lgl	large , lgl , large_graph	The Large Graph Layout algorithm for large graphs
layout_random	random	Places the vertices completely randomly
layout_random_3d	random_3d	Places the vertices completely randomly in 3D
layout_reingold_tilford	rt , tree	Reingold-Tilford tree layout, useful for (almost) tree-like graphs
layout_reingold_tilford_circular	rt_circular tree	Reingold-Tilford tree layout with a polar coordinate post-transformation, useful for (almost) tree-like graphs
layout_sphere	sphere , spherical , circular_3d	Deterministic layout that places the vertices evenly on the surface of a sphere

tulip:

Layout

Tulip allows the visualization of information, and thus, provides several layout algorithms to display information and data in a neat fashion.

• Basic :The standard functions can be found in this sub group such as the Circular display or the Random layout .
• Force Directed :These layouts will try to place nodes so that the distance in the graph (specific metric on the edges) should be the closest to the distance on the drawing. Known such algorithm are the FM^3, the GEM Frick and the Kamada Kawai.
• Hierarchical :Those representations, in accord to their name, are perfect for presenting hierarchical structures or graph showing precedence relationships. The Balloon and the Sugiyama algorithms are good examples of such layout.
• Misc :This sub group contains miscellaneous algorithms, notably the packing and overlap removal algorithms.
• Multilevel :Multilevel layout is computed by including gradually the initial nodes into a layout, thus iteratively improving the node placement. The MMM and the fast multipole layout follow these steps. The iterativity allows to gradually enhance the representation.
• Planar :These algorithms are specialized in generating aesthetic planar layouts. With minimized edge crossings, those representations offer understandable 2D visualizations.
• Tree :As indicated by the sub group name, these layouts are particularly suited to trees or hierarchical data. They can be applied to any graph because if a graph is not tree it is internally applied to a spanning tree of each of its connected components.

graphviz:

dot - “hierarchical” or layered drawings of directed graphs. This is the default tool to use if edges have directionality.

neato - "spring model’’ layouts. This is the default tool to use if the graph is not too large (about 100 nodes) and you don’t know anything else about it. Neato attempts to minimize a global energy function, which is equivalent to statistical multi-dimensional scaling.

fdp - "spring model’’ layouts similar to those of neato, but does this by reducing forces rather than working with energy.

sfdp - multiscale version of fdp for the layout of large graphs.

twopi - radial layouts, after Graham Wills 97. Nodes are placed on concentric circles depending their distance from a given root node.

circo - circular layout, after Six and Tollis 99, Kauffman and Wiese 02. This is suitable for certain diagrams of multiple cyclic structures, such as certain telecommunications networks.

[steveroush]

“Better” is in the eye of the beholder.

• Can you point to, or describe, unsatisfactory layouts?
• Do you want the layout engine to do the entire job (place nodes & edges)?
• Or will you place the nodes and the engine places the edges?

[frankliu]

With sfdp, fairly nice and symmetrical

With fdp, kind of messy

I would like the layout engine to do the entire job. If you have some suggestion to make it closer to

That would be great, I was thinking maybe with subgraphs, rather than having individual pos for every node.

[steveroush]

Circo gives this (with no tweaking):

By explicitly locating the nodes in a row/column manner, I got this:

And this (changing columns for two nodes):

Here is the input to the latter:

    digraph D {
      graph [splines=true]
     
      node [shape=rect style=rounded fixedsize=false width=""]

      n001 [label="001" row=3 col=3]
      n011 [label="011" row=3 col=7]
      n000 [label="000" row=5 col=3]
      n101 [label="101" row=5 col=4]
      n010 [label="010" row=5 col=6]
      n111 [label="111" row=5 col=7]
      n100 [label="100" row=7 col=3]
      n110 [label="110" row=7 col=7]

      n001 -> n011
      n001 -> n010
      n011 -> n110
      n011 -> n111
      n000 -> n000
      n000 -> n001
      n101 -> n011
      n101 -> n010
      n010 -> n101
      n010 -> n100
      n111 -> n111
      n111 -> n110
      n100 -> n001
      n100 -> n000
      n110 -> n100
      n110 -> n101
    }

I ran the input thru dot -Tdot to get the nodes sized, then thru a gvpr program to relocate the nodes into row/column placement, then neato -n to get the output.
F=DeBruijn;dot -Tdot $F.gv |gvpr -c -f rowcol3.gvpr |neato -n -Tpng >$F.png
But, I had to determine the basic node placement (what node goes in what cell)
If there is an algorithm that would determine basic node placement, then the rest is straight forward, otherwise circo or sfdp require the least work.

[frankliu]

@steverous thanks for the tremendous effort into answering my question. Yes, I think your row and col does a great job. I tried circo but it didn’t get the nice symmetrical result you posted, probably has to do with the order that I entered the edges.

Also thanks for showing me your pipeline, I haven’t seen a gvpr pipeline before so it is certainly instructive for me. I thought the same could be done with the pos=“x,y!” attribute, but I think that is a little more restrictive because one has to figure out the correct scaling, is this why you chose to use the row col gvpr method instead?

[steveroush]

My circo input was the same I posted w/ row/col attributes - circo does not recognize my added attributes, so it ignores them.
Yes, pos=“x,y!” (or pin=true) would also work. I came up with the generalized row/col scheme earlier this year to investigate how to create more stylized layouts. Check-out https://graphviz.discourse.group/t/stupid-dot-tricks/31