Python networkx соединяет подграф со свободным узлом

Question

Допустим, у нас есть следующий график (см. Ниже):

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)])

В какой-то момент существует подграф, состоящий изнесколько взаимосвязанных узлов и один узел, у которого нет ребер:

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

Поскольку все узлы неполного подграфа происходят из одного и того же полного графа, они могутбыть подключенным (например, по короткому пути) к тому, что изображено на следующем рисунке:

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

Интересно, есть ли функция networkxчто данный набор (или любой итеративный из узлов) возвращает подграф, который гарантирует, что все узлы связаны.Другими словами (и в конкретном случае) я хотел бы получить список [1,2,3,4,5,6,10,11] в качестве вывода функции.

Редактирование разъяснений

Поскольку мне кажется, что меня неправильно поняли, яЯ привожу еще несколько примеров.

Первый пример

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]

Узлами вывода являются те узлы, которые связывают подграф, т. е. в подграфе нет свободных концов.

Второй пример

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]

Пример 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]

В общем, есть функция, которая на основе chosen_nodes создает подграф, в котором все узлы как-то связаны (ребра взяты изgraph).

def get_connected_subgraph(graph, chosen_nodes):
    return output_nodes

Answer 1

Самый простой способ достижения вашей цели - вычислить все кратчайшие пути между выбранными вами узлами, а затем определить набор узлов, образующих эти пути.

#!/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:
/12813879/python-networkx-soedinyaet-podgraf-so-svobodnym-uzlom
"""
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