# snarl [![Build Status](https://api.travis-ci.org/orenbenkiki/snarl.svg?branch=master)](https://travis-ci.org/orenbenkiki/snarl) [![codecov](https://codecov.io/gh/orenbenkiki/snarl/branch/master/graph/badge.svg)](https://codecov.io/gh/orenbenkiki/snarl) [![Docs](https://docs.rs/snarl/badge.svg)](https://docs.rs/crate/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](https://graphviz.org/), the interactive [Gephi](https://gephi.org/), libraries like
[igraph](https://igraph.org/) and [networkx](https://networkx.github.io/), 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](LICENSE.txt) for details.