python - Python で Networkx を使用して DAG の最長パスを検索する

Question

文字列の非常に大きな 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)

私は、すべてのノードから他のすべてのノードへのパス距離をチェックする単純なアプローチを試みました...これは明らかに非現実的であり、終了しません。

また、このスレッドのlongest_path()コードを作り直そうとしましたが、役に立ちませんでした。

トポロジカルソートの実行とグラフの順序付けについて理解できることについて多くのことを読みましたが、これを実装するのに問題があります。Networkx は function を提供するtopological_sort(g)ので、作業は私のために行われます。しかし、topo_sorted グラフができたので、ここからどのように進めればよいでしょうか?