Как отсортировать иерархический список в дереве/пиримидной модели dicts?

Question

Я пытаюсь создать иерархию dicts для использования для создания модели дерева в Qt.

Данные в списке с каждой записью будучи [Следующая одноуровневый, предыдущий родственный, First_Child, Родитель] и индекс элемента в списке имя/индекс контура, описанного в иерархии записи.

Например, если бы я, чтобы ввести иерархию из раздела 4.RETR_TREE here

hierarchy = 
    array([[[ 7, -1, 1, -1], 
      [-1, -1, 2, 0], 
      [-1, -1, 3, 1], 
      [-1, -1, 4, 2], 
      [-1, -1, 5, 3], 
      [ 6, -1, -1, 4], 
      [-1, 5, -1, 4], 
      [ 8, 0, -1, -1], 
      [-1, 7, -1, -1]]]) 

Я хотел бы получить этот результат:

{0:{1:{2:{3:{4:{5:{},6:{}}}}}}, 
7:{}, 
8:{}} 

Я ищу, чтобы сделать это, чтобы построить дерева в Qt, поэтому я могу легко видеть, какие контуры содержат другие. Если у вас есть лучшее представление о том, как преобразовать данные иерархии в модель дерева Qt, которые также будут оценены.

Заранее благодарен!

Answer 1

Подобно @uselpa Иду с раствором, который не сортировать узлы, имеющие один и тот же родительский узел, так как словарь Python не имеет фиксированного порядка:

import numpy as np 
H = np.array(
    [[ 7, -1, 1, -1], 
    [-1, -1, 2, 0], 
    [-1, -1, 3, 1], 
    [-1, -1, 4, 2], 
    [-1, -1, 5, 3], 
    [ 6, -1, -1, 4], 
    [-1, 5, -1, 4], 
    [ 8, 0, -1, -1], 
    [-1, 7, -1, -1]]) 

def T(i): 
    children = [(h, j) for j, h in enumerate(H) if h[3] == i] 
    children.sort(key = lambda h: h[0][1]) 
    return {c[1]: T(c[1]) for c in children} 

print T(-1) 

Выход:

{0: {1: {2: {3: {4: {5: {}, 6: {}}}}}}, 8: {}, 7: {}} 

Таким образом, вы можете пропустить сортировку детей и в конечном итоге со следующим компактным кодом:

T = lambda i: {j: T(j) for j, h in enumerate(H) if h[3] == i} 
print T(-1) 

Answer 2

Я не знаком с Qt, numpy или opencv, поэтому мне, вероятно, что-то не хватает, но я все равно попробую.

Следующий алгоритм создает словарь по запросу:

def make_hdict(hier): 
    def recur(parent): 
     res = {} 
     for i,n in enumerate(hier): 
      if n[3] == parent: 
       res[i] = recur(i) 
     return res 
    return recur(-1) 

Тестирование:

hierarchy = [[ 7, -1, 1, -1], #0 
      [-1, -1, 2, 0], #1 
      [-1, -1, 3, 1], #2 
      [-1, -1, 4, 2], #3 
      [-1, -1, 5, 3], #4 
      [ 6, -1, -1, 4], #5 
      [-1, 5, -1, 4], #6 
      [ 8, 0, -1, -1], #7 
      [-1, 7, -1, -1]] #8  
print(make_hdict(hierarchy)) 
=> {0: {1: {2: {3: {4: {5: {}, 6: {}}}}}}, 8: {}, 7: {}} 

Как вы можете видеть, я использую только последнее поле ("Родитель") в этой точке. В частности,

1. Я не использую «следующие родственный» и «предыдущие родственный» поскольку словарь неупорядоченного
2. Я не использую «первый ребенок», поскольку она является избыточной информацией.

Это то, что вы хотите?