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.
You are to implement two classes: DiGraph.java and SocialGraph.java.
You are not required to submit JUnit test code. You may share any test code on Blackboard Learn.
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.
[Liam, 1, Jim, 2, Larry, 2]
[Jim, 1, Keith, 1, Kaith, 3]
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
recommendFriends James weightedDist 5
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.
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.
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.