Python JSON to tree with anytree

Question

I have JSON data that looks something like

{'Tree': [
  {"From": "1",
  "To": "2"},
  {"From": "2",
  "To": "3"}
]}

basically an array of all existing references between nodes. I want to be able to draw trees starting from a chosen root node using this data.

I find that using anytree I must link a node to a parent node, but ideally I want to simply link it to the name and have it put together the tree structure on its own.

# I want to do this
child[0] = Node(data[0]["To"], parent=data[0]["From"])

# But I think I need to assign a node, not its name
child[1] = Node(data[1]["To"], parent=child[?])

Suggestions on how to do this?

Is there any meaning that makes From different from To, or are edges undirected, working on both ways? — trincot
– trincot, Commented Feb 1, 2023 at 18:55
Is the list guaranteed to be ordered so that no node (other than the root) is referenced via "From" before being referenced via "To"? — chepner
– chepner, Commented Feb 1, 2023 at 18:55
The edges are directed, from "From" and pointing to "To" nodes. The list is not guaranteed to be ordered. — neveratdennys
– neveratdennys, Commented Feb 1, 2023 at 22:49

trincot · Accepted Answer · 2023-02-02 07:31:25Z

1

Do this in two steps:

Convert the input format into an adjacency list: a dictionary keyed by the node keys, and with associated lists that hold the keys of the connected nodes.
Choose a root node, and then create the anytree tree using the adjacency list.

Here are two functions that deal with these two tasks:

from anytree import Node, RenderTree
from collections import defaultdict 

def makegraph(edges):
    adj = defaultdict(list)
    for edge in edges:
        a, b = edge.values()
        adj[a].append(b)
        adj[b].append(a)
    return adj

def maketree(adj, nodekey):
    visited = set()
    
    def dfs(nodekey, parent):
        if nodekey not in visited:
            visited.add(nodekey)
            node = Node(nodekey, parent)
            for childkey in adj[nodekey]:
                dfs(childkey, node)
            return node
                
    return dfs(nodekey, None)

Here is how to use it:

edges = [
    {"From": "1", "To": "2"},
    {"From": "2", "To": "3"}
]

adj = makegraph(edges)
# Choose "1" as root:
root = maketree(adj, '1')
print(RenderTree(root))
# Now let's choose "2" as root:
root = maketree(adj, '2')
print(RenderTree(root))

edited Feb 2, 2023 at 7:31

answered Feb 1, 2023 at 20:19

trincot

357k38 gold badges282 silver badges338 bronze badges

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

7 Comments

neveratdennys Over a year ago

It looks like recursive calls would far exceed the limit and I'll try to convert it to use loops.

trincot Over a year ago

Are you sure the input is a tree?

trincot Over a year ago

I guess the input is not a tree... In that case you could skip edges that would make a cycle while making the tree. See updated maketree.

neveratdennys Over a year ago

You are exactly right, Cycles shouldn't exist in my data but it looks like they do exist. I converted your first ans to use loops and found it was a infinite loop caused by cycles in the structure. Thank you!

neveratdennys Over a year ago

The updated function has some issues it looks like 'NoneType' object has no attribute 'children'

|

Collectives™ on Stack Overflow

Python JSON to tree with anytree

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related