How to identify root nodes in a python dictionary?

Question

I have a python dictionary that is representing a graph. I wish to identify the root/independent nodes so that I can process them simultaneously and then the next nodes will become root/independent nodes. I am confused about how to implement this technique in python.

Below is a sample dictionary:

my_graph = {
            1:[4],
            2:[6],
            3:[9],
            4:[5,7],
            5:[8],
            6:[],
            7:[],
            8:[],
            9:[]
           }

I will divide the process into different frames. The expected result depending upon the above dictionary is given as:

1- start: root/independent nodes are = 1,2,3

2- after frame 1 root/independent nodes are = 4,6,9

3- after frame 2 root/independent nodes are = 5,7

4- after frame 3 root/independent nodes are = 8

Edit 1: I am trying to get sequence in any form e.g. a list, array or any other similar data-structure to a dependency graph of nodes in given dictionary, where each child node is dependent on its parent node so cannot be processed before parent. As a next step, I wish to get some parallelism i.e. I can process all root nodes at once.

I have been reading about Dask and luigui but not sure if they are the ultimate solution or I can do it some simple way.

Answer 1

This is called "topological sort". A simple algorithm is

1. build a mapping between nodes and number of "incoming" arcs
2. process nodes with 0 (those are "roots") and update the counters as you proceed (when you process a node decrement counter for all neighbors).

You may get to a stop before completion if the graph is not a tree (there are loops). In this case you will get to a point where the graph is not empty but there is no available root.

In your case

def tsort(graph): 
    counts = dict((k, 0) for k in graph) 
    for n, neighbors in graph.items(): 
        for nh in neighbors: 
            counts[nh] = counts[nh] + 1 
    while graph: 
        roots = [k for k in graph if counts[k] == 0] 
        if not roots: 
            raise RuntimeError("Cycles present, no topological sort possible") 
        print("roots", roots) 
        for r in roots: 
            print("Processing", r) 
            for nh in graph[r]: 
                counts[nh] -= 1 
            del graph[r]