Code Review Asked by msmilkshake on February 14, 2021
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);
}
}
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]
Just some remarks, I didn't review every method...
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:
addEdge() method add missing nodes is enough.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.You should add Javadoc comments explaining what the methods do and what the parameters mean.
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.
You chose to represent edges by three elements:
from node,to node,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.
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.
Correct answer by Ralf Kleberhoff on February 14, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP