Как построить вложенный список смежности из списка смежности и иерархии? ⇐ Python

[Anonymous]

У меня есть простое представление списка смежности такого графика < /p>

Код: Выделить всё

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

, который выглядит так, что

Но у каждого узла также есть «тип экологически Иерархия, присутствующая в списке смежности выше. Например, это сообщило бы нам, что «узел 6 имеет тип« ba », а все узлы типа« ba »типа 'b'». < /P>
Например, рассмотрим это происхождение: < /p>

Код: Выделить всё

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

, который при визуализировании будет выглядеть так, как это

, что я хочу создавать программно -то, что я хочу, что я хочу, что это будет следующему. Основная идея состоит в том, чтобы представить поддерев для каждого ключа в списке смежности (вместе с полем «/код»), которое, в свою очередь, будет содержать свой собственный список смежности и т. Д. (Рекурсивно).

Код: Выделить всё

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

Что такое элегантный способ преобразования исходного списка смежности + отдельная карта «Ancestry» для создания такой структуры данных?

Подробнее здесь: https://stackoverflow.com/questions/795 ... -hierarchy