I have been obsessed with graphs for a few years now. This obsession has resulted in three projects: graph-dsl, graphs, and graph-wm. Graphs are excellent data structures that have helped me in a few situations at work. In this tutorial we will develop a mutable DirectedGraph class in Java using Test Driven Development (TDD).
This tutorial starts each step with a goal. The goal is to either write a failing test, refactor existing code, or write production code. With each step you will get closer to representing a directed graph with a full suite of tests proving it works. These steps will help you practice TDD and provide insight into how TDD can help you write better code. Before we start coding here is an introduction to graphs and the definitions used to design the code.
Graph
Graph
is not always well defined in programming languages. There are different implementations in java used for different situations. It is difficult for me to start coding a graph without some plan. First we need to put some concepts in place.
A graph encapsulates vertices and edges. A vertex is a value stored in the graph while an edge is a connection between those values. This implementation will contain a set of vertices and a set of edges.
Using a Set
implies uniqueness. Only unique vertices and edges are allowed in the graph. These objects must correctly implement equals
and hashCode
.
Identity for edges can be tricky. It depends on if the graph is directed or undirected. In an undirected graph only one edge can be between any two vertices. In a directed graph one or two edges can be between any two vertices. If there are two edges between two vertices those edges must be in opposite directions. These properties will affect the implementation of equals and hashCode for edges.
At this point we have enough information to start coding but I want to explain TDD.
TDD
Here are the three laws of TDD (from Clean Coder by Robert C. Martin):
- You are not allowed to write any production code until you have first written a failing unit test.
- You are not allowed to write more of a unit test than is sufficient to fail -- and not compiling is failing.
- You are not allowed to write more production code that is sufficient to pass the currently failing unit test.
These laws imply a workflow which consists of:
- write a test that fails
- write small production changes until all tests pass
- refactor production code
- refactor test code
refactor π change code in a way that does not fail tests and does not change the api or functionality.
To help facilitate TDD test status will be shown as a β when failing and a βοΈ when passing.
The TDD workflow quickly switches between writing tests to writing production code. In These steps there very little refactoring but a future tutorial may introduce refactoring.
Lets get started.
Step 1
Like many tutorials this one is broken down into steps. Steps can be linked to using the form "step-1" for example.
[step-1](#step-1)
The goal in using steps is to help discussion in the comments.
The DirectedGraph
class is production code. The class should not be written until there is a failing test according to law #1. Here is that test.
public class DirectedGraphTest {
@Test
void constructor() {
DirectedGraph graph = new DirectedGraph();
}
}
Test Satus: β failing, write production code
Step 2
Workflow: The criteria in law #1 is met and now the workflow changes to add production code. A failure to compile is considered a test failure according to law #2 and so no more unit test code should be written.
Action: Create the DirectedGraph
class. Most IDEs are helpful in situations where a class, method, or variable is missing. I am using intellij to create the class.
public class DirectedGraph {
}
Test Satus: βοΈ passing, write failing test
Step 3
Workflow: According to law #3 we should not write more production code. The only valid option is to follow law #1 and write a failing unit test.
Test Design: Back to the first test, it is obviously incomplete. The purpose of a constructor is to initialize the object. We have already discussed that DirectedGraph
will have two Set
s. This test should show that the graph
is initialized by checking that these two Set
s are empty.
Action: Add failing check for vertices.
@Test
void constructor() {
DirectedGraph graph = new DirectedGraph();
assertThat(graph.getVertices()).isEmpty();
}
Test Status: β failing, write production code
Step 4
Workflow: The getVertices()
method does not compile and now the test is failing (law #2) and production code can be added (law #1).
Action: The method can be added using the IDE but intellij does not know the return type to use. Here is the code.
public Set<T> getVertices() {
}
Production Design: In this case the IDE does not know how to design this method and I added the return value as a generic. The test is driving that these design decisions need to be made now. I am deciding that vertices must be a member variable and returned by getVertices()
. I am also deciding that vertices are generic. Making vertices generic also implies that DirectedGraph
is now generic.
public class DirectedGraph<T> {
public Set<T> getVertices() {
return null;
}
}
Test Status: β failing, write production code
Step 5
Action: The test will still fail but it does compile. At this point we need to return an empty Set for the test to pass.
public Set<String> getVertices() {
return HashSet<>();
}
Test Satus: βοΈ passing, write failing test
Returning a new Set
seems like an odd thing to do but I believe it is in line with the laws of TDD. Vertices will likely not become a member variable until a failing test shows it is needed.
Step 6
Refactor Test: π The test shows some warnings about the use of raw types. This can be fixed by adding a type parameter.
@Test
void constructor() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThat(graph.getVertices()).isEmpty();
}
Test Satus: βοΈ passing, write failing test
Step 7
Workflow: Now the test is passing and another failing unit test is needed (law #2). Remember the current goal is to check the constructor. There is a test that checks vertices but what about edges.
I want to add an assertion that looks something like this:
assertThat(graph.getEdges()).isEmpty()
Design: But what is an edge? I have not decided how edges are represented in a graph. At this point I need a failing test but it doesn't have to be the constructor test. The context needs to switch to a focus on designing an edge.
DirectedEdge class
A DirectedEdge
class should contain the source vertex and the target vertex of the edge. These are the endpoints of the edge. DirectedEdge
must also use a generic type so the graph can specify different vertex types when creating an edge. Since edges will be in a Set
they must implement equals
and hashCode
. I am also deciding that DirectedEdge
should be an immutable value class which means source and target will be required constructor parameters and the class is final. This is enough information to create tests.
public class DirectedEdgeTest {
@Test
void constructor() {
DirectedEdge<String> edge = new DirectedEdge<>();
}
}
Test Status: β failing, write production code
Step 8
As was in the case of DirectedGraphTest
the DirectedEdge
class may be generated in an IDE.
public final class DirectedEdge<T> {
}
Test Satus: βοΈ passing, write failing test
Step 9
Action: The test now passes but is the constructor correct? Lets add verification of the source vertex.
@Test
void constructor() {
DirectedEdge<String> edge = new DirectedEdge<>();
assertThat(edge.getSource()).isEqualTo("A");
}
Test Status: β failing, write production code
Step 10
The method getSource()
does not exist but also notice that the test is expecting it to be equal to "A". First getSource()
can be added to DirectedEdge
.
public T getSource() {
return null;
}
The test will compile but still fail expecting the source to be "A".
public T getSource() {
return (T) "A";
}
Test Satus: βοΈ passing, write failing test
Step 11
Action: Add verification for target vertex.
@Test
void constructor() {
DirectedEdge<String> edge = new DirectedEdge<>();
assertThat(edge.getSource()).isEqualTo("A");
assertThat(edge.getTarget()).isEqualTo("B");
}
Test Status: β failing, write production code
Step 12
Action: Add getTarget()
method to DirectedEdge
.
public T getTarget() {
return (T) "B";
}
Test Satus: βοΈ passing, write failing test
Step 13
Action: replace default constructor with required args constructor.
@Test
void constructor() {
DirectedEdge<String> edge = new DirectedEdge<>("A", "B");
assertThat(edge.getSource()).isEqualTo("A");
assertThat(edge.getTarget()).isEqualTo("B");
}
Test Status: β failing, write production code
Step 14
Action: Add required args constructor (removing default constructor).
public final class DirectedEdge<T> {
public DirectedEdge(T source, T target) {
}
public T getSource() {
return (T) "A";
}
public T getTarget() {
return (T) "B";
}
}
Test Satus: βοΈ passing, write failing test
Step 15
Action: Add new constructor test with different source and target.
@Test
void constructor_AB() {
DirectedEdge<String> edge = new DirectedEdge<>("A", "B");
assertThat(edge.getSource()).isEqualTo("A");
assertThat(edge.getTarget()).isEqualTo("B");
}
@Test
void constructor_XY() {
DirectedEdge<String> edge = new DirectedEdge<>("X", "Y");
assertThat(edge.getSource()).isEqualTo("X");
assertThat(edge.getTarget()).isEqualTo("Y");
}
Test Status: β failing, write production code
Step 16
Action: Add member variables and assign in constructor.
public final class DirectedEdge<T> {
private final T source;
private final T target;
public DirectedEdge(T source, T target) {
this.source = source;
this.target = target;
}
public T getSource() {
return "A";
}
public T getTarget() {
return "B";
}
}
Test Status: β failing, write production code
Step 17
Action: Return member variables from getters.
public T getSource() {
return source;
}
public T getTarget() {
return target;
}
Test Satus: βοΈ passing, write failing test
Step 18
Action: Add null checks
It doesn't make sense to allow a null source
or target
. These parameters should be checked in the constructor. A nice way to do this is with Objects.requireNonNull
.
@Test
void constructor_fails_on_null_source() {
assertThatNullPointerException().isThrownBy(() -> new DirectedEdge<>(null, "B"));
}
Test Status: β failing, write production code
Step 19
Action: write null checks
public DirectedEdge(T source, T target) {
this.source = requireNonNull(source);
this.target = target;
}
Test Satus: βοΈ passing, write failing test
Step 20
Action: Add check for exception message
Checking for the exception is ok but there is not real way to prove that the exception is caused by a null source
. One way to show this is to check the message for the NullPointerException
.
assertThatNullPointerException()
.isThrownBy(() -> new DirectedEdge<>(null, "B"))
.withMessage("source must not be null");
Test Status: β failing, write production code
Step 21
Action: Add message to NPE
requireNonNull
has another form that allows a message to be passed to the NPE.
this.source = requireNonNull(source, "source must not be null");
Test Satus: βοΈ passing, write failing test
Step 22
Action: Perform same test for target
@Test
void constructor_fails_on_null_target() {
assertThatNullPointerException()
.isThrownBy(() -> new DirectedEdge<>("A", null))
.withMessage("target must not be null");
}
Test Status: β failing, write production code
Step 23
Action: Add check for target
in constructor
public DirectedEdge(T source, T target) {
this.source = requireNonNull(source, "source must not be null");
this.target = requireNonNull(target, "target must not be null");
}
Test Satus: βοΈ passing, write failing test
Step 24
Action: Test equals
and hashCode
.
Since edges are stored in a HashSet it makes sense to implement equals
and hashCode
.
Testing the equals
and hashCode
contract is difficult even in this simple case. There are two member variables source
and target
. Instead of writing all of these tests there is a tool available which can do these tests for us. This will be done using equals-verifier.
@Test
void equalsContract() {
EqualsVerifier.forClass(DirectedEdge.class).verify();
}
Test Status: β failing, write production code
Step 25
Action: Write equals
and hashCode
methods using IDE.
To generate this code in intellij I used the java 7+ format and source and target are non null.
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
DirectedEdge<?> that = (DirectedEdge<?>) o;
return source.equals(that.source) &&
target.equals(that.target);
}
@Override
public int hashCode() {
return Objects.hash(source, target);
}
Test Status: β failing, write production code
The equalsContract
test will still fail since source
and target
are non-null.
Action: Suppress these warnings.
EqualsVerifier.forClass(DirectedEdge.class).suppress(Warning.NULL_FIELDS).verify();
Test Satus: βοΈ passing, write failing test
Step 26
Action: Add check for edges in DirectedGraph
constructor
Now that there is a DirectedEdge
class edges in the DirectedGraph
constructor class can be checked.
@Test
void constructor() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThat(graph.getVertices()).isEmpty();
assertThat(graph.getEdges()).isEmpty();
}
Test Status: β failing, write production code
Step 27
Action: Add getEdges
method
public Set<DirectedEdge<T>> getEdges() {
return new HashSet<>();
}
Test Satus: βοΈ passing, write failing test
Step 28
In this step we are testing that vertices can be added to the graph.
Action: Make test for adding vertices
@Test
void vertex_adds_new_vertex() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.vertex("A");
}
Test Status: β failing, write production code
Step 29
Action: Add vertex
method
public void vertex(T vertex) {
}
Test Satus: βοΈ passing, write failing test
Step 30
Action: Add check for added vertex
@Test
void vertex_adds_new_vertex() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.vertex("A");
assertThat(graph.getVertices()).containsExactly("A");
}
Test Status: β failing, write production code
Step 31
This test proves that DirectedGraph
needs to store vertices.
Action: Add vertices member and change vertex
method to add the vertex. Change getVertices()
to return vertices.
public class DirectedGraph<T> {
private final Set<T> vertices;
public DirectedGraph() {
vertices = new HashSet<>();
}
public Set<T> getVertices() {
return vertices;
}
public Set<DirectedEdge<T>> getEdges() {
return new HashSet<>();
}
public void vertex(T vertex) {
vertices.add(vertex);
}
}
Test Satus: βοΈ passing, write failing test
Step 32
The set returned by getVertices()
should be unmodifiable.
Action: Add test ensuring vertices are unmodifiable.
@Test
void vertices_are_unmodifiable() {
DirectedGraph<Integer> graph = new DirectedGraph<>();
Set<Integer> vertices = graph.getVertices();
assertThatThrownBy(() -> vertices.add(10))
.isInstanceOf(UnsupportedOperationException.class);
}
Test Status: β failing, write production code
Step 33
Action: return unmodifiable set in getVertices()
.
public Set<T> getVertices() {
return unmodifiableSet(vertices);
}
Test Satus: βοΈ passing, write failing test
Step 34
The same can be done for getEdges()
.
*Action: * Add test for getEdges()
ensuring set is unmodifiable.
@Test
void edges_are_unmodifiable() {
DirectedGraph<Integer> graph = new DirectedGraph<>();
Set<DirectedEdge<Integer>> edges = graph.getEdges();
assertThatThrownBy(() -> edges.add(new DirectedEdge<>(1, 2)))
.isInstanceOf(UnsupportedOperationException.class);
}
Test Status: β failing, write production code
Step 35
Action: return unmodifiable set in getEdges()
.
public Set<DirectedEdge<T>> getEdges() {
return unmodifiableSet(new HashSet<>());
}
Test Satus: βοΈ passing, write failing test
Step 36
null
vertices should not be allowed.
Action: vertex
fails on on null parameter.
@Test
void vertex_fails_on_null_vertex() {
DirectedGraph<Integer> graph = new DirectedGraph<>();
assertThatNullPointerException()
.isThrownBy(() -> graph.vertex(null))
.withMessage("vertex must not be null");
}
Test Status: β failing, write production code
Step 37
Action: check for null vertices.
public void vertex(T vertex) {
requireNonNull(vertex, "vertex must not be null");
vertices.add(vertex);
}
Test Satus: βοΈ passing, write failing test
Step 38
Now that vertices can be added to the graph, edges should be added to the graph. This method should ensure that the vertices are added if not present in the graph. This time the tests start by checking for error conditions. The idea is to test for errors before writing the happy path code.
*Action: * Add check for null source parameter to edge
method.
@Test
void edge_fails_on_null_source() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThatNullPointerException()
.isThrownBy(() -> graph.edge(null, "B"))
.withMessage("source must not be null");
}
Test Status: β failing, write production code
Step 39
The edge
method does not exist and needs to be added.
public void edge(T source, T target) {
}
Test Status: β failing, write production code
Step 40
Now the edge
method needs to throw the exception.
*Action: * Add NPE to edge
method.
public void edge(T source, T target) {
throw new NullPointerException("source must not be null");
}
Test Satus: βοΈ passing, write failing test
Step 41
The edge
method should also check target
for null.
*Action: * Add test for null target parameter in edge
method.
@Test
void edge_fails_on_null_target() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThatNullPointerException()
.isThrownBy(() -> graph.edge("A", null))
.withMessage("target must not be null");
}
Test Status: β failing, write production code
Step 42
The edge
method now needs to actually check source for a null value.
*Action: * Add null checks for source and target in edge
method.
public void edge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
}
Test Satus: βοΈ passing, write failing test
Step 43
The edge
method should add the source vertex if it is not already in the graph.
*Action: * Add test for source vertex in graph after calling edge
.
@Test
void edge_adds_source_vertex() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.edge("A", "B");
assertThat(graph.getVertices()).contains("A");
}
Test Status: β failing, write production code
Step 44
*Action: * Add source vertex to graph in edge
method.
public void edge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
vertex(source);
}
Test Satus: βοΈ passing, write failing test
Step 45
The target vertex should also be added to the graph.
*Action: * Add test for target vertex in graph after calling edge
.
@Test
void edge_adds_target_vertex() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.edge("A", "B");
assertThat(graph.getVertices()).contains("B");
}
Test Status: β failing, write production code
Step 46
*Action: * Add source vertex to graph in edge
method.
public void edge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
vertex(source);
vertex(target);
}
Test Satus: βοΈ passing, write failing test
Step 47
The actual edge should be added as well.
*Action: * Add test checking if edge is added to the graph.
@Test
void edge_adds_an_edge() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.edge("A", "B");
assertThat(graph.getEdges()).containsExactly(new DirectedEdge<>("A", "B"));
}
Test Status: β failing, write production code
Step 48
The test proves that edges
needs to be a member variable which requires changes to the constructor getEdges()
and the edge
method.
*Action: * Add edges member variable, use member in getEdges
and edges
method.
public class DirectedGraph<T> {
private final Set<T> vertices;
private final Set<DirectedEdge<T>> edges;
public DirectedGraph() {
vertices = new HashSet<>();
edges = new HashSet<>();
}
public Set<T> getVertices() {...}
public Set<DirectedEdge<T>> getEdges() {
return unmodifiableSet(edges);
}
public void vertex(T vertex) {...}
public void edge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
vertex(source);
vertex(target);
edges.add(new DirectedEdge<>(source, target));
}
}
Test Satus: βοΈ passing, write failing test
Step 49
At this point a method can be added to remove edges.
*Action: * Add test for removeEdge
.
@Test
void removeEdge_fails_on_null_source() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThatNullPointerException()
.isThrownBy(() -> graph.removeEdge(null, "A"))
.withMessage("source must not be null");
}
Test Status: β failing, write production code
Step 50
*Action: * removeEdge
needs to be added in order to compile.
public void removeEdge(T source, T target) {
}
Test Status: β failing, write production code
Step 51
*Action: * Add check for a null source.
public void removeEdge(T source, T target) {
requireNonNull(source, "source must not be null");
}
Test Satus: βοΈ passing, write failing test
Step 52
*Action: * Write a failing test checking for null target.
@Test
void removeEdge_fails_on_null_target() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThatNullPointerException()
.isThrownBy(() -> graph.removeEdge("A", null))
.withMessage("target must not be null");
}
Test Status: β failing, write production code
Step 53
*Action: * Add check in removeEdge
for null target
.
public void removeEdge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
}
Test Satus: βοΈ passing, write failing test
Step 54
removeEdge
should fail if the edge is not found.
*Action: * Add test expecting exception when edge does not exist.
@Test
void removeEdge_fails_on_missing_edge() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThatIllegalArgumentException()
.isThrownBy(() -> graph.removeEdge("A", "B"))
.withMessage("edge with source \"A\" and target \"B\" does not exist");
}
Test Status: β failing, write production code
Step 55
*Action: * Add check to see if edges contains the edge and throw exception if it is missing.
public void removeEdge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
if(!edges.contains(new DirectedEdge<>(source, target))) {
throw new IllegalArgumentException(String.format("edge with source \"%s\" and target \"%s\" does not exist", source, target));
}
}
Test Satus: βοΈ passing, write failing test
Step 56
*Action: * Add test for removing and edge from the graph.
@Test
void removeEdge_removes_edge() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.edge("A", "B");
graph.removeEdge("A", "B");
assertThat(graph.getEdges()).isEmpty();
}
Test Status: β failing, write production code
Step 57
Instead of calling contains
the code can call remove
. This will remove the edge and still throw an exception when the edge does not exist in the graph.
*Action: * Use remove
instead of contains
.
public void removeEdge(T source, T target) {
requireNonNull(source, "source must not be null");
requireNonNull(target, "target must not be null");
if(!edges.remove(new DirectedEdge<>(source, target))) {
throw new IllegalArgumentException(String.format("edge with source \"%s\" and target \"%s\" does not exist", source, target));
}
}
Test Satus: βοΈ passing, write failing test
Step 58
Now a method is needed to remove vertices. Lets write a test for it.
*Action: * Add test for removing vertices.
@Test
void removeVertex_removes_vertex() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.vertex("A");
graph.removeVertex("A");
assertThat(graph.getVertices()).isEmpty();
}
The test will fail to compile.
Test Status: β failing, write production code
Step 59
*Action: * Add removeVertex
method.
public void removeVertex(T vertex) {
}
Test Status: β failing, write production code
Step 60
*Action: * remove vertex.
public void removeVertex(T vertex) {
vertices.remove(vertex);
}
Test Satus: βοΈ passing, write failing test
Step 61
*Action: * add test for null vertex parameter in removeVertex
.
@Test
void removeVertex_fails_on_null_vertex() {
DirectedGraph<String> graph = new DirectedGraph<>();
assertThatNullPointerException()
.isThrownBy(() ->graph.removeVertex(null))
.withMessage("vertex must not be null");
}
Test Status: β failing, write production code
Step 62
*Action: * Add null check to method.
public void removeVertex(T vertex) {
requireNonNull(vertex, "vertex must not be null");
vertices.remove(vertex);
}
Test Satus: βοΈ passing, write failing test
Step 63
There is one more failure condition when removing vertices. If the vertex being removed has adjacent edges those edges should also be removed.
Action: Add test checking that adjacent edges are removed when vertex is removed.
@Test
void removeVertex_removes_adjacent_edges() {
DirectedGraph<String> graph = new DirectedGraph<>();
graph.edge("A", "B");
graph.removeVertex("A");
assertThat(graph.getEdges()).isEmpty();
}
Test Status: β failing, write production code
Step 64
Action: Find all adjacent edges and remove them in removeVertex
.
public void removeVertex(T vertex) {
requireNonNull(vertex, "vertex must not be null");
Iterator<DirectedEdge<T>> i = edges.iterator();
while(i.hasNext()) {
DirectedEdge<T> next = i.next();
if(next.getSource().equals(vertex) || next.getTarget().equals(vertex)) {
i.remove();
}
}
vertices.remove(vertex);
}
Test Satus: βοΈ passing, refactor π change code in a way that does not fail tests
Step 65
Now is a time to refactor. The refactor is actually suggested by Intellij. It replaces the iterator with a call to removeIf
using a lambda.
Action: Refactor removeVertex
to use removeIf
when removing adjacent edges.
public void removeVertex(T vertex) {
requireNonNull(vertex, "vertex must not be null");
edges.removeIf(next -> next.getSource().equals(vertex) || next.getTarget().equals(vertex));
vertices.remove(vertex);
}
Test Satus: βοΈ passing, write failing test
Conclusion
The DirecteGraph
class is now able to create and remove vertices and edges. This tutorial described a design for graphs and provided a step-by-step guide for building DirectedGraph
using TDD.
There are still several problems to solve but this is a good start in representing a graph as code.
Top comments (0)