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

[Anonymous]

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

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

{
1: [2, 3, 4],
2: [5],
3: [6, 9],
4: [3],
5: [3],
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], 'subgraphs': {}},
4: {'edges': ['B'], 'subgraphs': {}},
'A': {'edges': ['B'],
'subgraphs': {'AA': {'edges': [],
'subgraphs': {2: {'edges': [5], 'subgraphs': {}},
5: {'edges': [], 'subgraphs': {}}}}}},
'B': {'edges': [],
'subgraphs': {3: {'edges': ['BA', 'BB'], 'subgraphs': {}},
'BA': {'edges': [],
'subgraphs': {6: {'edges': [7, 8], 'subgraphs': {}},
7: {'edges': [], 'subgraphs': {}},
8: {'edges': [], 'subgraphs': {}}}},
'BB': {'edges': [],
'subgraphs': {9: {'edges': [], 'subgraphs': {}}}}}}}

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

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