Container edges

[ferranpujolcamins]

This PR introduces a new type of edge that holds a value of an arbitrary type. I've have created UniqueElementsGraphContainerEdge, a subclass of UniqueElementsGraph to work with such edges. I also made some renaming so we don't need to specify the edge type all the time when we just want a UniqueElementsGraph with unweighted edges.

A similar class just conforming to Graph could also be implemented. So far I just implemented this for UniqueElementsGraph because is what I need, and I wanted to know your opinion before spending more time on this.

My particular use case is to model a state machine. The associated values on the edges are tuples made up by the event that triggers a transition of state and the side-effect that should be executed on the transition.

There's no performance hit in almost all test cases. Some of the search test cases seem to suffer a performance decrease of 6-7%.

[davecom]

Hi @ferranpujolcamins, Thanks for this. I think we should have a way to make SwiftGraph usable for edges containing arbitrary types. Interestingly this was the original design of WeightedEdge. Back in the 2014-2017 era of SwiftGraph (I think those are about right) WeightedEdge just required that its weights be Summable meaning they implemented the + operator (for Dijkstra's algorithm). So, a String could be a weight. Then to "simplify" things we made the weights have to be conforming to Numeric.

Now that Swift has conditional conformance, could we potentially remove the Numeric constraint on WeightedEdge's weights and implement Dijkstra using conditional conformance for WeightedGraphs where the weights are Numeric? Then instead of introducing a new type like ContainerEdge (which I support if we can't do this), we could instead just use WeightedEdge for scenarios like you suggest?

What do you think? Wouldn't this be simpler? If we can't do it though, let's merge your changes.

Best, Dave

[davecom]

Hi @ferranpujolcamins ,

I've implemented what I described above on Master (it probably should've been that way anyway). Now WeightedEdge weights can be anything that implements just Codable and Comparable. Can you now do what you want to do simply with WeightedGraph?

Best, Dave

[ZevEisenberg]

Ergonomically, I like the sound of not having a separate ContainerEdge, and just being able to use weight-sensitive algorithms on edges that have numeric associates. I'm currently using a custom graph subclass that uses an edge with an associated value that does not represent a weight/cost; it's just that edges on my graph have a little extra metadata. So if you were to make this change, I'd probably suggest changing the name of WeightedEdge to ContainerEdge, and possibly leaving WeightedEdge as a deprecated typealias for compatibility.

[ferranpujolcamins]

Hi @davecom You are right, this is not the best way to proceed. Working with extensions is best. I'm preparing a new PR that I think is better.

I appreciate the feedback.