cancel
Showing results for 
Search instead for 
Did you mean: 
Reply
Highlighted
JVos Frequent Visitor
Frequent Visitor

Recursive query to derive indirect relationships

I have a table with direct relations between so-called 'routings' (let's say: process steps). Now I want to derive all indirect relations. For example when routing 1 directly preceeds 2, 2 directly preceeds 3, 3 directly preceeds 4, then 1 INdirectly preceeds 3 and 4 and 2 INdirectly preceeds 4. I use Power Query within Excel 2016.

 

Example table with direct relations:

FromToRelationType
12Direct
13Direct
24Direct
35Direct
56Direct
67Direct
68

Direct

 

And this is what the result should be (so comprising direct and indirect relations):

FromToRelationType
12Direct
13Direct
24Direct
35Direct
56Direct
14Indirect
15Indirect
16Indirect
17Indirect
18Indirect
36Indirect
37Indirect
38Indirect
57Indirect
58Indirect

 

This is how I want to derive all indirect relationships:

1. Start with routings that aren't present in the To column (they're at the start of a chain of routings) (level 1);

2. Determine their successors (level 2);

3. Determine the successors of those successors (level 3);

4. Set indirect relationships between predecessors and successors of level 2;

5. Take routings of level 2 as level 1 and perform steps 1 to 4 again. This until the result of step 3 is empty (ends of chains are reached).

 

I am trying to create a custom recursive function for this, but it's a hard job. How could this best be solved?

6 REPLIES 6
Nolock Member
Member

Re: Recursive query to derive indirect relationships

Hi @JVos,

I've written the recursive part of the task and you have now a list of all descendent for every row.
Unfortunately I can't finish it now because of time pressure. I'll continue tomorrow if you don't finish it by yourself till then.

 

EDIT: The working solution with comments. It creates a list of all descendents for every row and then merges the result with the origin table.

 
 
let
    Source = Table.FromRows(Json.Document(Binary.Decompress(Binary.FromText("i45WMlTSUTICYpfMotTkEqVYHYiQMaoQSIUJqhBIhSmqEIhrhioE4ppjClkgCcUCAA==", BinaryEncoding.Base64), Compression.Deflate)), let _t = ((type text) meta [Serialized.Text = true]) in type table [From = _t, To = _t, RelationType = _t]),
    ChangedType = Table.TransformColumnTypes(Source,{{"From", Int64.Type}, {"To", Int64.Type}, {"RelationType", type text}}),

    // get list of all descendants
    fnTransitiveRelationList = (sourceTbl as table, curToBeDoneList as list) as list =>
        let
            curNumber = List.First(curToBeDoneList),
            rowsStartingWithCurNumber = Table.SelectRows(sourceTbl, each [From] = curNumber),

            result =
                if Table.IsEmpty(rowsStartingWithCurNumber) and List.IsEmpty(curToBeDoneList) then
                    {}
                else
                    let 
                        toList = Table.Column(rowsStartingWithCurNumber, "To"),

                        nextToBeDoneList = List.Distinct(
                            List.Combine(
                                {
                                    List.RemoveFirstN(curToBeDoneList, 1), 
                                    toList
                                }
                            )
                        ),
                        recursiveResultList = @fnTransitiveRelationList(sourceTbl, nextToBeDoneList),

                        curRecursiveResultList = List.Distinct(
                            List.Combine(
                                {
                                    toList, 
                                    recursiveResultList
                                }
                            )
                        )
                    in
                        curRecursiveResultList
        in
            result,

    // create a table from all descendants with a from column and relation type = indirect
    fnTransitiveRelationTable = (sourceTbl as table, from as number) as table =>
        let
            recursiveList = fnTransitiveRelationList(sourceTbl, {from}),
            recordList = List.Transform(recursiveList, each [From = from, To = _, RelationType = "Indirect"]),
            result = Table.FromRecords(recordList)
        in
            result,

    // add a column TableOfDescendants
    TableOfDescendents = Table.AddColumn(ChangedType, "TableOfDescendents", each fnTransitiveRelationTable(ChangedType, [From])),

    // combine input table with new descendants
    TableOfAllDescentantsTables = Table.Combine({ChangedType, Table.Combine(TableOfDescendents[TableOfDescendents])}),
    // distinct on columns From and To
    Result = Table.Distinct(TableOfAllDescentantsTables, {"From", "To"})
in
    Result
 

 

 

JVos Frequent Visitor
Frequent Visitor

Re: Recursive query to derive indirect relationships

Hi @Nolock: Thank you for your solution. In the meantime I figured out a solution by myself, but it's very resource / time consuming when there are more than 5 iterations. I am going to try you solution next week.

JVos Frequent Visitor
Frequent Visitor

Re: Recursive query to derive indirect relationships

Hi @Nolock: in the basis, I get your solution to work in my Excel file. Two things:

 

1. Can you shortly explain how you created the Base64 string that is present in your code?

 

2. With the real data - above I gave a simple example - the query function is running endless. This is maybe because the relations aren't strict transitve. For example:

 

FromToRelationType
6779Direct
7969Direct
7971Direct
7172Direct
7273Direct
6794Direct
9495Direct
9596Direct

 

Two paths to get from 67 to 71:

67 => 79 => 71

67 => 94 => 95 => 96 => 71

 

Note that in this real example there are no loops defined. However I need also to cope with such situations.

 

I am going to try to find a solution building on the code you provided. But if you quickly know how to solve this, I am pleased with your help.

JVos Frequent Visitor
Frequent Visitor

Re: Recursive query to derive indirect relationships

@Nolock: The duplicate paths to get from 67 to 71 aren't the problem, I found already. I am going to investigate now my complete set with data what might be the problem (probably a loop).

 

Problem is indeed a loop in the from-to's, e.g. 76 > 77 and 77 > 76.

JVos Frequent Visitor
Frequent Visitor

Re: Recursive query to derive indirect relationships

@Nolock: I worked out the solution to prevent endless loops. In short: the 'froms' that are already done, are remember in a list and not offered to be done in a next recursion. At the end of the query self-referencing transitions are removed.

 

let
    Source = Excel.CurrentWorkbook(),
    tmpInput = Source{[Name="tmpInput"]}[Content],
    ChangedType = Table.TransformColumnTypes(tmpInput,{{"From", Int64.Type}, {"To", Int64.Type}, {"RelationType", type text}}),

    // get list of all descendants
    fnTransitiveRelationList = (sourceTbl as table, curToBeDoneList as list, alreadyDoneList as list) as list =>
        let
            curNumber = List.First(curToBeDoneList),
            rowsStartingWithCurNumber = Table.SelectRows(sourceTbl, each [From] = curNumber),
            alreadyDoneList = List.Combine({alreadyDoneList, {curNumber}}),

            result =
                if Table.IsEmpty(rowsStartingWithCurNumber) and List.IsEmpty(curToBeDoneList) then
                    {}
                else
                    let 
                        toList = Table.Column(rowsStartingWithCurNumber, "To"),

                        nextToBeDoneList = List.Distinct(
                            List.Combine(
                                {
                                    List.RemoveFirstN(curToBeDoneList, 1), 
                                    toList
                                }
                            )
                        ),
                        nextToBeDoneListNoAlreadyDone = List.Difference(nextToBeDoneList,alreadyDoneList),
                        recursiveResultList = @fnTransitiveRelationList(sourceTbl, nextToBeDoneListNoAlreadyDone, alreadyDoneList),

                        curRecursiveResultList = List.Distinct(
                            List.Combine(
                                {
                                    toList, 
                                    recursiveResultList
                                }
                            )
                        )
                    in
                        curRecursiveResultList
        in
            result,

    // create a table from all descendants with a from column and relation type = indirect
    fnTransitiveRelationTable = (sourceTbl as table, from as number) as table =>
        let
            recursiveList = fnTransitiveRelationList(sourceTbl, {from},{}),
            recordList = List.Transform(recursiveList, each [From = from, To = _, RelationType = "Indirect"]),
            result = Table.FromRecords(recordList)
        in
            result,

    // add a column TableOfDescendants
    TableOfDescendents = Table.AddColumn(ChangedType, "TableOfDescendents", each fnTransitiveRelationTable(ChangedType, [From])),

    // combine input table with new descendants
    TableOfAllDescentantsTables = Table.Combine({ChangedType, Table.Combine(TableOfDescendents[TableOfDescendents])}),

    // distinct on columns From and To
    Result = Table.SelectRows(Table.Distinct(TableOfAllDescentantsTables, {"From", "To"}), each [From] <> [To])
in
    Result
Nolock Member
Member

Re: Recursive query to derive indirect relationships

You get the Base64 string when you create a table with help of PowerQuery Editor GUI via Home / External Data / Enter Data.