python - Python を使用してツリーからすべての可能な最長パスを抽出する

Question

以下に示すように、Pygraphviz を使用して生成されたキーワード ツリーがあります。タプルのリストとしてツリーの端を持っています。考えられるすべての関係をカバーするように、このツリーから考えられるすべての最長パスを抽出するアルゴリズムまたは最良の方法を探しています。

私は Pygraphviz を使用していたので、これを達成するための直接的で簡単な方法を探していました。しかし、Pygraphviz にはこれに対するオプションがないようです。

edges = 
[('Sara', 'chocolate'),
('chocolate', 'loves'),
('oranges', 'chocolate'),
('Jessi', 'chocolate'),
('best', 'best'),
('friends', 'chocolate'),
('Aron', 'chocolate')]

期待される結果：

[['Sara', 'chocolate', 'loves'],   
 ['oranges', 'chocolate', 'loves'],   
 ['Jessi', 'chocolate', 'loves'],  
 ['friends', 'chocolate', 'loves'],  
 ['Aron', 'chocolate', 'loves'],  
 ['Sara', 'chocolate', 'oranges'],  
 ['Sara', 'chocolate', 'Jessi'],  
 ['Sara', 'chocolate', 'friends'],  
 ['Sara', 'chocolate', 'Aron'],  
 ['oranges', 'chocolate', 'Jessi'],  
 ['oranges', 'chocolate', 'friends'],  
 ['oranges', 'chocolate', 'Aron'],  
 ['Jessi', 'chocolate', 'friends'],
 ['Jessi', 'chocolate', 'Aron'],  
 ['friends', 'chocolate', 'Aron'],
 ['best', 'best']]

私の現在のコード:

from collections import defaultdict
import itertools
edges = [('Sara', 'chocolate'),
         ('chocolate', 'loves'),
         ('oranges', 'chocolate'),
         ('Jessi', 'chocolate'),
         ('best', 'best'),
         ('friends', 'chocolate'),
         ('Aron', 'chocolate')]
neighbors = {}
rev_neighbors = {}
for edge in edges:
    neighbors[edge[0]] = edge[1]

for edge in edges:
    neighbor = neighbors.get(edge[1])
    if neighbor:
        print edge[0], edge[1], neighbor

v = defaultdict(list)
for key, value in sorted(neighbors.iteritems()):
    v[value].append(key)
for key, value in v.iteritems():
    if not len(list(itertools.combinations(value, 2))) == 0:
        for item in list(itertools.combinations(value, 2)):
            print item[0], key, item[1]

PS: xlabels の数は無視してください。