Problem
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 queuetempDependeciesQueue
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;
}
}
Solution
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();
}
}
}
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();
}