In the last few months I have been answering dozens of users’ questions. And there were at least three or four of you with different use cases but the same nominator: I have a table with two columns ...
Updated 6 years ago
Version 3.0
Blog Post
I have rewritten the algorithm. It uses an iteration instead of a recursion.
It can also handle cycles as you can see in the test data sample.
In the beginning of the code is also another data sample which shows, that it works with paths longer than 10.
let
Source = Table.FromRows(Json.Document(Binary.Decompress(Binary.FromText("Hcu5EQAwCAPBXhQT+DfUwtB/G5aV3GxymegwDJQla5jSpLq0qC1t6kiHutKlXHIqpPhvQ9UD", BinaryEncoding.Base64), Compression.Deflate)), let _t = ((type text) meta [Serialized.Text = true]) in type table [From = _t, To = _t]),
ChangedType = Table.TransformColumnTypes(Source,{{"From", type text}, {"To", type text}}),
/*
x1 = Table.FromList({1..20}, Splitter.SplitByNothing(), null, null, ExtraValues.Error),
x2 = Table.RenameColumns(x1, {"Column1", "From"}),
x3 = Table.AddColumn(x2, "To", each [From] + 1),
x4 = Table.TransformColumns(x3, {{"From", Text.From}, {"To", Text.From}}),
ChangedType = Table.TransformColumnTypes(x4,{{"From", type text}, {"To", type text}}),
*/
// buffer the source table
BufferedTable = Table.Buffer(ChangedType),
// create a distinct sorted list of From values
FromDistinctList = List.Sort(List.Distinct(Table.Column(BufferedTable, "From"))),
// get all direct descendants as a record (key-value pairs From ==> To)
DirectDescendantsRecord = List.Accumulate(
FromDistinctList,
[],
(state, current) =>
state &
Expression.Evaluate(
"[" & current & "= Table.Column(Table.SelectRows(BufferedTable, each [From] = current), ""To"")]",
[Table.Column = Table.Column, Table.SelectRows = Table.SelectRows, BufferedTable = BufferedTable, current = current]
)
),
// get a count of all nested elements
fnCountOfRecordElements = (rec as record) => List.Count(List.Combine(Record.FieldValues(rec))),
fnNextStep = (
lastStepResult as record
) as record =>
let
// get descendants of the last step
lastDescendents = lastStepResult[result],
newDescendents = List.Transform(
Record.FieldNames(lastDescendents),
(fieldName) =>
let
// last descendents of a field name
values = Record.Field(lastDescendents, fieldName),
// for all last descendents get their descendents
newIndirectDescendents = List.Combine(
List.Transform(
values,
(value) => Record.FieldOrDefault(lastDescendents, value, {})
)
),
// remove descendents which we have already visited (cares of cycles)
removeAlreadyVisited = List.RemoveItems(newIndirectDescendents, values),
// combine old and new descendents
allDescendants = List.Distinct(
List.Combine({values, removeAlreadyVisited})
),
// create a record of field name and all its descendants
result = Expression.Evaluate("[" & fieldName & "=allDescendants]", [allDescendants = allDescendants])
in
result
),
// create a new descendents record as a combination of all till now found descendents
combinedRecord = Record.Combine(newDescendents)
in
[
result = combinedRecord,
countOfRecordElements = fnCountOfRecordElements(combinedRecord),
lastCountOfRecordElements = lastStepResult[countOfRecordElements]
],
// get a list of all descendants (iteration)
fnTransitiveRelationList = (
directDescendantsRecord as record
) as table =>
let
// iterate until 2 following each other iterations have the same count of elements
whileTrue =
List.Generate(
// init
() =>
[
// all descendants found till now
result = directDescendantsRecord,
// count of all nested elements
countOfRecordElements = fnCountOfRecordElements(directDescendantsRecord),
// count of last all nested elements
lastCountOfRecordElements = -1
],
// do while counts of all nested elements are different
(current) => current[lastCountOfRecordElements] <> current[countOfRecordElements],
// calculate next step
(last) => fnNextStep(last)
),
// get last item of the list (the list contains all iterations of the algorithm)
lastItem = List.Last(whileTrue),
// get property result
combinedRecord = lastItem[result],
// create a table
toTable = Record.ToTable(combinedRecord),
// concat values
combineDescendants = Table.TransformColumns(toTable, {{"Value", each Text.Combine(_, ";")}})
in
combineDescendants,
// get recursive all descendants of current value
TransitiveClosure = fnTransitiveRelationList(DirectDescendantsRecord)
in
TransitiveClosure