Skip to content

Commit 1884857

Browse files
snirtsnirt
authored
Make DFS and BFS search algorithms generic (fixes #4229) (#4230)
1 parent 1ef700e commit 1884857

File tree

6 files changed

+244
-85
lines changed

6 files changed

+244
-85
lines changed

‎pom.xml

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,9 @@
3838
<groupId>org.assertj</groupId>
3939
<artifactId>assertj-core</artifactId>
4040
<version>${assertj.version}</version>
41+
<scope>test</scope>
4142
</dependency>
43+
4244
<dependency>
4345
<groupId>org.junit.jupiter</groupId>
4446
<artifactId>junit-jupiter-api</artifactId>

‎src/main/java/com/thealgorithms/datastructures/Node.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.thealgorithms.datastructures;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class Node<T> {
7+
8+
private final T value;
9+
private final List<Node<T>> children;
10+
11+
public Node(final T value) {
12+
this.value = value;
13+
this.children = new ArrayList<>();
14+
}
15+
16+
public Node(final T value, final List<Node<T>> children) {
17+
this.value = value;
18+
this.children = children;
19+
}
20+
21+
public T getValue() {
22+
return value;
23+
}
24+
25+
public void addChild(Node<T> child) {
26+
children.add(child);
27+
}
28+
29+
public List<Node<T>> getChildren() {
30+
return children;
31+
}
32+
}

‎src/main/java/com/thealgorithms/searches/BreadthFirstSearch.java

Lines changed: 24 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,45 @@
11
package com.thealgorithms.searches;
22

3-
import com.thealgorithms.searches.DepthFirstSearch.Node;
4-
import java.util.ArrayDeque;
5-
import java.util.Optional;
6-
import java.util.Queue;
3+
import com.thealgorithms.datastructures.Node;
4+
import java.util.*;
75

86
/**
97
* @author: caos321
108
* @date: 31 October 2021 (Sunday)
9+
* @wiki: https://en.wikipedia.org/wiki/Breadth-first_search
1110
*/
12-
public class BreadthFirstSearch {
13-
public static Optional<Node> search(final Node node, final String name) {
14-
if (node.getName().equals(name)) {
11+
public class BreadthFirstSearch<T> {
12+
13+
private final List<T> visited = new ArrayList<>();
14+
15+
public Optional<Node<T>> search(final Node<T> node, final T value) {
16+
if (node == null) {
17+
return Optional.empty();
18+
}
19+
if (node.getValue().equals(value)) {
20+
// add root node to visited
21+
visited.add(value);
1522
return Optional.of(node);
1623
}
24+
visited.add(node.getValue());
1725

18-
Queue<Node> queue = new ArrayDeque<>(node.getSubNodes());
26+
Queue<Node<T>> queue = new ArrayDeque<>(node.getChildren());
1927

2028
while (!queue.isEmpty()) {
21-
final Node current = queue.poll();
29+
final Node<T> current = queue.poll();
30+
visited.add(current.getValue());
2231

23-
if (current.getName().equals(name)) {
32+
if (current.getValue().equals(value)) {
2433
return Optional.of(current);
2534
}
2635

27-
queue.addAll(current.getSubNodes());
36+
queue.addAll(current.getChildren());
2837
}
2938

3039
return Optional.empty();
3140
}
41+
42+
public List<T> getVisited() {
43+
return visited;
44+
}
3245
}

‎src/main/java/com/thealgorithms/searches/DepthFirstSearch.java

Lines changed: 12 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -1,79 +1,32 @@
11
package com.thealgorithms.searches;
22

3+
import com.thealgorithms.datastructures.Node;
34
import java.util.ArrayList;
45
import java.util.List;
5-
import java.util.Objects;
66
import java.util.Optional;
77

88
/**
99
* @author: caos321
1010
* @date: 31 October 2021 (Sunday)
11+
* @wiki: https://en.wikipedia.org/wiki/Depth-first_search
1112
*/
12-
public class DepthFirstSearch {
13+
public class DepthFirstSearch<T> {
1314

14-
static class Node {
15+
private final List<T> visited = new ArrayList<>();
1516

16-
private final String name;
17-
private final List<Node> subNodes;
18-
19-
public Node(final String name) {
20-
this.name = name;
21-
this.subNodes = new ArrayList<>();
22-
}
23-
24-
public Node(final String name, final List<Node> subNodes) {
25-
this.name = name;
26-
this.subNodes = subNodes;
27-
}
28-
29-
public String getName() {
30-
return name;
31-
}
32-
33-
public List<Node> getSubNodes() {
34-
return subNodes;
17+
public Optional<Node<T>> recursiveSearch(final Node<T> node, final Integer value) {
18+
if (node == null) {
19+
return Optional.empty();
3520
}
36-
}
37-
38-
public static Optional<Node> search(final Node node, final String name) {
39-
if (node.getName().equals(name)) {
21+
visited.add(node.getValue());
22+
if (node.getValue().equals(value)) {
4023
return Optional.of(node);
4124
}
4225

43-
return node.getSubNodes().stream().map(value -> search(value, name)).flatMap(Optional::stream).findAny();
44-
}
45-
46-
public static void assertThat(final Object actual, final Object expected) {
47-
if (!Objects.equals(actual, expected)) {
48-
throw new AssertionError(String.format("expected=%s but was actual=%s", expected, actual));
49-
}
26+
return node.getChildren().stream().map(v -> recursiveSearch(v, value)).flatMap(Optional::stream).findAny();
5027
}
5128

52-
public static void main(final String[] args) {
53-
final Node rootNode = new Node("A", List.of(new Node("B", List.of(new Node("D"), new Node("F", List.of(new Node("H"), new Node("I"))))), new Node("C", List.of(new Node("G"))), new Node("E")));
54-
55-
{
56-
final String expected = "I";
57-
58-
final Node result = search(rootNode, expected).orElseThrow(() -> new AssertionError("Node not found!"));
59-
60-
assertThat(result.getName(), expected);
61-
}
62-
63-
{
64-
final String expected = "G";
65-
66-
final Node result = search(rootNode, expected).orElseThrow(() -> new AssertionError("Node not found!"));
67-
68-
assertThat(result.getName(), expected);
69-
}
70-
71-
{
72-
final String expected = "E";
73-
74-
final Node result = search(rootNode, expected).orElseThrow(() -> new AssertionError("Node not found!"));
75-
76-
assertThat(result.getName(), expected);
77-
}
29+
public List<T> getVisited() {
30+
return visited;
7831
}
7932
}

‎src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java

Lines changed: 83 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -2,33 +2,101 @@
22

33
import static org.junit.jupiter.api.Assertions.*;
44

5+
import com.thealgorithms.datastructures.Node;
56
import java.util.List;
67
import java.util.Optional;
8+
import org.junit.jupiter.api.BeforeEach;
79
import org.junit.jupiter.api.Test;
810

9-
class BreadthFirstSearchTest {
11+
public class BreadthFirstSearchTest {
12+
private Node<String> root;
13+
private BreadthFirstSearch<String> bfs;
1014

11-
private static final DepthFirstSearch.Node rootNode = new DepthFirstSearch.Node("A",
12-
List.of(new DepthFirstSearch.Node("B", List.of(new DepthFirstSearch.Node("D"), new DepthFirstSearch.Node("F", List.of(new DepthFirstSearch.Node("H"), new DepthFirstSearch.Node("I"))))), new DepthFirstSearch.Node("C", List.of(new DepthFirstSearch.Node("G"))), new DepthFirstSearch.Node("E")));
15+
// Tree structure:
16+
//
17+
// A
18+
// / | \
19+
// B C D
20+
// / \
21+
// E F
22+
23+
@BeforeEach
24+
public void setUp() {
25+
// nodes declaration
26+
root = new Node<>("A");
27+
28+
var nodeB = new Node<>("B");
29+
var nodeC = new Node<>("C");
30+
var nodeD = new Node<>("D");
31+
32+
var nodeE = new Node<>("E");
33+
var nodeF = new Node<>("F");
34+
35+
// tree initialization
36+
root.addChild(nodeB);
37+
root.addChild(nodeC);
38+
root.addChild(nodeD);
39+
40+
nodeB.addChild(nodeE);
41+
nodeB.addChild(nodeF);
42+
43+
// create an instance to monitor the visited nodes
44+
bfs = new BreadthFirstSearch<>();
45+
}
1346

1447
@Test
15-
void searchI() {
16-
Optional<DepthFirstSearch.Node> Inode = BreadthFirstSearch.search(rootNode, "I");
17-
assertTrue(Inode.isPresent());
18-
assertEquals(Inode.get().getName(), "I");
48+
public void testSearchRoot() {
49+
String expectedValue = "A";
50+
List<String> expectedPath = List.of("A");
51+
52+
// check value
53+
Optional<Node<String>> value = bfs.search(root, expectedValue);
54+
assertEquals(expectedValue, value.orElse(new Node<>("")).getValue());
55+
56+
// check path
57+
assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
1958
}
2059

2160
@Test
22-
void searchG() {
23-
Optional<DepthFirstSearch.Node> Gnode = BreadthFirstSearch.search(rootNode, "G");
24-
assertTrue(Gnode.isPresent());
25-
assertEquals(Gnode.get().getName(), "G");
61+
public void testSearchF() {
62+
String expectedValue = "F";
63+
List<String> expectedPath = List.of("A", "B", "C", "D", "E", "F");
64+
65+
// check value
66+
Optional<Node<String>> value = Optional.of(bfs.search(root, expectedValue).orElse(new Node<>(null)));
67+
assertEquals(expectedValue, value.get().getValue());
68+
69+
// check path
70+
assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
2671
}
2772

2873
@Test
29-
void searchE() {
30-
Optional<DepthFirstSearch.Node> Enode = BreadthFirstSearch.search(rootNode, "E");
31-
assertTrue(Enode.isPresent());
32-
assertEquals(Enode.get().getName(), "E");
74+
void testSearchNull() {
75+
List<String> expectedPath = List.of("A", "B", "C", "D", "E", "F");
76+
Optional<Node<String>> node = bfs.search(root, null);
77+
78+
// check value
79+
assertTrue(node.isEmpty());
80+
81+
// check path
82+
assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
83+
}
84+
85+
@Test
86+
void testNullRoot() {
87+
var value = bfs.search(null, "B");
88+
assertTrue(value.isEmpty());
89+
}
90+
91+
@Test
92+
void testSearchValueThatNotExists() {
93+
List<String> expectedPath = List.of("A", "B", "C", "D", "E", "F");
94+
var value = bfs.search(root, "Z");
95+
96+
// check that the value is empty because it's not exists in the tree
97+
assertTrue(value.isEmpty());
98+
99+
// check path is the whole list
100+
assertArrayEquals(expectedPath.toArray(), bfs.getVisited().toArray());
33101
}
34102
}

0 commit comments

Comments
 (0)