Как посчитать потомков по нескольким родительским узлам?

Question

Таким образом, приведены следующие данные, где функция представляет [id, name,age,parent 1 id,parent 2 id].

[[0,'john',12,3,4],[1,'rachel',25,3,4],[2,'carol',10,1,5], [3, 'maggie',40,,], [4,'peter',50,,],[5,'mike',30,,]

Как мне узнать количество потомков Петра? Так что должно быть 3, так как Рэйчел, Джон и Кэрол - потомки.

Каков наилучший способ приблизиться к этому в python. Я думал о древовидной структуре данных, но я не совсем понимаю, как ее реализовать.

Мой подход состоял в том, чтобы использовать хэш-карту следующим образом:

hmap = {}
for i in range(1,len(data)):
    for j in range(1,len(data)):
        if data[i][0] == data[j][3] or data[i][0] == data[j][4]:
            if data[i][1] in hmap:
                hmap[data[i][1]] +=1
            else:
                hmap[data[i][1]] =1
            print(data[i][1], data[j][1])

Но это только дало бы детям. Тогда мне нужно было бы добавить детей детей.

Любое руководство будет оценено.

Answer 1

В идеале я бы порекомендовал использовать отдельную таблицу SQL с is_checked в качестве логического значения и длинной итерацией.Тем не менее, вы можете попробовать это с двойной list структурой, а именно list_id_to_check и list_id_checked:

def find_descendants(parent_id, persons):
    list_id_to_check = [parent_id]
    list_id_checked = []
    list_descendant_ids = []
    while True:
        if not list_id_to_check:
            break
        for id_to_check in list_id_to_check:
            for person in persons: 
                if id_to_check in person[-2:]:
                    if person[0] not in list_descendant_ids:
                        list_descendant_ids.append(person[0])
                    if person[0] not in list_id_checked and person[0] not in list_id_to_check:
                        list_id_to_check.append(person[0])
            list_id_to_check.remove(id_to_check)
            list_id_checked.append(id_to_check)
            continue
    return list_descendant_ids