Jovian
⭐️
Sign In
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.add_edge(n,i,marked=False,andby=andby(mainGraph,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]):
            gprime.add_edge(i[0],i[1])


   
    n = findleaf(gprime)

    nodeList = list(mainGraph.neighbors(n))
   
   
    addToG(n,nodeList)
    # 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 [ ]: