Finding Transitive Dependencies, Code Kata 18

Question

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");
 System.out.println(codeKata.getDependencies());
 }
 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++) {
 dependencies.add(rawDepenenciesBreak[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) {
 dependeciesQueue.add(s);
 }
 }
 // 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) {
 allDependencies.add(d);
 if (inputDependencies.get(d) != null) {
 for (String s : inputDependencies.get(d)) {
 tempDependeciesQueue.add(s);
 }
 }
 }
 // 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;
 }
}

Answer 1

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.*;
import java.util.stream.Collectors;
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) {
 this.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;
 }
 else
 {
 this.children.add(n);
 return true;
 }
 }
 public Set<Node> allDescendants() {
 Set<Node> all = new TreeSet<>();
 for (Node c : children) {
 all.add(c);
 all.addAll(c.allDescendants());
 }
 return all;
 }
 @Override
 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(node.name) : node.name == null;
 }
 @Override
 public int hashCode() {
 return name != null ? name.hashCode() : 0;
 }
 @Override
 public String toString() {
 return name + " depends transitively on " + allDescendants().stream().map(x -> x.name).collect(Collectors.joining(","));
 }
 @Override
 public int compareTo(Node o) {
 return name.compareTo(o.name);
 }
 }
 private Map<String, Node> nodesMap = new HashMap<String, Node>();
 private void print() {
 for (String name : nodesMap.keySet()) {
 System.out.println(nodesMap.get(name).toString());
 }
 }
 /**
 * 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");
 codeKata.print();
 } catch (CyclicDependencyException e) {
 e.printStackTrace();
 }
 try {
 Kata18 codeKata2 = new Kata18();
 codeKata2.tryDirectDependency("A B");
 codeKata2.tryDirectDependency("B A");
 codeKata2.print();
 } catch (CyclicDependencyException e) {
 e.printStackTrace();
 }
 }
}

• Anuruddha Lanka Liyanarachchi: How can I make this thread safe?

Answer 2

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);
 }
 }
 //NEEDED TO CHECK CIRCULARITIES IN DEPENDENCIES
 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>();
 Arrays.sort(toBeSorted);
 return toBeSorted;
 }
 public void printAll() {
 for (String key : _map.keySet()) {
 String[] deps = dependencies_for(key);
 System.out.println(key
 + " depends on: "
 + Arrays.toString(deps)
 );
 }
 }
 @Override
 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);
 }
 @Override
 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:

@Test
 public final void testMyFamilyDependency() {
 //input
 _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" } );
 //output
 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") );
 //console 
 _dep.printAll();
}

• janos: And this way it's better because...?
• ciroBorrelli: it's shorter of course, what else!
• ciroBorrelli: moreover, can be tested with strings longer than 1-char. See my tests here: link
• janos: This would be a better answer if you included in it the explanations and tests you mentioned in comments. It will be also better to include the tests directly in the post rather than linking to it