Graph Implementation in Java using adjacency list

Question

I am building a Graph class to learn and eventually plan to add Dijkstra's algorithm to this implementation. What do you think of the overall approach? Any feedback on how to improve this?

Vertex.java - contains all vertex information

public class Vertex {
    int key;
    String name;

    protected Vertex(String name, int key) {
        this.name = name;
        this.key = key;
    }

    protected int getKey() {
        return this.key;
    }

    protected void setKey(int key) {
        this.key = key;
    }

    protected String getName() {
        return this.name;
    }
}

Graph.java - edges are directed

public class MyGraph {
    HashMap<String, Vertex> vertexes = new HashMap<>();
    List<HashSet<Vertex>> adjList = new LinkedList<>();
    int index = 0;

    public void addVertex(String name) {
        if (!vertexes.containsKey(name)) {
            Vertex v = new Vertex(name, index);
            vertexes.put(name, v);
            index++;
            adjList.add(new HashSet<>());
        } else {
            System.out.println("Vertex " + name + " already exists in graph.");
        }
    }

    // v1 has directed edge towards v2
    public void addEdge(String name1, String name2) {
        // are both vertexes already in the graph?
        if (!vertexes.containsKey(name1) || !vertexes.containsKey(name2)) {
            System.out.println("Please enter vertexes that already exist in the graph.");
            return;
        }
        Vertex source = getVertex(name1);
        Vertex destination = getVertex(name2);

        // does edge already exist?
        int key = source.getKey();
        if (adjList.get(key).contains(destination)) {
            System.out.println("Edge from " + name1 + " to " + name2 + " already exists.");
            return;
        } else {
            adjList.get(key).add(destination);
        }
    }

    // removes all vertexes/edges from graph
    public void clear() {
        vertexes = new HashMap<>();
        adjList = new LinkedList<>();
        index = 0;
    }

    public HashSet<Vertex> getNeighbors(String name) {
        Vertex v = getVertex(name);
        Iterator iterator = adjList.get(v.getKey()).iterator();
        HashSet neighbors = new HashSet();
        while (iterator.hasNext()) {
            neighbors.add(iterator.next());
        }
        return neighbors;
    }

    private Vertex getVertex(String name) {
        return vertexes.get( name);
    }

    public boolean isEmpty() {
        return index == 0 && vertexes.isEmpty() && adjList.isEmpty();
    }

    public void removeEdge(String name1, String name2) {
        if (!containsVertex(name1) || !containsVertex(name2)) {
            System.out.println("Please check your inputs: at least one is invalid and dne in graph.");
            return;
        }
        Vertex v1 = getVertex(name1);
        Vertex v2 = getVertex(name2);
        adjList.get(v1.getKey()).remove(v2);
    }

    public void removeVertex(String name) {
        // before removing vertex
        // iterate over this.adjList
        //  1. remove all neighbors (hashset) from this.adjList
        //  2. need to remove all incoming edges from other vertexes
        //  3. update keys for all vertexes that come after one to be removed
        // 4. remove from HashMap this.vertices
        // 5. index--;
        if (!containsVertex(name)) {
            System.out.println("Vertex does not exist.");
            return;
        }
        Vertex v  = getVertex(name);
        int key = v.getKey();

        // remove vertex neighbors list from adjacency list
        adjList.remove(key);

        // remove references to vertex as a neighbor
        Iterator adjListIterator = adjList.iterator();
        while (adjListIterator.hasNext()) {
            HashSet neighborList = (HashSet) adjListIterator.next();
            if (neighborList.contains(v)) {
                neighborList.remove(v);
            }
        }

        // update keys for all vertexes that come after this
        if (key < size() - 1) {
            Iterator vertexIterator = vertexes.values().iterator();
            while (vertexIterator.hasNext()) {
                Vertex vertex = (Vertex) vertexIterator.next();
                int vertexKey = vertex.getKey();
                if (vertexKey > key) {
                    vertex.setKey(vertexKey-1);
                }
            }
        }
        vertexes.remove(name);
        index--;
    }

    // returns the number of vertexes
    public int size() {
        return vertexes.size();
    }

    public boolean containsVertex(String name) {
        Vertex v = getVertex(name);
        return (v != null && adjList.get(v.getKey()) != null);
    }
}

Answer 1

First of all, the field index in MyGraph is redundant, because it only stores the number of vertexes which is already reflected by the size of vertexes and adjList. Having a property stored multiple times makes code confusing and fragile, because a bug could cause the respective fields to contain contradictory vaules.

Also, I don't think key should be a field of Vertex, because the way you use it, it is not a property of a vertex, but only a value that's associated with a vertex by a graph, so while the field key makes sense in the context of a graph, it is meaningless when considering a vertex alone. Now, removing the field key from Vertex reduces Vertex to a useless wrapper class for a String, so you might as well scratch the vertex class and simply store the vertexes directly as Strings in MyGraph.

Now, about the purpose of Vertex.key. Theoretically, it represents the order in which the vertexes were added to the graph, but in your code, it only serves to associate the vertexes in MyGraph.vertex with the edges in MyGraph.adjList. Again, this makes the code fragile, because a bug could cause adjList to contain a set of edges at an index i that's not meant for the vertex with the key i. Instead, you could store the vertexes in a Map<String, Set<String>> (I'll just use String instead of Vertex as per my earlier suggestion), and if you want to preserve the order in which the vertexes were added to the graph, you can use a LinkedHashMap. That way, the relationship between vertexes and their neighbors is expressed directly by the code rather than an arbitrary correlation between an int field and the index in a list.

Next, your method getNeighbors(String) can be simplified. First of all, instead of creating an empty HashSet and then manually adding every element from a different HashSet, you could just invoke the constructor HashSet(Collection<? extends E>) instead of the no-argument-constructor (also, I suggest you avoid using raw types, because generics provide additional compile-time type-safety). Besides, there's an even better alternative: Collections.unmodifiableSet​(Set<? extends T>). The advantage of this method is that the returned Set will not be modifiable directly, but it will still reflect changes to the original map, so you might think of it not as a "copy", but rather as a "read-only access". In this case, you might want to rename the method to viewNeighbors (although I'm not sure whether this is really more descriptive or just a personal habit of mine).

Also, I see that you are using a LinkedList for adjList, even though you are mostly performing get operations on it, and ArrayList.get(int) is O(1) while LinkedList.get(int) is O(n) (where n is the list size). Only in removeVertex(String) do you remove an element from it, but keep in mind that, while deleting an element from a LinkedList per se is O(1), LinkedList.remove(int) first has to traverse the list to find the element, which is O(n), while ArrayList.remove(int) would find the element in O(1) and remove it in O(n). True, removing an element from an ArrayList can be slow for very large lists, slower than finding an element in a LinkedList, but unless you intend to create gigantic graphs with hundred thousands of vertexes where you continually remove vertexes in a loop, I doubt you would gain anything from using a LinkedList. Also, ArrayList.add(E) is O(1) unless the internal array must be resized, in which case it will be O(n).

Finally, you are mixing up user interface with program logic by including all those System.out.println statements. I think it would be better to throw exceptions whenever appropriate (like an IllegalArgumentException, for example) and let the calling method handle it. After all, a graph doesn't care whether an attempt to add a vertex or an edge was executed via the command line or by some other erroneous code.