获取 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 中，您可以使用以下函数从起始节点获取树图：

bfs_tree(G, source, reverse=False)

这是文档的 link：Network bfs_tree。

Answer 2

这是一个递归算法，可以让所有节点连接到一个输入节点。

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)

I believe the key thing here to prevent infinite recursive calls is the condition to check that node which is neighbor in the original graph is not already connected in the sub_G that is being created. Otherwise, you will always be going back and forth and edges between nodes that already have edges.

我测试如下：

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。

Answer 3

假设图是无向的，为此有一个内置的 networkx 命令：

node_connected_component(G, n)

文档是 here。它 returns 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)。

获取 NetworkX 图中的连接节点

Fetch connected nodes in a NetworkX graph

python

networkx

graph-theory