从字符串列表中构造一棵树

Question

我有 400 个这样的列表：

[A ,B, C,D,E]
[A, C, G, B, E]
[A,Z,B,D,E]
...
[A,B,R,D,E]

每个长度为 5 个以 A 开头的项目。

我想构建一个树或有向无环图（同时计算一个权重），其中每个级别都是项目的索引，即 A 具有第一个索引中所有可能项目的边，它们将具有边child 在第二个索引中，依此类推。

有没有一种简单的方法可以在 networkx 中进行构建？我想做的是为每个级别创建所有元组，即级别 0 ： (A,B) ,(A,C) , (A,Z) 等 ..但不确定如何移动它

Answer 1

如果我没理解错的话，您可以使用有向图的 nx.add_path 将每个列表设置为路径。

l = [['A' ,'B', 'C','D','E'],
     ['A', 'C','G', 'B', 'E'],
     ['A','Z','B','D','E'],
     ['A','B','R','D','E']]

虽然你有多个级别的节点，但你可能应该根据它们的级别重命名它们，因为你不能有多个节点同名。所以一种方法可能是：

l = [[f'{j}_level{lev}' for lev,j in enumerate(i, 1)] for i in l]
#[['A_level1', 'B_level2', 'C_level3', 'D_level4', 'E_level5'],
# ['A_level1', 'C_level2', 'G_level3', 'B_level4', 'E_level5'],
# ['A_level1', 'Z_level2', 'B_level3', 'D_level4', 'E_level5'],
# ['A_level1', 'B_level2', 'R_level3', 'D_level4', 'E_level5']]

现在构建图表：

G = nx.DiGraph()
for path in l:
    nx.add_path(G, path)

然后您可以使用 graphviz 的点布局创建树状结构：

from networkx.drawing.nx_agraph import graphviz_layout
pos=graphviz_layout(G, prog='dot')
nx.draw(G, pos=pos,
        node_color='lightgreen', 
        node_size=1500,
        with_labels=True, 
        arrows=True)

从字符串列表中构造一棵树

construct a tree out of list of strings

python

graph

networkx