Week 08 Lab Exercise

Weighted Graphs and Grid Planning

Objectives

To explore an application of weighted graphs and minimum spanning trees
To gain a better understanding of minimum spanning trees and MST algorithms
To see how graphs might be used with real-world data

Admin

Marks: 5 (see the Assessment section for more details)
Demo: in the Week 8, 9 or 10 lab session
Submit: see the Submission section
Deadline to submit to give: 5pm Monday of Week 9
Late penalty: 0.2% per hour or part thereof deducted from the attained mark, submissions later than 5 days not accepted

Background

When dealing with weighted graphs in the real world, especially networks, there is often a desire to connect nodes in the cheapest way possible, as connecting or traversing nodes usually incurs material, labour or time costs. This is where minimum spanning trees are most useful.

A minimum spanning tree is a subset of the edges of a weighted graph that connects all the vertices together with the minimum possible total edge weight. Minimum spanning trees have applications in the design of networks, such as computer networks, telecommunications networks and transportation networks. They also have other practical applications such as in cluster analysis and circuit design. In this lab, we will focus on their use in designing electrical networks.

Setting Up

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/24T1/labs/week08/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then run the unzip command on the downloaded file.

If you've done the above correctly, you should now have the following files:

Makefile: a set of dependencies used to control compilation
Graph.h: the interface for the Graph ADT
Graph.c: an incomplete implementation of the Graph ADT
Pq.h: the interface for the Priority Queue ADT
Pq.c: a complete implementation of the Priority Queue ADT
place.h: the definition of the place and power line data types
gridPlanner.c: a main program to read in locations and design electrical grids
planner.c: an implementation of the grid-planning algorithm (incomplete)
planner.h: the interface to the grid-planning algorithm, used by gridPlanner.c
testGraphMst.c: a main program to test the minimum spanning tree algorithm
tests/: a sub-directory containing a collection of test cases

Once you've got these files, the first thing to do is to run the command

make

This will compile the initial version of the files, and produce the ./testGraphMst and ./gridPlanner executables.

File Walkthrough

Graph.h

Graph.h defines the interface to the Graph ADT. The graphs produced by this ADT are undirected, which means that edges are always bidirectional, and weighted, which means that each edge has a weight that indicates some kind of cost. The interface describes some additional rules/restrictions: edge weights are doubles and must be positive, and self-loops (edges going from a vertex to itself) aren't allowed.

Graph.c

Graph.c contains the implementation of the Graph ADT. The implementation is almost complete except for the GraphMst function, which computes the minimum spanning tree of a given graph. Completing this will be one of the tasks in this lab.

testGraphMst.c

testGraphMst.c reads in graph data from standard input, calls GraphMst to produce a minimum spanning tree of the graph, and then displays the result.

To read in a graph, the program first reads in an integer representing the number of vertices in the graph, and then reads in edges. Each edge is represented by three comma-separated values: two integers which are the endpoints of the edge and a double which is the weight of the edge. Here are some examples of entering graph data into the program:

./testGraphMst
3
0, 1, 5.0
0, 2, 4.0
1, 2, 3.0

...
./testGraphMst < tests/graphMst/1.in     # from a file
...

The program has two output modes. If not given any command-line arguments, the program will output the original graph and the minimum spanning tree in plain text.

./testGraphMst < tests/graphMst/1.in
Graph:
Number of vertices: 3
Number of edges: 3
Edge 0 - 1: 5.000000
Edge 0 - 2: 4.000000
Edge 1 - 2: 3.000000

Minimum Spanning Tree:
Number of vertices: 3
Number of edges: 2
Edge 0 - 2: 4.000000
Edge 1 - 2: 3.000000

If the program is given the command-line argument -v, it will output HTML instead. If you redirect the output to a .html file, you can open the file in your web browser, which will give you a nice visualisation of the result.

./testGraphMst -v < tests/graphMst/1.in > tests/graphMst/1.html
# now open the file in a web browser

Pq.h

Pq.h defines the interface to the priority queue ADT. A priority queue is somewhat like a queue except that each item has a priority, and items are removed in priority order. This particular priority queue stores edges and removes the edge with the lowest weight first (i.e., lower weight = higher priority).

place.h

place.h contains the definition of the place and power line data types used by the rest of the code. A place is represented by a name and two integers x and y representing its coordinates on a map. A power line is represented by the two locations which it goes between.

struct places and struct powerLines are structs, not struct pointers, so you should access them using the dot operator rather than the arrow operator. You can also easily create copies of struct places and new struct powerLines without using malloc.

gridPlanner.c

gridPlanner.c reads in a series of places from standard input (one per line), calls planGrid1 or planGrid2, which determine where to build power lines to minimise cost, and then displays the result. Like testGraphMst.c, this program also has two output modes: plain text and visualiser.

Every place is either a city or a power plant. Places are represented by four comma-separated values: (1) a string which is either "city" or "plant", (2) the name of the place, (3) its x-coordinate, and (4) its y-coordinate. See the input files in the tests/gridPlanner directory for examples.

planner.c

This file will contain the implementation of your grid planning algorithm. planGrid1 designs an electrical grid for the simple scenario where there may be many cities but just one power plant. planGrid2 handles more complex (but realistic) scenarios where there may be many power plants, and is left as a challenge task.

Task 1 - Finding a Minimum Spanning Tree

Implement the GraphMst() function in Graph.c which takes in a graph and returns a minimum spanning tree of the graph as a new graph. If the given graph has no minimum spanning tree, the function should return NULL. If the graph has multiple minimum spanning trees, you can return any of them.

You may use any minimum spanning tree algorithm you like. You can (and are encouraged to) make use of the priority queue ADT that we've supplied.

When you think you are done, use the make command to recompile the testGraphMst program and use the provided input files (and/or your own) in the tests/graphMst directory to test your code. Each input file t.in has a corresponding expected output file t.exp. For example:

./testGraphMst < tests/graphMst/1.in
Graph:
Number of vertices: 3
Number of edges: 3
Edge 0 - 1: 5.000000
Edge 0 - 2: 4.000000
Edge 1 - 2: 3.000000

Minimum Spanning Tree:
Number of vertices: 3
Number of edges: 2
Edge 0 - 2: 4.000000
Edge 1 - 2: 3.000000
./testGraphMst < tests/graphMst/1.in > tests/graphMst/1.out
# compare 1.out with 1.exp manually or with diff

A more interesting way to test is to add the -v flag to toggle the program's visualiser mode. This will cause the program to spew a bunch of HTML that isn't very useful on the terminal, so redirect the output to an .html file instead:

./testGraphMst -v < tests/graphMst/1.in > tests/graphMst/1.html

Now open the file in your web browser to get a nice visualisation of the result. For example, here is what the visualisation for 3.in should look like:

The edges of the MST (if it exists) will be highlighted in green. The vertices will always be initially arranged in a circle, but you can change how the graph looks by dragging the vertices around the canvas.

The .html file must be in the tests/graphMst directory for the visualiser to work, because the visualiser depends on other files in that directory (style.css and visualiser.js). Alternatively, you can move style.css and visualiser.js to the same directory as the .html file.

Task 2 - Finding the Cheapest Power Grid!

Implement the planGrid1() function in planner.c which takes an array of cities (of size numCities) and a power plant, and determines the most optimal (i.e., cost-minimising) configuration of power lines such that every city has access to electricity. The function should fill the given powerLines array with the required power lines and return the number of power lines stored in the array. If there are multiple optimal configurations, you can choose any of them.

You can make the following simplifying assumptions:

Cost is directly proportional to the total length of power lines used, so you should aim to minimise this total length.
Power lines can only be built between pairs of cities or between a city and a power plant, so you can't create a new place and build a power line to it.
You can assume the land is flat so that there is no additional cost from a difference in altitude. The cost of a power line between two locations $(x_1, y_1)$ and $(x_2, y_2)$ will therefore be directly proportional to $$ \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$

Please note that you are not required to calculate the total cost - you are only required to find the configuration of power lines that would minimise the cost.

When you think you are done, use the make command to recompile the gridPlanner program and use the provided input files (and/or your own) in the tests/gridPlanner directory to test your code. For example:

./gridPlanner < tests/gridPlanner/1.in
City Sydney at (870, 204)
City Melbourne at (727, 94)
City Adelaide at (581, 174)
City Alice Springs at (474, 469)
City Darwin at (406, 736)
City Perth at (65, 254)
City Brisbane at (910, 374)
Power Plant Canberra at (821, 165)
Power line between Sydney (870, 204) and Canberra (821, 165)
Power line between Sydney (870, 204) and Brisbane (910, 374)
Power line between Melbourne (727, 94) and Canberra (821, 165)
Power line between Melbourne (727, 94) and Adelaide (581, 174)
Power line between Adelaide (581, 174) and Alice Springs (474, 469)
Power line between Alice Springs (474, 469) and Darwin (406, 736)
Power line between Alice Springs (474, 469) and Perth (65, 254)
./gridPlanner < tests/gridPlanner/1.in > tests/gridPlanner/1.out
# compare 1.out with 1.exp

Each input file t.in has a corresponding expected output file t.exp, but you are not required to match the exact order of power lines or match the order of place names for each power line. For example, it would be valid for the power line between Sydney and Canberra to read:

Power line between Canberra (821, 165) and Sydney (870, 204)

You can also test by using the program's visualiser mode:

./gridPlanner -v < tests/gridPlanner/1.in > tests/gridPlanner/1.html

Here is what the visualisation for 1.in should look like:

The .html file must be in the tests/gridPlanner directory for the visualiser to work, because the visualiser depends on other files in that directory (style.css and visualiser.js). Alternatively, you can move style.css and visualiser.js to the same directory as the .html file.

Optional Challenge Task

Implement the planGrid2() function in planner.c which also designs a minimal cost electrical grid, but can take into account multiple power plants, unlike planGrid1(). You can make the same simplifying assumptions as in the previous task.

When you think you are done, use the make command to recompile the gridPlanner program and run it with the provided input files tests/gridPlanner/challenge1.in and tests/gridPlanner/challenge2.in. For example, here's what the visualisation for 8.in should look like:

Submission

You need to submit two files: Graph.c and planner.c. You must submit all of these files, even if you did not complete all of the tasks. You can submit via the command line using the give command:

give cs2521 lab08 Graph.c planner.c

You can also submit via give's web interface. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

Assessment

Most of the marks for this lab will come from automarking. To receive the rest of the marks, you must show your work to your tutor during your Week 8, 9 or 10 lab session. You will be marked based on the following criteria:

Aspect	Marks	Criteria
Code correctness	4	These marks will come from automarking. Automarking will be run after submissions have closed. After automarking is run you will be able to view your results here.
Code style	1	This mark is based on your code style in Tasks 1 and 2. Code with good style should have these qualities: consistent indentation and spacing, no repetition of code, no overly complicated logic, no overly long functions, correct use of C constructs (such as `if` statements and `while` loops), and comments where appropriate. See the style guide.