You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by ru...@apache.org on 2020/06/09 07:57:29 UTC
[calcite] branch master updated: [CALCITE-4049] Reduce the time
complexity of getting shortest distances
This is an automated email from the ASF dual-hosted git repository.
rubenql pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/master by this push:
new f9e8413 [CALCITE-4049] Reduce the time complexity of getting shortest distances
f9e8413 is described below
commit f9e8413b46f4c648736b529a55e25b57ab5dee74
Author: liyafan82 <fa...@foxmail.com>
AuthorDate: Mon Jun 8 14:52:21 2020 +0800
[CALCITE-4049] Reduce the time complexity of getting shortest distances
---
.../java/org/apache/calcite/runtime/ConsList.java | 9 ++---
.../java/org/apache/calcite/util/graph/Graphs.java | 14 +++++++
.../calcite/util/graph/DirectedGraphTest.java | 47 +++++++++++++++++-----
3 files changed, 53 insertions(+), 17 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/runtime/ConsList.java b/core/src/main/java/org/apache/calcite/runtime/ConsList.java
index 445cf7e..b212626 100644
--- a/core/src/main/java/org/apache/calcite/runtime/ConsList.java
+++ b/core/src/main/java/org/apache/calcite/runtime/ConsList.java
@@ -33,6 +33,7 @@ import javax.annotation.Nonnull;
public class ConsList<E> extends AbstractImmutableList<E> {
private final E first;
private final List<E> rest;
+ private final int size;
/** Creates a ConsList.
* It consists of an element pre-pended to another list.
@@ -51,6 +52,7 @@ public class ConsList<E> extends AbstractImmutableList<E> {
private ConsList(E first, List<E> rest) {
this.first = first;
this.rest = rest;
+ this.size = 1 + rest.size();
}
public E get(int index) {
@@ -66,12 +68,7 @@ public class ConsList<E> extends AbstractImmutableList<E> {
}
public int size() {
- int s = 1;
- for (ConsList c = this;; c = (ConsList) c.rest, ++s) {
- if (!(c.rest instanceof ConsList)) {
- return s + c.rest.size();
- }
- }
+ return size;
}
@Override public int hashCode() {
diff --git a/core/src/main/java/org/apache/calcite/util/graph/Graphs.java b/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
index 822004d..2aaebd1 100644
--- a/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
+++ b/core/src/main/java/org/apache/calcite/util/graph/Graphs.java
@@ -137,6 +137,20 @@ public class Graphs {
return shortestPaths.get(Pair.of(from, to));
}
+ /**
+ * Returns the shortest distance between two points, -1, if there is no path.
+ * @param from From
+ * @param to To
+ * @return The shortest distance, -1, if there is no path.
+ */
+ public int getShortestDistance(V from, V to) {
+ if (from.equals(to)) {
+ return 0;
+ }
+ List<V> path = shortestPaths.get(Pair.of(from, to));
+ return path == null ? -1 : path.size() - 1;
+ }
+
private void findPaths(V from, V to, List<List<V>> list) {
final List<V> shortestPath = shortestPaths.get(Pair.of(from, to));
if (shortestPath == null) {
diff --git a/core/src/test/java/org/apache/calcite/util/graph/DirectedGraphTest.java b/core/src/test/java/org/apache/calcite/util/graph/DirectedGraphTest.java
index b1d612c..87a4f4e 100644
--- a/core/src/test/java/org/apache/calcite/util/graph/DirectedGraphTest.java
+++ b/core/src/test/java/org/apache/calcite/util/graph/DirectedGraphTest.java
@@ -161,9 +161,14 @@ class DirectedGraphTest {
}
private DefaultDirectedGraph<String, DefaultEdge> createDag() {
- // A - B - C - D
- // \ /
- // +- E - F
+ // D F
+ // ^ ^
+ // | |
+ // C <------ +
+ // ^ |
+ // | |
+ // | |
+ // B <- A -> E
final DefaultDirectedGraph<String, DefaultEdge> graph =
DefaultDirectedGraph.create();
graph.addVertex("A");
@@ -181,14 +186,15 @@ class DirectedGraphTest {
return graph;
}
- /** Unit test for
- * {@link org.apache.calcite.util.graph.Graphs.FrozenGraph}. */
- @Test void testPaths() {
- // B -> C
- // / \
- // A E
- // \ /
- // D -->
+ private DefaultDirectedGraph<String, DefaultEdge> createDag1() {
+ // +--> E <--+
+ // | |
+ // C |
+ // ^ D
+ // | ^
+ // | |
+ // | |
+ // B <-- A --+
final DefaultDirectedGraph<String, DefaultEdge> graph =
DefaultDirectedGraph.create();
graph.addVertex("A");
@@ -202,6 +208,13 @@ class DirectedGraphTest {
graph.addEdge("A", "D");
graph.addEdge("D", "E");
graph.addEdge("C", "E");
+ return graph;
+ }
+
+ /** Unit test for
+ * {@link org.apache.calcite.util.graph.Graphs.FrozenGraph}. */
+ @Test void testPaths() {
+ final DefaultDirectedGraph<String, DefaultEdge> graph = createDag1();
final Graphs.FrozenGraph<String, DefaultEdge> frozenGraph =
Graphs.makeImmutable(graph);
assertEquals("[A, B]", frozenGraph.getShortestPath("A", "B").toString());
@@ -215,6 +228,18 @@ class DirectedGraphTest {
assertEquals("[D, E]", frozenGraph.getShortestPath("D", "E").toString());
}
+ @Test void testDistances() {
+ final DefaultDirectedGraph<String, DefaultEdge> graph = createDag1();
+ final Graphs.FrozenGraph<String, DefaultEdge> frozenGraph =
+ Graphs.makeImmutable(graph);
+ assertEquals(1, frozenGraph.getShortestDistance("A", "B"));
+ assertEquals(2, frozenGraph.getShortestDistance("A", "E"));
+ assertEquals(-1, frozenGraph.getShortestDistance("B", "A"));
+ assertEquals(-1, frozenGraph.getShortestDistance("D", "C"));
+ assertEquals(1, frozenGraph.getShortestDistance("D", "E"));
+ assertEquals(0, frozenGraph.getShortestDistance("B", "B"));
+ }
+
/** Unit test for {@link org.apache.calcite.util.graph.CycleDetector}. */
@Test void testCycleDetection() {
// A - B - C - D