Right now, this only applies to when networkx graphs would be converted to backend graphs before running the networkx algorithm, so it would be accurate to call it should_convert_and_run, ...

I don't think we should restrict it to cases where a conversion would be done. I think we should allow backend developers the freedom to communicate that they may be too slow, buggy, experimental, etc. for specific operations/corner cases even if the graph is already converted. Of course, the backend should also be able to see if a conversion would be required or not and use that to influence its decision too. The "reason" string is crucial here for a good UX (and I think it should be required).

clarification: if backend= is specified, then should_run() will be ignored since backend= overrides everything.

@eriknw and I met offline and discussed that this PR could be merged with the policy in place to only consider should_run() if a conversion was required, but a future update could allow should_run() to be used in other situations that a backend may know of that results in sub-optimal performance or behavior even if the graph is converted.

Merging it now will allow should_run() to be used today for at least a subset of use cases (which could possibly be the majority of use cases), then expanded later to be used for more cases.

Thanks @dschult!

I think this is good to go in. It shouldn't hurt anything, and it gives backends a chance to improve UX (if they return False for should_run, then this should presumably be better for the user even if this is opaque).

IIRC, we'll want to do more with this in the future (such as using the returned string in logging, warning, or introspection), and we said this PR isn't a "must have" for 3.3, but I think it's still "nice to have". @rlratzel am I missing anything?

If nothing else, it's good to get this in so it's easier for me to refactor the dispatching code :)