Add a Protocol for Backend/Dispatcher interfaces

[aaronzo]

When creating a new backend, it's not clear at all what methods should be on the interface (things like can_run, conversions, etc.). These features are also being rapidly added - to create a fully featured and futureproof backend, a developer should be developing against networkx:main branch rather than a release since things are changing. This adds another layer of difficulty.

I know networkx doesn't use typing, but I think a typing.Protocol would go a long way here in helping developers, even without documentation. The great thing about protocols is that you can implement them without explicitly extending them, so it's down to each backend developer whether they choose to explicitly extend this class, check in a unit test whether they conform, or ignore it altogether. On the other hand it would give developers confidence that their work in a different repo somewhere is compatible with networkx. The protocol could have handy docstrings outlining each function. It would remove the need to have to check where exactly each hasattr in networkx.utils.backend is called and how it is used.

The methods in the protocol could even be typehinted. Making an exception to networkx's code style for this doesn't seem too awful given this is all happening at a metaprogramming level far away from the actual graph analytics code. Being stricter on what is prescribed from backends type-wise can only be a good thing in my opinion.

[eriknw]

Sounds reasonable to me. Would you be up for making a PR with what you'd like to see? It's a lot easier for me to comment than to do it 😂. If such a protocol existed, I would update it as changes were made.

To be a netowrkx backend, the installed package must have an entry point. For networkx version >= 3.2, this is done as:

[project.entry-points."networkx.backends"]
backend_name = "package.module_path:interface"

For networkx version < 3.2, this entry point was named "networkx.plugins".

The interface object must have two functions on it:

• convert_from_nx: create a backend graph; should raise NotImplementedError if it cannot
  • The signature and functionality of this changed in version 3.2
• convert_to_nx

The optional functions are:

• on_start_tests
• can_run (added in 3.2): assume True if not defined
• should_run (coming in 3.3): assume True if not defined

The interface object should also have functions to dispatch to. These must use the dispatch name of the function.

There is another entry point that backends may define:

[project.entry-points."networkx.backend_info"]
backend_name = "package.module_path:get_info"

For networkx version < 3.2, this entry point was named "networkx.plugin_info".

The purpose of this entry point is to provide information about the backend. It can also avoid importing the backend until the backend is used. Would the protocol be able to capture entry points and the items of the get_info() dict?

It is indeed kinda messy atm for a backend to support many networkx versions. nx-cugraph supports NetworkX 3.0 and above, so it can be done (and I'm looking forward to dropping older versions!).

@Schefflera-Arboricola created a "just for fun" example backend that was used in a discussion:
https://github.com/Schefflera-Arboricola/nx-j4f
I think it could also be nice to have a well-documented "cookie cutter" backend for other backend developers to learn from.

This PR may also be of interest: #7305

[aaronzo]

@eriknw Yeah - happy to have a go at this.

I'm thinking there might be a need for a 'minimal' and a 'maximal' interface, and both might be useful.

I'm not sure on how a protocol could check entry_points, I'll need to do some research there. It's certainly not a given feature of a protocol, but there's probably some trickery to be done with metaclasses. The class would need visibility of package entry points before build time, and this is where I'm unsure.

The interface object should also have functions to dispatch to. These must use the dispatch name of the function.

This will be another tricky thing to do if we're not simply recreating a stub of the networkx API in the protocol (and I don't think we should). There may be something we could programmatically build from the registered dispatchable functions though. Question there: What package path should a backend dispatch from? E.g. if the backend has

Dispatcher.pagerank

Then will networkx automatically dispatch a call to both

nx.algorithms.pagerank
nx.pagerank

in the same way?

[eriknw]

I'm thinking there might be a need for a 'minimal' and a 'maximal' interface, and both might be useful.

Can a single one capture that some things are optional?

The "dispatch name" of a function is usually just the name of the function, but we can also set it to a different name when required. For example, we do this a lot for approximation algorithms:
https://github.com/networkx/networkx/blob/main/networkx/algorithms/approximation/distance_measures.py

The dispatch names should all be able to be part of a single, flat namespace, because the backend interface is such a namespace. Currently, the main way to know what all of these names are is to look at this dict: nx.utils.backends._registered_algorithms.

[aaronzo]

If we use a single protocol, it's questionable what isinstance or issubclass should return if a backend doesn't implement optional functions - given I would want the protocol to be a 'tool' backend devs can use to check they are maximising usability of their backend as well as to check they are conforming to the minimum requirements.

also, useful info on the namespace :)

[aaronzo]

Follow up Q (sorry, I think there will be many): is there a reason why backend_info/get_info is a separate entry point from networkx.backends, instead of a method/attribute on the interface?
E: Just reread your first response and I think the answer is to allow lazy imports. I suppose this is only achieved if like graphblas-algorithms the get_info function is kept in a separate package?

[Schefflera-Arboricola]

The dispatch names should all be able to be part of a single, flat namespace, because the backend interface is such a namespace. Currently, the main way to know what all of these names are is to look at this dict: nx.utils.backends._registered_algorithms.

I’m not sure how heavily this would impact the whole networkx backend structure, but if we would store the subpackage_name(approximation) + func_name(all_pairs_node_connectivity) in the namespace instead of just the func_name then we wouldn’t need an overridden name(i.e. name parameter), and one advantage of this would be that if someone uses the backend as an independent package and they are not aware of the overridden name of the function they are using, then they would call it in a networkx way. like: nx.approximation.all_pairs_node_connectivity(G, backend=“cugraph”)
but that will probably result in an error. What do you think... is this worth exploring @eriknw?

Thank you :)

[aaronzo]

Okay, I've made a start on this @eriknw. #7369 discussion welcome!