Python - Parent-Child Hierarchy Recursive Structure

Question

I am trying to form a parent to child relationship combination using data available in my pandas dataframe.

Data Example:

Parent	Child
A	B
A	C
B	D
B	C
C	D

Expected chain results:

A|B

A|C

A|B|D

A|B|C

A|C|D

A|B|C|D

I tried something with networkx package to trace out the trees. I am partially successful. But it misses some of the hierarchies shown in the expected result.

Like, if the child has sub-nodes associated with it, it's not appearing as separate result.

For example, in the above data B is a child to A and has D & C are childs of B.

While applying my code, it shows A|B|D & A|B|C|D alone.

A|B is skipped as B has childs (C & D )

A|B|C is skipped as B has childs (C & D ) and subsequently C also has child (D)

A|C is skipped as C has child (D)

I used the code shown in below link

How to use recursion to record all routes in a parent child hierarchy?

"Need help" is not a suitable question here. Please show your attempt, and where things are not going as expected, and what you have done to research and debug. — trincot
– trincot, Commented Sep 26, 2023 at 16:26
This is a network problem, read on networkx as you already tagged. You can think of your data as a (collection of) trees, then find all the leaves, and path to the tree roots. — Quang Hoang
– Quang Hoang, Commented Sep 26, 2023 at 16:45

Timeless · Accepted Answer · 2023-09-26 16:51:51Z

1

A possible solution with all_simple_paths :

G = nx.from_pandas_edgelist(df, # or pd.read_csv("file.csv")
    source="parent", target="child", create_using=nx.DiGraph)

root = next(nx.topological_sort(G))

out = (
    pd.Series(
        [
            list(nx.all_simple_paths(G, root, c)) for c in df["child"]
        ]
    ).explode().sort_values(key=lambda s: s.str.len())
    .drop_duplicates().str.join("|").to_frame("paths")
)

Output :

print(out)

     paths
0      A|B
1      A|C
1    A|B|C
2    A|B|D
2    A|C|D
2  A|B|C|D

answered Sep 26, 2023 at 16:51

Timeless

38.3k6 gold badges33 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Balaji Srinivasan Over a year ago

Awesome. Thanks for your answer. I am able to get the tree structure as expected now. Once again, thanks for your guidance.

Collectives™ on Stack Overflow

Python - Parent-Child Hierarchy Recursive Structure

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related