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 bd121aa [CALCITE-4049] Improve the implementation of the
shortest-path algorithm
bd121aa is described below
commit bd121aa3a6d3b0314785a4c9141028b2ef252ebf
Author: liyafan82 <fan_li...@foxmail.com>
AuthorDate: Tue Jun 30 11:01:15 2020 +0800
[CALCITE-4049] Improve the implementation of the shortest-path algorithm
---
.../apache/calcite/plan/ConventionTraitDef.java | 6 +-
.../calcite/plan/RelOptMaterializations.java | 4 +-
.../java/org/apache/calcite/runtime/ConsList.java | 9 ++-
.../java/org/apache/calcite/util/graph/Graphs.java | 64 +++++++++-------------
.../calcite/util/graph/DirectedGraphTest.java | 30 ++++++----
5 files changed, 55 insertions(+), 58 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java
b/core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java
index 13a4ad9..d38d296 100644
--- a/core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java
+++ b/core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java
@@ -197,7 +197,7 @@ public class ConventionTraitDef extends
RelTraitDef<Convention> {
Convention toConvention) {
ConversionData conversionData = getConversionData(planner);
return fromConvention.canConvertConvention(toConvention)
- || conversionData.getShortestPath(fromConvention, toConvention) !=
null;
+ || conversionData.getShortestDistance(fromConvention, toConvention) !=
-1;
}
private ConversionData getConversionData(RelOptPlanner planner) {
@@ -234,10 +234,10 @@ public class ConventionTraitDef extends
RelTraitDef<Convention> {
return pathMap;
}
- public List<Convention> getShortestPath(
+ public int getShortestDistance(
Convention fromConvention,
Convention toConvention) {
- return getPathMap().getShortestPath(fromConvention, toConvention);
+ return getPathMap().getShortestDistance(fromConvention, toConvention);
}
}
}
diff --git
a/core/src/main/java/org/apache/calcite/plan/RelOptMaterializations.java
b/core/src/main/java/org/apache/calcite/plan/RelOptMaterializations.java
index d06ec2b..eb15bf0 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptMaterializations.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptMaterializations.java
@@ -254,8 +254,8 @@ public abstract class RelOptMaterializations {
Set<RelOptTable> usedTables,
Graphs.FrozenGraph<List<String>, DefaultEdge> usesGraph) {
for (RelOptTable queryTable : usedTables) {
- if (usesGraph.getShortestPath(queryTable.getQualifiedName(),
qualifiedName)
- != null) {
+ if (usesGraph.getShortestDistance(queryTable.getQualifiedName(),
qualifiedName)
+ != -1) {
return true;
}
}
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 b212626..445cf7e 100644
--- a/core/src/main/java/org/apache/calcite/runtime/ConsList.java
+++ b/core/src/main/java/org/apache/calcite/runtime/ConsList.java
@@ -33,7 +33,6 @@ 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.
@@ -52,7 +51,6 @@ 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) {
@@ -68,7 +66,12 @@ public class ConsList<E> extends AbstractImmutableList<E> {
}
public int size() {
- return size;
+ int s = 1;
+ for (ConsList c = this;; c = (ConsList) c.rest, ++s) {
+ if (!(c.rest instanceof ConsList)) {
+ return s + c.rest.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 2aaebd1..e731e17 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
@@ -22,14 +22,13 @@ import com.google.common.collect.ImmutableList;
import java.util.AbstractList;
import java.util.ArrayList;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
-import static org.apache.calcite.util.Static.cons;
-
/**
* Miscellaneous graph utilities.
*/
@@ -56,42 +55,40 @@ public class Graphs {
public static <V, E extends DefaultEdge> FrozenGraph<V, E> makeImmutable(
DirectedGraph<V, E> graph) {
DefaultDirectedGraph<V, E> graph1 = (DefaultDirectedGraph<V, E>) graph;
- Map<Pair<V, V>, List<V>> shortestPaths = new HashMap<>();
+ Map<Pair<V, V>, int[]> shortestDistances = new HashMap<>();
for (DefaultDirectedGraph.VertexInfo<V, E> arc
: graph1.vertexMap.values()) {
for (E edge : arc.outEdges) {
final V source = graph1.source(edge);
final V target = graph1.target(edge);
- shortestPaths.put(Pair.of(source, target),
- ImmutableList.of(source, target));
+ shortestDistances.put(Pair.of(source, target), new int[] {1});
}
}
while (true) {
// Take a copy of the map's keys to avoid
// ConcurrentModificationExceptions.
final List<Pair<V, V>> previous =
- ImmutableList.copyOf(shortestPaths.keySet());
- int changeCount = 0;
+ ImmutableList.copyOf(shortestDistances.keySet());
+ boolean changed = false;
for (E edge : graph.edgeSet()) {
for (Pair<V, V> edge2 : previous) {
if (edge.target.equals(edge2.left)) {
final Pair<V, V> key = Pair.of(graph1.source(edge), edge2.right);
- List<V> bestPath = shortestPaths.get(key);
- List<V> arc2Path = shortestPaths.get(edge2);
- if ((bestPath == null)
- || (bestPath.size() > (arc2Path.size() + 1))) {
- shortestPaths.put(key,
- cons(graph1.source(edge), arc2Path));
- changeCount++;
+ int[] bestDistance = shortestDistances.get(key);
+ int[] arc2Distance = shortestDistances.get(edge2);
+ if ((bestDistance == null)
+ || (bestDistance[0] > (arc2Distance[0] + 1))) {
+ shortestDistances.put(key, new int[] {arc2Distance[0] + 1});
+ changed = true;
}
}
}
}
- if (changeCount == 0) {
+ if (!changed) {
break;
}
}
- return new FrozenGraph<>(graph1, shortestPaths);
+ return new FrozenGraph<>(graph1, shortestDistances);
}
/**
@@ -102,39 +99,29 @@ public class Graphs {
*/
public static class FrozenGraph<V, E extends DefaultEdge> {
private final DefaultDirectedGraph<V, E> graph;
- private final Map<Pair<V, V>, List<V>> shortestPaths;
+ private final Map<Pair<V, V>, int[]> shortestDistances;
/** Creates a frozen graph as a copy of another graph. */
FrozenGraph(DefaultDirectedGraph<V, E> graph,
- Map<Pair<V, V>, List<V>> shortestPaths) {
+ Map<Pair<V, V>, int[]> shortestDistances) {
this.graph = graph;
- this.shortestPaths = shortestPaths;
+ this.shortestDistances = shortestDistances;
}
/**
- * Returns an iterator of all paths between two nodes, shortest first.
+ * Returns an iterator of all paths between two nodes,
+ * in non-decreasing order of path lengths.
*
* <p>The current implementation is not optimal.</p>
*/
public List<List<V>> getPaths(V from, V to) {
List<List<V>> list = new ArrayList<>();
- findPaths(from, to, list);
- return list;
- }
-
- /**
- * Returns the shortest path between two points, null if there is no path.
- *
- * @param from From
- * @param to To
- *
- * @return A list of arcs, null if there is no path.
- */
- public List<V> getShortestPath(V from, V to) {
if (from.equals(to)) {
- return ImmutableList.of();
+ list.add(ImmutableList.of(from));
}
- return shortestPaths.get(Pair.of(from, to));
+ findPaths(from, to, list);
+ list.sort(Comparator.comparingInt(List::size));
+ return list;
}
/**
@@ -147,13 +134,12 @@ public class Graphs {
if (from.equals(to)) {
return 0;
}
- List<V> path = shortestPaths.get(Pair.of(from, to));
- return path == null ? -1 : path.size() - 1;
+ int[] distance = shortestDistances.get(Pair.of(from, to));
+ return distance == null ? -1 : distance[0];
}
private void findPaths(V from, V to, List<List<V>> list) {
- final List<V> shortestPath = shortestPaths.get(Pair.of(from, to));
- if (shortestPath == null) {
+ if (getShortestDistance(from, to) == -1) {
return;
}
// final E edge = graph.getEdge(from, to);
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 87a4f4e..c98330e 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
@@ -64,14 +64,21 @@ class DirectedGraphTest {
g.addEdge("B", "D");
assertEquals("[A, B, D]", shortestPath(g, "A", "D").toString());
assertNull(shortestPath(g, "A", "E"), "There is no path from A to E");
- assertEquals("[]", shortestPath(g, "D", "D").toString());
+ assertEquals("[D]", shortestPath(g, "D", "D").toString());
assertNull(shortestPath(g, "X", "A"), "Node X is not in the graph");
- assertEquals("[[A, B, C, D], [A, B, D]]", paths(g, "A", "D").toString());
+ assertEquals("[[A, B, D], [A, B, C, D]]", paths(g, "A", "D").toString());
}
private <V> List<V> shortestPath(DirectedGraph<V, DefaultEdge> g,
V source, V target) {
- return Graphs.makeImmutable(g).getShortestPath(source, target);
+ List<List<V>> paths = Graphs.makeImmutable(g).getPaths(source, target);
+ return paths.isEmpty() ? null : paths.get(0);
+ }
+
+ private <V> List<V> shortestPath(Graphs.FrozenGraph<V, DefaultEdge> g,
+ V source, V target) {
+ List<List<V>> paths = g.getPaths(source, target);
+ return paths.isEmpty() ? null : paths.get(0);
}
private <V> List<List<V>> paths(DirectedGraph<V, DefaultEdge> g,
@@ -217,15 +224,16 @@ class DirectedGraphTest {
final DefaultDirectedGraph<String, DefaultEdge> graph = createDag1();
final Graphs.FrozenGraph<String, DefaultEdge> frozenGraph =
Graphs.makeImmutable(graph);
- assertEquals("[A, B]", frozenGraph.getShortestPath("A", "B").toString());
+ assertEquals("[A, B]", shortestPath(frozenGraph, "A", "B").toString());
assertEquals("[[A, B]]", frozenGraph.getPaths("A", "B").toString());
- assertEquals("[A, D, E]", frozenGraph.getShortestPath("A",
"E").toString());
- assertEquals("[[A, B, C, E], [A, D, E]]",
+ assertEquals("[A, D, E]", shortestPath(frozenGraph, "A", "E").toString());
+ assertEquals("[[A, D, E], [A, B, C, E]]",
frozenGraph.getPaths("A", "E").toString());
- assertNull(frozenGraph.getShortestPath("B", "A"));
- assertNull(frozenGraph.getShortestPath("D", "C"));
+ assertNull(shortestPath(frozenGraph, "B", "A"));
+
+ assertNull(shortestPath(frozenGraph, "D", "C"));
assertEquals("[[D, E]]", frozenGraph.getPaths("D", "E").toString());
- assertEquals("[D, E]", frozenGraph.getShortestPath("D", "E").toString());
+ assertEquals("[D, E]", shortestPath(frozenGraph, "D", "E").toString());
}
@Test void testDistances() {
@@ -355,9 +363,9 @@ class DirectedGraphTest {
g.addEdge("B", "D", 1);
assertEquals("[A, B, D]", shortestPath(g, "A", "D").toString());
assertNull(shortestPath(g, "A", "E"), "There is no path from A to E");
- assertEquals("[]", shortestPath(g, "D", "D").toString());
+ assertEquals("[D]", shortestPath(g, "D", "D").toString());
assertNull(shortestPath(g, "X", "A"), "Node X is not in the graph");
- assertEquals("[[A, B, C, D], [A, B, D]]", paths(g, "A", "D").toString());
+ assertEquals("[[A, B, D], [A, B, C, D]]", paths(g, "A", "D").toString());
assertThat(g.addVertex("B"), is(false));
assertThat(Iterables.size(g.getEdges("A", "B")), is(1));
