On this page:
1 Theme Song
2 The Testing Problem
3 Another Testing Strategy
4 Problem Statement
5 Efficiency
6 Built-Ins
7 Files
8 Handing In

MST

    1 Theme Song

    2 The Testing Problem

    3 Another Testing Strategy

    4 Problem Statement

    5 Efficiency

    6 Built-Ins

    7 Files

    8 Handing In

In this assignment you will implement solutions to the Minimum Spanning Tree problem.

1 Theme Song

Spanning Tree Song by Radia Perlman, Dawn Perlner, and Ray Perlner

NB: Radia Perlman is one of the “parents of the Internet”. You’re using her ideas and work to read this page and to listen to that song.

2 The Testing Problem

In general, given a graph, a solution must produce a tree (which is easy to check), one that spans (also easy), and one that is minimal. Unfortunately, there could be many solutions that are all minimal. We should recognize this situation: it makes it difficult to write concrete test cases!

We can still check the above properties for a small number of concrete cases. We can in principle also write an oracle, but the combinatorics are daunting: to confirm that a tree is minimal, we must in principle enumerate every single tree, calculate its weight, determine the minimum of these, and confirm that the algorithm produces a solution with this weight. The tricky problem, therefore, is determining the weight of a minimal solution.

3 Another Testing Strategy

In this assignment we will pursue another strategy to validate the “minimal” property. We have seen that there are multiple ways of computing minimal spanning trees. Therefore, in this assignment we will implement two different algorithms for the same problem. We will then measure the weights produced by the two solutions and check that they’re the same.

Of course, the fact that they produce solutions of the same weight doesn’t mean they are both correct: they could both be wrong! However, to produce the same wrong weight over many inputs, they must have a correlated error. (This error could, for instance, be in code they share, such as an implementation of union-find.) To account for the possibility of a correlated error, you should also test on at least a few inputs for which you know the definitive minimum.

4 Problem Statement

We will use the following Graph data definition:

data Edge:

  | edge(a :: String, b :: String, weight :: Number)

end

 

type Graph = List<Edge>

Graphs should not contain any loops (i.e., self-edges).

In this assignment, you will implement two MST solutions:
  • mst-prim :: Graph -> List<Edge>, which implements Prim’s algorithm.

  • mst-kruskal :: Graph -> List<Edge>, which implements Kruskal’s algorithm.

Note that Prim’s algorithm is extremely similar to Dijkstra’s, so this will be an opportunity to reinforce their similarities and differences.

You must consider edges to be undirected. However, the input will include edges in only one “direction”. For instance, a sample Graph might be [list: edge("A", "B", 3), edge("C", "B", 4), edge("C", "A", 5)].

It is possible for there to be multiple edges to exist between the same two vertices, but notice that they must be in the same direction. So it is valid to have: [list: edge("A","B",3), edge("A","B",5)] but not [list: edge("A","B",3), edge("B","A",5)].

Despite the fact that edges from "B" to "A", "B" to "C", and "A" to "C" are not explicitly listed, because the edges are undirected, you should treat them like they are there. (This implies that either version of a particular edge can be in the MST, but not both.) How you choose to handle this implementation-wise and testing-wise is left up to you.Hint: You could add all the edges in the opposite direction.

The weight of an edge can be 0 or negative. Furthermore, edges from a vertex to itself form a cycle. Such edges therefore create graphs but not trees.

Also implement:
  • generate-input :: Number -> Graph, which consumes a number and randomly produces a connected graph with that many vertices. How you actually do this is up to you; there’s no one “right” answer, and we’ll accept many different solutions so long as they incorporate randomness. (Note that a graph containing 0 or 1 vertices contains no edges, so make sure your output reflects this.)

  • mst-cmp :: Graph, (Graph -> List<Edge>), (Graph -> List<Edge>) -> Boolean, which consumes a well-formed graph and two purported MST implementations, applies both implementations to that graph, and returns true exactly when the two solutions are both trees, spanning, have the same weight, and only contain edges in the original graph.

We expect you to write a reasonable set of interesting manual tests for mst-prim, mst-kruskal, and mst-cmp. You must especially be manually checking that these compute minimal weight solutions, as discussed in Another Testing Strategy.

Finally, also implement:

5 Efficiency

We are not considering efficiency of implementation in this assignment, but we will check that you indeed implemented Prim’s and Kruskal’s algorithms correctly.

6 Built-Ins

In addition to the allowed functions in the general guidelines, you can also use immutable string dictionaries.

You can use any of the union-find implementations shown in class or in the textbook. You may use ref fields for that specific purpose. However, you are not allowed to use ref or any form of mutation elsewhere in your program.

7 Files

Template

(There is no Examplar for this assignment.)

8 Handing In

Submission Form