Transform map with multiple values to tree?

Answer 1

When you talk about transforming them into a set of trees, are you talking about the method of representing them in memory?

Or perhaps the algorithm by which we would walk your set of keys and values and put them into that in-memory representation?

Or are you talking about a graphical representation?

Answer 2

I'm not aware of any library methods that will do this transformation. Here's how I'd do it. It's pretty straightforward, IMO.

public class Tree {
    public Tree(String key) {
        // ...
    }
    public void addChild(Tree child) {
        // ...
    }
}

public Set<Tree> transform(Map<String, List<String>> input) {
    // Potential tree roots.  We start with all LHS keys as potential roots,
    // and eliminate them when we see their keys on the RHS.
    Set<String> roots = new HashSet<String>(input.keySet());

    // This map associates keys with the tree nodes that we create for them
    Map<String, Tree> map = new HashMap<String, Tree>();

    for (Map.Entry<String, List<String>> entry : input.entrySet()) {
        String key = entry.getKey();
        List<String> childKeys = entry.getValue();
        Tree tree = map.get(key);
        if (tree == null) {
            tree = new Tree(key);
            map.put(key, tree);
        }
        for (String childKey : childKeys) {
            roots.remove(childKey);
            Tree child = map.get(childKey);
            if (child == null) {
                child = new Tree(childKey);
                map.put(childKey, child);
            }
            tree.addChild(child);
        }
    }
    Set<Tree> res = new HashSet<Tree>(roots.size());
    for (String key : roots) {
        res.add(map.get(key));
    }
    return res;
}

EDIT: Note this algorithm will "work" if the input represents a set of DAGs (Directed Acyclic Graphs). However, I've just realized that the resulting a set of trees will share TreeNode instances for any common subtrees in the input data.

Beware that I haven't debugged this code :-)