4
\$\begingroup\$

I do not want to use a new data structure but the existing APIs in Java. Here's a solution. I am thinking if this can be made simpler. Input say {"1 2", "4 3", "5 5", "2 3"} and output is [1, 2, 3, 4] [5]

    static void formSet(String[] pairs) {

    List<Set<Integer>> list = new ArrayList<>();
    for(String s : pairs){
        String[] values = s.split(" ");
        Integer val1 = Integer.parseInt(values[0]);
        Integer val2 = Integer.parseInt(values[1]);

        Set<Integer> pairSet = new HashSet<>();
        pairSet.add(val1);
        pairSet.add(val2);

        Set<Integer> val1_set = null, val2_set = null;
        for(Set<Integer> set : list){
            if(set.contains(val1)) {
                val1_set = set;
            }

            if(set.contains(val2)) {
                val2_set = set;
            }
        }
        if(val1_set == null && val2_set == null)
            list.add(pairSet);
        if(val1_set != null && val2_set == null)
            val1_set.addAll(pairSet);
        if(val1_set == null && val2_set != null)
            val2_set.addAll(pairSet);
        if(val1_set != null && val2_set != null){
            list.remove(val2_set);
            val1_set.addAll(val2_set);
        }
    }

    for(Set<Integer> set : list){
        System.out.println(set);
    }
}
\$\endgroup\$
  • \$\begingroup\$ The approach you took could probably be improved (by sacrificing some memory) by having a map from Integer to Set that it belongs to, so you can remove the for(Set<Integer> set : list) cycle. Alternative approach would be having a map from Integer to collection of Integers that it directly connects to, and then traverse recursively and collect into List of Sets (I'll see if I can come up with some code). \$\endgroup\$ – Coderino Javarino May 14 '17 at 10:17
  • \$\begingroup\$ Can you please explain why that would be the output? Why two sets? Why their respective contents? \$\endgroup\$ – Marvin May 14 '17 at 10:21
  • 2
    \$\begingroup\$ @Marvin he has a disconnected graph. Given the edges, he wants to build list of sets of nodes, that have a path between them. \$\endgroup\$ – Coderino Javarino May 14 '17 at 10:24
1
\$\begingroup\$

First and foremost : your code contains a subtle bug. Try this input : {"1 2", "4 3", "5 5", "2 3", "1 3"}

As for style;

  • please respect standard naming conventions.
  • seperate concerns : parsing the string into a pair should be done in a separate method, this will improve readability.
  • it's unclear from just looking at your code what the algorithm does exactly. Try finding a better name for the method and certain variables. If that's insufficient, some documentation can also help.
  • probably this is an exercise, as your algorithm simply prints its result, rather than return it. But generally such methods are useless, plus it mingles concerns again. Make the method return its result, and make a client method print the result. The main method would then call three methods



List<Set<Integer>> pairs = parse(input);
List<Set<Integer>> clusters = calculateClusters(pairs);
print(clusters);
\$\endgroup\$
  • \$\begingroup\$ Thank you for your inputs. I am aware of putting the entire thing one method and this is just a quickly typed code for posting here. My question is can you simplify the code (not necessarily efficient). The problem statement is given and I am looking for the simplest approach using the existing java APIs to solve it. Thank you for point out the bug. \$\endgroup\$ – Subhomoy Sikdar May 18 '17 at 8:51
0
\$\begingroup\$

Your implementation is good. One thing I would change, I would add else before all but first if where you are comparing val_set against null, as e.g. if val1_set == null && val2_set == null, it wouldn't go to the next check of val1_set != null && val2_set == null, but skip to next loop.

if (...)
    ...
else if (...)
    ...

Alternative approach to the problem could be storing the edges you are given, and only after going through all input, traverse those edges and collect nodes that have a path between into sets. Is the solution simpler however? I don't know, probably not.

void makesets(String[] pairs) {
        //edges of the graph
        Map<Integer, Set<Integer>> connections = new HashMap<>();
        for (String pair : pairs) {
            Integer nr[] = Arrays.stream(pair.split(" "))
                .map(s -> Integer.parseInt(s))
                .toArray(Integer[]::new);
            for (int i = 0; i < 2; i++) {
                if (connections.get(nr[i]) == null)
                    connections.put(nr[i], new HashSet<>());
                connections.get(nr[i]).add(nr[1 - i]);
            }
        }
        Set<Integer> traversed = new HashSet<>();
        List<Set<Integer>> list = new ArrayList<>();
        for (Integer node : connections.keySet()) {
            if (traversed.contains(node)) continue;
            Set<Integer> set = new HashSet<>();
            collectSet(node, connections, set);
            list.add(set);
            traversed.addAll(set);
        }
        for(Set<Integer> set : list){
            System.out.println(set);
        }
    }

    void collectSet(Integer node, Map<Integer, Set<Integer>> connections, Set<Integer> collected){
        if (collected.add(node)) {
            connections.get(node).forEach(n -> collectSet(n, connections, collected));
        }
    }
\$\endgroup\$

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.