DAG - Iterate over graph - bfs but parents first-CodePudding

Hello I have a dag that looks like this

I'd like to travel it from the roots and print output like

I tried something like this but it's still not working. Could someone give me a tip on how such algorithm should look like or the name of this kind of graph traversal ?

from typing import List


class Node:
    def __init__(self, value, children) -> None:
        super().__init__()
        self.value = value
        self.children = children

    @staticmethod
    def create(value, *parents):
        node = Node(value, [])
        if parents is not None:
            for parent in parents:
                parent.children.append(node)
        return node


def travel(roots: List[Node], visited: List[Node]):
    print(" ".join([str(r.value) for r in roots]))
    visited  = roots
    all_children = []
    for r in roots:
        if r.children:
            for c in r.children:
                if c not in visited:
                    all_children.append(c)
    if all_children:
        travel(all_children, visited)


if __name__ == '__main__':
    root = Node.create(1)
    root2 = Node.create(6)
    roots = [root, root2]
    n2 = Node.create(2, root)
    n3 = Node.create(3, root)
    n4 = Node.create(4, n2, n3, root2)
    n5 = Node.create(5, n4)
    travel(roots, [])

CodePudding user response：

You could first traverse all nodes like you did, but then register for each node how many parents it has.

Put the nodes in a priority queue based on the number of parents they have. This can be implemented as a plain list, where the index represents the number of parents, and the associated value is a list of nodes that have that number of parents.

Then output all nodes that have no parents according to that priority queue. At the same time remove them from that priority queue and also decrement the parent count of the children of those nodes.

Repeat this process until the queue is empty.

def travel(roots: List[Node]):
    # Build dictionary keyed by node to register their number of parents
    parentcount: Dict[Node, int] = { node: 0 for node in roots }
    # Visit each node, and update that parent count for each of its children
    visited: Set[Node] = set()
    nodes: List[Node] = roots
    while nodes:
        nextlevel: List[Node] = []
        for node in nodes:
            if node not in visited and node.children:
                for child in node.children:
                    parentcount[child] = parentcount.get(child, 0)   1
                nextlevel.extend(node.children)
        visited.update(nodes)
        nodes = nextlevel
    # Make prioritiy queue: reverse the parentcount information: 
    #    group nodes that have the same parent count
    buckets: List[Set[Node]] = [set() for _ in visited]
    for node in visited:
        buckets[parentcount[node]].add(node)
    # Now we have the information to generate the output
    while buckets[0]:
        # Output nodes that have a parent count of 0. 
        nodes: List[Node] = list(buckets[0])
        buckets[0].clear()
        print(" ".join(str(node.value) for node in nodes))
        # Decrease the parent count of their children
        for node in nodes:
            if node.children:
                for child in node.children:
                    buckets[parentcount[child]].remove(child)
                    parentcount[child] -= 1
                    buckets[parentcount[child]].add(child)

NB: this function no longer takes the second argument.