How to find levels of each node in a graph where the root node is in the last level?

Viewed 235

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: Graph_1

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. Graph_2

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

0 Answers
Related