1

I'm writing a Graph, and decided to make the Adjacency List its own class.

Right now, (stripped down) it looks like this:

public class AdjacencyList<Vertex> {

    //A map between a vertex, and a list of vertices that it connects to.
    private HashMap<Vertex, HashSet<Vertex>> vertices =
        new HashMap<Vertex, HashSet<Vertex>>();

    //Adds a new vertex, and gives it a list of outgoing vertices.
    public void addVertex(Vertex v, List<Vertex> outgoing) {
        vertices.put(v, new HashSet<Vertex>(outgoing));
    }

    //Adds a directed (one-way) edge to the given vertex.
    public void addDirectedToVertex(Vertex v, Vertex newVertex) {
        HashSet<Vertex> outgoingList = vertices.get(v);
        if (outgoingList != null) {
            outgoingList.add(newVertex);

        } else {
            throw new NoSuchElementException("Vertex " + v + " doesn't exist.");
        }
    }

}

Which was fine, until I realized that it's possible to add a vertex to a vertex's outgoing list that doesn't have its own spot in the hash map. This could lead to someone adding a vertex to another vertex's outgoing list that doesn't otherwise exist anywhere; which I'm sure would cause problems down the road.

To fix it, I thought of adding a check to the top before the addition. If the vertex to be added to the list doesn't exist in the HashMap, I could either throw, or give it its own entry. Something like this:

//Adds a directed (one-way) edge to the given vertex.
public void addDirectedToVertex(Vertex v, Vertex newVertex) {
    if (!vertices.containsKey(newVertex)) {
        addVertex(newVertex);
    }

    HashSet<Vertex> outgoingList = vertices.get(v);
    if (outgoingList != null) {
        outgoingList.add(newVertex);

    } else {
        throw new NoSuchElementException("Vertex " + v + " doesn't exist.");
    }
}

Unfortunately, that means that every addition will require 2 lookups, which seems unnecessarily complicated.

Is this something I should be concerning myself about, or would this be considered pre-mature optimization?

If this is a legitimate problem, can any-one see a way to reconfigure things to improve it?

  • 1
    I've significantly fixed the terminology (using "Source" and "Target"), but it doesn't affect the question. I'm not sure if I should update it now. – Carcigenicate Jul 4 '15 at 23:37
3

Checking whether an element exists in a hash map is fairly cheap. Hash maps give fast lookups; it's what they do. I wouldn't worry about it, especially if you aren't actively encountering bad performance. The value of having good, resilient, failfast code is better than having code that might be trivially faster but makes it easier to introduce bugs.

One thing to consider is Amdahl's law. It doesn't make a lot of sense to worry about the insertion performance of your graph, when the computational cost of most algorithms working on your graph (because there's no point in having a graph if you're not going to do anything with it) will be orders of magnitude more expensive than putting things into the graph.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.