Graph algorithm interface

[maxfischer2781]

The only explicit graph algorithm neighbourhood is defined as a method for historical reasons. This allows for optimisations depending on the data structure. However, this approach has several shortcomings:

• Graphs not inheriting from .abc.Graph must re-implement every algorithm. This is especially the case for Cython extensions.
• Every algorithm must be implemented on .abc.Graph, which is a questionable choice for an ABC.
• It is not possible to add new algorithms as plugins.
• Graphs do not easily expose whether an algorithm is efficient for them.

I suggest an operator-like approach: each algorithm corresponds to one (or more) special methods. Graph implementations can provide such a method for efficient implementations. Otherwise, the algorithm uses a default implementation.

[maxfischer2781]

Current thoughts:

• Since algorithm-operators are specific to graphs, they should follow a naming convention. For example, neighbourhood should correspond to __graphi_neighbourhood__. This allows to dynamically add new algorithms without risking conflicts with the standard data model.
• Lookup should follow the operator opt-out:
  • Example for neighbourhood(graph, *args, **kwargs)
  • If graph.__graphi_neighbourhood__ is not defined, default.
  • If graph.__graphi_neighbourhood__(*args, **kwargs) returns NotImplemented, default.
  • Otherwise, return result.
• Regular operators use __operator__ = None to forbid an operation, even if it is defined on a parent class.
  • Use graph.__graphi_neighbourhood__ = None if an algorithm does not apply - e.g. an undirected algorithm on a directed graph.
  • Use graph.__graphi_neighbourhood__ = NotImplemented if an algorithm is not optimised - e.g. after changing the internal data structure.