CODEWITHSUNDEEP
pythondata-structurestree
fynmnx
fynmnx

Reputation: 611

How to count descendants given multiple parent nodes?

So given some data as follows where the feature represents [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,,]

How would I go about finding the number of descendants that peter has? So it should be 3 since rachel, john and carol are descendants.

What would be the best way to approach this in python. I was thinking of a tree data structure but I'm confused as in how to implement it.

My approach was to use a hashmap as follows:

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])

But that would just give the children. Then I would need to add the children's children.

Any guidance would be appreciated.

Upvotes: 0

Views: 194

Answers (1)

sashaboulouds
sashaboulouds

Reputation: 1854

Ideally, I would recommend to use separated SQL table, with is_checked as a Boolean value, and a long iteration. Still, you can try this, with a double list structure, namely list_id_to_check and 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

Upvotes: 1

Related Questions