Python networkx connect subgraph with a loose node

Question

Let's say we have the following graph (please see below):

import networkx as nx

G = nx.Graph()

G.add_edges_from([(1,2), (2,3), (1,3), (3,4), (4,5), (5,6), (6,10), (10,11), (5,7), (5,8), (8,9), (9,10)])

At one moment there is a subgraph that consists of few interconnected nodes and one node that has no edges:

nx.draw(G.subgraph([1,2,3,11]), with_labels=True)

Since all nodes of the incomplete subgraph come from the same full graph they can be connected (e.g. by a shortpath) what is presented on the following picture:

nx.draw(G.subgraph([1,2,3,4,5,6,10,11]), with_labels=True)

I wonder whether there is a networkx function that given a set (or any iterable of nodes) returns a subgraph that makes sure all nodes are connected. In other words (and case-specifically) I would like to get the list [1,2,3,4,5,6,10,11] as an output of a function.

Clarification edit

Since it seems that I'm being misunderstood I'm giving few more examples.

First example

G1 = nx.Graph()

G1.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,4), (4,5), (5,6), (6,7), (5,7), (5,8), (8,9), (9,10), (10,12), (10,11), (11,12)])

chosen_nodes = [1,2,3,12] # construct a subgraph based on those nodes

output_nodes = [1,2,3,4,5,8,9,10,12]

Output nodes are those nodes that make the subgraph connected, i.e. there are no loose ends in the subgraph.

Second example

G2 = nx.Graph()

G2.add_edges_from([(1,2), (2,3), (3,4), (4,5), (5,6), (4,6)])

chosen_nodes = [1,2,5]

output_nodes = [1,2,3,4,5]

Example 3

G3 = nx.Graph()

G3.add_edges_from([(1,2), (2,3), (3,5), (2,4), (4,5)])

chosen_nodes = [1,2,3]

output_nodes = [1,2,3]

In general there's is a function that based on chosen_nodes creates a subgraph in which all nodes are somehow connected (edges are taken from graph).

def get_connected_subgraph(graph, chosen_nodes):
    return output_nodes

Answer 1

The simplest way to achieve your goal is to compute all shortest paths between your chosen nodes, and then determine the set of the nodes forming these paths.

#!/usr/bin/env python
"""
Find the subgraph G' induced on G, that
1) contain all nodes in a set of nodes V', and
2) is a connected component.

See also:
https://stackguides.com/questions/58076592/python-networkx-connect-subgraph-with-a-loose-node
"""
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import itertools

def get_connected_subgraph(graph, v_prime):
    """Given a graph G=(V,E), and a vertex set V', find the V'', that
    1) is a superset of V', and
    2) when used to induce a subgraph on G forms a connected component.

    Arguments:
    ----------
    G : networkx.Graph object
        The full graph.
    v_prime : list
        The chosen vertex set.

    Returns:
    --------
    v_prime_prime : set
        The set of nodes fullfilling criteria 1) and 2).

    """
    vpp = set()
    for source, target in itertools.combinations(v_prime, 2):
        paths = nx.all_shortest_paths(graph, source, target)
        for path in paths:
            vpp = vpp.union(path)
    return vpp

def test_1():
    G1 = nx.Graph()
    G1.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,4), (4,5), (5,6), (6,7), (5,7), (5,8), (8,9), (9,10), (10,12), (10,11), (11,12)])
    chosen_nodes = [1,2,3,12] # construct a subgraph based on those nodes
    output_nodes = [1,2,3,4,5,8,9,10,12]
    returned_nodes = get_connected_subgraph(G1, chosen_nodes)
    assert set(output_nodes) == returned_nodes

def test_2():
    G2 = nx.Graph()
    G2.add_edges_from([(1,2), (2,3), (3,4), (4,5), (5,6), (4,6)])
    chosen_nodes = [1,2,5]
    output_nodes = [1,2,3,4,5]
    returned_nodes = get_connected_subgraph(G2, chosen_nodes)
    assert set(output_nodes) == returned_nodes

def test_3():
    G3 = nx.Graph()
    G3.add_edges_from([(1,2), (2,3), (3,5), (2,4), (4,5)])
    chosen_nodes = [1,2,3]
    output_nodes = [1,2,3]
    returned_nodes = get_connected_subgraph(G3, chosen_nodes)
    assert set(output_nodes) == returned_nodes