Detect Cyclic Dependancy in Hashmap in Java

Question

I have a hashmap of:

Tables => Set of Parent Tables [ HashMap<String, HashSet<String>> ]

Example of non-cyclic case could be:

A -> [B,C]
D -> [B,C]
B -> [C]
c -> []

Example of cyclic case would be:

A -> [B,C]
B -> [C]
C -> [A]

I want to reject the cyclic cases and hence need a function which could detect if the provided hashmap has any cycles or not :

public boolean hasDependencies(HashMap<String, HashSet<String>> objectAndItsDependentsMap)
{
   //Implementation
}

I have read posts suggesting algorithms to detect cycles but being a newbie to java could not use that knowledge to makeup the above function.

Answer 1

Here's a rough implementation based solely on your example. I suggest testing against other examples.

public boolean hasDependencies(Map<String, Set<String>> objectAndItsDependentsMap) {
    for (String node : objectAndItsDependentsMap.keySet()) {
        final Set<String> directNeighbors = objectAndItsDependentsMap.get(node);
        for (String directNeighbor : directNeighbors) {
            Set<String> next = objectAndItsDependentsMap.get(directNeighbor);
            while (next != null) {
                for (String n : next) {
                    next = objectAndItsDependentsMap.get(n);
                    if (next != null && (next.contains(n) || next.contains(node))) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

Answer 2

I would recommend you read about and implement Tarjan's algorithm.

Tarjan's algorithm

I used it some time ago. It's quite efficient.

See also:

Best algorithm for detecting cycles in a directed graph