2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
2
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$
0
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ And this way it's better because...? \$\endgroup\$ – janos Dec 12 '16 at 19:30
  • \$\begingroup\$ it's shorter of course, what else! \$\endgroup\$ – ciroBorrelli Dec 13 '16 at 22:41
  • \$\begingroup\$ moreover, can be tested with strings longer than 1-char. See my tests here: link \$\endgroup\$ – ciroBorrelli Dec 13 '16 at 22:43
  • \$\begingroup\$ 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 \$\endgroup\$ – janos Dec 14 '16 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.