Data Structures CSE 2341
Fall 2018 Programming Assignment 04 Page of
Degrees of LinkedIn
Due: Monday Nov 5 @ 6am posted to GitHub in the CSE 2341 Repo Created by the Course Staff and Release Issued.
When you log in to LinkedIn and go to a profile that you’re not already linked with, sometimes you’ll see information about who you and the profile of interest have in common. In this project, you’ll implement an algorithm to determine the shortest chain of people possible to make a connection between two people.
Each oval represents an individual; each line connecting two ovals represents two individuals being linked. We call the line connecting two individuals an edge.
In this project, you’ll determine some characteristics of the social graph as well as characteristics of connections between certain individuals.
Connections Data – This file will contain a sequence of individual-to-individual connections. A connection between two individuals is bidirectional.
Distance Requests – This file will contain a sequence of name pairs. You’ll need to calculate the minimum distance between these two individuals using iterative backtracking on your adjacency list. The distance between an individual and himself or herself is defined to be zero. The distance between two individuals that are directly connected via an edge is defined to be one.
The names of the two input files as well as the output file will be provided via command line arguments.
Here is an example of a data input file (it is not one that goes with the figure above):
Bob Smith|Sally Simpson
Sally Simpson|Daniel Davidson Sally Simpson|Susan Jackson Susan Jackson|Daniel Davidson
The first line of the file will contain an integer indicating how many rows of data will be in the file. Each subsequent row will contain two individual’s names separated with a pipe (shift-\ on most keyboards).
Requested Distance Data File
A sample input file for requested minimum connection distance is shown below. . The first line will contain an integer indicating the number of input lines in this file. The subsequent lines will contain a pipe-delimited list of individual pairs separated by a pipe. No name will be present in this file that doesn’t exist in the Connections Data file.
Bob Smith|Daniel Davidson Sally Simpson|Daniel Davidson Bob Smith|Bob Smith
The first n lines of the output file will contain one line for each unique individual in the Connections Data file. Each line will contain the name of an individual (alphabetic ordering by name as it appears in the input file) followed by an integer value of the number of people this person is connected to directly and indirectly with max distance of 2. In other words, this is the number of people an individual shares an edge with and all of the people those folks share an edge with.
The next m lines of output contain one line for each name pair in the Requested Distance Data File. You’ll print the name pair followed by a space followed by the minimum distance between those two individuals as calculated by an exhaustive iterative backtracking solution. You may assume that the network of individuals represented in the connections data file provides at least one path between any two individuals.
So, in total, the output file should have n + m lines of output where n is the number of unique individuals in the system (the number of nodes) and m is the number of requested pairs for which min distance is requested.
Executing Your Program
The final version of your program will be run from the command line with the following arguments:
./linkedin -r <ConnectionsDatafile> <RequestedConnections> <OutputFile>
Alternatively, your program should run tests for the LinkedList, Stack, and Adjacency List if is is called with the following argument:
What to Submit
By Monday, Nov 5 @ 6am, you should have pushed the following to Github and opened a release:
- Completed Project All code submitted should :
- be well formatted and documented
- follow all best practices covered in lecture and lab
- follow good design principles for object oriented programming
Your project will be graded by one of the TAs for the course.
Design of Algorithms for Calculating required information
Source Code Quality