Implementation of a graph in Java

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
*/
public abstract class AbstractGraph {

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

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

public AbstractGraph(AbstractGraph 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
*

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:

• DirectedGraphWeightFunction,

• 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 getChildrenOf(NodeType node)

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

Set 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 which looks like this

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

Now, breadht-first search might look

public List breadthFirstSearch(NodeType source, NodeType target, NodeExpander 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.

StackExchange Code Review Q#151883, answer score: 4