liyafan82 commented on a change in pull request #1832: [CALCITE-3827] Reduce
the time complexity of finding in-edges of a vertex in the graph
URL: https://github.com/apache/calcite/pull/1832#discussion_r385524816
##########
File path:
core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java
##########
@@ -120,45 +132,62 @@ public E getEdge(V source, V target) {
}
public boolean removeEdge(V source, V target) {
- final VertexInfo<V, E> info = vertexMap.get(source);
- List<E> outEdges = info.outEdges;
+ // remove out edges
+ final VertexInfo<V, E> outInfo = vertexOutMap.get(source);
+ List<E> outEdges = outInfo.edges;
+ boolean outRemoved = false;
for (int i = 0, size = outEdges.size(); i < size; i++) {
E edge = outEdges.get(i);
if (edge.target.equals(target)) {
outEdges.remove(i);
edges.remove(edge);
- return true;
+ outRemoved = true;
+ break;
}
}
- return false;
+
+ // remove in edges
+ final VertexInfo<V, E> inInfo = vertexInMap.get(target);
+ List<E> inEdges = inInfo.edges;
+ boolean inRemoved = false;
+ for (int i = 0, size = inEdges.size(); i < size; i++) {
+ E edge = inEdges.get(i);
+ if (edge.source.equals(source)) {
+ inEdges.remove(i);
+ inRemoved = true;
+ break;
+ }
+ }
+ assert outRemoved == inRemoved;
+ return outRemoved;
}
public Set<V> vertexSet() {
- return vertexMap.keySet();
+ return vertexOutMap.keySet();
}
public void removeAllVertices(Collection<V> collection) {
- vertexMap.keySet().removeAll(collection);
- for (VertexInfo<V, E> info : vertexMap.values()) {
+ // remove out edges
+ vertexOutMap.keySet().removeAll(collection);
+ for (VertexInfo<V, E> info : vertexOutMap.values()) {
//noinspection SuspiciousMethodCalls
- info.outEdges.removeIf(next -> collection.contains(next.target));
+ info.edges.removeIf(next -> collection.contains(next.target));
+ }
+
+ // remove in edges
+ vertexInMap.keySet().removeAll(collection);
+ for (VertexInfo<V, E> info : vertexInMap.values()) {
+ //noinspection SuspiciousMethodCalls
+ info.edges.removeIf(next -> collection.contains(next.source));
}
}
public List<E> getOutwardEdges(V source) {
- return vertexMap.get(source).outEdges;
+ return vertexOutMap.get(source).edges;
}
public List<E> getInwardEdges(V target) {
- final ArrayList<E> list = new ArrayList<>();
- for (VertexInfo<V, E> info : vertexMap.values()) {
- for (E edge : info.outEdges) {
- if (edge.target.equals(target)) {
- list.add(edge);
- }
- }
- }
- return list;
+ return vertexInMap.get(target).edges;
Review comment:
I agree with you that the perf gain would be insignificant for small graphs.
We have a performance benchark on a relatively large graph (8-level binary
tree). Please see the comment aboe. Thank you.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
