Followup ideas from the `_dispatch` code audit

[dschult]

PR #6688 required going through a lot of our code base and finding out which input arguments were treated how. In that PR, many comments were created and attached to various parts of our codebase. This Issue attempts to collect the comments that didn't lead to an immediate solution or answer. The idea is to check them off when we either resolve them or decide not to resolve them. If I've missed something please add it in the comments and I'll try to put it on the list via editing.

Timing impact

• [x] timing of functions when not dispatched Full test suite for networkx: (very crude test using pytest time reporting)
  • without dispatch decorators (before PR #6688): 48.14s
  • with dispatch decorators: 48.83s
  • in nx-loopback test mode without dispatch decorators (should take longer due to converting graphs): 56.37s
  • in nx-loopback test mode without dispatch decorators (should take longer due to converting graphs): 154.24s Time a function call that takes very little time: G=nx.path_graph(5); %timeit nx.shortest_path(0,3)
  • without dispatch decorators: 2.67 µs
  • with dispatch decorators: 3.3 µs Increase number of nodes: G=nx.path_graph(50);%timeit nx.shortest_path(G, 0, 47)
  • without dispatch decorators: 21.9 µs
  • with dispatch decorators: 22.3 µs
• [x] timing of import of networkx:
  Change to new git branch, then python -X importtime -c "import networkx"
  • without dispatch decorators: ~70 +/-2 ms (200+/-4 ms for first invocation after switching branches)
  • with dispatch decorators: ~72 +/-2 ms (204+/-4 ms for first invocation after switching branches)

API warts:

• [ ] algorithms/tree/operations.py::join accepts a list of 2-tuples with (graph, root) pairs
• [ ] convert.py::to_dict_of_dicts has argument edge_data which is a value
• [ ] algorithms/approximation/treewidth.py::min_fill_in_heuristic has input graph which is expected to be a dict.
• [ ] algorithms/shortest_paths/astar.py::astar_path
• [ ] allowing graph_name to be specified in LoopbackDispatcher.convert_from_nx helped a lot with debugging for this PR
• [ ] Also note that LoopbackDispatcher.convert_from_nx has a list of function names for which converting the graph doesn't happen. We can add to that list if needed (escape hatch for debugging).
• [ ] _dispatch handles inputs to to_numpy_array specially for dtype argument.
• [ ] algorithms/tree/branchings.py::maximum_branching: handles "preserve_attrs" input specially for True/False. If True it preserves all the attributes -- not just the one used in the algorihm.
• [ ] we should make some functions in flow.py private; like: preflow_push_impl
• [ ] we don't convert the inner graphs when they are used as edge keys or attributes (see test_christofides_hamiltonian.)
• [ ] the current _dispatch can't specify a string as the default value of an edge_attr argument. If this becomes as issue we could use the string provided so long as it doesn't equal an argument of the function. We will do that if/when it is needed.
• [ ] attr_matrix and attr_sparse_matrix require the edge attribute must be present for all edges.
• [x] Some cases use "weight" internally for edge attribute but don't allow that name to change. Already a separate Issue: #6753 Find them with git grep -A 2 '_dispatch.*preserve_edge_attrs={"G":'
  • second_order_centrality
  • quotient_graph
  • panther_similarity
  • generate_random_paths
  • number_of_walks

Misc notes:

• it is okay for backends to raise if not all edges have "weight" attribute when @_dispatch gets edge_attrs={"weight": None}

Questions:

Q: how to handle create_using inputs when dispatching?

For the future, perhaps we should:

• have a dispatch class instead of a closure
• create a decorator to indicate whether multigraph edges can be merged with min, sum, etc.
• see whether dispatch should be included in the networkx/drawing/layout.py algorithms.

[MridulS]

Putting this here from https://github.com/networkx/networkx/pull/6688/files#issuecomment-1652314158

• [x] add preserve_all_attrs=True argument to _dispatch and convert_from_nx that is equivalent to preserve_edge_attrs=True, preserve_node_attrs=True, preserve_graph_attrs=True.

[aaronzo]

Extra point on quotient_graph - though it's a pattern that could repeat: The function takes a weight parameter (since #6814), but this is only used by the function logic if another parameter, edge_data is None. Therefore there is efficiency lost in keeping the weight attribute if edge_data != None. This also applies to the open PR #6557.