13. Topological Sorting using Kahns Algorithm

In [3]:

from utils.graph import GraphAdjList as Graph
from utils.graph_properties import GraphPropertiesAdjList as gp

from utils.graph import GraphAdjList as Graph from utils.graph_properties import GraphPropertiesAdjList as gp

In [2]:

g = Graph()

g = Graph()

In [4]:

g.insert_node_directed(5, 2)
g.insert_node_directed(5, 0)
g.insert_node_directed(4, 0)
g.insert_node_directed(4, 1)
g.insert_node_directed(2, 3)
g.insert_node_directed(3, 1)

g.insert_node_directed(5, 2) g.insert_node_directed(5, 0) g.insert_node_directed(4, 0) g.insert_node_directed(4, 1) g.insert_node_directed(2, 3) g.insert_node_directed(3, 1)

In [5]:

g.graph

g.graph

Out[5]:

defaultdict(list, {5: [2, 0], 4: [0, 1], 2: [3], 3: [1]})

In [10]:

num_vertices = gp.num_vertices(g.graph)

num_vertices = gp.num_vertices(g.graph)

In [7]:

# class topologicalSorting:

#     def __init__(self, graph, num_vertices):
#         self.

# class topologicalSorting: # def __init__(self, graph, num_vertices): # self.

In [14]:

def topological_sorting(graph, num_vertices):

    in_degree = [0] * num_vertices

    for node in graph:
        for neighbour in graph[node]:
            in_degree[neighbour] += 1

    queue = []
    for node in range(num_vertices):
        if in_degree[node] == 0:
            queue.append(node)

    count_visited = 0

    topological_order = []

    while queue:
        node = queue.pop(0)
        topological_order.append(node)

        for neighbour in graph[node]:
            in_degree[neighbour] -= 1

            if in_degree[neighbour] == 0:
                queue.append(neighbour)

        count_visited += 1

    if count_visited != num_vertices:
        print("Cycle present in graph, it is not a DAG")
    else:
        print("topological_order: ", topological_order)

def topological_sorting(graph, num_vertices): in_degree = [0] * num_vertices for node in graph: for neighbour in graph[node]: in_degree[neighbour] += 1 queue = [] for node in range(num_vertices): if in_degree[node] == 0: queue.append(node) count_visited = 0 topological_order = [] while queue: node = queue.pop(0) topological_order.append(node) for neighbour in graph[node]: in_degree[neighbour] -= 1 if in_degree[neighbour] == 0: queue.append(neighbour) count_visited += 1 if count_visited != num_vertices: print("Cycle present in graph, it is not a DAG") else: print("topological_order: ", topological_order)

In [15]:

topological_sorting(g.graph, num_vertices=num_vertices)

topological_sorting(g.graph, num_vertices=num_vertices)

topological_order:  [4, 5, 2, 0, 3, 1]

In [ ]: