Check `not_implemented_for` usage pattern for mistakes

[dschult]

I have noticed a few places where the not_implemented_for decorator is called such that it excludes MultiDiGraph, but not MultiGraph nor DiGraph. That might be correct in some of these cases, but I suspect some/many of these functions are not supposed to be used with directed graphs nor with multigraphs.

A quick git grep 'not_implemented_for("directed", "multigraph")' shows:

networkx/algorithms/approximation/maxcut.py:@not_implemented_for("directed", "multigraph")
networkx/algorithms/approximation/maxcut.py:@not_implemented_for("directed", "multigraph")
networkx/algorithms/community/asyn_fluid.py:@not_implemented_for("directed", "multigraph")
networkx/algorithms/distance_regular.py:@not_implemented_for("directed", "multigraph")
networkx/algorithms/distance_regular.py:@not_implemented_for("directed", "multigraph")
networkx/algorithms/isomorphism/tree_isomorphism.py:@not_implemented_for("directed", "multigraph")

We should check them.

[harshal-dupare]

Hi @dschult, this seems interesting, so may I take it up? On top of that, when I was going through the repo, I found that on doing a quick search for TODO it's not very clear why the algorithm is not implemented for certain types of graphs. Eg.

https://github.com/networkx/networkx/blob/27127bc95b773c6a68c0cebc19b10bdb03f48d2c/networkx/algorithms/clique.py#L296 https://github.com/networkx/networkx/blob/27127bc95b773c6a68c0cebc19b10bdb03f48d2c/networkx/algorithms/distance_regular.py#L181 https://github.com/networkx/networkx/blob/27127bc95b773c6a68c0cebc19b10bdb03f48d2c/networkx/algorithms/approximation/dominating_set.py#L21

I was wondering if it would be helpful to have a message/text/doc or some references, telling more about why it is not implemented for certain types of graphs?

[dschult]

I believe most of the reason for not implementing something in directed graphs is a question of whether the quantity is naturally defined in the same way for directed and undirected graphs. e.g. for distance_regular the TODO comment says that there is a definition of directed strongly regular graphs. There isn't per se a reason why it has not been implemented except that no one has cared enough to go look up the definition, see if it is possible to implement in a reasonable way, and then implement it. I'm hopeful that if someone was interested in that concept that they would look into developing it and maybe it wouldn't be too hard.

As to whether it would be helpful to have a message/text/doc telling more about that choice, are you thinking that we add to the comments in the code (sounds good), or making a section of the doc_string (perhaps, especially if we either already get questions about it or if we want someone to implement it), or making a centralized collection in the docs somewhere which lists the functions and what might be possible (I'm not as pleased by this one, though I think our potential projects page would be a good central place to put changes we want to have someone work on.

Thanks for the question! :)