lab_adjList

Learning Objectives

• Experience implementing core graph ADT functions using adjacency lists
• Explore how a weighted input adjusts the graph structure

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 list 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!). However as a fun twist this week instead of using the adjacency list as seen in class, you will be performing these operations on a weighted adjacency list.

For full credit here, you must implement:

• insertVertex
• removeVertex
• insertEdge
• removeEdge
• getAllEdges

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

insertVertex()

# INPUT:
# An input graph (as an adjacency list)
# 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 list
None insertVertex(adjList inGraph, string v):

The adjacency list (as seen in class) consists of single dictionary with vertices as keys and a list of vertices as values. Edges are tracked by looking up the starting vertex as a key and finding the ending vertex in the list of values. Consider carefully what modifications you must make to inGraph to add a new vertex to a weighted adjacency list.

removeVertex()

# INPUT:
# An input graph (as an adjacency list)
# 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(adjList 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:
# A weighted adjacency list (inGraph)
# Two vertex labels describing the new edge being added (u and v)
# An integer (or float) containing the weight of the corresponding edge (weight)
# OUTPUT:
# Nothing
# Instead add the edge to the graph
# NOTE: You may assume u and v are already in the graph
# and that the edge does not already exist
None insertEdge(adjList inGraph, string u, string v, int weight):

Completing this function requires a firm understanding of the underlying data storage structures of the adjacency list. 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. Additionally consider how the inclusion of weights will alter the storage structure (and your function).

removeEdge()

# INPUT:
# A weighted adjacency list (inGraph)
# Two vertex labels describing the new edge being removed (u and v)
# OUTPUT:
# Nothing
# Instead remove the edge from the graph
# NOTE: You may assume u and v are already in the graph
# However the actual edge from u to v might not exist
# Your code should be able to handle those cases
# (Removing an edge that doesnt exist does nothing)
None removeEdge(adjList inGraph, string u, string v):

Completing this function requires a firm understanding of the underlying data storage structures of the adjacency list. 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)
# An edge weight (inWeight)
# Output:
# A list of size-3 tuples containing all edges of weight inWeight 
# The format should be: (<vertex v>, <vertex u>, <weight)
# Given that our graph is undirected, every edge should be given twice
# (You will always find matching edges (A, B, inWeight) and (B, A, inWeight))
# If there are no edges of the input weight, you should return an empty list.
tuple(v, u, w) getAllEdges(adjList inGraph, int inWeight):

Lastly write a function that takes in a weight and returns the full list of edges containing this weight. Given an undirected graph, every edge should be given twice.