[feature proposal] Adaptor class for a networkx graph

[winni2k]

It strikes me that an adaptor class for a tskit Tree to make it look like a networkx DiGraph would give easy access to networkx's substantial graph algorithm library (https://networkx.github.io/documentation/stable/reference/algorithms/index.html) to perform the traversals described in the tutorial and much more.

I think I could write something like that. Would there be interest in including such code in tskit?

[jeromekelleher]

Very interesting idea @winni2k! I think we would definitely be interested in that.

Is there an interchange format that networkx will understand, or do we need to import networkx? I don't want to make networkx a hard requirement (but could be an extras_require).

[winni2k]

There are several interchange formats that networkx understands including python data structures such as dicts of lists, dicts of dicts, and numpy/scipy matrices (see here). Networkx also understands several graph storage formats (see here). This approach would require making a copy of a tree to then interrogate it. We would write a conversion function that converts a Tree object to a numpy/scipy adjacency matrix that can then be fed to networkx.from_numpy_matrix. No imports of networkx necessary. Minimal code. But we would have to instruct users on how to call networkx.from_numpy_matrix. It looks like we could even export branch lengths as branch weights.

There's an alternative approach where we write a wrapper class for a Tree class that has the duck type of a networkx.DiGraph class. That would avoid copying the tree data, but would be harder to implement and keep in sync with the networkx library (more coupling). No import of networkx necessary either.

I think I'd prefer the first option because it is simpler.

Either way, I think we would need to import networkx during testing to catch when the networkx API changes.

[molpopgen]

Great idea.

[jeromekelleher]

The from_numpy_matrix option sounds perfect to me. Let's not worry the overhead about making a copy, it's unlikely we're going to be doing this for ginormous trees. So, how about we add a method to the tree class as_matrix() which will return a numpy adjacency matrix in a form that networkx understands, and give a short recipe in the docstring for how to import this into networkx?

A bit in the tutorial exploring how to do cool things with this would be icing on the cake.

[winni2k]

Great! I'll set aside some time to do this in the next few days.