Implementation of a graph in Java

Question

A long time ago I posted my implementation of directed graph is Java. Recently I took a look at @coderodde's implementation and decided to write an implementation of undirected graph and directed graph. Besides I wrote some automated tests for both classes.

It's partially based on @coderodde's solution.

Here is the code:

AbstractGraph

package api;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * The implementation is partially based on
 * https://codereview.stackexchange.com/q/116686/23821
 * 
 * @author Maksim
 *
 * @param <T>
 */
public abstract class AbstractGraph<T> {

    // O(V+E)
    protected final Map<T, Map<T, Double>> graphData;
    private final Map<T, Color> colorMap = new HashMap<>();
    private int edgeCount;

    public AbstractGraph() {
        graphData = new HashMap<>();
    }

    public AbstractGraph(AbstractGraph<T> graph) {
        graphData = new HashMap<>(graph.graphData);
    }

    /**
     * Returns the number of nodes in this graph.
     * 
     * @return the size of this graph.
     */
    public final int getNodeCount() {
        return graphData.size();
    }

    /**
     * Returns the number of edges in this graph.
     * 
     * @return the number of edges.
     */
    public final int getEdgeCount() {
        return edgeCount;
    }

    /**
     * Adds the node with ID {@code nodeId} to this graph. O(1)
     * 
     * @param nodeId
     *            the ID of the node to add.
     * @return {@code true} if the structure of this graph has changed, which is
     *         the same as that the added node was not present in the graph.
     */
    public final boolean addNode(T nodeId) {
        if (hasNode(nodeId)) {
            return false;
        } else {
            graphData.put(nodeId, null);
            return true;
        }
    }

    /**
     * Checks whether the given node is present in this graph.
     * 
     * @param nodeId
     *            the query node.
     * @return {@code true} if the query node is in this graph. {@code false}
     *         otherwise.
     */
    public final boolean hasNode(T nodeId) {
        return graphData.containsKey(nodeId);
    }

    /**
     * Removes the argument node from this graph.
     * 
     * @param nodeId
     *            the node to remove.
     * @return {@code true} only if the node was present in the graph which
     *         means that the structure of the graph has changed.
     */
    public final boolean removeNode(T nodeId) {
        final boolean hasNode = hasNode(nodeId);
        if (hasNode) {
            graphData.remove(nodeId);
            Iterator<T> nodeIterator = graphData.keySet().iterator();
            while (nodeIterator.hasNext()) {
                graphData.get(nodeIterator.next()).remove(nodeId);
            }
        }
        return hasNode;
    }

    /**
     * @param from
     * @param to
     * @param weight
     *            the weight of the edge.
     * @return {@code true} only if the edge was not present in the graph, or
     *         the weight of the edge has changed.
     */
    public final boolean addEdge(T from, T to, double weight) {
        if (weight == Double.NEGATIVE_INFINITY || Double.isNaN(weight)) {
            throw new IllegalArgumentException("weight must be a number or the positive inifinity");
        }
        ensureCanAddEdge(from);
        ensureCanAddEdge(to);
        Double oldWeight = graphData.get(from).put(to, weight);
        if (oldWeight == null) {
            edgeCount++;
        }
        boolean fromEdgeUpdated = (oldWeight == null || Double.compare(oldWeight, weight) != 0);
        if (fromEdgeUpdated) {
            addOppositeEdge(to, from, weight);
        }
        return fromEdgeUpdated;
    }

    final void ensureCanAddEdge(T node) {
        Map<T, Double> fromEdges = graphData.get(node);
        if (fromEdges == null) {
            graphData.put(node, new HashMap<>());
        }
    }

    abstract void addOppositeEdge(T to, T from, double weight);

    /**
     * Creates an edge between {@code tailNodeId} and {@code headNodeId} with
     * the default weight of 1.0. This method is a shortcut for constructing
     * (virtually) unweighted graphs.
     * 
     * @param tailNodeId
     *            the tail node of the edge.
     * @param headNodeId
     *            the head node of the edge.
     * @return {@code true} only if the edge was not present in the graph, or
     *         the weight of the edge has changed.
     */
    public final boolean addEdge(T from, T to) {
        return addEdge(from, to, 1.0);
    }

    /**
     * Returns the weight of the edge {@code (tailNodeId, headNodeId)}. If the
     * query edge does not exist, returns {@link java.lang.Double#NaN}.
     * 
     * @param from
     * @param to
     * @return the weight of the edge.
     */
    public final double getEdgeWeight(T from, T to) {
        if (hasEdge(from, to)) {
            return graphData.get(from).get(to);
        } else {
            return Double.NaN;
        }
    }

    /**
     * Removes the edge from {@code from} and {@code to}.
     * 
     * @param from
     *            the tail node of the edge to remove.
     * @param to
     *            the head node of the edge to remove.
     * @return {@code true} if the target edge was in this graph, and thus is
     *         removed.
     */
    public final boolean removeEdge(T from, T to) {
        if (hasEdge(from, to)) {
            graphData.get(from).remove(to);
            removeOppositeEdge(to, from);
            return true;
        } else {
            return false;
        }
    }

    abstract void removeOppositeEdge(T to, T from);

    /**
     * Returns a boolean value indicating whether this graph contains an edge
     * from {@code tailNodeId} to {@code headNodeId}.
     * 
     * @param tailNodeId
     *            the tail node of the query edge.
     * @param headNodeId
     *            the head node of the query edge.
     * @return {@code true} only if the query edge is in this graph.
     */
    public final boolean hasEdge(T from, T to) {
        Map<T, Double> fromAdj = graphData.get(from);
        return fromAdj != null && fromAdj.get(to) != null;
    }

    /**
     * Removes all nodes and edges from this graph.
     */
    public final void clear() {
        graphData.clear();
    }

    public final String dfs() {
        if (graphData.isEmpty()) {
            return "[]";
        } else {
            StringBuilder builder = new StringBuilder();
            dfsInternal(graphData.keySet().iterator().next(), builder);
            colorMap.clear();
            return builder.toString();
        }
    }

    private void dfsInternal(T node, StringBuilder builder) {
        colorMap.put(node, Color.GREY);
        builder.append(node + " ");
        Map<T, Double> adj = graphData.get(node);
        if (adj != null) {
            for (T adjNode : adj.keySet()) {
                // Not visited yet
                if (colorMap.get(adjNode) == null) {
                    dfsInternal(adjNode, builder);
                }
            }
        }
        colorMap.put(node, Color.BLACK);
    }

    public final String bfs() {
        if (graphData.isEmpty()) {
            return "[]";
        }
        StringBuilder builder = new StringBuilder();
        Queue<T> queue = new ArrayDeque<>();
        queue.add(graphData.keySet().iterator().next());
        while (!queue.isEmpty()) {
            T node = queue.remove();
            builder.append(node + " ");
            colorMap.put(node, Color.GREY);
            Map<T, Double> adjNodes = graphData.get(node);
            if (adjNodes != null) {
                for (T adjNode : adjNodes.keySet()) {
                    if (colorMap.get(adjNode) == null) {
                        queue.add(adjNode);
                    }
                }
            }
            colorMap.put(node, Color.BLACK);
        }
        colorMap.clear();
        return builder.toString();
    }

    private boolean hasCyclesInternal(T current, T source) {
        colorMap.put(current, Color.GREY);
        Map<T, Double> adjMap = graphData.get(current);
        if (adjMap == null) {
            colorMap.put(current, Color.BLACK);
            return false;
        } else {
            Set<T> adjNodes = adjMap.keySet();
            for (T adj : adjNodes) {
                if (!colorMap.containsKey(adj)) {
                    if (hasCyclesInternal(adj, current)) {
                        return true;
                    }
                } else if (!isSource(adj, source) && colorMap.get(adj) == Color.GREY) {
                    return true;
                }
            }
            colorMap.put(current, Color.BLACK);
        }
        return false;
    }

    abstract boolean isSource(T adj, T source);

    public final boolean hasCycles() {
        if (graphData.isEmpty()) {
            return false;
        } else {
            try {
                return hasCyclesInternal(graphData.keySet().iterator().next(), null);
            } finally {
                colorMap.clear();
            }
        }
    }

    @Override
    public String toString() {
        return graphData.isEmpty() ? "[]" : graphData.toString();
    }

    private enum Color {
        GREY, BLACK
    }
}

UndirectedGraph

package api;

public class UndirectedGraph<T> extends AbstractGraph<T> {

    public UndirectedGraph() {}

    public UndirectedGraph(UndirectedGraph<T> graph) {
        super(graph);
    }

    @Override
    void addOppositeEdge(T to, T from, double weight) {
        graphData.get(to).put(from, weight);
    }

    @Override
    void removeOppositeEdge(T to, T from) {
        graphData.get(to).remove(from);
    }

    @Override
    boolean isSource(T node, T source) {
        return node == source;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof UndirectedGraph)) {
            return false;
        }
        UndirectedGraph<?> other = (UndirectedGraph<?>) obj;
        return graphData.equals(other.graphData);
    }

    @Override
    public int hashCode() {
        return graphData.hashCode();
    }

}

DirectedGraph

package api;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class DirectedGraph<T> extends AbstractGraph<T> {

    public DirectedGraph() {}

    public DirectedGraph(DirectedGraph<T> graph) {
        super(graph);
    }

    public final Set<T> inDegreeOf(T nodeId) {
        if (hasNode(nodeId)) {
            Set<T> inDegree = new HashSet<>();
            Iterator<T> fromIter = graphData.keySet().iterator();
            while (fromIter.hasNext()) {
                T from = fromIter.next();
                if (graphData.get(from).containsKey(nodeId)) {
                    inDegree.add(from);
                }
            }
            return inDegree;
        } else {
            return null;
        }
    }

    @Override
    void addOppositeEdge(T to, T from, double weight) {
    }

    @Override
    void removeOppositeEdge(T to, T from) {
    }

    public final Set<T> outDegreeOf(T nodeId) {
        if (graphData.containsKey(nodeId)) {
            return graphData.get(nodeId).keySet();
        } else {
            return null;
        }
    }

    @Override
    boolean isSource(T node, T source) {
        return false;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof DirectedGraph)) {
            return false;
        }
        DirectedGraph<?> other = (DirectedGraph<?>) obj;
        return graphData.equals(other.graphData);
    }

    @Override
    public int hashCode() {
        return graphData.hashCode();
    }

}

DirectedGraphTest

package api.test;

import java.util.HashSet;
import java.util.Set;

import org.junit.Assert;
import org.junit.Test;

import api.DirectedGraph;
import api.UndirectedGraph;

public class DirectedGraphTest {

    @Test
    public void inDegree() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(1, 2);
        directedGraph.addEdge(2, 4);
        directedGraph.addEdge(3, 4);
        directedGraph.addEdge(5, 4);
        directedGraph.addEdge(6, 4);

        Set<Integer> expected = new HashSet<>();
        expected.add(2);
        expected.add(3);
        expected.add(5);
        expected.add(6);

        Assert.assertEquals(expected, directedGraph.inDegreeOf(4));
    }

    @Test
    public void outDegree() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(1, 2);
        directedGraph.addEdge(2, 4);
        directedGraph.addEdge(3, 4);
        directedGraph.addEdge(5, 4);
        directedGraph.addEdge(6, 4);
        directedGraph.addEdge(2, 8);
        directedGraph.addEdge(2, 7);
        directedGraph.addEdge(2, 10);

        Set<Integer> expected = new HashSet<>();
        expected.add(4);
        expected.add(7);
        expected.add(8);
        expected.add(10);

        Assert.assertEquals(expected, directedGraph.outDegreeOf(2));
    }

    @Test
    public void hasCycles() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(1, 2);
        directedGraph.addEdge(2, 3);
        directedGraph.addEdge(3, 1);
        Assert.assertTrue(directedGraph.hasCycles());
    }

    @Test
    public void hasNoCycles() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(1, 2);
        directedGraph.addEdge(2, 3);
        directedGraph.addEdge(1, 3);
        Assert.assertFalse(directedGraph.hasCycles());
    }

    @Test
    public void equalsSymmetric() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(12, 56);
        directedGraph.addEdge(56, 100);
        DirectedGraph<Integer> directedGraph2 = directedGraph;
        Assert.assertTrue(directedGraph.equals(directedGraph2));
    }

    @Test
    public void equalsReflecsive() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(12, 56);
        directedGraph.addEdge(56, 100);
        Assert.assertTrue(directedGraph.equals(directedGraph));
    }

    @Test
    public void equalsTransitive() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(12, 56);
        directedGraph.addEdge(56, 100);

        DirectedGraph<Integer> directedGraph2 = new DirectedGraph<>();
        directedGraph2.addEdge(12, 56);
        directedGraph2.addEdge(56, 100);

        DirectedGraph<Integer> directedGraph3 = new DirectedGraph<>();
        directedGraph3.addEdge(12, 56);
        directedGraph3.addEdge(56, 100);

        Assert.assertTrue(directedGraph.equals(directedGraph2));
        Assert.assertTrue(directedGraph2.equals(directedGraph3));
        Assert.assertTrue(directedGraph.equals(directedGraph3));
    }

    @Test
    public void equalsOtherWrongType() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(12, 56);
        directedGraph.addEdge(56, 100);

        UndirectedGraph<Integer> undirectedGraph = new UndirectedGraph<>();
        undirectedGraph.addEdge(12, 56);
        undirectedGraph.addEdge(56, 100);
        Assert.assertFalse(directedGraph.equals(undirectedGraph));
    }

    @Test
    public void equalsNotEqualGraphs() {
        DirectedGraph<Integer> directedGraph = new DirectedGraph<>();
        directedGraph.addEdge(12, 56);
        directedGraph.addEdge(56, 100);

        DirectedGraph<Integer> directedGraph2 = new DirectedGraph<>();
        directedGraph2.addEdge(12, 57);
        directedGraph2.addEdge(56, 100);

        Assert.assertFalse(directedGraph.equals(directedGraph2));
    }

}

UndirectedGraphTest

package api.test;

import org.junit.Assert;
import org.junit.Test;

import api.UndirectedGraph;

public class UndirectedGraphTest {

    private static final double EPSILON = 0.000001;

    @Test
    public void addFirstNode() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        Assert.assertTrue(graph.addNode(1));
    }

    @Test
    public void checkFirstNodeAdded() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1000);
        Assert.assertTrue(graph.hasNode(1000));
    }

    @Test
    public void checkNotExistingNodeAbsent() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1000);
        Assert.assertFalse(graph.hasNode(2000));
    }

    @Test
    public void addNode() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        Assert.assertTrue(graph.addNode(2));
    }

    @Test
    public void addAlreadyAddedNode() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        Assert.assertFalse(graph.addNode(1));
    }

    @Test
    public void addEdgeToEmptyGraph() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        Assert.assertTrue(graph.addEdge(1, 2));
    }

    @Test
    public void checkEdgeAddedToEmptyGraph() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2);
        Assert.assertTrue(graph.hasEdge(1, 2));
    }

    @Test
    public void checkOppositeEdgeAddedToEmptyGraph() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2);
        Assert.assertTrue(graph.hasEdge(2, 1));
    }

    @Test
    public void connectExistingNodes() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        graph.addNode(2);
        Assert.assertTrue(graph.addEdge(1, 2));
    }

    @Test
    public void checkExistingNodesConnected() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        graph.addNode(2);
        graph.addEdge(1, 2);
        Assert.assertTrue(graph.hasEdge(1, 2));
    }

    @Test
    public void checkExistingOppositeNodesConnected() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        graph.addNode(2);
        graph.addEdge(1, 2);
        Assert.assertTrue(graph.hasEdge(2, 1));
    }

    @Test
    public void updateEdgeWeight() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        graph.addEdge(1, 3, 2.0);
        Assert.assertTrue(Double.compare(2.0, graph.getEdgeWeight(1, 3)) == 0);
    }

    @Test
    public void checkWeightUpdated() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        graph.addEdge(1, 3, 2.0);
        final double expected = 2.0;
        Assert.assertEquals(expected, graph.getEdgeWeight(1, 3), EPSILON);
    }

    @Test
    public void checkOppositeWeightUpdated() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        graph.addEdge(1, 3, 3.6);
        final double expected = 3.6;
        Assert.assertEquals(expected, graph.getEdgeWeight(1, 3), EPSILON);
    }

    @Test
    public void connectAlreadyConnectedNodes() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        Assert.assertFalse(graph.addEdge(1, 3));
    }

    @Test
    public void connectOppositeOfAlreadyConnectedNodes() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        Assert.assertFalse(graph.addEdge(3, 1));
    }

    @Test
    public void hasNoCyclesTwoNodes() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        Assert.assertFalse(graph.hasCycles());
    }

    @Test
    public void hasSelfLoop() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 1);
        Assert.assertTrue(graph.hasCycles());
    }

    @Test
    public void hasNoLoopsSingleNode() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(12);
        Assert.assertFalse(graph.hasCycles());
    }

    @Test
    public void hasSelfLoop2() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        Assert.assertTrue(graph.hasCycles());
    }

    @Test
    public void hasCycles() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 3);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        Assert.assertTrue(graph.hasCycles());
    }

    @Test(expected = IllegalArgumentException.class)
    public void addNonEdge() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2, Double.NaN);
    }

    @Test(expected = IllegalArgumentException.class)
    public void addNegativeInfinityEdge() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2, Double.NEGATIVE_INFINITY);
    }

    @Test
    public void addPositiveInfinityEdge() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2, Double.POSITIVE_INFINITY);
        Assert.assertTrue(graph.getEdgeWeight(1, 2) == Double.POSITIVE_INFINITY);
    }

    @Test
    public void nanWeightWhenNoEdge() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        graph.addNode(34);
        Assert.assertTrue(Double.isNaN(graph.getEdgeWeight(1, 34)));
    }

    @Test
    public void nanWeightWhenNoNodes() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addNode(1);
        graph.addNode(34);
        Assert.assertTrue(Double.isNaN(graph.getEdgeWeight(2, 67)));
    }

    @Test
    public void hasCyclesEmpty() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        Assert.assertFalse(graph.hasCycles());
    }

    @Test
    public void removeEdge() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 5);
        Assert.assertTrue(graph.removeEdge(1, 2));
        Assert.assertFalse(graph.hasEdge(2, 2));
        Assert.assertTrue(graph.hasEdge(1, 3));
        Assert.assertTrue(graph.hasEdge(2, 5));
    }

    @Test
    public void removeNode() {
        UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(1, 5);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);
        graph.addEdge(4, 6);
        graph.addEdge(2, 4);
        graph.addEdge(5, 6);
        Assert.assertTrue(graph.removeNode(3));
        Assert.assertFalse(graph.hasEdge(1, 3));
        Assert.assertFalse(graph.hasEdge(5, 3));
        Assert.assertFalse(graph.hasEdge(4, 3));
    }
}

Answer 1

Your code looks pretty consistent, so I will back off to commenting the overall design issues.

Advice 1 (heavily opinion-based)

Decouple the weight map from the graph: you have a directed graph and an undirected graph. Also, you define:

1. DirectedGraphWeightFunction,
2. UndirectedGraphWeightFunction.

Advice 2

Decouple the algorithms from the graph implementation. The idea here is that you do not write algorithms that are specific to your graph implementation. Instead, you expose an API that will facilitate the graph algorithms:

Set<NodeType> getChildrenOf(NodeType node)

The above will allow, at the very least, any unidirectional graph search algorithm. If you add also add

Set<NodeType> getParentsOf(NodeType node) 

that will allow bidirectional search as well.

Even better, in your, say, depth-first search (which should be decoupled from the concrete graph implementation), make it ask only the start node NodeType source and a NodeExpander<NodeType> which looks like this

public interface NodeExpander<NodeType> {
    public Collection<NodeType> expand(NodeType nodeToExpand);
}

Now, breadht-first search might look

public List<NodeType> breadthFirstSearch(NodeType source, NodeType target, NodeExpander<NodeType> expander) {
    ...
    while (queue not empty) {
        NodeType currentNode = queue.pop();

        for (NodeType neighbor : expander.expand(currentNode)) {
            ...
        }
    }
}

Finally, it might be useful to provide a method returning all the nodes of a graph.

Hope that helps.

Answer 2

You have chosen this class hierarchy:

          AbstractGraph
            /      \ 
UndirectedGraph  DirectedGraph

It is a valid one of course. But you coded it too strongly, and also an other, more OOP way exists.

(Hint) Those things:

    if(obj instanceof DirectedGraph)

And

    @Override
    void addOppositeEdge(T to, T from, double weight) { /* empty Method! */ }

Usually give away a structural problem

---

Here's where you went wrong

This is (what I feel was) your thought process:

• Let's make an abstract class to gather as much re-usable code as I can
• Make specific implementations with the differences only.
• The abstract class wil be built like a strong framework, and orchestrate the actions taken by the sub-classes in a standardised way

This is solid. The probem with that approach, is that usually you will hit a moment where one of your implementations needs to e.g. check some constraint, and this was not originally planned in the framework.

"It's OK", you think, "I'll just automatically add a checkStuff() method in my framework class, and let my implementation do their own thing".

But now your other implementations need to worry about implementing a checkStuff() method which they don't need.

Suddently your framework becomes very rigid (You must check pre-requisites in this preCheck() method and only there, etc.) and also your objects starts to leak: The AbstractGraph checks ensureCanAddEdge(from) and ensureCanAddEdge(to). But why would an Directed graph worry about ensureCanAddEdge(to), when it should not even attempt it? You're losing an opportunity to leave that node's map empty. The UndirecteGraph's philosophy has leaked into AbstractGraph, and from there to DirectedGraph!

Most wanted culprits:

abstract void addOppositeEdge(T to, T from, double weight);
abstract void removeOppositeEdge(T to, T from);

These really need to go away from AbstractGraph, they are an implementation detail of UndirectedGraph and pollute the other classes.

---

Here's a more flexible way

Now the above class hierarchy can normally provide a big advantage: each implementation can be really optimised differently to its siblings. That's not compatible with a strong framework however. The philosophy is this:

Whenever a constraint appears on a subclass, keep the new functionality local. If you cannot because the super is forcing a certain paradigm, make the super even more abstract. It may well end up being stripped to an interface.

In this case, I'd like to leverage the undirected graph's symmetry to only store half the weights (A to B, but not B to A, assuming there is an ordering where A>B). I can't with your AbstractGraph which forces a directed storage. So we need to keep the graph storage mechanism abstract and let implementations worry about it! And maybe another class will store graph implicitly, or in a matrix... It cannot do that with the current AbstractGraph.

Here's what I propose for a gradual change:

GraphInterface --> getEdges(), getAllNodes(), addEdge(), removeEdge(), getNodeCount(), getNodeExplorer()...
      |
      +---------------+-----------------+
      |               |                 |
DirectedGraph  UndirectedGraph    ImplicitGraph
                + addBidirEdge()   + setFunction()
 (stores all     (stores edges      (stores edges
    edges)         sparsely)          implicitly)

I've made GraphInterface an interface to force specific Node storage implementations. You could take advantage of Java 8's default keyword to provide typical implementation straight in the interface like so:

default boolean addEdge(T from, T to, double weight) {
    addEdge(T from, T to, 1.0);
}

The advantage is that DirectedGraph is now free to extend something else, like a Map directly! In general I like to let people extend what they want.

Now the most generic class is an interface, leaving future implementations completely free.

---

The more OOP class hierarchy

I wouldn't have chosen to have an AbstractGraph at all. Here's why there is no need.

A DirectedGraph is more general than an UndirectedGraph: it can represent both a directed, or an un-directed graph. An undirected graph is just a directed graph which makes sure all edges have their opposite edge. Uou even took advantage of this by making AbstractGraph store directed edges, and making all classes inherit this storage system.

In typical OOP, this lends itself well to having the following class hierarchy:

 DirectedGraph
       |
UndirectedGraph

Note: None of these classes need to be abstract.

Where UndirectedGraph overrides the directed methods to make sure they are, actually, undirected. For instance in DirectedGraph:

boolean addEdge(T from, T to, double weight) {
    (some pre-requisite checks, this is good)
    ensureCanAddEdge(from);
    graphData.get(from).put(to, weight);
    return (some post-requisite checks);
}

Will be Overriden in UndirectedGraph to :

@Override
boolean addEdge(T edgeA, T edgeB, double weight) {
    (maybe some additional pre-requisite checks, but probably not needed)
    boolean a2bOK = super.addEdge(edgeA, edgeB, weight);
    if(!a2bOK) {
        return false;
    }
    boolean b2aOK = super.addEdge(edgeB, edgeA, weight);
    return b2aOK && (some specific post-requisite checks);
}

This is how OOP is usually done. The higher level class is more general, the lower-level is more precise, and adds constraints. The nice thing is this is quite close to what you did (have a undirected graph be stored as a directed one).

---

The final hierarchy I would have used

All the above observations can be combined into this:

GraphInterface
       |
       +----------------+
       |                |
 DirectedGraph    ImplicitGraph
       |
UndirectedGraph

---

Notes on your Unit tests:

equalsReflecsive Should be equalsReflexive

equalsOtherWrongType is misquiding. Have you tried equals between an UndirectedGraph and a DirectedGraph like so:

DirectedGraph A: 12 --> 56
DirectedGraph A: 56 --> 12
UndirectedGraph B: 56<-->12

Are they equal? To me, they should be, because they represent the same graph. But you have a class check in your equals that does if(obj instanceof DirectedGraph) which I believe makes it fail.

---

Notes on additional functionality:

Just like @coderodde, I noted that you added a lot of functionality in the classes, that people may not need, are may be implemented better as standalone functions. Also the sheer name AbstractGraph does not lead me to expect it would contain graph analysis functions.

The excess features includes:

• Color. It may be an attribute of the T object you're handling. Indeed the user may provide a ColoredNode object if he wants it colored. He can then also make it Rainbow colored, which you didn't allow.
  On that topic, dfs() is mutating the color map, which I would never expect - and still don't understand. A search function should leave the object unchanged. I suspect you may want to make those color map variables method-scoped at least. You seem to have a tight coupling to your own graphic representation system, which I advise you to untie.
• dfs and bfs are search functions. They should be in a separate utility package. Given the sheer amount of similar algos that exist, all this has to be externalized.
  It is not obvious why they would return a String? To leverage each Graph's specificity and speed up the search, you may use double-dispatch to find a fitting implementation, but that's for a separate question. also there was no Javadoc on those functions, so I didn't review them further.
• hasCycles and all cycle-detection functions also warrant their own package and classes.
• outDegreeOf I have no idea what this name means, and it has no Javadoc.

In a NodeExpander object that @codereodde suggested I would like to see:

Set<T> getConnectedNodes(T initialNode);
Set<T> getConnectedNodes(T initialNode, int iterationLimit);
Set<T> getConnectedNodes(T initialNode, long timeoutMillis);
Set<T> path(T from, T to);
Set<T> getConnectedNodes(T from, T to, int iterationLimit);
Set<T> getConnectedNodes(T from, T to, double maxDist);
Set<T> getConnectedNodes(T from, T to, long timeoutMillis);

As you can see I want more control over my computation, possibly even a mix of the above, and we really need an external API to harness that functionality!

---

Lack of Edges

You did not provide an Edge Object.

Some algos work on edges. There are graphs that link from a same source, to a same destination, through multiple edges of varying costs. This is not possible with your implementations.

Like this:

 ------(12.0)-----> 
A                    B
 -----(11.5)------>

Some algos also need to ask List<Edge> graph.getEdgesFrom(T target).

To be considered.