Generate edge list from from nested dictionary

Question

Below is the tree as a dictionary:

output_dict = { 'Sort': [ { 'Aggregate': [ { 'Hash Join': [{ 'Hash Join': [ { 'Sequential Scan': [ ] }, { 'Hash': [ { 'Sequential Scan': [ ] } ] } ] },{ 'Hash': [ { 'Sequential Scan': [ ] } ] } ] } ] } ] }

I would like to transform the above data into a networkx compatible format. Preferably in the edge list format.

I.E.

('Sort', 'Aggregrate')
('Aggregrate', 'Hash Join'))

I have tried using a BFS template but with no success Appreciate any help given thanks

I'm not totally sure I understand what the format of the original structure is, is each key a node in a graph and the value a list of dictionaries where each element has exactly one key of the same format (node to other nodes)? Also you say tree but the keys 'Sequential Scan' and 'Hash' appears multiple times — Tadhg McDonald-Jensen, Nov 08 '21 at 16:03

Ajax1234 · Answer 1 · 2021-11-08T16:16:23.163

You can use a recursive generator function:

output_dict = { 'Sort': [ { 'Aggregate': [ { 'Hash Join': [{ 'Hash Join': [ { 'Sequential Scan': [ ] }, { 'Hash': [ { 'Sequential Scan': [ ] } ] } ] },{ 'Hash': [ { 'Sequential Scan': [ ] } ] } ] } ] } ] }
def edges(d, p=None):
   for a, b in d.items():
      if p is not None: 
         yield (p,a)
      yield from (j for k in b for j in edges(k, p=a))

print(list(edges(output_dict)))

Output:

[('Sort', 'Aggregate'), ('Aggregate', 'Hash Join'), ('Hash Join', 'Hash Join'), ('Hash Join', 'Sequential Scan'), ('Hash Join', 'Hash'), ('Hash', 'Sequential Scan'), ('Hash Join', 'Hash'), ('Hash', 'Sequential Scan')]

score 1 · Answer 2 · answered Nov 08 '21 at 16:06

You could use a simple DFS like traversal through the nested dictionary:

def edge_list(dictionary):
    if not dictionary:
        return []
    edges = []
    for root in dictionary:
        if dictionary[root]:
            for children in dictionary[root]:
                edges.extend((root, child) for child in children)  # add direct child links
                edges.extend(edge_list(children))  # recursive call
    return edges


print(edge_list(output_dict))

Output:

[('Sort', 'Aggregate'), ('Aggregate', 'Hash Join'), ('Hash Join', 'Hash Join'), ('Hash Join', 'Sequential Scan'), ('Hash Join', 'Hash'), ('Hash', 'Sequential Scan'), ('Hash Join', 'Hash'), ('Hash', 'Sequential Scan')]

I think this might be what you want.

Thanks @rdas tested and works great – hongjun Nov 08 '21 at 16:13 — hongjun, Nov 08 '21 at 16:13

score 0 · Answer 3 · answered Nov 08 '21 at 20:21

The data format is kind of annoying with all the nested lists, really you could combine all the dictionaries in every list of yours, so I'd logically split up the function to work on a list and the name of the current node since the looping is a little easier to communicate:

def edges_from_node_and_children(root, list_of_children):
    for UNNECESSARILY_NESTED_DICT in list_of_children:
      for child, further_children in UNNECESSARILY_NESTED_DICT.items():
        # for each child produce the link between the root and this child
        yield (root, child)
        # as well as all links from the child further down
        yield from edges_from_node_and_children(child, further_children)
        
def edges(d):
    for node,children in d.items():
        yield from edges_from_node_and_children(node,children)

Then if you wanted to streamline the iterators with itertools you could use chain.from_iterable and starmap to cut out most of the loops:

import itertools
from typing import Dict,List
List_of_children_type = List[Dict[str, 'List_of_children_type']]

def edges_from_node_and_children(root:str, children: List_of_children_type):
    #for TEMP in children:
    # for child, further_children in TEMP.items():
    ## or equivelent chain iterator loop
    for child, further_children in itertools.chain.from_iterable(map(dict.items, children)):
        # for each child produce the link between the root and this child
        yield (root, child)
        # as well as all links from the child further down
        yield from edges_from_node_and_children(child, further_children)
        
def edges(d):
    return itertools.chain.from_iterable(itertools.starmap(edges_from_node_and_children, d.items()))
    ## or equivelently
    #for node,children in d.items():
    #    yield from edges_from_node_and_children(node,children)

# this has the same structure as your list but the elements are all unique so I could properly test it
output_dict = {
    'A': [
        { 'B': [
            { 'C': [
                { 'D1': [
                    { 'E1': [ ] },
                    { 'E2': [
                        { 'F': [ ] }
                ]}]},
                { 'D2': [
                    { 'Z': [ ] }
    ]}]}]}]}

# or print(list(edges(output_dict)))
print(*edges(output_dict), sep="\n")

Can I find out what would be the best way to add a suffix at the end of each duplicate? i.e. D1, E1 .. — hongjun, Nov 09 '21 at 04:15
you could try my `traverse` function from [here](https://stackoverflow.com/questions/36579996/python-loop-through-all-nested-key-value-pairs-created-by-xmltodict/36582214#36582214) to just generate all the lowest level leaves, might come in handy and would be more generalized, otherwise you can just tag on something to `root` or `child` in the `yield (root,child)` statement — Tadhg McDonald-Jensen, Nov 09 '21 at 04:42

Generate edge list from from nested dictionary

3 Answers3