minorminer
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
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