Convert list of graph edges to JSON tree

Question

I have a list of tuples with edges from networkx which are guaranteed to be tree-like:

[('king', 'governor'),
 ('governor', 'editor'),
 ('king', 'state'),
 ('state', 'collapse'),
 ('collapse', 'coverage'),
 ('collapse', 'author'),
 ('collapse', 'opening'),
 ('state', 'head'),
 ('state', 'lord')]

These are sorted in a depth-first search order, but could just as easily be sorted in breadth-first order if that would make this easier.

I'm looking for a way to convert this list of edges, to a JSON object. The previous example would become:

{'king': [{'governor': [{'editor': []}]},
          {'state': [{'collapse': [{'coverage': []},
                                   {'author': []},
                                   {'opening': []}]},
                     {'head': []},
                     {'lord': []}]
           }]
}

Whether the leaf nodes should be represented as a dict as in the example output, or simply as strings, is up to you. If there is an easier way to do this using a networkx.DiGraph than its list of edges, that would work just as well.

Any help is appreciated.

Answer 1

import json                                                                                                                                                                                                        

data = [('king', 'governor'),                                                                                                                                                                                      
        ('governor', 'editor'),                                                                                                                                                                                    
        ('king', 'state'),                                                                                                                                                                                         
        ('state', 'collapse'),                                                                                                                                                                                     
        ('collapse', 'coverage'),                                                                                                                                                                                  
        ('collapse', 'author'),                                                                                                                                                                                    
        ('collapse', 'opening'),                                                                                                                                                                                   
        ('state', 'head'),                                                                                                                                                                                         
        ('state', 'lord')];                                                                                                                                                                                        

root = data[0][0]                                                                                                                                                                                                  
node2chilren = {root: []}                                                                                                                                                                                          
for parent, child in data:                                                                                                                                                                                         
    childnode = {child: []}                                                                                                                                                                                        
    children = node2chilren[parent]                                                                                                                                                                                
    children.append(childnode)                                                                                                                                                                                     
    node2chilren[child] = childnode[child]                                                                                                                                                                         

jsonstr = json.dumps({root: node2chilren[root]}, indent=4)                                                                                                                                                         
print jsonstr

outputs

{
    "king": [
        {
            "governor": [
                {
                    "editor": []
                }
            ]
        }, 
        {
            "state": [
                {
                    "collapse": [
                        {
                            "coverage": []
                        }, 
                        {
                            "author": []
                        }, 
                        {
                            "opening": []
                        }
                    ]
                }, 
                {
                    "head": []
                }, 
                {
                    "lord": []
                }
            ]
        }
    ]
}