python - タプル(エッジ)のリストをPythonの最長パスのリストに変換します

Question

図を見てください。下。私のプロジェクトの一環として、フォレストの端のリストを一意の最長パスのリストに変換する必要があります。最長パスとは、実際には、任意のルート ノードをリーフ ノードに、またはリーフをリーフ ノードに接続するパスです。ここでの問題は、入力としてエッジのリストしかなく、そこからこれらのパスを導出することになっていることです。

ディクショナリ (エッジのリストを使用して作成) を使用して隣接ノードを検索することにより、この問題を再帰的に解決しようとしていますが、問題を処理する適切な方法ではないようで、視覚化するのも難しいと感じています。この問題を解決するための既知の効率的なアルゴリズム/方法があるかどうかを提案してください。

PS:重みは無視してください (それらは単なるラベルです)。「最長」とは、最大ノードをカバーするパスを意味します。

入力:
タプルのリスト(エッジ)

edges = [('point', 'floating'), ('754', 'floating'),
('clock', 'IEEE'), ('ARM', 'barrel'), 
('barrel', 'shifter clock'), ('shifter', 'barrel'), 
('representation', 'representation'), ('cycles', '754'), 
('point representation', 'point'), ('barrel shifter', 'point')]

期待される出力:

inference_paths = [
    ['cycles', '754', 'floating', 'point', 'point representation'],
    ['cycles', '754', 'floating', 'point', 'barrel shifter'],
    ['point repr', 'point', 'barrel shifter'],
    ['ARM', 'barrel', 'shifter clock'],
    ['shifter', 'barrel', 'shifter clock'],
    ['ARM', 'barrel', 'shifter'],
    ['clock', 'IEEE'],
    ['representation']
] 

私の失敗したコード:

edges = [('point', 'floating'), ('754', 'floating'), ('clock', 'IEEE'), ('ARM', 'barrel'), ('barrel', 'shifter clock'), ('shifter', 'barrel'), ('representation', 'representation'), ('cycles', '754'), ('point representation', 'point'), ('barrel shifter', 'point')]
neighbors = {}
inference_paths = []

for edge in edges:
    neighbors[edge[0]] = edge[1]

for edge in edges:
    neighbor = neighbors.get(edge[1])
    if neighbor:
        if not edge[1] == edge[0] == neighbor:
            inference_paths.append([edge[0], edge[1], neighbor])
        else:
            inference_paths.append([edge[0]])
    else:
        inference_paths.append([edge[0], edge[1]])


for path in inference_paths:
    print path

私の出力:

[['point', 'floating'],
['754', 'floating'],
['clock', 'IEEE'],
['ARM', 'barrel', 'shifter clock'],
['barrel', 'shifter clock'],
['shifter', 'barrel', 'shifter clock'],
['representation'],
['cycles', '754', 'floating'],
['point representation', 'point', 'floating'],
['barrel shifter', 'point', 'floating']]

森：