lab_adjMatrix

Learning Objectives

• Experience implementing core graph ADT functions using adjacency matrices

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 adjacency matrix is one of the three core graph implementations we will cover in this class (and one of the two which are meaningfully useful). Here you will be implementing the remaining ‘core’ operations that we saw in class but did not code (plus one additional method just for fun!).

For full credit here, you must implement:

• insertVertex
• removeVertex
• insertEdge
• removeEdge
• getDegree

NOTE: The only function you have to code that actually returns a value is getDegree(). All other functions should modify the input graph directly.

insertVertex()

# INPUT:
# An input graph (as an adjacency Matrix)
# A vertex label (v)
# Here our labels will be either an int, a float, or a string
# You may assume that all vertices are unique
# (The label being added is NOT already in the graph)
# Output:
# Nothing
# Instead add the vertex to the adjacency matrix
# HINT: Be sure you add the vertex *everywhere* it needs to be
None insertVertex(adjMatrix inGraph, string v):

The adjacency matrix (as seen in class) consists of a vertex dictionary and a 2D matrix of edges. Consider carefully what modifications you must make to inGraph to add a new vertex.

removeVertex()

# INPUT:
# An input graph (as an adjacency Matrix)
# A vertex label (v)
# Here our labels will be either an int, a float, or a string
# You may assume that the vertex being removed exists
# Output:
# Nothing
# Instead remove the vertex from the adjacency matrix
# HINT: Be sure you remove the vertex *everywhere*
None removeVertex(adjMatrix inGraph, string v):

Like with insertVertex(), consider carefully what modifications you must make to inGraph to completely remove an existing vertex. As a hint, make sure your ending graph is internally consistent and has no connections to the removed vertex.

addEdge()

# INPUT:
# An input graph (as an adjacency Matrix)
# Two vertex labels (u and v)
# Here our labels will be either an int, a float, or a string
# You may assume that all input vertices are unique and exist
# Output:
# Nothing
# Instead add the edge to the adjacency matrix
# Warning: The autograder may try to add the same edge twice
# Your code should be able to handle these cases 
# (adding an existing edge does nothing)
None insertEdge(adjMatrix inGraph, string u, string v):

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.

removeEdge()

# INPUT:
# An input graph (as an adjacency Matrix)
# Two vertex labels (u and v)
# Here our labels will be either an int, a float, or a string
# You may assume that all input vertices are unique and exist
# Output:
# Nothing
# Instead add the edge to the adjacency matrix
# Warning: The autograder may try to remove the same edge twice
# Your code should be able to handle these cases 
# (removing an missing edge does nothing)
None removeEdge(adjMatrix inGraph, string u, string v):

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.

getDegree()

# INPUT:
# An input graph (as an adjacency Matrix)
# A vertex label (v)
# Here our labels will be either an int, a float, or a string
# You may assume that all input vertices are unique and exist
# Output:
# An integer storing the number of adjacent vertices to node v
int getDegree(adjMatrix inGraph, string v):

Lastly write a function that takes in a vertex and returns a count of the total number of adjacent vertices. This can include the vertex itself (if the self-loop edge (v, v) exists).