Lab: Digraphs

In this lab, you will write code to calculate basic digraph statistics.

Instructions

You should complete this lab individually.

Background

There are multiple ways to represent digraphs in computer programs. In this lab, you will work with a Python program that represents digraphs using a dictionary of sets.

Step 1: Review Starter Code

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

• argparse
• defaultdict
• property

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

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

Calculate digraph 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 digraph:

This digraph can be input to digraphs.py by running:

> python digraphs.py a "b c" "c b" "d e" "e f" "f f"
Size: 6
Maximum in-degree: 2
Maximum out-degree: 1
Minimum in-degree: 0
Minimum out-degree: 0

Step 2: Implementation

Implement these methods:

• size
• in_degree
• out_degree

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

Finally, test your code with several different digraphs.

Optional: Visualize Digraphs using Graphviz

Graphviz is a tool for visualizing directed and undirected graphs. If you have time, install Graphviz and use it to render some digraphs.

• First, download digraph.dot, which contains the source code for the digraph from Step 1.
• Next, install Graphviz by following the instructions for your platform
  • On macOS, install graphviz-gui via MacPorts
  • On Windows, use the latest 64-bit EXE installer. Accept the option to add Graphviz to your PATH.
• Then, use Graphviz to render digraph.dot. You should see the digraph from Step 1.
  • On macOS, open digraph.dot using the “Graphviz” app installed in /Applications/MacPorts/
  • On Windows, use the dot command in the terminal to save a PNG image of the digraph using:

    dot -Tpng digraph.dot -o digraph.png
    

Familiarize yourself with Graphviz’s DOT language by comparing the data in digraph.dot to the digraph rendered by Graphviz.

Finally, consider modifying the Digraph class’s __str__ method to output DOT code for Graphviz.

Submit

Upload digraphs.py to Gradescope.

Learning Goals

• Understand how digraphs are represented in programs
• Calculate digraph statistics