在NetworkX图中获取相连节点

Question

简单的问题：我想检索与NetworkX图中给定节点连接的所有节点，以创建子图。在下面的示例中，只需提取圆圈内的所有节点，给定其中任何一个的名称即可。

我尝试了以下递归函数，但由于该网络中只有91个节点，即使代码没有错误，也会达到Python的递归限制。

无论下面的代码是否有问题，实现我想要的最佳方法是什么？我将在各种大小的图上运行此代码，并且事先不知道最大递归深度。

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)

- Bede Constantinides

---

这是一个有向图还是无向图？ - Abdallah Sobehy

@AbdallahSobehy 无向的，尽管我处理的数据是否有向还存在争议。 - Bede Constantinides

Answer 1

假设图是无向的，那么可以使用networkx中内置的命令来实现：

node_connected_component(G, n)

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

它不是递归的，但我认为你实际上并不需要或者甚至不想要它。

---

对你代码的评论: 你有一个错误，往往会导致无限递归。如果和v都是至少具有2度的邻居，则它将从开始，将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)。

- Joel

---

非常好的答案。我本来期望有一个networkx函数可以做到这一点，但是我没有找到 - 谢谢！我的代码中的错误似乎非常明显。 - Bede Constantinides

Answer 2

您可以从给定节点或任何节点开始使用广度优先搜索。在Networkx中，您可以使用以下函数从起始节点获得树图：

bfs_tree(G, source, reverse=False)

这里是一个链接指向文档：Network bfs_tree。

- Kirell

---

谢谢Kikhos。类似的，我认为[v for u,v in nx.bfs_edges(G, source)]也会给我一个所需的节点列表。 - Bede Constantinides

当前链接：https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.breadth_first_search.bfs_tree.html#networkx.algorithms.traversal.breadth_first_search.bfs_tree - keithpjolley

需要注意的是，这也适用于有向图。 - keithpjolley

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的子图。

- Abdallah Sobehy

---

非常好的答案，教授了算法而不是像@Joel那样使用内置库函数。谢谢。 - Bede Constantinides