class Graph(object):
def __init__(self,G):
self.G = G
self.color = [0] * len(G)
self.isDAG = True
def DFS(self,i):
self.color[i] = 1
for j in range(len(self.G)):
if self.G[i][j] != 0:
if self.color[j] == 1:
self.isDAG = False
elif self.color[j] == -1:
continue
else:
print('We are visiting node' + str(j + 1))
self.DFS(j)
self.color[i] = -1
def DAG(self):
for i in range(len(self.G)):
if self.color[i] == 0:
self.DFS(i)
#Python program to print topological sorting of a DAG
from collections import defaultdict
#Class to represent a graph
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list) #dictionary containing adjacency List
self.V = vertices #No. of vertices
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
# A recursive function used by topologicalSort
def topologicalSortUtil(self,v,visited,stack):
# Mark the current node as visited.
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Push current vertex to stack which stores result
stack.insert(0,v)
# The function to do Topological Sort. It uses recursive
# topologicalSortUtil()
def topologicalSort(self):
# Mark all the vertices as not visited
visited = [False]*self.V
stack =[]
# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Print contents of stack
print stack
