Support for multiple edges with same from/to vertex?

[runeksvendsen]

I'm wondering whether it would be difficult to add support for multiple edges that go from and to the same vertex. Particularly, I'm interested in knowing how much work it would require to adapt the dijkstra implementation to this.

To be clear, I'm asking about support for a graph that can have two or more edges that all go from some vertex a to some other vertex b (not about support for edges where fromVertex == toVertex). I imagine edges could be deleted selectively by comparing them with their Eq instance (like fgl does: https://www.stackage.org/haddock/lts-11.13/fgl-5.6.0.0/Data-Graph-Inductive-Graph.html#v:delLEdge).

[andrewthad]

I've not considered this before. One approach to handling multiple edges would be to fake it. Something like Graph g (Bag Int) Int would give you edges labeled by a bag of Ints. The trick would be getting dijkstra's algorithm to do want you want it to. You should just be able to call mapEdges to keep the lowest weight in each edge's bag before running dijkstra's algorithm. There's no way that dijkstra's algorithm would ever use any of the higher-weight edges anyway, so I think you are safe to just discard them.

[runeksvendsen]

There's no way that dijkstra's algorithm would ever use any of the higher-weight edges anyway, so I think you are safe to just discard them.

That's a good point, actually.

Originally, I wanted to keep multiple edges with the same from/to vertex in a single graph, and delete the edges that form the shortest path (as per dijkstra), and then repeat, in order to enumerate all the shortest paths formed by all my edges (starting with the shortest and going up in length from there).

But, as you say, it makes just as much -- if not more -- sense to just keep a graph of type Graph g (MinHeap e) Int as a sort of queue, and then derive a graph from this (which has only a single edge per each from/to vertex combination) by removing the edge with the minimal edge weight from the heap for each from/to vertex.

[runeksvendsen]

I have one more question.

I would like to use the dijkstra-functions (in Data.Graph.Immutable) to find the shortest path in the form of either a list of edges or a list of vertices. But, as far as I can see, I can only use these functions to find the shortest path length between two given vertices.

Is it possible to get back a list of edges/vertices that comprise the shortest path between two vertices?

[andrewthad]

You're in luck. What you are asking for is precisely why I made the API so general. The type signature is:

dijkstra ::
     (Ord s, Monoid s, Foldable t)
  => (v -> v -> s -> e -> s) -- ^ Weight function
  -> s -- ^ Weight to assign start vertex
  -> t (Vertex g) -- ^ Start vertices
  -> Graph g e v -- ^ Graph
  -> Graph g e s

Let's say that you have these instantiations of the type variables:

• v: Word (some kind of identifier)
• e: Int (a length)
• s: ?

I picked different types for v and e so that it will be clearer what's going on with s. For s, we define a datatype:

data MeasuredPath = MeasuredPath Int [Word]
instance Ord MeasuredPath where
  compare (MeasuredPath len1 vs1) (MeasuredPath len2 vs2) = compare len1 len2 <> compare vs1 vs2
instance Semigroup MeasuredPath where
  (<>) = min
instance Monoid MeasuredPath where
  mempty = MeasuredPath maxBound []

The idea is that the semigroup/monoid instances prefer the shortest path. The Ord instance is what you would have gotten with stock deriving, but I wrote it out for clarity. Now, for the function argument:

f :: Word -> Word -> MeasuredPath -> Int -> MeasuredPath
f _src dst (MeasuredPath len vs) weight = MeasuredPath (len + weight) (dst : vs)

And that should do it. One more interesting thing is that you can use Set [Word] instead of [Word] in MeasuredPath and make the appropriate change to the Semigroup instance and then you get all the shortest paths from the start vertex to every other vertex.

[runeksvendsen]

Excellent! Now everything makes sense.

That is indeed much more general than I had anticipated. It even supports multiplying edge weights rather than summing them (which I'm also looking for).

May I suggest you add this example to the documentation? For some reason I had assumed the "weight function" was simply a way to extract an edge weight (s) from an edge (e). This example clears it all up.

[andrewthad]

Good idea, I'll add that example to the docs.

[runeksvendsen]

I've implemented the algorithm you suggested (using a MinHeap for each edge of an MGraph), and deriving a Graph with only the minimum edge from the MinHeap for each edge.

Unfortunately, the performance is pretty poor. I assume this is related to the fact that dijkstra only operates on immutable graphs. This requires me to -- for each application of dijkstra -- 1) copy the MGraph 2) reduce the MinHeap of each edge to just a single edge, and 3) run dijkstra on the resulting (immutable) Graph. Step 1) takes time proportional to O(n), where n is the number of edges in the graph, and my algorithm runs dijkstra n times as well (once for each edge in the graph -- at most), which makes the resulting algorithm O(n^2).

What's the reason that dijkstra is only defined for the immutable graph type? I assume it would be possible to implement with a mutable graph as input, but perhaps I'm missing something.