'How to find level of nodes with multiple entry and exit nodes in a directed acyclic graph?

For the directed acyclic graph given by the following python code, there are two entry nodes (node 0 and node 1) and two exit nodes (node 8 and node 15).

class Graph:
    def __init__(self, edges, n):
        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):
    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()
 
# Graph Data
    # Edge (x, y, w) represents an edge from `x` to `y` having weight `w`
    n = 16
    edges = [(0, 2, 8), (0, 3, 5), (0, 4, 6), (1, 5, 1), (1, 6, 1), (1, 7, 4), (2, 8, 7), 
             (2, 9, 8), (3, 8, 7), (3, 10, 3), (4, 8, 2), (4, 11, 5), (5, 8, 5), 
             (5, 12, 8), (6, 8, 7), (6, 13, 3), (7, 8, 6), (7, 14, 7), (9, 15, 1), (10, 15, 2),
             (11, 15, 1), (12, 15, 1), (13, 15, 4), (14, 15, 3)]

# construct a graph from a given list of edges
graph = Graph(edges, n)
new_graph = [[] for i in range(n)]
# print adjacency list representation of the graph
printGraph(graph)

The function given below works well to determine the level of each node unless there is only 1 entry and exit node but in the above case since there are two entry nodes, it shows node 0 in Level '1' but node 1 in Level 'None' and also the rest of the level representation is getting messed up.

# 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 0 
    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
level = getLevels(new_graph, n, 0)

The Level of all the entry nodes should be same, i.e., the Level of 'Node 0' as well as 'Node 1' should be '1'. How do I go about doing that? One way I think would be adding an pseudo entry node and exit node with weight=0 but by doing that my n increases by 2. Is there any other way to go around it? Please help!



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source