# How can I avoid needing to check for the existence another vertex when adding to an adjacency list?

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) {

} 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)) {
}

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

} 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?

• 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