Referring to an instance that refers to an instance

Question

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));
        
        }
    }
}

Answer 1

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.