Power Query: get all descendants
Going the other way
Previously, I wrote a post on getting a person's chain of command, or lineage, using Power Query. Given a table of people and their managers/Jedi Masters, and starting with a given name, Power Query will find that person's manager, then that person's manager, and so on, until it finds no more. You can read about that here.
This time, I need to go the other way. Starting from one person at the top, I need to find their subordinates, then all of their subordinates, and so on, until I get no more.
Similarly as the chain of command script, the core of this one is List.Generate()
. Let's take a look.
In a non-canon galaxy...
I love Star Wars, and I grew up in a time when there was something called the Expanded Universe. With that in mind, let's start with this table as an example.
Name | Parent |
---|---|
Anakin Skywalker | Shmi Skywalker |
Luke Skywalker | Anakin Skywalker |
Leia Organa | Anakin Skywalker |
Ben Skywalker | Luke Skywalker |
Jaina Solo | Leia Organa |
Jacen Solo | Leia Organa |
Anakin Solo | Leia Organa |
Allana Solo | Jacen Solo |
Here is this table in Power Query:
Code
#table(
{"Name", "Parent" },
{
{"Anakin Skywalker", "Shmi Skywalker"},
{"Luke Skywalker", "Anakin Skywalker"},
{"Leia Organa", "Anakin Skywalker"},
{"Ben Skywalker", "Luke Skywalker"},
{"Jaina Solo", "Leia Organa"},
{"Jacen Solo", "Leia Organa"},
{"Anakin Solo", "Leia Organa"},
{"Allana Solo", "Jacen Solo"}
}
)
If I start with the name Leia Organa, I want to end up with the list:
List |
---|
Leia Organa |
Jaina Solo |
Jacen Solo |
Anakin Solo |
Allana Solo |
If I start with "Luke Skywalker", I want to get this:
List |
---|
Luke Skywalker |
Ben Skywalker |
If I start with Shmi Skywalker, then I'll end up with everyone in the family tree, which is all of her descendants.
Code
The thing that separates this task (going down a hierarchy) from the one I've done before (going up a chain of command) is the fact that we will be dealing with lists, and not single values. That is, all of a person's subordinates will be represented as a list. We have to reconcile this fact with two others:
- A person only has a single-valued name (not a list)
- a recursive function needs to have inputs and outputs that have the same type, so that it can feed into itself (in our case, our recursive function needs to take a list and return a list)
getSubordinates()
The first thing we need to do is the basic task of getting a single person's subordinates. This is a fairly easy table-filtering function.
getSubordinates = (target as text) as list =>
Table.SelectRows(
people,
each [Parent] = target
)[Name]
getAllSubordinates()
We know how to get one person's subordinates. How do we get the subordinates for a group of people? We'll basically start with a list of targets, and loop through them, calling getSubordinates()
each time. Note that this function takes a list and returns as list. This means that we can recurse this function.
Note also the application of List.Combine()
, where we flatten out the "list of lists" so that the return type is just a list.
getNextSubordinates = (targets as list) as list =>
List.Combine(
List.Transform(
targets,
each getSubordinates(_)
)
),
Recursion
The final part of this is to recurse this. As before, we'll use List.Generate()
. At the end of this, we'll end up with a list of lists, and that is why in fullchain
, we flatten it out.
Note also that the starting value in List.Generate()
is a list, because we need everything to be of list type.
chain = List.Generate(
() => targets, // starting value, as a list
each List.Count(_) <> 0, // stopping condition, when there are no more subordinates
each getNextSubordinates(_)
),
fullchain = List.Combine(chain)
Full code
The full code is here:
( startingName as text, referenceTable as table ) as list =>
let
targets = {startingName},
people = Table.Buffer(referenceTable),
// this gets all of the subordinates for one person
getSubordinates = (target as text) as list =>
Table.SelectRows(
people,
each [Parent] = target
)[Name],
// this function, given a list of names ("targets"), gets all of the subordinates for all of the people in the list of names. the input type (list) and the output type (list) need to be the same because this function will be called on recursively in List.Generate, and it needs to be able to feed itself its own output.
getNextSubordinates = (targets as list) as list =>
List.Combine(
List.Transform(
targets,
each getSubordinates(_)
)
),
chain = List.Generate(
() => targets, // starting value, as a list
each List.Count(_) <> 0, // stopping condition, when there are no more subordinates
each getNextSubordinates(_)
),
fullchain = List.Combine(chain)
in
fullchain