Algorithms on graphs with edge weights, module structure and guarantee of specific properties on the edge labels.

[adithyaov]

I'm currently implementing the Dijkstra Algorithm and the natural structure the algorithm should be implemented on is the edge labeled Adjacency map. The labels are basically the edge weights.

Shouldn't all the algorithms involving edge weights use the labeled Adjacency map? I've created a directory src/Algebra/Graph/Labelled/Algorithm. Seems right to have different modules for different algorithms. The code looks structured and cleaner this way because complex algorithms might require the combination of many local elements. It does not make sense to have these local elements for different algorithms in a single module.

For example, the current Dijkstra algorithm that I have written has many local function like dijkstraStepNonEmpty, addUnreachableVertices etc. It makes sense to have all the local functions in a single module called Algebra.Graph.Labelled.Algorithm.Dijkstra. The edge weight should typically be constrained to any type which has the properties of a positive number, for simplicity it is Int in the prototype.

Also, wouldn't it be better to provide a way to make types with the properties of positive numbers and restrict functions like dijkstra to these types? The signature would then be as follows,

dijkstra :: (Ord a, PositiveNumer e) => a -> AdjacencyMap e a -> Maybe (Map a e)

Or we could use the Data.Natural module and somehow handle the Indeterminate.

[adithyaov]

Maybe I should split this into multiple issues?

[snowleopard]

@adithyaov Thanks for starting this discussion!

Shouldn't all the algorithms involving edge weights use the labeled Adjacency map?

Yes, I think this would be best. If a user would like to find shortest paths in a graph without edge labels then it's not difficult to convert it to a graph with unit edge weights.

I've created a directory src/Algebra/Graph/Labelled/Algorithm.

I think the structure should be as follows:

• Algorithms operating on the algebraic representation from Algebra.Graph.Labelled should live in the directory src/Algebra/Graph/Labelled/Algorithm.
• Algorithms operating on the adjacency map representation from Algebra.Graph.Labelled.AdjacencyMap should live in the directory src/Algebra/Graph/Labelled/AdjacencyMap/Algorithm.

Seems right to have different modules for different algorithms. The code looks structured and cleaner this way because complex algorithms might require the combination of many local elements.

Yes, placing algorithms in separate modules like Algebra.Graph.Labelled.AdjacencyMap.Algorithm.Dijkstra should be fine.

The edge weight should typically be constrained to any type which has the properties of a positive number, for simplicity it is Int in the prototype.

What do you mean by "properties of a positive number"? Can you be more specific? Can you formulate this as a subclass of one of the algebraic structures from Algebra.Graph.Label?

Maybe I should split this into multiple issues?

One issue is fine.

[adithyaov]

What do you mean by "properties of a positive number"? Can you be more specific? Can you formulate this as a subclass of one of the algebraic structures from Algebra.Graph.Label?

I believe NonNegative in Algebra.Graph.Label would work.

[snowleopard]

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.

[adithyaov]

I saw the video, I'm yet to read the mentioned paper.

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

My bad, I answered NonNegative as I had only + in mind.

Agreed, For the Dijkstra algorithm, one should be able to use both the semirings Distance and Capacity and any other semiring that follows a few properties mentioned below.

Properties of positive numbers is the wrong phrase. What I meant to say was we can only use monoids (we do not need to consider <+>) that do not break the invariant in Dijkstra.

The basic property of Dijkstra is that if a-....-c-d is the shortest part from a to d then a-...-c is the shortest path between a and c and so on. And since Dijkstra is a greedy algorithm, once we fix a distance to a vertex we do not change it. We need to consider the properties of the sequence operator <.>. Dijkstra algorithm cannot be applied if the following properties fail,

1. a <.> b eq* a
2. a <.> b eq* b

for all a and b, eq* should exclusively be >= or <=. (Hence ((-inf, inf), +) cannot be used)

let A = (-inf, 0] and B = [0, inf), Dijkstra's algorithm can work on the following monoids, (A, -) (B, +) -- Distance (B, min) -- Capacity etc.

Dijkstra follows a simple rule, if all edges have non-negative weights, adding an edge will never make the path smaller. In the same sense if we use Capacity, adding an edge will never make the capacity larger.

Exact requirements for these semirings

I think any semiring such that <.> should follow the rules mentioned above should suffice. I'll get back to this issue if I find something new. Maybe it is better to change the title of this issue as guarantee of positive properties on the edge labels is not a proper question to ask. One should rather ask about the properties of the monoid that don't break the invariant in Dijkstra.

[snowleopard]

@adithyaov I'm pretty sure in this situation we shouldn't be reinventing requirements for a semiring for the Dijkstra algorithm. Could you study some literature on this topic and/or other graph libraries? It'd feel much more comfortable picking an abstraction which has already been successfully used.

Unlike the algebra of graphs itself, pathfinding in graphs with labels from semirings is a well-studied topic.

[adithyaov]

I came across a paper, namely, Semiring frameworks and algorithms for shortest-distance problems by Mehryar Mohri which provides a simple understanding of generic algorithms on semirings.

It provides a clear solution to all the problems addressed in this issue.

[snowleopard]

@adithyaov Great, thanks for sharing!