Finding Transitive Dependencies, Code Kata 18

Posted on


I have coded for the problem Code Kata 18. Provided the input dependencies, I need to come up with all the transitive dependencies. While working, I encountered various problems like Data Structure Solution, ConcurrentModificationExceptions and others.

  • Used HashMap of String,HashSet to represent a class along with dependencies (inputDependencies,transitiveDependencies). Used HashMap because the lookup for the dependencies needs to be fast.
  • Used a Queue (dependeciesQueue) to store the present dependencies, later iterated over this queue. But I was unable to insert/remove in the same queue due to Java’s Concurrent Modification exception. So I have used another temporary queue tempDependeciesQueue

I came up with this code by mapping this problem to BFS on a graph. Please help me with these queries.

  • I still find my code little unreadable, can I make it elegant.
  • Is my choice of Data Structures correct for having better performance?
  • Is this approach okay?
  • If there is a cyclic dependency, the program will get stuck in an infinite loop. One way I can avoid is to mark already used dependencies similar to visited vertices in BFS. Can I avoid this issue in any other way?

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;

public class CodeKata18_Dependencies {  
    Map<String, HashSet<String>> inputDependencies = new HashMap<String,HashSet<String>>();

    public static void main(String args[]) {
        CodeKata18_Dependencies codeKata = new CodeKata18_Dependencies();
        codeKata.addDirectDependency("A B C");
        codeKata.addDirectDependency("B C E");
        codeKata.addDirectDependency("C G");
        codeKata.addDirectDependency("D A F");
        codeKata.addDirectDependency("E F");
        codeKata.addDirectDependency("F H");

    public boolean addDirectDependency(String rawDependency) {
        String[] rawDepenenciesBreak = rawDependency.split(" ");
        String key = rawDepenenciesBreak[0];
        HashSet<String> dependencies = new HashSet<String>();
        for (int i = 1; i < rawDepenenciesBreak.length; i++) {
        return inputDependencies.put(key, dependencies) != null;

    public Map<String, HashSet<String>> getDependencies() {
        Map<String, HashSet<String>> transitiveDependencies = new HashMap<String, HashSet<String>>();
        // Iterate though the provided input dependencies..
        for (Entry<String, HashSet<String>> entry : inputDependencies.entrySet()) {
            String key = entry.getKey();
            Set<String> dependenciesForKey = entry.getValue();
            Queue<String> dependeciesQueue = new LinkedList<String>();
            if (dependenciesForKey != null) {
                for (String s : dependenciesForKey) {
            // Used to store all the dependencies till now..
            HashSet<String> allDependencies = new HashSet<String>();
            // As concurrent modifications is not allowed, a temp queue is
            // maintained
            Queue<String> tempDependeciesQueue = new LinkedList<String>();
            // If dependenciesQues is not empty, all all the values in the
            // queues to allDependencies
            // and add all the dependencies of these to tempDependeciesQueue
            while (!dependeciesQueue.isEmpty()) {
                for (String d : dependeciesQueue) {
                    if (inputDependencies.get(d) != null) {
                        for (String s : inputDependencies.get(d)) {
                // Replace dependeciesQueue with tempDependeciesQueue and Make
                // tempDependeciesQueue new list.
                dependeciesQueue = tempDependeciesQueue;
                tempDependeciesQueue = new LinkedList<String>();
            // Put the dependencies obtained in the final list.
            transitiveDependencies.put(key, allDependencies);
        return transitiveDependencies;


I think it becomes easier if you code the dependencies as a graph, consisting of Nodes that might have children.

You can prevent adding a child if it creates a cycle.

For quick access to all the nodes I store them in a Map.

Note that this implementation is not thread safe.

import java.util.*;

public class Kata18 {

    private class CyclicDependencyException extends Throwable {

    //I implement Comparable because I want a nice sorted list when printing.
    class Node implements Comparable<Node> {
        Set<Node> children = new HashSet<Node>();
        String name;

        public Node(String name) {
   = name;

        public boolean addChild(Node n) {
            //if we add a child, all the children of the that node cannot be this node, otherwise we create a cycle.
            if (n.allDescendants().contains(this))
                return false;
                return true;

        public Set<Node> allDescendants() {
            Set<Node> all = new TreeSet<>();

            for (Node c : children) {
            return all;

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return name != null ? name.equals( : == null;


        public int hashCode() {
            return name != null ? name.hashCode() : 0;

        public String toString() {
            return name + " depends transitively on " + allDescendants().stream().map(x ->","));

        public int compareTo(Node o) {
            return name.compareTo(;

    private Map<String, Node> nodesMap = new HashMap<String, Node>();

    private void print() {
        for (String name : nodesMap.keySet()) {

     * Get a node from the Map if it already exists, else create it and put it in the map.
    public Node getOrCreateNode(String nodeName) {
        Node currentNode;
        if (!nodesMap.containsKey(nodeName)) {
            currentNode = new Node(nodeName)
            nodesMap.put(nodeName, currentNode);
        } else {
            currentNode = nodesMap.get(nodeName);
        return currentNode;

    public boolean tryDirectDependency(String rawDependency) throws CyclicDependencyException {
        String[] elements = rawDependency.split(" ");

        String nodeName = elements[0];

        Node node = getOrCreateNode(nodeName);

        for (int i = 1; i < elements.length; i++) {
            if (!node.addChild(getOrCreateNode(elements[i]))) {
                throw new CyclicDependencyException();
        return true;

    public static void main(String args[]) {

        try {
            Kata18 codeKata = new Kata18();
            codeKata.tryDirectDependency("A B C");
            codeKata.tryDirectDependency("B C E");
            codeKata.tryDirectDependency("C G");
            codeKata.tryDirectDependency("D A F");
            codeKata.tryDirectDependency("E F");
            codeKata.tryDirectDependency("F H");

        } catch (CyclicDependencyException e) {

        try {
            Kata18 codeKata2 = new Kata18();
            codeKata2.tryDirectDependency("A B");
            codeKata2.tryDirectDependency("B A");
        } catch (CyclicDependencyException e) {

I agree with RobAu but I do not use a new (Node) class to build the graph.
I use a java Map instead. Code is shorter and execution time a little bit faster (due to Java optmizations)

Moreover, I modified a little the Code Kata 18 implementation in order to accept String(s) in input, not only char(s). See the test below

Here is the Java code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Dependencies {

    private Map<String, String[]> _map;

    public Dependencies() {
        _map = new HashMap<String, String[]>();

    public void add_direct(String item, String... deps) {
        for (String dep : deps) {
            //check for dep's circularities/loops before mapping
            if (!checkDependent(dep, item) ) _map.put(item, deps);

    private boolean checkDependent(String dep, String item) {
        boolean isDependent = false;
        String[] deps = dependencies_for(dep);

        for (String e : deps) {
            isDependent  = (e.equals(item)) ? true : false;
        return isDependent;

    private List<String> _res = new ArrayList<String>();
    public String[] dependencies_for(String key) {
        String[] deps = _map.get(key);
        if(deps == null) return getSorted(); //guard clause

        for (String dep : deps) recourse_for(dep);

        return getSorted();

    private void recourse_for(String key) {
        if(! _res.contains(key)) _res.add(key);

        String[] deps = _map.get(key);
        if(deps==null) return; //guard clause

        for (String dep : deps) recourse_for(dep);

    private String[] getSorted() {
        String[] toBeSorted = _res.toArray(new String[0]) ; 
        _res = new ArrayList<String>();
        return toBeSorted;

    public void printAll() {
        for (String key : _map.keySet()) {
            String[] deps = dependencies_for(key);
                + " depends on: "
                + Arrays.toString(deps)

    public String toString() {
        String[] collection = new String[_map.size()];
        int i = 0;
        for (String key : _map.keySet()) {
            String[] deps = dependencies_for(key);
            collection[i++] = key + " depends on: "
                + Arrays.toString(deps);

        return Arrays.toString(collection);

    public boolean equals(Object other) {
        if (other == null) return false;
        if (other == this) return true;
        if (!(other instanceof Dependencies))return false;
        if (this.toString().trim().toLowerCase() 
            .equals(other.toString().trim().toLowerCase()) ) return true;
        return false;

And here is a JUnit tests:

    public final void testMyFamilyDependency() {
        _dep.add_direct("CIRO", new String[] { "PINA", "SOLDI" } );
        _dep.add_direct("PINA", new String[] { "SOLDI" } );
        _dep.add_direct("ENRI", new String[] { "CIRO", "PINA", "SOLDI" } );
        _dep.add_direct("LALA", new String[] { "PINA", "SOLDI" } );

        assertArrayEquals( new String[] { "PINA", "SOLDI" }, _dep.dependencies_for("LALA") );
        assertArrayEquals( new String[] { "CIRO", "PINA", "SOLDI" }, _dep.dependencies_for("ENRI") );
        assertArrayEquals( new String[] { "PINA", "SOLDI" }, _dep.dependencies_for("CIRO") );


Leave a Reply

Your email address will not be published. Required fields are marked *