-
Notifications
You must be signed in to change notification settings - Fork 1
/
BFSVisit.java
139 lines (123 loc) · 6.95 KB
/
BFSVisit.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package org.hit.internetprogramming.eoh.server.graph.algorithm;
import lombok.NonNull;
import org.hit.internetprogramming.eoh.common.graph.IGraph;
import java.util.*;
/**
* A class that implements BFS algorithm in order to find shortest paths in a graph.
*
* @param <V> Type of elements in an {@link IGraph} (We use the {@link org.hit.internetprogramming.eoh.common.mat.Index} class)
* @author Haim Adrian
* @since 10-Jul-21
*/
public class BFSVisit<V> implements ShortestPathAlgorithm<V> {
/**
* A queue we are using during the BFS algorithm, to traverse the graph.
*/
private final ThreadLocal<Deque<V>> workingQueue = ThreadLocal.withInitial(ArrayDeque::new);
/**
* A map between visited vertices and their info. (distance, parents)
*/
private final ThreadLocal<Map<V, VertexDistanceInfo<V>>> visitedVertices = ThreadLocal.withInitial(HashMap::new);
/**
* Algorithm:<br/>
* <pre>{@code
* Add root of the graph to the workingQueue
* While queue is not empty:
* currVertex = remove from queue.
* Invoke getReachableVertices on currVertex.
* For each reachableVertex do:
* If the distance[reachableVertex] is longer than distance[currVertex] + 1:
* Add reachableVertex to queue
* Update distance of reachableVertex to be distance[currVertex] + 1
* Clear previously stored parents of reachableVertex, and set currVertex as its parent
* Else if distance[reachableVertex] equals distance[currVertex] + 1:
* Add currVertex as additional parent of reachableVertex
* }</pre>
* @param graph The graph to traverse
* @return Vertex info about all vertices we have visited while traversing from root. (Not necessarily all vertices in the graph)
* @see #traverse(IGraph, Object)
*/
@Override
public Map<V, VertexDistanceInfo<V>> traverse(@NonNull IGraph<V> graph) {
return traverse(graph, null);
}
/**
* This method differs from {@link #traverse(IGraph)} by defining a vertex to stop searching from.<br/>
* This is a destination vertex to avoid of running a full BFS, and just run it until some target.
* Algorithm:<br/>
* <pre>{@code
* Add root of the graph to the workingQueue
* While queue is not empty:
* currVertex = remove from queue.
* Invoke getReachableVertices on currVertex.
* For each reachableVertex do:
* If the distance[reachableVertex] is longer than distance[currVertex] + 1:
* Add reachableVertex to queue
* Update distance of reachableVertex to be distance[currVertex] + 1
* Clear previously stored parents of reachableVertex, and set currVertex as its parent
* Else if distance[reachableVertex] equals distance[currVertex] + 1:
* Add currVertex as additional parent of reachableVertex
* }</pre>
* @param graph The graph to traverse
* @param destination A destination vertex, such that when we reach it we stop traversing. May be {@code null}. When null, it works the same as {@link #traverse(IGraph)}.
* @return Vertex info about all vertices we have visited while traversing from root. (Not necessarily all vertices in the graph)
* @see #traverse(IGraph)
*/
@Override
public Map<V, VertexDistanceInfo<V>> traverse(@NonNull IGraph<V> graph, V destination) {
Deque<V> workingQueue = this.workingQueue.get();
Map<V, VertexDistanceInfo<V>> visitedVertices = this.visitedVertices.get();
workingQueue.clear();
visitedVertices.clear();
V currVertex = graph.getRoot();
workingQueue.add(currVertex);
visitedVertices.computeIfAbsent(currVertex, VertexDistanceInfo::new).setDistance(0);
// As long as we haven't reached nowhere (We scanned all reachable vertices)
while (!workingQueue.isEmpty()) {
currVertex = workingQueue.remove();
// In case we have reached to destination, stop traversing the graph.
if (currVertex.equals(destination)) {
// This will break the outer loop in an ordinary way
workingQueue.clear();
} else {
Collection<V> reachableVertices = graph.getReachableVertices(currVertex);
VertexDistanceInfo<V> parentVertexInfo = visitedVertices.get(currVertex);
// Check if we have reached to destination, to avoid of adding other neighbors.
if ((destination != null) && reachableVertices.contains(destination)) {
updateVisitedVertexIfNecessary(destination, currVertex, parentVertexInfo, workingQueue, visitedVertices);
} else {
for (V currReachableVertex : reachableVertices) {
updateVisitedVertexIfNecessary(currReachableVertex, currVertex, parentVertexInfo, workingQueue, visitedVertices);
}
}
}
}
return visitedVertices;
}
/**
* A helper method extracted from {@link #traverse(IGraph, Object)}, to avoid of duplicating vertex handling
* code. In this method we check if a shorter path was found, to update lengths and parents of a vertex, thus
* keeping the shortest paths only.
* @param vertex The vertex to test
* @param parentVertex Optional parent of the vertex we test
* @param parentVertexInfo Vertex info to avoid of looking up is visitedVertices when running inside a loop
* @param workingQueue A queue to insert into when the vertex distance got updated with a shorter distance
* @param visitedVertices Map of previously visited vertices, to get their info
*/
private void updateVisitedVertexIfNecessary(V vertex, V parentVertex, VertexDistanceInfo<V> parentVertexInfo, Deque<V> workingQueue, Map<V, VertexDistanceInfo<V>> visitedVertices) {
VertexDistanceInfo<V> vertexInfo = visitedVertices.computeIfAbsent(vertex, VertexDistanceInfo::new);
// In case the path from parent is shorter than the computed one, keep the shorter path and add that
// vertex to the queue so we will continue traversing until we reach destination.
if (vertexInfo.getDistance() > (parentVertexInfo.getDistance() + 1)) {
vertexInfo.setDistance(parentVertexInfo.getDistance() + 1);
workingQueue.add(vertex);
// Clear old (longer) parents. We will add the new parent down below.
vertexInfo.getParents().clear();
}
// When the distance equals, save current vertex as additional parent.
// We might get here after the previous if as well, as we've updated the distance.
if (vertexInfo.getDistance() == (parentVertexInfo.getDistance() + 1)) {
vertexInfo.getParents().add(parentVertex);
}
}
}