Best way to update set of set

There is a list of edges connecting the vertices. I'm trying to divide these vertices into groups that are connected to each other.

static class Edge {
final String from, to;
Edge(String from, String to) {
this.from = from;
this.to = to;
}
}
static Set<String> find(String k, Set<Set<String>> sets) {
for (Set<String> set : sets)
if (set.contains(k))
return set;
return null;
}
static Set<Set<String>> connectedVertices(List<Edge> edges) {
Set<Set<String>> result = new HashSet<>();
for (Edge e : edges) {
Set<String> from = find(e.from, result);
Set<String> to = find(e.to, result);
if (from == null && to == null) {
result.add(new HashSet<>(Set.of(e.from, e.to)));
} else if (from == null) {
to.add(e.from);
} else if (to == null) {
from.add(e.to);
} else if (from != to) {
result.remove(to);
from.addAll(to);
}
}
return result;
}

And

    List<Edge> edges = List.of(
new Edge("a", "b"),
new Edge("c", "b"),
new Edge("c", "d"),
new Edge("a", "c"),
new Edge("e", "f"),
new Edge("x", "y"),
new Edge("y", "d"));
System.out.println(connectedVertices(edges));

But the result is not what I expected.

Expected:

[[e, f], [a, b, c, d, x, y]]

Actual:

[[a, b, c, d, x, y], [a, b, c, d], [e, f]]

I get the results I expect with the following changes, but it's verbose. Is there a better way?

static Set<Set<String>> connectedVertices(List<Edge> edges) {
Set<Set<String>> result = new HashSet<>();
for (Edge e : edges) {
Set<String> from = find(e.from, result);
Set<String> to = find(e.to, result);
if (from == null && to == null) {
result.add(new HashSet<>(Set.of(e.from, e.to)));
} else if (from == null) {
result.remove(to);
to.add(e.from);
result.add(to);
} else if (to == null) {
result.remove(from);
from.add(e.to);
result.add(from);
} else if (from != to) {
result.remove(from);
result.remove(to);
from.addAll(to);
result.add(from);
}
}
return result;
}

The problem is that the elements of a hash set should not be mutable, but here you are changing the inner sets of the outer set, which changes their hash codes. The changed hash code causes the result.remove call to fail to remove to.

remove tries to look for to with the new hash code, but to is stored in a different bucket, because when it was added, its hash code is different.

From the docs:

> Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

I would just use a list of sets, rather than a set of sets. The only operation that you are doing, that sets are really good at, is remove. Using a list would turn remove into an O(n) operation. But since the algorithm overall has a way higher complexity than that, an extra O(n) operation is not going to matter in the long term. I would consider whether the condition else if (from != to) is hit very often, and whether your approach of "keep on removing, changing, then adding back in" is actually faster for small inputs using a benchmark.

static Set<String> find(String k, List<Set<String>> sets) {
for (Set<String> set : sets)
if (set.contains(k))
return set;
return null;
}
static List<Set<String>> connectedVertices(List<Edge> edges) {
List<Set<String>> result = new ArrayList<>();
for (Edge e : edges) {
Set<String> from = find(e.from, result);
Set<String> to = find(e.to, result);
if (from == null && to == null)
result.add(new HashSet<>(Set.of(e.from, e.to)));
else if (from == null) {
to.add(e.from);
} else if (to == null) {
from.add(e.to);
} else if (from != to) {
result.remove(to);
from.addAll(to);
}
}
return result;
}

If you would like a set as a result, you could always do

new HashSet(connectedVertices(edges))