# priyankakankal17/astar

a year ago
In [1]:
``import networkx as nx ``
In [2]:
``````costs = {'n0': 0 , 'n1':2 , 'n2':4,'n3':4,'n4':1,'n5':1,'n6':2,'n7':0,'n8':0}
goalNodes = ['n7','n8']``````
In [3]:
``````def makeG(mg):
for i in mg.nodes:
mg.node[i]['solved']=False
mg.node[i]['cost'] = costs[i]

for i in mg.edges:
mg[i[0]][i[1]]['marked']=False
mg[i[0]][i[1]]['andby']=None

``````
In [4]:
``````def cost(mg,node):
return nx.get_node_attributes(mg,'cost')[node]

``````
In [5]:
``````def solved(mg,node):
return nx.get_node_attributes(mg,'solved')[node]

``````
In [6]:
``````
def andby(mg,edge1,edge2):
return nx.get_edge_attributes(mg,'andby')[edge1,edge2]

``````
In [7]:
``````def marked(mg,edge1,edge2):
return nx.get_edge_attributes(mg,'marked')[edge1,edge2]

``````
In [8]:
``````def findleaf(g):
for i in g.nodes:
if not g.__getitem__(i):
if i not in goalNodes:
return i

return None

``````
In [9]:
``````def addToG(n,nodeList):
for i in nodeList:
# print(i)
if not g.has_edge(n,i):
g.node[i]['cost'] = cost(mainGraph,i)
g.node[i]['solved'] = False
if i in goalNodes :
g.node[i]['solved'] = True

``````
In [10]:
``````def findMin(q,m):
ls = []
MinNode = min(q,key=q.get)
ls.append(MinNode)
if andby(g,m,MinNode):
ls.append(andby(g,m,MinNode))

return ls

``````
In [11]:
``````mainGraph = nx.DiGraph()
startNode = 'n0'

edges = [
('n0','n1'),
('n0','n4'),
('n0','n5'),
('n1','n3'),
('n2','n4'),
('n2','n5'),
('n2','n3'),
('n3','n5'),
('n3','n6'),
('n4','n5'),
('n4','n8'),
('n5','n7'),
('n5','n8'),
('n6','n7'),
('n6','n8')
]

``````
In [12]:
``````mainGraph.add_edges_from(edges)
makeG(mainGraph)
mainGraph.edges['n0','n4']['andby'] = 'n5'

mainGraph.edges['n0','n5']['andby'] = 'n4'

mainGraph.edges['n2','n4']['andby'] = 'n5'

mainGraph.edges['n2','n5']['andby'] = 'n4'

mainGraph.edges['n3','n5']['andby'] = 'n6'

mainGraph.edges['n3','n6']['andby'] = 'n5'

mainGraph.edges['n5','n7']['andby'] = 'n8'

mainGraph.edges['n5','n8']['andby'] = 'n7'

mainGraph.edges['n6','n7']['andby'] = 'n8'

mainGraph.edges['n6','n8']['andby'] = 'n7'

g = mainGraph.subgraph(startNode).copy()

``````
In [13]:
``````
if startNode in goalNodes :
g.node[startNode]['solved'] = True

while (solved(g,startNode) != True):
gprime = g.subgraph(startNode).copy()
for i in g.edges:
if marked(g,i[0],i[1]):

n = findleaf(gprime)

nodeList = list(mainGraph.neighbors(n))

# print(g.nodes)
s = [n]

while (len(s) != 0):

for i in s:
if i not in list(g.neighbors(i)):
m = s.pop(s.index(i))
break

q = {}
for i in list(g.neighbors(m)):
if andby(g,m,i):
q[i] = 2 + costs[i]+costs[andby(g,m,i)]
else:
q[i] = 1 + costs[i]

markList = findMin(q,m)

for i in markList:
g.edges[m,i]['marked'] = True
for j in list(g.neighbors(m)):
if andby(g,m,j) != i and i != j:
g.edges[m,j]['marked'] = False
for a in list(g.neighbors(j)):
g.edges[j,a]['marked'] = False

checkNeighbors = True
for i in g.neighbors(m):
if marked(g,m,i):
if solved(g,i) == False:
checkNeighbors = False
if checkNeighbors:
g.node[m]['solved'] = True

if costs[m] != q[markList[0]]:
costs[m] = q[markList[0]]
for i in list(g.predecessors(m)):
if marked(g,i,m):
s.append(i)

if solved(g,m):
for i in list(g.predecessors(m)):
if marked(g,i,m):
s.append(i)

markedge = nx.get_edge_attributes(g,'marked')

``````
In [14]:
``````print("The answer graph contain below edges:")
for i in markedge:
if markedge[i]:
print(i)

``````
```The answer graph contain below edges: ('n0', 'n4') ('n0', 'n5') ('n4', 'n8') ('n5', 'n7') ('n5', 'n8') ```
In [15]:
``import jovian``
In [ ]:
``jovian.commit()``
```[jovian] Saving notebook.. ```
In [ ]:
`` ``