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
}
}
