lab_graph

Learning Objectives

• Practice coding data structure implementations using lists and matrices
• Review a conceptual understanding of graph implementations by coding key functions
• Compare and contrast the efficiency of edge list and adjacency matrix

Submission Instructions

Using the Prairielearn workspace, test and save your solution to the following exercises. (You are welcome to download and work on the files locally but they must be re-uploaded or copied over to the workspace for submission).

Assignment Description

The edge list and adjacency matrix are two of the three core graph implementations we will cover in this class. Here you will be implementing some of the insert and remove functions we covered conceptually in class but did not code up.

For full credit here, you must implement:

• el_insertVertex
• el_insertEdge
• am_insertVertex
• am_removeVertex
• am_insertEdge
• am_removeEdge

NOTE: All functions in this assignment should modify the input graph (either el for edgeList or am for adjMatrix) directly.

el_insertVertex()

# INPUT:
# el, an edgeList object containing the graph of interest
# v1, a vertex label that must be added to the graph
# OUTPUT:
# None, instead the graph should be modified to contain v1
def el_insertVertex(el, v1):

The edge list (as defined by a vote in lecture) consists of a vertex list and a list of edges. Consider carefully what class variables need to be updated to insert a single vertex.

el_insertEdge()

# INPUT:
# el, an edgeList object containing the graph of interest
# v1, the starting vertex label of the edge being added to the graph
# v2, the ending vertex label of the edge being added to the graph
# OUTPUT:
# None, instead the graph should be modified to contain the edge (v1, v2)
# If v1 or v2 is a new label, it should also be added to vertex list!
def el_insertEdge(el, v1, v2):

The edge list (as defined by a vote in lecture) consists of a vertex list and a list of edges. Consider carefully what class variables need to be updated to insert a single edge, potentially comprising new vertex labels.

am_insertVertex()

# INPUT:
# am, an adjMatrix object containing the graph of interest
# v1, a vertex label that must be added to the graph
# OUTPUT:
# None, instead the graph should be modified to contain v1
# HINT: Be sure you add the vertex *everywhere* it needs to be
def am_insertVertex(am, v1):

The adjacency matrix (as seen in lecture) consists of a vertex dictionary and a 2D matrix of edges. Consider carefully what class variables need to be updated to insert a single vertex.

am_removeVertex()

# INPUT:
# am, an adjMatrix object containing the graph of interest
# v1, a vertex label that must be removed from the graph
# OUTPUT:
# None, instead the graph should be modified to completely remove v1
# This means removing it from both vertices and edge list
# NOTE: This also requires adjusting the index values in the dictionary!
def am_removeVertex(am, v1):

Like with am_insertVertex(), consider carefully what modifications you must make to the input adjMatrix to completely remove an existing vertex. As a hint, make sure your ending graph has no connections to the removed vertex and has appropriate index values for all of the remaining items in your dictionary.

TIP: The python pop() method works for lists when given an index and for dictionaries when given a key value.

am_insertEdge()

# INPUT:
# am, an edgeList object containing the graph of interest
# v1, the starting vertex label of the edge being added to the graph
# v2, the ending vertex label of the edge being added to the graph
# OUTPUT:
# None, instead the graph should be modified to contain the edge (v1, v2)
# If v1 or v2 is a new label, it should also be added to vertex list!
def am_insertEdge(am, v1, v2):

Completing this function requires a firm understanding of the underlying data storage structures of the adjacency matrix. Consider how you might find a specific edge value given two input strings and how you would modify that value to ‘insert’ a new edge.

Your code should be relatively simple if both vertices exist in the matrix already but may require making larger adjustments to the data structure if one (or both) of the vertices defining the edge is new.

am_removeEdge()

# INPUT:
# am, an edgeList object containing the graph of interest
# v1, the starting vertex label of the edge being added to the graph
# v2, the ending vertex label of the edge being added to the graph
# OUTPUT:
# None, instead the graph should be modified to not contain the edge (v1, v2)
# You may assume both v1 and v2 already exist in the adjacency matrix
def am_removeEdge(am, v1, v2):

Completing this function requires a firm understanding of the underlying data storage structures of the adjacency matrix. Consider how you might find a specific edge value given two input strings and how you would modify that value to ‘remove’ an edge. You may assume that the vertices already exist.