Graph Implementation in Java using adjacency list - v2

Question

Updated version from Graph Implementation in Java using adjacency list

public class MyGraph {
    // add vertex name as key, and neighbors as values in set
    HashMap<String, HashSet<String>> adjList = new HashMap<>();

    public void addVertex(String name) {
        if (adjList.containsKey(name)) {
            throw new IllegalArgumentException();
        }
        adjList.put(name, new HashSet<>());
    }

    public void addEdge(String source, String destination) {
        // are both vertexes already in the graph?
        if (!adjList.containsKey(source) || !adjList.containsKey(destination)) {
            throw new IllegalArgumentException();
        }

        // does edge already exist?
        if (adjList.get(source).contains(destination)) {
            throw new IllegalArgumentException();
        } else {
            adjList.get(source).add(destination);
        }
    }

    public HashSet<String> getNeighbors(String name) {
        return adjList.get(name);
    }

    // return true if there is an edge from source -> destination
    public boolean isNeighbor(String source, String destination) {
        if (!adjList.containsKey(source) || !adjList.containsKey(destination)) {
            throw new IllegalArgumentException();
        }
        return adjList.get(source).contains(destination);
    }

    public void removeEdge(String source, String destination) {
        if (!adjList.containsKey(source) || !adjList.containsKey(destination)) {
            throw new IllegalArgumentException();
        }
        adjList.get(source).remove(destination);
    }

    public void removeVertex(String name) {
        if (!adjList.containsKey(name)) {
            throw new IllegalArgumentException();
        }
        // remove vertex and its neighbors, if any
        adjList.remove(name);

        // remove vertex as a neighbors from other vertexes
        Set vertexes = adjList.keySet();
        Iterator i = vertexes.iterator();
        while (i.hasNext()) {
            String vertex = (String) i.next();
            if (adjList.get(vertex).contains(name)) {
                adjList.get(vertex).remove(name);
            }
        }
    }

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

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

    public boolean isEmpty() {
        return adjList.isEmpty();
    }
}

Answer 1

• You should make your class final unless you're explicitly intending it to be extended.

• adjList should be private. You don't want other classes in your package reaching into a MyGraph and messing with its adjacencies. It would also be reasonable to make it final. Map defines a clear method you can use.

• In general, prefer using interfaces where possible. Within your code, the fact that adjList is a HashMap and not a TreeMap is irrelevant. So just refer to it as a Map.

• Most of your comments are noise. If the purpose of a block of code isn't obvious, you can usually create a new method with a name that makes it obvious.

• There's no charge for extra characters, and it's easier to read adjacencyLists than adjList.

• Is it really necessary to throw an error if the user asks you to do something you've already done for them? If they need to know if the edge already existed, you can return a boolean. This is how the Collections API works, and I think it's a good model.

• You can't safely return a Set from your adjList, because if a user mucks with that, they're changing the internals of your graph. Use a new Set instance.

• For isNeighbor and removeEdge, do those need to be exceptions?

• Remember to use generics consistently.

• There's no need to call contains in removeVertex. Sets don't break if you try to remove a non-existent element.

• In removeVertex, it's a lot easier to just loop over the values in the map, rather than the keys.

If I were to refactor your code, a first pass might look something like:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public final class MyGraph {

    // add vertex name as key, and neighbors as values in set
    private final Map<String, Set<String>> adjacencyLists = new HashMap<>();

    public void addVertex(final String name) {
        if (this.adjacencyLists.containsKey(name)) {
            throw new IllegalArgumentException();
        }
        this.adjacencyLists.put(name, new HashSet<>());
    }

    public boolean addEdge(final String source, final String destination) {
        if (!this.adjacencyLists.containsKey(source) || !this.adjacencyLists.containsKey(destination)) {
            throw new IllegalArgumentException();
        }

        return this.adjacencyLists.get(source).add(destination);
    }

    public Set<String> getNeighbors(final String name) {
        return new HashSet<>(this.adjacencyLists.get(name));
    }

    /**
     * @return true if there is an edge from source -> destination
     */
    public boolean isNeighbor(final String source, final String destination) {
        if (!this.adjacencyLists.containsKey(source) || !this.adjacencyLists.containsKey(destination)) {
            throw new IllegalArgumentException();
        }
        return this.adjacencyLists.get(source).contains(destination);
    }

    public boolean removeEdge(final String source, final String destination) {
        if (!this.adjacencyLists.containsKey(source)) {
            return false;
        }

        return this.adjacencyLists.get(source).remove(destination);
    }

    public boolean removeVertex(final String name) {
        if (!this.adjacencyLists.containsKey(name)) {
            return false;
        }

        this.adjacencyLists.remove(name);

        for (final Set<String> adjacencies : this.adjacencyLists.values()) {
            adjacencies.remove(name);
        }

        return true;
    }

    /**
     * removes all vertexes/edges from graph
     */
    public void clear() {
        this.adjacencyLists.clear();
    }

    /**
     * @return the number of vertexes
     */
    public int size() {
        return this.adjacencyLists.size();
    }

    public boolean isEmpty() {
        return this.adjacencyLists.isEmpty();
    }
}