Adjacency Matrix:- Edges Given
import numpy as np
edges = [(0, 1), (1, 2), (2, 0), (0, 2), (2, 3)]
AMatrix = np.zeros(shape=(4, 4))
for (i, j) in edges:
AMatrix[i, j] = 1
# print(AMatrix)
Adjacency List
Alist = {}
for i in range(4):
Alist[i] = []
for (i, j) in edges:
Alist[i].append(j)
# print(Alist)
Reachability in a graph
# (A) BFS USING QUEUES
class Queue():
def __init__(self):
self.queue = []
def isempty(self):
return self.queue == []
def addq(self, v):
self.queue.append(v)
return
def delq(self):
if not self.isempty():
return self.queue.pop(0)
def __str__(self):
return str(self.queue)
def BFS(AList, v):
visited = {}
for u in AList.keys():
visited[u] = False
Q = Queue()
visited[v] = True
Q.addq(v)
while(not(Q.isempty())):
u = Q.delq()
visited[u] = True
for v in AList[u]:
if not visited[v]:
Q.addq(v)
return visited
Path Recording
def BFSPath(AList, v):
(visited, parent) = ({}, {})
Q = Queue()
for u in AList:
visited[u] = False
parent[u] = -1
visited[v] = True
parent[v] = 0
Q.addq(v)
while(not Q.isempty()):
j = Q.delq()
for u in AList[j]:
if not visited[u]:
visited[j] = True
parent[u] = j
Q.addq(u)
return (parent)
# print(BFSPath(L,0))
Distance Recording
def BFSDistance(AList, v):
(level, parent) = ({}, {})
Q = Queue()
for u in AList:
level[u] = -1
parent[u] = -1
level[v] = 0
Q.addq(v)
while(not Q.isempty()):
j = Q.delq()
for u in AList[j]:
if level[u] == -1:
level[u] = level[j]+1
parent[u] = j
Q.addq(u)
return (level)
# (B) DFS
Using Stack
class Stack():
def __init__(self):
self.stack = []
def isempty(self):
return self.stack == []
def adds(self, v):
self.stack.append(v)
return
def dels(self):
if not self.isempty():
return self.stack.pop()
def __str__(self):
return str(self.stack)
def DFS(AList, v):
visited = {}
S = Stack()
for u in AList:
visited[u] = False
visited[v] = True
S.adds(v)
while(not S.isempty()):
j = S.dels()
for u in AList[j]:
if not visited[u]:
visited[u] = True
S.adds(u)
return visited
AList = {0: [1, 4], 1: [0], 4: [8, 9], 8: [4, 9], 9: [4, 8]}
#print(DFS(AList, 0),'\n')
def inl(AList, v):
(visited, parent) = ({}, {})
for i in AList:
visited[i] = False
parent[i] = -1
return dfs(AList, visited, parent, v)
def dfs(AList, visited, parent, v):
visited[v] = True
for k in AList[v]:
if not visited[k]:
parent[k] = v
(visited, parent) = dfs(AList, visited, parent, k)
return (visited, parent)
print(AList, '\n')
#print('DFS:- ',DFS(AList,0))
#print(inl(AList, 0))
Application of BFS/DFS
# (1) Number of Components
ADList = {0: [1, 4], 1: [0], 2: [3, 6, 7], 3: [2, 7], 4: [0, 8, 9], 5: [], 6: [2, 10], 7: [2, 3, 10, 11], 8: [4, 9], 9: [4, 8],
10: [6, 7], 11: [7]}
def CompNumber(AList):
(comp, seen) = (0, 0)
Compid = {}
for i in AList:
Compid[i] = -1
while(seen <= max(AList.keys())):
unvisited = min([i for i in AList if Compid[i] == -1])
visited = BFS(AList, unvisited)
for v in visited:
if visited[v]:
Compid[v] = comp
seen += 1
# print('unvisited',unvisited)
#print([i for i in visited if visited[i]] )
comp = comp+1
return comp
#print('Number of Components:- ',CompNumber(ADList))
# (2) Detecting Cycles in Graph
# Usinfg Pre/Post (INCORRECT)
def DFSPrePost(AList, v):
(visited, pre, post) = ({}, {}, {})
count = 0
for i in AList:
visited[i] = False
pre[i] = -1
post[i] = -1
S = Stack()
visited[v] = True
# pre[v]=count
# count+=1
S.adds(v)
while(not S.isempty()):
pre[v] = count
count += 1
j = S.dels()
for u in AList[j]:
if not visited[u]:
visited[u] = True
S.adds(u)
post[u] = count
count += 1
return(pre, post, count)
# AList={0:[1,4],1:[0],4:[8,9],8:[4,9],9:[4,8]}
#print(DFSPrePost(AList,0))
(visited, pre, post) = ({}, {}, {})
def inl(AList, v):
count = 0
for i in AList:
visited[i] = False
pre[i] = -1
post[i] = -1
return dfs(AList, v, count)
def dfs(AList, v, count):
visited[v] = True
pre[v] = count
count += 1
for k in AList[v]:
if not visited[k]:
count = dfs(AList, k, count)
count += 1
post[v] = count
# return count
return (count)
L={0:[2,3,4],1:[2,7],2:[5],3:[5,7],4:[7],5:[6],6:[7],7:[]}
#print(inl(L, 0))
#print('\n',pre,post)
Topological Sorting
def Topological(AList):
(indegree,Q,L)=({},Queue(),[])
for v in AList:
indegree[v]=len([i for i in AList.values() if v in i])
for v in indegree:
if indegree[v]==0:
Q.addq(v)
while(not Q.isempty()):
#print(Q)
j=Q.delq()
L.append(j)
indegree[j]-=1
for u in AList[j]:
if indegree[u]!=-1:
indegree[u]-=1
if indegree[u]==0:
Q.addq(u)
return L
#print(Topological(L))
# Longest-Path From Topological Sorting
def TopoLongestPath(AList):
(L,Path,Q,indegree)=([],{},Queue(),{})
for v in AList:
indegree[v]=len([i for i in AList.values() if v in i])
Path[v]=0
for v in indegree:
if indegree[v]==0:
Q.addq(v)
while(not Q.isempty()):
j=Q.delq()
L.append(j)
indegree[j]-=1
for v in AList[j]:
if indegree[v]!=-1:
indegree[v]-=1
if indegree[v]==0:
Path[v]=max(Path[j]+1,Path[v])
Q.addq(v)
return (L,Path)
#print(TopoLongestPath(L))
){kind=link}
0 Comments