class Step6GraphTransitivityCleaner {

    public static Set<Set<String>> mergeClusters(Set<Set<String>> equalClusters)
    {
        // create a new undirected graph
        Graph graph = new DefaultGraph("CC Test");
        graph.setAutoCreate(true);
        graph.setStrict(false);

        // add all "edges"; for each pair from each cluster
        for (Set<String> cluster : equalClusters) {
            List<String> clusterList = new ArrayList<>(cluster);

            for (int i = 0; i < clusterList.size(); i++) {
                for (int j = i + 1; j < clusterList.size(); j++) {
                    // edge name
                    String iName = clusterList.get(i);
                    String jName = clusterList.get(j);

                    List<String> names = Arrays.asList(iName, jName);
                    Collections.sort(names);
                    String edgeName = StringUtils.join(names, "_");

                    graph.addEdge(edgeName, iName, jName);
                }
            }
        }

        // compute connected components
        ConnectedComponents cc = new ConnectedComponents();
        cc.init(graph);

        Set<Set<String>> result = new HashSet<>();

        cc.setCountAttribute("cluster");
        cc.compute();

        //        System.out.println(cc.getConnectedComponentsCount());

        // re-create clusters from all connected components
        for (ConnectedComponents.ConnectedComponent component : cc) {
            Set<String> cluster = new HashSet<>();
            for (Node n : component) {
                cluster.add(n.getId());
            }
            result.add(cluster);
        }

        //        System.out.println(result);

        return result;
    }

}

class Step6GraphTransitivityCleanerTest {

    @Test
    public void testMergeClusters()
            throws Exception
    {

        Set<Set<String>> c1 = new HashSet<>();
        c1.add(new HashSet<>(Arrays.asList("1", "2")));
        c1.add(new HashSet<>(Arrays.asList("3", "4")));
        Set<Set<String>> merged1 = Step6GraphTransitivityCleaner.mergeClusters(c1);
        assertEquals(2, merged1.size());

        Set<Set<String>> c2 = new HashSet<>();
        c2.add(new HashSet<>(Arrays.asList("1", "2")));
        c2.add(new HashSet<>(Arrays.asList("3", "4")));
        c2.add(new HashSet<>(Arrays.asList("5", "4")));

        Set<Set<String>> merged2 = Step6GraphTransitivityCleaner.mergeClusters(c2);
        assertEquals(2, merged2.size());

        Set<Set<String>> c3 = new HashSet<>();
        c3.add(new HashSet<>(Arrays.asList("1", "5")));
        c3.add(new HashSet<>(Arrays.asList("3", "4")));
        c3.add(new HashSet<>(Arrays.asList("5", "4")));

        Set<Set<String>> merged3 = Step6GraphTransitivityCleaner.mergeClusters(c3);
        assertEquals(1, merged3.size());
    }

}