在NetworkX图中获取连接的节点

Question

直截了当的问题:我想检索连接到NetworkX图中给定节点的所有节点,以便创建子图.在下面显示的示例中,我只想提取圆圈内的所有节点,给出其中任何一个节点的名称.

我尝试了以下递归函数,但是命中了Python的递归限制,即使此网络中只有91个节点.

无论下面的代码是否有错误,我做什么的最佳方法是什么？我将在各种大小的图形上运行此代码,并且不会事先知道最大递归深度.

def fetch_connected_nodes(node, neighbors_list):
    for neighbor in assembly.neighbors(node):
        print(neighbor)
        if len(assembly.neighbors(neighbor)) == 1:
            neighbors_list.append(neighbor)
            return neighbors_list
        else:
            neighbors_list.append(neighbor)
            fetch_connected_nodes(neighbor, neighbors_list)

neighbors = []
starting_node = 'NODE_1_length_6578_cov_450.665_ID_16281'
connected_nodes = fetch_connected_nodes(starting_node, neighbors)

Answer 1

假设图形是无向的,则有一个内置的networkx命令:

node_connected_component(G, n)

文档在这里.它返回G包含的连接组件中的所有节点n.

它不是递归的,但我认为你实际上不需要甚至不需要它.

对您的代码的评论:您有一个通常会导致无限递归的错误.如果u并且v它们都是度数至少为2的邻居,那么它将开始u,放入v列表中,当处理v放入u列表并继续重复时.它需要更改为仅处理不在的邻居neighbors_list.检查它是昂贵的,所以改为使用一套.如果起始节点具有1级,那么也存在一个小问题.您对1级的测试不能完成您所追求的目标.如果初始节点具有1级,但其邻居具有较高程度,则它将找不到邻居的邻居.

这是对代码的修改:

def fetch_connected_nodes(G, node, seen = None):
    if seen == None:
        seen = set([node])
    for neighbor in G.neighbors(node):
        print(neighbor)
        if neighbor not in seen:
            seen.add(neighbor)
            fetch_connected_nodes(G, neighbor, seen)
    return seen

你称之为fetch_connected_nodes(assembly, starting_node).

Answer 2

您可以简单地使用从给定节点或任何节点开始的广度优先搜索。

在 Networkx 中，您可以使用以下函数从起始节点获取树图：

bfs_tree(G, source, reverse=False)

这是文档的链接：Network bfs_tree。

Answer 3

这是一个递归算法，用于获取连接到输入节点的所有节点。

def create_subgraph(G,sub_G,start_node):
    sub_G.add_node(start_node)
    for n in G.neighbors_iter(start_node):
        if n not in sub_G.neighbors(start_node):
            sub_G.add_path([start_node,n])
            create_subgraph(G,sub_G,n)

我相信这里防止无限递归调用的关键是检查原始图中的邻居节点是否尚未在正在创建的 sub_G 中连接的条件。否则，您将始终在已经具有边缘的节点之间来回移动和边缘。

我测试如下：

G = nx.erdos_renyi_graph(20,0.08)
nx.draw(G,with_labels = True)
plt.show()
sub_G = nx.Graph()
create_subgraph(G,sub_G,17)
nx.draw(sub_G,with_labels = True)
plt.show()

您将在附图中找到完整的图和包含节点 17 的 sub_graph。