我有一个非常大的字符串DAG(~200k) . 我想找到此图中存在的最长路径 . 下面的代码是我如何设置图表(从字符串列表 new_list
) .
#create new empty graph
g = nx.DiGraph()
#add all words to graph
for word in new_list:
g.add_node(word)
#fill graph with valid word chains
for word in g.nodes():
for c in string.ascii_lowercase:
new_word = alphagramatize(word+c) #add char c to word in alphagram order
if(binary_search(new_list, new_word) != -1):
g.add_edge(word, new_word)
我尝试了一种天真的方法来检查从每个节点到每个其他节点的路径距离......这显然是不切实际的,不会终止 .
我也试图从this线程重做 longest_path()
代码,但无济于事 .
我已经阅读了很多关于执行拓扑排序和图表排序的内容,但我很难实现这一点 . Networkx提供了一个函数 topological_sort(g)
,因此我可以完成工作 . 但是,如果我有一个topo_sorted图,我该如何从这里继续?