Assignment 6: Breadth-First Search

Objectives

to use queues
to use graphs
to implement elementary graph algorithms

Introduction

Recall the Travelling Salesperson assignment. We wish to add the following heuristic to the TSP program:

generate a list of all pairs of cities
sort that list in order of increasing distance, breaking ties arbitrarily
start with an empty partial tour
for each pair of cities, if they are not already connected by the partial tour and if each city in the pair is included in at most one other pair added previously, then add a segment between the two cities in the pair to the partial tour.

We can implement this heuristic with an undirected graph. The partial tour is represented by a graph, which initially has no edges in it. Adding a segment is adding an edge to the graph. Checking if two cities are already connected is checking if there is already a path between them in the graph. Checking how many pairs each city has already been included in is checking the degree of the corresponding vertices. Finally, to construct the final tour, you can find a path between the two vertices with degree 1.

Assignment

Part 1

Complete the implementation of a adjacency-list-based undirected graph in /c/cs223/hw6/Optional/lugraph.c to implement all of the functions declared in /c/cs223/hw6/Required/lugraph.h. In particular, complete the following functions:

lugraph_connected, which determines if there is a path in the graph between two vertices;
lugraph_bfs which performs breadth-first search on a graph and returns a pointer to an opaque lug_search struct that records information about the search, including the number of edges in the shortest path from the starting point of the search to each vertex in the graph, and the previous vertex on the shortest paths to all the reachable vertices;
lug_search_distance, which returns the distance from a starting vertex $v_1$ to a vertex $v_2$, given a pointer to a lug_search struct that resulted from starting BFS at $v_1$; and
lug_search_path, which returns the path from a starting vertex $v_1$ to a vertex $v_2$, given a pointer to a lug_search struct that resulted from starting BFS at $v_1$.

The lugraph_connected and lugraph_bfs functions should run in $O(n + m)$ time, where $n$ is the number of vertices in the graph and $m$ is the number of edges. The lug_search_distance functions should run in $O(1)$ time and the lug_search_path function should run in $O(k)$ time where $k$ is the number of edges in the returned path.

Your implementations should check those preconditions that it is possible to check in $O(1)$ time and return something appropriate so that programs do not crash or hang when they are not met.

There is an incomplete set of unit tests in /c/cs223/hw6/Required/lugraph_unit.c. Your makefile must create an executable called Unit that starts with the unit tests' main.

Part 2

Modify your TSP program to implement the above heuristic algorithm when -greedy is given as a method name. The tour output should start with the first city in the input file and should be ordered in the same way as for -insert. The -greedy method should execute in $O(n^3)$ time. All input and output formats remain the same. You will only be tested on the output of the -greedy method.

Example

[jrg94@cicada code]$ for i in `seq 1 17`; do ./Unit $i; done
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
PASSED
[jrg94@cicada code]$ ./TSP /c/cs223/hw2/Tests/8_cities.in -greedy
-greedy         :   9711.84 SEA YVR BWI DCA STL MCI DAL IAH SEA

Submissions

Submit a makefile with a default target that builds both the TSP and Unit executables, your log file, and your source code necessary to build the executables. Do not submit the provided location module or the lugraph.h header file. Your makefile should assume that those files have been copied into the current directory, but not that they are still in their original locations.