15–122: Principles of Imperative Computation — Summer 2019
Final Exam
Friday 9th August, 2019
1 Graph Representation [C] (55 points)
The graph interface seen in class and reported on page 30 could return a collection of neigh– bors of a vertex as a NULL–terminated linked list of vertices. An adjacency matrix imple– mentation had to construct this list when graph_get_neighbors was called, and later free it when graph_free_neighbors was called. An adjacency list implementation could be more efficient: it simply returned the pointer to the adjacency list of the requested vertex and did nothing to dispose of it.
Task 1.1 The following client function uses the graph interface:
unsigned int count_neighbors_of_0(graph_t G) {
REQUIRES(G != NULL && graph_size(G) > 0);
vert_list *nbors = graph_get_neighbors(G, 0);
unsigned int c = 0;
while (nbors != NULL) {
c++;
nbors = nbors->next;
}
graph_free_neighbors(nbors);
return c;
}
This function, although it technically respects the graph interface seen in class, is prob– lematic. Assume we are using an adjacency matrix implementation of graphs. What is wrong with this function?
Task 1.2 Here is another snippet of code – imagine that, for an unknown reason, the client wants to ignore all neighbors that are multiples of 10, so they set them to a dummy value that their later code can ignore:
vert_list *nbors = graph_get_neighbors(G, 5);
for (vert_list *p = nbors; p != NULL; p = p->next) {
if (p->vert % 10 == 0)
p->vert = 99999999; // set vertex to dummy value }
unknown_function_that_hates_multiples_of_ 10(nbors);
graph_free_neighbors(nbors);
Again, this client code respects the graph interface but is still problematic. Now assuming we are using an adjacency list implementation, what is undesirable about this function?
An approach to avoid this problem altogether is to make the type of values returned by graph_get_neighbors abstract. Here are the relevant parts of a modified graph interface that does precisely that: it exports the type neighbors_t without revealing how it is defined. The new function neighbors_next returns the next vertex in a collection of neighbors, assuming that there are more neighbors. The function neighbors_empty checks this property.
Therefore, we can now get a collection of neighbors by calling graph_get_neighbors, and then repeatedly check whether it is empty and ask for the next neighbor if not.
C0–style contracts are included for readability.
//typedef ________ *neighbors_t ; // NEW
neighbors_t graph_get_neighbors(graph_t G, vertex v); // UPDATED
//@requires G != NULL;
//@requires v < graph_size(G);
//@ensures \result != NULL;
vertex neighbors_next(neighbors_t N); // NEW
//@requires N != NULL && ! neighbors_empty(N);
bool neighbors_empty(neighbors_t N); // NEW
//@requires N != NULL;
void neighbors_free( neighbors_t N); // UPDATED
//@requires N != NULL;
Task 1.3 Using this new graph interface, modify the code given on page 1 for the client function
count_neighbors_of_0 to prevent the problem you unveiled in task 1.
|
int count_neighbors_of_0(graph_t G) {
REQUIRES(G != NULL && graph_size(G) > 0);
int c = 0;
neighbors_t nbo rs = ;
while ( ) { c++;
; }
; return c;
}
|
We will now update the adjacency list implementation of the graph interface to match the new interface. Recall the definition of the internal type graph:
typedef struct adjlist_node adjlist;
struct adjlist_node { vertex vert;
adjlist *next; };
typedef struct graph_header graph;
struct graph_header { unsigned int size;
adjlist **adj; };
You may assume that the specification functions is_graph and is_vertex have been defined for you.
We concretely define the type neighbors_t as follows:
struct neighbor_header_adjlist {
adjlist* next_nbor; };
typedef struct neighbor_header_adjlist nbors_AL;
typedef nbors_AL *neighbors_t; // for the client
The type nbors_AL contains one field, which is a pointer to the node which contains the next vertex that should be returned (or NULL if there are no more neighbors).
Task 1.4 Implement the function graph_get_neighbors so that it has constant cost. Include ap– propriate contracts.
|
nbors_AL *graph_get_neighbors(graph_t G, vertex v) {
}
|
Task 1.5 Implement the function neighbors_empty which checks whether there are any more neighbors in a collection. Include appropriate contracts.
|
bool neighbors_empty(nbors_AL *N) {
|
Task 1.6 Implement the function neighbors_next, which also should have constant cost. It should not allocate any additional memory. Include appropriate contracts.
|
vertex neighbors_next(nbors_AL *N) {
}
|
Task 1.7 Complete the body of neighbors_free so that, by the time we are done using a graph, all allocated memory has been freed and none has been freed twice.
|
void neighbors_free(nbors_AL *N) {
}
|
Next, we will do the same with the adjacency matrix implementation of the graph interface. The internal types graph and nbors_AM are now defined as follows:
typedef struct graph_header graph;
struct graph_header { unsigned int size;
bool **adj; // 2-D array };
struct neighbor_header_adjmatrix { bool * row;
unsigned int length;
unsigned int next; };
typedef struct neighbor_header_adjmatrix nbors_AM;
typedef nbors_AM *neighbors_t; // for the client
Neighbor collections (right) are defined as a struct containing a pointer to the row of the matrix for the vertex whose neighbors we are considering, the length of this array, and the index of the next cell of this array that contains a neighbor of the vertex. This means you’ll need to very carefully consider how to set the next field in both graph_get_neighbors and neighbors_next.
7pts Task 1.8 Implement the function graph_get_neighbors. Include appropriate contracts.
|
nbors_AM *graph_get_neighbors(graph *G, vertex v) {
}
|
What is the worst–case complexity of graph_get_neighbors as a function of the number v of vertices and the number e of edges in the input graph?