minorminer icon indicating copy to clipboard operation
minorminer copied to clipboard

subgraph.find_subgraph has unexpected behaviour if some nodes are disconnected. Only nodes assocaited to at least one edge are embedded

Open jackraymond opened this issue 3 months ago • 0 comments

Description subgraph fails to find an embedding if source graph contains nodes without edges. This is a pathological case, but worth protecting against.

To Reproduce

S = nx.Graph()
S.add_node_from(1)
T = S.copy()
emb = minorminer.subgraph.find_subgraph(S, T)
# emb is an empty list, not {1: 1} as expected

Expected behavior A graph that includes disconnected nodes should be embeddable if the connected components are embeddable and there are sufficiently many total nodes.

Environment:

  • OS: [Ubuntu 16.04.4 LTS]
  • Python version: [e.g. 3.7.0]

Additional context

jackraymond avatar Nov 06 '24 22:11 jackraymond