Do the needful with the given question and given code: def __init__(self, nodes=None, edges=None): self.nodes, self.adj =
Question:
Do the needful with the given question and given code:
def __init__(self, nodes=None, edges=None):
self.nodes, self.adj = [], {}
if nodes != None:
self.add_nodes_from(nodes)
if edges != None:
self.add_edges_from(edges)
def __len__(self):
return len(self.nodes)
def __contains__(self, x):
return x in self.nodes
def __iter__(self):
return iter(self.nodes)
def __getitem__(self, x):
return iter(self.adj[x])
def __str__(self):
return 'V: %sE: %s' % (self.nodes, self.adj)
def add_node(self, n):
if n not in self.nodes:
self.nodes.append(n)
self.adj[n] = []
def add_nodes_from(self, i):
for n in i:
self.add_node(n)
def add_edge(self, u, v): # undirected unweighted graph
self.adj[u] = self.adj.get(u, []) + [v]
self.adj[v] = self.adj.get(v, []) + [u]
def add_edges_from(self, i):
for n in i:
self.add_edge(*n)
def number_of_nodes(self):
return len(self.nodes)
def number_of_edges(self):
return sum(len(l) for _, l in self.adj.items()) // 2
class DGraph(Graph):
def add_edge(self, u, v):
self.adj[u] = self.adj.get(u, []) + [v]
class WGraph(Graph):
def __init__(self, nodes=None, edges=None):
self.nodes, self.adj, self.weight = [], {}, {}
if nodes != None:
self.add_nodes_from(nodes)
if edges != None:
self.add_edges_from(edges)
def add_edge(self, u, v, w):
self.adj[u] = self.adj.get(u, []) + [v]
self.adj[v] = self.adj.get(v, []) + [u]
self.weight[(u,v)] = w
self.weight[(v,u)] = w
def get_weight(self, u, v):
return self.weight[(u,v)]
class DWGraph(WGraph):
def add_edge(self, u, v, w):
self.adj[u] = self.adj.get(u, []) + [v]
self.weight[(u,v)] = w
def display(self):
return self.weight
def find_path(self, start, end, path=[], cost=0):
newpath=None
path=path+[start]
if start == end:
return path,cost
if start not in self.adj:
return None, cost
paths=[]
for node in self.adj[start]:
if node not in path:
newpath,cost = self.find_path(node, end, path, cost+self.get_weight(start, node))
if newpath!=None:
return newpath, cost
return None, cost
if __name__ == '__main__':
D=DWGraph()
D.add_node('A')
D.add_edge('A', 'B', 2)
D.add_edge('A', 'C', 1)
D.add_edge('B', 'C', 2)
D.add_edge('B', 'D', 5)
D.add_edge('C', 'D', 1)
D.add_edge('C', 'F', 3)
D.add_edge('D', 'C', 1)
D.add_edge('D', 'E', 4)
D.add_edge('E', 'F', 3)
D.add_edge('F', 'C', 1)
D.add_edge('F', 'E', 2)
print(D.find_path('A', 'F'))