2

我有一个使用 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。

4

0 回答 0