-1

我可能想多了,遗漏了一些明显的东西,但我想知道我可以使用哪种 NetworkX 算法来实现以下目标:

给定一个有向图,例如:

简单有向图

以及节点列表,例如:Q1、Q2

找到所有连接到 Q1 和 Q2 的节点(或者换句话说,它们的子节点),结果如下:

第一季度

第二季度

哪种算法可以做到这一点?

4

2 回答 2

0

第一种方法是使用列表,从您的节点开始访问每个节点的前任并将其放入列表中,以这种方式与您找到的节点一起构建一棵树。

另一种方法是在反转边缘的图上使用访问(DFS 或 BFS)。

考虑以下示例,其中我从节点“Q1”开始构建bfs 树。

import networkx as nx

g = nx.DiGraph()

g.add_edges_from([("M1","Q1"),("I1","M1"),("I2","M1"),("I3","M1"),("I3","M2"),("M2","Q2")])

#creating a graph with the edges reversed
g2 = nx.DiGraph()
g2.add_edges_from([(v,u) for (u,v) in g.edges()])

t = nx.bfs_tree(g2, "Q1")

for (u,v) in t.edges():
    t.remove_edge(u,v)
    t.add_edge(v,u)


print(t.nodes(),t.edges())
# ['Q1', 'M1', 'I1', 'I2', 'I3'] [('M1', 'Q1'), ('I1', 'M1'), ('I2', 'M1'), ('I3', 'M1')]
于 2018-08-25T15:41:49.960 回答
0

看起来你只需要对networkx.Digraph.predecessors进行递归

于 2018-08-25T11:57:59.610 回答