Avoiding duplicate entries in an array

Question

I am writing a method that adds Vertex objects to an array. I need to check if the vertex I am adding already exists in the array. I am not sure where I am going wrong. Here is my method:

public void addVertex(Vertex v) {
    if (activeVertices >= maxVertices) {
        System.out.println("Graph full");
        return;
    }
    for(int i=1; i<vertices.length; i++) {
        if(vertices[i] != vertices[i-1]){
            vertices[activeVertices] = v; // add vertex to list of vertices
            v.graphIndex = activeVertices; // record index of vertex in graph
            activeVertices++;  // increment vertex count
        }
    }
}

Vertex class:

public class Vertex {
    public String name;
    public int graphIndex; // index of adjacency matrix position of node in graph

    public Vertex (String s) {
        name = s;
        graphIndex = -1; // invalid position by default 
    }

    public String toString() {
        return name;
    }

}

The class that contains the addVertex() method:

public class Graph {
    private int maxVertices;
    private Vertex[] vertices; // array of nodes
    private int[][] edges; // adjacency matrix
    int activeVertices;


    public Graph(int maxSize) {
        maxVertices = maxSize;
        vertices = new Vertex[maxVertices];
        activeVertices = 0;
    }


    public void addVertex(Vertex v) {
        if (activeVertices >= maxVertices) {
            System.out.println("Graph full");
            return;
        }
        for(int i=1; i<vertices.length; i++) {
            if(vertices[i] != vertices[i-1]){
                vertices[activeVertices] = v; // add vertex to list of vertices
                v.graphIndex = activeVertices; // record index of vertex in graph
                activeVertices++;  // increment vertex count
            }
        }
    }
    public void addEdge(Vertex v1, Vertex v2, int w) {
        edges[v1.graphIndex][v2.graphIndex] = w;
        edges[v2.graphIndex][v1.graphIndex] = w;
    }

    public Graph minimumSpanningTree() {
        Graph mst = new Graph(maxVertices); // create new graph
        int[] set = new int[activeVertices];
        for (int i=0; i<activeVertices; i++) { // copy nodes to graph
            mst.addVertex(vertices[i]);
            set[i]=i; // assign each node to its own set
        }
        PriorityQueue q = new PriorityQueue(maxVertices*maxVertices); // create priority queue
        for (int i=0; i<activeVertices; i++) { // copy edges to queue
            for (int j=0; j<activeVertices; j++) { 
                if (edges[i][j]!=0) {
                    q.enqueue(new Edge(vertices[i],vertices[j],edges[i][j]));
                }
            }
        }

        while (!q.isEmpty()) { // iterate over all edges in priority order
            Edge e = q.dequeue(); // consider next edge
            if (set[e.source.graphIndex]!=set[e.destination.graphIndex]) { // skip edges not connecting different sets
                mst.addEdge(e.source, e.destination, e.weight); // add edge to MST
                System.out.println("adding "+e);
                int setToMerge=set[e.destination.graphIndex]; // rename nodes from "other" set
                for (int i=0; i<activeVertices; i++) {
                    if (set[i]==setToMerge) { // find nodes from "other" set
                        set[i]=set[e.source.graphIndex]; // reassign nodes
                    }
                }
            }
        }
        return mst;
    }

    public void print() {
        System.out.format("    ");
        for (int i=0; i<activeVertices; i++) {
            System.out.format("%3s ", vertices[i].name);
        }
        System.out.format("\n");
        for (int j=0; j<activeVertices; j++) {
            System.out.format("%3s ", vertices[j].name);
            for (int i=0; i<activeVertices; i++) {
                System.out.format("%3d ", edges[i][j]);
            }
            System.out.format("\n");
        }
    }
}

Answer 1

Whenever you write a value class, i.e. a class that represents a value or quantity of something, you should always override the following methods for your class:

• equals(Object o);
• hashCode();

Not all classes are value classes. Some represent system resources and others represent actions or processes, but whenever a class is written as an abstraction for a collection of data you should always consider writing the above methods.

The reason is straightforward. Whereas Java primitives have only value, Java reference types (which include all the instances of classes you write yourself) have both value and location. This confers the properties of both equality and identity to reference types and they are very different.

By default, the equals() method in the Object class performs an identity comparison and NOT an equality comparison ... and it's a good thing too. Because any subclass of Object can have vastly different notions of "how instances can be considered equal" there is no straightforward way that Object could have a superclass method that would test equality for any arbitrary Java object. In contrast, it is always straightforward to test for identity. If any two references indicate the same location, then their objects are identical. This exemplifies the different notions of equality and identity.

You need to be able to test whether your Vertex instances are equal and not whether they are identical. For this reason, you really do need to override the equals(Object o) method. If you also override hashCode() (which you should), then you may be able to store your vertices in a HashSet, which would guarantee that no two vertices would be equal.

Answer 2

First, you should be using equals instead of ==. You should write a proper equals method in your Vertex class (use Google to find plenty of tutorials on how to do this).

For example, if you wanted two Vertex objects to be considered equal only when their names were the same, then your equals method would look something like this:

public boolean equals(Object obj) {
    if(obj == null) {
        return false;
    }

    if(obj instanceof Vertex) {
        Vertex otherVertex = (Vertex) obj;
        if(this.name.equals(otherVertex.name)) {
            return true;
        }
    }
    return false;
}

If you wanted to compare graphIndex as well, then you would need to check that in the equals method as well.

Assuming you have a proper equals method in your Vertex class, the simplest solution would be to use the ArrayUtils.contains method, from the Apache Commons library (Apache Commons has TONS of useful methods, which can save you a lot of time. You should check it out). This method takes in an array and an Object, and checks if the array contains the object or not.

Answer 3

You're always checking vertices[1] against vertices[0] and adding based on the result. You're not checking for v, and not actually looking in the whole array.

If an == check (identity, not equivalence) is really what you want, then:

public void addVertex(Vertex v) {
    if (activeVertices >= maxVertices) {
        System.out.println("Graph full");
        return;
    }
    for(int i=0; i<vertices.length; i++) {
        if(vertices[i] == v){
            // Already have it
            return;
        }
    }
    vertices[activeVertices] = v; // add vertex to list of vertices
    v.graphIndex = activeVertices; // record index of vertex in graph
    activeVertices++;  // increment vertex count
}

If you want equivalence instead, replace

if(vertices[i] == v){

with

if(v.equals(vertices[i])){

---

Side note: Based on your having an activeVertices variable, I suspect you may be better off with ArrayList<Vertex> rather than Vertex[]. That would also give you the contains method (which uses equals), which may be able to replace your loop (if you want an equals, not ==, check).