[Python] How to build a nested adjacency list from an adjacency list and a hierarchy?

I have a simple adjacency list representation of a graph like this

{
1: [2, 3, 4],
2: [5],
3: [6, 9]
4: [],
5: [],
6: [7, 8],
7: [],
8: [],
9: []
}


which looks like this



But each node also has a "type ancestry" which tells us what "type" of node it is, and this is completely different from the hierarchy present in the adjacency list above. For example, it would tell us that "node 6 is of type 'C', and all type 'C' nodes are type 'D'".

For example, consider this ancestry:

{
1: [], # no ancestry
2: ['A'],
3: ['B'],
4: [],
5: ['A'],
6: ['C', 'B'], # Read this as "6 is a type C node, and all type C nodes are type B nodes"
7: ['C', 'B'],
8: ['C', 'B'],
9: ['D']
}


which when visualized would look like this



So what I want to produce programmatically is a "hierarchical/nested" adjacency list which would look like below. The main idea is to introduce a subtree for each key in the adjacency list (along with the edges field), which would in turn contain its own adjacency list and so forth (recursively).

{
1: {
'edges': ['A', 'B', 4],
'subgraph': {}
},
'A': {
'edges': [],
'subgraph': {
2: {
'edges': [5],
'subgraph': {}
},
5: {
'edges': [],
'subgraph': {}
}
}
},
'B': {
'edges': [],
'subgraph': {
3: {
'edges': ['C', 'D'],
'subgraph': {}
},
'C': {
'edges': [],
'subgraph': {
6: {
'edges': [7, 8],
'subgraph': {}
},
7: {
'edges': [],
'subgraph': {}
},
8: {
'edges': [],
'subgraph': {}
},
}
},
'D': {
'edges': [],
'subgraph': {
9: {
'edges': [],
'subgraph': {}
},
}
}
}
},
4: {
'edges': [],
'subgraph': {}
}
}


What is an elegant way of transforming the original adjacency list + the separate "ancestry" map to produce such a data structure?

Continue reading...