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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

I need this python project finished by tonight please help

 

 

Assignment Specifications

The assignment contains the construction of the following class which goes in your place.py file. Do

not put it in your proj11.py file.

class Place:

(a) __init__(self, name, i):

Initialize self.name as the parameter name, a string.

self.index is a unique identifier of this Place. Initialize self.index as the

parameter i, an int. This index identifies the index needed to index the “g” and “paths”

parameters in set_distances and set_paths.

self.dist is the list of distances from other Places. Initialize self.dist as

None. (We are initializing this list to None because we will be assigning a value to

self.dist, not appending to an existing list. Using None helps us remember to not

append.)

self.paths is the list of paths from other Places. Initialize self.paths as

None.

Argument: self, string, integer

Return: no return value

(b) get_name(self):

This method will simply return self.name.

Argument: self

Return: string

(c) get_index(self):

This method will simply return self.index.

Argument: self

Return: int

(d) set_distances(self, g):

This method sets the distances of this Place from other Places in the list

self.dist. The parameter g is a list of lists of those distances. The value of the

self.dist list is its index in the parameter g. That is, self.dist will be equal to

the (self.index)-th list in g.

Hint: use [:] to make a copy when assigning self.dist so this Place instance will

have its own copy of the list of distances from other Places. That is, use

g[self.index][:]

Argument: self, list of lists

Return: None

(e) set_paths(self, paths):

This method is nearly identical to the set_distances method. This method sets the

paths from this Place to other Places in the list self.paths. The parameter

paths is a list of lists of those paths. The value of the self.paths list is its index in

the parameter paths. That is, self.paths will be equal to the (self.index)-th list

in paths. As with the previous method, make a copy of the list of paths.

Argument: self, list of lists of lists

Return: None

(f) get_distance(self, j):

This method will return self.dist[j] which is the distance between this Place

instance, self, and Place j in the list of distances to other Places.

Argument: self, integer

Return: float

(g) get_path(self, j):

This method will return self.path[j] which is a shortest path between this Place,

self, and the Place j in the list of paths to other Places.

Argument: self, integer

Return: list

(h) __str__(self):

This method will return a formatted string representation of this Place instance. Begin

by making a tuple

tup = ( self.index, self.name, self.dist, self.paths)

These are the only four values which identify a place.

Return a string using the following format on that tuple:

"Node {}, {}: distances {}, paths {}"

Argument: self

Return: string

Hint: We can use * to “move” items out of a list/tuple, and into a formatted string.

Ex:

my_list = [“I”, “am”, “awesome”]

“{} {} {}”.format(*my_list)

 I am awesome

(i) __repr__(self):

This method will also return an unformatted string representation of this Place instance.

Create the same tuple created in __str__ but simply return str(tup).

Argument: self

Return: string

The assignment contains the following functions that go in your proj11.py file.

(a) open_file():

This function repeatedly prompts the user for a filename until the file is opened successfully. An

error message should be shown if the file cannot be opened. It returns a file pointer. Use tryexcept to determine if the file can be opened.

Argument: no argument

Return: <file_pointer>

(b) read_file(fp):

This function reads a file pointer fp and returns a list of tuples L.

Each row of the file contains a pair of places and the distance between them (e.g., via a road

connected them both). Each tuple will have the following structure:

(<place_1>,<place_2>,<distance between place_1 and place_2>)

place_1 and place_2 must be arranged strictly as written in the file.

Remember that the places are strings and the distance between them is an int.

So your tuple will have

(str, str, int)

For example, the file map0.csv is

 City 1,City 2,Distance

 A,X,7

 A,E,8

 Y,X,5

 Y,F,2

 X,D,1

So the list of tuples returned will be

[('A', 'X', 7), ('A', 'E', 8), ('Y', 'X', 5), ('Y', 'F', 2), ('X', 'D', 1)]

Argument: <file_pointer>

Return: <list_of_tuples>

(c) adjacency_matrix_construction(L):

This function takes a list of tuples L as argument where each tuple is of the structure we discussed

in read_file()). It will return two items: a list of places in L, and the adjacency matrix of

distances between places.

First, build the list of places (you will need this list for the second part of this function).

Let’s name the list: places_lst. It is a list of strings.

Read through the list of tuples L and make a list of all the places that appear in any tuple.

No place can be repeated in this list. Sort the list alphabetically (even if the places are digits).

Hint: a set is a useful intermediate data structure to get a collection of unique items.

For example, if L (from map0.csv) is

L = [('A', 'X', 7), ('A', 'E', 8), ('Y', 'X', 5), ('Y', 'F', 2), ('X', 'D', 1)]

Then places_lst will be

places_lst = ['A', 'D', 'E', 'F', 'X', 'Y']

Let that the length of places_lst be n.

Create an n x n matrix g initialized to zeros. Remember that an n x n matrix can be represented

by a list of lists where each row is a list. In this case, there will be n rows where each row will be

initialized to be a list of n zeros. So a 6x6 matrix will be initialized as

g = [ [0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0],

[0,0,0,0,0,0], [0,0,0,0,0,0]]

Next we need to fill the matrix g with values (noting that many zeros will remain as zeros).

The information we need is in the parameter L, the list of tuples, and in places_lst.

We use places_lst to get a place’s index, e.g. ‘A’ is at index 0; ‘X’ is at index 4, and so on.

We use L to get the distance, so the first tuple of L is ('A', 'X', 7)which tells us that the

distance between ‘A’ and ‘X’ is 7. Since ‘A’ is at index 0 in places_lst and ‘X’ is at index 4

in places_lst, we will assign g[0][4] = 7 and since the distance from ‘A’ to ‘X’ is the

same as the distance from ‘X’ to ‘A’ we also assign g[4][0] = 7. Walk through every tuple

in L, find the indices of the places in the tup, and then assign distances in g. 

In this example, the resulting adjacency matrix g will be:

 [ [0 , 0 , 8 , 0 , 7 , 0 ]

 [0 , 0 , 0 , 0 , 1 , 0 ]

 [8 , 0 , 0 , 0 , 0 , 0 ]

 [0 , 0 , 0 , 0 , 0 , 2 ]

 [7 , 1 , 0 , 0 , 0 , 5 ]

 [0 , 0 , 0 , 2 , 5 , 0 ] ]

Argument: <list_of_tuples>

Return: <list_of_strings>, <list_of_lists_of_integers>

(d) make_objects(places_lst, g):

This function takes the list of places places_lst and the adjacency matrix g as

arguments and returns a dictionary of Place objects that are in the places_lst. Actually,

we will return two dictionaries: one indexed by name and one indexed by id because

sometimes we want to find a Place by name and sometimes by id.

This function will invoke the provided function apsp() on top of your draft file by passing

g to it, and it will take the return value in variables g, paths. The variable g is a matrix

that now contain the shortest distances between each pair of places; whereas paths is a

matrix that contain a shortest path between each pair of places.

Next create the dictionaries of Place objects:

for each index i of places_lst, you will (Hint: use for … enumerate)

a) create an object a_place for a place by initializing it with the place’s name (found

in places_lst[i] and the place’s index i

b) Set the variable self.dist of this place by invoking the set_distances() method for

your a_place object by passing g to it.

c) Set the variable self.path of this place by invoking the set_paths() method for

your a_place object by passing paths to it.

d) Now add your a_place object to the indexed-by-name dictionary and the other

a_place object to the indexed-by-id dictionary. Note that because the places_lst

was created to have no duplicates (part of its specification), you do not have to

worry about handling duplicates when creating dictionary entries.

Argument: <list_of_strings>, <list_of_lists_of_integers>

Return: <dict_of_objects>, <dict_of_objects>

(e) main()

(i) Open file. Invoke open_file(). Store the return value in fp.

(ii) Read the file. Invoke read_file() by passing the argument fp to it. Store the return value

in L.

(iii) Construct the adjacency matrix. Invoke adjacency_matrix() by passing the argument L

to it. Store the return values in places_lst, g.

(iv) Make place objects. Invoke make_objects() by passing the arguments places_lst and g to

it. Store the return value in name_dict_of_places, id_dict_of_places.

You now have a dictionary of Place objects (two dictionaries to make life easier).

(v) Execute the following instructions again and again until the user terminates.

A. Display banner

B. Enter starting place. If it is ‘q’ , end the program, otherwise check the validity

of the outputIf not valid reprompt until it is valid.

C. Loop until the user enters `end’.

a. Enter next destination (a name as a string)

Error check: destination is in places_lst and this destination is not

the same as the previous destination

b. Store each destination (as a name string) in a list route_lst

You now have an ordered list of destinations on your route.

It is simply a list of names (strings).

D. Taking stock: You will need to determine two things that you need in Step E.

This code goes along with Step E, not separately. They are essentially the same

step, but we broke it down for understanding.

a. A path containing intermediate destinations to get to places on your

route. For example, to drive from Lansing to Chicago the shortest path

may take you by Benton Harbor. You need to find Lansing’s Place

object and get the path from Lansing to Chicago with the call:

Lansing_Place_Object.get_path(‘Chicago’)

but instead of “Chicago” you will use Chicago’s ID so it will actually be

Lansing_Place_Object.get_path(Chicago_ID)

How do you find Lansing’s Place Object? You have a dictionary of

place objects named name_dict_of_places that you can index by name so

Lansing’s Place Object will be at name_dict_of_places[‘Lansing’].

Similarly, you can find Chicago’s Place Object and then use that to get

its ID using Chicago_Place_Object.get_index().

Note that its ID is actually an index into the adjacency matrix.

b. A distance. Continuing our example, you need to find the distance from

Lansing to Chicago which you can find in

Lansing_Place_Object.get_distance(Chicago_ID)

(If you are wondering, the path such as through Benton Harbor is already

considered in this distance value.)

E. Initialize a path list. Initialize a distance. Then loop through your route list

a. Add to your path: the intermediate nodes to the next destination

Error check: if there is no path, print an error message (see Note II

below)

b. Add to the distance: the distance to the next destination.

F. If there is a path, output the path and its distance

 

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