CODEWITHSUNDEEP
pythonrecursiontree
Shubzumt
Shubzumt

Reputation: 143

Generic Tree in Recursion in Python

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.

Upvotes: 1

Views: 781

Answers (1)

trincot
trincot

Reputation: 350272

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

Upvotes: 1

Related Questions