Description
1 Introduction and purpose
In this project you will extend upon your graph implementation from Project #7 in two ways: new functions will be
added that allow removing components of graphs as well as an entire graph; and the graph functions will have to free
any allocated memory when it is no longer needed. Some tests in this project will check for memory leaks and memory
errors resulting in heap corruption (making parts of the heap invalid); Section 4 explains how these tests do this. Your
functions in Project #7 could have passed some (or even all) of their tests despite having errors of these types, but in
this project you will have to fix this. The purpose of the project is to ensure that you are not only able to create a more
complex dynamically allocated data structure, but also able to correctly free memory for such a data structure.
You must again have a makefile (still named Makefile) in your submission that will compile your code for all of the
public tests. Other than two points mentioned in Appendix B below, the requirements for your makefile are the same
as in the previous project, so they are not repeated here. See Project #7 and the notes in Appendix B about makefile
dependencies. Note that Project #7 explained in detail how to test your makefile before submitting.
Due to the size of the course it is not possible for us to provide project information or help via email/ELMS
messages, so we will be unable to answer such questions. But you are welcome to ask them verbally during the TAs’
office hours.
1.1 Fixing problems in your Project #7 code
Even if you had trouble with Project #7 and may not get a high score on it, you can still do fine in the course (one
project just isn’t worth much toward your grade). But you do have to get Project #7 to work though, so you can reuse
it and expand upon it in this project. So if you know that you have bugs in your Project #7 code, fix them right away.
(Hint– valgrind is your friend; see the rest of this section.)
A few days after this project is assigned we will provide the Project #7 secret tests in ~/216public/project07.
You can use them to figure out changes needed in your Project#7 code when reusing it in this project.
But even if you aren’t aware of any bugs in your Project #7 code your functions might still, as mentioned above,
have some errors in the heap, despite being able to pass the Project #7 tests. But in this case your code will fail many
of the tests in this project (the ones that are checking for consistency and correctness of the heap). So it is strongly
recommended, before even trying to write the new functions in this project, that you first use valgrind to test for– and
fix– any heap problems in your Project #7 code as follows:
• Before even extracting the files from the project08.tgz tarfile, make a complete second copy of your entire
project07 directory, with a different name. (This is just so you can make changes to your previous code while
still keeping a backup of your Project #7 code as it was submitted.)
• In the new copy of your project07 directory, add the -g compilation option to your makefile (if it’s not already
in your compilation options), run make clean, then rebuild all of the public tests.
• Now run valgrind –leak-check=no public01.x and look for any errors reported by valgrind.
As the Project #7 assignment mentioned, the Project #7 tests will unavoidably have memory leaks, because there
are no Project #7 functions that remove any components of a graph, so the tests have no way to free the memory
used by String_graph variables when they finish. But the –leak-check=no option to valgrind prevents it
from checking for memory leaks, so it will only check for other types of problems in the heap.
valgrind was explained in discussion section and a number of small examples were shown (the tarfile with the
examples is in ~/216public on Grace). The examples had different kinds of memory problems that could occur,
and allowed you to see how valgrind identified the different kinds of problems.
• Fix any memory problems in your string-graph.c that valgrind identified. If you need help understanding
what valgrind is saying, after carefully reviewing and rerunning the valgrind examples in ~/216public, you
can ask the TAs in office hours to help you understand what valgrind is telling you.
• Repeat the same command for the rest of the public tests, fixing any problems reported for any of the later tests
as well.
© 2023 L. Herman; all rights reserved 1
• Then you can use your fixed string-graph.c in writing this project.
Of course this procedure assumes that you were in discussion section when valgrind was demonstrated and explained by the TAs (on Monday, March 27), so you understand it. If you weren’t in discussion then, you’re on your own
for figuring valgrind out. Try to ask a friend who was in discussion that day to explain it to you and show you the
examples.
1.2 Extra credit and number of submissions
You can again get extra credit for this project. If you make only one submission that passes all the public tests you
will get 3 extra–credit bonus points. And if your single submission is made at least 48 hours before the on–time
deadline you will get 3 additional extra credit bonus points, for 6 extra credit points total. (Obviously you can’t get
the second 3 extra credit points if you don’t get the first 3, but you can get the first 3 without getting these second 3.)
But as before, if you make too many submissions you may again lose credit. To avoid making submissions that
don’t compile or don’t pass all the public tests you should compile the tests, run them, check your output, and fix any
problems, all before submitting. And you should write your makefile first, and test it before submitting, as discussed
below.
(If for some reason your code passes all the public tests on Grace but doesn’t work when you submit it, so you
have to submit more than once– and this is not due to an error on your part, a bug in your code, or a problem
with your makefile– you can talk with me in my office hours about receiving extra credit despite having more than one
submission.)
2 New functions to be written
Just copy your string-graph.c and string-graph-datastructure.h files from your project07 directory (or copy
the corrected versions from the new copy of your project07 directory if you followed the procedure in Section 1.1
above) to the new project08 directory that will be created by extracting the files from this project’s tarfile. As
mentioned above, make whatever changes are needed to fix any bugs in your Project #7 code that was copied to the
project08 directory, and add the new functions described below to it. But before starting to code, look at the public
tests so you see how the functions are called.
Write one function at a time (entirely or even partially), then test it (as soon as that is possible) thoroughly before
going on! Write and test helper functions before writing code that uses them, and test them separately first as well.
Project #7 said that if a pointer passed into a parameter of any function is NULL the function should have no effect,
and (with two exceptions) if it returns an integer value it should return 0. This also applies (with one exception to the
return value) to the new functions being added in this project
2.1 void free_vertex_name_list(char **const names)
This is a helper or utility function that is not actually part of a graph. It should free all the dynamically–allocated
memory of the strings in the array names, then free the array names itself. It should have no effect if the pointer names
itself is NULL. If names is non–NULL the function may assume that its last element will always be NULL (i.e., the array
will be like those returned by the function get_vertex_list(), and by the new function get_neighbor_names()
explained below). So the user of your code can use this function to free the memory returned by get_vertex_list()
and get_neighbor_names() when they are no longer needed, to avoid memory leaks.
2.2 char **get_neighbor_names(String_graph *const graph, const char vertex[])
If its parameter graph itself is NULL, or if the graph does not have a vertex with the name vertex, this function should
just return NULL. Otherwise it should return a newly–created dynamically–allocated array, say new_arr, of pointers
to characters, where the pointers point to copies of the names of the neighbors of the vertex vertex in the parameter
graph. (Recall that a neighbor of the parameter vertex is a vertex, say other, such that there is an edge from the parameter
vertex to other.) The names pointed to by the pointers in new_arr must be in increasing lexicographic (dictionary)
order. Each name must be stored in a newly–created dynamically–allocated character array; that is, the pointers in
new_arr should not just be aliases of the names stored somewhere in your graph data structure.
© 2023 L. Herman; all rights reserved 2
If vertex has n neighbors, the array returned by the function must be an array with n+1 elements, where the
last element must be NULL. (So if the vertex vertex has no neighbors the function must return a dynamically allocated
array of one element, which will be NULL.)
(The return value of this function for NULL parameters is the exception referred to in the third paragraph in Section 2.)
2.3 int remove_graph_edge(String_graph *const graph, const char source[],
const char dest[])
This function should remove the edge going from source to dest in its parameter graph. If either source or dest are
not vertices in the graph, or if they are vertices but there is no edge from source to dest, the function should just return
0 without changing anything, otherwise it should remove the edge and return 1. Any dynamically–allocated memory
used by the edge must be freed.
Recall that your data structure must contain at least one linked list or binary search tree somewhere. If, given
your data structure, it’s necessary to remove elements from linked lists or binary search trees in order to remove graph
edges, how to do these things was covered in CMSC 132.
2.4 int remove_vertex_from_graph(String_graph *const graph, const char vertex[])
If vertex is not a vertex in its parameter graph this function should just return 0 without changing anything, otherwise
it should remove vertex from the graph and return 1. If a vertex is removed then all its outgoing as well as incoming
edges must also be removed, because an edge needs both its source and destination vertices to exist. Any dynamically–
allocated memory used by the vertex and its associated edges must be freed.
2.5 void graph_delete(String_graph *const graph)
This function should deallocate all dynamically–allocated memory that is used in the String_graph variable that its
parameter graph points to, releasing the graph and all its data in the process. So when this function returns, the graph
data structure that graph previously pointed to effectively no longer exists in memory.
See Section 3 for explanation about when this function can– and must– be called.
3 Valid sequences of calls to the functions
A sequence of calls to the graph functions (including the ones from Project #7 as well as the new ones added in this
project) on a given String_graph variable is valid if and only if the sequence satisfies the following:
• graph_init() is the first call in the sequence.
• Unless it is the last call in the sequence of calls to the graph functions, a call to graph_delete() must be followed
immediately by a call to graph_init().
So following a graph_init() call and until the next graph_delete() call (if any), there can be any sequence of
calls of functions other than graph_init() and graph_delete(). And it is invalid to call any other functions on a
String_graph variable after graph_delete() is called on it, until graph_init() is called on it.
The effect of an invalid sequence of calls is undefined. Ensuring that the sequence of calls of your function is valid
is the responsibility of the caller of your functions– which includes your own tests– your code does not have to try to
detect violations of these properties, and in fact it has no way to do so.
If the user of your functions wants to avoid memory leaks they must make only valid sequences of calls to the graph
functions, and they must also ensure that the last function call they make in any sequence of calls to the functions on
a String_graph variable must be graph_delete(). They must also call free_vertex_name_list() exactly once on
every pointer returned by the two functions get_vertex_list() and get_neighbor_names(), and after that they must
not use the pointers again. (Note that a String_graph variable will still be valid even if this is not done.)
4 Memory checking and memory errors
We have included an object file memory-functions.o in the project tarfile, which has two functions named
setup_memory_checking() and check_heap() that are similar to the functions from Project #6. The header file
© 2023 L. Herman; all rights reserved 3
memory-functions.h contains their prototypes. They have no parameters or return value. We use them as follows in
some of our tests to detect memory leaks and corruption:
• setup_memory_checking() must be called once in a program before any memory is dynamically allocated; it
sets up things to check the consistency and correctness of the heap. If this function has been called initially, and
the program has any memory errors later (such as overwriting beyond the end of an allocated memory region in
the heap) the program will crash (consequently failing a test).
• If there is any memory in use in the heap at all when check_heap() is called it prints a message and causes the
program to immediately quit. If there is no memory in use in the heap at all then calling it just has no effect.
Some tests will initially call setup_memory_checking(), then call check_heap() after functions are called on the
different data structures and their memory is cleared. If the functions that are supposed to remove all or part of your
graph data structure are not freeing memory properly, your program will report that there is some allocated memory in
the heap– meaning a memory leak occurred- causing these tests to fail. (This could also happen if the user calls your
functions in an invalid order, for example by calling graph_init() on a nonempty String_graph variable without
calling graph_delete() on it first, but this is their fault. If you are using our memory checking functions in your own
tests and you make an invalid sequence of calls to these functions, such tests would fail.)
The facilities we use to perform this memory checking are not compatible with memcheck (valgrind), because
memcheck uses its own versions of the memory management functions, that themselves use some memory in the heap.
Consequently, if you run any tests that use our memory checking functions under valgrind, the test will appear to
fail with a memory leak, even if your code does not have memory leaks. You can use either our memory checking
functions with a program, or valgrind with it, but not both at the same time, or they will give incorrect results.
Appendix B describes how to easily use valgrind in this project.
The functions discussed in this section are for tests of your code to use. Do not try to call them from your
graph functions– this won’t work. And since your code in string-graph.c will not be calling these functions, your
string-graph.c should not include memory-functions.h. (Any of your own tests that want to check the correctness
of the heap will include memory-functions.h, and will have to be linked with memory-functions.o.)
A Development procedure review
A.1 Obtaining the project files, compiling, checking your results, and submitting
Log into the Grace machines and use commands similar to those from before:
cd ~/216
tar -zxvf ~/216public/project08/project08.tgz
This will create a directory project08 that contains the necessary files for the project, including the header files
string-graph.h, compare-vertex-lists.h, and memory-functions.h, the object files compare-vertex-lists.o
and memory-functions.o, and the public tests. As was discussed above, copy both of your string-graph.c and
string-graph-datastructure.h files from your project07 directory (or copy the corrected versions from the new
copy of your project07 directory if you followed the procedure in Section 1.1 above) to the project08 directory after
extracting it from the project tarfile, so you can add the new functions in it.
As in Project #7 you will not be compiling your code from the command line; you will use make and your makefile
to compile everything. diff can be used as before to check whether your code passes a public test or not, for example:
make public01.x
public01.x | diff – public01.output
(You can also run make from Emacs if desired.)
Note that your makefile cannot run each test when building it, because this will probably not work on the submit
server. If you want to create a separate target in your makefile that runs the tests this will not cause a problem on the
submit server (although a better way to do this will be explained in discussion section soon).
Running submit from the project directory will submit your project, but you first must make sure your makefile
works and you have passed all the public tests, by compiling them– using your makefile– and running them yourself.
Unless you have versions of all required functions that will at least compile, your program will fail to compile at
all on the submit server. (Suggestion– create skeleton versions of all functions when starting to code, that just have an
appropriate return statement.)
© 2023 L. Herman; all rights reserved 4
A.2 Grading criteria
Your grade for this project will be based on:
public tests 40 points
secret tests 45 points
programming style 15 points
Some secret tests may test your makefile. Section 4 of Project #7 explains the requirements for your makefile, so
review that to ensure that you are satisfying them, in case they are tested by secret tests in this project.
B Project–specific requirements, suggestions, and other notes
• The data structure requirements are the same in this project as in Project #7. Be sure you have followed them–
reread them in the Project #7 assignment.
• Note that different public tests in this project use different things and include different header files, so different
tests will have different dependencies in your makefile, and different files will have to be linked to create the
executables for different tests.
We emphasize again that you should not wait to write your makefile. Write it first– before you even start
writing the graph functions. This will avoid having to type commands for compiling the public tests, but more
importantly, using your makefile all during development, every time you compile your code, will allow you to
ensure it works correctly before you submit. You can copy your makefile from your project07 directory to the
directory for this project as a starting point, but the tests in this project will have different dependencies than they
did in Project #7, and different files will have to be linked to create their executables than in Project #7.
• Now that the preprocessor has been covered, and the conditional compilation directives that are actually always
used in C header files have been explained in class, you must now have correct conditional compilation directives
in your header file string-graph-datastructure.h.
(Note that part of using conditional compilation correctly is that you must spell the name of the preprocessor
symbol used for conditional compilation either as described in class and in the lecture slides, or in the form that
the Reek text uses, or you may lose some credit.)
• Since one header file in this project includes another one, your makefile must now use one of the approaches
recently discussed in class for handling dependencies in this situation, otherwise it may not perform needed
recompilations. (If your makefile doesn’t use one of these approaches you might lose a few points due to failing
a secret test.)
• As mentioned earlier, you cannot use valgrind together with our memory checking functions. We want to make
it easy for you to use valgrind if you have memory problems that arise while writing this project, so we wrote
the tests to allow you to easily turn off our memory checking, by just compiling with the preprocessor symbol
ENABLE_VALGRIND defined.
To be able to use valgrind (this assumes your Makefile is correct):
– Add a definition of ENABLE_VALGRIND (e.g., -D ENABLE_VALGRIND) to the compiler options in your
Makefile. (Recall you also have to add the -g option to be able to use valgrind, as well as gdb.)
– Force all the tests to be recompiled using make clean (or touching all source/header files would also work),
and recompile everything (our tests and yours).
– Now you can use valgrind on any test. When you’ve found the problem and are done using valgrind,
don’t forget to remove the definition of ENABLE_VALGRIND from the compilation options in your makefile
and recompile everything again, otherwise you will not be running the same versions of the tests as the
submit server is, because it will be using our memory checking for some tests. After re–enabling our
memory checking by removing -D ENABLE_VALGRIND and recompiling, rerun the tests to confirm that they
pass.
© 2023 L. Herman; all rights reserved 5
– When running valgrind, add the option –leak-check=no to turn off checking for memory leaks for any
test that is not calling graph_delete() on any String_graph variables when they are no longer needed
and is also not calling free_vertex_name_list() on any pointers returned by get_vertex_list() and
and get_neighbor_names() when they are no longer needed.
• Do not write code using loops (or recursion) that has the same effect as any string library functions. If you need
to perform an operation on strings and there is a string library function already written that accomplishes that
task, you are expected to use it, otherwise you will lose credit.
• You will lose credit if you cast the return value of the memory allocation functions. Besides being completely
unnecessary, in some cases this can mask certain errors in code.
• For this project you will lose one point from your final project score for every submission that you make in excess
of four submissions, for any reason.
• You cannot modify anything in the header files string-graph.h, compare-vertex-lists.h, or
memory-functions.h, or add anything to them, because your submission will be compiled on the submit server using our versions of these files. You cannot write any new header files of your own other
than string-graph-datastructure.h. Your code may not comprise any source (.c) files other than
string-graph.c, so all your code must be in that file.
• Any helper functions that you write in string-graph.c, whose prototypes are not already in string-graph.h,
will be “private”, so they should be declared static, and their prototypes should be placed at the top of
string-graph.c, not in string-graph.h or string-graph-datastructure.h.
• If you have a problem with your code and have to come to the TAs’ office hours for debugging help you must
come with tests you have written yourself that illustrate the problem (not the public tests), what cases it occurs
in, and what cases it doesn’t occur in. In particular you will need to show the smallest test you were able to
write that illustrates the problem, so whatever the cause is can be narrowed down as much as possible before the
TAs even start helping you. You must also have used the gdb debugger, explained in discussion section, and be
prepared to show the TAs how you attempted to debug your program using it and what results you got.
And besides having used gdb, you must have also run memcheck (valgrind) if your code has any bugs, and
be able to understand the results it shows.
• Recall that the course project policies handout on ELMS says that all your projects must work on at least half of
the public tests (by the end of the semester) in order for you to be eligible to get a C− or better in the course.
C Academic integrity
Please carefully read the academic honesty section of the syllabus. Any evidence of impermissible cooperation on
projects, use of disallowed materials or resources, publicly providing others access to your project code online, or
unauthorized use of computer accounts, will be submitted to the Office of Student Conduct, which could result in an
XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you
are not permitted to do in regards to academic integrity when it comes to projects. These policies apply to all students,
and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them.
More information is in the course syllabus – please review it now.
The academic integrity requirements also apply to any test data for projects, which must be your own original
work. Exchanging test data or working together to write test cases is also prohibited.
© 2023 L. Herman; all rights reserved 6
