Hi everyone, I’m currently working on a dependency solver and will need the use a graph for the error reporting algorithm (when the solver failed to find compatible versions). I’m not very familiar with all the graph packages out there and there seems be at least 3 packages (elm-community, janiczek and drathier). So I’m asking here if some of you familiar with them could advise me. My use case is the following.

If solving fails, I may end up with the following derivation tree.

```
root: 1.0.0 <- derived from:
root: 1.0.0, foo: Not ( 1.0.0 <= v < 2.0.0 )
root: 1.0.0, foo: any <- derived from:
root: 1.0.0, baz: Not ( 1.0.0 <= v < 2.0.0 )
foo: any, baz: Not ( 3.0.0 <= v < 4.0.0 ) <- derived from:
bar: any, baz: Not ( 3.0.0 <= v < 4.0.0 )
foo: any, bar: Not ( 2.0.0 <= v < 3.0.0 )
```

Which corresponds to the following derivation graph.

```
┌─────────────────────────┐ ┌─────────────────────────┐
│{foo any, not bar ^2.0.0}│ │{bar any, not baz ^3.0.0}│
└────────────┬────────────┘ └────────────┬────────────┘
│ ┌─────────────────────┘
▼ ▼
┌────────────┴──────┴─────┐ ┌────────────────────────────┐
│{foo any, not baz ^3.0.0}│ │{root 1.0.0, not baz ^1.0.0}│
└────────────┬────────────┘ └─────────────┬──────────────┘
│ ┌───────────────────────┘
▼ ▼
┌──────────┴────┴─────┐ ┌────────────────────────────┐
│{foo any, root 1.0.0}│ │{root 1.0.0, not foo ^1.0.0}│
└──────────┬──────────┘ └─────────────┬──────────────┘
│ ┌────────────────────────┘
▼ ▼
┌─────┴───┴──┐
│{root 1.0.0}│
└────────────┘
```

But in more complex cases, this is in general a directed acyclic binary graph such as the following one.

```
┌───┐ ┌───┐
│ │ │ │
└─┬─┘ └─┬─┘
└▶┐ ┌◀┘
┌───┐ ┌┴─┴┐ ┌───┐
│ │ │ │ │ │
└─┬─┘ └┬─┬┘ └─┬─┘
└▶┐ ┌◀┘ └▶┐ ┌◀┘
┌┴─┴┐ ┌┴─┴┐
│ │ │ │
└─┬─┘ └─┬─┘
└─▶┐ ┌◀─┘
┌┴─┴┐
│ │
└───┘
```

So the first thing I’ll need is to be able to create the graph from a tree-like type similar to:

```
type Incompatibility
= External
| Derived Incompatibility Incompatibility
```

Then I’ll need to be able to count outgoing edges for each node, and modify the node accordingly. Finally, I’ll need to traverse the graph, in a depth first manner from the “root” and accumulate a list of Strings while doing it. Advanced control on the traversal would be great.

I think that’s all. Any advise on the best fitting graph package for this?

PS: for the curious, or if more details are needed, the algorithm I’m porting to Elm is called PubGrub (https://github.com/dart-lang/pub/blob/master/doc/solver.md).