Let's code: graphs in java
Tags: java, tdd, tutorial, graphs
Published: 2020-06-18 01:47:45

I have been obsessed with graphs for a few years now. This obsession has resulted in three projects: [graph-dsl](https://github.com/moaxcp/graph-dsl), [graphs](https://github.com/moaxcp/graphs), and [graph-wm](https://github.com/moaxcp/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 <a name="graph"></a>

`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 <a name="step-1"></a>

Like many tutorials this one is broken down into steps. Steps can be linked to using the form "[step-1](#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](#TDD). Here is that test.

```java
public class DirectedGraphTest {
  @Test
  void constructor() {
    DirectedGraph graph = new DirectedGraph();
  }
}
```

**Test Satus:** ❌ failing, write production code

# Step 2 <a name="step-2"></a>

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

```java
public class DirectedGraph {

}
```

**Test Satus:** ✔️ passing, write failing test

# Step 3 <a name="step-3"></a>

**Workflow:** According to [law #3](#TDD) we should not write more production code. The only valid option is to follow [law #1](#TDD) 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.

```java
@Test
void constructor() {
  DirectedGraph graph = new DirectedGraph();
  assertThat(graph.getVertices()).isEmpty();
}
```

**Test Status:** ❌ failing, write production code

# Step 4 <a name="step-4"></a>

**Workflow:** The `getVertices()` method does not compile and now the test is failing ([law #2](#TDD)) and production code can be added ([law #1](#TDD)).

**Action:** The method can be added using the IDE but intellij does not know the return type to use. Here is the code.

```java
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.

```java
public class DirectedGraph<T> {
  public Set<T> getVertices() {
    return null;
  }
}
```

**Test Status:** ❌ failing, write production code

# Step 5 <a name="step-5"></a>

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

```java
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 <a name="step-6"></a>

**Refactor Test:** 🔄 The test shows some warnings about the use of raw types. This can be fixed by adding a type parameter.

```java
@Test
void constructor() {
  DirectedGraph<String> graph = new DirectedGraph<>();
  assertThat(graph.getVertices()).isEmpty();
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 7 <a name="step-7"></a>

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

```java
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.

```java
public class DirectedEdgeTest {
  @Test
  void constructor() {
    DirectedEdge<String> edge = new DirectedEdge<>();
  }
}
```

**Test Status:** ❌ failing, write production code

# Step 8 <a name="step-8"></a>

As was in the case of `DirectedGraphTest` the `DirectedEdge` class may be generated in an IDE.

```java
public final class DirectedEdge<T> {
}
```

**Test Satus:** ✔️ passing, write failing test

#Step 9 <a name="step-9"></a>

**Action:** The test now passes but is the constructor correct? Lets add verification of the source vertex.

```java
@Test
void constructor() {
  DirectedEdge<String> edge = new DirectedEdge<>();
  assertThat(edge.getSource()).isEqualTo("A");
}
```

**Test Status:** ❌ failing, write production code

# Step 10 <a name="step-10"></a>

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

```java
public T getSource() {
  return null;
}
```

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

```java
public T getSource() {
  return (T) "A";
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 11 <a name="step-11"></a>

**Action:** Add verification for target vertex.

```java
@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 <a name="step-12"></a>

**Action:** Add `getTarget()` method to `DirectedEdge`.

```java
public T getTarget() {
  return (T) "B";
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 13 <a name="step-13"></a>

**Action:** replace default constructor with required args constructor.

```java
@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 <a name="step-14"></a>

**Action:** Add required args constructor (removing default constructor).

```java
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 <a name="step-15"></a>

**Action:** Add new constructor test with different source and target.


```java
@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 <a name="step-16"></a>

**Action:** Add member variables and assign in constructor.

```java
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 <a name="step-17"></a>

**Action:** Return member variables from getters.

```java
public T getSource() {
  return source;
}

public T getTarget() {
  return target;
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 18 <a name="step-18"></a>

**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`.

```java
@Test
void constructor_fails_on_null_source() {
  assertThatNullPointerException().isThrownBy(() -> new DirectedEdge<>(null, "B"));
}
```

**Test Status:** ❌ failing, write production code

# Step 19 <a name="step-19"></a>

**Action:** write null checks

```java
public DirectedEdge(T source, T target) {
  this.source = requireNonNull(source);
  this.target = target;
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 20 <a name="step-20"></a>

**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`. 

```java
assertThatNullPointerException()
  .isThrownBy(() -> new DirectedEdge<>(null, "B"))
  .withMessage("source must not be null");
```

**Test Status:** ❌ failing, write production code

# Step 21 <a name="step-21"></a>

**Action:** Add message to NPE

`requireNonNull` has another form that allows a message to be passed to the NPE.

```java
this.source = requireNonNull(source, "source must not be null");
```

**Test Satus:** ✔️ passing, write failing test

# Step 22 <a name="step-22"></a>

**Action:** Perform same test for `target`

```java
@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 <a name="step-23"></a>

**Action:** Add check for `target` in constructor

```java
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 <a name="step-24"></a>

**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](https://jqno.nl/equalsverifier/).

```java
@Test
void equalsContract() {
    EqualsVerifier.forClass(DirectedEdge.class).verify();
}
```

**Test Status:** ❌ failing, write production code

# Step 25 <a name="step-25"></a>

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

```java
@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.

```java
EqualsVerifier.forClass(DirectedEdge.class).suppress(Warning.NULL_FIELDS).verify();
```

**Test Satus:** ✔️ passing, write failing test

# Step 26 <a name="step-26"></a>

**Action:** Add check for edges in `DirectedGraph` constructor

Now that there is a `DirectedEdge` class edges in the `DirectedGraph` constructor class can be checked.

```java
@Test
void constructor() {
  DirectedGraph<String> graph = new DirectedGraph<>();
  assertThat(graph.getVertices()).isEmpty();
  assertThat(graph.getEdges()).isEmpty();
}
```

**Test Status:** ❌ failing, write production code

# Step 27 <a name="step-27"></a>

**Action:** Add `getEdges` method

```java
public Set<DirectedEdge<T>> getEdges() {
  return new HashSet<>();
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 28 <a name="step-28"></a>

In this step we are testing that vertices can be added to the graph.

**Action:** Make test for adding vertices

```java
@Test
void vertex_adds_new_vertex() {
  DirectedGraph<String> graph = new DirectedGraph<>();
  graph.vertex("A");
}
```

**Test Status:** ❌ failing, write production code

# Step 29 <a name="step-29"></a>

**Action:** Add `vertex` method

```java
  public void vertex(T vertex) {

  }
```

**Test Satus:** ✔️ passing, write failing test

# Step 30 <a name="step-30"></a>

**Action:** Add check for added vertex

```java
@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 <a name="step-31"></a>

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.

```java
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 <a name="step-32"></a>

The set returned by `getVertices()` should be unmodifiable.

**Action:** Add test ensuring vertices are unmodifiable.

```java
@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 <a name="step-33"></a>

**Action:** return unmodifiable set in `getVertices()`.

```java
public Set<T> getVertices() {
  return unmodifiableSet(vertices);
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 34 <a name="step-34"></a>

The same can be done for `getEdges()`.

**Action: ** Add test for `getEdges()` ensuring set is unmodifiable.

```java
@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 <a name="step-35"></a>

**Action:** return unmodifiable set in `getEdges()`.

```java
public Set<DirectedEdge<T>> getEdges() {
  return unmodifiableSet(new HashSet<>());
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 36 <a name="step-36"></a>

`null` vertices should not be allowed.

**Action:** `vertex` fails on on null parameter.

```java
@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 <a name="step-37"></a>

**Action:** check for null vertices.

```java
public void vertex(T vertex) {
  requireNonNull(vertex, "vertex must not be null");
  vertices.add(vertex);
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 38 <a name="step-38"></a>

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.

```java
@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 <a name="step-39"></a>

The `edge` method does not exist and needs to be added.

```java
public void edge(T source, T target) {
}
```

**Test Status:** ❌ failing, write production code

# Step 40 <a name="step-40"></a>

Now the `edge` method needs to throw the exception.

**Action: ** Add NPE to `edge` method.

```java
public void edge(T source, T target) {
  throw new NullPointerException("source must not be null");
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 41 <a name="step-41"></a>

The `edge` method should also check `target` for null.

**Action: ** Add test for null target parameter in `edge` method.

```java
@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 <a name="step-42"></a>

The `edge` method now needs to actually check source for a null value.

**Action: ** Add null checks for source and target in `edge` method.

```java
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 <a name="step-43"></a>

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

```java
@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 <a name="step-44"></a>

**Action: ** Add source vertex to graph in `edge` method.

```java
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 <a name="step-45"></a>

The target vertex should also be added to the graph.

**Action: ** Add test for target vertex in graph after calling `edge`.

```java
@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 <a name="step-46"></a>

**Action: ** Add source vertex to graph in `edge` method.

```java
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 <a name="step-47"></a>

The actual edge should be added as well.

**Action: ** Add test checking if edge is added to the graph.

```java
@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 <a name="step-48"></a>

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.

```java
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 <a name="step-49"></a>

At this point a method can be added to remove edges.

**Action: ** Add test for `removeEdge`.

```java
@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 <a name="step-50"></a>

**Action: ** `removeEdge` needs to be added in order to compile.

```java
public void removeEdge(T source, T target) {
}
```

**Test Status:** ❌ failing, write production code

# Step 51 <a name="step-51"></a>

**Action: ** Add check for a null source.

```java
public void removeEdge(T source, T target) {
  requireNonNull(source, "source must not be null");
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 52 <a name="step-52"></a>

**Action: ** Write a failing test checking for null target.

```java
@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 <a name="step-53"></a>

**Action: ** Add check in `removeEdge` for null `target`.

```java
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 <a name="step-54"></a>

`removeEdge` should fail if the edge is not found.

**Action: ** Add test expecting exception when edge does not exist.

```java
@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 <a name="step-55"></a>

**Action: ** Add check to see if edges contains the edge and throw exception if it is missing.

```java
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 <a name="step-56"></a>

**Action: ** Add test for removing and edge from the graph.

```java
@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 <a name="step-57"></a>

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

```java
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 <a name="step-58"></a>

Now a method is needed to remove vertices. Lets write a test for it.

**Action: ** Add test for removing vertices.

```java
@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 <a name="step-59"></a>

**Action: ** Add `removeVertex` method.

```java
public void removeVertex(T vertex) {
}
```

**Test Status:** ❌ failing, write production code

# Step 60 <a name="step-60"></a>

**Action: ** remove vertex.

```java
public void removeVertex(T vertex) {
  vertices.remove(vertex);
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 61 <a name="step-61"></a>

**Action: ** add test for null vertex parameter in `removeVertex`.

```java
@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 <a name="step-62"></a>

**Action: ** Add null check to method.

```java
public void removeVertex(T vertex) {
  requireNonNull(vertex, "vertex must not be null");
  vertices.remove(vertex);
}
```

**Test Satus:** ✔️ passing, write failing test

# Step 63 <a name="step-63"></a>

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.

```java
@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 <a name="step-64"></a>

**Action:** Find all adjacent edges and remove them in `removeVertex`.

```java
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 <a name="step-65"></a>

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.

```java
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](#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.