haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
184 stars 54 forks source link

Shortest path algorithms assume that vertex only have one edge between them #67

Open gregnwosu opened 7 years ago

gregnwosu commented 7 years ago

In the case of vertices representing cities and edges representing roads. There are multiple edges between cities representing different route possibilities. Shortest path just gives me a list of nodes and there's no way to discover which edges are involved in the route from a list of nodes.

ivan-m commented 7 years ago

Yes, a lot of FGL was written assuming no multiple edges.

Unless you want to duplicate the function space, we can't change this until the next major version bump.

gregnwosu commented 7 years ago

Understood, I think duplicating the function space is okay until the next major version. Another function could return a list of edges (lets call it an "EdgePath"). I naively think this would be a relatively simple fix. In the next version we can make Path = [LEdge] .