Assignment 6

Surfin’ U.S.A.

CSE 13S, Winter 2024

1    Introduction

As students of the best coastal university in the United States, if not the world, you have probably seen Santa Cruz’s surfing culture.  Santa Cruz is so well known for its surf culture that the city of Santa Cruz and surfing are almost synonymous. Santa Cruz is also one of the cities mentioned in the Beach Boys’ 1963 song, Surfin’ U.S.A.

Jess’s friend, Alissa, wants to jump into the ocean at every city mentioned in the song to prove that Santa Cruz has the best oceans and beaches. Because Alissa is a broke college student, she can’t afford gas, and therefore must get between the cities on a budget (Figure 1).  Alissa will be starting her trip in Santa Cruz on Friday morning (March 1st), and will spend some time in each beach. She does not want to repeat any beaches during her trip as she must return back to Santa Cruz so she can feed her roommate’s cat, Tank at the end of the day.

Figure 1: Every place mentioned in the Beach Boy’s 1963 song “Surfin’ U.S.A.”[1]

In this assignment, your task will be to use graph theory to help herget to each city using the smallest amount of gas. You must make sure that her route starts and ends in Santa Cruz, and she visits every other city exactly once.  While you could in theory make a list of every possible route between every city, this is inefficient, and will very quickly create a lot of work for you. Instead, you will use graph theory, depth first search, and a stack to implement a solution to the classic Travelling Salesman Problem.

2    Graphs

2.1    General Info

A graph is a structure used frequently in discrete mathematics.  There are two  (main) types of graphs:  a directed graph,and anundirected graph. A graph consists of two basic parts: vertices and edges. A vertex is a point in space: in this example, a city. An edge is a line connecting two vertices. This has a "weight". This can be thought of like the amount of time it takes to travel between two cities. In a undirected graph, the weight of the edge between two cities is the same, regardless of the direction.  In a directed graph, the weight can be different based on direction, or the edge could only connect the vertices in one direction.  This means that you can travel directly from point A to point B, but not from point B to point A.

Some other important features to note in a graph are cycles and loops. A loop is an edge from a vertex to itself.  This can have any weight, not necessarily zero, but also does not need to exist.  Also note the existence of a cycle.  A cycle is a path that takes you back to where you started. You will read more about cycles when you read about the Travelling Salesman Problem (TSP, in Section 5).  Finally, while negative edges are possible in a graph, you will not find them in this assignment.

Figure 2: A graph of the difficulty to get food on campus[2].

This graph of the locations to get food on campus shows a lot of the features of graphs.  On the other hand, if you are at Crown/Merrill, you can get food without going anywhere, and therefore taking zero effort (a loop).  This is also clearly a directed graph, as it is harder to get from Porter/Kresge Dining Hall to College 9/Lewis as you are going uphill.  Also notice that if you are travelling from Crown/Merrill, and your only goal is to get food, you might as well stop at 9/Lewis, as it’s on the way.  There is no path from Crown/Merrill to Porter/Kresge that doesn’t pass by 9/Lewis.

This leads us to the question of:  how do we store the graph?  There are two ways that are usually used to store a graph. Both of these ways work to store a directed graph, but they also both have trade-offs.

Table 1: An (incomplete) adjacency list.

The first is called an adjacency list.  (See Table 1.)  An adjacency list stores a graph as a list of pairs of edges, and a weight between them.  This works fine for a graph with few edges, but is a lot harder with a graph that has many edges.  The reason for this is that if we have to find an edge, we must search the whole list before we know if it exists.  Take a note of how hard it would be to find an edge weight if you were given a complete adjacency list for this graph! An adjacently list is still useful to us if we need to store the list in a minimal amount of space, as it only stores edges that exist, and therefore no space is wasted.

C/S    C/M    P/K    RCC    9/L

C/S        0        5       X        5       5

C/M        3        0       X        X       4

P/K         X        X       0        2       10

RCC       10        X       4        0       12

9/L         3        4        6        6       0

Figure 3: The adjacency matrix for the dining hall graph[2].

The other way to store a graph is using an adjacency matrix.  (See Figure 3.)  If we have a graph with E edges, our adjacency matrix is an E × E matrix, where for every a in (0, 1, 2,..., E − 1) and for every b in (0, 1, 2,..., E − 1), Mab  is the weight of the edge between Vertex A and Vertex B

2.2    Assignment Specifics

In the case of Alissa’s tour of California, you should treat all edges as undirected unless told otherwise (you handle undirected graphs by adding a second edge in the opposite direction). Obviously, the edges will also have weights. You will be storing your weights in an adjacency matrix. You will also store an extra array of strings holding the names of the vertices on the graph.

Here is the completed struct, as defined in graph .c

typedef struct graph { uint32_t vertices; bool directed; bool *visited; char **names; uint32_t **weights; } Graph;

Since this struct is only defined in graph .c, files that use the graph (which need to include graph.h) only know that some struct called Graph exists; they do not know what its members are.  This means the only way they can manipulate a Graph is by storing a pointer to it and calling the functions declared in graph .h.

2.3    Functions

Your graph will have the following functions:

Graph  *graph_create(uint32_t  vertices,  bool  directed)

Creates a new graph struct, and returns a pointer to it. Initializes all items in the visited array to false.

Graph *graph_create (uint32_t vertices, bool directed) { Graph *g = calloc(1, sizeof(Graph)); g->vertices = vertices; g->directed = directed; // use calloc to initialize everything with zeroes g->visited = calloc(vertices, sizeof(bool)); g->names = calloc(vertices, sizeof(char *)); // allocate g->weights with a pointer for each row g->weights = calloc(vertices, sizeof(g->weights[0])); // allocate each row in the adjacency matrix for (uint32_t i = 0; i < vertices; ++i) { g->weights[i] = calloc(vertices, sizeof(g->weights[0][0])); } return g; }

void  graph_free(Graph  **gp)

Frees all memory used by the graph.  Take a close look at when memory is allocated in this function to be sure you free everything! Double check with valgrind.

This function takes in a double pointer (Graph  **; a pointer to a pointer) so that it can set the Graph pointer (that gp points to) to NULL. If it didn’t do this, it would be possible to try to access the Graph using a pointer that had already been freed. Using a value after freeing it has the potential to create serious vulnerabilities. To avoid this, we set *gp to NULL to ensure that any attempt to use the Graph after freeing it will immediately crash your program.

uint32_t  graph_vertices(const  Graph  *g)

Finds the number of vertices in a graph.

void  graph_add_vertex(Graph  *g,  const  char  *name,  uint32_t  v)

Gives the city at vertex v the name passed in.  This function makes a copy of the name and stores it in the graph object.  The parameter is const to indicate that graph_add_vertex() cannot modify the string passed into it.

if (g->names[v]) free(g->names[v]); g->names[v] = strdup(name);

The strdup() function makes a copy of the string, which is necessary (and means it must be freed later). Otherwise, you wouldn’t be sure that the pointer passed into  graph_add_vertex()  would still be valid as long as the Graph existed (for instance, the caller might pass in a buffer which they will later use for something else). We also make sure that if we overwrite an existing name, the old one is freed.

const  char*  graph_get_vertex_name(const  Graph  *g,  uint32_t  v)

Gets the name of the city with vertex v from the array of city names.  This does not allocate a new string, it simply returns the one stored in the Graph.  g is const since this function doesn’t need to modify the Graph, and its return type is const to prevent the caller from manipulating the string that it returns.

char  **graph_get_names(const  Graph  *g)

Gets the names of the every city in an array.  Returns a double pointer – an array of strings – but  not  a copy.

void  graph_add_edge(Graph  *g,  uint32_t  start,  uint32_t  end,  uint32_t  weight)

Adds an edge between start and end with weight weight to the adjacency matrix of the graph.

uint32_t  graph_get_weight(const  Graph  *g,  uint32_t  start,  uint32_t  end)

Looks up the weight of the edge between start and end and returns it.

void  graph_visit_vertex(Graph  *g,  uint32_t  v)

Adds the vertex v to the list of visited vertices.

void  graph_unvisit_vertex(Graph  *g,  uint32_t  v)

Removes the vertex v from the list of visited vertices.

bool  graph_visited(const  Graph  *g,  uint32_t  v)

Returns true if vertex v is visited in graph g, false otherwise.

void  graph_print(const  Graph  *g)

Optionally, prints a human-readable representation of a graph.  Even though this function is not required, we strongly recommend that you implement it as it will aid in making sure that you are reading in the graph correctly.

2.4    The  .graph format

You will write a function that reads a text-file representation of a graph, creates a new Graph, and returns a pointer to it. The text file has a name that ends in  .graph. The .graph file contains several lines, grouped into four sections, which are defined in Table 2 below.  Each line has a maximum length of PATH_MAX as defined in <limits .h>

Another example graph, basic.graph is as follows (notated with C style comments)

2                        //  There  are  2  vertices  in  the  graph

Home                  //  The  first  vertex  is  called  "home"

The  Beach       //  The  2nd  vertex  is  called  "The  Beach"

2                        //  There  are  two  edges  in  this  Graph

0 1 1                 // The first edge is from 0 (home) to 1 (the beach) with a weight of 1

1  0  2             //  The  other  edge  is  from  1  back  to  0  with  a  weight  of  2

For a more detailed example, you can look at any other  .graph file provided in the resources repository. 

Section	Purpose	Example
1	One line: Number of Vertices	3
2	Several lines:  Names of Vertices.  If the number of vertices is  n, there are n names, one name per line.	Home   Beach Bookstore
3	One line: Number of Edges	2
4	Several lines:  All edges and weights as a adjacency list, in the format  Start  End  Weight, ex:  0  1  5  would represent the edge from Home to Beach (with a weight of 5).  The numbers correspond to the vertices listed in Section 2, with the first vertex being num- ber 0. There are exactly as many edges in this list as specified in the line above.	0  1  5 1  2  7

Table 2: Format of a  .graph file.

3    Stacks

3.1    General Information

A stack is an abstract data type used to store a list of elements.   Unlike  arrays,  a  stack  only  has  two essential operations:  Push, and Pop.   This means that it does not have random access; that is to say that you cannot access an element in the middle of the stack in any way. It is a good idea to think of a stack like you would think about a stack of pancakes. When you create a new pancake, you must add it to the top of the stack.  When somebody grabs a pancake to eat, they must remove it from the top of the stack.  This means that a stack follows a last in - first out (LIFO) ordering.  You can’t remove a pancake from the middle of the stack.

 3.2    Assignment Specifics

Our implementation of a stack will be used to track the path that Alissa takes on her trip. We will use an array (items)to represent the list of elements.  Because we modify the last element of the array, we need a variable to track where the end of the stack resides in your computer’s memory. This will be stack->top. In order to not wastefully allocate memory, your path ADT will dynamically allocate the array inside.  It will only do this once, and it will store the maximum

capaity of the stack in the struct field struct->capcacity. Here is the complete struct, as defined in stack .c.

typedef struct stack { uint32_t capacity; uint32_t top; uint32_t *items; } Stack;

3.3    Functions

The stack that you implement will have push and pop, along with a few functions to make them easier for you to use:

Stack  *stack_create(uint32_t  capacity)

Creates a stack, dynamically allocates space for it, and returns a pointer to it.

// Attempt to allocate memory for a stack // Cast it to a stack pointer too! Stack *s = (Stack *) malloc(sizeof(Stack)); s->capacity = capacity; s->top = 0; // We need enough memory for <capacity> numbers s->items = calloc(s->capacity, sizeof(uint32_t)); // We created our stack, return it! return s;

While malloc and calloc can return a null pointer, we will assume that this will not happen during this assignment.  If you want, you should get in the habit of checking for that edge case when you allocate memory.

Also note that the value of stack->top is 0 on an empty list. This does not mean that there is an item at index 0. The stack->top field simply points to the next empty slot on the stack.

void  stack_free(Stack  **sp)

Frees all space used by a given stack, and sets the pointer to NULL.

// sp is a double pointer, so we have to check if it, // or the pointer it points to is null. if (sp != NULL && *sp != NULL) { // Of course, we have to remember to free the // memory for the array of items first, // as that was also dynamically allocated! // If we freed the Stack first then we would // not be able to access the array to free it. if ((*sp)->items) { free((*sp)->items); (*sp)->items = NULL; } // Free memory allocated for the stack free(*sp); } if (sp != NULL) { // Set the pointer to null! This ensures we dont ever do a double free! *sp = NULL; }

bool  stack_push(Stack  *s,  uint32_t  val)

Adds val to the top of the stack S, and increments the counter.  Returns true if successful, false otherwise (ex: the stack is full).

// If the stack is full, return false; if (stack_full(s)) { return false; } // Set val s->items[s->top] = val; // Move the top of the stack s->top++; return true;

bool  stack_pop(Stack  *s,  uint32_t  *val)

Sets the integer pointed to by val to the last item on the stack, and removes the last item on the stack. Returns true if successful, false otherwise. Remember that stack->top is not the indexof the top value of the stack.

bool  stack_peek(const  Stack  *s,  uint32_t  *val)

Sets the integer pointed to by val to the last item on the stack, but does not modify the stack.  Returns true if successful, false otherwise. Remember that stack->top is not the indexof the top value of the stack.

bool  stack_empty(const  Stack  *s)

Returns true if the stack is empty, false otherwise. A stack is empty when there are no elements in it.

bool  stack_full(const  Stack  *s)

Returns true if the stack is full, false otherwise.  A stack is full when the number of elements is equal to the capacity.

uint32_t  stack_size(const  Stack  *s)

Returns the number of elements in the stack. An empty stack contains zero elements.

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

Overwrites dst with all the items from s rc. You should also make sure to update dst->top so that your code knowshow many items are now in the stack.  Finally, although it’s unlikely to come up in this assignment as all your Stacks will be the same length, we should consider that dst may not have a capacity large enough to store every item from src. You can use the assert function to make sure that this is not the case (if it does happen, it is likely an error in your code).

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

This function will print out the stack as a list of elements, given a list of vertex names, starting with the bottom of the stack. Every item in the stack should be less than the number of vertices so you can index the array successfully.

for (uint32_t i = 0; i < s->top; i += 1) { fprintf(outfile, "%s\n", cities[s->items[i]]); }