Use equal vertex in a JGraphT SimpleGraph

Question

In Java, want to create a simple graph (a unweighted, undirected graph containing no graph loops or multiple edges) containing vertexes/edges that are equal.

I have two Java Classes, one for the vertexes:

 class Vertex {

    private int field;

    public Vertex(int field) {
        this.field = field;
    }

    @Override
    public boolean equals(Object obj) {

        if (obj.getClass().getPackage()
                .equals(this.getClass().getPackage())
                && obj.getClass().getName()
                        .equals(this.getClass().getName())) {

            Vertex vertex = (Vertex) obj;

            if (this.field == vertex.field)
                return true;
        }

        // Else
        return false;
    }

    @Override
    public int hashCode() {
        // No need for a perfect hash
        return this.field;
    }
}

And a class for the edges:

class Edge {

    private int field;

    public Edge(int field) {
        this.field = field;
    }

    @Override
    public boolean equals(Object obj) {

        if (obj.getClass().getPackage()
                .equals(this.getClass().getPackage())
                && obj.getClass().getName()
                        .equals(this.getClass().getName())) {

            Edge edge = (Edge) obj;

            if (this.field == edge.field)
                return true;
        }

        // Else
        return false;
    }

    @Override
    public int hashCode() {
        // No need for a perfect hash
        return this.field;
    }
}

I currently use the JGraphT library. But I ran into a IllegalArgumentException: "loops not allowed" after starting this code:

    // Define a EdgeFactory
    EdgeFactory<Vertex, Edge> BOND_FACTORY = new EdgeFactory<Vertex, Edge>() {
        @Override
        public Edge createEdge(Vertex sourceVertex, Vertex targetVertex) {
            return new Edge(2);
        }
    };
    // Create the graph
    SimpleGraph<Vertex, Edge> graph = new SimpleGraph<Vertex, Edge>(
            BOND_FACTORY);

    // Create vertexes
    Vertex v1 = new Vertex(1);
    Vertex v2 = new Vertex(1);

    // Add them to the graph
    graph.addVertex(v1);
    graph.addVertex(v2);
    graph.addEdge(v1, v2);

The problem is that i try to add v2 to the graph, but because v1.equals(v2) == true v2 is never added to the graph. From the JavaDoc of the lib:

Adds the specified vertex to this graph if not already present. More formally, adds the specified vertex, v, to this graph if this graph contains no vertex u such that u.equals(v).

This check is implemented here.

But then, how do I acomplish what I'm trying to do? Is there another implemention in this library that I could use for it, or is changing the equals() method a good idea?

Answer 1

It seems that for you, vertices v1 and v2 in the example are distinguishable. Then you must make sure that they're distinguishable for the graph as well. In other words, make sure that v1.equals(v2) returns false. You might want to consider adding a member variable "id" (or something) to Vertex, and base equals and hashcode on that variable. The contract of that member variable would be that two vertices having the same id are equal.

If you then create two vertices with the same field, but different ids, then v1.equals(v2) will be false, and the two Vertex objects represent different vertices in the graph. For example:

Vertex v1 = new Vertex("a", 1);
Vertex v2 = new Vertex("b", 1);

The constructor of Vertex would then have to look like:

public Vertex(String id, int field) {
  this.id = id;
  this.field = field;
}

Another solution would be to simply remove the hashcode and equals methods from Vertex, so that the inherited methods from Object are used, in which case two Vertex instances are equal if and only if they refer to the same object (i.e., memory address).

The same holds for the Edge class. I'm not really sure about how you intend to use the Edge's field property, but I'd simply remove it to avoid running into the same kind of problem.