Generic Tree in Recursion in Python

Question

I am quite new in Python and stuck in a generic tree.

I have 2 columns. Assume names to be A and B. Now the thing is values of column A are parents of the corresponding value in column B. Now the value of column B is again searched in column A. Now it becomes the parent and its corresponding value a child.

For example:

A    B
--------
1    2
5    3
2    5
3

Now here for value '1'.

1 is parent. 2 is child of 1. Now 2 is again searched in column A. this now makes 2 a parent and 5 its child. Now we search for again it gives us the Value 3 . Same goes for 3 but there is no value in front of 3 so tree ends here and 3 is the leaf node of tree. Here in example I have displayed one child of each parent but in my dataset each parent can have many child and tree goes until all leaf nodes are reached. I know recursion is the solution here but how?

What I need in output is all possibles sets with the parent. In this case [1,2], [1,2,5], [1,2,5,3]. Also if 1 had 2 children let's say 2 and 4.

Then [1,2,4] will also be counted as a set. Any help here? I am struggling really hard!

Venky = {}

def Venkat(uno):
    x = df[df.ColA == uno]
    data = list(zip(x['ColB'],x.ColA))
    Venky[uno] = Node(uno)

    for child,parent in data:
        Venky[child] = Node(child, parent=Venky[uno])
        print(Venky[child])
        y = df[df['ColA'] == (Venky[child]).name]
        if (y['ColB'].empty == False):
            data = list(zip(y['ColB'],y.ColA,))
            #y_unique = y['ColB'].unique()
            for k in y['ColB']:
                    
                    res = Venkat(k)
                    return res
        
        
udo = 'a'
Venkat(udo)
for pre, fill, node in RenderTree(Venky[udo]):
    print("%s%s" % (pre, node.name))

Above is my sample code. df is my colA and colB dataframe . ColA is column A and same for colB. I have also imported Anytree and pandas library for this code. The outbut I am getting is something like this:

Node('/1/2')
Node('/4/nan')
1
└── 2
Node('/1/2')
Node('/4/nan')
None

Here 4 is sibling of 2 in the tree i.e 1 has 2 child here 2 and 4 unlike dataset. But currently I don't care about output. I want to construct a tree now. Then I will play around with output.

Thanks for pointing out though will definitely take care next time. — Shubzumt
– Shubzumt, Commented Jan 13, 2018 at 19:36
I have updated my question above and believe me I have searched for every possible python tree link here — Shubzumt
– Shubzumt, Commented Jan 13, 2018 at 19:49

trincot · Accepted Answer · 2018-01-13 20:03:50Z

1

I would suggest a solution where you first convert the table structure to a dictionary providing a list of child nodes (dictionary value) for each node (dictionary key).

Then perform a depth first walk through that tree, using recursion, extending a path with the newly visited child. Output the path at each stage. For this a generator is an ideal solution.

Code:

def all_paths(table, root):
    # convert table structure to adjacency list
    children = {}
    for node, child in table:
        if child: 
            children[node] = children.setdefault(node, []) + [child]

    # generator for iteration over all paths from a certain node
    def recurse(path):
        yield path
        if path[-1] in children:
            for child in children[path[-1]]: # recursive calls for all child nodes
                yield from recurse(path + [child])

    return recurse([root])

# Sample data in simple list format    
table = [
    [1, 2],
    [5, 3],
    [2, 5],
    [2, 6],
    [2, 4],
    [6, 7],
]

# Output all paths from node 1
for path in all_paths(table, 1):
    print(path)

The above outputs:

[1]
[1, 2]
[1, 2, 5]
[1, 2, 5, 3]
[1, 2, 6]
[1, 2, 6, 7]
[1, 2, 4]

See it run on repl.it

edited Jan 13, 2018 at 20:03

answered Jan 13, 2018 at 19:50

trincot

357k38 gold badges282 silver badges338 bronze badges

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

6 Comments

Shubzumt Over a year ago

Thanks for the great reply @trincot. I really appreciate it. The code works good but it just prints only child of 1 and not further childrens of its childrens.I want whole tree to be populated. Thanks again

trincot Over a year ago

Not sure what you mean. See the output generated on repl.it. NB: Needs python 3.3+ for yield from syntax.

Shubzumt Over a year ago

Yeah its workin fine on repl.it . But in my dataset tree ends when there is no corresponding value(Na) in ColB. Probably this is causing error in my dataframe

Shubzumt Over a year ago

My Bad. It totally solved my issue. Thanks for this elegant and sweet code.

Shubzumt Over a year ago

BTW, is there any way i can render a tree?

|

Collectives™ on Stack Overflow

Generic Tree in Recursion in Python

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related