python - 连接到子图网络的节点或节点集x

Question

我有 2 个图A和B。B是A的强连通子图。我想在A中找到具有到B中任何节点的路径的节点。如何在 Networkx 中执行此操作？

注意：我已经尝试过使用弱连接组件，但是没有用。

标签： pythonnetworkxgraph-theory

Answer 1

如果B是强连通的，那么如果选择 中的任何节点u，B那么如果 中的某个节点x有A一条到 中的某个节点的路径b，B那么就有一条从x到的路径u（有一条从b到的路径，u因为B是强连通的，然后是x到b到的u路径存在）。因此，拥有到 in 中任何节点的路径与拥有到 inB中的一个特定节点的路径是一回事B。让X是具有到 的路径的节点集u。这是你想要的套装。

如果你这样做了，X = nx.ancestors(A, u)那么X是一组具有路径的节点u。如果你想要子图本身，那么做G = A.subgraph(X)，但如果你只想要一组节点，那么它就是X.

---

注意 - 这实际上是 Epidemics on Networks 包https://epidemicsonnetworks.readthedocs.io/en/latest/ （我写的）中使用的算法，用于使用定向渗透估计流行病的概率。