Lab: Undirected Graphs

In this lab, you will modify the code from the digraphs lab to represent undirected graphs.

Instructions

You should complete this lab individually.

Background

In the digraphs lab, the Python code represented digraphs using a dictionary of sets. Each set element represented an arc from that vertex. Undirected graphs can be represented in a similar way, except that edges must be stored in the sets associated with both incident vertices.

Step 1: Review Starter Code

Download and review the starter code, consulting the Python documentation for:

Use the --help option to see program’s command-line interface:

> python graphs.py -h
usage: graphs.py [-h] [vertices ...]

Calculate graph statistics.

positional arguments:
  vertices    A lone vertex (e.g., "x") or a pair of vertices (e.g., "x y")

options:
  -h, --help  show this help message and exit

Consider the graph:

A graph with six vertices: a, b-c, d-e, e-f, f-d.

This graph can be input to graphs.py by running:

> python graphs.py a "b c" "d e" "e f" "f d"
Size: 6
Maximum degree: 2
Minimum degree: 0

Step 2: Implementation

Implement these methods:

Then, update the code in the main method to calculate maximum/minimum degree.

Finally, test your code with several different graphs.

Optional: Implement Edge Weights

For some applications, it is important to associate weights with edges. Consider modifying your program to store edge weights. For example, you could input edge weights by running:

> python graphs.py a "b c 1.0" "d e 1.5" "e f 1.5" "f d 3.0"

Submit

Upload graphs.py to Gradescope.

Learning Goals