Question

Can you solve and send me the original code which I can copy and paste plz. Thank you.

Kahn's Algorithm

Implement Kahn's Algorithm for giving a topological ordering of a graph as discussed in class. The input graph will be in adjacency list format.

1. Count the in-degree (number of edges ending at) each vertex.

2. Create a queue of nodes with in-degree 0.

3. While the queue is not empty:

a. Add the first element in the queue to the ordering.

b. Decrement the in-degree of each of the first element’s neighbors.

c. Add any neighbors that now have in-degree 0 to the queue.

d. Remove the first element from the queue.

4. If the ordering doesn't contain all nodes then the graph had a cycle and we return None

5. Else we return the ordering

graph = [

[1, 3],

[],

[3, 6, 7],

[6],

[],

[],

[],

[5, 4],

]

order = topological(graph)

print(order)

[0, 2, 1, 3, 7, 6, 4, 5] # one POSSIBLE ordering

order.index(0) < order.index(3)

order.index(0) < order.index(1)

order.index(2) < order.index(3)

order.index(2) < order.index(6)

order.index(2) < order.index(5)

order.index(3) < order.index(6)

order.index(7) < order.index(5)

from collections import deque

#complete following code

def topological(graph):
in_deg = [0 for _ in range(len(graph))]
  
for node1 in range(len(graph)):
for node2 in graph[node1]:
in_deg[node2] += 1
  
queue = deque()
"""
Iterate over all the nodes and append the nodes with in-degree 0 to the queue
"""
# your code here
  
ordereing = []
while len(queue) > 0:
current_node = queue.popleft()
ordereing.append(current_node)

for neighbor in graph[current_node]:
in_deg[neighbor] -= 1
"""
If this neighbor in-degree now becomes 0, we need to append it to the queue
"""

# your code here
  
"""
If we couldn't process all nodes, this means there was a cycle in the graph
and the graph wasn't a DAG.
"""
if len(ordereing) != len(graph):
return None
  
return ordereing

order.index(7) < order.index(4)

Answer 1

Solution

#Since you have only asked for the code.

from collections import deque
def topological(graph):
    in_deg = [0 for _ in range(len(graph))]
    
    for node1 in range(len(graph)):
        for node2 in graph[node1]:
            in_deg[node2] += 1
    
    queue = deque()
    """
    Iterate over all the nodes and append the nodes with in-degree 0 to the queue
    """
    for node1 in range (len(graph)):
        if in_deg[node1]==0:
            queue.append(node1)
    
    ordereing = []
    while len(queue) > 0:
        current_node = queue.popleft()
        ordereing.append(current_node)

        for neighbor in graph[current_node]:
            in_deg[neighbor] -= 1
            if in_deg[neighbor]==0:
                queue.append(neighbor)
    """
    If this neighbor in-degree now becomes 0, we need to append it to the queue
    """

    
    """
    If we couldn't process all nodes, this means there was a cycle in the graph
    and the graph wasn't a DAG.
    """
    if len(ordereing) != len(graph):
        return None
    
    return ordereing

Hope this helps! Please rate the solution if you like it.

Thanks!