Convert flat array of persons into nested pedigree tree in JavaScript

user_5457222 0
Viewed 85

I'm trying to transform a flat list of persons into a structured tree of ancestry.

The source array of persons looks like this:

const list = [
    {
        id: 1,
        name: 'John',
        akin: true,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [2]
    },
    {
        id: 2,
        name: 'Maria',
        akin: false,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [1]
    },
    {
        id: 3,
        name: 'Steven',
        akin: true,
        fatherId: 1,
        motherId: 2,
        partnerIds: [4, 5]
    },
    {
        id: 4,
        name: 'Stella',
        akin: false,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [3]
    },
    {
        id: 5,
        name: 'Laura',
        akin: false,
        motherId: undefined,
        fatherId: undefined,
        partnerIds: [3]
    },
    {
        id: 5,
        name: 'Solomon',
        akin: true,
        motherId: 4,
        fatherId: 3,
        partnerIds: []
    },
    {
        id: 6,
        name: 'Henry',
        akin: true,
        fatherId: 3,
        motherId: 5,
        partnerIds: []
    }
]

It can contain n generations of people whose direct ancestors are defined by their respective fatherId and motherId. Unknown parents (oldest known ancestor, or related only by partnership) are simply undefined. Partnerships are indicated by an array of partnerIds.

The expected output should look like this:

const pedigree = [
    {
        id: 1,
        name: 'John',
        partnerships: [
            {
                partner: {
                    id: 2,
                    name: 'Maria',
                },
                children: [
                    {
                        id: 3,
                        name: 'Steven',
                        partnerships: [
                            {
                                partner: {
                                    id: 4,
                                    name: 'Stella',
                                },
                                children: [
                                    {
                                        id: 5,
                                        name: 'Solomon'
                                    }
                                ]
                            },
                            {
                                partner: {
                                    id: 5,
                                    name: 'Laura',
                                },
                                children: [
                                    {
                                        id: 6,
                                        name: 'Henry',
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

Visually the result would look like this: Visual pedigree The desired output format is not intended for storing, but for easier visualization and processing for later rendering.

I tried to loop over the flat list, create a hashTable for referencing the single persons and then find partners and common children. My issue is though that my approach only works for two generations, or one level of nesting, although I need it to be suitable for n generations. I think I need some recursive function or way of starting to loop up from the bottom of ancestry somehow, but I can't figure out a smart way.

I'd be glad for any suggestions or tips!

EDIT: This is what I've tried:

const createPedigree = (dataset) => {
    const hashTable = Object.create(null)
    dataset.forEach(
        (person) => (hashTable[person.id] = { ...person, partnerships: [] })
    )
    const dataTree = []
    dataset.forEach((person) => {
        if (person.akin) {
            if (person.partnerIds.length) {
                person.partnerIds.forEach((partnerId) => {
                    hashTable[person.id].partnerships.push({
                        partner: { ...dataset.find((p) => p.id === partnerId) },
                        children: []
                    })
                })
            }
        }
        dataTree.push(hashTable[person.id])
    })
    dataset.forEach((child) => {
        // fill partnerships with children
        if (child.fatherId && child.motherId) {
            if (
                hashTable[child.fatherId].akin &&
                hashTable[child.fatherId].partnerships.length
            ) {
                let mother = hashTable[child.fatherId].partnerships.find(
                    (partnership) => {
                        return partnership.partner.id === child.motherId
                    }
                )
                mother.children.push(child)
            } else if (hashTable[child.motherId].akin) {
                let father = hashTable[child.motherId].partnerships.find(
                    (partnership) => {
                        return partnership.partner.id === child.fatherId
                    }
                )
                father.children.push(child)
                
            }
        }
    })
    return dataTree
}
hierarchy tree recursion arrays javascript
1 Answers

You are correct in the assumption that a general solution will involve some recursive calls (or a queue of candidates to expand until the queue is empty).

The output structure levels alternate between:

  1. a person with partnerships
  2. partnerships that contain a partner and children (each child is then again a 1.)

To make things simpler we can just model the 2 steps above with 2 separate functions. I chose the names expandPerson and expandPartnership.

const expandPerson = (personId, dataset) => {
    // we get the person from the dataset by their id
    const personData = dataset.find(p => p.id == personId)
    // we clone only the data that we want in the output
    const person = { id: personData.id, name: personData.name }

    // all partnerIds of this person need to become their parnerships
    // so we just map them to an "expanded partnership" (step 2.)
    person.partnerships = personData.partnerIds
       .map(partnerId => expandPartnership(partnerId, person.id, dataset))

    // we return the "expanded" person
    return person
}

const expandPartnership = (partner1Id, partner2Id, dataset) => {
    // we get the partner from the dataset by their id
    const partnerData = dataset.find(p => p.id == partner1Id)
    // we clone only the data that we want in the output
    const partner = { id: partnerData.id, name: partnerData.name }

    // all people in the dataset, whose parents are partner1Id
    // and pertner2Id are the children
    const children = dataset
      .filter(p => p.motherId == partner1Id && p.fatherId == partner2Id
        || p.motherId == partner2Id && p.fatherId == partner1Id)
      // we map each child as an "expanded person" again (back to step 1.)
      .map(p => expandPerson(p.id, dataset))

    // we return the "expanded" partnership
    return { partner, children }
}

In the code you then just call const pedigree = expandPerson(1, list)

If the root is not always id: 1 just find the root id first

const rootId = list.find(p => p.akin && !p.fatherId && !p.motherId).id
const pedigree = expandPerson(rootId, list)

Note: you have a duplicate id (id: 5) in the provided input. You have to fix that.

user_24222240
Related