Add method to compute Minimum cost spanning arborescence to WeightedGraph

[NickTheFreak97]

There are various use cases of graphs where it's relevant to extract a minimum cost spanning arborescence (equivalent of minimum spanning tree for undirected weighted graphs).

For example in my case it was relevant to create a variant of the observer pattern (then turned into mediator), to avoid redundant updates: you create a dependency graph and for each component, extract a minimum cost spanning arborescence (weights are used if some routes for updates are preferred to others), then send updates down the MSA rooted in the component.

I can share some code if needed.

[davecom]

Sure, if you want to share a pull request I'll take a look. Please put it in an extension to Graph or UnweightedGraph in a separate file and tests would be ideal too. Thanks!

[NickTheFreak97]

I'm not that great at using Github and I'm not sure how to properly do that. Though I have the extension pushed in this repo on a convenience account that I use to park libraries for my main project without polluting my main.

It is already structured as an extension and in separate files. Currently it only contains the method for computing the MSA on top of SwiftGraph (and an Union-Find by rank with path compression leftover file that I plan to remove in the future because I don't need it anymore).

A possible improvement is to move part of the code from func msa(_:) to a private helper function that works under the assumption that every vertex of the graph is reachable from the specified root. This way, when only a subset of the vertices was reachable from root, the check won't be performed twice, leading to performance improvements.

EDIT: I did what I described in this last paragraph in the latest commit.