Computer Project This assignment focuses on the design, implementation, and testing of a Python program using classes

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Need help on 2 of the functions. The make_objects(places_lst, g): function and the main function. I need help on these by tonight. Please let me know if you can help

 

Assignment Background

How does Google maps provide a route to travel? How does a phone call connect to a distant phone?

How does a packet of information find its way across the internet? The mathematical concept of graphs is

the underlying data structure.

This project is going to be about graphs. For this project, we will consider the task of finding a route

between two places.

Let us start by defining graphs. A graph is a collection of vertices. On paper, we represent vertices just by

single points. These vertices are connected to each other by edges. Two vertices connected by edges can

be seen as two points connected by lines. The following image shows an example of a graph.

From this graph, we can conclude some simple things about it. First is that there are 6 vertices in total,

and there are 5 edges in total. From the perspective of how the vertices are connected, to each other, we

can make the following observations.

(a) Vertex 0 is connected to vertex 2 and vertex 4.

(b) Vertex 1 is connected to vertex 2 and vertex 5.

(c) Vertex 2 is connected to vertex 0, vertex 1 and vertex 3.

(d) Vertex 3 is connected to vertex 2 only.

(e) Vertex 4 is connected to vertex 0 only.

(f) Vertex 5 is connected to vertex 1 only.

We should note, to be mathematically precise, that in this graph we have only these edges and no other

edges.

0 1

2 5

4 3

Such a model can be used to mimic several systems that we see around us. An example is as follows. We

can have places (state, city, house) represented by vertices. We are going to model the edges as follows.

For instance, if place a and place b are connected by a road directly, then we put an edge between vertex

a and vertex b. We can also show the length of that road. Note that one road is represented by one edge in

the graph. We can show the length of that road by labelling the edge with a number. We show an example

in the following figure.

We have colored red the numbers that we have used to label the edges. We also call those numbers the

weight of the edges, in the sense that they represent the cost of reaching from one vertex to another (cost

of travelling between those vertices). We can make the following observations about this graph.

(a) The cost of travelling between place 0 and place 2 is 4.

(b) The cost of travelling between place 0 and place 4 is 8.

(c) The cost of travelling between place 1 and place 2 is 5.

(d) The cost of travelling between place 1 and place 5 is 2.

(e) The cost of travelling between place 2 and place 3 is 1.

Remember that the weight of an edge, in this case, is representing the cost of travelling between a pair of

vertices.

We can represent a graph in Python by using a 2-D list (two-dimensional list), also known as a matrix.

Think about a matrix as an excel sheet. Each element in the outer list is a list that represents the row and

each element in the inner list is a cell. We can do this as follows: Given that the number of vertices is n,

then the list that we construct will be an n ⨉ n list. For this project, all matrices will be square, that is

every list in the two-dimensional list will be the same size. An example is as follows.

0 1 2 3 4 5

0 0 0 4 0 8 0

1 0 0 5 0 0 2

2 4 5 0 1 0 0

3 0 0 1 0 0 0

4 8 0 0 0 0 0

5 0 2 0 0 0 0

1

2

5

4

0 1

2 5

4 3

8

Let this matrix (list-of-lists) be called G. We call G the adjacency matrix of the graph drawn above. In G,

the cell at a-th row and b-th index of that row is equal to the weight of the edge that is connecting the

vertex a and vertex b. So G[a][b] is equal to the weight of the edge, and so G[b][a] is also equal to the

same weight. This symmetry makes our task easier. This symmetry also signifies that not only we can

travel from a to b, we can also travel from b to a. For example,

(a) G[0][2] = G[2][0] = 4,

(b) G[1][5] = G[5][1] = 2,

(c) G[2][3] = G[3][2] = 1, and so on.

Observe that this matrix exactly corresponds to the graph drawn above.

Now let us suppose that we want to compute for each pair of places a and b, the shortest distance between

them. Let that G is the adjacency matrix constructed from the places and the distance to their nearest

neighbors, as given in the matrix above.

For example, the distance matrix (called D) of the above matrix will look like this.

0 1 2 3 4 5

0 0 9 4 5 8 11

1 9 0 5 6 17 2

2 4 5 0 1 12 7

3 5 6 1 0 13 8

4 8 17 12 13 0 19

5 11 2 7 8 19 0

In D, the cell at a-th row and b-th index of that row is the distance between a vertex a and vertex bW even

if there is no edge between a and b. For example, there is no edge between vertex 0 and vertex 1.

However, there is an edge between vertex 0 and vertex 2 and there is an edge between vertex 1 and 2. So

the distance between vertex 0 and 1 is equal to the distance between 0 and 2 plus the distance between 2

and 1: 4 + 5 = 9.

Similarly, we can also construct the (shortest) path matrix for each pair of places a and b. This matrix will

contain a shortest path between place a and place b at position [a][b].

A path matrix (corresponding to the adjacency matrix and the distance matrix drawn above) looks like

this:

0 1 2 3 4 5

0 0 [0, 2, 1] [0, 2] [0, 2, 3] [0, 4] [0, 2, 1, 5]

1 [1, 2, 0] 0 [1, 2] [1, 2, 3] [1, 2, 0, 4] [1, 5]

2 [2, 0] [2, 1] 0 [2, 3] [2, 0, 4] [2, 1, 5]

3 [3, 2, 0] [3, 2, 1] [3, 2] 0 [3, 2, 0, 4] [3, 2, 1, 5]

4 [4, 0] [4, 0, 2, 1] [4, 0, 2] [4, 0, 2, 3] 0 [4, 0, 2, 1, 5]

5 [5, 1, 2, 0] [5, 1] [5, 1, 2] [5, 1, 2, 3] [5, 1, 2, 0, 4] 0

We provide the function to compute both the distance matrix and path matrix; this function takes

the adjacency matrix as input, and returns both the distance matrix and path matrix.

This implies that, for example, if we have to travel from place 0 to place 5, then any shortest path will

have a length of 11, and there is a shortest path which is a sequence for 4 places, namely, 0,2,1, and 5.

(there can be other paths which are shortest paths, in the sense that their distance is equal to the shortest

path that we have computed)

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of