CODEWITHSUNDEEP
pythonalgorithmdata-structures
nirvair
nirvair

Reputation: 4180

longest path in a tree in python

So, I have a dictionary which is in tree structure. Well, not entirely tree. But, I have to find the longest path from this tree.

This is the dictionary: 

{'1:0': [], '1:1': ['2:1', '1:0'], '1:2': ['1:3', '2:2', '1:1'], '1:3': [], '0:1': ['0:2', '1:1', '0:0'], '0:0': ['1:0'], '0:3': [], '0:2': ['0:3'], '2:3': ['2:2'], '2:2': ['3:2'], '2:1': ['2:2'], '2:0': ['2:1'], '3:2': [], '3:3': ['3:2'], '3:0': [], '3:1': ['3:2']}

There could actually be many roots. For example, in the key 1:1, it has two child nodes, of which one is a dead-end (1:0). And then 2:1 has a child 2:2. Also, 1:1 is a child of 1:2

How can I write this code in python to traverse and find the longest path?

Upvotes: 0

Views: 1112

Answers (2)

Ajax1234
Ajax1234

Reputation: 71451

You can use a recursive version of the breadth-first search:

_d = {'1:0': [], '1:1': ['2:1', '1:0'], '1:2': ['1:3', '2:2', '1:1'], '1:3': [], '0:1': ['0:2', '1:1', '0:0'], '0:0': ['1:0'], '0:3': [], '0:2': ['0:3'], '2:3': ['2:2'], '2:2': ['3:2'], '2:1': ['2:2'], '2:0': ['2:1'], '3:2': [], '3:3': ['3:2'], '3:0': [], '3:1': ['3:2']}
def paths(d, _start, _current = []):
  if _current:
    yield _current
  for i in d[_start]:
     if i not in _current:
        yield from paths(d, i, _current+[i])

results = [c for i in _d for c in paths(_d, i, [i])]
_max_len = max(map(len, results))
_paths = [i for i in results if len(i) == _max_len]

Output:

[['1:2', '1:1', '2:1', '2:2', '3:2'], ['0:1', '1:1', '2:1', '2:2', '3:2']]

Upvotes: 3

Paritosh Singh
Paritosh Singh

Reputation: 6246

You should consider a different structure to hold this data, this is essentially a graph problem. python comes with a really useful networkx library for graphs.
You can use dag_longest_path to find the longest path in a directed graph.

semi_tree = {'1:0': [], '1:1': ['2:1', '1:0'], '1:2': ['1:3', '2:2', '1:1'], '1:3': [], '0:1': ['0:2', '1:1', '0:0'], '0:0': ['1:0'], '0:3': [], '0:2': ['0:3'], '2:3': ['2:2'], '2:2': ['3:2'], '2:1': ['2:2'], '2:0': ['2:1'], '3:2': [], '3:3': ['3:2'], '3:0': [], '3:1': ['3:2']}
import networkx as nx
my_graph = nx.DiGraph(semi_tree)
result = nx.dag_longest_path(my_graph)
print(result) #Output: ['1:2', '1:1', '2:1', '2:2', '3:2']

Upvotes: 1

Related Questions