snarl

Compute a planar layout for a weighted graph.

Motivation

There exist a plethora of utilities for computing graph layout, for example the venerable neato, the interactive Gephi, libraries like igraph and networkx, to mention just a few.

Why use Snarl

Snarl's claims to fame are:

• Handling dense input graphs.

  Most (all?) other layout programs assume that all of the edges in the input graph must play a role in the layout. If your data is dense (e.g., some matrix of objects similarities), it is up to you to first construct some sparse edges subset (e.g., using K-Nearest-Neighbors) to pass to the layout program.

  In contrast, snarl will happily perform this task for you. It will try to pick the most important edges from the dense graph, such that the result will be a "nice" planar graph used for the layout. The general problem of extracting the heaviest planar sub-graph from a dense graph is NP-hard, so snarl uses a heuristic. This heuristic tries to also take into account the 2D layout of the graph.

  You may still choose to provide snarl with a sub-graph, if for no other reason than performance. Still, the fact snarl will extract the planar sub-graph means that you need to be much less strict when constructing such an input sub-graph.

• Avoiding fold-overs.

  A disadvantage of a pure spring model is that it is blind to edge crossing. As a trivial example, a spring model does not distinguish between this layout:

     A--B
    /| /
   / |/
  C--D
  

  And this layout:

  A--B
  |\/
  |/\
  D--C
  

  In fact, it may prefer the latter as it is more compact. However, this second layout is inferior when it comes to communicating the graph to the human viewer. A technical way to evaluate this is that the nodes B and C are close together in the second layout, but are far from each other in the graph. In an ideal layout, the distance in the layout and the distance in the graph should be strongly correlated.

  A pure spring-based model will happily generate such fold-overs, depending on the (randomized) starting positions of the nodes. Even if you have a method to generate better initial positions, many existing tools (e.g., neato), do not allow you to specify these positions as input.

  Fold-overs are the main reason that dense graphs need to be pruned before being passed as input to the layout tool. However, even if you pass such tools a completely planar graph, they would still generate such fold-overs, as the only thing they optimize for is the spring energies, not edge crossings.

  In contrast, snarl will extract a planar sub-graph from the input graph, so that 2D the layout will not contain any crossing edges and fold-overs.

  You can choose whether to include the additional (crossing) edges in the spring model, and (independently) whether to display them in your final graph. For dense input graphs, you should typically just use the planar sub-graph in both these steps. If your graph is already sparse (but not fully planar), including these edges may make more sense.

• It is available as both an executable program and as a modular library.

  The program allows for simple application of the full pipeline on some data. The library allows to construct alternative pipelines, skipping steps and/or replacing them with alternative implementations.

Why not to use Snarl

First and foremost, snarl is very new and doesn't have the maturity of existing tools. (Bug reports and pull requests are welcome! :-)

Second, having snarl automatically extract a planar sub-graph from your data might not be the right thing for you. Even though snarl can utilize the additional crossing edges when it applies its spring model, this isn't really what it was designed or optimized for. If you also intend to display these edges, then snarl probably has no advantage over the existing mature tools.

Installing

To install:

cargo install snarl

Running

TODO.

Input formats

TODO.

Output formats

TODO.

Linking

TODO.

License

snarl is distributed under the GNU General Public License (Version 3.0). See the LICENSE for details.