Dictionary with reference of value to key in Python

Question

Is there any method available in python to obtain the key that a value belongs to within a nested dictionary?

An example would be:

dic = {1 : 
       {2 : 
        {3 : 4}},
       5 : 
       {6 :
        {7 : 8}}
      }

Where I would then want to know the path one needs to take to reach either 4 or 8.

This would look something like:

find_path(dic, 8)

which should return something like

5, 6, 7 # since dic[5][6][7] leads to 8.

For context: I am trying to create 60^5 game states for an AI that I intend to implement for a game. I need to analyze all game states at a depth of 5 to determine which is best. Then, in order to reach the state at depth 5, I need to know what steps to take at depth 1, 2, 3 and 4 in order to reach this game state. I don't know whether dictionaries are optimal to achieve this, so would love to hear some other suggestions if possible.

Did you try to write some code for find_path()? Can you share it? — quamrana
– quamrana, Commented Jan 5, 2020 at 16:25

DarrylG · Accepted Answer · 2020-01-05 20:12:20Z

3

Two Solutions

The first - Recursion

The second - Depth First Search

First Solution - Using Recursion

def find_path(d, value, path = [], sol = []):
    for k, v in d.items():
        if isinstance(v, dict):
            path.append(k)
            find_path(v, value, path, sol)
            path.pop()
        elif v == value:
            path.append(k)
            sol.append(path[:])
            path.pop()
    return sol

dic = {1 : {2 : 
             {3 : 4}
            }, 
        5 : {6 :
             {7 : 8}}}

for v in range(10):
    found = find_path(dic, v, [], [])
    if found:
        print("{} -> {}".format(v, found[0))  # showing first solution
                                              # found will show them all
    else:
        print("No path to {}".format(v))

Output

No path to 0
No path to 1
No path to 2
No path to 3
4 -> [1, 2, 3]
No path to 5
No path to 6
No path to 7
8 -> [5, 6, 7]
No path to 9

Second Solution - Using Depth First Search

from collections import deque 

def find_using_dfs(d, value):
    " Finds using depth first searh through dictionary "

    # Use queue for Depth First Search (LIFO)
    stack = deque()

    for k, v in d.items():
        stack.append((v, [k]))

    while stack:
        v, path = stack.pop()
        if isinstance(v, dict):
            for k, viter in v.items():
                path.append(k)
                stack.append((viter, path[:]))
                path.pop()

        elif v == value:
            return path

    return None   

dic = {1 : {2 : 
             {3 : 4}
            }, 
        5 : {6 :
             {7 : 8}}}

for v in range(0, 10):
    found = find_path_proc(dic, v)
    if found:
        print("{} -> {}".format(v, found))
    else:
        print("No path to {}".format(v))

Output

No path to 0
No path to 1
No path to 2
No path to 3
4 -> [1, 2, 3]
No path to 5
No path to 6
No path to 7
8 -> [5, 6, 7]
No path to 9

edited Jan 5, 2020 at 20:12

answered Jan 5, 2020 at 16:55

DarrylG

17.2k2 gold badges21 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Menno Van Dijk Over a year ago

Having 60^5 game states would cause python to break using recursion, no?

DarrylG Over a year ago

@MennoVanDijk--added a second solution which is non-recursive (i.e. performs a Depth First Search)

Razmik Melikbekyan · Accepted Answer · 2020-01-05 17:16:50Z

You can do it with networkx:

from collections import Mapping
import networkx as nx

graph_data = {1 : 
       {2 : 
        {3 : 4}},
       5 : 
       {6 :
        {7 : 8}}
      }
# Empty directed graph
G = nx.DiGraph()

# Iterate through the layers
q = list(graph_data.items())
while q:
    v, d = q.pop()
    for nv, nd in d.items():
        G.add_edge(v, nv)
        if isinstance(nd, Mapping):
            q.append((nv, nd))
        else:
            if not isinstance(nd, dict):
                G.add_edge(nv, nd)

As a final step we can use nx.shortest_path function.

all_paths = nx.shortest_path(G, target=8)
max_len_key =  max(all_paths, key=lambda k: len(all_paths[k]))
print(all_paths[max_len_key])

And the output will be:

[5, 6, 7, 8]

Kateřina Churanová · Accepted Answer · 2020-01-05 17:17:20Z

0

To make it fast, I'd consider creating a {key: parent_key} dict instead. In your case,

dic = {1:None, 2:1, 3:2, 4:3, 
       5:None, 6:5, 7:6, 8:7}

If those keys are some complicated game states, you can have them as mere IDs and keep actual states in a separate dict or even list. Or you can have

class State:
    pass

StateNode = namedtuple('StateNode', ('state', 'parent_id'))
dic = {1: StateNode(State(), None), 2: StateNode(State(), 1), 3: StateNode(State(), 2)}

Either way, when you know id of your leaf node (which I assume you know), you can simply draw nodes from dict until you reach a node with parent None.

answered Jan 5, 2020 at 17:17

Kateřina Churanová

213 bronze badges

Comments

Boendal · Accepted Answer · 2020-01-05 17:24:05Z

Another way I can think of is to create an inverted dict. Takes a lot more space but is more efficient as far as I can tell. It would look something like this:

dic = {1 :
       {2 :
        {3 : 4}},
       5 :
       {6 :
        {7 : 8}}
      }

inverted_dic = {}

def create_inverted_dic(d):
    def create_inverted_dic_rec(sub_dic,root):
        for k,v in sub_dic.items():
            inverted_dic[k] = root
            if isinstance(v,dict):
                create_inverted_dic_rec(v,k)
            else:
                inverted_dic[v] = k

    for k,v in d.items():
        inverted_dic[k] = None
        create_inverted_dic_rec(v,k)

def find_path(value):
    output = []
    while not value is None:
        value = inverted_dic.get(value,None)
        if value:
            output.append(value)
    output.reverse()
    return output

create_inverted_dic(dic)

for i in range(10):
    print("{} ->  {}".format(i, find_path(i)))

Output

The advantage is that it also show the path to subdicts if you not only need the leaf.

0 ->  []
1 ->  []
2 ->  [1]
3 ->  [1, 2]
4 ->  [1, 2, 3]
5 ->  []
6 ->  [5]
7 ->  [5, 6]
8 ->  [5, 6, 7]
9 ->  []

Collectives™ on Stack Overflow

Dictionary with reference of value to key in Python

4 Answers 4

2 Comments

Comments

Comments

Output

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Output

Comments

Your Answer

Sign up or log in

Post as a guest

Related