I have the following python code to construct a graph and find the level of each node of the graph(DAG in my case):
import queue
# A class to represent a graph object
class Graph:
# Constructor to construct a graph
def __init__(self, edges, n):
# A list of lists to represent an adjacency list
self.adjList = [None] * n
# allocate memory for the adjacency list
for i in range(n):
self.adjList[i] = []
# add edges to the directed graph
for (src, dest, weight) in edges:
# allocate node in adjacency list from src to dest
self.adjList[src].append((dest, weight))
# Function to print adjacency list representation of a graph
def printGraph(graph,n):
for src in range(len(graph.adjList)):
# print current vertex and all its neighboring vertices
for (dest, weight) in graph.adjList[src]:
new_graph[src].append(dest)
print(f'({src} —> {dest}, {weight}) ', end='')
print()
# function to determine level of
# each node starting from x using BFS
def getLevels(graph, V, x):
level = [None] * V
# array to store level of each node
marked = [False] * V
# create a queue
que = queue.Queue()
# enqueue element x
que.put(x)
# initialize level of source
# node to 1
level[x] = 1
# marked it as visited
marked[x] = True
# do until queue is empty
while (not que.empty()):
# get the first element of queue
x = que.get()
# traverse neighbors of node x
for i in range(len(graph[x])):
# b is neighbor of node x
b = graph[x][i]
# if b is not marked already
if (not marked[b]):
# enqueue b in queue
que.put(b)
# level of b is level of x + 1
level[b] = level[x] + 1
# mark b
marked[b] = True
# display all nodes and their levels
print("Nodes", " ", "Level")
for i in range(V):
print(" ",i, " --> ", level[i])
return level
# construct a graph from a given list of edges
graph = Graph(data.edges, data.tasks)
new_graph = [[] for i in range(data.tasks)]
# print adjacency list representation of the graph
printGraph(graph,data.tasks)
parents = getParents(graph, data.tasks)
level = getLevels(new_graph, data.tasks, 0)
print(parents)
The code works fine for a graph in which the root node is in level 1 such as the graph shown below:

But for a graph that starts from the bottom, in which the root node is in the last level as shown in the figure below, my code shows the level of each node as NONE.

I have been struggling to level the graph as shown in the second picture. Any help would be appreciated!