# Tree edge list expansion **URL:** \ **Category:** Articles\ **Created:** [February 20, 2026, 5:03pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570 "2026-02-20T17:03:29Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![Sir-McNeil](https://community.easymorph.com/letter_avatar_proxy/v4/letter/s/57b2e6/32.png) [@Sir-McNeil](https://community.easymorph.com/u/Sir-McNeil)\ **Post date:** [February 20, 2026, 5:03pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/1 "2026-02-20T17:03:29Z")
As part of several projects, I need to expand a tree structure, e.g.: - node 0 - node 1 - node 2 - node 4 - node 5 - node 3 - node 6 - node 7 I use the following terminology: - **root node** : node without parent (0) - **internal node** : node with parent and child(ren) (2, 3, 6) - **leaf node** : node without a child (1, 4, 5, 7) The tree structure is a deliberate and mostly accurate simplification: in some cases, the structure is actually a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) (DAG), and in other cases, there's not one single tree but a forest. # input _EDITED based on tesing using the Hierarchy path action:_ - _added root nodes as child with empty parent_ - _added a test case for a singleton tree_ - _added a test case for multiple trees (a forest)_ - _added a test case for directed acyclic graphs_ The tree structure is represented by an edge list, e.g.: | parent | child | | --- | --- | | | 0 | | 0 | 1 | | 0 | 2 | | 0 | 3 | | 2 | 4 | | 2 | 5 | | 3 | 6 | | 6 | 7 | A single, parentless, childless node is added to the test data to test how the flow deals with multiple roots (a forest instead of a single tree), and to test how the flow deals with singleton trees. | parent | child | | --- | --- | | | 8 | A simple "diamond" structure is added to the test data to test how the flow deals with directed acyclic graphs (trees in which nodes may have more than one parent). | parent | child | | --- | --- | | | 9 | | 9 | 10 | | 9 | 11 | | 10 | 12 | | 11 | 12 | # output _EDITED to reflect added test cases (see **input** above), and changed the desired output to more closely align with that of the Hierarchy path action._ The output may come in two shapes: - paths - reachability pairs and which rows get included in the output is determined by the use case. Options: 1. where should paths start/end? - only from root nodes? - only to leaf nodes - only to/from specific nodes? 2. should partial paths be included? 3. should the path from a node to itself be included? The below table shows what the output would look like for questions 2 and 3 (3 is always a subset of 2: a self-path is necessarily a partial path). Question 1 is a matter of choosing specific ancestors and descendants. | ancestor | path | descendant | | 2. | 3. | | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | | x | x | | 0 | 0|1 | 1 | | | | | 0 | 0|2 | 2 | | x | | | 0 | 0|2|4 | 4 | | | | | 0 | 0|2|5 | 5 | | | | | 0 | 0|3 | 3 | | x | | | 0 | 0|3|6 | 6 | | x | | | 0 | 0|3|6|7 | 7 | | | | | 1 | 1 | 1 | | x | x | | 2 | 2 | 2 | | x | x | | 2 | 2|4 | 4 | | x | | | 2 | 2|5 | 5 | | x | | | 3 | 3 | 3 | | x | x | | 3 | 3|6 | 6 | | x | | | 3 | 3|6|7 | 7 | | x | | | 4 | 4 | 4 | | x | x | | 5 | 5 | 5 | | x | x | | 6 | 6 | 6 | | x | x | | 6 | 6|7 | 7 | | x | | | 7 | 7 | 7 | | x | x | | 8 | 8 | 8 | | x | x | | 9 | 9 | 9 | | x | x | | 9 | 9|10 | 10 | | x | | | 9\* | 9|10|12 | 12\* | | | | | 9 | 9|11 | 11 | | x | | | 9\* | 9|11|12 | 12\* | | | | | 10 | 10 | 10 | | x | x | | 10 | 10|12 | 12 | | x | | | 11 | 11 | 11 | | x | x | | 11 | 11|12 | 12 | | x | | | 12 | 12 | 12 | | x | x | \* reachability pairs should not be duplicated, even if multiple paths exist ---
**Author:** ![dgudkov](https://community.easymorph.com/user_avatar/community.easymorph.com/dgudkov/32/5_2.png) [@dgudkov](https://community.easymorph.com/u/dgudkov)\ **Post date:** [February 20, 2026, 5:07pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/2 "2026-02-20T17:07:17Z")
Hi Laurens, Did you check [the "Hierarchy path" action](https://help.easymorph.com/doku.php?id=transformations:hierarchypath)? It seems like it would be trivial to do what you need with the help of this action, as long as the graph is acyclic. ---
**Author:** ![Sir-McNeil](https://community.easymorph.com/letter_avatar_proxy/v4/letter/s/57b2e6/32.png) [@Sir-McNeil](https://community.easymorph.com/u/Sir-McNeil)\ **Post date:** [February 20, 2026, 5:53pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/3 "2026-02-20T17:53:16Z")
Hi @dgudkov, Definitely a great action to work with! It needs some extra work to accommodate for self paths, and to get to the desired output, but that should be no problem. ---
**Author:** ![Sir-McNeil](https://community.easymorph.com/letter_avatar_proxy/v4/letter/s/57b2e6/32.png) [@Sir-McNeil](https://community.easymorph.com/u/Sir-McNeil)\ **Post date:** [February 20, 2026, 6:34pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/4 "2026-02-20T18:34:49Z")
_EDITED to reflect added test cases (see **input** in the original post) and changed desired output (see **output** in the original post). Then EDITED again to fix a bug and add test data inflation._ Here's the test set I use to verify it all works. [test data - input.csv](https://community.easymorph.com/uploads/short-url/bGhFCJgLA7RV6ukd8TWjFNVKdfK.csv) (88 Bytes) [test data - output.csv](https://community.easymorph.com/uploads/short-url/qG9Sjq05Z6Gy9udH9DU9I1YhXnV.csv) (682 Bytes) [testbed.morph](https://community.easymorph.com/uploads/short-url/qrjBxAKkgeV1W57LPBDNMU9mJo1.morph) (25.4 KB) [dummy.morph](https://community.easymorph.com/uploads/short-url/9cg2Vosd45M7yayU5nqemhy6LOn.morph) (3.7 KB) ---
**Author:** ![Sir-McNeil](https://community.easymorph.com/letter_avatar_proxy/v4/letter/s/57b2e6/32.png) [@Sir-McNeil](https://community.easymorph.com/u/Sir-McNeil)\ **Post date:** [February 21, 2026, 1:01pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/5 "2026-02-21T13:01:27Z")
I tried implementing this with the [Hierarchy path](https://help.easymorph.com/doku.php?id=transformations:hierarchypath) action suggested by @dgudkov. [Hierarchy path.morph](https://community.easymorph.com/uploads/short-url/iQ0ySJGUGSjVKBsKYwrYLWB7xQL.morph) (11.4 KB; _EDITED to match changed input and output specifications_) # findings - minor changes to the data required, mainly adding a root node with empty parent. _This also pointed out a flaw in the original input specification: single nodes without parent or child(ren) could not be represented, but are present in the use cases (see below). I've adjusted the input specification and test data._ - paths are extracted very easily using the [Split delimited text into columns](https://help.easymorph.com/doku.php?id=transformations:splitdelimitedtext) action - reachability pairs are extracted fairly easily using a combination of [keepbefore()](https://help.easymorph.com/doku.php?id=syntax:functions:keepbefore) and [mirror()](https://help.easymorph.com/doku.php?id=syntax:functions:mirror) - the action only generates all partial paths _from_ a root, e.g. `0`, `0|3`, `0|3|6` and `0|3|6|7` the action does not generate all partial paths _to_ a leaf, e.g. `3`, `3|6`, `3|6|7`, `6`, `6|7` and `7` are missing _the missing partial paths can be derived fairly easily_ - filters can be applied to specify the options - directed acyclic graph (DAG) don't work because the child is a primary key, so duplicates (required for specifying multiple parents) are not allowed _I have not found a workaround for this and **welcome any suggestions** _ So most of it works well. How important is the directed acyclic graph? Unfortunately, one of the primary use cases can't do without it. # use case Users are assigned roles: | user | role | | --- | --- | | john | 1 | | jane | 2 | | minnie | 3 | Roles can be (and often are) nested, e.g.: - role 1 - role 2 - role 3 Actual permissions can be (and are) assigned to any role (not only the leaf), e.g.: | role | permission | | --- | --- | | 1 | read invoices | | 1 | create invoices | | 2 | modify invoices | | 3 | approve invoices | In this specific use case _inheritance goes up the tree_, i.e. role 2 has all permissions of roles 2 and 3, and role 1 has all permissions of roles 1, 2 and 3. A junior would get role 3 (fewest permissions), a senior role 2 (more permissions) and a manager role 1 (most permissions). This example is still simple and (crucially) a strict tree, not a directed acyclic graph. In reality, the lowest level roles contain permissions for individual tasks, like "view sales orders" or "modify AP master data". These tasks are included in the (job) roles of several employees, and therefore have multiple parent roles. ---
**Author:** ![Sir-McNeil](https://community.easymorph.com/letter_avatar_proxy/v4/letter/s/57b2e6/32.png) [@Sir-McNeil](https://community.easymorph.com/u/Sir-McNeil)\ **Post date:** [March 9, 2026, 4:31am UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/6 "2026-03-09T04:31:09Z")
I implemented this with a pair of [Repeat](https://help.easymorph.com/doku.php?id=transformations:repeat) actions, one for the tree expansion, another for partial paths (pretty much the same as with the Hierarchy path. [Repeat.morph](https://community.easymorph.com/uploads/short-url/QEfm0NIR3ZL8W7xIAIUI9BILT2.morph) (27.1 KB) # findings - moving the output even closer to that of Hierarchy path simplified the flow. This is a testament to the design of the I/O formats for Hierarchy path. - I didn't find a way of having the input passed to the Repeat action, so I resorted to writing it to disk outside the Repeat action, and reading it from disk inside the Repeat action. - The actual tree expansion was the easy bit. My addition of specifications (and guarantees) about partial paths and self-paths added quite a bit of logic. - I didn't expect to even get close to the performance of a native easymorph action, but I shouldn't have bothered checking: yes, the native Hierarchy path is probably faster, but it doesn't matter. Both run in milliseconds, even on an artificially inflated dataset of 1 million rows. - Fortunately, I did check performance, because it pointed me to memory being a limiting factor. Below is the max memory consumption for the entire flow (the difference between the two options. | rows | max. memory | | --- | --- | | 0 | 175MB | | 1000 | 500MB | | 10000 | 740MB | | 100000 | 2.5GB | | 1000000 | 9.5GB | The memory consumption came as somewhat of a surprise to me. The as the data for the largest input (1 million rows, 2 columns with longest total text length of 4 characters) would take up 12MB uncompressed (assuming null-terminated strings and UTF16). This is purely theoretical, of course, and I realise that the data structure would take up extra space. On the other hand, the data should compress well; even a simple integer replacement of unique values would reduce the theoretical data size to 3MB. Saving the tree to disk showed that in practice, the data structure takes up much more space: on disk, the input data takes up 250MB. I might dig into this a bit more. ---
**Author:** ![dgudkov](https://community.easymorph.com/user_avatar/community.easymorph.com/dgudkov/32/5_2.png) [@dgudkov](https://community.easymorph.com/u/dgudkov)\ **Post date:** [March 9, 2026, 2:21pm UTC](https://community.easymorph.com/t/tree-edge-list-expansion/6570/7 "2026-03-09T14:21:45Z")
EasyMorph uses columnar compression that doesn't work well on columns with long unique strings. In such cases, columnar compression even _increases_ data, instead of compressing it. This can be particularly noticeable on synthetic datasets. In real life, datasets typically have mixed column types, so overall columnar compression does compress data. Besides that, the "Repeat" action keeps all intermediate results of each iteration in memory and that increases memory consumption as well.