New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support for multiple edges with same from/to vertex? #8

Open
runeksvendsen opened this Issue Jan 3, 2019 · 4 comments

Comments

Projects
None yet
2 participants
@runeksvendsen

runeksvendsen commented Jan 3, 2019

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

This comment has been minimized.

Owner

andrewthad commented Jan 3, 2019

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

This comment has been minimized.

runeksvendsen commented Jan 4, 2019

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

This comment has been minimized.

runeksvendsen commented Jan 15, 2019

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

This comment has been minimized.

Owner

andrewthad commented Jan 15, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment