Basic abstract graph implementation in Java

Question

I am trying to write a graph implementation in Java. I would appreciate it if someone can please review the code for me and give constructive feedback.

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

public class Graph {
    private int V;  // Number of vertices

    private int E;  // Number of edges

    private HashMap<Integer, LinkedList<Integer>> adj;  // adjacency list

    Graph() {
        adj = new HashMap<>();
    }

    /**
     * Returns the number of vertices
     * @return Number of vertices in the graph
     */
    public int vertices() {
        return this.V;
    }

    /**
     * Number of edges in the graph
     * @return Returns the number of edges in the graph
     */
    public int edges() {
        return this.E;
    }


    public void addEdge(int v, int w) {
        if(adj.containsKey(v)) {
            adj.get(v).add(w);
            ++E;
        } else if(adj.containsKey(w)) {
            adj.get(w).add(v);
            ++E;
        } else {
            LinkedList<Integer> llOne = new LinkedList<>();
            LinkedList<Integer> llTwo = new LinkedList<>();
            llTwo.add(v);
            llOne.add(w);
            adj.put(v, llOne);
            adj.put(w, llTwo);
            ++V; ++E;
        }
    }

    @Override
    public String toString() {
        StringBuilder returnString = new StringBuilder();
        for (int key : adj.keySet()) {
            returnString.append(key).append(": ");
            LinkedList<Integer> nodesList = adj.get(key);
            returnString.append(Arrays.toString(nodesList.toArray()));
        }
        return returnString.toString();
    }
}

Answer 1

Your constructor might as well be public; it doesn't matter if a user can create a separate Graph instance after all.

private int V;  // Number of vertices
private int E;  // Number of edges

Why not directly call them numberOfVertices and numberOfEdges or even just vertices and edges? Throughout the program you act if the variables are part of a math equation. However, that doesn't make your code any more readable.

Note that on most IDE's you can easily refactor after typing in the code as well. The current names make the variables look like generic types or constants. Not good.

public int vertices() {

I'd call that getVertices; you directly retrieve a field value without any other side effects, so this is consider a getter by most.

public void addEdge(int v, int w) {

Now we have two variables called v, that's not a good idea, even if they just vary in case.

---

About the functionality of the program:

1. There doesn't seem to be an option in case both v and w are present; in that case an edge needs to be added (it's separate from the other ones as no vertex needs to be added).
2. This program assumes that if one of the vertices already exists (the first branch in the if statement) that the edge cannot add a vertex (at least the count doesn't go up). This seems incorrect.
3. It also assumes that you can add parallel edges. So this is a multi-graph. In that case name your class that way.
4. In the case none of the vertices exist then you only add one to V which cannot be correct.
5. There doesn't seem any special handling for v == w: so called loops. I don't know if that's correct or not.

If you only want singular edges between vertices then you should explicitly skip if a v can be found with a w in the list. In that case you might be better off using a SortedSet such as a TreeSet.

---

If you allow your vertices and edges to be counted then you you would not have the trouble of keeping more state than necessary and getting out of sync. For instance, you could simply only count those edges to values higher than the key in the map (or divide by 2?). Counting the vertices should be easy.

For instance, I would come up with something similar to the following:

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * Implements a multi-graph without loops. A loop is an edge from one vertex to the same vertex.
 */
public class MultiGraph {
    private HashMap<Integer, List<Integer>> adjacentVerticesByVertex;

    /**
     * Constructs an empty graph.
     */
    public MultiGraph() {
        adjacentVerticesByVertex = new HashMap<>();
    }

    public int getNumberOfVertices() {
        return this.adjacentVerticesByVertex.size();
    }

    public int getNumberOfEdges() {
        int edgesBothWays = 0;
        for (var adjForVertice : adjacentVerticesByVertex.values()) {
            edgesBothWays += adjForVertice.size();
        }
        return edgesBothWays / 2;
    }

    public void addEdge(int vertexA, int vertexB) {
        if (vertexA == vertexB) {
            throw new IllegalArgumentException("Loops are not allowed");
        }

        addVertexAsAdjacent(vertexA, vertexB);
        addVertexAsAdjacent(vertexB, vertexA);
    }

    private void addVertexAsAdjacent(int vertexA, int vertexB) {
        var verticesForVertexA =
                adjacentVerticesByVertex.getOrDefault(vertexA, new LinkedList<Integer>());
        verticesForVertexA.add(vertexB);
        if (verticesForVertexA.size() == 1) {
            adjacentVerticesByVertex.put(vertexA, verticesForVertexA);
        }
    }

    @Override
    public String toString() {
        var sb = new StringBuilder();

        sb.append(String.format("Vertices: %d, Edges: %d, Adjacent vertices:",
                getNumberOfVertices(), getNumberOfEdges()));

        for (int key : adjacentVerticesByVertex.keySet()) {
            sb.append(String.format(" (V: %d ", key));
            var nodesList = adjacentVerticesByVertex.get(key);
            sb.append(Arrays.toString(nodesList.toArray()));
            sb.append(")");
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        var g = new MultiGraph();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 2);
        g.addEdge(10, 11);
        System.out.println(g);
    }
}

The disadvantage of counting all the edges this way is of course that you have to iterate over all vertices and check the size. Furthermore, as it is, it stores each edge twice - this way it is easier to go back and forth between two vertices with an edge, but it also means more memory usage.

But as you can see V is now gone, and just getting the number of keys in the set is undoubtedly just one call, so we are all the better for it: try and minimize the state within objects falls firmly within KISS principles.

Answer 2

Thinking about naming...

• When I see a single capital letter, it makes me think of generic type. I find your usage misleading.
• Single letter variable names can be OK when it's obvious what they are, such as indexers in loops, I would suggest avoiding them for anything with larger scope, particularly at the field level.
• int V; // Number of vertices, why not just call it numberOfVertices? You don't need the comment and the rest of the code is that little bit easier to interpret?
• edges(): Typically in Java I'd expect this type of method to be called getEdges, it's really just returning the field. In fact, when I first saw it, I thought it would be returning some collection of edges, but it doesn't it just returns a count. Consider renaming it to match what it returns.
• LinkedList<Integer> llOne = new LinkedList<>();. Generally, avoid embedding the type information (ll) in the variable name. Think about what the list is representing and call it that, rather than 'one' and 'two'.

Answer 3

Additional to these good answers a minor issue: using interfaces instead of concrete classes.

When you're working with List it would be helpful to work with the interface instead of its concrete implementation, for instance:

//LinkedList<Integer> llOne = new LinkedList<>(); concrete
List<Integer> llOne = ... //interface - as mentioned above consider better naming

same here:

//LinkedList<Integer> nodesList = adj.get(key); concrete
List<Integer> nodesList = adj.get(key);       //interface

Answer 4

Naming

Firstly, you must change the names from V to say "numberOfVertices" and "E" to numberOfEdges. The functions to get the numberOfVertices would be named as "getNumberOfVertices" and so on. Try to make the naming such that comments become entirely unnecessary.Similarly, adj should at least be named as "adjacencyList".

LinkedList<Integer> llOne = new LinkedList<>();
LinkedList<Integer> llTwo = new LinkedList<>();

are also not suitably named.

 StringBuilder returnString = new StringBuilder();

Bad name again. It does not convey any other information that it is supposed to be returned and it is a string.

Usability

How is this graph supposed to be used outside this class? The only information that you are allowing someone to access is the number of vertices, edges and stringified graph. How is the user of this class supposed to traverse this graph if he needs to?