Q:- Graph Theory

Scenario

UIT and many other universities nationwide are doing a joint project on multimedia. A computer network is built to connect these universities using communication links that construct a graph. The universities decided to install a file server at UIT Karachi to share data. As the links transmission time is controlled by the link setup and management. so, the cost of a data transfer is directly related to the number of links consumed. The target is that UIT Karachi desired to share data with NUST Islamabad by utilizing minimum cost.

Draw a graph with the help of these unweighted graph arcs and analyze an algorithm to compute the minimum

cost for sharing of data between UIT Karachi and NUST Islamabad.

NUST Islamabad --> UIT Karachi

UIT Karachi UET Lahore

NUST Islamabad BZU Multan

UET Lahore Faisalabad Uni

Faisalabad Uni BZU Multan

UET Lahore

Implementation

Data structure

You have to implement the graph by applying a dictionary data structure to hold the vertices and edges in the

form of key: value pairs

SharedData

This class consists of functions that are responsible for creating a graph, calculating the most cost-efficient path between UIT Karachi and NUST Islamabad, and compute its cost.

I am sharing a sample code what you have to write

Its basically a scenario that how how can you make a function under the class and also a guideline how many parameters we need to pass in each function even comments can also guide you when you code with python

class Graph: def init (self): pass # create a graph with the help of a dictionary and return it. def build_graph (self): return g class sharedData: def _init__(self): pass calculate the cost-efficient path from the graph # return mincostpath in the form of list start and end consists of initial and final Locations def minimum_cost_path(self, graph, start, end, path=[]) #path=0intiate populating it from the start # Use for loop to iterate on a graph #recursive call of this function return mincostpath calculate the cost along the minimum cost path def calculate_cost (self, mincostpath); #calculate the cost based onedges return pathcost The testing code must print the following output: The cost-efficient path byw UIT Karachi & NUST Islamabad is: UIT Karachi', 'UET Lahore', 'BZU Multan', 'NUST Islamabad The cost along this path is: 3