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

Do the needful with the given question and given code:1. Change the function find_path to return a list of all paths


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'))

        


1. Change the function find_path to return a list of all paths (without cycles) instead of the first path it finds.2. Consider a simple (directed) graph (digraph) having six nodes (A-F) and the following arcs (directed edges) with the respective cost of an edge given in parentheses:A -> B (2)A-> C (1)B-> C (2)B-> D (5)C -> D (1)C -> F (3)D -> C (1)D -> E (4)E -> F (3) F-> C (1)F-> E (2)Using the code for a directed weighted graph in Example 2, instantiate an object of DWGraph in __main__, add the nodes and edges of the graph using the relevant functions, and implement a function find_path() that takes starting and ending nodes as arguments and returns at least one path (if one exists) between those two nodes. The function should also keep track of the cost of the path and return the total cost as well as the path. Print the path and its cost in___main__.

Step by Step Solution

3.54 Rating (164 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock

CODE class Graph def initself nodesNone edgesNone selfnodes selfadj if nodes None selfaddnodesfromnodes if edges None selfaddedgesfromedges def lensel... View full answer

blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!