CODEWITHSUNDEEP
javacollections
Setup
Setup

Reputation: 330

Looking for the right collection - bidirectional unique pairs

I need a collection in Java which represents the following data structure: If I get the following inputs I need to store them as described below:

A->B //should be stored

A->C //should be stored

A->B //should not be allowed (stored) anymore as it is in the collection already

B->A //should also not be allowed (stored) as A->B is in the collection already

C->B //should be stored

D->C //should be stored

I hope you get the idea.

I tried a HashMap<Set<String>, Set<String>> already but mutating keysets goes wrong, as described here: https://stackoverflow.com/a/2393748/2346207

Upvotes: 0

Views: 188

Answers (3)

rook
rook

Reputation: 6240

You could use java.util defaults only also, for example as set of sets:

HashSet<HashSet<String>> h = new HashSet<HashSet<String>>();

h.add(new HashSet<String>(Arrays.asList("A", "B")));
h.add(new HashSet<String>(Arrays.asList("B", "A"))); // will be ignored
h.add(new HashSet<String>(Arrays.asList("B", "C"))); // ok, new member

a bit wordy in Java for oneliners, but that works.

Upvotes: 1

Dmitry Ginzburg
Dmitry Ginzburg

Reputation: 7461

For example, let the Vertex be Comparable<Vertex>

As reto suggested, you should create Edge class with equals and hashCode overridden:

public class Edge {
    Vertex first, second;
    public Edge (Vertex first, Vertex second) {
        int order = first.compareTo(second);
        this.first = (order > 0) ? first : second;
        this.second = (order > 0) ? second : first;
    }
    @Override
    public boolean equals (Object o) {
        if (!(o instanceof Edge))
            return false;
        Edge other = (Edge)o;
        return other.first.equals(first) && other.second.equals(second);
    }
    @Override
    public int hashCode() {
        return first.hashCode() * 31 + second.hashCode();
    }
}

The ordering will be ignored by making first <= second always

Upvotes: 1

reto
reto

Reputation: 10463

A Set<Edge> where you define the type Edge with the appropriate equals and hashCode methods will work to store this information.

Your input A->B is represented in the class Edge. The class has two fields, lets call them source and destination. This wording would be in line with the arrows that you use (directed vs. undirected graph).

Tutorials like this one http://tutorials.jenkov.com/java-collections/hashcode-equals.html explain the basics of equals and hashCode. In your case it's important and an Edge A->B is considered equal to an Edge B->A (again, directions in the graph... A<->B)

Upvotes: 4

Related Questions