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?