In the two tasks of this assignment you will be asked to complete the implementation of the SocialGaph class shown below. You can copy-paste the code into your Java development environment. The class has a private attribute called map of type HashMap> that is used to store the social graph in the manner explained above. The addIndividual and hasKnowsArrow methods are already implemented.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
/**
* The SocialGraph class stores a social graph and implements
* a number of methods to construct and query the graph.
*/
public class SocialGraph {
// The map that stores the social graph
private HashMap, List> map
= new HashMap, List>();
/**
* Add individual a to this social graph.
* Do nothing if a already exists in this social graph.
*/
public void addIndividual(String a, String b) {
if (!map.containsKey(a)) {
map.put(a, new ArrayList());
}
}
/**
* Returns true if a knows b.
*/
public boolean hasKnowsArrow(String a, String b) {
if (map.containsKey(a)) {
return map.get(a).contains(b);
} else {
return false;
}
}
/**
* Update the social graph with a knows arrow from a to b.
* This method will add a and b to the social graph unless
* they already exist.
*/
public void addKnowsArrow(String a, String b)
{ // Your code here
}
/**
* Remove the knows arrow from a to b. Do nothing if this arrow
* does not exist or if a or b do not exist in the social graph.
*/
public void removeKnowsArrow(String a, String b) {
// Your code here
}
/**
* Return true if a knows b with degree x.
*/
public boolean knowsWithDegree(String a, String b, int x) {
// Your code here
return false;
}
}
Task A (5pt)
Implement the addKnowsArrow and removeKnowsArrow of the SocialGraph class. The addKnowsArrow method must first ensure that individuals a and b are present in the graph. Then it must add a knows arrow from a to b by updating the hash map in the appropriate way. The removeKnowsArrow method must remove the knows arrow from a to b but should not remove the individuals a or b from the graph. (4pt) Now create another class called SocialGraphTest with a static main method in which you use your SocialGraph implementation to construct an instance that represents the social graph from Figure 1. You do not need to include any user input or output. (1pt)
Task B (5pt)
Let’s define the notion "X knows Y with degree n" as follows:
X knows Y with degree 1
if X knows Y,
X knows Y with degree 2
if X knows someone who knows Y,
X knows Y with degree 3
if X knows someone who knows someone who knows Y, and so on. For example, according to the social graph in Figure 1, Anne knows Bob with degree 1, Anne knows Charlie with degree 2, and Anne knows Daisy with degree 1 and 2. Implement the knowsWithDegree(String a, String b,
int
x) method so that it returns true whenever person a knows person b with degree x. Hint: The definition already states that a knows b with degree 1 whenever a knows b. Now observe that a knows b with degree n (for any n > 1) whenever a knows someone who knows b with degree n-1. This observation immediately suggests a recursive solution. This solution requires no more than eight lines of code. Now extend the SocialGraphTest class from Task A so that it checks whether Anne knows Daisy with degrees 1, 2 and 3, and prints the answers on the console.