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
}
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:
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.