Find Invalid User Relationships in User to Manager Map (validate map as valid tree structure with no circular relationships)

Question

We have a new service where an admin can upload a spreadsheet of new users they want to add to our application. During our processing we make a union map of all the users both existing and new additions, and check to make sure that the users will still be in a valid tree structure(s) after the update goes through.

Requirements:
For the user relationship tree structure to be valid,

• There can be no circular references (ex. Users cannot be each other's manager)
• A single branch of the tree cannot exceed 50 users (ex. There should not be 50 middle-management managers between CEO and Janitor).
• Its ok if the tree is severed into multiple trees when a user does not have a manager. Separate warnings are generated for that circumstance.

This may need to scale to up to 1,000,000 user relationships, so far, the current solution supports at least 10,000 user relationships in a reasonable amount of time (less than 1 minute running locally).

FYI this is Groovy/Java

Solution So Far:
I have a method that takes a HashMap of user relationships and it returns a list of invalid users ids.

Map<String, String> userRelationships = [["userId1": "userId2"], ["userId2": "userId3"], ...]
def invalidRelationships = findInvalidRelationships(userRelationships)

.

/**
 * Takes a map of user relationships (user with corresponding manager)
 * For each relationship, climb up the tree and look to see if the user is repeated in their branch
 * If user is found again up the tree branch, that is a bad circular reference
 * If the current branch goes on past 50 users, that is too long and also invalid
 * Report all users that are part of that bad relationship
 * userRelationship.key is the user
 * userRelationship.value is the manager
 */
def findInvalidUserRelationships(Map<String, String> userRelationships) {
    Set<String> invalidUserRelationshipUsers = []
    userRelationships.each { Entry<String, String> currentUserRelationship ->
        Set<String> usersInCurrentBranch = []
        Entry<String, String> nextIterationRelationship = currentUserRelationship
        while (
                nextIterationRelationship?.value && //while not top of tree (not null manager)
                        !invalidUserRelationshipUsers.contains(nextIterationRelationship.key) && //while user not part of circular relationship
                        !usersInCurrentBranch.contains(nextIterationRelationship.key) //while user not connected to other circular relationship
        ) {
            usersInCurrentBranch << nextIterationRelationship.key
            //if bad circular relationship found or branch has more than max users, report users as invalid
            if (nextIterationRelationship.value == currentUserRelationship.key || usersInCurrentBranch?.size() > 50) {
                invalidUserRelationshipUsers += usersInCurrentBranch
            }
            //set next user relationship to check in next iteration (manager's manager) - (go upline)
            nextIterationRelationship = new MapEntry(
                    nextIterationRelationship.value, //manager of current iteration user will be next user
                    userRelationships[nextIterationRelationship.value as String] //manager's manager
            )
        }
    }
    return invalidUserRelationshipUsers as List<String>
}

I have already made lots of optimizations, at least compared to how bad it was before using only Lists instead of Maps and Sets, but I was wondering if there would be a more efficient solution to this problem. I wondered if a Java TreeMap would be appropriate somewhere here, but could not figure out how it could improve performance.

Answer 1

Using TreeMap?

You have a tree represented in a HashMap, which is completely fine. A TreeMap has a specific tree structure based on comparable. I don't think the hierarchy of the employees can be expressed with a suitable comparable.

Variable names

Meaningful variable names are good. In this case, the operation of findInvalidUserRelationships is purely mathematical (finding cycles in a graph, checking whether the height of a tree exceeds 50) and I find it easier to understand the method using more math related names. It might also be more readable here to use

map.each { k, v -> println("key: $k, value: $v") }

instead of

map.each { entry -> println("key: $entry.key, value: $entry.value") }

So I have rewritten your method and in the following I will refer to the rewritten version.

List<String> findInvalidNodes(Map<String, String> edges) {
    Set<String> invalidNodes = []
    edges.each { String currentNode, _ ->
        Set<String> nodes = []
        String child = currentNode
        String parent = edges[currentNode]

        while ( parent && !invalidNodes.contains(child) && !nodes.contains(child) ) {
            nodes << child
            if (parent == currentNode || nodes.size() > 50) {
                invalidNodes.addAll(nodes)
            }
            child =  parent
            parent = edges[parent]
        }
    }
    return invalidNodes as List<String>
}

I have already conducted a minor change by replacing invalidNodes += nodes with invalidNodes.addAll(nodes). This can be a slight improvement of performance since invalidNodes grows over time and += creates a new list each time it is invoked while addAll simply adds items to the existing list.

Performance

You traverse the tree starting from each node to the top. Therefore there are several nodes that are visited multiple times. Think about a linear tree structure.

Map edges = (1..51).collectEntries { [it+1 as String, it as String] }
findInvalidNodes(edges)

The tree has 52 nodes and is therefore invalid. But since I built the map edges so that the order of entries is worst case, you start with nodes 1, 2, ..., 51 and need 1+2+3+...+51 = 1326 loops to detect that the nodes are invalid. If you started with the last entry of the map it would only take 51 loops. Since the height is limited to a constant amount I would see the method still as scalable. You can think about saving information for visited nodes and use that information once you find a visited node.

Is the Method working as intended?

Root node missing

Due to the while condition while(parent) a child with no parent (therefore all roots of the trees) cannot be treated as invalid. For the same reason a root node will never show up in nodes list so effectively you check for tree height > 51 and not tree height > 50.

Child of invalid Parent not invalid

Due to the while condition while ( !invalidNodes.contains(child) ) the loop breaks once the parent of a child is invalid. But the child is never added to the invalidNodes list. Is this really intended?

Map edges = (1..101).collectEntries { [it+1 as String, it as String] }}
assert findInvalidNodes(edges) == [2, 3, ..., 52] 

This tree has 102 nodes, but only [2, 3, ..., 52] are invalid. 53, 54, ..., 102 are not treated as invalid. If you add one more

Map edges = (1..102).collectEntries { [it+1 as String, it as String] }}
findInvalidNodes(edges)
assert findInvalidNodes(edges) == [2, 3, ..., 103] 

all nodes are recognized as invalid.

This also implies that the order of the entries in edges affects which nodes appear in the invalidNodes list:

Map<String, String> edges = [:]
edges["53"] = "51"
edges.putAll( (1..51).collectEntries { [it+1 as String, it as String] } )
assert findInvalidNodes(edges) == [2, 3, ..., 50, 51, 53]

Map<String, String> edges = [:]
edges.putAll( (1..51).collectEntries { [it+1 as String, it as String] } )
edges["53"] = "51"
assert findInvalidNodes(edges) == [2, 3, ..., 50, 51, 52]

Final words

Having said all this, for me as a non graph theory expert the task you are conducting - despite sounding so easy - is far from being trivial. So I would probably wind up with a lot of bugs in my code. But if I had to, I would rebuild the tree in a custom tree structure so that I can traverse the tree starting from the root. That is very flexible, but has great overhead compared to a simple HashMap.

EDIT

I thought it would only be fair to give a solution (that might contain bugs). This uses a HashMap as a tree representation, but with parent as key and a list of children as value. I wasn't sure if you really wanted a height limit of 51 or just 50 so this should be adjusted to your requirements.

List findInvalidNodesUsingMap(Map edges) {
    /*
    convert tree representation
    from child -> parent
    to parent -> children
    */
    Map tree = edges.groupBy { child, parent -> parent }
            .collectEntries { parent, Map children -> [parent, children.keySet()] }

    // nodes without parents must be roots
    Set roots = edges.values().findAll { !(it in edges.keySet()) }

    /*
    since all nodes can have at most one parent,
    all paths with cycles cannot have a root node.
    therefore, all nodes that cannot be accessed starting
    from one of the root nodes must be part of a path
    containing a cycle
    */

    Set validRoots = roots.findAll { heightBelowLimit(it, 1, tree) }

    Set validNodes = []
    validRoots.each { collectNodes(it, tree, validNodes) }

    Set invalidNodes = (roots + edges.keySet()).findAll { !(it in validNodes) }
    return invalidNodes as List
}

Boolean heightBelowLimit(String node, int level, Map tree){
    if(level > 50){
        false
    }else {
        !tree.containsKey(node)
                ? true
                : tree[node].every { heightBelowLimit(it, level + 1, tree) }
    }
}

void collectNodes(String node, Map tree, Set nodes){
    nodes << node
    if(tree.containsKey(node)){
        tree[node].each { collectNodes(it, tree, nodes) }
    }
}