Implementing a Directed and Undirected Graph in Java

By 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.

Thank you in advance!!

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;
    }
    
    public boolean addNode(T node) {
        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) {
        return addEdge(from, to, 1.0);
    }
    
    public boolean addEdge(T from, T to, double weight) {
        return addEdge(from, to, weight, true);
    }
    
    public boolean addEdge(T from, T to, double weight, boolean addsNodes) {
        if (weight == Double.NEGATIVE_INFINITY ||
                Double.isNaN(weight)) {
            throw new IllegalArgumentException(
                    "Weight must be a number or the positive infinity");
        }
        if (addsNodes) {
            addNode(from);
            addNode(to);
        }
        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) {
                inDegree.add(graphNode);
            }
        }
        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
    public boolean addEdge(T node1, T node2, double weight, boolean addsNodes) {
        if (super.addEdge(node1, node2, weight, addsNodes)) {
            return super.addEdge(node2, node1, weight, addsNodes);
        }
        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;
    }
    
    public void loadGraph(DirectedGraph<T> graph) {
        this.graph = graph;
    }
    
    public void breadthFirstSearch(T from) {
        breadthFirstSearch(from, null);
    }
    
    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<>();
        LinkedList<T> queue = new LinkedList<>();
        queue.add(from);
        while (!queue.isEmpty()) {
            T parent = queue.pop();
            visited.add(parent);
            for (T node : graph.outDegreeOf(parent)) {
                if (visited.contains(node)) {
                    continue;
                }
                queue.add(node);
                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);
                }
            }
            settledNodes.add(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;
        LinkedList<T> list = new LinkedList<>();
        while (next != null) {
            list.addFirst(next);
            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<>();
        dGraph.addEdge("Zero", "One", 1.5);
        dGraph.addEdge("One", "Zero", 1.5);
        dGraph.addEdge("One", "Two", 0.7);
        dGraph.addEdge("Two", "Three", 1.9);
        dGraph.addEdge("Three", "Four", 1.1);
        dGraph.addEdge("Four", "One", 1.7);
        dGraph.addEdge("Four", "Five", 0.9);
        dGraph.addEdge("Five", "Four", 1.1);
        dGraph.addEdge("Five", "Zero", 2.0);
        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<>();
        uGraph.addEdge("Zero", "One");
        uGraph.addEdge("One", "Zero");
        uGraph.addEdge("One", "Two");
        uGraph.addEdge("Two", "Three");
        uGraph.addEdge("Three", "Four");
        uGraph.addEdge("Four", "One");
        uGraph.addEdge("Four", "Five");
        uGraph.addEdge("Five", "Four");
        uGraph.addEdge("Five", "Zero");
        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.

Javadocs

You should add Javadoc comments explaining what the methods do and what the parameters mean.

addsNodes

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.

Leave a Reply

Your email address will not be published. Required fields are marked *