1
\$\begingroup\$

Here I've attached my java implementation of a directed graph. I've used a modified adjacency-list mechanic to utilize a map instead of a list for quicker lookup times. Looking for comments / suggestions on my approach, particularly whether or not it's worth implementing a map to replace an adjacency list, or if I'm writing my DFS / BFS methods correctly.

Graph class:

public class Graph<T> {

    private HashMap<GraphNode<T>, HashSet<GraphNode<T>>> adjacencyMap;
    private int numVertices;
    private int numEdges;
    private final String type = "directed";
    private final boolean weighted = false;

    public Graph() {
        this.adjacencyMap = new HashMap<>();
    }

    /**
    * Adds a vertex to the graph.
    * @param vertex vertex to add.
    * @return true if vertex was added successfully, false if otherwise.
    * @
    */
    public boolean addVertex(GraphNode<T> vertex) {
        if(!this.adjacencyMap.containsKey(vertex)) {
            this.adjacencyMap.put(vertex, new HashSet<>());
            this.numVertices++;
            return true;
        }
        return false;
    }

    /**
    * Removes a specified vertex from the graph.
    * @param vertex vertex to remove.
    * @return true if vertex was removed successfully, false if otherwise.
    * @
    */
    public boolean removeVertex(GraphNode<T> vertex) {
        if(this.adjacencyMap.containsKey(vertex)) {
            this.adjacencyMap.remove(vertex);
            for(Map.Entry<GraphNode<T>, HashSet<GraphNode<T>>> entry : this.adjacencyMap.entrySet()) {
                if(entry.getValue().contains(vertex)) {
                    this.adjacencyMap.get(entry.getKey()).remove(vertex);
                }
            }
            this.numVertices--;
            return true;
        }
        return false;
    }

    /**
    * Adds an edge between two vertices to the graph.
    * @param x source vertex of edge to add.
    * @param y destination vertex of edge to add.
    * @return true if the edge was added successfully, false if otherwise.
    * @
    */
    public boolean addEdge(GraphNode<T> x, GraphNode<T> y) {
        if(this.adjacencyMap.containsKey(x)) {
            if(!this.adjacencyMap.get(x).contains(y)) {
                this.adjacencyMap.get(x).add(y);
                this.numEdges++;
                return true;
            }
        }
        return false;
    }

    /**
    * Removes a specified edge between two vertices from the graph, if it already exists.
    * @param x source vertex of edge to remove.
    * @param y destination vertex of edge to remove.
    * @return true if the edge was removed successfully, false if otherwise.
    * @
    */
    public boolean removeEdge(GraphNode<T> x, GraphNode<T> y) {
        if(this.adjacencyMap.containsKey(x)) {
            if(this.adjacencyMap.get(x).contains(y)) {
                this.adjacencyMap.get(x).remove(y);
                this.numEdges--;
                return true;
            }
        }
        return false;
    }

    /**
    * Determines if two vertices are adjacent (or, if an edge exists between them).
    * @param x source vertex.
    * @param y destination vertex.
    * @return true if both vertices are adjacent, false if otherwise.
    * @
    */
    public boolean isAdjacent(GraphNode<T> x, GraphNode<T> y) {
        HashSet<GraphNode<T>> adjacencySet = this.adjacencyMap.get(x);
        if(adjacencySet != null) {
            if(adjacencySet.contains(y)) {
                return true;
            }
        }
        return false;
    }

    /**
    * Determines if graph contains a given vertex or not.
    * @param vertex vertex to search.
    * @return true if the graph contains the vertex, false if otherwise.
    * @
    */
    public boolean containsVertex(GraphNode<T> vertex) {
        if(this.adjacencyMap.containsKey(vertex)) {
            return true;
        }
        return false;
    }

    /**
    * Returns a HashSet containing all neighbors of a given vertex (or, all vertices with which the vertex shares an edge).
    * @param vertex vertex to search.
    * @return a HashSet containing all neighbors of the vertex.
    * @
    */
    public HashSet<GraphNode<T>> getNeighbors(GraphNode<T> vertex) {
        return this.adjacencyMap.get(vertex);
    }

    /**
    * Determines whether or not a path exists between two nodes, using Depth-First Search.
    * Uses a wrapper method to initialize objects required for search traversal.
    * @param source source node to be used in search.
    * @param destination destination node to be used in search.
    * @return true if a path exists between source and destination nodes, false if otherwise.
    * @
    */
    public boolean depthFirstSearch(GraphNode<T> source, GraphNode<T> destination) {
        if(!this.adjacencyMap.containsKey(source) || !this.adjacencyMap.containsKey(destination)) {
            return false;
        }
        Stack<GraphNode<T>> stack = new Stack<>();
        stack.push(source);
        return depthFirstSearch(stack, destination);
    }
    private boolean depthFirstSearch(Stack<GraphNode<T>> stack, GraphNode<T> destination) {
        HashMap<GraphNode<T>, VisitStatus> visited = new HashMap<>();
        while(!stack.isEmpty()) {
            GraphNode<T> current = stack.pop();
            visited.put(current, VisitStatus.VISITING);
            if(current.equals(destination)) {
                return true;
            }
            for(GraphNode<T> neighbor : this.adjacencyMap.get(current)) {
                if(visited.containsKey(neighbor)) {
                    if(visited.get(neighbor).equals(VisitStatus.UNVISITED)) {
                        stack.push(neighbor);
                    }
                } else {
                    stack.push(neighbor);
                }
            }
            visited.put(current, VisitStatus.VISITED);
        }
        return false;
    }

    /**
    * Determines whether or not a path exists between two nodes, using Breadth-First Search.
    * Uses a wrapper method to initialize objects required for search traversal.
    * @param source source node to be used in search.
    * @param destination destination node to be used in search.
    * @return true if a path exists between source and destination nodes, false if otherwise.
    * @
    */
    public boolean breadthFirstSearch(GraphNode<T> source, GraphNode<T> destination) {
        if(!this.adjacencyMap.containsKey(source) || !this.adjacencyMap.containsKey(destination)) {
            return false;
        }
        LinkedList<GraphNode<T>> queue = new LinkedList<>();
        queue.addLast(source);
        return breadthFirstSearch(queue, destination);
    }
    private boolean breadthFirstSearch(LinkedList<GraphNode<T>> queue, GraphNode<T> destination) {
        HashMap<GraphNode<T>, VisitStatus> visited = new HashMap<>();
        while(!queue.isEmpty()) {
            GraphNode<T> current = queue.removeFirst();
            visited.put(current, VisitStatus.VISITING);
            if(current.equals(destination)) {
                return true;
            }
            for(GraphNode<T> neighbor : this.adjacencyMap.get(current)) {
                if(visited.containsKey(neighbor)) {
                    if(visited.get(neighbor).equals(VisitStatus.UNVISITED)) {
                        queue.addLast(neighbor);
                    }
                } else {
                    queue.addLast(neighbor);
                }
            }
            visited.put(current, VisitStatus.VISITED);
        }
        return false;
    }

    /**
    * Returns the number of vertices within the graph.
    * @return an integer representing number of vertices contained within the graph.
    * @
    */
    public int getNumVertices() {
        return this.numVertices;
    }

    /**
    * Returns the number of edges within the graph.
    * @return an integer representing number of edges contained within the graph.
    * @
    */
    public int getNumEdges() {
        return this.numEdges;
    }

}

GraphNode class:

public class GraphNode<T> {

    private T data;

    public GraphNode() {}

    public GraphNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

VisitStatus enum:

public enum VisitStatus {
    UNVISITED,
    VISITING,
    VISITED
}
\$\endgroup\$
  • \$\begingroup\$ I would handle the adjacency in the Node level and not in the Graph level. \$\endgroup\$ – OhadR Aug 15 at 7:06
1
\$\begingroup\$

Object field declarations

    private HashMap<GraphNode<T>, HashSet<GraphNode<T>>> adjacencyMap;

This could be

    private Map<GraphNode<T>, Set<GraphNode<T>>> adjacencyMap = new HashMap<>();

Then you don't need to specify a constructor at all.

As a general rule, it is preferred to use the interface as the type rather than the implementation. This makes it easier to change implementations in the future. Both because you specify the implementation in fewer places and because this forces you to code to the interface.

Redundant variables

    public int getNumVertices() {
        return this.numVertices;
    }

Why bother with numVertices? Why not

    public int getVertexCount() {
       return adjacencyMap.size();
    }

Then you don't have to manually maintain an extra variable that tracks information that you already have.

I prefer singular names (e.g. vertex count) for singular variables and plural names for collections. In this case, you have a simple scalar variable and I would give it a singular name. This is of course a personal preference rather than a standard.

You don't have to use this. with object fields in Java unless there is a conflict between a local variable/parameter and an object field. You can. It will work fine. But you don't need to do so. Some find that it makes the code more readable in that it indicates that a particular variable is an object field and not something local. My personal preference is to leave it off unless necessary.

Contrast this with the variable holding the edge count. That variable has actual impact, as it saves having to count the number of edges, which is stored in many collections. But here, the vertex count is already tracked exactly by the number of keys in the adjacencyMap. Adding an extra variable means that there is one more thing to maintain. One more thing that can fail.

Inconsistent idiom

In several places, you enforce that for there to be a path between two vertices, both vertices must be in the graph. However, when adding an edge, you don't do this.

        if(this.adjacencyMap.containsKey(x)) {
            if(!this.adjacencyMap.get(x).contains(y)) {
                this.adjacencyMap.get(x).add(y);
                this.numEdges++;
                return true;
            }
        }
        return false;

This could be

        if (adjacencyMap.containsKey(x) && adjacencyMap.containsKey(y)) {
            if (!adjacencyMap.get(x).contains(y)) {
                adjacencyMap.get(x).add(y);
                numEdges++;

                return true;
            }
        }

        return false;

Or

        if (adjacencyMap.containsKey(x)) {
            if (!adjacencyMap.get(x).contains(y)) {
                addVertex(y);
                adjacencyMap.get(x).add(y);
                numEdges++;

                return true;
            }
        }

        return false;

Either way, you only have edges in the graph between two vertices in the graph.

Or even

        Set<GraphNode<T>> adjacentVertices = adjacencyMap.get(x);
        if (adjacentVertices != null && adjacentVertices.add(y)) {
            addVertex(y);
            numEdges++;

            return true;
        }

        return false;

Now, rather than always checking for presence, we assume that things will be there until told that they aren't. This change in pattern almost always works when containsKey is immediately followed by get.

Similarly, we now check if the add did anything after calling it rather than checking if it will work and then calling it.

Because the && operator short circuits, this has the same effect as if the second condition were in a second if inside the first.

\$\endgroup\$
  • \$\begingroup\$ thanks for the reply. I never considered that tracking something as small as a scalar variable could result in slightly decreased lookup times (in the case of edge count), or introduce a potential inconsistency within the data structure (through a vertex count mismatch). Would you say that there's any real value to using an 'adjacency map' outlined above, as opposed to a typical adjacency list? \$\endgroup\$ – koprulu Feb 8 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.