CODEWITHSUNDEEP
pythondata-structuresgraph
muruDiaz
muruDiaz

Reputation: 127

How to identify root nodes in a python dictionary?

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.

Upvotes: 3

Views: 1978

Answers (3)

solub
solub

Reputation: 1363

Much easier:

while d: #'d' is a dictionary
    roots = set(d).difference(*d.values())
    print(roots)
    [d.pop(k) for k in roots]

or in a recursive way:

def traverse(d):
    if d:
        roots = set(d).difference(*d.values())
        print(roots)
        [d.pop(k) for k in roots]
        return traverse(d)

Either way prints:

set([1, 2, 3])
set([4, 6, 9])
set([5, 7])
set([8])

Upvotes: 0

6502
6502

Reputation: 114481

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]

Upvotes: 2

monkut
monkut

Reputation: 43830

Sounds like you want to perform a Topological Sort

You can use the library, toposort to do the heaving lifting for you, it will determine the dependencies and order in which the nodes should be processed:

import toposort

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

# change values to sets (required by toposort)
for key, value in my_graph.items():
    my_graph[key] = set(value)

result = toposort.toposort(my_graph)
print(list(result))

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

Upvotes: 0

Related Questions