## Description

1 Introduction

I wonder why it is that when I plan a route too carefully, it goes to pieces,

whereas if I blunder along in blissful ignorance aimed in a fancied

direction I get through with no trouble.

—John Steinbeck, Travels with Charley: In Search of Amerca

Denver Long decides to augment his income during his retirement years by selling the fine products

produced by the Shinola Corporation. He enjoys driving his Lincoln, and so it’s the life of a traveling

salesman for him. Having accidentally taken a wrong turn near Chula Vista and winding up in Mexico,

he asks his son to have his class create a computer program that will provide an optimal route to all the

cities along his route and then return him to his home in scenic Clearlake.

2 Directed Graphs

A graph is a data structure G = 〈V,E〉 where V = {v0,…, vn} is the set of vertices (or nodes) and E = {

〈vi

, v j〉,…}

is the set of edges that connect the vertices. For example, you might have a set of cities V =

{El Cajon,La Mesa,San Diego,…,La Jolla} as the vertices and write “El Cajon” → “Lakeside” to indicate

that there is a path (Los Coches Road) from El Cajon to Lakeside. If there is a path from El Cajon to

Lakeside, as well as a path from Lakeside to El Cajon, then the edge connecting El Cajon and Lakeside is

undirected.

© 2021 Darrell Long 1

Such a simple graph representation simply tells you how vertices are connected and provides the idea

of one-way roads. But it really does not help Denver, since it does not provide any notion of distance.

We solve this problem by associating a weight with each edge and so we might write “Santee → El Cajon,

2” to indicate that there is a path of two miles long from Santee to El Cajon. Given a set of edges and

weights, then we can then find the shortest path from any vertex to any other vertex (the answer may be

that there is no such path). There are elegant (and quick) algorithms for computing the shortest path,

but that is not exactly what we want to do. We want to find a path through all of the vertices, visiting

each exactly once, such that there is a direct (single step) connection from the last vertex to the first. This

is called a Hamiltonian path. This will address Denver’s need to get home, but won’t necessarily be the

shortest such path. So, we need to go through every possible Hamiltonian path given the list of cities

Denver is traveling through and pick the shortest path. Note: if you find yourself on a path that is longer

than the current best found Hamiltonian path, then you can preemptively reject your current path.

3 Representing Graphs

Nothing can be more limiting to the imagination than only writing about

what you know.

—John W. Gardner

Perhaps the simplest way to represent a graph is with an adjacency matrix. Consider an n × n adjacency matrix M, where n is the number of vertices in the graph. If Mi,j = k, where 1 ≤ i ≤ j ≤ n, then we

say that there exists a directed edge from vertex i to vertex j with weight k. Traveling through wormholes

is considered hazardous, so any valid edge weight k must be non-zero and positive.

0 1 2 3 4 5 ··· 25

0 0 10 0 0 0 0 0 0

1 0 0 2 5 0 0 0 0

2 0 0 0 0 0 3 0 5

3 0 0 0 0 21 0 0 0

4 0 0 0 0 0 0 0 0

5 0 0 0 0 0 0 0 0

.

.

. 0 0 0 0 0 0 0 0

25 0 0 0 0 0 0 0 0

Each edge will be represented as a triplet 〈i, j,k〉. The set of edges in the adjacency matrix above is

E = {〈0, 1, 10〉,〈1, 2, 2〉,〈1, 3, 5〉,〈2, 5, 3〉,〈2, 25, 5〉,〈3, 4, 21〉}.

If the above adjacency matrix were made to be undirected, it would be reflected along the diagonal.

© 2021 Darrell Long 2

0 1 2 3 4 5 ··· 25

0 0 10 0 0 0 0 0 0

1 10 0 2 5 0 0 0 0

2 0 2 0 0 0 3 0 5

3 0 5 0 0 21 0 0 0

4 0 0 0 21 0 0 0 0

5 0 0 3 0 0 0 0 0

.

.

. 0 0 0 0 0 0 0 0

25 0 0 5 0 0 0 0 0

We will create a graph ADT based on this struct definition:

1 struct Graph {

2 uint32_t vertices ; // Number of vertices .

3 bool undirected ; // Undirected graph ?

4 bool visited [ VERTICES ]; // Where have we gone ?

5 uint32_t matrix [ VERTICES ][ VERTICES ]; // Adjacency matrix .

6 };

We elect to use an adjacency matrix with set maximum dimensions. This is both to simplify the

abstraction and also due to the computational complexity of solving the Traveling Salesman Problem

(TSP) with depth-first search (DFS), which is discussed in §5. The VERTICES macro will be defined and

supplied to you in vertices.h. In this header file, there is another macro START_VERTEX which defines

the origin vertex of the shortest Hamiltonian path we will be searching for. You may not modify this file.

The struct definition of a graph must go in graph.c. The following subsections define the interface for

the graph ADT.

vertices.h

1 # ifndef __VERTICES_H__

2 # define __VERTICES_H__

3

4 # define START_VERTEX 0 // Starting ( origin ) vertex .

5 # define VERTICES 26 // Maximum vertices in graph .

6

7 # endif

3.1 Graph *graph_create(uint32_t vertices, bool undirected)

The constructor for a graph. It is through this constructor in which a graph can be specified to be undirected. Make sure each cell of the adjacency matrix, matrix, is set to zero. Also make sure that each index

of the visited array is initialized as false to reflect that no vertex has been visited yet. The vertices

field reflects the number of vertices in the graph.

© 2021 Darrell Long 3

3.2 void graph_delete(Graph **G)

The destructor for a graph. Remember to set the pointer G to NULL.

3.3 uint32_t graph_vertices(Graph *G)

Return the number of vertices in the graph.

3.4 bool graph_add_edge(Graph *G, uint32_t i, uint32_t j, uint32_t k)

Adds an edge of weight k from vertex i to vertex j. If the graph is undirected, add an edge, also with

weight k from j to i. Return true if both vertices are within bounds and the edge(s) are successfully

added and false otherwise.

3.5 bool graph_has_edge(Graph *G, uint32_t i, uint32_t j)

Return true if vertices i and j are within bounds and there exists an edge from i to j. Remember: an

edge exists if it has a non-zero, positive weight. Return false otherwise.

3.6 uint32_t graph_edge_weight(Graph *G, uint32_t i, uint32_t j)

Return the weight of the edge from vertex i to vertex j. If either i or j aren’t within bounds, or if an edge

doesn’t exist, return 0.

3.7 bool graph_visited(Graph *G, uint32_t v)

Return true if vertex v has been visited and false otherwise.

3.8 void graph_mark_visited(Graph *G, uint32_t v)

If vertex v is within bounds, mark v as visited.

3.9 void graph_mark_unvisited(Graph *G, uint32_t v)

If vertex v is within bounds, mark v as unvisited.

3.10 void graph_print(Graph *G)

A debug function you will want to write to make sure your graph ADT works as expected.

4 Depth-first Search

Again it might have been the American tendency in travel. One goes, not so

much to see but to tell afterward.

—John Steinbeck, Travels with Charley: In Search of Amerca

We need a methodical procedure for searching through the graph. Once we have examined a vertex,

© 2021 Darrell Long 4

we do not want to do so again—we don’t want Denver going through cities where he has already been

(he has been known to wear out his welcome: charming women and fighting men).

Depth-first search (DFS) first marks the vertex v as having been visited, then it iterates through all of

the edges 〈v,w〉, recursively calling itself starting at w if w has not already been visited.

1 procedure DFS (G,v) :

2 label v as visited

3 for all edges from v to w in G. adjacentEdges (v) do

4 if vertex w is not labeled as visited then

5 recursively call DFS (G,w)

6 label v as unvisited

Finding a Hamiltonian path then reduces to:

1. Using DFS to find paths that pass through all vertices, and

2. There is an edge from the last vertex to the first. The solutions to the Traveling Salesman Problem

are then the shortest found Hamiltonian paths.

5 Computational Complexity

Many a trip continues long after movement in time and space have ceased.

I remember a man in Salinas who in his middle years traveled to Honolulu

and back, and that journey continued for the rest of his life. We could

watch him in his rocking chair on his front porch, his eyes squinted,

half-closed, endlessly traveling to Honolulu.

—John Steinbeck, Travels with Charley: In Search of Amerca

How long will this take? The answer is, it will take a very long time if there are a large number of

vertices. The running time of the simplest algorithm is O(n!) and there is no known algorithm that runs

in less than O(2n

) time. In fact, the TSP has been shown to be NP-hard, which means that it is as difficult

as any problem in the class NP (you will learn more about this in CSE 104: Computability and Computational Complexity). Basically, it means that it can be solved in polynomial time if you have a magical

computer that at each if-statement is takes both branches every time (creating a copy of the computer

for each such branch).

6 Representing Paths

We find after years of struggle that we do not take a trip; a trip takes us.

—John Steinbeck, Travels with Charley: In Search of Amerca

Given that vertices are added to and removed from the traveled path in a stack-like manner, we decide to abstract a path as follows:

© 2021 Darrell Long 5

1 struct Path {

2 Stack * vertices ; // The vertices comprising the path .

3 uint32_t length ; // The total length of the path .

4 };

The following subsections define for the interface for the path ADT.

6.1 Path *path_create(void)

The constructor for a path. Set vertices as a freshly created stack that can hold up to VERTICES number

of vertices. Initialize length to be 0. The length field will track the length of the path. In other words, it

holds the sum of the edge weights between consecutive vertices in the vertices stack.

6.2 void path_delete(Path **p)

The destructor for a path. Remember to set the pointer p to NULL.

6.3 bool path_push_vertex(Path *p, uint32_t v, Graph *G)

Pushes vertex v onto path p. The length of the path is increased by the edge weight connecting the vertex

at the top of the stack and v. Return true if the vertex was successfully pushed and false otherwise.

6.4 bool path_pop_vertex(Path *p, uint32_t *v, Graph *G)

Pops the vertices stack, passing the popped vertex back through the pointer v. The length of the

path is decreased by the edge weight connecting the vertex at the top of the stack and the popped vertex.

Return true if the vertex was successfully popped and false otherwise.

6.5 uint32_t path_vertices(Path *p)

Returns the number of vertices in the path.

6.6 uint32_t path_length(Path *p)

Returns the length of the path.

6.7 void path_copy(Path *dst, Path *src)

Assuming that the destination path dst is properly initialized, makes dst a copy of the source path src.

This will require making a copy of the vertices stack as well as the length of the source path.

6.8 void path_print(Path *p, FILE *outfile, char *cities[])

Prints out a path to outfile using fprintf(). Requires a call to stack_print(), as defined in §7.10,

in order to print out the contents of the vertices stack.

© 2021 Darrell Long 6

7 Stacks, Revisited

If you have some respect for people as they are, you can be more

effective in helping them to become better than they are.

—John W. Gardner

You will use the stack that you implemented for assignment 3 with slight modifications. If there were

any problems with your stack for that assignment, make sure to fix them for this assignment. Here is the

modified stack interface for this assignment.

1 struct Stack {

2 uint32_t top ;

3 uint32_t capacity ;

4 uint32_t * items ;

5 };

7.1 Stack *stack_create(uint32_t capacity)

The constructor function for a Stack. The top of a stack should be initialized to 0. The capacity of a

stack is set to the specified capacity. The specified capacity also indicates the number of items to allocate

memory for, the items in which are held in the dynamically allocated array items.

7.2 void stack_delete(Stack **s)

The destructor function for a stack. Remember to set the pointer s to NULL.

7.3 bool stack_empty(Stack *s)

Return true if the stack is empty and false otherwise.

7.4 bool stack_full(Stack *s)

Return true if the stack is full and false otherwise.

7.5 uint32_t stack_size(Stack *s)

Return the number of items in the stack.

7.6 bool stack_push(Stack *s, uint32_t x)

If the stack is full prior to pushing the item x, return false to indicate failure. Otherwise, push the item

and return true to indicate success.

© 2021 Darrell Long 7

7.7 bool stack_peek(Stack *s, uint32_t *x)

Peeking into a stack is synonymous with querying a stack about the element at the top of the stack. If the

stack is empty prior to peeking into it, return false to indicate failure.

7.8 bool stack_pop(Stack *s, uint32_t *x)

If the stack is empty prior to popping it, return false to indicate failure. Otherwise, pop the item, set the

value in the memory x is pointing to as the popped item, and return true to indicate success.

7.9 void stack_copy(Stack *dst, Stack *src)

Assuming that the destination stack dst is properly initialized, make dst a copy of the source stack src.

This means making the contents of dst->items the same as src->items. The top of dst should also

match the top of src.

7.10 void stack_print(Stack *s, FILE *outfile, char *cities[])

Prints out the contents of the stack to outfile using fprintf(). Working through each vertex in the

stack starting from the bottom, print out the name of the city each vertex corresponds to. This function

will be given to aid you.

1 void stack_print ( Stack *s, FILE * outfile , char * cities []) {

2 for ( uint32_t i = 0; i < s-> top ; i += 1) {

3 fprintf ( outfile , “%s”, cities [s-> items [i]]) ;

4 if (i + 1 != s- > top ) {

5 fprintf ( outfile , ” -> “) ;

6 }

7 }

8 fprintf ( outfile , “\n”);

9 }

8 Command-line Options

Attitude is a choice. Happiness is a choice. Optimism is a choice. Kindness

is a choice. Giving is a choice. Respect is a choice. Whatever choice you

make makes you. Choose wisely.

—Roy T. Bennett, The Light in the Heart

Your program must support any combination of the following command-line options.

• -h : Prints out a help message describing the purpose of the graph and the command-line options

it accepts, exiting the program afterwards. Refer to the reference program in the resources repo for

an idea of what to print.

© 2021 Darrell Long 8

• -v : Enables verbose printing. If enabled, the program prints out all Hamiltonian paths found as

well as the total number of recursive calls to dfs().

• -u : Specifies the graph to be undirected.

• -i infile : Specify the input file path containing the cities and edges of a graph. If not specified,

the default input should be set as stdin.

• -o outfile : Specify the output file path to print to. If not specified, the default output should be

set as stdout.

9 Reading An Input Graph

It behooves a man who wants to see wonders sometimes

to go out of his way.

—John Mandeville, The Travels of Sir John Mandeville

We will be storing graphs in specially formatted files. Here is an example:

$ cat mythical.graph

4

Asgard

Elysium

Olympus

Shangri-La

0 3 5

3 2 4

2 1 10

1 0 2

The first line of a graph file is the number of vertices, or cities, in the graph. Assuming n is the number

of vertices, the next n lines of the file are the names of the cities. Each line after that is an edge. It is to be

scanned in as a triplet 〈i, j,k〉 and interpreted as an edge from vertex i to vertex j with weight k.

10 Specifics

The gladdest moment in human life, methinks, is a

departure into unknown lands.

—Sir Richard Burton

Here are the specifics for your program implementation.

1. Parse command-line options with looped calls to getopt(). This should be familiar from assignments 2 and 3.

© 2021 Darrell Long 9

2. Scan in the first line from the input. This will be the number of vertices, or cities, that will be in

the graph. Print an error if the number specified is greater than VERTICES, the macro defined in

vertices.h.

3. Assuming the number of specified vertices is n, read the next n lines from the input using fgets().

Each line is the name of a city. Save the name of each city to an array. You will want to either

make use of strdup() from <string.h> or implement your own strdup() function. If the line

is malformed, print an error and exit the program. Note: using fgets() will leave in the newline

character at the end, so you will manually have to change it to the null character to remove it.

4. Create a new graph G, making it undirected if specified.

5. Scan the input line by line using fscanf() until the end-of-file is reached. Add each edge to G. If

the line is malformed, print an error and exit the program.

6. Create two paths. One will be for tracking the current traveled path and the other for tracking the

shortest found path.

7. Starting from the origin vertex, defined by the macro START_VERTEX in vertices.h, perform a

depth-first search on G to find the shortest Hamiltonian path. Here is an example function prototype that you may use as the recursive depth-first function:

1 void dfs ( Graph *G, uint32_t v, Path *curr , Path * shortest

, char * cities [] , FILE * outfile ) ;

The parameter v is the vertex that you are currently on. The currently traversed path is maintained

with curr. The shortest found path is tracked with shortest. The array of city names is cities.

Finally, outfile is the output to print to.

8. After the search, print out the length of the shortest path found, the path itself (remember to return

back to the origin), and the number of calls to dfs().

$ ./tsp < mythical.graph

Path length: 21

Path: Asgard -> Shangri-La -> Olympus -> Elysium -> Asgard

Total recursive calls: 4

If the verbose command-line option was enabled, print out all the Hamiltonian paths that were

found as well. It is recommended that you print out the paths as you find them.

$ ./tsp -v < ucsc.graph

Path length: 7

Path: Cowell -> Stevenson -> Merrill -> Cowell

Path length: 6

Path: Cowell -> Merrill -> Stevenson -> Cowell

Path length: 6

Path: Cowell -> Merrill -> Stevenson -> Cowell

Total recursive calls: 5

© 2021 Darrell Long 10

11 Deliverables

Travel isn’t always pretty. It isn’t always comfortable. Sometimes it hurts, it

even breaks your heart. But that’s okay. The journey changes you; it should

change you. It leaves marks on your memory, on your consciousness, on

your heart, and on your body. You take something with you. Hopefully, you

leave something good behind.

—Anthony Bourdain

1. Your program, called tsp, must have the following source and header files:

• vertices.h defines macros regarding vertices.

• graph.h specifies the interface to the graph ADT.

• graph.c implements the graph ADT.

• stack.h specifies the interface to the stack ADT.

• stack.c implements the stack ADT.

• path.h specifies the interface to the path ADT.

• path.c implements the path ADT.

• tsp.c contains main() and may contain any other functions necessary to complete the assignment.

You can have other source and header files, but do not try to be overly clever. You may not modify

any of the supplied header files.

2. Makefile: This is a file that will allow the grader to type make or make all to compile your program.

• CC=clang must be specified.

• CFLAGS=-Wall -Wextra -Werror -Wpedantic must be included.

• make should build your program, as should make all.

• make clean must remove all files that are compiler generated.

• make format should format all your source code, including the header files.

3. Your code must pass scan-build cleanly.

4. README.md: This must be in Markdown. This must describe your program briefly, its usage, and

how to build it using your Makefile.

5. DESIGN.pdf: This must be a PDF. The design document should contain answers to the pre-lab

questions at the beginning and describe your design for your program with enough detail that

a sufficiently knowledgeable programmer would be able to replicate your implementation. This

does not mean copying your entire program in verbatim. You should instead describe how your

program works with supporting pseudo-code.

© 2021 Darrell Long 11

12 Supplemental Readings

One of the reasons people stop learning is that they become less and less

willing to risk failure. you learn, the more places you’ll go.

—John W. Gardner

• The C Programming Language by Kernighan & Ritchie

– Chapter 4 §4.10

– Chapter 7 §7.4–7.8

• Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest, & C. Stein

– Chapter 10 §10.1

– Chapter 35 §35.2

13 Submission

A man who procrastinates in his choosing will inevitably have his choice

made for him by circumstance.

—Hunter S. Thompson, The Proud Highway

Refer back to asgn0 for the steps on how to submit your assignment through git. Remember: add,

commit, and push! Your assignment is turned in only after you have pushed and submitted the commit

ID on Canvas. If you forget to push, you have not turned in your assignment and you will get a zero. “I

forgot to push” is not a valid excuse. It is highly recommended to commit and push your changes often.

Fhewhqccydw yd S yi byau wylydw q cedauo q sxqydiqm.

© 2021 Darrell Long 12