12. Topological Sorting

In [30]:

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 [31]:

g = Graph()
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 = Graph() 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 [32]:

g.graph

g.graph

Out[32]:

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

In [25]:

class topologicalSorting:
    def __init__(self, num_vertices, graph):
        self.graph = graph
        self.num_vertices = num_vertices
        self.visited_node_set = set()
        self.stack = []

    def topological_sorting_util(self, node):
        self.visited_node_set.add(node)
        for v in self.graph[node]:
            if v not in self.visited_node_set:
                self.topological_sorting_util(v)

        self.stack.append(node)

    def topological_sorting(self):
        for node in range(self.num_vertices):
            if node not in self.visited_node_set:
                self.topological_sorting_util(node)
        print(self.stack[::-1])

class topologicalSorting: def __init__(self, num_vertices, graph): self.graph = graph self.num_vertices = num_vertices self.visited_node_set = set() self.stack = [] def topological_sorting_util(self, node): self.visited_node_set.add(node) for v in self.graph[node]: if v not in self.visited_node_set: self.topological_sorting_util(v) self.stack.append(node) def topological_sorting(self): for node in range(self.num_vertices): if node not in self.visited_node_set: self.topological_sorting_util(node) print(self.stack[::-1])

In [33]:

num_vertices = gp.num_vertices(g.graph)

num_vertices = gp.num_vertices(g.graph)

In [35]:

test = topologicalSorting(num_vertices=num_vertices, graph=g.graph)

test = topologicalSorting(num_vertices=num_vertices, graph=g.graph)

In [36]:

test.topological_sorting()

test.topological_sorting()

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

In [39]:

g.graph[2]

g.graph[2]

Out[39]:

[3]

In [ ]: