Python Forum
Recursion through nested dictionary - Unable to get desired output
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Recursion through nested dictionary - Unable to get desired output
#1
Hello,

I am writing a recursive function for dictionary of variable depth. I've posted a sample of this dictionary below. Only 'call_next_rule' key can have a nested dictionary as its value.

d4 = {'call_next_rule': 
                       {'call_next_rule': 
                                         {'call_next_rule': None, 'executed_rule': 'rule_4B',     'rule_successful': True},
                        'executed_rule': 'rule_4A', 'rule_successful': True},
      'executed_rule': 'rule_4', 'rule_successful': True}
The desired output is:

Output:
[('MyRoot', 'rule_4'), ('rule_4', 'rule_4A'), ('rule_4A', 'rule_4B')]
Instead I get nested tuples
(I do realize I am not returning a list here, but rather nested tuples)
Output:
('My Root', ('rule_4', ('rule_4A', 'rule_4B')))
Here is my recursive function:

def get_edges(d, parent = None):

    result = list()
    if parent is None:
        parent = 'My Root'

    for k,v in d.items():
        if d['call_next_rule'] == None:  #base case 
            child = d['executed_rule']
            return (parent, child)
        else:
            if isinstance(v, dict):
                child = get_edges(v, parent = d['executed_rule'])
                             
                #result.append((parent, child[0]))
                #result.append((child[0], child[1]))
                
                return (parent, child)

get_edges(d4)
I've tried 2 solutions to get the desired output that I want:
1. For a 2 level deep nested dictionary, uncommenting above two lines and then returning 'result' list back works. But it fails for 3 level or deeper dictionary.

2. I have used a 'static' counter variable to count number of times 'get_edges()' is called. Then I use this counter in another function to get the output that I want. I feel that this is clumsy.

What should I do here to get the result I want?

P.S. Last time I worked with recursion was over 10 years ago with C++ and tree algorithms. I barely did it then, and I am barely doing it now. Recursion is not my strong point and I am a novice in Python.
I have tried avoiding recursion but 'stack of iterators' pattern is confusing to me and I just don't know how to break this problem into multiple 'while' or 'for' loops. I am open to any suggestions that you may have.

(Thanks in advance)
Reply
#2
For tasks of that type, I always find helper function and accumulator objects helpful

You don't have to go over all the key/value pair on each recursion level - there are only 2 keys that you are interested in - call_next_rule and executed_rule. I used this fact to simplify the search algorithm

def get_edges(json_obj):
    results = list()

    def _get_executed(target, parent=None):
        if parent is None:
            parent = 'My Root'
        executed = target['executed_rule']
        results.append((parent, executed))
        next_rule = target['call_next_rule']
        if next_rule is not None:
            _get_executed(next_rule, executed)
         
    _get_executed(json_obj)
    return results
And the result is up to spec
Output:
In [16]: get_edges(d4) Out[16]: [('My Root', 'rule_4'), ('rule_4', 'rule_4A'), ('rule_4A', 'rule_4B')]
Test everything in a Python shell (iPython, Azure Notebook, etc.)
  • Someone gave you an advice you liked? Test it - maybe the advice was actually bad.
  • Someone gave you an advice you think is bad? Test it before arguing - maybe it was good.
  • You posted a claim that something you did not test works? Be prepared to eat your hat.
Reply
#3
from collections import deque


def iterative_next_rule(dataset):
    stack = deque([dataset])
    while stack:
        data = stack.pop()
        if data is None:
            continue
        if 'call_next_rule' in data:
            stack.append(data['call_next_rule'])
        if all(key in data for key in ['executed_rule', 'rule_successful']):
            yield data['executed_rule'], data['rule_successful']
        else:
            print('Illegal Data.')


d4 = {
    'call_next_rule':
        {
        'call_next_rule':
            {
            'call_next_rule': None, 'executed_rule': 'rule_4B', 'rule_successful': True
            },
        'executed_rule': 'rule_4A', 'rule_successful': True
         },
    'executed_rule': 'rule_4', 'rule_successful': True
    }


for value in iterative_next_rule(d4):
    print(value)
This should do what you want I guess.
I'm using an iterative way, to prevent recursion.
Almost dead, but too lazy to die: https://sourceserver.info
All humans together. We don't need politicians!
Reply
#4
EDITED

(Jul-09-2018, 08:02 AM)DeaD_EyE Wrote: I'm using an iterative way, to prevent recursion.

I really liked the idea of iteration (I did not think of that) - but in that case, you don't even need stack
Output:
In [28]: def iterative_next_rule(dataset, parent='My rule'): ...: while dataset: ...: executed_rule = dataset['executed_rule'] ...: if all(key in dataset for key in ['executed_rule', 'rule_successful']): ...: yield parent, executed_rule ...: parent = executed_rule ...: dataset = dataset.get('call_next_rule') ...: In [29]: list(iterative_next_rule(d4)) Out[29]: [('My rule', 'rule_4'), ('rule_4', 'rule_4A'), ('rule_4A', 'rule_4B')]
OK - I sinned again against my rule No 3 Wall . Fixed to spec
Test everything in a Python shell (iPython, Azure Notebook, etc.)
  • Someone gave you an advice you liked? Test it - maybe the advice was actually bad.
  • Someone gave you an advice you think is bad? Test it before arguing - maybe it was good.
  • You posted a claim that something you did not test works? Be prepared to eat your hat.
Reply
#5
By the way, I forgot to say, that this function is modifying the dict.
If working with a stack, it should be prevented by copying, but the solution without an stack is more elegant.
Almost dead, but too lazy to die: https://sourceserver.info
All humans together. We don't need politicians!
Reply
#6
(Jul-09-2018, 08:52 AM)DeaD_EyE Wrote: By the way, I forgot to say, that this function is modifying the dict.
Yep, missed that too - though I inadvertently avoided that.

As about the stack - I loved the technique and I gonna for sure try it (learned some new trick today Smile ), just in this case it's a redundant overhead.
Test everything in a Python shell (iPython, Azure Notebook, etc.)
  • Someone gave you an advice you liked? Test it - maybe the advice was actually bad.
  • Someone gave you an advice you think is bad? Test it before arguing - maybe it was good.
  • You posted a claim that something you did not test works? Be prepared to eat your hat.
Reply
#7
Volcano63 and DeaD_EYE - thank you!

Volcano63 - recursive solution:
Thank you for pointing out that I need to recurse only through two keys. Your helper/accumulator solution is easier to follow than what I wrote. It's so simple, I am envious at how you did that!
I like how you used recursive function within a function to keep everything in one place.

DeaD_EYE - iterative solution:
Stack is a nifty idea and it took me some time to understand purpose of 'continue' keyword but now I see what it does.
It is great to see an iterative solution to this problem! Admittedly, I prefer this solution as I get a case of anxiety whenever I see recursion.

You've both have gone truly above and beyond to help me understand a different approaches to solving this problem (including follow up posts on modifying dictionary in-place). Thank you again.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  need to compare 2 values in a nested dictionary jss 2 796 Nov-30-2023, 03:17 PM
Last Post: Pedroski55
  Json filter is not capturing desired key/element mrapple2020 1 1,073 Nov-24-2022, 09:22 AM
Last Post: ibreeden
  how can I display only desired items? 3lnyn0 5 1,973 Dec-25-2021, 06:49 PM
Last Post: menator01
  Nested dictionary acting strange Pedroski55 2 2,054 May-13-2021, 10:37 PM
Last Post: Pedroski55
  format the output from a nested dictionary. nostradamus64 9 4,424 May-03-2021, 04:45 PM
Last Post: nostradamus64
Lightbulb Python Nested Dictionary michaelserra 2 2,560 Apr-18-2021, 07:54 AM
Last Post: michaelserra
  ERROR: importing desired module mbgamer28 0 1,648 Apr-05-2021, 07:46 PM
Last Post: mbgamer28
  Not rounding to desired decimal places? pprod 2 2,503 Mar-05-2021, 11:11 AM
Last Post: pprod
  Why this code not getting desired output ? MDRI 2 2,485 Sep-18-2020, 02:11 AM
Last Post: MDRI
  JupyterLab Dictionary Content Output Format Ourkid123uk 0 1,279 Sep-04-2020, 02:18 PM
Last Post: Ourkid123uk

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020