Labelled acyclic graph and optimum path algorithm + Additional changes

[adithyaov]

This is a draft implementation of labeled acyclic graph required if one wants to make algorithms on acyclic graphs. There is still a lot of work to be done including writing tests.

[Avasil]

There is still a lot of work to be done including writing tests.

If you'd like to split some of it, I would be happy to lend a hand!

[adithyaov]

@Avasil Of Course :-). Some tasks that I find incomplete are written as TODO's in AdjacencyMap.hs. We need to write tests for the module as well. Please ignore the TODO that says Improve the Show instance. It's too complex to achieve in a short amount of time. That should probably be done in another PR later. Please let me know which TODO's you would like to work on. The TODO's are the tasks that I've noticed to be incomplete which might be an incomplete list in itself. If you find something else missing please feel free to add another TODO.

[Avasil]

Awesome! Should I add things to your PR or wait after it's merged?

I will have a limited access to the internet for a couple of days (Saturday - Wednesday) so I was thinking about waiting until I come back

[adithyaov]

Should I add things to your PR or wait after it's merged?

Without adding the function consistent and tests, the PR probably should not be merged.

I will have a limited access to the internet for a couple of days (Saturday - Wednesday) so I was thinking about waiting until I come back.

Ah, I see. In that case, for the time being, I'll add the consistent function and the tests and hopefully that is sufficient for the PR to be merged. You can continue working on the rest of the TODO's or add your own once you come back.

[adithyaov]

@jitwit I agree, this is not completely Dijkstra. But for an acyclic graph one does not need to maintain a set of nodes. One can directly relax the edges in the topological order. I think one can consider this as a simplification of Dijkstra for acyclic graphs.

In CLSR I think they name it dag-shortest-paths for what it's worth!

Ah yes, I think I'll rename it to shortestPath or dagShortestPath. Thank you for the feedback.

EDIT:

@jitwit The following describes a minor issue. This is equivalent to the shortest path if the edges are distances, If the edges are capacities then this is equivalent to finding the max capacity and hence I feel giving the name shortestPath is not semantically correct. If possible could you please suggest some generic name?

[snowleopard]

@jitwit The following describes a minor issue. This is equivalent to the shortest path if the edges are distances, If the edges are capacities then this is equivalent to finding the max capacity and hence I feel giving the name shortestPath is not semantically correct. If possible could you please suggest some generic name?

Indeed! In fact, we could probably use the same algorithm for finding the longest path too, which would be even more confusing :)

Perhaps, we could call it optimumPath? I would then match the Optimum data type:

https://hackage.haskell.org/package/algebraic-graphs-0.4/docs/Algebra-Graph-Label.html#t:Optimum

We could also look at how such generic path-finding algorithms are called in the literature.

[jitwit]

It looks like in the Mohri paper Generic-Topological-Single-Source-Shortest-Distance is used, which is a mouthful. In response to @adithyaov's question about Capacity giving maximum, I guess Mohri slapped generic on the front to indicate both shortest and distance should be understood abstractly!

Huang paper attributes shortest paths from topological sorting to Viterbi (1967) and calls the algorithm Viterbi, though in a footnote he mentions it's sometimes also credited to Lawler (1976).

Huang: https://www.aclweb.org/anthology/C08-5001 Mohri: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.367.5897&rep=rep1&type=pdf

[snowleopard]

@jitwit Thanks for the pointers! I haven't come across the name "Viterbi algorithm" from Huang's paper. For me, this name is usually associated with this famous algorithm:

https://en.wikipedia.org/wiki/Viterbi_algorithm

From these options, I'm still in favour of optimumPath.

[jitwit]

@snowleopard Yeah, I find Viterbi confusing since it makes me think the semiring is specialized! Also, dag is kind of in the module name, so it's probably unnecessary to include that in the function name.

optimumPath is concise and descriptive. Maybe it should be plural since a Map a e is produced?

[snowleopard]

Maybe it should be plural since a Map a e is produced?

@jitwit I'd stick with the singular name because the source vertex is fixed. I've seen both singular and plural used in the literature, but I generally prefer using singular names in library APIs.

[snowleopard]

@adithyaov A general comment: it looks to me that there is a more general function that can be factored out of your implementation. Something fold-like, but for an acyclic graph, where you start with an initial state s and then traverse the graph in the topological order, at each step modifying the state with a function like s -> a -> [a] -> s, where a is the current vertex and [a] is the list of its predecessors. In case of optimumPath your state s is the resulting map Maybe (Map a e) which switches from Nothing to an initial map as soon as you encounter the source path vertex.

[adithyaov]

@adithyaov A general comment: it looks to me that there is a more general function that can be factored out of your implementation. Something fold-like, but for an acyclic graph, where you start with an initial state s and then traverse the graph in the topological order, at each step modifying the state with a function like s -> a -> [a] -> s, where a is the current vertex and [a] is the list of its predecessors. In case of optimumPath your state s is the resulting map Maybe (Map a e) which switches from Nothing to an initial map as soon as you encounter the source path vertex.

Ah, I see. Having such a function in the library would be useful. I guess, I'll create something like this and implement optimumPath on top of that. I'll create it in Acyclic.Labelled.AdjacencyMap for now.

[snowleopard]

I'll create it in Acyclic.Labelled.AdjacencyMap for now.

I think it should go into Algebra.Graph.Acyclic.Labelled.AdjacencyMap.Algorithm. Oh, the module names are getting ridiculously long, we need to do something with this.

[snowleopard]

@adithyaov Looking at the current implementation of optimumPath via fold, the latter doesn't look very convenient. Perhaps, we should switch to the following type signature?

fold :: (Ord a) => (e -> a -> a -> s -> s) -> s -> AdjacencyMap e a -> s

Instead of folding a graph vertex-by-vertex, we go edge-by-edge (the e -> a -> a part) in the topological order. With this change, I think optimumPath will look much more natural. Could you try it?

I've also switched to ... -> s -> s hopefully making the step function easier to apply to the state.

[snowleopard]

I've added some more comments.

@adithyaov There are a few TODOs in the code: do you plan to address any of them in this PR?

[snowleopard]

Also, the CI fails with a compile error.

[adithyaov]

@snowleopard I plan to address most of the TODOs before the merge. I apologize for the delay. Will address the CI fail as soon as possible.

[snowleopard]

@adithyaov Thanks, and don't worry about the delay.

[adithyaov]

@snowleopard That is an interesting failure. I think it's because I changed the arbitrary instance.

Edit: Ah I see, It was because of how comm was defined. In the tests gmap was defined in terms of toAcyclicOrd. I think one could replace it shrink though.

[adithyaov]

Please don't review this PR yet, I'll include a small writeup with all the major changes in this PR. This would make reviewing easier. I'll probably squash a few commits as well.