How to quickly topological sort a tree from a list?

Question

Algorithms

Hello!
There is a list with attributes (Name, ID, ParentID), which is a tree of different nesting levels. What is the fastest way to restore a tree from this list? Thanks

Answer 1

Well, for example like this:

class TreeNode:
    def __init__(self):
        self.children = []
        self.name = None

    def add_child(self, child):
        self.children.append(child)

    def set_name(self, name):
        self.name = name

entries = {}
for entry in data:
    parent = entries.get(entry.ParentID, TreeNode())
    child = entries.get(entry.ID, TreeNode())
    parent.add_child(child)
    child.set_name(entry.Name)
    entries[entry.ParentID] = parent
    entries[entry.ID] = child

root = entries[RootID]

Depending on the "dictionary" used (in the example entries), we get different complexity. If, for example, it is known that IDs are numbers from 0 to N, then you can use a simple array as a dictionary - then we get guaranteed O (n), if we write in C ++ and use std:: map or TreeMap in Java as a dictionary, then O(n log n).

Answer 2

I don't quite understand the problem you are trying to solve.

How to quickly topological sort a tree from a list?

You actually have arcs (arcs) of the graph. You can fill in a more convenient data structure from this data (adjacency list, for example) and run the topological sorting algorithm on it. For example, based on depth-first search. That is, using DFS (depth-first search, depth-first search), we look for a node (vertex, node, vertex) from which there are no outgoing arcs (sink node), assign it a value equal to the number of nodes, remove it from the graph, repeat . Number - node position in the resulting list. Complexity O(m+n), where n is the number of nodes, m is the number of arcs. This is if a topologically sorted list of nodes is enough for you.

What is the fastest way to restore a tree from this list?

This is another question. What do you have in mind? What is the meaning of 'restore'? You have a tree (as a special case of a graph) already given a list of arcs, in fact, in what form do you need to present it?
If in the form (Name, ID, ChildID), then it seems to me that in O (m) it is possible to create a similar structure with actually inverted (relative to the given tree) arcs. For each tuple (Name, ID, ParentID), create (or update the Name field if the node already exists) a node (Name, ID), a node ParentID (if it has not been created), specify a child node ID for the ParentID node.