Digraph

Implementation for an immutable directed graph (often called "digraph"). An edge in the directed graph has a source and a target nodes. The given edge is designated as "outgoing edge" for the source node and as "incoming edge" for the target node. This directed graph implementation provides several add- and finder-methods for edges and nodes.

JUnit tests provide more details how to deals with the digraph.

public class DummyNode {

    private int id;
    private String name;

    public DummyNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        DummyNode dummyNode = (DummyNode) o;
        return id == dummyNode.id &&
                Objects.equals(name, dummyNode.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

public class DummyEdge {

    private int id;
    private String name;

    public DummyEdge(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        DummyEdge dummyNode = (DummyEdge) o;
        return id == dummyNode.id &&
                Objects.equals(name, dummyNode.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

/**
 * Tests the following Digraph with 4 nodes and 4 edges:
 * <pre>
 *                -------->--------
 *               /                 \
 * 1          2 /                   \ 3          4
 * o----->-----o----------<----------o----->-----o
 * </pre>
 */
class DigraphTest {

    private DummyNode node1;
    private DummyNode node2;
    private DummyNode node3;
    private DummyNode node4;

    private DummyEdge edge1;
    private DummyEdge edge2;
    private DummyEdge edge3;
    private DummyEdge edge4;

    private IDigraphBuilder<DummyEdge, DummyNode> digraphBuilder;

    @BeforeEach
    public void setup() {
        node1 = new DummyNode(1, "1");
        node2 = new DummyNode(2, "2");
        node3 = new DummyNode(3, "3");
        node4 = new DummyNode(4, "4");

        edge1 = new DummyEdge(12, "1 -> 2");
        edge2 = new DummyEdge(23, "2 -> 3");
        edge3 = new DummyEdge(32, "3 -> 2");
        edge4 = new DummyEdge(34, "3 -> 4");

        digraphBuilder = Digraph.<DummyEdge, DummyNode>builder()
                .idNodeExtractor(DummyNode::getId)
                .idEdgeExtractor(DummyEdge::getId)
                .edge(edge1, node1, node2)
                .edge(edge2, node2, node3)
                .edge(edge3, node3, node2)
                .edge(edge4, node3, node4);
    }

    @Test
    void getNodes() {
        assertThat(digraphBuilder.build().getNodes().size()).isEqualTo(4);
    }

    @Test
    void getEdges() {
        assertThat(digraphBuilder.build().getEdges().size()).isEqualTo(4);
    }

    @Test
    void findNodeById() {
        IDigraph<DummyEdge, DummyNode> digraph = digraphBuilder.build();
        assertThat(digraph.findNodeById(1).isPresent()).isTrue();
        assertThat(digraph.findNodeById(2).isPresent()).isTrue();
        assertThat(digraph.findNodeById(3).isPresent()).isTrue();
        assertThat(digraph.findNodeById(4).isPresent()).isTrue();
        assertThat(digraph.findNodeById(1234).isPresent()).isFalse();
    }

    @Test
    void findSourceNodeByEdge() {
        IDigraph<DummyEdge, DummyNode> digraph = digraphBuilder.build();
        assertThat(digraph.findSourceNodeByEdge(edge1).orElseThrow(IllegalStateException::new)).isEqualTo(node1);
        assertThat(digraph.findSourceNodeByEdge(edge2).orElseThrow(IllegalStateException::new)).isEqualTo(node2);
        assertThat(digraph.findSourceNodeByEdge(edge3).orElseThrow(IllegalStateException::new)).isEqualTo(node3);
        assertThat(digraph.findSourceNodeByEdge(edge4).orElseThrow(IllegalStateException::new)).isEqualTo(node3);
    }

    @Test
    void findTargetNodeByEdge() {
        IDigraph<DummyEdge, DummyNode> digraph = digraphBuilder.build();
        assertThat(digraph.findTargetNodeByEdge(edge1).orElseThrow(IllegalStateException::new)).isEqualTo(node2);
        assertThat(digraph.findTargetNodeByEdge(edge2).orElseThrow(IllegalStateException::new)).isEqualTo(node3);
        assertThat(digraph.findTargetNodeByEdge(edge3).orElseThrow(IllegalStateException::new)).isEqualTo(node2);
        assertThat(digraph.findTargetNodeByEdge(edge4).orElseThrow(IllegalStateException::new)).isEqualTo(node4);
    }

    @Test
    void findEdgeById() {
        IDigraph<DummyEdge, DummyNode> digraph = digraphBuilder.build();
        assertThat(digraph.findEdgeById(12).isPresent()).isTrue();
        assertThat(digraph.findEdgeById(23).isPresent()).isTrue();
        assertThat(digraph.findEdgeById(32).isPresent()).isTrue();
        assertThat(digraph.findEdgeById(34).isPresent()).isTrue();
        assertThat(digraph.findEdgeById(1234).isPresent()).isFalse();
    }

    @Test
    void findIncomingEdgesByNode() {
        IDigraph<DummyEdge, DummyNode> digraph = digraphBuilder.build();
        assertThat(digraph.findIncomingEdgesByNode(node1)).isEmpty();
        assertThat(digraph.findIncomingEdgesByNode(node2)).containsExactlyInAnyOrder(edge1, edge3);
        assertThat(digraph.findIncomingEdgesByNode(node3)).containsExactlyInAnyOrder(edge2);
        assertThat(digraph.findIncomingEdgesByNode(node4)).containsExactlyInAnyOrder(edge4);
    }

    @Test
    void findOutgoingEdgesByNode() {
        IDigraph<DummyEdge, DummyNode> digraph = digraphBuilder.build();
        assertThat(digraph.findOutgoingEdgesByNode(node1)).containsExactlyInAnyOrder(edge1);
        assertThat(digraph.findOutgoingEdgesByNode(node2)).containsExactlyInAnyOrder(edge2);
        assertThat(digraph.findOutgoingEdgesByNode(node3)).containsExactlyInAnyOrder(edge3, edge4);
        assertThat(digraph.findOutgoingEdgesByNode(node4)).isEmpty();
    }

    @Test
    void shouldThrowExceptionWhenMissingSourceNode() {
        // test a bad formed graph -> try to add an edge with non existing source node
        assertThrows(IllegalStateException.class, () -> {
            digraphBuilder.edgeWithNodeIds(new DummyEdge(5, "dummy edge"), 99, node1);
        });
    }

    @Test
    void shouldThrowExceptionWhenMissingTargetNode() {
        // test a bad formed graph -> try to add an edge with non existing target node
        assertThrows(IllegalStateException.class, () -> {
            digraphBuilder.edgeWithNodeIds(new DummyEdge(5, "dummy edge"), node1, 99);
        });
    }
}