8000 `MultiGraph` views return inconsistent `has_edge` results · Issue #7724 · networkx/networkx · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

MultiGraph views return inconsistent has_edge results #7724

New issue
8000

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
nelsonaloysio opened this issue Nov 18, 2024 · 4 comments · Fixed by #7729
Closed

MultiGraph views return inconsistent has_edge results #7724

nelsonaloysio opened this issue Nov 18, 2024 · 4 comments · Fixed by #7729

Comments

@nelsonaloysio
Copy link
Contributor
nelsonaloysio commented Nov 18, 2024 •
edited
Loading

Current Behavior

Filtered views of a MultiGraph, created with edge_subgraph, return inconsistent results from has_edge.

Expected Behavior

Match the same results from a Graph: either True if the edge exists in the subgraph view, or False if not.

Steps to Reproduce

In case of a MultiGraph: checking if the edge ('a', 'c') exists in the view may return either True or False.

import networkx as nx

G = nx.MultiGraph()

G.add_edges_from([("a", "b"),
                  ("a", "c"),       # <-- to be filtered out
                  ("c", "b")])

H = nx.edge_subgraph(G, [("a", "b", 0), ("c", "b", 0)])

print(f"{H.edges()}\n\n"
      f"{H.has_edge('a', 'c')} \t H.has_edge('a', 'c')\n"
      f"{('a', 'c') in H.edges()} \t ('a', 'c') in H.edges()\n\n"
      f"{'c' in H['a']} \t 'c' in H['a']\n"
      f"{'c' in list(H['a'])} \t 'c' in list(H['a'])")

# [('a', 'b'), ('b', 'c')]
#
# True      H.has_edge('a', 'c')    # <-- inconsistent result
# False     ('a', 'c') in H.edges()
#
# True      'c' in H['a']           # <-- inconsistent result
# False     'c' in list(H['a'])

In case of a Graph: checking if the edge ('a', 'c') exists in the view returns only False (as expected).

import networkx as nx

G = nx.Graph()

G.add_edges_from([("a", "b"),
                  ("a", "c"),
                  ("c", "b")])

H = nx.edge_subgraph(G, [("a", "b"), ("c", "b")])

print(f"{H.edges()}\n\n"
      f"{H.has_edge('a', 'c')} \t H.has_edge('a', 'c')\n"
      f"{('a', 'c') in H.edges()} \t ('a', 'c') in H.edges()\n\n"
      f"{'c' in H['a']} \t 'c' in H['a']\n"
      f"{'c' in list(H['a'])} \t 'c' in list(H['a'])")

# [('a', 'b'), ('b', 'c')]
#
# False     H.has_edge('a', 'c')
# False     ('a', 'c') in H.edges()
#
# False     'c' in H['a']
# False     'c' in list(H['a'])

Note that the same results follow in case of a DiGraph vs. a MultiDiGraph object.

Environment

Python version: 3.11.10
NetworkX version: 3.4.2

Additional context

I am not sure if this is a known issue or a side-effect of edge keys in multigraphs, but thought I should report it just in case.
@dschult
Copy link
Member
dschult commented Nov 18, 2024

Thanks for this Report! It is not a known/reported issue.

I can verify that this behavior is indeed a bug.
To get this strange behavior, both 'a' and 'c' must be incident to visible edges in the subgraph and there must be a hidden edge between 'a' and 'c'. The means 'c' in H['a'] passes because the nodes are in the view and G['a']['c'] exists and we don't check whether any edges between them are visible. Similarly, for H.has_edge when the edge key is not included, we don't check whether none of the edges are visible. We just check if the dict of edge-keys exists.

So, we need to 1) add a hook into those lookups to check if any visible edges are present, and 2) make sure that other strange behavior isn't also happening for other lookups.

This bug only affects edge_subgraphs of multigraphs.

A workaround is nx.edge_subgraph(G, <edges>).copy(). That workaround is actually faster than the subgraph view when you need to look up most of the edges more than once. Subgraph views save memory, not time. And the memory saved is the size of the subgraph as a graph (which is often pretty small).

nelsonaloysio added a commit to nelsonaloysio/networkx that referenced this issue Nov 21, 2024
@nelsonaloysio
Fixes networkx#7724: filtered MultiGraph views from edge_subgraph.
0ed5d34
nelsonaloysio added a commit to nelsonaloysio/networkx that referenced this issue Nov 21, 2024
@nelsonaloysio
Fixes filtered MultiGraph views from edge_subgraph (networkx#7724).
8c15bdc
nelsonaloysio added a commit to nelsonaloysio/networkx that referenced this issue Nov 21, 2024
@nelsonaloysio
Fix for filtered MultiGraph views from edge_subgraph (networkx#7724).
5fed905
@nelsonaloysio nelsonaloysio mentioned this issue Nov 21, 2024
Merged
@nelsonaloysio
Copy link
Contributor Author
nelsonaloysio commented Nov 21, 2024 •
edited
Loading

Thank you for the quick reply! I had no idea of the trade-off between memory and time on subgraph view lookups, nor the amount of memory saved by subgraph views in contrast to graphs. That's very good to know, thanks for sharing!

On the issue itself, it's interesting that this can only be observed for multigraphs. After debugging it for a bit, I found a one-liner solution (#7729) that fixes the inconsistencies in the example above, but I'm not sure it covers every possible use case.

nelsonaloysio added a commit to nelsonaloysio/networkx that referenced this issue Nov 21, 2024
@nelsonaloysio
Fix for filtered MultiGraph views from edge_subgraph (networkx#7724).
bc0d8e4
@dschult
Copy link
Member
dschult commented Nov 21, 2024

Excellent!
Thanks for hunting down this lookup in the "Inner" layer: FilterMultiInner.
That is the heart of the bug for sure -- and I wasn't sure whether a fix would be there or would need to be made in many places where this interacts with the other view/filter classes. Glad to see that the examples discovered and reported here are fixed so easily.

I'm not sure how to ensure that other strange behavior is not also occurring. That is what tests are for! :) I thought we had it covered, but clearly we didn't. Hopefully this at least gets us closer.

@nelsonaloysio
Copy link
Contributor Author

Great! It was indeed very nice to find such an easy fix - wasn't sure to expect it or not. Debugging was also a breeze, btw.

Hope this is enough to solve the issue! At least for starters, as I can't think of any more tests to include right now. :)

Schefflera-Arboricola pushed a commit that referenced this issue Nov 21, 2024
@nelsonaloysio
Fix for filtered MultiGraph views from edge_subgraph (#7724). (#7729)
f21f284 
* Fix for filtered MultiGraph views from `edge_subgraph` (#7724).

* Added `test_consistent_edges` method to `TestEdgeSubGraph`.
@rossbar rossbar mentioned this issue Nov 26, 2024
Merged
dschult added a commit to rossbar/networkx that referenced this issue Dec 12, 2024
@dschult
Merge branch 'main' into networkxgh-7724-followup
07b4ae8
@rossbar rossbar mentioned this issue Mar 24, 2025
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix for filtered MultiGraph views from edge_subgraph (#7724). nelsonaloysio/networkx
2 participants
@dschult @nelsonaloysio
0