Python Forum

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)

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')]

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.

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 . Fixed to spec

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.

(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 ), just in this case it's a redundant overhead.

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.