# Data Science at FMP: Tree Structure Analysis

DevFeed: [Data Science at FMP: Tree Structure Analysis](<https://devfeed.tech/articles/data-science-at-fmp-tree-structure-analysis-19743.md>)

Original publisher: [Read original article](<https://tech.findmypast.com/datsci-tree-structure-analysis/>)

Author: David Lack

Published: 2022-08-09T00:00:00Z

Content type: tutorial

Language: en

Sources: [Findmypast](<https://devfeed.tech/sources/findmypast.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [data](<https://devfeed.tech/topics/data.md>), [Data Science](<https://devfeed.tech/topics/data-science.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [data](<https://devfeed.tech/tags/data.md>), [data-science](<https://devfeed.tech/tags/data-science.md>), [graph](<https://devfeed.tech/tags/graph.md>), [product](<https://devfeed.tech/tags/product.md>), [structure](<https://devfeed.tech/tags/structure.md>)

## AI overview

The article explains how Findmypast analyzes the structure of customer family trees using directional graphs. It models people as nodes and relationships as directed edges, then uses weighted shortest-path algorithms to calculate generations and the people in each generation.

## Source excerpt

Introduction A key part of our product is the ability to build family trees on our site. To better understand how our customers are building and using the tree features we wanted to work out what sort of structure the trees generally have and answer questions like how many generations do users have? Do users follow their pedigree line, their parents, grandparents and so on or build out their other relations? Do users focus on a paternal or maternal line or both? Trees can be quite complex structures with a lot of information contained within them. For example, a small tree with just a mother, father and daughter has 3 people but multiple relations depending on how you think about it. It could have 3 simple relations: Mother and Father are linked by a married relation Mother and Daughter are linked by a child relation Father and Daughter are also linked by a child relation These relations can be expanded on to give direction information as well, in which case you end up with 6 relationships: Mother is married to Father Father is married to Mother Mother is parent of Daughter Daughter is child of Mother Father is parent of Daughter Daughter is child of Father Adding in direction information has doubled the amount of relationships in the tree and this is before including other members of the tree and adding other relationships such as sibling relationships. Analysing this complex data is a challenge, how do we work out how many generations there are? How many people are in each generation? To solve these problems we decided to use directional graphs, as this seemed the most natural way to deal with this data. In a directional graph, nodes are connected by edges with a direction. The example of the simple tree matches a graph well, each person is a node and each relationship linking people is an edge. Calculating Generation Information In order to use graphs to calculate the number of generations and the people within each generation, we need to perform a weighted short