# Implementing a Directed and Undirected Graph in Java

Posted on

Problem

I am learning Graphs on my own and want to use a graph for a personal small project, so I decided to take a look here in Code Review for some cool implementations and came across this one by Maksim Dmitriev

I found it really great, so, heavily inspired and based on his implementation, I present you my own implementation.

I’d appreciate some honest review, and where I can get this better and more robust.

DirectedGraph.java

``````package experiments.implement.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

public class DirectedGraph<T> {
private final Map<T, Map<T, Double>> graphData = new HashMap<>();
private final Map<T, T> nodeSet = new HashMap<>();
private int edgeCount = 0;

public int getNodeCount() {
return nodeSet.size();
}

public int getEdgeCount() {
return edgeCount;
}

graphData.putIfAbsent(node, new HashMap<>());
return nodeSet.putIfAbsent(node, node) == null;
}

public T getNode(T node) {
return nodeSet.getOrDefault(node, null);
}

public T removeNode(T node) {
node = getNode(node);
if (node != null) {
edgeCount -= graphData.get(node).size();
graphData.remove(node);
nodeSet.remove(node);
for (T t : graphData.keySet()) {
if (graphData.get(t).remove(node) != null) {
--edgeCount;
}
}
}
return node;
}

public Iterator<T> nodeIterator() {
return graphData.keySet().iterator();
}

public Set<T> getNodes() {
return nodeSet.keySet();
}

public boolean addEdge(T from, T to) {
}

public 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 infinity");
}
}
if ((from = getNode(from)) == null
|| (to = getNode(to)) == null) {
return false;
}
Double oldWeight = graphData.get(from).put(to, weight);
if (oldWeight == null) {
++edgeCount;
}
return !Objects.equals(weight, oldWeight);
}

public double getEdgeWeight(T from, T to) {
if (hasEdge(from, to)) {
return graphData.get(from).get(to);
}
return Double.NaN;
}

private boolean hasEdge(T from, T to) {
return graphData.getOrDefault(from, new HashMap<>(0)).containsKey(to);
}

public boolean removeEdge(T from, T to) {
if (hasEdge(from, to)) {
graphData.get(from).remove(to);
--edgeCount;
return true;
}
return false;
}

public Set<T> outDegreeOf(T node) {
if (getNode(node) == null) {
return null;
}
return graphData.get(node).keySet();
}

public Set<T> inDegreeOf(T node) {
Set<T> inDegree = new HashSet<>();
for (T graphNode : nodeSet.keySet()) {
if (graphData.get(graphNode).getOrDefault(node, null) != null) {
}
}
return inDegree.isEmpty() ? null : inDegree;
}

public void clear() {
graphData.clear();
nodeSet.clear();
edgeCount = 0;
}

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

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

@Override
public String toString() {
StringBuilder sb = new StringBuilder("{");
Iterator<T> nodesIter = graphData.keySet().iterator();
while (nodesIter.hasNext()) {
T node = nodesIter.next();
sb.append(node);
Iterator<T> edgesIter = graphData.get(node).keySet().iterator();
sb.append(":[");
while (edgesIter.hasNext()) {
T edge = edgesIter.next();
sb.append("<")
.append(edge)
.append(", ").append(graphData.get(node).get(edge))
.append(">");
if (edgesIter.hasNext()) {
sb.append(", ");
}
}
sb.append("]");
if (nodesIter.hasNext()) {
sb.append(", ");
}
}
return sb.append("}").toString();
}
}
``````

UndirectedGraph.java

``````package experiments.implement.graph;

import java.util.Set;

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

@Override
public int getEdgeCount() {
return super.getEdgeCount() / 2;
}

@Override
}
return false;
}

@Override
public boolean removeEdge(T node1, T node2) {
if (super.removeEdge(node1, node2)) {
return super.removeEdge(node2, node1);
}
return false;
}

@Override
public Set<T> inDegreeOf(T node) {
return super.outDegreeOf(node);
}
}
``````

EXTRA: Some utility algorithm implementations like, Breadth First Search and Dijkstra Search
GraphUtil.java

``````package experiments.implement.graph;

import java.util.*;

public class GraphUtil<T> {

private Map<T, Double> distances;
private Map<T, T> previousNodes;
private DirectedGraph<T> graph;

public GraphUtil(DirectedGraph<T> graph) {
this.graph = graph;
}

this.graph = graph;
}

}

public void breadthFirstSearch(T from, T to) {
Set<T> nodes = new HashSet<>(graph.getNodes());
previousNodes = new HashMap<>(nodes.size(), 1);
Set<T> visited = new HashSet<>();
while (!queue.isEmpty()) {
T parent = queue.pop();
for (T node : graph.outDegreeOf(parent)) {
if (visited.contains(node)) {
continue;
}
previousNodes.putIfAbsent(node, parent);
if (node.equals(to)) {
return;
}
}
}
}

public void dijkstraSearch(T from) {
Set<T> nodes = new HashSet<>(graph.getNodes());
Set<T> settledNodes = new HashSet<>();
distances = new HashMap<>(nodes.size(), 1);
previousNodes = new HashMap<>(nodes.size(), 1);
for (T node : nodes) {
distances.put(node, Double.POSITIVE_INFINITY);
}
distances.put(from, 0.0);
T previous = from;

while (!nodes.isEmpty()) {
Set<T> outDegree = graph.outDegreeOf(previous);
for (T node : outDegree) {
if (settledNodes.contains(node)) {
continue;
}
double weight = graph.getEdgeWeight(previous, node);
if (weight < distances.get(node)) {
distances.put(node, distances.get(previous) + weight);
previousNodes.put(node, previous);
}
}
nodes.remove(previous);
double smallest = Double.POSITIVE_INFINITY;
for (T node : nodes) {
smallest = Math.min(smallest, distances.get(node));
}
for (T node : nodes) {
if (distances.get(node) == smallest) {
previous = node;
}
}
}
}

public List<T> getPathTo(T to) {
if (previousNodes == null || previousNodes.isEmpty()) {
return null;
}
T next = to;
while (next != null) {
next = previousNodes.getOrDefault(next, null);
}
return list;
}

public double getDistanceTo(T to) {
if (distances == null || distances.isEmpty()) {
return Double.NaN;
}
return distances.getOrDefault(to, Double.NaN);
}
}
``````

And now, just some basic program to experiment with some features of the graph:

Main.java

``````package experiments.implement.graph;

public class Main {
public static void main(String[] args) {
DirectedGraph<String> dGraph = new DirectedGraph<>();
System.out.println(dGraph);
System.out.println("Nodes: " + dGraph.getNodeCount() + ", Edges: " + dGraph.getEdgeCount());
System.out.println("In degree: " + dGraph.inDegreeOf("Zero"));
System.out.println("Out degree: " + dGraph.outDegreeOf("Zero"));

UndirectedGraph<String> uGraph = new UndirectedGraph<>();
System.out.println(uGraph);
System.out.println("Nodes: " + uGraph.getNodeCount() + ", Edges: " + uGraph.getEdgeCount());
System.out.println("In degree: " + uGraph.inDegreeOf("Zero"));
System.out.println("Out degree: " + uGraph.outDegreeOf("Zero"));
uGraph.removeEdge("Five", "Zero");
System.out.println(uGraph);
System.out.println("Nodes: " + uGraph.getNodeCount() + ", Edges: " + uGraph.getEdgeCount());
System.out.println("In degree: " + uGraph.inDegreeOf("Zero"));
}
}
``````

And the output of this little main method:

``````{Zero:[<One, 1.5>], Five:[<Zero, 2.0>, <Four, 1.1>], One:[<Zero, 1.5>, <Two, 0.7>], Four:[<Five, 0.9>, <One, 1.7>], Two:[<Three, 1.9>], Three:[<Four, 1.1>]}
Nodes: 6, Edges: 9
In degree: [Five, One]
Out degree: [One]
{Zero:[<Five, 1.0>, <One, 1.0>], Five:[<Zero, 1.0>, <Four, 1.0>], One:[<Zero, 1.0>, <Four, 1.0>, <Two, 1.0>], Four:[<Five, 1.0>, <One, 1.0>, <Three, 1.0>], Two:[<One, 1.0>, <Three, 1.0>], Three:[<Four, 1.0>, <Two, 1.0>]}
Nodes: 6, Edges: 7
In degree: [Five, One]
Out degree: [Five, One]
{Zero:[<One, 1.0>], Five:[<Four, 1.0>], One:[<Zero, 1.0>, <Four, 1.0>, <Two, 1.0>], Four:[<Five, 1.0>, <One, 1.0>, <Three, 1.0>], Two:[<One, 1.0>, <Three, 1.0>], Three:[<Four, 1.0>, <Two, 1.0>]}
Nodes: 6, Edges: 6
In degree: [One]
``````

Solution

Just some remarks, I didn’t review every method…

## Concise API

As an API for creating and querying graphs, `DirectedGraph` could be more focussed. E.g. there are too many different methods for adding nodes or edges to the graph. More is not always better. Example questions:

• Do you need graphs with isolated nodes (no connecting edges)? If not, having the `addEdge()` method add missing nodes is enough.
• What about weight? Is this part of the graph model that you implement, or not? If yes, remove all the methods without a `weight` parameter. If you want to support unweighted edges as well, see below for a more generic approach. The current version allows for any strange mixture between weighted and unweighted edges.

Especially the `addsNodes` parameter has a non-intuitive meaning. If false, adding the edge will only succeed if the nodes are already present in the graph. If not present, the edge is ignored, and you inform the caller about the failure by returning `false`. But a `false` return value can also mean that the edge was already present, which presents an ambiguity to your caller. I’d eliminate the methods with the `addsNodes` parameter and always add nodes if not yet present.

If you want to keep the `addNodes` parameter (for probably misguided performance reasons), I’d document that like “If false, the caller guarantees that the `from` and `to` nodes are already present in the graph.” If the nodes are indeed missing, you should throw an IllegalArgumentException or similar.

## Edge model

You chose to represent edges by three elements:

• the `from` node,
• the `to` node,
• a weight.

And you place some specific restrictions on weight, disallowing `NaN` and negative infinity.

A more generic approach would be to model the edges as first-class objects, with an interface `Edge`. For graph management, you only need the `from` and `to` nodes, any additional information (e.g. weight) is just for the user’s convenience, so can be added by the specific classes implementing that interface.

``````public interface Edge<T> {
T getFromNode();
T getToNode();
}

public class DirectedGraph<T, E extends Edge<T> {
...
}
``````

Then you just need one method for adding something to the graph, being

``````boolean addEdge(E edge) {
...
}
``````

And it’s up to your caller to use the appropriate Edge implementation, as you already did it with the node model. This way, the edges can be unweighted, weighted, or labelled with whatever information necessary for the user’s graphing needs.

## UndirectedGraph

You implemented `UndirectedGraph` as a subclass of `DirectedGraph`, implying that every `UndirectedGraph` can as well be seen as a `DirectedGraph`. But I think the semantics of both graph types are different, so I’d recommend to have `UndirectedGraph` not inherit from `DirectedGraph`.

If you really want to re-use the `DirectedGraph` implementation (I’d not do that), you can do that by giving `UndirectedGraph` a field of type `DirectedGraph`, meaning that you implement the undirected graph by maintaining an internal directed graph where every edge is duplicated. Then you can implement the public methods for an undirected graph by using the appropriate actions on the embedded directed graph. This is called delegation.

Your `UndirectedGraph` still has methods like `inDegreeOf()` and `outDegreeOf()` (inherited/overridden from the directed graph), and this does not match the concept of an undirected graph.

With your modelling, an `UndirectedGraph` can be stored into a variable of type `DirectedGraph`. A user unaware of the subclass will then experience strange behavior of that `DirectedGraph`, being e.g. that every edge gets doubled.