COMPSCI 1JC3
Introduction to Computational Thinking
Fall 2021
Assignment 3
Dr. William M. Farmer and Curtis D’Alves
McMaster University
Revised: November 4, 2021
The purpose of Assignment 3 is to write a module in Haskell that im-
plements a simple library for working with a directed graph data structure.
The requirements for Assignment 3 are given below. Please submit Assign-
ment 3 as a single Assign 3.hs file to the Assignment 3 folder on Avenue
under Assessments/Assignments. Assignment 3 is due Sunday, Nov 21,
2021 before midnight. Assignment 3 is worth 10% of your final grade.
Although you are allowed to receive help from the instructional
staff and other students, your submitted program must be your
own work. Copying will be treated as academic dishonesty!
1 Background
Graph theory is a field of mathematics that deals with the study of graphs,
mathematical structures that model relationships between pairs of objects.
In computer science, we conceptualize graphs as abstract data structures
composed of nodes (a.k.a., vertices, points, or objects) and edges (a.k.a., links,
lines, or relations) between these nodes. Edges can be directed or undirected,
as illustrated in Figure 1.
Different graph structures can model many problems in software: you
might use them to model a peer-to-peer network, people and their friends on
a social media site, a map of places and roads connecting them, and many
more abstract problems. There are also many famous algorithms that deal
with graph processing, including Dijkstra’s shortest path, Ford-Fulkerson
maximum flow, Prim’s minimum spanning tree, and many more.
(a) Undirected Graph (b) Directed Graph
Figure 1: Example Graphs
1
There are numerous ways to represent graphs as data structures, one
simple way is to keep a pair of lists, one for nodes and the other for edges.
This approach is inefficient but simple. For example, we could define such
a data structure in Haskell using the following type declarations:
1 data Graph = Graph [Node] [Edge]
2 data Edge = (Node,Node)
3 data Node = …
The definition of Node would depend on what information you would
like each node to contain. Note: this can be interpreted as a directed graph,
where the first node has a directed edge pointing to each node in the list of
nodes paired with it. Take Figure 2 as an example.
1 a,b,c :: Node
2 nodes = [a,b,c]
3 edges = let
4 a’ = getNodeID a
5 b’ = getNodeID b
6 c’ = getNodeID c
7 in [(a ’, b ’),( a ’, c ’)
8 ,( c ’, a ’),( c ’, c ’)]
9
10 graph :: Graph
11 graph = Graph nodes edges
(a) Example Haskell Encoding
(b) Corresponding Visualization
Figure 2: Graphs in Haskell
2 The Assignment
The purpose of Assignment 3 is to write a module in Haskell that implements
a simple library for working with a directed graph data structure
2.1 Requirements
Download from Avenue Assign3 Project Template.zip which contains
the Stack project files for this assignment.
The file contains type definitions that can be used to represent a directed
graph, using the Haskell graph encoding described (see the Background sec-
tion for details).
1 −− A ‘‘graph with node type n’’ is a list of nodes and a list of edges
2 type Graph n = Graph { getNodes :: [Node a]
3 , getEdges :: [Edge] }
4
5 −− An edge is the ID of another node
2
6 type Edge = (NodeID,NodeID)
7 type NodeID = Int
8
9 −− A ‘‘node of type a’’ is a value of type ‘‘ a ’’ along with an ID
10 data Node a = Node { getNodeID :: NodeID
11 , getNodeVal :: a }
Each Node contains a value (of any type ‘‘a’’) and a unique NodeID. This
allows two nodes to hold the same value while being distinguishable from
each other. The list Edges references these NodeID rather than the nodes
themselves.
Modify the Assign 3.hs in the src folder so that the following require-
ments are satisfied.
1. Add your name, the date, and “Assignment 3” in the comments at the
top of your file. Define macid to be your MacID.
2. The file includes a function named maxNodeID of type Graph a ->
Maybe NodeID that returns the largest NodeID in a Graph.
3. The file includes a function named insertNode of type a -> Graph a
-> Graph a that inserts a new Node with the given value into a Graph.
The new NodeID should be the previously largest NodeID plus one. If
the graph has no nodes, then NodeID should be 0.
4. The file includes a function named removeNode of type NodeID ->
Graph a -> Graph a that removes any Node with the given NodeID
(including occurrences of NodeID in edges) from the given Graph.
5. The file includes a function named lookupNode of type NodeID ->
Graph a -> Maybe (Node a) that returns the Node corresponding to
the given NodeID in the given Graph. If no Node with NodeID exists,
the function returns Nothing.
6. The file includes a function named insertEdge of type Eq a =>
(NodeID,NodeID) -> Graph a -> Maybe (Graph a) that inserts an
edge from the Node with the given NodeID in the first part of the tuple
to the Node with the given NodeID in the second part of the tuple.
If the edge already exists, it should NOT introduce a duplicate. If
the nodes corresponding to either of the given NodeIDs do not already
exist, the function should return Nothing.
7. Your file can be imported into GHCi and all of your functions perform
correctly.
HINT: Do not be afraid to define extra auxiliary functions, particularly to
help with the implementations of removeNode and insertEdge.
3
2.2 Testing
Include in your file a test plan for the functions maxNodeID, insertNode,
removeNode, lookupNode, and insertEdge. The test plan must include at
least three test cases for each function. Each test case should have following
form:
Function: Name of the function being tested.
Test Case Number: The number of the test case.
Input: Inputs for function.
Expected Output: Expected output for the function.
Actual Output: Actual output for the function.
The test plan should be at the bottom of your file in a comment region
beginning with a {- line and ending with a -} line.
4
Background
The Assignment
Requirements
Testing