パイソン - 見つける最長パス

Question

は、関数は、入力として辞書にかかります、と私は辞書内の最長パスの長さを見つけたいです。基本的に、辞書内でkey2がvalue1と一致し、key3がvalue2と一致すると、これはパスとしてカウントされます。例えば：上記の場合

{'a':'b', 'b':'c', 'c':'d'} 

、長さが3であるべきです。どうすればこれを達成できますか？または、具体的にどのように私はキーと値を比較するでしょうか？事前に

多くのおかげで（これは何も、文字列、数値など、数字だけではないかもしれません）！

Answer 1

私は非循環有向グラフ（DAG）のエッジのリストとして辞書を扱い、グラフの最長経路を見つけるためにnetworkxモジュールを使用します。あなたがいないの主張している場合

import networkx as nx 

data = {'a':'b', 'b':'c', 'c':'d'} 

G = nx.DiGraph() 
G.add_edges_from(data.items()) 
try: 
    path = nx.dag_longest_path(G) 
    print(path) 
    # ['a', 'b', 'c', 'd'] 

    print(len(path) - 1) 
    # 3 
except nx.exception.NetworkXUnfeasible: # There's a loop! 
    print("The graph has a cycle") 

Answer 2

をあなたは「キーと値を比較」する必要がない理由

def find_longest_path(data): 
    longest = 0 
    for key in data.iterkeys(): 
     seen = set() 
     length = -1 
     while key: 
      if key in seen: 
       length = -1 
       raise RuntimeError('Graph has loop') 
      seen.add(key) 
      key = data.get(key, False) 
      length += 1 
     if length > longest: 
      longest = length 

    return longest