'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 |
|---|
