CPSC 035: Lab 9: Social Meatia

Due on Friday, December 4th (by the end of the day, U.S. Eastern Daylight Time).

Overview

In this lab, you will develop your understanding of graphs and graph algorithms. You will do this by writing a series of graph algorithms to assist the citizens of the fictional town of Hampton in a variety of social-media-related tasks. You will then provide written examples of how some of these graph algorithms work.

Pig

OpenClipArt.org

Part I: Implementing Graph Algorithms

The URL for your repository will be

git@github.swarthmore.edu:cs35-f20/lab09-<your-teamname>

where your-teamname has been selected at random. You should be able to find your team repository by visiting the course organization on GitHub.

Your starting repository contains several files with main functions, each of which defines a different program. Your lab also includes a Makefile which will, by default, compile all of these programs (as well as your tests). We will discuss the individual programs below as separate parts of your lab. The files common to all of these programs include

  • adjacencyListGraph.h/adjacencyListGraph-inl.h: An implementation of an undirected, labeled, weighted graph in the form of a template class.

  • adts/: As usual, this directory contains the definitions of ADT interfaces as well as supplied implementations of the ADTs we’ve previously discussed.

  • graphAlgorithms.h/graphAlgorithms-inl.h: The definitions of the graph search algorithms you will implement.

  • graphIO.h/graphIO-inl.h: Support code for reading graphs from files.

  • stringUtils.h/stringUtil.cpp: Support code for error messages.

Make sure you have examined adts/graph.h to understand the interface you will be using in this lab.

Step 1: Depth-First Search for Oinked In

Pig

OpenClipArt.org

Those familiar with the social networking site Oinked In know that it primarily provides the service of guessing whether or not two people know each other. (It then eagerly recommends that they connect with each other and talk about their jobs.) You will write a simple depth-first search algorithm which, given a graph, will be able to answer this pressing question.

The file graphAlgorithms-inl.h contains a stub for a function reachableDFS which is called by the program oinkedIn. You can build oinkedIn either by running make (which builds all of our programs) or by building it specifically (e.g. make oinkedIn). The program has already been written for you in oinkedIn.cpp. That program expects three command-line arguments:

  • The name of the input graph file defining a social network graph.

  • The name of the first person to check.

  • The name of the second person to check.

Several social network graph files can be found in the test_data directory (e.g. test_data/social_network_25.graph). When using the terminal to run this program, make sure to include names in quotes so the program receives the whole name as a single string. For instance, you might run ./oinkedIn test_data/socialNetwork_8.graph "Kevin Bacon" "Jaimie Dengar". By using quotes, we can include spaces in our arguments on the command line.

When testing your search algorithm, you should start by running oinkedIn on small graphs first. Correct answers for several searches can be found in files corresponding to the social network filename (e.g. test_data/socialNetwork_25.oinkedIn.txt). Note that all of the social networks are connected graphs except for those whose names include the word “`Disconnected`”.

Using Dictionaries as Sets

Remember that a depth-first search on a graph must contend correct with cycles. This is especially important here, since the graph is undirected (and so every edge represents a cycle!). In order to avoid revisiting a node, you’ll need some way of keeping track of the nodes you’ve visited before.

Fortunately, dictionary data structures can be employed as sets! To keep track of a set of V, for instance, you can create a dictionary mapping V to any other type (e.g. Dictionary<V,bool>). Whenever an element is added to the set, you put that element with an arbitrary boolean. When an element is removed from the set, you remove that element.

A better idea would be to define a HashSet class which uses a HashTable field to perform these tasks. Then, you could write a series of operations such as add, remove, and even union so that the code which uses the Set would be more readable. You may do this, but you are not required to do so; just using a dictionary will work for this assignment.

Step 2: Breadth-First Searching and the Degrees of Kevin Bacon

Kevin Bacon

Wikimedia Commons

The Six Degrees of Kevin Bacon is a simple parlor game in which, given an entertainment personality, one must use six or fewer steps to connect that person to Kevin Bacon, who is an actor. This problem can be solved by representing the relationships between people as a social network graph and then performing a breadth-first search to find the path between them.

You will implement the shortestLengthPathBFS function in graphAlgorithms-inl.h to satisfy this requirement. The program bacon utilizes this function. It takes two command-line arguments:

  • The name of the input graph file defining a social network graph.

  • The name of the person to connect to Kevin Bacon.

For instance, you might run ./bacon test_data/socialNetwork_8.graph "Jaimie Dengar". This program always searches for Kevin Bacon; he is in all of the social network graphs. For some examples of the expected behavior of this routine, consult the answer files in the test_data directory (e.g. test_data/socialNetwork_25.bacon.txt). Make sure to test your code both on connected and disconnected social networks.

Step 3: Network Latency Testing via Dijkstra’s Algorithm for Instaham

Pig

OpenClipArt.org

Instaham is a social network designed primarily for the purpose of distributing pictures of food. A user in this network subscribes to a feed and receives these images when they are posted by the feed’s owner. In order to maximize food image distribution potential, the network engineers of Hampton need to determine the speed with which an image can be sent from one point in town to another.

Your test_data directory contains a collection of graphs which describe the town’s network (e.g. test_data/town_25.graph). Town network graphs are undirected graphs weighted by floats describing the delay of the connection. Given a point in town, the network engineers need a list of other town locations and the minimum time to reach that location. To accomplish this task, you will implement the singleSourceShortestPath function using Dijkstra’s algorithm.

Once you have implemented that function, you can use the program instaham to test it. This program expects two command-line arguments:

  • The name of the file containing the town network graph.

  • The name of the location from which to perform the analysis.

As with the other programs, you can find correct sample outputs in the test_data directory.

Coding Style Requirements

As usual, you will also be required to observe good coding practices:

  • Your C++ code must have proper and consistent indentations.

  • You must have proper and consistent usage of spacing & braces for if, else, for, and while conditions as well as class definitions and code blocks.

Part II: Written Assignment

Piglet

PublicDomainPictures.net

For the final part of your lab, you are interviewing with Stynet, the Internet service provider which connects Hampton to the rest of the world. To complete the interview, you will provide written answers to questions regarding the following graph:

graph

Give your answers to the following questions in a file named WrittenLab.pdf. You may use the provided WrittenLab.tex file; running make WrittenLab.pdf will produce your document. You may also use some other program to generate the document.

  1. Perform a breadth-first search of the graph starting from vertex A. Give the number of steps to reach every other vertex. Additionally, give the order in which the vertices are first witnessed; that is, give the order in which they first enter the exploration queue (and not necessarily the order in which they are explored).

  2. Use Dijkstra’s algorithm on this graph starting from vertex A. Give the cost of the least-cost path to every other vertex. Additionally, give the order in which the vertices are first witnessed; that is, give the order in which they first enter the exploration queue (and not necessarily the order in which they are explored).

  3. Give two valid topological sorts of this graph.

Summary of Requirements

When you are finished, you should have

  • An implementation of the three graph algorithms

  • No memory errors or leaks

  • Code which conforms to the style requirements

  • A write-up answering the above graph algorithm questions

  • A completed lab assignment survey from each student

Zachary Palmer and Michael Wehar, Swarthmore College, 2020