Social Graphs

Introduction

This assignment gives you an opportunity to write a Java class that constructs a directed graph to model friendships in a social network. Graphs are useful for many applications such as computer gaming (e.g., modeling game objects with spatial relationships), maps of cities and routes, computer networking (e.g., finding a shortest route for sending data between computers), just to name a few.

Overview

You are to implement two classes: DiGraph.java and SocialGraph.java.

• The DiGraph class is a public generic class. This class requires methods for manipulating a weighted directed graph such as adding vertices and edges, removing vertices and associated edges, and computing a shortest path from a given vertex to all the other vertices. See the template code for this class for all the methods to be implemented. The class uses a Java Map to store entries of a vertex and weighted edges. The code for the Edge class is given.
• SocialGraph is a class with the public static void main(String[] args). It reads each line from an input file with the filename specified in args[0]. If the input filename is not given (args.length<1), print out an error message on screen and return. Each line in the file has a command and arguments. The commands are for establishing a friendship between names, shows friends of a given name. The main method calls the method associated with each command and pass in arguments. See the input file infile.txt and the output results in outfile.txt. You can assume that the format of the input file is correct.

You are not required to submit JUnit test code. You may share any test code on Blackboard Learn.

Social Graph Construction

Fig. 1 show the graph after “add James Larry 1” after the DiGraph object is constructed. James is a friend of Larry. The weight indicates the distance of the friendship based on James’s perception (i.e., how close Larry is to James based on James’s perception). The distance is between 1 and 5 inclusive. With 1 indicates the least distance (i.e., a best friend); 5 indicates the maximum distance. Note that without an explicit “add Larry James 1,” in the input file, Larry is not a friend of James. Also, if later, an edge from Larry to James is added, it is not required that the weight of this edge be the same as that of James to Larry. In other words, the distance of the friendship is not necessarily symmetric.

Figure 1. Graph as a result of “add James Larry 1” in the input file; the number of vertices in the graph is 2 and the number of edges is 1. See image.

Figure 2. (a) Result of the lines shown in (b) in the input file on the graph in Fig. 1. The number of vertices in the graph is 7 and the number of edges is 10. See image.

In Fig. 1, the edge between James and Larry is already there. The “add James Larry 2” line overrides the existing weight between James and Larry. The rest of the nodes are added accordingly. The result of each line is shown.

showFriends James
[Liam, 1, Jim, 2, Larry, 2]
showFriends Larry
[Kaith, 1]
showFriends Liam
[Jim, 1, Keith, 1, Kaith, 3]
showFriends Jim
[Keith, 1]
showFriends Keith
[Jim, 1]
showFriends Kaith
[]

The recommendFriends name dist|weightedDist topK command has two options: “dist” to find the friend candidates using friendship distances and “weightedDist” is to find the friend candidates using friendship distances weighted by the number of incoming edges. The more the incoming edges, the person is more well liked. name is to be replaced by the name of interest. topK is to be replaced by the maximum number of names to return (when there is no tie in terms of distance/weighted distance).

recommendFriends James dist 1
Keith, 2
recommendFriends James weightedDist 5
Keith, 16
Kaith, 21

• recommendFriends James dist 1 Find one candidate friend for James using the friendship distance only. The shortest path from James to Keith has a distance of 1+1=2 (James, Liam, Keith). The distance from James to Jim is also 2; however, Jim is already a friend of James. So, we do not list Jim as the candidate.
• recommendFriends James weightedDist 5 Find five best candidate friends for James using the shortest friendship distance multiplied by the total number of edges in the graph less the number of incoming edges to that node. This is a simple weighted distance function. The lower the weighted distance is, the better the candidate. The weight distance calculation favors candidates who are closer friends of friends (low distance) and are wellliked.
• Given the graph in Fig. 2, the total number of edges in the graph is 10. The shortest friendship distance from James to Keith is 2. Keith has 2 incoming edges; therefore, the weighted distance for Keith is 2*(10-2)=16. The shortest friendship distance from James to Kaith is 3 (James, Larry, Kaith). Kaith has 3 incoming edges; the weighted friendship distance is 3*(10-3)=21. We do not recommend Larry or Jim for James since they are already friends of James. We do not recommend Pie since Pie is not reached by any existing friends of James.
• When there are several candidates with the same distance/weighted distance as the last candidate in the topK list, include all these candidates in the list even though the number of names returned may be more than the specified topK value.

Fig. 3 shows the graph when the line “remove Jim” is processed. The vertex “Jim” and incoming and outgoing edges of Jim are all removed. See image.

Figure 3. The resulting Graph when “remove Jim” line is applied to the graph in Fig. 2. The vertex “Jim” is removed along with its outgoing edges and incoming edges to this vertex. A total of 4 edges are removed. The number of edges in the graph is down to 6.

Java Collections Objects

You may use any Java Collection objects to help with your implementation, but you must use the provided member variable map to keep vertices and Edge objects to keep edges and correctly update the value of numEdges. You may use additional member variables or write private methods as needed. Be careful not to introduce many more variables.

Note that Java LinkedList and PriorityQueue class implement Java Queue generic interface.

Documentation

All public methods must have Javadoc comments, including descriptions of each parameter and any exceptions that might be thrown. Add the description on how you implement the methods. Any other methods or helper classes you introduce must have either Javadoc or inline comments explaining what the methods do. Add @author tag followed by your full name in each Java source file.