Python - finding the longest way

Question

The function will take the dictionary as input, and I want to find the length of the longest path in the dictionary. In principle, if in the dictionary key2 corresponds to value 1, and key3 corresponds to value2, etc., this is considered as a path. For instance:

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

In the above case, the length should be three. How can i achieve this? Or more specifically, how can I compare keys with values? (it can be any lines, numbers, etc., and not just numbers)

Thank you very much in advance!

Answer 1

I would consider the dictionary as a list of edges in a directed acyclic graph (DAG) and use the networkx module to find the longest path on the graph:

 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 a loop! print("The graph has a cycle") 

Answer 2

If you insist on not importing anything, you could do something like:

 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