CODEWITHSUNDEEP
pythondata-structuresmultiway-tree
Bari Tala
Bari Tala

Reputation: 57

Multiway trees and structures

I have a problem in applied math that can be almost perfectly mapped to finding the longest path in a multiway tree.

I have a function child() which gives child nodes (points in space satisfying a condition). The only caveat is that child() requires all previous nodes connected to it including the root node. It is here where I am struggling to write my code recursively. So far, I have something like below.

def multitree(node):
     tmp_list = child(node)
     for child2 in tmp_list:
           if len(child(child2)))==0:       #if you hit a leaf (dead end), go to next element
                 continue
           else:
                 multitree(child2)

But at this point, I'm not sure what to return. I essentially want to map the entire multiway tree until i reach a leaf for everything. Any ideas or tips? thanks guys.

edit:

Update 1: For completeness sake, I sketched out a rough idea of what input child() requires: https://i.sstatic.net/QDyNj.png Basically to find the child nodes of the node marked by the arrow child() requires the list of nodes between root and the node itself, i.e. the nodes marked with a red dot.

Update 2:

I've written child(node) as below and I am currently working on it --

def pathwalk(node):

    children = child(node)
    paths = [child(node.append(kid)) for kid in children]

    return paths

Upvotes: 1

Views: 1117

Answers (2)

Bari Tala
Bari Tala

Reputation: 57

I think I've found the issue. Since I wanted to keep a running list of all nodes you find the children of (you keep track of the path you walk, see imgur pic). I edited Illuvatar's routine by adding

children_vals = [longest_path(node+[c]) for c in children]

In this way, you recursively concatenate every parent with its child.

Upvotes: 0

Iluvatar
Iluvatar

Reputation: 1537

You can do something like this to get just the longest path. Here it gets you a list of nodes, from there you can extract any relevant information:

def longest_path(node):
    children = child(node)

    if not children: # leaf node
        return [node]

    children_vals = [longest_path(c) for c in children]
    longest = max(children_vals, key=len)
    return [node] + longest

Doesn't handle ties, or rather chooses one option arbitrarily.

(note: semi-tested)

Upvotes: 1

Related Questions