I am not sure if the title to this question is correct. I have this school assignment where we have to create two classes. In one class, we define relationships between people e.g. A knows B, and in the other class we ask questions about that, e.g. does A know B?

The first class below defines relationships and gives methods, the second class inquires about them. I am sure that my mistake lies somewhere in the public boolean 'knowsWithDegree'. Are you able to help?

public class SocialGraph {

private HashMap<String, List<String>> map = new HashMap<String, List<String>>();

public SocialGraph() {   // empty constructor
    map = new HashMap<String, List<String>>();
}

public void addIndividual(String a) {
    if (!map.containsKey(a)) {
        map.put(a, new ArrayList<String>());
    } else {
    }
}

public boolean hasKnowsArrow(String a, String b) {
    if (map.containsKey(a)) {
        return map.get(a).contains(b);
    } else {
        return false;
    }
}

public void addKnowsArrow(String a, String b) {

    if ((!map.containsKey(a) || !map.containsKey(b)) || (hasKnowsArrow(a, b))) {
    } else {
        map.get(a).add(b);
    }
}

public void removeKnowsArrow(String a, String b) {

    if ((!map.containsKey(a) || !map.containsKey(b)) || (!hasKnowsArrow(a, b))) {
    } else {
        map.get(a).remove(b);
    }
}

public boolean knowsWithDegree(String a, String b, int x) {
    Object[] keys = map.keySet().toArray();

    int y;
    y = 0;

    if (map.get(a).contains(b)) {
        y = 1;
    } else {

        if ((map.get(a).contains(map.get(keys[0]).contains(b))) || (map.get(a).contains(map.get(keys[1]).contains(b))) ||
                (map.get(a).contains(map.get(keys[2]).contains(b))) || (map.get(a).contains(map.get(keys[3]).contains(b)))) {
            y = 2;
        }
    }
    if (x == y) {
        return true;
    } else
        return false;
}

}

public class SocialGraphTest {

public static void main(String[] args) {
    SocialGraph socialGraph = new SocialGraph();
    socialGraph.addIndividual("Anne");
    socialGraph.addIndividual("Daisy");
    socialGraph.addIndividual("Bob");
    socialGraph.addIndividual("Charlie");


    socialGraph.addKnowsArrow("Anne", "Bob");
    socialGraph.addKnowsArrow("Anne", "Daisy");
    socialGraph.addKnowsArrow("Bob", "Daisy");
    socialGraph.addKnowsArrow("Bob", "Charlie");

    System.out.println(socialGraph.hasKnowsArrow("Anne", "Bob")); //should be true
    System.out.println(socialGraph.hasKnowsArrow("Anne", "Daisy"));//should be true
    System.out.println(socialGraph.hasKnowsArrow("Bob", "Daisy"));//should be true
    System.out.println(socialGraph.hasKnowsArrow("Bob", "Charlie"));//should be true
    System.out.println(socialGraph.hasKnowsArrow("Anne", "Charlie")); //should be false

    System.out.println ();

    System.out.println (socialGraph.knowsWithDegree ("Anne", "Daisy", 1));
    System.out.println (socialGraph.knowsWithDegree ("Anne", "Charlie", 2));
    System.out.println (socialGraph.knowsWithDegree ("Anne", "Daisy", 3));

}

}

CodePudding user response：

Here is an example using recursion:

        public boolean knowsWithDegree(String a, String b, int x) {
            return knowsWithDegreeRecursive(a, b, x, new HashSet<>());
        }
        
        private boolean knowsWithDegreeRecursive(String a, String b, int x, Set<String> visited) {
            if (x < 1) {
                // x must be at least 1
                return false;
            }
            

            if (map.get(a).contains(b)) {
                // If a knows b, then the number of degrees should be 1
                return x == 1;
            }
            
            if (x == 1) {
                // Since the degree is 1 and a does not know b, then a does not know b to the specified degree
                return false;
            }
            
            // Go through each person that a knows
            for (String c : map.get(a)) {
                
                if (visited.contains(c)) {
                    // We've already checked this person
                    continue;
                }
                
                // Mark c as visited so we don't check them again
                visited.add(c);
                
                // See if this person knows b, with one fewer degree
                // e.g. if we're seeing if a knows b with a degree of 2, then c should know b with a degree of 1
                boolean knowsWithDegree = knowsWithDegreeRecursive(c, b, x - 1, visited);
                
                // If c knows b with the degree minus 1, then a knows b with the specified degree
                if (knowsWithDegree) {
                    return true;
                }
            }
            
            // a does not know b to the specified degree
            return false;
        }
        

If the order of the knowsArrows doesn't matter, I would recommend using HashSet in your map over ArrayList.