# Implementation of a directed graph

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.

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<>();

Node<T> node = vertexes.get(key);
if (node == null) {
vertexes.put(key, node = new Node<T>(key));
}
return node;
}

// Required: O(V)
// Here it's O(1)
public boolean areAdjacent(T first, T second) {
if (vertexes.containsKey(first) && vertexes.containsKey(second)) {
} else {
return false;
}
}

// Required: O(E)
// Here it's O(1)
public void removeVertex(T key) {
vertexes.remove(key);
}

// Required: O(E)
// Here it's O(1)
public void removeEdge(T from, T to) {
}

// Required: O(1)
// Here it's O(1)
}

// Required: O(1)
// Here it's O(1)
public void addEdge(T from, T to) {

boolean newSet = false;
newSet = true;
}
if (newSet) {
}
}

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
// and
// http://cs.stackexchange.com/questions/9676/the-purpose-of-grey-node-in-graph-depth-first-search#comment140072_9681
node.color = Color.GREY;
}
}
node.color = Color.BLACK;
}
}

@Override
public String toString() {
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;
return true;
} else {
}
}
}
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
}
}


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

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

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

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.

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

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.