The labelled shortest path between two nodes contains an incorrect first label

Verizon / quiver

A reasonable library for modeling multi-graphs in Scala

http://verizon.github.io/quiver/

Apache License 2.0

200 stars 39 forks source link

The labelled shortest path between two nodes contains an incorrect first label #21

Closed mgttlinger closed 7 years ago

mgttlinger commented 7 years ago

Given that the path between nodes A and B currently contains A as well as B, when we label the transitions and simply produce a Vector[(N, B)] the first or the last transition label has to be wrong given that there must be one edge less than nodes in the path.

As I see it there are a few ways to fix this:

Create a custom data type for labelled paths
Remove the start node from the path to keep the incoming edge semantic of the pairs
Add big disclaimer comment that at least states that the first edge label is wrong

timperrett commented 7 years ago

@mgttlinger so option 3 is out of the window for me, i'd rather we have a systemic fix. Option 2 seems most appealing but we'd have to audit if that would break any of our existing functionality. @kaiserpelagic can comment more on usage in Nelson. @rossabaker your input here would also be valued :-)

mgttlinger commented 7 years ago

Option 2 would still result in the odd situation where the unlabelled path contains the start node but the labelled one doesn't.

mgttlinger commented 7 years ago

Option 4: Change the Vector[(N, B)] to (Vector[N], Vector[B]) then they can have different lengths.

mgttlinger commented 7 years ago

I'd prefer option 4 personally. If that would work for your use cases I could implement that. I think that would also fix #22. And make #23 go green.

mgttlinger commented 7 years ago

Any more comments? Should I implement this?

rossabaker commented 7 years ago

Hi, @mgttlinger. Apologies for the slow reply.

What would you think of Option[(N, Vector[(N, B)])]? That would only permit N=0,B=0 or N=B+1. The constraints of that type make sense to me, but I'm not sure about the ergonomics.

I'm also planning to start work on #19. I am unsure whether this makes Quiver more or less compelling for your use case, but wanted to throw that out there.

mgttlinger commented 7 years ago

I'm fine with that type. I will fix this next week. I don't really care about the cats port as I'm stuck with scalaz 7.1 at work anyway.

rossabaker commented 7 years ago

Would you prefer one last release built on scalaz with your enhancements, or can you live with cats on the classpath since it won't conflict with your scalaz version? How important are the scalaz instances to you?

mgttlinger commented 7 years ago

I don't care about the scalaz instances. I just use the graph for pathfinding. If it isn't too much effort a scalaz release wold be nice but not mandatory. Also I'm not sure when I will get around implementing this change. The type change is done, but the search no longer finds the shortest path when the shortest path would be to not make a step at all. I'm a bit held up at work this month...