12-02 MST Testing

Minimal Spanning Tree: Basic Version

We discussed in class a method for creating a minimal spanning tree from a weighted graph. If you need to look it up, it is known as Prim’s Algorithm.

from typing import List, Dict, Tuple, Set
def spanning_tree(g: WeightedGraph, start: Vertex)
                 -> Set[Tuple[Vertex, Vertex]]: 
    answer = set()
    return answer

Data to produce

Create a function that finds a minimal spanning tree of a random graph with n vertices and 10*n edges. Produce a table of timing values for n=[50,100..500] and graph your results.

Random Graph

  • wg.insert_weighted_edge(self, start, end, wt)
  • WeightedGraph.random(n_vertices, n_edges, max_weight): Add random edges with weight randomly selected in range(max_weight).

Timing

  • import timeit
  • timeit.timeit(func, number=5): Produce time by running func five times. The function must take no arguments.

When you are timing your code, you should make sure you only compute the time for the actual algorithm, not any setup. In this case, that means not including the random graph generation in your timings.

Suggested organization:

  • st_timing(wg: WeightedGraph) -> float: A function to time your algorithm given a weighted graph. This function uses timeit.
  • st_random_timing(n_vertices: int, n_edges: int) -> float: A function that generates your random graph and then calls the st_timing function on it.
  • st_summary(): Generate a list of ordered pairs and print out the data in a format usable by your graphing tool (e.g., “n, timing_result,” on each line).

Graphing Results

It is important to visualize your results. Sometimes trends or mistakes are clear from a picture but hard to see in the raw numbers.

You can use any method you would like to make a line graph. One possibility is Google Sheets.

  • Paste your timings into a Google Sheet.
  • Use =split(CELL, ',') to break up the x and y coordinates of your pairs.
  • Select the columns with the separate x and y values and Insert -> Chart to create a line graph.