CS61C Fall 2016 Project 1: Flight Map

TA: Manu Goyal

Due September 22, 2016 @ 11:59pm

Goals

This project aims to get you more familiar with some important concepts in C programming. It covers data structure design, memory management, algorithms, and some file IO.

Setup

To get the starter code for this project, we will be using git.

  1. Create a private repository in your class account (which you should have set up in lab 0), of the form proj1-xxx, where xxx is your login. Please make absolutely certain your repository is set to private. If you fail to set the repository to private, we will have to assume intention to cheat and you will be severely punished.
  2. From the access management settings, grant admin access to cs61c-staff. Do not add this after completing your project. Do it now, to avoid penalties to your grade.
  3. Create a local copy of your project files, and add the code from the project 1 starter repository as a remote. Use the following commands to do so: 
                  $  git clone https://mybitbucketusername@bitbucket.org/mybitbucketusername/proj1-xxx.git 
              $  cd proj1-xxx 
              $  git remote add proj1-starter https://github.com/61c-teach/fa16-proj1-starter.git 
              $  git fetch proj1-starter 
              $  git merge proj1-starter/master -m "merge proj1 skeleton code"
    Note: in case we announce updates to the project starter code, you'll need to merge the updates in with your current repo. To do this, simply re-run the last two steps from above 
                  $  git fetch proj1-starter 
              $  git merge proj1-starter/master -m "merge proj1 skeleton code"

Once you complete these steps, you will have all the skeleton files inside of your repository. As you develop your code, you should make commits in your git repo and push them as you see fit.

Note: the software necessary to build the project code is on the hive machines (ssh in with ssh cs61c-xxx@hive[1-26].cs.berkeley.edu). Do not try working on another group of instructional machines (cory, ashby, icluster, etc.), as we have not tested everything on these machines. You are free to use your own personal computers to work on the project as well, just make sure you install all the necessary tools (valgrind and gdb are strongly recommended, in addition to the standard UNIX tools), and make sure to test on the hive machines before submitting.

Overview

Imagine you're an airline, tasked with routing people between various cities, while maintaining an ever-changing map of cities and flights between cities. We're going to build a simple system to solve this problem. Our system will keep track of a set of named cities as well as a set of bi-directional links between them. It'll be able to answer queries about the number of cities and the links each city has to others, and also find routes between cities.

You will be completing the implementation of flight_map.c, which is tied to the header file flight_map.h. The header file includes an abstract struct definition map_t, which you will need to fill in, as well as signatures for the functions you will need to implement. We will describe these components in a bit more detail below. There is also a file tests.c, where you can place your own tests (more on testing later).

Note: we will only be grading what you have in flight_map.c. You should place all of your graded code in this file. Do not expect your modifications to other files to be used while grading, we will only be looking at your flight_map.c file.

You should comment your code so we can give feedback and possibly partial credit easier.

Description of Structures and Functions

map_t structure

Before you can implement the functions, you'll need to figure out a correct data representation for the map object. In general, your map needs to keep track of a set of cities, and a set of bi-directional links between cities. Cities and links can be added and removed dynamically, and cities are identified in the interface by a const char* name.

Hint: read through the remaining functions you'll need to implement (but do not actually implement them), before settling on a data representation for the map_t structure. You will most likely need to create some helper data structures to accompany map_t, possibly with their own set of helper functions. Do not worry too much about getting this exactly right before starting to implement the other functions. You will almost certainly need to modify this data representation as you get a better sense of what functionality the interface requires. However, do make sure you are reasonably confident in the correctness of your structure before trying to implement everything else. A good map_t structure with robust helper methods will make implementing the remaining functions much easier.

Hint: you will most likely need to maintain a collection of city objects, which keep track of the city name, links to other cities, and possibly some other auxiliary data. Do not bother designing a highly efficient data structure (like a hashtable) to support these operations. We will not be measuring performance, so correctness is paramount. Something simpler, like a linked list, will suffice. Do not be afraid to search the internet for basic examples of linked list implementations. Here is a pretty comprehensive tutorial on linked lists that might come in handy.

map_create and map_free

These functions will create a new instance of a map, and release all of its allocated memory, respectively. Make sure to keep track of where in the code you are allocating memory, so you can free everything at the correct time. As a rule of thumb, you should have a free statement for every malloc in the code.

add_city and remove_city

These functions add a city to the map, and remove a city, respectively. If new city was successfully added or removed, then return a 1. Duplicate cities are not allowed, so return a 0 if the city already exists (in the case of add_city) or if the city does not exist (in the case of remove_city), or in case of another error. In remove_city, make sure to remove all links to the city being removed that you may be storing elsewhere.

Note that the city is specified as a const char* in both functions. The user will never deal with any internal city objects you create, so you will need to keep track of the mapping from city name to city object yourself.

Also note that even though the city name argument is of type const char*, this does not mean that the city will be a string literal. You should keep an independent copy of the city name in your map, and free it whenever necessary.

num_cities

This function returns the number of cities currently in the map. As a reminder, there are no performance constraints (within reason) on your code, so do not worry too much about algorithmic complexity.

link_cities and unlink_cities

These functions create and remove links between cities in the map. These are bi-directional links, so make sure there is a connection going in both directions. As in add_city and remove_city, return 1 if a link was successfully created or removed, and 0 if nothing was done or another error occurred. While one city can link to multiple other cities, you must not allow duplicate links between the same pair of cities. In order for these functions to succeed, both cities passed in must exist. No cities should be created or removed in these functions.

linked_cities

This function returns an array of city names that directly link to the given city. Cities that are only indirectly linked (more than one hop away) to the source should not appear in this list. The array should be a dynamically-allocated array of const char*, with the last element being NULL, to indicate the end of the list. In case the city doesn't exist, do not create an array, return NULL instead. It is not necessary to return the cities in any specific order.

Note that the return type specifies const char* as the string type, rather than char*. This means the user is not responsible for managing the memory of the strings you return them, only the array. So don't make separate copies of the city names to return in this function, because the testing code will not free the individual strings, and you will cause a memory leak.

Remember that if the city does exist but is not linked to any other cities, you should return an empty array, which contains one element set to NULL.

find_path

This will probably be the most involved function you have to implement. It accepts two city names, a source and a destination, and returns an array of cities (similar to linked_cities) that are linked together in order from the source to the destination. The details of the return value format are described in flight_map.h, so we will give some high-level implementation hints.

In more abstract terms, the map can be thought of as an undirected graph, where cities are vertices, and links are the edges between the vertices. The fact that the edges are undirected means that you can traverse between cities in both directions. This function requires you to search through this graph and find a path through the graph that starts with the source vertex and ends with the destination vertex, without any vertices repeating in the path.

You are free to implement any graph search algorithm of your choice. Remember that we are not asking you to find the shortest path, but instead any path that links the source to the destination without any repeated vertices. We describe a high-level algorithm for depth-first search, a well-known graph search algorithm that is well-documented on the internet (the Wikipedia article is quite detailed as well). Here is a basic description of how the DFS algorithm might run on your map.

  1. Start your search on the source city. Mark the city as visited.
  2. If you have found the destination, return an array that can hold the entire path, with NULL as the last element and destination as the second to last element.
  3. If you are not at the destination, iterate through the cities linked to by the current city. For each city that is not already marked, recurse with this city as the new source city (returning to step 2). If a path was yielded, add the original source city to the path and return.

Hint: this description mentions marking each city as you encounter it for the first time. This is necessary so that we can keep track of which cities we have already seen and which we have yet to explore. If this is not done, the DFS can get into an infinite cycle, exploring a cycle of linked cities over and over again. One way to implement such a marker is to store a boolean on each city and set it for each city visited. This requires clearing all booleans before the search begins. Another way to implement this is using a strictly increasing integer, that is incremented for every call to find_path. If a city has a lower mark value than to the current, it will be considered unvisited and its mark will be set to the current. Otherwise it will be considered visited and skipped.

Extra Credit

The following functions can be implemented for a small amount of extra credit (no more than 10% the point value of the project). We reserve the right to determine the exact amount of extra credit at or under this limit.

map_export and map_import

These functions provide functionality for serializing the map to a file, and creating a map from a serialized description in a file, respectively. You are free to design any serialization format you wish, as long as the map can be completely recovered from an exported version.

We suggest you use the methods in stdio.h to read and write the given files. You might find the fprintf and fscanf methods useful. Note that we won't be testing city names with whitespace, so feel free to use whitespace to separate city names when printing and scanning.

Testing & Debugging

We provide a file tests.c, which contains some very basic tests for the flight_map. These tests are nowhere near complete, so we strongly suggest you add your own tests.

A Makefile is provided for you. Standard usage is as follows: 

        // compiles executable tests
        $  make 
        // compiles executable and runs ./tests
        $  make check
        // compiles the executable and runs valgrind on ./tests
        $  make memcheck

Notice we have provided a command to run valgrind on your code. Valgrind is a very useful tool designed to find memory leaks and invalid memory accesses in your code. We strongly recommend you run Valgrind on your code before submitting. We will run it while grading, and you will be penalized for having memory leaks or invalid accesses in your code. We also recommend using GDB (covered in lab 1) to step through your code when you run into bugs.

It is crucial to remember that we will only use your flight_map.c file when grading. No modifications to any of the other files (such as tests.c) will be accounted for, so make sure your code runs correctly with only modifications to flight_map.c before submitting.

Submission

There are two steps required to submit proj1. Failure to perform both steps will result in loss of credit:

First, you must submit using the standard unix submit program on the instructional servers. This assumes that you followed the earlier instructions and did all of your work inside of your git repository. To submit, follow these instructions after logging into your cs61c-xxx class account: 

        // Your proj1 git repo, should contain all the files for the project
        $  cd <proj1 repo directory> 
        $  submit proj1

Once you type submit proj1, follow the prompts generated by the submission system. It will tell you when your submission has been successful, and you can confirm this by looking at the output of glookup -t.

Second, you must submit proj1 to your BitBucket repository. To do so, follow these instructions: 

        // Your proj1 git repo, should contain all the files for the project
        $  cd <proj1 repo directory> 
        // If you have any outstanding un-committed changes, add all modified
        // files in proj1 directory
        $  git add -u 
        $  git commit -m "your commit message here" 
        // The tag MUST be "proj1-sub". Failure to do so will result in loss of credit.
        $  git tag -f "proj1-sub" 
        // Note the "--tags" at the end. This pushes tags to bitbucket
        $  git push origin master --tags

Resubmitting

If you need to re-submit, you can follow the same set of steps that you would if you were submitting for the first time. The only exception to this is in the very last step, git push origin master --tags, where you may get an error like the following: 

        (21:28:08 Sun Feb 01 2015 cs61c-ta@hive12 Linux x86_64)
        ~/work $  git push origin master --tags 
        Counting objects: 22, done.
        Delta compression using up to 8 threads.
        Compressing objects: 100% (19/19), done.
        Writing objects: 100% (21/21), 9.73 KiB | 0 bytes/s, done.
        Total 21 (delta 4), reused 0 (delta 0)
        To git@bitbucket.com:cs61c-staff/cs61c-ta
        bf20433..d1ff9ed  proj1 -> proj1
        ! [rejected]        proj1-sub -> proj1-sub (already exists)
        error: failed to push some refs to git@bitbucket.com:cs61c-staff/cs61c-ta'
        hint: Updates were rejected because the tag already exists in the remote.

If this occurs, simply run the following instead of git push origin master --tags: 

        $  git push -f origin master --tags

Note that in general, force pushes should be used with caution. They will overwrite your remote repository with information from your local copy. As long as you have not damaged your local copy in any way, this will be fine.