Java Graph Implementation

Question

Attempt to implement undirected graph with intentions of making a directed implementation too. I'm also new to Generics. I'm sure there's a lot of things I can do better

public class UndirectedGraph<T> implements Graph<T> {

    private Map<T, List<T>> adjacencyList;

    public UndirectedGraph() {
        adjacencyList = new HashMap<>();
    }

    //Checks if a vertex with the same name exists, if not adds it and returns true
    @Override
    public boolean addVertex(T vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new LinkedList<T>());
            return true;
        }
        return false;
    }

    @Override
    public boolean addEdge(T src, T dst) {
        if (adjacencyList.containsKey(src) && adjacencyList.containsKey(dst)) {
            adjacencyList.get(src).add(dst);
            adjacencyList.get(dst).add(src);
            return true;
        }
        return false;
    }


    //Prints the adjacecny list
    public void printAdjacencyList() {
        adjacencyList.entrySet().forEach(entry -> {
            System.out.println(entry.getKey() + " " + entry.getValue().toString());
        });
    }


    //Removes the vertex and all the edges tied to it.
    @Override
    public boolean removeVertex(T vertex) {
        if (adjacencyList.containsKey(vertex)) {
            adjacencyList.remove(vertex);
            for (Map.Entry<T, List<T>> entry : getAdjacencyList().entrySet()) {
                List<T> list = entry.getValue();
                for (T e : list) {
                    if (e.equals(vertex)) {
                        entry.getValue().remove(e);
                    }
                }
            }
            return true;
        }
        return false;
    }

    /*IF graph is directed, removes the edge from the list of the source
     * If graph is not directed, removes the edge from the list of the source and destination*/

    @Override
    public boolean removeEdge(T source, T destination) {
        if (source != null && destination != null) {
            adjacencyList.get(source).remove(destination);
            adjacencyList.get(destination).remove(source);
            return true;
        }
        return false;
    }

    public Map<T, List<T>> getAdjacencyList() {
        return adjacencyList;
    }
}

Graph Interface:

public interface Graph<T> {

    public boolean addVertex(T vertex);
    public boolean addEdge(T src, T dst);
    public boolean removeVertex(T vertex);
    public boolean removeEdge(T source, T destination);
} 

Answer 1

In the Graph interface, there's no need to declare the methods public. Interface methods are implicitly public.

The adjacency graph should probably be a Map<T, Set<T>>, as the order of connected nodes is not important. This will make some lookups mildly faster, but more importantly it won't imply to readers that the order matters.

The adjacency graph can be assigned inline. There's no reason to make readers go into the constructor to find the assignment.

The adjacency graph can be marked final. This makes it clear to readers that it is never reassigned.

All of the methods return true or false, but if a method fails there is no way for the caller to figure out why. At the very least, all the interface methods need javadoc explaining under what conditions they return which value. Consider also whether throwing runtime exceptions would make sense when these methods are invoked with invalid values.

Prefer guard clauses instead of sticking all the code of a method in an if block. For example,

public boolean removeVertex(T vertex) {
    if (adjacencyList.containsKey(vertex)) {
        return false;
    }
    adjacencyList.remove(vertex);
    //...
    return true;
}

addVertex could leverage putIfAbsent.

Objects should not be responsible for printing themselves. For starters, what if the client code is using a logging framework? Instead, override toString() to return a string representation of the adjacency graph.

removeVertex can be cleaned up by looping over values() instead of entrySet() and by using remove(vertex) on the Collection that is returned.

getAdjacencyList returns the actual backing data structure of the graph, which means a client can accidentally or maliciously break the invariants of the graph. Either return a Collections.unmodifiableMap() or make a copy of the map and return that.