I have got it to produce adjacency list in the current format:
carbongraph = {'(0, 1)': [(0, 2)], '(0, 2)': [(0, 1), (0, 3), (1, 2)], '(0, 3)': [(0, 2)], '(1, 2)': [(0, 2), (2, 2)], '(2, 2)': [(1, 2)]}
But this format will not work for my longest path algorithm, It gives the following error
TypeError: object of type 'NoneType' has no len()
but it will work in the following format for some reason:
carbongraph = {'(0, 1)':['(0, 2)'], '(0, 2)':['(0, 1)','(0, 3)','(1, 2)'],
'(0, 3)':['(0, 2)'], '(1, 2)' :['(0, 2)','(2, 2)'], '(2, 2)':['(1, 2)']}
So how do i convert from the current format to the required format
What I have tried:
grid = [[0,1,1,1],
[0,0,1,0],
[0,0,1,0]]
lst = []
for rows, row in enumerate(grid) :
for cols, col in enumerate(row) :
if grid[rows][cols] in [1] :
lst.append((rows, cols))
print (lst)
adjacencylist = []
def adjacentnode(nodea,nodeb):
if nodea[0] == nodeb[0] and nodea[1] == nodeb[1] + 1:
adjacent = True
elif nodea[0] == nodeb[0] and nodea[1] == nodeb[1]-1:
adjacent = True
elif nodea[1] == nodeb[1] and nodea[0] == nodeb[0]+1:
adjacent = True
elif nodea[1] == nodeb[1] and nodea[0] == nodeb[0]-1:
adjacent = True
else:
adjacent = False
return adjacent
#Below is where conversion happens
carbongraph = {}
for node in range(len(lst)):
adjacencylist.append((lst[node],[]))
for neighbour in range(len(lst)):
adjacentnodes = (adjacentnode(lst[node],lst[neighbour]))
if adjacentnodes == True:
adjacencylist[node][1].append(lst[neighbour])
for item in adjacencylist:
carbongraph[str(item[0])] = (item[(1)])
for adj in item[1]:
adj = str(adj)
def shortestpath(graph, start, end, path = []):
path = path + [start]
if start == end:
return path
if start not in graph:
return None
for node in graph[start]:
if node not in path:
newpath = shortestpath(graph, node, end, path)
if newpath:
return newpath
return None
LeafArray = []
for leaf in carbongraph:
degree = (len(carbongraph[leaf]))
if degree == 1:
LeafArray.append(leaf)
print(LeafArray)
chainlist = []
for node in LeafArray:
for neighbour in LeafArray:
currentpath = (shortestpath(carbongraph,node,neighbour))
carbonchain = len(currentpath)#error occurs here
print (currentpath)
chainlist.append(carbonchain)
longestchain = max(chainlist)
print (longestchain)
def Prfix():
if longestchain == 4:
prefix = "But"
elif longestchain == 5:
prefix = "Pent"
elif longestchain == 6:
prefix = "Hex"
elif longestchain == 7:
prefix = "Hept"
elif longestchain == 8:
prefix = "Oct"
return prefix
print (Prfix())