Propose an abstraction for the Dijkstra algorithm

[adithyaov]

NonNegative does not have a semiring instance, so it's unclear how you are going to compose two non-negative labels in sequence and in parallel. Ideally we should be able to use the Dijkstra algorithm to solve many problems just by picking different semirings like Distance or Capacity.

To figure out exact requirements for these semirings I suggest you watch my "Labelled Algebraic Graphs" talk at Haskell eXchange and also read this paper: http://stedolan.net/research/semirings.pdf. If the answers are not there, perhaps it's worth doing some research for the right algebraic structure.

Originally posted by @snowleopard in https://github.com/snowleopard/alga/issues/184#issuecomment-480602457

[adithyaov]

Ideally we should be able to use the Dijkstra algorithm to solve many problems just by picking different semirings like Distance or Capacity.

Although Dijkstra is used for shortest path, semantically it can be used for the max capacity path as well. For the former, the comparison operator <= is required and >= for the latter. How do you suggest implementing this?

One way is to create another type class that would have the required, including the comparison operator? On top of that, The semiring would have to satisfy the property mentioned in #184

Please look at the following for reference, Dijkstra.hs Functions like minValuedElemKey and mapUnionMin should be abstracted out. Note: minValuedElemKey should be replaced by heap operations instead for efficiency

Such abstraction can be used for other algorithms as well. If this kind of abstraction seems like overkill, a simpler solution is to always consider the Distance semiring.

[adithyaov]

Wouldn't it make sense to abstract the comparison mechanism out of all the algorithms? Most of the algorithms semantically work for both, the min of something and the max. Hence, abstracting the comparison seems like a good design.

Also, does anyone think we can use the GHC backpack? Backpack provides better abstraction.

[adithyaov]

Wouldn't it make sense to abstract the comparison mechanism out of all the algorithms?

We are doing this by using the properties of semirings. The comparison can be decided, based on the + operator.

Please refer to Semiring frameworks and algorithms for shortest-distance problems by Mehryar Mohri which provides a simple understanding of generic algorithms on semirings.

Also, does anyone think we can use the GHC backpack? Backpack provides better abstraction.

I don't think we need to look into backpack yet. The above document provides a clean solution.