Implementation of a directed graph

Question

I wrote an implementation of a directed graph using the adjacency list representation. My goal was to meet the big O requirements which I'd found here.

Please let me know about any drawbacks of the implementation.

package sample;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class Graph<T> {
 private static final String EOL = System.getProperty("line.separator");
 // Required: O(V + E)
 // Here it's O(V)
 private final Map<T, Node<T>> vertexes = new HashMap<>();
 private final Map<T, Set<Node<T>>> vertexesWithAdjacents = new HashMap<>();
 private Node<T> addVertexInternal(T key) {
 Node<T> node = vertexes.get(key);
 if (node == null) {
 vertexes.put(key, node = new Node<T>(key));
 vertexesWithAdjacents.put(key, null);
 }
 return node;
 }
 // Required: O(V)
 // Here it's O(1)
 public boolean areAdjacent(T first, T second) {
 if (vertexes.containsKey(first) && vertexes.containsKey(second)) {
 Set<Node<T>> firstAdj = vertexesWithAdjacents.get(first);
 Set<Node<T>> secondAdj = vertexesWithAdjacents.get(second);
 return firstAdj != null && vertexesWithAdjacents.get(first).contains(new Node<T>(second))
 || secondAdj != null && vertexesWithAdjacents.get(second).contains(new Node<T>(first));
 } else {
 return false;
 }
 }
 // Required: O(E)
 // Here it's O(1)
 public void removeVertex(T key) {
 vertexesWithAdjacents.remove(key);
 vertexes.remove(key);
 }
 // Required: O(E)
 // Here it's O(1)
 public void removeEdge(T from, T to) {
 vertexesWithAdjacents.get(from).remove(new Node<T>(to));
 }
 // Required: O(1)
 // Here it's O(1)
 public void addVertex(T key) {
 addVertexInternal(key);
 }
 // Required: O(1)
 // Here it's O(1)
 public void addEdge(T from, T to) {
 addVertexInternal(from);
 Node<T> toNode = addVertexInternal(to);
 Set<Node<T>> fromAdj = vertexesWithAdjacents.get(from);
 boolean newSet = false;
 if (fromAdj == null) {
 newSet = true;
 fromAdj = new HashSet<>();
 }
 fromAdj.add(toNode);
 if (newSet) {
 vertexesWithAdjacents.put(from, fromAdj);
 }
 }
 private void resetWhite() {
 for (T key : vertexes.keySet()) {
 vertexes.get(key).color = Color.WHITE;
 }
 }
 private void dfsInternal(Node<T> node) {
 if (node.color == Color.WHITE) {
 System.out.print(node + " ");
 // Actually we can set BLACK here.
 // GREY matters in hasCyclesInternal
 // See also http://cs.stackexchange.com/q/9676/15063
 // and
 // http://cs.stackexchange.com/questions/9676/the-purpose-of-grey-node-in-graph-depth-first-search#comment140072_9681
 node.color = Color.GREY;
 Set<Node<T>> nodeAdj = vertexesWithAdjacents.get(node.key);
 if (nodeAdj != null) {
 for (Node<T> adj : nodeAdj) {
 dfsInternal(adj);
 }
 }
 node.color = Color.BLACK;
 }
 }
 @Override
 public String toString() {
 if (vertexesWithAdjacents.isEmpty()) {
 return "[]";
 }
 StringBuilder builder = new StringBuilder();
 for (T key : vertexesWithAdjacents.keySet()) {
 builder.append(key + ": " + vertexesWithAdjacents.get(key) + EOL);
 }
 return builder.toString();
 }
 public void dfs() {
 if (!vertexes.isEmpty()) {
 resetWhite();
 dfsInternal(vertexes.entrySet().iterator().next().getValue());
 }
 }
 public boolean hasCycles() {
 if (!vertexes.isEmpty()) {
 resetWhite();
 return hasCyclesInternal(vertexes.entrySet().iterator().next().getValue());
 } else {
 return false;
 }
 }
 private boolean hasCyclesInternal(Node<T> node) {
 if (node.color == Color.WHITE) {
 node.color = Color.GREY;
 Set<Node<T>> adjNodes = vertexesWithAdjacents.get(node.key);
 if (adjNodes != null) {
 for (Node<T> adj : adjNodes) {
 if (adj.color == Color.GREY) {
 return true;
 } else {
 return hasCyclesInternal(adj);
 }
 }
 }
 node.color = Color.BLACK;
 }
 return false;
 }
 private static class Node<T> {
 T key;
 Graph.Color color;
 public Node(T key) {
 this.key = key;
 }
 @Override
 public int hashCode() {
 return key.hashCode();
 }
 @Override
 public String toString() {
 return key.toString();
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj) {
 return true;
 }
 if (!(obj instanceof Node)) {
 return false;
 }
 Node<?> other = (Node<?>) obj;
 return key.equals(other.key);
 }
 }
 private enum Color {
 WHITE, GREY, BLACK
 }
}

Answer 1

Advice 1

I would remove Node<T> and use T as the actual node type.

Advice 2

Also, I don't think it is worth maintaining vertexes; just use vertexesWithAdjacents. (By the way, the plural form of vertex is vertices.)

Advice 3

Since your graph is directed, it would make sense to make it explicit by renaming the graph to DirectedGraph.

Advice 4

In areAdjacent it looks like you don't obey the fact that the graph is directed: given an arc \$(u, v)\$ with no arc \$(v, u)\,ドル both will return true in areAdjacent.

Advice 5

I would remove the colors from each node and use a map from nodes to colors.

Advice 6

Furthermore, I would implement cycle detection algorithm and DFS as not methods in the graph class.

Finally

You could take a look at this implementation.

Hope that helps.

• Maksim Dmitriev: I just posted a new implementation codereview.stackexchange.com/q/151883/23821