python - 如何找到包含给定节点集最大数量的连通分量

Question

我有一个包含许多基因及其相互作用的图表。我有兴趣找到一个子图，其中一组特定基因的最大数量为图中的 A、B、C、D、E。

尝试了 BFS 算法以及连接组件。但不知道如何找到我感兴趣的基因的子图。

def bfs(G, gene, n):
"""

Using breadth-first search
returns a graph of breadth n starting at source gene.
"""
S = nx.algorithms.traversal.breadth_first_search.bfs_tree(G, source=gene, depth_limit=n)
return S

给定一个具有 V 个顶点和 E 个边的图 G(V,E) ，我想找到一个子图 G'(v,e)，其中 v 是 V 的子集，这样 G' 包含我的最大节点数兴趣。

Answer 1

编辑虽然我认为我的原始代码(现在位于底部)很好，但我认为您可以使用返回集合的 node_connected_component(G,u) 做得更好与 u 位于同一组件中的节点。

让我解释一下下面的代码。首先，我将逐步介绍有趣的基因。对于第一个基因，我寻找它所在的 G 组件，然后找到同一组件中的所有其他有趣的基因。然后，当我查看每个后续有趣的基因时，我确保我还没有在与另一个相同的组件中遇到它。如果它是一个新组件，我会在同一组件中找到所有其他有趣的基因。最后，我找到了具有最有趣基因的组件。

component_count = {}
seen = {}
for source in interesting_genes:
    if source not in seen:
        reachable_nodes = nx.node_connected_component(G, source)
        reachable_nodes_of_interest = [target for target in interesting_genes if target in reachable_nodes]
        for node in reachable_nodes_of_interest:
            seen[node] = True
        component_count = len(reachable_nodes_of_interest)

source = max(component_count, key=component_count.get) #finds the node with the largest component_count


Gprime = G.subgraph(nx.node_connected_component(G, source))

<小时/>

看看the documentation对于single_source_shortest_path_length。

seen = {source:False for source in interesting_genes}  #if we've found the component of a node, no need to recalculate it.
component_count = {}  #will count how many other interesting genes there are in a component
for source in interesting_genes:
    if not seen[source]:
        reachable_nodes_dict = nx.single_source_shortest_path_length(G, node)
        reachable_nodes_of_interest = [target for target in interesting_genes if target in reachable_nodes_dict]
        for target in reachable_nodes_of_interest:
            seen[target] = True
        component_count[source] = len(reachable_nodes_of_interest)
source = max(component_count, key=component_count.get) #finds the node with the largest component_count


Gprime = G.subgraph(nx.node_connected_component(G, source))