Understanding nx-loopback graph conversion

[dschult]

I'm having trouble figuring out how the nx-loopback backend converts the graph during testing.

It appears that the order of the nodes and edges change between running a doctest with vs without the nx-loopback backend. So I went looking for where/how the nx-loopback backend converts the graph during testing. I could not find any dispatcher object for the nx-loopback backend. I also looked for any code that tested for loopback to see if there is a hardcoded conversion/copying of the graph. And while I found a place where copy(graph) is used, it doesn't seem to be relevant to this test -- and I looked at copy(graph) manually and it doesn't cause the change in order I see when using nx-loopback.

The case I have been working with/testing is in a doctest, in case that matters.

I put the following in an example in a docstring (inside dag.py in my case):

>>> G = nx.DiGraph([(1, 2), (0, 4), (3, 1), (2, 4), (0, 5), (4, 5), (1, 5)])
>>> for node in G.nodes:
>>>     print(f"{node}: {G.pred[node]}")

Running pytest --doctest-modules --pyargs networkx/algorithms/dag.py produces:

    1: {3: {}}
    2: {1: {}}
    0: {}
    4: {0: {}, 2: {}}
    3: {}
    5: {0: {}, 4: {}, 1: {}}

Running NETWORKX_TEST_BACKEND=nx-loopback pytest --doctest-modules --pyargs networkx/algorithms/dag.py produces:

    1: {3: {}}
    2: {1: {}}
    0: {}
    4: {2: {}, 0: {}}
    3: {}
    5: {1: {}, 0: {}, 4: {}}

The order of the nodes in the G.pred dict change.

So, what is actually happening to G when the nx-loopback backend is used? Thanks!

[eriknw]

I just saw this issue.

The loopback graph classes use the dispatching metadata that indicate what data is used. For example, if only "weight" edge attribute is used, then only it will be copied. See convert_from_nx here:
https://github.com/networkx/networkx/blob/main/networkx/classes/tests/dispatch_interface.py

This file should probably be moved, as it's pretty hard to find.

Note that there is an "ignore" list at the top of this function that skips the usual conversion for a handful of functions. For example, dfs_labeled_edges is skipped due to sensitive tests. If there are other sensitive tests and there is no other reasonable workaround, I think it's okay to add more functions to the "ignore" list.

[Schefflera-Arboricola]

for reference #7398 (comment)

[dschult]

Thanks @eriknw
I found the dispatch_interface.py module yesterday -- and I agree it should probably be moved. Maybe to utils/tests.

This might be a case we want to add to the ignore list -- thanks for that too.

Also, it looks like G.add_edges_from is the main tool tool for copying the edges, so I'm tracking down why that might change the order of the edges from one graph to its copy. There might be a fix there somewhere.

@Schefflera-Arboricola I think if we use the min/max functions we would need to use the sorted route. But it seems to me that if we just take the raw adj/edge data, the order should be unchanged even across all operating systems. The trick lies in the strange and sometimes-hard-to-predict way that the adjacency data structure reports the edge order. We have to preserve the adjacency dict ordering to preserve the edge reporting order. Python keeps dict-order fixed across OSs now, so it "should" work if we are careful about adjacencies when we copy. But my intuition could be wrong too. :)

[dschult]

This is a question about backend conversions -- so not directly related to nx-loopback, but I'm hoping it is causing errors for nx-loopback so I can solve them. :)

This refers to the code in _convert_and_call_for_tests.

@eriknw For functions that mutate an incoming graph, the _convert_and_call_for_tests code "binds" the args twice -- once with the result of the conversion to the backend graph type (G1) and once with just the original input networkx graph (G2). It then replaces the data-guts (like ._adj or .graph) of G2 with data from G1. I am guessing that the intent is to have the original input networkx graph (which is G2) be mutated based on the results of the mutations that were applied to the converted graph G1.

But assumptions are made about G1 that may depend on the backend graph type storage. For example, G1 should have attributes _adj or edges or graph depending on the mutations that are made. Do we require that backend graph data storage have these attributes or am I missing a conversion step?

We need to be very careful when replacing data-guts of a networkx graph with those of another -- there are dependencies between e.g. _adj and _pred which are subtle. I am hoping that I can find some subtle changes to make to allow the loopback conversion to maintain adj and edges order. I've got something that seems to work, but I want to make sure I don't mess up the logic of the handling of input graph mutation.

Thanks!

[eriknw]

Thanks for taking a close look and asking good questions. G1 here is not a backend graph--it is a networkx graph having been converted via convert_to_nx--so we can safely assume it has attributes like _adj. The graph that G1 is converted from is the backend graph that was the input to the function, so this is able to test that the function correctly mutates the input (backend) graph.

Much of the code here is pragmatic and often regarded as technical debt. Typically, a good way to see why code like this exists is to delete some of it and see what tests break. It's very possible we should be more careful when updating the original graph attributes (such as _pred), but doing so has not been necessary to pass tests.

[dschult]

OK... Thanks for that clarification -- and that correction pointing out that G1 is actually a networkx graph arising by converting the backend graph used by the backend back to nx. This helped me understand what is going on better.

I still have a question though:

• Why do we split the input graph into two? IIUC, one gets converted to the backend type which then gets input to the backend function. The other gets updated with the mutated data obtained by converting the mutated backend graph back to nx and then copying data to the second version of the input graph. Why not just update the input networkx graph that was converted? Is there another feature I am missing of having two pointers to the input?
  [Edit: This is for testing only. The approach is to create two versions of the input graph when the function mutates the graph. Then call the networkx function on G1 and the backend function on a converted version. Then copy the mutations to G2, and compare G1 and G2. That's why we need two copies of the graph.]

Tracking down the nx-loopback issues along with tracking through this conversion path helped me find two errors when copying the guts of G1 into G2.

• For directed graphs, re-assigning to G2._adj will also require reassigning to G2._pred so that the two dict-structures point to the same datadict objects. (Each edge has one datadict, which is pointed to by both _adj and _pred.)
• The cached_properties edges, degree, in_edges, etc need to be reset when _adj is reassigned to. Current code automatically resets adj when _adj is written to. But not other cached_properties like edges. Despite misgivings, I think we should change the descriptor code-magic to reset edges and friends when _adj is assigned to. And it would be really cool to reset _pred when _adj is set, but I don't think that can be automated easily. We should probably leave that up to the user and help them know enough to update _pred appropriately. They are playing with private data attributes after all. But it's really easy to assign to _adj, test it with Graph and assume it will work for DiGraph. Maybe a "hacker's tips" section of the docs could explain the subtleties.

I will update #7432 to make nx-loopback maintain edge order. Not sure yet whether changes to the cached property resetting will be in that PR or another. [Edit: I put the changes to fix the cached properties too.]

Thanks!