CODEWITHSUNDEEP
pythondictionarybreadth-first-search
jason
jason

Reputation: 2106

How to recover the path from a pair of (parent, child) in dictionary in python?

I have a dictionary key:set

the key is a child node with string, and its value is a set contain its parent node's string.

For example

startnode = "hit"
endnode = "cog"
mydict =  {'hot': {'hit'}, 'dot': {'hot'}, 'lot': {'hot'}, 
       'dog': {'dot'}, 'log': {'lot'}, 'cog': {'dog', 'log'}}

'cog': {'dog', 'log'}: means dog and log both point to child node cog

How to recover all possible paths from any two nodes?

In this example, the results will be

res = [["hit","hot","dot","dog","cog"],
       ["hit","hot","lot","log","cog"]]

I tried to use loop, but I fail since each child can have arbitrary parent. Any thoughts?

Upvotes: 1

Views: 530

Answers (1)

Saeid
Saeid

Reputation: 4265

First create a dictionary such that the keys are parents and the values are children of the keys. Then run any path finding algorithm (bfs or dfs) to find all the possible paths.

To create the dictionary from what you have:

from collections import defaultdict
adjacency = defaultdict(set)
for key in mydict:
   for node in mydict[key]:
     adjacency[node].add(key)

Result is:

defaultdict(set,
            {'dog': {'cog'},
             'dot': {'dog'},
             'hit': {'hot'},
             'hot': {'dot', 'lot'},
             'log': {'cog'},
             'lot': {'log'}})

You can read this article for explanation and implementation of bfs and dfs in python.

Upvotes: 2

Related Questions