2
\$\begingroup\$

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
    }
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

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.