By Massimo Presta

Search a tree or a graph in a reactive fashion

java reactor reactorseries recursion

Oct 31, 2021

Say you have to traverse a tree or a graph in a reactive fashion, no problem! Project Reactor has got you covered. Suppose you have a Node object that looks like the following:

public class Node {

    private final String name;
    private final boolean marked;
    private final List<Node> children;

    public Node(String name, boolean marked) {
        this.name = name;
        this.marked = marked;
        this.children = new ArrayList<>();
    }

    public Node(String name) {
        this.name = name;
        this.marked = false;
        this.children = new ArrayList<>();
    }

    public String getName() {
        return name;
    }

    public boolean isMarked() {
        return marked;
    }

    public List<Node> getChildren() {
        return children;
    }

    public void addChild(final Node...nodes) {
        children.addAll(Arrays.asList(nodes));
    }

    // ...
}

And Suppose you have the following tree:

@BeforeEach
void setUp() {
    //           RootNode
    //              |
    //             / \
    //            /   \
    //         Node1 Node2
    //           |     |
    //          /\      \
    //         /  \      \
    //     Node3 Node4   Node5

    rootNode = new Node("rootNode");

    node1 = new Node("Node1");
    node2 = new Node("Node2", true);
    node3 = new Node("Node3");
    node4 = new Node("Node4", true);
    node5 = new Node("Node5");

    node1.addChild(node3, node4);
    node2.addChild(node5);

    rootNode.addChild(node1, node2);
}

In the snippet above node2 and node4 have a marked value equals to true. In the following examples I will show how you can search a marked node using breadth first and depth first recursions. Those are just two types of algorithms that are used for traversing a tree or a graph. With DFS, the recursion starts at the root node and explores each branch before moving to the adjacent nodes. With BFS the adjacent nodes are explored before the child nodes. You can find more info on those techniques here.

Breadth First Search is generally recommended for trees that are very tall but not too wide or when the wanted node is closer to the root node. With Reactor you can execute BFS with the method Flux.expand.

@Test
@DisplayName("Reactive breadth first recursion")
void bfsRecursion() {
    StepVerifier.create(Flux.fromIterable(rootNode.getChildren())
            .expand(child -> Flux.fromIterable(child.getChildren())))
            .expectNext(node1, node2, node3, node4, node5)
            .verifyComplete();
}

@Test
@DisplayName("Reactive breadth first search")
void bfsFindFirstMarked() {
    Flux<Node> findMarked = Flux.fromIterable(rootNode.getChildren())
            .expand(child -> Flux.fromIterable(child.getChildren()))
            .takeUntil(Node::isMarked);

    StepVerifier.create(findMarked)
            .expectNext(node1, node2)
            .verifyComplete();

    // check that the found node is equal to the expected node2
    Node found = findMarked.last().block();

    assertNotNull(found);
    assertEquals(node2, found);
}

The bfsRecursion test shows how the whole tree is traversed when the expand method is used. The bfsFindFirstMarked method executes a breadth search of a marked node. In this instance the recursion stops when the node is found due to the use of takeUntil. Because this example is using BFS then node2 is found before node4.

Depth First Search is generally recommended for trees that are not too tall but wide or when the wanted node is further away from the root node. With Reactor you can execute DFS with the method Flux.expandDeep.

@Test
@DisplayName("Reactive depth first recursion")
void dfsRecursion() {
    StepVerifier.create(Flux.fromIterable(rootNode.getChildren())
            .expandDeep(child -> Flux.fromIterable(child.getChildren())))
            .expectNext(node1, node3, node4, node2, node5)
            .verifyComplete();
}

@Test
@DisplayName("Reactive depth first search")
void dfsFindFirstMarked() {

    Flux<Node> findMarked = Flux.fromIterable(rootNode.getChildren())
            .expandDeep(child -> Flux.fromIterable(child.getChildren()))
            .takeUntil(Node::isMarked);

    StepVerifier.create(findMarked)
            .expectNext(node1, node3, node4)
            .verifyComplete();

    // check that the found node is equal to the expected node4
    Node found = findMarked.last().block();

    assertNotNull(found);
    assertEquals(node4, found);
}

The dfsRecursion test shows how the tree is traversed in a depth first order compared to the previous example. The dfsFindFirstMarked method executes a depth search of a marked node, as a result node4 is found before node2.

The complete source code for the snippets illustrated in this article can be found in the java-series repo.