Which graph package to choose?

[mattpiz]

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).

[rupert]

Hi,

If you are looking for more advanced graph traversals, my ai-search package supports quite a few algorithms besides the most obvious depth-first one. I used it recently to write a transitive closure algorithm over a set of dependencies, for example. Suggestions for more algorithms welcome (maybe pre, in and post order would be useful). You can also control traversal order to some degree by writing a step function that presents nodes in a particular order.

If you just need depth-first, it can sometimes be simpler to write the depth first algorithm directly in terms of the problem at hand. I took that approach for the matching algorithm over tries that you can see here: https://github.com/elm-scotland/elm-tries/blob/1.0.0/src/Trie.elm#L561

What you find when doing a fold over a graph, is that since you have multiple child paths to accumulate, the expression for exploring them depends on the results of each in turn - and this makes the algorithm not tail recursive, since you must keep coming back to some node to explore further possibilities a stack frame needs to hold the context for that node. The trick is to introduce an explicit list of pending nodes to explore - called a trail.

This algorithm outline will give you something tail-recursive:

depthFirstFold : (a -> b -> b) -> b -> Tree a -> b
depthFirstFold fn accum tree = 
    depthFirstFoldInner fn accum [ tree ]

depthFirstFoldInner : (a -> b -> b) -> b -> List (Tree a) -> b
depthFirstFoldInner fn accum trail =
    -- Check the head of the trail.
    -- No head, done, just return the accum and empty trail.
    -- If there is a head, process it through fn, to get a new accum.
    -- Expand all child nodes of the head of the trail, onto the trail as the new trail.
    -- Recurse on depthFirstFoldInner.