# Layout algorithms **URL:** \ **Category:** Help\ **Created:** [April 23, 2020, 4:20pm UTC](https://forum.graphviz.org/t/layout-algorithms/59 "2020-04-23T16:20:38Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![frankliu](https://avatars.discourse-cdn.com/v4/letter/f/bbce88/32.png) [@frankliu](https://forum.graphviz.org/u/frankliu)\ **Post date:** [April 23, 2020, 4:20pm UTC](https://forum.graphviz.org/t/layout-algorithms/59/1 "2020-04-23T16:20:38Z")
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](https://en.wikipedia.org/wiki/De_Bruijn_graph)** > > In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of m symbols S = {s1, …, sm}, the set of vertices is: > If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this ve... 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](http://www.cs.sandia.gov/~smartin/software.html) 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](http://sourceforge.net/projects/lgl/) 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. ---
**Author:** ![steveroush](https://avatars.discourse-cdn.com/v4/letter/s/a9adbd/32.png) [@steveroush](https://forum.graphviz.org/u/steveroush)\ **Post date:** [April 24, 2020, 8:08pm UTC](https://forum.graphviz.org/t/layout-algorithms/59/2 "2020-04-24T20:08:28Z")
“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? ---
**Author:** ![frankliu](https://avatars.discourse-cdn.com/v4/letter/f/bbce88/32.png) [@frankliu](https://forum.graphviz.org/u/frankliu)\ **Post date:** [April 24, 2020, 9:02pm UTC](https://forum.graphviz.org/t/layout-algorithms/59/3 "2020-04-24T21:02:17Z")
With sfdp, fairly nice and symmetrical ![de-bruijn](https://global.discourse-cdn.com/graphviz/original/1X/8ab5d8cd3d03975c1bbebf8820bf6ecc808a7333.png) With fdp, kind of messy ![de-bruijn](https://global.discourse-cdn.com/graphviz/original/1X/24372ca2fd1e191355dfbd3798da9f6a2db6dc2b.png) I would like the layout engine to do the entire job. If you have some suggestion to make it closer to ![image](https://global.discourse-cdn.com/graphviz/original/1X/446eaaf585b89c3b949a7ba213b09504217a65e1.png) That would be great, I was thinking maybe with subgraphs, rather than having individual pos for every node. ---
**Author:** ![steveroush](https://avatars.discourse-cdn.com/v4/letter/s/a9adbd/32.png) [@steveroush](https://forum.graphviz.org/u/steveroush)\ **Post date:** [April 24, 2020, 10:09pm UTC](https://forum.graphviz.org/t/layout-algorithms/59/4 "2020-04-24T22:09:24Z")
Circo gives this (with no tweaking): ![DeBruijn2.circo](https://global.discourse-cdn.com/graphviz/original/1X/6825357984e8aefec9b754dd64655b0af9fa8088.png) By explicitly locating the nodes in a row/column manner, I got this: ![DeBruijn](https://global.discourse-cdn.com/graphviz/original/1X/7f42ac26c1b3277280ed76af8f21f9062e6880d7.png) And this (changing columns for two nodes): ![DeBruijn1](https://global.discourse-cdn.com/graphviz/original/1X/b4083de5704b3f34496dfadd94f69bbf5a3caeca.png) Here is the input to the latter: ```auto 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. ---
**Author:** ![frankliu](https://avatars.discourse-cdn.com/v4/letter/f/bbce88/32.png) [@frankliu](https://forum.graphviz.org/u/frankliu)\ **Post date:** [April 24, 2020, 10:27pm UTC](https://forum.graphviz.org/t/layout-algorithms/59/5 "2020-04-24T22:27:21Z")
@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? ---
**Author:** ![steveroush](https://avatars.discourse-cdn.com/v4/letter/s/a9adbd/32.png) [@steveroush](https://forum.graphviz.org/u/steveroush)\ **Post date:** [April 25, 2020, 12:09am UTC](https://forum.graphviz.org/t/layout-algorithms/59/6 "2020-04-25T00:09:47Z")
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](https://graphviz.discourse.group/t/stupid-dot-tricks/31)