DEV Community

John Mercier
John Mercier

Posted on • Updated on

Let's code: graphs in java

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):

  1. You are not allowed to write any production code until you have first written a failing unit test.
  2. You are not allowed to write more of a unit test than is sufficient to fail -- and not compiling is failing.
  3. 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:

  1. write a test that fails
  2. write small production changes until all tests pass
  3. refactor production code
  4. 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)
Enter fullscreen mode Exit fullscreen mode

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();
  }
}
Enter fullscreen mode Exit fullscreen mode

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 {

}
Enter fullscreen mode Exit fullscreen mode

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 Sets. This test should show that the graph is initialized by checking that these two Sets are empty.

Action: Add failing check for vertices.

@Test
void constructor() {
  DirectedGraph graph = new DirectedGraph();
  assertThat(graph.getVertices()).isEmpty();
}
Enter fullscreen mode Exit fullscreen mode

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() {
}
Enter fullscreen mode Exit fullscreen mode

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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<>();
}
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

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<>();
  }
}
Enter fullscreen mode Exit fullscreen mode

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> {
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

The test will compile but still fail expecting the source to be "A".

public T getSource() {
  return (T) "A";
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 12

Action: Add getTarget() method to DirectedEdge.

public T getTarget() {
  return (T) "B";
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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";
  }
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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";
  }
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 17

Action: Return member variables from getters.

public T getSource() {
  return source;
}

public T getTarget() {
  return target;
}
Enter fullscreen mode Exit fullscreen mode

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"));
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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");
Enter fullscreen mode Exit fullscreen mode

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");
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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();
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 27

Action: Add getEdges method

public Set<DirectedEdge<T>> getEdges() {
  return new HashSet<>();
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 29

Action: Add vertex method

  public void vertex(T vertex) {

  }
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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);
  }
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 33

Action: return unmodifiable set in getVertices().

public Set<T> getVertices() {
  return unmodifiableSet(vertices);
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 35

Action: return unmodifiable set in getEdges().

public Set<DirectedEdge<T>> getEdges() {
  return unmodifiableSet(new HashSet<>());
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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) {
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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"));
}
Enter fullscreen mode Exit fullscreen mode

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));
  }
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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) {
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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));
  }
}
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

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));
  }
}
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

The test will fail to compile.

Test Status: ❌ failing, write production code

Step 59

*Action: * Add removeVertex method.

public void removeVertex(T vertex) {
}
Enter fullscreen mode Exit fullscreen mode

Test Status: ❌ failing, write production code

Step 60

*Action: * remove vertex.

public void removeVertex(T vertex) {
  vertices.remove(vertex);
}
Enter fullscreen mode Exit fullscreen mode

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");
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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();
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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)